9.1 PLANTEAMIENTO 9.2 RESOLUCIÓN GRÁFICA 9.3. EJEMPLOS 9.4 AUTOEVALUACIÓN




9. PROGRAMACIÓN LINEAL

    La Programación matemática es una técnica desarrollada en los últimos cincuenta años que sin usar, en principio, recursos matemáticos muy profundos ha tenido aplicaciones importantes en distintos campos de la actividad humana, desde el social y estratégico hasta la economía y los negocios. Cómo en la mayor parte de las matemáticas aplicadas, el aspecto crucial es la construcción de modelos de una situación real concreta a los que se aplica técnicas matemáticas posteriormente. El objetivo es la optimización de recursos; es decir, determinar que alternativa es mejor que las demás en una situación definida (recursos humanos, materiales, ...etc.) y en un sentido que debe precisarse (maximización de beneficios, minimización de costes, ...etc.).

    En esta introducción nos limitaremos a estudiar un modelo y un método que se llama Programación Lineal. En los problemas trataremos de optimizar (maximizar o minimizar) una función que será de dos variables. Desde el punto de vista económico los problemas tendrán como objetivo calcular los beneficios máximos, o los costes mínimos, que se encuentran sujetos a unas determinadas limitaciones, llamadas restricciones. Los conocimientos matemáticos necesarios para seguir el tema se reducen a la resolución de inecuaciones de dos variables en el plano. Se pueden repasar estos conceptos en Inecuaciones.

    La maximización de beneficios nos llevará a problemas en los que tengamos que determinar la producción: qué se debe fabricar y en qué cantidades para que se obtenga el máximo beneficio teniendo en cuenta las limitaciones técnicas y humanas. En el campo agrícola la adecuada utilización de los terrenos, los cupos de producción, ..., etc.

    En los problemas de mínimos podremos calcular los costes mínimos para alimentar a los animales de una granja condicionado a los requerimientos nutricionales. Minimización de la contaminación atmosférica, optimización de recursos humanos, ..., etc.

Ejemplos de situaciones que estudiaremos:

1- Un laboratorio farmacéutico desea elaborar un reconstituyente de manera que cada frasco contenga al menos 4 unidades de vitamina A, 23 unidades de vitamina B y 6 de vitamina C. Para suministrar estas vitaminas se emplea un aditivo M que cuesta 100 Ptas. el gramo, el cual contiene 4 unidades de vitamina A, 6 de B y 1 de C y un aditivo H a un costo de 160 Ptas. por gramo que contiene 1 unidad de vitamina A, 10 de B y 6 de C. ¿Cuántos gramos de cada aditivo se deben incluir en cada frasco para minimizar el costo?

2- Una empresa de construcción dispone de 1800 millones de Ptas. para construir dos tipos de chalets adosados, siendo el coste del tipo S de 30 y del tipo P de 20 millones. El beneficio que se obtiene por la venta de un chalet del tipo S es de 4 millones de Ptas. Y por la venta de uno del tipo P de 3 millones de Ptas. Si el ayuntamiento ha condicionado los permisos a que el número de edificaciones sea inferior a 80. ¿Cuántos chalets de cada tipo deben edificarse para que el beneficio sea máximo? ¿Qué beneficios obtendría la empresa constructora?.

9.1. Planteamiento.

    Resolver un problema de programación lineal consiste en optimizar una función lineal sujeta a unas restricciones, entendiendo por optimizar encontrar un valor máximo o mínimo según los casos (Maximizar o Minimizar la función).

 - La función lineal respecto a las variables x e y se llama función objetivo.  F(x,y) = mx+ny,  siendo m , n, dos números reales.
- Las ecuaciones o inecuaciones condicionantes se llaman restricciones.
- Las soluciones del sistema (el conjunto de los puntos del recinto plano que delimitan las rectas representativas del sistema) constituyen la región factible, que es la región donde debemos buscar la solución.

    Optimizar condicionada a las restricciones:

a1x + b1y ~ c1
a2x + b2y ~ c2
.....................
anx + bny ~ cn

