Programacion entera

PROGRAMACIÓN ENTERA

* Problema lineal con restricción de integralidad para alguna variable

Aplicaciones:
* Problemas con costos iniciales, fijos y otras economías de escala
*Organización de recursos
* Programación de tareas
* Formulación para un problema (parte) especifico más efectiva

Programa entero puro
Todas las variables restringidas a tomar valores enterosMáx. z = x1 + x2
s.t10x1 - 8x2 ≤13
2x1 - 2x2 ≥ 1
X1, X2 ≥ 0; X1, X2 enteros

Programa entero mixto
Algunas variables restringidas a tomar valores enteros
Max z = x1 + x2
S, t 10x1 - 8x2 ≤ 13
2x1- 2x2 ≥1
X1, x2 ≥ 0; x1 entero

Ej. Formulación presupuesto inversiones
Encontrar el programa de inversión que maximice el VPN.
Inversión Costo Inicial

Parámetros
NPVj = Valor presente netoproyecto j = 1,…., 4.
Cj = Costo año 1 proyecto j = 1,…., 4.
Cap = Capital disponible

Variables

Añadir nuevas restricciones:

1. Máximo dos inversiones son posibles.

2. Si se invierte en2, debe invertirse en 1 también

3. Si se invierte en 2, no puede invertirse en 4

Formulación de restricciones con variables binarias
En los siguientes problemas, las variables x son continuas ylas variables z son binarias.

Del conjunto de alternativas z1; z2,…, zk seleccione cuando mucho una.

Del conjunto de alternativas z1; z2,…., zk seleccione exactamente una.

Del conjunto dealternativas z1; z2,….., zk seleccione al menos una.

Del conjunto de alternativas z1; z2,…, zk seleccione más de tres.

Variables de control
En los siguientes problemas, las variables x soncontinuas y las variables z son binarias.

Si se construye la bodega z = 1, se pueden almacenar hasta 13 toneladas de x en ella. Esto equivale a “Si z = 0, entonces x = 0, pero si z = 1, entonces x ≤13”
X≤ 13z

Si se construye la bodega z = 1, debe usarse para almacenar al menos 56 toneladas pero no más de 141 toneladas de x en ella. Esto equivale a “Si z = 0, entonces x = 0, pero si
z = 1,...