No me gusta este tutorial. ¡Regrésame al tutorial más viejo (inglés)!
Recursos
Nota Para seguir este tutorial, debes saber como
graficar desigualdades lineales y sistemas de desigualdades lineales.
Fundamentos
Empezamos por considerar los tipos de problemas que estaremos solucionando:
Problema de programación lineal (Problema PL) con dos incógnitas
Un
problema de programación lineal o
problema PL con dos incógnitas $x, y$ es uno en cual debemos hallar el valor máximo o mínimo de una expresión lineal
llamada la
función objetiva, sujeta a unas
restricciones lineales de la forma
$cx + dy \leq e \qquad$ o $\qquad cx + dy \geq e.$
El conjunto solución del sistema de restricciones se llama la
región factible del problema PL. El valor más grande o más pequeño de la función objetiva se llama el
valor óptimo, y una par de valores $(x, y)$ que resultan en el valor óptimo es una
solución óptima.
Teorema fundamental de la programación lineal
- Si un problema PL tenga soluciones optimales, entonces éstas deben aparecer en vértices, o esquinas, del conjunto factible.
- Un subconjunto del plano es acotado si puede ser completamente encerrado por un rectángulo. Problemas PL cuyas regiones factibles son acotadas (vea más abajo) y no vacías siempre tienen solucciones optimales.
Ejemplo
El problema de programación lineal tiene la siguiente región factible con cuatro puntos de esquina marcados con puntos:
|
● $(0, 0)$ | | $p = 0 + 3(0) = 0$ |
● $(30, 0)$ | | $p = 30 + 3(0) = 30$ |
● $(10, 40)$ | | $10 + 3(40) = 120$ |
● $(0, 50)$ | | $p = 0 + 3(50) = 150$ |
|
|
|
Pues el punto esquina con el máximo valor de
p es (0, 50), hemos solucionado el problema de programación lineal, y la solución es:
$x = 0, y = 50;\ \ p = 150.$
Notas
-
Cada punto de esquina es a la intersecciób de dos (o más) rectas de límite, así que es posible que debas resolver un sistema de dos ecuaciones lineales en dos desconocidas para hallar sus cooredenadas exactas.
-
Si el valor óptimo de la función objetiva se produce en dos puntos de esquina, entonces cada punto de la recta que los conecta también es una solución óptima.
La gráfica a la izquierda muestra la región factible para el siguiente problema PL:
|
|
|
Por lo tanto, la solución del problema PL es como sigue:
Regiones factibles no acotadas
Problemas PL con regiones factibles no acotadas
Recordemos de arriba que un subconjunto del plano es
acotado si puede ser completamente encerrado por un rectángulo. Si no es posible encerrarlo, entonces es
no acotado. Cuando no es acotado la región factible de un problema PL, entonces es posible que no tenga una solución óptima.
A continuación son dos problemas PL con la misma región factible no acotada. El problema a la izquierda tiene una solución óptima, pero no el problema a la derecha. Compruébalo por ti mismo por hacer clic en varios puntos de la región factible para mirar los valores correspondientes de $c$.
Soluctionar problemas PL con regiones factibles no acotadas
A veces podemos reconocer si o no un problema PL con una región factible no acotada tiene soluciones óptimas:
Los sigueintes se aplican cuando tenemos las restricciones $x \geq 0,\ y \geq 0.$
- Si estás minimizando $c = ax + by$ con $a$ y $b$ no negativas, entonces soluciones óptimas siempre existen.
- Si estás maximizando $p = ax + by$ con $a$ y $b$ ambas positivas, entonces no hay ninguna solución óptima.
- Si estás maximizando $p = ax + by$ con $a \leq 0$ y $b \leq 0,$ entonces soluciones óptimas siempre existen.
- Si estás minimizando $c = ax + by$ con $a$ y $b$ ambas negativas, entonces no hay ninguna solución óptima.
Ejemplo
El ejemplo arriba a la izquierda satisface (a) y por lo tanto tiene soluciones óptimas (lo resolveremos a continuación). El ejemplo arriba a la derecha satisface satisface ninguno de los requisitos, por lo que, en principio, puede o no tener soluciones óptimas. Veremos de abajo un método de tratar con ejemplos como esto.
Ahora resuelve el ejemplo arriba a la izquierda:
%Q
¿Qué tal con problemas que no cumplan ningunas de las condiciones (a)–(d) anterior?
%A
En %4 encontrarás una discusión de un método sencillo para averiguar si hay soluciones óptimas en el caso de una región factible no acotada:
Dibuja un (gran) rectángulo que incluye todos los puntos esquina de la región factible, y calcula los valores de la función objetiva en los puntos equinos nuevos introducidos por el rectángulo. Si el valor óptimo está todavia a uno de los puntos esquina originales, entonces el problema PL tiene una solución óptima; si no, entonces no hay soluciones óptimas.
Ahora prueba los ejercicios en %4, algunos de los %8, o seguir al siguiente tutorial por pulsar "siguiente tutorial" ubicado a la izquierda.
Última actualización: octubre 2016
Derechos de autor © 2016