planteamiento de problemas de programación · pdf filede programación lineal....
TRANSCRIPT
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 1
Planteamiento de problemas de programación lineal
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 2
Ejemplo. Fabricantes muebleros
Asignación de recursos limitados
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 3
• La Fabricantes muebleros, un fabricante de muebles de oficina, produce dos tipos de escritorios: ejecutivos y secretariales.
• La compañía tiene dos plantas en las que fabrica los escritorios. La planta 1, que es una planta antigua, opera con doble turno 80 horas por semana.
• La planta 2 es una planta más nueva y no opera a su capacidad total.
• Sin embargo, y dada que los administradores planean operar la segunda planta con base en un turno doble como el de la planta 1, se han encontrado operadores para que trabajen los dos turnos.
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 4
• En estos momentos, cada turno de la planta 2 trabaja 25 horas por semana.
• No se paga ninguna prima adicional a los trabajadores del segundo turno.
• La tabla muestra el tiempo de producción (en horas par unidad) y los costos estándar (en dólares por unidad) en cada planta.
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 5
TABLA. Tiempo (horas) y costos (dólares)
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 6
• La compañía ha competido con éxito en el pasado asignando un precio de $350 a los escritorios ejecutivos.
• Sin embargo, parece que la compañía tendrá que reducir el precio de los escritorios secretariales a $275 con el objeto de estar en posición competitiva.
• La compañía ha estado experimentando excesos de costos en las últimas ocho a diez semanas; por tanto, los administradores han fijado una restricción presupuestaria semanal sobre los costos de producción.
• El presupuesto semanal para la producción total de escritorios ejecutivos es $2000, en tanto que el presupuesto para los escritorios secretariales es $2200.
• A los administradores les gustaría determinar cuál es el número de cada clase de escritorios que deben fabricarse en cada planta con el objeto de maximizar las utilidades, en la próxima semana.
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 7
SOLUCIÓN
ObjetivoLa compañía necesita determinar el número
de escritorios ejecutivos y secretariales que deben fabricarse en la planta 1 y los que deben fabricarse en la planta 2 con el objeto de maximizar las utilidades.
La utilidad por unidad en las respectivas plantas es la diferencia entre el precio de venta y los costos estándar.
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 8
Restricciones1.No se dispone de más de 80 horas para la
producción combinada de escritorios en la planta 1.
2.No se dispone de más de 50 horas para la producción combinada de escritorios en la planta 2.
3.Los costos asociados con la producción combinada de escritorios ejecutivos en las dos plantas no deben exceder $2000.
4.Los costos asociados con la producción combinada de escritorios secretariales en las dos plantas no deben exceder de $2200.
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 9
Variables de decisiónDado que es necesario determinar la cantidad de cada tipo
de escritorio que va a fabricarse en la planta 1 y en la planta 2, se requieren cuatro variables:
X1 = número de escritorios ejecutivos que se fabrican en la planta 1, la próxima semana.
X2 = número de escritorios secretariales que se fabrican en Ia planta 1 , la próxima semana.
X3 = número de escritorios ejecutivos que se fabrican en la planta 2, la próxima semana.
X4 = número de escritorios secretariales que se fabrican en la planta 2, la próxima semana.
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 10
Coeficientes de la función objetivo (estructura matemática)
La función objetivo se expresará en dólares, puesto que el objetivo es maximizar utilidades; por tanto, los coeficientes cj se expresarán en dólares por unidad, dado que las xj están expresadas en unidades.
Los coeficientes cj se determinan encontrando la diferencia entre el precio de venta de un determinado tipo de escritorio y los costos estándar multiplicados en la fabricación de ese escritorio en la planta específica.
Por ello:
C1 = 350 - 250 = $100/escritorio ejecutivo fabricado en la planta 1C2 = 275 -200 = $75/escritorio secretarial fabricado en la planta 1C3 = 350 - 260 = $90/escritorio ejecutivo fabricado en la planta 2C4 = 275 - 180 = $95/escritorio secretarial fabricado en la planta 2
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 11
Función objetivo (estructura matemática)
MAXIMIZAR: Z = 100X1+75X2+90X3+95X4
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 12
Restricciones (estructura matemática)
Es posible identificar y verificar la consistencia de las unidades de medición de los coeficientes aij y de los valores del segundo término al mismo tiempo que se desarrolla la estructura matemática de las restricciones.
Puesto que las unidades de medición pueden diferir de una restricción a otra, se considera cada una de ellas en forma separada.
1. Límite del tiempo de producción en la planta 1 (80 horas):(7.0 horas / unidad) x (x1 unidades) +(4.0 horas / unidad) x (x2 unidades) <= 80 horas
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 13
2. Límite del tiempo de producción en la planta 2 (50 horas):
(6.0 horas / unidad) x (x3 unidades) +(5.0 horas / unidad) x (x4 unidades) <= 50 horas
3. Restricción de costos de los escritorios ejecutivos ($2000):
(250 dólares / unidad) x (x1 unidades) +(260 dólares / unidad) x (x3 unidades) <= $2000
4. Restricción de costos de los escritorios secretariales ($2200):
(200 dólares / unidad) x (x2 unidades) +(180 dólares / unidad) x (x4 unidades) <= $2200
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 14
Planteamiento matemáticoMAXIMIZAR: Z = 100x1 + 75x2 + 90x3 + 95x4
Sujeto a: 7.0x1 + 4.0x2 <= 80 (tiempo de la planta 1)6.0x3+5.0x4<=50 (tiempo de la planta 2)250x1 + 260x3 <= 2000 (costos de los escritorios
ejecutivos)200x2 + 180 x4 <= 2200 (costos de los escritorios
secretariales)x1, x2, x3, x4 >= 0 y enteras
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 15
Ejemplo. Hospital de la Mujer
Dieta de costo mínimo
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 16
• La señora López, dietista del Hospital, es responsable de la planeación y administración de los requerimientos alimenticios de los pacientes.
• La señora López examina en estos momentos un caso de un paciente que se le ha restringido a una dieta especial que consta de dos fuentes alimenticias.
• Al paciente no se le ha restringido la cantidad de los dos alimentos que puede consumir; sin embargo, se deben satisfacer los siguientes requerimientos nutritivos mínimos por día: 1000 unidades del nutriente A, 2000 del nutriente B y 1500 unidades del nutriente C.
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 17
• Cada onza de la fuente alimenticia No. 1 contiene 100 unidades del nutriente A, 400 unidades de nutriente B y 200 unidades de nutriente C; cada una de la fuente alimenticia No. 2 contiene 200 unidades de nutriente A, 250 unidades del nutriente B y 200 unidades del nutriente C.
• Ambas fuentes alimenticias son algo costosas (la fuente No. 1 cuesta $6.00 por libra y la fuente No. 2 cuesta $8.00 por libra); por tanto, la señora López desea determinar la combinación de fuentes alimenticias que arroje el menor costo y que satisfaga todos las requerimientos nutritivos.
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 18
SOLUCION
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 19
Objetivo
El objetivo en este caso consiste en determinar el número de onzas de cada una de las dos fuentes alimenticias que cuesten lo menos posible y que satisfagan los requerimientos nutritivos de los nutrientes A, B y C.
Un punto importante que debe reconocerse es que las unidades de medición para las fuentes alimenticias se expresan en onzas, en tanto que sus costos se expresan en libras.
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 20
Restricciones
1.Se deben consumir cuando menos 1000 unidades del nutriente A por día.
2.Se deben consumir cuando menos 2000 unidades del nutriente B por día.
3.Se deben consumir cuando menos 1500 unidades del nutriente C por día.
4.No existe restricción sobre Ia cantidad que se consume por día de cada una de las fuentes alimenticias.
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 21
Variables (estructura matemática)
Se requerirán dos variables, puesto que se desea determinar la cantidad que debe consumirse de dos fuentes alimenticias:
X1 = número de onzas de la fuente alimenticia No. 1 que debe consumirse diariamente
X2 = número de onzas de la fuente alimenticia No. 2 que debe consumirse diariamente
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 22
Función objetivo (estructura matemática)
El objetivo de éste problema consiste en minimizar costos. El único ajuste que es necesario hacer a los coeficientes
de costos es reconocer que en el esbozo del problema, los costos de las respectivas fuentes alimenticias se expresaran en libras y no en onzas.
Por tanto, c1 = $6.00/16 = $0.375 por onza y c2 = $8.00/16 = $0.50 por onza, puesto que existen 16 onzas en cada libra de las respectivas fuentes alimenticias.
Entonces, la función objetivo puede expresarse de la siguiente manera:
MINIMIZAR: Z = 0.375x1 + 0.50X2
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 23
Restricciones (estructura matemática)
Se ha elaborado la tabla para ayudar a reestructurar las restricciones que le siguen.
TABLA. Datos de nutrientes
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 24
1. Restricción del nutriente A:[(100 unidades del nutriente A)/(onza de la
fuente No. 1)] x (x1 onzas de la fuente No. 1) + [(200 unidades del nutriente A)/(onza de la fuente No. 2)] x (x2 onzas de la fuente No. 2) >= 1000 unidades del nutriente A
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 25
2. Restricción del nutriente B:[(400 unidades del nutriente B)/(onza de la
fuente No. 1)] x (x1 onzas de la fuente No. 1) + [(250 unidades del nutriente B)/(onza de la fuente No. 2)] x (x2 onzas de la fuente No. 2) >= 2000 unidades del nutriente B
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 26
3. Restricción del nutriente C:[(200 unidades del nutriente C)/(onza de la
fuente No. 1)] x (x1 onzas de la fuente No. 1) + [(200 unidades del nutriente C)/(onza de la fuente No. 2)1 x (x2 onzas de la fuente No. 2) >= 1500 unidades del nutriente C
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 27
Planteamiento matemáticoMINIMIZAR: Z = 0.375x1 + 0.50x2
SUJETO A:
100x1 + 200x2 >= 1000400x1 + 250x2 >= 2000200x1 + 200 x2 >= 1500X1 ,X2 >= 0
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 28
Ejemplo. PEMEX
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 29
PEMEX
• Comercializa gasolina de dos grados: la extra y la normal.
• Cada gasolina debe satisfacer ciertasespecificaciones, tales como la presión de vapor aceptable y el octanaje mínimo.
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 30
Los requerimientos de manufacturason:
Gasolina Octanajemínimo
Presiónmáxima de vapor
Precio de venta (porbarril)
Normal 80 9 21
Extra 100 6 24
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 31
Se utilizan 3 tipos de gasolina parafabricar las gasolinas normal y extra.Gasolinabase
Octanaje Presiónde vapor
Disponibilidad
máxima(barriles)
Costopor barril
1 108 4 32000 22
2 90 10 20000 20
3 73 5 38000 19
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 32
• La compañía se ha comprometido con un comprador a proporcionar 30,000 barrilesde gasolina normal por semana.
• No se tienen compromisos con respecto a la gasolina extra.
• Le gustaría determinar el plan de producción para las 2 clases de gasolinaque maximicen las utilidades para la próxima semana.
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 33
Variables de Decisiónx1 . Nùmero de barriles de gasolina 1 para fabricar
gasolina normal
x2 . Nùmero de barriles de gasolina 2 para fabricar gasolina normal.
x3 . Nùemro de barriles de gasolina 3 para fabricar gasolina normal.
x4 . Nùmero de barriles de gasolina 1 para fabricar gasolina extra.
x5 . Nùmero de barriles de gasolina 2 para fabricar gasolina extra.
x6 . Nùmero de barriles de gasolina 3 para fabricar gasolina extra.
para la próxima semana
para la próxima semana
para la próxima semana
para la próxima semana
para la próxima semana
para la próxima semana
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 34
Función Objetivo
• Coeficientes
Max_Z x1− x2+ 2 x3⋅+ 2 x4⋅+ 4x5+ 5x5+Gasolina Octanaje mínimo Presión máxima
de vaporPrecio de venta(por barril)
Normal 80 9 21
Extra 100 6 24
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 35
RestriccionesX1+X2+X3 <= 30000
x1 x4+ 32000≤
x2 x5+ 20000≤
x3 x6+ 38000≤
4x1x1 x2+ x3+
10x2x1 x2+ x3+
+5x3
x1 x2+ x3++ 9≤
108x1x1 x2+ x3+
90x2x1 x2+ x3+
+73x1
x1 x2+ x3++ 80≥
4x1x4 x5+ x6+
10x2x4 x5+ x6+
+5x3
x4 x5+ x6++ 6≤
108x1x4 x5+ x6+
90x2x4 x5+ x6+
+73x1
x4 x5+ x6++ 100≥
xi 0≥
i 1..6
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 36
Ejemplo. Compañía Ferguson
Asignación de capital
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 37
COMPAÑÍA FERGUSON• La Ferguson enfrenta el problema de determinar que
proyectos de “crecimiento” debe emprender en lospróximos 4 años.
• La compañía tiene una cantidad limitada de fondos parainversiones de capital; por tanto, no puede financiartodos los proyectos.
• A cada uno de estos se Ie ha caracterizadodeterminando su valor presente y el requerimiento(costo) asociado de capital.
• Cada proyecto tiene diferentes requerimientos de capital para los próximos 4 años.
• En Ia tabla siguiente se muestran eI valor presenteestimada, los requerimientos de capital y el capital disponible proyectado para cada uno de ellos.
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 38
Desarrollar plan para la asignación de fondos.
A los administradores de la Ferguson les gustaría desarrollar un plan de asignaciónde capital que muestre las erogaciones que deben hacer para cada uno de los 4 añosy qué proyectos se deben financiar bajo el plan general.
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 39
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 40
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 41
Variables de decisión
xj . valor proporcional que indica la medida en que se finanacia el proyecto
xj . 1 indica que si se financia el proyecto
xj . 0 indica que no se financia el proyecto
j 1 2, 3, 4,
DURANTE LOS 4 AÑOS
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 42
Función Objetivo
44332211 xcxcxcxcz +++=
Max_Z 18000x1 20+ 000x2 72000x3+ 80000x4+,180000
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 43
Restricciones
30 000x1 12+, 000x2 30+, 000x3 20+, 000x4 65≤, 000,
40 000x1 8+, 000x2 30+, 000x3 30+, 000x4 85≤, 000,
40 000x1 0x2+ 20+, 000x3 40+, 000x4 80≤, 000,
30 000x1 4+, 000x2 30+, 000x3 10+, 000x4 50≤, 000,
x1 x2, x3, x4 1≤,
xj 0> j 1, 2, 3, 4,
Año 1:
Año 2:
Año 3:
Año 4:
para garantizar que cada proyecto no sobrepase el 100% del mismo
X1+X2+X3+X4<=1
>=
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 44
Ejemplo. Compañía B&ZBrewingTransporte
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 45
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 46
Datos
464
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 47
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 48
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 49
Variables de decisión
xij i 1, 2, 3, xij .numero de camiones qeu se envian de la planta i al almacen jj 1 2, 3, 4,
queEn un período de tiempo dado
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 50
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 51
Función ObjetivoMin ∑
==
==
=4_3
1
ji
jiijij xCz
34333231
24232221
14131211
685388682995791690416352
867654513464
xxxxxxxx
xxxxz
+++++++
++++=Min
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 52
Investigación de Operaciones
M. En C. Eduardo Bustos Farías 53
Restricciones
xij 0≥ i 1 2, 3,
j 1 2, 3, 4,
85706580
100
12575
342414
332313
322212
312111
34333231
24232221
14131211
≤++≤++≤++≤++
≤+++
≤+++≤+++
xxxxxxxxxxxx
xxxx
xxxxxxxx
=
=
=
=
1
2
3
3
2
1
4
464513
654867
352 416690
791
995 687
388685
Plantas de Producción Almacenes de Depósito
Boulder Colorado(75)
Mineapolis,Minessota (125)
OlympiaWashington (100)
San Diego, Cal.(80)
Pravo, Utah (65)
Albuquerque,Nvo. México (70)
Lincoln,Nebraska (85)