PE


3. 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 incluyenCostos 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:

Alternativa Inversión VPN
1 $ 5000 $ 16000
2 $ 7000 $ 22000
3 $ 4000 $ 12000
4 $ 3000 $ 8000


Sea:Xj = 1 si decide invertir en alternativa j = 1,2,3,4
= 0 si NO

Máx Z = 16 x1 + 22 x2 + 12 x3 + 8 x4
5 x1 + 7 x2 + 4 x3 + 3 x4  14

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)

Xj = 1 se incluye el artículo j en la mochila0 no se incluye

Máx Z = c1x1 + c2x2 + ... + cnxn
s.a.
x1 + x2 + .... + xn  b
3.2 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áximorendimiento.


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 recursosde manera secuencial.

Problema del Agente Viajero (TSP)
Determinar la mejor secuencia de actividades ejecutando cada actividad una sola vez.
3.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 puedenaparecer 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 sonvariables 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 tresplantas 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

a. X1 + X2 = 1

b. las posibilidades son:
X1 X2
0 0
0 1
1 0 <----- eliminar con la restricción X1  X2
1 1
c. X1 + X2 + X3  1

d. X1 + X2 + X3  2

e. Supongamos: si la planta 2 no seabre, la planta 1 no debe abrirse
X1 X2
0 0
0 1
1 0 <----- eliminar con la restricción X1  X2
1 1 entonces la condición es: X1  X2 + X3

f. Si se abre la planta 1, la planta 2 debe abrirse X2  X1
Si la planta 3 no se abre, la planta 2 debe abrirse. X2 + X3  1
entonces la condición es igual a la suma de ambas 2X2 + X3  1 + X1

VARIABLES BINARIAS Y...