METODO DUAL SIMPLEX.
TEORIA
DE LA DUALIDAD.
Cada
problema de programación lineal tiene un segundo problema asociado con el. Uno
se denomina primal y el otro dual. Los 2 poseen propiedades muy relacionadas,
de tal manera que la solución óptima a un problema proporciona información
completa sobre la solución óptima para el otro.
Las
relaciones entre el primal y el dual se utilizan para reducir el esfuerzo de
computo en ciertos problemas y para obtener información adicional sobre las
variaciones en la solución óptima debidas a ciertos cambios en los coeficientes
y en la formulación del problema. Esto se conoce como análisis de sensibilidad
o post-optimidad.
DEFINICION
DEL PROBLEMA DUAL.
Para
poder elaborar el problema dual a partir del primal, este se debe presentar en
su forma canónica de la siguiente forma:
Maximizar 
Sujeto
a:
El
problema dual se puede obtener a partir del problema primal y viceversa de la
siguiente manera:
1. Cada
restricción de un problema corresponde a una variable en el otro.
2. Los
elementos del lado derecho de las restricciones en un problema son iguales a
los coeficientes respectivos de la función objetivo en el otro.
3. Un
problema busca maximizar y el otro minimizar.
4. El
problema de maximización tiene restricciones 
que y el problema de
minimización tiene restricciones 
que.
5. Las
variables en ambos casos son no negativas.
EJEMPLO:
Considere
el problema primal siguiente:
Maximizar 
Sujeto
a:
Elaborar
el dual a partir del primal.
Minimizar 
Sujeto
a:
Cuando
el problema primal no está en forma canónica, es necesario hacer ajustes para
poder presentarlo así. Los cambios más frecuentes son:
1. Si
la función objetivo es minimizar, se puede transformar a una función objetivo
de maximizar de la siguiente forma:
Minimizar 
Maximizar 
2. Una
restricción mayor o igual que se transforma en una restricción menor o igual
que de la siguiente manera:
3. Una
restricción de igualdad se transforma en 2 inecuaciones.
EJEMPLO: (PRIMAL).
Maximizar 
Sujeto
a:
Maximizar 
Sujeto
a:
Dual
Miminizar 
Sujeto
a:
Encuentre el problema dual a partir del primal siguiente:
EJEMPLO:
Maximizar 
Sujeto a:
Maximizar 
Sujeto a:
Maximizar 
Sujeto a:
Minimizar 
Sujeto a:
EJEMPLO:
Minimizar 
Sujeto a:
Maximizar 
Sujeto a:
Maximizar 
Sujeto a:
Minimizar 
Sujeto a:
Maximizar 
Sujeto a:
EJEMPLO:
Minimizar 
Sujeto
a:
Maximizar 
Sujeto
a:
Minimizar 
Sujeto
a:
Maximizar 
Sujeto
a:
Encuentre
el problema dual asociado al problema primal siguiente:
Minimizar 
Sujeto
a:
Maximizar 
Sujeto
a:
Minimizar 
Sujeto
a:
Maximizar 
Sujeto
a:
SOLUCION OPTIMA PRIMAL (2FASES)
|
V.
Básica |
Z |
X1 |
X2 |
S1 |
S2 |
Solución |
Z |
1 |
-5000/3 |
0 |
-500/3 |
0 |
6000 |
|
S2 |
0 |
1 |
0 |
-2 |
1 |
12 |
|
X2 |
0 |
2/3 |
1 |
-1/3 |
0 |
12 |
SOLUCION
OPTIMA DEL DUAL
|
V.
Básica |
Z |
W1 |
W2 |
S1 |
S2 |
Solución |
Z |
1 |
0 |
12 |
0 |
12 |
6000 |
|
S1 |
0 |
0 |
-1 |
1 |
-2/3 |
5000/3 |
|
W1 |
0 |
1 |
2 |
0 |
1/3 |
500/3 |
EJEMPLO:
Una
compañía produce y vende 2 tipos de máquinas de escribir: manual y eléctrica.
Cada máquina de escribir manual es vendida por un ingreso de 40 dls. y cada
máquina de escribir eléctrica produce un ingreso de 60 dls. Ambas máquinas
tienen que ser procesadas (ensambladas y empacadas) a través de 2 operaciones
diferentes (O1 y O2).
La
compañía tiene una capacidad de 2000 hrs. Mensuales para la operación O1 y 1000
hrs. Mensuales de la operación O2.
El
número de horas requeridas de O1 y O2 para producir un modelo terminado se da
en la siguiente tabla.
|
|
HORAS |
REQUERIDAS |
CAPACIDAD |
OPERACIÓN |
MANUAL |
ELECTRICA |
(HRS MENSUALES) |
|
O1 |
3 |
2 |
2000 |
|
O2 |
1 |
2 |
1000 |
Encuentre
el número óptimo de unidades de cada tipo de máquina de escribir que se debe
producir mensualmente para maximizar el ingreso.
OBJETIVO
: Maximizar el ingreso total
RESTRICCIONES
: horas mensuales de las operaciones
VARIABLE
DE DECISION: número de máquinas de escribir a producir
X1
= número de máquinas de escribir manuales
X2
= número de máquinas de escribir eléctricas
Maximizar 
Sujeto
a:
Minimizar 
Sujeto
a:
|
V.
Básica |
Z |
W1 |
W2 |
S1 |
S2 |
Solución |
Z |
1 |
0 |
0 |
5 |
25 |
35000 |
|
S1 |
0 |
1 |
0 |
1/ 2 |
-1/2 |
500 |
|
W1 |
0 |
0 |
1 |
-1/ 4 |
3/ 4 |
250 |
METODO DUAL SIMPLEX.
Este
método se aplica a problemas óptimos pero infactibles. En este caso, las
restricciones se expresan en forma canónica (restricciones 
).
La
función objetivo puede estar en la forma de maximización o de minimización.
Después de agregar las variables de holgura y de poner el problema en la tabla,
si algún elemento de la parte derecha es negativo y si la condición de
optimidad está satisfecha, el problema puede resolverse por el método dual
simplex. Note que un elemento negativo en el lado derecho significa que el
problema comienza óptimo pero infactible como se requiere en el método dual
simplex. En la iteración donde la solución básica llega a ser factible esta
será la solución óptima del problema.
CONDICION DE FACTIBILIDAD.
La
variable que sale es la variable básica que tiene el valor más negativo (los
empates se rompen arbitrariamente si todas las variables básicas son negativas,
el proceso termina y esta última tabla es la solución óptima factible).
CONDICION DE OPTIMIDAD.
La
variable que entra se elige entre las variables no básicas como sigue. Tome los
cocientes de los coeficientes de la función objetivo entre los coeficientes
correspondientes a la ecuación asociada a la variable que sale.
Ignore
los cocientes asociados a denominadores positivos o cero.
La
variable que entra es aquella con el cociente más pequeño si el problema es de
minimizar o el valor absoluto más pequeño si el problema es de maximización (rompa los empates arbitrariamente). Si los
denominadores son ceros o positivos el problema no tiene ninguna solución
factible.
Minimizar 
Sujeto
a:
Minimizar 
Sujeto
a:
|
V.
Básica |
Z |
X1 |
X2 |
S1 |
S2 |
Solución |
Z |
1 |
-2000 |
-1000 |
0 |
0 |
0 |
|
S1 |
0 |
-3 |
-1 |
1 |
1 |
-40 |
|
S2 |
0 |
-2 |
-2 |
0 |
0 |
-60 |
|
V.
Básica |
Z |
X1 |
X2 |
S1 |
S2 |
Solución |
Z |
1 |
-1000 |
0 |
0 |
-500 |
30000 |
|
S1 |
0 |
-2 |
0 |
1 |
-1/2 |
-10 |
|
X2 |
0 |
1 |
1 |
0 |
-1/2 |
30 |
|
V. Básica |
Z |
X1 |
X2 |
S1 |
S2 |
Solución |
Z |
1 |
0 |
-1000 |
-500 |
-250 |
35000 |
|
S1 |
0 |
1 |
-1 |
-1/2 |
1/ 4 |
5 |
|
S2 |
0 |
0 |
-2 |
1/ 2 |
-5/4 |
25 |
