• Author / Uploaded
• diego duran garcia

Citation preview

PROBLEMAS METODO SIMPLEX

Presentado a:

ING. GUIOMAR VEGA ALVAREZ

Presentado por:

LUIS GUILLERMO DEVIA COD: 339692

UNIVERSIDAD COOPERATIVA DE COLOMBIA FACULTAD DE INGENIERIA INGENIERIA CIVIL IBAGUE 2015

EJERCICIO #1: El señor Martínez fue llamado para dar consulta a la compañía sigma, que con sus dos máquinas automáticas puede hacer montaje de motocicletas. La compañía tiene un contrato para armar 60 motocicletas de 4 cilindros, 120 de 2 cilindros y 150 de un cilindro, diariamente. Le cuesta 200 (en miles de pesos) operar la primera máquina y se puede hacer un montaje de 1,4 y 6 motocicletas de 4,2 y 1 cilindros, respectivamente. Cuesta 300 (en miles de pesos) operar la segunda máquina y puede hacer 2 montajes diariamente de cada motocicleta. El señor Martínez tiene que encontrar la combinación de motocicletas que se deben montar con estas 2 máquinas para minimizar el costo de operación. Formule un modelo de programación lineal.

Maquinas Motos

Maquina 1

Maquina 2

1 4 6 200

2 2 2 300

4 cilindros 2 cilindros 1 cilindros Costo ( $/mont)

Requerimiento (motos) 60 120 150

OBJETIVO: Minimizar costos ($) n: 2 ( maquina 1 , maquina 2 ) m: 3 (motos 4c, motos 2c, motos 1c) Xj: cantidad de montajes a realizar en la maquina j-esima :. J= 1,2



MIN Z=

200

X1

+

300

$ $ MONT MONT MONT 

X2

$

MONT

S.a o

Motos 4CL 1 X1

+

2

X2

≥

MOTO MOTO MONT MONT MONT MONT o

Motos 2CL 4 X1

+

2

X2

MOTO MOTO MONT MONT MONT MONT

60 MOTOS

≥

120 MOTOS

o

Motos 1CL 6 X1

+

2

X2

≥

MOTO MOTO MONT MONT MONT MONT 

C.N.N

150 MOTOS

X1 , X2 ≥ 0

METODO GRAFICO: MIN Z=

200 X1

+

1) 1 X1 + 2 X2 ≥ 2) 4 X1 + 2 X2 ≥ 3) 6 X1 + 2 X2 ≥

300 X2

60 120 150

1) 1 X1 + 2 X2 = 60 2) 4 X1 + 2 X2 = 120 3) 6 X1 + 2 X2 = 150

1) 1 X1 + 2 X2 = 60

X1 X2

0 30

60 0

2) 4 X1 + 2 X2 = 120

X1 X2

0 60

30 0

X1 X2

0 75

25 0

X1 X2

0 40

60 0

3) 6 X1 + 2 X2 = 150

ZE= 12000 = 200 X1 + 300 X2

Para hallar las coordenadas del punto B L1 y L2. 1) 1 X1 + 2 X2 = 60 2) 4 X1 + 2 X2 = 120 (-1)

2X2 = 60 – 20 X2 = 40/2

1 X1 + 2 X2 = 60

X2*= 20

-4 X1 - 2 X2 = - 120_____

Z*= 200(20) + 300(20)

-3X1 = -60 X1* = 20 C.N.N 4) X1= 0 5) X2= 0

Z* = 10000

SOLUCIONES: X1*= 20 X2*= 20 Z* = 10000

METODO SIMPLEX: 

MIN Z=

200 X1

+

1) 1 X1 + 2 X2 ≥

60

2) 4 X1 + 2 X2 ≥

120

3) 6 X1 + 2 X2 ≥

150

C.N.N

300 X2 – 0X3 + MX4 – 0X5 + MX6 – 0X7 + MX8 VS VA VS VA VS VA 1) 1 X1 + 2 X2 - X3 + X4 = 60 VS VA 2) 4 X1 + 2 X2 - X5 + X6 = 120 VS VA 3) 6 X1 + 2 X2 - X7 + X8 = 150 VS VA

X1 , X2 ≥ 0

C.N.N

X1 , X2, X3, X4, X5, X6 ,X7, X8 ≥ 0

n=8 m=3 p= n-m = 5 NB = X1, X2, X3, X5, X7 q = m = 3 B = X4, X6, X8



---CBi M M M ---

Cj Base X4 X6 X8 Zj-Cj

