INSTITUTO TECNOLGICO
DE NUEVO LEON
Ingeniera en Gestin Empresarial
Materia: Investigacin de Operaciones
Investigacin
Unidad #2
Nombre:
Numero de control:
Yesenia Eguren
13480380
Jessica Hernndez
13480459
Jessica Contreras
13480386
Rmulo Gaytn
13480416
Nelson Gonzales
13480354
Catedrtica: Alma Judith de la Garza Inzunza
Guadalupe, Nuevo Len a 26 de
Febrero del 2015
Mtodo Dual
Simplex
Este mtodo se aplica a problemas ptimos pero infactibles. En
este caso, las restricciones se expresan en forma cannica
(restricciones <).
La funcin objetivo puede estar en la forma de maximizacin o
de minimizacin. Despus de agregar las variables de holgura y
de poner el problema en la tabla, si algn elemento de la parte
derecha es negativo y si la condicin de optimidad est
satisfecha, el problema puede resolverse por el mtodo dual
simplex. Note que un elemento negativo en el lado derecho
significa que el problema comienza ptimo pero infactible como
se requiere en el mtodo dual simplex. En la iteracin donde la
solucin bsica llega a ser factible esta ser la solucin ptima del
problema.
CONDICION DE FACTIBILIDAD.
La variable que sale es la variable bsica que tiene el valor
ms negativo (los empates se rompen arbitrariamente si
todas las variables bsicas son no negativas, el proceso
termina y esta ltima tabla es la solucin ptima factible).
CONDICION DE OPTIMIDAD.
La variable que entra se elige entre las variables no bsicas
como sigue. Tome los cocientes de los coeficientes de la
funcin objetivo entre los coeficientes correspondientes a la
ecuacin asociada a la variable que sale. Ignore los cocientes
asociados a denominadores positivos o cero. La variable que
entra es aquella con el cociente ms pequeo si el problema
es de minimizar o el valor absoluto ms pequeo si el
problema es de maximizacin (rompa los empates
arbitrariamente). Si los denominadores son ceros o positivos
el problema no tiene ninguna solucin factible.
Ejemplo
Min. Z = 4X1 + 12X2 + 18X3
X1 +
3X3 3
2X2 + 2X3 5
X1, X2, X3 0
SOLUCIN
PASO 1:
Convertir el problema de minimizacin en uno de
maximizacin. La funcin objetivo se multiplica por -1
Max. Z = - 4X1 - 12X2 - 18X3
Las restricciones se multiplican por -1
- X1
- 3X3 -3
-2X2 - 2X3 -5
X1, X2, X3 0
PASO 2:
Se convierten las inecuaciones en ecuaciones.
Z + 4X1 + 12X2 + 18X3 = 0
X1 -
3X3 + S1 = -3
2X2 - 2X3 + S2 = -5
PASO 3:
Se determinan las variables bsicas y no bsicas.
Bsicas: S1 y S2
No Bsicas: X1, X2 y X3
PASO 4:
Elaborar la tabla inicial del simplex
Variable
Bsica
Variables
Solucin
X1
X2
X3
S1
S2
S1
-1
-3
-3
S2
-2
-2
-5
12
18
PASO 5:
Determinar la variable que sale (fila pivote)
Es el nmero ms negativo de la solucin de las restricciones = fila
de S2
PASO 6:
Determinar la variable que entra (columna pivote)
Razn = Coeficiente de Z / coeficiente fila
pivote.
Razn Mayor = Columna X2 (-12 / 2)
Variable
Bsica
S1
S2
Z
razn
Variables
Solucin
X1
X2
X3
S1
S2
-1
0
4
-
0
-2
12
-6
-3
-2
18
-9
1
0
0
-
0
1
0
0
-3
-5
0
PASO 7:
Elaborar la nueva tabla del simplex
Nueva fila pivote = Fila pivote / elemento pivote
0 -2 -2 0 1 -5 Fila Pivote
-2 -2 -2 -2 -2 -2 Elemento Pivote
0 1 1 0 -0,5 2,5 Nueva Fila Pivote
Nuevas filas = fila anterior - coeficiente de la columna pivote x nueva fila pivote.
Nueva Fila (S1)
-1
-3
-3
fila anterior
coeficiente
0 -0,5 2,5 nueva fila pivote
-1
-3 1
-3
nueva fila
Nueva Fila (Z)
4
12
18
12
12
12 12 12 12
0 -0,5
0
0
2,5
6 -30
Nueva Tabla del Simplex
Variable
Bsica
S1
X2
Z
razn
Variables
Solucin
X1
X2
X3
S1
S2
-1
0
4
-4
0
-2
12
-
-3
1
6
-2
1
0
0
0
0
-1
6
-
-3
2.5
-30
Se realizan nuevamente los pasos del 5 al 7 obteniendo como
solucin final:
Variable
Bsica
Variables
X1
X2
Solucin
X3
S1
S2
NOTA:
No 0.33
hay ms
iteraciones
cuando
no existan soluciones
X3
0
1
-0.33
0
1
X2
-0.33
1
0
0.33
-0.5
1.5
con
coeficientes
negativos.
Z
2
0
0
2
6
-36
R\ El valor mnimo se alcanza para un X2 = 3/2 y X3 = 1, para
un Z = 36
Interpretacin y
Comparacin de
Resultados Obtenidos
El Problema Dual del Problema del Carpintero y su Interpretacin
En esta seccin, construiremos el Problema Dual del Problema del Carpintero
y
presentaremos
la
interpretacin
econmica
del
mismo.
Recordemos los parmetros de entrada no controlables del Problema del
Carpintero:
Datos de entrada no
controlables
Mano de
obra
Materia
prima
Ingresos
netos
Y
su
Maximizar 5 X1 + 3 X2
Mesas
Sillas
Disponible
40
50
formulacin
de
PL
Sujeta a:
2 X1 + X2 40 restriccin de mano de obra
X1 + 2 X2 50 restriccin de materiales
tanto X1 como X2 son no negativas.
Donde X1 y X2 representan la cantidad de mesas y sillas a fabricar.
Supngase que el Carpintero desea contratar un seguro para sus
ingresos netos. Digamos que:
U1 = el monto en dlares pagadero al Carpintero por cada hora de
trabajo perdida (por enfermedad, por ejemplo),
U2 = el monto en dlares pagadero al Carpintero por cada unidad
de materia prima perdida (por incendio, por ejemplo).
Por supuesto que el corredor de seguros intenta minimizar el monto
total de US$(40U1 + 50U2) pagadero al Carpintero por la Compaa
de Seguros. Sin embargo, como es de esperar, el Carpintero fijar
las restricciones (es decir las condiciones) para que la compaa de
seguros cubra toda su prdida que equivale a sus ingresos netos
debido a que no puede fabricar los productos. En consecuencia, el
problema de la compaa de seguros es:
Minimizar 40 U1 + 50 U2
Sujeta a:
2U1 + 1U2 5 ingresos netos por una mesa
1U1 + 2U2 3 ingresos netos por una silla
U1, U2 son no negativas.
Si implementa este problema en un paquete de software, ver que
la solucin ptima es U1 = US$7/3 y U2 = US$1/3 con el valor
ptimo de US$110 (el monto que el Carpintero espera recibir). Esto
asegura que el Carpintero pueda manejar su vida sin
inconvenientes. El nico costo es la prima que le cobra la compaa
de seguros.
Como puede ver, el problema de la compaa de seguros est
estrechamente relacionado con el problema original.
Segn la terminologa del proceso de diseo de modelos de IO/CA,
el problema original se denomina Problema Primario mientras que el
problema relacionado se denomina Problema Dual
Tal como vimos en el Problema del Carpintero y su Problema Dual,
el Valor Optimo es siempre el mismo para ambos problemas. Esto
se denomina Equilibrio Econmico entre el Problema Primario y el
Problema Dual.
COMO NORMALIZAR UNA
PROGRAMACIN LINEAL
PARA PODER OBTENER
SU DUAL
Como veremos ms adelante, para poder resolver los problemas
de programacin lineal por el mtodo Simplex, ser conveniente
tener las restricciones de nuestro problema de tal forma que los
trminos bi sean mayores o iguales a cero.
Por ello, ya que podemos encontrarnos con restricciones del
tipo:
ai * Xi -bi
ai * Xi -bi
ai * Xi = -bi
Podremos homogeneizar nuestro sistema, convirtindolo al tipo:
-ai*Xibi
-ai*Xibi
-a*Xi=bi
con slo multiplicar por 1 y cambiar el sentido de nuestra
desigualdad.
Es decir:
ai * Xi -bi (-1) * ai * Xi bi
donde se mantendrn las condiciones de la restriccin y se
posibilitar la resolucin del problema mediante el mtodo
Simplex.
Ejemplo.
En una fbrica de vino se producen vinos del tipo: tinto, rosado y
blanco.
Cada botella de tinto nos produce un beneficio de 20 pesetas.
Cada botella de rosado nos produce un beneficio de 15 pesetas.
Cada botella de blanco nos produce un beneficio de 15 pesetas.
Para cada litro de vino tinto se necesita 1 Kg de uvas. Para cada
litro de vino rosado se necesita Kg de uvas. Para cada litro d
vino blanco se necesita Kg de uvas.
Sabiendo que es necesario producir un mnimo de 20 litros de vino
blanco, y que poseen 100 Kg de uva, calcular la produccin
vincola para que nuestro beneficio sea mximo.
Solucin:
Definicin de variables internas:
X1: litros de vino tinto.
X2: litros de vino rosado.
X3: litros de vino blanco.
F.O..: Max 20 X1 + 15 X2 + 15 X3
S.a..: X1 0
X2 0
X3 0
X1 + * X2 + * X3 100 X3 20
Nota: Las restricciones:X10, X20, X30 se pueden
obviar, con lo que nuestro problema quedara:
F.O..: Max 20 X1 + 15 X2 + 15 X3
S.a..:X1 + * X2 + * X3 100
X3 20
Planteamiento
s de TI
Una compaa fabrica tabicn y ladrillo, la empresa obtiene
un margen de utilidad de $3.25 y $6.00 por cada 100
ladrillos y por cada 100 tabicones, respectivamente. En
estos momentos la compaa no tiene compromisos por
pedidos de clientes de ladrillos o de tabicones. No existe
inventario alguno de ninguno de los dos productos. La
produccin de ladrillo y tabicn requiere un proceso de dos
etapas. Primero se les moldea y despus se los hornea. En
el proceso de moldeado se requieren 4 Hrs de tiempo para
fabricar 100 ladrillos y de 8 Hrs para fabricar 100
tabicones. El proceso de horneado no difiere para ninguno
de los dos productos, re requieren para 8 Hrs por cada 100
piezas de cada uno. Existen disponibles un mximo de 80
Hrs de tiempo de moldeado y el mximo tiempo disponible
para el proceso de horneado es de 120hrs por semana. Es
posible vender todas las piezas que se pueden fabricar.
Variables de Decisin= X1= Fab 100 ladrillos
X2= Fab 100 tabicones
Funcin Objetivo= MaxZ= 3.25 X1 + 6.00 X2
Restricciones=
4 X1 + 8 X2
8 X1 + 8 X2
X1, X2
<0
< 80
< 120
2.-La Higgins Company fabrica piezas de alta precisin que se
utilizan en los motores de automviles de carrera. La pieza se
fabrica en un proceso de forjado y refinacin y son necesarias
cantidades mnimas de diversos metales. Cada pieza requiere 40
onzas de plomo, 48 de cobre y 60 de fierro colado. Existen 4
tipos de mineral disponible para el proceso de forjado y
refinacin. El mineral del tipo 1 contiene 4 onzas de plomo, 2 de
cobre y 2 de acero colado por libra. Una libra de mineral tipo 2
contiene 2 onzas de plomo, 6 de cobre y 6 de acero colado. Una
libra del mineral tipo 3 contiene 1 onza de plomo, 4 de cobre y 4
de acero colado. Por ltimo el mineral tipo 4 contiene 1/2onza
de plomo, 1 de cobre y 8 onzas de acero colado por libra. El
costo por libra para los cuatro minerales en $20, $30, $60 y
$50, respectivamente. A la Higgins le gustara mezclar los
minerales de manera que se satisfagan las especificaciones de
las piezas y se minimice el costo de fabricarlas.
Variables de Decisin= X1= Min 1
X2= Min 2
X2= Min 3
X2= Min 4
Funcin Objetivo=
50 X4
Restricciones=
1/2 X4 > 40
+ 4 X4 > 48
+ 4 X4 > 60
MaxZ= 20 X1 + 30 X2 + 60 X3 +
4
X1 + 2 X2 + 1 X3 +
2
X1 + 6 X2 + 4 X3
X1 + 6 X2 + 4 X3
