Metodo Simplex 1

METODO SIMPLEX

Luis Medina Aquino

METODO SIMPLEX

• Es un método sistemático y eficiente para encontrar y probar soluciones situadas en los vértices de optimalidad. El método Simplex termina una vez se haya encontrado la solución óptima.

METODO SIMPLEXEjemplo: Se tiene el siguiente programa lineal, en su forma canónica: Maximizar Z = 200 X1 + 240 X2 Sujeto a: 6 X1 + 12 X2 £ 120 8 X1 + 4 X2 £ 64 X1 ³ 0, X2 ³ 0 El conjunto de soluciones factibles está determinado por el polígono ABCD, en donde: Para A (0, 10) è Z = 2,400 Para B (4, 8) è Z = 2,720 Para C (8, 0) è Z = 1,600 Para D (0, 0) è Z = 0

Solución Gráfica

METODO SIMPLEX• El método Simplex requiere que las

restricciones sean ecuaciones (o restricciones con relación de igualdad) en vez de inecuaciones (o restricciones con relación de desigualdad).

• Cualquier inecuación puede ser convertida en una ecuación agregando una cantidad no negativa en el lado de menor valor de la inecuación. Esta cantidad no negativa se llama variable de holgura.

METODO SIMPLEXEn la restricción 1 será: 6 X1 + 12 X2 + S1 = 120En la restricción 2 será: 8 X1 + 4 X2 + S2 = 64 El problema de programación lineal incorporando las

variables de holgura se convierte en su forma estándar:

Maximizar Z = 200 X1 + 240 X2 + 0 S1 + 0 S2Sujeto a:

6 X1 + 12 X2 + 1 S1 + 0 S2 = 120 1a8 X1 + 4 X2 + 0 S1 + 1 S2 = 64 2a

X1, X2, S1, S2 0

METODO SIMPLEX• Variables Básicas y Soluciones Básicas Factibles • El conjunto de soluciones básicas en el problema dado

en 1a y 2a:•Solución (1): X1 = 0, X2 = 0, S1 = 120, S2 = 64•Solución (2): X1 = 8, X2 = 0, S1 = 72, S2 = 0•Solución (3): X1 = 0, X2 = 1, S1 = 108, S2 = 60

• Observe que las soluciones (1), (2) y (3) satisfacen también las restricciones de no negatividad. Por tanto, son soluciones factibles

METODO SIMPLEX• Si tenemos más variables que ecuaciones,

podemos tener un conjunto extra de variables iguales a cero, obteniendo así un sistema con igual número de variables y restricciones. Una solución así es llamada una solución básica.

• Una solución básica factible para las ecuaciones 1a y 2a es una solución que tenga a lo sumo dos (= número de ecuaciones) variables con valores positivos y el resto de variables con valores iguales a cero.

•

METODO SIMPLEX• Las soluciones (1) y (2) son soluciones básicas factibles.• • Solución (1): X1 = 0, X2 = 0 S1 = 120, S2 = 64• Variables no básicas (= 0) Variables básicas (> 0)• • Solución (2): X2 = 0, S2 = 0 X1 = 8, S1 = 72• Variables no básicas (= 0) Variables básicas (> 0)• • Solución (3): X1 = 0, X2 = 1, S1 = 108, S2 = 60• En la solución 3 hay tres variables que son positivas, por tanto, es una

solución factible pero no una solución básica factible.

METODO SIMPLEX

Maximizar Z = C1 X1 + C2 X2 + .... + Cn Xn + Cn+1 Xn+1 + .... + Cn+m Xn+m

Sujeto a :

a11 X1 + a12 X2 + .... + a1n Xn + Xn+1 (=S1) = b1

a21 X1 + a22 X2 + .... + a2n Xn + Xn+2 (=S2) = b2

…… ……. …….. ….am1 X1 + am2 X2 + .... + amn Xn + Xn+m (=Sm) = bm

Xj > 0 j = 1, 2, 3, ...., m+n

TABLA SIMPLEX Cj C1 C2 .... Cn Cn+1 Cn+2 ....Cn+m

CB VB X1 X2 .... Xn Xn+1 Xn+2 ....Xn+m BCn+1 Xn+1 a11 a12 ....a1n 1 0 ....0 b1

Cn+2 Xn+2 a21 a22 ....a2n 0 1 ....0 b2

.... .... .... .... .... .... .... .... ....

.... .... .... .... .... .... .... .... ....

Cn+m Xn+m am1 am2 ....amn 0 0 ....1 bm

Zj Z1 Z2 ....Zn Zn+1 Zn+2 ....Zn+m CBTB

Cj - Zj C1-Z1 C2-Z2 ....Cn-Zn Cn+1-Zn+1 Cn+2-Zn+2 Cn+m-Zn+m

En este problema habrá m variables básicas con un valor positivo y n variables no básicas con valor cero, para que exista una solución básica factible.

ITERACION 0 Cj 200 240 0 0

