INVESTIGACION DE

OPERACIONES 1

Profesora Ing. Giannina Castro G

pcmagcas@[Link]
 UNIDAD 1

PROGRAMACIÓN LINEAL
Semana 2
Interpretación administrativa y análisis de sensibilidad con el
método gráfico

Objetivo de aprendizaje: Al finalizar la clase los estudiantes calculan e interpretan

conceptos como holguras, excedentes, costo reducido, precios duales, rangos de
variación permitidos de los coeficientes de la función objetivo y de los lados
derechos de las restricciones.

1. Modelo
 Prob 1
Una empresa produce dos tipos de productos, uno para el mercado nacional y el
otro para exportación. Se quiere determinar la mezcla de producción óptima para
el siguiente mes. El producto que se elabora para el mercado nacional usa en su
producción 7 unidades de la materia prima 1, 18 unidades de la materia prima 2 y
11 horas de mano de obra. El producto que se exporta utiliza en su elaboración 8
unidades de la materia prima 1, 11 unidades de la materia prima 2 y 23 horas de
mano de obra. Por política de la compañía la producción de ambos productos
debe utilizar por lo menos 56 unidades de la materia prima 1 y hasta 198 unidades
de la materia prima 2. Por motivos de la situación actual el número de horas con
las que se cuenta mensualmente ha ido variando en los últimos meses y para este
mes se prevé que se podrá contar con un máximo de 253 horas de mano de obra
en la planta de producción. Además, se presenta la siguiente restricción: cuatro
veces la producción del producto para exportación no debe ser mayor que nueve
veces la producción del producto para el mercado nacional más 36 unidades.
Tomando en cuenta el precio de venta y los costos de todo aquello utilizado en la
producción de ambos productos se ha llegado a establecer que la utilidad por
unidad del producto en el mercado nacional es de $ 200 y que la utilidad de un
producto que se exporta es de $ 500. Elabore un modelo de programación lineal
extendida y compacta.
Prob 1 (SOL)

Modelo extendido Modelo compacto

FORMATO FORMATO
Variable de Decisión (VD) Datos

Función Objetivo (FO) Max Z = C*X

Restricciones (RR) Sujeto a:

A*X <= b
Condición de No Negatividad
(CNN) X>=0
Prob 1 (SOL)
Programa Lineal (PL) Programa Lineal (PL)
[notación extendida] [notación compacta]
Max Z = 200X1 + 500X2 Datos:
Sujeto a: Xj = [X1 X2]
Cj = [200 500]
[MP1] 7X1 + 8X2 >= 56
-7X1 – 8X2 <= -56
𝐴𝑖𝑗 = 𝑏𝑖 =
[MP2] 18X1 + 11X2 <= 198
[MO] 11X1 + 23X2 <= 253
[Prod] 4X2 – 9X1 <= 36
Max Z = σ𝑖=1 ∗ ∀𝑖 =
Xi >= 0 ; i=1,2
Sujeto a:

෍ ∗ ≤
𝑖=1

Xi >= 0, para todo i

 Prob 2
La empresa Cosmética S.A. fabrica dos tipos de productos. Para producir una unidad
del producto dirigido al mercado tipo A se necesitan 15 unidades de materia prima, 20
horas de máquina y 9 horas de mano de obra. Para producir una unidad del producto
dirigido al mercado tipo B se necesitan 23 unidades de materia prima, 14 horas de
máquina y 4 horas de mano de obra. La demanda total del producto dirigido al
mercado tipo B no es mayor de 14 unidades y la demanda para el producto dirigido al
mercado tipo A no debe exceder de 10 unidades. Por políticas de la empresa son
severas y establecen: La producción del producto dirigido al mercado tipo A no debe
exceder a 12 unidades más 4 veces la producción del producto dirigido al mercado tipo
B. También se deben utilizar por lo menos 36 horas hombre en la producción total de
la empresa. Además, se requiere que la producción del producto dirigido al mercado
tipo B no exceda a cuatro veces la producción del producto dirigido al mercado tipo A
más doce unidades. La empresa cuenta con un máximo de 345 unidades de materia
prima y con una disponibilidad máxima de 280 horas de máquina. Se sabe que el
precio de venta del producto dirigido al mercado tipo A es de 400 dólares y los costos
involucrados en la producción de este tipo de producto suman 100 dólares. El precio
de venta del producto dirigido al mercado tipo B es de 500 dólares y los costos
involucrados en la producción de este tipo de producto suman 200 dólares. Formule
un modelo de programación lineal extendido y compacto..
Prob 2 (SOL)
Programa Lineal (PL)
Variable de Decisión: (VD)
Xi = Cantidad (en unidad) de productos tipo i
i: 1,2 (productos); i=1 (tipo A); i=2 (tipo B)

