apuntes inv de operaciones

INTRODUCCIN

MODELO DE OPTIMIZACIN

Estn diseados para proporcionar los "mejores" valores de diseo del sistema y las variables de

poltica operativa - valores que conduzcan a los ms altos niveles de rendimiento del sistema.

Conformados por:

Funciones objetivo

Variables de decisin

Restricciones

CLASIFICACIN

1. Estticos y Dinmicos: Sucesin de decisiones para periodos mltiples.

2. Lineales y no lineales. Las variables de decisin aparecen en la funcin objetivo y

restricciones, estn multiplicadas por constantes y acomodadas en forma de suma.

3. Modelo enteros y no enteros: Una o ms variables de decisin son enteras o

fraccionarias.

4. Modelo determinstico y estocstico: Se conoce con certeza el valor de la funcin

objetivo, cumpliendo o no las restricciones.

MTODOS

1. Programacin lineal: Planeacin de las actividades para obtener un resultado ptimo

2. Programacin entera: Los mtodos de ramificar y acotar encuentran la solucin ptima

para un problema de programacin entera.

3. Mtodo de transporte: Analiza los costos de transporte tanto de la materia prima como

de los productos terminados

4. Mtodo de asignacin: El objetivo es asignar los trabajos a las mquinas (un trabajo por

mquina) con el costo mnimo total.

5. Programacin no lineal: Los problemas no lineales se caracterizan por tener relaciones no

lineales; es decir, no existe una relacin directa y proporcional entre las variables que

intervienen.

6. Mtodo de sustitucin directa: Es un mtodo en donde la funcin objetivo est sujeta a

una o dos restricciones de igualdad lineales o no lineales, con en la cual se resuelve

explcitamente una variable y dicha variable se elimina en la formulacin del problema.

En la teora puede ser fcil de aplicar, sin embargo, no es conveniente su uso desde el

punto de vista prctico. La razn para esto es que las restricciones sern no lineales para la

mayora de los problemas prcticos, y muchas veces son muy complicados de resolver.

7. Programacin Cuadrtica: Es un mtodo usado para determinar la cartera de inversiones

ptima de un conjunto dado. Este tipo de problemas de optimizacin se caracterizan por

que la funcin objetivo de n variables es minimizado sujeto a m restricciones de

desigualdades o igualdades lineales.

8. Mtodo de LaGrange: Este mtodo se usa para resolver PNL en los que las restricciones,

son las restricciones igualdades.

Normalmente se usa un factor o multiplicador para su resolucin. Tambin suele

presentarse en problemas con dos variables y una sola restriccin

9. Mtodo de Fibonacci: Mtodo iterativo irrestricto basado en la serie de Fibonacci. Es

considerado uno de los mtodos ms exactos. Es usado para encontrar el mnimo de una

funcin univariable, aunque la funcin no sea continua.

Programacin Lineal Consiste en optimizar una funcin lineal, denominada funcin objetivo que esta sujeta a una serie

de restricciones. Se vern 3 mtodos para resolver un problema de programacin lineal

MTODO GRFICO

El mtodo grfico se emplea para resolver problemas que presentan slo 2 variables de decisin.

El procedimiento consiste en trazar las ecuaciones de las restricciones en un eje de coordenadas

X1, X2 para tratar de identificar el rea de soluciones factibles (soluciones que cumplen con todas

las restricciones). La solucin ptima del problema se encuentra en uno de los vrtices de esta

rea de soluciones creada, por lo que se buscar en estos datos, el valor mnimo o mximo del

problema.

Clculos analticos para graficar el sistema de inecuaciones lineales, incluyendo la condicin de no

negatividad (NN [ ]), que nos indica que solamente trabajaremos en el primer

cuadrante del plano cartesiano, cuadrante donde X1 y X2 son positivas.

El valor de la funcin objetivo en cada una de las esquinas del rea de soluciones factible es:

La funcin objetivo se maximiza cuando y ;

Algoritmo Simplex

Algoritmo del mtodo simplex para un problema de maximizacin

