PROGRAMACIÓN LINEAL MÉTODO GRÁFICO
Enviado por 4897 • 24 de Agosto de 2017 • Apuntes • 4.041 Palabras (17 Páginas) • 344 Visitas
Solución gráfica a problemas de programación lineal
El método gráfico se utiliza para la solución de problemas de Programación Lineal (PL), representando geométricamente las restricciones, condiciones técnicas y la función objetivo. Una consideración importante que debemos tomar en cuenta es que este método sólo se puede emplear si el modelo únicamente está formulado con dos variables. Para modelos con tres o más variables, el método gráfico es impráctico o imposible.
Pasos del Método Gráfico
- Dibujar un plano coordenado y asociar un eje a cada variable del modelo.
- Representar en el plano las restricciones funcionales.
- Identificar gráficamente el conjunto de soluciones factibles (región factible).
- Representar en el plano la función objetivo.
- Identificar gráficamente la solución óptima.
maximizar x1 + 2x2
sujeto a x1 + x2 ≤ 4
x1,, x2 ≥ 0[pic 2]
[pic 3]
[pic 4][pic 5][pic 6][pic 7][pic 8][pic 9][pic 10]
[pic 11]
[pic 12]
[pic 13][pic 14][pic 15][pic 16][pic 17]
[pic 18]
La región que está formada por las restricciones (el triángulo amarillo) se llama región factible, dicha región es el área que cumple con todas las restricciones. Usualmente los puntos óptimos (los mejores) se encuentran en un vértice (los puntos de rojo).
Ya que tenemos los puntos que podrían ser óptimos (0,0), (0,4) y (4,0) evaluamos en la función objetivo:
Valor de la función x1 + 2x2 al sustituir | Punto |
0 + 2(0) = 0 | (0, 0) |
0 + 2(4) = 8 | (0, 4) |
4 + 2(0) = 4 | (4, 0) |
Debido a que la función objetivo es de maximizar (queremos el valor más alto), entonces el punto óptimo será (0,4) ya que nos da el mayor beneficio y cumple todas las restricciones con una función objetivo de 8 unidades.
Tipos de solución: Óptima Única
Una solución es óptima única, cuando tanto las variables como la función del objetivo toman valores finitos, existiendo una sola combinación de valores de las variables que optimiza el valor de la función objetivo. Para observar un ejemplo de solución óptima única, presentamos el siguiente ejemplo:
max 3x1 + 4x2 [pic 19]
s. a: 4x1 + 2x2 ≥ 4
x1 | x2 |
0 | 3 |
9 | 0 |
x1 | x2 |
0 | 2 |
1 | 0 |
x1 + 3x2 ≤ 9
x1 | x2 |
0 | 14 |
4 | 0 |
7x1 + 2x2 ≤ 28
x1, x2 ≥0
[pic 20]
[pic 21]
[pic 22][pic 23][pic 24][pic 25]
[pic 26]
[pic 27][pic 28]
[pic 29]
[pic 30][pic 31][pic 32]
[pic 33]
[pic 34]
[pic 35]
[pic 36][pic 37]
La solución óptima es (66/19, 35/19) con un valor de 338/19.
minimizar -3x1 - x2
sujeto a x1 + 3x2 ≤ 6
x1 - x2 ≤ 4
x1, x2 ≥ 0[pic 38]
[pic 39]
[pic 40][pic 41][pic 42][pic 43]
[pic 44]
[pic 45][pic 46]
[pic 47]
[pic 48]
[pic 49][pic 50][pic 51][pic 52]
[pic 53]
Continuamos con la restricción x1 - x2 ≤ 4 (convirtiéndola a igualdad), dando valores para graficar.
x1 | x2 |
0 | -4 |
4 | 0 |
Ahora evaluamos el punto (0, 0) en la desigualdad 0 - (0) ≤ 4 debido a que se cumple la desigualdad los puntos factibles son los considerados de la recta hacia el punto que probamos es decir (0, 0).
El área factible será la región que cumpla con todas las restricciones (en este caso, la región amarilla). Los posible puntos óptimos son los rojos, note que hay un punto que no sabemos cuál es, puede adivinarse pero no aseguramos que el punto que identificamos a simple vista sea correcto, por lo que debemos calcular dicho punto, esto lo haremos resolviendo el sistema de ecuaciones que está compuesto por las dos desigualdades (debido a que es un vértice, las consideramos como igualdades) que intersecan es decir, x1 + 3x2 = 6 y x1 - x2 = 4. Utilizaremos el método de suma y resta para resolver el sistema de ecuaciones (puedes utilizar, cualquier método para resolver).
...