OPTIMIZACIÓN

UNIVERSIDAD TECNOLÓGICA DE BOLÍVAR

MANUEL SOTO DE LA VEGA

2
ALGORITMO SIMPLEX DUAL

3
ALGORITMO SIMPLEX DUAL
El método simplex dual se inicia con una solución mejor que óptima
(teorema de la dualidad débil) y una solución básica no factible.

Las condiciones de optimalidad y factibilidad están diseñadas para preservar

la optimalidad de las soluciones básicas a medida que la solución se mueve
hacia la factibilidad.

4
ALGORITMO SIMPLEX DUAL
Para iniciar la programación lineal óptima y no factible, se debe cumplir con
dos requisitos:

1. La función objetivo debe satisfacer la condición de optimalidad del

método simplex regular.
2. Todas las restricciones deben ser del tipo (≤)

5
ALGORITMO SIMPLEX DUAL
Las desigualdades del tipo (≥) se convierten en (≤) al multiplicar ambos lados
de la desigualdad por -1.
Si la programación lineal incluye restricciones (=), la ecuación se puede
reemplazar por dos desigualdades. Por ejemplo,

𝑥1 + 𝑥2 = 1
equivale a
𝑥1 + 𝑥2 ≤ 1
𝑥1 + 𝑥2 ≥ 1

6
ALGORITMO SIMPLEX DUAL
Ejemplo 1:
min 𝑍 = 3𝑥1 + 2𝑥2 + 𝑥3

S.A.
3𝑥1 + 𝑥2 + 𝑥3 ≥ 3
−3𝑥1 + 3𝑥2 + 𝑥3 ≥ 6
𝑥1 + 𝑥2 + 𝑥3 ≤ 3

𝑥1 , 𝑥2 , 𝑥3 ≥ 0

7
ALGORITMO SIMPLEX DUAL
x1 x2 x3 s1 s2 s3 Sol
z -3 -2 -1 0 0 0 0
s1 3 1 1 -1 0 0 3
s2 -3 3 1 0 -1 0 6
s3 1 1 1 0 0 1 3
No se tiene la base inicial

8
ALGORITMO SIMPLEX DUAL
x1 x2 x3 s1 s2 s3 Sol
z -3 -2 -1 0 0 0 0
s1 -3 -1 -1 1 0 0 -3
s2 3 -3 -1 0 1 0 -6
s3 1 1 1 0 0 1 3
Se tiene la base inicial pero el problema primal es infactible, aunque optimo.

9
ALGORITMO SIMPLEX DUAL
x1 x2 x3 s1 s2 s3 Sol
z -3 -2 -1 0 0 0 0
s1 -3 -1 -1 1 0 0 -3
s2 3 -3 -1 0 1 0 -6
s3 1 1 1 0 0 1 3
Se tiene la base inicial pero el problema primal es infactible, aunque optimo.

Se quiere eliminar la infactiblidad

Sale la más negativa

10
ALGORITMO SIMPLEX DUAL
x1 x2 x3 s1 s2 s3 Sol
z -3 -2 -1 0 0 0 0
s1 -3 -1 -1 1 0 0 -3
s2 3 -3 -1 0 1 0 -6 Sale
s3 1 1 1 0 0 1 3

Cociente -1 0,66667 1 #¡DIV/0! 0 #¡DIV/0!

Entra
Sale s2 y entra x2

11
ALGORITMO SIMPLEX DUAL
x1 x2 x3 s1 s2 s3 Sol
z -5 0 -0,33333 0 -0,66667 0 4
s1 -4 0 -0,66667 1 -0,33333 0 -1
s2 -1 1 0,33333 0 -0,33333 0 2
s3 2 0 0,66667 0 0,33333 1 1
El problema primal sigue siendo optimo e infactible

12
ALGORITMO SIMPLEX DUAL
x1 x2 x3 s1 s2 s3 Sol
z -5 0 -0,33333 0 -0,66667 0 4
s1 -4 0 -0,66667 1 -0,33333 0 -1 Sale
x2 -1 1 0,33333 0 -0,33333 0 2
s3 2 0 0,66667 0 0,33333 1 1

Cociente 1,25 #¡DIV/0! 0,5 0 2 #¡DIV/0!

Entra
Sale s1 y entra x3

13
ALGORITMO SIMPLEX DUAL
x1 x2 x3 s1 s2 s3 Sol
z -3 0 0 -0,5 -0,5 0 4,5
x3 6 0 1 -1,5 0,5 0 1,5
x2 -3 1 0 0,5 -0,5 0 1,5
s3 -2 0 0 1 0 1 0
El problema primal sigue siendo optimo pero ahora factible!

14
ALGORITMO SIMPLEX DUAL
Observe cómo funciona el simplex dual. En todas las iteraciones la
optimalidad se mantiene (todos los costos reducidos son ≤ 0) ya que cada
nueva iteración mueve la solución hacia la factibilidad.

En la iteración 3, la factibilidad se restaura por primera vez, y el proceso

finaliza con la solución factible óptima.

