Solución óptima a los problemas de transporte La solución inicial puede ser óptima o no, la forma de saberlo es realizando la prueba de optimalidad que consiste en los siguientes pasos: a) Calcular los coeficientes de cada renglón y de columna de la matriz de transporte. Este procedimiento se inicia asignando el cero como coeficiente al primer renglón (si es posible). Seguidamente se busca una casilla que tenga un valor asignado y se emplea para encontrar otro coeficiente empleando la siguiente fórmula: Coeficiente desconocido = (Costo en la celda llena – coeficiente conocido de renglón o columna de columna o renglón) b) Calcular el costo marginal de las celdas vacías, aplicando la siguiente fórmula: Costo marginal = Costo en la celda – (Coeficiente de renglón + coefic. de columna) La solución será óptima si todos los costos marginales son no negativos. Mejoramiento de la solución: Este procedimiento es utilizado cuando la solución inicial no es óptima. Se comienza de la siguiente manera: a) Identificar la casilla con el costo marginal más negativo. A partir de ésta trazar una trayectoria cerrada con ángulos rectos en las casillas llenas. b) Determinar la cantidad a reasignar, seleccionando la menor de las cantidades correspondientes a las casillas con signo negativo. c) El proceso es iterativo hasta obtener una solución óptima.

Diferentes formas de trayectorias que se pueden dibujar:

1

Para el caso de problemas de transporte en el que se requiera maximizar, el método a aplicar es invertir todas las reglas. Se incluyen las ganancias en cada casilla, asignamos valores empezando con la casilla que tenga la mayor ganancia y así sucesivamente. La solución es óptima si todas las ganancias marginales son valores no positivos. El proceso de mejoramiento de la solución se inicia identificando la casilla con la ganancia marginal más positiva, el resto del procedimiento coincide con el de minimización a partir de los incisos b y c. Ejemplo 1. Una compañía ha firmado un contrato para suministrar asfalto destinado a cuatro proyectos de construcción de carreteras. La compañía cuenta con tres plantas de asfalto que pueden proporcionar este material a cualquiera de los proyectos o bien a todos.

Planta 1 2 3 Demanda Diaria Cargas de Camión

1 80 40 100 550

Proyectos de construcción 2 3 100 60 80 75 120 90 400 900

4 70 60 110 700

Cap. Diaria Cargas de camión 1200 1000 800

La compañía desea determinar el número de camiones que debe asignar cada planta a cada proyecto con el propósito de minimizar los costos de transporte.

Solución : Modelo de programación lineal para el problema: Xij: Cantidad de unidades que deben enviarse de la planta i al proyecto j. i = 1, 2, 3 j = 1, 2, 3, 4 Minimizar Z = 80X11 + 100X12 + 60X13 + 70X14 + 40X21 + 80X22 + 75X23 + 60X24 + 100X31 + 120X32 + 90X33 + 110X34 Sujeto a:

X11 + X12 + X13 + X14 = 1200 X21 + X22 + X23 + X24 = 1000 X31 + X32 + X33 + X34 = 800

X11 + X21 + X31 = 550 X12 + X22 + X32 = 400 X13 + X23 + X33 = 900 X14 + X24 + X34 = 300 Xij >= 0 para i = 1, 2, 3

Restricciones de oferta

Restricciones de demanda j = 1, 2, 3, 4

2

Problemas de trasporte: 1) La siguiente tabla muestra las capacidades de tres fábricas y sus costos de producción. También refleja diferentes costos de transporte de las diversas fábricas a los diversos mayoristas y la demanda mensual de cada uno de estos. Encuentre un programa de producción que cubra todas las necesidades a un costo mínimo total. Costo de Fábrica produc. A $110 B 95 C 130 Demanda uni/mens

Costo de transporte I II III IV 11 13 9 19 12 16 10 14 14 13 12 15 4200 8300 6300 2700

Capacidad uni/mens 7500 10000 8000

2) La siguiente tabla muestra tres fábricas con diferentes capacidades y costos de producción. También refleja diferentes costos de trasporte de las diversas fábricas a cuatro almacenes regionales. El precio de venta varía de acuerdo con el almacén. Encuentre el programa óptimo para maximizar las utilidades. Costos de Planta producción (Centavos) 1 38 2 27 3 30 Precio de venta (Centavo) Demanda

#1 23 21 18 64 300

Costos de Transporte Almacén #2 #3 18 21 24 23 21 27 63 64 450

500

