Presentacion Clases V 2

MAESTRIA PYGE
Ing. Rodrigo Semprtegui lvarez
MAESTRIA PYGE
I.
Introduccin
I.1. Introduccin
Antecedentes:
MAESTRIA PYGE
Durante la Segunda Guerra Mundial, el mando britnico consult a cientficos y tcnicos sobre distintas cuestiones militares: Despliegue de radares. Direccin de operaciones antisubmarinas, de minas, bombardeos y traslado de tropas. El resultado se llam Investigacin de Operaciones Militares, y ms tarde Investigacin Operativa (IO) El MIT contribuy a su puesta en marcha El profesor Morse (MIT) fue pionero en los EE.UU. Fund el Centro OR del MIT y colabor en la fundacin de ORSA.
3
I.
Introduccin
MAESTRIA PYGE
Qu son las ciencias de la gestin (investigacin operativa)? Hoy en da: las ciencias de la gestin y la investigacin operativa suponen el empleo de modelos matemticos para proporcionar pautas que permitan a los gestores tomar decisiones efectivas partiendo de la informacin de la que disponen, o para hallar el modo de ampliar sta, en caso de que sea insuficiente para llegar a la decisin adecuada.
I.
Introduccin
La investigacin operativa en la historia 1947 Proyecto Scoop (Scientific Computation of Optimum Programs), en el que George Dantzig y otros cientficos desarrollan el mtodo simplex de programacin lineal. Dcada de 1950 Aos muy interesantes: progresos matemticos, teora de colas, programacin matemtica. Comparar con: Inteligencia artificial (I.A.) en los 60. Dcada de 1960 Crece el inters: ms progreso, grandes proyectos. Comparar con: Inteligencia artificial en los 80.
MAESTRIA PYGE
I.
Introduccin
Dcada de 1970 poca de desilusin y estancamiento. NPcompleto. Expectativas ms realistas. Dcada de 1980 Gran expansin del uso de computadores personales. Acceso cada vez ms fcil a datos. Se extiende la disposicin de los directivos al empleo de modelos. Dcada de 1990 Uso creciente de sistemas de I.O. Nuevos avances de la tecnologa de I.O; p.ej: ampliaciones de optimizacin y simulacin a hojas de clculo, lenguajes de modelacin, optimizacin a gran escala. Mayor interconexin entre la I.A. y la I.O
6
MAESTRIA PYGE
I.
Introduccin
La investigacin operativa en el ao 2000 CIENTOS de oportunidades para el campo de la I.O. Datos, datos y ms datos Datos de e-business (click stream, compras, otros datos de transacciones, correo electrnico, etc.) El proyecto del genoma humano y su desarrollo Mayor automatizacin en la toma de decisiones Necesidad de mayor coordinacin para la utilizacin de recursos (gestin de la cadena de suministro)
MAESTRIA PYGE
I.
Introduccin
Definicin
MAESTRIA PYGE
Aplicacin del mtodo cientfico por un grupo multidisciplinario personas a la resolucin de un problema. Objetivo El principal objetivo de esta rea de conocimientos consiste en formular y resolver diversos problemas orientados a la toma de decisiones, mediante mtodos cientficos, que optimizan el funcionamiento del proceso analizado, generalmente bajo condiciones que implican la utilizacin de recursos escasos.
I.
Introduccin
Naturaleza
La naturaleza de los problemas abordados pueden ser:
MAESTRIA PYGE
Mtodos
determinsticos: Programacin lineal, programacin entera, transporte, teora de la localizacin o redes, programacin multicriterio, teora de inventarios, etc. (Modelos de Prog. Matemtica)
Mtodos probabilsticos: Cadenas de markov, teora de juegos,
lneas de espera, teora de inventarios, etc.

Mtodos
hbridos: probabilsticos.
Conjugan
mtodos
determinsticos
Mtodos heursticos: soluciones basadas en la experiencia.

9
I.
Introduccin
MAESTRIA PYGE
Gran cantidad de problemas reales cada ms complejos y especializados requieren de:

Uso
de metodologas para matemtica de estos problemas.
la
formulacin
Mtodos y herramientas de resolucin, como los
que provee la Investigacin de Operaciones.
10
I.
Introduccin
I.1.1 Formulacin del Problema 1. Definir el Problema
MAESTRIA PYGE
Definir el Problema Especificacin de Objetivos Reunir Datos Estimar Valores de Parametros Representacin Idealizada del Problema Estimar el Grado de Acercamiento del Modelo a la Realidad Escoger el modelo que mejor se adapta a los objetivos
2.
Observar el Sistema

3. 4. 5. 6. 7.
Formular el Modelo Matemtico para el Problema
Verificar el Modelo y usar el Modelo para Predicciones
Seleccionar la Alternativa Adecuada
Presentar los Resultados y Conclusiones del Estudio a la Organizacin Implantar y Evaluar las Recomendaciones
11
I.
Introduccin
Formular el Problema
MAESTRIA PYGE
Observar el Sistema
Formular el Modelo Matemtico
Verificar el Modelo y usar para predicciones

Seleccionar la Alternativa Presentar Resultados y Conclusiones
Implantar y Evaluar Recomendaciones

12
I.
Introduccin
I.2 Elementos de un modelo de optimizacin.
MAESTRIA PYGE
Supongamos que se dispone de determinadas piezas para la elaboracin de dos productos finales. Se dispone de 8 piezas pequeas y 6 piezas grandes, que son utilizadas para elaborar sillas (usando 2 piezas pequeas y 1 pieza grande) y mesas (usando 2 piezas de cada tipo). Interesa decidir cuntas sillas y mesas fabricar de modo de obtener la mxima utilidad, dado un beneficio neto de U$ 15 por cada silla y de U$20 por cada mesa fabricada.
13
I.
Introduccin
MAESTRIA PYGE
Posibles soluciones factibles a considerar, esto es soluciones que respetan las restricciones del nmero de piezas disponibles, son por ejemplo, fabricar:
4 sillas, que reportan una utilidad de U$60 1 sillas y 2 mesas , utilidad de U$55
3 mesas, utilidad de U$60

1 mesa y tres sillas, utilidad de U$65 2 sillas y 2 mesas, utilidad de U$70 etc.
14
I.
Introduccin
Componentes de un modelo matemtico: i) Las variables de decisin, que consiste en definir cules son las decisiones que se debe tomar. En el ejemplo, x: nmero de sillas elaboradas. y: nmero de mesas elaboradas.
MAESTRIA PYGE
Qu puedes decidir?
Ej: cuanto producir; cuanto invertir, y en qu, son variables de decisin
ii) La funcin objetivo del problema, que permita tener el mejor criterio para decidir entre todas las soluciones factibles. En el ejemplo, maximizar la utilidad dada por: z = f(x,y) = 15x + 20y
Qu quiere decir mejor?

Ej: maximizar beneficio, minimizar coste, son objetivos
15
I.
Introduccin
MAESTRIA PYGE
iii) Restricciones del problema, que consiste en definir un conjunto de ecuaciones e inecuaciones que restringen los valores de las variables de decisin a aquellos considerados como factibles. En el ejemplo, respetar la disponibilidad de piezas para la fabricacin de sillas y mesas: Piezas pequeas: 2x + 2y 8 Piezas grandes : x + 2y 6 Tambin se impone restricciones de no negatividad: x,y 0
Qu restricciones limitan las decisiones?

Ej: no exceder presupuesto, no usar ms piezas que las disponibles, etc. son restricciones iv) Resolucin del Modelo y Anlisis de la Solucin
16
I.
Introduccin
En resumen:
MAESTRIA PYGE
Max sa:
15x + 20y 2x + 2y 8 x + 2y 6 x,y 0
El ejemplo corresponde a un modelo de Programacin Lineal. Si adems restringimos los valores de x e y a nmeros enteros, tendramos un modelo de Programacin Entera. Por otra parte, si hubiese retornos crecientes a escala, deberamos emplear una funcin objetivo no lineal como f(x,y) = cxa + dyb con a,b >1, y tendramos un modelo de Programacin No Lineal.
17
I.
Introduccin
BIBLIOGRFIA EN INVESTIGACIN DE OPERACIONES
MAESTRIA PYGE
1. Introduccin a la Investigacin de Operaciones, F.S. Hillier y G.J. Lieberman, McGraw Hill, Sexta Edicin, 1997. 2. Investigacin de Operaciones, una introduccin, H.A. Taha, Prentice Hall, Mxico, Sexta Edicin, 1998. 3. Introduction to Management Science, F. Hillier, M. Hillier and G.J. Lieberman. Irwin McGraw-Hill, 1999. 4. Model Operations Research: A practical Introduction. M.W. Carter and C.C.Price. CRC Press, 2000. 5. Practical Management Science: Spreadsheet Modeling and Applications, Winston, W.L., Albright S.C. y Broadie M., International Thomson Publishing Company, 1997.
18
MAESTRIA PYGE
II. Modelos de Programacin Matemtica Programacin Lineal
Temario:
MAESTRIA PYGE
II.1. Introduccin II.2. Definiciones II.3. Suposiciones de la PL II.4. Ejemplos de modelamiento. II.5. Resolucin grfica de problemas. II.6. Anlisis de Sensibilidad. II.7. El Mtodo Simplex. II.8. Dualidad en Programacin Lineal. II.9. Anlisis de Sensibilidad o Post-Optimal
20

II.1 INTRODUCCIN
La programacin lineal es un caso especial de la programacin
MAESTRIA PYGE
matemtica, en donde todas las funciones que participan en el modelo son lineales.
Utilizacin:

Planificacin Gestin de recursos humanos y materiales Transporte Planificacin financiera Organizacin de la produccin. Una extensa gama de problemas que aparecen en las reas de tipo industrial, econmico, administrativo, militar, etc.
21

II.2 DEFINICIONES
Funcin Lineal.- una funcin f(x1, x2, x3,. xn) es una funcin
MAESTRIA PYGE
lineal de x1, x2, x3,. xn, si y solo si para algn conjunto de constantes c1, c2, c3,. cn, existe una funcin f(x1, x2, x3,. xn) = c1 x1+ c2 x2, c3 x3,. cn xn
Desigualdad Lineal.- una desigualdad f(x1, x2, x3,. xn) b
f(x1, x2, x3,. xn) b es lineal, si y solo si la funcin f(x1, x2, x3,. xn) es lineal y b es cualquier nmero real.
optimizacin, para el cual:
Se busca maximizar o minimizar una funcin lineal de variables de
Un problema de Programacin Lineal.- es un problema de

decisin. Los valores de las variables de decisin satisfacen un conjunto de restricciones. Cada restriccin es una ecuacin o una desigualdad lineal.
22

La Regin Factible y la Solucin ptima: Regin Factible.- Es el conjunto de todos los puntos que satisfacen todas las restricciones del problema de PL.
MAESTRIA PYGE
Solucin ptima.- Para un problema de maximizacin en PL la solucin ptima es el punto o conjunto de puntos de la regin factible con mayor valor de la funcin objetivo. Para un problema de minimizacin en PL la solucin ptima es el punto o conjunto de puntos de la regin factible con menor valor de la funcin objetivo.
23

Suposiciones de Proporcionalidad y Aditividad. El hecho de que la funcin objetivo de un problema de PL tiene
MAESTRIA PYGE
que ser una funcin lineal de las variables de decisin, tiene dos implicaciones:
La contribucin de cada variable de decisin a la funcin objetivo es
proporcional al valor de la variable de decisin. La contribucin a la funcin objetivo por parte de cualquier variable de decisin es independiente de los valores de las otras variables de decisin.
El hecho de que cada restriccin de un problema de PL tiene
que ser una desigualdad o igualdad lineal de las variables de decisin, tiene tambin dos implicaciones:
La contribucin de cada variable al lado izquierdo de cada
restriccin es proporcional al valor de la variable de decisin. La contribucin de cada variable al lado izquierdo de cada restriccin independiente de los valores de las otras variables de decisin.
24

Suposicin de Divisibilidad. La suposicin de divisibilidad requiere que cada variable de decisin pueda tomar valores fraccionarios. En muchas situaciones donde no se presenta la divisibilidad, redondear cada variable de la solucin ptima del problema de PL a un valor entero, puede proporcionar una solucin razonable ms no necesariamente ptima.
MAESTRIA PYGE
Suposicin de Certidumbre. La suposicin de certidumbre significa que tiene que conocerse con certidumbre cada parmetro (coeficiente de la funcin objetivo, coeficientes de las variables de las restricciones, lado izquierdo de las restricciones).
25
II.4 Ejemplos de modelamiento. MAESTRIA PYGE

i) Problema de Transporte (ENERGIA). El problema consiste en decidir cuntas unidades trasladar desde ciertos puntos de origen (plantas, ciudades, etc.) a ciertos puntos de destino (centros de distribucin, ciudades, etc..) de modo de minimizar los costos de transporte, dada la oferta y demanda en dichos puntos. Se suponen conocidos los costos unitarios de transporte, los requerimientos de demanda y la oferta disponible.
26
MAESTRIA PYGE
Por ejemplo, suponga que una empresa posee dos plantas que elaboran un determinado producto en cantidades de 250 y 450 unidades diarias, respectivamente. Dichas unidades deben ser trasladadas a tres centros de distribucin con demandas diarias de 200, 200 y 250 unidades, respectivamente. Los costos de transporte (en $/unidad) son:
C.Dist. 1 C.Dist.2 C.Dist.3 Planta 1 Planta 2 21 28 25 13 15 19
27
Diagrama: MAESTRIA PYGE

X11
C.D.1
Planta 1 X12 X21 Planta 2 X13 X23 C.D.3 X22 C.D.2
Orgenes
Destinos
28

Variables de decisin: xij = Unidades transportadas desde la planta i (i=1,2), hasta el centro de distribucin j (j=1,2,3)
MAESTRIA PYGE
Funcin Objetivo: Minimizar el costo total de transporte dado por la funcin: 21x11+25x12+15x13+28x21+13x22+19x23 Restricciones del problema: 1) No Negatividad: xij 0
2) Demanda: CD1 : x11 +x21 CD2 : x12 +x22 CD3 : x13 + x23
= 200 = 200 = 250

29
MAESTRIA PYGE
3) Oferta : P1 : x11 + x12 + x13 250 P2 : x21 + x22 + x23 450 Las variables de decisin deben aceptar soluciones como nmeros reales para tener un modelo de P.L.
30
MAESTRIA PYGE
ii) Problema de la dieta: este consiste en determinar una dieta de manera eficiente, a partir de un conjunto dado de alimentos, de modo de satisfacer ciertos requerimientos nutricionales. Supongamos que se tiene la siguiente informacin:
Leche Legumbre Naranjas Requerimientos (galon) (1 porcin) (unidad) Nutricionales Niacina Tianina Vitamina C Costo 3,2 1,12 32 2 4,9 1,3 0 0,2 0,8 0,19 93 0,25 13 15 45
31

Variables de decisin:
x1 : galones de leche utilizados en la dieta.
MAESTRIA PYGE
x2 : porciones de legumbre utilizadas en la dieta.

x3 : unidades de naranja utilizadas en la dieta.
Funcin Objetivo:
Minimizar el costo total de la dieta, dado por: 2 x1 + 0.2 x2 + 0.25 x3 Restricciones del problema:
Requerimientos mnimos de los nutrientes considerados:

3.2 x1 + 4.9 x2 + 0.8 x3 13 1.12 x1+ 1.3 x2 + 0.19 x3 15 32 x1+ + 93 x3 45 x1 0 ; x2 0 ; x3 0
32
iii) Problema de dimensionamiento de lotes:
MAESTRIA PYGE
Este consiste en hallar una poltica ptima de produccin para satisfacer demandas fluctuantes en el tiempo, de modo de minimizar costos de produccin e inventario, considerando la disponibilidad de diversos recursos escasos. Supongamos que una fabrica puede elaborar hasta 150 unidades en cada uno de los 4 perodos en que se ha subdividido el horizonte de planificacin y se tiene adicionalmente la siguiente informacin:
33
MAESTRIA PYGE
Periodos Demandas Costo Prod. Costo de Inventario (unidades) (US$/unidad) (US$/unidad)

1 2 3 4
130 80 125 195
6 4 8 9
2 1 2.5 3
Supuestos adicionales: 1) Existe un inventario inicial de 15 unidades. 2) No se acepta demanda pendiente o faltante (es decir, se debe satisfacer toda la demanda del periodo).
34
MAESTRIA PYGE
xt : nmero de unidades elaboradas en el periodo t.

It : nmero de unidades de inventario al final del periodo t. Funcin objetivo: Consiste en minimizar los costos de produccin y el costo de mantenimiento de inventario. 6x1+ 4x2 + 8x3 + 9x4 + 2I1 + I2 + 2.5I3 + 3I4
Notar que en el ptimo I4 ser 0, as que incluso podramos no incluirla, pero de todos modos la consideramos.
35
Restricciones del problema:
MAESTRIA PYGE
1) Restricciones de cotas, que reflejan la capacidad de produccin. xt 150 t Perodo 2) Restricciones de no negatividad xt 0 t Perodo
3) Restricciones de demanda
x1 + I0 I1 = 130 x2 + I1 I2 = 80 Periodo 1 Periodo 2 I0=15
x3 + I2 I3 = 125
x4 + I3 I4 = 195
Periodo 3
Periodo 4
36
iv) Problema de planificacin financiera:
MAESTRIA PYGE
Supongamos que un banco dispone de $250 millones para destinar a 4 tipo de crditos ofrecidos, los cuales tienen las siguientes, tasas de crdito:

Primer crdito corriente (PCC) Segundo crdito corriente (SCC) Crdito para el hogar Crdito personal
:12% :16% :16% :10%
37
La asignacin de estos crditos, debe satisfacer la siguiente poltica utilizada por la institucin:
MAESTRIA PYGE
El monto asignado a los PCC, debe ser al menos, el 55% del monto asignado a los crditos corrientes, y al menos un 25% del total del dinero prestado.
El SCC, no puede exceder el 30% del total del dinero prestado, por polticas tributarias el inters recibido por el banco no debe exceder a un retorno del 14% sobre el capital prestado. Cunto asignar a cada tipo de crdito, de la manera ms eficiente, respetando la poltica del banco?
38

Variables de decisin: x1 :Monto asignado al PCC. x2 : Monto asignado SCC.
MAESTRIA PYGE
x3 : Monto asignado al crdito para el hogar.

x4 : Monto asignado al crdito personal. Funcin Objetivo: Se propone maximizar los retornos recibidos en la asignacin, dados por: 0.12 x1 + 0.16 x2 + 0.16 x3 + 0.10 x4 Restricciones del problema: x1 0.55 ( x1 + x2 ) x1 0.25 ( x1 + x2 +x3 + x4 )
x2 0.30 ( x1 + x2 +x3 + x4 ) (0.12x1+0.16x2+0.16x3+0.10x4 ) 0.14 ( x1+ x2 +x3 +x4 )

