Ingeniero

Formulaci´n del problema de Programaci´n Entera o o

T´cnica de Ramificaci´n y acotaci´n e o o

PEM

Programaci´n Entera o
C´sar Asensio, Luis M. Esteban y Antonio R. Laliena e

Departamentode Matem´tica Aplicada (EUPLA) a

Asensio, Esteban & Laliena (E.U.P.L.A.)

Programaci´n Entera o

Formulaci´n del problema de Programaci´n Entera o o

T´cnica de Ramificaci´n y acotaci´n e oo

PEM

´ Indice

1

Formulaci´n del problema de Programaci´n Entera o o

2

T´cnica de Ramificaci´n y acotaci´n e o o

3

PEM

Asensio, Esteban & Laliena (E.U.P.L.A.)Programaci´n Entera o

Formulaci´n del problema de Programaci´n Entera o o

T´cnica de Ramificaci´n y acotaci´n e o o

PEM

Programaci´n entera y programaci´n entera mixta o o

Ciertos problemasrequieren que los valores de las variables de decisi´n sean enteras. o Ejemplos: Asignar personas o m´quinas a una cierta actividad, a decidir si una instalaci´n se debe localizar en un lugar o no, hacero una inversi´n o no hacerla. o Si la funci´n objetivo es lineal, las restricciones lineales y las o variables enteras tenemos un problema de Programaci´n entera PE o Si no todas las variables sonenteras el problema es de programaci´n entera mixta PEM o

Asensio, Esteban & Laliena (E.U.P.L.A.)

Programaci´n Entera o

Formulaci´n del problema de Programaci´n Entera o o

T´cnica deRamificaci´n y acotaci´n e o o

PEM

Formulaci´n de un programa con variables binarias o
Un ejemplo tipo es el de una empresa que esta planeando ampliar su producci´n, de modo que esta considerandoabrir una nueva instalaci´n o o en la ciudad A o B, donde adem´s se plantea la construcci´n de a lo a o sumo un almac´n en la ciudad de la instalaci´n. e o Para resolver este problema son necesarias lasvariables de decisi´n del o tipo: 1 si la decisi´n es positiva o xi = i = 1, 2, 3, 4 0 si la decisi´n es negativa o donde x1 se refiere a la construcci´n o no de la instalaci´n en A, x2 a la o o...