Función Objetivo (FO)

Max Z =

Restricciones (RR)
[MP]:
[Máq]:
[MO]:
[Demanda 1]:
[Demanda 2]:
[Producción]:
[Producción]:
Condición de No Negatividad (CNN):
Xi >= 0 ; i=1,2
 Prob 2 (SOL) Programa Lineal (PL)
Programa Lineal (PL) [notación compacta]
[notación extendida] Datos:
Xj = [X1 X2]
Max Z = 300X1 + 300X2 Cj = [300 300]
Sujeto a:
15X1 + 23X2 <= 345
20X1 + 14X2 <= 280
9X1 + 4X2 >= 36 𝐴𝑖𝑗 = 𝑏𝑖 =
X1>=10
X2<=14
X1 – 4X2 <= 12
-4X1 + X2 <= 12
XI >= 0 Max Z = σ𝑖=1 ∗ ∀𝑖 =

Sujeto a:

෍ ∗ ≤
𝑖=1

Xi >= 0, para todo i =

 Prob 3
Ejemplo 1 En la máquina cortadora de prendas de un taller de confecciones pueden procesarse un
máximo de 1500 prendas por semana. Esta semana, el taller de confecciones ha recibido la solicitud de
7 clientes por el servicio de corte de prendas, con las siguientes características:
Cliente Cantidad total máxima de Dificultad del corte Utilidad por prenda
prendas por cortar (valor / prenda) cortada (soles/prenda)
1 300 8 2.0
2 250 7 2.5
3 150 6 3.2
4 200 8 2.5
5 150 5 2.0
6 230 5 2.5
7 500 3 3.0

Es posible brindarle el servicio de corte a cada cliente por una cierta cantidad de prendas, no
necesariamente por el máximo de forma obligatoria. El valor de dificultad de corte para cada prenda
de cada pedido que se señala en la tabla indica la cantidad de esfuerzo que deben hacer los operarios
al cortar cada prenda. Un valor más alto de dificultad indica mayor esfuerzo para los operarios (valor
máximo: 10, valor mínimo: 0). Con la finalidad de que el trabajo no les demande un esfuerzo muy
grande se desea que el trabajo total a realizar tenga un valor de dificultad promedio por prenda no
mayor a 5. Identificar las variables de solución, formular el modelo de programación lineal. Resolver el
modelo y presentar el informe de la solución.
Formulación de PL
¿Quién se encuentra en esta situación de toma de decisiones?
¿Sobre qué actividad debe decidir el taller?
¿Qué desconoce el taller sobre el corte de prendas?
X1 +X2 +X3 +X4 +X5 +X6 +X7 ≤ 1500
Que puede compactarse, como veremos enseguida:
σ7𝑖=1 𝑋𝑖 ≤ 1500
El texto del ejercicio señala también que cada cliente tiene un número máximo de
prendas por cortar:
X1 ≤ 300 ….. número máximo de prendas por cortar para el cliente 1
X2 ≤ 250 ….. número máximo de prendas por cortar para el cliente 2
X3 ≤ 150 ….. número máximo de prendas por cortar para el cliente 3
X4 ≤ 200 ….. número máximo de prendas por cortar para el cliente 4
X5 ≤ 150 ….. número máximo de prendas por cortar para el cliente 5
X6 ≤ 230 ….. número máximo de prendas por cortar para el cliente 6
X7 ≤ 500 ….. número máximo de prendas por cortar para el cliente 7