Adicionalmente: x1 + x2 +x3 + x4 250
39
MAESTRIA PYGE
v) Problema de mezcla de productos: en este problema una refinera produce 4 tipos de gasolina (gas 1, gas 2, gas 3 y gas 4). Dos caractersticas importantes de cada gasolina son su nmero de performance (NP) y su presin de vapor (RVP), que estn dados por:
NP gas 1 107 RVP 5 Barriles diarios 3814
gas 2
gas 3 gas 4
93
87 108
8
4 21
2666
4016 1300
40
MAESTRIA PYGE
Estas gasolinas pueden ser vendidas directamente a un precio de $24,83 por barril o bien mezcladas para obtener gasolinas de aviacin (avgas A y avgas B). La calidad de estas dos ltimas junto con sus precios de venta son:
NP
RV
Precio por barril (US$)
avgas A Al menos 100 A lo ms 7 Avgas B Al menos 91 A lo ms 6
26,45 25,91
El NP y RVP de cada mezcla es un promedio de los respectivos NP y RVP de las gasolinas empleadas. Se desea obtener un plan de venta de las distintas gasolinas que maximice los retornos.
41

Variables de decisin: xj : cant. de barriles del gas j que son vendidos sin mezclar, con j = 1, 2, 3, 4.
MAESTRIA PYGE
xA : cant. de barriles de avgas A.
xB : cant. de barriles de avgas B.
xjA: cant. de gas j usado en avgas A. xjB: cantidad de gas j usado en avgas B.
Funcin objetivo: Max 24,83 (x1 + x2 + x3 + x4) + 26,45xA + 25,91xB Restricciones: x1 + x1A + x1B = 3814
x2 + x2A + x2B = 2666

x3 + x3A + x3B = 4016 x4 + x4A + x4B = 1300 x1A + x2A + x3A + x4A = xA x1B + x2B + x3B + x4B = xB
42

NP, avgas A:
MAESTRIA PYGE
NP, avgas B:
107x1A 93x 2 A 87x 3 A 108x 4 A 100 xA 107x1B 93x 2B 87x 3B 108x 4B 91 xB
RVP, avgas A:
5x1A 8x 2 A 4x 3 A 21x 4 A 7 xA
RVP, avgas B:
5 x 1B 8 x 2 B 4 x 3 B 21x 4 B 6 xB
43

vi) Problema de expansin de la capacidad de un Sistema de Potencia Elctrica: En este problema se desea planificar la expansin de la capacidad de un sistema elctrico para los siguientes T aos. La demanda (estimada) para el ao t corresponde a dt MW para t = 1, 2, ..., T. La capacidad existente del sistema corresponde a ct MW para el ao t = 1, 2, ..., T. Existen 2 alternativas para la expansin de la capacidad del sistema: 1) Usar plantas trmicas a petrleo; 2) Usar plantas trmicas a gas. Se requiere una inversin pt por MW instalado de una planta a petrleo que est operativa al comienzo del ao t, y el correspondiente costo para una planta a gas es gt. Por razones polticas y de seguridad, se ha decidido que no ms del 30% de la capacidad instalada, corresponda a plantas a gas (nuevas). Cada planta a petrleo tiene una vida de 20 aos y una planta a gas una vida de 15 aos. Se desea proponer un plan de expansin al mnimo costo posible.
44
MAESTRIA PYGE

Variables de decisin: xt : cantidad de MW expandidos en planta a petrleo al inicio del ao t, con t = 1, 2, ..., T.
MAESTRIA PYGE
yt : cantidad de MW expandidos en planta a gas al inicio del ao t, con t = 1, 2, ..., T. zt : cantidad total de MW disponible en plantas nuevas a petrleo al inicio del ao t. wt : cantidad total de MW disponible en plantas nuevas a gas al inicio del ao t.
45

Min
p t x t gt yt
T t 1
MAESTRIA PYGE
c t z t w t dt z t xk
k 1 t t
w t yk
k 1 t
t 15 t 15 t 1...T
t 20 t 20
wt
k t 14
zt
k t 19
wt 0,30 ct zt w t x t , yt , z t , w t 0
46

vii) Problema de Establecimiento del Horario de Trabajo: Una oficina de correos necesita de un nmero diferente de empleados de tiempo completo, para diferentes das de la semana. El nmero de empleados de tiempo completo requeridos para cada da se da en la taba siguiente:
DIA No. EMP. NECESARIO Lunes 17 Jueves 19 Domingo 11 No. EMP. NECESARIO Martes 13 Viernes 14 DIA No. EMP. NECESARIO Mircoles 15 Sbado 16 DIA
MAESTRIA PYGE
Las reglas sindicales sealan que cada empleado debe trabajar por 5 das consecutivos y despus descansar 2 das. La oficina de correos quiere cumplir con sus requerimientos diarios y utilizar solamente empleados de tiempo completo. Formule un PL para minimizar los empleados de tiempo completo
47

Variables de Decisin: xi : nmero de empleados que empieza a trabajar el da i
MAESTRIA PYGE
Funcin Objetivo:
Min z= x1 + x2 + x3 + x4 + x5 + x6 + x7 x1 x1 + x2 x1 + x2 + x3 x1 + x2 + x3 + x4 x1 + x2 + x3 + x4 + x5 x2 + x3 + x4 + x5 + x6 x3 + x4 + x5 + x6 + x7 + x4 + x5 + x6 + x7 + x5 + x6 + x7 + x6 + x7 + x7 17 13 15 19 14 16 11
Restricciones:
xi 0 (i=1,2,3,7)
48

PROBLEMAS PROPUESTOS: 1.- Supngase que la oficina de correos puede obligar a trabajar un da extra a la semana. Por ejemplo un empleado que ha trabajado de lunes a viernes, tendra que trabajar el sbado. Se paga al empleado 50 dlares diarios por los 5 primeros das y 62 dlares por el da extra (en caso de haber trabajado). Formule un PL cuya solucin permita a la oficina de correos minimizar el costo para cumplir con sus necesidades laborales semanales. 2.-Supngase que la oficina de correos tiene una planta de 25 empleados a tiempo completo y no se le permite ni contratar ni despedir empleados. Formular un PL para programar el horario de los empleados a fin de maximizar el nmero de fines de semana libres recibidos por los empleados.
MAESTRIA PYGE
49

PROBLEMAS PROPUESTOS: 3.- Los empleados del Departamento de Polica trabajan dos turnos de 6 horas diarias, escogidos entre los siguientes 4 turnos posibles: 1) de 0h a 6 h, 2) de 6h a 12h, 3) de 12 a 18h, 4) de 18 a 24h. Se necesita el siguiente nmero de policas por cada turno: 1) 15, 2) 5, 3) 12 y 4) 6. A los policas que tienen turno consecutivos se les paga 12 dlares la hora y a los policas que no tienen turnos consecutivos se le para 18 dlares la hora. Formule un PL para minimizar los costos y cubrir la demanda diaria de fuerza laboral del Departamento de Polica
MAESTRIA PYGE
50
II.5. Resolucin grfica de problemas. MAESTRIA PYGE

Consideremos el siguiente problema a resolver grficamente: Max sa: z = 3x1 + 5x2 x1 2x2 3x1 + 2x2 x1 , x2 0 4 12 18
51
MAESTRIA PYGE
x2 9
Regin de puntos factibles Funcin Objetivo
6 4
x1
52
MAESTRIA PYGE
x2 9
Regin de puntos factibles Funcin Objetivo
6 4
x1
53
MAESTRIA PYGE
x2 9 x* 6 4
Regin de puntos factibles Funcin Objetivo Solucin Optima
6
54
MAESTRIA PYGE
x2 9 x* 6 4
6
55
MAESTRIA PYGE
x2 9 x* 6 4
6
56
MAESTRIA PYGE
x2 9 x* 6 4 x*
6
57
MAESTRIA PYGE
En primer lugar, se debe obtener la regin de puntos factibles en el plano, obtenida por medio de la interseccin de todos los semi-espacios que determinan cada una de las inecuaciones presentes en las restricciones del problema. A continuacin, con el desplazamiento de las curvas de nivel de la funcin objetivo en la direccin de crecimiento de la funcin (que corresponde a la direccin del vector gradiente de la funcin, z(x1,x2) = (3,5)T, se obtiene la solucin ptima del problema en la interseccin de las rectas: 2x2 = 12 y 3x1+2x2 = 18 (restricciones activas). Esto es: x1 * = 2 x2 * = 6
z* = 3 x1* + 5 x2* = 36
58

Algunas reflexiones Los ejercicios anteriores plantean un PROBLEMA DE DECISIN
MAESTRIA PYGE
Hemos tomado una situacin real y hemos construido sus equivalentes matemticos: MODELO MATEMTICO Durante la formulacin de los modelos matemticos, hemos considerado el mtodo cuantitativo que nos permitir resolver el modelo numricamente ALGORITMO El algoritmo es un conjunto de instrucciones que siguiendo de manera ordenada producen una solucin numrica
NUEVA DEFINICION
Ciencia para la representacin de problemas reales mediante modelos matemticos que junto con mtodos cuantitativos nos permiten obtener una solucin numrica a los mismos.
59
Notar que se pueden dar otras situaciones en la bsqueda de una solucin ptima para esta clase de problemas: 1) La solucin ptima exista pero haya ms de una. En el ejemplo, considerese la nueva funcin objetivo: z = 6x1+4x2. 2) El problema no tenga solucin, dada una regin de puntos factibles no - acotada. En el ejemplo, reemplace cada desigualdad por una . 3) El problema no tenga solucin, porque no existen puntos factibles. En el ejemplo, suponga que agregamos la restriccin: x1 5.
MAESTRIA PYGE
60
II.3. Anlisis de sensibilidad.

MAESTRIA PYGE
Consideremos otro ejemplo: max z= 15x + 20 y s.a. 2x+2y8 x+2y 6 x,y0
61
MAESTRIA PYGE
Max 15x 20y sa : 2x 2y 8

4 3
x 2y 6 x, y 0
6
62
A partir de la resolucin grfica del problema se tiene:

MAESTRIA PYGE
Solucin ptima : x1*= 2 ; x2*= 2 Valor ptimo : z = z(2,2) = 70
El anlisis de sensibilidad permite responder, entre otras, las siguientes preguntas:

1) Cul es el intervalo de variacin de algn coeficiente de la funcin objetivo, de modo que la actual solucin siga siendo la ptima?
63
MAESTRIA PYGE
Max 15x 20y sa : 2x 2y 8

4
x 2y 6 x, y 0
3 2
6
64
MAESTRIA PYGE
Max 15x 20y sa : 2x 2y 8

4
x 2y 6 x, y 0
6
65
MAESTRIA PYGE
Max 15x 20y sa : 2x 2y 8

4
x 2y 6 x, y 0
6
66
MAESTRIA PYGE
Max 15x 20y sa : 2x 2y 8

4
x 2y 6 x, y 0
6
67
MAESTRIA PYGE
Max 15x 20y sa : 2x 2y 8

4
x 2y 6 x, y 0
6
68
MAESTRIA PYGE
Max 15x 20y sa : 2x 2y 8

4
x 2y 6 x, y 0
6
69
MAESTRIA PYGE
Max 15x 20y sa : 2x 2y 8

4
x 2y 6 x, y 0
6
70
MAESTRIA PYGE
Max 15x 20y sa : 2x 2y 8

4
x 2y 6 x, y 0
6
71
Sea
MAESTRIA PYGE
z = c1x1+c2x2
La solucin ptima de la nueva funcin, seguir siendo: x1*= 2 ; x2*= 2 s:
c1 1 1 c2 2
72
MAESTRIA PYGE
Tambin podemos estudiar el intervalo de un slo coeficiente, dejando el resto de los parmetros fijos:
Para C1: Para C2:
c1 1 1 20 2
10 c1 20
15 1 1 c2 2
15 c 2 30
73
MAESTRIA PYGE
2) Cul es el intervalo de variacin de los coeficientes del lado derecho (trminos libres) de las restricciones, de modo que la actual solucin siga siendo la ptima? Estudiaremos por separado las variaciones de cada uno de los coeficientes del lado derecho de las restricciones, de modo preservar la geometra del problema, esto es, que se conserven las mismas restricciones activas de la solucin ptima inicial.
74
MAESTRIA PYGE
Max 15x 20y sa : 2x 2y 8

4 3 2
x 2y 6 x, y 0
8
75
MAESTRIA PYGE
Max 15x 20y sa : 2x 2y 8

4 3 2
x 2y 6 x, y 0
8
76
Primera restriccin.
MAESTRIA PYGE
La mayor variacin del coeficiente del lado derecho se alcanza en x=0 y y=4, de donde se obtiene: z(0,4) = 15 0 + 20 4 = 80 y b1* = 0 + 2 4 = 8 La menor variacin del coeficiente del lado derecho se alcanza en: x=4 ; y=0, de donde se obtiene: z(4,0) = 15 4 + 20 0 = 60 y b1 = 4 + 2 0 = 4 De aqu, se calcula el precio sombra P1, que indica la razn o tasa de cambio de la funcin objetivo con respecto al cambio en una unidad del lado derecho:
P1 z(0,4) z(4,0) 80 60 5 * b1 b1 84
77
MAESTRIA PYGE
Max 15x 20y sa : 2x 2y 8

4
x 2y 6 x, y 0
6
78
MAESTRIA PYGE
Max 15x 20y sa : 2x 2y 8

4
x 2y 6 x, y 0
6
79

Segunda restriccin. La mayor variacin del coeficiente del lado derecho se alcanza en x=6 y y=0, de donde se obtiene:
MAESTRIA PYGE
z(0,4) = 15 x 6 + 20 x 0 = 90 y b1*= 2 x 6 + 2x0 = 12 La menor variacin del coeficiente del lado derecho se alcanza en: x=0 ; y= 3, de donde se obtiene: z(4,0) = 15 x 0 + 20 x 3 = 60 y b1= 2 x 0 + 2 x 3 = 6 De aqu, se calcula el precio sombra P2, que indica la razn o tasa de cambio de la funcin objetivo con respecto al cambio en una unidad del lado derecho: z(6,0) z(0,3) 90 60 P2 5 * b2 b2 12 6
80

Ejemplo 2 Una fbrica produce 2 tipos de juguetes de madera: soldados y trenes se vende un soldado en 27 dlares y se usan 10 dlares de materia prima y 14 dlares en mano de obra. Se vende un tren en 21 dlares y se usan 9 de materia prima y 10 dlares en mano de obra. La produccin de soldados y trenes necesita de 2 tipos de trabajo especializado: carpintera y acabado. Un soldado requiere de 1 hora de carpintera y 2 de acabado. Un tren requiere de 1 hora de carpintera y una de acabado. La empresa dispone de 80 horas de carpintera y 100 de acabado y puede conseguir toda la materia prima necesaria. La demanda de trenes no tiene lmite pero no se pueden vender mas de 40 soldados a la semana. Formule un PL para maximizar la ganancia semanal.
MAESTRIA PYGE
81

x nmero de trenes y nmero de soldados
MAESTRIA PYGE
max z = 3x + 2y s.a. 2x+y 100 x +y 80 x 40 x,y0
ganancia restriccin de acabado restriccin de carpintera restriccin de demanda de soldados
82
MAESTRIA PYGE
max z= 3x + 2y s.a. 2x+y 100 x+y 80 x 40 x, y 0
83
II. Modelos de Programacin Matemtica Programacin Lineal solucin MAESTRIA PYGE
x=20 y=60
84
A partir de la resolucin grfica del problema se tiene:

MAESTRIA PYGE
Solucin ptima : x*= 20 ; y*= 60 Valor ptimo : z = z(20,60) = 180
El anlisis de sensibilidad permite responder, entre otras, las siguientes preguntas:

1) Cul es el intervalo de variacin de algn coeficiente de la funcin objetivo, de modo que la actual solucin siga siendo la ptima?
85
MAESTRIA PYGE
86
Sea
MAESTRIA PYGE
z = c1x1+c2x2
La solucin ptima de la nueva funcin, seguir siendo: x*= 20 ; y*= 60 s: c1 2 1 c2
87
MAESTRIA PYGE
Tambin podemos estudiar el intervalo de un slo coeficiente, dejando el resto de los parmetros fijos:
Para C1:
c1 2 1 2
Para C2:
2 c1 4
3 2 1 c2
3 c2 3 2
88
MAESTRIA PYGE
2) Cul es el intervalo de variacin de los coeficientes del lado derecho (trminos libres) de las restricciones, de modo que la actual solucin siga siendo la ptima? Estudiaremos por separado las variaciones de cada uno de los coeficientes del lado derecho de las restricciones, de modo preservar la geometra del problema, esto es, que se conserven las mismas restricciones activas de la solucin ptima inicial.
89
max z= 3x + 2y MAESTRIA PYGE

s.a. 80 40 0
2x+y 100 x+y x x, y
90

Primera restriccin. La mayor variacin del coeficiente del lado derecho se alcanza en x=60 y y =0, de donde se obtiene:
MAESTRIA PYGE
z(60,0) = 3 60 + 2 0 = 180 y b1* = 2 60 + 1 0 = 120 La menor variacin del coeficiente del lado derecho se alcanza en: x= 4 ; x2 = 0, de donde se obtiene:
z(40,0) = 3 40 + 2 0 = 120 y b1 = 2 40 + 1 0 = 80
Obsrvese que, aunque para 80b1120 la base actual es ptima los valores de las variables de decisin y de la funcin objetivo cambian. Por ejemplo si 80b1100 la solucin ptima cambiar del punto B a algn otro punto en el segmento AB. Similarmente si 100b1120 la solucin ptima cambiar del punto B a algn otro punto en el segmento AD.
91
MAESTRIA PYGE
Para ilustrar la idea, sea b1 el nmero de horas de acabado disponibles. Si cambiamos b1 a 100+ sabemos que la base ser ptima para -20 20 la solucin para el PL ser todava e punto en el que las restricciones de acabado y carpintera son obligatorias. Por lo tanto si cambiamos b1 = 100+ se puede encontrar los nuevos valores de las variables al resolver 2x + y = 100 + y x + y =80
Esto produce que x=20+, y y=60- lo que significa que si aumentamos el nmero de horas de acabado da como resultado un aumento de nmero de soldados producidos y una disminucin de trenes producidos.
92

De aqu, se calcula el precio sombra P1, que indica la razn o tasa de cambio de la funcin objetivo con respecto al cambio en una unidad del lado derecho:
MAESTRIA PYGE
z(60 ,0) z(40 ,0) 180 120 P1 1.5 * b1 b1 120 80
93
MAESTRIA PYGE
max z= 3x + 2y s.a. 2x+y 100 x+y 80 x 40 x, y 0
94

Segunda restriccin. La mayor variacin del coeficiente del lado derecho se alcanza en x=0 y y=100, de donde se obtiene:
MAESTRIA PYGE
z(0,100) = 30 + 2100 = 200 y b2*= 10 + 1100 = 100 La menor variacin del coeficiente del lado derecho se alcanza en: x=0 ; y=60, de donde se obtiene:
z(0,60) = 30 + 260 = 120 y b2= 10 + 160 = 60

