Karla Valeria Ramírez Martínez 18 de abril del 2018
Investigación de Operaciones
“Método Simplex Dual”
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
cómputo 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.
Para poder elaborar el problema dual a partir del primal, este se debe presentar en su
“forma canónica”.
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.
En clase vimos la forma que tiene un PL (Problema lineal) primal y como pasa a la
forma de un PL dual. Representado de la siguiente manera:
Problema Primal Problema Dual
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑍 = ∑𝑛𝑗=1 𝐶𝑗 𝑋𝑗 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝑊 = ∑𝑛𝑖=1 𝑏𝑗 𝑦𝑗
𝑆. 𝑎 = ∑𝑛𝑗=1 𝑎𝑖𝑗 𝑥𝑖𝑗 ≤ 𝑏𝑖 𝑆. 𝑎 = ∑𝑛𝑖=1 𝑎𝑖𝑗 𝑦 ≤ 𝐶𝑗
para i = 1, 2 para j = 1, 2
y y
... m ... n
𝑋𝑗 ≥ 0 𝑌𝑗 ≥ 0
para j = 1, 2 para i = 1, 2
... n ... m
Ejemplo cuando se está en la ”forma canónica”
Fuentes de Información:
[Link]
HTML
Karla Valeria Ramírez Martínez 18 de abril del 2018
Investigación de Operaciones
Primal.- Dual.-
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑍 = 5𝑋1 + 6𝑋2 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝑊 = 60𝑌1 + 45𝑌2 + 20𝑌3 + 30𝑌4
𝑆. 𝑎 = 𝑋1 + 9𝑋2 ≤ 60 𝑆. 𝑎 = 𝑌1 + 2𝑌2 + 5𝑌3 + 0𝑌4 ≥ 5
2𝑋1 + 3𝑋2 ≤ 45 9𝑌1 + 3𝑌2 − 2𝑌3 + 𝑌4 ≥ 6
5𝑋1 − 2𝑋2 ≤ 20 𝑌1 , 𝑌2 , 𝑌3 , 𝑌4 ≥ 0
𝑋2 ≤ 30
𝑋1 , 𝑋2 ≥ 0
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 cuando se está en la ”forma no canónica”
Primal.-
Maximizar
Fuentes de Información:
[Link]
HTML
Karla Valeria Ramírez Martínez 18 de abril del 2018
Investigación de Operaciones
Sujeto a:
Maximizar
Sujeto a:
Maximizar
Sujeto a:
Dual.-
Minimizar
Sujeto a:
Conclusión.-
Comprendí que cada PL Primal tiene un PL Dual y que una vez obteniendo la
solución óptima de uno de ellos se obtiene la solución del segundo ya que estas
tienen que ser las mismas, haciendo así favorable la solución del más sencillo.
Fuentes de Información:
[Link]
HTML
Karla Valeria Ramírez Martínez 18 de abril del 2018
Investigación de Operaciones
Se aplica la transpuesta al problema primal para obtener el dual, siguiendo los
pasos cuando este está en su forma canónica o bien los pasos que aplican cuando
nuestro problema no está en la forma canónica.
Fuentes de Información:
[Link]
HTML