Metodo Grafico

Vista previa del material en texto

Investigación
Operativa
Programación Lineal
 Método Gráfico
Profesor: Ing. Carlos A. Martin
E-mail: ing_carlos_martin@hotmail.com
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
INTRODUCCIÓN A LA PL
¿Qué es un problema de PL?: Función lineal, desigualdad 
lineal. 
Características de un problema de PL: Objetivos, 
Restricciones, F. O., interpretación de variables. Ejemplo 
Prototipo. 
Formulación matemática de problemas de PL: Identificación 
de las V. D. y sus correlaciones con los coeficientes 
tecnológicos, recursos y contribuciones económicas. 
Ing. Carlos Martin
SOLUCIÓN GRÁFICA DE PROBLEMAS BIDIMENSIONALES DE PL
Observación de algunos aspectos técnicos:
Punto Extremo, 
Vértice adyacente,
Solución Única,
Redundancia,
Polígono Abierto
 Solución no Acotada: Ilimitabilidad,
 Solución Acotada
 Más de una solución óptima, 
Imposibilidad, 
Degeneración. 
Ejemplos.
Ing. Carlos Martin
PRESENTACIÓN
En esta unidad se presenta el método de la solución gráfica de problemas de PL incluyendo problemas 
de maximización y minimización.
OBJETIVO GENERAL
Al finalizar el modulo el estudiante debe estar en capacidad de solucionar un problema de pl
utilizando el método gráfico; así como interpretar correctamente la solución y analizar el consumo 
de recursos.
OBJETIVOS ESPECÍFICOS
Graficar las restricciones con base en ecuaciones lineales para determinar el área factible de 
solución.
Graficar la F. O. para establecer el punto o puntos de solución óptima de problemas de PL.
Establecer la solución óptima del problema mediante el uso de ecuaciones simultáneas.
Interpretar la solución del problema con base en el planteamiento y formulación del problema; así 
como el respectivo análisis de consumo de recursos.
COMPETENCIAS
El estudiante tendrá la capacidad de utilizar el método gráfico de solución de problemas de PL; y con 
base en ésta interpretar el tipo de solución del problema.
INDICADORES DE LOGRO
El estudiante deberá demostrar el manejo en el planteamiento de modelos de PL, obtener la solución 
a través del método gráfico e interpretar la solución.
CONOCIMIENTOS PREVIOS
Gráfica de las funciones lineales.
Solución algebraica de sistemas de ecuaciones lineales.
Concepto de máximos y mínimos en una gráfica.
Ing. Carlos Martin
MODELO GENERAL DE OPTIMIZACIÓN
Elementos principales:
• Variables
• F. O.
• Restricciones
Es posible reducir el problema real a través de ciertas simplificaciones a:
• P. L., P. no L., P. D., etc.
• De lo contrario se recurre a la Simulación.
Ing. Carlos Martin
PROBLEMA DE OPTIMIZACIÓN DE DOS V. DE D.
Este es un problema típico en la teoría de optimización: la maximización (o
minimización) de una función real de variables reales (a veces una sola
variable) sujeta a un número de restricciones (a veces este número es cero).
La función f se llama función objetivo,
x1 y x2 se llaman variables independientes o variables decisionales.
El problema es encontrar valores reales para x1 y x2, que satisfagan las
restricciones (1.2), (1.3) y (1.4), los cuales introducidos en (1.1) hagan que f
(x1,x2) tome un valor no menor que para cualquier otro par x1,x2.
Ing. Carlos Martin
CONCEPTOS BÁSICOS DE OPTIMIZACIÓN
• La FO Z = f (X1,X2) es no lineal.
• Tiene el mismo valor en todos 
los puntos de cada línea 
(Isolínea), de modo que los 
contornos pueden asimilarse a 
las isobaras (o isotermas) de un 
mapa climático.
• La restricción h1 (X1,X2) es no 
lineal.
La solución del problema es:
Z = 1
Ing. Carlos Martin
Ing. Carlos Martin
PROGRAMACION LINEAL (PL)
Es un problema de optimización, donde:
 Maximiza (o minimiza) una función lineal de variables de
decisión: La función objetivo
 Los valores de las variables de decisión tienen que
