ESCUELA MILITAR DE INGENIERA

ESCUELA MILITAR DE INGENIERADepartamento de Ingeniera IndustrialOPTIMIZACIN

Laboratorio No. 3 Optimizacin Entera1. (Secuenciacin de Conductores). Una empresa de autobuses realiza trayectos entre cuatro ciudades A, B C y D, de acuerdo al siguiente esquema.

Los trayectos estn representados por arcos etiquetados con un par de nmeros: El primero representa el nmero de trayectos; el segundo su duracin en horas, incluyendo los tiempos de trnsito en las estaciones de las ciudades por donde pase.La empresa tiene contratados a cuatro conductores P, J, L y M. Los dos primeros viven en la ciudad A; los dos segundos, en D. La poltica que sigue la empresa es sus operaciones viene determinada por las condiciones: Cada da un conductor realiza con su autobs slo una operacin, es decir, una sucesin de trayectos que comienzan y terminan en su ciudad de residencia y no incluye un mismo trayecto ms de una vez. Ningn conductor puede estar al volante ms de 8 horas.La empresa est en condiciones de afirmar que cubrir cada trayecto al menos una vez por da, pero sin garantizar una adecuada conexin entre horarios para los diferentes trayectos. Adems la empresa paga a los conductores 5000 pesos/hora al volante y 2000 pesos/trnsito (ciudades intermedias por las que pasa la ruta). Formular un programa entero que sugiera cmo deben asignarse los conductores a los trayectos para que el costo total sea mnimo.Construccin del ModeloConsiderando que cada conductor sale y regresa a la ciudad donde reside, debe considerarse las posibles rutas que puede hacer cada conductor considerando, adems, el lmite mximo de 8 horas y que cada trayecto debe cubrirse una vez. Por ejemplo, los conductores P y J puede hacer la ruta 3 7 8, pues comienza y termina en la ciudad A, cumplindose las condiciones indicada.El costo asociado es:

ya que son 2+3+2=7 horas y 2 trnsitos, con ciudades intermedias B y C. La tabla siguiente resume todas las posibilidades.

Luego, el problema de asignar conductores a trayectos se reduce al de asignar conductores a rutas factibles.Variables de Decisin

Restricciones (Camino 1) Para establecer las restricciones, obsrvese, que por ejemplo, el camino 1 queda cubierto si se hacen las rutas 3 5. Ello se conseguir imponiendo

Procediendo de forma similar para el resto de los caminos, se tiene las restricciones Camino 2

Camino 3

Camino 4

Camino 5

Camino 6

Camino 7

Camino 8

No se puede utilizar ms rutas que conductores para cubrirlas. A lo sumo se pueden cubrir cuatro de las seis rutas.

Funcin Objetivo: Minimizar el costo total, en miles de pesos, de las rutas usadas

Formulacin del Programa 0-1

Min s.a.

R. Deben realizarse:i. La ruta constituida por los trayectos 3-2, con el itinerario entre ciudades A-B-A.ii. La ruta compuesta por los trayectos 4-6-8, con el itinerario entre ciudades A-D-C-Aiii. La ruta conformada por los trayectos 1-7-5, con el itinerario entre ciudades D-B-C-DEl costo total mnimo asciende a $ 110 000, siendo necesario tan slo 3 conductores, quedando uno ocioso.2. (Planificacin de la produccin y expansin). Una empresa fabrica tres productos, 1, 2, 3, que deben procesarse en dos tipos de maquinaria denominadas A y B. La siguiente tabla proporciona los tiempos de procesamiento por t unidades procesadas con cada mquina, as como los beneficios por t unidades en miles de pesos y la disponibilidad de cada tipo de maquinaria en horas por semana.

La empresa considera aumentar la disponibilidad de tiempo de procesamiento de la maquinaria, de acuerdo con algunas de las posibilidades indicadas en la tabla siguiente.