Estas 7 restricciones presentadas de forma “extendida” tienen todas la misma forma

matemática y representan la misma condición para cada uno de los 7 clientes: se trata
de una familia de restricciones. Esta familia puede expresarse de manera compacta,
como veremos enseguida:
Formulación de PL
𝑋𝑖 ≤ 𝑀á𝑥𝑖moi Para i= 1,2,…7

𝑋𝑖 ≤ 𝑀á𝑥𝑖moi ∀ 𝑖 = 1, … , 7

Es lo que indica que se trata de una familia

La dificultad promedio ponderada del total de prendas por cortar no debe ser mayor a 5
es una restricción adicional, que expresada en la forma extendida es:
(8X1+7X2+6X3+8X4+5X5+5X6+3X7)/(X1+X2+X3+X4+X5+X6+X7) ≤ 5 Debe señalarse que
así como aparece escrita la expresión esta no es lineal, pues no cumple la propiedad de
aditividad. Sin embargo, este problema se soluciona pasando al lado derecho la
expresión del denominador: (8X1+7X2+6X3+8X4+5X5+5X6+3X7) ≤ 5
(X1+X2+X3+X4+X5+X6+X7) Al igual que la primera restricción, esta expresión también
puede expresarse de manera compacta
 Prob 4
En uno de los talleres de producción de una fábrica de muebles de madera, se debe definir
el plan de producción de cuatro modelos de sillas, maximizando utilidades. Los datos
relacionados con requerimientos, por unidad, son:
Planchas Listones de Mano de Costo de Precio de
Modelos
de madera madera obra producción venta
CLÁSICO 1/2 1.5 40 min S/ 30 S/ 80
EJECUTIVO 1/2 2 30 min S/ 40 S/ 90
JUNIOR 1/4 1.5 30 min S/ 34 S/ 75
FAMILIAR 1/4 2 25 min S/ 35 S/ 70
Además, se debe tener en cuenta que:
• En el taller, la producción está a cargo de cuatro operarios que trabajan de lunes a
sábado, 8 horas diarias.
• En el almacén de materias primas, se cuenta con 150 planchas de madera y 800 listones
para la próxima semana.
• El área de ventas calcula que las unidades totales vendidas durante la próxima semana
serán por lo menos 400; de las cuáles, máximo 60 serán del modelo clásico y, por los
menos 110 corresponderán al modelo ejecutivo.
Suponiendo que la empresa venderá todas los muebles que puede producir,
formule el problema como un modelo de programación lineal que permita
maximizar las utilidades de la empresa.
Presente el modelo en programación algebraica extendida y compacta.
Prob 5
Una planta química fabrica dos tipos de productos: A1 y A2, los cuales son elaborados sobre la base de las
siguientes materias primas: M1, M2 y M3. La siguiente tabla muestra el requerimiento (en kilogramos) de cada
materia prima por kilogramo de producto fabricado, así como la disponibilidad de cada materia prima (kg) y
costos asociados (S/ por kg) para el próximo periodo de planificación
Requerimiento de MP
Materias Disponibilidad Costo
(por Kg de producto)
Primas (kg) (S/ por Kg)
Producto A1 Producto A2
M1 4 10 50 000 5.6
M2 12 4 72 000 4.3
M3 16 7 46 000 7.9

Además, se debe tener en cuenta que en el proceso de producción se consume también energía eléctrica,
agua y tiempo de máquina; la información de los consumos de estos recursos por kilogramo de producto
fabricado, así como los costos asociados, se presentan en la siguiente tabla:

Energía Agua Tiempo de máquina Precio de venta

