Investigacin de Operaciones

Mtodo SIMPLEX
FELIPE CASELLI B.
INGENIERO CIVIL INDUSTRIAL
MAGSTER EN INGENIERA DE NEGOCIOS

2015

PL, Introduccin al Mtodo

SIMPLEX
Conceptos previos:
Algoritmo
Concavidad/convexidad de conjuntos y
funciones.
Dependencia/Independencia de Vectores
Rango de la Matriz.
Operaciones fila con Matrices (Gauss-Jordan
para sistemas de ecuaciones lineales Ax=b).
Inversa de Matrices.

PL, Introduccin al Mtodo

SIMPLEX
El mtodo del SIMPLEX fue creado en 1947
por el matemtico George Dantzig .
El mtodo del SIMPLEX se utiliza, para resolver
problemas de programacin lineal en los que
intervienen dos o ms variables.
El lgebra matricial y el proceso de eliminacin
de Gauss-Jordan para resolver un sistema de
ecuaciones lineales constituyen la base del
mtodo SIMPLEX.

PL, Introduccin al Mtodo

SIMPLEX
Para un Problema de Programacin Lineal se
quiere encontrar el vector solucin que lo optimiza
El SIMPLEX es un procedimiento iterativo que
permite ir mejorando la solucin a cada paso.
El proceso concluye cuando no es posible seguir
mejorando dicha solucin.

El mtodo del SIMPLEX se basa en la siguiente

propiedad:
Si la funcin objetivo f, no toma su valor mximo en
el vrtice A, entonces hay una arista que parte de A,
a lo largo de la cual f aumenta.
4

PL, Introduccin al Mtodo

SIMPLEX
El vector solucin ser considerado como la
base las variables que lo componen sern
Variables Bsicas.
Las variables restantes sern Variables No
Bsicas y no formarn parte de la base.
Para un problema con N variables de decisin
(no negativas) y M restricciones del tipo ,
cuntas variables habr en total?, cuntas
de ellas sern variables bsicas?

SIMPLEX, Descripcin
General
Dado un problema con R variables (incluyendo
las de restriccin) y M restricciones:
Si cada eleccin de variables no bsicas diera
una solucin bsica, se podran elegir R - M
variables no bsicas generando el siguiente
total de soluciones (vrtices):

R
R!
=
M ( R M )! M !
6

Mtodo SIMPLEX, Descripcin

General
El Simplex considera los siguientes pasos:
1. Dejar el problema de la forma estndar
2. Escribir la tabla inicial simplex: encontrar la Solucin
Bsica Factible Inicial.
3. Verificar si se cumple el criterio de optimalidad.
Si no se cumple, encontrar solucin adyacente:
encontrar la Variable No Bsica que entra en la base y
la Variable Bsica que sale de la base. Pasar al paso 4
Si se cumple, termina el algoritmo

4. Encontrar los coeficientes de la nueva tabla y volver

al paso 3
7

Mtodo SIMPLEX, Descripcin

General
Requerimientos del algoritmo:
1. Vector lado derecho con coeficientes no
negativos.
2. Variables no negativas.

PL, Introduccin al Mtodo

SIMPLEX
Ejemplo:
Max Z= f(x,y)= 3x + 2y
sujeto a:
2x + y 18
2x + 3y 42
3x + y 24
x, y 0

5 variables y 3 restricciones 10 soluciones bsicas

(solo 5 factibles)
9

SIMPLEX, Descripcin
General para maximizacin
1.

Convertir el PPL en su forma estndar

Convertir las desigualdades en igualdades
Igualar la funcin objetivo a cero

2.

3.

Ubicar Solucin Bsica Factible de inicio

Para problemas en que todas las restricciones son , con lados

derechos no negativos se usan como variables bsicas de inicio las
holguras

Verificar si se cumple criterio de optimalidad para la Base actual

