PROGRAMACION LINEAL

SIMPLEX, DUAL, SENSIBILIDAD

1
Simplex
 Solución Algebraica - Método Simplex

El método simplex es un método iterativo (algoritmo) utilizado para encontrar

algebraicamente, la solución óptima de un problema de PL.

PASOS DEL SIMPLEX

1. Encontrar una solución básica inicial;
2. Verificar si la solución es óptima. Si así fuera pare, en caso contrario, siga
para el paso 3
3. Determinar la variable no básica que debe entrar a la base.
4. Determinar la variable básica que debe salir de la base;
5. Encontrar la nueva solución compatible básica y volver al paso 2.

Sea el Problema

Máximizar z = 3x1 + 2x2 + 5x3 s.a.

x1 + 2x2 + x3 <= 430
3x1 + 2x3 <= 460
x1 + 4x2 <= 420
x1, x2, x3 >= 0
3
 Solución Algebraica - Método Simplex

Primer paso: Transformar el sistema de M desigualdades lineales restrictivas

En un sistema de M ecuaciones lineales.

x1 + 2x2 + x3 + x4 = 430
3x1+ 2x3 + x5 = 460
x1+ 4x2 + x6 = 420

Segundo paso: Colocar las ecuaciones en forma tabulada

Z – 3x1 – 2x2 – 5x3 = 0

x1 + 2x2 + x3 + x4 = 430
3x1 + +2x3 + x5 = 460
x1 + 4x2 + x6 = 420

4
 Solución Algebraica - Método Simplex
Tercer paso: Determinar una solución inicial viable

VB z x1 x2 X3 X4 x5 x6 b

Z 1 -3 -2 -5 0 0 0 0

X4 0 1 2 1 1 0 0 430

X5 0 3 0 2 0 1 0 460

x6 0 1 4 0 0 0 1 420

X1=x2=x3=0

X4 =430; x5 = 460; x6 = 420

5
 Solución Algebraica - Método Simplex
Tercer paso: Determinar una solución inicial viable

VB z x1 x2 X3 X4 x5 x6 b

Z 1 -3 -2 -5 0 0 0 0

X4 0 1 2 1 1 0 0 430

X5 0 3 0 2 0 1 0 460

x6 0 1 4 0 0 0 1 420

X1=x2=x3=0

X4 =430; x5 = 460; x6 = 420

6
 Solución Algebraica - Método Simplex
Tercer paso: Determinar una solución inicial viable

VB z x1 x2 X3 X4 x5 x6 b

Z 1 -3 -2 -5 0 0 0 0

X4 0 1 2 1 1 0 0 430

X5 0 3 0 2 0 1 0 460

x6 0 1 4 0 0 0 1 420

X1=x2=x3=0

X4 =430; x5 = 460; x6 = 420

7
 Solución Algebraica - Método Simplex
Tercer paso: Determinar una solución inicial viable

VB z x1 x2 X3 X4 x5 x6 b

Z 1 -3 -2 -5 0 0 0 0

X4 0 1 2 1 1 0 0 430

X5 0 3 0 2 0 1 0 460

x6 0 1 4 0 0 0 1 420

X1=x2=x3=0

X4 =430; x5 = 460; x6 = 420

8
 Solución Algebraica - Método Simplex
Cuarto paso: Verificar si la solución es óptima

VB z x1 x2 X3 X4 x5 x6 b

Z 1 -3 -2 -5 0 0 0 0

X4 0 1 2 1 1 0 0 430

X5 0 3 0 2 0 1 0 460

x6 0 1 4 0 0 0 1 420

La solución no es óptima, porque las variables x1,x2 y x3 asumen valor

cero.
Quinto paso:Determinar la variable que entra xi , y

Sexto paso: Determinar la variable que sale xi

9
 Solución Algebraica - Método Simplex

VB z x1 x2 X3 X4 x5 x6 b Cociente
b/X3
Z 1 -3 -2 -5 0 0 0 0
X4 0 1 2 1 1 0 0 430
X5 0 3 0 2 0 1 0 460
x6 0 1 4 0 0 0 1 420

