MODELACIÓN Y PROGAMACIÓN

MATEMÁTICA

MÉTODO SIMPLEX
JULIO CÉSAR LONDOÑO ORTEGA
Email: [email protected]
Método Simplex
 Método Simplex
Es un método que puede resolver cualquier problema de programación lineal. Además
de la solución óptima, el método Simplex entrega el análisis de sensibilidad.

El método Simplex busca la solución óptima en los extremos de la región factible, cada
extremo se denomina solución básica y se identifica algebraicamente como un sistema
de ecuaciones simultaneas.
Una solución básica se obtiene igualando a cero las variables necesarias con el fin de
igualar el número de variables y el número total de ecuaciones para que la solución sea
única y luego se resuelve el sistema con las variables restantes.
El método Simplex, parte de una solución inicial y luego se traslada sistemáticamente a
otra solución básica que mejore el valor de la función objetivo.
 Forma estándar de un modelo de
programación lineal

•Las restricciones son ecuaciones y el lado derecho (segundo miembro

de la ecuación) es no negativo en el problema primal (más adelante se
discutirá el concepto de problema primal y dual)
•Todas las variables son no negativas
•La función objetivo puede ser minimizar o maximizar.
Forma estándar de un modelo de programación lineal

Minimizar z = -2x1 + 5x2 -3x3

Sujeto a:
3x1 - 5x2+ 5x3 = 10
-3x1 - 2x2- 2x3 ≥ -15
3x1 - 5x2+ 5x3 ≥ 3
x2 ≤0
x3 No restringida
Forma estándar de un modelo de programación lineal

Minimizar equivale a maximizar el negativo

Maximizar z = 2x1 - 5x2 +3x3

En la segunda restricción el lado derecho es negativo, si

se multiplica por -1 en ambos lados de la ecuación, el lado
derecho será positivo, pero el sentido de la desigualdad
cambia.

(-1)[-3x1 - 2x2- 2x3] ≤ -1( -15)

3x1 + 2x2 + 2x3 ≤ 15
 Forma estándar de un modelo de
programación lineal

Para convertir una restricción de desigualdad en una

restricción de igualdad, se logra mediante el ingreso de
una variable de holgura para la desigualdad de menor o
igual o una variable de exceso para la restricción de
mayor o igual; así la segunda restricción queda:

3x1 + 2x2 + 2x3 + S1 = 15

Y la tercera restricción queda:

3x1 - 5x2+ 5x3 - S2 = 3

Forma estándar de un modelo de programación lineal

La variable no restringida o irrestricta se convierte

mediante la resta de dos variables positivas así:

x3 , La variable no restringida o irrestricta es igual

a:

x 3 = x 3+ - x 3-

Si x3 resulta positiva, x3- es cero

Si x3 resulta negativa, x3+ es cero.
Forma estándar de un modelo de programación
lineal

Las variables no positivas se reemplazan con la variable

negativa de esta, así:
x2 = -x2’

Por lo tanto la restricción queda:

x2’ ≥ 0

Ya que el sentido de la restricción cambia.

Una vez se tiene el modelo de programación lineal en su

forma estándar, es posible desarrollar un algoritmo
algebraico que permita encontrar una solución óptima.
 Algoritmo Simplex

Forma Matricial:
Función objetivo
Optimizar Z = C1X1+ C2X2+………+ CnXn

Sujeto a:
a11x1 + a12x2 + … + a1nxn = b1
a21x1 + a22x2 +… + a2nxn = b2
. . .
. . .
. . .
am1x1 + am2x2 + … + amnxn = bm
 Algoritmo Simplex

O equivalente a:

XB : Variables básicas, hacen

Función Objetivo Z = CXT parte de la solución
XR : Variables no – básicas, su
Sujeto a: AX = b , valor es “cero”

X ≥0 CB : Coeficientes que acompañan a

las variables básicas en la F. O
CR: Coeficientes que acompañan a
las variables no – básicas en la F.O.
C = [CB CR] B: Sub-matriz de A que acompañan
a las variables básicas
A = [B R] R: Sub-matriz de A que acompañan
a las variables no - básicas
X = [XB XR]T
 Algoritmo Simplex