(todos los coeficientes del rengln Z son no negativos):
Si no lo es, se determina una nueva sbf adyacente: Entra a la base la
variable NO bsica con coeficiente ms negativo, la columna de la
Variable No Bsica que entra a la base se denomina columna pivote.
Sale de la base la Variable Bsica que gane la prueba del cociente:
divisin de los coeficientes de la columna solucin por los coeficientes
positivos de la columna pivote, gana la variable con resultado menor. La
fila de la variable que sale de la base se denomina fila pivote. Pasar a 4.
Si lo es, detenerse.

4.

Se realizan operaciones fila para generar la forma cannica nueva,

se retorna a 3 y se usa la nueva sbf.
10

SIMPLEX, Dejar el problema

de la forma estndar.

Para convertirlas en igualdades se introduce una

variable de holgura para cada una de las
restricciones:
2x + y + h1
= 18
2x + 3y +
h2
= 42
3x + y +
h3
= 24
Se iguala la Funcin Objetivo a cero:
Z - 3x - 2y = 0

11

SIMPLEX, Escribir la tabla

inicial
Base

Habr una columna (j) para

cada variable del problema
y una fila (i) para cada
restriccin ms una ltima
fila para los coeficientes de
la funcin objetivo, se
agregarn los coeficientes
de las igualdades
obtenidas en su posicin
correspondiente (i,j).

Variables de
Decisin

Variables de Holgura

Valores
Solucin

h1

h2

h3

h1

18

h2

42

h3

24

-3

-2

12

SIMPLEX, Tabla inicial:

Condicin de Optimalidad
Verificacin del criterio
de optimalidad: si
todos los Cz 0 se ha
llegado al ptimo.
Entra a la base la
variable con el
coeficiente en Z ms
negativo
Si existiesen dos o
ms coeficientes
iguales que cumplan la
condicin anterior,
entonces se elige uno
cualquiera de ellos
(usted rompe el
empate).

Base

Variables de
Decisin

Variables de Holgura

Valores
Solucin

h1

h2

h3

h1

18

h2

42

h3

24

-3

-2

13

SIMPLEX, Tabla inicial:

Condicin de Optimalidad
Base
Variables de
Variables de Holgura
Valores
Para encontrar la
Decisin
Solucin
variable bsica que
x
y
h1
h2
h3
tiene que salir de la
base se hace la prueba
h1
2
1
1
0
0
18
del cociente: dividir
cada coeficiente de la
h2
2
3
0
1
0
42
columna solucin por el
trmino correspondiente h3
3
1
0
0
1
24
de la columna pivote,
Z
-3
-2
0
0
0
0
ssi estos ltimos son
mayores que cero.
Sale de la base la VB con cociente menor, eso seala a la fila
pivote.

14

SIMPLEX, Tabla inicial:

Condicin de Optimalidad
Resultado prueba
cociente:
h1: 9
h2: 21
h3: 8

Base

Variables de
Decisin

Variables de Holgura

Valores
Solucin

h1

h2

h3

h1

18

h2

42

En la interseccin de la
fila pivote y columna
h3
3
1
0
0
1
24
pivote est el elemento
Z
-3
-2
0
0
0
0
pivote operacional, en
este caso: 3.
En el caso de que todos los coeficientes de la columna pivote
fuesen menores o iguales a cero, entonces se tendra una
solucin no acotada y no se puede seguir.
Si al calcular los cocientes, dos o ms son iguales, indica que
cualquiera de esas variables bsicas pueden salir de la base. Uno
15
rompe el empate (la siguiente solucin ser degenerada).

SIMPLEX, Encontrar los

coeficientes de la nueva tabla
Los nuevos coeficientes de la columna pivote
(x) se obtienen dividiendo todos los coeficientes
de la fila pivote (h3) por el pivote operacional
(3), que es el que hay que convertir en 1.
A continuacin mediante la reduccin
gaussiana hacemos cero los restantes trminos
de la columna pivote, con lo que obtenemos los
nuevos coeficientes de las otras filas
incluyendo los de la funcin objetivo.

16

SIMPLEX, Encontrar los

