La Programación Lineal

La Programación Lineal es uno de los contenidos que se tratan en la materia de Matemáticas Aplicadas a las Ciencias Sociales de 2º de bachillerato. Esta entrada está dedicada a eso, a la programación lineal, y se presenta como un pequeño trabajo de ampliación realizado por los alumnos/as y que ha consistido en contestar a una serie de preguntas. Os mostramos aquí uno de ellos:

1. ¿En qué consiste la Programación Lineal?

La Programación Lineal (PL) consiste en una de las principales ramas de la Investigación Operativa, con objeto de realizar un proceso de toma de decisiones. Frecuentemente, trata del estudio de complejos sistemas reales, con la finalidad de mejorar (u optimizar) su funcionamiento.
En esta categoría se consideran todos aquellos modelos de optimización donde las funciones que lo componen, es decir, función objetivo y restricciones, son funciones lineales en las variables de decisión.

• La función f(x,y) = ax + by + c llamada función objetivo y que es necesario optimizar. En esa expresión xe y son las variables de decisión, mientras que a, b y c son constantes.
• Las restricciones que deben ser inecuaciones lineales. Su número depende del problema en cuestión. El carácter de desigualdad viene impuesto por las limitaciones, disponibilidades o necesidades, que son: inferiores a ... ; como mínimo de .... Tanto si se trata de maximizar como de minimizar, las desigualdades pueden darse en cualquiera de los dos sentidos.
• Al conjunto de valores de x e y que verifican todas y cada una de las restricciones se lo denomina conjunto (o región ) factible. Todo punto de ese conjunto puede ser solución del problema; todo punto no perteneciente a ese conjunto no puede ser solución.
• La solución óptima del problema será un par de valores (x_0, y₀) del conjunto factible que haga que f(x,y) tome el valor máximo o mínimo.

Un modelo de Programación Lineal (PL) considera que las variables de decisión tienen un comportamiento lineal, tanto en la función objetivo como restricciones del problema. En este sentido, la Programación Lineal es una de las herramientas más utilizadas debido a que por su naturaleza se facilitan los cálculos y en general permite una buena aproximación de la realidad. Los modelos de Programación Lineal por su sencillez son frecuentemente usados para abordar una gran variedad de problemas de naturaleza real en ingeniería y ciencias sociales, lo que ha permitido a empresas y organizaciones importantes beneficios y ahorros asociados a su utilización. Por ejemplo, muchas empresas mediante la Programación Lineal pueden obtener a priori los resultados o los máximos/mínimos beneficios fruto de sus factores productivos para así decidir y llevar a cabo una tarea productiva mucho más eficiente.* Al final de la presentación, podremos analizar exhaustivamente los usos de la Programación Lineal.

1. Tipos de soluciones de Programación Lineal

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

• Factible: si existe la región factible que satisface las restricciones . En este caso nos podemos encontrar:

1. Solución única. La solución óptima está formada por un único punto con coordenadas reales.
2. Con solución múltiple. Un problema de Programación Lineal puede tener más de un óptimo. Además, o bien el problema tiene un único óptimo, o bien, tiene infinitos óptimos. Hay infinitas soluciones, que corresponden a los puntos del segmento situado entre dos vértices de la región factible.
   En estos casos, como ya vimos en el capítulo anterior, la función objetivo es paralela a una de las restricciones.
3. Región factible no acotada, óptimo finito. La no acotación de la región factible no implica necesariamente óptimo infinito. Puede ocurrir que la función objetivo alcance el óptimo en la zona acotada de la región factible. 
4. Región factible no acotada, óptimo finitoe infinito. Puede darse el caso que todos los puntos de una de las semirrectas que determinan la región factible no acotada sean solución del problema5.  No factible. Región factible vacía. El conjunto de restricciones de un problema de Programación Lineal puede ser incompatible, conduciendo a una región factible vacía.  El conjunto de soluciones del sistema de desigualdades no determina ninguna región factible.Este tipo de problemas carece de solución.

1. Personas famosas que han estudiado la Programación 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 fránces 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.
Recientemente, el matemático ruso Leonodas Vitalyevich Kantarovitch publica una extensa monografía titulada “Métodos matemáticos de organización y planificación de la producción” en la que por primera vez se hace corresponder a una extensa gama de problemas una teoría matemática precisa y bien definida llamada, hoy en día, programación lineal .
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.
En 1947, G.B. Dantzig formula, en términos matemáticos muy precisos, el enunciado estándar al que cabe reducir todo problema de programación lineal.
Los fundamentos matemáticos de la programación lineal se deben al matemático norteamericano de origen húngaro Janos von Neuman(1903-1957), quien en 1928 publicó su famoso trabajo “Teoría de Juegos”. En 1947 conjetura la equivalencia de los problemas de programación lineal y la teoría de matrices desarrollada en sus trabajos. La influencia de este respetado matemático, hace que otros investigadores se interesaran paulatinamente por el desarrollo riguroso de esta disciplina.

Janos von Neuman

1. Usos de la Programación Lineal.