--bi 60 120 150 330M

200 a1 1 4 (6) 11M-200

300 a2 2 2 2 6M-300

0 a3 -1 0 0 -M

M a4 1 0 0 0

0 a5 1 0 0 -M

X1=X2=X3=X5=X7=0

X1

Fp

150 25 -100

(6) 1 -4

2 0 1/3 0 -4/3 0

0 0 0

0 0 0

0 0 0

-1 -1/6 2/3

1 1/6 -2/3

x 1/6 x -4

M a6 0 -1 0 0

0 a7 0 0 -1 -M

M a8 0 0 1 0

--Ө= bi/aij 60/1=60 120/4=30 150/6=25 ----------

X8 XX

+

Fp +

120 20

4 0

2 2/3

0 0

0 0

-1 -1

1 1

0 2/3

0 -2/3

25 -25 60 35

1 -1 1 0

1/3 0 0 -1/3 0 0 2 -1 1 5/3 -1 1

0 0 0 0

0 0 0 0

-1/6 1/6 0 1/6

1/6 -1/6 0 -1/6

X6

x -1

X4

 ---CBi

Cj Bas e M X4 M X6 200 X1 --- Zj-Cj

--bi

200 a1

35 20 25 55M+500 0

0 0 1 0

300 a2 (5/3) 2/3 1/3 7/3M700/3

0 M 0 M a3 a a5 a 4 6 -1 1 0 0 0 0 -1 1 0 0 0 0 - 0 - 0 M M

0 a7 1/6 2/3 -1/6 5/6M100/3

M a8 -1/6 -2/3 1/6 -11/6M - 100/3

--Ө= bi/aij 35/5/3=21 20/2/3=30 25/1/3=75 ----------

X4 XX

X2=X3=X5=X7=X8=0

X2

35 0 F p

+

F p

21 0

(5/3 ) 1

14 0

-2/3

3/5 2/5

20 0 6 0

2/3 0

0 2/5

0 -1 1 -2/5 -1 1

21 0

1

3/5 1/5

3/5

0 0

1/5 0 1/5

0 0 -1/30

1/10 1/30

0 0 0 0

1/6 1/5

7 +

0

25 1 18 1

1/3 1/3 0

-1

1

0

0

1/6

-1/6

x 3/5

3/5

0

0

1/10

x-2/3

-2/5

0

0

1/15 2/3 3/5

1/10 1/15

0 1/5

1/10

-1/6 -1/5

-2/3 -3/5

X6 x-1/3

X1



X6 XX

---CBi

Cj Base

--bi

200 a1

300 a2

0 a3

M a4

0 a5

0 a7

M a8

--Ө= bi/aij

0

M a 6 0

30 0 M 20 0 ---

X2

21

0

1

-3/5

3/5

1/10

-1/10

21/1/10=210

X6 X1

6 18

0 1

0 0

2/5 1/5

-2/5 -1/5

-1 0

1 0

3/5 -1/5

-3/5 1/5

6/3/5=10 18/-1/5=-90

Zj-Cj

6M+ 9900

0

0

2/5M- -7/5M -M 140 +140

0

3/5M -8/5M - 10 +70

----------

X3=X4=X5=X7=X8=0

X7

F p

+

F p

6 1 0 -1

0 0 0 0

2 1 2 0

0 1 0 1

-2/5 -1 -2/3 -5/3

1 5/3

(3/5) (1)

-3/5 -1

1/6

-1/6

0

0

1/10 1/10

1/10

-3/5

1/1 5 3/5

-1/10

-2/3

2/3

1/6

-1/6

0

0

2/3

-2/3

-5/3

0 0 2/15

2/15 -1/5 -1/3

-1/3

5/ 3 1/ 3 0 1/ 3

0 0 -1/15

10 0 0 2

+

2/5 2/3

18 1 0 20 1 0

1/5 1/3

0 -1/3

x 5/3 x -1/10

X2

(1)

-1

x 1/5

1/5

1/5 1/5 0

X1

-1/5 0

 ---CBi

Cj Base

--bi

200 300 a1 a2

30 0 0 20

X2

20

0

X7 X1

10 20

0 1

0 a3

M a4

0 a5

M a6

0 a7

M a8

1

-2/3

2/3

1/6

-1/6

0

0

0 0

2/3 1/3

-2/3 -1/3

-5/3 -1/3

5/3 1/3

1 0

-1 0

--Ө= bi/aij

0 ---

Zj-Cj

