5.

El Mtodo Simplex
En lo que sigue consideremos un problema de
programacin lineal en su forma estndar.
Min c 1 x 1 + c 2 x 1 + ......... + c n x n
s .a . a 11 x 1 + a 12 x 2 + ......... + a 1n x n = b 1
a 21 x 1 + a 22 x 2 + ........ + a 2 n x n = b 2

a m1 x 1 + a m 2 x 2 + ........ + a mn x n = b m
x i 0; i = 1, 2 ,...., n.
donde m n.
Matricialmente escrito como:
Min cT x
s .a . Ax = b
x 0
No existe prdida de la generalidad al suponer que un
problema viene dado en la forma estndar. En efecto,
si tuvisemos el siguiente problema:

P) Mx 9u + 2v + 5z
s.a. 4u + 3v + 6z 50
u + 2v + 3z 8
2u 4v + z = 5

u 0 ; v 0
z IR

Es posible reformular de manera equivalente el problema

anterior usando que:
1.-Siempre es posible llevar un problema de
maximizacin a uno de minimizacin. Si f(x) es la
funcin objetivo a maximizar y x* es la solucin ptima:

*
f ( x ) f ( x ), "x factible

- f ( x * ) - f ( x ), "x factible

\ x * es tambin el mnimo de - f ( x ).

2.- Cada restriccin del tipo puede ser llevada a una

ecuacin de igualdad usando una (nueva) variable de
holgura no negativa, con un coeficiente nulo en la
funcin objetivo.
3.- De igual modo, cada restriccin del tipo puede ser
llevada a una ecuacin de igualdad usando una variable de
exceso no negativa.

4.- Siempre es posible escribir una variable libre de signo

como la diferencia de dos variables no negativas.

En resumen el problema P) puede ser escrito de manera

equivalente como:
 Min 9x1 2x2 5x3 +5x4 +0x5 +0x6
4x1+ 3x2+ 6x3- 6x4+ x5 =50
x1+ 2x2 - 3x3+ 3x4 -x6 = 8
2x1 - 4x2 + x3 - x4 = 5

xi 0, i=1,2,3,4,5,6.

Con u = x1
v = x2
z = x3 - x4
s1 = x5 (HOLGURA)
s2 = x6 (EXCESO)
La bsqueda de la solucin ptima se restringe a
encontrar un vrtice ptimo y cada vrtice del conjunto
de las restricciones del problema, llamado regin de
puntos factibles, corresponde a una solucin bsica
factible del sistema Ax=b.
Esta corresponde a su vez a aquellas soluciones que
resultan de resolver el sistema para exactamente m
variables, fijando las restantes n-m en cero, llamadas
respectivamente variables bsicas y no-bsicas, que
adems deben satisfacer condiciones de no-negatividad.
Teorema Fundamental de la Programacin Lineal:
si un problema tiene solucin ptima, tiene
una solucin bsica factible ptima.

Dada una matriz B de mxm invertible, esta

induce una particin de las variables y parmetros
del modelo como lo muestra la siguiente diapositiva
 X X B
1
n X 2 m
X = . =

.
X n-m
B D n
X D

A= m C B
m

C =

n-m
C D

XB:variables bsicas.
m n-m
XD:variables no bsicas.
B : es llamada una matriz CB:costos bsicos.
de base
CD:costos no bsicos.
Criterio de Optimalidad:
T D
cT x = c xB + cD xD

(B - 1 b - B - 1 D x ) + c x
B

T T
= c D

B 1 D )x
B