1. Convierta el PL en una forma estndar.

2. Encuentre una solucin factible bsica (sfb), si es posible, a partir de la forma estndar.

3. Determinar si la sfb actual es ptima.

4. Si la sfb actual no es ptima, entonces se determina cul variable no bsica se debe

transformar en variable bsica y cul variable bsica se debe transformar en variable no

bsica con el objeto de hallar una nueva sfb.

5. Aplicar Operaciones de rengln (OER) para encontrar la nueva sfb. Regresar al paso 3.

La Dakota Furniture Company fabrica escritorios, mesas y sillas. Para la manufactura de cada

tipo de mueble se requiere madera y dos tipos de manos de obra calificada: acabado y carpintera.

La cantidad de recursos necesarios para elaborar cada tipo de muebles se proporciona en la tabla

1.

Se cuenta en la actualidad con 48 ft tabln de madera, 20 horas de acabado y 8 horas de

carpintera. Un escritorio se vende en 60 dlares, una mesa en 30 dlares y una silla en 20 dlares.

Dakota opina que la demanda de escritorios y sillas es ilimitada, pero cuando mucho se pueden

vender 5 mesas. Puesto que los recursos disponibles ya se compraron, Dakota quiere maximizar el

ingreso total.

Definimos las variables: x1, x2 y x3.

X1: Nmero de escritorios fabricados.

X2: Nmero de mesas fabricadas.

X3: Nmero de sillas fabricadas

Para comenzar con el paso dos, se eligen las variables bsicas (VB) y las variables no bsicas

(VNB). Quedando de la siguiente manera:

De esta manera obtenemos nuestra primera solucin factible (con x1, x2 y x3 igual a cero), pero no

ptima.

Variable bsica que sale:

VB x1 x2 x3 s1 s2 s3 s4 Solucin RMC

z -60 -30 -20 0 0 0 0 0

s1 8 6 1 1 0 0 0 48

s2 4 2 1,5 0 1 0 0 20

s3 2 1,5 0,5 0 0 1 0 8

s4 0 1 0 0 0 0 1 5

Para determinar la variable saliente se sigue la siguiente regla:

La restriccin con el cociente ms pequeo se denomina ganador de la prueba de cociente, este

indicar que variable bsica deber salir

Las operaciones que hacemos despus son:

1. Dividir toda la fila pivote entre el elemento pivote.

2. Para las dems filas se sigue la siguiente ecuacin:

La solucin ptima es:


z -60 -30 -20 0 0 0 0 0

s1 8 6 1 1 0 0 0 48 6

s2 4 2 1,5 0 1 0 0 20 5

s3 2 1,5 0,5 0 0 1 0 8 4

s4 0 1 0 0 0 0 1 5 -


z 0 15 -5 0 0 30 0 240

s1 0 0 -1 1 0 -4 0 16

s2 0 -1 0,5 0 1 -2 0 4

x1 1 0,75 0,25 0 0 0,5 0 4

s4 0 1 0 0 0 0 1 5


z 0 15 -5 0 0 30 0 240

s1 0 0 -1 1 0 -4 0 16 -16

s2 0 -1 0,5 0 1 -2 0 4 8

x1 1 0,75 0,25 0 0 0,5 0 4 16

s4 0 1 0 0 0 0 1 5 -


z 0 5 0 0 10 10 0 280s1 0 -2 0 1 2 -8 0 24 -16

x3 0 -2 1 0 2 -4 0 8 8

x1 1 1,25 0 0 -0,5 1,5 0 2 16

s4 0 1 0 0 0 0 1 5 -

Si el caso hubiese sido de minimizacin, tomamos como referencia que todos los coeficientes de la

fila cero sean negativos.

Mtodo de 2 fases o Ms

En la fase 1 se agregan variables artificiales y se resuelven por mtodo simplex normal.

En la fase 2 se quitan las variables artificiales y se vuelve a utilizar el mtodo simplex.

z 280

x1 2

x2 0

x3 8

Programacin Lineal

(Problemas de ejercitacin)

