MÉTODOS DE RESOLUCIÓN
1. Procedimiento analítico.
Este procedimiento únicamente es válido para problemas con regiones factibles acotadas. Para resolver un problema de Programación Lineal mediante el procedimiento analítico, necesitamos conocer el siguiente teorema.
|
Teorema fundamental de la Programación lineal Si un problema de Programación Lineal tiene región factible no vacía, entonces, si existe el óptimo (máximo o mínimo) de la función objetivo, se encuentra en un punto extremo (vértice) de la región factible. Si una función alcanza el valor óptimo en dos vértices consecutivos de la región factible, entonces alcanza también dicho valor óptimo en todos los puntos del segmento que determinan ambos vértices. |
Teniendo en cuenta el teorema anterior, para calcular el máximo o el mínimo de una función, será suficiente con evaluar la función objetivo en todos los vértices de la región factible y quedarnos con el que proporciona el valor óptimo.
|
Actividad 10. Aplicar el Teorema fundamental de la Programación Lineal para calcular el máximo y el mínimo de la función F(x,y)=2x+3y sujeta a las restricciones de la actividad 5 de la página anterior:
(Como ya tenemos la región factible y los vértices, hay que calcular el valor de la función objetivo en cada uno de ellos. Para ello te puedes ayudar de la siguiente escena sabiendo que a, b y c son los coeficientes de la función objetivo F(x,y)=ax+by+c) |
Escena 4
2. Procedimiento gráfico.
Este procedimiento es válido tanto para problemas con regiones factibles acotadas como no acotadas. Como los problemas que vamos a estudiar tienen dos variables, es posible efectuar una representación gráfica en el plano y encontrar gráficamente la solución. Sin embargo, este procedimiento no es generalizable para un número cualquiera de variables.
Cualquier punto de la región factible es una solución factible para el problema de Programación Lineal, sin embargo, nos interesa encontrar en cualquier problema la solución óptima. Para encontrarla hacemos F(x,y)=0 y representamos la recta que se obtiene llamada recta de beneficio nulo. Posteriormente recorremos la región factible con rectas paralelas a la que hemos representado, llamadas líneas de nivel o rectas de beneficio constante. Observamos como varía la función objetivo al desplazar las rectas de nivel en un sentido o en otro y los últimos puntos de contacto de estas rectas con la región factible proporcionan el valor o valores máximos y mínimos.
Vamos a comprobarlos con las siguientes actividades y la siguiente escena.
|
Actividad 11. Aplicar el procedimiento gráfico para calcular el máximo y el mínimo de la función F(x,y)=2x+3y sujeta a las restricciones de la actividad 5 de la página anterior:
La escena ya aparece configurada con los vértices y la función objetivo de la actividad. Para otro ejercicio cualquiera, coloca el puntero dentro de la escena y pulsa el botón derecho del ratón, se abrirá una ventana en la que puedes introducir el valor de los vértices partiendo de uno de ellos y siguiendo un orden de giro en cualquier sentido. (Recuerda que si la región factible es no acotada debes introducir un punto de cada una de las dos semirrectas que determinan la región factible, lo suficientemente alejados del área visible de la escena para que gráficamente se vea la región no acotada). Después en la barra superior introduce el número de vértices que tienes y se representará la región factible. Ahora, en la barra inferior, da a "Función obj." el valor 1 y se representa la recta de beneficio nulo. En otro ejercicio puedes modificar los valores de a, b y c sabiendo que F(x,y)=ax+by+c. Por último desplaza el punto de la recta de beneficio y observa como va aumentando o disminuyendo el valor de la función objetivo para cada una de las rectas de nivel. Los últimos puntos de contacto de las rectas de nivel con la región factible proporcionan los valores máximo y mínimo. (Si en la escena desplazas la recta con lentitud cuando se abandona la región factible se marcará de color distinto los valores máximo y mínimo). |
Escena 5
|
Actividad 12. Experimenta con la escena y modifica los vértices o el valor de la función objetivo para comprender mejor el procedimiento gráfico. Observa el valor de la función objetivo que aparece en la parte inferior. Intenta razonar en qué casos aparecen infinitas soluciones. |
|
Actividad 13. Calcular el máximo y el mínimo de la función F(x,y)=8x+4y sujeta a las restricciones de la actividad 8 de la página anterior:
|
|
Actividad 14. Experimenta con la escena y modifica los vértices o el valor de la función objetivo para comprender mejor el procedimiento gráfico y estudiar los distintos tipos de problemas que puede haber según su solución. |
(Adaptada por Mª Pilar Gistau Calvo)
©
Ministerio de Educación. Año 2009
Los contenidos de esta unidad didáctica están bajo una licencia de Creative Commons si no se indica lo contrario.