Productos
(Kw-h/kg) (m3 / kg) (H-Máq./kg (S/ por unidad)
A1 3 0.8 0.15 15
A2 2 1.2 0.18 20
Costo del recurso S/. 1.7 por Kw-h S/. 0.4 por m3 S/. 30 por H-Máq

La disponibilidad de tiempo de máquina es de 600 horas-máquina, además se sabe que el presupuesto

disponible para todos los gastos es de S/. 480 000. Formule el modelo de programación lineal que permita
determinar el plan de producción que maximice las ganancias. Todo lo que se produzca se podrá vender
Prob 5 (SOL)

Formule el modelo de PL compacto

 Prob 6
Una empresa agrícola prepara una mezcla de alimento para ganado. El alimento es una
mezcla de maíz y soya con la siguiente composición:

Proteínas Fibras Minerales Azúcar

Alimento
(mg) (mg) (mg) (g)
Maíz 0.09 0.02 0.3 3.8
Soya 0.60 0.06 0.7 1.8

La bolsa de alimento debe contener por lo menos 3.6 mg de proteínas, máximo 4.2 mg de fibras y al
menos 2.4 mg de minerales. Sabiendo que se quiere un alimento con el menor contenido de azúcar
posible, se pide lo siguiente: Defina las variables de decisión y en qué unidades se expresan y escriba el
modelo de programación lineal
 Prob 7
Juanito se dedica a la elaboración de tres tipos de cebiche en bolsa para las playas de Lima, los cuales
gozan de gran aceptación por parte de sus clientes. Los ingredientes principales son: pescado,
conchas negras, calamar, cebolla y camote. La siguiente tabla muestra la composición de los
ingredientes que se utilizan por cada bolsa:

Pescado Conchas Cebolla Camote

Tipo Calamar (Kg)
(kg) negras (Kg) (unid) (unid)
Tradicional 1 0 0 3 3
Especial 0 0.5 0 1 0
Mixto 0.5 0.1 0.3 3 3

La demanda de cebiche para este fin de semana no constituye un factor limitante. No obstante, Juanito
debe vender como mínimo 500, 200 y 300 bolsas de cebiche tradicional, especial y mixto,
respectivamente, para asegurar la rentabilidad de su negocio. El precio de venta de cada tipo de
cebiche se muestra a continuación:
Tipo de cebiche Precio de venta (soles/bolsa)
Tradicional 30
Especial 35
Mixto 28
Los costos de los ingredientes y su disponibilidad son:

Pescado Conchas Calamar Cebolla Camote

Ingrediente
(kg) negras (Kg) (Kg) (unid) (unid)
Ingrediente 24 S/ Kg 30 S/ Kg 18 S/ Kg 0.5 S/unid 0.1 S/unid
Disponibilidad 5000 unid
1000 Kg 200 Kg 100 Kg 5000 unid

Identificar las variables de decisión y formular el modelo de programación lineal en la forma compacta.
TAREA 1
Debido a la gran aceptación del cebiche en bolsa, ahora Juanito está planificando para el próximo
verano la venta de sopa en botellón. Las sopas de mayor demanda son: especial de pollo, marítima de
mariscos y tradicional de habas. Los ingredientes principales son: pollo, mariscos, habas y alverjas. La
siguiente tabla muestra el requerimiento de los ingredientes que se utilizan por cada botellón de 3
litros, el requerimiento (Kg / botellón) es el siguiente:

Tipo de sopa Pollo mariscos Habas Alverjas

Especial de pollo 0.30 0 0.25 0.25
Marítima de mariscos 0 0.30 0.10 0.50
Tradicional de habas 0.15 0.15 1 0.25

Juanito debe vender como mínimo 250, 100 y 300 botellones de sopa especial de pollo, marítima de
mariscos y tradicional de habas, respectivamente, para asegurar la rentabilidad de su negocio. El precio
de venta de cada tipo de sopa se muestra a continuación:
Tipo de sopa Precio de venta (soles/botellón)
Especial de pollo 30
Marítima de mariscos 35
Tradicional de habas 25
Formulación de PL
El costo y la disponibilidad de cada ingrediente con que Juanito cuenta para que él mismo prepare
sus sopas son los siguientes:

Ingrediente Pollo mariscos Habas Alverjas

Costo (s/Kg) 20 30 5 10
Disponibilidad (Kg) 80 40 200 150

Además de preparar él mismo sus sopas, Juanito puede comprar sopas en botellón ya preparadas a sus
tías Julia y Bertha, con la siguiente restricción: “Para cada tipo de sopa, la cantidad de botellones que
Juanito compre a sus tías en total de ese tipo, no debe ser superior a la cantidad de botellones de sopa
de ese tipo que Juanito prepare”. Los costos de compra por cada tipo de sopa y por cada tía se
muestran a continuación (Costo de compra soles/botellón)

Tipo de sopa Tía Julia Tía Bertha

Especial de pollo 20 25
Marítima de mariscos 20 30
Tradicional de habas 30 20

Según la información brindada, debe definir las variables de decisión y formular el modelo de
programación lineal en la forma compacta.
FORMULACION MATEMATICA COMPACTA
SOLUCION SIMPLEX
Introducción
George Bernard Dantzig [Físico y Matemático]

George Bernard Dantzig fue un profesor de computación,

físico y matemático estadounidense. Su padre era un
matemático ruso que trabajó con Poincaré en París y que
acabó emigrando a Estados Unidos. Dantzig fue
galardonado con diversos premios como, por ejemplo, el
premio de Teoría John Von Neumann, por su trabajo sobre
programación lineal. Falleció en 2005 por diabetes, a la
edad de 90 años.
Cierto día, cuando estudiaba en la Universidad de Berkeley, Dantzig llegó tarde a clase
y se encontró en la pizarra dos problemas estadísticos que el profesor había puesto
como ejemplos de problemas aún no resueltos, pero él pensó que eran problemas de
clase. Aunque le costó más de lo que esperaba, finalmente encontró la solución ya que
al ser trabajos de clase pensó que la solución debía ser asequible. Dantzig entregó los
ejercicios pensando que los entregaba fuera de plazo. Pocos días después, el profesor le
visitó para anunciarle que lo que había resuelto no eran ejercicios de clase sino
problemas que nadie había conseguido resolver y le propuso publicar una de sus
soluciones en una revista científica. 23
Temario

Algoritmo SIMPLEX

Modelo de Modelo de
Maximización Minimización

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 24

 FORMA ESTÁNDAR DE UN PPL
Un problema de Programación Lineal se dice que está en su forma
estándar si cumple las siguientes condiciones:

E1) Todos los términos del lado derecho de las restricciones deben
ser constantes mayores o iguales que cero.

