8 Método simplex

El método simplex es uno de los algoritmos más populares en programación lineal. Fue prop-
uesto por Dantzig, también conocido por proponer el problema de enrutamiento de vehı́culos,
VRP por sus siglas en inglés (Dantzig and Ramser 1959), uno de los problemas más estudiados
en ciencias del transporte.

8.1 Forma estándar de un LP

Las restricciones en un LP, pueden presentarse de dos maneras, en forma de ecuación o in-
ecuación. En el primer caso, el lado derecho de la restricción es igual al lado izquierdo. En el
segundo caso, los dos lados pueden ser diferentes.

Las variables, en un LP, pueden ser negativas, no negativas o no restringidas en signo (pueden
tomar valores reales positivos o negativas).

Cuando se habla de la forma estándar de un LP, este se formula de manera tal que todas las
restricciones son ecuaciones y todas las variables son no negativas.

8.1.1 Ejemplos

Ejemplo 1

La empresa Cueros Ltda. fabrica dos tipos de bolsos: el modelo premium y el modelo regular.
Cada tipo requiere 2 yardas cuadradas de cuero. Una bolso regular requiere 5 horas de de
mano de obra calificada, y el premium requiere 9 horas. Cada semana se tienen 150 yardas
cuadradas de cuero disponibles y 435 horas de mano de obra calificada. Cada bolso del modelo
regular contribuye con U M 5 a la utilidad y cada bolso del modelo de lujo contribuye con U M 8.
Formule en LP que maximice la utilidad y el LP en la forma estándar.

Definamos las variables de decisión como x1 y x2 , como el número bolsos regulares y premium
producidos a la semana, respectivamente.

La función objetivo es entonces

max z = 5x1 + 8x2

Tenemos una restricción con respecto al número de horas disponibles a la semana

5x1 + 9x2 ≤ 435

33
Por otra parte tenemos una cantidad limitada de cueros

2x1 + 2x2 ≤ 150

Por último tenemos que sólo puede producirse un número no negativo de bolsos

x1 , x2 ≥ 0

El modelo nos queda entonces como

max z =5x1 + 8x2

st :
5x1 + 9x2 ≤ 435
2x1 + 2x2 ≤ 150
x1 , x2 ≥ 0

Revisando el modelo, encontramos que las dos variables de decisión son no negativas, por tanto
se cumple con una de las condiciones. Vemos que las dos restricciones son inecuaciones, en
este caso el lado derecho es mayor o igual al lado izquierdo, por tanto usamos las denominadas
variables de holgura, que representan la diferencia entre los dos lados de la inecuación. El
modelo expresado en la forma estandar queda de la siguiente manera

max z =5x1 + 8x2

st :
5x1 + 9x2 + s1 = 435
2x1 + 2x2 + s2 = 150
x1 , x2 , s1 , s2 ≥0

Ejemplo 2

¿Recuerda el ejemplo de la dieta? Escrı́balo en la forma estándar.

El ejemplo de la dieta presentado en la Sección 7.1.1, formulado de manera concreta, quedarı́a

como se muestra a continuación

34
 min z =500x1 + 3, 000x2 + 1, 200x3 + 600x4 + 1, 500x5
st :
210x1 + 288x2 + 40x3 + 120x4 + 116x5 ≥ 2000
6x3 + 1.5x5 ≥8
0.4x1 + 3x2 + 0.5x3 + 3.3x5 ≥ 14
20x1 + 20x2 + 25x3 + 375x4 + 19x5 ≥ 800
x1 , x2 , x3 , x4 , x5 ≥0

Como en el ejemplo anterior, las variables de decisión son no negativas, por tanto se cumple
con una de las condiciones requeridas para tener el modelo en la forma estándar. Sin embargo
todas las restricciones son inecuaciones. En este caso el lado derecho es menos o igual al lado
izquierdo, por tanto usamos las denominadas variables de exceso, que representan la diferencia
entre los dos lados de la inecuación. El modelo expresado en la forma estandar queda de la
siguiente manera