1. La SAVE IT COMPANY opera un centro de reciclado que recoge 4 tipos de materiales de desecho

slido y lo trata para amalgamarlo en un producto comercializable. (El tratamiento y el

amalgamiento son dos procesos diferentes). Se puede hacer tres grados diferentes de este

producto (Vea la Tabla 1), segn la mezcla de materiales que se use. Aunque existe alguna

flexibilidad para esta mezcla en cado grado, los estndares de calidad especifican una cantidad

mnima y mxima para la proporcin de los materiales permitidos en ese grado. (Esta proporcin

es el peso del material expresado como un personaje del peso total del producto de ese grado).

Para los dos grados ms altos se especifica un porcentaje fijo de uno de los materiales. Estas

especificaciones se dan en la Tabla 1 junto con el costo de amalgamado y el precio de venta de

cada producto.

El centro de reciclado recoge los materiales de desecho slido de ciertas fuentes habituales por lo

que casi siempre puede mantener una tasa de produccin estable para tratarlos. En la Tabla 2 se

dan las cantidades disponibles para la recoleccin y tratamiento semanal, al igual que el costo de

proceso para cada tipo de material.

La Sav-It Co. Es propiedad de Green Earth, una organizacin dedicada a asuntos ecolgicos. Esta

organizacin ha logrado contribuciones y apoyos por la cantidad de $30,000 semanales, que

deben usarse slo para cubrir el costo del tratamiento completo de los desechos slidos. El

consejo directivo Green Earth ha girado instrucciones a la administracin de la Save-It para que

divida este dinero entre los materiales de manera tal que se recolecte y se trate al menos la mitad

de la cantidad disponible de cada material. Esta restriccin se muestra en la Tabla 2.

Dentro de las restricciones especificas en las Tablas 1 y 2, la administracin desea determinar la

cantidad que debe producir de cada grado y la mezcla exacto de materiales que usar para cada

uno, de manera que maximice la ganancia semanal neta (ingresos totales por ventas, menos costo

total de amalgamiento).

Solucin

Variable de decisin

Xij= proporcin del material j usado por semana en el producto de grado i producido por semana

(i=A=1, B=2, C=3; j=1, 2, 3, 4)

Funcin objetivo

Max z=Costos - Utilidades

Max z=8.5(X11+ X12+ X13+ X14)+ 7.0(X21+ X22+ X23+ X24)+ 5.5(X31+ X32+ X33+ X34)-3.0 (X11+ X12+ X13+

X14)- 2.5(X21+ X22+ X23+ X24)- 2.0(X31+ X32+ X33+ X34)

Restricciones

Especicificaciones de la mezcla

Disponibilidad de materiales

Restricciones sobre las cantidades tratadas

Restricciones sobre costos de tratamiento

3.0 (X11+ X21+ X31)+ 6.0(X12+ X22+ X32)+ 4.0(X13+ X23+ X33)+ 5.0 (X14+ X24+ X34)=30,000

Restricciones de no negatividad

N,N

La solucin en Lindo se muestra a continuacin:

2. Cierta empresa produce dos tipos de gasolinas, grado normal y grado extra, estas se producen

mezclando tres tipos de componentes de petrleo. La gasolina grado normal, puede venderse a

$0.50 de dlar por galn, y la de grado extra en $0.54 de dlar por galn.

Los compromisos actuales con los distribuidores requiere que se fabriquen cuando menos 10 000

galones de gasolina normal.

Los costos y ofertas de petrleo se muestran en las siguientes tablas:

Variable de decisin.

Funcin objetivo

Restricciones

Disponibilidad de componentes.

Requerimiento de gasolina normal.

Especificaciones para gasolina normal y extra.

3. Tecnologa Agrcola S.A. es una compaa fabricante de fertilizantes. El gerente desea planear la

combinacin de sus dos mezclas a fin de obtener la mayor de sus utilidades. Las mezclas son:

El mayorista comprara cualquier cantidad de ambas mezclas de fertilizante que la compaa pueda