coeficientes de la nueva tabla
Dicho de otra forma:
Fila pivote:
Nueva fila pivote= (Fila pivote original)
(Pivote operacional)

Resto de las filas:

Nueva fila= (Fila original) - (Coeficiente de la
fila original en la columna pivote) x (Nueva fila
pivote)

17

SIMPLEX, Encontrar los

coeficientes de la nueva tabla
Verificacin criterio de optimalidad
y entra a la base por
ser la variable con
coeficiente ms
negativo (-1 )
Resultados prueba
cuociente:
h1: 6
h2: 11.1
x : 24

Sale h1.
Elemento pivote
operacional: 1/3.

Base

Variables de
Decisin

Variables de Holgura

Valores
Solucin

h1

h2

h3

h1

1/3

-2/3

h2

7/3

-2/3

26

1/3

1/3

-1

24

18

SIMPLEX, Encontrar los

coeficientes de la nueva tabla
1. Verificar Criterio de
optimalidad.
2. Identificar Variable No
Bsica que entra en la
base.
3. Identificar la Variable
Bsica que sale de la
base.
4. Resultados prueba:
1. 6/(-2) = n/a
2. 12/4 = 3
3. 6/1 = 6

5. VB que sale es h2.

6. El elemento pivote, que
ahora hay que hacer 1, es
4.

Base

Variables de
Decisin

Variables de Holgura

Valores
Solucin

h1

h2

h3

-2

h2

-7

12

-1

-1

30

19

SIMPLEX, Encontrar los

coeficientes de la nueva tabla

Base

y
h3
x
Z

Variables de
Decisin

x
0
0
1
0

y
1
0
0
0

Variables de Holgura

h1
-1/2
-7/4
3/4
5/4

h2
1/2
1/4
-1/4
1/4

h3
0
1
0
0

Valores
Solucin

12
3
3
33

Como todos los coeficientes de la fila de la funcin objetivo son

no negativos, hemos llegado a la solucin ptima

20

SIMPLEX, Interpretacin
Geomtrica
Las sucesivas tablas que hemos
construido van proporcionando el valor
de la funcin objetivo en los distintos
vrtices, ajustndose, a la vez, los
coeficientes de las variables iniciales y
de holgura.
En la primera iteracin (Tabla I) han
permanecido todos los coeficientes
iguales, se ha calculado el valor de la
funcin objetivo en el vrtice A(0,0),
siendo este 0.
A continuacin se desplaza por la arista
AB, calculando el valor de f , hasta llegar
a B, este paso se visualiza en la Tabla II.
21

SIMPLEX, Interpretacin
Geomtrica

En esta segunda iteracin se ha calculado

el valor que corresponde al vrtice B(8,0):
Z=f(8,0) = 24
Sigue por la arista BC, hasta llegar a C,
donde se obtienen los datos de la Tabla III.
En esta tercera iteracin se ha calculado el
valor que corresponde al vrtice C(6,6) :
Z=f(6,6)=30.

22

SIMPLEX, Interpretacin
Geomtrica

Contina haciendo clculos a travs de la arista

CD, hasta llegar al vrtice D. Los resultados que
se obtienen son los de la Tabla IV.
Concluye con esta tabla, advirtiendo que ha
terminado (comprobando que la solucin no
mejora al desplazarse por la arista DE)
El valor mximo de la funcin objetivo es 33, y
corresponde a x = 3 e y = 12 (vrtice D).
Si se calcula el valor de la funcin objetivo en el
vrtice E(0,14), se verifica que su valor no
supera las 33 unidades
Z= f(0,14)= 3x0 + 2x14 = 28
23

Simplex, resumen inicio y

tabla final
Max Z= f(x,y)= 3x + 2y
sujeto a:
2x + y 18
2x + 3y 42
3x + y 24
x, y 0
Base

Z - 3x - 2y = 0
2x + y + h1 = 18
2x + 3y + h2 = 42
3x + y + h3 = 24

Variables de Decisin

