DESARROLLO:
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 de origen 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. 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.
TIPOS DE MODELOS DE INVESTIGACION:
Un modelo matemático consta al menos de tres elementos o condiciones básicas: Las Variables de decisión, la Función Objetivo y las Restricciones.
Las variables de decisión son incógnitas que deben ser determinadas a partir de la solución del modelo. Los parámetros representan
los valoresconocidos del sistema o que se pueden controlar. Las variables de decisión se representan por:
X1, X2, X3,…, Xn ó Xi, i = 1, 2, 3,…, n.
La función objetivo es una relación matemática entre las variables de decisión, parámetros y una magnitud que representa el objetivo o producto del sistema. Es la
medición de la efectividad del Modelo formulado en función de las variables. Determina lo que se va optimizar (Maximizar o Minimizar).
La solución ÓPTIMA se obtiene cuando el
valor de la Función Objetivo es óptimo (valor máximo o mínimo), para un conjunto de
valores factibles de las variables. Es decir, hay que reemplazar las variables obtenidas
X1, X2, X3,…, Xn; en la Función Objetivo Z =
f (
C1X1, C2X2, C3X3,…, CnXn) sujeto a las restricciones del modelo matemático.
Por ejemplo,
si el objetivo es minimizar los costos de operación, la función objetivo debe expresar la relación entre el
costo y las variables de decisión, siendo el resultado el menor costo de las
soluciones factibles obtenidas.
Las restricciones son relaciones entre las variables de decisión y los
recursos disponibles. Las restricciones del modelo limitan el valor de las variables de decisión. Se generan cuando los recursos disponibles son limitados.
En el Modelo se incluye, adicionalmente de las restricciones, la Restricción de No Negatividad de las Variables de decisión, o sea: Xi = 0.
Por ejemplo, si una de las variables de decisión representa el número de empleados de un taller, el valor de esa variable no puede ser negativo. O también, si una de las variables es la cantidad de mesas a fabricar, su valor solamente podrá ser igual a cero ó mayor que cero, o sea positivo; sería absurdo obtener como resultado que se va a fabricar – 4 mesas.
La
programación lineal es la interrelación de los componentes de un sistema, en términos
matemáticos, ya sea en forma de
ecuaciones o inecuaciones lineales llamado
Modelo de Programación Lineal. Es una técnica utilizada para desarrollar
modelos matemáticos, diseñada para optimizar el uso de los recursos limitados en
una empresa u
organización.
PROBLEMAS CON METODO GRAFICO:
El método gráfico se emplea para resolver problemas que presentan sólo 2 variables de decisión. El procedimiento consiste en trazar las ecuaciones de las restricciones en un eje de coordenadas X1, X2 para tratar de identificar el área de soluciones factibles (soluciones que cumplen con todas las restricciones).
La solución óptima del problema se encuentra en uno de los vértices de esta área de soluciones creada, por lo que se buscará en estos datos el valor mínimo o máximo del problema.
EJEMPLO 1:
Una compañía de auditores se especializa en preparar liquidaciones y auditorías de empresas pequeñas. Tienen interés en saber cuantas auditorías y liquidaciones pueden realizar mensualmente para maximizar sus ingresos. Se dispone de 800 horas de trabajo directo y 320 horas para revisión. Una auditoría en promedio requiere de 40 horas de trabajo directo y 10 horas de revisión, además aporta un ingreso de 300 dls. Una liquidación de impuesto requiere de 8 horas de trabajo directo y de 5 horas de revisión, produce un ingreso de 100 dls. El máximo de liquidaciones mensuales disponibles es de 60.
OBJETIVO : Maximizar el ingreso total.
VARIABLE DE DECISION: Cantidad de auditorías (X1).
Cantidad de liquidaciones (X2).
RESTRICCIONES : Tiempo disponible de trabajo directo
Tiempo disponible de revisión
Número máximo de liquidaciones.
Maximizar 
Sujeto a:
La solución óptima siempre se encuentra en uno de los vértices del conjunto de soluciones factibles. Se analizan estos valores en la función objetivo. El vértice que representa el mejor valor de la función objetivo será la solución óptima.
PROBLEMAS POR EL METODO SIMPLEX:
El Método Simplex publicado por George Dantzig en 1947 consiste en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación Lineal en caso de existir esta última.
La primera implementación computacional del Método Simplex es el ano 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.
El Método Simplex hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar.
APLICACIONES DE LA PROGRAMACIÓN LINEAL:
Problema de Inversión: Considere que usted dispone de un capital de 21.000 dólares para invertir en la bolsa de valores. Un amigo le recomienda 2 acciones que en el último tiempo han estado al alza: Acción A y Acción B. La Acción A tiene una rentabilidad del 10% anual y la Acción B del 8% anual. Su amigo le aconseja tener una cartera equilibrada y diversa y por tanto le recomienda invertir un máximo de 13.000 dólares en la Acción A y como mínimo 6.000 dólares en la Acción B. Además la inversión en la Acción A debe ser menor o igual que el doble de la inversión destinada a la Acción B. Usted quiere formular y resolver un modelo de Programación Lineal que permita obtener la política de inversión que permita obtener la máxima rentabilidad (interés) anual.
Variables de Decisión:
x = dólares invertidos en Acción A.
y = dólares invertidos en Acción B.
Función Objetivo: Se busca maximizar la rentabilidad anual que resulta de invertir en los 2 tipos de acciones.
Maximizar 0.1x + 0.08y
Restricciones: Considera las recomendaciones de su amigo.
| x + y ≤ 21.000 | Se puede invertir como máximo 21.000 dólares en total |
| x ≤ 13.000 | Invertir como máximo 13.000 dólares en Acción A |
| y ≥ 6.000 | Invertir como mínimo 6.000 dólares en Acción B |
| x - 2y ≤ 0 | Inversión en A debe ser menor o igual que el doble de la inversión en B |
| x≥0, y≥0 | No Negatividad |
Sólución Óptima: X = 13.000 Y = 8.000. Valor Óptimo V(P) = 1.940 dólares. Se recomienda verificar estos resultados a través de la
resolución gráfica y/o utilizando
Solver de Excel.
Problema de Proceso Productivo: Una empresa produce tres tipos de muebles (A, B y C), cada uno de los cuales se vende a $200, $150 y $120 respectivamente. Para la producción de estos muebles la empresa cuenta con 315 horas disponibles en un taller de corte de madera, 110 horas disponibles en un taller de lijado y 50 horas en un taller de pintado. Se ha estimado que el mueble A requiere por unidad 15 horas de trabajo en el taller de corte, 2 horas en el taller de lijado y 1 hora en el taller de pintado (estos mismos valores para los muebles B y C son 7,5:3:1 y 5:2:1, respectivamente). Se requiere formular y resolver un modelo de Programación Lineal que permita encontrar la cantidad a elaborar y vender de estos muebles de modo que la empresa obtenga el mayor beneficio.
Variables de Decisión:
X = Unidades a elaborar y vender del mueble A.
Y = Unidades a elaborar y vender del mueble B.
Z = Unidades a elaborar y vender del mueble C.
De esta forma el modelo de optimización que permite encontrar el plan óptimo de producción es el siguiente:
Este es el modelo utilizado para ejemplificar el uso de
Solver de Excel en donde se pueden encontrar los resultados.
Problema de Mezcla de Productos: Se dispone de 2 ingredientes para fabricar caramelos, cuyo sabor variará dependiendo de la proporción en que intervengan cada uno de los ingredientes. El primer ingrediente se compra a $10 por kg. y el segundo a $20 por kg. El proceso de elaboración supone un costo de $5 por kg. fabricado, cuya cantidad total corresponde simplemente a la suma de los kg. empleados en la mezcla. La demanda máxima para un mes se cifra en 100 kg y el precio de venta $50 kg. A la empresa no le interesa producir más de los que puede vender en el mes. Por último, la composición de la masa debe contener una proporción que no supere el 50% del primer ingrediente y el 80% del segundo ingrediente. Se requiere determinar cuántos kg. de caramelos se tiene que fabricar al mes y las proporciones en las que deben ser utilizados los ingredientes para obtener un máximo beneficio.
Variables de Decisión:
X1: Kg a usar del ingrediente 1 en un mes
X2: Kg a usar del ingrediente 2 en un mes
Función Objetivo: Obtener la maxima utilidad de la venta de los caramelos descontando los costos de producción
Maximizar 50*(X1 + X2) – 10*X1 – 20*X2 - 5*(X1 + X2) = 35*X1 + 25*X2
Restricciones:
Demanda Máxima: X1 + X2 <= 100
Composición: X1/(X1 + X2) <= 50% o 0,5*X1 – 0,5*X2 <= 0
Composición: X2/(X1 + X2) <= 80% o -0,8*X1 + 0,2*X2 <= 0
No Negatividad: X1,X2>=0
Sólución Óptima: X1 = 50 X2 = 50. Valor Óptimo V(P) = $3.000.