CB VB X1 X2 S1 S2 B6 12 1 0 1208 4 0 1 64

ZjCj - Zj Cj-Zj<0

R01

R02


6 X1 + 12 X2 + 1 S1 + 0 S2 = 1208 X1 + 4 X2 + 0 S1 + 1 S2 = 64

X1, X2, S1, S2 ³ 0


CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

ZjCj - Zj Cj-Zj<0

R01

R02


6 X1 + 12 X2 + 1 S1 + 0 S2 = 1208 X1 + 4 X2 + 0 S1 + 1 S2 = 64

X1, X2, S1, S2 ³ 0


CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

Zj 0 0 0 0 0Cj - Zj Cj-Zj<0

R01

R02


CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

Zj 0 0 0 0 0Cj - Zj 200 240 0 0 Cj-Zj<0

R01

R02


CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

Zj 0 0 0 0 0Cj - Zj 200 240 0 0 Cj-Zj<0

R01

R02

Vértice D

Solución básica. Vértice D: X1=0, X2=0, S1=120, S2=64

Para A (0, 10) è Z = 2,400 Para B (4, 8) è Z = 2,720 Para C (8, 0) è Z = 1,600 Para D (0, 0) è Z = 0


CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

Zj 0 0 0 0 0Cj - Zj 200 240 0 0 Cj-Zj<0

R01

R02

Columnapivote


CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

Zj 0 0 0 0 0Cj - Zj 200 240 0 0 Cj-Zj<0

R01

R02

Columnapivote

120/12 =10

64/4 =16


CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

Zj 0 0 0 0 0Cj - Zj 200 240 0 0 Cj-Zj<0

R01

R02

Columnapivote

120/12 =10 √64/4 =16


CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

Zj 0 0 0 0 0Cj - Zj 200 240 0 0 Cj-Zj<0

R01

R02

Columnapivote

Fila pivote

ITERACION 1

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

Zj 0 0 0 0 0Cj - Zj 200 240 0 0 Cj-Zj<0

R01

R02

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1 0

0 S2 0 1Zj

Cj - Zj Cj-Zj<0

ITERACION 0

R11

R12

ITERACION 1

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

Zj 0 0 0 0 0Cj - Zj 200 240 0 0 Cj-Zj<0

R01

R02

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1 0

0 S2 0 1Zj

Cj - Zj Cj-Zj<0

ITERACION 0

R11

R12

R11 = R0

1/12

ITERACION 1

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

Zj 0 0 0 0 0Cj - Zj 200 240 0 0 Cj-Zj<0

R01

R02

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 0 1Zj

Cj - Zj Cj-Zj<0

ITERACION 0

R11

R12

R11 = R0

1/12

ITERACION 1

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

Zj 0 0 0 0 0Cj - Zj 200 240 0 0 Cj-Zj<0

R01

R02

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 0 1Zj

Cj - Zj Cj-Zj<0

ITERACION 0

R11

R12

R12= R0

2 - 4 R11

R02 8 4 0 1 64

-4R11

R12

ITERACION 1

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

Zj 0 0 0 0 0Cj - Zj 200 240 0 0 Cj-Zj<0

R01

R02

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 0 1Zj

Cj - Zj Cj-Zj<0

ITERACION 0

R11

R12

R12= R0

2 - 4 R11

R02 8 4 0 1 64

-4R11 -2 -4 -1/3 0 -40

R12

ITERACION 1

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

Zj 0 0 0 0 0Cj - Zj 200 240 0 0 Cj-Zj<0

R01

R02

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 0 1Zj

Cj - Zj Cj-Zj<0

ITERACION 0

R11

R12

R12= R0

2 - 4 R11

R02 8 4 0 1 64

-4R11 -2 -4 -1/3 0 -40

R12 6 0 -1/3 1 24

ITERACION 1

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

Zj 0 0 0 0 0Cj - Zj 200 240 0 0 Cj-Zj<0

R01

R02

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 6 0 -1/3 1 24Zj

Cj - Zj Cj-Zj<0

ITERACION 0

R11

R12

R12= R0

2 - 4 R11

R02 8 4 0 1 64

-4R11 -2 -4 -1/3 0 -40

R12 6 0 -1/3 1 24

ITERACION 1

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

Zj 0 0 0 0 0Cj - Zj 200 240 0 0 Cj-Zj<0

R01

R02

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 6 0 -1/3 1 24Zj 120 240 20 0 2400

Cj - Zj Cj-Zj<0

ITERACION 0

R11

R12

ITERACION 1

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B0 S1 6 12 1 0 1200 S2 8 4 0 1 64

Zj 0 0 0 0 0Cj - Zj 200 240 0 0 Cj-Zj<0

R01

R02

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 6 0 -1/3 1 24Zj 120 240 20 0 2400

Cj - Zj 80 0 -20 0 Cj-Zj<0

ITERACION 0

R11

R12

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 6 0 -1/3 1 24Zj 120 240 20 0 2400

Cj - Zj 80 0 -20 0 Cj-Zj<0