Optimizar Z  C B X B  C R X R (I)
Sujeto a : BX B  RX R b (II)
X 0

Una solución básica es aquella en que XR=0 y por BX B  b  X B  B 1b

lo tanto:

Una solución básica factible es aquella solución básica X B  B 1b  X B  0

que:
Premultiplicando la ecuación (II) por B-1 B 1BX B  B 1R X R  B 1b

Notación, B 1mxmR m x ( n  m ) Y m x ( n  m )  B 1b  X B

Solución básica actual X B YX R X B (III)

se pretende es investigar la posible variación de la solución
actual, ocasionada por el futuro cambio de base.
Si se hace XR = 0, todo se reduce a la solución actual.

Premultiplicando (III) por CB X B YX R X B (III)

C B X B C BYX R  C BX B (III)

Valor actual de la función objetivo Z  C BX B

Z  C B X B C BYX R (IV)
 Restando (I – IV)

mizar Z  C B X BZ:CValor Zfuncion

R X R de cualquier
(I) : Valorobjetivo,
de cualquier funcion objetivo,
to a : Z BX B BZ
C BX C RBYX
RX  b R (IV)
(II)
: Valor de actual deZla funcion
: Valor de actual de la funcion objetivo,
objetivo,
(C XY 0
B C )X Cambio
R R
(C Ben C
Y el R )Xde
valor Cambio
R la funcionen el valor de la func
objetivo si se modificaobjetivo
la base si se modifica la base

Z  Z  (C BY C R )X R (V)
𝑪𝐵 𝒀 = 𝑪𝐵 𝒀𝑚+1 ⋮ 𝒀𝑚+2 ⋮ … ⋮ 𝒀𝑛
= 𝑪𝐵 𝒀𝑚+1 ⋮ 𝑪𝐵 𝒀𝑚+2 ⋮ … ⋮𝑪𝐵 𝒀𝑛

C R  Cm 1 Cm  2  Cn
Los términos CBY j son los productos escalares entre el vector CB y las
columnas de la matriz Y, y se le denomina Zj. Así, la ecuación V puede
transformarse a:
Z  Z  (C BY C R )X R (V)
Z  Z  ( Z j  C j )X j (VI)
j

Como solo una variable No – Básica Xj es la que entra a la base y tomará

seguramente un valor positivo, la sumatoria se reduce a un solo término,
debido a que el resto de variables básicas son cero. La ecuación (VI) se
transforma en:

Z  Z  ( Z k  Ck ) X k (VII)

Donde Xk es la variable No - básica que entrará a la base

 Criterio de Entrada

Z  Z  ( Z k  Ck ) X k (VII)

Entra a la base aquella variable cuyo Xk contribuya a

darle un mejor valor a la función objetivo, por lo tanto sí
se está:
Maximizando (Zj - CJ) debe ser lo más negativo
Minimizando (Zj - CJ) debe ser lo más positivo.
 Criterio de Salida
La ecuación (III), se puede escribir en forma explicita de la siguiente manera:

X B YX R X B (III)
 X1   y1.m1 y i.m  2  y ik  y i.m 1   X m 1 
 X1   X   y y 2.m 2  y 2k  y i.m 1  X m  2 
 X   2   2.m1
 2      
          Xk 
       
X m      
 X m   y m.m1 y m.m 2  y mk  y i.m 1   X n 
Donde se ha identificado a la variable Xk futura para entrar a la base
Cuando se efectúa el producto YXR, solo se mantendrán los términos que multiplican a Xk,
debido a que las demás variables no básicas valen cero.
  X1  X1  y1k X k
X  X  y X
 2 2 2k k
Se generan a continuación las siguientes ecuaciones: 
  
X m  X m  y mk X k

 X 1  y1k X k  0
X  y X 0
 2 2k k
Garantizando que la solución básica sea factible, entonces: 
 
 X m  ymk X k  0

 Xs 
Por lo tanto: X k  min  ; ysk  0
 ysk 
 Porqué ysk debe ser mayor que cero?
