Programacion linial

Programaci´n Lineal1
o

Prof. Jorge Amaya A.2
Abril de 2007

.

1

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Contents
1 Introducci´n y Ejemplos
o

3

1.1

Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2

Formas can´nicas de un programa lineal . . . . . . . . . . . . . . . . . . . .
o

8

2 Soluci´n de un Problema de Programaci´n Lineal
o
o
2

15

2.1

Motivaci´n: soluci´n gr´fica en IR
o
o
a

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

15

2.2

Algoritmo Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.2.1

Fase II del Algoritmo Simplex . . . . . . . . . . . . . . . . . . . . . .

16

2.2.2

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

22

3 Introducci´na la Dualidad en Programaci´n Lineal
o
o

27

3.1

Definici´n de dualidad y principales propiedades . . . . . . . . . . . . . . . .
o

29

3.2

Interpretaci´n econ´mica de la dualidad . . . . . . . . . . . . . . . . . . . .
o
o

33

3.3

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

3.4

Ejercicios de dualidad . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . .

35

3.5

Algoritmo Simplex-dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

4 Introducci´n al An´lisis Post-optimal (An´lisis de Sensibilidad)
o
a
a

38

4.1

Variaci´n en los coeficientes de la funci´n objetivo . . . . . . . . . . . . . . .
o
o

38

4.2

Variaci´n en el vector de recursos (lado derecho) . . . . .. . . . . . . . . . .
o

41

4.3

Introducci´n de una actividad (o variable) . . . . . . . . . . . . . . . . . . .
o

42

4.4

Introducci´n de una nueva restricci´n . . . . . . . . . . . . . . . . . . . . . .
o
o

44

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 ocriterio 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. La matriz 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 esacotado, 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 y solamente 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) es infactible 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...