Capacidad (Unidades) #4 25 18 25 64

650 630 620

850

1850

3) En tres fábricas 1, 2, 3 se dispone de ciertas cantidades de un producto, esas cantidades son respectivamente 100, 120 y 120. El producto se entrega a 5 almacenes 1, 2, 3, 4 y 5 que deben recibir respectivamente 40, 50, 70, 90 y 100 toneladas. El costo de trasporte de una unidad del producto desde cada fábrica a cada almacén se da en la tabla. Determine el plan de trasporte inicial y una solución mejorada, de tal manera que el costo sea mínimo.

Fábricas 1 2 3

1 0.4 0.6 0.5

Almacenes 3 0.2 0.2 0.6

2 0.1 0.5 0.2

3

4 0.6 0.5 0.4

5 0.9 0.7 0.8

4) Una compañía panificadora puede producir un pan especial en cualquiera de sus dos plantas en la siguiente forma: Capacidad de producción (Barras) 2500 2100

Planta A B

Costo de producción Centavos/Barra 23 25

Cuatro cadenas de restaurantes desean adquirir este pan, sus demandas y los precios que desean pagar son los siguientes: Cadena 1 2 3 4

Demanda máxima (Barras) 1800 2300 550 1750

Precio ofrecido (Centavos/Barra) 39 37 40 36

El costo en centavos de embarcar una barra de pan de una planta a un restaurante se da en la siguiente tabla:

Planta A Planta B

Cadena 1 6 12

Cadena 2 8 6

Cadena 3 11 8

Cadena 4 9 5

5) La cadena BURT BURGER tiene tres restaurantes en el país. Los restaurantes utilizan vasos desechables estándares. Se ha invitado a tres proveedores para competir por la concesión de surtir esto vasos, sus propuesta son: Proveedor A B C

Precio por C/1000 $0.90 $1.00 $1.10

Capacidad anual 30,000.00 75,000.00 135,000.00

El costo de trasporte en $ por cada 1000 vasos varía desde cada proveedor a cada BURT BURGER.

DE A B C

A la BURT BURGER N. 1 N. 2 0.80 0.10 0.50 0.20 0.20 0.40

N. 3 0.30 0.50 0.20

Las necesidades anuales para las tres BURT BURGER son 30,000, 60,000 y 120,000 respectivamente. ¿Cuántos vasos deben comprarse de cada proveedor para cada restaurante? 4

6) Utilice el método de transporte para encontrar la solución inicial del siguiente problema: Una compañía usa tres componentes A, B y C y requiere 60, 100 y 80 unidades de cada una de ellas respectivamente. Los componentes se pueden producir en cada una de las tres máquinas o se pueden comprar a los costos que se muestran en la siguiente tabla. Las capacidades de las máquinas se muestran entre paréntesis. Componente A B C

I(50) $15 12 10

II(80) $7 8 11

III(75) $10 13 4

Compra $15 14 12

7) Una empresa de la industria láctea posee tres plantas cercanas unas de otras, las cuales dispondrán a partir del próximo mes de 5000, 2500 y 8000 litros de leche diarios a distribuir. Para repartir estos se abrirán seis centros cada uno de los cuales distribuirá las siguientes cantidades: 2000, 1000, 3000, 4500, 2000 y 1500. Los costos de transporte (en centavos) a los nuevos centros de distribución son:

Plantas Planta A Planta B Planta C

D1 5 12 8

D2 4 11 11

CENTROS DE DISTRIBUCIÓN D3 D4 6 9 7 4 10 10

D5 8 6 7

D6 12 10 8

a) Formule el modelo de transporte b) Construya la matriz de transporte y determine el plan inicial de distribución de tal manera que el costo sea mínimo. c) Determine el plan de distribución óptimo.

8) Una tienda quiere comprar las siguientes cantidades de vestidos de mujer. Tipo de vestido Cantidad

A 150

B 100

C 75

D 250

E 200

Cuatro diferentes fabricantes someten propuestas para surtir no más de las cantidades a continuación (todos los tipos de vestidos combinados). Fabricantes Cantidad total

W 300

X 250

Y 150

5

Z 200

La tienda estima que su ganancia por vestido varía según el fabricante como se muestra en la matriz de abajo. ¿Cómo deberán hacerse los pedidos?

W Fabricante X Y Z

A 33 36 30 39

VESTIDO C 51 56 51 48

B 42 39 43 33

6

D 27 21 24 30

E 18 12 15 21