Programacion lineal

PROGRAMACION LINEAL

La Programación Lineal es una pequeña parte de una teoría matemática que se ha consolidado en el siglo XX con el nombre de Optimización. En general, se trata de un conjunto de técnicas matemáticas que intentan obtener el mayor provecho posible de sistemas económicos, sociales, tecnológicos, etc… cuyo funcionamiento se puede describir matemáticamente de modo adecuado.
Unaterminología establecida desde los primeros tiempos de la Optimización, denominaba a la solución óptima un programa de acción a poner en práctica; de ahí que la búsqueda de un tal programa de acción utilizando métodos matemáticos se llamase Programación Matemática.
Según las características de las funciones del problema y de las variables se tienen diferentes tipos de problemas de ProgramaciónMatemática. Si todas las funciones del problema, objetivo y restricciones son lineales, se tiene un problema de Programación Lineal.

UN POCO DE HISTORIA
La Programación Lineal es una teoría matemática desarrollada en el siglo XX. Los matemáticos que han intervenido en la creación y desarrollo de la Programación Lineal han sido:
Leonid Vitalevich Kantorovitch, que en 1939 publica una monografíatitulada "Métodos matemáticos de organización y planificación de la producción".
Tjalling Charles Koopmans, que junto con el anterior estudiaron entre 1941 y 1942 el conocido ahora como problema del transporte. Ambos recibieron el premio Nobel de Economía en 1975.
George Joseph Stigler, que en 1945 planteó el problema del régimen alimenticio optimal, conocido ahora como problema de la dieta.George Bernard Dantzig, que formuló en 1947 el enunciado general al que se reduce cualquier problema de Programación Lineal y autor del método del simplex para la resolución de problemas.
John von Neumann, que en 1947 relacionó los problemas de Programación Lineal con la teoría de Matrices.

DEFINICION Y TERMINOLOGIA
Un problema de Programación Lineal consiste en optimizar (maximizar o minimizar)la función:
z = F ( x1, x2, ... ,xn ) = c1x1 + c2x2 + ... + cnxn
sujeto a:
a11x1 + a12x2 + . . . + a1nxn ≤ = ≥ b
a21x1 + a22x2 + . . . + a2nxn ≤ = ≥ b2
. . .
am1x1 + am2x2 + . . . + amnxn ≤ = ≥ bm
x1 , x2 , . . . , xn ≥ 0
A la función z = F ( x1, x2, ... ,xn ) = c1x1 + c2x2 + ... + cnxn se le denomina función objetivo o función criterio.
Los coeficientes c1, c2, ... , cn son númerosreales y se llaman coeficientes de beneficio o coeficientes de costo. Son datos de entrada del problema.
x1, x2, ... , xn son las variables de decisión (o niveles de actividad) que deben determinarse.
Las desigualdades ai1x1 + ai2x2 + . . . + ainxn ≤ bi , con i = 1, ... , m se llaman restricciones.
Los coeficientes aij , con i = 1, ... , m y j = 1, ... , n son también números reales conocidos y seles denomina coeficientes tecnológicos.
El vector del lado derecho, es decir los términos bi , con i = 1, ... , m, se llama vector de disponibilidades o requerimientos y son también datos conocidos del problema.
Las restricciones xj ≥ 0 con j = 1, ... , n se llaman restricciones de no negatividad.
Al conjunto de valores de (x1, x2, ... ,xn) que satisfacen simultáneamente todas las restriccionesse le denomina región factible. Cualquier punto dentro de la región factible representa un posible programa de acción.
La solución óptima es el punto de la región factible que hace máxima o mínima la función objetivo.
TIPOS DE PROBLEMAS DE PROGRAMACIÓN LINEAL
En un problema de Programación Lineal, según sean las restricciones, se obtendrán poliedros diferentes, acotados o no, y según sea laposición de la función objetivo respecto de dicho poliedro se pueden originar diferentes situaciones. Según el tipo de soluciones que presenten un problema de Programación Lineal puede ser:
Factible: si existe la región factible. En este caso nos podemos encontrar:
Óptimo finito y único. La solución óptima está formada por un único punto con coordenadas reales.
Múltiples óptimos. Un problema de...