min z =500x1 + 3, 000x2 + 1, 200x3 + 600x4 + 1, 500x5

st :
210x1 + 288x2 + 40x3 + 120x4 + 116x5 − e1 = 2000
6x3 + 1.5x5 − e2 =8
0.4x1 + 3x2 + 0.5x3 + 3.3x5 − e3 = 14
20x1 + 20x2 + 25x3 + 375x4 + 19x5 − e3 = 800
x1 , x2 , x3 , x4 , x5 , e1 , e 2 , e 3 , e 4 ≥0

8.2 Variables básicas y no básicas

Suponga un LP en la forma estándar con m restricciones y n variables (x1 , x2 , . . . , xn )

max (o min) z = c1 x1 + c2 x2 + . . . + cn xn
s.t. a11 x1 + a12 x2 + . . . + a1n xn ≤ b1
a21 x1 + a22 x2 + . . . + a2n xn ≤ b2
.. .. ..
. . .
am1 x1 + am2 x2 + . . . + amn xn ≤ bm

Si dado el problema anterior definimos

35
  
a11 a12 . . . a1n
 a21 a22 . . . a2n 
A =  ..
 
.. .. 
 . . . 
am1 am2 . . . amn
 
x1
 x2 
x =  .. 
 
.
xn
 
b1
 b2 
b =  .. 
 
.
bn

Para encontrar una solución básica al sistema Ax = b, se escoge un conjunto de variables

n − m (se asume n > m) y se igualan a cero. Este es el conjunto de variables no básicas.
Entonces se resuelve el sistema para las restantes n − (n − m) = m variables (conjunto de
variables básicas) y se le asignan los variables que satisfagan Ax = b.

8.2.1 Ejemplo

Encuentre todas las soluciones básicas del siguiente sistema:

x1 +x2 =3
x2 + x3 = 4

Tenemos varias opciones

x1 +x2 = 3
x2 = 4

En este caso tenemos que x2 = 4, por tanto x1 = −1, con x3 como variable no básica.

Si se toma x2 como variable no básica, el valor de las variables básicas se halla directamente.

x1 =3
x3 = 4

36
Si la variable básica es x1 , el sistema nos queda como

x2 =3
x2 + x3 = 4

De donde se obtiene que x2 = 3 y x3 = 1.

8.3 Puntos extremos

Cualquier solución básica en la que todas las variables son no negativas, es una solución
básica factible (bfs). Por otro lado, un punto en la región factible de un LP es un punto
extremo si y sólo si es una solución básica factible (bfs) del LP.

8.3.1 Ejemplo

¿Recuerda el ejemplo de Cueros Ltda presentado en la Sección 8.1.1? Encuentre todos los
puntos extremos.

Recordemos que el modelo escrito en la forma estándar es como el que se presenta a continuación

max z =5x1 + 8x2

st :
5x1 + 9x2 + s1 = 435
2x1 + 2x2 + s2 = 150
x1 , x2 , s1 , s2 ≥0

Para encontrar los puntos extremos, debemos encontrar las soluciones básicas factibles. Esto
lo logramos haciendo dos iguales a cero (no básicas)

Si x1 y x2 se asumen no básicas, tenemos que el sistema es

s1 = 435
+ s2 = 150

El valor de las variables básicas es no negativo, por lo tanto este es un punto extremo.

Si x1 y s1 se asumen no básicas, tenemos que el sistema es

37
 9x2 = 435
2x2 + s2 = 150

145 160
Como resultado tenemos que x2 = 3
y s2 = 3
, también es un punto extremo.

Si x1 y s2 se asumen no básicas, tenemos que el sistema es

9x2 + s1 = 435
2x2 = 150

En este caso tenemos que x2 = 75 y s1 = −240, una de las variables es negativa, por tanto no
es un punto extremo.

Si x2 y s1 se asumen no básicas, tenemos que el sistema es