Obsrvese que, aunque para 60b280 la base actual es ptima los valores de las variables de decisin y de la funcin objetivo cambian. Por ejemplo si 60b280 la solucin ptima cambiar del punto B a algn otro punto en el segmento BF. Similarmente si 80b1100 la solucin ptima cambiar del punto B a algn otro punto en el segmento AC.
95
MAESTRIA PYGE
Ahora, sea b2 el nmero de horas de carpintera disponibles. Si cambiamos b2 a 80+ sabemos que la base ser ptima para -20 20 la solucin para el PL ser todava e punto en el que las restricciones de acabado y carpintera son obligatorias. Por lo tanto si cambiamos b2 = 80+ se puede encontrar los nuevos valores de las variables al resolver 2x + y = 100 y x + y =80 +
Esto produce que x=20-, y y=60+2 lo que significa que si aumentamos el nmero de horas de carpintera da como resultado una disminucin del nmero de soldados producidos y un disminucin de trenes producidos.
96
MAESTRIA PYGE
De aqu, se calcula el precio sombra P2, que indica la razn o tasa de cambio de la funcin objetivo con respecto al cambio en una unidad del lado derecho:
z(0,100 ) z(0,60 ) 200 120 P2 2 * b2 b2 100 60
97
Supongamos que cambiamos b3 = 40+ se puede encontrar los nuevos valores de las variables al resolver
MAESTRIA PYGE
2x + y = 100
x + y =80
Esto produce que la solucin original x=20, y y=60. Entonces se puede demostrar que la base actual es ptima para un -20, lo que significa que si se cambia el lado derecho de esta restriccin en el intervalo en la cual la base es ptima, la solucin del PL no cambia.
98
II.4. El Mtodo Simplex.

MAESTRIA PYGE
Un PL puede tener restricciones en forma de igualdad o de desigualdad. Tambin pueden tener variables que tienen que ser no negativas o no tener restriccin de signo. Para usar el Algoritmo Simplex hay que transformar el PL en un problema equivalente, en el cual:
Todas las restricciones son ecuaciones Todas las variables son no negativas
Un PL que se encuentra en esta forma est en su forma ESTANDAR.

99
MAESTRIA PYGE
Ejemplo 1 de transformacin en su forma Estandar

Una Empresa produce dos tipos de cinturones: El modelo de lujo y el modelo regular. Cada tipo requiere un metro de cuero. El cinturn regular requiere de una hora de trabajo especializado y el de lujo necesita de dos horas. Se dispone semanalmente de 60 horas de mano de obra especializada y 40 metros de cuero. Si cada cinturn regular y cada cinturn de lujo contribuyen a las ganancias con 3 y 4 dlares cada uno; cual es el plan de produccin para generar la mxima utilidad?
100
Si definimos:
MAESTRIA PYGE
X1 = Nmero de cinturones de lujo producidos X2 = Nmero de cinturones regulares producidos El modelo sera: Max Z= 4X1+3X2 s.a. X1+ X2 40 (Restriccin del cuero) 2X1+ X2 60 (Restriccin de mano de obra) X1, X2 0 (Restriccin de no negatividad)
101
El modelo en la forma estandar:
MAESTRIA PYGE
Max Z= 4X1+3X2 s.a. X1 + X2 + S1 = 40 2X1+ X2 + S2 = 60 X1, X2, S1 , S2 0
(Restriccin del cuero) (Restriccin de mano de obra) (Restriccin de no negatividad)
102
II. Modelos de Programacin Matemtica Programacin Lineal Ejemplo 2 de transformacin en su forma Estandar MAESTRIA PYGE
Min Z= 50X1+20X2 +30X3 +80X4 s.a. 400X1+ 200X2 + 150X2 + 500X2 500 3X1 + 2X2 6 2X1 + 2X2 + 4X3 + 4X4 10 2X1 + 4X2 + X3 + 5X4 8 X1, X2 , X3 , X4 0 En la Forma Estadar: Min Z= 50X1+20X2 +30X3 +80X4 s.a. 400X1+ 200X2 + 150X2 + 500X2 E1 = 500 3X1 + 2X2 E2 =6 2X1 + 2X2 + 4X3 + 4X4 E3 = 10 2X1 + 4X2 + X3 + 5X4 E4 = 8 X1, X2 , X3 , X4 ,E1 ,E2 ,E3 ,E4 0
103
II. Modelos de Programacin Matemtica Programacin Lineal Ejemplo 3 de transformacin en su forma Estandar MAESTRIA PYGE
Max Z= 20X1+15X2 s.a. X1
100 X2 100 50X1 + 35X2 4000 20X1 + 15X2 2000 X1, X2 0
En la Forma Estadar: Max Z= 20X1+15X2 s.a. X1 +S1 = 100 X2 +S2 = 100 50X1 + 35X2 +S3 = 4000 20X1 + 15X2 E4 = 2000 X1, X2 ,S1 ,S2 ,S3 ,E4 0
104

II.4. El Mtodo Simplex. En lo que sigue consideremos el siguiente programacin lineal en su forma estndar: Min c1x1 + c2x2 + ... + cnxn sa a11x1 + a12x2 + ... + a1nxn = b1 a21x1 + a22x2 + ... + a2nxn = b2 ... ... ... am1x1 + am2x2 + ... + amnxn = bm xi 0, i = 1, 2, ..., n Matricialmente escrito como: Min cTx s.a. Ax = b x0 y mn problema de
MAESTRIA PYGE
105
MAESTRIA PYGE
En resumen, es posible reformular de manera equivalente el problema usando las siguientes justificaciones:
1) Siempre es posible llevar un problema de maximizacin a uno de minimizacin. Si f(x) es la funcin objetivo a maximizar y x* es la solucin ptima: f(x*) f(x) , x factible - f(x*) - f(x) , x factible
\ x* es tambin mnimo de - f(x)
106

2) Cada restriccin del tipo puede ser llevada a una ecuacin de igualdad usando una (nueva) variable de holgura no negativa, con un coeficiente nulo en la funcin objetivo.
MAESTRIA PYGE
3) De igual modo, cada restriccin del tipo puede ser llevada a una ecuacin de igualdad usando una variable de exceso no negativa. 4) Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no negativas.
107

Considrese un sistema Ax = b de m ecuaciones lineales con n variables (supngase nm)
MAESTRIA PYGE
DEFINICION: Se obtiene una solucin bsica de Ax = b, haciendo n-m variables (variables no bsicas VNB) iguales a cero y resolviendo el sistema resultante de m variables que quedan (variables bsicas VB).
Naturalmente, las selecciones diferentes de variables no bsicas VNB llevaran a soluciones bsicas diferentes. La bsqueda de la solucin ptima se restringe a encontrar un vrtice ptimo y cada vrtice del conjunto de las restricciones del problema, llamado regin de puntos factibles, corresponde a una solucin bsica factible del sistema Ax = b. Esta solucin bsica factible, corresponde a su vez a aquellas soluciones que resultan de resolver el sistema para exactamente m variables, fijando las restantes n-m en cero, llamadas respectivamente variables bsicas y no-bsicas, que adems deben satisfacer condiciones de no-negatividad
108
II. Modelos de Programacin Matemtica
Programacin Lineal
EJEMPLO 1 DE SOLUCION BASICA FACTIBLE:
MAESTRIA PYGE
max Z= 4x1 + 3 x2 s.a. x1 + x2 40 2x1 + x2 60 x1, x2 0

Variables Bsicas x1,x2 x1,s1 x1,s2 x2,s1 x2,s2 s1,s2 Variables No Bsicas s1,s2 x2,s2 x2,s1 x1,s2 x1,s1 x1,x2
max s.a.
Z= 4x1 + 3 x2 x1 + x2 +s1 2x1 + x2 +s2 x1, x2, s1, s2 0

Punto x2= 20 s1= 10 s2= -20 x2= 60 s2= 20 s2= 30 E C
= 40 = 60
Solucin Bsica Factible s1=s2= 0 x2=s2= 0 x2=s1= 0 X1=s2=0 x1=s1= 0 x1=x2= 0 x1= 20 x1= 30 x1= 40 s1= -20 x2= 40 s1= 40
No es sbf porque s2<0 No es sbf porque s1<0 B F
109
Programacin Lineal
MAESTRIA PYGE
110
Programacin Lineal
EJEMPLO 2 DE SOLUCION BASICA FACTIBLE:
MAESTRIA PYGE
max Z= x1 + 2 x2 + 2 x3 s.a. 2 x1 + x2 8 x3 10 x1, x2, x3 0

Variables Bsicas x1,x3 s1,s2 s1,x3 x2,x3 x2,s2 x1,s2 x1=4 s1=8 s1=8 x2=8 x2=8 x1=4 x3=10 s2=10 x3=10 x3=10 s2=10 s2=10 x2=s1=s2=0 D x1=x2=x3=0 F x1=x2=s2=0 E x1=s1=s2=0 C x1=x3=s2=0 B x2=x3=s1=0 A 24 0 20 36 16 4
111
Solucin Bsica Factible
Punto
MAESTRIA PYGE
112
MAESTRIA PYGE
Teorema Fundamental de la Programacin Lineal:

Si un problema tiene solucin ptima, tiene una solucin bsica factible ptima.
113

Dada una matriz B de m x m invertible, esta induce una particin de las variables y parmetros del modelo como se muestra a continuacin:
MAESTRIA PYGE
n
B A=
D m
x1 xB x x 2 xn xD
nm
c B c c D
nm
xB :variables bsicas. xD :variables no bsicas.

m
n-m
cB :costos bsicos.
cD :costos no bsicos.
B : es llamada una matriz de base
114

Supongamos el problema en la forma estandar:
MAESTRIA PYGE
Max z= 60 x1 + 30 x2 +
20 x3 + 0 s1 + 0 s2 + 0s3
s1 =48 + s2 = 20 + s3 = 20
s.a:
8 x1 + 6 x2 + x3 + 4 x1 + 2 x2 + 1.5 x3 2 x1 + 1.5 x2 + 0. 5 x3 x1, x2, x3, s1, s2, s3 0
Donde la solucin es:
z= 280 con s1=24 ,x3=8 y x1=2

las variables bsicas son: s1,x3,x1 las variables no bsicas son: x2,s2,s3
115

Por lo tanto el sistema anterior puede expresarse como: Max z= CB xB + CD xD s.a: B xVB + D xD = b xB , xD 0 Es decir:
max z= 0 20 60 S1 X3 X1 + 30 0 0 x2 s2 s3
MAESTRIA PYGE
s.a. 1
8
4 2 0 0 0
S1
X3 X1 +
6
2 1.5
0
1 0 x2 s2 s3
0
0 1 0 0 0
x2
s2 s3
0 1.5 0 0.5 S1 X3 X1
116

Multiplicando las restricciones: B xB + D xD = b por B-1:
MAESTRIA PYGE
B-1 B xB + B-1 D xD = B-1 b o bien: xB + B-1 D xD = B-1 b
Donde:
1 B-1= 0 0 2 2 -0.5 -8 -4 1.5
117

Sustituyendo en nuestro ejemplo:
s1
MAESTRIA PYGE
1 + 0
2 2
-8 -4
6 2
0 1
0 0
x2 s2 =
1 0
2 2
-8 -4
48 20
x3
x1
-0.5
1.5
1.5
s3
-1
1.5
O bien:
s1
x3 x1 +
-2
-2 1.25
2
2 -0.5
-8
-4 1.5
x2
s2 s3 =
24
8 2
118

Ahora expresemos la funcin objetivo de la misma manera: Tomemos las restricciones B xB + D xD = b y multipliquemos por el vector CBB-1
MAESTRIA PYGE
CB xB + CB B-1DxD= CBB-1 b z- CB xB - CD xD =0 Sumando las dos ltimas relaciones: z+(CB B-1D- CD)xD= CBB-1 b
119
MAESTRIA PYGE
Criterio de Optimalidad:
T T c T x cB x B cD xD T B
T c B b B D x B cD xD 1
T T T cB B b cD cD B D xB xD
valor actual de la funcin obj.
vector de costos reducidos.
120
MAESTRIA PYGE
La ecuacin que define cada uno de los costos reducidos es: T 1 rj c j cB B Aj Donde j es el ndice de variable no-bsica y Aj la respectiva columna en A de esa variable.
La actual solucin bsica factible es ptima ssi rj j, existe una variable no bsica xp con costo reducido negativo, que entra a la nueva base.
121
MAESTRIA PYGE
Para decidir quin deja la base, es necesario calcular el mayor valor que puede tomar la variable entrante que garantiza la factibilidad de la nueva solucin bsica, con:
y1 0 y1 p x y 2 0 B 1A 2 p B 1b j x y m0 mp
y se debe calcular:
yi0 yk 0 Min / yip 0 xk deja la base ykp yip

122

Ejemplo. Resolver el siguiente problema de P.L. Max 40x + 60y sa: 2x + y 70 x + y 40 x + 3y 90 x,y 0 Se deben agregar 3 variables de holgura ( s1 , s2 , s3 var.bsicas), y llevar a forma estndar (x1 = x y x2 = y). Min sa: x1 + x2 x1 + 3x2 -40x1 60x2 2x1 + x2 + s1 + s2 = 70 = 40 + s3 = 90
MAESTRIA PYGE
x1, x2, x3, s1 , s2 , s3 0,
123

Tabla inicial:
MAESTRIA PYGE
x1
2 1 1 -40
x2
1 1 3 -60
s1
1 0 0 0
s2
0 1 0 0
s3
0 0 1 0 70 40 90 0
124
MAESTRIA PYGE
Usamos como variable entrante a la base x2 (pues r2<0).

x1
2 1 1 -40
x2
1 1 3 -60
s1
1 0 0 0
s2
0 1 0 0
s3
0 0 1 0 70 40 90 0
Se calcula Min { 70/1, 40/1, 90/3 } = 30, por lo tanto sale s3.
125
MAESTRIA PYGE
Actualizando, queda la siguiente tabla (no ptima), donde la variable entrante a la base es x1 (pues r1<0).
x1
5/3 2/3 1/3 -20
x2
0 0 1 0
s1
1 0 0 0
s2
0 1 0 0
s3
-1/3 -1/3 1/3 20 40 10 30 1800
Se calcula Min { 40/(5/3), 10/(2/3), 30/(1/3) } = 15, por lo tanto s2 deja la base actual.
126
Actualizando, queda la siguiente tabla final:
MAESTRIA PYGE
x1
0 1 0 0
x2
0 0 1 0
s1
1 0 0 0
s2
-5/2 -1/3 1/3 20
s3
- 10 15 15 25 2100
Como todos los costos reducidos son mayores o iguales que cero nos encontramos en la solucin ptima.
127
MAESTRIA PYGE
x 1 15 x B x 2 25 s1 15
z* = - 40 x 15 - 60 x 25 = - 2100
s2 0 xD s3 0
En la formulacin inicial, tenemos como solucin ptima x*=15, y *=25, con valor ptimo 2.100.
128
Ejemplo 2 del mtodo Simplex MAESTRIA PYGE

Min Z= 2X1 -3X2 s.a. X1 + X2 4 X1 - X2 6 X1, X2 0
129
Mtodo 1
-Z
X1
X2 S1 S2 ld
Variable Bsica
Razn
MAESTRIA PYGE
Min Z= 2X1 - 3X2 s.a. X1 + X2 4 X1 - X2 6 X1, X2 0
1 0 0
2 1 1
-3 1 -1
0 1 0
0 0 1
0 -Z=0 4 S1=4 6 S2=6 (4/1)=4 Ninguna
-Z
1 0 0
X1
5 1 2
X2 S1 S2 ld
0 1 0 3 1 1 0 0 1
Variable
Bsica
12 -Z=12 4 X2=4 10 S2=10

130
Mtodo 2
X1
X2 S1 S2 ld
Variable Bsica
Razn
MAESTRIA PYGE
Max -Z= -2X1 +3X2 s.a. X1 + X2 4 X1 - X2 6 X1, X2 0
1 0 0
-2 1 1
3 1 -1
0 1 0
0 0 1
0 Z=0 4 S1=4 6 S2=6 (4/1)=4 Ninguna
-Z
1 0 0
X1
-5 1 2
X2 S1 S2 ld
0 1 0 -3 1 1 0 0 1
Variable
Bsica
12 Z=-12 4 X2=4 10 S2=10

131
Resumen del Mtodo Simplex:
MAESTRIA PYGE
Paso 0: Escribir el problema de programacin lineal en su forma estndar. Paso 1: Escoger una solucin bsica factible inicial. Paso 2: Escoger una variable no - bsica con costo reducido negativo que determina la variable entrante y seguir al paso tres. Sin embargo, si todos los costos reducidos son mayores que cero , parar, ya que la actual solucin es la ptima. Paso 3: Calcular el criterio de factibilidad que determina que variable deja la base. Si todos los cuocientes son negativos: problema no - acotado, parar. Paso 4: Actualizar la tabla de modo de despejar el valor de las nuevas variables bsicas, los costos reducidos y el valor de la funcin objetivo. Volver al Paso 2.
132
II. Modelos de Programacin Matemtica Programacin Lineal II. Modelos de Programacin Matemtica Programacin Lineal
MAESTRIA PYGE
No siempre es fcil obtener una solucin bsica factible inicial, en las variables originales del modelo. Para conseguir esto existen varios procedimientos como son:

Mtodo de la M grande. Mtodo Simplex de dos fases.
133
MAESTRIA PYGE
INTRODUCCIN Hasta el momento slo se han estudiado problemas en la forma estndar. Maximizar Z. Restricciones de la forma menor igual. Todas las variables no negativas
FORMA ESTANDAR Maximizar Z= Sujeto a: 3X1 X1 + 5X2 2X2 2X2
3X1 + X1, X2
4 12 18 0
134
MAESTRIA PYGE
Existen variaciones cuando:

Restricciones en forma de igualdad
Lados derechos negativos

Restricciones de la forma mayor igual que Funcin objetivo minimizar
135

Mtodo de la M grande. Paso 1: Modifique las restricciones de tal manera que el lado derecho de cada restriccin sea no negativa. Paso 2: Transforme cada restriccin de desigualdad a la forma estandar Paso 3: Si la restriccin i es una igualdad o un restriccin de aadir una variable artificial ai Paso 4: Sea M un nmero positivo muy grande. Si el PL es de minimizacin aadir (para cada variable artificial) Mai a la funcin objetivo. Si el PL es de maximizacin aadir (para cada variable artificial) -Mai a la funcin objetivo. Paso 5: Ya que cada variable artificial estar en la funcin objetivo (rengln cero) eliminar todas las variables artificiales de la funcin objetivo (rengln cero) Paso 5: Resolver el problema con el mtodo simplex.
MAESTRIA PYGE
136

1. RESTRICCION EN FORMA DE IGUALDAD
MAESTRIA PYGE
Cualquier restriccin del tipo
a11 X1 + a12 X2 + a13 X3 + + a1n Xn =b1

Es equivalente a a11 X1 + a12 X2 + a13 X3 + + a1n Xn b1 a11 X1 + a12 X2 + a13 X3 + + a1n Xn b1
Lo que es inconveniente pues aumenta el nmero de restricciones
137
MAESTRIA PYGE
Lo que se hace entonces es introducir variables artificiales Cambiemos la tercera restriccin de desiguladad de Wyndor Glas c.o. por una igualdad
FORMA ESTANDAR Maximizar Z= Sujeto a:
3X1 X1
5X2 2X2 2X2
3X1 + X1, X2
4 12 18 0
138
MAESTRIA PYGE
139
MAESTRIA PYGE
140
MAESTRIA PYGE
141
MAESTRIA PYGE
142
MAESTRIA PYGE
143
MAESTRIA PYGE
144
MAESTRIA PYGE
PROBLEMA REAL
PROBLEMA ARTIFICIAL
5 x2 Max z= s.a. 3 x1 + 5 x2 M x5
Max z= s.a.
x1
x1
x1
2
3 x1 + 2
x2
x2
12
18 3 x1 +
2
2
x2
x2
12
18
x1
x2
0
As: 3
x1
x1
,
+ 2
x2
x2 + x5
0
18
145
MAESTRIA PYGE
146
MAESTRIA PYGE
147
MAESTRIA PYGE
148
MAESTRIA PYGE
149
MAESTRIA PYGE
150
MAESTRIA PYGE
151
MAESTRIA PYGE
152
MAESTRIA PYGE
153
MAESTRIA PYGE
154
MAESTRIA PYGE
155
MAESTRIA PYGE
156
MAESTRIA PYGE
157
MAESTRIA PYGE
158
MAESTRIA PYGE
159
MAESTRIA PYGE
160

