Programación lineal (dos variables)
- Detalles
- Categoría: 2º Bachillerato
- Publicado el Martes, 04 Octubre 2011 12:48
- Escrito por Mariano Herrero
Apareció para resolver problemas de carácter logístico y militar, aunque actualmente se aplica a la resolución de problemas económicos y sociales (problemas de mezclas, distribución de factorías, planes de producción, almacenaje, problemas de circulación, estudios de comunicación internas, etc.,), mediante técnicas matemáticas.
Se trata de encontrar la solución óptima consistente en optimizar (maximizar beneficios o minimizar costes) una función f(x, y) = ax + by + c llamada función objetivo con una serie de restricciones (condiciones que han de satisfacer las variables de decisión x e y) formuladas como desigualdades, pues los recursos económicos suelen ser limitados.
Al conjunto de todas las soluciones posibles (valores x e y que verifican todas y cada una de las restricciones) se le llama conjunto de soluciones factibles o región factible.
La región factible de dos variables es una región del plano limitada por las rectas que forman las restricciones (intersección de la solución de cada una de las inecuaciones).
Dicha región factible puede estar:
- Acotada (cerrada): siempre hay solución, que puede ser única o tener infinitas soluciones (un segmento)
- No acotada (abierta): puede haber solución o no tener solución.
Frontera de la región factible está determinada por las rectas que definen las restricciones.
Vértices o puntos extremos son cada uno de los puntos de intersección de dichas rectas asociadas a las restricciones. Para calcular las soluciones de cada vértice se resuelve el sistema de ecuaciones de las dos rectas que concurren en dicho vértice.
La solución óptima es aquella que maximiza o minimiza la función objetivo; se encuentra siempre en la frontera de la región factible. Si la solución es única, la solución óptima se encuentra en alguno de los vértices o puntos extremos de dicha región.
Utilizamos dos métodos: Método analítico
Se representa gráficamente la región factible.
Se halla los valores de en cada uno de los vértices de la región factible.
Si se trata de maximizar, el vértice que haga mayor la función objetivo f(x,y) es la solución; si hay dos vértices consecutivos en los que f(x,y) toma el mismo valor máximo => hay infinitas soluciones (todos los infinitos puntos del segmento que une dichos puntos)
Si tenemos que minimizar es exactamente igual, pero será el vértice que haga menor f(x,y).
Método gráfico:
Sea f(x, y) = ax + by + c la función objetivo, se llaman rectas de nivel asociadas a la función objetivos a rectas de la forma ax + by = k, donde k es un número real que varía.
Las rectas de nivel son rectas paralelas (los coeficientes a y b determinan su pendiente); variando k tenemos las distintas rectas de nivel.
La función objetivo toma el mismo valor en todos los puntos de cada recta de nivel
NOTA: Si los coeficiente a y b de la función objetivo (que determinan su pendiente)
son del mismo signo (pendiente negativa), a medida que aumenta k la función objetivo también aumenta, mientras que si son de distinto signo (pendiente positiva) la función objetivo disminuye.
Pasos a seguir para hallar la solución óptima:
Se lee el enunciado cuantas veces sea necesario con el fin de definir las variables x e y determinando la función objetivo. A veces es conveniente reordenar los datos y colocarlos en forma de tabla para facilitar las inecuaciones de las restricciones.
Se representa gráficamente la región factible limitada por las restricciones.
Se representa una cualquiera de las rectas de nivel ax + by = k; la más sencilla es la recta: ax + by = 0 (pasa por el origen de coordenadas)
Se trazan rectas paralelas a la recta de nivel ya trazada, por cada uno de los vértices del recinto (región factible).
Si se trata de maximizar, se observa qué recta tiene mayor ordenada (maximiza la función objetivo) y a qué vértice corresponde. Igualmente para minimizar, se observa qué recta tiene menor ordenada y a qué vértice corresponde
Las coordenadas de dicho vértice son la solución óptima. Si hay dos vértices que maximizan la función objetivo, entonces el segmento que los une, está contenido en la recta de nivel que pasa por esos dos puntos, y hay infinitas soluciones (todos los infinitos puntos de dicho segmento).
Ver Ejemplo1
Ejemplo2 propuesto en la Universidad de Castilla la Mancha junio 2010.
Método del simplex
Es un procedimiento iterativo de cálculo matricial para la programación lineal, que ignora soluciones no factibles y mejora la función objetivo en cada etapa, determinando si la solución es o no la óptima. Se utiliza para tres o más variables.
Se toma un vértice de la región factible y se aplica la siguiente propiedad (si maximizamos):
Si f(x,y) NO toma su valor máximo en dicho vértice, entonces hay una arista que parte de éste vértice a lo largo de la cual f(x,y) aumenta.
La solución óptima se obtiene desplazándose a través de las aristas de la región factible, hasta alcanzar un vértice en el que f(x,y) sea máxima; esto se consigue cuando NO haya ninguna arista que parta de éste vértice (f máxima) en la que f(x,y) aumente de valor.
Para ello se convierten las desigualdades en igualdades y en consecuencia se introduce una variable de holgura para cada una de las desigualdades; también se iguala a CERO la función objetivo.