- El
modelo tipo "mochila" - Formulación de modelos con variables
enteras - Ejercicios. Modelos de programación
entera - Problemas de
planeación - Modelos de programación
entera
Un modelo se dice de
programación entera si incluye
alguna(s) variable(s)
entera(s)
TIPOS DE VARIABLES
ENTERAS
1. Variables Enteras Generales
2. Variables Binarias
CLASES DE MODELOS DE PE
Dependiendo del tipo de variables que
incluyen pueden ser:
1. Modelos de PE pura
2. Modelos Mixtos
Los Modelos Mixtos son útiles
cuando se incluyen
Costos Semifijos
COSTOS SEMIFIJOS
Son costos cuya magnitud no depende del
volúmen producido, pero que sólo ocurren si se
produce.
El modelo tipo
"mochila"
EJEMPLO:
Una persona dispone de $14,000 y desea
escojer la mejor combinación de entre cuatro alternativas
de inversión:
La solución de este modelo Binario
indica la mejor combinación.
Formulación del Modelo
"Mochila"
OBJETIVO: incluir el máx # de
productos de distinto valor (ci) en un espacio limitado
(b)
Formulación de modelos con variables
enteras
APLICACIONES TIPICAS
Modelos tipo Mochila:
se busca incluir el máximo
número de diversos productos con diferente valor, en un
espacio limitado.
Selección de
Cartera:
seleccionar la mejor combinación de
alternativas para alcanzar el máximo
rendimiento.
Modelos con Costos
Semi-Fijos
Modelos con costos variables y costos
semi-fijos
(de preparación o de
instalación.)
Problemas de Cobertura
Determinar el número mínimo
de localizaciones con el objeto de proveer cobertura a un grupo
de areas
Problemas de
Asignación
Se busca asignar uno-a-uno recursos en
forma óptima.
Programación de
Recursos:
asignar optimamente recursos de manera
secuencial.
Problema del Agente Viajero
(TSP)
Determinar la mejor secuencia de
actividades ejecutando cada actividad una sola vez.
2.1 USO DE VARIABLES
BINARIAS
(se usan para indicar decisiones
lógicas)
Suponga que se disponen de k
alternativas y sea
Xj = 1 si se escoje la alternativa j
0 si no
ALTERNATIVAS MUTUAMENTE
EXCLUSIVAS
Alternativas que no pueden aparecer juntas
en la solución
x1 + x2 ( 1
MAXIMO # ACEPTABLE DE
ALTERNATIVAS
Cuando todas las alternativas no pueden
estar juntas en la solución
x1 + x2 + x3 + x4 + x5 ( 2
ALTERNATIVAS DEPENDIENTES
El valor de una variable depende del valor
de otra(s)
Ejemplo:
alternativa 2 sólo puede estar en
solución si alternativa 1 se seleccionó
x2 ( x1
EJERCICIO
Suponga que X1 X2 y X3 son variables
binarias cuyo valor 1 indica que se va a abrir una planta en una
lugar determinado y 0 indica lo contrario. Escriba una
restricción para cada una de las siguientes
condiciones:
a. Si se abre la planta 1 entonces la
planta 2 no debería abrirse.
b. Si se abre la planta 1 entonces la
planta 2 debería abrirse.
c. Al menos una de las tres plantas
debería abrirse.
d. No más de dos de las tres plantas
debería abrirse.
e. Si ni la planta 2 y ni la planta 3 se
abren, la planta 1 no debería abrirse.
f. Si se abre la planta 1 o la planta 3 no
se abre, la planta 2 debe abrirse.
SOLUCIÓN
VARIABLES BINARIAS Y
CONTINUAS
RANGOS CONDICIONADOS
Si una variable contínua puede tomar
valor CERO ó, POSITIVO pero dentro de un intervalo
específico
Ejemplo:
MAXIMO # DE RESTRICCIONES
Cuando una solución factible solo
necesita satisfacer un subconjunto de todas las
restricciones del modelo
Ejemplo:
Ejercicios.
Modelos de programación entera
1. Un fabricante de muebles de oficina, produce dos
tipos de escritorios: ejecutivos y secretariales. La compania
tiene dos plantas en las que fabrica los escritorios. La planta 1
es una planta antigua que opera con doble turno de 80 horas por
semana. La planta 2 es una planta mas nueva y no opera a su
capacidad total. Cada turno de la planta 2 trabaja 25 horas por
semana y la planta opera 2 turnos. La siguiente tabla muestra el
tiempo de producción (horas/unidad) y los costos
estándar ($/unidad) en cada planta. Tambien se muestran
los precios de venta de cada escritorio.
Debido a que la compañía ha estado
experimentando un exceso de costos durante el ultimo periodo
presupuestal, los administradores han fijado una
restricción semanal sobre los costos de
producción.
El Costo Semifijo por producir en cada planta
asciende a $ 600 y $900 para las plantas 1 y 2 respectivamente.
Además en caso de producir algun modelo de escritorio se
debe asegurar una producción mínima de 100
unidades.
El presupuesto semanal para la producción en
miles de pesos tambien se muestra en la tabla. Se le pide a usted
averiguar cuál es el numero óptimo de escritorios
de cada tipo, a producirse en cada planta con el objeto de
maximizar las ganancias.
PROBLEMA 1:
Nuevas Variables y Restricciones:
2. A un paciente hospitalizado se le han restringido la
cantidad de los dos alimentos que puede consumir. De acuerdo con
lo prescrito por el doctor, se deben satisfacer los siguientes
requerimientos nutritivos mínimos por día: 1000
unidades de nutriente A, 2000 del nutriente B, y 1500 unidades
del nutriente C. Existen dos fuentes alimenticias disponibles F1
y F2. Cada onza de la fuente alimenticia F1 contiene 100 unidades
del nutriente A, 400 unidades del nutriente B, y unidades del C.
Cada onza de F2 contiene 200 unidades de A, 250 unidades de B, y
200 unidades de C. Las fuentes alimenticias cuestan $6 y $8 por
onza.
a) Si se considera que los costos de pedidos no
son despreciables y ascienden a $5 y $7.5 para las fuentes F1 y
F2, cuál es la mejor combinación de fuentes
alimenticias?
b) Si además sólo es necesario
satisfacer dos de los tres requerimientos nutritivos,
cuál es la mejor combinación de fuentes
alimenticias?
PROBLEMA 2:
MIN 5 Y1 + 7.5 Y2 + 6 X1 + 8 X2
SUBJECT TO
2) – 99999 W1 + 100 X1 + 200 X2 >= – 98999
3) – 99999 W2 + 400 X1 + 250 X2 >= – 97999
4) – 99999 W3 + 200 X1 + 200 X2 >= – 98499
5) – 99999 Y1 + X1 <= 0
6) – 99999 Y2 + X2 <= 0
7) W1 + W2 + W3 >= 2
END
INT Y1
INT Y2
INT W1
INT W2
INT W3
3. Una companía enfrenta el problema
de determinar en qué proyectos invertir durante los
próximos 4 anos. La compania dispone de un presupuesto
limitado anual para inversiones. Existen 4 proyectos disponibles.
A éstos se les ha caracterizado por su valor presente
estimado y los costos anuales de capital requeridos. Estos se
muestran en la siguiente tabla:
Requerimientos de Capital Anual (en miles de
dólares)
La compra de nueva maquinaria sólo puede
realizarse en caso de que la expansión de la planta se
lleve a cabo y se deseen invertir en la búsqueda de nuevos
productos. Desarrolle un plan de asignación de
capital que muestre las erogaciones necesarias para cada uno de
los 4 anos y seleccione que proyectos conviene financiar.
Suponga además que se ha decidido que si se invierte
en la Ampliación del almacén no se podrá
invertir en Nueva Maquinaria.
4. La companía OVM fabrica un
producto cuya demanda es estacional y cambia mes con mes. El
pronóstico de la demanda para los proximos cuatro meses es
1800, 2200, 3400, y 2800 unidades. Debido a la demanda variable,
se ha encontrado que en algunos meses existe producción en
exceso lo cual ocasiona grandes costos de almacenaje y
mantenimiento. En otros meses la compania no puede cubrir la
demanda resultando en perdidas de oportunidades de
venta.
La capacidad de la planta es de 2400 articulos por mes
utilizando turnos normales. De requerirse subcontratos es posible
disponer hasta de 800 articulos adicionales.
El costos variable de produccion es de $ 400 dolares por
unidad, para articulos fabricados. El costo de subcontrato
implica pagar un costo unitario de $450. De no venderse un
articulo y almacenarse para el proximo mes se incurre en un costo
de 15 dolares por mes.
De producir unidades en un mes particular es
necesario realizar la preparación de maquinaria, hacer
corridas de prueba y echar a andar ciertos equipos especiales,
por lo quese incurriría en costos semifijos de $150. De
ordenar un artículo al subcontratista se requiere incurrir
en un costo semifijo de $50/orden.
Se le pide a usted que determine un programa
óptimo de adquisición que minimice los costos de
producción, almacenaje y subcontrato para el
período de 4 meses. El programa debe satisfacer la demanda
pronosticada.
PROBLEMA 4:
Nuevas Variables y Restricciones:
5. Una compañia tiene tres localizaciones
alternativas para ubicar nuevos almacénes que den servicio
a la región norte del país. Existen 5 clientes
(C1,C2,C3,C4,C5) importantes es esta región. Se desea
determinar en cuáles localizaciones se instalarán
almacenes como puntos de distribución para surtir a los
clientes.
SOLUCIÓN
6. (Cobertura Total ) El Alcalde del DF
está considerando la reubicación de un
número de estaciones de policía con el objeto de
reforzar el cumplimiento de la ley en colonias de alta
criminalidad. Las localidades donde potencialmente puede ubicarse
estaciones de policia así como las colonias de la ciudad
que pueden ser cubiertas por estas localidades se muestran en la
siguiente tabla. Formule un modelo de PE para encontrar el
número mínimo de estaciones cubriendo todas las
colonias peligrosas.
SOLUCION:
7. (Maximizar Cobertura con recursos
limitados ) Un banco está planeando abrir 2
sucursales en Monterrey. La dirección ha dividido la
ciudad en 7 zonas así como ha estimado el número de
clientes potenciales en c/u. . Se supone que un local ubicado en
una zona podría atender a los clientes de zonas vecinas
así como a los de su propia zona. (Vease la tabla
siguiente)
a) Plantee un modelo de PE para encontrar
las zonas dónde ubicar las sucursales con el objeto de
maximizar el número de clientes potenciales
atendidos.
b) Suponga que la cobertura del banco no es
igual si los clientes potenciales son atendidos a través
de un local que no está ubicado en la misma zona. La
cobertura es del 50% en la misma zona de la sucursal establecida
y 25% si los clientes acuden a sucursales fuera de su zona.
Modifique el modelo para este caso.
8. Una companía necesita contratar
personal de seguridad. Se estima que los guardias trabajaran
turnos de 8 horas y que cada dia se necesitan seis turnos para
cubrir las 24 horas. Las siguientes tablas muestran el
número requerido de personal de seguridad por cada 4 horas
del día y los horarios de entrada y salida de cada turno.
Se necesita determinar cuántos guardias deberán
trabajar en cada turno con el objeto de minimizar el
número de ellos.
SOLUCION:
Problemas de
planeación
Determinar la "mejor" secuencia de
actividades
Mejor: costo, tiempo o distancia
Actividades: Tareas a efectuarse en varias
máquinas, o
secuencia de localizaciones a
visitar
TRAVELING SALESMAN PROBLEM (EL AGENTE
VIAJERO)
Determinar la ruta más corta
para que saliendo de un punto base se visiten diversas
localizaciones "sólo una vez" y después se vuelva
al punto base
EJEMPLO
Un vendedor trabaja para una compañía
localizada a sur de México D.F. Esta semana debe visitar a
cuatro clientes. La siguiente tabla muestra las distancias desde
la compañía hasta cada cliente. El vendedor desea
visitar la ruta más corta considerando que no conviene
visitar a algun cliente más de una vez.
Cuántas combinaciones posibles hay ?
Saliendo de la oficina hay 4 posibles
destinos
saliendo del primer destino hay 3 posibles
destinos
saliendo del segundo destino hay 2 posibles
destinos
saliendo del último cliente sólo hay 1
posibles destinos : la oficina
En total existen 4! = 24 posibles
combinaciones
Cual es la de menor costo o tiempo
?
SOLUCIÓN
Tour : secuencia de visitas
Subtour : tour en el que se visita una
localización más de una vez (o su base más
de veces)
Como eliminar subtours (son soluciones infactibles)
?
EJEMPLO
Una pequeña empresa tiene un contrato para llevar
a cabo varios trabajos de preparación de pinturas
utilizando una máquina de alta velocidad. Cuando la
máquina cambia de trabajo deba limpiarse por completo
antes de realizar un trabajo diferente en el que la
combinación de pinturas y colorantes sea distinta. En la
tabla a continuación se muestran los tiempos de limpieza
en minutos para todas las posibles secuencias de trabajos. El
objetivo es minimizar la suma de todos los tiempos de limpieza
eligiendo la mejor secuencia de trabajos.
Trabajo
Modelos de
programación entera
METODOS DE SOLUCION
Se requiere que una solución
factible tenga valores enteros para alguna o todas las variables
de decisión.
La Región Factible no es una
región contínua sino que está formada por
puntos separados.
Un Modelo de PE se llama Relajado si no se
toma en cuenta la restricción de soluciones
enteras.
El modelo de PE relajado es el
modelo de PL
Redondear una solución de PL puede
resultar en una solución lejos de la óptima
ó en una solución No factible.
No existe un procedimiento de analisis de
sensibilidad para modelos de PE (tal como en PL) . Tampoco se
genera información sobre sensibilidad al usar la
computadora.
3 MODELOS DE PROGRAMACION
ENTERA
METODOS DE SOLUCION
1. METODO GRAFICO
Solo 2 variables
2. REDONDEO DE LA SOLUCION DE PL
No se asegura obtener la
solución óptima
En algunos casos se obtiene una
solución muy lejos de
la óptima
3. ENUMERACION COMPLETA
Si hay 2 variables binarias, 4
soluciones posibles
Si hay 50 variables binarias, 250
soluciones posibles
4. RAMIFICACION Y ACOTAMIENTO (Branch &
Bound)
5. PLANOS DE CORTE (Strong Cutting
Planes)
2.1 ENUMERACION
COMPLETA
EJEMPLO
Cada nodo representa un modelo en el que
alguna(s) variable(s) tiene su valor especificado
Cada nodo terminal representa una
solución entera (factible ó no)
Si en un nodo cualquiera la solución
es infactible los nodos que siguen bajo él, tendran
solución infactible
2.1 ENUMERACION
COMPLETA
EJEMPLO
2.2 REDONDEO DE LA SOLUCION DE
PL
EJEMPLO:
La solución óptima de
PE tiene un valor en Z que es
43% superior a la solución
redondeada!
Al redondear se debe tener en cuenta
la magnitud las variables
Siempre verificar que la solución
redondeada se mantenga factible
2.3 RAMIFICACION Y
ACOTAMIENTO
(Land & Doig, 1960)
RAMIFICAR (Un modelo de PL con
solución no entera):
Dividir la región factible en 2
regiones que
– no contengan la solución del
modeloPL relajado
– sí contengan todas sus
soluciones enteras factibles
CRITERIO BASICO:
Agregar restricciones a un modelo no
puede producir
un modelo con mejor solución
Z
PROCEDIMIENTO DE MAXIMIZACION
1. Resolver Modelo PE relajado
(Si solución es entera es la
óptima)
2. Definir Cotas Superior e
Inferior
Cota Superior (CS) = Modelo
relajado
Cota Inferior (CI) = Redondeo
factible
3. Ramificar
4. Para cada nodo, resolver su modelo
relajado y definir su CS y CI
Si solución es entera, o
Si solución es infactible, o Ya no
ramificar
Si Z ( CI más el nodo
5. Si ya no se puede ramificar
la solución óptima es la del
nodo con mejor solución entera
6. Si se puede ramificar, volver al paso
3
– La CI es igual a la mejor solución
entera hasta el momento
– La CS en un nodo es igual a Z
encontrado
– A medida que se ramifica y se desciende
del árbol la CS tiende a disminuir
RAMIFICACION Y
ACOTAMIENTO
CASOS ESPECIALES
MODELOS MIXTOS
Sólo ramificar variables
enteras
MODELOS BINARIOS
Modelo Relajado: Reemplazar X= 0 ó 1
por X ( 1
Ramificar una variable binaria
X = 0 (1 rama)
X = 1 (1 rama)
MINIMIZAR
Cambiar CS por CI
2. Definir Cotas Superior e
Inferior
Cota Superior (CS) = Redondeo
factible
Cota Inferior (CI) = Modelo
relajado
4. Para cada nodo,
resolver su modelo relajado y definir su CS
y CI
Si solución es entera
Si solución es infactible Ya no
ramificar más el nodo
Si Z > CS
– La CS es igual a la mejor
solución entera hasta el momento
– La CI en un nodo es igual a Z
encontrado
– A medida que se ramifica y se desciende
del Arbol la CI tiende a aumentar
ANALISIS DE SENSIBILIDAD
Costos Reducidos y Precios Sombra Ver
pág. 353 Eppen
Enviado por:
Pablo Turmero