peprogramacione

Programaci´
on Lineal Entera
Los modelos de programaci´
on entera son una extensi´
on de los modelos
lineales en los que algunas variables toman valores enteros.
Con frecuencia las variables enteras s´
olo toman valores en 0-1, ya que
este tipo de variables permiten representar condiciones l´
ogicas.
Este tipo de modelos permite representar sistemas mucho m´
as complejos.
on de los mismos secomplica excesivamente. No se
A cambio, la resoluci´
puede utilizar la suavidad de las funciones para inferir el comportamiento
de las mismas cerca del ´
optimo.
Problemas con unas solas decenas de variables pueden ser casi imposibles
de resolver.

1

Programaci´
on Entera: contenidos

1. Introducci´
on
2. Algunos modelos b´
asicos y Modelizaci´
on con variables binarias
a) El problema deltransporte
b) Problema de la mochila
c) Problema del viajante (opt. combinatoria)
d) Problema de asignaci´
on, asignaci´
on generalizada
y asignaci´
on cuadr´
atica
e) Problema del cubrimiento, empaquetado y partici´
on
f ) Problema del emparejamiento (opt. combinatoria)
g) Otros problemas
3. Resoluci´
on del problema.
a) Planos de corte
b) Ramificaci´
on y acotaci´
on (Branch and Bound).

2

Programaci´on Entera: ejemplos
m´ın ctx
Ax ≤ b
x≥0
xi entera para i ∈ I ⊆ {1, . . . , n}

Si I = {1, . . . , n} ⇒ Programaci´
on Lineal Entera Pura.
Si I = {1, . . . , n} ⇒ Programaci´
on Lineal Entera Mixta.
Si xi ∈ {0, 1}, ∀ i ∈ I ⇒ Programaci´
on Binaria o 0–1.

3

Programaci´
on Entera: ejemplos
En general, un problema de Programaci´
on Lineal Entera puede surgir por
varios motivos:

Directos: lasvariables que se utilizan son cuantitativas y enteras.
Codificados: Se utilizan variables enteras para representar el
cumplimiento o no de ciertas condiciones (normalmente son variables
0 − 1).
Transformados: Las variables enteras aparecen para facilitar la
modelizaci´
on de algunas condiciones (implicaciones, disyunciones, etc.)

4

Problemas directos: ejemplo
Una empresa de autom´
oviles dispone detres factor´ıas, A, B y C y de dos
centros de distribuci´
on, D1 y D2.
Las capacidades de producci´
on de las 3 factor´ıas durante un a˜
no son
1000, 1500 y 1200 veh´ıculos, respectivamente.
Las demandas en los centros de producci´
on son de 2300 y 1400 veh´ıculos
respectivamente.
El coste de transporte en tren es de 10 pesetas por kil´
ometro y veh´ıculo.
Si la matriz de distancias entre lasfactor´ıas y los centros de distribuci´
on
vienen dada por la siguiente tabla, ¿cu´
antos veh´ıculos deben fabricarse
en cada factor´ıa para que el transporte desde cada una de las factor´ıas a
cada uno de los centros de distribuci´
on sea m´ınimo?

A
B
C

D1
1000
1250
1275

D2
2690
1350
850
5

Problemas directos: ejemplo
Modelo: problema del transporte en el que la mercanc´ıa que debe sertransportada es un bien indivisible

3

minimizar

2

(10dij )xij
i=1 j=1

sujeto a x11 + x12 ≤ 1000
x21 + x22 ≤ 1500
x31 + x32 ≤ 1200
x11 + x21 + x31 ≥ 2300
x12 + x22 + x32 ≥ 1400
xij ∈ Z+, i = 1, 2, j = 1, 2, 3
donde
xij =

cantidad de veh´ıculos a transportar de la factor´ıa i, i = 1, 2
hasta el centro de distribuci´
on j, j = 1, 2, 3
6

Problemas codificados: ejemplo
Un ingeniero inform´
atico aut´onomo quiere optar a realizar un proyecto
inform´
atico de entre 5 que salen a concurso.
S´
olo tiene presupuesto para pagar las tasas de solicitud en 3 proyectos.
¿A qu´
e 3 proyectos optar?
Beneficio esperado (en miles de euros) que puede obtener a los 3 a˜
nos
con cada uno de los proyectos.
Estimaci´
on de la probabilidad de que no le concedan cada uno de los
proyectos
Proyecto
Beneficio (mileseuros)
Probabilidad de rechazo

1
90
0.4

2
150
0.7

3
80
0.4

4
100
0.5

5
120
0.6

Problema: qu´
e proyectos deber´ıa solicitar para obtener un beneficio mayor
y asegurarse de que la suma de las probabilidades de rechazo no sea
superior a 1.5
7

Problemas codificados: ejemplo (cont.)

Variables de decisi´
on:
xi =


1,
0,

si se solicita el proyecto i,
si no se soliciota el proyecto i.

i =...