en este caso, entra x3 y sale x5. La intersección x3 ^ x5 es

el pivote

Sétimo paso: Calcular la nueva matriz de coeficientes, ejecutando las operaciones

convenientes en las líneas de la matriz.

10
 Solución Algebraica - Método Simplex

VB z x1 x2 X3 X4 x5 x6 b Cociente
b/X3
Z 1 -3 -2 -5 0 0 0 0
X4 0 1 2 1 1 0 0 430 430/1=430
X5 0 3 0 2 0 1 0 460 460/2=230
x6 0 1 4 0 0 0 1 420 420/0 ∄

en este caso, entra x3 y sale x5. La intersección x3 ^ x5 es

el pivote

Sétimo paso: Calcular la nueva matriz de coeficientes, ejecutando las operaciones

convenientes en las líneas de la matriz.

11
 Solución Algebraica - Método Simplex
VB Z X1 X2 x3 X4 X5 X6 B cociente
Z 1 4.5 -2 0 0 2.5 0 1150
X4 0 -0,5 2 0 1 -0,5 0 200 200/2=100
X3 0 1.5 0 1 0 0,5 0 230 230/0 ∄
x6 0 1 4 0 0 0 1 420 420/4=105

Octavo paso: Repetir todos los pasos, del 4 al 7, tantas veces como fuera
necesario, hasta que la solución óptima sea encontrada.

VB z x1 x2 x3 x4 x5 x6 B
Z 1 4 0 0 1 2 0 1350
X2 0 -0,25 1 0 0.5 -0,25 0 100
X3 0 1.5 0 1 0 0,5 0 230
X6 0 2 0 0 -2 1 1 20

El máximo de z es 1350, para x2 = 100, x3 =230 e x6 = 20

12
 Solución Algebraica - Método Simplex
VB Z X1 X2 x3 X4 X5 X6 B cociente
Z 1 4.5 -2 0 0 2.5 0 1150
X4 0 -0,5 2 0 1 -0,5 0 200 200/2=100
X3 0 1.5 0 1 0 0,5 0 230 230/0 ∄
x6 0 1 4 0 0 0 1 420 420/4=105

Octavo paso: Repetir todos los pasos, del 4 al 7, tantas veces como fuera
necesario, hasta que la solución óptima sea encontrada.

VB z x1 x2 x3 x4 x5 x6 B
Z 1 4 0 0 1 2 0 1350
X2 0 -0,25 1 0 0.5 -0,25 0 100
X3 0 1.5 0 1 0 0,5 0 230
X6 0 2 0 0 -2 1 1 20

El máximo de z es 1350, para x2 = 100, x3 =230 e x6 = 20

13
 Solución Algebraica - Método Simplex
Método simplex – Casos especiales
Algunos casos que pueden ocurrir en los modelos de programación lineal

1) Problemas de Minimización
se resolvió, hasta el momento, modelos con función objetivo a ser maximizada. Cuando la
función objetivo es de minimización se pueden hacer dos cosas:

a) Invertir el análisis de optimización y el criterio de entrada a la base.

b) Transformar el problema de minimización en uno de maximización.

por ejemplo, Min W = 2x1 + 3x2 - 5x3 equivale a:

Máx Z = -2x1 - 3x2 + 5x3 y en la solución final hacer W = - Z

2) Empate en la entrada
Cuando hubiera empate en la elección de la variable que entra a la base, se debe escoger
la variable arbitrariamente. La única inconveniencia en la elección es un camino más
largo o más corto para obtener la solución óptima.

14
 Solución Algebraica - Método Simplex

3) Empate en la salida – Degeneración

Como en el caso anterior, la decisión debe ser arbitraria.

Máx Z = 5x1 + 2x2 s.a

x1 <= 3
x2 <= 4
4x1 + 3x2 <= 12
x1 , x2 >= 0

VB z x1 x2 x3 x4 X5 B
F.O. 1 -5 -2 0 0 0 0
X3 0 1 0 1 0 0 3
X4 0 0 1 0 1 0 4
x5 0 4 3 0 0 1 12

