INVESTIGACIN DE
OPERACIONES 2
MIGUEL NGEL ORUNA RODRGUEZ
INVESTIGACIN DE
OPERACIONES 2
LOGRO DEL CURSO:
UNIDAD I
PROGRAMACIN ENTERA Y
DINMICA DETERMINSTICA
Logro de la Unidad:
IDEAS PREVIAS
Qu entiendo por optimizacin?
Qu con criterios max y min?
Qu se optimiza usualmente?
Cmo aplica los conceptos de eficiencia y eficacia con
el objetivo de optimizar las labores de una empresa?
PROBLEMA 1
Una firma industrial elabora dos productos, en los cuales entran cuatro componentes
en cada uno. Hay una determinada disponibilidad de cada componente y un
beneficio por cada producto. Se desea hallar la cantidad de cada artculo que debe
de fabricarse, con el fin de maximizar los beneficios.
El siguiente cuadro resume los coeficientes de transformacin, o sea, la calidad de
cada componente que entra en cada producto. El cuadro es:
Productos
Componentes
P1
(Kgs.)
P2
(Kgs.)
Disponibilidad
(Kgs.)
A
B
C
D
1
2
2
1
3
1
2
1
15,000
10,000
12,000
10,000
Beneficios S/. X Kg
PROBLEMA 2
Una compaa manufacturera fabrica los productos 1 y 2; y es suficientemente
afortunada como para vender todo lo que puede producir actualmente. Cada
producto requiere un tiempo de manufacturacin en los tres departamentos y la
disponibilidad de una cantidad fija de horas-hombre por semana en cada
departamento, tal como se muestra en el cuadro siguiente:
Tiempo de Manufactura en Horas
Productos
Dpto. A
Dpto. B
Dpto. C
1
2
2
2
1
2
4
2
HH Disp/Sem
160
120
280
El problema consiste en decidir qu cantidad de cada producto debe manufacturarse
con el objeto de hacer el mejor empleo de los medio limitados de produccin
sabiendo que la ganacia por cada unidad del producto 1 es 10 soles y del producto 2
es 25 soles.
PROBLEMA 3
Una persona necesita un mnimo de 60 unidades de carbohidratos, 40 de protenas y
35 unidades de grasas al mes. Est frente a 2 alimentos A y B; el primero contiene 5,
3 y 5 unidades de carbohidratos, protenas y grasas al mes por Kg., mientras el
alimento B contiene 2, 2 y 1 unidad por kilo. Si A cuesta 15 soles por kilo y B 7 soles.
Cuntos kilos de A y B deben adquirirse para satisfacer la dieta y mantenerse en
buena forma?:
Componentes
Productos
Carbohidrat
os
S/. 15
S/. 7
Requerimientos
Mnimos
60
40
35
S/. 15
Base 1 mes
Protenas
Grasas
Costo por Kg.
PROBLEMA 4
Un panadero tiene 150, 90 y 150 unidades de los ingredientes A, B y C
respectivamente. Un pastel requiere 5, 2 y 1 unidades de A, B y C respectivamente.
Un pan requiere 1, 1 y 2 unidades de A, B y C respectivamente. Si el pan se vende a
35 centavos y el pastel a 80 centavos Qu cantidad se debe hacer de cada una y
cual es la ganancia bruta?
PROBLEMA 5
Una industria produce 2 artculos distintos: A y B. La elaboracin de una unidad del
artculo A se lleva S/.20.00 de mano de obra y S/.10.00 el B. De materia prima se
lleva S/.10.00 la unidad de A y S/.30.00 la unidad de B. El desgaste de equipos se
supone proporcional a la produccin y es de S/.5.00 por cada unidad de A y S/.1.00
por cada unidad de B. El beneficio por unidad de artculo es de S/.8.00 para A y
S/.5.00 para B. Si solamente se cuenta con S/.100,000.00 para salarios,
S/.180,000.00 para materia prima y no se quiere que el desgaste de los equipos
exceda de S/.40,000.00 Cul es la cantidad que se debe producir de cada artculo
para obtener las utilidades ms altas posibles?.
PROBLEMA 6
Una Compaa produce 2 tipos de hojas de afeitar: las convencionales que son de
poca duracin y las inoxidables que son de larga duracin, las convencionales
requieren 8 unidades de acero de carbono y 2 de aleacin de acero para producir
100 hojas. Las inoxidables requieren 4 unidades de acero de carbono y 6 de aleacin
de acero para producir 100 hojas. Un reciente contrato le ha permitido a la compaa
adquirir 24,000 unidades de acero de carbono y 10,000 de aleacin de acero. Con el
fin de determinar la mxima utilidad se desea saber cual sera la mayor produccin si
por 100 horas de las convencionales la utilidad es de S/.100. y por 100 de las
inoxidables la utilidad es de S/.150.
Producto
Insumo
X1
Convencionales
X2
Inoxidables
Disponible
Insumo
Acero al Carbn
Aleacin de Acero
Utilidad
0.08
0.02
1.00
0.04
0.06
1.50
24,000
10,000
PROBLEMA 7
En una mueblera se planea la produccin de mesas y de sillas, cada mesa requiere
de 2 horas de mquina y 1 hora de mano de obra, cada silla requiere de 6 horas de
mquina y 4 horas de mano de obra. La mquina tiene un mximo disponible de 12
horas. La mano de obra tiene un mximo disponible de 7 horas. La ganancia de cada
mesa es de S/.3.00 y la de cada silla es de S/.5.00 Cuntas sillas y mesas deben
de producirse para obtener la mxima ganancia?.
PROBLEMA 8
La Compaa JCC hace puertas y ventanas. Cada puerta requiere 1 hora de la
mquina I y 2 horas de la mquina II. Cada ventana requiere 3 horas de la mquina I
y 2 horas de la mquina II. La compaa tiene un mximo de 9 horas para la
mquina I y 8 horas para la mquina II. Determinar la cantidad de puertas y ventanas
a fabricarse para obtener la mxima ganancia si se gana:
1. S/. 10.00 en cada puerta y S/.20.00 en cada ventana
2. S/. 10.00 en cada puerta y S/.35.00 en cada ventana
PROBLEMA 9
La Compaa SONY produce 2 tipos de TV blanco y negro. Compra diferentes
elementos de otra compaa local y las arma en su planta. La Tv de tipo X necesita
5 horas de montaje y la del tipo Z 2 horas. Se dispone diariamente de 10 horas en
el departamento de montaje, la compaa puede gastar hasta S/.15.00 para comprar
los elementos de la Tv. Utiliza S/.3.00 de material por el Tv X y S/.5.00 por el Tv
tipo Z.
Se gana S/.5.00 por cada Tv X y S/.3.00 por cada Tv Z Cuntas unidades de
cada uno se producen para maximizar la utilidad?
PROBLEMA 10
Un hombre planea comprar cierto tipo de alimentos: carne y pescado, ambos pueden
proveer unidades nutritivas para un mnimo requerido durante un periodo dado como
sigue:
Tipo de
Nutrientes
Unidades de Nutrientes en
1 Lb de Carne
1 lb de Pescado
A
B
C
Precio x Unidad
1
2
3
S/. 2.5
3
2
2
S/.1.5
Mnimo de
Unidad
Requerida
9
10
12
Cuntas libras de carne y pescado deben comprar para obtener los mnimos
requerimientos nutrientes al mnimo costo?
PROBLEMA 11
La compaa de transporte CONSTANTINO tiene que transportar 480 camas y 360
roperos. Tienen 2 tipos de camiones A y B. El costo unitario de cada ropero o cama
en el camin A es de S/.20.00 y el costo unitario de cada ropero o cama en el camin
B es de S/.18.00. La capacidad de cada camin: A: 6 camas y 9 roperos. Mientras
que la del camin B: 6 camas y 3 roperos. Cuntos roperos y camas debe llevar
cada camin?.
PROBLEMA 12
La compaa EBEL, tiene dos minas diferentes que producen un tipo de mineral. Las
minas estn ubicadas en diferentes partes del pas y tiene diferentes capacidades de
produccin. Despus de romper por comprensin, el mineral se clasifica en tres
clases: alto, medio y bajo.
Hay demanda establecida para cada grado de mineral. EBEL tiene un contrato con
una fundicin para proveer 13 toneladas de grado alto, 9 toneladas de grado medio y
27 toneladas de grado bajo, cada semana.
El costo de la produccin es de S/.200.00 cada da para la primera mina S/.160.00
cada da para la segunda. En un da la primera mina produce 7 toneladas de grado
alto, 3 toneladas de medio y 2 toneladas de grado bajo. La segunda mina produce en
un da 3 toneladas de grado alto, 1 tonelada de grado medio y 12 toneladas de grado
bajo.
Cuntos das a la semana se debe operar cada mina para suplir la demanda
econmicamente?
PROBLEMA 13
La fbrica WILSON hace dos productos, sillas y escritorios de madera. La
fabricacin de estos productos se realiza en cuatro departamentos; un
departamento donde se corta la madera, un departamento de ensamblaje,
un departamento donde se tapizan sillas y un departamento de linleo
donde se ponen las coberturas de linleo en los escritorios.
Hay 27,000 minutos disponibles en cada departamento y no se puede
cambiar este tiempo. Las estadsticas de aos pasados muestran que una
silla requiere 15 minutos de cortado y un escritorio 40 minutos. El
ensamblaje de una silla requiere 12 minutos y un escritorio 50 minutos. Se
necesitan 56.25 minutos para cada escritorio en el departamento de linleo.
Departamento
Corte
Ensamble
Tapizado
Linleo
Tiempo
Disponible
27,000
27,000
27,000
27,000
Tiempo Necesario
Sillas
Escritorio
15
12
18.75
---
40
50
--56.25
La utilidad de cada escritorio es S/.75.00 y por cada silla S/.25.00
PROBLEMA 14
La tienda COLACCI tiene 100,000 metros cuadrados disponibles en el primer piso y
estn en el proceso de distribuir es espacio entre tres departamentos.
1) Cosmticos, 2) Ropa de hombre y 3) Ropa de mujer. Una buena decoracin
requiere que los cosmticos no ocupen ms de 50% del piso. Las costumbres
comerciales requieren que la ropa de mujer y los cosmticos juntos no deben
exceder la ropa de hombres por ms de 30,000 metros cuadrados. La ganancia
anual de cada uno de estos departamentos es:
1) Cosmticos S/.1,000 / metro cuadrado.
2) Ropa para hombres 600/ metro cuadrado.
3) Ropa para mujeres 800 / metro cuadrado.
PROBLEMA 15
Una compaa manufacturera fbrica los productos 1 y 2; es
suficientemente afortunada como para vender todo lo que puede producir
actualmente.
Cada producto requiere un tiempo de manufacturacin en los 3
departamentos y la disponibilidad de una cantidad fija de horas hombre por
semana en cada departamento; tal como se muestra en el siguiente
cuadro:
Productos
Tiempo de manufactura por hrs.
P1
P2
HH disp./Sem.
Dpto. A
Dpto. B
Dpto. C
2
2
160
1
2
120
4
2
280
El problema es decidir que cantidad de cada producto debe manufacturarse
con el objeto de hacer mejor empleo de los medio limitados de produccin
sabiendo que la ganancia por cada unidad del producto 1 es de S/.10.00 y
del 2 es S/.25.00.
PROBLEMA 16
Una empresa fabrica radios a transistor de tipo Ra y Rb. Estos utilizan transistores
de tipo T1 y T2, teniendo en existencia una cantidad limitada, de los cuales se
muestran.
T1 : 1000 unidades
T2 : 1200 unidades
Adems,
Tipo de Radio
Ra
Rb
Transistor
T1
T2
Utilidad
Unitaria
1
4
4
1
50
30
Hallar el nmero ptimo de radios a fabricar de cada tipo para obtener la mxima
utilidad.
PROBLEMA 17
Una compaa manufactura dos tipos de bates de bisbol, uno de peso ligero y otro
de peso mediano que se vende a los equipos de las ligas mayores.
La produccin de un bate requiere una operacin de torno para darle forma , un
proceso de lija para suavizar la madera y para los medianos solo una mano de
laqueado final.
Un bate para las ligas menores requiere un minuto de torno , de alta velocidad , en
tanto que el bate para las ligas de mayores toma 2 minutos , puesto que se le debe
dar la forma con tolerancias muy entradas. Debido a la rapidez que se da a los bates
ligeros , se requiere de 3 minutos en la maquina lijadora , en tanto que el mediano
necesita solo 2 minutos para ser lijado . El laqueado es hecho a mano y como
resultado de esto solo puede producirse 400 medianos durante una semana que
equivale a la misma cantidad de minutos.
Para una semana promedio de trabajo deben utilizarse 1,000 minutos de tiempo de
torno , 1,800 minutos de tiempo de lijado y 400 minutos de laqueado.
Asmase que la compaa puede vender tantos bates de cada tipo como los que
puede producir , adems se conoce que la utilidad es de $30 por cada peso ligero y
de $40 por cada mediano promedio producido.
Resp. 400 bates ligeros.
300 bates medianos.
PROBLEMA 18
Determinar los envios desde las plantas hacia los lugares de venta (Pedidos
mnimos)
Flete por Unidad
Quito
Plantas
Planta
Arequipa
Lima
Trujillo
Arequipa
Lima
Trujillo
Produccin
1500
2500
2200
6200
Destino de Venta
Santiago
Buenos Aires Sao Pablo
17
14
12
13
11
24
18
13
12
12
18
12
Demanda
Quito
1596
Santiago
1461
Buenos Aires
1368
Sao Pablo
1144
PROBLEMA 19
Un proveedor de bebidas dietticas debe preparar con las existentes de su bodega,
un pedido de 500 litros de ponche diettico el cual debe contener por lo menos 20%
de jugo de naranja, 10% de jugo de toronja y 5% de jugo de betabel. La siguiente
tabla informa de 5 bebidas existentes con su contenido de jugos y el costo de las
mismas. Qu cantidad de cada bebida deber de emplear el proveedor para
cumplir el pedido a un costo mnimo? Formule un modelo de programacin lineal que
represente este problema.
PROGRAMACIN ENTERA Y BINARIA
Logro de sesin: Al finalizar la sesin, el
estudiante resuelve problemas de optimizacin de
programacin entera y binaria
AGENDA
1. Programacin Entera
2. Programacin Binaria.
PROGRAMACIN ENTERA (PE)
En general, son problemas de programacin
lineal (PPL), en donde sus variables de
decisin deben tomar valores enteros.
TIPOS DE PE
Cuando se requiere que todas las variables de decisin tomen
valores enteros, entonces se habla de programacin entera pura.
Cuando algunas variables son enteras, y otras contnuas, entonces
se habla de programacin entera mixta (PEM).
Un caso especial de programacin entera (PE) es cuando todas las
variables son binarias (0 o 1), entonces se habla de programacin
entera binaria (PEB).
En general, los problemas de PE son ms difciles de resolver que
los PPL con variables contnuas. Por ello se han desarrollado
diversas tcnicas de solucin.
EJEMPLO 1
a) Problema de Programacin Entera Pura
El Restaurante RataBurger es una nueva cadena de comida rpida.
El local planifica su expansin en el centro y reas suburbanas.
La gerencia desea determinar cuntos restaurantes abrir en cada rea
a fin de aumentar al mximo la ganancia semanal neta.
Requerimientos y restricciones:
No ms de 19 gerentes pueden ser asignados.
Por lo menos deben abrirse dos restaurantes en el centro.
La inversin total no puede exceder a $2.7 Millones.
Datos Adicionales
Inversin por la ubicacin
Ganancia diaria
Horas de operacin
Nmero de gerentes necesarios
Suburbano
Centro
200,000
600,000
1,200
2,000
24 horas
12 horas
SOLUCIN
Variables de Decisin
X1 = Nmero de restaurantes abiertos en lugares suburbanos.
X2 = Nmero de restaurantes abiertos en el centro .
El modelo matemtico se formula a continuacin:
Max Z= 8400 X1 + 14000 X2
(Ganancia semanal diaria x 7 das)
ST
0.2 X1
+
0.6X2
<= 2.7
(Inversin mxima MUS$2.7)
X2
>= 2
(2 Restaurantes en el centro)
3X1
+
X2
<= 19
(No mas de 19 Gerentes)
X1, X2 >= 0
EJEMPLO 2
b) Problema de Programacin Entera Mixta
Shelley Mednick ha decidido realizar una inversin.
Ella invertir en:
-TCS, una compaa de abastecimiento y comunicaciones y/o
- MFI, un fondo mutuo.
Shelley es una inversionista precavida. Ella tiene lmites sobre el
nivel de inversin, y defini una meta para la ganancia anual.
Datos:
TCS vende actualmente cada accin a $55.
TCS proyecta vender cada accin a $68 dentro de un ao.
MFI espera obtener 9% de utilidad anual.
Restricciones:
La utilidad esperada debe ser de por lo menos $250.
La cantidad mxima invertida en TCS no debe sobrepasar un 40%
de la inversin total.
La cantidad mxima invertida en TCS no debe sobrepasar $750.
Variables de decisin
X1 = Nmero de acciones a comprar en TCS.
X2 = Cantidad de dinero que invertir en MFI.
El modelo matemtico:
Min z= 55X1
+
X2
ST
13 X1 + 0.09 X2
>= 250
33 X1 0.40 X2
<= 0
55X1
<= 750
X1, X2>=0
X1 Entero
EJEMPLO 3
c) Problema de Programacin Binaria
Un excursionista debe determinar que objetos
debe llevar consigo en la mochila para realizar
una excursin de un da. Cada uno de los
objetos tiene asociado un peso y una utilidad
personal para el excursionista.
Los objetos que puede llevar, as como su
peso y utilidad son los que
se recogen en la tabla siguiente:
Sabiendo que el peso mximo que puede
llevar en la mochila es de 100. Determinar
que objetos debe llevar nuestro excursionista
en la mochila para que la utilidad de los
objetos sea mxima.
Objeto
Linterna
Saco
Cocina
Manta
Comida
Ropa
Varios
Peso Utilidad
40
40
50
80
30
10
10
10
10
4
40
20
30
60
EJEMPLOS 4 (OTROS)
Problema de costo fijo y costo variable
Un agricultor debe almacenar 200 toneladas de manzanas y 300
toneladas de naranjas en cmara frigorifica durante un mes.
Para ello, dispone de dos cmaras frigorficas propias (A y B) con
capacidad de 400 y 600 toneladas respectivamente.
El costo de almacenamiento en la cmara A es de S/. 60 por tonelada
de manzana, y S/. 50 por tonelada de naranjas, y en la cmara B es
de S/. 70 por tonelada de naranjas o manzanas.
Adems, el agricultor puede arrendar un frigorfico con una capacidad
de 250 toneladas a un costo fijo de S/. 12,000.
Determine cuanta fruta debe almacenar en cada frigorfico propio y/o
arrendado el agricultor para minimizar su costo total de
almacenamiento.
Variables de decisin:
Cuntas toneladas de manzanas y naranjas se almacenan en
cada cmara propia:
X mA : toneladas de manzanas almacenadas en cmara A
X nA : toneladas de naranjas almacenadas en cmara A
X mB : toneladas de manzanas almacenadas en cmara B
X nB : toneladas de naranjas almacenadas en cmara B
Variables de decisin:
Adems, se debe decidir si se arrienda o no la bodega externa, y
las toneladas a almacenar en esta bodega si se arrienda
sea
Y=
1 si se arrienda la bodega
0 si no se arrienda la bodega
X mC : toneladas de manzanas almacenadas en cmara arrendada
X nC : toneladas de naranjas almacenadas en cmara arrendada
Funcin objetivo:
Minimizar (costo almacenamiento en cmaras + costo arriendo):
Min Z = 60 X mA + 50 X nA + 70 (X mB + X nB) + 12.000 Y
Restricciones del problema:
Restricciones
X mA + X nA
X mB + X nB
X mC + X nC
de capacidad cmaras
400
(capacidad cmara A)
600
(capacidad cmara B)
250 Y (capacidad cmara C, sujeto a la
condicin de que esta cmara se arriende)
Restricciones de cantidad de fruta a almacenar
X mA + X mB + X mC = 200 (total manzanas almacenadas)
X nB + X nB + X nC = 300 (total naranjas almacenadas)
Restriccin de no negatividad.
X nA, X mA, X nB, X mB , X nC, X mC 0
Restriccin de variable binaria
Y = 0, 1
EJEMPLO 5 (OTROS EJEMPLOS)
Seleccin de alternativas de produccin
Se desea construir 2 plantas de produccin. Para localizar las plantas se tiene 4
ciudades alternativas: A, B, C, y D. Adems, se desea construir un almacn que
sirva como bodega a un costo de MUS$ 80. Se espera que el almacn genere
utilidades por MUS$ 180. Pero sta debe localizarse en una ciudad en donde
se haya construido una planta. A continuacin se presentan las inversiones y
ganancias esperadas para cada alternativa. Formule un modelo matemtico
que maximice la ganancia si se dispone de un mximo de 400 MUS$ para
invertir.
Ciudad
A
B
C
D
Inversin
100
150
240
190
Ganancia
90
120
200
150
Sea xij:1 si se localiza la planta o bodega i en la ciudad j.
con i:P,B y j:A,B,C,D
F.O. MAX z = 90XPA+120XPB+200XPC+150XPD
+180(XBA+XBB+XBC+XBD)
s.a.
100XPA+150XPB+240XPC+190XPD+80(XBA+XBB+XBC+XBD)400
Alternativas
XBA+XBB+XBC+XBD = 1
mtuamente
XPA+XPB+XPC+XPD = 2
excluyentes
XBA - XPA 0
XBB - XPB 0
Decisiones
XBC - XPC 0
contingentes
XBD - XPD 0
Xij {0,1}
RESUMEN
Variables
PE
PE
PEB
PEM
Enteras
Binarias (0,1)
Enteras y
contnuas
Mtodos de
Solucin
Tec. Planos de corte
Tec. Ramificacin y
acotamiento
Algoritmos especficos
(Teora de redes)
TRABAJO GRUPAL
En grupo de 5 personas desarrollar (2
Problemas por cada tipo)
Programacin Entera
Programacin Binaria
Programacin Mixta (Entera-Continua)
Asimismo proponer un problema de tipo
Programacin Mixta (Entera-Continua y
Binaria)