5x1 = 435
2x1 + s2 = 150

En este caso tenemos que x1 = 87 y s2 = −24. Una de las variables es negativa, por tanto no
es un punto extremo.

Si x2 y s2 se asumen no básicas, tenemos que el sistema es

5x1 + s1 = 435
2x1 = 150

La solución al sistema es x1 = 75 y s1 = 60. El valor de las variables básicas es no negativo,

por lo tanto este es un punto extremo.

Si s1 y s2 se asumen no básicas, tenemos que el sistema es

5x1 + 9x2 = 435

2x1 + 2x2 = 150

Para resolverlo reemplazamos x1 = 75 − x2 en la primera ecuación, la cual nos queda entonces

375−5x2 +9x2 = 435, de donde se obtiene que x2 = 15. De la ecuación dos se obtiene entonces

38
que x1 = 60. El valor de las variables básicas es no negativo, por lo tanto este es un punto
extremo.

Es importante aclarar que este no es un método para resolver el problema. En este caso, puede
ser “fácil” hacer la enumeración de todas las soluciones básicas, pero en problemas de mayor
tamaño, esta puede no ser una alternativa viable. Sin embargo cabe resaltar que si un LP
tiene una solución óptima, entonces tiene una solución básica óptima, la cual coincide con un
punto extremo.

8.4 Pasos del método simplex

El método simplex consta de pocos pasos, lo que lo hace bastante sencillo. A continuación
procedemos a enumerarlos, pero la explicación se hará con un ejemplo.

1. Convierta el LP a la forma estándar

2. Obtenga una solución básica factible, de ser posible.

3. Determine si la actual solución es óptima

4. De no ser óptima la actual solución, determine, cuál de las variables no básicas debe
pasar a ser básica y cuál de las variables básicas debe pasar a ser no básica.

5. Use operaciones elementales de fila para encontrar la nueva solución básica factible, con
mejor valor de la función objetivo. Regrese al paso 3.

8.4.1 Ejemplo I

Una empresa fabrica armarios, mesas y sillas. La manufactura de cada tipo de producto
requiere madera y dos tipos de trabajo especializado: carpinterı́a y acabado, como se muestra
en la Tabla 9. Actualmente hay disponibles 500 pies de madera, 300 horas de acabado y
200 de carpinterı́a. El precio de venta es UM120,000, UM100,000 y UM80,000, por armario,
mesa y silla, respectivamente. La demanda por mesas y sillas es ilimitada, pero máximo cinco
armarios pueden ser vendidos. Encuentre las cantidades a producir que maximicen el ingreso
(usando simplex).

Recurso Armario Mesa Silla

Madera (pies) 10 6 3
Horas acabado 4 2 5
Horas carpinterı́a 2 1.5 1
Tabla 9: Recursos necesarios para la manufactura

39
Sean x1 , x2 y x3 las cantidades de armarios, mesas y sillas, respectivamente. El modelo es
bastante sencillo:

max z =120, 000x1 + 100, 000x2 + 80, 000x3

st :
10x1 + 6x2 + 3x3 ≤ 500
4x1 + 2x2 + 5x3 ≤ 300
2x1 + 1.5x2 + x3 ≤ 200
x1 ≤5
x1 , x2 , x3 ≥0

Ahora debemos escribirlo en la forma estándar.

max z =120, 000x1 + 100, 000x2 + 80, 000x3

st :
10x1 + 6x2 + 3x3 + s1 = 500
4x1 + 2x2 + 5x3 + s2 = 300
2x1 + 1.5x2 + x3 + s3 = 200
x1 + s4 =5
x1 , x2 , x3 , s1 , s2 , s3 , s4 ≥0

Para facilitar la aplicación de el método simplex, se reescribe la función objetivo y se enumeran

las filas, empezando por la fila cero. Por simplicidad se elimina la fila correspondiente a las
restricciones de no negatividad.

z − 120, 000x1 − 100, 000x2 − 80, 000x3 =0

