• Author / Uploaded
• Jose M Stonem

• Categories
• Matemáticas Aplicadas
• Algoritmos
• Áreas de informática
• Matemáticas
• Informática y tecnología de la información

Citation preview

Problema 8.2-21

Una contratista, Susan Meyer , tiene que acarrear grava a tres construcciones. Puede comprar hasta 18 toneladas a una cantera ubicada al norte de la ciudad y 14 toneladas a una del sur. Necesita 10, 5 y 10 toneladas en las respectivas construcciones 1,2 y 3. El precio de compra por tonelada en cada cantera y los costos de acarreo son los siguientes : Cantera Norte Sur

Costo por tonelada acarreada 1 2 3 $100 $90 $160 $180 $110 $140

Precio por tonelada $300 $420

Susan desea determinar cuando acarrear de cada cantera a cada construcción de manera que se minimice el costo total de compra y acarreo de la grava. a) Obtener una solución BF inicial utilizando Vogel b) Encuentre la solución optima. Tabla de costo por tonelada acarreada

Origen

Costos Por Tonelada Acarreada Destino Construcción 1 Construcción 2 Construcción 3 Norte

100

90

160

Sur Demanda

180 10

110 5

140 10

Total de Recursos: 18+14 = 32 Total de Demanda: 10+5+10 = 25

Recursos

18 14

 Solución Crear Construcción Ficticia 4F con demanda de 7

Origen

Costos Por Tonelada Acarreada Destino Construcción Construcción Construcción Construcción 1 2 3 4F Norte

100

90

160

Recursos

0

18 14

Sur

Demanda

180

110

140

0

10

5

10

7

Simplificando la tabla para una mejor resolución asignando números a las construcciones y orígenes.

Origen

Construccion

1

1

2

3

4F

Recursos

100

90

160

0

18 14

2

Demanda 

180

110

140

0

10

5

10

7

Solucion BF aplicando el método de Vogel

Numero de variables básicas: m + n – 1 = 4+2 – 1 = 5

Origen

1

Construcción 2 3

4F

Recursos

Diferencia Renglón

1

100

90

160

0

18

90

2

180

110

140

0

14

110

10 80

5 20

10 20

7 0

Demanda Diferencia C.

X24=7 Disminuir recurso: 14-7= 7 Eliminar columna 4F

Origen

1

1

2 Demanda Diferencia C.

Origen

Recursos

Diferencia Renglón

90

160

18

10

180 10 80

110 5 20

140 10 20

7

30

1

2 Demanda Diferencia C.

1 Origen

4F

100

1

1

2 Demanda Diferencia C. Solucion Inicial X24= 7 X11= 10 X12= 5 X13= 3 X23= 7

Construcción 2 3

Construcción 2 3

X11= 10 Disminuir recurso 18-10 = 8 Eliminar columna 1

4F

Recursos

Diferencia Renglón

90

160

8

70

110 5 20

140 10 20

7

30

Construcción 2 3

X12=5 Disminuir recurso 8-5= 3 Eliminar columna 2

4F

Recursos

160

3

140 10

7 X13= 3 X23= 7

Diferencia Renglón

Método Simplex 1ra iteración Variable básica Construcción 2 3

1 100

Origen

1

90

10 180

2

Demanda VJ

0 10 100

160

5 110

-

+

Prueba de Optimalidad:  Variable Saliente: X13= 3 

Variable Entrante: X14= -20

Nueva solución: X14= 3 X23= 7+3 = 10 X24= 7-3= 4 X11= 10 X12= 5

Recursos

UI

18

0

14

-20

0

3

140

40 5 90

4F

7 10 160

+

-20

0

7 7 20

-

Método Simplex 2da iteración Variable básica Construcción 2 3

Origen

1

1

100

90

10 2

Demanda VJ

180

160

5 110

80 10 100

10 10 140

Recursos

UI

18

0

14

0

0

20 140

20 5 90

4F

3 0

4 7 0

Solucion Final: X11= 10 X12= 5 X14= 3 X23= 10 X24=4 Costo total de compra: 10(100) + 5(90) + 3(0) + 10(140) + 4(0)= 1000+ 450 + 0 + 1400 +0 = 2,850 unidades