b + (c
D D

-1 T -
= c T
B
T
- c D
B D B

valor actual de vector de

la funcin obj. costos
reducidos.
Ecuacin que define cada uno de los costos
reducidos: r j = c j - c TB B -1 A j , j= ndice de variable
no-bsica y Aj la respectiva columna en A de esa var.
Actual solucin bsica factible es ptima ssi rj "j
Si existe una variable no bsica xp con costo reducido
negativo, esta entra a la nueva base. Para decidir quin deja la
base, es necesario calcular el mayor valor que puede tomar la
variable entrante que garantiza la factibilidad de la nueva
solucin bsica, con
y y1 p
10

y 20 y 2 p
- -
B 1b = . B 1 Ap =

.
y y m p
m0
se debe calcular:
yk 0 y 0
= Min i / y ip > 0
y Kp y ip
x , deja la base.
k
Ejemplo. Resolver el siguiente problema de P.L.
Mx 40 x + 60 y
s .a . 2 x + y 70
x + y 40
x + 3 y 90
x , y 0

Se deben agregar 3 variables de holgura ( x1 , x2 , x3

var.bsicas), y llevar a forma estndar (x4=x y x5=y).

Min - 40 x 4 - 60 x 5
s.a . x1 + + 2 x 4 + x 5 = 70
x2+ + x 4 + x 5 = 40
x 3 + x 4 + 3 x 5 = 90
xi 0, i = 1,2,3,4,5.
Tabla inicial x1 x2 x3 x4 x5
1 0 0 2 1 70
0 1 0 1 1 40
0 0 1 1 3 90
0 0 0 -40 -60 0

Usamos como variable entrante a la base x5 ( pues r5<0).

x1 x2 x3 x4 x5
1 0 0 2 1 70
0 1 0 1 1 40
0 0 1 1 3 90
0 0 0 -40 -60 0

Se calcula Min{ 70/1, 40/1, 90/3 }=30, por lo tanto sale x3.
Actualizando, queda la siguiente tabla (no ptima)
x1 x2 x3 x4 x5
1 0 - 1/3 1 2/3 0 40
0 1 - 1/3 2/3 0 10
0 0 1/3 1/3 1 30
0 0 20 -20 0 1800

Luego la variable entrante a la base es x4 ( pues r4<0).

x1 x2 x3 x4 x5
1 0 - 1/3 1 2/3 0 40
0 1 - 1/3 2/3 0 10
0 0 1/3 1/3 1 30
0 0 20 -20 0 1800

Se calcula Min{ 40/(5/3), 10/(2/3), 30/(1/3) }= 15, por lo

tanto x2 deja la base actual.
Actualizando, queda la siguiente tabla final
x1 x2 x3 x4 x5
1 -2 1/2 1/2 0 0 15
0 1 1/2 - 1/2 1 0 15
0 - 1/2 1/2 0 1 25
0 30 10 0 0 2100

Como todos los costos reducidos son mayores o iguales

que cero nos encontramos en la solucin ptima.
x 1 15
x 0
x = x 4 = 15 , XD = 2 =
B
x 25 x 3 0
5
*
Z = -40* 15 - 60 * 25 = -2.100 .
En la formulacin inicial, tenemos como solucin ptima
x*=15, y *=25, con valor ptimo 2.100
 Resumen del Mtodo Simplex

Paso 0 : Escribir el problema de programacin lineal en su

forma estndar.

Paso 1 : Escoger una solucin bsica factible inicial.

Paso 2 : Escoger una variable no-bsica con costo reducido

negativo que determina la variable entrante, seguir al paso
tres. Si todos los costos reducidos son mayores que cero ,
parar, la actual solucin es ptima.

Paso 3 : Calcular el criterio de factibilidad que determina que

variable deja la base. Si todos los cuocientes son negativos:
problema no-acotado, parar.
Paso 4 :Actualizar la tabla de modo de despejar el valor
de las nuevas variables bsicas, los costos reducidos
y el valor de la funcin objetivo. Volver al Paso 2.

- No siempre es fcil obtener una solucin bsica

factible inicial, en las variables originales del modelo.
Para conseguir esto existen varios procedimientos:

Metodo Simplex de dos fases

Mtodo de la M- grande
 Mtodo Simplex de dos Fases

Fase 1: Se considera un problema auxiliar que resulta agregar

tantas variables auxiliares a las restricciones del problema
de modo de tener una sol. bsica factible. Resolver por
Simplex un nuevo problema que considera como funcin
objetivo la suma de las variables auxiliares. Si el valor
ptimo es cero ir a la Fase 2. En caso contrario, no existe
solucin factible.

Fase 2: Resolver por Simplex el problema original a partir de

la solucin bsica factible hallada en Fase1.
 Ejemplo:
Mx 2x 1
+ x 2

s .a . 10 x 1
+ 10 x 2
9
10 x 1
+ 5x 2
1
x i 0 , i= 1 , 2 .
Se debe agregar una variable de holgura y una variable
de exceso (x3 , x4 ), y llevarlo a su forma estndar.

Min - 2x 1 - x 2

s .a . 10 x 1 + 10 x 2
+ x 3
=9
10 x 1 + 5 x 2
-x 4
=1
x i 0 , i = 1, 2 ,3, 4 .
Aplicamos Simplex de dos Fases :
Fase 1:
Min x5
s.a . 10 x 1 + 10 x 2 + x 3 = 9
10 x 1 + 5 x 2 - x 4 + x 5 = 1
xi 0 , i = 1, 2,3, 4,5 .

As queda la siguiente tabla:

x1 x2 x3 x4 x5
10 10 1 0 0 9
10 5 0 -1 1 1
0 0 0 0 1 0
 x 1 0
x = xx3 = 9,
1 x = x = 0
B 5 D x 24 0
Luego se hace cero el costo reducido de la variable x5
de la tabla anterior, y queda la siguiente tabla inicial.
x1 x2 x3 x4 x5
10 10 1 0 0 9
10 5 0 -1 1 1
-10 -5 0 1 0 -1
Luego la variable entrante a la base es x1 ( pues r1<0).
x1 x2 x3 x4 x5
10 10 1 0 0 9
10 5 0 -1 1 1
-10 -5 0 1 0 -1
Calculamos Min{ 9/10, 1/10}= 1/10, por lo tanto sale x5.
x1 x2 x3 x4 x5

0 5 1 1 -1 8
1 1/2 0 - 1/10 1/10 1/10
0 0 0 0 0 0

0 x
x 1 / 10
2

x = 1
= , xD = 0= x
B 4
3
x 8
x
0
5
Que corresponde a la solucin ptima del problema en
la Fase 1, con valor ptimo 0. De aqu entonces
tomamos x1 y x3 como variables bsicas para fase 2.
Fase 2:
x1 x2 x3 x4
0 5 1 1 8
1 1/2 0 - 1/10 1/10
-2 -1 0 0 0
En la tabla hacemos 0 los costos reducidos de var.bsicas
x1 x2 x3 x4

0 5 1 1 8
1 1/2 0 - 1/10 1/10
0 0 0 - 1/5 1/5

Luego la variable entrante a la base es x4 ( pues r4<0).

calculamos Min{ 8/1, (-1/10)/(1/10)}= 8, por lo tanto sale x3.
x1 x2 x3 x4
0 5 1 1 8
1 1 0 1/10 9/10
0 1 1/5 0 1 4/5

x 9 / 10 x 0
x = 1= , x = 2 =
B D
x 4 8 x 3 0

Que resulta ser la solucin ptima del problema.

Algunos casos especiales

1.- Problema Infactible. Esta situacin se detecta cuando el

valor ptimo del problema de la fase 1 da mayor que cero.
2.- Mltiples soluciones ptimas. Esta situacin se detecta
cuando existen costos reducidos iguales a cero en una o
ms de las variables bsicas ptima
3.- Problema no acotado. Esta situacin se detecta cuando al
realizar el clculo de la variable que deja la base todos los
elementos ykj de la columna j en la tabla son negativos,
para j el ndice de una variable no bsica con costo
reducido negativo.