Ejemplo: Max sa: 2x1 + x2 10x1 + 10x2 9 10x1 + 5x2 1 x1,x2 0
MAESTRIA PYGE
Se debe agregar una variable de holgura (x3) y una variable de exceso (x4), y llevarlo a su forma estndar. Min -2x1 - x2 sa: 10x1 + 10x2 +s3 =9 10x1 + 5x2 - e4 = 1 x1,x2, x3, x4 0
161

Mtodo Simplex de dos Fases.
Fase 0: Usamos los pasos 1,2 y 3 del mtodo de la M grande Fase 1: Paso 1: Por el momento, ignorar la funcin objetivo original. En su lugar resuelva un PL cuya funcin objetivo es min w= ai . La resolucin de este programa lineal har las variables necesariamente iguales a cero. Ya que cada ai 0, la solucin del PL corresponder a uno de los 3 casos siguientes: caso 1: El valor ptimo de w>0. En este caso el problema no tiene solucin caso 2: El valor ptimo de w=0, y no hay variables artificiales en la base ptima de la fase I. En este caso omitimos todas las columnas que corresponden a las variable artificiales en el cuadro de la fase I. Combinamos la funcin objetivo original con las restricciones del cuadro ptimo de la fase I. Pasamos a la fase II caso 3: El valor ptimo de w=0, y por lo menos una variable artificial est en la base ptima de la fase I. En este caso podemos encontrar la solucin para el PL original, si al final de la fase I, omitimos del cuadro ptimo de la fase I todas las variables artificiales no bsicas y cualquier variable del problema original con coeficiente negativo en el rengln cero de l cuadro ptimo de la fase I Fase 2: Resolver el problema con el mtodo simplex.
162
MAESTRIA PYGE

Mtodo Simplex de dos Fases.
MAESTRIA PYGE
Aplicamos Simplex de dos Fases :

Fase 1:
Min sa:
x5 10x1 + 10x2 +s3 =9 10x1 + 5x2 - e4 + a5 = 1 x1,x2, x3, x4, x5 0
Quedando la siguiente tabla:

Variables Bsicas w s3 a5 0 10 10 0 10 5 0 1 0 0 0 -1 1 0 1 0 9 1
163
x1
x2
s3
e4
a5
valor

donde:
s3 9 x1 0
MAESTRIA PYGE
xB=
xD=
x2
a5
e4
Luego se hace cero el costo reducido de la variable x5 de la tabla anterior, y queda la siguiente tabla inicial.
Variables
Bsicas w s3 a5 -10 10 10 -5 10 5 0 1 0 1 0 -1 0 0 1 -1 9 1
x1
x2
s3
e4
a5
valor
164
II. Modelos de Programacin Matemtica Programacin Lineal Mtodo Simplex de dos Fases. MAESTRIA PYGE
La variable entrante a la base es x1 ( pues r1 < 0).

Variables Bsicas
x1
x2
s3
e4
a5
valor
w
s3 a5
-10
10 10
-5
10 5
0
1 0
1
0 -1
0
0 1
-1
9 1
Calculamos Min { 9/10, 1/10}= 1/10, por lo tanto sale a5.

165

Obtenindose la siguiente tabla final:
Variables x1 x2 s3 e4 a5 valor
MAESTRIA PYGE
Bsicas
w s3 x1 s3
0 0 1
0 5 1/2 8
0 1 0
1 1 -1/10
0 -1 1/10
0 8 1/10 x2
xB=
xD=
e4
x1
1/10
a5
Donde, la anterior, corresponde a la solucin ptima del problema en la Fase 1, con valor ptimo 0. De aqu entonces tomamos x1 y x3 como variables bsicas.
166

Fase 2:
Variables Bsicas x1 x2 s3 e4 valor
MAESTRIA PYGE
z
-2
-1
s3 x1
0 1 1/2
1 0 -1/10
1 1/10
En la tabla hacemos 0 los costos reducidos de variables bsicas

Variables Bsicas z s3 x1 0 0 1 0 5 1/2 0 1 0 -1/5 1 -1/10 1/5 8 1/10 x1 x2 s3 e4 valor
Luego la variable entrante a la base es e4 (pues r4<0). Y calculando Min { 8/1, (-1/10)/(1/10) } = 8, se tiene que sale s3.
167

Quedando:
Variables
MAESTRIA PYGE
x1
x2
s3
e4
valor
Bsicas z e4 0 0 1 5 1/5 1 0 1 9/5 8
x1
1/10
9/10
donde la solucin ptima del problema resulta ser:

e4 xB = x1 = 9/10 8 xD = s3 x2 = 0 0
168

Consideremos otro ejemplo para el caso 2
min z= 2 x1 + 3 x2
MAESTRIA PYGE
s.a.
1/2 x1
1 x1
+
+
1/4 x2
3 x2
4
20
x1 x1
+ ,
x2 x2
10 0
Aumentando las variables de holgura, exceso y artificiales

min z=
2 x1 1/2 x1 1 x1 x1
+ + + +
3 x2 1/4 x2 3 x2 x2 + s1 e2 + a2 + a3 = = = 4 20 10
169
II. Modelos de Programacin Matemtica Programacin Lineal Primera Fase

min w= a2 1/2 1 x1 x1 x1 + + + 1/4 3 x2 x2 x2 + s1 e2 + a2 + a3 + a3 = = = 4 20 10
MAESTRIA PYGE
variable w s1 a2 a3
w 1
x1 0 1/2 1 1
x2 0 1/4 3 1
s1 0 1 0 0
e2 0 0 -1 0
a2 -1 0 1 0
a3 -1 0 0 1
valor 0 4 20 10
170

sumamos las columnas 2 y 3 para eliminar las variables a2 y a3
VB w x1
1 0 2 1/2
x2
4 0
s1
0 1
e2
-1 0
a2
0 0
a3
0 0
valor
30 4
prueba
MAESTRIA PYGE
w s1
16
a2
a3
0
0
1
1
3
1
0
0
-1
0
1
0
0
1
20
10
7
10
171

Haciendo 1 al pivote
VB w x1 1 0 0 0 2 0.5 1/3 1 x2 4 0 1 1 s1 0 1 0 0 e2 -1 0 -1/3 0 a2 0 0 1/3 a3 0 0 0 1 valor 30 4 20/3 10
MAESTRIA PYGE
w
s1 a2 a3
Realizando operaciones
VB w s1 x2 a3 w x1 1 0 0 0 2/3 5/12 1/3 2/3 x2 s1 e2 0 0 1 0 0 1 0 0 1/3 1/12 -1/3 1/3 a2 -4/3 -1/12 1/3 -1/3 a3 valor 0 0 0 1 10/3 7/3 20/3 10/3 28/5 20 1/5 prueba
172
VB
w x1 1 0 0 2/3 5/12 1/3
x2 0 0 1
s1 0 1 0
e2 1/3 1/12 -1/3
a2 -4/3 -1/12 1/3
a3 0 0 0
valor 10/3 7/3 20/3
MAESTRIA PYGE
w
s1 x2
x1
1/2
-1/2
3/2
VB w
w x1 1 0
x2 0
s1 0
e2 0
a2 -1
a3 -1
valor 0
s1
x2 x1
0
0 0
0
0 1
0
1 0
1
0 0
-1/8
-1/2 1/2
1/8
1/2 -1/2
-5/8
-1/2 3/2
1/4
5 5
173

Fase 2 Volvemos a introducir la funcin objetivo original
VB
z
z x1
1 0 0 0 -2 0 0 1
x2
-3 0 1 0
s1
0 1 0 0
e2
0 -1/8 -1/2 1/2
valor
0 1/4 5 5
MAESTRIA PYGE
s1
x2 x1
Como tanto x1 como x2 estn en la base ptima de la fase 1 debemos eliminarlas del rengln 0
VB z z x1 1 0 x2 0 s1 0 e2 -1/2 valor 25
s1
x2 x1
0
0 0
0
0 1
0
1 0
1
0 0
-1/8
-1/2 1/2
1/4
5 5
Debido a que no hay como mejorar la funcin objetivo original Esta es OPTIMA
174

Supongamos que en el ejemplo anterior se cambia la segunda restriccin (a fin de analizar el caso 1)
min z= 2 x1 + 3 x2
MAESTRIA PYGE
s.a.
1/2 x1
1 x1 x1
+
+ +
1/4 x2
3 x2 x2
4
36 10
x1
x2
Aumentando las variables de holgura, exceso y artificiales

min z= s.a. 2 x1 1/2 x1 1 x1 x1 + + + + 3 x2 1/4 x2 3 x2 x2 + s1 - e2 + a2 + a3 = 4
= 36 = 10
175
II. Modelos de Programacin Matemtica Programacin Lineal Primera Fase

min w= a2
1/2 x1 + 1 x1 + x1 + 1/4 x2 3 x2 x2 + s1 e2 + a2 + a3
+ a3
= = = 4 36 10
MAESTRIA PYGE
variable w s1 a2 a3
w x1 1 0 0 0 0 1/2 1 1
x2 0 1/4 3 1
s1 0 1 0 0
e2 0 0 -1 0
a2 -1 0 1 0
a3 -1 0 0 1
valor 0 4 36 10
176

sumamos las columnas 2 y 3 para eliminar las variables a2 y a3
MAESTRIA PYGE
VB
w x1
x2
s1
e2
a2
a3
valor
prueba
w
s1
1
0
2
1/2
4
1/4
0
1
-1
0
0
0
0
0
46
4 16
a2
a3
0
0
1
1
3
1
0
0
-1
0
1
0
0
1
36
10
12
10
177

VB w x1 1 0 0 0 -2 1/2 -2 1 x2 0 1/4 0 1 s1 0 1 0 0 e2 -1 0 -1 0 a2 0 0 1 0 a3 valor -4 6 -1/4 3/2 -3 6 1 10
MAESTRIA PYGE
w
s1 a2 x2
Como ninguna variable en el rengln 0 tiene coeficiente positivo se trata de un cuadro ptimo de la fase 1. Debido a que el valor de w=6>0 el PL no tiene solucin factible
178
Algunos casos especiales MAESTRIA PYGE

1) Problema Infactible. Esta situacin se detecta cuando el valor ptimo del problema de la Fase 1 da mayor que cero. 2) Mltiples soluciones ptimas. Esta situacin se detecta cuando existen costos reducidos iguales a cero en una o ms de las variables bsicas ptimas. 3) Problema no acotado. Esta situacin se detecta cuando al realizar el clculo de la variable que deja la base, todos los elementos ykj de la columna j en la tabla, son negativos para j el ndice de una variable no bsica con costo reducido negativo.
179

II.5. Dualidad en Programacin Lineal. Consideremos un ejemplo de produccin de 2 productos finales que hacen uso de tres recursos escasos (mquinas), cuyas disponibilidades en horas corresponden a los lados derechos de las restricciones. P) Max 40x1 + 60x2 sa: 2x1+2x2 70 x1 + x2 40 x1 + 3x2 90 x1 , x2 0 La solucin ptima y el valor ptimo del problema P) esta dada por: x1 * = 5 x2* = 25 z = v(p) = 2100
180
MAESTRIA PYGE
MAESTRIA PYGE
En lo que sigue, combinaremos las distintas restricciones del problema, ponderando por los valores 1, 2 y 3 cada una, respectivamente, de modo de obtener la mejor cota superior del valor ptimo del problema P). Vale decir: 1(2x1+2x2) + 2(x1+x2) + 3(x1+3x2) 70 1 + 40 2 + 90 3 Para garantizar que el lado derecho de esta ltima desigualdad sea una cota superior de la funcin objetivo se debe cumplir que : 2 1 + 2 + 3 40 21 + 2 + 3 3 60
181
La mejor eleccin de esta cota se obtendra al resolver:
MAESTRIA PYGE
70 1 + 40 2 + 90 3 2 1 + 2 + 3 40 21 + 2 + 3 3 60 1, 2, 3 0 Este problema se conoce como el problema Dual D) asociado al problema Primal P). D) Min sa: Tambin resulta que al formular el problema dual de D) se obtiene el problema primal (o uno equivalente). Cualquiera de los dos entrega la misma informacin y el valor ptimo alcanzado es el mismo.
182

Ms generalmente, si el problema primal es: P) n
Max
c jx j
j1 n j1
MAESTRIA PYGE
sa :
aijx j bi
xj 0
i 1,2,..., n
j 1,2,..., m
su dual resulta el problema: D) Min
bi i
i 1 m
sa :
aiji c j
i 1
j 1,2,..., n
i 0
i 1,2,..., m
183

Lo que se puede expresar en forma matricial como: P) Max cTx sa: Ax b x0
MAESTRIA PYGE
bT AT c 0 Si el problema primal corresponde a: P) Max -cTx sa: Ax b x0 Su dual resulta ser: D) Min -bT sa: AT c 0 Es decir, el dual del dual es el problema primal D) Min sa:
184
MAESTRIA PYGE
Teorema de dualidad dbil: Si x IRn, es una solucin factible del problema primal P) y IRm, una solucin factible del problema dual D), entonces:
c x c jx j bi i bT
T j 1 i 1
En particular, si ambas soluciones son los ptimos de sus respectivos problemas, sus valores ptimos cumplen que : v(P) v(D) Teorema de dualidad fuerte: Si x* = (x1*, x2*, ..., xn*)T, es una solucin ptima problema primal P), entonces el problema dual D) tiene solucin ptima * = (1*, 2*, ..., m*)T que satisface:
v(P) c x * c j x j * bi i * b T v(D)
T j1 i 1
185
MAESTRIA PYGE
Adems: i)Si P) es no-acotado entonces D) es infactible. ii)Si D) es no-acotado entonces P) es infactible. Ejemplo: P) Min sa: 3x1 + 4x2 + 5x3 x1+ 2x2 + 3x3 5 2x1 + 2x2 + x3 6 x1 , x2 , x3 0 5 1 + 6 2 1 + 22 3 21 + 22 4 31 + 2 5 1, 2 0
D)
Max sa:
186

Resolvemos D) por Simplex, en su forma estndar:
1
MAESTRIA PYGE
1
2
2 2 1 -6
3 4
1 0 0 0 0 1 0 0
5
0 0 1 0 3 4 5 0
2 3 -5
3 3 xB 4 4 5 5 1 0 xD 2 0
Luego la variable entrante a la base es 2 (pues r2<0). Y calculando Min { 3/2, 4/2, 5/1 } = 3/2, se tiene que sale 3
187
1 2 3 4 5
MAESTRIA PYGE
1 0 0
-1 -1/2
0 1 0
0 0 1
3/2 1 7/2
1 5/2
-2 0 3 0 0 9 Luego la variable entrante a la base es 1 (pues r2<0). Y calculando Min { (3/2)/(1/2), 1/1, (7/2)/(5/2)} = 1, se tiene que sale 4
2 3 / 2 xB 4 1 5 7 / 2 1 0 xD 3 0
188
MAESTRIA PYGE
1 2 3 4 5
0 1 0 0 1 0 0 0 1 -1 2 1 -1/2 1 -5/2 2 0 0 1 0 1 1 1 11
1 1 x B 2 1 5 1 3 0 xD 4 0
Sol. ptima de D):
1* = 1; 2* = 1;
Sol. ptima de P): x1* = 1; x2* = 2; x3* = 0;
v(D) = 11
v(P) = 11
189
Mtodo Simplex Dual:
MAESTRIA PYGE
La idea de este mtodo consiste en resolver de alguna manera el problema dual asociado a P) en la tabla y variables del problema primal P), segn veremos en su aplicacin a un problema primal (ejercicio anterior). Min 3x1 + 4x2 + 5x3 sa: x1+ 2x2 + 3x3 5 2x1 + 2x2 + x3 6 x1 , x2 , x3 0
190
Mtodo Simplex Dual:
MAESTRIA PYGE
Min sa:
3x1 + 4x2 + 5x3 + 0x4 + 0x5 x1 + 2x2 + 3x3 - x4 5 2x1 + 2x2 + x3 - x5 6 x1 , x2 , x3 , x 4 , x5 0
x(-1) x(-1)
x1
-1 -2 3
x2
-2 -2 4
x3
-3 -1 5
x4
1 0 0
x5
0 1 0 -5 -6 0
191
Mtodo Simplex Dual:
MAESTRIA PYGE
En la tabla anterior se toman dos variables de exceso x4 y x5 , y se multiplica por un nmero negativo con la finalidad de encontrar la matriz identidad IRn, adems es necesaria la condicin de que los costos reducidos de la tabla sean mayores que cero ( lo que en este caso se cumple). En la tabla anterior se escoge, usando el lado derecho, alguna variable con valor negativo.
Escogemos x5 , variable que dejar la base. Enseguida , se obtiene la variable entrante calculando: Min { (-3/-2) , (-4/-2),(-5/-1)} = 3/2. De donde resulta que x1 entra a la base.
192
Mtodo Simplex Dual:
MAESTRIA PYGE
x1
0 1 0
x2
-1 1 1
x3
-5/2
x4
1 0 0
x5
-1/2 -1/2 3/2 -2 3 -9
1/2 7/2
La tabla posee an un lado derecho negativo (costos reducidos negativos del problema dual), por lo cual no es factible en P).
193

x4 (=-2) deja la base, luego calculamos : Min {(-1/-1),((-7/2)/(-5/2)),((-3/2)/(-1/2))} = 1, por lo que x2 entra a la base.
MAESTRIA PYGE
x1
0 1 0
x2
1 0 0
x3 x4 x5
5/2 -1 -2 1 1 1 -1 1 2 1 -11
La tabla posee lados derechos no-negativos (costos reducidos positivos del problema dual) y tambin los costos reducidos de las variables no bsicas x3, x4 y x5 son no-negativos , por lo que tenemos una solucin factible en P) que es la solucin ptima del problema.
x 1 1 x x 2 2 x 3 0 v(P) 11
194
II. Modelos de Programacin Matemtica Programacin Lineal II.6. Anlisis de Sensibilidad o Post-Optimal MAESTRIA PYGE
1) Qu ocurre con las actuales variables bsicas si se cambia algn coeficiente del lado derecho (b)? Si calculamos: xB B b y se cumple: xB 0 Las mismas variables bsicas lo son tambin de la nueva solucin ptima, calculada con el nuevo b . Si lo anterior no se cumple, se puede aplicar el Mtodo Simplex Dual. 2) Qu ocurre con la actual solucin ptima si se agrega una nueva variable al problema ?
1
Para decidir si la actual solucin bsica es ptima para el nuevo problema, calculamos el costo reducido de la nueva variable mediante la formula:
T 1 rk ck cB B Ak
195

