HISTORIA DE LA PROGRAMACION LINEAL (investigacion de operaciones)

El problema de la resolución de un sistema lineal de inecuaciones se remonta, al menos, a Joseph Fourier, después de quien nace el método de eliminación de Fourier-Motzkin. La programación lineal se plantea como un modelo matemático desarrollado durante la Segunda Guerra Mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas industrias lo usaron en su planificación diaria.

Los fundadores de la técnica son George Dantzig, quien publicó el algoritmo simplex, en 1947, John von Neumann, que desarrolló la teoría de la dualidad en el mismo año, y Leonid Kantoróvich, un matemático ruso, que utiliza técnicas similares en la economía antes de Dantzig y ganó el premio Nobel en economía en 1975. En 1979, otro matemático ruso, Leonid Khachiyan, diseñó el llamado Algoritmo del elipsoide, a través del cual demostró que el problema de la programación lineal es resoluble de manera eficiente, es decir, en tiempo polinomial.2 Más tarde, en 1984, Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal, lo que constituiría un enorme avance en los principios teóricos y prácticos en el área.

El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70 personas a 70 puestos de trabajo es un ejemplo de la utilidad de la programación lineal. La potencia de computación necesaria para examinar todas las permutaciones a fin de seleccionar la mejor asignación es inmensa (factorial de 70, 70!) ; el número de posibles configuraciones excede al número de partículas en el universo. Sin embargo, toma sólo un momento encontrar la solución óptima mediante el planteamiento del problema como una programación lineal y la aplicación del algoritmo simplex. La teoría de la programación lineal reduce drásticamente el número de posibles soluciones factibles que deben ser revisadas.

QUE ES LA PROGRAMACION 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ón estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.

TERMINOS CLAVES

TÉRMINOS CLAVE
Modelo Matemático
Representación de un problema donde el objetivo y todas las condiciones de restricción se describen con expresiones matemáticas.
Restricciones de no negatividad
Conjunto de restricciones que requiere que todas las variables sean no negativas.
Solución Factible
Solución que satisface simultáneamente todas las restricciones.
Región Factible
Conjunto de todas las soluciones factibles.
Variable de holgura
Variable agregada al lado izquierdo de una restricción de "menos o igual que" para convertir la restricción en una igualdad. El valor de esta variable comúnmente puede interpretarse como la cantidad de recurso no usado.
Forma Estándar
Programación lineal en el que todas las restricciones están escritas como igualdades. La solución óptima de la forma estándar de un programa lineal es la misma que la solución óptima de la formulación original del programa lineal.
Punto Extremo
Desde el punto de vista gráfico, los puntos extremos son los puntos de solución factible que ocurren en los vértices o "esquinas" de la región factible. Con problemas de dos variables, los puntos extremos están determinados por la intersección de las líneas de restricción.
Variable de Excedente
Variable restada del lado izquierdo de una restricción de "mayor o igual que" para convertir dicha restricción en una igualdad. Generalmente el valor de esta variable puede interpretarse como la cantidad por encima de algún nivel mínimo requerido.

DESARROLLO

Desarrollo
Contrucción de los Modelos de Programación Lineal
De forma obligatoria se deben cumplir los siguientes requerimientos para construir un modelo de Programación Lineal.
Requerimiento 1. Función objetivo. (F.O).
Debe haber un objetivo (o meta o blanco) que la optimización desea alcanzar.
Requerimiento 2. Restricciones y decisiones.
Debe haber cursos o alternativas de acción o decisiones, uno de los cuáles permite alcanzar el objetivo.
Requerimiento 3. La F.O 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 Definir las variables de decisión.
Definir el objetivo o meta en términos de las variables de decisión.
Definir las restricciones.
Restringir todas las variables para que sean no negativas.

METODOS DE SOLUCIÓN

Métodos de solución
El método simplex es un procedimiento iterativo que permite tender progresivamente hacia la solución óptima. Es un procedimiento sistemático y eficiente para encontrar y probar soluciones situadas en los vértices de optimalidad.
El método requiere que las restricciones sean ecuaciones en lugar de inecuaciones, lo cual se logra añadiendo variables de holgura a cada inecuación del modelo, variables que nunca pueden ser negativas y tienen coeficiente 0 en la función objetivo. Para el modelo formulado anteriormente tenemos:
Z – 6X1 – 4X2 = 0
2X1 + 2X2 + s1 = 160
X1 + 2X2 + s2 = 120
4X1 + 2X2 + s3 = 280
Todas las variables son no negativas.
acontinuacion un video sobre programacion lineal