fabricar. Esta dispuesto a pagar a $71.50 la tonelada de (5.5.10) y a $69 la tonelada de (5.10.5).

En este mes la disponibilidad y costos de materia prima son:

Hay un costo de $15 por tonelada por mezclado de fertilizantes.

Objetivo: Maximizar las utilidades


Funcin objetivo:

Restricciones

Corrida en lindo:

Mtodo de Ramificar y Acotar

Programacin Entera: Los programas lineales enteros son aquellos en los que algunas o

todas las variables estn restringidas a tener valores enteros (o discretos).

La empresa Telfa Corporation se dedica a la fabricacin de mesas y sillas. Para la fabricar una mesa

se requieren una hora de mano de obra y 9 pies de tabln de madera, en tanto que para una silla

se necesitan 1 hora de mano de obra y 5 pies de tabln de madera. En la actualidad, estn

disponibles 6 horas de mano de obra y 45 pies de tabln de madera al mes. Cada mesa contribuye

con 8 dlares a las utilidades y cada silla con 5 dlares. Formule y resuelva un PE para maximizar

las utilidades de Telfa .

Paso 1.- Definir las variables.

Paso 2.- Establecer funcin objetivo.

Max

(

) (

) (

) (

)

Paso 4.- Establecer Restricciones.

Restriccin de la madera

(

) (

) (

) (

)

Restriccin de mano de obra

(

) (

) (

) (

)

Si todas las variables de decisin asumieran valores enteros la solucin ptima del

problema de PL sera la solucin ptima del problema de PE.

Como no sucede lo antes mencionado en este caso se debe continuar al paso nmero 6.

Paso 6.-Dividir la regin factible de la relajacin del PL.

La solucin ptima del PL es

Como es maximizar, el valor ptimo no debe de ser mayor a 41.25

Se elige de modo arbitrario una variable fraccionaria de la solucin ptima del problema de PL

para generar dos zonas de posibles soluciones. En este caso se elige y a continuacin se

presentan 2 opciones diferentes.

Paso 7.-Se realiza un rbol (que es la representacin de todos los subproblemas que se

proponen).

Nodo: sub problema i (1, 2, 3.N)

Arco: Lnea que une los nodos

Restriccin: Se suma con el subproblema anterior

t = Indica el orden en el cual se resuelve el problema

S 2 Subproblema 1 + restriccin


A esto se le conoce como ramificacin sobre

Paso 8.- Escoger un subproblema y resolverlo

La solucin optima del subproblema 2 no ofreci una solucin de enteros nicamente por

lo cual se reptela metodologa del paso 6.

Paso 9.- Se repite la ramificacin sobre la variable fraccionaria


S 5 Subproblema 2 + restriccin 1

Paso 10.- Escoger un subproblema y resolverlo.

El subproblema 4 no es factible.

Al resolver el subproblema 5 se obtiene la solucin:

Z= 365/9

X1=40/9

X2=1

Como el valor de continua siendo fraccionario esta variable se vuelve a ramificar

Paso 11.- Escoger un subproblema y resolverlo.



Paso 12.- Escoger un subproblema y resolverlo

Para el Subproblema la solucin es:

Z= 37

X1=4

X2=1

Dado que los valores de la solucin son enteros, estos representan una solucin factible

para el problema de PE.

Ejemplos

Forme el rbol de ramificacin y acotamiento para el siguiente problema:

Sujeto a

0 y enteros

Se escoge a como la variable de ramificacin.

Se tienen dos nuevos PL: PL1 y PL2

PL1:

Sujeto a

0

PL2:

Sujeto a

0

An se puede hacer un PL3 ya que en el PL2 no se cumple que las variables sean

nmeros enteros, entonces:

Sujeto a

0

rbol de ramificacin y acotamiento

Min z= -5x1-8x2

St

X1+x2

Lo resolvemos obteniendo la siguiente solucin ptima: z0 = 41,25; x1 = 2,25 y x2 = 3,75

2. Notamos que las 2 variables son fraccionarias por lo que podemos tomar cualquiera de