A lo sumo se puede realizar un tipo de incremento para cada mquina. Los ndices de demanda de los productos son

Se supone que la inversin total no puede exceder de 340000 pesos(a) Formular un modelo de programacin entera que proporcione el programa de procesamiento e inversin de mayor beneficioVariables de DecisinVariables de decisin continuas

Variables de decisin 0-1

Restricciones Lmites de disponibilidad de horas en mquinas A y B

(Maquinaria A)

(Maquinaria B) Lmites de Demanda

Lmites de Inversin (en miles de pesos)

Eleccin del tipo de ampliacin para cada maquinaria (slo puede elegirse un tipo de ampliacin)

Variables enteras y continuas

Funcin Objetivo: Consiste en maximizar el beneficio neto que se obtiene de la diferencia entre el beneficio y el costo de la inversin (en miles de pesos)

Formulacin del Programa Entero

Maximizar s.a.

Solucin Mediante WinQSB:Tabla de equivalencias entre variables

R. Debeni. Procesarse 13.5 toneladas del producto 1ii. Procesarse 3 toneladas del producto 2iii. Procesarse 7 toneladas del producto 3iv. Debe incrementarse la disponibilidad de la maquinaria B en 12 horasSiendo el beneficio mximo mximo de 1780000 pesos(b) Si la empresa desease aumentar la disponibilidad de un solo tipo de maquinaria, Cmo se modificar el modelo anterior reflejando est situacin?S solo se admite el aumento de la disponibilidad de un tipo de maquinaria, debe sustituirse las restricciones

por

En este caso, la solucin es la misma que en (a), como caba esperar a la vista de la solucin anterior.(c) Si no se quiere aadir la disponibilidad de B a menos que se aada de A Cmo se representa esta nueva condicin?Si ahora no se incrementa la disponibilidad de B, a menos que se incrementa la de A, entonces a la formulacin de (a) debe aadirse la restriccin

En este caso R. Debeni. Procesarse 10.67 toneladas del producto 1ii. Procesarse 3 toneladas del producto 2iii. Procesarse 7 toneladas del producto 3iv. No deben incrementarse la disponibilidad de ninguna maquinaria.Siendo el beneficio mximo mximo de 1728333 pesos(d) La empresa desea ampliar la disponibilidad con la maquinaria B si y slo si se incrementa tambin la de A. Cmo debe modificarse la condicin considerada en c?Si la empresa desea ampliar la disponibilidad de la maquinaria B si y slo si ampla tambin A, bastara con escribir la restriccin de (c) como una igualdad

Obtenindose la misma solucin que en (c).

1

Hoja1ProductoDemanda (t)Tipo deProductosDisponibilidadTipo de MaquinariaABMnimaMximamaquinaria123(horas)Incremento de Disponibilidad (Horas)10158121617A25470160170170175238B346863720807095

Hoja2

Hoja3

Hoja1RutaConductoresTrayectos enN deN dejfactiblesla rutahorastrnsitos1P, J3-241222P,J3-7-872393P,J,L,M4-1-272394P,J,L,M4-6-882445L,M1-7-582446L,M6-56132

Hoja2

Hoja3

Hoja1Tipo deProductosDisponibilidadmaquinaria123(horas)A25470B34686807095

Hoja2

Hoja3

Hoja1Tipo deProductosDisponibilidadTipo de MaquinariaABmaquinaria123(horas)Incremento de Disponibilidad (Horas)1015812A25470160170170175B34686807095

Hoja2

Hoja3

Hoja1ProductoDemanda (t)Tipo deProductosDisponibilidadTipo de MaquinariaABMnimaMximamaquinaria123(horas)Incremento de Disponibilidad (Horas)10158121617A25470160170170175238B346863720807095

Hoja2

Hoja3

B

C

D

(8,2)

(3,2)

(2,2)

(7,3)

(6,3)

(5,3)

(1,2)

(4,3)

A