programación entera

Modelos de Programación Entera
En muchas aplicaciones, la solución de un problema
tiene sentido solamente si una parte o todas las
decisiones toman valores restringidos a números enteros.
Un problema lineal de programación entera es de la
forma:
P) Max cTx
s.a. A x = b
x  0, xj entero (j Є Ĵ)

Modelos de Programación Entera
En este sentido los algoritmos de resolución de los modelosde Programación Entera difieren a los utilizados en los
modelos de Programación Lineal.
Algunos algoritmos de Programación Entera (PE) son:
Branch & Bound
 Branch & Cut
 Planos Cortantes
 Relajación Lagrangeana
 Etc…


i) Problema de Inversión
Una empresa está pensando invertir en cuatro
proyectos diferentes, cada proyecto se finaliza a lo más
en 3 años. Los flujos de cajarequeridos en cada año
junto con el Valor Presente Neto de cada proyecto,
concluidos los años de ejecución, y las disponibilidades
de recursos financieros se resumen en la siguiente tabla:

i) Problema de Inversión
Proy 1 Proy 2 Proy 3 Proy 4 Disp. Recursos
Año 1

10

8

6

12

30

Año 2

8

15

4

0

15

Año 3

18

0

16

0

12

V.P.N.

35

18

2416

Interesa determinar en cuáles proyectos invertir de
modo de conseguir el mayor V.P.N. de la inversión.

i) Problema de Inversión
Variables de decisión:
1, si se invierte en el proyecto i
xi  
0, sin o

con i  1,2,3,4

Función objetivo:
Max 35x1 + 18x2 + 24x3 + 16x4

i) Problema de Inversión
Restricciones (tres alternativas):
1) Reinvirtiendo el dinero no utilizado enun período:

Año1: 10x1 + 8x2 + 6x3 + 12x4 + s1 = 30
Año2: 8x1 + 15x2 + 4x3
Año3: 18x1
xi  {0,1}

+ 16x3
i = 1,2,3,4

+ s2 = 15 + s1
 12 + s2

i) Problema de Inversión
2) Sin invertir el dinero no utilizado en un período, pero
utilizando el retorno de los proyectos concluidos:
Año1: 10x1 + 8x2 + 6x3 + 12x4

 30

Año2: 8x1 + 15x2 + 4x3

 15 + 16x4

Año3: 18x1

 12 +18x2

xi  {0,1}

+ 16x3

i = 1,2,3,4

i) Problema de Inversión
3) Reinvirtiendo el dinero no utilizado en un período y,
también el retorno de proyectos concluidos:
Año1: 10x1+ 8x2+ 6x3+ 12x4+ s1 = 30
Año2: 8x1+ 15x2+ 4x3
Año3: 18x1

xi  {0,1}

+ 16x3

i = 1,2,3,4

+ s2 = 15 + s1 + 16x4
 12 + s2 + 18x2

i) Problema de Inversión
Notar que el conjunto de las solucionesfactibles es
finito. Esto ocurrirá generalmente con los problemas de
Programación Entera (puros). En el ejemplo, el número
de soluciones factibles no supera el número de las
soluciones binarias del problema (variables restringidas
sólo a valores 0 o 1) que son 24 = 16, dado el número
de variables utilizadas, de hecho las soluciones factibles
son menos de 16 pues en particular xi=1 parai=1,2,3,4 no satisface las disponibilidades de capital
en cualquiera de las tres alternativas.

i) Problema de Inversión
Supongamos que adicionalmente la inversión efectuada
requiera nuevas restricciones.
Se debe invertir en al menos 1 de los 3 primeros
proyectos:

x1 + x2 + x3  1
El proyecto 2 no puede ser tomado a menos que el
proyecto 3 si sea tomado:
x2  x3

i) Problema deInversión
Se puede tomar el proyecto 3 o 4 pero no ambos:
x3 + x4  1

No se puede invertir en más de dos proyectos:
x1 + x2 + x3 + x4  2

ii) Inclusión de Costos Fijos
Supongamos que se desea tener lotes de compra de un
producto dado, para satisfacer demandas que fluctúan en
el tiempo sobre un horizonte de planificación dividido en T
períodos.
Asumimos conocidos: una estimación de lademanda dt con t
= 1, 2, ..., T, los costos asociados a la compra de una
unidad pt, los costos asociados al mantenimiento de una
unidad en inventario de cada período ht y los costos fijos
asociados a la gestión de compra en el período t , st.
Observación: No se permite unidades faltantes (demanda
pendiente).

ii) Inclusión de Costos Fijos
Variables de decisión
xt:

número de unidades...