10x1 + 6x2 + 3x3 + s1 = 500
4x1 + 2x2 + 5x3 + s2 = 300
2x1 + 1.5x2 + x3 + s3 = 200
x1 + s4 =5

Obtenemos una solución básica factible, haciendo x1 = 0, x2 = 0, x3 = 0, por tanto z = 0 y

como variables básicas tenemos que s1 = 500, s2 = 300, s3 = 200, s4 = 5. La solución actual
no es óptima porque hay variables no básicas que si aumentan su valor a uno, la función
objetivo aumenta también su valor (variables no básicas con coeficiente negativo en la fila cero).
Tomamos como candidata a ingresar al conjunto de variables básicas, aquella con coeficiente
más negativo en la fila cero (este criterio aplica sólo para ejercicios de maximización).

40
Ahora todos los elementos de la columna de x1 (variable no básica con coeficiente más neg-
ativo) deben ser iguales a cero, excepto en una de las filas distinta a la fila cero. Se dice
que en esta fila se hace el pivote. Tal fila se escoge diviendo el lado derecho por el re-
spectivo coeficiente en la fila, siempre y cuando este sea mayor a cero, y se toma el co-
eficiente con el resultado más pequeño. Para cada una de estas operaciones tenemos que
500/10 = 50, 300/4 = 75, 200/2 = 100, 5/1 = 5, por tanto tomamos la fila cuatro,
porque es la que tiene una menor relación entre el lado derecho y el coeficiente. Procedemos
a hacer operaciones elementales de fila, adicionando múltiplos de la fila cuatro a las otras y
obtenemos que

z −100, 000x2 −80, 000x3 +120, 000s4 =600,000

6x2 +3x3 +s1 −10s4 =450
2x2 +5x3 +s2 −4s4 =280
1.5x2 +x3 +s3 −2s4 =190
x1 +s4 =5

Ahora temos que que la solución básica factible es z = 600, 000, x1 = 5, s1 = 450, s2 = 280, s3 =
190, las variables no básicas son x2 , x3 , s4

Como en la fila cero, aún hay variables no básicas con coeficientes negativos, concluimos que
aún no hemos encontrado la solución óptima. Se toma la variable con corficiente más negativo
en la fila cero para ingresar al conjunto de variables básicas (x2 ). La fila sobre la que se
hará el pivote se escoge igual que en el paso anterior, pero esta vez, no se tiene en cuenta
el la fila cuatro, porque el coeficiente asociado a la variable x2 en esa fila es cero. Como
450/6 = 75 280/2 = 140 190/1.5 = 126.7, seleccionamos la fila uno. Luego de hacer las
operaciones elementales de fila, adicionando múltiplos de la fila uno a las demás, el problema
nos queda

z −30, 000x3 +16, 666.67s1 −46, 666.67s4 =8,100,000

x2 +0.5x3 +0.17s1 −1.67s4 =75
4x3 −0.33s1 +s2 −0.67s4 =130
0.25x3 −0.25s1 +s3 +0.5s4 = 77.50
x1 +s4 =5

Ahora temos que que la solución básica factible es z = 8, 100, 000, x1 = 5, x2 = 75, s2 =
130, s3 = 77.5, las variables no básicas son x3 , s1 , s4 . Ahora puede verse en la fila cero que
la variable con el coeficiente más negativo es s4 . Para seleccionar en cuál fila debe hacerse
el pivote, no se tienen en cuenta la filas uno y dos, porque el coeficiente asociado a s4 es
negativo. Se selecciona entonces la fila cuatro. Luego de hacer las operaciones elementales de
fila, usando para ello múltiplos de la fila cuatro, el problema nos queda

41
 z +46, 666.67x1 −30, 000x3 +16, 666.67s1 =8,333,333.33
1.67x1 +x2 +0.5x3 +0.17s1 =83.33
0.67x1 +4x3 −0.33s1 +s2 =133.33
−0.5x1 +0.25x3 −0.25s1 +s3 = 75
x1 +s4 =5