Variables de Holgura

Valores
Solucin

h1

h2

h3

-1/2

1/2

12

h3

-7/4

1/4

-3/4

-1/4

5/4

1/4

33

5 variables, 3 restricciones 10 vrtices; solo 5 factibles (con

SIMPLEX se complet en 4 iteraciones)
24

SIMPLEX, Algunos Casos

Especiales
Minimizacin de un problema de programacin lineal
Problemas de PL con mltiples soluciones ptimas
Problemas de PL no acotados
Este caso ya se mencion: Recuerda cmo se identificaba?

Problemas de PL con variables no restringidas

Problemas de PL con restricciones del tipo (solucin
artificial de inicio)
Problemas de PL sin solucin factible
Problemas de PL con solucin degenerada

25

SIMPLEX, Minimizacin de un
Problema de Programacin Lineal

1. Se puede hacer la equivalencia entre Min z=

f(x1,..xi) y Max -Z = -f(x1,..xi) y seguir el
algoritmo de la misma forma.
2. Se puede hacer una modificacin al algoritmo
cambiando el sentido del criterio de entrada
de variables a la base: se elige la variable
cuyo valor, en la fila de la funcin objetivo,
sea el mayor de los positivos y se finalizan
las iteraciones cuando todos los coeficientes
de la fila de la funcin objetivo son negativos.
26

SIMPLEX, Algunos Casos

Especiales

Minimizacin de un problema de programacin lineal

Problemas de PL con mltiples soluciones ptimas
Problemas de PL no acotados
Problemas de PL con variables no restringidas
Problemas de PL con restricciones del tipo o =
Problemas de PL sin solucin factible

27

SIMPLEX, Mltiples puntos para

la Solucin ptima
Max Z = 60x1 + 35x2 + 20x3
s.a.
8x1 + 6x2 +
x3 48
4x1 + 2x2 + 1,5x3 20
2x1 + 1,5x2 + 0,5x3 8
x2
5
x1, x2, x3 0

It 0
Z
H1
H2
H3
H4

X1
-60
8
4
2
0

Z - 60x1 - 35x2 - 20x3 = 0

s.a.
8x1 + 6x2 +
x3 + h1
= 48
4x1 + 2x2 + 1,5x3
+h2
= 20
2x1 + 1,5x2 + 0,5x3
+ h3
= 8
x2
+ h4 = 5
x1, x2, x3, h1, h2, h3, h4 0

X2
-35
6
2
1,5
1

X3
-20
1
1,5
0,5
0

H1
0
1
0
0
0

H2
0
0
1
0
0

H3
0
0
0
1
0

H4
0
0
0
0
1

B
0
48
20
8
5

28

It 0
Z
H1
H2
H3
H4

X1
-60
8
4
2
0

X2
-35
6
2
1,5
1

X3
-20
1
1,5
0,5
0

H1
0
1
0
0
0

H2
0
0
1
0
0

H3
0
0
0
1
0

H4
0
0
0
0
1

B
0
48
20
8
5

It 1
Z
H1
H2
X1
H4

X1
0
0
0
1
0

X2
10
0
-1
0,75
1

X3
-5
-1
0,5
0,25
0

H1
0
1
0
0
0

H2
0
0
1
0
0

H3
30
-4
-2
0,5
0

H4
0
0
0
0
1

B
240
16
4
4
5

It 2
Z
H1
X3
X1
H4

X1
0
0
0
1
0

X2
0
-2
-2
1,25
1

X3
0
0
1
0
0

H1
0
1
0
0
0

H2
10
2
2
-0,5
0

H3
10
-8
-4
1,5
0

H4
0
0
0
0
1

B
280
24
8
2
5
29

It 2
Z
H1
X3
X1
H4

X1
0
0
0
1
0

X2
0
-2
-2
1,25
1

X3
0
0
1
0
0

H1
0
1
0
0
0

H2
10
2
2
-0,5
0

H3
10
-8
-4
1,5
0

H4
0
0
0
0
1