15
ALGORITMO SIMPLEX DUAL
Ejemplo 2:

min 𝑍 = 5𝑥1 + 12𝑥2 + 4𝑥3

𝑆. 𝐴.
𝑥1 + 2𝑥2 + 𝑥3 ≤ 5
2𝑥1 − 𝑥2 + 3𝑥3 = 2
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

16
ALGORITMO SIMPLEX DUAL
Ejemplo 2:

min 𝑍 = 5𝑥1 + 12𝑥2 + 4𝑥3

𝑆. 𝐴.
𝑥1 + 2𝑥2 + 𝑥3 ≤ 5
2𝑥1 − 𝑥2 + 3𝑥3 ≤ 2
2𝑥1 − 𝑥2 + 3𝑥3 ≥ 2
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

17
ALGORITMO SIMPLEX DUAL
Ejemplo 2:

min 𝑍 = 5𝑥1 + 12𝑥2 + 4𝑥3

𝑆. 𝐴.
𝑥1 + 2𝑥2 + 𝑥3 ≤ 5
2𝑥1 − 𝑥2 + 3𝑥3 ≤ 2
−2𝑥1 + 𝑥2 − 3𝑥3 ≤ −2
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

18
ALGORITMO SIMPLEX DUAL
x1 x2 x3 s1 s2 s3 Sol
z -5 -12 -4 0 0 0 0
s1 1 2 1 1 0 0 5
s2 -2 1 -3 0 1 0 -2
s3 2 -1 3 0 0 1 2

19
ALGORITMO SIMPLEX DUAL
x1 x2 x3 s1 s2 s3 Sol
z -5 -12 -4 0 0 0 0
s1 1 2 1 1 0 0 5
s2 -2 1 -3 0 1 0 -2 Sale
s3 2 -1 3 0 0 1 2

Cociente 2,5 - 1,33333 - - -

Entra
ALGORITMO SIMPLEX DUAL
x1 x2 x3 s1 s2 s3 Sol
z -2,33333 -13,3333 0 0 -1,33333 0 2,66667
s1 0,33333 2,33333 0 1 0,33333 0 4,33333
x3 0,66667 -0,33333 1 0 -0,33333 0 0,66667
s3 0 0 0 0 1 1 0

Solución óptima

21
SIMPLEX DUAL GENERALIZADO

Problema factible Problema infactible Problema infactible

pero no óptimo pero óptimo y no óptimo
• Simplex (primal) • Simplex dual • Simplex
generalizado

22
SIMPLEX DUAL GENERALIZADO
Algoritmo simplex basado en el uso de uno tras otro de los métodos simplex
dual y simplex primal. Primero utilice el algoritmo dual para deshacerse de la
no factibilidad (sin preocuparse de la optimalidad). Una vez restaurada la
factibilidad, puede usarse el simplex primal para hallar el óptimo.

Como alternativa podemos aplicar primero el simplex primal para asegurar la

optimalidad (sin preocuparnos de la factibilidad) y luego utilizar el simplex
dual para buscar la factibilidad.

23
SIMPLEX DUAL GENERALIZADO
Ejemplo 3:

max 𝑍 = −10𝑥1 + 20𝑥2

𝑆. 𝐴.
𝑥1 + 2𝑥2 ≤ 4
2𝑥1 − 3𝑥2 ≥ 6
𝑥1 , 𝑥2 ≥ 0

24
SIMPLEX DUAL GENERALIZADO
x1 x2 s1 s2 Sol
z 10 -20 0 0 0
s1 1 2 1 0 4
s2 2 -3 0 -1 6
El problema no es óptimo, pero tampoco se tiene una base factible.

Aplicamos primero simplex primal.

Entra 𝑥2 y sale 𝑠1
25
SIMPLEX DUAL GENERALIZADO
x1 x2 s1 s2 Sol
z 20 0 10 0 40
x2 0,5 1 0,5 0 2
s2 3,5 0 1,5 -1 12
El problema es óptimo, pero aún no se tiene la base factible.

26
SIMPLEX DUAL GENERALIZADO
x1 x2 s1 s2 Sol
z 20 0 10 0 40
x2 0,5 1 0,5 0 2
s2 -3,5 0 -1,5 1 -12
El problema es óptimo pero infactible.

Aplicamos simplex dual

Entra 𝑥1 y sale 𝑠2
27
SIMPLEX DUAL GENERALIZADO
x1 x2 s1 s2 Sol
z 0 0 1,42857 5,71429 -28,5714
x2 0 1 0,28571 0,14286 0,28571
x1 1 0 0,42857 -0,28571 3,42857
El problema es óptimo y también factible

28
SIMPLEX DUAL GENERALIZADO
En la literatura abunda muchas variaciones del método simplex (por
ejemplo, el método primal-dual, el método simétrico, el método
entrecruzado y el método multiplex) que dan la impresión de que cada
procedimiento es diferente, cuando, en realidad, todos buscan una solución
de punto de esquina, con una tendencia hacia los cálculos automáticos y,
quizás, eficiencia computacional.

29