15
 Solución Algebraica - Método Simplex

Escogiendo la variable que sale:

fila 1 : x1 <= 3/1 = 3
fila 2 : x1 <= 4/0 = indeterminado
fila 3 : x1 <= 12/4 = 3

VB z x1 x2 x3 x4 X5 b
F.O. 1 0 -2 5 0 0 15
X1 0 1 0 1 0 0 3
X4 0 0 1 0 1 0 4
X5 0 0 3 -4 0 1 0

Obs:Note que la variable básica x5 es nula. Esto siempre ocurrirá cuando hubiera un
empate en la salida. En este caso, las variables x3 y x5 se anularon al mismo tiempo.
Cuando ello ocurre se dice que la solución factible básica es degenerada.
16
 Solución Algebraica - Método Simplex
La próxima tabla será:

VB z X1 x2 x3 x4 x5 b
F.O. 1 0 0 7/3 0 2/3 15
X1 0 1 0 1 0 0 3
X4 0 0 0 4/3 1 -1/3 4
X2 0 0 1 -4/3 0 1/3 0

Obs: Si en caso de empate fuese escogido x5 en vez de x3, para salir de la base, se obtendría:

VB z X1 x2 x3 x4 x5 b
F.O. 1 0 7/4 0 0 5/4 15
X3 0 0 -3/4 1 0 -1/4 0
X4 0 0 1 0 1 0 4
X1 0 1 3/4 0 0 1/4 3

17
 Solución Algebraica - Método Simplex
Obs: en este caso se consiguió llegar a la solución óptima con una iteración menos.

ejercicios:

1) Máx Z = 2x1 + 3x2 , s.a

-x1 + 2x2 <= 4
x1 + x2 <= 6
x1 + 3x2 <= 9
x1, x2 >=0 encontrar la solución gráfica o con simplex.

2) Máx Z = 7x1 + 9x2 , s.a

x1 - x2 >= - 2
3x1 + 5x2 <= 15
5x1 + 4x2 <= 20
x1, x2 >= 0 encontrar la solución gráfica o con simplex.

18
 Solución Algebraica - Método Simplex

3) Máx z = 3x1 + x2 + 5x3 , s.a

x1 - 2x2 + 4x3 + x4 = 12
2x1 + x2 + 3x3 + x5 = 15
x1, x2, x3, x4, x5 >= 0
a) ¿Cuál es la solución básica inicial obvia y cual es el valor de Z?
b) Suponer que la variable x3 pase de 0 a 1, manteniendo x1 = x2 = 0. ¿Cuál es el valor resultante
de x4, x5 y de Z?

Casos de Dificultades
Suponga que todos los coeficientes bj sean >=0. Habrá dificultad cuando el modelo presente una
restricción del tipo >=. En estos casos, se usa el proceso de la función objetivo artificial o método
de las dos fases.
La fase I consiste en abandonar o no la función objetivo y trabajar con la función objetivo
artificial, formada por la variable artificial.
Si el modelo requiriera más de una variable artificial para completar la base inicial, la función
objetivo Z será igual a la suma de esas variables artificiales. Así, el objetivo en la fase I es hacer
que la o las variables artificiales sean igual a cero, excluyéndose de la base la función artificial,
antes de pasar a la fase II.

19
 Solución Algebraica - Método Simplex
Resolver usando simplex.
Min Z = - x1 + 2x2 , s.a Max (-Z) = x1 - 2x2 Max (-Z) = x1 - 2x2
6x1 + 5x2 >= 90 6x1 + 5x2 - x3 = 90 6x1 + 5x2 - x3 +A1 = 90
- x1 + x2 <= 8 - x1 + x2 + x4 = 8 - x1 + x2 + x4 = 8
2x1 - x2 <= 20 2x1 - x2 + x5 = 20 2x1 - x2 + x5 = 20
x1, x2 >= 0 x1, x2 >= 0 x1, x2 >= 0

