Download Presentación

Investigación de operaciones
Autor: Raymundo Palacios
Capítulo 4
Método gráfico
4.1 Introducción
El método gráfico es una técnica analítica que soluciona
problemas de programación lineal formulados con
ecuaciones lineales de primer grado y que contienen un
máximo de dos o tres variables de decisión.
Sin embargo, no es factible utilizar esta técnica
descriptiva para solucionar los problemas que puede
enfrentar una organización, ya que para llevar a cabo la
elaboración y la comercialización de productos y
servicios en un segmento de un mercado real, el modelo
determinístico con seguridad estará formulado con más
de tres variables de decisión.
Por consiguiente, es impráctico e imposible utilizar el
método gráfico para solucionar modelos que se diseñan
con más de tres variables de decisión.
4.1 Introducción
Método gráfico.−Método analítico que permite resolver
problemas de programación lineal en un plano cartesiano.
Los problemas se formulan por medio de ecuaciones lineales
que contienen dos o tres variables de decisión.
El problema de PL se resuelve mediante una función objetivo
que se debe maximizar (utilidad) o minimizar (tiempo costo),
sujeta a restricciones.
La solución consiste en graficar las restricciones de manera
que se forme una región factible en la cual se buscará una
solución que satisfaga todas las restricciones, lo cual se logra
encontrando el vértice óptimo cuyas coordenadas nos
permitan encontrar la solución óptima; es decir, maximizar o
minimizar la función objetivo.
4.1 Introducción
Restricciones activas u obligatorias.- Son aquellas
que delimitan geométricamente a la región factible.
Restricciones redundantes.− Son restricciones que no son necesarias
para solucionar un problema de programación lineal, en el sentido de
que la región factible es exactamente la misma si incluye o no a estas
restricciones.
Variables de holgura.- Para una restricción del tipo ≤ la diferencia
entre el lado derecho y el lado izquierdo de la misma se denomina
HOLGURA; para convertir esta desigualdad en igualdad sólo es
necesario sumar una variable de holgura no negativa en el lado
izquierdo de la restricción.
4.1 Introducción
En el método gráfico, la solución óptima se descubre
seleccionando los vértices que conforman al polígono que
delimita a la región factible, trazando la recta de la función
objetivo consecutivamente por cada vértice, y luego
desplazando la recta paralelamente, sustituyendo las
coordenadas de cada uno de los vértices de la región factible
en la función objetivo, para obtener la optimización de la
función objetivo, ya sea maximizando o minimizando su valor.
El vértice que suministre el valor óptimo (máximo o mínimo)
representa la solución óptima.
4.3 MODELO DE PL BASADO EN UNA
DIETA PARA UN CABALLO LUSITANO
Retomemos el problema de la alimentación recomendada para un caballo
lusitano durante tres meses (con maíz, trigo y sorgo mezclando dos
costales que contienen diversas cantidades de estos alimentos en
diferentes proporciones) que se presenta en el capítulo 3.
El objetivo es minimizar los costos.
La cantidad de alimentos que deberá comprar durante los tres meses se
encuentra estimada en la tabla 3.3.
Al dueño le cuesta $30 pesos el costal X y $40 pesos el costal Y ¿Cuántos
costales puede comprar de X y Y al menor costo posible?
4.3 MODELO DE PL BASADO EN UNA
DIETA PARA UN CABALLO LUSITANO
El problema de PL queda planteado como sigue:
Minimizar Z = 30X + 40Y
Sujeto a:
4X ≥ 12 Cantidad de maíz
3Y ≥ 6 Cantidad de trigo
X + 1.5Y ≤ 9 Cantidad de sorgo
donde X, Y ≥ 0
4.3 MODELO DE PL BASADO EN UNA
DIETA PARA UN CABALLO LUSITANO
Solución del modelo
Para resolver el problema, se encuentran valores para las
variables de decisión que satisfagan todas las
restricciones y que, al mismo tiempo, proporcionen el
valor óptimo para la función objetivo Grafiquemos cada
una de las restricciones, considerando las desigualdades
disponibles como ecuaciones en forma de igualdades,
excepto las restricciones de no negatividad:
4X = 12; X = 3
3Y = 6; Y = 2
X + 1.5Y = 9
4.3 MODELO DE PL BASADO EN UNA
DIETA PARA UN CABALLO LUSITANO
Se obtiene una región factible o semiplano factible,
determinado por el triángulo rectángulo cuyos vértices
son los puntos O, P y Q y que se muestra a continuación:
P (3, 4)
O (3, 2)
Q (6, 2)
4.3 MODELO DE PL BASADO EN UNA
DIETA PARA UN CABALLO LUSITANO
En la siguiente tabla se muestra la obtención de la solución óptima (minimizar el
costo) para la función objetivo 30X + 40Y = Z :
Vértice (X, Y)
Resultado
Evaluación
O (3, 2)
30(3) + 40(2) = 170
Solución óptima
P (3, 4)
30(3) + 40(4) = 250
Solución factible
Q (6, 2)
30(6) + 40(2) = 260
Solución factible
Por lo tanto, el vértice buscado es O (3,2), lo que significa que la solución óptima
es mezclar 3 costales de X con 2 costales de Y.
Si sustituimos estos valores en la función objetivo 30 X + 40 Y = Z obtenemos el
costo mínimo de 30(3) + 40(2) = 170 pesos.
4.4 MODELOS GRÁFICOS ACOTADOS,
NO ACOTADOS Y NO FACTIBLES
Todo problema de programación lineal queda clasificado en alguna de las
siguientes situaciones que no se traslapan:
Primer caso: El problema tiene una solución óptima.
Segundo caso: El problema carece de una solución óptima porque es no
acotado.
Tercer caso: El problema carece de solución óptima porque es no factible.
En la práctica, un programa lineal correctamente formulado siempre tiene
una solución óptima.
Cuando un problema se encuentra mal formulado o cuando existen
errores al capturar los datos del problema en un software, siempre se
incurre en los casos 2 y 3.
4.4 MODELOS GRÁFICOS ACOTADOS, NO
ACOTADOS Y NO FACTIBLES
Se denomina modelo gráfico acotado en una figura
geométrica con solución única a un problema que
está delimitado por un área factible, en el cual la
función objetivo adopta sólo un valor óptimo en uno
de los vértices de la región factible.
Si la función objetivo es paralela a una de las
restricciones, entonces a este problema se le
denomina modelo gráfico acotado en una recta con
solución única que se encuentra restringido por un
área factible en la cual la función objetivo alcanza
sólo un valor óptimo en uno de los vértices.
MODELO GRÁFICO ACOTADO EN UNA FIGURA
GEOMÉTRICA CON SOLUCIONES MÚLTIPLES
Se denomina modelo gráfico acotado en una
figura geométrica con soluciones múltiples a un
problema que se encuentra restringido bajo un
área factible en la cual la función objetivo alcanza
infinitos valores óptimos que corresponden a los
puntos del segmento situado entre dos vértices
de la región factible (véase la figura 4.19).
En estos casos la función objetivo es paralela a
una de las restricciones.
MODELO GRÁFICO NO ACOTADO SIN
SOLUCIÓN
Se denomina modelo gráfico no acotado sin solución a un
problema que se encuentra restringido bajo un área factible
no acotada, donde la función objetivo toma infinitos valores
sin llegar a una solución específica y por consiguiente no
óptima.
Estos tipos de modelos no acotados son “patológicos”.
Tal vez el modelo fue mal formulado debido a que no se
incluyó una o varias restricciones importantes, o tal vez a
causa de errores al capturar los datos en un programa de
software.
MODELO GRÁFICO NO FACTIBLE SIN
SOLUCIÓN
Se denomina modelo gráfico no factible sin solución a
un problema que es inconsistente en sus restricciones;
es decir, el modelo carece de una combinación de
valores para las variables de decisión que satisfaga
simultáneamente todas las restricciones.
La infactibilidad depende solamente de las
restricciones y no tiene nada que ver con la función
objetivo.