Programacion lineal metodo simplex

Matemática

28/08/2013

Programación

Programación
Matemática
Método
Simplex
1
Dra. Norka Bedregal Alpaca

Representación Analítica de un PPL

PROGRAMACIÓN

LINEAL

El problema general de la PL es encontrar un vector

X = ( x1 , x 2 , K , x k , K , x n )
que optimice la forma lineal

c1 x1 + c2 x 2 +K+ c k x k +K+ cn x n → optimo
sujeta a las restricciones lineales
a11x1 + a12 x2 + K + a1k xk + K + a1n xn (≤)( =)( ≥) b1
a21 x1 + a22 x2 + K + a2 k xk + K + a2 n xn (≤)( =)( ≥) b2
.......... .......... .......... .......... .......... .......... .......... .......
ai1 x1 + ai 2 x2 + K + aik xk + K + ain xn (≤)( =)( ≥) bi
.......... .......... .......... .......... .......... .......... .......... .......
am1 x1 + am 2 x2 + K + amk xk + K + amn xn (≤)( =)( ≥)bm

xj ≥ 0

j = 1, 2, K , n

2
Dra. Norka Bedregal Alpaca

1

28/08/2013

LINEAL

Representación Analítica de un PPL
Definición:
Se entiende por programa lineal aquel que:
opt Z = C X
sujeto a :

PROGRAMACIÓN

AX

Donde:

(≤)(=)(≥) B
X ≥Θ

m : número de recursos (i: recursos)
n : número de productos (j: productos)
aij : número de unidades de recurso i necesariaspara producir una
unidad de producto j
bi: número máximo de unidades del recurso i disponibles
cj : utilidad por unidad de producto j
xj : cantidad producida del producto j

3
Dra. Norka Bedregal Alpaca

PROGRAMACIÓN

LINEAL

Formas equivalentes de la PL
Forma Canónica o Forma Estándar:
La siguiente forma de PL recibe
el nombre de forma canónica o
estándar

maz Z = C X
sujeto a :AX ≤ B
X ≥Θ

Cualquier otra forma es equivalente a esta. Esta equivalencia se
demuestra con el uso de las siguientes reglas
Regla 1:
Maximizar CX es equivalente a minimizar –CX
Minimizar CX es equivalente a maximizarr -CX

4
Dra. Norka Bedregal Alpaca

2

28/08/2013

Formas equivalentes de la PL

PROGRAMACIÓN

LINEAL

Ejemplo:

Máx: Z = 8X1 + 14X2 - 5X3

esmatemáticamente equivalente a
Mín: Z´ = - X0 = -8X1 -14X2 +5X3
Regla 2:
Las siguientes desigualdades son equivalentes
AX ≤ B ⇔ − AX ≥ −B
AX ≥ B ⇔ − AX ≤ −B

Ejemplo:

2X1 + 9X2 - 4X3 > 9

al multiplicarla por (-1), se convierte en
-2X1 - 9X2 + 4X3 < -9

5
Dra. Norka Bedregal Alpaca

LINEAL

Regla 3:

PROGRAMACIÓN

Formas equivalentes de la PL

Ejemplo:

Toda igualdad se puededescomponer en dos desigualdades
AX = B ⇔

AX ≤ B

∧

AX ≥ B

3X1 + 5X2 - 8X3 = 10
es matemáticamente equivalente a las dos siguientes desigualdades

3X1 + 5X2 - 8X3 < 10
3X1 + 5X2 - 8X3 > 10
6
Dra. Norka Bedregal Alpaca

3

28/08/2013

PROGRAMACIÓN

LINEAL

Formas equivalentes de la PL
Regla 4:
Toda desigualdad de la forma menor o igual se puede convertir en
igualdad
Todadesigualdad de la forma mayor o igual se puede convertir en
igualdad
AX ≤ B ⇒ AX + Y = B
AX ≥ B ⇒ AX − W = B

Ejemplo:
9X1 + 7X2 - 3X3 < 5
puede reemplazarse por
9X1 + 7X2 - 3X3 + s4 = 5 , s4 > 0
Es práctica común considerar como cero al coeficiente objetivo
de la variable de faltante.

7

Dra. Norka Bedregal Alpaca

LINEAL

Formas equivalentes de la PL
Ejemplo:
-5X1 + 7X2- 2X3> 15

PROGRAMACIÓN

puede reordenarse como
-5X1 + 7X2 - 2X3 - S4 = 15 , S4 > 0
También es usual asignar un valor de cero al coeficiente objetivo
de la variable de sobrante.

8
Dra. Norka Bedregal Alpaca

4

28/08/2013

PROGRAMACIÓN

LINEAL

Formas equivalentes de la PL
Regla 5:
Una variable no restringida en signo es aquella que puede tomar
toda clase de valores negativos,cero o positivos, y puede
expresarse como la diferencia de dos variables no negativas

Ejemplo:
X7 = X7+ - X7-

,

X7+ y X7- > 0

9
Dra. Norka Bedregal Alpaca

PROGRAMACIÓN

LINEAL

Formas equivalentes de la PL
Ejemplo:

Mín.

Z = 21X1 - 18X2 + 28X3

Sujeto a:
- 2X1 + 4X2 + 3X3 < 350
6X1 + 4X2 + 2X3 > 220
5X1 + 2X2 + 3X3 = 180
X1, 2, 3 > 0

10
Dra. Norka Bedregal...