Programación lineal (dos variables)

 

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.

 

región factible acotada y no acotada

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  ab  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 ab  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.