Después de estudiar detalladamente los conceptos básicos de Programación Lineal ubicados en un contexto de aplicaciones de la Investigación Operativa en el mundo empresarial e industrial, se hace preciso describir cómo es posible aplicar los conceptos anteriores en diferentes situaciones prácticas. Este desarrollo de situaciones del mundo real constituye el auténtico desarrollo de la programación lineal. No se tratan de meras aplicaciones, sino del campo específico natural de desarrollo de la programación lineal. Destacamos lo principales campos donde la programación lineal se hace imprescindible:

• Marketing. La Programación Lineal se utiliza en el campo del marketing y la publicidad como una herramienta que nos permite determinar cuál es la combinación más efectiva de medios para anunciar nuestros productos. En muchas ocasiones partiremos de un presupuesto para publicidad fijo y nuestro objetivo será distribuirlo entre las distintas opciones que se nos ofrecen (televisión, radio, periódicos, revistas, etc.) de forma que nuestros productos tengan la mayor difusión posible.
• Estudios de mercado.
• Producción empresarial. A menudo las técnicas de PL permiten decidir sobre la cantidad más adecuada que una empresa debe producir de cada uno de sus productos a fin maximizar los beneficios sin dejar de cumplir con unos determinados requisitos (financieros, de demanda, contractuales, de disponibilidad de materias primas, etc.).
• Planificación de la producción. El establecer un plan de producción para un período de semanas o meses resulta ser una tarea difícil e importante en la mayoría de las plantas de producción.
• Asignación de tareas en empresas. El objetivo aquí será asignar de la forma más eficiente posible un trabajo a cada empleado o máquina. Ejemplos de este tipo de asignación serían la distribución de coches patrulla por las calles de una ciudad o la destino de cada jefe de ventas a una determinada zona geográfica. El objetivo puede ser bien minimizar los tiempos o costes de desplazamiento, o bien maximizar la efectividad de las asignaciones.
• Planificación de horarios. Así pues, en nuestro propio instituto podemos ver una de las aplicaciones de la Programación Lineal.
• Logística. El llamado problema del transporte se refiere al proceso de determinar el número de bienes o mercancías que se han de transportar desde cada uno de los orígenes a cada uno de los destinos posibles.
• Mezclas. Por ejemplo, el problema de la dieta. Este problema representa una de las primeras aplicaciones de la PL, y comenzó a utilizarse en los hospitales para determinar la dieta más económica con la que alimentar a los pacientes a partir de unas especificaciones nutritivas mínimas.

CONCLUSIÓN: Con todo lo expuesto anteriormente, podemos decir que la Programación Lineal está presente en nuestros días a menudo, nos facilita las labores administrativas de una forma muy eficiente. Reflexión: Si un país subdesarrollado utilizase los métodos de la programación lineal, su producto interior bruto (PIB) aumentaría entre un 10 y un 15% en tan sólo un año. EJEMPLO PRÁCTICOEn un almacén se guarda aceite de girasol y de oliva. Para atender a los clientes se han de tener almacenados un mínimo de 20 bidones de aceite de girasol y 40 de aceite de oliva y, además, el número de bidones de aceite de oliva no debe ser inferior a la mitad del número de bidones de aceite de girasol. La capacidad total del almacén es de 150 bidones. Sabiendo que el gasto de almacenaje es el mismo para los dos tipos de aceite (1 unidad monetaria) . ¿Cuántos bidones de cada tipo habrá que almacenar para que el gasto sea máximo?

Paso 1º:Reordenar los datos del problema y a partir de las cantidades decididas, x e y, escribir el sistema de inecuaciones que determinan las restricciones. Expresar el problema en la forma estándar:

Maximizar Z= f(x,y) = x + y

Restricciones: x + y <= 150

y >= x/2

x>=0; y>=0 x >= 20 ; y>= 40

Paso 2 º: Representar gráficamente las restricciones y marcar claramente la región factible.Para las restricciones anteriores debemos representar las rectas: x + y = 150 , y = x/2 , x = 20 e y = 40, obteniéndose la región factible que en la figura se encuentra coloreada.Paso 3º: Hallar las coordenadas de los vértices del polígono obtenido.Resolviendo los sistemas : { x = 20, y = 40 } , { y = x/2 , y = 40 } , { y = x/2 , x + y = 150} , { x + y = 150, x = 20}; se obtienen los vértices: A(20,40) , B(80,40) , C(100, 50) , D(20,130)Paso 4º: Sustituir las coordenadas de esos puntos en la función objetivo y hallar el valor máximo o mínimo. Sustituyendo en f(x,y) = x + y, se tiene:f(20,40) = 60 , f(80,40) = 120 , f(100, 50) = 150 , f(20,130) = 150 Como el valor máximo se obtiene en los puntos C y D, puede optarse por cualquiera de los dos, o por cualquier punto perteneciente al segmento que los une. Así, por ejemplo, se obtendría el mismo gasto con 40 bidones de aceite girasol y 110 bidones de aceite de oliva; o 90 y 60 respectivamente. Paso 5º:También es conveniente representar las rectas de nivel para comprobar que la solución gráfica coincide con la encontrada. Esta conveniencia se convierte en necesidad cunado la región factible es no acotada. En nuestro caso, puede comprobarse que las rectas de nivel tienen la misma pendiente que la recta límite de la restricción x + y 150 ; por tanto, hay múltiples soluciones.