Programacion Entera

programacion entera´ FACULTAD DE CIENCIAS NATURALES Y MATEMATICA ´ ESCUELA PROFESIONAL DE MATEMATICA INTRODUCCION A LA PROGRAMACION ENTERA

por

ORLANDO SARMIENTO CHUMBES

´ CALLAO - PERU

2008

1

Introducci´n a la Programaci´n o o Entera
Cuando en los problemas de programaci´n lineal obligamos a algunas o todas las variables o de decisi´n que s´lo admitan valores enteros,estaremos en un problema de programaci´n o o o lineal entera. Como por ejemplo, sea

(P) : maximizar z = x1 − 3x2 − 4x3 sujeto a : 2x1 + x2 − x3 4x1 − 3x2 3x1 + 2x2 + x3 x1 , x2 , x3 x2 , x3 enteros El problema (P) restringe x2 y x3 a valores enteros no negativos, en cuanto que x1 es un real cualquiera no negativo. (P) puede tambi´n ser denominado un problema de prograe maci´n lineal mixta, pues notodas las variables son restringidas a valores enteros. o Podriamos imaginar la soluci´n de (P) ignorando la ultima restricci´n, para esto el probo ´ o lema ser´ considerado como el de un problema lineal. En el caso que la soluci´n obtenida ıa o tomara valores enteros en todas las variables de decisi´n, tendriamos resuelto el probo lema original (P). En tanto, si alguna de las variables toman valoresfraccionarios en la soluci´n del problema lineal, cuando deber´ ser enteras, la primera idea es tratar o ıan 2 ≤ ≤ ≤ ≥ 4 2 3 0

de redondear a los valores enteros mas proximos de manera que las soluciones enteras obtenidas sean viables. Infelizmente este procedimiento podr´ tomar soluciones enteras a distintas del ´ptimo. A manera de ilustraci´n consideremos el siguiente ejemplo. o o (P ) :maximizar z = x1 + 19x2 sujeto a : x1 x1 x1 + + ≥ 20x2 x2 0 x2 ≥ 0 ≤ ≤ 50 20

xj entero, j = 1, 2. Dejando de lado la restricci´n x1 , x2 enteros el problema (P ) se convertir´ : o a ¯ (P ) : maximizar z = x1 + 19x2 sujeto a : x1 x1 x1 + + ≥ 20x2 x2 0 x2 ≥ 0 ≤ ≤ 50 20

¯ (P ) es un problema de programaci´n lineal que puede ser solucionado utilizando el o m´todo del simplex. Para esto debemosaumentar las variables de holgura x3 y x4 de la e siguiente manera. ¯ (P ) : maximizar z = x1 + 19x2 sujeto a : x1 + 20x2 + x3 x1 + x2 + x4 = = 50 20

xj ≥ 0,

j = 1, 2, 3, 4.

¯ Resolveremos (P ) en la pr´xima secci´n, y al mismo tiempo, presentaremos el m´todo o o e simplex por operaciones entre columnas. 3

1.1 Esquematizaci´n del M´todo Simplex por operaciones entre columnas o e ¯ Pararesolver el problema (P ) de la secci´n anterior presentaremos, para facilitar la visi´n o o de las iteraciones del m´todo simplex, una disposici´n dados en cuadros propuestos por e o ¯ Gomory. Sin perdida de generalidad (P ) podr´ ser escrito de la siguiente forma. a ¯ (P ) : maximizar z sujeto a z = x1 x2 x3 x4 = = = = 0 − 1(−x1 ) − 19(−x2 ) 0 − 1(−x1 ) + 0 (−x2 ) 0 + 0(−x1 ) − 1 (−x2 ) 50 + 1(−x1) + 20(−x2 ) 20 + 1(−x1 ) + 1 (−x2 )

xj ≥ 0, j = 1, 2, 3, 4. Las ecuaciones arriba podran ser representados esquematicamente por el siguiente cuadro : Q1 z x1 x2 x3 x4 1 0 0 0 50 20 −x1 −1 −1 0 1 1 −x2 −19 0 −1 20 1

El cuadro de arriba denominado Q1, posee la primera linea de izquierda para derecha, su denominaci´n Q1 asociada a la columna de las variables, 1 es asociado a la columna de olos t´rminos independientes, −x1 es asociado a la columna de la forma −(1 0 − B −1 a1 ), e

4

y −x2 es asociado a la columna de la forma −(0 1 −B −1 a2 ). Las variables x1 y x2 son no b´sicas. Para x1 = x2 = 0 tenemos x3 = 50 y x4 = 20. Asi la matriz (a3 a4 ) = (e1 e2 ) es a ¯ b´sica primal viable de (P ). Sobre el cuadro Q1 pasemos aplicar los test de optimalidad a del m´todo simplex. eRetomemos el cuadro inicial Q1. Q1 z x1 x2 x3 x4 1 −x1 0 0 0 50 20 −x2

−1 −19 −1 0 1 1 0 −1 20∗ 1

donde * representa el elemento pivot, esto es, la columna asociada a la variable x2 entrar´ a a la base sustituyendo a la columna asociada a la variable x3 . Por operaciones de pivoteamiento (m´todo de eliminaci´n de Gauss - Jordan ), obtene o dremos los cuadros siguientes. Q2 z x1 x2 x3 x4 1 −x1...