Dualidad Intranet

Tema 2:
Optimización lineal
JOHN ZAMORA CORDOVA
UTP

Sumario
 El

modelo de programación lineal
 Formulación de modelos
 Método gráfico
 Método del simplex



Casos anómalos
Método de las dos fases

 Dualidad

El modelo de
programación lineal

Introducción






Definición: Se dice que una función f: RnR es lineal sii
para algún conjunto de constantes {c1,c2,...,cn} se tiene
que:
f x1 , x 2 ,..., x n  c1 x1  c2 x 2  ...  cn x n
Ejemplos: f(x,y)=x–2y es lineal, pero f(x,y)=x2+2y no es
lineal.
Definición: Sea f: RnR una función lineal, y bR una
constante. Entonces se dice que las desigualdades
f(x1,...,xn)b, f(x1,...,xn)b, son desigualdades lineales, y
que la igualdad f(x1,...,xn)=b es una igualdad lineal. En
general nos referiremos a las tres con el nombre derestricciones lineales

Concepto de problema de
programación lineal


Definición: Un problema de programación lineal es
un problema de optimización en el que:





Se debe maximizar (o minimizar) una función lineal de las
variables de decisión que se llama función objetivo
Los valores de las variables deben satisfacer un conjunto
de restricciones lineales

Frecuentemente nos encontraremos que en elproblema de programación lineal aparecen también
restricciones de signo para las variables, del tipo
xi0. En realidad estas restricciones son un tipo de
restricciones lineales.

Forma general de un problema
de programación lineal


La forma más general de un problema de programación
lineal será:

Maximizar (o minimizar) c1 x1  ...  cn x n
Sujeto a :
a11 x1  ...  a1n x n ~ b1
...
am1 x1 ...  amn x n ~ bm
x1 ,..., xn 0 (que pueden aparecer o no)

donde el símbolo ~ puede denotar a ,  o =.

Forma matricial


A los coeficientes de la función objetivo (ci) se les llama
costes. A los términos independientes de las
restricciones (bi), recursos. A los elementos de la matriz
de coeficientes que define las restricciones (aij),
coeficientes técnicos. Para simplificar la notación, sillamamos c al vector de costes, b al vector de recursos,
y A a la matriz de coeficientes técnicos, podemos
escribir el problema en la llamada forma matricial:
Maximizar (o minimizar) cT x

Sujeto a :
Ax ~ b
x 0 (puede aparecer o no)

Región factible




Mientras no se indique lo contrario, consideraremos que
las restricciones del tipo xi0 se incluyen (si aparecen en
el problema) dentro delconjunto de restricciones Ax ~ b,
con lo cual el problema quedaría:

Maximizar (o minimizar) c T x
Sujeto a Ax ~ b
Definición: Dado un problema de programación lineal,
llamaremos región factible del problema y la
denotaremos por S al conjunto de puntos que cumplen
todas las restricciones del problema, es decir:
S {x  R n | Ax ~ b}

Soluciones óptimas




Definición: Dado un problema deprogramación lineal,
diremos que un punto x0S es una solución óptima sii se
cumple que f(x0)f(x) xS (para el caso de minimizar)
o bien f(x0)f(x) xS (para el caso de maximizar). En
tal caso, a f(x0) se le llamará valor óptimo de la función
objetivo.
Si existe una sola solución óptima, diremos que el
problema tiene solución única. Si no existe solución
óptima, pero S, diremos que el problema tienesolución ilimitada. Si S=, diremos que el problema no
tiene solución.

Formulación de
modelos

Introducción
 Cuando

se desea resolver un problema del
mundo real, se formula en primer lugar un
modelo
 Un modelo es una simplificación de la
realidad que se intenta que sea lo
suficientemente exacta como para poder
extraer de él conclusiones útiles
 En particular nos interesan los modeloscuantitativos, en los que la realidad es
modelada mediante números

Modelos cuantitativos


En los modelos cuantitativos para problemas de
optimización intervienen:





Variables de decisión, cuyos valores numéricos
finales nos proporcionan la solución
La función objetivo, que es una cantidad que se
desea maximizar (beneficio, rendimiento, etc.) o
minimizar (coste, tiempo,...). En el caso de...