PROGRAMACION ENTERA IP

LAURENCE A. WOSLEY

FORMULACIONES
Cap 1

19/02/2020 1
 CONTENIDO

1. Formulaciones
1.1 Introducción
1.2. Qué es programación entera?
1.3. Formulación Ips y BIPs
1.4. La explosión combinatoria
1.5. Formulación entera mixta
1.6. Formulaciones alternativas
1.7.Formulaciones buenas e ideales.
1.8. Notas
1.9. Ejercicios

19/02/2020 2
 1.1. Introducción
Existe una gran variedad de problemas que pueden ser formulados y resueltos
usando la programación entera.

1. Programación de trenes (Metro).

Cada tren tiene un tiempo de viaje entre estaciones y un tiempo que

permanece en cada estación. En una misma línea pueden existir
varios trenes y los que viajan en la misma línea deben estar
separados por un intervalo mínimo de tiempo. La idea es programar
los tiempos de llegada y partida para hacer la conexión entre los
trenes A y B de tal manera que los tiempos de llegada de A y el de
salida de B sean lo suficientemente largos para permitir a los
pasajeros cambiar, pero lo suficientemente cortos para que el
tiempo de espera no sea excesivo.

19/02/2020 3
 2. Programación de la tripulación en las aerolíneas.

Dada la programación de vuelos para un tipo de avión particular,

se debe programar semanalmente el tiempo de servicio para la
tripulación que consiste en un conjunto de uno o más vuelos
que la tripulación debe atender y se deben satisfacer
restricciones como el tiempo total limitado de vuelo, tiempo
mínimo de descanso entre vuelos, longitud máxima de tiempo
de servicio, regreso de la tripulación a su punto de partida etc.
El objetivo es minimizar la nómina de la empresa.

3. Planeación de la producción.

Una compañía multinacional desea planear la producción en un

horizonte de planeación de tres meses donde el plan de
producción y el envío sean esquematizados con base en los
reportes de ventas estimadas. El plan debe cubrir entre 200 y
400 productos producidos en 5 fábricas diferentes para ser
enviados a 50 áreas distintas de ventas. Para la solución se
permite un tiempo de cómputo máximo de 15 minutos
19/02/2020 4
 4. Planeación de la generación eléctrica.
Consiste en realizar una programación que puede ser por horas para un
día o una semana con el fin de determinar que generadores estarán
activos y en que niveles en cada hora. Se deben satisfacer restricciones
como la capacidad de los generadores activos para que la tasa de
producción de energía no sea excesiva y se satisfaga la demanda cada
hora, con alguna reserva para atender picos inesperados en la demanda .
Los generadores tienen mínimos tiempos de encendido y de apagado y
su costo de arranque depende de funciones no lineales del tiempo que
han estado inactivos.

5. Telecomunicaciones.

Un ejemplo de aplicación típico consiste en determinar que

instalaciones nuevas construir con el fin de cubrir una demanda
predicha de trasmisión de voz y datos entre instalaciones, teniendo
en cuenta que la instalación de capacidad sólo se da en cantidades
discretas y que se debe estar en capacidad de responder a fallas en
las líneas entre centros.

19/02/2020 5
 6. Manejo en Tierra de Aeronaves (Ground Holding of Aircrafts)
Dados diferentes aeropuertos, una lista de vuelos, y la capacidad de cada
aeropuerto en cada periodo, la función de las condiciones del clima y
predicciones, el problema es decidir cuales planes retrasar y por cuanto tiempo,
teniendo en cuenta el numero de pasajeros, los vuelos en conexión, el tiempo
esperado hasta condiciones de mejora, entre otras, con el objetivo de minimizar
los costos del Avión y los inconvenientes del pasajero.

7. Problemas de Corte
Ya sean cortes de longitudes de papel de rollos, plástico de hojas largas
rectangulares, o patrones para hacer ropa, el problema esta en cada caso para
seguir determinadas reglas de corte, satisfacer la demanda, y minimizar el
desperdicio.

19/02/2020 6
 1.1. Que es programación entera?
Suponga que se tiene un problema de programación lineal.

𝒎𝒂𝒙 𝑐𝑥: 𝐴𝑥 ≤ 𝑏, 𝑥 ≥ 0
Donde:
A es una matriz m*n.
b un vector columna m-dimensional
c un vector fila n-dimensional.
x Un vector columna n-dimensional de variables desconocidas.
Casos

• Si algunas pero no todas las variables son enteras entonces se tiene:

(Lineal) Programación entera mixta.
max 𝑐𝑥 + ℎ𝑦
MIP 𝐴𝑥 + 𝐺𝑦 ≤ 𝑏
x>=0, y>=0, y ϵ Z.

19/02/2020 7
 Donde:
A es m*n. h es un vector fila 1*p ,
G es m*p. y es un vector columna p*1
c es un vector fila 1*n x es un vector columna n*1

El problema tiene n variables continuas y p variables enteras.

• Si todas las variables son enteras entonces se tiene:

Programación entera.
max 𝑐𝑥
𝐴𝑥 ≤ 𝑏
IP
𝑥 ≥0𝑥 ∈𝑍

• Si todas las variables son restringidas a los valores 0-1 se tiene:

(0-1) o Programación Binaria.
max 𝑐𝑥
BIP 𝐴𝑥 ≤ 𝑏
𝑥 ∈ 0,1 𝑛

19/02/2020 8
 Problema combinatorio de optimización

En este tipo de problema se tiene un conjunto finito 𝑁 = 1, … 𝑛 Para

cada elemento j de N se tiene un peso 𝑐𝑗 ∀ 𝑗ϵ𝑁. Se tiene también un
conjunto 𝐹compuesto de subconjuntos factibles de N.
El objetivo es encontrar un subconjunto S 𝒅𝒆 𝑵 cuyo peso sea el
mínimo.

min 𝑆⊂𝑁 ෍ 𝑐𝑗 : 𝑆ϵ𝐹

𝑗 ϵ𝑆