E2) Todas las restricciones deben estar en forma de igualdades.

E3) Todas las variables deben ser mayores o iguales que cero.

Muchos problemas de P.L. cuando son formulados no siempre

aparecen en su forma estándar desde un inicio por lo que es
necesario hacer ciertas transformaciones.
Recordemos de la Semana 1:
Ejemplo.- Pasar el siguiente
problema a su forma estándar:
El método SIMPLEX se
MIN 3X1 – 2X2 + 4X3 aplica sólo a modelos que
s.a: tienen restricciones del
X1 + 2X3  5 – 3X2
tipo menor igual o igual

4X1 + 3X2 – 2X3  -13

2X1 + X2 + X3 = 12
X1, X2, X3 >= 0

Modelo en forma estándar:

Min 3X1 – 2X2 + 4X3

El método parte de dos afirmaciones
importantes:

[Link] conjunto de posibles soluciones o conjunto

factible de cualquier problema de programación
lineal puede representarse mediante un poliedro
convexo.

[Link] un problema de programación lineal tiene

una solución óptima y finita, ésta estará en
un vértice del poliedro convexo que representa al
problema.

El algoritmo simplex parte de uno de los vértices

del poliedro, y verifica si es el óptimo; si no lo es,
busca un nuevo vértice adyacentes que va
mejorando el valor de la función objetivo. Se
continúa iterando hasta llegar al vértice que
representa la solución óptima.
 Ejemplo:

