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.

...