(el símbolo ~, según el problema planteado, corresponderá a uno de los cuatro siguientes < ,£ ,> ,³ ). La región factible es un polígono. El hecho fundamental - cuya demostración excede de estas páginas- es que si existe solución óptima se encuentra en un vértice del polígono que constituye la región factible.

9.2. Resolución gráfica.

    El método gráfico en el caso de dos variables es muy clarificador. En los gráficos de los ejemplos que se proponen más adelante se ilustra el proceso. Los pasos a seguir son:

1º- Se dibuja el recinto limitado por las restricciones del problema.
2º- Se representa gráficamente la función objetivo igualada a cero: mx + ny =0
3º- Se desplaza paralelamente la recta mx + ny = 0 hacia la derecha y/o hacia la izquierda, hasta que pase por cada uno de los vértices del recinto (región factible):

    El óptimo máximo será el vértice de la región factible cuya recta tenga mayor ordenada en el origen (más alejado hacia la derecha si la recta es creciente). El óptimo mínimo el vértice cuya recta tenga menor ordenada en el origen (más alejado hacia la izquierda).

    Podremos realizar una comprobación analítica parcial de la siguiente forma:

- Si la región factible es acotada se calcula el valor de la función objetivo en cada uno de los vértices de la región (o lo largo de uno de los lados). El valor máximo (o mínimo) correspondiente a los vértices del polígono será el óptimo buscado.
- Si la región no es acotada habrá que ver si el óptimo pertenece a la zona donde hay vértices. En ese supuesto se procede como si la región fuera acotada. En caso contrario el problema carece de solución.

 9.3. Ejemplos y ejercicios:

 Ejemplo 1. Optimizar la función f (x, y)= 2x + y, condicionada a las restricciones:
y £ 4
x + y ³ 0
y - x ³
    Observa el gráfico siguiente. Las restricciones dan lugar a la región factible, en este caso el triángulo que está rayado. La función objetivo se representa mediante una recta variable que inicialmente pasa por el origen de coordenadas. Situando el ratón en el punto rojo P puedes mover la recta hacia la derecha o la izquierda, lo que va produciendo distintos valores de esta función. El valor máximo será el correspondiente al último punto de la región factible que encuentres al desplazarte hacia la derecha. El valor mínimo el último que te encuentres al desplazarte hacia la izquierda.

    El óptimo máximo es el punto más alejado hacia la derecha; es el punto (2,4). El óptimo mínimo es el punto más alejado hacia la izquierda; es el punto (-4,4). Por tanto, el valor óptimo máximo es f (2,4) = 2.2 + 4 = 4 + 4 = 8, y el valor óptimo mínimo f (-4,4) = 2.(-4) + 4 = -4.

    Para el otro vértice de la región acotada (-1,1) la función objetivo valdría 2.(-1) + 1 =-1, con lo que queda comprobado analíticamente cuáles son el máximo y el mínimo.

Ejemplo 2: 
    Las restricciones de la función objetivo son: x ³ 0,  y ³ 0,  15x+28y ³450,  25x+10y ³ 200 y la función objetivo f(x,y)=25x+30y  
1) ¿Qué valor del recinto hace mínima la función objetivo?
2) ¿Qué función objetivo debemos coger para que el ejercicio 1 tengan infinitas soluciones? ¿cómo debe ser la recta para que ésto ocurra?

    En este caso la región factible no es finita. No existirá valor máximo de la función objetivo. Pero si existe valor mínimo que será el primero que encuentres desplazando la recta de la función objetivo hacia la derecha. Se trata según puedes comprobar pulsando el ratón encima del punto de (2,15). Observa que este punto se puede encontrar resolviendo el sistema formado por las rectas verde: 15x+28y=450  y  roja: 25x+10y=200.

Otros ejercicios de aplicación

9.4. Autoevaluación.

Pulsa el cuestionario. La ventana que aparece a continuación te propone unas cuestiones para que tu mismo valores si has comprendido el tema. Contéstalas todas y comprueba el resultado. Medita sobre las respuestas y repítelo hasta que las respondas bien todas.

Cuestionario