satisfacer un conjunto de restricciones
 Cada restricción tiene que ser una ecuación o una
desigualdad lineal.
 Hay una restricción de signo para c/variable: > 0; ≤ 0; SRS
Ing. Carlos Martin
PROGRAMACION LINEAL (PL)
La PL es una caso particular del problema general de 
optimización: la FO y las restricciones son lineales en 
cada una de las variables de decisión y estas son no 
negativas.
PROBLEMA DE PROGRAMACION LINEAL DE DOS V. DE D.
Consideremos el caso de maximización y que el n° de 
variables de decisión genuinas es k = 2
Ing. Carlos Martin
Es posible transformar las inecuaciones en igualdades introduciendo 
las variables de holgura (V. H.).
Las V. de H. no tienen un beneficio (su coeficiente de beneficio = 0), 
representan físicamente los sobrantes de cada recurso.
i = 1, 2,3 ,4, 5
Ing. Carlos Martin
EJEMPLO
Gepetto S.L., manufactura muñecos y trenes de madera. 
Cada muñeco:
• Produce un beneficio neto de 3 €.
• Requiere 2 horas de trabajo de acabado.
• Requiere 1 hora de trabajo de carpintería.
Cada tren:
• Produce un beneficio neto de 2 €.
• Requiere 1 hora de trabajo de acabado.
• Requiere 1 hora trabajo de carpintería. 
Cada semana Gepetto puede disponer de:
• Todo el material que necesite.
• Solamente 100 horas de acabado.
• Solamente 80 horas de carpintería.
También:
• La demanda de trenes puede ser cualquiera (sin límite).
• La demanda de muñecos es como mucho 40.
Si quiere max. beneficios: Cuántos muñecos y trenes deben fabricar?
Ing. Carlos Martin
Variables de 
Decisión
x = nº de muñecos
producidos a la
semana
y = nº de trenes
producidos a la
semana
Función Objetivo
En cualquier PPL, la decisión a tomar
es como maximizar (normalmente el 
beneficio) o minimizar (el coste) de 
alguna función de las variables de 
decisión. 
Esta función a maximizar o minimizar
se llama función objetivo. 
Max z = 3x + 2y
El objetivo de Gepetto es elegir
valores de x e y para maximizar
3x + 2y. 
Usaremos la variable z para 
denotar el valor de la función
objetivo. 
La función objetivo de Gepetto
es:
ESTE PROBLEMA ES UN EJEMPLO TÍPICO DE UN PROBLEMA DE PL
Restricciones
Son desigualdades que
limitan los posibles
valores de las variables 
de decisión.
En este problema las 
restricciones vienen
dadas por la 
disponibilidad de horas
de acabado y carpintería
y por la demanda de 
muñecos.
También suele haber
restricciones de signo o 
no negatividad:
x ≥ 0
y ≥ 0
Ing. Carlos Martin
Restricción 1: no más de 100 horas de tiempo de acabado pueden ser usadas.
Restricción 2: no más de 80 horas de tiempo de carpinteria pueden ser usadas.
Restricción 3: limitación de demanda, no deben fabricarse más de 40 muñecos.
Estas tres restricciones pueden expresarse matematicamente por las 
siguientes desigualdades:
Restricción 1: 2 x + y ≤ 100
Restricción 2: x + y ≤ 80
Restricción 3: x ≤ 40
Cuando x e y crecen, la función objetivo de Gepetto también crece. Pero
no puede crecer indefinidamente porque, para Gepetto, los valores de x e y 
están limitados por las siguientes tres restricciones:
RESTRICCIONES
Además, tenemos las restricciones de signo: x ≥ 0 e y ≥ 0
Ing. Carlos Martin
x ≥ 0 (restricción de signo)
y ≥ 0 (restricción de signo)
Muñeco Tren
Beneficio 3 2
Acabado 2 1 ≤ 100
Carpintería 1 1 ≤ 80
Demanda ≤ 40
FORMULACIÓN MATEMÁTICA DEL PPL
Max z = 3x + 2y (función objetivo)
2 x + y ≤ 100 (acabado)
x + y ≤ 80 (carpinteria)
x ≤ 40 (demanda muñecos)
Variables de Decisión x = nº de muñecos producidos a la semana
y = nº de trenes producidos a la semana
Max z = 3x + 2y (función objetivo)
Sujeto a (s.a:)
2 x + y ≤ 100 (restricción de acabado)
x + y ≤ 80 (restricción de carpinteria)
x ≤ 40 (restricción de demanda de muñecos)
x ≥ 0 (restricción de signo)
y ≥ 0 (restricción de signo)
Para el problema de Gepetto, combinando las restricciones 
de signo x ≥ 0 e y ≥ 0 con la función objetivo y las 
restricciones, tenemos el siguiente modelo de optimización:
FORMULACIÓN MATEMÁTICA DEL PPL
Ing. Carlos Martin
La estructura general de nuestro problema es:
Ing. Carlos Martin
Ing. Carlos Martin
Ing.Carlos Martin
Región Factible
• La región factible de un PPL es el conjunto de todos los puntos que 
satisfacen todas las restricciones. 
• Es la región del plano delimitada por el sistema de desigualdades 
que forman las restricciones.
Ing. Carlos Martin
x = 40 e y = 20 está en la región 
factible porque satisfacen todas 
las restricciones de Gepetto.
Sin embargo, x = 15, y = 70 no 
está en la región factible porque 
este punto no satisface la 
restricción de carpintería
[15 + 70 > 80].
Restricciones de Gepetto:
2x + y ≤ 100 (restricción finalizado)
x + y ≤ 80 (restricción carpintería)
x ≤ 40 (restricción demanda)
x ≥ 0 (restricción signo)
y ≥ 0 (restricción signo)
Ing. Carlos Martin
Recuerda que:
• La región factible en cualquier PPL 
está limitada por segmentos (es un 
polígono, acotado o no). 
• La región factible de cualquier PPL 
tiene solamente un número finito de 
vértices.
• Cualquier PPL que tenga solución
óptima tiene un vértice que es óptimo.
Ing. Carlos Martin
SOLUCIÓN ÓPTIMA
La mayoría de los PPL tienen solamente una
solución óptima. Sin embargo, algunos PPL no 
tienen solución óptima, y otros PPL tienen un 
número infinito de soluciones.
Más adelante veremos que la solución del PPL de 
Gepetto es x = 20 e y = 60. 
Esta solución da un valor de la función objetivo de:
z = 3x + 2y = 3·20 + 2·60 = 180 €
Cuando decimos que x = 20 e y = 60 es la solución óptima, estamos
diciendo que, en ningún punto en la región factible, la función objetivo
tiene un valor (beneficio) superior a 180.
Para un problema de maximización, una solución
óptima es un punto en la región factible en el cual la 
función objetivo tiene un valor máximo. 
Para un problema de minimización, una solución
óptima es un punto en la región factible en el cual la 
función objetivo tiene un valor mínimo.
Se puede demostrar 
que la solución 
óptima de un PPL 
está siempre en la 
frontera de la región 
factible, en un 
vértice (si la 
solución es única) o 
en un segmento 
entre dos vértices 
contiguos (si hay 
infinitas soluciones)
Ing. Carlos Martin
2x + y = 100
Cualquier PPL con sólo dos 
variables puede resolverse
gráficamente.
Por ejemplo, para representar
gráficamente la primera
restricción, 2x + y ≤ 100 :
Dibujamos la recta 2x + y = 100
20
20 40 60 80
40
60
80
100
Y
X
Elegimos el semiplano que
cumple la desigualdad: el 
punto (0,0) la cumple
(2·0 + 0 ≤ 100),
así que tomamos el 
semiplano que lo contiene.
Ing. Carlos Martin
Representación Gráfica de las Restricciones
Dibujar la Región Factible
Puesto que el PPL de Gepetto tiene dos variables, se puede
resolver gráficamente. 
La región factible es el conjunto de todos los puntos que
satisfacen las restricciones:
2 x + y ≤ 100 (restricción de acabado)
x + y ≤ 80 (restricción de carpintería)
x ≤ 40 (restricción de demanda)
x ≥ 0 (restricción de signo)
y ≥ 0 (restricción de signo)
Vamos a dibujar la región factible que satisface estas restricciones.
Ing. Carlos Martin
Y
X
20
20 40 60 80
40
60
80
100
2x + y = 100
Restricciones
2 x + y ≤ 100
x + y ≤ 80
x ≤ 40
x ≥ 0
y ≥ 0
DIBUJAR LA REGIÓN FACTIBLE
Teniendo en 
cuenta las 
restricciones de 
signo (x ≥ 0, y ≥ 0), 
nos queda:
Ing. Carlos Martin
Y
X
20
20 40 60 80
40
60
80
100
x + y = 80
Restricciones
2 x + y ≤ 100
x + y ≤ 80
x ≤ 40
x ≥ 0
y ≥ 0
DIBUJAR LA REGIÓN FACTIBLE
Ing. Carlos Martin
Y
X
20
20 40 60 80
40
60
80
100
x = 40
Restricciones
2 x + y ≤ 100
x + y ≤ 80
x ≤ 40
x ≥ 0
y ≥ 0
DIBUJAR LA REGIÓN FACTIBLE
Ing. Carlos Martin
Y
X
20
20 40 60 80
40
60
80
100
Restricciones
2 x + y ≤ 100
x + y ≤ 80
x ≤ 40
x ≥ 0
y ≥ 0
Dibujar la región factible
Ing. Carlos Martin
Y
X
20
20 40 60 80
40
60
80
100
Restricciones
2 x + y ≤ 100
x + y ≤ 80
x ≤ 40
x ≥ 0
y ≥ 0
DIBUJAR LA REGIÓN FACTIBLE
Ing. Carlos Martin
Y
X
20
20 40 60 80
40
60
80
100
2x + y = 100
x + y = 80
x = 40
La intersección 
de todos estos 
semiplanos 
(restricciones) 
nos da la región 
factible
Región
Factible
DIBUJAR LA REGIÓN FACTIBLE
Ing. Carlos Martin
Y
X
20
20 40 60 80
40
60
80
100
2x + y = 100
x + y = 80
x = 40
Región
Factible
La región factible (al 
estar limitada por 
rectas) es un polígono.
En esta caso, el 
polígono ABCDE.
A
B
C
D
E
Como la solución 
óptima está en alguno 
de los vértices (A, B, C, 
D o E) de la región 
factible, calculamos 
esos vértices.
Vértices de la región factible
Restricciones
2 x + y ≤ 100
x + y ≤ 80
x ≤ 40
x ≥ 0
y ≥ 0
Ing. Carlos Martin
Región
Factible
E(0, 80)
(20, 60)
C(40, 20)
B(40, 0)
A(0, 0)
Vértices de la región factible
Los vértices de la región factible 
son intersecciones de dos 
rectas. El punto D es la 
intersección de las rectas
2x + y = 100
x + y = 80
La solución del sistema x = 20, 
y = 60 nos da el punto D.
20
20 40 60 80
40
60
80
100
Y
X
D
B es solución de
x = 40
y = 0
2x + y = 100
x = 40
x + y = 80
C es solución de
x = 40
2x + y = 100
E es solución de
x + y = 80
x = 0
Ing. Carlos Martin
Investigación
Operativa
Resolución Gráfica
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Método Gráfico
 Procedimiento