19/02/2020 9
 Problema del Agente Viajero para 4 Ciudades

Sea el conjunto N De N se pueden obtener muchos subconjuntos

N= (1-1), (1-2),(1-3),(1-4) posibles.
(2-1), (2-2),(2-3),(2-4)
(3-1), (3-2),(3-3),(3-4) El numero de subconjuntos posibles (contando
(4-1), (4-2),(4-3),(4-4) a N y ∅) es =𝟐𝟏𝟔 = 𝟔𝟓𝟓𝟑𝟔

Para el Problema, los Tours factibles son los siguientes:

1 2 3 4 1 ES decir F: Subconjuntos de Tours factibles
1 2 4 3 1 (1-2) (2-3) (3-4) (4-1)
1 3 2 4 1 (1-2) (2-4) (4-3) (3-1)
1 3 4 2 1 (1-3) (3-2) (2-4) (4-1)
1 4 2 3 1 (1-3) (3-4) (4-2) (2-1)
1 4 3 2 1 (1-4) (4-2) (2-3) (3-1)
(1-4) (4-3) (3-2) (2-1)

No Factibles (1-2)
(1-2) (2-3)
(1-2) (2-3) (3-1) (4,4)
(1-2) (2-1) (3,4) (4,1)
 Problema Resourse Constrained Project Scheduling Problem (RCPSP)
Se tienen 30 actividades 𝑖=1,…,30,
𝑇𝑖 : Tiempo de inicio de cada actividad.
σ, 𝑇𝑖 = 100
Sea el conjunto N conformado por las parejas 𝑖 actividad-Tiempo de inicio (𝒊, 𝑻𝒊 )

En total se tienen 3000 elementos del Conjunto N

Las soluciones factibles para este Problema deben:

• Respetar precedencias.
• respetar recursos.
• Tener un elemento de N par cada actividad (que todas las actividades sean
Programadas)

Ejemplo1.1. El problema del Redondeo

Dado que los problema de I.P. son similares a los L.P. la teoría de L.P. es
fundamental para resolver problema de I.P.

Para resolver problemas de I.P. el redondeo puede no ser suficiente como en

el siguiente ejemplo.
Ejemplo 1.1. max 1.00𝑥1 + 0.64𝑥2
50𝑥1 + 31𝑥2 ≤ 250
3𝑥1 − 2𝑥2 ≥ −4
𝑥1, 𝑥2 ≥ 0 𝑥1, 𝑥2ϵ Z
6

4
3𝑥1 − 2𝑥2 = −4
3
50𝑥1 + 31𝑥2 = 250
FO: z=3.28 2

1
1.00𝑥1 + 0.64𝑥2 = 1
0
0 1 2 3 4 5 6

Observe que la solución obtenida del problema relajado (quitando la restricción de

enteros) equivale a resolver un LP cuya solución es (376/193, 950/193) = (1.95, 4.92) que
está muy alejada de la solución óptima del problema original la cual es(5,0) y que al
redondearlo da (2,5) que es no factible. Para problemas binarios la situación es peor y es
aún difícil saber si existe una solución factible.
19/02/2020 12
 1.3. Formulaciónde IPs BIPs y MIPs
PASOS PARA LA FORMULACIÓN DE MIP

1. Defina las que parecen ser las variables necesarias (es importante hacer
la distinción entre los datos y las variables).

2. Use las variables para definir un conjunto de restricciones para que los
puntos factibles correspondan a las soluciones factibles del problema.

3. Use las variables para definir la función objetivo.

4. Si hay dificultades itere (devuélvase a 1.).

ALGUNOS EJEMPLOS BÁSICOS DE FORMULACIÓN DE

PROBLEMAS IP
El problema de asignación
Hay n personas para llevar a cabo n trabajos. Cada persona se asigna para
realizar exactamente un trabajo. Hay un costos 𝑐𝑖𝑗 si la persona i es asignada al
trabajo j. Se debe encontrar el mínimo costo de asignación.

19/02/2020 13
 1. Definición de variables .

𝑥𝑖𝑗 = 1 𝑠𝑖 𝑙𝑎 𝑝𝑒𝑟𝑠𝑜𝑛𝑎 𝒊 ℎ𝑎𝑐𝑒 𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝒋, y 𝑥𝑖𝑗 =

0 𝑑𝑒 𝑜𝑡𝑟𝑎 𝑚𝑎𝑛𝑒𝑟𝑎.

2. Definición de las restricciones .

Cada persona sólo hace un trabajo.
𝑛

෍ 𝑥𝑖𝑗 = 1 𝑝𝑎𝑟𝑎 𝑖 = 1, … . . 𝑛
𝑗=1

Cada trabajo es hecho por una persona.

෍ 𝑥𝑖𝑗 = 1 𝑝𝑎𝑟𝑎 𝑗 = 1, … . . 𝑛
𝑖=1

𝑥𝑖𝑗 ϵ (0,1) ∀ 𝑖, 𝑗

19/02/2020 14
 2. Definición de la función objetivo.
El costo de la asignación es minimizado

𝑛 𝑛

min ෍. ෍ 𝑐𝑖𝑗 𝑥𝑖𝑗

𝑖=1 𝑗=1

EL PROBLEMA DE LA MOCHILA (Caso de las inversiones)

Hay un presupuesto b disponible para invertir en n proyectos bajo

consideración. Se tiene que 𝑎𝑗 es el desembolso para el proyecto j, y
𝑐𝑗 es el retorno esperado de la inversión. La idea es maximizar el
retorno sin exceder el presupuesto que se tiene.

19/02/2020 15
 EL PROBLEMA DE LA MOCHILA (Caso de las inversiones)

1. Definición de variables .

𝑥𝑗 = 1 𝑠𝑖 𝑒𝑙 𝑝𝑟𝑜𝑦𝑒𝑐𝑡𝑜 𝑗 𝑒𝑠 𝑠𝑒𝑙𝑒𝑐𝑐𝑖𝑜𝑛𝑎𝑑𝑜, 𝑦 <=b

