Metodo Simplex

Fundamentos de Investigaci´n de Operaciones
o
Investigaci´n de Operaciones 1
o
M´todo Simplex
e
1 de agosto de 2004

1.

Estandarizaci´n
o

Cuando se plantea un modelo de LP pueden existir igualdades y desigualdades. De la misma forma pueden existir variables que deben ser no negativas o bien sin restricci´n de signo (srs). Antes de
o
emplear el m´todo Simplex para resolver un LP,el problema debe ser convertido en uno equivalente
e
en el cual todas las restricciones son ecuaciones y todas las variables son no negativas. Esta versi´n
o
equivalente se denomina forma est´ndar del LP.
a
Para convertir un LP en su forma est´ndar cada desigualdad debe ser transformada en una iguala
dad. Para ilustrar la t´cnica consideremos el siguiente ejemplo:
e
Ejemplo 1 Una f´bricade zapatos de cuero produce dos l´
a
ıneas: modelos de lujo y modelos regulares.
Cada tipo modelo requiere un pie cuadrado de cuero. Un modelo regular necesita 1 hora de mano de
obra, mientras que un modelo de lujo requiere 2 horas de mano de obra. Cada semana se dispone de
40 pies cuadrados de cuero y de 60 horas de mano de obra. Cada zapato regular genera una utilidad
de 30 mil y cadamodelo de lujo representa una utilidad de 40 mil.
Para plantear el modelo se emplear´n las variables:
a
x1 : n´mero de zapatos de lujo producidos a la semana
u
x2 : n´mero de zapatos regulares producidos a la semana
u

(1.1)

Luego, el modelo de LP queda (escribiendo la funci´n objetivo en decenas de miles):
o
Max
s.t.

z = 4x1 + 3x2 (Funci´n Objetivo)
o
x1 + x2 ≤ 40
2x1 + x2 ≤ 60x1 , x2
≥0

(a) Restricci´n de cuero
o
(b) Restricci´n de mano de obra
o
(c) Restricci´n de signo
o

(1.2)

Para convertir cada desigualdad de tipo ≤ en una igualdad introduciremos una variable de holgura
si . Cada variable si (una por cada desigualdad de tipo ≤) representa la cantidad de recurso no empleado
de esa restricci´n. Luego, en la restricci´n (a) se tiene:
o
o
s1 = 40 −x1 − x2

´
o

x1 + x2 + s1 = 40

(1.3)

´
o

2x1 + x2 + s2 = 60

(1.4)

Similarmente, para la restricci´n (b) se tiene:
o
s2 = 60 − 2x1 − x2

1

Segundo Semestre 2004

M´todo Simplex
e

Luego, cualquier combinaci´n (x1 , x2 ) satisface la restricci´n i s´lo si al reemplazar los valores se
o
o
o
obtiene si ≥ 0. Finalmente, la versi´n estandarizada del problema (1.2)queda:
o
Max
s.t.

z = 4x1 + 3x2

(Funci´n Objetivo)
o

x1 + x2 + s1 = 40 (a) Restricci´n de cuero
o
2x1 + x2 + s2 = 60 (b) Restricci´n de mano de obra
o

(1.5)

Para ilustrar como estandarizar desigualdades de tipo ≥ consideremos el siguiente ejemplo:
Ejemplo 2
Min
s.t.

z = 50x1 + 20x2 + 30x3 + 80x4
400x1 + 200x2 + 150x3 + 500x4
3x1 + 2x2
2x1 + 2x2 + 4x3 + 4x4
2x1 + 4x2+ x3 + 5x4
x1 , x2 , x3 , x4

≥
≥
≥
≥
≥

(Funci´n Objetivo)
o
500
6
10
8
0

(a)
(b)
(c)
(d)
(e)

(1.6)

Para convertir una restricci´n de tipo ≥ en una restricci´n de igualdad, se definen las variables de
o
o
exceso ei . La variable de exceso ei representa la cantidad de sobresatisfacci´n de la restricci´n i,
o
o
as´ para la restricci´n (a) se tiene:
ı
o
e1 = 400x1+ 200x2 + 150x3 + 500x4 − 500

´
o

400x1 + 200x2 + 150x3 + 500x4 − e1 = 500 (1.7)

Similarmente:
e2 = 3x1 + 2x2 − 6
´ 3x1 + 2x2 − e2 = 6
o
e3 = 2x1 + 2x2 + 4x3 + 4x4 − 10 ´ 2x1 + 2x2 + 4x3 + 4x4 − e3 = 10
o
e4 = 2x1 + 4x2 + x3 + 5x4 − 8
´ 2x1 + 4x2 + x3 + 5x4 − e4 = 8
o

(1.8)

Luego, cualquier combinaci´n (x1 , x2 , x3 , x4 ) satisface la restricci´n i s´lo si al reemplazarlos valores
o
o
o
se obtiene ei ≥ 0. Finalmente, la versi´n estandarizada del problema (1.6) queda:
o
Ejemplo 3
Min
s.t.

z = 50x1 + 20x2 + 30x3 + 80x4
400x1 + 200x2 + 150x3 + 500x4 − e1
3x1 + 2x2 − e2
2x1 + 2x2 + 4x3 + 4x4 − e3
2x1 + 4x2 + x3 + 5x4 − e4

(Funci´n Objetivo)
o
=
=
=
=

500
6
10
8

(a)
(b)
(c)
(d)

(1.9)

Evidentemente, para modelos de LP que...