Programacion entera

Clase # 17

Programación entera es programación lineal con la restricción adicional de que los valores de las variables de decisión sean enteros. µ P.E pura: Todas las variables de decisión tienen valores enteros. µP.E mixta (PEM) : Algunas de las variables de decisión tienen valores enteros. Las demás cumplen con la suposición de divisibilidad.

Programación Entera.

17-1

17-2

µP.E.Binaria (PEB) : Utiliza variables binarias Sólo tiene 2 alternativas posibles 1 Xj = 0 si la decisión j es no. si la decisión j es si.

Ejemplo de formulación. La CALIFORNIA MANUFACTURING CO. , está analizando la posibilidad de expansión. Fábrica: Construcción de una fábrica en Los Angeles o en San Francisco, o tal vez en ambas ciudades Almacén: Construcción de un almacén a lo sumo, pero ladecisión está restringida a que si hay almacén en ese sitio tiene que haber fábrica.
Veamos

Las Xj son variables de decisión restringidas a tomar valores 0,1.
17-3

17-4

# de Pregunta sí o no decisión

Variable VNP Capital de requerido decisión Beneficio

Formulemos entonces el problema: 1. Variables de decisión. La variable de decisiónXj es tal que: 1 se construye. Xj = 0 no seconstruye. j= 1,2,3,4.

1 2 3 4

¿Construir fábrica en Los Angeles? ¿Construir fábrica en San Francisco? ¿Construir almacén en Los Angeles? ¿Construir almacén en San Francisco?

X1

$9 mill $6 mill

X2 $5 mill $3 mill X3 X4
$6 mill $5mill $4 mill $2mill

Capital disponible : $10 mill
17-5

17-6

1

2.Función objetivo.

3.Restricciones

X3 + X4 ≤ 1 Max Z = 9 X1 + 5 X2 + 6 X3 + 4 X4X3 ≤ X1 X4 ≤ X2
Como las variables de decisión son adimensionales, Z tiene unidades de

Alternativas mutuamente excluyente Se construye la fabrica solo si se construye el almacén Capital disponible

6X1 + 3X2 + 5X3 + 2X4 ≤ 10

[$ millones]
17-7

Xj ∈ [0,1] para j= 1,2,3,4.
17-8

El problema completo será:

Otras posibilidades de formulación. Es ocasiones es necesario utilizarvariables para expresar relaciones combinatorias dentro de la formulación de los problemas. Para esto, además de las variables originales Xj , se hace necesario el uso de variables auxiliares yi del tipo binario, introducidas en la reformulación
17-9 17-10

Max Z = 9 X1 + 5 X2 + 6 X3 + 4 X4 X3 + X4 ≤ 1 + X3 ≤0

-X1 -X2

+ X4 ≤ 0

6X1 + 3X2 + 5X3 + 2X4 ≤ 10 Xj ∈ [0,1] para j= 1,2,3,4.

1.Restricciones una u otra.
9

X2 3 X 1 + 2 X2 = 1 8

Sólo una (cualquiera de las 2) debe cumplirse, mientras que la otra puede cumplirse, pero no se requiere que lo haga. Esto tiene una aplicación práctica en los casos en que se tienen 2 tipos de recursos para un cierto propósito. P.ej : o bien 3 X1 + 2X2 ≤ 18 o

8 7 6 5 4 3 2 1

X 1 + 4X2 = 16

X1 + 4X2 ≤ 16

Veamos
17-11

X1
0 2 4 68 10 12 14 16
17-12

2

Para lograr lo enunciado anteriormente el problema se formula así:
Una de las dos 3 O una de las dos 3

2. Deben cumplirse K de N restricciones. Considere la situación en la que el modelo completo incluye un conjunto de N restricciones posibles entre las que sólo K de ellas se deben cumplir. (suponga que K < N).

X 1 + 2X 2

≤ 18 ≤
16

+ M

X 1 + 2X 2≤ 18 ≤
16 + M

X 1 + 4X 2

X 1 + 4X 2

Esto se lleva a la forma equivalente
3

X 1 + 2X 2

≤ 18 ≤

+ My

y ∈ [0,1]
17-13

Las N-K restricciones que no se eligen quedan eliminadas del problema, aun cuando por coincidencia las soluciones factibles puedan satisfacer algunas de ellas.
Veamos
17-14

X 1 + 4X 2

16 + M (1-y)

Se tienen N restricciones del tipo

La formulaciónequivalente del requerimiento de que K de estas restricciones se deban cumplir será:

f 1 ( x 1 , x 2 , ........., x n ) f 2 ( x 1 , x 2 , ........., x n )

≤ ≤

d1 d2

f 1 ( x 1 , x 2 , ........., x n ) f 2 ( x 1 , x 2 , ........., x n )

≤ ≤ ≤

d 1+ M y1 d 2 + My 2

f N ( x 1 , x 2 , ........., x n )

dN + My N
la

f N ( x 1 , x 2 , ........., x n )

≤

Σ
dN
17-15...