donde k es el ndice de la nueva variable y Ak su respectiva columna en la matriz de coeficientes. Si se cumple que rk0 se conserva la actual solucin ptima. En caso contrario, se sigue con el Simplex. 3) Que ocurre con la actual solucin ptima del problema P) si se cambian los coeficientes que definen la funcin objetivo ?
Supongamos que el vector de coeficientes en la funcin objetivo n cambia a un vector c IR La actual solucin ptima tambin lo es para P con:
MAESTRIA PYGE
P)
Min c x sa : Ax b x0
196
MAESTRIA PYGE
Siempre que los nuevos costos reducidos sean mayores o iguales a cero (notar que tambin cambia el valor de la funcin objetivo en la actual solucin ptima). Es decir se debe cumplir que:
T 1 rD cD cB B D0
o equivalentemente j
rj c j c B 1 Aj 0
T B
En caso contrario, se aplica el Simplex a partir de la tabla final de P) con los nuevos costos reducidos y nuevo valor de la actual solucin bsica.
197
MAESTRIA PYGE
Veamos los cambios que tienen lugar cuando slo vara un coeficiente del vector c de la funcin obj.
a) Cambio de un coeficiente asociado a una variable nobsica xJ: Se conserva la misma solucin ptima del problema P) ssi. para esa variable xJ:
rj
T 1 c j cBB A j
198
Consideremos : MAESTRIA PYGE

c j c j j
Por lo tanto se conserva la misma solucin ssi:
j rj
c j c j rj
199
MAESTRIA PYGE
b) Cambio en un coeficiente de la funcin objetivo asociado a una variable bsica: En este caso para tener la misma solucin ptima, se debe cumplir que el costo reducido de todas las variables.a cero.
rj
T 1 c j cBB A j
ci ci i
0 cB cB i 1 cB ie i 0
200
MAESTRIA PYGE
Si el incremento es cualquiera en el siguiente intervalo, se conserva la misma solucin ptima:
rj rj Max / yij 0 i Min / yij 0 yij yij

donde rj es el costo reducido de la respectiva variable no bsica en la actual solucin ptima y los coeficientes yij denotan las entradas en la tabla final del Simplex asociadas a la variable bsica xi (cuyo costo cambia) y la respectiva variable no bsica xj
201
MAESTRIA PYGE
Ejemplo:
La siguiente tabla, es la tabla final de un problema de programacin lineal.

1,00 0,00 2,33 6,67 1,67 0,03 3,33 0,00 1,00 0,00 0,27 -0,01 2,93 -0,07 0,03 0,27 1333,33 66,67 18666,67
0,00 -0,03
Con esta tabla realizaremos un anlisis de sensibilidad:

202
MAESTRIA PYGE
a) Variar los recursos ( lado derecho):
Las xB del problema primal no cambian como base ptima, si los valores asociados a estas variables.
xB B1b y se cumple xB 0
Para calcular estos intervalos de recursos, se necesita la matriz inversa asociada a las variables bsicas del tabla final.
203
MAESTRIA PYGE
4 10 B 1 40
1/ 15 4 / 15 B 1 / 150 2 / 75
1
Intervalo recurso 1:
1 / 15 6000 b1 4 / 15 1 / 150 2 / 75 x 4000 0
20000 4 b1 0 15 15 10000 b1 0 150 150
b1 5000
b1 10000
204
MAESTRIA PYGE
5000 b1 10000 1000 b1 16000
Intervalo recurso 2:
1 / 15 6000 4 / 15 1 / 150 2 / 75 x 4000 b 0 2
2500 b2 20000 1500 b2 24000
205
MAESTRIA PYGE
Variable x1:
Max {0} C1 Min {((20/3)/(7/3)),((10/3)/(5/3))}
0 D1 2
Variable x4:
10 C1* 12
Mx {((20/3)/(-1/30))} D4 Min {((10/3)/(1/30))}

-200 D4 100 -60 C4* 240
206
MAESTRIA PYGE
Variable x2:
C2* = C2 + 2 2 - r2 Variable x3:
C2 = -20 C2* - 20 - ( 20/3) C2* - 80/3
C3* = C3 + 3 3 - r3
C3 = -18 C3* - 18 - ( 10/3) C3* - 64/3

207
BIBLIOGRFIA EN PROGRAMACIN LINEAL
1. Linear Programming and Network Flow, M.Bazaraa, J.Jarvis and H.Sherali. John Wiley & Sons, Inc., New York, Second Edition 1990. 2. Introduction to Linear Optimization, D.Bertsekas and J.Tsitsiklis. Athena Scientific USA, 1997. 3. Linear Programming, V.Chvtal. W.H. Freeman and Company, New York, 1983. 4. Linear Programming and Extensions, G. Dantzig. Princeton University Press, New Jersey, tenth printing, 1993. 5. Introduccin a la Programacin Lineal y No Lineal, D.Luenberger. Adisson Wesley Iberoamericana, 1989. 6. Linear and Combinatorial Programming, K. Murty. John Wiley & Sons, Inc., New York, Second Edition 1976. 7. Model Building in Mathematical Programming, H.P. Williams. John Wiley & Sons, Inc., New York, 4rd Edition 1999.
208
MAESTRIA PYGE
DIRECCIONES ELECTRNICAS EN PROGRAMACIN LINEAL
MAESTRIA PYGE
Preguntas de consulta frecuente en Programacin Lineal:

http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html
Servidor NEOS, gua de software de Programacin Lineal:

http://www-fp.mcs.anl.gov/otc/Guide/SoftwareGuide/Categories/linearprog.html
Servidor NEOS, ejemplo problema de la dieta:

http://www-fp.mcs.anl.gov/otc/Guide/CaseStudies/diet/index.html
Gua de software de Programacin Lineal en revista OR&MS Today (INFORMS Magazine):

http://lionhrtpub.com/software-surveys.shtml
209
MAESTRIA PYGE
II. Modelos de Programacin Matemtica Programacin Entera

Temario: MAESTRIA PYGE
III.1. Introduccin y ejemplos de modelamiento. III.2. Resolucin de problemas de P. E. III.3. Mtodo de Branch and Bound.
211

Ejemplo de Restricciones O
MAESTRIA PYGE
Seat considera la fabricacin de 3 tipos de automviles: compacto, mediano y largo. En la tabla se presentan los recursos requeridos y las ganancias proporcionadas por cada tipo de automvil. En la actualidad se cuenta con 6000 ton de acero y 60000 horas de trabajo. Para que la produccin de un tipo de automvil sea econmicamente factible hay que fabricar al menos 1000 unidades de este tipo. Formular un modelo matemtico para optimizar las ganancias.
COMPACTO MEDIANO Ton. de acero hors de trabajo 1.5 30 3 25
LARGO 5 40
ganancia (dolares)
2000
3000
4000
212

Consideremos como variables de decisin x1 = nmero de automviles compactos x2 = nmero de automviles medianos x2 = nmero de automviles grandes Por lo tanto la funcin objetivo (ganancia de la fbrica): Max z=2000 x1+ 3000x2 + 4000x3 R1 R2 R3 R4 R4 x1 0 x2 0 x3 0 1.5 x1 30 x1 x11000 x21000 x31000 + 3 x2 + 5 x3 600 +25 x2 + 40 x3 60000
MAESTRIA PYGE
213

Restricciones O MAESTRIA PYGE
Se dan dos restricciones de la forma: f(x1, x2, xn) 0 g(x1, x2, xn) 0 Se desea asegurar que se cumpla por lo menos una de las dos restricciones. Deber agregarse las siguientes dos restricciones: f(x1, x2, xn) My g(x1, x2, xn)M(1-y) Donde: y es una variable 0-1 y M es un nmero muy grande que asegure que se satisfagan: f(x1, x2, xn)M g(x1, x2, xn)M Para todos los valores de x1, x2, xn que satisfagan las otras restricciones.
214

Max z=2000 x1+ 3000x2 + 4000x3
MAESTRIA PYGE
x1 M1 y1 1000- x1 M1(1-y1) R2 x2 M2 y2 1000- x2 M2(1-y2) R3 x3 M3 y3 1000- x3 M3(1-y3) R4 1.5 x1 + 3 x2 + 5 x3 6000 R4 30 x1 +25 x2 + 40 x3 60000 x1, x2, x3 0 y1, y2, y3 = 0 1 R1
215
Ejemplo de Restricciones SI ENTONCES

STour recibe pagos de los turistas con tarjetas de crdito de 4 regiones diferentes galpagos, costa, sierra y oriente. El valor promedio de pagos por los clientes de cada regin es galpagos 70000, costa 50000, sierra 60000 y oriente 40000. STour debe decidir hacia donde deben enviar los clientes sus pagos, ya que recibe el 20% de inters anual y desea recibir los pagos lo ms pronto posible. STour considera montar las oficinas para procesar los pagos en cuatro ciudades Puerto Ayora, Guayaquil, Cuenca y Puyo. El nmero promedio de das (a partir del envo del pago) hasta la liquidacin de un cheque y hasta que STour pueda depositar el dinero depende de la ciudad a la cual se manda el pago como se muestra en la tabla siguiente. El costo anual por manejar una oficina es de 50000. Si se abre la oficina en Puerto Ayora solo puede recibir el dinero de galpagos y de ninguna otra regin (si galpagos enva su dinero a la Puerto Ayora entonces ninguna otra regin puede enviar el dinero a Puerto Ayora) Formular un PL para minimizar la suma de los costos por intereses perdidos y por el manejo de la oficina. Supngase que cada regin debe enviar su dinero a una sola oficina. DESDE HACIA P.Ayora Guayaquil Cuenca Puyo
Galpagos Costa Sierra Oriente 2 6 8 8 6 2 5 5 8 5 2 5 8 5 5 2
216
MAESTRIA PYGE

Restricciones SI ENTONCES MAESTRIA PYGE
Se desea asegurar que se cumpla g(x1,x2,xn)0 si se satisface f(x1,x2,xn)>0, mientras que si no se satisface f(x1,x2,xn)>0 entonces g(x1,x2,xn)0 no debe satisfacerse. Deber agregarse las siguientes dos restricciones: -g(x1, x2, xn)My f(x1, x2, xn) M(1-y) Donde: y es una variable 0-1 y M es un nmero muy grande que asegure que se satisfagan: f(x1, x2, xn)M g(x1, x2, xn)M Para todos los valores de x1, x2, xn que satisfagan las otras restricciones.
217
II. Modelos de Programacin Matemtica Programacin Entera Funciones lineales por partes
Supongamos que una funcin lineal por partes tiene los puntos de ruptura b1,b2,bn. Para algn k (k=1,2,3n-1), bk x bk+1. Entonces, para algn nmero zk (0 zk 1) se puede escribir x como: x= zk bk+(1-zk)bk+1 Ya que f(x) es lineal para bk x bk+1 , podemos escribir como: f(x)=zk f(bk)+(1-zk) f(bk+1 ) Paso 1: donde se presenta f(x) remplazar por z1f(b)+z2f(b2)+z3f(b3)..znf(bn) Paso 2: aadir las siguientes restricciones: z1y1, z2y1+y2 , z3y1+y2. zn-1 yn-2+yn-1, zn 1 y1+y2+y3.+yn-1=1 z1+z2+z3.+zn-1=1 X=z1b1+z2b2+z3b3+.znbn
MAESTRIA PYGE
218

Ejemplo de Funciones lineales por partes
MAESTRIA PYGE
Supngase que se produce gasolina a partir de petoleo. Al comprar el petrleo de nuestro proveedor se recibe un descuento por cantidad. Los 500 primeros galones de petrleo cuestan 0.25 dlares el galn; los siguientes 500 galones a 0.20 dlares; y los siguientes 500 galones a 0.15 dlares Se pueden comprar como mximo 1500 galones
219
MAESTRIA PYGE
220

a) Problema de la mochila.
Una empresa est pensando invertir en cuatro proyectos diferentes, cada proyecto se finaliza a lo ms en 3 aos. Los flujos de caja requeridos en cada ao junto con el Valor Presente Neto de cada proyecto, concluIdos los aos de ejecucin, y las disponibilidades de recursos financieros se resumen en la siguiente tabla:
Proy 1 Proy 2 Proy 3 Proy 4
Ao 1 Ao 2 Ao 3 V.P.N. 10 8 18 35 8 15 0 18 6 4 16 24 12 0 0 16
MAESTRIA PYGE
Disp. Recursos
30 15 12
Interesa determinar en cules proyectos invertir de modo de conseguir el mayor V.P.N. de la inversin.
221

MAESTRIA PYGE
1, si se invierte en el proyecto i xi 0, sin o

Funcin objetivo:
con i 1,2,3,4
Max 35x1 + 18x2 + 24x3 + 16x4
222

Restricciones (tres alternativas): 1) Reinvirtiendo el dinero no utilizado en un perodo: Ao1: 10x1 + 8x2 + 6x3 + 12x4 + s1
MAESTRIA PYGE
= 30 + s2 = 15 + s1 12 + s2
Ao2: 8x1 + 15x2 + 4x3 Ao3: 18x1 xi {0,1} + 16x3 i = 1,2,3,4
2) Sin invertir el dinero no utilizado en un perodo, pero utilizando el retorno de los proyectos concludos: Ao1: 10x1 + 8x2 + 6x3 + 12x4 30 Ao2: 8x1 + 15x2 + 4x3 Ao3: 18x1 xi {0,1} + 16x3 i = 1,2,3,4 15 + 16x4 12 + 18x2
223

3) Reinvirtiendo el dinero no utilizado en un perodo y, tambin el retorno de proyectos concluidos:
MAESTRIA PYGE
Ao1: 10x1+ 8x2+ 6x3+ 12x4+ s1 Ao2: 8x1+ 15x2+ 4x3 Ao3: 18x1 + 16x3
= 30 12 + s2 + 18x2
+ s2 = 15 + s1 + 16x4
xi {0,1}
i = 1,2,3,4
224

Notar que el conjunto de las soluciones factibles es finito. Esto ocurrir generalmente con los problemas de Programacin Entera (puros). En el ejemplo, el nmero de soluciones factibles no supera el nmero de las soluciones binarias del problema (variables restringidas slo a valores 0 o 1) que son 24 = 16, dado el nmero de variables utilizadas, de hecho las soluciones factibles son menos de 16 pues en particular xi=1 para i=1,2,3,4 no satisface las disponibilidades de capital en cualquiera de las tres alternativas.
MAESTRIA PYGE
225

Tomemos el ejemplo de la mochila dado con anterioridad
Supongamos que adicionalmente la inversin efectuada requiera nuevas restricciones.
MAESTRIA PYGE
- Se debe invertir en al menos 1 de los 3 primeros proyectos:
x1 + x2 + x3 1
- El proyecto 2 no puede ser tomado a menos que el proyecto 3 si sea tomado: x2 x3 - Se puede tomar el proyecto 3 o 4 pero no ambos: x3 + x4 1 - No se puede invertir en ms de dos proyectos: x1 + x2 + x3 + x4 2
226

b) Cumplimiento de un subconjunto de las restricciones de un problema. Consideremos un problema que posee las siguientes restricciones:
MAESTRIA PYGE
12x1 + 24x2 + 18x3 2400 15x1 + 32x2 + 12x3 1800 20x1 + 15x2 + 20x3 2000
Supongamos adems, que nos basta con obtener alguna solucion ptima que verifique el cumplimiento de al menos 2 de las 3 restricciones anteriores.
1, si la restriccin j se satisface yj 0, casocontrario
227
Cada inecuacin anterior la reemplazamos por:
MAESTRIA PYGE
12x1 + 24x2 + 18x3 2400 + M1 (1- y1)

15x1 + 32x2 + 12x3 1800 + M2 (1- y2) 20x1 + 15x2 + 20x3 2000 + M3 (1- y3) Adems, debemos agregar la restriccin que permita que a lo ms una de las restricciones no se cumpla: y1 + y2 + y3 2 Mi = constante lo suf. grande
228

c) Inclusin de costos fijos.
MAESTRIA PYGE
Supongamos que se desea tener lotes de compra de un producto dado, para satisfacer demandas que fluctan en el tiempo sobre un horizonte de planificacin dividido en T perodos. Asumimos conocidos: una estimacin de la demanda dt, con t = 1, 2, ..., T, los costos fijos asociados a la compra de una unidad pt, los costos asociados al mantenimiento de una unidad en inventario de cada perodo ht y los costos fijos asociados a la gestin de compra en el perodo t, st. Observacin: no se permite unidades de faltante.
229

Variables de decisin
MAESTRIA PYGE
x t: It :
nmero de unidades compradas en t. nivel de inventario al final del perodo t. con t: 1, 2, ..., T
1, si se hace una compra en el periodo t yt 0, sin o
230

Funcin objetivo
T
MAESTRIA PYGE
Min
Restricciones xt + It-1 - It = dt xt Mt yt
st
t 1
y t p t x t h t It
t = 1, 2, ..., T I0 = inventario inicial t = 1, 2, ..., T Mt = cte. grande
231

d) Problema de cobertura: Dado un nmero de regiones o zonas, en las cuales se ha subdividido una comuna, cuidad, pas, etc., digamos que un total de m, se desea instalar un cierto nmero de servidores (escuelas, centros de atencin primaria de salud, compaas de bomberos, etc.) de entre un conjunto de n potenciales servidores ubicados en alguna de las zonas dadas.
MAESTRIA PYGE
Se conoce la informacin relativa a que zonas pueden ser atendidas por cada uno de los n potenciales servidores, es decir, se conoce la matriz de incidencia A = (aij) donde :
1, si la zona i puede ser atendida por el servidor j aij 0, sin o con i 1,2,..., m y j 1,2,..., n
232

Se desea determinar cules son los servidores que deben ser instalados de modo de dar cobertura a cada zona, dados los costos de instalacin cj del servidor j.
MAESTRIA PYGE
1, si se instala el servidor j xj 0, sin o

Funcin objetivo:
Min
cj xj
j 1
Restricciones: Para cada zona i
j1
aij x j 1
Se agrega la siguiente restriccin, si adicionalmente, hay algn lmite en el nmero de servidores que se pueden instalar (digamos k) : m
xj k
j 1
233
e) Problema de transporte y localizacin:
MAESTRIA PYGE
Si se tiene un conjunto de m clientes que demandan di unidades de un producto determinado. Una compaa desea satisfacer esas demandas desde un cierto conjunto de plantas elegidas de n potenciales lugares donde se instalarn. Sean cj los costos asociados a la instalacin de la planta j , vj el costo unitario de produccin de la planta j y tij el costo de transporte de una unidad desde la planta j al cliente i . Se desea decidir cules plantas abrir y el tamao de cada una de modo de satisfacer las demandas estimadas.
234
MAESTRIA PYGE
1, si se abre la planta j yj 0, sin o

xij = el nmero de unidades elaboradas en la planta j para satisfacer el cliente i, con j = 1,...,n y i = 1,....,m.
235
MAESTRIA PYGE
Funcin objetivo:
m Min c j y j v j xij i 1 j 1 j 1 n n
tijxij
j 1 i 1
Costo de Instalacin
Costo de Produccin
Costo de Transporte
236
Restricciones: MAESTRIA PYGE
1) Demanda cliente i:
x ij di
i 1
2) Relacionar variables de produccin con las asociadas a la apertura de plantas (variables binarias):
xij Mj y j
j 1
donde Mj es una constante grande (por ejemplo, capacidad mxima de produccin de la planta j), con xij 0 e yj {0,1}.
237
III.2. Resolucin de problemas de P. E. MAESTRIA PYGE