Min A1= - 6x1 - 5x2 + x3 + 90  max (-A1) = 6x1 + 5x2 - x3 – 90

 -A1 - 6x1 - 5x2 + x3 = - 90

VB x1 x2 x3 x4 x5 A1 B cociente
F.O. -1 2 0 0 0 0 0
F.A. -6 -5 1 0 0 -1 -90
A1 6 5 -1 0 0 1 90
X4 -1 1 0 1 0 0 8
x5 2 -1 0 0 1 0 20
20
 Solución Algebraica - Método Simplex
Resolver usando simplex.
Min Z = - x1 + 2x2 , s.a Max (-Z) = x1 - 2x2 Max (-Z) = x1 - 2x2
6x1 + 5x2 >= 90 6x1 + 5x2 - x3 = 90 6x1 + 5x2 - x3 +A1 = 90
- x1 + x2 <= 8 - x1 + x2 + x4 = 8 - x1 + x2 + x4 = 8
2x1 - x2 <= 20 2x1 - x2 + x5 = 20 2x1 - x2 + x5 = 20
x1, x2 >= 0 x1, x2 >= 0 x1, x2 >= 0

Min A1= - 6x1 - 5x2 + x3 + 90  max (-A1) = 6x1 + 5x2 - x3 – 90

 -A1 - 6x1 - 5x2 + x3 = - 90

VB x1 x2 x3 x4 x5 A1 B cociente
F.O. -1 2 0 0 0 0 0
F.A. -6 -5 1 0 0 -1 -90
A1 6 5 -1 0 0 1 90
X4 -1 1 0 1 0 0 8
x5 2 -1 0 0 1 0 20
21
 Solución Algebraica - Método Simplex
Resolver usando simplex.
Min Z = - x1 + 2x2 , s.a Max (-Z) = x1 - 2x2 Max (-Z) = x1 - 2x2
6x1 + 5x2 >= 90 6x1 + 5x2 - x3 = 90 6x1 + 5x2 - x3 +A1 = 90
- x1 + x2 <= 8 - x1 + x2 + x4 = 8 - x1 + x2 + x4 = 8
2x1 - x2 <= 20 2x1 - x2 + x5 = 20 2x1 - x2 + x5 = 20
x1, x2 >= 0 x1, x2 >= 0 x1, x2 >= 0

Min A1= - 6x1 - 5x2 + x3 + 90  max (-A1) = 6x1 + 5x2 - x3 – 90

 -A1 - 6x1 - 5x2 + x3 = - 90

VB x1 x2 x3 x4 x5 A1 B cociente
F.O. -1 2 0 0 0 0 0
F.A. -6 -5 1 0 0 -1 -90
A1 6 5 -1 0 0 1 90 90/6=15
X4 -1 1 0 1 0 0 8 8/(-1)= - 8
x5 2 -1 0 0 1 0 20 20/2=10
22
 Solución Algebraica - Método Simplex

VB X1 X2 X3 X4 X5 A1 b cociente
F.O. 0 3/2 0 0 1/2 0 10
F.A. 0 -8 1 0 3 -1 -30
A1 0 8 -1 0 -3 1 30 30/8=3.75
X4 0 1/2 0 1 1/2 0 18 18/0.5=36
X1 1 -1/2 0 0 1/2 0 10 10/(-0.5)=-20

VB X1 X2 X3 X4 X5 A1 b
F.O. 0 0 3/16 0 17/16 -3/16 70/16
F.A. 0 0 0 0 0 0 0
X2 0 1 -1/8 0 -3/8 1/8 30/8
X4 0 0 1/16 1 11/16 -1/16 258/16
X1 1 0 -1/16 0 5/16 1/16 190/16

23
 Solución Algebraica - Método Simplex

VB X1 X2 X3 X4 X5 A1 b cociente
F.O. 0 3/2 0 0 1/2 0 10
F.A. 0 -8 1 0 3 -1 -30
A1 0 8 -1 0 -3 1 30 30/8=3.75
X4 0 1/2 0 1 1/2 0 18 18/0.5=36
X1 1 -1/2 0 0 1/2 0 10 10/(-0.5)=-20

