Programacion lineal

Programaci´n Lineal1 o

Prof. Jorge Amaya A.2
.

Abril de 2007

Este es un texto destinado exclusivamente a los alumnos del curso MA37A-OPTIMIZACION, de la Escuela de Ingenier´ de la Universidad de Chile. ıa 2 Departamento de Ingenier´ Matem´tica y Centro de Modelamiento Matem´tico, Universidad de Chile. ıa a a Se agradece enviar sus comentarios a: jamaya@dim.uchile.cl

1

Contents
1Introducci´n y Ejemplos o 1.1 1.2 Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Formas can´nicas de un programa lineal . . . . . . . . . . . . . . . . . . . . o 3 4 8 15 15 15 16 22 27 29 33 35 36 38 38 41 42 44

2 Soluci´n de un Problema de Programaci´n Lineal o o 2.1 2.2 Motivaci´n: soluci´n gr´fica en IR o o a 2.2.1 2.2.2
2

. . . . . . . . . . . . .. . . . . . . . . .

Algoritmo Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fase II del Algoritmo Simplex . . . . . . . . . . . . . . . . . . . . . . Fase I del Algoritmo Simplex: obtenci´n de una soluci´n inicial b´sica o o a factible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Introducci´n a la Dualidad en Programaci´n Lineal o o 3.13.2 3.3 3.4 3.5 Definici´n de dualidad y principales propiedades . . . . . . . . . . . . . . . . o Interpretaci´n econ´mica de la dualidad . . . . . . . . . . . . . . . . . . . . o o Ejercicios de dualidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algoritmo Simplex-dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Relaciones de dualidad (c´mo determinar el dual decualquier problema lineal) 35 o

4 Introducci´n al An´lisis Post-optimal (An´lisis de Sensibilidad) o a a 4.1 4.2 4.3 4.4 Variaci´n en los coeficientes de la funci´n objetivo . . . . . . . . . . . . . . . o o Variaci´n en el vector de recursos (lado derecho) . . . . . . . . . . . . . . . . o Introducci´n de una actividad (o variable) . . . . . . . . . . . . . . . . . . . o Introducci´n de unanueva restricci´n . . . . . . . . . . . . . . . . . . . . . . o o

2

1

Introducci´n y Ejemplos o

Un problema de programaci´n lineal se escribe de manera expl´ o ıcita como: (P L) min z = c 1 x1 + a1,1 x1 + a2,1 x1 + . . . c 2 x2 + . . . + a1,2 x2 + . . . + a2,2 x2 + . . . + . . . cn−1 xn−1 + a1,n−1 xn−1 + a2,n−1 xn−1 + . . . cn xn a1,n xn = b1 a2,n xn = b2 . . .

am,1 x1 + am,2 x2 + . .. + am,n−1 xn−1 + am,n xn = bm xi ≥ 0 ∀i o en forma compacta como: (P L) min z = cT x Ax = b x ≥0 con x, c ∈ IRn , b ∈ IRm , A ∈ Mm×n (IR), con m ≤ n. En la funci´n objetivo o criterio cT x, la variable x se conoce como variable de decisi´n o o o nivel de actividad y c como vector de costos. El conjunto de restricciones S = {Ax = b, x ≥ 0} es un poliedro cerrado y se llama conjunto factible. Lamatriz A se conoce como la matriz de coeficientes tecnol´gicos y b como o vector de recursos o, simplemente, lado derecho. Otras definiciones preliminares: o o • Si S es acotado, existe soluci´n, pues se minimiza una funci´n lineal continua sobre un conjunto compacto (cerrado y acotado). • Si S es no acotado, puede ocurrir que c t x → −∞, con x ∈ S. • Se dir´ que el problema (PL) es acotado si ysolamente si ∃x ∈ S a c t x ≤ c t x ∀x ∈ S.

• Se dir´ que el problema (PL) es no acotado si y solamente si ∃d ∈ IRn , xo ∈ S tal a t que c (xo + λd) → −∞ si λ → ∞ con xo + λd ∈ S ∀λ > 0 Es evidente que si (PL) es no acotado, entonces S es no acotado. La otra implicancia no siempre es cierta, como veremos cuando estudiemos c´mo resolver un programa lineal. o a o / • Se dir´ que el problema (PL) esinfactible si y s´lo si S = o.

3

1.1

Ejemplos

En lo que sigue, revisaremos algunos ejemplos cl´sicos de la programaci´n lineal. a o Ejemplo 1.1 Problema de transporte Consideremos una industria que tiene dos f´bricas, una en la ciudad O1 y otra en la ciudad a O2. Ella produce un bien que es consumido en D1, D2 y D3. La oferta en O1 es de 10.000 unidades diarias, mientras que la...