B
280
24
8
2
5

It 3
Z
H1
X3
X2
H4

X1
0
1,6
1,6
0,8
-0,8

X2
0
0
0
1
0

X3
0
0
1
0
0

H1
0
1
0
0
0

H2
10
1,2
1,2
-0,4
0,4

H3
10
-5,6
-1,6
1,2
-1,2

H4
0
0
0
0
1

B
280
27,2
11,2
1,6
3,4

Z= f(x1, x2, x3) = 60x1 + 35x2 + 20x3

Solucin 1:
Solucin 2:
f (2, 0, 8) = 280
f (0, 1.6, 11.2) = 280
30

SIMPLEX, Mltiples puntos

para la Solucin ptima
Por regla, con el algoritmo SIMPLEX, en el
rengln de Z los coeficientes de las variables
bsicas tendrn valor igual a cero y las
variables no bsicas tendrn valores No
Negativos (para el caso de Maximizacin).
Si en el rengln Z una Variable No Bsica
tiene coeficiente igual a cero, es posible que
el problema tenga mltiples puntos para
solucin ptima (para un mismo valor de la F.
O.).
31

SIMPLEX, Algunos Casos

Especiales

Minimizacin de un problema de programacin lineal

Problemas de PL con mltiples soluciones ptimas
Problemas de PL no acotados
Problemas de PL con variables no restringidas
Problemas de PL con restricciones del tipo o =
Problemas de PL sin solucin factible

32

SIMPLEX, Problemas con

solucin no acotada
Breadco Bakeries elabora dos clases de pan:
baguette y pan negro. Cada baguette se vende en
36 centavos y cada hogaza de pan negro se vende
en 30 centavos. Para elaborar una baguette se
requieren 1 paquete de levadura y 6 onzas de
harina; para el pan negro se requiere 1 paquete de
levadura y 5 onzas de harina. Breadco tiene en la
actualidad 5 paquetes de levadura y 10 onzas de
harina. Se pueden comprar ms paquetes de
levadura a 3 centavos cada uno y harina a 4
centavos la onza. Plantee y resuelva un modelo de
PL con el que se pueda maximizar la utilidad de
Breadco.

33

SIMPLEX, Problemas con

solucin no acotada
Sean X1: La cantidad, en unidades, de Baguettes a hornear.
X2: La cantidad, en unidades, de hogazas de pan negro a hornear.
X3: La cantidad, en paquetes, de levadura a comprar.
X4: La cantidad, en onzas, de harina a comprar.

Max Z = 36x1 + 30x2 - 3x3 - 4x4

S.a.
1)

Restriccin de Levadura:

2)

Restriccin de la Harina:

3)

No Negatividad:

x1 + x 2 x3 5
6 x1 + 5 x 2 x 4 10
x1, x 2, x3, x 4 0

34

SIMPLEX, Problemas con

solucin no acotada
It 0
Z
H1
H2

X1
-36
1
6

X2
-30
1
5

X3
3
-1
0

X4
4
0
-1

H1
0
1
0

H2
0
0
1

B
0
5
10

It 1
Z
H1
X1

X1
0
0
1

X2
0
0,17
0,83

X3
3
-1
0

X4
-2
0,17
-0,17

H1
0
1
0

H2
6
-0,17
0,17

B
60
3,33
1,67

It 2
Z
X4
X1

X1
0
0
1

X2
2
1
1

X3
-9
-6
-1

X4
0
1
0

H1
12
6
1

H2
4
-1
0

B
100
20
5
35

SIMPLEX, Problemas con

solucin no acotada

Cuando no se ha llegado a la solucin ptima, y los

coeficientes de la columna pivote son nicamente
valores No Positivos (para cada restriccin), no se
puede hacer la prueba del cociente y el PPL es No
Acotado.
Al ser todos los cocientes no positivos quiere decir
que el valor de la Variable Entrante puede ser tan
grande como se quiera sin hacer que las Variables
Bsicas actuales queden negativas.