La variable que sale de la base toma el valor de cero, entonces,

X s  X s  yik X k  0
Donde Xs es la variable a salir de la base así:
Xs
Xk  ; yik  0
yik

Se establece como criterio de salida del Método Simplex:

Sale de la base aquella variable cuyo cociente q sea el mínimo, donde:

Xs
 ; ysk  0
ysk
Este cálculo se realiza únicamente con los términos de la columna k, correspondiente a la
variable que va a entrar a la base.
 Criterio de parada

Se deduce del criterio de entrada, la parada ocurre cuando no

existen variables candidatas a entrar a la base, implica que no se
puede mejorar más la función objetivo.

El proceso (Zj – Cj) ≥ 0, para maximizar

Simplex concluye
si todos los:
(Zj – Cj) ≤ 0, para minimizar
 Resumen del Método Simplex
•Parte de una solución básica factible inicial
•Proceso de cambio de base
1.Se selecciona la variable que va a entrar a la base
2.Se determina la variable a salir de la base
3.Se realiza el cambio de base
•Se verifica el proceso de parada
•La solución básica factible actual es la óptima, y concluye el proceso

Revisar la aplicación del método Simplex en forma matricial, sección 3.3 notas de clase de Vidal,
página 100
Aplicación del Método Simplex Matricial

Maximizar Z  5X 1  3X 2
Considere el modelo: Sujeto a :
3X 1  5X 2  15
5X 1  2X 2  10
X1, X 2  0

Maximizar Z  5X 1  3X 2  0S1  0S 2
Sujeto a :
Forma estándar
3X 1  5X 2  S1  15
5X 1  2X 2  S 2  10
X 1 , X 2 , S1 , S 2  0
Aplicación del Método Simplex Matricial
Maximizar Z  5X 1  3X 2  0S1  0S 2
Sujeto a :
3X 1  5X 2  S1  15
5X 1  2X 2  S 2  10
X 1 , X 2 , S1 , S 2  0
Solución inicial factible: X1=0, X2=0, S1=15, S2=10:

C B  00 C R  53

10 35
B  R 
01 52

15 S1 X1
b  XB XR
10 S2 X2
 Maximizar Z  5X 1  3X 2  0S1  0S 2
1 Sujeto a :
1 1 0 15 15 X B Es la solucion
X B B b   3X 1  5X 2  S1  15
0 1 10 10 factible inicial 5X 1  2X 2  S 2  10
X 1 , X 2 , S1 , S 2  0
15
Z  C BX B 0 0  0* 15  0* 10  0
10

Primer Cambio de Base: Criterio de entrada: (Zj −Cj) sea el “más negativo”.

Z  C BY j  C BB -1a j , donde a j son las columnas de A

que forman la matriz R

Z1  C BY 1  0 0 3 5  0
T

1 1 03 5 3 5
Y B R  
Z 2  C BY 2  0 0 5 2  0
T
0 15 2 5 2

Z1  C1  0  5  5
Entra X1 Z 2  C2  0  3  3
 Maximizar Z  5X 1  3X 2  0S1  0S 2
Sujeto a :
Criterio de Salida 3X 1  5X 2  S1  15
5X 1  2X 2  S 2  10
S1 15 3 5 X 1 X 1 , X 2 , S1 , S 2  0
XB   
 Xs  S 2 10 5 2 X 2
X k  min  ; ysk  0
15 10 
 ysk    min  ,   min5, 2  2
3 5
Sale de la base S2
Segundo Cambio de Base: Las nuevas condiciones son

13 05
C B  05 C R  03 B  R 
0 5 12

15 S1 S2
b  XB XR
10 X1 X2
 Maximizar Z  5X 1  3X 2  0S1  0S 2
Sujeto a :
3X 1  5X 2  S1  15
5X 1  2X 2  S 2  10
X 1 , X 2 , S1 , S 2  0

1
1 - 3
1 1 3 15 5 15 9
X B B b   
0 5 10 0 1 10 2
5 1 - 3 0 5  3 19
5 5 5
Y  B 1R  
9
Z  C B X B  0 5  0* 9  5* 2  10 0 1 12 1 2
5 5 5
2

