programacion

Programaci´n Lineal III. An´lisis
o
a
Post-Optimal
P.M. Mateo y David Lahoz
27 de mayo de 2009
En este tema se estudia al an´lisis post-optimal, ¿qu´ ocurre en un problea
e
ma de programaci´n lineal que ya hemos resuelto si realizamos un cambio en
o
alguno de los elementos que lo definen?. Cambios en el costo de una variable,
en el valor de un recurso, incorporaci´n de variables y/orestricciones, etc.
o
El tema se divide en dos partes diferenciadas el an´lisis de sensibilidad en el
a
que se realizan cambios discretos, Por ejemplo, un valor de un costo por otro,
o un coeficiente de la matriz de coeficientes tecnol´gicos por otro, o se quita
o
una variable o se a˜ade una restricci´n, etc. La segunda parte corresponde
n
o
a lo que se conoce como an´lisis par´metrico eneste caso se desea conocer
a
a
la soluci´n del problema cuando la definici´n de uno o m´s par´metros del
o
o
a
a
problema dependen de una forma lineal de un par´metro. Mas detalladaa
mente los elementos del tema son; modificaci´n discreta del vector de costos,
o
modificaci´n discreta del vector de recursos. Luego se muestra como a˜adir
o
n
variables y restricciones. A continuaci´n semuestra como realizar modificao
ciones discretas de la matriz A y finalmente se muestra como resolver los
problemas de parametrizaci´n del vector de costos y del vector de recursos.
o

1

Prog. Lineal

Dualidad

A. Post-optimal

Prog. Entera

´
Indice
1. Introducci´n
o

3

2. An´lisis de sensibilidad I
a
2.1. Modificaci´n en el vector de costos . . . . . . . . . . . . . . . . . .. . .
o
2.2. Modificaci´n en el vector de recursos . . . . . . . . . . . . . . . . . . . .
o

3
5
10

3. Incorporaci´n de variables y restricciones
o
12
3.1. Incorporaci´n de variables . . . . . . . . . . . . . . . . . . . . . . . . . . 12
o
3.2. Incorporaci´n de restricciones . . . . . . . . . . . . . . . . . . . . . . . . 13
o
4. An´lisis de sensibilidad II. Modificaci´n de lamatriz A
a
o

15

5. An´lisis param´trico
a
e
18
5.1. Parametrizaci´n en el vector de costos . . . . . . . . . . . . . . . . . . . 18
o
5.2. Parametrizaci´n en el vector de recursos . . . . . . . . . . . . . . . . . . 21
o

2

Prog. Lineal

1.

Dualidad

A. Post-optimal

Prog. Entera

Introducci´n
o

En todos los modelos de programaci´n lineal los coeficientes de lafunci´n objetivo y
o
o
las restricciones se dan como datos de entrada o como par´metros fijos del modelo. En
a
los problemas reales los valores de estos coeficientes no est´n, en general, perfectamente
a
fijados, debido a que la mayor´ de ellos dependen de par´metros no controlables, por
ıa
a
ejemplo, futuras demandas, coste de materias primas, costo de energ´ etc. y no pueden
ıa,
ser predichascon exactitud antes de que el problema sea resuelto. Tambi´n puede sucee
der que aunque conozcamos los par´metros exactamente estemos interesados en estudiar
a
c´mo var´ la soluci´n ´ptima si cambiamos alg´n par´metro intencionadamente, a efeco
ıa
o o
u
a
tos de tratamiento, ambas situaciones se resuelven de forma an´loga.
a
Cada variaci´n en los valores de los datos del problemagenerar´ un nuevo problema
o
a
de programaci´n lineal. El an´lisis de sensibilidad y el an´lisis param´trico nos proo
a
a
e
porcionar´n herramientas para el c´lculo de las soluciones ´ptimas de los problemas
a
a
o
obtenidos por la modificaci´n de los par´metros originales del problema.
o
a
En el procedimiento de resoluci´n siempre se partir´ de una soluci´n optima del probo
a
o ´
lemaoriginal, problema antes de ser modificado, y a partir de ella se calcular´n las
a
distintas soluciones asociadas a las modificaciones del problema original.

2.

An´lisis de sensibilidad I
a

Bajo este ep´
ıgrafe estudiaremos modificaciones discretas de los par´metros del proa
blema, cambio de un vector de costos/recursos por otro vector de costos/recursos. Por
ˆ
ejemplo, un vector c =...