La solución básica factible actual es z = 8, 333, 333.33, x2 = 83.33, s2 = 133.33, s3 = 75, s4 = 5,

las variables no básicas son x1 , x3 , s1 . La variable con el coeficiente más negativo en la fila cero
que es x3 . Se pivotea en la fila dos, toda vez que 133.33/4 = 33.33 es la razón más pequeña.
Luego de hacer las operaciones elementales de fila, el problema nos queda

z +51, 666.67x1 +14, 166.67s1 +7, 500s2 =9,333,333.33

1.58x1 +x2 +0.21s1 −0.13s2 =66.67
0.17x1 +x3 −0.08s1 +0.25s2 =33.33
−0.54x1 −0.23s1 −0.06s2 +s3 = 66.67
x1 +s4 =5

No se tienen coeficientes negativos en la fila cero, por lo tanto se concluye que la solución
básica factible actual óptima, z = 9, 333, 333.33, x2 = 66.67, x3 = 33.33, s3 = 66.67, s4 = 5, las
variables no básicas son x1 , s1 , s2 . Esto quiere decir que los ingresos son máximos cuando no
se producen armarios, se producen 66.67 mesas y 33.33 sillas.

8.4.2 Ejemplo II

Dado el siguiente LP, usando el método simplex determine si tiene una única solución óptima
(encuéntrela), múltiples (encuentre dos) o no acotado.

max z =2x1 + 2x2 + 2x3

st :
x1 + 2x2 + 2x3 ≤ 40
2x1 + x2 + 2x3 ≤ 40
2x1 + 2x2 + x3 ≤ 40
x1 , x2 , x3 ≥0

Procedemos a escribirlo en la forma estándar

42
 max z =2x1 + 2x2 + 2x3
st :
x1 + 2x2 + 2x3 + s1 = 40
2x1 + x2 + 2x3 + s2 = 40
2x1 + 2x2 + x3 + s3 = 40
x1 , x2 , x3 , s1 , s2 , s3 ≥0

Previamente hemos escrito las ecuaciones, al momento de aplicar el método simplex. Ahora
procederemos a escribirlo usando la forma tableau, escribiendo sólo los coeficientes. Esta es
mucho más práctica, especialmente si se trabaja con hojas de cálculo.

z x1 x2 x3 s1 s2 s3 rhs
1 -2 -2 -2 0 0 0 0
0 1 2 2 1 0 0 40
0 2 1 2 0 1 0 40
0 2 2 1 0 0 1 40

Los coeficientes negativos en la fila cero tienen el mismo valor, por lo tanto se toma uno al
azar. El mismo tipo de decisión aplica para seleccionar entre las filas dos y tres. Cada uno de
los siguientes tableau es el resultado de una iteración del método simplex.

z x1 x2 x3 s1 s2 s3 rhs
1 0 -1 0 0 1 0 40
0 0 1.5 1 1 -0.5 0 20
0 1 0.5 1 0 0.5 0 20
0 0 1 -1 0 -1 1 0

Se selecciona la variable x2 para ingresar a la base y se pivotea sobre la fila tres.

z x1 x2 x3 s1 s2 s3 rhs
1 0 0 -1 0 0 1 40
0 0 0 2.5 1 1 -1.5 20
0 1 0 1.5 0 1 -0.5 20
0 0 1 -1 0 -1 1 0

Se selecciona la variable x3 para ingresar a la base y se pivotea sobre la fila uno.

43
 z x1 x2 x3 s1 s2 s3 rhs
1 0 0 0 0.4 0.4 0.4 48
0 0 0 1 0.4 0.4 -0.6 8
0 1 0 0 -0.6 0.4 0.4 8
0 0 1 0 0.4 -0.6 0.4 8

No hay coeficientes negativos en la fila cero, ası́ que se concluye que la solución actual es
óptima, z ∗ = 48, x1 = 8, x2 = 8, x3 = 8.