VB X1 X2 X3 X4 X5 A1 b
F.O. 0 0 3/16 0 17/16 -3/16 70/16
F.A. 0 0 0 0 0 0 0
X2 0 1 -1/8 0 -3/8 1/8 30/8
X4 0 0 1/16 1 11/16 -1/16 258/16
X1 1 0 -1/16 0 5/16 1/16 190/16

24
 Solución Algebraica - Método Simplex

VB X1 X2 X3 X4 X5 A1 b cociente
F.O. 0 3/2 0 0 1/2 0 10
F.A. 0 -8 1 0 3 -1 -30
A1 0 8 -1 0 -3 1 30 30/8=3.75
X4 0 1/2 0 1 1/2 0 18 18/0.5=36
X1 1 -1/2 0 0 1/2 0 10 10/(-0.5)=-20

VB X1 X2 X3 X4 X5 A1 b
F.O. 0 0 3/16 0 17/16 -3/16 70/16
F.A. 0 0 0 0 0 0 0
X2 0 1 -1/8 0 -3/8 1/8 30/8
X4 0 0 1/16 1 11/16 -1/16 258/16
X1 1 0 -1/16 0 5/16 1/16 190/16

25
 Solución Algebraica - Método Simplex

VB X1 X2 X3 X4 X5 A1 b cociente
F.O. 0 3/2 0 0 1/2 0 10
F.A. 0 -8 1 0 3 -1 -30
A1 0 8 -1 0 -3 1 30 30/8=3.75
X4 0 1/2 0 1 1/2 0 18 18/0.5=36
X1 1 -1/2 0 0 1/2 0 10 10/(-0.5)=-20

VB X1 X2 X3 X4 X5 A1 b
F.O. 0 0 3/16 0 17/16 -3/16 70/16
F.A. 0 0 0 0 0 0 0
X2 0 1 -1/8 0 -3/8 1/8 30/8
X4 0 0 1/16 1 11/16 -1/16 258/16
X1 1 0 -1/16 0 5/16 1/16 190/16

26
 Solución Algebraica - Método Simplex
solución Final:
X1 = 190/16
X2 = 30/8
X3 = 0
X4 = 258/16
X5 = 0
A1 = 0
Z = - x1 + 2x2
Z = -190/16 + 2(30/8) = - 70/16

27
 Solución Algebraica - Método Simplex
Maximizar el lucro Z = x1 + 1.5 x2, s.a

2 x1 + 2 x2 <= 160
x1 + 2 x2 <= 120
4 x1 + 2 x2 <= 280
x1, x2 >= 0

28
Primal y dual
 Dualidad
• Multiplicadores
– Importantes en problemas de optimización
• Dualidad
– Justificación de esta importancia
– Resultados teóricos
• Aplicación práctica:
– Análisis de sensibilidad
30
 Dualidad
– Problema lineal (primal) y condiciones de
extremo:
Ax  b
min cTx AT = c
s.a Ax  b  0
T (Ax - b ) = 0
– Condiciones lineales y cuadráticas
• Tanto en x como en 

31
 Dualidad
– ¿Existe un problema en  con las condiciones
de extremo anteriores?
Ax  b
AT = c max bT
0  s.a AT = c
T(Ax - b ) = 0 0
– Problema dual
• Las variables son los multiplicadores

32
 Dualidad
• Propiedades:
– Solución de ambos problemas es la misma
• Multiplicadores del primal: variables del dual
• Variables del primal: multiplicadores del dual
– Es indiferente resolver uno u otro
• Pero el costo computacional no es el mismo
– Problema dual del dual: primal

33
 Dualidad
• Otras propiedades:
– Dualidad débil
• Para dos puntos factibles: x (factible primal) y 
(factible dual)
cTx  bT
– Los valores del dual son cotas del primal
• En los óptimos respectivos,
cTx* = bT*

34
 Dualidad
– Justificación del resultado de dualidad débil
• Si x y  son factibles,
AT = c  TAx = cTx
Ax  b ,   0  TAx  bT
 cTx  bT