Supongamos que tenemos el siguiente problema de programacin lineal: PL) Max s.a. cTx Ax=b x0 Pero todas o una parte de las variables deben restringir su valor a nmeros enteros, dando origen a un problema de Programacin Entera (puro) o de Programacin Entera- Mixta, respectivamente.
238
Por ejemplo:
MAESTRIA PYGE
PLE)
Max s.a.
cTx Ax=b x 0, xj entero
El problema PL) corresponde a la relajacin continua del problema PLE), que resulta de eliminar las condiciones de integralidad de las variables de decisin en PLE). El valor ptimo de PL) provee slo una cota superior del valor ptimo de PLE). Notar sin embargo, que si la solucin ptima de PL) cumple con la integralidad de los valores requiridos, entonces esta solucin es tambin solucin ptima de PLE).
239
MAESTRIA PYGE
240
MAESTRIA PYGE
241
MAESTRIA PYGE
242

Ejemplo MAESTRIA PYGE
PLE) Max s.a.
x2 - 2x1 + 2x2 1 2x1 + x2 7 x1 0, x2 0
enteros
243
MAESTRIA PYGE
2x1 + x2 7
7
x2
- 2x1 + 2x2 1
. . . .
. . . . .
3.5
x1
244

Notar que en el ejemplo la solucin ptima puede ser hallada por simple enumeracin de todas las soluciones factibles. Aqu las soluciones ptimas son:
MAESTRIA PYGE
x1 * = 1
x1 * = 2
x2 * = 1
x2 * = 1
Esta alternativa de enumeracin queda naturalmente restringida a problemas muy pequeos. Alternativamente, podemos resolver la relajacin continua asociada al problema PLE). Si la solucin ptima de la relajacin continua da una solucin entera, esa es la solucin ptima no solo del problema lineal sino que tambin lo es del problema lineal entero. En el ejemplo, la solucin de la relajacin continua es: x1 = 3/2 x2 = 2
245

A partir de esta ltima solucin podemos redondear o truncar los valores que no salieron enteros, obteniendo respectivamente en el ejemplo: x1 = 2 x1 = 1 x2 = 2 x2 = 2 las cuales no son soluciones factibles de PLE), de modo que desde el punto de vista de una resolucin numrica no es suficiente con resolver la relajacin continua. Todava podran resultar soluciones factibles de PLE), pero no neceasariamente ptimas. Por ejemplo: PLE) Max s.a. f(x1, x2) = x1 + 5x2 x1 + 10x2 10 x1 1 x1 0, x2 0 enteros
246
MAESTRIA PYGE

Solucin ptima de PL)
x1 = 1 f(1,9/10)=5,5
MAESTRIA PYGE
x2 = 9/10
Redondeando o truncando los valores
x1 = 1
x2 = 1 x1 = 0;
infactible
x1 = 1
x2 = 0
f(1,0)=1
Pero la solucin ptima de PLE) es: x2 = 1; v(PLE) = 5
247

III.3. Mtodo de Branch and Bound. Consideremos el siguiente problema de programacin entera:
MAESTRIA PYGE
PLE)
Max s.a.
21x1 + 11x2 7x2 + 4x2 13 x1 0 x2 0 x1, x2 enteros
Consideremos inicialmente la resolucin de la relajacin continua de PLE), que consiste en eliminar las condiciones de integralidad.
248

III.3. Mtodo de Branch and Bound. MAESTRIA PYGE
x2
x2 = 3
3/2 2 x2 = 2
21x1+11x2=39
1 x2 = 1 13/7 sol. relajada
x1 = 1
x1
x1 = 2
21x1+11x2
7x1+4x2=13
249

Descripcin del mtodo Branch and Bound (maximizacin)
MAESTRIA PYGE
Paso 0 Hacer P0), la relajacin continua de PLE)
Fijar la cota inferior del v(PLE) en -.

Paso1 Seleccionar un problema no resuelto, Pi) Resolver Pi) como problema de programacin lineal. Agotar este problema, usando: (i) que se encontr una solucin entera (ii) que el problema resulta infactible (iii) que el problema no provee un valor mejor que la actual cota del valor ptimo v(PLE).
250

Si el problema Pi) resulta agotado y da solucin entera, mejorar el valor de la cota inferior de v(PLE). Si todos los problemas estn agotados, parar.
MAESTRIA PYGE
Solucin ptima de PLE), la solucin entera asociada a la actual cota inferior de v(PLE), si existe (si no existe entonces PLE) es infactible) Si el problema no est agotado pasar al paso 2. Paso 2 Seleccionar una variable xj= j, cuyo valor en la solucin ptima de Pi) no de entero. Eliminar la regin correspondiente a j < j < j + 1 Crear dos nuevos problemas de programacin lineal que incorporen a Pi) dos restricciones mutuamente excluyentes: xj j, xj j +1 una en cada problema y volver al paso 1.
251
MAESTRIA PYGE
P0
x1 = 1 x2 = 3/2 z = 37.5
x21 x1 = 1 x2 = 1 z = 32 x11
x1 = 13/7 x2 = 0 z = 39 x12
P1
x22
P2
infactible x1 = 5/7 x2 = 2 z = 37 x11
P11 P121
P12
x1 = 0 x2 = 13/4 z = 35.75 x23 x1 = 0 x2 = 3 P1211 z = 33
P122
x24 infactible
P1212
infactible
P0) Relajacin continua -< z 39 P1) Max 21x1 + 11x2 s.a. 7x1 + 4x2 13 x1 1 x1 0 x2 0 P2) Max 21 x1 + 11x2 s.a. 7x1 + 4x2 13 x1 1 x2 1 x1 0 x2 0 De donde 32 z 39 Solucin ptima x1* = 0; x2* = 3; z = 33 252

BIBLIOGRFIA EN PROGRAMACIN ENTERA
MAESTRIA PYGE
1) Integer Programming, L.A.Wolsey. John Wiley & Sons, Inc., New York, 1998. 2) Combinatorial Optimization C.H.Papadimitriou and K.Steiglitz. Prentice Hall Inc., USA, 1982. 3) Linear and Combinatorial Programming, K. Murty. John Wiley & Sons, Inc., New York, Second Edition 1976. 4) Integer and Combinatorial Optimization, George L. Nemhauser and Laurence A. Wolsey. John Wiley & Sons, Inc., New York, 1999. 5) Model Building in Mathematical Programming, H.P. Williams. John Wiley & Sons, Inc., New York, 4rd Edition 1999.
253

DIRECCIONES ELECTRNICAS EN PROGRAMACIN ENTERA
MAESTRIA PYGE
Preguntas de consulta frecuente en Programacin Lineal:

http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html
Servidor NEOS, gua de software de Programacin Entera:

http://www-fp.mcs.anl.gov/otc/Guide/SoftwareGuide/Categories/intprog.html
Servidor NEOS, ejemplo problema corte de rollos:

http://www-fp.mcs.anl.gov/otc/Guide/CaseStudies/cutting/index.html
Gua de software de Programacin Lineal en revista OR&MS Today (INFORMS Magazine):

254
MAESTRIA PYGE
PROGRAMACION SEPARABLE
La forma de los problemas de PNL separable es:

MAESTRIA PYGE
max o min Z f j ( x j )
i 1
s.a.
g
j 1
ij
( x j ) bi
Ejemplo
max Z 30 x1 2 x 35 x 2 2 x
2 1
MAESTRIA PYGE
2 2
s.a. x 2 x 250
2 1 2 2
x1 x 2 20 x1 , x1 0
max Z f 1 ( x1 ) f 2 ( x 2 ) donde
MAESTRIA PYGE
f1 ( x1 ) 30 x1 2 x12
f 2 ( x 2 ) 35x 2 2 x
2 2
s.a. g11 ( x1 ) g12 ( x 2 ) 250 g 21 ( x1 ) g 22 ( x 2 ) 20 donde g11 ( x1 ) x12 g 21 ( x1 ) x1

2 g12 ( x 2 ) 2 x 2
g 22 ( x 2 ) x 2
buscamos los nmeros i y i tales que :
i xi i
MAESTRIA PYGE
Para el ejemplo : R1 0 x1 15.81 0 x 2 11.18 R2 0 x1 20 0 x1 20
0 x1 16 0 x2 12
sup ongamos pi , j xi pi , j 1
MAESTRIA PYGE
entonces para 0 1 xi pi , j (1 ) pi , j 1 y aproximamos f i ( xi ) f i ( pi , j ) (1 ) f i ( pi , j 1 ) g ir ( xi ) g ir ( pi , j ) (1 ) g ir ( pi , j 1 )
generali z a ndo
j1 j 2 j 3 j 4 ...... jn 1
MAESTRIA PYGE
x j j1 p j1 j 2 p j 2 j 3 p j 3 j 4 p j 4 ...... jn p jn f j ( x j ) j1 f j ( p j1 ) j 2 f j ( p j 2 ) j 3 f j ( p j 3 ) j 4 f j ( p j 4 ) ...... jn f j ( p jn ) gij ( x j ) j1 gij ( p j1 ) j 2 gij ( p j 2 ) j 3 gij ( p j 3 ) j 4 gij ( p j 4 ) ...... jn gij ( p jn ) donde exiten solamente 2 con sec utivos que son diferentes de cero
para el ejemplo
11 12 13 14 15 1 x1 11 p11 12 p12 13 p13 14 p14 15 p15 x1 11 0 12 4 13 8 1412 1516
21 22 23 24 25 1 x2 21 p21 22 p22 23 p23 24 p24 25 p25 x2 21 0 22 4 23 8 2412 2516
MAESTRIA PYGE
f1 ( x1 ) 11 f1 ( p11 ) 12 f1 ( p12 ) 13 f1 ( p13 ) 14 f1 ( p14 ) 15 f1 ( p15 ) f1 ( x1 ) 11 0 12 88 13 112 14 72 15 ( 32) f 2 ( x2 ) 21 f 2 ( p21 ) 22 f 2 ( p22 ) 23 f 2 ( p23 ) 24 f 2 ( p24 ) 25 f 2 ( p25 ) f 2 ( x2 ) 21 0 22 87 23 138 24 153) 25132 g11 ( x1 ) 11 g11 (0) 12 g11 ( 4) 13 g11 (8) 14 g11 (12) 15 g11 (16) g11 ( x1 ) 11 0 1216 13 64 14144 15 256 g12 ( x2 ) 12 g12 (0) 22 g12 (3) 23 g12 (6) 24 g12 (9) 25 g12 (12) g12 ( x2 ) 12 0 2218 23 72 24162 25 288 g 21 ( x1 ) 12 g12 (0) 22 g12 ( 4) 23 g12 (8) 24 g12 (12) 25 g12 (16) g 21 ( x1 ) 12 0 22 4 23 8 2412 2516 g 22 ( x1 ) 21 g 22 ( p21 ) 22 g 22 ( p22 ) 23 g 22 ( p23 ) 24 g 22 ( p24 ) 25 g 22 ( p25 ) g 22 ( x1 ) 21 0 22 6 23 6 24 9 2512
MAESTRIA PYGE
11 y1 12 y1 y2 13 y2 y3 14 y3 y4 15 y4 21 z1 22 z1 z2 23 z2 z3 24 z3 z4 25 z4
y1 y2 y3 y4 y5 1 z1 z2 z3 z4 z5 1 0 ij 1 y {0,1} z {0,1}
263
II. Modelos de Programacin Matemtica Programacin No - lineal

BIBLIOGRFIA EN PROGRAMACIN NO LINEAL
1. Nonlinear Programming, M.Bazaraa, H.Sherali and C.Shetty. John Wiley & Sons, Inc., New York, Second Edition 1993. 2. Nonlinear Programming, D.Bertsekas. Athena Scientific USA, 1995. 3. Numerical Methods for Unconstrained Optimization and Nonlinear Equations, J.Dennis and R.Schnabel. SIAM Classics in Applied Mathematics 16. SIAM Publications, Philadelphia, 1996. 4. Practical Methods of Optimization, R.Fletcher. John Wiley & Sons, Inc., 1981. 5. Introduccin a la Programacin Lineal y No Lineal, D.Luenberger. Adisson Wesley Iberoamericana 1989. 6. Mathematical Programming: Theory and Algorithms, M.Minoux. John Wiley & Sons, Inc., New York, 1986 7. Optimization Software Guide, J.Mor and S.Wright, SIAM Frontiers in Applied Mathematics 14, SIAM Publications, Philadelphia 1993.
264
MAESTRIA PYGE
II. Modelos de Programacin Matemtica Programacin No - lineal

DIRECCIONES ELECTRNICAS EN LINEAL
PROGRAMACIN NO
MAESTRIA PYGE
Preguntas de consulta frecuente en Programacin No Lineal:

http://www-unix.mcs.anl.gov/otc/Guide/faq/nonlinear-programming-faq.html
Servidor NEOS, gua de software de Programacin No Lineal :

http://www-fp.mcs.anl.gov/otc/Guide/SoftwareGuide/Categories/unconstropt.html http://www-fp.mcs.anl.gov/otc/Guide/SoftwareGuide/Categories/constropt.html
Servidor NEOS, ejemplo problema de carteras de inversin:

http://www-fp.mcs.anl.gov/otc/Guide/CaseStudies/port/index.html
Gua de software de Programacin No Lineal en revista OR&MS Today (INFORMS Magazine):

265
III. Programacin Dinmica
MAESTRIA PYGE
Contenidos
III. Programacin
Dinmica
266

MAESTRIA PYGE
La programacin dinmica se utiliza tanto en problemas lineales
como no lineales. La programacin dinmica es til para resolver un problema donde se deben tomar una serie de decisiones interrelacionadas. A diferencia de la P.L., la programacin dinmica no tiene formulacin matemtica estndar. Se trata de un enfoque de tipo general para la solucin de problemas, y las ecuaciones se derivan de las condiciones individuales de los mismos.
267
El problema de la diligencia
Un cazafortunas desea ir de Missouri a California en una diligencia, y quiere viajar de la forma ms segura posible. Tiene los puntos de salida y destino conocidos, pero tiene mltiples opciones para viajar a travs del territorio. Se entera de la posibilidad de adquirir seguro de vida como pasajero de la diligencia. El costo de la pliza estndar (Cij) se muestra en la tabla de la siguiente pgina. Cul es la ruta que minimiza el costo de la pliza de seguro?
MAESTRIA PYGE
268
MAESTRIA PYGE
269
Algunas Alternativas de Solucin

MAESTRIA PYGE
1.
2.
3.
Enumeracin exhaustiva: enumerar todas las rutas posibles, calcular su costo y elegir la de menor valor. En total son 18. Elegir la ruta ms barata en cada etapa. Esta solucin no necesariamente conduce al ptimo global. Un pequeo sacrificio en una etapa puede permitir mayores ahorros ms adelante Programacin Dinmica:
Estrategia de solucin: un problema complejo es desagregado en problemas ms simples que se resuelven etapa por etapa En el caso de la diligencia un problema simple sera pensar qu pasara si al viajero slo le faltara una etapa del viaje
270

Por P.D. la solucin sera entonces ir desde el estado actual (i cualquiera que sea) y llegar a su destino final (estado J) al costo cij. Se hace lo mismo para cada jornada (etapa), ensanchando el problema. As encontramos la solucin ptima del lugar al que debe dirigirse teniendo en cuenta la informacin de la iteracin anterior. Formulacin Sea Xn ( n = 1,2,3,4 ) las variables que representan el destino inmediato en la etapa n. A X1 X2 X3 X4 Donde X4 = J Sea fn (S, Xn) el costo total de la mejor poltica global para las etapas restantes, dado que el agente se encuentra en el estado S, listo para iniciar la etapa n y se dirige a Xn como destino inmediato.
MAESTRIA PYGE
271

Dados S y n , sea Xn* el valor de Xn (no necesariamente nico), que minimiza fn (S , Xn) , y sea fn*(S) el valor mnimo correspondiente de fn (S, Xn) entonces: fn* (S) = Min Xn fn(S, Xn) = fn(S, Xn*) Costo Mnimo costo Inmediato + futuro (etapa (etapa n) n+1 en adelante) cs , xn + fn+1* (Xn) Costo ptimo acumulado Costo por ir de la ciudad i al destino j
MAESTRIA PYGE
fn(S, Xn)
= =
272

Etapa n=4 Como el destino final (estado J) se alcanza al terminar la etapa 4, entonces
MAESTRIA PYGE
f5*(J) = 0 El objetivo es hallar f1*(A) y su ruta correspondiente. Cuando el cazafortunas tiene slo una etapa por recorrer (n=4) , su ruta de ah en adelante, estar determinada por el estado actual (H o I) y su destino final X4=J La ruta ser: S J donde S= H o I Luego f4*(S) = cS,J + f5*(J) = cS,J f4(H) = cH,J = 3 f4(I) = cI,J = 4
273
III. Programacin Dinmica Etapa n=3

El cazafortunas tiene 2 etapas por recorrer (n=3). Suponga que sale de E.
MAESTRIA PYGE
Luego f3*(E) = 4 y X3* = H En general para la etapa 3 se tiene:
274
Etapa n=2
En la segunda etapa, el cazafortunas tiene 3 jornadas por recorrer (n=2). Suponga que sale de C.
MAESTRIA PYGE
Luego f2*(C) = 7 y X2* = E En general para la etapa 2 se tiene:
275
Etapa n=1
En la primera etapa, el cazafortunas tiene todas las jornadas por recorrer (n=1). Necesriamente debe salir de A.
MAESTRIA PYGE
Luego f1*(A) = 11 y X1* = C D Veamos:
276
III. Programacin Dinmica La solucin del problema grficamente MAESTRIA PYGE
Podemos ver que hay 3 soluciones ptimas
277

Caractersticas de la P.D.
1. El problema se puede dividir por etapas, que requieren una poltica de decisin en cada una de ellas. 2. Cada etapa tiene un cierto nmero de estados asociados a su inicio. (Estados son las diferentes condiciones posibles en las que se puede encontrar el sistema en cada etapa del problema). 3. El efecto de la poltica de decisin en cada etapa, es transformar el estado actual en un estado asociado con el INICIO de la siguiente etapa. 4. El procedimiento pretende hallar la poltica ptima para el problema completo. Esto quiere decir, la poltica a emplear desde cualquier posible estado del problema. 5. Dado el estado actual, la poltica ptima desde este estado es independiente de las polticas adoptadas en las etapas anteriores. (la solucin depende nicamente del estado actual y no de cmo se lleg all) PRINCIPIO DE OPTIMALIDAD EN LA P.D., (Richard Bellman, 1957)
MAESTRIA PYGE
278

Caractersticas de la P.D. cont.
MAESTRIA PYGE
6. El procedimiento de la solucin termina cuando se obtiene la poltica ptima de la ltima etapa (por lo general la solucin en esta etapa es trivial) 7. Siempre se dispone de una relacin recursiva (esto es lo que permite trabajar las decisiones interrelacionadas). La relacin recursiva ser: fn* (Sn)= Max Xn { fn (Sn, Xn) } fn* (Sn)= Min Xn { fn (Sn, Xn) }
Donde: N: Nmero de etapas n: etiqueta para la etapa actual (n=1,2,3,N) Sn: Estado actual para la etapa n Xn: Variable de decisin para la etapa n
279

Caractersticas de la P.D cont.
MAESTRIA PYGE
8.Cuando se tiene una relacin recursiva como la de la funcin, el procedimiento de solucin hacia atrs inicia en la ltima etapa y se mueve hacia la primera, etapa por etapa
Xn* : Valor ptimo de Xn dado Sn
280
MAESTRIA PYGE
ALGORITMO DE P.D. HACIA ATRS: Para cada valor probable de la variable de estado al inicio de la etapa, determinar el mejor estado final
ALGORITMO DE P.D. HACIA ADELANTE: Para cada valor probable de la variable de estado al final de la etapa, determinar el mejor estado inicial
281
MAESTRIA PYGE
Introduccin a las tcnicas Heursticas
INTRODUCCIN
Esta es una nueva herramienta que nos ayuda en la
resolucin de los diferentes tipos de problemas.