• Representar cada restricción, encontrar la región
factible y dibujar la pendiente del funcional .
• Trasladamos la FO (en el sentido del crecimiento-
MAX o del decrecimiento-MIN) por todo el
polígono conservando su forma paralela con la
original, la detenemos en el ultimo punto de
contacto entre el convexo y el funcional.
• Allí se encuentra la solución óptima (vértice/s).
Ing. Carlos Martin
Método Gráfico
VENTAJAS
 Rico en materia de interpretación de 
 Resultados
 Análisis de sensibilidad. 
DESVENTAJAS
 Limitado en cuanto al número de variables 
 2 si es un gráfico 2D
 3 si es 3D)
Ing. Carlos Martin
Resolución Grafica de un PL de dos Variables
Ing. Carlos Martin
Resolución Gráfica: Representación de la Pendiente del Funcional “Z”
Ing. Carlos Martin
Resolución Gráfica
Ing. Carlos Martin
Solución Analítica
Ing. Carlos Martin Ing. Carlos Martin
Interpretación de la Solución del Problema
• X1: Cantidad a producir del Producto 1 = 3,5 U. de P. 
• X2: Cantidad a producir del Producto 2 = 1,5 U. de P.
• Z: Valor del Funcional = 18,5 U. M.
Análisis del Consumo de Recursos
Reemplazando en cada restricción los valores de las variables de 
decisión genuinas, podemos calcular los valores de las variables de 
holgura, es decir, podemos saber cuanto es la cantidad de recurso 
sobrante, o dicho de otra manera, cual fue el consumo de cada 
uno de los recursos.
• R1 sobrante , R2 y R3 agotados
• Variables básicas y variables no básicas
Ing. Carlos Martin
Tipos de Restricciones
•Hay 2:
•Restricción Activa:
Cuando el Recurso correspondiente a esa 
restricción está Agotado.
•Restricción Inactiva: Cuando el Recurso
correspondiente no está agotado, entonces 
hay un sobrante
Ing. Carlos Martin
Max z = 3x + 2y (función objetivo)
Sujeto a (s.a:)
2 x + y ≤ 100 (restricción de acabado)
x + y ≤ 80 (restricción de carpinteria)
x ≤ 40 (restricción de demanda de muñecos)
x ≥ 0 (restricción de signo)
y ≥ 0 (restricción de signo)
Para el problema de Gepetto tenemos el siguiente modelo de 
optimización:
Resolución Gráfica de Nuestro Ejemplo con GLP
Variables de Decisión x = nº de muñecos producidos a la semana
y = nº de trenes producidos a la semana
En GLP Hacemos: x → X1 nº de muñecos producidos a la semana
y → X2 nº de trenes producidos a la semana
Ing. Carlos Martin
Y
X
20
20 40 60 80
40
60
80
100
Región
Factible
(0, 80)
(20, 60)
(40, 20)
(40, 0)
(0, 0)
Max z = 3x + 2y
z = 0 z = 100
z = 180
Para hallar la 
solución óptima, 
dibujamos las 
rectas en las 
cuales los puntos
tienenel mismo
valor de z.
La figura muestra
estas lineas para
z = 0, z = 100, y z 
= 180
Resolución gráfica
Ing. Carlos Martin
Región
Factible
(0, 80)
(20, 60)
(40, 20)
(40, 0)
(0, 0)
Max z = 3x + 2y
z = 0 z = 100
z = 180
La última recta de z 
que interseca (toca) 
la región factible
indica la solución
óptima para el PPL. 
Para el problema de 
Gepetto, esto ocurre
en el punto D
(x = 20, y = 60).
20
20 40 60 80
40
60
80
100
Y
X
Resolución gráfica
b = 9 0
D
Z = b C2 => Z = (90) (2) => 
=> Z = 180
Ing. Carlos Martin
Investigación
Operativa
Resolución Gráfica con GLP
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Software GLP y PHPSimplex
GLP
• El software Graphic Linear Optimizer (GLP) es una 
herramienta que permite resolver gráficamente modelos de 
Programación Lineal.
• GLP fue desarrollado bajo la supervisión del profesor Jeffrey 
Moore (Ph. D) perteneciente a la Universidad de Stanford en 
Estados Unidos.
• https://www.youtube.com/watch?v=8j3400gdJvw
• https://www.youtube.com/watch?v=9cfKFTYskxs
PHPSimplex
• http://www.phpsimplex.com/simplex/simplex.htm
Ing. Carlos Martin
https://www.youtube.com/watch?v=9cfKFTYskxs
https://www.youtube.com/watch?v=9cfKFTYskxs
http://www.phpsimplex.com/simplex/simplex.htm
Resolución con GLP
Ing. Carlos Martin
Resolución con GLP
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110
0
5
10
15
20
25
30
35
40
45
50
55
60
65
70
75
80
85
90
95
100
105
110
X2
X1
 Acabado: 2 X1 + 1 X2 = 100
 Carpinteria: 1 X1 + 1 X2 = 80
 Demanda: 1 X1 + 0 X2 = 40
