MODELO DE PROGRAMACION ENTERA Y BINARIA

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  lo´gicas.

Este tipo de modelos permite representar sistemas mucho m´as complejos. A  cambio,  la resoluci´on  de los mismos  se complica  excesivamente.  No se

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. Introducci´on

2. Algunos  modelos  b´asicos  y  Modelizaci´on  con vari- ables  binarias

a)  El problema  del transporte

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  parti- ci´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).

m´ın   ctx

Ax  ≤ b x ≥ 0[pic 2]

xi entera para i ∈ I ⊆ {1, . . . , n}

X  Si I = {1, . . . , n} ⇒  Programaci´on  Lineal Entera Pura.

X  Si I = {1, . . . , n} ⇒  Programaci´on  Lineal Entera Mixta.

X  Si xi ∈ {0, 1}, ∀ i ∈ I ⇒  Programaci´on  Binaria  o 0–1.

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

Directos:  las  variables  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.)

Una empresa de autom´oviles dispone de tres 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 las factor´ı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?

[pic 3]

Modelo: problema  del transporte en el que  la mercanc´ıa  que debe ser

transportada es un bien  indivisible

minimizar

3      2

X X (10dij )xij

donde

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

x         = 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

ij

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[pic 4]

con cada uno de los proyectos.

Estimaci´on  de la probabilidad  de que no le concedan  cada uno de los[pic 5]

proyectos[pic 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

Variables  de decisi´on:[pic 7]

1,    si  se solicita  el proyecto  i,

xi =

0,    si  no se soliciota  el proyecto  i.

i = 1, 2, 3, 4, 5

Restricciones:[pic 8]

• L´ımite  presupuestario:

x1  + x2  + x3  + x4  + x5  ≤ 3

• Suma de las  probabilidades  de rechazo no exceda 1.5

0,4x1 + 0,7x2 + 0,4x3 + 0,5x4 + 0,6x5 ≤ 1,5

• Condici´on  de variables  binarias:

xi ∈ {0, 1}, i = 1, 2, 3, 4, 5

Objetivo:  maximizar  el beneficio esperado[pic 9]

90x1 + 150x2 + 80x3 + 100x4 + 120x5

¿C´omo  cambiar´ıas  el modelo  anterior  si  se hubiera  pedido  que la probabilidad  de no obtener  ning´un  proyecto  fuese, a lo sumo, del 10 %?

...