Actividad 1. Procedimiento de Optimización.

Nombre del Facilitador: José Luis Gallegos Ramírez

Nombre del Alumno: Nelson Estrada Escobar

2014

Universidad Abierta y a Distancia de México.

Carrera: Ingeniería en Desarrollo de Software.

Septimo Cuatrimestre

Materia: Investigación de OperacionesESAD

Introducción:

Esta actividad te permitirá iniciar con la resolución de problemas de Investigación de operaciones, para aquellos problemas relacionados con el transporte, que es el tema 1 de esta unidad. Estos problemas son parte todavía de la programación lineal pero ahora formando parte de las redes.

Propósito:

Esta actividad tiene el fin de reafirmar tu conocimiento con respecto al proceso de resolución de problemas de transporte y te ayudará a identificar el procedimiento de optimización, de tal manera, que llegues al grado de comprenderlo. Te servirá de preparación para entrar de lleno a la optimización y la ruta crítica.

Instrucciones:

1.- Lee y Resuelve los siguientes ejercicios como se pide.

2.- Escribe el procedimiento que seguiste para cada ejercicio. Agrega imágenes del software de computadora que usaste. Asegúrate de que sea entendible el procedimiento.

3.- Incluye la tabla simplex que se te pide desarrolles en cada ejercicio.

4.- Incluye la formulación del problema como un problema de transporte.

5.- Presenta la solución óptima resultado de algún programa de computadora disponible para resolver problemas de investigación de operaciones. Revisa el Tema1 de la Unidad 2 donde se te sugieren algunos ejemplos.

6.- Escribe tus conclusiones para cada ejercicio.

Ejercicio 1:

Una compañía embotelladora de agua tiene 3 fábricas denominadas A B y C, las cuales producen 150, 200 y 250 cargas respectivamente y requieren llevarlas a los 5 centros de distribución que hay en el país. Cada centro de distribución requiere de 100 cargas mensuales cada una. La siguiente tabla muestra la distancia en kilómetros que hay entre las fábricas y los centros de distribución.

Fabrica Centro de distribución1 2 3 4 5

A 500 300 1000 1200 1500 B 1000 900 600 1400 1000 C 600 800 1200 1500 700

El costo del flete por embarque es $1000 pesos más $ 5 pesos por kilómetro. ¿Cuántas cargas deben mandarse desde cada planta a cada centro de distribución para minimizar el costo total de transporte?

a) Formule este problema como un problema de transporte. b) Dibuje la representación de red. c) Obtenga una solución óptima con algún software de los vistos en la Unidad 2.

Ejercicio 2:

La señora Lupita que tiene una cocina económica necesita comprar exactamente 5 litros de leche el día de hoy y al menos 7 litros mañana. El proveedor 1 quiere vender el litro de leche hoy a $6.00 pesos con un máximo de 9 litros y ya mañana a un precio de $5.00 pesos. El proveedor 2 quiere vender un máximo de 7 litros en total a un precio de $5.70 hoy, mañana a un precio de $5.40 por litro.

La señora Lupita quiere saber cuánto debe comprar a cada uno para minimizar su costo y a la vez cumplir con los requerimientos mínimos de su cocina económica.

a) Formule el modelo de programación lineal y elabore la tabla simplex inicial.

b) Formule este problema como un problema de transporte mediante la construcción de la tabla de parámetros apropiada.

c) Obtenga una solución óptima con algún software de los vistos en la Unidad 2. Ya que realizaste tus ejercicios:

7.- Guarda la actividad con el nombre DIOP_U2_A1_XXYZ.Doc. Sustituye las XX por las dos primeras letras del primer nombre, la Y por la inicial del apellido paterno y la Z por la inicial del apellido materno.

8.- Envía el archivo a tu Facilitador mediante la sección de Tareas para recibir retroalimentación. No olvides consultar los criterios de evaluación de la actividad.

Ejercicio 1:

Una compañía embotelladora de agua tiene 3 fábricas denominadas A B y C, las cuales producen 150, 200 y 250 cargas respectivamente y requieren llevarlas a los 5 centros de distribución que hay en el país. Cada centro de distribución requiere de 100 cargas mensuales cada una. La siguiente tabla muestra la distancia en kilómetros que hay entre las fábricas y los centros de distribución.

Fabrica Centro de distribución1 2 3 4 5

A 500 300 1000 1200 1500 B 1000 900 600 1400 1000 C 600 800 1200 1500 700