8.4.3 Ejemplo III

Dado el siguiente LP, usando el método simplex determine si tiene una única solución óptima
(encuéntrela), múltiples (encuentre dos) o no acotado.

min z =8x1 −3x2

st :
2x1 +x2 ≤ 10
x2 ≤6
2x1 −2x2 ≤8
x1 , x 2 ≥0

Procedemos a escribirlo en la forma estándar

min z =8x1 −3x2

st :
2x1 +x2 + s1 = 10
x2 + s2 =6
2x1 −2x2 + s3 =8
x1 , x2 , s1 , s2 , s3 ≥0

El procedimiento es igual, sólo cambia el criterio para seleccionar la variable que deba entrar
a la base. Ahora se selecciona la variable con el coeficiente más positivo.
z x1 x2 s1 s2 s3 rhs
1 -8 3 0 0 0 0
0 2 1 1 0 0 10
0 0 1 0 1 0 6
0 2 -2 0 0 1 8

44
Se seleciona la variable x2 para ingresar a la base y se pivotea sobre la fila dos.

z x1 x2 s1 s2 s3 rhs
1 -8 0 0 -3 0 -18
0 2 0 1 -1 0 4
0 0 1 0 1 0 6
0 2 0 0 2 1 20

No hay coeficientes positivos en la fila cero, por lo que se concluye que la solución actual
z ∗ = −18, x1 = 0, x2 = 6 es óptima. Nótese que la función objetivo puede tomar valores
negativos.

8.4.4 Ejemplo IV

Dado el siguiente LP, usando el método simplex determine si tiene una única solución óptima
(encuéntrela), múltiples (encuentre dos) o no acotado.

max z =120x1 + 70x2 + 40x3

st :
8x1 + 6x2 + x3 ≤ 48
4x1 + 2x2 + 1.5x3 ≤ 20
2x1 + 1.5x2 + 0.5x3 ≤8
x1 ≤5
x1 , x2 , x3 ≥0

Ahora debemos escribirlo en la forma estándar.

max z =120x1 + 70x2 + 40x3

st :
8x1 + 6x2 + x3 + s1 = 48
4x1 + 2x2 + 1.5x3 + s2 = 20
2x1 + 1.5x2 + 0.5x3 + s3 =8
x1 s4 =5
x1 , x2 , x3 , s 1 , s2 , s3 , s4 ≥0

Ahora se proceden a realizar las iteraciones del método simplex

45
 z x1 x2 s3 s1 s2 s3 s4 rhs
1 -120 -70 -40 0 0 0 0 0
0 8 6 1 1 0 0 0 48
0 4 2 1.5 0 1 0 0 20
0 2 1.5 0.5 0 0 1 0 8
0 1 0 0 0 0 0 1 5

Se seleciona la variable x1 para ingresar a la base y se pivotea sobre la fila tres.

z x1 x2 x3 s1 s2 s3 s4 rhs
1 0 20 -10 0 0 60 0 480
0 0 0 -1 1 0 -4 0 16
0 0 -1 0.5 0 1 -2 0 4
0 1 0.75 0.25 0 0 0.5 0 4
0 0 -0.75 -0.25 0 0 -0.5 1 1

Se seleciona la variable x3 para ingresar a la base y se pivotea sobre la fila dos.

z x1 x2 x3 s1 s2 s3 s4 rhs
1 0 0 0 0 20 20 0 560
0 0 -2 0 1 2 -8 0 24
0 0 -2 1 0 2 -4 0 8
0 1 1.25 0 0 -0.5 1.5 0 2
0 0 -1.25 0 0 0.5 -1.5 1 3

Esta es una solución óptima, z ∗ = 560, x1 = 2, x2 = 0, x3 = 8. Sin embargo puede observarse

que hay una variable no básica (x2 ) con coeficiente cero en la fila cero. Probemos qué ocurre
si se incluye en la base.