36

SIMPLEX, Algunos Casos

Especiales

Minimizacin de un problema de programacin lineal

Problemas de PL con mltiples soluciones ptimas
Problemas de PL no acotados
Problemas de PL con variables no restringidas
Problemas de PL con restricciones del tipo o =
Problemas de PL sin solucin factible

37

SIMPLEX, Problemas con

Variables No Restringidas

SIMPLEX requiere que todas las variables sean No

Negativas.

POR QU?

Si X es no restringida de signo se debe hacer la

transformacin:
X = X+ - XDonde tanto X+ como X- sern variables 0 y se
pueden incluir en el modelo para ser resuelto por
SIMPLEX

38

SIMPLEX, Problemas con

Variables No Restringidas
Adaptado del ejemplo 3.1-1, p. 73. Taha, H.; Investigacin de operaciones, 7 edicin, Pearson Educacin.

McBurger es un restaurante de comida rpida que

vende hamburguesas extra y de queso. En una extra se
usa un cuarto de libra de carne, en una de queso slo
se una 0.2 lb. El restaurante comienza el da con 200
lb de carne, pero puede pedir ms, con un costo
adicional de 25 centavos por libra para cubrir el costo
de la entrega. Toda carne que sobre al final del da se
dona a instituciones caritativas y se incurre en un costo
adicional de 10 centavos por libra entregada. Las
utilidades de McBurger son 20 centavos por una extra y
15 centavos por una de queso. En total, McBurger no
espera vender ms de 900 hamburguesas en cualquier
da. Cuntas hamburguesas de cada tipo debe
planear McBurger para el da?
39

SIMPLEX, Problemas con

Variables No Restringidas
Sean
X1 la cantidad a hacer de hamburguesas extra [un]
X2 la cantidad a hacer de hamburguesas de queso [un]
X3 la variacin de carne respecto del disponible (cantidad
faltante o sobrante) [lb]

Restricciones
Cantidad mxima esperada de hamburguesas a vender:
X1 + X2 900
Cantidad mxima de carne a utilizar:
0.25X1 + 0.2X2 + X3+ - X3- = 200
0.25X1 + 0.2X2 + X3 200
Sustitucin variable nrs:
X3 = X3+ - X3-

F.O.: Max Z = 0.2X1 + 0.15X2 0.1 X3+ 0.25X3 F.O.: Max Z = 0.2X1 + 0.15X2 ?
40

SIMPLEX, Problemas con

Variables No Restringidas
En la Tabla de SIMPLEX la columna de X+
siempre tendr signo contrario a X-. Las 2 no
pueden ser parte de una sfb de forma
simultnea.
Como resultado se pueden dar los siguientes
casos:
X + > 0 y X- = 0
X + = 0 y X- > 0
X + = X-

X = X+
X = - XX=0

42

SIMPLEX, Algunos Casos

Especiales

Minimizacin de un problema de programacin lineal

Problemas de PL con mltiples soluciones ptimas
Problemas de PL no acotados
Problemas de PL con variables no restringidas
Problemas de PL con restricciones del tipo o =
Problemas de PL sin solucin factible

43

SIMPLEX, Problemas con

Solucin Artificial de Inicio
En todo caso en que una restriccin tenga
signo distinto de , se debe de agregar una
variable artificial para obtener una solucin
factible inicial (artificial).
POR QU?

44

SIMPLEX, Problemas con Solucin

Artificial de Inicio

Min z = 2x1 + 3x2

Sa
x1 + x2 4
x1 + 3 x2 20
x1 + x2 = 10
x1, x2 0

z - 2x1 - 3x2

=0

x1 + x2 + h
x1 + 3 x2

=4
s + R1

= 20

x1 + x2 +
R2 = 10
x1, x2, h, s, R1, R2 0

El problema artificial se puede solucionar a travs de dos

mtodos:
Mtodo de la M grande
Mtodo de las dos fases

45