MAX 2x + y
s.a:
Gráficamente:
x+y  0
y x, y  0 MAX 2x + y
S1
s.a: (0,0,10)
(0,10)
10 x + y + S1 = 10
x, y ,S1  0

(10,0,0)
x
(10,0)
(0,0) 10 x (0,10,0)

 Solución Optima: x = 10
 Solución Optima : x=10 y y =0
S1 = 0
 Máximo : 20
y=0
 Máximo : 20

Conclusiones

1) Existe una relación biunívoca entre los puntos del espacio de soluciones factibles de un
problema y el de su correspondiente forma estándar.
2) A cada punto extremo le corresponde otro punto extremo de la forma estándar
3) A la solución óptima le corresponde la solución óptima de la forma estándar.
4) El valor óptimo no varía.
Modelos de maximización
 MODELO DE MAXIMIZACIÓN

PROBLEMA:
Una empresa produce pintura para interiores y exteriores y se tiene
la siguiente información para la elaboración de una tonelada de
pintura:
Tipo de Cantidad de Materia Prima Utilidad
pintura operarios (Ton) (miles de soles)
Interior 1 2 2
Exterior 2 1 3
Disponibilidad 6 8

¿cuánto y qué tipo de pintura se debe producir para maximizar la utilidad?

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 31

Formulación

Modelo de PL
X1: Cantidad de toneladas de pintura para interiores

X2: Cantidad de toneladas de pintura para exteriores

MAX Z = 2 X 1+3 X 2 Maximizar utilidad

S .a.
1X 1 + 2 X 2  6 Disponibilidad de operarios

2 X 1 + 1X 2  8 Disponibilidad de materia prima

X1, X 2  0

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 32

Modelo Estándar
Max Z= 2 x 1 + 3 x2
sujeto a:
1X1 + 2X2 ≤ 6
2X11 + 1X2 ≤ 8
x1 , x2 ≥ 0
Uso de la variables de holgura
1X1 + 2X2 ≤ 6 2X11 + 1X2 ≤ 8
1X1 + 2X2 + h1 = 6 2X11 + 1X2 + h2 = 8

1X1 + 2X2 + h1 = 6
2X1 + 1X2 + h2 = 8
Sistema de ecuaciones lineales no cuadradas
33
Tablero Simplex*
Max Z= 2 x 1 + 3x 2 + 0 h 1 + 0 h 2
sujeto a:
1 x1 + 2 x2 + h1 =6
2 x1 + x2 + h2 =8
x 1 , x 2, h 1 , h 2 ≥ 0

Función Objetivo: 2 x 1 + 3x 2 + 0 h 1 + 0 h 2 = Z
Z - 2 x1 - 3 x2 + 0 h1 + 0 h2 = 0

Tablero inicial
z x1 x2 h1 h2 LD
1 -2 -3 0 0 0
0 1 2 1 0 6
0 2 1 0 1 8
* George Dantzing 34
Solución básica factible inicial
z x1 x2 h1 h2 LD
1 -2 -3 0 0 0
0 1 2 1 0 6
0 2 1 0 1 8

x1 = 0.0
Solución Inicial
x2 = 0.0
SBFI = SOLUCION BASICA FACTIBLE INICIAL h1 = 6.0
Condición de latencia, todo se dispone al inicio. h2 = 8.0
z0 = 0.0

35
Tablero de solución óptima
Finalmente, se tiene:
z x1 x2 h1 h2 LD
1 0 0 4/3 1/3 32/3
0 0 1 2/3 -(1/3) 4/3
0 1 0 -(1/3) 2/3 10/3
Gauss Jordan para las iteraciones
x1 = 10/3
x2 = 4/3
Solución óptima h1 = 0.0
Condición máxima; a partir de esta solución, cualquier h2 = 0.0
otra combinación lineal disminuye el valor de Z. z* = 32/3
36
PROCESO DE SOLUCION
Tablero inicial
Z X1 X2 h1 h2 LD