𝑥𝑗 =0 de otra manera.

2. Definición de las restricciones.

El presupuesto no puede ser excedido
𝑛

෍ 𝑎𝑗 𝑥𝑗 <=b
𝑗=1

𝑥𝑗 ϵ (0,1) ∀ 𝑗
3. Definición de la función objetivo.
El retorno esperado es maximizado
𝑛

෍ 𝑐𝑗 𝑥𝑗
𝑗=1

19/02/2020 16
 PROBLEMA DEL CONJUNTO DE COBERTURA (THE SET COVERING
PROBLEM)

Dado cierto número de regiones, el problema es decidir donde instalar un

conjunto de depósitos. Por ejemplo si los depósitos son unidades de bomberos,
una estación puede servir a una región si un vehículo de Bomberos puede llegar a
la escena dentro de ocho minutos. El objetivo es escoger los depósitos a un
mínimo costo y que cada región sea cubierta.

Este problema se puede formular de manera más abstracta como un COP

(combinatorial optimization problem).

Sea 𝑀 = 1, … . . 𝑚 El conjunto de regiones.

𝑠𝑒𝑎 𝑁 = 1, … . . 𝑛 el conjunto de potenciales depósitos.

𝑺𝒆𝒂 𝑺𝒋 ⊆ M el conjunto de las regiones que pueden ser servidas por el depósito j.
𝑐𝑗 el costo de instalación del depósito j.
.

min ෍ 𝑐𝑗 : ∪𝑗∈𝑇 𝑆𝑗 = 𝑀
𝑇⊆ N 𝑗∈𝑇

19/02/2020 17
 Se tiene entonces que para decidir cuales son los centros de servicio a escoger
de tal manera que se cubran todas las regiones y se logre un costo mínimo, se
puede usar la siguiente ecuación que representa un COP.
.

min ෍ 𝑐𝑗 : ∪𝑗∈𝑇 𝑆𝑗 = 𝑀
𝑇 ⊆ 𝑁 𝑗∈𝑇

Se desea escoger un subconjunto T de centros de servicio (CS) de tal manera que la suma de
los costos de instalación de los CS que pertenece a T sea mínimo, y que la unión de todos los
𝑆𝑗 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑟𝑒𝑔𝑖𝑜𝑛𝑒𝑠 𝑎𝑡𝑒𝑛𝑑𝑖𝑑𝑜𝑠 𝑝𝑜𝑟 𝑒𝑙 𝑐𝑒𝑛𝑡𝑟𝑜 𝑒𝑛 𝑗 sea igual a M (Todas las regiones).
∀𝑗 ∈𝑇

Recuerde que los 𝑺𝒋 son subconjuntos de M y que cada 𝑺𝒋 representa las regiones que pueden
ser servidas por el centro j.

∪𝑗∈𝑇 𝑆𝑗 = 𝑀: 𝐸𝑠𝑡𝑜 𝑙𝑜 𝑞𝑢𝑒 𝑚𝑒 𝑑𝑖𝑐𝑒 𝑒𝑠 𝑞𝑢𝑒 𝑙𝑜𝑠 𝑑𝑒𝑝ó𝑠𝑖𝑡𝑜𝑠 𝑞𝑢𝑒 𝑠𝑒 𝑒𝑠𝑐𝑜𝑗𝑎𝑛 𝑑𝑒𝑏𝑒𝑛 𝑐𝑢𝑏𝑟𝑖𝑟 𝑒𝑙
𝑠𝑒𝑟𝑣𝑖𝑐𝑖𝑜 𝑑𝑒 𝑡𝑜𝑑𝑎𝑠 𝑙𝑎𝑠 𝑟𝑒𝑔𝑖𝑜𝑛𝑒𝑠.

Note que la anterior formulación es de la forma de un COP

19/02/2020 18
 El Set Covering Problem, también se puede formular como un BIP. A continuación se