z x1 x2 x3 s1 s2 s3 s4 rhs
1 0 0 0 0 20 20 0 560
0 1.6 0 0 1 1.2 -5.6 0 27.2
0 1.6 0 1 0 1.2 -1.6 0 11.2
0 0.8 1 0 0 -0.4 1.2 0 1.6
0 1 0 0 0 0 0 1 5

Otra solución óptima es z ∗ = 560, x1 = 0, x2 = 1.6, x3 = 11.2. Es claro que hay múltiples
soluciones. Esto puede identificarse cuando el coeficiente en la fila cero, relacionado con una
variable no básica es igua la cero y no hay otra variable básica que deba seleccionarse para
entrar a la base.

46
8.4.5 Ejemplo V

Dado el siguiente LP, usando el método simplex determine si tiene una única solución óptima
(encuéntrela), múltiples (encuentre dos) o no acotado.

max z = 5x2
st :
0.5x1 − 2x2 ≤ 10
− x1 + 3x2 ≤ 2
x1 , x 2 ≥0

Procedemos a escribirlo en la forma estándar

max z = 5x2
st :
0.5x1 − 2x2 + s1 = 10
− x1 + 3x2 + s2 = 2
x1 , x2 , s1 , s2 ≥0

Se hacen las iteraciones del método simplex en el tableau.

z x1 x2 s1 s2 rhs
1 0 -5 0 0 0
0 0.5 -2 1 0 10
0 -1 3 0 1 2

Se seleciona la variable x2 para ingresar a la base y se pivotea sobre la fila dos.

z x1 x2 s1 s2 rhs
1 -1 2/3 0 0 1 2/3 3 1/3
0 - 1/6 0 1 2/3 11 1/3
0 - 1/3 1 0 1/3 2/3

La variable x1 tiene coeficiente negtivo en la fila cero, por lo que debe seleccionarse para entrar
a la base. Sin embargo, al momento de seleccionar la fila sobre la cual pivotear, se encuentra
que todos los coeficientes son negativos y no es posible seleccionar fila alguna. En estos casos
se considera que el problema es no acotado.

47
Vale la pena resaltar que un problema no acotado es distinto a uno no factible. Siendo la
principal diferencia entre ambos, que el primero tiene soluciones factibles.

9 Método simplex dos fases

El método simplex dos fases se usa cuando no existe una solución básica factible obvia al
problema. En este caso se hace uso de variables artificiales, las cuales se adicionan en las
restricciones que sean igualdades o inecuaciones del tipo “mayor que” (≥). En la primera
fase se minimiza la suma de las variables artificiales, esto se hace independentemente de si el
problema original es una minimización o una maximización.

9.1 Pasos del método simplex dos fases

1. Modificar las restricciones de manera tal que no haya ningún valor en el lado derecho
(rhs) que sea negativo.

2. Se reescribe el modelo en su forma estándar.

3. En cada restricción que sea una igualdad o una inecuación del tipo “mayor que” (≥) se
adiciona una variable artificial ai . No es necesario si en la respectiva restricción existe
previamente una variable que puede tomarse como variable básica.

4. Se optimiza el problema, sustituyendo la función objetivo originalP por la suma de las

variables artificiales. La nueva función objetivo es entonces w = ai

5. Dependiendo de el resultado del paso anterior, se procede de distintas maneras

• si w∗ > 0, el problema original se considera no factible

• si w∗ = 0 y no hay variables artificiales en la base, se sustituye la función objetivo
por la original y se aplica el método simplex.
• si w∗ = 0 y hay variables artificiales en la base, se sustituye la función objetivo por
la original. Previamente se eliminan todas las variables artificiales que no estén en
la base y las variables originales que hayan quedado con un coeficiente negativo en
la fila cero al finalizar el paso anterior.

Tenga en cuenta que la solución a la primera fase siempre será acotada y factible.

9.2 Ejemplos

Ahora se ilustrarán mediante ejemplos, cada uno de los casos mencionados previamente.

48