SIMPLEX, Mtodo de la M
grande
1. Se estandariza el problema.
2. Crear una variable artificial para cada restriccin del tipo:
ax=b o axb
3. Agregar las variables artificiales en la FO con coeficiente M
(MUY GRANDE) que empeore el valor de la FO:
Para problema de Max usar M
Para problema de Min usar +M
4. Se genera la tabla inicial y se iguala los coeficientes de las VB
en el rengln Z a 0 (para las variables artificiales)
5. Se realiza procedimiento del SIMPLEX
Para problemas de Max entra VNB con coef. + negativo
Para problemas de Min entra VNB con coef. + positivo
6. Si una variable artificial queda en iteracin final el problema es
NO Factible
46

SIMPLEX, Problemas con Solucin

Artificial de Inicio

Max Z = 5x1 + 5x2 - 2x3

s.a:
4 x1 + 2 x2 + x3 20
x1 + 4 x2 5 x3 = 60
x1, x2, x3 0
Iteracin 0
VB

X1

Z - 5x1 - 5x2 + 2x3 + MR = 0

4 x1 + 2 x2 + x3 + H = 20
x1 + 4 x2 5 x3 + R = 60
x1, x2, x3, H, R 0

X2

X3

SOLN

47

SIMPLEX, Problemas con

Solucin Artificial de Inicio
Iteracin 0
VB
X1
X2
X3
H
R
H
4
2
1
1
0
R
1
4
-5
0
1
Z
-5
-5
2
0
M
1.- Se debe realizar operaciones filas para dejar el coeficiente de las VB = 0.
Iteracin 1
VB
X1
X2
X3
H
R
H
4
2
1
1
0
R
1
4
-5
0
1
Z
-M-5
-4M-5
5M+2
0
0
Iteracin 2
VB
X2
R
Z

X1
2
1
7M+5

X2
1
4
0

X3
0,5
-5
7M+4,5

H
0,5
0
2M+2,5

R
0
1
0

SOLN
20
60
0

SOLN
20
60
-60M

SOLN
10
60
-20M+50

Por lo tanto, este problema NO es factible

48

SIMPLEX, Mtodo de las dos

Fases
Se separa el problema en dos (cada fase)
Fase 1:
Se Minimiza la suma de las variables artificiales, usando las
restricciones del problema original; la solucin de este
problema ser la sbf inicial para la fase 2. Esto es
independiente de si el problema original es de Max o Min.

Fase 2:
Para la tabla de inicio de la Fase 2 se utiliza como
coeficientes de restriccin los obtenidos en la Fase 1, la sbf
inicial ser la solucin antes obtenida
Se reemplaza la fila de la FO de la Fase 1 por los
coeficientes de la FO del problema original estandarizado y
se verifica la coherencia del problema.
Se realiza el procedimiento SIMPLEX de forma normal de
acuerdo al objetivo del problema original
49

SIMPLEX, Mtodo de las dos

Fases
Problema No Factible: en la Fase 1 la solucin
ptima incluye una variable artificial mayor que
0 (R>0). Si el problema fuera factible las
variables artificiales no seran necesarias, i.e.
R=0
Problema Factible:
Sin Rs en sbf inicial Fase 2
Con Rs en sbf inicial en Fase 2: en tabla final R
tiene valor 0 en rengln Z

50

SIMPLEX, Mtodo de las dos

Fases

Max Z = x1 + x2
s.a:
6 x1 + 4 x2 = 36
4 x1 + 4 x2 30
x1 + x2 20
x1, x2 0

Fase I:

Z - x1 - x2 = 0
6 x1 + 4 x2 +
R1
4 x1 + 4 x2 - S +
R2
x1 + x2 +
H

Min W = R1 + R2
s.a
6 x1 + 4 x2 +
R1
4 x1 + 4 x2 - S +
R2
x1 + x2 +
H

= 36
= 30
= 20

= 36
= 30
= 20

51

SIMPLEX, Mtodo de las dos

Fases
VB
R1
R2
H
W

X1
6
4
1
0