T
Z1  C BY 1  0 5  3 1 1
5 5
T
Z 2  C BY 2  0 5 19 2 2
5 5
Entra X2
Z1  C1  1  0  1
Z 2  C2  2  3  1
 Maximizar Z  5X 1  3X 2  0S1  0S 2
Sujeto a :
9  5 5 S2
3 19
Criterio de Salida S1 3X 1  5X 2  S1  15
XB    5X 1  2X 2  S 2  10
X1 2 1 2 X2 X 1 , X 2 , S1 , S 2  0
5 5
 45  45
  min  , 5 
19  19

Sale de la base S1

Tercer Cambio de Base: Las nuevas condiciones son:

53 01
C B  35 C R  00 B  R 
2 5 10

15 X2 S2
b  XB XR
10 X1 S1
 Maximizar Z  5X 1  3X 2  0S1  0S 2
1 5 - 3 15 45 Sujeto a :
5 3 15 19 19 19
X B  B 1b    3X 1  5X 2  S1  15
2 5 10 - 2 5 10 20 5X 1  2X 2  S 2  10
19 19 19 X 1 , X 2 , S1 , S 2  0

Z  C B X B  235  12.37
19

-3 0 1 3 5
5
19 19 9 19
Y  B 1R  
-2 5 1 0 5 -2
19 19 19 19
T
Z1  C BY 1  3 5  3 5  16
19 19 19
T
Z 2  C BY 2  3 5 5 -2 5
19 19 19
Z1  C1  16  0  16
19 19 Se cumple el criterio
de parada
Z 2  C2  5 0  5
19 19
 Cj → 5 3 0 0

Variables Cociente
CB XB X1 X2 S1 S2
Básicas 

S1 0 15 3 5 1 0 5
S a l e ←S2 0 10 5 2 0 1 2
zj 0 0 0 0 0
z j - cj -5 -3 0 0

S a l e S1 0 9 0 3 4/5 1 - 3/5 2 3/8

Entra
X1 5 2 1 2/5 0 1/5 5

zj 10 5 2 0 1
z j - cj 0 -1 0 1

X2 3 2 7/19 0 1 5/19 - 3/19

Entra
X1 5 1 1/19 1 0 - 2/19 5/19

zj 5 3 5/19 16/19
Z máximo 12 7/19
z j - cj 0 0 5/19 16/19

Se cumple el criterio de parada, no hay mas candidatas a entrar

Valor de las
variables de la Matriz Inversa de
solución óptima La Base
Método Simplex
Casos especiales
 El Método de la Gran M

Maximizar Z  2 X 1  3 X 2
Sujeto a : X1  2 X 2  4
USO DE VARIABLES ARTIFICIALES
X1  X 2  3
X1 , X 2  0

Maximizar Z  2 X 1  3 X 2
Sujeto a : X 1  2 X 2  S1  4
MODELO EN FORMA ESTÁNDAR
X1  X 2 3
X 1 , X 2 , S1  0

Observar que no aparece la matriz idéntica de orden 2

 El Método de la Gran M

Maximizar Z  2 X 1  3 X 2
Sujeto a : X 1  2 X 2  S1  4
X1  X 2  A  3
X 1 , X 2 , S1  0  A variable artificial

Para resolver el problema original la variable artificial debe ser igual a cero
en la solución óptima, lo cual se logra la mayoría de las veces sacándola
de la base.
Esto se logra, penalizándola en la función objetivo con un valor muy grande
positivo (si se está minimizando) o muy pequeño negativo (si se está
maximizando).
 El Método de la Gran M
Maximizar Z  2 X 1  3 X 2  MA
Sujeto a : X 1  2 X 2  S1  4
X1  X 2  A  3
X 1 , X 2 , S1  0  A variable artificial

En el modelo anterior M es un valor real positivo muy grande (M >> 0 ó (M

→ +∞) ).
Los tableros, por lo tanto, serían los siguientes:
 El Método de la Gran M
