INVESTIGACIÓN DE OPERACIONES
Unidad II
Programación Lineal
Tema: Método gráfico
• Método gráfico
• Caso P.L.E
Objetivo
Desarrollar modelos de
programación lineal
aplicando el método
gráfico.
Método gráfico
Max z = f ( x, y )
s.a. 2 x + y 100
El método gráfico se emplea para resolver
x + y 80
PPL que presentan solo 2 variables de
decisión. Para ello consideramos: x 40
x, y 0
• Graficar la región factible en este caso
limitada por rectas, puede ocurrir que no
toda la región este limitada (caso no
acotado). Recordar que la región factible
es aquella definida por las restricciones y
en programación lineal se encuentra en el
primer cuadrante (por la condición de no
negatividad) .
• Luego se iguala a cero la función objetivo,
obteniendo una recta la cual se gráfica (no es parte
de la región factible), dicha recta es referencial para
trazar paralelas (rectas de isoutilidad); dependiendo
del problema, se toma el último punto o el primer
punto de la región factible, puede darse el caso que
es todo un segmento de recta entonces se tienen
infinitos puntos óptimos pero el valor óptimo es único
Para poder conocer hacia donde debemos
avanzar con las rectas paralelas y así obtener el
punto óptimo, podemos:
a) Evaluar puntos en la función objetivo y con ello
conocer cuando aumenta o disminuye de valor.
b) Hallar el gradiente de la función objetivo,
dicho vector siempre indica donde esta el
máximo, en este caso como la función es lineal el
gradiente son los coeficientes de las variables. Por
ejemplo si la función objetivo fuera 𝑧 = 2𝑥 − 5𝑦
entonces tenemos 𝛻𝑧 = (2, −5).
NOTA: Otro criterio para hallar el punto óptimo es
tomar los vértices del polígono que es la frontera
de la región factible; evaluarlos en la función
objetivo y de acuerdo a ello obtener el óptimo.
Este criterio no funciona en caso de enteros
(pues no necesariamente los vértices tienen
coordenadas enteras) y tampoco si la región
factible no es acotada.
También puede ser tedioso hallar los vértices que
resultan de la intersección de rectas y no es
nada práctico si son muchos.
Ejemplo 1
Resolver:
Solución:
Graficamos la región factible recordando que se encuentra en el primer cuadrante
(𝑥, 𝑦 ≥ 0)
Ejemplo 1
Luego igualamos a cero la función objetivo obteniendo 5𝑥 + 4𝑦 = 0 𝑧 = 0 y la
graficamos y algunas paralelas más (se puede evaluar puntos para obtener el valor
de z en las paralelas).
Ejemplo 1
Podemos observar que z aumenta de valor si trazamos las paralelas en la dirección
donde esta el punto de intersección de las dos rectas para este caso (no siempre
es así).
Si tomamos el gradiente que es 𝛻𝑧 = (5,4) dicho vector también nos indicaría en
que dirección aumenta z.
Ejemplo 1
Entonces la solución es la intersección de las dos rectas, por lo tanto resolvemos el
sistema de ecuaciones lineales:
14 18
Cuya solución es 𝑥, 𝑦 = , y reemplazando en la función objetivo obtenemos
5 5
14 18 142
el valor máximo 𝑧 = 5 +4 =
5 5 5
Ejemplo 2
Resolver:
Solución:
Graficamos la región factible recordando que se encuentra en el primer cuadrante
(a, 𝑏 ≥ 0), las dos primeras restricciones representan una región sombreada, y la
tercera (igualdad) es una recta; por lo tanto la región factible es el segmento de
recta que se encuentra dentro de la región sombreada.
Ejemplo 2
Luego igualamos a cero la función objetivo obteniendo 3a − 𝑏 = 0 𝐺 = 0 y la
graficamos y algunas paralelas más.
Ejemplo 2
Utilizando 𝛻𝐺 = 3, −1 , podemos observar en que dirección aumenta el valor de G
(también se puede realizar evaluando la función objetivo en algunos puntos), en
este caso tomamos la dirección contraria pues deseamos minimizar. Del grafico el
punto óptimo se obtiene de la intersección de L2 con L3.
Ejemplo 2
7 2
Cuya solución es 𝑎, 𝑏 = , y reemplazando en la función objetivo obtenemos
3 3
7 2 19
el valor mínimo G = 3 − =
3 3 3
Nota:
• En este ejemplo se puso la parte sombreada para visualizar mejor, la región
factible solo es el segmento de recta de color verde.
Ejemplo 3
Resolver:
Solución:
Graficamos la región factible recordando que se encuentra en el primer cuadrante
(x, y ≥ 0), en este caso la región factible son los segmentos de rectas horizontales
(segunda coordenada entera) dentro de la región definida por las desigualdades.
Ejemplo 3
Luego igualamos a cero la función objetivo obteniendo −x + 2y = 0 𝐻 = 0 y la
graficamos y algunas paralelas más.
Ejemplo 3
Utilizando 𝛻𝐻 = −1,2 , podemos observar en que dirección aumenta el valor de H
(también se puede realizar evaluando la función objetivo en algunos puntos). Del
grafico el punto óptimo se obtiene de la intersección de L2 con la recta y=2.
Ejemplo 3
Cuya solución es 𝑥, 𝑦 = 1,2 y reemplazando en la función objetivo obtenemos
el valor máximo H = −1 + 2(2) = 3.
Nota:
• En este ejemplo se puso la parte sombreada para visualizar mejor, la región
factible son los segmentos horizontales (en algunos casos también hay puntos).
• Si la variable entera fuera 𝑥 la región factible serían segmentos verticales.
• Si las dos variables fueran enteras la región factible serían solo puntos.
En los demás ejemplos se considerarán más criterios y la formulación matemática.
Ejemplo 4
Una compañía de auditores se especializa en preparar liquidaciones y auditorias
de empresas pequeñas. Tienen interés en saber cuántas auditorias y liquidaciones
pueden realizar mensualmente para maximizar sus ingresos. Se dispone de 800
horas de trabajo directo y 320 horas para revisión. Una auditoria en promedio
requiere de 40 horas de trabajo directo y 10 horas de revisión, además aporta un
ingreso de 300 dólares. Una liquidación de impuesto requiere de 8 horas de trabajo
directo y de 5 horas de revisión, produce un ingreso de 100 dólares. El máximo de
liquidaciones mensuales disponibles es de 60.
Solución:
Primero vamos a modelar el problema:
Definimos las variables de decisión. Sea:
x1: # de auditorías
x2: # de liquidaciones
El objetivo del problema es maximizar el ingreso total.
Luego la función objetivo es: Max z = 300 x + 100 x
1 2
Ejemplo 4 Max z = 300 x1 + 100 x2
Luego las restricciones:
s.a. 40 x1 + 8 x2 800
Tiempo disponible de trabajo directo 40 x1 + 8 x2 800 10 x1 + 5 x2 320
Tiempo disponible para la revisión 10 x1 + 5 x2 320 x2 60
Número máximo de liquidaciones x2 60 x1 , x2 0
Luego el modelo del PPL es: x1 , x2 : enteros
x2
La región factible en este caso viene dada por una
colección de puntos con coordenadas x e y ambas
enteras.
x1
¿Cómo determinar la solución óptima?
Max z = 300 x1 + 100 x2
s.a. 40 x1 + 8 x2 800
Tras haber identificado la región factible para la
compañía de auditores, se busca la solución óptima, 10 x1 + 5 x2 320
la cual es el punto de la región factible con el valor x2 60
más grande de z = 300 x1 + 100 x2 . Para encontrar la
solución óptima, es necesario graficar una recta en la x1 , x2 0
cual todos los puntos tengan el mismo valor z . En un x1 , x2 : enteros
problema de maximización, esta recta recibe el x2
nombre de recta de isoutilidad (en un problema de
minimización, recta de isocostos). Para trazar una
recta de isoutilidad, se escoge un punto en la región
factible y se calcula su valor . Sea el punto (20, 0) ,
para (20,0), su valor de z =300(20)+100(0)=6000.
Por consiguiente, (20, 0) queda en la recta de
isoutilidad z = 300(20) + 100(0) = 6000 .
Si se vuelve a escribir 300 x1 + 100 x2 = 6000 como x2 = 60
, − 3 x1
entonces la recta de isoutilidad 300 x + 100 x = 6000
1 2
tiene pendiente de -3. Puesto que todas las rectas de
isoutilidad son de la forma 300 x1 + 100 x2 = cte , todas
las rectas de isoutilidad tienen la misma pendiente.
x1
¿Cómo determinar la solución óptima?
Max z = 300 x1 + 100 x2
Esto significa que una vez que se trazó una recta de
s.a. 40 x1 + 8 x2 800
isoutilidad, es posible encontrar todas las otras rectas
de isoutilidad, desplazándose en forma paralela a la 10 x1 + 5 x2 320
recta de isoutilidad que ya se graficó.
x2 60
Ya queda claro cómo encontrar la solución óptima
para un PPL de dos variables. Después de trazar una x1 , x2 0
sola recta de isoutilidad, es posible generar otras
x2
x1 , x2 : enteros
rectas de isoutilidad desplazándose en forma
paralela a la recta ya graficada en una dirección en
que se incremente z (en el caso de un problema de
maximización). Después de un punto, las rectas de
isoutilidad ya no intersecan la región factible. La
última recta de isoutilidad que corta (toca) la región 300(12) + 100(40) = 7600
factible define el valor de z más grande de
cualquier punto en la región factible e indica la Recta de
isoutilidad
solución óptima para el PPL. En este ejemplo, la
función objetivo z = 300 x1 + 100 x2 aumenta al
desplazarse en una dirección para la cual tanto x1
como x2 se incrementan. x1
Interpretación
Interpretación: Max z = 300 x1 + 100 x2
La empresa debe realizar 12 auditorías y s.a. 40 x1 + 8 x2 800
40 liquidaciones para tener un ingreso 10 x1 + 5 x2 320
máximo de 7600 dólares.
x2 60
x1 , x2 0
x2
x1 , x2 : enteros
300(12) + 100(40) = 7600
Recta de
isoutilidad
Casos Especiales
También existen casos especiales en los que el PPL no
tienen una solución óptima única.
1.Algunos PPL tienen un número infinito de soluciones
óptimas (soluciones óptimas múltiples o alternativas)
2.Algunos PPL no tienen soluciones factibles (PPL no
factible)
3. Algunos PPL son no acotados; hay puntos en la
región factible con valores arbitrariamente
grandes (en problemas de maximización)
Bibliografía:
https://www.captio.net/blog/las-ocho-etapas-en-el-
proceso-de-toma-de-decisiones-de-la-empresa
