geografia

Temas 3 y 4
Introducci´on a la Programaci´on Lineal. M´etodo
SIMPLEX
Mar´ıa del Carmen Juan Mart´ınez
Universitat de Val`
encia

Resoluci´
on de problemas de optimizaci´
on lineales
Condici´
on necesaria y suficiente de Kuhn-Tucker para problemas lineales
Consideremos un problema de optimizaci´
on lineal. Entonces x¯ es un punto de
Khun-Tucker de dicho problema si y solamente si x¯es o
´ptimo (global).
Conclusi´
on
Para resolver un problema de optimizaci´
on lineal basta con encontrar un punto
de Kuhn-Tucker de dicho problema. Sin embargo, encontrar un punto de K-T
supone resolver las condiciones de K-T, y ello no es sencillo. Ahora bien, en PL
no vamos a resolver las condiciones, sino que vamos a utilizar otro tipo de
puntos que u
´nicamente aparecen en PL.Resoluci´
on de problemas de optimizaci´
on lineales
En 1947 el matem´
atico estadounidense George Dantzig di´
o a conocer su famoso
algoritmo para la resoluci´
on de problemas de PL: el algoritmo del Simplex. En el
dise˜
no de dicho algoritmo un nuevo tipo de puntos juegan un papel crucial. Son las
denominadas Soluciones Factibles B´
asicas.

Teorema fundamental de la PL
Cualquierproblema de PL que tenga soluci´
on o
´ptima, tiene una SFB que es
soluci´
on o
´ptima.

Conclusiones
Si conocemos todas las SFBs
de un PL, entonces la que nos
proporcione el mejor valor de la
funci´
on objetivo es la soluci´
on
o
´ptima.
Si conocemos una SFB y
resulta ser un punto de KT,
entonces es la soluci´
on o
´ptima.

Soluciones Factibles B´asicas
Variables de holguraSi la restricci´
on i de un problema de PL es de tipo ≤, entonces la
convertimos en una restricci´
on de igualdad a˜
nadiendo una nueva variable
sumando, a la que denotaremos si y denominaremos variable de holgura
de la restricci´
on i, junto con la condici´
on de signo si ≥ 0.
Si la restricci´
on i de un problema de PL es de tipo ≥, entonces la
convertimos en una restricci´
on deigualdad a˜
nadiendo una nueva variable
restando, a la que denotaremos si y denominaremos variable de holgura
de la restricci´
on i, junto con la condici´
on de signo si ≥ 0.
Si la restricci´
on i de un problema de PL es de igualdad, entonces no
precisa de variable de holgura.
Ejemplo
Max.
s.a

3x1 + x2
x1 ≥ 3
x1 + x2 ≤ 4
2x1 − x2 = 3
x1 , x2 ≥ 0

Max.
s.a

3x1 + x2
x1 − s1 =3
x1 + x2 + s2 = 4
2x1 − x2 = 3
x1 , x2 , s1 , s2 ≥ 0

Soluciones Factibles B´
asicas

Definici´
on
Un problema de PL con todas las variables no negativas y todas las
restricciones de igualdad (a˜
nadiendo variables de holgura si es necesario) se
dice que est´
a escrito en forma est´
andar.

Definici´
on
Consideremos un problema de PL en forma est´
andard. Supongamos quetenemos un total de n variables (incluyendo las variables de holgura) y m
restricciones independientes. Entonces elegimos n − m variables y las igualamos
a 0. Denominaremos a estas variables variables no b´
asicas. A las restantes m
variables las denominaremos variables b´
asicas.
Una Soluci´
on F´
actible B´
asica (SFB) es un punto f´
actible del problema en el
que n − m variables son nob´
asicas y m variables son b´
asicas. Al conjunto de
variables b´
asicas se le denomina base de la SFB.

Soluciones Factibles B´
asicas

Metodolog´ıa de obtenci´
on de las SFB de un PL
Escribimos el problema en forma est´
andard. Entonces obtenemos el total
de variables n y el total de restricciones m. Comprobamos la independencia
de las restricciones si fuera necesario.

Elegimosuna combinaci´
on de n − m variables para que sean no b´
asicas.
Igualamos estas variables no b´
asicas a 0.
Sustituimos los 0 en el sistema formado por las restricciones.
Resolvemos el sistema:
Si el sistema es infactible, descartamos la combinaci´
on elegida de
variables no b´
asicas.
Si el sistema es factible pero en la soluci´
on obtenida alguna variable
toma un valor negativo,...