Programacion Enter

ULPGC
INVESTIGACIÓN OPERATIVA
CURSO 2003-2004

PROGRAMACIÓN ENTERA
Hillier y Lieberman , cap.13

Introducción
l Programación

lineal (método del
simplex) variables continuas
l Programación entera: restricción
adicional: variables han de ser enteras
Caso particular: programación entera binaria
(0/1)

Programación entera mixta: algunas
variables han de ser enteras, otras no

1

Como formularproblemas de PEB
l Alternativas

mutuamente excluyentes

X1+X2=1
l X1+X2<=1
l

l Decisiones
l

contingentes

X3-X1<=0

Como formular problemas de PEB (2)
Uso de variables binarias auxiliares
l Restricciones

de una u otra

3X1+2X2<=18+yM
l X1+4X2<=16+(1-y)M
l M muy grande
l

l Deben

cumplirse K de M restricciones
l Funcones con N valores posibles

2

Como formular problemas de PEB (3)
Problema decargo fijo

l Ver

Hillier y Lieberman cap 13

Como formular problemas de PEB (4)
Reescribiendo variables enteras como funciones lineales de
variables binarias
l
l

Una variable X tiene la restricción 0<=X<=u
donde 2 N-1 Cada valor factible de X se puede expresar
de forma única como la suma de N+1
variables binarias auxiliares y
N

X = ∑ 2 i yi
i=0

l

Donde las y son variables binariasauxiliares

3

Resolución de problemas de
programación entera
l Enumeración

exhaustiva
l Relajación lineal (LP relaxation)
l Branch and bound (Ramificar y acotar)
l Método de los planos de corte (Gomory)

Enumeración exhaustiva
No es viable, debido a que las soluciones crecen
de forma exponencial
PEB n variables: 2n posibles soluciones

4

Relajación lineal (I)
Consiste en resolver el mismo problemasin las
condiciones de variables enteras
Si el óptimo cumple las condiciones de las variables
enteras, entonces es óptimo del problema entero
5
4

Politopo entero:
Todos los ptos extremos
son enteros

3
2
1
0
0

1

2

3

4

5

Branch and bound
Método de enumeración implícita:
divide en problemas menores: ramificación
y descarta algunos de ellos: acotación
A veces puede usarse como heurístico, sino se
exploran todos los nodos. Si se exploran todos sí se
garantiza el óptimo.
Puede aplicarse tanto a PEB como a PEM

5

Ejemplo 1
l Ver

Hillier y Lieberman, 13.4

Algoritmo Branch & Bound
0. Resolver el problema lineal relajado asociado
- si la solución es entera: solución óptima
- si no es entera, ir al paso 1. Inicializar la cota
1. Ramificación: Crear dos subproblemas ramificando unavariable
(en 0-1 o en x≤K y x≥K)
2. Acotación: Para cada subproblema, determinar una cota (superior
o inferior) para la función objetivo
3. Sondeo: Se deja de desarrollar una rama si:
- la solución es entera. En ese caso, y si la f.obj. es mejor que
la cota actual, se guarda como nueva cota
- la función objetivo es peor que la cota
- la solución es no factible
4. Si se ha llegado al final de todas lasramas, parar y escoger como
óptima la solución con mejor función objetivo.

6

Variantes del algoritmo
Para la ramificación:
- escoger el último nodo generado (fácil reoptimizar)
- escoger el nodo más prometedor (mejor cota)

Planos de corte
Se llama plano de corte a toda restricción válida
deducida de las restricciones lineales
Se trata de que todas las soluciones enteras lo
verifiquen, pero queaísle las soluciones obtenidas por
relajación lineal, hasta llegar a una solución entera
El algoritmo converge pero es bastante lento
Algoritmo de plano secante de Gomory

7

Corte fraccional de Gomory
Sea una variable xk no entera. Su fila del Simplex será:

xk = xk − ∑ ykj x j
j∈N

Y fk y fjk son las partes fraccionales de xk e ykj
Entonces, el plano de corte correspondiente es:

f k − ∑ fk jx j ≤ 0
j ∈N

y la variable de holgura será entera

ULPGC
INVESTIGACIÓN OPERATIVA
CURSO 2002-2003
MEDIDAS DE EFICIENCIA MEDIANTE
MODELOS DEA
Aplicaciones prácticas de los
métodos de programación entera

8

Productividad y eficiencia
l
l
l

Productividad=outputs/inputs
Eficiencia: compara valores observados con
valores óptimos (de outputs o inputs)
? Productividad=f(? eficiencia, tecnología,...

Leer documento completo

Regístrate para leer el documento completo.