X2
4
4
1
0

S
0
-1
0
0

R1
1
0
0
-1

R2
0
1
0
-1

H
0
0
1
0

B
36
30
20
0

1.- Se debe realizar operaciones filas para dejar el coeficiente de las VB = 0.

VB
R1
R2
H
W'

X1
6
4
1
10

X2
4
4
1
8

S
0
-1
0
-1

R1
1
0
0
0

R2
0
1
0
0

H
0
0
1
0

B
36
30
20
66

Prueba Cociente
6
7 1/2
20

VB
X1
R2
H
W

X1
1
0
0
0

X2
2/3
1 1/3
1/3
1 1/3

S
0
-1
0
-1

R1
1/6
- 2/3
- 1/6
-1 2/3

R2
0
1
0
0

H
0
0
1
0

B
6
6
14
6

Prueba Cociente
9
4 1/2
42

52

SIMPLEX, Mtodo de las dos

Fases
VB
X1
X2
H
W

X1
1
0
0
0

X2
0
1
0
0

S
1/2
- 3/4
1/4
0

R1
1/2
- 1/2
0
-1

Ahora que se lleg al ptimo se

vuelve al problema original
cambiando SOLO los coeficientes
de la fila funcin objetivo.
Luego se debe dejar en 0 los
coeficientes en Z de las VB.
VB
X1
X2
H
Z

X1
1
0
0
-1

X2
0
1
0
-1

S
1/2
- 3/4
1/4
0

R1
1/2
- 1/2
0
0

R2
- 1/2
3/4
- 1/4
-1

H
0
0
1
0

B
3
4 1/2
12 1/2
0

Prueba C.
6
N/A
50

Z - x1 - x2 = 0
6 x1 + 4 x2 +
R1
4 x1 + 4 x2 - S +
R2
x1 + x2 +
H
R2
- 1/2
3/4
- 1/4
0

H
0
0
1
0

B
3
4 1/2
12 1/2
0

Prueba C.
N/A

= 36
= 30
= 20
6
50

Se pueden bloquear las variables artificiales y no considerarlas para las operaciones

sucesivas.
53

SIMPLEX, Mtodo de las dos

Fases

VB
X1
X2

X1
1
0

X2
0
1

S
1/2
- 3/4

R1
1/2
- 1/2

R2
- 1/2
3/4

H
0
0

B
3
4 1/2

H
Z'

0
0

0
0

1/4
- 1/4

0
0

- 1/4
1/4

1
0

12 1/2
7 1/2

VB
S
X2
H
Z

X1
2
1 1/2
- 1/2
1/2

X2
0
1
0
0

S
1
0
0
0

H
0
0
1
0

Prueba
Cuociente
6
N/A
50

B
6
9
11
9

Esta tabla es la ptima. El problema tiene solucin nica con

X2= 9 y Z = 9.

54

SIMPLEX, Algunos Casos

Especiales
Minimizacin de un problema de programacin lineal
Cambiar criterio de optimalidad (entrada de variable no bsica a la
base)

Problemas de PL con mltiples soluciones ptimas

Coeficiente en Z de una VNB=0

Problemas de PL no acotados
No hay VB candidata a salir de la base

Problemas de PL con variables no restringidas

Transformacin de la variable nrs a otras no negativas

Problemas de PL con restricciones del tipo o =

Se agrega una variable artificial a cada restriccin con signo distinto

de , las que sern parte de la sbfi

Problemas de PL sin solucin factible

En la solucin ptima al menos una variable artificial es VB

Problema con solucin degenerada

Punto sobre-restringido, variable bsica con valor cero
55

Max Z = 3X1 + 4X2 - X3

s.a.
2X1 + X2 = 20
2X3 5;

Ejercicio

Resuelva el siguiente problema mediante

Simplex, utilice el mtodo de las dos fases.
Max Z = 3X1 + 4X2 - X3
s.a.
2X1 + X2 = 20
2X3 5;
Xi 0; i=1, 2, 3

56