ellas como variable de ramicacin. Escojamos la variable x2 para ramicar generndose

as los siguientes problemas:

Tenemos ahora que la lista est compuesta por 2 problemas pendientes: L={(P1),(P2)}. Sin

embargo, an no encontramos una solucin entera por lo que no actualizamos el

incumbente.

Resolviendo primero (P1), se tiene que z1 = 41; x1 = 1,8 y x2 = 4, que tampoco es

solucin entera por lo que ramicamos nuevamente por variable x1, dando origen a los

problemas:

Tenemos como problemas pendientes L={(P2),(P3),(P4)} y aun ninguna solucin entera.

Escogemos (P3) para ser resuelto obteniendo que es infactible. Esto signica que

eliminamos a (P3) sin ser ramicado.

Primera solucin entera: z5 = 37; x1 = 1 y x2 = 4 por lo que actualizamos el incumbente: z

= 37.

Ahora la lista es L=,(P2),(P6)-. Resolviendo (P6) se tiene que z6 = 40; x1 = 0 y x2 = 5,

que es una solucin entera mejor que la anterior por lo que actualizamos el incumbente:

z = 40.

Resolviendo nalmente el ultimo problema de la lista: (P2) se obtiene que z2 = 39; x1 =

3 y x2 = 3, que es una solucin entera peor que la del incumbente por lo cual no es

necesario ramicar.

Como no quedan problemas en la lista, hemos encontrado que el ptimo entero del

problema viene dado por z = 40; x 1 = 0 y x 2 = 5

Programacin entera binaria

La California Manufacturing Company est analizando su expansin mediante la

construccin de una nueva fbrica en Los Angeles, en San Francisco, o en ambas ciudades.

Tambin se piensa en construir, a los ms, un nuevo almacn; pero esta decisin est

restringida a la ciudad donde se construya la nueva fbrica.

A continuacin se muestran los datos para tomar la decisin, incluido el valor presente

neto de cada alternativa y el capital requerido para sus respectivas inversiones. El objetivo

es encontrar la combinacin factible de alternativas para maximizar el valor presente neto

total.

El objetivo es encontrar la combinacin factible de alternativas que maximice el valor

presente neto total.

Solucion:

Se trata de un modelo de programacin entera, en el que las variables de decisin tienen

la forma binaria [slo pueden tomar dos valores: xito (1) y fracaso (0) segn sea el caso]