R11

R12

ITERACION 1

Vértice A

Solución básica. Vértice A: X1=0, X2=10, S1=0, S2=24


ITERACION 2

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 6 0 -1/3 1 24Zj 120 240 20 0 2400

Cj - Zj 80 0 -20 0 Cj-Zj<0

R11

R12

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B

ZjCj - Zj Cj-Zj<0

ITERACION 1

R21

R22

Columna pivote

10/(1/2) = 2024/6 = 4

ITERACION 2

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 6 0 -1/3 1 24Zj 120 240 20 0 2400

Cj - Zj 80 0 -20 0 Cj-Zj<0

R11

R12

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B

ZjCj - Zj Cj-Zj<0

ITERACION 1

R21

R22

Columna pivote

10/(1/2) = 2024/6 = 4 √

ITERACION 2

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 6 0 -1/3 1 24Zj 120 240 20 0 2400

Cj - Zj 80 0 -20 0 Cj-Zj<0

R11

R12

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 0 1200 X1 1 0

ZjCj - Zj Cj-Zj<0

ITERACION 1

R21

R22

Columna pivote

Fila pivote

ITERACION 2

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 6 0 -1/3 1 24Zj 120 240 20 0 2400

Cj - Zj 80 0 -20 0 Cj-Zj<0

R11

R12

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 0 1200 X1 1 0

ZjCj - Zj Cj-Zj<0

ITERACION 1

R21

R22

R22 = R1

2/6

ITERACION 2

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 6 0 -1/3 1 24Zj 120 240 20 0 2400

Cj - Zj 80 0 -20 0 Cj-Zj<0

R11

R12

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 0 1200 X1 1 0 -1/18 1/6 4

ZjCj - Zj Cj-Zj<0

ITERACION 1

R21

R22

R22 = R1

2/6

ITERACION 2

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 6 0 -1/3 1 24Zj 120 240 20 0 2400

Cj - Zj 80 0 -20 0 Cj-Zj<0

R11

R12

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 0 1200 X1 1 0 -1/18 1/6 4

ZjCj - Zj Cj-Zj<0

ITERACION 1

R21

R22

R21= R1

1 – 1/2 R22

R11 1/2 1 1/12 0 10

-1/2R22

R21

ITERACION 2

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 6 0 -1/3 1 24Zj 120 240 20 0 2400

Cj - Zj 80 0 -20 0 Cj-Zj<0

R11

R12

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 0 1200 X1 1 0 -1/18 1/6 4

ZjCj - Zj Cj-Zj<0

ITERACION 1

R21

R22

R21= R1

1 – 1/2 R22

R11 1/2 1 1/12 0 10

-1/2R22 -1/2 0 1/36 -1/12 -2

R21

ITERACION 2

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 6 0 -1/3 1 24Zj 120 240 20 0 2400

Cj - Zj 80 0 -20 0 Cj-Zj<0

R11

R12

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 0 1200 X1 1 0 -1/18 1/6 4

ZjCj - Zj Cj-Zj<0

ITERACION 1

R21

R22

R21= R1

1 – 1/2 R22

R11 1/2 1 1/12 0 10

-1/2R22 -1/2 0 1/36 -1/12 -2

R21 0 1 1/9 -1/12 8

ITERACION 2

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 6 0 -1/3 1 24Zj 120 240 20 0 2400

Cj - Zj 80 0 -20 0 Cj-Zj<0

R11

R12

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 0 1 1/9 -1/12 8200 X1 1 0 -1/18 1/6 4

ZjCj - Zj Cj-Zj<0

ITERACION 1

R21

R22

R21= R1

1 – 1/2 R22

R11 1/2 1 1/12 0 10

-1/2R22 -1/2 0 1/36 -1/12 -2

R21 0 1 1/9 -1/12 8

ITERACION 2

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 1/2 1 1/12 0 10

0 S2 6 0 -1/3 1 24Zj 120 240 20 0 2400

Cj - Zj 80 0 -20 0 Cj-Zj<0

R11

R12

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 0 1 1/9 -1/12 8200 X1 1 0 -1/18 1/6 4

Zj 200 240 140/9 40/3 2720Cj - Zj 0 0 -140/9 -40/3 Cj-Zj<0

ITERACION 1

R21

R22

Cj 200 240 0 0 CB VB X1 X2 S1 S2 B240 X2 0 1 1/9 -1/12 8200 X1 1 0 -1/18 1/6 4

Zj 200 240 140/9 40/3 2720Cj - Zj 0 0 -140/9 -40/3 Cj-Zj<0

ITERACION 2

R21

R22

Ya que todos los Cj – Zj, £ 0 entonces la tabla es óptima.La respuesta final es: X1 = 4 y X2 = 8 (variables básicas) y S1 = S2 = 0 (variables no básicas), y el valor de Z = 2720.

Vértice B


GRACIAS

Ing. Luis Medina

Metodo Simplex 1

Documents

Transcript of Metodo Simplex 1