Upload
julio-pari
View
4.106
Download
6
Embed Size (px)
Citation preview
Programación Lineal:
Método Gráfico
IO1 R. Delgadillo 2
Método Gráfico.
Introducción
Gráfica de las restricciones
Región factible
Gráfica de la Función Objetivo
Solución Óptima
Ejemplos
IO1 R. Delgadillo 3
Introducción
Un problema de programación Lineal, puede ser resuelto por:
Método gráfico
Método análitico
IO1 R. Delgadillo 4
Introducción
El Método gráfico:
Utiliza la geometría plana
Es fácilmente comprensible
Da una idea clara de lo que sucede al resolver un problema lineal.
Permite visualizar alguna propiedades de la Programación Lineal
Tiene limitaciones respecto al número de variable ( a lo mas 3)
IO1 R. Delgadillo 5
Introducción
La Métodologia que sigue el Método Gráfico es:
Gráfica de la región factible
Diseño de la función objetivo
Desplazamiento de la función objetivo en dirección del incremento (ó decremento) del valor de la F.O.
IO1 R. Delgadillo 6
Gráfica de las restricciones
Una restricción es una limitación al modelo de programación lineal
Una restricción viene dada por una desigualdad
El gráfico de una restricción está dado por el gráfico de las desigualdades que representa la restricción.
IO1 R. Delgadillo 7
Gráfica de las restricciones
Procedimiento para graficar una desigualdad (restricción) :
Gráfique la igualdad: convierta la desigualdad en igualdad y grafique esta recta.
Escoja un punto de ensayo: Elija un punto que no pertenezca a la recta.
Evalue el primer miembro de la expresión: sustituya el punto de ensayo en el primer miembro de la desigualdad
IO1 R. Delgadillo 8
Gráfica de restricciones
Determine si el punto de ensayo satisface la desigualdad: Si el punto de ensayo satisface la
desigualdad, entonces la desigualdad está representada por la recta y todos los puntos de la parte del plano en la que se encuentra el punto de ensayo.
Si en punto de ensayo no satisface la desigualdad, entonces la recta y todos los puntos del plano que no están del lado del punto de ensayo satisfacen la desigualdad.
IO1 R. Delgadillo 9
Gráfica de restricciones
Graficar: 2x +4y >= 4
2
1
(0,0)
2x + 4y = 4 Área que satisface la desigualdad
Punto de ensayo
IO1 R. Delgadillo 10
Gráfica de restricciones
Graficar: 2x +4y >= 4
5x + 10y <= 20
2
1
(0,0)
4
2
Área que satisface las dosrestricciones
IO1 R. Delgadillo 11
Región Factible
Al graficar todas las resticciones se generará un área delimitada por las mismas, a esta región se le conoce como región factible
Región factible ó conjunto factible:
Es el conjunto de todos los valores no negativos de las variables de decisión que satisfacen todas las restricciones simultáneamente
IO1 R. Delgadillo 12
Diseño de la Función Objetivo
La representación gráfica de la función objetivo será la gráfica de un contorno
Un Contorno (isocuanta) de una función f de dos variables es el conjunto de todos los pares(x1,x2) para los cuales f(x1,x2) toma un valor constante especifico.
Cuando f es la función de utilidad se le denomina recta de isoutilidad, y si es de costos, recta de isocostos.
IO1 R. Delgadillo 13
Diseño de la Función Objetivo
Los contornos de una función lineal forman una familia de rectas paralelas
Ejemplo: Supóngase que estamos vendiendo dos productos.
La utilidad por unidad del producto 1 es $2 y del producto 2 es $4.
Esto es la función de utilidad es:
F(x1,x2)= 2 x1 + 4 x2
IO1 R. Delgadillo 14
Diseño de la Función Objetivo
Si queremos graficar todas las combinaciones de cantidades de producto 1 y 2 para tener una utilidad igual a 10
=> f(x1,x2)= 2 x1 + 4 x2 = 10
IO1 R. Delgadillo 15
Diseño de la Función Objetivo
5
2.52 x1 +4 x2 = 10
2 x1 +4 x2 = 20
10
5
15
7.52 x1 +4 x2 = 30
IO1 R. Delgadillo 16
Diseño de la Función Objetivo
En resumen:
El gráfico de la F.O. es el gráfico de una igualdad
Los contornos de una función lineal forman una familia de rectas paralelas
El desplazamiento de la F.O forma una familia de rectas paralelas (contornos de la F.O).
IO1 R. Delgadillo 17
Solución Óptima
Solución óptima: Es un punto de la región factible con mayor valor de la F.O. (problema de Máximo) ó con menor valor de la F.O. (problema de Mínimo)
La solución óptima se consigue por el desplazamiento de la F.O. En dirección de su mejor valor. (mejor es mayor o menor)
IO1 R. Delgadillo 18
Ejemplo
Resolver gráficamente el siguiente modelo de programación lineal
F.O. Max 2x1 + 7x2
sujeto a:
3x1 + 4x2 <= 12
x1 + 8x2 <= 8
6x1 + x2 <= 15
x1, x2 >= 0
IO1 R. Delgadillo 19
Ejemplo
0 1 2 3
0
1y
x
: 3.0 x + 4.0 y = 12.0
: 1.0 x + 8.0 y = 8.0
: 6.0 x + 1.0 y = 15.0
Payoff: 2.0 x + 7.0 y = 9.6
Optimal Decisions(x,y): ( 2.4, 0.7)
: 3.0x + 4.0y <= 12.0
: 1.0x + 8.0y <= 8.0
: 6.0x + 1.0y <= 15.0
IO1 R. Delgadillo 20
Ejercicios
Graficar el siguiente modelo de programación lineal.
F.O. Max 5A + 6B
s.a: 3A + 5B <= 30
2A + 3B <= 12
A + 5B >= 15
4A + B <= 8
A, B >= 0
IO1 R. Delgadillo 21
Ejercicios
Graficar el siguiente modelo de programación lineal.
F.O. Max 3A + 7B
s.a: 6A + 11B <= 66
2A + B <= 10
0.5A + 0.4B >= 6
A + B >= 4
A, B >= 0
IO1 R. Delgadillo 22
Ejercicios
Graficar el siguiente modelo de programación lineal.
F.O. Max 12A + 10B
s.a: 6A + B <= 6
9A + 4B <= 18
2A + 5B <= 20
A + B <= 1
A, B >= 0