{

Y la funcin objetivo es valor presente neto de estas decisiones.

Si se hace la inversin para la construccin de lo dado [ ], el VPN est dado en la

tabla anterior. Si no se hace [ ], el VPN es 0.

*VPN total+

st

1. .

2. La compaa quiere construir cuando mucho un almacn nuevo.

3. Las decisiones 3 y 4 dependen de la 1 y 2 [decisiones contingentes/condicionales]. La

compaa considerara la construccin de un almacn si la empresa nueva tambin estar

ah.

4. La condicin para que las variables de decisin sean binarias.

es binaria, para

Ramificacin. Al manejarse variables binarias, la forma ms sencilla de partir el conjunto

de soluciones factibles es fijar el valor de una variable. Hecho esto, el problema completo

se divide en dos sub-problemas. [En este caso, se fijar la variable ]

Acotamiento. Hay que obtener una cota que muestre qu tan buena puede ser la

solucin factible, resolviendo una soltura [aquella que elimina restricciones que hacen que

el problema sea difcil; en este caso son aquellas que hacen que las variables sean

enteras].

Problema Completo:

Soltura: Sustituir que es binaria, para por y para los

mismos valores de j.

Sub-problema 1 y Sub-problema 2:

Soltura: Sustituir que es binaria, para por y para los mismos

valores de j.

Una vez hecho el acotamiento, se resuelve el problema y los sub-problemas por mtodos

de programacin lineal

Sondeo. Es cuando un sub-problema ya no se toma en cuenta en base a ciertos

parmetros dados en el modelo . Un sub-problema se sondea si:

1. Su cota z*

2. Su soltura no tiene soluciones factibles

3. La solucin ptima es entera

A partir de este punto, se contina ramificando a partir del sub-problema 2, evaluando

cada una de las variables restantes y considerando los pasos anteriores, hasta llegar a una

solucin ptima.

Problemas de Transporte

Una compaa tiene cuatro enlatadoras que abastecen a cuatro almacenes y la gerencia

quiere determinar la programacin de envo de costo mnimo para su produccin mensual

de latas de tomate. La oferta de las enlatadoras, las demandas de los almacenes y los

costos de envo por caja de latas de tomate se muestran en la Tabla 1.

Minimizar

Z = 25 x11+ 35 x12 + 36 x13 + 60 x14 + 55 x21 + 30 x22 + 45 x23 + 38 x24 +

40 x31+50 x32 + 26 x33 + 65 x34 + 60 x41 + 40 x42 + 66 x43 + 27 x4

Variables

Z=costo a minimizar.

xij=cantidades de productos enviadas de cada centro de suministro a cada centro

de demanda.

y xij0 (i = 1,2,3,4; j = 1,2,3,4)

P2. Una compaa tiene 4 fabricas (F1, F2, F3, F4) que envan su produccin a 4 almacenes

(A1, A2, A3, A4). Los costos y capacidades de produccin, en cada una de las 4 fbricas son:

Las demandas mensuales del producto en cada uno de los 4 puntos de distribucin son:

Los costos del transporte, en $/unidad, entre las diversas combinaciones de fbricas y

almacenes son:

Formule un problema de programacin lineal para minimizar los costos de transporte y

produccin

Xij = Unidades de producto a enviar desde la fbrica i-sima (i=1, 2, 3, 4) al almacn j-

simo (j=1, 2, 3, 4)

Funcin objetivo:

Restricciones

Resolviendo en lindo

El entrenador de un equipo de natacin debe asignar competidore4s para la prueba de

200 metros de relevo combinado que irn a las Olimpiadas Juveniles. Como muchos de sus

mejores nadadores son rpidos en ms de una estilo, no es fcil decidir qu nadador

asignar a cada uno de los cuatro estilos. Los cinco mejores nadadores y sus mejores

tiempos (en segundos) en cada estilo son los siguientes:

El entrenador quiere determinar cmo asignar cuatro nadadores a los cuatro estilos de

nado para minimizar la suma de los mejores tiempos correspondientes.

a) Formule este problema como uno de asignacin

b) Obtenga una solucin ptima.

Solucion:

El nmero de asignados (cinco) debe ser igual al nmero de estilos (cuatro) as que se

introduce una asignacin ficticia (estilo) como Crol. El papel de esta asignacin es

proporcionar un estilo a la persona adicional. No se incurre en tiempos del estilo as que

sern ceros.


Funcin Objetivo

Minimizar

Restricciones:

Asignados Asignacin

No negatividad

Resolviendo en lindo:

GRADOS DE LIBERTAD

Los grados de libertad son un indicador para identificar los casos en los que probablemente el

problema de balance de materia no producir una solucin.

Redefiniendo:

(Composiciones o flujos)

Posibilidades:

Si , el problema puede resolverse

, problema subespeficado (puede realizarse una optimizacin al proceso)

, no hay solucin

Relacin de ecuaciones

Las variables desconocidas de las corrientes de proceso pueden derivarse de lo siguiente:

-Balance de materia

-Balance de energa

-Especificaciones del proceso

-Propiedades y leyes fsicas

-Restricciones fsicas (fracciones molares)

-Relaciones estequiomtricas

BIBLIOGRAFA

Thomas F. Edgar, David M. Himmelblau; OPTIMIZATION OF CHEMICAL PROCESSES;Ed

McGraw-Hill; EUA 2001; 2da ed.

Wayne L. Winston; INVESTIGACIN DE OPERACIONES, Algoritmos y Aplicaciones; Ed.

Thomson; Mxico 2005; 4 ed.

N.V.S. Raju;OPTIMIZATION METHODS FOR ENGINEERS

apuntes inv de operaciones

Documents