1000 0

0

0

400/3

-M +400/3

-50/3 -M +50/3

0

-M

----------

X3=X4=X5=X6=X8=0

Solución : Z* = 10000 X1*= 20 X2*= 20

Solución : Z* = 10000 X5*= 0 X1*= 20 X6*= 0 X2*= 20 X7*= 10 X3*= 0 X8*= 0 X4*= 0

EJERCICIO #2: Un agricultor quiere cultiva maíz y trigo en un terreno de 70 hectáreas. Sabe que 1 hectárea (Ha) puede rendir 30 quintales de maíz o 25 quintales de trigo. Cada hectárea requiere un capital de $30 si se cultiva con maíz y de $40 si se cultiva con trigo. El capital total disponible es de $2.500.Las necesidades de agua de riego son de 900 m3 por hectárea de maíz y 650 m3 por hectárea de trigo en Octubre; y de 1.200 m3 por hectárea y 850 m3 por hectárea de maíz y trigo respectivamente en el mes de Noviembre. La disponibilidad de agua en Octubre es de 57.900 m3 y en Noviembre de 115.200 m3.Si los precios del maíz y del trigo son $4.50 y $6.00 por quintal métrico (qq) respectivamente. Hay que determinar la cantidad de maíz y de trigo que debe producirse para obtener el beneficio máximo.

 1 qq métrico=100 Kg=0.1TON FACTORES PRODUCTIVOS TERRENO ( Ha )

REQUERIMIENTOS POR UNIDAD DE PRODUCCIÓN ( Ha ) MAÍZ TRIGO

─────

─────

DISPONIBILIDAD DE RECURSOS

70

CAPITAL ( $ / Ha ) AGUA RIEGO OCTUBRE ( m3/Ha ) AGUA RIEGO NOVIEMBRE ( m3/Ha ) RENDIMIENTO ( qq / Ha ) PRECIO

30

40

2500

900

650

57900

1200

850

115200

30

25

─────

4.50

6.00

─────

OBJETIVO: MAXIMIZAR LA UTILIDAD ($).

n = 2 [Maíz (X1) y Trigo (X2)] m = 4 (Terreno, Capital, Agua Octubre, Agua Noviembre) X1 = Cantidad de Hectáreas (Ha) a sembrar de Maíz X2 = Cantidad de Hectáreas (Ha) a sembrar de Trigo MAX:

Z

=

4,50 (30) X1 +

6,00 (25) X2

$

=

$ qq × × Ha qq Ha

+

$ qq × × Ha qq Ha

Z

=

135 X1

+

150 X2

$

=

$ × Ha Ha

$ × Ha Ha

+

S.a.: TERRENO (1)

CAPITAL (2)

AGUA OCTUBRE (3)

X1

+

X2

≤

70

Ha

+

Ha

→

Ha

30 X1 +

40 X2 ≤

2.500

$ × Ha Ha

+

$ × Ha Ha

→

$

900

X1

+

650

≤

57.900

m3 × Ha Ha

+

m3 × Ha Ha

→

m3

X2

AGUA NOVIEMBRE (4)

1200 X1

+

850

m3 × Ha Ha

+

m3 × Ha Ha

C.N.N →

X1, X2

≥

X2

≤

115.200

→

m3

0

SOLUCIÓN POR EL METODO GRAFICO: MAX: 

Z

=

135 X1

+

150 X2

X1

+

X2

≤

70

S. a:

(1) (2)

30 X1 +

40 X2 ≤

2.500

(3)

900

X1

+

650

X2

≤

57.900

(4)

1.200 X1

+

850

X2

≤

115.200

C.N.N.

X1, X2 ≥

→

0

Ecuaciones de las inecuaciones:

(1)

X1

(2)

30 X1

(3)

900

X1

+

X2

+

40 X2

+

650

X2

70

X1 X2

0 70

70 0

=

2.500

X1 X2

0 62,50

83.33 0

=

57.900

X1 X2

0 89,08

64,33 0

=

1.200 X1

(4)

C.N.N.

+

→

ZE = 8100 =

850

X2

=

115.200

(5)

X1

=

0

(6)

X2

=

0

135X1 + 150X2

ZE = 10500 =

135X1 +

X1 X2

X1 X2

0 54

60 0

X1 X2

0 70

77.80 0

150X2

 Para hallar las coordenadas del punto B (L1 y L2) (1)

X1

(2) (1)

+

X2

=

70

30 X1

+ 40 X2

=

2.500