Cj→ 2 3 0 -M
Variables CB XB X1 X2 S A
Básicas
← S 0 4 1 2 1 0 4/2=2
A -M 3 1 1 0 1 3/1=3
Zj -3M -M -M 0 -M
Zi-Cj -M-2 -M-3 0 0
X2 3 2 ½ 1 ½ 0
← A -M 1 ½ 0 -½ 1
Zj -6M 3/2-M/2 3 3/2+M/2
Zi-Cj -1/2- 0 3/2+M/2
M/2
X2 3 1 0 1 1 -1
X1 2 2 1 0 -1 2
Zj 7 2 3 1 1
Zi-Cj 0 0 1 1+M
Obsérvese que la variable artificial sala de la base en el segundo tablero. Una vez salga, no podrá volver a
entrar a la base, y puede incluso ignorarse esta columna para encontrar la solución óptima
 Soluciones Degeneradas
Maximizar Z  3 X 1  9 X 2
Sujeto a : X1  4 X 2  8
X1  2 X 2  4
X1 , X 2  0

Solución Solución Gráfica

Óptima
Degenerada
 Maximizar Z  3 X 1  9 X 2
Modelo en forma Sujeto a : X 1  4 X 2  S1 8
Estándar X1  2 X 2  S2  4
X 1 , X 2 , S1 , S 2  0
VARIABLES CJ 3 9 0 0
BÁSICAS CB XB X1 X2 S1 S2 θ
S1 0 8 1 4 1 0 2
S2 0 4 1 2 0 1 2
ZJ 0 0 0 0 0
ZJ-CJ -3 -9 0 0
X2 9 2 0.25 1 0.25 0 8
SOLUCIÓN S2 0 0 0.5 0 -0.5 1 0
ÓPTIMA
ZJ 18 2.25 9 2.25 0
ZJ-CJ -0.75 0 2.25 0
X2 9 2 0 1 0.5 -0.5
SOLUCIÓN X1 3 0 1 0 -1 2
ÓPTIMA NO ZJ 18 3 9 1.5 1.5
MEJORA
ZJ-CJ 0 0 1.5 1.5
 Infinitas Soluciones Óptimas
Minimizar Z  2 X 1  3 X 2  X 3
Sujeto a : X 1  4 X 2  2X 3  8
3X1  2 X 2 6
X1 , X 2 , X 3  0

Solución Óptima No Acotada

Maximizar Z  1.2 X 1  X 2  0.8 X 3
Sujeto a : X1  X2  50000
0.4 X 1  0.6 X 2  X 3  27000
X1, X 2 , X 3  0
 SOLUCIÓN NO FACTIBLE
Minimizar Z  10 X 1  15 X 2  12 X 3
Sujeto a : 5 X1  3X 2  X 3  144
- 5 X 1  6 X 2  15 X 3  240
2 X1  X 2  X 3  80
X1, X 2 , X 3  0
Solución de problemas de Programación Lineal
con el Método Simplex
Maximizar Z= 4X1 +4X2

Sujeto a:

R-1: X1 +3X2 ≤ 300

R-2: X1 + X2 ≤ 200

R-3: 6/5X1 + X2 ≤ 600

R-4: 4X1 + 7X2 ≤ 2800

Lógicas (X1 , X2 ) ≥ 0
Considere el siguiente problema:

Maximizar 4𝑋1 + 3𝑋2 + 𝑋3 + 2𝑋4

Sujeto a: 4𝑋1 + 2𝑋2 + 𝑋3 + 𝑋4 = 5
3𝑋1 + 𝑋2 +2𝑋3 + 𝑋4 ≤ 4
(𝑋1 , 𝑋2 , 𝑋3 , 𝑋4 ) ≥ 0
Considere el siguiente problema:

𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝑍 = 2𝑋1 + 𝑥2
Sujeto a:
𝑥2 ≥ 10
2𝑥1 +5𝑥2 ≥ 60
𝑥1 + 𝑥2 ≥ 18
3𝑥1 + 𝑥2 ≥ 44
𝑥1 𝑦 𝑥2 ≥ 0