Payoff: 3 X1 + 2 X2 = 180
Optimal Decisions(X1,X2): ( 20, 60)
 Acabado: 2X1 + 1X2 <= 100
 Carpinteria: 1X1 + 1X2 <= 80
 Demanda: 1X1 + 0X2 <= 40
Ing. Carlos Martin
Investigación
Operativa
Resolución Analítica
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Región
Factible
(0, 80)
(20, 60)
(40, 20)
(40, 0)
(0, 0)
Max z = 3x + 2y
También podemos encontrar la 
solución óptima calculando el 
valor de z en los vértices de la 
región factible.
Vértice z = 3x + 2y
(0, 0) z = 3·0+2·0 = 0
(40, 0) z = 3·40+2·0 = 120
(40, 20) z = 3·40+2·20 = 160
(20, 60) z = 3·20+2·60 = 180
(0, 80) z = 3·0+2·80 = 160
20
20 40 60 80
40
60
80
100
Y
X
La solución óptima es:
x = 20 muñecos
y = 60 trenes
z = 180 € de beneficio
Resolución Analítica
Ing. Carlos Martin
Investigación
Operativa
Problemas de Minimización
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Un problema de minimización
Dorian Auto fabrica y vende coches y furgonetas. 
La empresa quiere emprender una campaña
publicitaria en TV y tiene que decidir comprar los 
tiempos de anuncios en dos tipos de programas: 
del corazón y fútbol.
• Cada anuncio del programa del corazón es visto por 6 millones de 
mujeres y 2 millones de hombres.
• Cada partido de fútbol es visto por 3 millones de mujeres y 8 millones 
de hombres.
• Un anuncio en el programa de corazón cuesta 50.000 € y un anuncio 
del fútbol cuesta 100.000 €.
• Dorian Auto quisiera que los anuncios sean vistos por lo menos 30 
millones de mujeres y 24 millones de hombres.
• Dorian Auto quiere saber cuántos anuncios debe contratar en cada tipo 
de programa para que el coste de la campaña publicitaria sea mínimo.
Ing. Carlos Martin
• Cada anuncio del programa del 
corazón es visto por 6 millones de 
mujeres y 2 millones de hombres.
• Cada partido de fútbol es visto por 3 
millones de mujeres y 8 millones de 
hombres.
• Un anuncio en el programa de 
corazón cuesta 50.000 € y un anuncio 
del fútbol cuesta 100.000 €.
• Dorian Auto quisiera que los anuncios 
sean vistos por lo menos por 30 
millones de mujeres y 24 millones de 
hombres.
• Dorian Auto quiere saber cuántos 
anuncios debe contratar en cada 
tipo de programa para que el coste 
de la campaña publicitaria sea 
mínimo.
Corazón
(x)
Fútbol
(y)
mujeres 6 3 6x + 3y ≥ 30
hombres 2 8 2x + 8y ≥ 24
Costo Anuncio
(X 1.000€)
50 100 50x +100y
Formulación del problema:
Variables de decisión: 
x = nº de anuncios en programa de corazón
y = nº de anuncios en fútbol
Min z = 50x + 100y (función objetivo en 1.000 €)
s.a: 6x + 3y ≥ 30 (mujeres)
2x + 8y ≥ 24 (hombres)
x, y ≥ 0 (no negatividad)
Formulación del Problema
Ing. Carlos Martin
X
Y
2 4 6 8 10 12 14
14
12
10
8
6
4
2
Min z = 50 x + 100y
s.a. 6x + 3y ≥ 30
2x + 8y ≥ 24
x, y ≥ 0
6x + 3y = 30
2x + 8y = 24
Dibujamos la región factible.
X
Y
2 4 6 8 10 12 14
14
12
10
8
6
4
2
La región factible
no está acotada
Región
Factible
Calculamos los vértices de la región factible:
A
B
C
El vértice A es solución del 
sistema
6x + 3y = 30
x = 0
Por tanto, A(0, 10)
El vértice B es solución de
6x + 3y = 30
2x + 8y = 24
Por tanto, B(4, 2)
El vértice C es solución de
2x + 8y = 24
y = 0
Por tanto, C(12, 0)
Ing. Carlos Martin
Región
Factible
Resolvemos por el método analítico
A(0, 10)
B(4, 2)
C(12, 0)
X
Y
2 4 6 8 10 12 14
14
12
10
8
6
4
2
Vértice z = 50x + 100y
A(0, 10)
z = 50·0 + 100·10 =
= 0+10000 = 10 000
B(4, 2)
z = 50·4 + 100·2 =
= 200+200 = 400
C(12, 0)
z = 50·12 + 100·0 =
= 6000+0 = 6 000
El coste mínimo se obtiene en B.
Solución:
x = 4 anuncios en pr. corazón
y = 2 anuncios en futbol
Coste z = 400 (mil €)
Evaluamos la función objetivo z en los vértices.
Región
Factible
Resolvemos por el Método Gráfico
A(0, 10)
B(4, 2)
C(12, 0)
X
Y
2 4 6 8 10 12 14
14
12
10
8
6
4
2
El coste mínimo 
se obtiene en el 
punto B.
Solución:
x = 4 anuncios en pr. corazón
y = 2 anuncios en futbol
Min z = 50 x + 100y
s.a. 6x + 3y ≥ 30
2x + 8y ≥ 24
x, y ≥ 0
Z = 600
Z = 400
Z = b C2 => Z = (4) (100) => 
=> Z = 400 (mil €)
b=4
Z
Ing. Carlos Martin
Número de Soluciones de un PPL
Se pueden dar también las siguientes posibilidades:
• Algunos PPL tienen un número infinito de 
soluciones óptimas (soluciones óptimas múltiples ). 
• Algunos PPL no tienen soluciones factibles
(notienen región factible).
• Algunos PPL son no acotados: Existen puntos en la 
región factible con valores de z arbitrariamente
grandes (en un problema de maximización).
Los dos ejemplos anteriores, Gepetto y Dorian Auto, 
tienen, cada uno, una única solución óptima.
No en todos los PPL ocurre esto. 
Ing. Carlos Martin
Casos 
 Solución Única
 Redundancia
 Polígono Abierto
 Solución no acotada: Ilimitabilidad
 Solución acotada
 Más de una solución óptima 
 Imposibilidad
 Degeneración
