Program

Tema 5 Programaci´n Entera o
5.1 El problema de Programaci´n Lineal Entera o

Los P.P.E (Problemas de Programaci´n Entera) son problemas de optimizaci´n o o en los que algunas o todas las variables de decisi´n se restringen a que unicamente o ´ tomen un conjunto de valores discretos. Problema: Regi´n factible generalmente no es convexa. Simplex estaba fundao mentado geom´tricamente enconjuntos convexos. e En general, la soluci´n de problemas enteros es mucho m´s complicada que o a la programaci´n lineal continua. o Los tres problemas de estructura entera son:

Problema Entero (PE) Opt Z = cT x s.a. Ax ≤ b x ≥ 0 y enteras.

Problema Entero Mixto (PEM) Opt Z = cT x + dT y s.a. Ax+By ≤ b x≥0 y ≥ 0 y enteras. 1

2 Problema Cero-Uno o Problema Binario Opt Z = cT x s.a. Ax ≤ b x = 0´ 1. o

Programaci´n Entera o

5.1.1

Formulaci´n de Problemas de Programaci´n Lineal o o Entera

Distribuci´n de un presupuesto o Suponemos que una empresa se encuentra ante la disyuntiva de elegir entre qu´ inversiones realizar. Sea e n m cj ai,j el n´mero de inversiones disponibles. u el n´mero de etapas en las que se realiza la inversi´n. u o el beneficio de la j−´sima inversi´n. e o elcoste de la inversi´n j−´sima en el periodo de tiempo i−´simo. o e e

bi capital disponible para realizar inversiones en el periodo de tiempo i−´simo. e ¿Qu´ inversiones debe realizar la empresa si desea maximizar los beneficios e obtenidos? Las variables son cualitativas, por tanto, tenemos que cuantificarlas.   1 Si elijo la inversi´n 1 o =  0 Si no elijo la inversion 1   1 Si elijo lainversi´n 2 o =  0 Si no elijo la inversion 2

x1

x2 ...

5.1 El problema de Programaci´n Lineal Entera o

3

xi

  1 Si elijo la inversi´n i o =  0 Si no elijo la inversion i

El problema queda:

Max s.a.

Z = c1 x1 + c2 x2 + . . . + cn xn a1,1 x1 + a1,2 x2 + . . . + a1,n xn ≤ b1 a2,1 x1 + a2,2 x2 + . . . + a2,n xn ≤ b2 . . . am,1 x1 + am,2 x2 + . . . + am,n xn ≤ bm xi ∈ {0,1}, i = 1, ...n.

Problema de la mochila Este problema se plantea como la situaci´n con la que se encuentra un excuro sionista que debe elegir entre varios objetos para transportar en su mochila de forma que la mochila no debe exceder de un peso (P) determinado, y el objetivo consiste en maximizar el valor de la mochila, es decir, de los objetos que elige. Tenemos: n pj Vj objetos, peso delobjeto j, valor del objeto j.   1 Si elijo el objeto i =  0 Si no elijo el objeto i

xi

El problema queda planteado de la siguiente forma:

4

Programaci´n Entera o

Max s.a.

Z = v 1 x1 + v 2 x2 + . . . + v n xn p 1 x1 + p 2 x2 + . . . + p n xn ≤ P xi ∈ {0, 1}, i = 1, ...n.

Problema del costo fijo Un determinado producto se puede fabricar en n m´quinas. Cada m´quina, a a mj , (j =1, . . . n), tiene un coste fijo kj siempre que dicha m´quina se utilice en a la fabricaci´n de una cantidad xj > 0 del producto dado. Adem´s cada m´quina o a a tiene un costo variable de cj unidades monetarias por cada unidad producida. La producci´n de la m´quina j−´sima en el periodo de tiempo considerado est´ limio a e a tada por bj . Se trata de determinar la cantidad producida por cada m´quinapara a satisfacer la demanda D de dicho producto en el periodo de tiempo considerado con costo m´ ınimo. 1o Determinar la funci´n objetivo. o xj Cantidad producida por la m´quina j, a   0 Si x = 0 j c(xj ) =  1 Si x > 0 j Por tanto, el objetivo ser´ M inZ = ıa
n j=1

C(xj ). Tal cual no lo sabemos

minimizar pues es una funci´n por partes. Estamos ante el tipo de P.P.E. transo formado.Introducimos las siguientes variables enteras,   0 Si x = 0 j =  1 Si x > 0. j

yj

El problema quedar´ planteado como: ıa

5.2 M´todos de resoluci´n e o

5

Max s.a.

Z=

n j=1 cj xj

+

n j=1

kj yj

n j=1

xj ≥ D

0 ≤ xj ≤ bj yj xi ∈ Z+ , i = 1, ...n.

5.2
5.2.1

M´todos de resoluci´n e o
Redondear hacia los enteros m´s pr´ximos a o

Inconvenientes •...