- 30 X1

- 30 X2

=

- 2.100

10 X2

=

400

=

40

40

=

70

X1*

=

30

X2* 

Se reemplaza X2 en (1)

X1

(1)



[se multiplica (1) por -30]

+

Se reemplaza X1* y X2* en la función objetivo para hallar Z*

Z*

=

135 (30)

+

150 (40)

Z*

=

4.050

+

6.000

Z*

=

10.050

0 135,53

96 0

CUADRO SOLUCIÓN

Z* = 10.050 X1* = 30 X2* = 40 SOLUCIÓN DEL PROBLEMA – METODO SIMPLEX DE LA TABLA 

MIN Z=

135 X1

+

150 X2

S.a. 1)

X1 +

2)

X2

≤

70

30 X1 + 40 X2 ≤

3)

900 X1 + 650 X2

2500

≤

57900

4) 1200 X1 + 850 X2 ≤

115200

C.N.N X1, X2 ≥ 0



MIN Z=

135 X1

+

150 X2 + 0X3 + 0X4 + 0X5 + 0X6 VR

VR

VR

VR

S.a. 1)

X1 +

X2

+ X3 VR 2) 30 X1 + 40 X2 + X4 VR 3) 900 X1 + 650 X2 + X5 VR 4) 1200 X1 + 850 X2 + X6 VR

=

70

=

2500

=

57900

=

115200

C.N.N X1, X2, X3, X4, X5, X6 ≥ 0

n=6

→

Variables

m=4

→

Restricciones

p=n–m=6–4=2

→

Variables NO BÁSICAS (=0)

q = m = restantes = 4

→

Variables BÁSICAS (>0)

 Iniciando el problema de Programación Lineal por el Método Simplex de la Tabla, se consideran como variables Básicas a las variables adicionales positivas (Variables de Holgura y Variables Artificiales)

X3, X4, X5, X6

Variables BÁSICAS (>0): Variables NO BÁSICAS (=0): ─── CBi 0 0 0 0 ───

Cj BASE X3 X4 X5 X6 Zj - Cj

─── Bi 70 2500 57900 115200 0

135 a1 1 30 900 1200 -135

X1=X2=0

X1, X2 INTERACCIÓN I 150 0 0 a2 a3 a4 1 1 0 40 0 1 650 0 0 850 0 0 -150 0 0

0 a5 0 0 1 0 0

0 a6 0 0 0 1 0

─── θ = Bi/aij 70/1 = 70.00 X4 2500/40 = 62.50 57900/650 = 89.08 115200/850 = 135.53 ───

X2

Fila Pivote Fila Pivote Fila Pivote Fila a Arreglar Fila Arreglada

2500 125/2 -125/2 70 15/2

30 3/4 -3/4 1 1/4

40 1 -1 1 0

0 0 0 1 1

1 1/40 -1/40 0 -1/40

0 0 0 0 0

0 0 0 0 0

(x1/40) (x-1)

Fila Pivote Fila Pivote Fila a Arreglar Fila Arreglada

125/2 -40625 57900 17275

3/4 -975/2 900 825/2

1 -650 650 0

0 0 0 0

1/40 -65/4 0 -65/4

0 0 1 1

0 0 0 0

(x-650)

1

0

1/40

0

0

-850

0

-85/4

0

0

850 0

0 0

0 -85/4

0 0

1 1

Fila Pivote

125/2

Fila Pivote

-53125

Fila a Arreglar Fila Arreglada

115200 62075

3/4 1275/2 1200 1125/2

───

135

───

Cj

150

INTERACCIÓN II 0 0

0

0

(x-850)

─── X3

CBi 0 150 0 0 ───

BASE X3 X2 X5 X6 Zj - Cj

Bi 15/2 125/2 17275 62075 9375

a1 1/4 3/4 825/2 1125/2 -45/2

X2=X4=0

a3 1 0 0 0 0

a4 -1/40 1/40 -65/4 -85/4 15/4

a5 0 0 1 0 0

a6 0 0 0 1 0

θ = Bi/aij 60/2 = 30.00 250/3 = 83.33 1382/33 = 41.88 4966/45 = 110.36 ───

X1

Fila Pivote Fila Pivote Fila Pivote Fila a Arreglar Fila Arreglada Fila Pivote Fila Pivote Fila a Arreglar Fila Arreglada Fila Pivote Fila Pivote Fila a Arreglar Fila Arreglada

─── CBi 135 150 0 0 ───

a2 0 1 0 0 0