ASPECTOS FUNDAMENTALES DEL METODO SIMPLEX

Aspectos Fundamentales Del Método Simplex
Encuentra una solución óptima
Es un método de cambio de bases
Requiere que la función objetivo sea expresada de tal forma que cada variable básica tenga como coeficiente 0 Requiere que cada variable básica aparezca en una y solamente una ecuación de restricción.
Dualidad
Asociado a cada problema de Programación Lineal existe un llamado dual, de hecho al de Programación Lineal se le llama primal. La forma general del problema dual es la siguiente: Optimizar Z = b1Y1+ b1Y2 +….+ bn Yn). Función objetivo.
Sujeta a a11Y1+ a11Y2 +…..+ am1Y1) £ C1 a21Y1+ a22Y2 +…..+ am2Y2) £ C1
. Restricciones
a1mY1+ a2mY2 +…..+ amnYm) £ Cn
Para facilitar la comprensión de lo anterior considérese el diagrama siguiente:

El problema dual tiene las siguientes características:
El el objetivo de la optimización es contrario al del primal.
Las inecuaciones de restricción son inversas.
La solución del dual es la misma que la del primal.
Desde el punto de vista económico, el significado de las variables duales es de gran interés para los gerentes, ya que representan el valor por unidad de recurso adicional, lo cuál permite tomar decisiones sobre donde invertir para incrementar las utilidades.
Análisis de Sensibilidad
El objetivo del análisis de sensibilidad es determinar la influencia de ciertos valores en la solución óptima, que nos permite la interpretación razonable de los resultados obtenidos. En muchos casos la información lograda por la aplicación del análisis de sensibilidad puede ser más importante y más informativa que simple resultado obtenido en la solución óptima.
El análisis deviene del resultado de los cambios en:
Los coeficientes en la función objetivo.
Los términos independientes en las restricciones.

Ejercicios Propuestos

EJERCICIOS PROPUESTOS
1- Una empresa se dedica a la producción de pinturas para interiores y exteriores para su distribución al mayor. Se utilizan dos materiales básicos, A y B, para producir las pinturas. La disponibilidad máxima de A es de 6 toneladas diarias; la de B es de 8 toneladas por día. La necesidad diaria de materia prima por tonelada de pintura para interiores y exteriores se resumen en la tabla que sigue: Toneladas de MP por Disponibilidad
tonelada de pintura máxima en toneladas
Exterior Interior
Materia prima A 1 2 6
Materia prima B 2 1 8
El estudio de mercado ha establecido que la demanda diaria de pintura para interiores no puede ser mayor que la pintura para exteriores en más de una tonelada. Así mismo, el estudio señala que la demanda máxima de pintura para interiores está limitada a dos toneladas diarias. La ganancia por tonelada es de $3000 para la pintura de exteriores y $2000 para la pintura de interiores. Cuánta pintura para exteriores e interiores debe producir la empresa todos los días para maximizar el ingreso bruto?

2- A una empresa se le ha planteado la tarea de cumplir un contrato de explotación de dos productos A y B para el próximo semestre. El contrato estipula que deben ser entregados como mínimo 2000 unidades de ambos productos, siendo al menos 800 de B. Los precios de venta son de 50 y 80 pesos por unidad para A y B respectivamente. La empresa cuenta con 3 establecimientos que pueden acometer esa tarea disponiendo los mismos de 550, 800 y 930 horas de tiempo productivo en el semestre respectivamente. El tiempo de producción que toma cada producto, en horas, para cada establecimiento, así como el costo por hora de producción de cada uno, se dan en la tabla siguiente: Productos
Establecimientos A B Costo/hora(pesos/h)
1 0,9 1,3 25
2 1,2 - 20
3 1,0 1,5 22
Para balancear el uso de la fuerza laboral, se desea por la empresa que el % de capacidad productiva utilizada en los tres establecimientos sea la misma. Por otra parte para el terminado de los productos se utiliza una materia prima de importación de las que disponen 3000 unidades, siendo la norma unitaria de consumo de una unidad para A y 2 para B. Plantee el modelo matemático que permita conocer la forma más provechosa de cumplir el contrato.

programacion lineal