ilustra la formulación del problema anterior como un problema de programación Binaria.
Para facilitar la descripción, considere una matriz A de incidencia de ceros y unos,
de tal manera que 𝑎𝑖𝑗 =1 si i ∈ 𝑆𝑗 (es decir si el centro j puede atender la región i
y 𝑎𝑖𝑗 =0 de otra manera.

1. Definición de variables .
𝑥𝑗 = 1 si se selecciona el depósito j; 𝑥𝑗 = 0 de otra manera
2. Definición de las restricciones.
Al menos un centro debe servir la región i
σ𝑛𝑗=1 𝑎𝑖𝑗 𝑥𝑗 ≥ 1 ∀ 𝑖 𝑥𝑗 ϵ (0,1) ∀ 𝑗

3. Definición de la función objetivo.

El costo total es minimizado
𝑛

min ෍ 𝑐𝑗 𝑥𝑗
𝑗=1

19/02/2020 19
 EL PROBLEMA DEL AGENTE VIAJERO( TSP)
Un vendedor (agente viajero) debe visitar cada una de n ciudades
exactamente una vez, y después retornar a su punto de inicio. El tiempo en
viajar de la ciudad i a la ciudad j es 𝑐𝑖𝑗 . Encuentre al orden en el que el debería
hacer su tour para finalizar lo más rápido posible. A continuación se formula
como un BIP.
1. Definición de variables .
𝑥𝑖𝑗 = 1 𝑠𝑖 𝑒𝑙 𝑎𝑔𝑒𝑛𝑡𝑒 𝑣𝑖𝑎𝑗𝑎 𝑑𝑖𝑟𝑒𝑐𝑡𝑎𝑚𝑒𝑛𝑡𝑒 𝑑𝑒 𝑙𝑎 𝑐𝑖𝑢𝑑𝑎𝑑 𝑖 𝑎𝑙 𝑎 𝑐𝑖𝑢𝑑𝑎𝑑 𝑗,
y 𝑥𝑖𝑗 = 0 𝑑𝑒 𝑜𝑡𝑟𝑎 𝑚𝑎𝑛𝑒𝑟𝑎.
𝑥𝑖𝑖 : No esta definida para i=1,……..,n.
2. Definición de las restricciones.
Sale de la ciudad i exactamente una vez

෍ 𝑥𝑖𝑗 = 1 𝑝𝑎𝑟𝑎 𝑖 = 1, … … . . 𝑛
𝑗:𝑗≠𝑖

Llega a la ciudad j exactamente una vez

෍ 𝑥𝑖𝑗 = 1 𝑝𝑎𝑟𝑎 𝑗 = 1, … … . . 𝑛
𝑖:𝑖≠𝑗

19/02/2020 20
 Subtours
2
1 3
6
5

7
8
4

Los subtours son soluciones que se pueden dar si no se ponen restricciones al

respecto para evitarlos ya que se necesita garantizar conectividad, por tanto se
debe imponer que el agente debe ir de un conjunto de ciudades a otro por
medio de restricciones de conjuntos de corte (de ciclos): cut-set constraints.
Debe salir del subtour que se está formando al menos una vez antes de que se cierre.

෍. ෍ 𝑥𝑖𝑗 ≥ 1 para S⊂N, 𝑆 ≠ ∅

𝑖∈𝑠 𝑗∉𝑠

19/02/2020 21
 La restricción anterior se puede reemplazar por la siguiente representación
(restricciones de eliminación de subtours)

෍. ෍ 𝑥𝑖𝑗 ≤ 𝑆 −1 para S⊂N, 2 ≤ 𝑆 ≤ 𝑛 − 1

𝑖∈𝑠 𝑗∈𝑠
El número de ciudades utilizadas internamente en un conjunto S de ciudades
debe ser menor que el número de ciudades 𝑆 totales del conjunto.

3. Definición de la función objetivo.

𝑛 𝑛

𝑚𝑖𝑛 ෍. ෍ 𝑐𝑖𝑗 𝑥𝑖𝑗

𝑖=1 𝑗=1

LA EXPLOSIÓN COMBINATORIA
Varios de los problemas que hemos visto son en todo sentido combinatorios
ya que la solución óptima es un subconjunto de un conjunto finito. En
principio estos problemas pueden ser resueltos por enumeración. Es decir
que se necesita contar el número de soluciones posibles.

19/02/2020 22
 El problema de asignación: Hay una correspondencia uno a uno entre las
asignaciones y permutaciones de 1, … . , 𝑛 . Por tanto hay n! soluciones.
El problema de la mochila y de cobertura: en los dos casos el número de
subconjuntos es 𝟐𝒏 .
El problema del agente viajero: Empezando de la ciudad 1, el agente
tiene n-1 elecciones por hacer. Para la siguiente ciudad hay n-2 ciudades
posibles, y así sucesivamente. Por tanto hay (n-1)! tours factibles.

La tabla 1.1 muestra algunas funciones que crecen rápidamente. Por ejemplo
el TSP con n=101 ciudades tiene aproximadamente 9,33*10^157 tours.

n log n n^0,5 n^2 2^n n!

10 3,32 3,16 10^2 1,02*10^3 3,6*10^6
100 6,64 10 10^4 1,27*10^30 9,33*10^157
1000 9,97 31,62 10^6 1,07*10^301 4,02*10^2567
Tabla 1.1

19/02/2020 23
 1.2. Formulaciones de programación
entera mixta.
Suponga que se necesita modelar una función típica no lineal de costo con carga fija.
Por ejemplo cuando se tienen que producir una cantidad de ítems x, existe un costo
fijo f de preparar las máquinas (independientemente de cuanto se produzca). Este
costo solo debe ser cargado si x>0, de lo contrario no es necesario preparar las
máquinas y el costo fijo por tanto sería cero.
h(x)=f+ px si 0<x≤Cy h(x)=0 si x=0

h(x) Para poder modelar este costo fijo se

hace uso de una variable binaria y
f+ px definida como sigue: y=1 si x>0; y=0
de otra manera. Entonces
reemplazamos h(x) por fy+px y
adicionamos las restricciones x<=Cy
f para y variable binaria.

19/02/2020 24
 Localización de instalaciones con capacidad ilimitada.
Uncapacitated Facility Location (UFL)

Dado un conjunto de depósitos potenciales 𝑁 = 1, … . , 𝑛 , y un conjunto M=

1, … . , 𝑚 de clientes, se tiene un costo fijo 𝑓𝑗 asociado con el uso del depósito j y
un costo de transporte 𝑐𝑖𝑗 si toda la orden del cliente se entrega desde el depósito j.
El problema es decidir que depósitos abrir y cuales sirven a cada cliente para
minimizar el costo total.
1. Definición de variables .
𝒚𝒋 = 1 𝑠𝑖 𝑠𝑒 𝑎𝑏𝑟𝑒 𝑒𝑙 𝑑𝑒𝑝𝑜𝑠𝑖𝑡𝑜 𝑗, 𝑦𝑗 = 0, 𝑑𝑒 𝑜𝑡𝑟𝑎 𝑚𝑎𝑛𝑒𝑟𝑎.
𝒙𝒊𝒋 𝑒𝑠 𝑙𝑎 𝑓𝑟𝑎𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑙𝑎 𝑑𝑒𝑚𝑎𝑛𝑑𝑎 𝑑𝑒𝑙 𝑐𝑙𝑖𝑒𝑛𝑡𝑒 𝑖 𝑠𝑎𝑡𝑖𝑠𝑓𝑒𝑐ℎ𝑎 𝑑𝑒𝑙 𝑑𝑒𝑝𝑜𝑠𝑖𝑡𝑜 𝑗.

2. Definición de las restricciones.

Satisfacción de la demanda del cliente i
𝑛

෍ 𝑥𝑖𝑗 = 1 𝑝𝑎𝑟𝑎 𝑖 = 1, … , 𝑚.
𝑗=1

La suma de las fracciones que atienden los depósitos para cada cliente i debe ser igual a
uno para que se satisfaga la demanda total del cliente.
19/02/2020
 Relación entre 𝑥𝑖𝑗 y 𝑦𝑗

Antes note que σ𝑖∈𝑀 𝑥𝑖𝑗 ≤ 𝑚 𝑦𝑎 𝑞𝑢𝑒𝑥𝑖𝑗 ≤ 1∀ 𝑖∀ 𝑗 .

σ𝑖∈𝑀 𝑥𝑖𝑗 ≤ 𝑚𝑦𝑗 𝑦𝑗 ∈ 0,1 para 𝑗 ∈ 𝑁

3. Definición de la función objetivo.

𝑚𝑖𝑛 σ𝑖∈𝑀. σ𝑗∈𝑁 𝑐𝑖𝑗 𝑥𝑖𝑗 +σ𝑗∈𝑁 𝑓𝑗 𝑦𝑗

19/02/2020 26
 Tamaño de Lote con capacidad de producción y almacenamiento
ilimitadas. Uncapacitated Lot Sizing (ULS)

Se quiere decidir el plan de producción para un horizonte de planeación de n

períodos para un solo producto.

Definición de datos (coeficientes) .

𝒇𝒕 Costo fijo de producir en el periodo t.
𝒑𝒕 Costo de producción por unidad en el periodo t
𝒉𝒕 Costo de almacenamiento unitario en el periodo t
𝒅𝒕 Demanda en el periodo t.

1. Definición de variables.
𝒙𝒕 Cantidad producida en el periodo t.
𝒔𝒕 Inventario al final del periodo t.
𝒚𝒕 𝑦𝑡 = 1 si se produce en t, 𝑦𝑡 = 0 de otra manera.

19/02/2020 27
 El modelo matemático (MIP) es el siguiente:

𝑛 𝑛 𝑛

𝑚𝑖𝑛 ෍ 𝑝𝑡 𝑥𝑡 + ෍ ℎ𝑡 𝑠𝑡 + ෍ 𝑓𝑡 𝑦𝑡
𝑡=1 𝑡=1 𝑡=1

𝑠𝑡−1 + 𝑥𝑡 = 𝑑𝑡 + 𝑠𝑡 para t=1,…,n. (Ecuaciones de balance de inventarios)

𝑥𝑡 ≤ 𝑀𝑦𝑡 para t=1,…,n. (Restricciones que relacionan las x con las y)

𝑠0 = 0; 𝑠𝑡 , 𝑥𝑡 ≥ 0; 𝑦𝑡 ∈ 0,1 para t=1,…,n.

Note que no existe limite superior para x; por tanto se puede usar un valor muy
grande, es decir C=M, o calcularlo con base en los datos .
Si 𝑠𝑛 = 0, entonces podemos establecer una cota superior para x como
sigue: 𝑥𝑡 ≤ σ𝑛𝑖=𝑡 𝑑𝑖 , 𝑒𝑠 𝑑𝑒𝑐𝑖𝑟 𝑀 = σ𝑛𝑖=𝑡 𝑑𝑖
Note que sumando las ecuaciones de balance desde 1 hasta t se obtiene la
ecuación: 𝑠𝑡 = σ𝑡𝑖=1 𝑥𝑖 - σ𝑡𝑖=1 𝑑𝑖 y reemplazando este valor en la función
objetivo se obtiene: 𝑚𝑖𝑛 σ𝑛𝑡=1 𝑐𝑡 𝑥𝑡 + σ𝑛𝑡=1 𝑓𝑡 𝑦𝑡 − 𝐾 𝑑𝑜𝑛𝑑𝑒:
𝑐𝑡 = 𝑝𝑡 +ℎ𝑡 +…+ ℎ𝑛 y 𝐾 = σ𝑛𝑡=1 ℎ𝑡 (σ𝑡𝑖=1 𝑑𝑡 )

19/02/2020 28
 Prueba de que 𝑲 = σ𝒏𝒕=𝟏 𝒉𝒕 (σ𝒏𝒕=𝟏 𝒅𝒕 )

σ𝑛𝑡=1( 𝑠𝑡−1 + 𝑥𝑡 − 𝑠𝑡 − 𝑑𝑡 )=0

+ 𝑠0 + 𝑥1 − 𝑠1 − 𝑑1
+ 𝑠1 + 𝑥2 − 𝑠2 − 𝑑2
+ 𝑠2 + 𝑥3 − 𝑠3 − 𝑑3
= σ𝑛=3 𝑛=3
𝑖=1 𝑥𝑖 -σ𝑖=1 𝑑𝑖 -𝑠3 = 0
𝑠𝑡 = σ𝑡𝑖=1 𝑥𝑖 - σ𝑡𝑖=1 𝑑𝑖
σ𝑛𝑡=1 𝑝𝑡 𝑥𝑡 + σ𝑛𝑡=1 ℎ𝑡 𝑠𝑡 = σ𝑛𝑡=1 𝑝𝑡 𝑥𝑡 + σ𝑛𝑡=1 ℎ𝑡 σ𝑡𝑖=1 𝑥𝑖 − σ𝒏𝒕=𝟏 𝒉𝒕 σ𝒕𝒊=𝟏 𝒅𝒊
σ𝑛𝑡=1 ℎ𝑡 σ𝑡𝑖=1 𝑥𝑖 = ℎ1 𝑥1
+ℎ2 𝑥1 + 𝑥2 𝐾
+ℎ3 (𝑥1 + 𝑥2 + 𝑥3 )
+…… ℎ𝑛 (𝑥1 + 𝑥2 + ⋯ + 𝑥𝑛 )
=𝑥1 (ℎ1 + ℎ2 + ⋯ + ℎ𝑛 ) + 𝑥2 ℎ2 + ⋯ + ℎ𝑛 + ⋯ +𝑥𝑛 ℎ𝑛

σ𝑛𝑡=1 𝑥𝑡 (𝒑𝒕 + σ𝒏𝒊=𝒕 𝒉𝒊 ) Cada 𝑥𝑡 en la FO, esta acompañada del

término: (𝒑𝒕 + σ𝒏𝒊=𝒕 𝒉𝒊 ) = 𝒑𝒕 +𝒉𝒕 +…+ 𝒉𝒏 =𝒄𝒕

19/02/2020 29
 ALTERNATIVAS DISCRETAS O DISYUNCIONES

Las disyunciones que se explican a continuación son muy útiles en problemas de

programación de tiempos (scheduling problems). Suponga que se deben procesar dos
trabajos en una misma máquina y que no pueden ser procesados al mismo tiempo.

Si se tiene que:
𝒑𝒊 : Son los tiempos de procesamiento. Para i=1,2.
𝒕𝒊 : Son los tiempos de inicio. Para i=1,2.

Entonces note que cualquiera de los trabajos puede preceder al otro, es decir
que puede ser que:
𝒕𝟐 ≥ 𝒕𝟏 + 𝒑𝟏 (𝒕𝟏 precede a 𝒕𝟐 )
O se puede dar que:
𝒕𝟏 ≥ 𝒕𝟐 + 𝒑𝟐 (𝒕𝟐 precede a 𝒕𝟏 )
Para especificar esta situación se utiliza la disyunción con la ayuda de una
variable binaria lo que se define a continuación.

19/02/2020 30
 Suponga que 𝒙 ∈ 𝑅𝑛 satisface a 0 ≤ 𝑥 ≤ 𝑢 y que 𝑎1 𝒙 ≤ 𝑏1 ó 𝑎2 𝒙 ≤ 𝑏2

𝑥2
𝑎1 𝒙 ≤ 𝑏1
Restricciones.

𝑎2 𝒙 ≤ 𝑏2

𝑥1
Introduciendo las variables binarias 𝑦𝑖 para i=1,2. Entonces si 𝑀 ≥ 𝑚𝑎𝑥 𝑎𝑖 𝒙 − 𝑏𝑖 : 0 ≤ 𝑥 ≤ 𝑢
para i=1,2, se toman las siguientes restricciones:
𝑎𝑖 𝒙 − 𝑏𝑖 ≤ M(1 − 𝑦𝑖 ) para i=1,2.
𝑦1 + 𝑦2 = 1, 𝑦𝑖 ∈ 0,1 𝑝𝑎𝑟𝑎 𝑖 = 1,2.

Si 𝒚𝟏 = 𝟏, se satisface 𝒂𝟏 𝒙 ≤ 𝒃𝟏 , mientras que ó 𝒂𝟐 𝒙 ≤ 𝒃𝟐 permanece

inactiva (como si no existiera en ese momento). Y recíprocamente si 𝒚𝟐 = 𝟏,
19/02/2020 31
Ejemplo: Dos productos se pueden hacer con base en dos tecnologías: cobre o
aluminio. Las cantidades máximas a producir son 2 unidades de c/u de los dos
productos.
Los consumos unitarios y las disponibilidades son:
cobre aluminio
Producto 1 (x1) 3 2
Producto 2 (x2) 5 3
Disponibilidad 8 4
Si se hacen en cobre se debe cumplir: 3x1+5x2 ≤ 8
Si se hacen en aluminio se debe cumplir: 2x1+3x2 ≤ 4
a1 = (3,5), a2 = (2,3), b1 = 8, b2 = 4
M≥max (3x1+5x2-8,2x1+3x2-4)=max(3*2+5*2-8,2*2+3*2-4)=max(8,6)=8 (el máximo
faltante si se produjeran las cantidades máximas).
3x1+5x2-8 ≤8(1-y1):la restricción se cumpla si y1=1 y es redundante se y1=0
2x1+3x2-4 ≤ 8(1-y2):la restricción se cumpla si y2=1 y es redundante se y2=0
Como y1+y2=1, una de las dos se cumple y la otra es redundante.

19/02/2020 32
 1.6. Formulaciones Alternativas
En esta sección se examinarán formulaciones alternativas y se tratará de entender
por qué algunas pueden ser mejores que otras. Primero es necesario precisar que
es una formulación.

Definición 1.1 Un subconjunto de 𝑅𝑛 descrito por un conjunto

finito de restricciones lineales 𝑃 = 𝑥 ∈ 𝑅𝑛 : 𝐴𝑥 ≤ 𝑏 es un
poliedro.
Definición 1.2 Un poliedro 𝑃 ⊆ 𝑅𝑛 es una formulación para un
conjunto X ⊆ 𝑍 𝑛 si y sólo si X = 𝑃⋂𝑍 𝑛 .
Si se permite que haya valores reales y enteros, la Definición 1.2 se generaliza como
sigue: Un poliedro 𝑃 ⊆ 𝑅𝑛+𝑝 es una formulación para un conjunto X ⊆ (𝑍 𝑛 ∗ 𝑅𝑝 ) si y
sólo si X = 𝑃⋂(𝑍 𝑛 ∗ 𝑅𝑝 ).

Ejemplo 1.2 en la figura 1.5, se muestran dos formulaciones para el conjunto 𝑋 =

1,1 , 2,1 , 3,1 , 1,2 , 2,2 , 3,2 , (2,3)

19/02/2020 33
 4

3
𝑷𝟐

2
𝑃1

0
0 1 2 3 4

Figura 1.5. Dos formulaciones diferentes de un IP

Formulación equivalente para el problema de la Mochila.
Considere el conjunto de puntos

𝑋= 0,0,0,0 , 1,0,0,0 , 0,1,0,0 , 0,0,1,0 , 0,0,0,1 , 0,1,0,1 , (0,0,1,1)

Observe que los siguientes tres poliedros son formulaciones para X

𝑃1 = 𝑥 ∈ 𝑅4 : 0 ≤ 𝑥 ≤ 1; 83𝑥1 + 61𝑥2 + 49𝑥3 + 20𝑥4 ≤ 100
𝑃2 = 𝑥 ∈ 𝑅4 : 0 ≤ 𝑥 ≤ 1; 4𝑥1 + 3𝑥2 + 2𝑥3 + 1𝑥4 ≤ 4
19/02/2020 34
 𝑥 ∈ 𝑅4 : 4𝑥1 + 3𝑥2 + 2𝑥3 + 1𝑥4 ≤ 4
1𝑥1 + 1𝑥2 + 1𝑥3 ≤ 1
𝑃3 =
1𝑥1 + 1𝑥4 ≤ 1
0≤𝑥≤1
Geométricamente se puede ver que pueden existir infinitas formulaciones para un
conjunto X, pero como poder escoger entre ellas?

Formulación Equivalente del Problema UFL

Para 𝑗 fija, considere las restricciones:

෍ 𝑥𝑖𝑗 ≤ 𝑚𝑦𝑗 , 𝑦𝑗 ∈ 0,1 , 0 ≤ 𝑥𝑖𝑗 ≤ 1 𝑝𝑎𝑟𝑎 𝑖 ∈ 𝑀

𝑖∈𝑀
Estas restricción se puede escribir de la siguiente manera:
𝟎 ≤ 𝒙𝒊𝒋 ≤ 𝒚𝒋 𝒑𝒂𝒓𝒂 𝒊 ∈ 𝑴, 𝒚𝒋 ∈ 𝟎, 𝟏
Lo que lleva a la formulación alternativa siguiente:
𝑚𝑖𝑛 σ𝑚 𝑛 𝑛
𝑖=1. σ𝑗=1 𝑐𝑖𝑗 𝑥𝑖𝑗 + σ𝑗=1 𝑓𝑗 𝑦𝑗
σ𝑛𝑗=1 𝑥𝑖𝑗 = 1, 𝑝𝑎𝑟𝑎 𝑖 ∈ 𝑀
𝑥𝑖𝑗 ≤ 𝑦𝑗 𝑝𝑎𝑟𝑎 𝑖 ∈ 𝑀, 𝑗 ∈ 𝑁
𝑥𝑖𝑗 ≥ 0 para i ∈ 𝑀, 𝑗 ∈ 𝑁, 𝑦𝑗 ∈ 0,1 𝑝𝑎𝑟𝑎 𝑗 ∈ 𝑁.
19/02/2020 35
 Formulación Extendida para el Problema ULS
Si se quisiera saber cuando se usan los artículos producidos
• Definición de Variables:
𝒘𝒊𝒕 : Cantidad producida en el periodo i para satisfacer la demanda del periodo t
𝒚𝒕 =1, si ocurre producción en el periodo t, y 𝒚𝒕 =0 de otra manera (igual que antes).
• Definición de Restricciones :
Satisfacción de la demanda en el periodo t
σ𝑡𝑖=1 𝑤𝑖𝑡 = 𝑑𝑡 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑡
Restricciones para la de cota superior de las variables:
𝑤𝑖𝑡 ≤ 𝑑𝑡 𝑦𝑖 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑖, 𝑡, 𝑖 ≤ 𝑡
Las variables son Mixtas
𝑤𝑖𝑡 ≥ 0𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑖, 𝑡, 𝑖 ≤ 𝑡, 𝑦𝑡 ∈ 0,1 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑡
• Definición de la función objetivo.
𝑚𝑖𝑛 σ𝑛𝑖=1. σ𝑛𝑡=1 𝑐𝑖 𝑤𝑖𝑡 + σ𝑛𝑡=1 𝑓𝑡 𝑦𝑡
Si se quiere, se pueden definir las variables viejas en términos de las variables
agregando la siguiente ecuación.
𝑛

𝑥𝑖 = ෍ 𝑤𝑖𝑡
𝑡=1
19/02/2020 36
 Pero existe una formulación definida como la formulación Ideal y se puede
demostrar que no existe ninguna otra formulación que sea mejor que la Ideal.
Observe la siguiente gráfica similar a la figura 1.5 pero ésta contiene la
formulación 3 que es la ideal.

0
0 1 2 3 4

Cuando una formulación es ideal cada punto extremo es entero así que el IP se
puede resolver como un LP. (ya que al resolver sobre un poliedro el punto óptimo
siempre va a estar en un punto extremo)
19/02/2020 37
Definición 1.3 Dado un conjunto X ⊆ Rn, el casco convexo de X denotado conv(X) se
define como:
𝑐𝑜𝑛𝑣 𝑋 = 𝑥: 𝑥 = σ𝑡𝑖=1 λ𝑖 𝑥 𝑖 , σ𝑡𝑖=1 λ𝑖 = 1, λ𝑖 ≥ 0 para i=1,……..,t. t sobre todos los
subconjuntos 𝑥 1 , … … … . , 𝑥 𝑡 de X.

Preposición1.1 conv(X) es un poliedro

19/02/2020 38
 Preposición1.2 Los puntos extremos de Conv(X) están en X

Si no estuvieran en X serían una combinación convexa y un punto extremo no

pueden ser una combinación convexa .

Así que dadas todas las formulaciones P posibles para X, la formulación ideal Conv(X)
tiene la propiedad de que X⊆Conv(X)⊆P para todas las formulaciones P. Es decir que la
mejor formulación se puede encontrar si se encuentra Conv(x) ya que está contenido
en todas las demás.

Definición 1.4 Dado un conjunto X ⊆ Rn, y dos formulaciones P1

y P2 para X, P1 es una mejor formulación que P2 si P1⊂ P2.

Es decir que si se puede demostrar que P2 no está en P1 entonces P1 es mejor

formulación que P2, y para demostrarlo se tiene que hallar un punto en P2
que no esté en P1

19/02/2020 39
 Formulaciones para el Problema UFL (Uncapacitated Facility Location)

Sea 𝑃1 la formulación dada anteriormente en las diapositivas 25 y 26, con una sola
restricción para cada j como sigue:
σ𝑖∈𝑀 𝑥𝑖𝑗 ≤ 𝑚𝑦𝑗 para cada j
y sea 𝑃2 otra formulación pero en vez de una sola restricción, con m
restricciones para cada j:
𝑥𝑖𝑗 ≤ 𝑦𝑗 𝑝𝑎𝑟𝑎 𝑖 ∈ 𝑀 para cada j

Note que si cada punto (x,y) satisface las restricciones 𝑥𝑖𝑗 ≤ 𝑦𝑗 para 𝑖 ∈ 𝑀, entonces
sumando sobre 𝑖 ∈ 𝑀 se muestra que también se satisfacen las restricciones
σ𝑖 𝑥𝑖𝑗 ≤ 𝑚𝑦𝑗 . Entonces 𝑃2 ⊆ 𝑃1 .

Para mostrar que 𝑃2 ⊂ 𝑃1 es necesario encontrar un punto en 𝑃1 que no está en 𝑃2 .

Suponga por simplicidad que n (número de depósitos) divide a m (número de
clientes), esto es 𝑚 = 𝑘𝑛 con 𝑘 ≥ 2 y entero. Entonces un punto en el cual cada
depósito sirve a 𝑘 clientes, 𝑥𝑖𝑗 = 1 para 𝑖 = 𝑘 𝑗 − 1 + 1, … , 𝑘 𝑗 − 1 + 𝑘, 𝑗 =
1, … . . 𝑛, 𝑥𝑖𝑗 = 0 de otra manera, y 𝑦𝑗 = 𝑘/𝑚 para 𝑗 = 1, … , 𝑛 esta en 𝑃1 \𝑃2 .

19/02/2020 40
 Búsqueda de un Punto en P1 que no está en P2

Ejemplo Con m=12 Clientes y n=3 depósitos, k=12/3=4

Depósitos Clientes
1 𝑥𝑖,𝑗 : 𝑥 cliente,depósito
2
1
3 𝑥1,1 = 𝑥2,1 = 𝑥3,1 = 𝑥4,1 = 1, 𝑙𝑜𝑠 𝑑𝑒𝑚á𝑠𝑥𝑘,1 = 0
4
𝑥5,2 = 𝑥6,2 = 𝑥7,2 = 𝑥8,2 = 1, 𝑙𝑜𝑠 𝑑𝑒𝑚á𝑠𝑥𝑘,2 = 0
5
6
2 𝑥9,3 = 𝑥10,3 = 𝑥11,3 = 𝑥12,3 = 1, 𝑙𝑜𝑠 𝑑𝑒𝑚á𝑠𝑥𝑘,3 = 0
7
8 1
𝑦1 = 𝑦2 = 𝑦3 =
3
9
10 Para formulación 𝑷𝟏 Para formulación 𝑷𝟐
3
11 𝑝𝑎𝑟𝑎 𝑗 = 1 (𝐷𝑒𝑝ó𝑠𝑖𝑡𝑜 1)
12 𝑝𝑎𝑟𝑎 𝑖 = 1, 𝑗 = 1
σ𝑖∈𝑀 𝑥𝑖1 ≤ 𝑚𝑦1 para cada j
𝑥𝑖𝑗 ≤ 𝑦𝑗
𝑥1,1 + 𝑥2,1 + 𝑥3,1 + 𝑥4,1 ≤ 12𝑦1
𝑥11 ≤ 𝑦1
𝟒≤
𝟏𝟐
= 𝟒 (se cumple para 𝑷𝟏 ) 𝟏
𝟑 𝟏≤ (𝒏𝒐 𝒔𝒆 𝒄𝒖𝒎𝒑𝒍𝒆 𝒑𝒂𝒓𝒂 𝑷𝟐 )
𝟑
19/02/2020 41
 Recordando las dos siguientes formulaciones,

𝑃1 = 𝑥 ∈ 𝑅4 : 0 ≤ 𝑥 ≤ 1; 83𝑥1 + 61𝑥2 + 49𝑥3 + 20𝑥4 ≤ 100

𝑃2 = 𝑥 ∈ 𝑅4 : 0 ≤ 𝑥 ≤ 1; 4𝑥1 + 3𝑥2 + 2𝑥3 + 1𝑥4 ≤ 4
a continuación se demuestra que 𝑃2 es subconjunto de 𝑃1 .
𝑃2 ⊂ 𝑃1
Sea 4𝑥1 + 3𝑥2 + 2𝑥3 + 1𝑥4 ≤ 4 Multiplicado por 25
= 100𝑥1 + 75𝑥2 + 50𝑥3 + 25𝑥4 ≤ 100
83𝑥1 ≤ 100𝑥1
61𝑥2 ≤ 75𝑥2
49𝑥3 ≤ 50𝑥3
20𝑥4 ≤ 25𝑥4
Definición 1.5. Dado un poliedro 𝑄 ⊆ 𝑅𝑛 ∗ 𝑅𝑝 , las proyecciones de 𝑄 sobre el
subespacio 𝑅𝑛 denotada 𝑃𝑟𝑜𝑦𝑥 𝑄 se define como:
𝑷𝒓𝒐𝒚𝒙 𝑸= 𝒙 ∈ 𝑹𝒏 : 𝒙, 𝒘 ∈ 𝑸 𝒑𝒂𝒓𝒂 𝒂𝒍𝒈𝒖𝒏𝒐𝒔 𝒘 ∈ 𝑹𝒑
Por tanto 𝑷𝒓𝒐𝒚𝒙 𝑸 es la Formulación de Q en el espacio 𝑅 𝑛 de las
variables x originales, y esto permite comparar Q, con otras
formulaciones P ⊆ 𝑹𝒏

19/02/2020 42
 Referencias

[1] Wolsey, Laurence A. Integer Programing, Chap-1,

[2] Nadjib Brahimi , Stephane Dauzere-Peres, Najib M. Najid & Atle Nordli. Single Item
Lot Sizing Problems, European Journal of Operational Research, 168 (2006) 1-16

19/02/2020 43