• Si x y  son además óptimos,
T(Ax - b ) = 0  TAx = bT
 cTx = bT

35
 Dualidad
• Otras propiedades:
– Dualidad fuerte
• Para un problema primal (P) y su dual (D),
– Si (P) es óptimo,
(D) es óptimo (con la misma solución)
– Si (P) no está acotado,
(D) no es factible
– Si (P) no es factible,
(D) no es factible o no está acotado

36
 Dualidad
• Justificación de dualidad fuerte
• Si uno de los problemas es óptimo, los
multiplicadores son óptimos para el otro
• Si un problema no está acotado, por dualidad débil
no puede existir un punto factible del otro
• Si un problema no es factible, el otro no puede ser
óptimo
– Primal y dual son intercambiables

37
 Dualidad
• Construcción del problema dual:
– Función objetivo: min  max
Lado derecho  multiplicadores
– Restricciones:
1. (Matriz de coeficientes)T  multiplicadores
= coefs. función objetivo
2. Signo de multiplicadores

38
 Dualidad
• Ejemplo:
max cTx + dTy min bT + hT
s.a Ax + y = b s.a AT +  = c
By  h   + BT = d
x0 ,0
– Agrupando términos:
min bT - hT
s.a AT  c
 - BT = d
0
39
 Dualidad
• Interpretación económica:
– Problema primal: min cTx
s.a Ax = b
x0
– Determinar mejor nivel de utilización de procesos x
– Para hacer frente a una demanda b
– Con costo mínimo
• Decisión centralizada para toda la empresa
– Planificador central

40
 Dualidad
– Problema dual:
max bT max bT
s.a AT +  = c  s.a AT  c
0
– Determinar precios de productos demandados
– Para obtener máximo ingreso
– Beneficio cero
• Decisión descentralizada
– Mecanismo basado en precios (mercado)

41
DUALIDAD
• Problema de programación lineal:
maximizar 300 x1  200 x2
sujeto a :
x1  x2  900.000 restricción (1)

3x1  x2  1.800.000 restricción (2)

x1  700.000 restricción (3)

x2  600.000 restricción (4)

x1 , x2  0
• Problema de programación lineal primal:
maximizar 3 x1  2 x2
sujeto a :
x1  x2  9 restricción (1)
3 x1  x2  18 restricción (2)
x1  7 restricción (3)
x2  6 restricción (4)
x1 , x2  0
• Problema de programación lineal dual:

minimizar 9 y1  18 y2  7 y3  6 y4
sujeto a :
y1  3 y2  y3  3 restricción (1)
y1  y2  y4  2 restricción (2)
y1 , y2 , y3 , y4  0
maximizar 3 x1  2 x2 minimizar 9 y1  18 y2  7 y3  6 y4
sujeto a : sujeto a :
x1  x2  9 y1  3 y2  y3  3
3 x1  x2  18 y1  y2  y4  2
x1  7 y1 , y2 , y3 , y4  0
x2  6
x1 , x2  0
 Análisis de
sensibilidad
 Variaciones en los parámetros
de la formulación

• Coeficientes de la función objetivo

• Coeficientes tecnológicos de las
restricciones
• Constantes de las restricciones
(disponibilidad de recursos)
• Resolver con el simplex en forma tabulada
incluyendo los parámetros que representan
la variación de algunos de los coeficientes
• Máximizar z = 3x1 + 2x2 + 5x3 s.a.
• x1 + 2x2 + x3 <= 430
• 3x1 + 2x3 <= 460
• x1 + 4x2 <= 420
• x1, x2, x3 >= 0

Sea el Problema

Máximizar z = 3x1 + 2x2 + (5+K1)x3 s.a.

x1 + 2x2 + x3 <= 430
3x1 + 2x3 <= 460 – K2
x1 + (4+K3)x2 <= 420
x1, x2, x3 >= 0
Cambios en c

Cambios en b
 Cambios en parámetros c

Plantear el dual y analizar cambios en la

F.O. del dual:
Cambios en parámetros b
Cambios en parámetros b
Ejercicio