Adjuntas: Flores Pérez Elizabeth
Piña Guerrero Viviana
Optimización I – Gpo. 1551 / 1552
Método Dual Simplex
El método dual simplex es un algoritmo que nos ayuda a la resolución de modelos de PL que
al obtener su forma estándar, notamos que no podemos aplicar el método simplex (regular)
de forma directa o inmediata.
Un caso típico de aplicación, el cual revisaremos en este curso, es cuando nuestro modelo(s)
de programación lineal cumplen con las siguientes características:
• Sentido de la optimalidad: minimización.
• Restricciones: ≤, ≥ y/o =
• Signo de variables: 𝒙𝒋 ≥ 𝟎
Tal es el caso del siguiente ejemplo:
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟: 𝑧 = 2𝑥1 + 3𝑥2
𝑆𝑢𝑗𝑒𝑡𝑜 𝑎:
2𝑥1 + 𝑥2 ≥ 3
𝑥1 + 𝑥2 = 2
𝑥1 , 𝑥2 ≥ 0
Si quisiéramos resolver este modelo por el método simplex que aprendimos a inicio del
curso, no podríamos ya que tenemos que agregarle a este, variables de exceso (𝑒𝑗 ) y en
consecuencia, artificiales (𝑎𝑗 ). ¿Cuáles métodos usaríamos para su resolución?
Pero, aquí es donde hace su entrada el método dual simplex. Con unas sencillas
modificaciones a nuestro modelo original podremos resolverlo usando el método simplex
regular, ¡sí, en serio!.
Así que comencemos por ver cuáles son estas modificaciones, para ello nos basaremos en
las señaladas en los libros de Hillier-Lieberman y de Taha en sus capítulos correspondientes
a “Teoría de dualidad”.
Adjuntas: Flores Pérez Elizabeth
Piña Guerrero Viviana
Optimización I – Gpo. 1551 / 1552
Método Dual Simplex
De acuerdo con Taha, el método dual simplex inicia con una solución óptima y una solución
básica (𝑥𝐵 ) no factible. Para iniciar la programación lineal óptima y no factible, se debe
cumplir con 2 requisitos:
1. La función objetivo debe satisfacer la condición de optimalidad del método simplex
regular. ¿Cuál es esta condición en un modelo PL de minimización?
2. Todas las restricciones deben ser del tipo (≤).
*La solución inicial es no factible si al menos uno de los lados derechos de las desigualdades
es negativo. ¿Qué sucedería si los lados derechos de las desigualdades son positivos?
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟: 𝑧 = 2𝑥1 + 3𝑥2
𝑆𝑢𝑗𝑒𝑡𝑜 𝑎:
2𝑥1 + 𝑥2 ≥ 3
𝑥1 + 𝑥2 = 2
𝑥1 , 𝑥2 ≥ 0
Determinar la forma estándar con la que trabajaremos.
a) Cambiar la función objetivo Z.
El sentido de la optimalidad originalmente es de minimizar, por lo tanto cambiará a
maximizar y deberemos de multiplicar toda la función por −1.
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟: 𝑧 = 2𝑥1 + 3𝑥2 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟: −𝑧 = −2𝑥1 − 3𝑥2
Adjuntas: Flores Pérez Elizabeth
Piña Guerrero Viviana
Optimización I – Gpo. 1551 / 1552
Método Dual Simplex
b) Las restricciones (=) se transforman en 2 desigualdades (≤, ≥).
¿Recuerdas en qué tema vimos algo similar?
En el caso de encontrarnos con igualdades, como en el ejemplo, visualizaremos a la igualdad
como dos restricciones.
𝑥1 + 𝑥2 ≤ 2
𝑥1 + 𝑥2 = 2
𝑥1 + 𝑥2 ≥ 2
Hasta este momento nuestro modelo se encuentra así:
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟: −𝑧 = −2𝑥1 − 3𝑥2
𝑆𝑢𝑗𝑒𝑡𝑜 𝑎:
2𝑥1 + 𝑥2 ≥ 3
𝑥1 + 𝑥2 ≤ 2
𝑥1 + 𝑥2 ≥ 2
𝑥1 , 𝑥2 ≥ 0
¿Con nuestro modelo así, podríamos ya aplicar simplex regular?¿Por qué?
c) Las restricciones (≥) se transforman en restricciones (≤).
Como recuerdas, podemos cambiar el signo de la desigualdad si multiplicamos nuestra
ecuación por −1.
Por lo tanto nuestro modelo ahora se ve así.
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟: −𝑧 = −2𝑥1 − 3𝑥2
𝑆𝑢𝑗𝑒𝑡𝑜 𝑎:
−2𝑥1 − 𝑥2 ≤ −3
𝑥1 + 𝑥2 ≤ 2
−𝑥1 − 𝑥2 ≤ −2
𝑥1 , 𝑥2 ≥ 0
Adjuntas: Flores Pérez Elizabeth
Piña Guerrero Viviana
Optimización I – Gpo. 1551 / 1552
Método Dual Simplex
¿El modelo resultante ya puede resolverse por el método simplex regular? ¿Por qué?
d) Obtener la forma estándar.
¿Tenemos una solución básica no factible?¿Por qué?
Los incisos a, b y c del paso 1 se encuentran resumidos en el siguiente cuadro:
𝑀𝑜𝑑𝑒𝑙𝑜 𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑙 𝑀𝑜𝑑𝑒𝑙𝑜 𝑚𝑜𝑑𝑖𝑓𝑖𝑐𝑎𝑑𝑜
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝑍 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 (−𝑍)
𝑛 𝑛
∑ 𝑎𝑖𝑗 𝑥𝑗 ≥ 𝑏𝑖 − ∑ 𝑎𝑖𝑗 𝑥𝑗 ≤ −𝑏𝑖
𝑗=1 𝑗=1
𝑛 𝑛 𝑛
∑ 𝑎𝑖𝑗 𝑥𝑗 = 𝑏𝑖 ∑ 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 𝑦 − ∑ 𝑎𝑖𝑗 𝑥𝑗 ≤ −𝑏𝑖
𝑗=1 𝑗=1 𝑗=1
𝑥𝑗 sin 𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑠𝑖𝑔𝑛𝑜 𝑥𝑗+ − 𝑥𝑗− , 𝑥𝑗+ ≥ 0, 𝑥𝑗− ≥ 0
Adjuntas: Flores Pérez Elizabeth
Piña Guerrero Viviana
Optimización I – Gpo. 1551 / 1552
Método Dual Simplex
Aplicar el método simplex regular.
Solo resta construir nuestra tabla simplex y seguir las nuevas condiciones de factibilidad y
optimalidad.
−𝒛 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 𝒙𝑩
−𝒛 𝟏 𝟐 𝟑 𝟎 𝟎 𝟎 0
𝒔𝟏 0 −2 −1 1 0 0 −𝟑
𝒔𝟐 0 1 1 0 1 0 𝟐
𝒔𝟑 0 −1 −1 0 0 1 −𝟐
Puedes notar que la anterior es una tabla óptima para maximización y cumple con la no
factibilidad debido a que en 𝑥𝐵 tenemos valores negativos. Cumpliendo así con las
condiciones para iniciar el método.
Te preguntarás ¿cómo es que vamos a elegir a nuestras variables de entrada y de salida?
Pues tanto la prueba de factibilidad como de optimalidad, cambiarán.
Condición dual de factibilidad. La variable de salida 𝑥𝑟 es la variable básica que tiene el
valor más negativo (los empates se rompen de forma arbitraria). Si todas las variables
básicas son no negativas, el algoritmo termina.
Condición dual de optimalidad. La variable de entrada es la variable no básica con 𝛼𝑟𝑗 < 0
que corresponde a
𝑐𝑗
mín {| | , 𝛼 < 0}
𝑁𝑜 𝐵á𝑠𝑖𝑐𝑎 𝛼𝑟𝑗 𝑟𝑗
Donde:
𝑪𝒋 ∶ 𝑐𝑜𝑒𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑒𝑠 𝑑𝑒𝑙 𝑟𝑒𝑛𝑔𝑙ó𝑛 𝑍
𝜶𝒓𝒋 ∶ 𝑐𝑜𝑒𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑒𝑠 𝑒𝑛 𝑒𝑙 𝑟𝑒𝑛𝑔𝑙ó𝑛 𝑑𝑒 𝑙𝑎 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒 𝑏á𝑠𝑖𝑐𝑎 𝑑𝑒 𝑠𝑎𝑙𝑖𝑑𝑎
(Los empates se rompen arbitrariamente).
¿Qué pasa si 𝛼𝑟𝑗 ≥ 0?
Conociendo lo anterior, vayamos a resolver nuestra tabla.
Adjuntas: Flores Pérez Elizabeth
Piña Guerrero Viviana
Optimización I – Gpo. 1551 / 1552
Método Dual Simplex
−𝒛 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 𝒙𝑩
−𝒛 1 2 3 0 0 0 0
𝒔𝟏 0 −2 −1 1 0 0 −𝟑
𝒔𝟐 0 1 1 0 1 0 2
𝒔𝟑 0 −1 −1 0 0 1 −2
−𝒛 1 0 2 1 0 0 −3
𝒙𝟏 0 1 1/2 −1/2 0 0 3/2
𝒔𝟐 0 0 1/2 1/2 1 0 1/2
𝒔𝟑 0 0 −1/2 −1/2 0 1 −𝟏/𝟐
−𝒛 1 0 1 0 0 2 −4
𝒙𝟏 0 1 1 0 0 −1 2
𝒔𝟐 0 0 0 0 1 1 0
𝒔𝟏 0 0 1 1 0 −2 1
Puedes ver que la tabla ya es óptima para maximización y ahora sí la solución es factible
debido a que los valores de las variables básicas son positivos (𝑍 no es variable básica).
Entonces ya podemos reportar nuestra solución de nuestro modelo original como:
𝑺𝒐𝒍𝒖𝒄𝒊ó𝒏 ó𝒑𝒕𝒊𝒎𝒂
𝒛=𝟒
𝒙𝟏 = 𝟐
𝒙𝟐 = 𝟎
Así concluimos el método. Es tu turno de realizar el siguiente ejercicio que se te propone en
plataforma.