El costo del flete por embarque es $1000 pesos más $ 5 pesos por kilómetro. ¿Cuántas cargas deben mandarse desde cada planta a cada centro de distribución para minimizar el costo total de transporte?

a) Formule este problema como un problema de transporte. b) Dibuje la representación de red. c) Obtenga una solución óptima con algún software de los vistos en la Unidad 2.

RestriccionesNivel de lasRestriccione

sCosto $ Centros de Distribución (km)

FABRICA Producción Flete Km 1 2 3 4 5*Carga

mensual*100 *100 *100 *100 *100

A 150 1000 5 500 300 1000 1200 1500B 200 1000 5 1000 900 600 1400 1000C 250 1000 5 600 800 1200 1500 700

Ahora mostraremos los kilómetros entre las fábricas y los centros de distribución de los productos de acuerdo a su distancia en kilómetros.

Centros de FábricasDistribución A B C

1 500 1000 600

2 300 900 800

3 1000 600 1200

4 1200 1400 1500

5 1500 1000 700

El costo del flete por embarque es 1000.00 pesos adicionando 5 pesos más por kilómetro por lo que las operaciones y la tabla quedarían de la siguiente manera:

Columna 11000 + (500 * 5) = 1000 + 2500= 35001000 + (1000 * 5)= 1000 + 5000= 60001000 + (600 * 5)= 1000 + 3000= 4000

Columna 21000 + (300 * 5)= 1000 + 1500= 25001000 + (900 * 5)= 1000 + 4500= 55001000 + (800 * 5)= 1000 + 4000= 5000

Columna 31000 + (1000 * 5)= 1000 + 5000= 60001000 + (600 * 5)= 1000 + 3000= 40001000 + (1200 * 5)= 1000 + 6000= 7000

Columna 41000 + (1200 * 5)= 1000 + 6000= 70001000 + (1400 * 5)= 1000 + 7000= 80001000 + (1500 * 5)= 1000 + 7500= 8500

Columna 51000 + (1500 * 5)= 1000 + 7500= 85001000 + (1000 * 5)= 1000 + 5000= 60001000 + (700 * 5)= 1000 + 3500= 4500

La tabla con los valores por columna:

Fabrica Centro de distribución (km)1 2 3 4 5

A (1) $3,500 $2,500 $6,000 $7,000 $8,500B (2) $6,000 $5,500 $4,000 $8,000 $6,000C (3) $4,000 $5,000 $7,000 $8,500 $4,500

Solución:

El modelo de programación lineal para el problema es el siguiente:

Variables de Decisión: xij: Unidades transportadas desde las fábricas i (i=A, B, C) hasta los centros de distribución j (j=1, 2, 3, 4, 5)

Función Objetivo: Minimizar el costo de transporte dado por la función: 

Minimizar:Z = 3500x11 + 2500x12 + 6000x13 + 7000x14 + 8500x15 + 6000x21 + 5500x22 + 4000x23 + 8000x24 + 6000x25 + 4000x31 + 5000x32 + 7000x33 + 8500x34 + 4500x35

Restricciones:

Para satisfacer los requerimientos de demanda haremos el siguiente procedimiento:

X11 + X12 + X13 + X14 + X15 = 150 (A) X21 + X22 + X23 + X24 + X25 = 200 (B)

X31 + X32 + X33 + X34 + X35 = 250 (C)

Todo ello sujeto a la oferta de las plantas:

X11 + X21 + X31 = 100 (1)X12 + X22 + X32 = 100 (2) X13 + X23 + X33 = 100 (3)

X14 + X24 + X34 = 100 (4) X15 + X25 + X35 = 100 (5)

No Negatividad: xij ≥ 0 i = A(1), B(2), C(3) j = 1,2,3,4,5

MÉTODO SIMPLEX

Pasando el problema a la forma estándar, añadiremos las variables de exceso, holgura, y artificiales según corresponda.

Como la restricción 1 es del tipo '≤' se agrega la variable de holgura X6.

Como la restricción 2 es del tipo '≤' se agrega la variable de holgura X7.

Como la restricción 3 es del tipo '≤' se agrega la variable de holgura X8.

MINIMIZAR:

100X1 + 100X2 + 100X3 + 100X4 + 100X5

