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

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

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

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

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

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

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

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

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

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

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

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

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 = R0

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

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 = R0

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

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

R12= R0

2 - 4 R11

R02 8 4 0 1 64

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

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

R12= R0

2 - 4 R11

R02 8 4 0 1 64

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

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

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

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

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

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

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

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

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

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 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

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

ZjCj - Zj Cj-Zj<0

ITERACION 1

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

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

ZjCj - Zj Cj-Zj<0

ITERACION 1

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

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

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

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

R22 = R1

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

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

R22 = R1

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

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= R1

1 – 1/2 R22

R11 1/2 1 1/12 0 10

-1/2R22

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

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= R1

1 – 1/2 R22

R11 1/2 1 1/12 0 10

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

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

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= 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

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= 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

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

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

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

Ejercicio Metodo Grafico 1

Infezione da Herpes simplex virus-1 nel sistema nervoso enterico ...

HERPES SIMPLEX 1+2 IgG REF 81020 (36 tests) - diesse.it IT-EN-ES-PT HSV IgG 2017.04.19.pdf · Herpes simplex virus ... PRINCIPIO DEL METODO Il test è basato sul principio ELISA (Enzyme

Metodi e Modelli di Programmazione Lineare · LP – L’algoritmo del simplesso (simplex) Il Simplesso (in forma algebrica) 1. Inizializzazione Determinare una soluzione di base

Metodo Simplex

Metodo Matte Libro 1

IL METODO SIMULTANEO - win.ictrescorecremasco.euwin.ictrescorecremasco.eu/sito/Metodo 2014-1/linked/dispensa_sito... · IC Trescore Cremasco Il metodo simultaneo vers. 07 feb 2011

metodo-deliberativo (1)

Metodo Renato Volume 1

Simplex Tabular

nell a e a · Curare l@herpes simplex l ' herpes simplex è una malattia contagiosa pro - vocata da virus. Può manifestarsi con senso di pizzicore, bruciore, dolore, prurito e, successiva

Simplex Lattice Design , Dwi Bagus Pambudi , Wirasti , St ...

RADIOMODEM UHF - Shop Online...1 CE DL868-IN-B RADIOMODEM UHF DL868-IN CEGENERALITA’ DL868-IN-B è un radiomodem UHF simplex/half-duplex di ottima qualità, con potenza d'uscita

Bastien 2A Metodo Completo · Livello IL NUOVO Bastien® Metodo Completo ... Metodo Completo per Pianoforte è un metodo ... Valore: 1/2 1 1½ 2 3 4

Chlamidia e Gonorrea - ssmtstatistica · Web viewHerpes simplex). Se il campione è ... Il metodo per l’identificazione di uno dei due patogeni si basa su una tecnica che permette

Attualita’ e Prospettive in Virologia - SJDIEM · Herpes simplex virus tipo 1 (HSV-1) ... occhio HSV-2 Neuroni ... DIFFUSIONE AI GANGLI NERVOSI Herpes simplex virus 1-2 e Varicella

Herpes Simplex, Herpes Zoster, dan Varicella

Metodo Per Pianoforte Livello 1

Carulli 27 Metodo Completo 1

capitolato-lavori-edili.doc - Contursi Terme (SA) · Web view- trattamenti preservanti con metodo ... per una redazione con editing da word processor, ... (tipo Simplex, ...