15/2 30 -45/2 125/2 40

1/4 1 -3/4 3/4 0

0 0 0 1 1

1 4 -3 0 -3

-1/40 -1/10 3/40 1/40 1/10

0 0 0 0 0

30 -12375 17275 4900

1 -825/2 825/2 0

0 0 0 0

4 -1650 0 -1650

-1/10 165/4 -65/4 25

0 0 1 1

0 0 0 0

-1/10 225/4 -85/4 35

0 0 0 0

0 0 1 1

30 -16875 62075 45200

Cj BASE X1 X2 X5 X6 Zj - Cj

1 -1125/2 1125/2 0

─── Bi 30 40 4900 45200 10050

135 a1 1 0 0 0 0

0 0 0 0

4 -2250 0 -2250

INTERACCIÓN III 150 0 a2 a3 0 4 1 -3 0 -1650 0 -2250 0 90

0 a4 -1/10 1/10 25 35 3/2

0 0 0 0 0

0 a5 0 0 1 0 0

(x4) (x-3/4)

(x-825/2)

0 a6 0 0 0 1 0

(x-1125/2)

─── θ = Bi/aij         ───

X3=X4=0

Solución : Z* = 10050 X1*= 30 X2*= 40

Solución : Z* = 10050 X4*= 0 X1*= 30 X5*= 4900 X2*= 40 X6*= 45200 X3*= 0

EJERCICIOS # 3 METODO GRAFICO MAX Z= 3X1 + 2X2 MIN Z= 2X2 - 1 MAX Z= 2X1 + 2X2

a. b. c. d. e. f.

S.a X1 + X2 ≥ 1 X2 – 5X1 ≤ 0 5X2 – X1 ≥ 0 X1 – X2 ≥ -1 X1 + X2 ≤ 6 X1 ≤ 3

CNN X1, X2 ≥ 0

SOLUCIÓN





X1 + X2 = 1

X2 = 5X1

X1 X2 X1 X2

0 1 0 0

1 0 2 10





5X2 =X1

X1 X2

X1 – X2 = -1



X1 + X2 = 6



X1 = 3

0 0

10 2

X1 X2

0 1

-1 0

X1 X2

0 6

6 0

Punto óptimo 4 RESTRICCIONES:

f. X1 ≤ 3

=> X1 = 3

e. X1 + X2 ≤ 6 =>

3 + X2 = 6 =>

MAX Z= 3X1 + 2X2 Z= 3(3) + 2(3) =>

Z=15

MIN Z= 2X2 - 1

2X2 – 1 = 9

2X2 – 1 = 3

X2 = 5

X2 = 2

Punto óptimo 6

X2 = 3

a., X1 + X2 ≥ 1 => X2 = 1/6 c., 5X2 – X1 ≥ 0 => X1= 5/6

2X2 – 1 = [ 2 (1/6) – 1 ] = -2/3

Z= 15

X1=5/6

X2=1/6

MAX Z= 2X1 + 2X2 2X1+2X2=6 X1 X2

0 3

2X1+2X2=16 X1 X2

3 0

0 8

8 0

EXISTEN INFINITOS PUNTOS OPTIMOS ENTRE

RESTRICCIONES PARA EL PUNTO 3

d., X1-X2=-1

=>

c,. X1 + X2=6

X1=5/2

=> X2 =7/2

2X1+2X2 = 2(5/2) + 2(7/2) =12

RESTRICCIONES PUNTO 4

f. X1 ≤ 3

=> X1= 3

e., X1 +X2=6

=> X2=3

2X1 + 2X2 = 2(3) + 2(3) = 12

EJERCICIOS # 4 1. MAX Z = 2X2 - X1

S. a a. X1-X2 ≥ -1 b. 0.5X1-X2 ≥ -2

SOLUCION

X1-X2= -1 X1 X2

0 1

0.5X1 – X2 = -2 -1 0

X1 X2

0 2

-4 0

MAX= 2X2 – X1 2X2 – X1 = 5 X1 X2

0 5/2

2X2 – X1 = 2 X1 X2

-5 0

0 1

-2 0

Existen infinitas soluciones entre el punto 3 y la continuación de la línea de la restricción B. X1 – x2 ≥ -1

x2 – x1 ≥ 1

0.5x1 – x2 ≥ -2

-X2 + 0.5X1≥-2 -0.5X1= -1 X1=2

(2)-X2= -1

=>

X2=3

2X2-X1= 2(3) - (2)= 4