3500X1 + 2500X2 + 6000X3 + 7000X4 + 8500X5 ≤ 1506000X1 + 5500X2 + 4000X3 + 8000X4 + 6000X5 ≤ 2004000X1 + 5000X2 + 7000X3 + 8500X4 + 4500X5 ≤ 250

X1, X2, X3, X4, X5 ≥ 0

MAXIMIZAR:

-100X1 -100X2 -100X3 -100X4 -100X5 + 0X6+ 0X7 + 0X8 3500X1 + 2500X2 + 6000X3 + 7000X4 + 8500X5 + 1X6 = 150

6000X1 + 5500X2 + 4000X3 + 8000X4 + 6000X5 + 1X7 = 2004000X1 + 5000X2 + 7000X3 + 8500X4 + 4500X5 + 1X8 = 250

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

Ahora pasaremos a construir la primera tabla del método Simplex.

Tabla 1

-100 -100 -100 -100 -100 0 0 0

Base Cb X0 X1 X2 X3 X4 X5 X6 X7 X8

X6 0 150 3500 2500 6000 7000 8500 1 0 0

X7 0 200 6000 5500 4000 8000 6000 0 1 0

X8 0 250 4000 5000 7000 8500 4500 0 0 1

Z 0 100 100 100 100 100 0 0 0

La solución óptima es

Z = 0 X1 = 0 X2 = 0 X3 = 0 X4 = 0 X5 = 0

Representación del modelo de transporte con nodos y arcos:

F.A

(150)

F.B(200)

F.C(250)

C.D.1(100)

C.D.2(100)

C.D.3(100)

C.D.3(100)

C.D.5(100)

X

X

X

XX

X

X

X

X

X

X

X

X

X

X

La producción total desde las tres fábricas (A, B, C) es de:

150 + 200 + 250 = 600 cargas de agua embotellada totales

Con esta cantidad cubrimos la demanda total de los cinco destinos (Centros de distribución 1, 2, 3, 4, 5)

100 + 100 + 100 + 100 + 100 = 500 cargas mensuales

Uso de Solver de Excel

Ejercicio 2:

La señora Lupita que tiene una cocina económica necesita comprar exactamente 5 litros de leche el día de hoy y al menos 7 litros mañana. El proveedor 1 quiere vender el litro de leche hoy a $6.00 pesos con un máximo de 9 litros y ya mañana a un precio de $5.00 pesos. El proveedor 2 quiere vender un máximo de 7 litros en total a un precio de $5.70 hoy, mañana a un precio de $5.40 por litro.

La señora Lupita quiere saber cuánto debe comprar a cada uno para minimizar su costo y a la vez cumplir con los requerimientos mínimos de su cocina económica.

a) Formule el modelo de programación lineal y elabore la tabla simplex inicial.

b) Formule este problema como un problema de transporte mediante la construcción de la tabla de parámetros apropiada.

c) Obtenga una solución óptima con algún software de los vistos en la Unidad 2. Ya que realizaste tus ejercicios:

El planteamiento es el siguiente:

Hoy = 5 Litros de Leche (5 lts)Mañana = 7 Litros de Leche (7 lts)

Por lo que ahora realizaremos la siguiente tabla:

PROVEEDOR 1 PROVEEDOR 2

LECHE Precio Max

(Litros)Total Precio

Max (Litros)

Total

HOY 6.00 9 54.00 5.70 7 39.90MAÑANA 5.00 9 45.00 5.40 7 37.80

Ahora pasaremos el problema en su forma estándar, añadiendo las variables de exceso, holgura y artificiales según corresponda.

Como la restricción 1 es del tipo '≤' se agrega la variable de holgura X3. Como la restricción 2 es del tipo '≤' se agrega la variable de holgura X4.

MINIMIZAR MAXIMIZAR

5X1 + 7X2 -5X1 – 7X2 + 0X3 + OX4

6X1 + 5X2 ≤ 9 6X1 + 5X2 + 1X3 = 95.7X1 + 5.4X2 ≤ 7 5.7 X1 + 5.4X2 + 1X4 = 7

X1, X2 ≥ 0 X1, X2, X3, X4 ≥ 0

Ahora construiremos la primera tabla del Método Simplex

Método Simplex

Tabla 1 -5 -7 0

Base Cb X0 X1 X2 X3

X3 0 9 6 5 1

X4 0 7 5.7 5.4 0

Z 0 5 7 0

La solución óptima para el problema es:

Z = 0X1 = 0X2 = 0

Uso del programa solver para buscar la solución: