PROGRAMACION LINEAL

En los siglos XVII y XVIII, grandes matemáticos como Newton, Leibnitz, Bernouilli y, sobre todo, Lagrange, que tanto habían contribuido al desarrollo del cálculo infinitesimal, se ocuparon de obtener máximos y mínimos condicionados de determinadas funciones.

Posteriormente el matemático francés Jean Baptiste-Joseph Fourier (1768-1830) fue el primero en intuir, aunque de forma imprecisa, los métodos de lo que actualmente llamamos programación lineal y la potencialidad que de ellos se deriva.

En 1941-1942 se formula por primera vez el problema de transporte, estudiado independientemente por Koopmans y Kantarovitch, razón por la cual se suele conocer con el nombre de problema de Koopmans-Kantarovitch. Tres años más tarde, G. Stigler plantea otro problema particular conocido con el nombre de régimen alimenticio optimal.

Mucha gente sitúa el desarrollo de la programación lineal entre los avances científicos más importantes de la mitad del siglo XX, y debemos estar de acuerdo con esta afirmación si tenemos en cuenta que su impacto desde 1950 ha sido extraordinario. Se han escrito decenas de libros de texto sobre la materia y los artículos publicados que describen aplicaciones importantes se cuentan ahora por cientos. De hecho, una proporción importante de todo el cálculo científico que se lleva a cabo en computadoras se dedica al uso de la programación lineal y a técnicas íntimamente relacionadas. (Esta proporción se estimó en un 25%, en un estudio de la IBM).

Un modelo de programación lineal proporciona un método eficiente para determinar una decisión óptima, (o una estrategia óptima o un plan óptimo) escogida de un gran número de decisiones posibles.

En todos los problemas de Programación Lineal, el objetivo es la maximación o minimización de alguna cantidad.

METODOS DE SOLUCION DE PROBLEMAS DE PROGRAMACION LINEAL

Existen tres métodos de solución de problemas de programación lineal:

• Método gráfico o de las rectas de nivel. Las rectas de nivel dan los puntos del plano en los que la función objetivo toma el mismo valor.

• Método analítico o de los vértices. El siguiente resultado, denominado teorema fundamental de la programación lineal, nos permite conocer otro método de solucionar un programa con dos variables: “En un programa lineal con dos variables, si existe una solución única que optimice la función objetivo, ésta se encuentra en un punto extremo (vértice) de la región factible acotada, nunca en el interior de dicha región. Si la función objetivo toma el mismo valor óptimo en dos vértices, también toma idéntico valor en los puntos del segmento que determinan. En el caso de que la región factible no es acotada, la función lineal objetivo no alcanza necesariamente un valor óptimo concreto, pero, si lo hace, éste se encuentra en uno de los vértices de la región”

• Esquema práctico. Los problemas de programación lineal pueden presentarse en la forma estándar, dando la función objetivo y las restricciones, o bien plantearlos mediante un enunciado.

TIPOS DE SOLUCIONES

Los programas lineales con dos variables suelen clasificarse atendiendo al tipo de solución que presentan. Éstos pueden ser:

• FACTIBLES. Si existe el conjunto de soluciones o valores que satisfacen las restricciones. Estas a su vez pueden ser: con solución única, con solución múltiple (si existe más de una solución) y con solución no acotada (cuando no existe límite para la función objetivo).

• NO FACTIBLES. Cuando no existe el conjunto de soluciones que cumplen las restricciones, es decir, cuando las restricciones son inconsistentes.

CONSTRUCCION DE LOS MODELOS DE PROGRAMACION LINEAL

De forma obligatoria se deben cumplir los siguientes requerimientos para construir un modelo de Programación Lineal:

• Función objetivo. (FO): Debe haber un objetivo (o meta o blanco) que la optimización desea alcanzar.

• Restricciones y decisiones: Debe haber cursos o alternativas de acción o decisiones, uno de los cuáles permite alcanzar el objetivo.

• La FO y las restricciones son lineales. Deben utilizarse solamente ecuaciones lineales o desigualdades lineales.

Modelo standard de Programación Lineal

Optimizar Z = C1X1+ C1X2 +….+ Cn Xn). Función objetivo.

Sujeta a a11X1+ a11X2 +…..+ a1nXn) £ b1

a21X1+ a21X2 +…..+ a2nXn) £ b1

Restricciones

am1X1+ am1X2 +…..+ amnXn) £ bm

Debiendo ser

X1 ³ 0, X2 ³ 0, ….. Xn ³ 0

Donde :

Xj : variables de decisión, j = 1,2.., n.

n : número de variables.

m : número de restricciones.

aij , bi , cj constantes, i = 1,2.., m.

Pasos para la construcción del modelo

BIBLIOGRAFIA

• http://thales.cica.es/rd/Recursos/rd98/Matematicas/29/matematicas-29.html

• Hiller F. Y G. Lieberman “Introducción a la investigación de operaciones”. McGraw Hill (5ª edición).

• www.monografias.com/trabajos6/proli/proli.shtml