Date post: | 18-Nov-2015 |
Category: |
Documents |
Upload: | camila-francisca-retamal-valenzuela |
View: | 249 times |
Download: | 3 times |
Optimizacin.
Prof. Oscar C. VsquezDII-Usach.
Temario1. Presentacin curso
a. Objetivos del cursob. Aspectos administrativosc. Programacin del cursod. Bibliografa.
2. Introduccina. Definicin Optimizacin-Investigacin de
Operaciones (IO)b. Historia de la IOc. El mundo de la IOd. Impacto de la IO en Chile y el mundo
Temario3. Programacin Lineal I
a. Definiciones y supuestos. b. Modelacin de problemas c. Mtodo grfico de resolucin.d. Mtodo simplex. e. Formulacin estndar.
4. Programacin Lineal IIa. Mtodo simplex, casos especiales.b. Dualidad fuerte y dbil.c. Anlisis de sensibilidad.d. Interpretacin econmica desde el modelo.
Temario
5. Programacin Lineal Enteraa. Modelamiento de problemas b. Mtodo de resolucin I. Ramificacin y acotamiento
6. Problemas de redesa. Conceptos bsicos de redes y grafos.b. Problemas clsicos: transporte-Asignacin-Flujo
mximoc. Mtodos de resolucin.d. Aplicaciones.
Temario1. Presentacin curso
a. Objetivos del cursob. Aspectos administrativosc. Programacin del cursod. Bibliografa.
2. Introduccina. Definicin Optimizacin-Investigacin de
Operaciones (IO)b. Historia de la IOc. El mundo de la IOd. Impacto de la IO en Chile y el mundo
Objetivo del Curso
Ingeniera Civil Industrial (ICI-USACH) Que hace?
Ingeniera Civil Industrial (ICI-USACH) Que hace?
Definicin de Perfil:El Ingeniero Civil Industrial de la Universidad de Santiago de Chile es un profesional con conocimientos, habilidades y actitudes que le permiten disear, gestionar e implementar organizaciones para la produccin de bienes y servicios para la comunidad, evidenciando un compromiso tico con las personas y el medioambiente. para lograr este propsito, cuenta con las competencias que le permiten integrar seres humanos, tecnologa, materiales e informacin, para contribuir al logro de los objetivos de una organizacin
Objetivo del Curso
Ingeniera Civil Industrial (ICI-USACH) Cmo lo hace?
ICI Cmo lo hace?
Realidad:Problemtica
Representacin (Modelo)
Implementacin
ConocimientosCompetencias-ICI
Respuesta: Solucin
Objetivo del curso
Proveer de conceptos, metodologa, tcnicas yaplicaciones de la investigacin operacional,dando nfasis a la compresin de este mtodocientfico como apoyo a la toma de decisionesmediante la identificacin, formulacin yresolucin de situaciones problemas.
Bibliografa
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, PrenticeHall, 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 andC.C.Price. CRC Press, 2000.
5. Practical Management Science: Spreadsheet Modeling andApplications, Winston, W.L., Albright S.C. y Broadie M., InternationalThomson Publishing Company, 1997
6. Articulo en revistas relacionados con el rea: EJOR, COR, OR etc.
Aspectos Administrativos
Profesor Ctedra: Oscar C. Vsquez, [email protected]: Lunes L1, L3 sala 418Atencin estudiantes: Oficina 208, martes 9:30 -10:30
Ayudante: A definir.Ayudantas: A definir.
mailto:[email protected]
Aspectos AdministrativosEvaluacin:Ctedra (4 evaluaciones)PEP 1. PEP 2. PP Controles (1 por PEP).PA Coef 2
Criterio Aprobacin:Nota Final >=3.95Si PEP 1, PEP 2 y PP >=3.95 o
1/3 (PEP 1 + PEP 2 + PP)>=4.95
Nota Final = 1/3 (PEP 1+PEP 2+ PP)
SinoNota Final = 1/4 (PEP 1+PEP 2+
PP + PA + PA - Min(PEP 1, PEP 2, PP, PA)
Nota final curso:Si Ctedra y Laboratorio >=3.95Nota Final = 0.7 Ctedra + 0.3
Laboratorio.SinoNota Final = Min(Ct, Lab)
Programacin cursoSemana Da lunes Contenido
1 16/03 Presentacin curso, Introduccin,
2 23/03
3 30/03
4 06/04
5 13/04
6 20/04 Control 1/ PEP 1
7 27/04
8 5/05
9 12/05
10 19/05
11 26/05 Control 2/ PEP 2
12 1/06
13 8/06
14 15/06
15 22/06 PA
16 6/07
Temario1. Presentacin curso
a. Objetivos del cursob. Aspectos administrativosc. Programacin del cursod. Bibliografa.
2. Introduccina. Definicin Optimizacin-Investigacin de
Operaciones (IO)b. Historia de la IOc. El mundo de la IOd. Impacto de la IO en Chile y el mundo
Qu es investigacin de operaciones (IO)?Investigacin de Operaciones (OperationReseach en ingls) es una disciplina que seocupa de la aplicacin de mtodos analticosavanzados para ayudar a la mejora de la tomade decisiones (INFORMS, 2012)Se considera tambin como un sub-campo delas matemticas (American MathematicalSociety, 2011)Trminos como Management science andDecision science son utilizados comosinnimos.
Qu es optimizacin?Optimizacin, en un problema de decisinasociado a la IEI, dice relacin con laseleccin de la mejor alternativa, respectoa un objetivo dado, considerando lasrestricciones que existen.En este contexto, el problema serepresenta a travs de un modelomatemtico en el cual se distinguen: unobjetivo, las variables y las restricciones.
1.- Objetivo
2.- Variables
3.- Restricciones
Es la medida cuantitativa del sistema que se desea optimizar (maximizar o minimizar)
Son las decisiones que afectan el objetivo del sistema.
Representan el conjunto de relaciones que ciertas variables estn obligadas a satisfacer.
Historia de la IO
Como disciplina formal, la investigacin operativa se origin en la Segunda Guerra Mundial.
En las dcadas posteriores a la guerra, las tcnicas empezaron a aplicarse con mayor frecuencia a problemas en los negocios, la industria y la sociedad.
Desde entonces, la investigacin operativa se ha ampliado en un campo ampliamente utilizados en diferentes sistemas de bienes y servicios (produccin, logstica, emergencia, etc.)
El mundo de la IOSociedades.IFORS: International Federation of Operational Research
Societies'EURO: Association of European Operational Research
SocietiesICHIO: Instituto Chileno de Investigacin de OperacionesConferencias.CLAIO: Congreso Latinoamrica de investigacin de
OperacionesEscuelas. ELAVIO: Escuela Latinoamericana de Investigacin de
Operaciones
Impacto de la IO en Chile y el mundo. INFORMS-Interfaces
Hewlett Packard: Delivering Profitable Growth for HPDirect.com Using Operations Research (Tanton et al., 2013)Optimizing Capital Investment Decisions at Intel Corporation (Kempf et al., 2013)A Method for Optimizing Waste Collection Using Mathematical Programming: A Buenos Aires Case Study (Bonomo et al., 2012) Scheduling the Chilean Soccer League by Integer Programming (Duran et al.,2007)Auction Improves School Meals in Chile (Epstein et al., 2002) A Strategic Empty Container Logistics Optimization in a Major Shipping Company (Epstein et al., 2012)
Un ejemploUsted tiene una empresa, donde vende mesas y sillas.Por cada mesa usted gana 3 u.m. y por cada silla usted gana 2 u.m. Suponga que no puede vender ms de 4 mesas, adems de restricciones de material, tiene solo 10 trozos de madera y 15 kilos de pegamento.Asuma que cada mesa ocupa 2 trozos de madera y cada sillaocupa 1 trozo de madera.Mientras cada mesa ocupa 1 kilos de pegamento y cada sillaocupa 3 kilos de pegamento.
.
Maximizar : Z = 3 + 2Sujeto a:
+
+
,
Restriccin 1
Restriccin 2
Restriccin 3
Solucin:
Restriccin 1
=
Restriccin 2
+ =
Restriccin 3
+ =
Si: = ; =
= ; =
Si: = ; =
= ; =
Indicacin: transformar las inecuaciones en ecuaciones
=
Mtodo GraficoIndicacin: crear un sistema de ecuaciones entre las rectas que se intersectan
+ = + = * -2
+ = =
=
= ; =
Funcin Objetivo: Z= + Despejando obtendremos: = =
Interseccin entre la restriccin 2, la restriccin 3 y la pendiente de la funcin objetivo
- Donde - representa la pendiente de la funcin
2 4 6 8 10 12 14 16
12
9
6
3
Simplex
Maximizar : Z = 3 + 2Sujeto a:
+ +
,
Recurso 1Recurso 2
Recurso 3
Estandarizando: + =
+ + = + + =
, , 0 variables de holgura
- Criterio de entrada a la base: la variable bsica positiva ms grande, entra a la base, en este caso 3>2 por lo tanto ingresa
Pivote
Criterio de salida: MIN { , ,
} = =
S1 S2 S3
- IMPORTANTE: Mnimo no negativo
-
Pivote
Criterio de salida: MIN { , ,
} = =
X1 S2 S3
- No se toma en cuenta
-
Pivote
Criterio de salida: MIN { , ,
} = =
X1 S2 X2
- Nmero negativo no se toma en cuenta
-
-
Ahora la solucin ptima que maximiza la F.O es:
X1=3 X2=4 Z =17
Definiciones y Supuestos
Problema de programacin lineal (PPL):Funcin objetivo lineal.Restricciones lineales en las variables.
Politopo convexo.Punto extremo.Tipos de soluciones:
Infactible, No acotada, Infinitas, Degenerada.
Modelacin de problemas y formulacin estndar
Modelacin: Variables de decisin, restricciones, funcin objetivo Formulacin estndar (PPL de la forma)
Max Z= CTX , sujeto a AX = b, X 0 C,X Rn , AMmxn, bRm , b 0
Casos:a. Min CTX = -Max CTXb. aijXj bi, aijXj + Xiholgura = bi, con Xih 0c. aijXj bi, aijXj - Xisuperflua = bi , con Xih 0d. Xj 0 , Xj = - Xje. Xj 0 , Xj = (Xj1 - Xj2 ), con Xj1 , Xj2 0f. bi 0 , la restriccin se multiplica por -1
Algunas Consideraciones de simplexEl mtodo simplex requiere de una solucin bsica factible (SBF).Problemas donde existe una restriccin del tipo o =, no es posible obtener una SBF.
Mtodos para obtener SBF: Gran M Dos Fases
http://148.204.211.134/polilibros/portal/Polilibros/P_Terminados/Investigacion_de_Operaciones_Careaga/Common/IO-modulo2-simplexpenal.htmhttp://148.204.211.134/polilibros/portal/Polilibros/P_Terminados/Investigacion_de_Operaciones_Careaga/Common/IO-modulo2-2fases.htm
Mtodo Gran MConsidere PPL estandarizado: Max Z = CtX , st AX = b, X 0 Entonces se construye :Max Z = CtX - yi M, st AX + Iy = b, X, y 0 , M >>1
El mtodo sacar a las yi de la funcin objetivo y = 0
Si existe un yi>0, el problema original es infactible.
Mtodo dos FasesConsidere PPL estandarizado: Max Z = CtX , st AX = b, X 0 Entonces se construye :Min W = yi, st AX + Iy = b, X, y 0 En el mtodo se despeja yi desde las restricciones. En el ptimo W = 0, es decir, yi = 0 , i. (Fase I)
Se elimina Y del problema y continua el problema original X y la funcin objetivo original (Fase II)
Algunas consideraciones del mtodo dos Fases
Si se trabaja con la Tabla, es conveniente guardar la fila Z de modo de hacer pocas iteraciones en la FASE II.
Si en la solucin ptima de FASE I se tiene que W > 0, entonces el problema original es infactible.
Situacin Especial: Si en el ptimo de FASE I existe un yi >0, pero tambin existe un Xj = 0, con Cj = 0 ,con j no bsico, entonces existe un ptimo alternativo y se puede reemplazar (la incorporacin a la base es sin costo).
Mtodo Simplex, Forma MatricialPASO 0: Obtener una solucin bsica factible: XB = B-1bPASO 1: Calcular el vector = CB B-1 y obtener los costos
reducidos de las variables no-bsicas: Cj = Cj - A.jPASO 2: Si Cj 0, j no bsico, PARAR. De lo contrario
obtener Cs = Mx{Cj} con Cj >0 e incorporar Xs a la basePASO 3: Calcular A.s = B-1A.s y con b = B-1b determinar
br/ ars = Min{bi/ais} con ais > 0 donde el ndice r seala a la variable Xr que sale.
PASO 4: Obtener la nueva base B y determinar su inversa. Luego, ir al paso 0.
Modelamiento en variables enteras
Oscar C. Vsquez
Aspectos Principales
Las soluciones de PPL tengan sentido prctico, se impone a las variables la condicin de que tomen solo valores enteros.
Esta condicin adicional de integridad en las variables transforma el PPL en uno de Programacin Lineal Entera. (PLE)
Variables binariasEn problemas de optimizacin lineal, cuando las decisiones son del tipo si o no, se puede modelar usando variables binarias (0,1).
1 Si la decisin j es siXj =
0 en otro caso
Alternativas Mutuamente Excluyentes: Slo una variable puede Tomar el valor 1: ( = 1), o cuando mucho una ( 1).Decisiones Contingentes: Dependen de decisiones previas (Xt Xt+1).
Algunas Aplicaciones:Problema de costo fijo
Suponga que debe decidir qu artculos fabricar en una lnea de produccin que opera por lotes.
El costo total de fabricacin del lote J es la suma del costo variable (Cj) y el costo fijo (Kj), esto es: CTj = Kj + CjXj con Xj como nivel de actividad
Este problema no se puede formular directamente dado el costo fijo. Esta dificultad se puede superar usando variables binarias.
PME/ MILP(mixed integer linear programming )
1 si Xj > 0Yj =
0 si Xj = 0Min Z = (CjXj + KjYj) st 0 Xj MYj ; Xj 0.Yj = {0,1} ; M: valor muy grandeSi Xj > 0, entonces Yj = 1 . Kj se suma al costo y Xj < M
Considere el problema que cuenta con dos restricciones, pero se requiere que solo una de ellas se cumpla, la otra puede cumplirse, pero no se requiere que lo haga.
Sean las dos restricciones siguientes:a11X1 + a12X2 b1 (restriccin 1) a21X1 + a22X2 b2 (restriccin 2)
Algunas Aplicaciones:Restricciones Excluyentes
MILPSolo una de ellas debe cumplirse, pero no necesariamente las dosSea: 1 Si se cumple la restriccin 1
Y = 0 si se cumple la restriccin 2
a11X1 + a12X2 b1 + M(Y-1) (restriccin 1) a21X1 + a22X2 b2 + M Y (restriccin 2) M: es un valor muy grande
Algunas Aplicaciones:Restricciones Excluyentes (k de n)
Suponga que en un problema con nrestricciones solo k de ellas deben cumplirse:
aijXj bi , i = 1,....n Parte del proceso de optimizacin es elegir la
combinacin de k restricciones que entregan el mejor valor de Z.
Las (n-k) restricciones no elegidas quedan eliminadas del problema.
MILP
1 si se debe cumplir la restriccin iYi =
0 otro caso
aijXj bi + (1-Yi)M M: valor muy grande
Yi = n-k; Yi ={1,0}
Algunas Aplicaciones:Problema Napsack o de la Mochila
Cada producto j tiene un aporte energtico aj y un peso wj
1 si el producto j es considerado en la mochila
Xj = 0 otro caso
Max ajXjst. wjXj W
Ejercicio: Una compaa puede entregar al mercado 4 productos. El gerente de produccin debe decidir cul de ellos fabricar y a qu nivel. La puesta en marcha de la lnea de produccin tiene asociado un costo fijo alto, el cual se muestra en la tabla siguiente, junto con el precio al cual se vende cada uno de ellos.Productos 1 2 3 4Costo fijo (M$) 50 40 70 60Precio de venta 70 60 90 80Por poltica de la empresa: a) no se puede producir ms de dos de estos productos
b) Cualquiera de los productos 3 4 se puede producir slo si se produce cualquiera de los productos 1 2.c) Solo una de las siguientes restricciones debe cumplirse.
5X1 + 3X2 + 6X3 + 4X4 6000 o bien,4X1 + 6X2 + 3X3 + 5X4 6000
Formule el modelo
DUALIDADMax Z = CtX, st AX b, X 0,
llamado Problema Primal (PP), existe un problema asociado llamado Problema Dual (PD), de la forma:
Min W = bt, st At C, 0.Note : PP m restricciones y n variables, entonces PD
tiene n restricciones y m variableCada variable dual est asociada a una restriccin del PP (por qu?).
DUALIDAD: Un caso especialMax Z = CtX, st AX =b, X 0, primalPor qu?Min W = bt, st At C, >< 0, dual
DUALIDAD: PropiedadesPropiedad de dualidad dbil.
Si X y son soluciones factibles en el PP y en el PD respectivamente, entonces se cumple:
Z = CtX W = bt .
Propiedad de dualidad fuerte. Sean X* y * soluciones factibles en el PP y en el PD
respectivamente; entonces ellas verifican que: CX* = b *.
DUALIDAD: Teorema de holgura complementaria
Sean X* y * soluciones factibles en el PP y en el PD respectivamente; entonces ellas verifican que:
(AX* - b) * = 0 y (At * - C) X* = 0.
DUALIDADMax Z = CtX, st AX b, X 0,
llamado Problema Primal (PP), existe un problema asociado llamado Problema Dual (PD), de la forma:
Min W = bt, st At C, 0.Note : PP m restricciones y n variables, entonces PD
tiene n restricciones y m variableCada variable dual est asociada a una restriccin del PP (por qu?).
Formulacin del Problema
Considere una pequea empresa que produce 2 tipos de pintura P1 y P2. El proceso de produccin requiere 3 materias primas (M1, M2 y M3) para elaborar estos dos productos. Para elaborar una tonelada de P1 se requiere 0,4 toneladas de M1 y 0,6 toneladas de M3. Una tonelada de P2 se forma con 0,5 toneladas de M1, 0,2 toneladas de M2 y 0,3 toneladas de M3. La disponibilidad de materia prima actual es de 20, 5 y 21 toneladas de M1, M2 y M3 respectivamente. El departamento de control de costos ha analizado el proceso y concluido que una tonelada de P1 genera una utilidad de M$ 40 en tanto que una tonelada de P2 solo genera una utilidad de M$ 30
Modelo matemtico
Max Z = 40P1 + 30P2Sujeto a: 0,4P1 + 0,5 P2 20 M1
0,2P2 5 M20,6P1 + 0,3 P2 21 M3
P1 ,P2 0
Solucin Optima Aplicando el algoritmo Simplex tabular, se obtiene la siguiente
solucin optima (en 2 iteraciones. Hgalo):
VB P1 P2 H1 H2 H3 LDP2 0 1 10/3 0 - 20/9 20H2 0 0 - 2/3 1 4/9 1P1 1 0 - 5/3 0 25/9 25-Z 0 0 -100/3 0 -400/9 -1600
Solucin Optima
En generalVB Xi Hj b
B-1A B-1 B-1b
-Z C-CBB-1A -CBB-1A -CBB-1b
Varia
bles
B
sicas
Modificacin de Parmetros
Que ocurrir con las solucin ptima si?: Cambia la utilidad obtenida por una o ambas
pinturas por cambios en: Precio al cual se transa en el mercado Costo de una o ms materias primas
Cambia la disponibilidad de una o ms de las materias primas
Se modifica la cantidad de materia prima requerida para elaborar cada pintura
Modificacin de Parmetros
Se disea una nueva mezcla llamada pintura 3 (P3) que utiliza las mismas materias primas
Se desea dejar de producir una de las pinturas Por condiciones legales, econmicas, ambientales,
etc..., se debe agregar nuevas restricciones al modelo matemtico inicial
Etc...
Anlisis de Sensibilidad
Se ocupa de la forma en que los cambios en los parmetros afectan la solucin ptima.
Slo se aplica cuando se ha obtenido la solucin ptima del problema original de programacin lineal.
Por la razn anterior suele llamarse tambin anlisis post optimal.
Anlisis de Sensibilidad
Cambio en la disponibilidad del recurso ( bi ) Cambio en el vector de coeficientes ( Cj ) Incorporacin de nuevas variables (Xn+1 ) Modificacin de un coeficiente tcnico ( aij ) Introduccin de nuevas restricciones ( Rm+1 )
1. Cambio en recursos (bi)
Altera slo la factibilidad del recurso; la optimalidad cambia en z* = * bi , slo si el recurso es escaso.
La solucin ptima se mantiene. En caso contrario, hacer lo siguiente:
1. Cambio en recursos (bi)
1.-Reemplazar, en la ltima iteracin del problema original, b por b`.
2.- Multiplicar por -1 las filas infactibles.3.- Agregar variables artificiales a las filas
arregladas.4.- Hacer Fase I y Fase II (o bien simplex dual).
Ejemplo 1
Suponga que la materia prima 1 ,(M1), del problema de pintura se incrementa en una unidad, entonces:b1 = 1
20b = 1 Solucin ptima del PPL original.
25
Ejemplo 1 (Cont.)
10/3 0 -20/9 Esta matriz se obtiene delB-1 = - 2/3 1 4/9 cuadro simplex ptimo
- 5/3 0 25/9 debajo de las V. de holgura.
b`= b + B-1 b
Ejemplo 1 (Continuacin)
Entonces:70/3 Esta nueva solucin se obtendra aplicando
b`= 1/3 simplex con M1 igual a 21 en lugar de 2070/3 en el problema original.
El nuevo valor de Z es : Z` = Z + z*z* = * b1, z* = (100/3)(1) = 100/3Z` = 1600 + 100/3 = 4900/3
Ejemplo 2
Suponga que la materia prima 2, (M2) del problema de pintura, se reduce en dos unidades, entonces:b2 = - 2 Como no se ha modificado b ni B-1 , la nueva
solucin es:b`= b + B-1 b
20 Esta nueva solucin se obtendra aplicando
b`= - 1 simplex con M2 igual a 3 en lugar de 5 en25 el problema original.
Ejemplo 2 (Continuacin)
El nuevo valor de Z es : Z` = Z + z* = 1600
Se reemplaza en el ltimo cuadro simplex del problema original, quedando una solucin infactible (simplex-dual) :
VB P1 P2 H1 H2 H3 LDP2 0 1 10/3 0 - 20/9 20H2 0 0 - 2/3 1 4/9 - 1P1 1 0 - 5/3 0 25/9 25
-Z 0 0 -100/3 0 -400/9 -1600
Ejemplo 2 (Continuacin) Recuperando la factibilidad se obtiene la nueva solucin
ptima y factible
VB P1 P2 H1 H2 H3 LDP2 0 1 0 5 0 15H1 0 0 1 - 3/2 - 2/3 3/2P1 1 0 0 - 5/2 -15/9 55/2
-Z 0 0 0 -50 -600/9 -1550
2. Cambio en costos (cj)
Corresponde a un cambio en la pendiente de la funcin objetivo y afecta un criterio de optimalidad del problema.Si cj = cj cB B-1 Aj 0 No cambia la base
Si cambia el vector costo en (c + c) ,entonces :cj = [cj + cj (cB + cB) B-1 Aij ] 0cj = [cj - (cB B-1 Aij) + cj - (cB B-1 Aij)] 0
2. Cambio en costos (cj)
cj = cj + cj 0En este caso, la base ptima no cambia. En caso contrario se reemplaza cj por cj en la tabla ptima y se hace la Fase II directamente.
Ejemplo 3Suponga que el precio del producto 1 (P1) se incrementa en 10 unidades monetarias (M$).
Ejemplo 3 (Continuacin) La nueva FO es: Z = 50P1 + 30P2DATOS:
C1 = 10 C = ( 0 , 0 , -100/3 , 0 , -400/9 ) C= ( 10 , 0 , 0 , 0 , 0 ) CB = ( 30 , 0 , 40 ) CB = ( 0 , 0 , 10 )
B-1 no se ha modificado luego es la misma de los ejemplos 1 y 2.
Ejemplo 3 (Continuacin)
cB B-1 = ( - 50/3 , 0 , 250/9 ) cB B-1 A = ( 10 , 0 , - 50/3 , 0 , 250/9 ) c -cB B-1 A = ( 0 , 0 , 50/3 , 0 , -250/9 ) C = C + C - [cB B-1 A] C = ( 0 , 0 , -50/3 , 0 , -650/9 ) 0 Se mantiene la base
Nuevo Valor de Z = (cB + cB)b = 1850
Ejemplo 4 Suponga que el precio del producto 1 (P1) se incrementa en 25
unidades monetarias (M$). Siguiendo el mismo procedimiento del ejemplo 3 se obtiene el
siguiente vector de costos reducidos: C = ( 0 , 0 , + 25/3 , 0 , -1025/9 ) 0 Se pierde la base de
solucin. El nuevo valor de Z es 2225 Como se ha perdido la optimalidad se debe reemplazar el
vector C y Z en el ltimo cuadro simplex.
Ejemplo 4 (continuacin)
El nuevo cuadro simplex, despus del reemplazo es el siguiente:
VB P1 P2 H1 H2 H3 LDP2 0 1 10/3 0 - 20/9 20H2 0 0 - 2/3 1 4/9 1P1 1 0 - 5/3 0 25/9 25
-Z 0 0 + 25/3 0 1025/9 -2225( 0 se pierde la optimalidad )
Ejemplo 4 (continuacin)
Recuperando la optimalidad se obtiene la siguiente solucin final:
VB P1 P2 H1 H2 H3 LDH1 0 3/10 1 0 - 2/3 6H2 0 1/5 0 1 0 5P1 1 1/2 0 0 15/9 35
-Z 0 -25/10 0 0 -975/9 -2275
3.- Incorporacin de nuevas variables
Otro cambio que aparece es la incorporacin de nuevas variables. Suponga que se incorporan (n+k) variables, con k=1,2,...,n. Eso implica que se conoce cn+k y A.n+k
Se obtiene el costo reducido cn+k = cn+k cB B-1 An+k, Si cn+k 0 , no se fabrica el producto. Sino cn+k > 0, se incorpora a la tabla simplex con la
columna reducida:An+k = B-1 A.n+k
Esto es lo que se incorpora a la tabla ptima final (agregando una nueva columna) y se hace la fase 2.
Ejemplo 5
Suponga que se desea producir una nueva pintura P3 con los siguientes parmetros:
C3 = 252/5 C3 = c3 cB B-1 A.3
A.3 = 2/5 C3 = + 125/45 ; > 01/5 Se incorpora al cuadro Simplex
cB y B-1 se conocen de ejemplos anteriores.
Ejemplo 5 (continuacin)
8/9A.3 = B-1 A.3 = 2/9 Nueva columna
-1/9El cuadro simplex ampliado es el siguiente:
VB P1 P2 P3 H1 H2 H3 LDP2 0 1 8/9 10/3 0 - 20/9 20H2 0 0 2/9 - 2/3 1 4/9 1P1 1 0 - 1/9 - 5/3 0 25/9 25-Z 0 0 125/45 -100/3 0 -400/9 -1600
Ejemplo 5 (continuacin)
Ingresando P3 a la base y sacado H2 se obtiene la siguiente solucin ptima, donde P3 tiene un nivel de actividad > 0
VB P1 P2 P3 H1 H2 H3 LDP2 0 1 0 6 - 4 - 4 16P3 0 0 1 - 3 9/2 2 9/2P1 1 0 0 - 2 1/2 3 51/2-Z 0 0 0 -25 -25/2 -50 -3225/2
4.- Incorporacin de nuevas Restricciones
Este cambio puede o no afectar al ESF. Si al reemplazar x* vectorial en la nueva restriccin se afecta la factibilidad de la solucin final, entonces:
1.- Se debe incorporar a la tabla final obtenida su forma cannica mediante operaciones fila y
2.- Multiplicar por (-1) la fila infactible para agregar la variable artificial.
3.- Realizar fases 1 y 2, o bien, simplex dual.
Universidad de Santiago de Chile - Depto. Ingenieria Industrial
Ejemplo 6 Suponga que por condiciones ambientales no se puede emitir
al ambiente ms de 100 unidades de contaminante. El proceso productivo genera 2 y 4 unidades de contaminante por cada tonelada de pintura P1 y P2 respectivamente.
La limitante anterior genera la siguiente nueva restriccin ambiental:
2P1 + 4P2 100 2P1 + 4P2 + H4 = 100 Esta nueva restriccin no cumple con la solucin ptima del
problema original.
Universidad de Santiago de Chile - Depto. Ingenieria Industrial
Ejemplo 6 (continuacin)
Se incorpora esta nueva restriccin al ltimo cuadro simplex, agregando una nueva fila y columnaVB P1 P2 H1 H2 H3 H4 LDP2 0 1 10/3 0 - 20/9 0 20H2 0 0 - 2/3 1 4/9 0 1P1 1 0 - 5/3 0 25/9 0 25H4 2 4 0 0 0 1 100-Z 0 0 -100/3 0 -400/9 0 -1600
Ejemplo 6 (continuacin) Se canoniza la base haciendo operaciones fila, resultando el
siguiente cuadro infactible:VB P1 P2 H1 H2 H3 H4 LDP2 0 1 10/3 0 - 20/9 0 20H2 0 0 - 2/3 1 4/9 0 1P1 1 0 - 5/3 0 25/9 0 25H4 0 0 - 10 0 30/9 1 - 30-Z 0 0 -100/3 0 -400/9 0 -1600
Universidad de Santiago de Chile - Depto. Ingenieria Industrial
Ejemplo 6 (continuacin) Aplicando Simplex Dual para recuperar la factibilidad se
obtiene la nueva solucin:VB P1 P2 H1 H2 H3 H4 LDP2 0 1 0 0 -10/9 1/3 10H2 0 0 0 1 2/9 -1/15 3P1 1 0 0 0 20/9 - 1/6 30H1 0 0 1 0 - 1/3 -1/10 3-Z 0 0 0 0 -500/9 -10/3 -1500
Universidad de Santiago de Chile - Depto. Ingenieria Industrial
5. Modificacin de un Coeficiente Tcnico (aij)
Suponga que se modifica A.k , con k=1,2,...,n. Esto implica que existen nuevos coeficientes tcnicos (aik).
Sea A`.k el nuevo vector de coeficientes tcnicos. Entonces, se obtiene el costo reducido c`k = ck cB B-1A`.k
Si c k 0 , no se fabrica el producto. Sino ck > 0, se incorpora a la tabla simplex con la
columna reducida:A.k = B-1 A.k
Esto es lo que se incorpora a la tabla ptima final (agregando una nueva columna) y se hace la fase 2.
Ejemplo 7 Suponga que por nuevas especificaciones tcnicas, para
producir una tonelada de pintura 1 (P1) se requiere 0,4 ; 0,4 y 0,2 toneladas de materia prima M1, M2 y M3 respectivamente.
2/5 2/5El vector A.1 = 0 ==> Cambia a : A`.1 = 2/5
3/5 1/5
Luego: c`1 = c1 cB B-1A`.1 = 160/9 > 0
Ejemplo 7 (continuacin)
8/9A.1 = B-1 A`.1 = 2/9 Nueva columna 1.
-1/9El cuadro simplex modificado sin canonizar es el siguiente:
VB P1 P2 H1 H2 H3 LDP2 8/9 1 10/3 0 - 20/9 20H2 2/9 0 - 2/3 1 4/9 1P1 -1/9 0 - 5/3 0 25/9 25
-Z 160/9 0 -100/3 0 -400/9 -1600
Universidad de Santiago de Chile - Depto. Ingenieria Industrial
Ejemplo 7 (continuacin)
El cuadro simplex canonizado es:
VB P1 P2 H1 H2 H3 LDP2 0 1 -10 0 20 220H2 0 0 - 4 1 6 51P1 1 0 15 0 - 25 -225-Z 0 0 -300 0 - 400 - 2400
Universidad de Santiago de Chile - Depto. Ingenieria Industrial
Ejemplo 7 (continuacin)
Finalmente, la solucin ptima es:
VB P1 P2 H1 H2 H3 LDP2 2 1 0 5 0 25H1 - 3/5 0 1 - 5/2 0 15/2H3 - 2/5 0 0 - 3/2 1 27/2-Z -20 0 0 - 150 0 -750
Universidad de Santiago de Chile - Depto. Ingenieria Industrial