MAESTRIA PYGE
As el objetivo es de minimizar costes y/o maximizar los
beneficios.
Estando dados de la siguiente forma:
optimizar f ( x) con las restricciones hi ( x) bi hi ( x) bi h ( x) b i i i 1..... l i 1..... m i 1..... n
INTRODUCCIN
Un algoritmo eficiente que se puede utilizar es el simplex.
MAESTRIA PYGE
Para el caso de tener muchas variables este ya no resulta eficiente, por el tiempo que requiere para realizar los clculos.
INTRODUCCIN
MAESTRIA PYGE
Existen los llamados Problemas de Optimizacin Combinatorios que contienen variables de decisin enteras y el espacio de soluciones est formado por ordenaciones o subconjuntos de nmeros naturales.
Los ms conocidos son:
Problema de la mochila Problema del viajante
Knapsack problem-De la mochila

MAESTRIA PYGE
Consiste en: Seleccionar de entre un conjunto de n productos, cada uno con un valor ci y un volumen vi. Determinando aquellos que quepan en un recipiente con volumen V y que tengan el mayor valor posible. As se determina un subconjunto para el cual:
|* 1..n
c
i
max
i 1..n
c
i
con la restricci n
v
i
Knapsack problem-De la mochila

MAESTRIA PYGE
xi toma el valor de 1 cuando el item se introduce en la mochila xi toma el valor de 0 en caso contrario. As:
max ci xi
i 1
con las restriccio nes
v x
i 1 i
V i 1..n
xi 0,1
Travelling Salesman Problem(TSP)

Dado un mapa de carreteras, se desea visitar n
MAESTRIA PYGE
ciudades de forma que se recorra el menor nmero de kilmetros y solo se visite una sola vez cada ciudad. Solucin Optima es la ruta
<1, 6, 3, 4, 2, 5>
6
15 20
Con un coste de 61km.

7
1
12 16
16
3
20 7 8 21 10
5
9
MAESTRIA PYGE
Complejidad Computacional
Problemas de tipo combinatorio

La enumeracin completa del conjunto de
MAESTRIA PYGE
soluciones y la generacin del conjunto de soluciones factibles no es eficiente.

El tiempo de clculo crece exponencialmente con
el nmero de tems del problema.
Problema de la mochila
Para el problema de la mochila el nmero de
subconjuntos del conjunto {1..n} es 2n

MAESTRIA PYGE
Si un computador pudiese generar en un segundo
un milln de esos subconjuntos el tiempo para hallar la solucin sera:

Con n = 20, 220 = un segundo. Con n = 40, 240 = dos semanas. Con n = 60, 260 = 365 siglos.
Problemas P
Aquellos para los cuales se conocen algoritmos que
MAESTRIA PYGE
necesitan un tiempo polinominal para ofrecer una solucin ptima.

Son resolubles eficientemente.
Problemas NP
Aquellos para los cuales no se conoce un algoritmo
MAESTRIA PYGE
polinomial de resolucin. No son algortmicamente resolubles eficientemente. P es un subconjunto de NP:
P NP
Problemas NP-completos
La mayora de problemas de inters empresarial son
MAESTRIA PYGE
NP-completos.
No se ha podido encontrar algoritmos eficientes
para la resolucin de problemas NP-completos.
MAESTRIA PYGE
Heursticas
HEURSTICAS
Del griego heuriskein que significa encontrar.
MAESTRIA PYGE
Son algoritmos que ofrecen soluciones factibles, que aunque no optimicen la funcin objetivo, se supone que al menos se acercan al valor ptimo.
Las heursticas son utilizadas como una herramienta til que da soluciones a problemas reales.
HEURSTICAS
Definicin:
MAESTRIA PYGE
Procedimientos simples, a menudo basados en el sentido comn, que se supone ofrecern una buena solucin (aunque no necesariamente la ptima) a problemas difciles, de un modo fcil y rpido Zanakis, Evans 1981
HEURSTICAS
Factores para la utilizacin de mtodos heursticos:
MAESTRIA PYGE
Cuando no existe un mtodo exacto de resolucin o ste requiere mucho tiempo de clculo o memoria. b. Cuando no se necesita la solucin ptima. c. Cuando los datos son poco fiables. d. Cuando las hay limitaciones de tiempo, espacio, etc. e. Como paso intermedio en la aplicacin de otro algoritmo.
a.
HEURSTICAS
MAESTRIA PYGE
Ventajas: Permiten mayor flexibilidad para el manejo de las caractersticas del problema.
Ofrecen ms de una solucin.
HEURSTICAS
Inconvenientes:
No es posible conocer la calidad de la solucin.
MAESTRIA PYGE
Existen mtodos para realizar acotaciones. Un
procedimiento es el de relajar el problema, de manera que sea ms fcil de resolver. utilizar mtodos que indican que la heurstica no es buena. heurstica.
Cuando estos procedimientos no son posibles, se puede
Siempre una tcnica exacta es mejor que cualquier tipo de
MAESTRIA PYGE
TIPOS DE HEURSTICAS
TIPOS DE HEURSTICAS
MTODOS CONSTRUCTIVOS
MAESTRIA PYGE
MTODOS DE DESCOMPOSICIN MTODOS DE REDUCCIN MANIPULACIN DEL MODELO MTODOS DE BSQUEDA POR ENTORNOS
MTODOS CONSTRUCTIVOS
MAESTRIA PYGE
Aaden paulatinamente componentes individuales a la solucin, hasta que se obtiene una solucin factible.
ALGORITMOS
GOLOSOS O DEVORA-DORES
(GREEDY)
MTODOS DE DESCOMPOSICIN
MAESTRIA PYGE
(Divide y vencers) Dividen el problema en subproblemas ms pequeos, siendo el
output de uno el input de otro.

APLICACIN A UN PROBLEMA DE
PROGRAMACIN LINEAL MIXTA.
MTODOS DE REDUCCIN
MAESTRIA PYGE
Identifican
alguna caracterstica que presumiblemente deba poseer la solucin ptima.
MANIPULACIN DEL MODELO

MAESTRIA PYGE
Modifican la estructura del modelo, hacindolo ms sencillo de resolver, y deduciendo de su solucin, la solucin del problema original.
REDUCIR EL ESPACIO DE SOLUCIONES AUMENTAR EL ESPACIO DE SOLUCIONES
MTODOS DE BSQUEDA POR ENTORNOS

MAESTRIA PYGE
Partiendo de una solucin factible inicial, y mediante alteraciones de esa solucin, pasan de forma iterativa a otras soluciones factibles de su entorno.
CRITERIO DE PARADA
ALMACENAMIENTO DE SOLUCIN PTIMA.

PASO DE UNA SOLUCIN FACTIBLE A OTRA.
(NEIGHBORHOOD)
MTODO DE BSQUEDA LOCAL O DE DESCENSO

MAESTRIA PYGE
En cada iteracin se pasa de una solucin actual a una de su entorno que sea mejor que ella,
finalizando cuando todas las soluciones del entorno sean peores.

OPTIMOS LOCALES.
EJEMPLO DE FUNCIN CON UN PTIMO LOCAL

MAESTRIA PYGE
Solucin inicial
ptimo local
Xi-2 Xi-1
Xi
Xi+1
MAESTRIA PYGE
Metaheursticas
Recocido Simulado
MAESTRIA PYGE
Recocer:
Proceso trmico para obtener estados de baja
energa en un slido, mediante un bao trmico.
Para cada temperatura durante el proceso de recocido, el slido puede alcanzar el equilibrio trmico solo si el enfriamiento se produce lentamente.
Caso contrario puede llegar a estados metaestables.
Recocido Simulado
MAESTRIA PYGE
La evolucin de un slido en el bao trmico puede
ser simulado mediante el algoritmo de la Metrpolis, basado en las tcnicas Monte Carlo. Realiza en paso de un estado a otro segn: Si el estado generado posee una energa menor que el estado que actualmente se tiene, se acepta el estado generado como actual. Caso contrario el estado se aceptar con una determinada probabilidad, la cual est en funcin de:

La temperatura La diferencia entre los dos niveles de energa.
Algoritmos genticos
MAESTRIA PYGE
Tcnicas de bsqueda basadas en la mecnica de

la seleccin natural y gentica [Goldberg, 1989]

Los algoritmos genticos son flexibles y pueden
ser aplicados problemas.
en un amplio nmero de
Algoritmos genticos
MAESTRIA PYGE
En los algoritmos biolgicos, la informacin hereditaria es pasada a travs de los cromosomas o genes, los cuales a su vez estn formados de un determinado nmero de valores (alelos).
Los organismos pueden agruparse formando poblaciones, los que mejor se adaptan tienen mayor probabilidad de sobrevivir y reproducirse.
Algoritmos genticos
MAESTRIA PYGE
Los alelos pueden representar valores de las variables de decisin, que se correspondern con los genes.
Los cromosomas representan las soluciones. Los algoritmos genticos, trabajan sobre una poblacin de soluciones generando una nueva en cada iteracin.
Bsqueda Tab
Los orgenes de la bsqueda tab se ubican a
MAESTRIA PYGE
fines de los 60s y principios de los 70s.

