Econometria Regresion gimnasio

Tema 3
Algoritmo Simplex. Dualidad.
An´lisis de Sensibilidad
a
En los temas anteriores se ha visto la formulaci´n de modelos de programaci´n lineal y su
o
o
resoluci´n gr´fica cuando tenemos dos variables de decisi´n. En este tema vamos a desao
a
o
rrollar el m´todo Simplex que se utiliza para resolver cualquier problema de programaci´n
e
o
lineal. Tambi´n se ver´ unos de losconceptos m´s importantes de la programaci´n lineal:
e
a
a
o
la dualidad. Finalmente se estudiar´ el efecto de cambios en la estructura del modelo
a
sobre la soluci´n ´ptima, es por tanto de gran importancia y recibe el nombre de an´lisis
oo
a
de sensibilidad.

3.1.

Fundamentos del Simplex

El problema fundamental de la programaci´n lineal consiste en determinar una soluci´n
o
o
paraun sistema de ecuaciones lineales simult´neas que optimice una determinada funci´n
a
o
objetivo. Tales sistemas se resuelven por el m´todo de Gauss. Para tal resoluci´n es
e
o
necesario manejar algunos conceptos.
Podemos establecer que la forma general de un problema de programaci´n general es
o
la siguiente:
Determinar el valor de un conjunto de variables, x = (x1 , x2 , . . . , xn ) ∈Rn que optimice
(maximice o minimice) una funci´n objetivo sujeta a unas restricciones, esto es,
o
Opt z = c1 x1 + c2 x2 + · · · cn xn
s.a a11 x1 + a12 x2 + · · · + a1n xn (≤, =, ≥)b1
a21 x1 + a22 x2 + · · · + a2n xn (≤, =, ≥)b2
······························
am1 x1 + am2 x2 + · · · + amn xn (≤, =, ≥)bm

37

3.1. Fundamentos del Simplex
o matricialmente el problema se expresa como
Optz = c x
s.a. Ax(≤, =, ≥)b
x≥0
siendo



a11
 a21
A=
 ···
am1

a12
a22
···
am2

···
···
···
···


a1n
a2n 
 , x = (x1 .x2 , . . . , xn ) , b = (b1 , b2 , . . . , bm ) , c = (c1 , c2 , . . . , cn )
··· 
amn

Hay dos formas especialmente importantes de presentar un problema lineal:
Forma est´ndar de un problema lineal. Se llama as´ a la presentaci´n de un
a
ıo
problema en la que:
1.
2.
3.
4.

El objetivo es de la forma maximizaci´n o minimizaci´n.
o
o
Todas las restricciones son de igualdad.
Todas las variables son no negativas.
Las constantes a la derecha de las restricciones son no negativas.

Por lo tanto, un problema de maximizar en forma est´ndar tiene la estructura
a
siguiente:
Opt z = c x
s.a. Ax = b
x≥0
donde cn×1 , xn×1, bm×1 , Am×n con n > m. Se denota Aj la j-´sima columna de A.
e
Forma can´nica de un problema lineal. Se llama as´ a la presentaci´n de un
o
ı
o
problema en la que:
1. El objetivo es de la forma maximizaci´n.
o
2. Todas las restricciones son del tipo ≤.
3. Todas las variables son no negativas.
Por lo tanto, un problema de maximizar en forma can´nica tiene la estructura
o
siguiente:M ax z = c x
s.a. Ax ≤ b
x≥0
donde cn×1 , xn×1 , bm×1 , Am×n con n > m.
38

´
Eva Ma Ramos Abalos

Tema 3. Algoritmo Simplex. Dualidad. An´lisis de Sensibilidad
a
El m´todo simplex se aplica a programas lineales en forma est´ndar. La mayor´ de
e
a
ıa
los problemas no son inicialmente modelizados en esta forma, sino que tienen muchas
restricciones de desigualdad. Por ello esnecesario dar la forma can´nica de un problema
o
lineal. Para ello se utilizar´n las transformaciones vistas en el tema 1.
a
El m´todo simplex es un algoritmo, es decir, un procedimiento sistem´tico que se ree
a
pite una y otra vez hasta obtener un resultado deseado. Cada vez que se lleva a cabo
el procedimiento sistem´tico se realiza una iteraci´n. En el procedimiento gr´fico se loa
o
acalizaban los puntos extremos de la regi´n factible, coincidiendo la soluci´n ´ptima en
o
oo
uno de esto puntos. Nuestro objetivo ahora es determinar algebraicamente estos puntos
extremos.
El primer paso ser´ pasar el problema a forma est´ndar, de esta forma, el conjunto de
a
a
restricciones se convierte en un sistema de ecuaciones simult´neas. En estas condiciones,
a
existe un equivalente a...