Programaci N Lineal

PROGRAMACIÓN LINEAL


La programación lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de un sistema de inecuaciones lineales, optimizando la función objetivo, también lineal.
Consiste en optimizar (minimizar o maximizar) una función lineal, denominada función objetivo, de tal forma que las variables de dicha funciónestén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.

APLICACIONES
La programación lineal constituye un importante campo de la optimización por varias razones, muchos problemas prácticos de la investigación de operaciones pueden plantearse como problemas de programación lineal. Algunos casos especiales de programación lineal, tales como losproblemas de flujo de redes y problemas de flujo de mercancías se consideraron en el desarrollo de las matemáticas lo suficientemente importantes como para generar por si mismos mucha investigación sobre algoritmos especializados en su solución. Una serie de algoritmos diseñados para resolver otros tipos de problemas de optimización constituyen casos particulares de la más amplia técnica de laprogramación lineal. Históricamente, las ideas de programación lineal han inspirado muchos de los conceptos centrales de la teoría de optimización tales como la dualidad, la descomposición y la importancia de la convexidad y sus generalizaciones. Del mismo modo, la programación lineal es muy usada en la microeconomía y la administración de empresas, ya sea para aumentar al máximo los ingresos o reducir almínimo los costos de un sistema de producción. Algunos ejemplos son la mezcla de alimentos, la gestión de inventarios, la cartera y la gestión de las finanzas, la asignación de recursos humanos y recursos de máquinas, la planificación de campañas de publicidad, etc.

FUNCIÓN OBJETIVO

La programación lineal consiste en optimizar (maximizar o minimizar) una función objetivo, que es una funciónlineal de varias variables:
f(x,y) = ax + by.
Ejemplo:
En una pastelería se hacen dos tipos de tartas: Vienesa y Real. Cada tarta Vienesa necesita un cuarto de relleno por cada Kg. de bizcocho y produce un beneficio de 250 Pts., mientras que una tarta Real necesita medio Kg. de relleno por cada Kg. de bizcocho y produce 400 Ptas. de beneficio. En la pastelería se pueden hacer diariamente hasta 150Kg. de bizcocho y 50 Kg. de relleno, aunque por problemas de maquinaria no pueden hacer mas de 125 tartas de cada tipo. ¿Cuántas tartas Vienesas y cuantas Reales deben vender al día para que sea máximo el beneficio?
 Solución
En primer lugar hacemos una tabla para organizar los datos:

Tipo
Nº
Bizcocho
Relleno
Beneficio
T. Vienesa
x
1.x
0,250x
250x
T. Real
y
1.y
0,500y
400y
 
 
150
50
 
 
Funciónobjetivo (hay que obtener su máximo):  f(x, y)=250x+ 400y 
Sujeta a las siguientes condiciones (restricciones del problema): 



Consideramos las rectas auxiliares a las restricciones y dibujamos la región factible:
 Para    0.25x+0.50y=50, ó  x + 2y=200
x
Y
0
100
200
0


 
Para   x + y =150
x
Y
0
150
150
0
La otras dos son paralelas a los ejes
Al eje OY    x=125
Al eje Ox      y =125
Y lasotras restricciones (x e y mayor o igual a cero) nos indican que las soluciones deben estar en el primer cuadrante
La región factible la hemos coloreado de amarillo:


Encontremos los vértices:
El  O(0,0), el  A(125, 0) y el  D(0, 100) se encuentran directamente (son las intersecciones con los ejes coordenados)
Se observa que la restricción yes redundante (es decir “sobra”)
Resolviendo el sistema:
,por reducción obtenemos y=50, x=100
Otro  vértice es el punto  C(100, 50)
Y el último  vértice que nos falta se obtiene resolviendo el sistema:
X+y=150
X=125
Cuya solución es: X=125,  Y=25  B(125, 25)
 
Los vértices de la región son O(0,0), A(125,0), B(125,25) y C(100,50) y D(0,100),
Si dibujamos el vector de  dirección de la función objetivo f(x, y)=250x+ 400y 
Haciendo 250x+ 400y =0,  ...