Se atribuye a Fred Glover, quien desarroll esta
heurstica para tratar de resolver problemas de cubierta no lineal, aunque varios de sus principios tambin fueron delineados independientemente por P. Hansen .
Bsqueda Tab
MAESTRIA PYGE
El uso de estructuras flexibles de memoria basadas en atributos,
diseadas para permitir una mejor explotacin de los criterios de evaluacin y la informacin histrica de la bsqueda que se conseguira con estructuras rgidas de memoria o con sistemas carentes de memoria condiciones que limitan y hacen ms flexible el proceso de bsqueda. Este mecanismo se encuentra inmerso en la tcnica en la forma de restricciones y criterios de aspiracin plazo), para implementar estrategias que intensifiquen y diversifiquen la bsqueda. Las estrategias de intensificacin refuerzan las propiedades de las combinaciones de movimientos que han demostrado ser buenas, mientras que las estrategias de diversificacin dirigen la bsqueda hacia nuevas regiones del espacio de soluciones factibles.
Un mecanismo asociado de control basado en la interaccin entre las
La incorporacin de memorias de diferente duracin (de corto a largo
GRASP
Una entre las metaheursticas ms exitosas que
aparecieron en los ltimos aos del siglo pasado es GRASP.
MAESTRIA PYGE
un mtodo multiarranque diseado para resolver
problemas difciles en optimizacin combinatoria. En su versin bsica cada iteracin consiste en dos fases: una fase constructiva cuyo producto es una solucin factible buena, aunque no necesariamente un ptimo local, y una bsqueda local, durante la cual se examinan vecindades de la solucin, al llegar a un ptimo local la iteracin termina. encontrada en cada una de ellas, hasta que se alcanza un criterio de terminacin.
La iteraciones continan, guardando la mejor solucin
Redes Neuronales
Una de las misiones en una red neuronal consiste en
MAESTRIA PYGE
simular las propiedades observadas en los sistemas neuronales biolgicos a travs de modelos matemticos recreados mediante mecanismos artificiales
Una red neuronal se compone de unidades llamadas neuronas. Cada neurona recibe una serie de entradas a travs de interconexiones y emite una salida. Esta salida viene dadas por 3 enlaces:
Enlace Sinptico Enlace de Activacin Enlace de Transferencia
Redes Neuronales
Enlace Sinptico: que por lo general consiste en la
MAESTRIA PYGE
sumatoria de cada entrada multiplicada por el peso de su interconexin (valor neto). Si el peso es positivo, la conexin se denomina excitatoria; si es negativo, se denomina inhibitoria. Puede no existir, siendo en este caso la salida la misma funcin de propagacin. devuelto por la funcin de activacin. Se utiliza para acotar la salida de la neurona y generalmente viene dada por la interpretacin que queramos darle a dichas salidas
Enlace de activacin: que modifica a la anterior.
Enlace de transferencia: que se aplica al valor
MAESTRIA PYGE
LOS INVENTARIOS SE RELACIONAN CON:

CONTABILIDAD: Proporcionan la estimacin de
costos en el control de inventarios. FINANZAS: Costos de oportunidad o intereses por concepto de la inversin en inventarios. SISTEMAS DE INFORMACIN: Desarrollo y mantenimiento de sistemas para la administracin de inventarios. MARKETING Y VENTAS: Se depende de los inventarios disponibles para atender a los clientes. OPERACIONES: Nos permite ejercer un control total del inventario en la empresa.
MAESTRIA PYGE
CONCEPTOS DE INVENTARIO
MAESTRIA PYGE
El inventario es volumen de materiales que
se tiene debido a que las partes o bienes terminados que se recibe, es mayor que el volumen de los mismos que se distribuye.
RAZONES PARA MANTENER INVENTARIOS ALTOS

SERVICIO AL CLIENTE: Un inventario alto acelera
la entrega y mejora la puntualidad en el reparto de mercanca; reduce la posibilidad de que se presenten faltantes o/y ordenes atrasadas. COSTO DE HACER PEDIDOS: Generalmente el costo de hacer pedidos es el mismo, independientemente del tamao del pedido, influyen factores como: 1.Tiempo para seleccionar un proveedor y negociar las condiciones de la operacin. 2.Tiempo para preparar la documentacin. 3.Tiempo para realizar el seguimiento y recibir la mercanca solicitada.
MAESTRIA PYGE

COSTO DE PREPARACIN: El costo que implica
reajustar una mquina para que fabrique un componente o artculo diferente del que estuvo fabricando anteriormente. Esto incluye la mano de obra y el tiempo requerido para efectuar las modificaciones, la limpieza y la instalacin de nuevas herramientas o aparatos. Adems se debe considerar los costos de material desperdiciado. El costo de preparacin es tambin independiente del tamao del pedido.
MAESTRIA PYGE

COSTO DE TRANSPORTE: El costo de transporte
de salida de la planta puede reducir aumentando los niveles de inventario. Tener inventario disponible permite realizar ms embarques con cargas completas y minimizar la necesidad de acelerar los embarques utilizando otras modalidades de transporte ms costosas. PAGOS A PROVEEDORES: Se puede reducir el total de los pagos a los proveedores obteniendo descuentos unitarios por volmenes o cantidades grandes de pedidos.
MAESTRIA PYGE
RAZONES PARA MANTENER INVENTARIOS BAJOS

La principal razn para mantener inventarios bajos es que el inventario representa una inversin monetaria temporal en bienes, por la cual la empresa tiene que pagar intereses (en lugar de recibirlos).
MAESTRIA PYGE

INTERS O COSTO DE OPORTUNIDAD: Para financiar un
MAESTRIA PYGE
inventario, las empresas tienen que conseguir un prstamo o perder la oportunidad de hacer un a inversin que nos puede devolver un rdito atractivo.
COSTOS DE ALMACENAMIENTO Y MANEJO:
El inventario requiere espacio y tiene que ser transportado para entrar o salir del almacn. Ese espacio tiene un costo, al igual que el personal y equipo (ejemplo montacargas), utilizados para manejar el inventario.
IMPUESTOS, SEGUROS Y MERMAS: Al final del ao, se pagan
ms impuestos cuando los inventarios son ms altos, y el seguro sobre los activos es ms caro cuando los elementos por asegurar son ms numerosos.

Las mermas o disminuciones se presentan
MAESTRIA PYGE
por:
1.
2. 3.
Robo o sustraccin de elementos del inventario por clientes o empleados Obsolescencia o caducidad del producto Deterioro por desperdicios o por daos fsicos (golpes accidentales).
TIPOS DE INVENTARIO
Los tipos de inventario no pueden identificarse por sus rasgos fsicos, sin embargo en trminos conceptuales cada uno tiene una gestacin diferente. Los tipos son: Inventario de Ciclo Inventario de Seguridad Inventario de Previsin Inventario en Trnsito
MAESTRIA PYGE
TIPOS DE INVENTARIO
INVENTARIO DE CICLO: La porcin del inventario
total que vara en forma directamente proporcional al tamao del lote se conoce como Inventario de Ciclo o Inventario del Ciclo. El tiempo transcurrido entre los pedidos se lo conoce como CICLO. La cantidad de inventario pedido o comprado, se lo conoce como TAMAO DE LOTE (Q). El tamao del lote, Q, vara en forma directamente proporcional al tiempo transcurrido (o ciclo) entre los pedidos. Cuanto ms tiempo transcurra entre dos pedidos sucesivos de un artculo determinado, tanto mayor tendr que ser el inventario de ciclo.
MAESTRIA PYGE
TIPOS DE INVENTARIO
Al inicio del ciclo el inventario es el mximo es decir Q Al final se encuentra en su mnimo valor, es decir 0 (cero) Por lo tanto, el inventario promedio de ciclo ser: Inventario Promedio de Ciclo = (Q+0)/2 = Q/2 Esta frmula es exacta, cuando la tasa de demanda es constante y uniforme. Sin embargo cuando la demanda por ciclo no es contante, proporciona una estimacin razonable y satisfactoria.
MAESTRIA PYGE
TIPOS DE INVENTARIO
MAESTRIA PYGE
INVENTARIO DE SEGURIDAD: Para evitar problemas en el servicio al cliente, se suele mantener un inventario extra, llamado inventario de seguridad, que es una proteccin contra la incertidumbre de la demanda, las cantidades suministradas y los tiempos de entrega. El inventario de seguridad garantiza que las operaciones no se interrumpan cuando esos problemas se presenten.
TIPOS DE INVENTARIO
INVENTARIO DE PREVISIN: Inventario que se
utiliza en las empresas para absorber las irregularidades que se presentan a menudo en la tasa de demanda o en el suministro. ejemplo. Los fabricantes de aparatos de aire acondicionado, suelen recibir hasta el 90% de su demanda anual durante solo tres meses al ao. Esa irregularidad en la demanda provoca que un fabricante acumule un inventario de previsin en los perodos de baja demanda, a fin de no tener que incrementar demasiado sus niveles de produccin cuando la demanda alcance sus puntos mximos.
MAESTRIA PYGE
TIPOS DE INVENTARIO
INVENTARIO EN TRNSITO: El inventario que se
mueve de un punto a otro recibe el nombre de inventario en trnsito. El inventario en trnsito esta constituido por los pedidos que los clientes han hecho, pero que todava no han sido entregado. El inventario en trnsito entre dos puntos puede medirse como la demanda promedio durante el tiempo de entrega, que es la demanda promedio del artculo por perodo (d) multiplicada por el nmero de perodos comprendidos dentro del tiempo de entrega del artculo (L), para trasladarse entre los dos puntos:
MAESTRIA PYGE
Inv. en Trnsito = dL
TIPOS DE INVENTARIO
EJEMPLO INVENTARIO DE CICLO E INVENTARIO
EN TRNSITO: Una planta enva mensualmente llantas a un mayorista, en partidas cuya lote promedio es de 2800 llantas. La demanda promedio del mayorista es de 700 llantas por semana y el tiempo de entrega desde la planta es de 3 semanas. Cuanto inventario del ciclo e inventario en trnsito maneja el mayorista? Inv. Del Ciclo = Q/2=2800/2= 1400 llantas Inv. En trnsito= DL= dL=(700 llantas/sem.)*3 sem. = 2100 llantas
MAESTRIA PYGE
336
TACTICAS PARA LA REDUCCION DE INVENTARIOS

Los administradores siempre buscarn formas efectivas para reducir el inventario, en trminos de costo. Es necesario entonces considerar algunos criterios como:
MAESTRIA PYGE
1.
Reducir el tamao del lote Q; sin embargo el hecho de efectuar tales reducciones en Q, sin realizar ningn otro cambio, nos puede complicar la situacin, por lo que es necesario tambin considerar adicionalmente aspectos como: Perfeccionar los mtodos para hacer pedidos y ajustes iniciales, lo cual abaratar los costos de hacer pedidos y de preparacin, y as permitir que el lote Q, pueda efectivamente ser menor. El incremento de la repetibilidad para suprimir o eliminar la necesidad de realizar cambios o alteraciones importantes.
TACTICAS PARA LA REDUCCION DE INVENTARIOS

Mejorar los pronsticos de demanda: esto nos evitar sorpresas en el comportamiento de los clientes. 3. Abreviar los tiempos de entrega: siempre que sea posible seleccionar proveedores que ofrezcan menores tiempos de entrega. 4. Reducir la incertidumbre en el suministro: los proveedores pueden ser ms fiables, si compartimos con ellos los planes de produccin. 5. Disminuir el Inventario de Previsin: para manejar con xito este criterio se necesita adicionalmente: Agregar nuevos productos con diferentes ciclos de demanda Organizar campaas de promocin de ventas fuera de temporada Ofrecer a los clientes planes de precios de tipo estacional
2.
MAESTRIA PYGE
COLOCACIN DE INVENTARIOS DE MANUFACTURA

Los gerentes toman decisiones sobre la colocacin de inventarios segn la clasificacin que se le da a un artculo: Artculo Especial: Aquel artculo que se fabrica a pedido, de acuerdo con ciertas especificaciones particulares, y en cantidades solicitadas. Artculo Estndar: Aquel que se fabrica para tenerlo en inventario y que normalmente est disponible cuando se lo requiere.
MAESTRIA PYGE
INVENTARIOS ANALISIS ABC
MAESTRIA PYGE
100
Porcentaje del valor monetario
CLASE C CLASE B
90 80 70 60 50 40 30 20 10 10 20 30 40 50 60 70 80 90 100
Porcentaje de los artculos CLASE A

Una organizacin tpica tiene miles de artculos en inventario, pero solo un pequeo porcentaje de ellos merecen ms atencin y control de la Gerencia El anlisis ABC, es un proceso que divide en 3 clases, de acuerdo con su uso monetario. Los artculos clase A: Representan tan solo el 20% del total de artculos, pero les corresponde el 80% de la inversin total. Los artculos clase B: Representan el 30%, pero les corresponde nicamente el 15% del uso monetario. Los artculos clase C: Les corresponde el 50% de los artculos, con apenas el 5% de la inversin total.
MAESTRIA PYGE
MAESTRIA PYGE
El objetivo del anlisis ABC, es identificar los niveles de inventario de los artculos clase A y permitir que la gerencia los controle cuidadosamente, utilizando adecuadamente los criterios analizados anteriormente
CANTIDAD ECONOMICA DE PEDIDO

MAESTRIA PYGE
La cantidad econmica de pedido EOQ (del ingls economic order quantity) permite determinar el mejor ciclo del nivel de inventario para un artculo, y por tanto, minimiza el total de los costos anuales de hacer pedidos y de manejo de inventarios.
CANTIDAD ECONOMICA DE PEDIDO

El planteamiento para hallar la EOQ se basa en Las siguientes suposiciones: 1.La demanda del artculo es constante (ej. siempre es de 10 unid. diarias) 2.No hay restricciones para el tamao de cada lote (ej. limitaciones por la capacidad del camin o del manejo de materiales) 3.Los dos nicos costos relevantes corresponden al manejo de inventario y el costo fijo por lote. 4.Las decisiones referentes a un artculo pueden tomarse independientemente de las decisiones de los dems. 5.El tiempo de entrega es constante (ej. siempre en 14 das se recibe exactamente lo que se pidi)
MAESTRIA PYGE
CLCULO DE LA EOQ
Cuando las suposiciones de la EOQ han sido satisfechas, el inventario del ciclo se comporta como se muestra en la figura: MAESTRIA PYGE
Inventario disponible (unidades)
Recepcin del pedido
Agotamiento del inventario (tasa de demanda)
Q/2
Inventario del ciclo promedio
1 ciclo
Porcentaje de los artculos

Niveles de inventario del ciclo
CLCULO DE LA EOQ
Un ciclo comienza con Q unidades en inventario (pedido), durante el ciclo es utilizado a una tasa constante. Se pide un nuevo lote calculando que el nuevo pedido se reciba precisamente cuando el inventario llegue a 0 (porque la demanda es constante). Ya que el inventario vara entre Q y 0, el inventario del ciclo promedio ser igual a la mitad del tamao del lote.
MAESTRIA PYGE
CLCULO DE LA EOQ
Costo total = CM+CP
Costo Anual (dolares) Costo Anual (dolares)
Costo de pedidos
Costo Anual (dolares)
CM
MAESTRIA PYGE
Costo de manejo
Tamao del lote (Q) (a) Costo anual de manejo de inventario
CP
Tamao del lote (Q) (b) Costo anual de hacer pedidos
Tamao del lote (Q) (c) Costo anual total
Costo anual manejo de inventarios= (inventario del ciclo promedio Q/2)(costo de manejo unitario H) Costo anual de hacer pedidos= (nm. pedidos/ao: D/Q)(costo de hacer pedidos o de preparacin S) Costo total (C) = costo anual de manejo + costo anual de hacer pedidos
CLCULO DE LA EOQ
En el siguiente ejemplo grfico observamos que el mejor tamao de lote, o EOQ, est en el punto ms bajo de la curva total (entre 50 y 100 unidades) MAESTRIA PYGE
Costo actual
3000
Costo Anual (dolares)
Costo total = Q/2*(H) + D/Q*(S)
2000 Costo de manejo = Q/2*(H)
1000 Costo de pedidos = D/Q*(S)
Costo mas bajo
50
100
150
200
250
300
350
400
El mejor Q (EOQ)
Tamao del lote (Q)
Actual Q
CLCULO DE LA EOQ
Esta frmula la obtenemos de las siguientes formas: - Con la derivada de la funcin del costo total con respecto a Q. - Igualando las frmulas correspondientes al costo anual de hacer pedidos y el costo anual de manejo de inventario y resolviendo para Q.
MAESTRIA PYGE
TIEMPO ENTRE PEDIDOS

MAESTRIA PYGE
El tiempo entre pedidos TBO (time between orders) para un tamao de lote es el tiempo promedio que transcurre entre la recepcin o solicitud de dos pedidos de reabastecimiento constituidos por Q unidades.
TBO EOQ = EOQ (12 meses/ao) D
COMPRESIN DEL EFECTO DE LOS CAMBIOS

MAESTRIA PYGE
- Un anlisis de sensibilidad de la EOQ, permite modificar sistemticamente los parmetros de importancia crucial a fin de determinar los efectos del cambio: - Un cambio en la tasa de demanda. A medida que aumenta la demanda, el tamao de lote tambin debe aumentar, pero ms lentamente que la demanda real.
COMPRESIN DEL EFECTO DE LOS CAMBIOS

- Un cambio en los costos de pedidos. Al aumentar
S, aumenta la EOQ, y en consecuencia, aumenta el inventario del ciclo promedio. - Un cambio en los costos de manejo de inventario. La EOQ disminuye a medida que H aumenta y viceversa. - Errores en la estimacin de D, H y S. El costo total es muy poco sensible a los errores, aun en el caso de que las estimaciones sean errneas por un amplio margen.
MAESTRIA PYGE
SISTEMAS DE CONTROL DE INVENTARIOS

Un sistema de control de inventarios responde a cunto y cundo debemos pedir. Al seleccionar un sistema, es fundamental considerar si el artculo corresponde a una demanda dependiente (son los que se requieren como componentes o insumos para un producto o servicio) o independiente (est afectada por las condiciones del mercado y no se relaciona con las decisiones de inventario de otro artculo).
MAESTRIA PYGE

El inventario de demanda independiente incluye: 1. Mercanca al mayoreo y al menudeo. 2. El inventario respectivo de la industria de servicios (ej. sellos y etiquetas en oficinas postales, artculos de oficina, artculos de supermercado, etc). 3. Inventarios para la distribucin de artculos finales y partes de sustitucin. 4. Suministros para mantenimiento, reparacin y operacin, es decir elementos que no forman parte del producto o servicio (uniformes para empleados, combustible). La demanda dependiente muestra un patrn muy distinto del que corresponde a la demanda independiente y deben administrarse con tcnicas diferentes
MAESTRIA PYGE

MAESTRIA PYGE
Los sistemas de control de inventarios especficamente son: - Sistema de revisin continua (Q) - Sistema de revisin peridica (P) - Sistemas hbridos:
-
Sistema de reabastecimiento opcional Sistema de inventario base
SISTEMAS DE CONTROL DE INVENTARIOS Sistema Q

Sistema de revisin continua, o sistema de punto de reorden (ROP) o sistema de cantidad de pedido fija. Se rastrea el inventario restante de un artculo cada vez que se hace un retiro del mismo, para saber si es momento de hacer un nuevo pedido. El estado de inventario (IP) mide la capacidad del artculo para satisfacer la demanda futura.
MAESTRIA PYGE

La IP(inventory position) se calcula con la relacion: IP = OH + SR BO Donde: OH = inventario disponible. SR = Las recepciones programadas (pedidos realizados, aun no recibidos) BO = rdenes atrasadas. Cuando la IP llega a un nivel mnimo predeterminado llamado punto de reorden (R), se pide una cantidad fija Q del artculo.
MAESTRIA PYGE

Sistema Q cuando la demanda y el tiempo de entrega son constantes y se conocen con certeza
El punto de reorden es igual a la demanda durante el tiempo de entrega. R En la figura anterior la O con pendiente Tiempo lnea descendente es el inventario disponible. Cuando aquel llega a R, se presenta un nuevo pedido. El inventario sigue descendiendo en el perodo de entrega L. El nuevo pedido llega justo cuando el inventario desciende a 0.
IP IP IP
Pedido recibido Pedido recibido Pedido recibido Pedido recibido
MAESTRIA PYGE
Inventario disponible
OH
OH
OH
Pedido prestado
Pedido prestado
Pedido prestado
TBO
TBO
TBO

Sistema Q cuando la demanda es incierta
IP
MAESTRIA PYGE
IP
Pedido recibido Pedido recibido
IP
Pedido recibido
Pedido recibido
R
Pedido prestado Pedido prestado Pedido prestado
O
L1 TBO 1 TBO 2 L2 TBO 3 L
3
Tiempo
Cuando la demanda es incierta: Punto de reorden = demanda promedio durante el perodo de entrega + inventario de seguridad.
Inventario disponible
La lnea ondulada con pendiente descendente indica que la demanda vara de un da a otro. La tasa de demanda cambiante denota que el tiempo entre perodos es variable, de modo que TBO1 TBO2 TBO3

MAESTRIA PYGE
Debido a la incertidumbre de la demanda, las ventas en el perodo de entrega son imprevisibles por lo que se aade un inventario de seguridad como medida de proteccin contra posibles perdidas de ventas. Cuanto ms grande sea el inventario de seguridad, y por ende ms alto el punto de reorden, tanto menos probable ser que se presenten faltantes.

Inventario de seguridad Una forma de determinar el inventario de seguridad adecuado es establecer un nivel de servicio o ciclo del nivel del servicio, es decir, la probabilidad deseada de no quedarse sin inventario en ningn ciclo de pedidos. Si la demanda vara poco en el ciclo, el inventario de seguridad puede ser pequeo, por el contrario, si la demanda vara en forma considerable de un ciclo a otro, el inventario de seguridad deber ser grande.
MAESTRIA PYGE

MAESTRIA PYGE
Ciclo del nivel de servicio = 85%
Demanda promedio durante el tiempo de entrega
Probabilidad de faltantes (1.0 - 0.85 = 0.15)
zs
Fig. Cmo encontrar el inventario de seguridad con una distribucin de probabilidad normal para un ciclo del nivel de servicio del 85%

La demanda promedio del tiempo de entrega es la lnea central, quedando el 50% a cada lado, entonces, si se selecciona un ciclo de nivel de servicio de 50%, el punto de reorden R sera la cantidad representada por esa lnea central. El inventario de seguridad ser 0 cuando R es igual a la demanda promedio. Para brindar un nivel de servicio por encima del 50%, el punto de reorden deber ser mayor que la demanda promedio durante el tiempo de entrega.
MAESTRIA PYGE

Clculo del inventario de seguridad Encontramos el inventario de seguridad multiplicando el nmero de desviaciones estndar, con respecto a la media que se requiera para aplicar el ciclo del nivel de servicio, z, por la desviacin estndar de la demanda en la distribucin de la probabilidad, L, durante el tiempo de entrega. Inventario de seguridad = z L
MAESTRIA PYGE
SISTEMAS DE CONTROL DE INVENTARIOS Sistema P

MAESTRIA PYGE
Conocido a veces como sistema de reorden a intervalos fijos o sistema de reorden peridico, e el cual la posicin de inventario de un artculo se revisa peridicamente y no en forma continua. Los nuevos pedidos se colocan siempre al final de cada revisin y el TBO tiene un valor fijo de P. La demanda total entre revisiones es variable.

MAESTRIA PYGE
En este caso persisten cuatro de las suposiciones originales de la EOQ:

- Que no existan restricciones en el tamao del lote. - Que los costos pertinentes sean los de manejo de
inventario y pedidos. - Que las decisiones de un artculo sean independientes de las decisiones del resto. - Que no exista incertidumbre en los tiempos de entrega ni en el suministro.

Sistema del tiempo entre revisiones Para manejar un sistema P, deben considerarse: la duracin del tiempo entre revisiones, P, y el nivel objetivo del inventario, T. La duracin del tiempo entre revisiones P, puede ser cualquier intervalo conveniente (todos los viernes, cada dos viernes). Seleccin del nivel objetivo de inventario Es el intervalo de proteccin o intervalo de tiempo para el cual deber estar planeado el inventario cuando se haga cada nuevo pedido, es decir T= d(P+L) (p perodos para revisar, corregir y restablecer la IP + tiempo de entrega).
MAESTRIA PYGE

MAESTRIA PYGE
Inventario de seguridad Se calcula de forma similar al sistema Q. Se multiplica las desviaciones estndar deseadas, z, por la desviacin estndar de la demanda en el curso de intervalo de proteccin, P+L Inventario de seguridad = z P+L
VENTAJAS COMPARATIVAS DE LOS SISTEMAS Q Y P

Las ventajas de los sistemas Q son las siguientes: 1. La frecuencia con que se revisa cada artculo puede ser individualizada. 2. Los tamaos de lote fijos, si son suficientemente grandes, suelen traducirse en descuentos por cantidad. 3. Los inventarios de seguridad ms bajos se traducen en ahorros.
MAESTRIA PYGE
VENTAJAS COMPARATIVAS DE LOS SISTEMAS Q Y P

Las ventajas de los sistemas P son las siguientes: 1. La administracin del sistema resulta cmoda porque el reabastecimiento se realiza a intervalos fijos. 2. Los pedidos de artculos mltiples de un mismo proveedor pueden hacerse en una sola orden de compra. 3. Solo es necesario conocer la IP (posicin de inventario), cuando se realiza una revisin.
MAESTRIA PYGE
SISTEMAS DE CONTROL DE INVENTARIOS Sistemas Hbridos

Sistemas Hbridos: - Sistema de reabastecimiento opcional. Se utiliza para revisar la IP a intervalos fijos, y si dicha posicin ha disminuido hasta un nivel predeterminado (para hacer un pedido de tamao variable que cubra las necesidades esperadas). - Sistema de inventario base. Expide una orden de reabastecimiento cada vez que realiza un retiro, por la misma cantidad que fue extrada en dicho retiro.
MAESTRIA PYGE

Presentacion Clases V 2

Cargado por

Copyright:

Formatos disponibles

Presentacion Clases V 2

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Presentacion Clases V 2

Cargado por

Copyright:

Formatos disponibles

MAESTRIA PYGE

Ing. Rodrigo Semprtegui lvarez

Ing. Rodrigo Semprtegui lvarez

Ing. Rodrigo Semprtegui lvarez

Ing. Rodrigo Semprtegui lvarez

Ing. Rodrigo Semprtegui lvarez

Ing. Rodrigo Semprtegui lvarez

Ing. Rodrigo Semprtegui lvarez

Mtodos probabilsticos: Cadenas de markov, teora de juegos,

lneas de espera, teora de inventarios, etc.

Mtodos heursticos: soluciones basadas en la experiencia.

Gran cantidad de problemas reales cada ms complejos y especializados requieren de:

de metodologas para matemtica de estos problemas.

Mtodos y herramientas de resolucin, como los

que provee la Investigacin de Operaciones.

I.1.1 Formulacin del Problema 1. Definir el Problema

Ing. Rodrigo Semprtegui lvarez

Formular el Modelo Matemtico para el Problema

Verificar el Modelo y usar el Modelo para Predicciones

Seleccionar la Alternativa Adecuada

Formular el Modelo Matemtico

Verificar el Modelo y usar para predicciones

Implantar y Evaluar Recomendaciones

I.2 Elementos de un modelo de optimizacin.

Ing. Rodrigo Semprtegui lvarez

Ing. Rodrigo Semprtegui lvarez

3 mesas, utilidad de U$60

Ing. Rodrigo Semprtegui lvarez

Qu quiere decir mejor?

Ing. Rodrigo Semprtegui lvarez

Qu restricciones limitan las decisiones?

Ing. Rodrigo Semprtegui lvarez

15x + 20y 2x + 2y 8 x + 2y 6 x,y 0

BIBLIOGRFIA EN INVESTIGACIN DE OPERACIONES

Ing. Rodrigo Semprtegui lvarez

II. Modelos de Programacin Matemtica Programacin Lineal

II. Modelos de Programacin Matemtica Programacin Lineal

Ing. Rodrigo Semprtegui lvarez

II. Modelos de Programacin Matemtica Programacin Lineal

Ing. Rodrigo Semprtegui lvarez

Desigualdad Lineal.- una desigualdad f(x1, x2, x3,. xn) b

Un problema de Programacin Lineal.- es un problema de

II. Modelos de Programacin Matemtica Programacin Lineal

II. Modelos de Programacin Matemtica Programacin Lineal

Ing. Rodrigo Semprtegui lvarez

El hecho de que cada restriccin de un problema de PL tiene

II. Modelos de Programacin Matemtica Programacin Lineal

Ing. Rodrigo Semprtegui lvarez

II. Modelos de Programacin Matemtica Programacin Lineal

II.4 Ejemplos de modelamiento. MAESTRIA PYGE

II. Modelos de Programacin Matemtica Programacin Lineal

Ing. Rodrigo Semprtegui lvarez

C.Dist. 1 C.Dist.2 C.Dist.3 Planta 1 Planta 2 21 28 25 13 15 19

II. Modelos de Programacin Matemtica Programacin Lineal

Diagrama: MAESTRIA PYGE

Planta 1 X12 X21 Planta 2 X13 X23 C.D.3 X22 C.D.2

II. Modelos de Programacin Matemtica Programacin Lineal

= 200 = 200 = 250

II. Modelos de Programacin Matemtica Programacin Lineal