Ing. Carlos Martin
Min z = 50 X1 + 100X2
s.a. 6X1 + 3X2 ≥ 30
2X1 + 8X2 ≥ 24
X1, X2 ≥ 0
 Maximización
max z = 3X1 + 3X2
s.a: 3X1 + 2X2 ≤ 120
X1 + X2 ≤ 50
X1 , X2 ≥ 0
 Minimización
Solución Única
• La restricción contiene a la región factible
max z = 3X1 + 2X2
s.a:
Consideremos el siguiente 
problema:
3X1 + 2X2 ≤ 120
X1 + X2 ≤ 50
X1 ≤ 55
X1 , X2 ≥ 0
Redundancia
REDUNDANTE
Ing. Carlos Martin
 SOLUCIÓN ACOTADA:
Polígono Abierto
 SOLUCIÓN NO ACOTADA: 
Ilimitabilidad
Max Z = 2 X1 + 2X2
s.a. -6X1 + 3X2 ≤ 9
2X1 + X2 ≥ 6
X1, X2 ≥ 0
Min Z = 2 X1 + 2X2
s.a. -6X1 + 3X2 ≤ 9
2X1 + X2 ≥ 6
X1, X2 ≥ 0
Ing. Carlos Martin
PPL No Acotado
max z = 2x – y
s.a: x – y ≤ 1
2x + y ≥ 6
x, y ≥ 0
La región factible es no acotada. 
Se muestran en el gráfico las 
rectas de nivel para z = 4 y z = 6. 
Pero podemos desplazar las 
rectas de nivel hacia la derecha
indefinidamente sin abandonar la 
región factible. 
Por tanto, el valor de z puede
crecer indefinidamente.
1
1 2 3 4
2
3
4
5
5
6
Y
X
z = 4
z = 6
Región Factible
Ing. Carlos Martin
max Z = 3X1 + 2X2
s.a:
Cualquier punto (solución)situado en el segmento AB puede ser
una solución óptima de Z =120.
3X1 + 2X2 ≤ 120
X1 + X2 ≤ 50
X1 , X2 ≥ 0
Más de Una Solución Óptima
Solucion AB
Ing. Carlos Martin
s.a:
max Z = 3x1 + 9x2
1,6X1 + 4X2 ≤ 80
X1 + 2X2 ≤ 40
X1 ,X2 ≥ 0
Degeneración
Desde el punto de vista 
practico, la condición 
indica que el modelo tiene 
al menos una restricción 
redundante
Solución Optima Degenerada
Ing. Carlos Martin
s.a:
max z = 3x1 + 2x2
La region no es convexa
3X1 + 2X2 ≤ 120
X1 + X2 ≤ 50
X1 ≥ 30
X2 ≥ 30
X1 , X2 ≥ 0
Imposibilidad
Sin soluciones factibles
No existe región factible
Ing. Carlos Martin
Ing. Carlos Martin
EJEMPLOS
•Problema de Dieta
•Problema de Producción
•Aplicación en Dietas
•Problema de Mezcla de Productos
•Plan de Manufactura
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Problema de Mezcla de Productos: 
• Se dispone de 2 ingredientes para fabricar caramelos, cuyo sabor variará dependiendo de 
la proporción en que intervengan cada uno de los ingredientes. 
• El primer ingrediente se compra a $10 por kg. y el segundo a $20 por kg. 
• El proceso de elaboración supone un costo de $5 por kg. fabricado, cuya cantidad total 
corresponde simplemente a la suma de los kg. empleados en la mezcla. 
• La demanda máxima mensual es de100 kg y el precio de venta $50 kg. 
• A la empresa no le interesa producir más de los que puede vender en el mes. 
• Por último, la composición de la masa debe contener una proporción que no supere el 50% 
del primer ingrediente y el 80% del segundo ingrediente. 
• Se requiere determinar cuántos kg. de caramelos se tienen que fabricar al mes y las 
proporciones en las que deben ser utilizados los ingredientes para obtener un máximo 
beneficio.
Ing. Carlos Martin
Variables de Decisión: 
X1: Kg a usar del ingrediente 1 en un mes 
X2: Kg a usar del ingrediente 2 en un mes
Función Objetivo: 
Obtener la máxima utilidad de la venta de los caramelos descontando los costos de producción
Maximizar z = 50*(X1 + X2) – 10*X1 – 20*X2 - 5*(X1 + X2) = 35*X1 + 25*X2
Restricciones: 
Demanda Máxima: X1 + X2 <= 100
Composición: X1/(X1 + X2) <= 50% o 0,5*X1 – 0,5*X2 <= 0 
Composición: X2/(X1 + X2) <= 80% o -0,8*X1 + 0,2*X2 <= 0
No Negatividad: X1, X2 >= 0
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
RESUMEN
• Solución de un problema de pl utilizando el método gráfico
• Interpretación de la solución y análisis del consumo de recursos.
• Grafico de las restricciones con base en ecuaciones lineales para
determinar el área factible de solución.
• Grafico de la F. O. para establecer el punto o puntos de solución óptima
• Calculo de la S. O. mediante el uso de ecuaciones simultáneas.
• El Polígono de soluciones: conjunto convexo.
• Solución optima: se encuentra al menos en un vértice de la región
factible.
• Restricción Activa (Recurso agotado).
• Restricción Inactiva (Recurso sobrante).
• Identificación de S. B. F. y de S. B. no F.
Ing. Carlos Martin
BIBLIOGRAFIA
 Prawda Witenberg J. “Métodos y Modelos de Investigación de 
Operaciones – Vol. 1 Modelos Determinísticos”. Editorial Limusa. 
©1999
 Taha Hamdy A. “Investigación de Operaciones”. Editorial Alfa 
Omega. ©1998
 Winston Wayne L.. “Investigación de Operaciones. Editorial. 
Grupo Editorial Iberoamericana. ©2005
 Hillier Frederick S. “Introducción a la Investigación de 
Operaciones. Editorial. Mc Graw Hill. ©2001
 Eppen G.D. “Investigacion de Operaciones En la Ciencia 
Administrativa. Editorial Prentice. ©2000
 Mathur-Solow – Investigación de Operaciones – Ed. Prentice Hall 
1996.
 MARIN, Isidoro. “Investigación Operativa”. UBA. Centro de 
Estudiantes Universidad Nacional de Buenos Aires. © 1970
Ing. Carlos Martin
Preguntas
Ing. Carlos Martin
Investigación
Operativa
Muchas Gracias
Profesor: Ing. Carlos A. Martin
E-mail: ing_carlos_martin@hotmail.com
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR