INVESTIGACION DE OPERACIONESPROF.: FELIPE LILLO V. ING. CIVIL INDUSTRIALflillo@hualo.ucm.cl

INVESTIGACION DE OPERACIONESPrograma del CursoDESCRIPCION El curso trata principalmente sobre la aplicacin de los modelos usuales de Investigacin de Operaciones en la solucin de problemas reales, tales como modelos de Programacin Lineal, Problemas de Transporte y Asignacin, Simulacin y Teora de Inventarios.

OBJETIVOS Aplicar modelos cuantitativos en la resolucin de problemas de administracin.Optimizar soluciones usando la Investigacin de Operaciones.Conocer el potencial que presenta la simulacin en el diseo de procesos.Conocer los sistemas de manejo de inventarios basados en demanda conocida.

METODOLOGA

Clases expositivas para conceptos tericos con discusiones sobre cada tema.Practicas en laboratorio , donde se conocern diversos software de apoyo a la I.O.

INVESTIGACION DE OPERACIONESPrograma del CursoCONTENIDOS.Introduccin a la Investigacin de OperacionesDefinicin de I.O.Historia de la I.O.Campos de aplicacin.

2.Formulacin matemticaMetodologa para la generacin de modelos.Formulaciones matemticas tpicas presentes en la P.L.

3.Programacin LinealDefinicin de P.L.Mtodos de Resolucin:Mtodo grficoMtodo algebraico (simplex)Anlisis de sensibilidad.Problemas especiales de P.L:Problemas de transporteProblemas de asignacin

4. Introduccin a la SimulacinDefinicin de la simulacinGua para proyectos de simulacn.Simulacn de Monte CarloModelos con incrementos de tiempo discretosModelos con incrementos de tiempo variable.Softwares de Simulacin

5.Teora de InventariosModelos con demanda real conocida:Modelo General.Sistema de revisin continua.Sistemas de revisin peridica.

Nota Final = 0.25*P1+25*P2+0.2T+0.30*PGP1 / P2: Notas pruebas parcialesT: Promedio trabajos practicos.PG: Prueba global

FECHASPrueba 1: 02 de Octubre del 2003Prueba 2: 27 de Noviembre del 2003P. Global: 04 de Diciembre del 2003

BIBLIOGRAFIATitulo: Investigacin de OperacionesAutor: Hamdy TahaEditorial: Prentice Hall / sexta edicin.Ao: 1998Titulo: Administracin de OperacionesAutor: Roger SchroederEditorial: Mc Graw Hill. / 3 edicin / Ao: 1999

INVESTIGACION DE OPERACIONESDefinicin:Conjunto de tcnicas matemticas y estadsticas aplicable a diversos sistemas con el fin de mejorarlos, buscando las mejores alternativas de accin; esto mediante el modelamiento matemtico de los problemas en estudio.

Proceso: Conjunto de Actividades que crean una Salida o Resultado a partir de una o ms Entradas o Insumos.

Sistema: Un Conjunto de Elementos interconectados utilizados para realizar el Proceso. Incluye subprocesos pero tambin incluye los Recursos y Controles para llevar a cabo estos procesos.

En el diseo de Procesos nos enfocamos en QU se ejecuta.

En el diseo del Sistemas el nfasis est en los detalles de CMO, DNDE Y CUNDO.Sistemas v/s Procesos

Sistemas v/s Procesos

Con el propsito de estudiar cientficamente un sistema del mundo real debemos hacer un conjunto de supuestos de cmo trabaja.

Estos supuestos, que por lo general toman la forma de relaciones matemticas o relaciones lgicas, constituye un Modelo que es usado para tratar de ganar cierta comprensin de cmo el sistema se comporta.

Modelos

INVESTIGACION DE OPERACIONES

INVESTIGACION DE OPERACIONESClasificacin de los modelosExisten mltiples tipos de modelos para representar la realidad. Algunos son:

Dinmicos: Utilizados para representar sistemas cuyo estado vara con el tiempo.Estticos: Utilizados para representar sistemas cuyo estado es invariable a travs del tiempo.

Matemticos: Representan la realidad en forma abstracta de muy diversas maneras.Fsicos: Son aquellos en que la realidad es representada por algo tangible, construido en escala o que por lo menos se comporta en forma anloga a esa realidad (maquetas, prototipos, modelos analgicos, etc.).

Analticos: La realidad se representa por frmulas matemticas. Estudiar el sistema consiste en operar con esas frmulas matemticas (resolucin de ecuaciones).Numricos: Se tiene el comportamiento numrico de las variables intervinientes. No se obtiene ninguna solucin analtica.

INVESTIGACION DE OPERACIONESClasificacin de los modelosContinuos: Representan sistemas cuyos cambios de estado son graduales. Las variables intervinientes son continuas.Discretos: Representan sistemas cuyos cambios de estado son de a saltos. Las variables varan en forma discontinua.

Determinsticos: Son modelos cuya solucin para determinadas condiciones es nica y siempre la misma.Estocsticos: Representan sistemas donde los hechos suceden al azar, lo cual no es repetitivo. No se puede asegurar cules acciones ocurren en un determinado instante. Se conoce la probabilidad de ocurrencia y su distribucin probabilstica. (Por ejemplo, llega una persona cada 20 10 segundos, con una distribucin equiprobable dentro del intervalo).

INVESTIGACION DE OPERACIONESClasificacin de los modelosEs interesante destacar que algunas veces los modelos y los sistemas no pertenecen al mismo tipo.

Por ejemplo:El estudio del movimiento del fluido por una caera (Fluidodinmica) corresponde a sistemas continuos. Sin embargo si el fluido se lo discretiza dividindolo en gotas y se construye un modelo discreto por el cual circulan gotas de agua (una, dos, diez, cien, mil) se est representando un sistema continuo por un modelo discreto.Gotas

INVESTIGACION DE OPERACIONESClasificacin de los modelosLa obtencin del rea bajo la curva representada por f(x,y)=0 para el rango 0

INVESTIGACION DE OPERACIONESClasificacin de los modelosEl azar en computadora es pseudo azar:Mediante un algoritmo matemtico se generan nmeros al azar con una distribucin aleatoria similar a la real. Se los puede utilizar en los modelos estocsticos obteniendo similares resultados a los que se obtienen en el sistema real. Sin embargo, este azar es repetitivo (cualquiera que conoce el algoritmo puede predecirlo) lo cual contradice a lo que sucede en un proceso aleatorio.En este caso, un sistema estocstico es representado por un modelo pseudoazar (determinstico).

INVESTIGACION DE OPERACIONESClasificacin de los modelos segn la I.O.Modelo MatemticoEs aquel modelo que describe el comportamiento de un sistema a travs de relaciones matemticas y supone que todas las variables relevantes son cuantificables. Por ende tiene una solucin optima.

Modelo de SimulacinEs un modelo que imita el comportamiento de un sistema sobre un periodo de tiempo dado, esta basado en observaciones estadsticas. Este tipo de modelo entrega soluciones aproximadas.

Modelo HeursticoEs una regla intuitiva que nos permite la determinacin de una solucin mejorada, dada una solucin actual del modelo, generalmente son procedimientos de bsqueda. Este tipo de modelo tambin entrega soluciones aproximadas.

INVESTIGACION DE OPERACIONESTpicos relacionadosAnlisis EstadsticoSimulacinProgramacin LinealSistema de RedesLneas de EsperaProblemas de InventarioProgramacin No - LinealProgramacin DinmicaProgramacin EnteraTeora de DecisionesTeora de Juegos

INVESTIGACION DE OPERACIONESEl Arte del ModeladoLa I.O debe ser considerada como una ciencia y la vez como un arte.Una ciencia por el uso de tcnicas matemticas para la resolucin de los problemas.Un arte ya que la formulacin del modelo depende en gran parte de la creatividad y la experiencia delas operaciones del equipo investigador.

INVESTIGACION DE OPERACIONESEtapas para puesta en prctica1. Definicin del problema:Alternativas de decisin (vars. de decisin).El objetivo de estudio (Funcin Objetivo).Identificacin de las restricciones del sistema que se modela.

2. Construccin del modelo:Traducir el problema a relaciones matemticas que incluyan las vars. decisin, la Funcin Objetivo y las restricciones.

3. Solucin del modelo:Uso de algoritmos de optimizacin.Se encuentran los valores de las vars. decisin.

4. Validacin del modelo:El modelo entrega una prediccin razonable del comportamiento del sistema estudiado?

5. Puesta en prctica:Traducir los resultados del modelo en instrucciones de operacin.

PROGRAMACIN LINEAL

PROGRAMACIN LINEALEs un mtodo matemtico que se emplea para resolver problemas de optimizacin. En palabras simples la P.L. busca asignar recursos limitados, entre actividades que compiten, de la forma mas optima posible.

Supuestos de la P.L.ProporcionalidadAditividadDivisibilidadCertidumbreObjetivo nicoNo negatividad

PROGRAMACIN LINEALConstruccin de modelosPROBLEMA DE LA MEZCLA DE PRODUCTOSUna compaa fabrica dos tipos de componentes electrnicos: transistores y bobinas.Cada transistor requiere un minuto de tiempo en el departamento de ensamble, dos minutos de tiempo en el departamento de Control de Calidad y un minuto de tiempo en empaque.Cada bobina requiere dos minutos de tiempo en ensamble, un minuto de tiempo en Control de Calidad y dos minutos en empaque.Existe un total de 300 minutos en Ensamble, 400 minutos en C. Calidad y 400 minutos en Empaque disponibles cada da. Tanto los transistores como las bobinas contribuyen en un dlar a la utilidad.La compaa desea determinar la mezcla de productos optima que maximice la utilidad total.

PROGRAMACIN LINEALConstruccin de modelosSolucin: FormulacinPaso 1: Identificar el objetivo (meta) a optimizarMaximizar las utilidades de la compaa (U).{dlares/da}Paso 2: Identificar las variables de decisin que deseamos determinarX.Cantidad de transistores a fabricar por da {unds./da}Y.Cantidad de bobinas a fabricar por da {unds./da}Paso 3: Identificar las restricciones del modeloR1) Tiempo disponible en el depto. de Ensamble por da 300 min.R2) Tiempo disponible en el depto. de C. Calidad por da de 400 min.R3) Tiempo disponible en el depto. de Empaque por da de 400 min.R4) No Negatividad.

PROGRAMACIN LINEALConstruccin de modelosPaso 4: Construccin del modelo matemticoF.ObjetivoMAX { U = X + Y }Sujeto a :R1) X + 2Y 300R2) 2X + Y 400R3) X + 2Y 400R4) X , Y 0

PROGRAMACIN LINEALConstruccin de modelosEJERCICIO PROPUESTOEl departamento de rayos X de un hospital tiene dos mquinas, A y B, que pueden utilizarse para revelar radiografas. La capacidad de procesamiento diaria de estas mquinas es A=80 y B=100 radiografas. El departamento debe planear procesar al menos 150 radiografas por da. Los costos de operacin por radiografa son $4 para la mquina A y $3 para la mquina B. Cuntas radiografas por da debe procesar cada mquina para minimizar costos?

Se pide:Formular como un problema de P.L. identificando claramente la funcin objetivo y las variables de decisin.

PROGRAMACIN LINEALConstruccin de modelosSolucin: FormulacinPaso 1: Identificar el objetivo (meta) a optimizarMinimizar los costos de procesamiento (C).{dlares/da}Paso 2: Identificar las variables de decisin que deseamos determinarX.Cantidad de radiografas a procesar en mquina A al da {rad./da}Y. Cantidad de radiografas a procesar en mquina B al da {rad./da}Paso 3: Identificar las restricciones del modeloR1) Capacidad de procesamiento de rad. en la maquina A de 80.R2) Capacidad de procesamiento de rad. en la maquina B de 100.R3) Capacidad mnima del departamento de 150 rad. por da.R4) No Negatividad.

PROGRAMACIN LINEALConstruccin de modelosPaso 4: Construccin del modelo matemticoF.ObjetivoM IN { C = 4X + 3Y }Sujeto a :R1) X 80R2) Y 100R3) X + Y 150R4) X , Y 0

PROGRAMACIN LINEALConstruccin de modelosPROBLEMA DE LA DIETALa compaa OF utiliza diariamente por lo menos 800 libras de alimento especial. El alimento especial es una mezcla de maz y semilla de soya, con las siguientes composiciones.

notas test

ADMINISTRACION DE LA PRODUCCION

NOTAS

TEST 1TEST 2TEST 3*TEST 4TEST 5*TEST 6*TEST 7TEST 8*PromedioPruebas ParcialesPruebaPromedioCondicin

NAPELLIDONOMBRE19-Mar26-Mar2-Apr16-Apr14-May28-May19-Jun30-JunTestNota1Nota2GlobalFinalAlumno

1ALVAREZPATRICIA1.002.405.706.505.005.803.506.005.81.31.12.82.6REPROBADO

2CISTERNASPABLO6.301.004.003.801.001.001.006.004.24.01.06.04.0APROBADOAYUDA

3DIAZSERGIO6.801.004.003.806.005.504.005.505.62.21.45.64.0APROBADOAYUDA

4GAETEBLANCA3.803.205.504.006.005.804.006.505.62.32.66.34.2APROBADO

5GAJARDOMARISOL3.501.001.005.706.405.801.006.005.54.32.24.34.0APROBADO

6GARCAJOSE1.002.105.004.006.003.501.006.505.05.01.75.94.4APROBADO

7GARRIDOMIGUEL1.004.104.806.506.405.801.006.005.95.52.54.04.4APROBADO

8LETELIERIVONNE3.803.404.504.006.405.802.006.005.34.01.95.74.3APROBADO

9LETELIEREDUARDO1.003.305.703.806.803.503.506.505.33.11.13.03.0REPROBADO

10MOYARICARDO3.201.001.001.006.005.504.005.504.82.91.45.23.6REPROBADO

11OKUINGHTTONSPATRICIO3.502.206.004.006.803.804.206.505.52.32.15.54.0APROBADOAYUDA

12SOTOVICTOR3.304.005.804.006.806.004.206.505.91.11.94.04.0APROBADOAYUDA

13ZUIGAMAURICIO1.001.503.804.006.003.501.006.504.84.42.96.34.7APROBADO

Promedio Curso3.94

N de Aprobados10

* : Una tarea reemplaza el test.

&CNotas Adm. de la Produccin

&CPrimer semestre 2001

asistencia

ASISTENCIA SEM 1 -2001

ASISTENCIA

NAPELLIDONOMBRE12-Mar19-Mar26-Mar2-Apr9-Apr16-Apr23-Apr30-Apr7-May14-May28-May4-Jun18-Jun25-Jun30-Jun9-Jul%

1ALVAREZPATRICIAppppOKppOKOK46%

2CISTERNASPABLOpppppppOKpppOKOK77%

3DIAZSERGIOpppppppOKpppppOKOK92%

4LETELIEREDUARDOppppppOKppppOKOK77%

5GAETEBLANCApppppppOKppppppOKOK100%

6GAJARDOMARISOLppppppOKppppOKOK77%

7GARCAJOSEpppppOKppppOKOK69%

8GARRIDOMIGUELppppppOKpppppOKOK85%

9LETELIERIVONNEpppppppOKpppppOKOK92%

10MOYARICARDOpppppOKppppOKOK69%

11OKUINGHTTONSPATRICIOppppppOKpppppOKOK85%

12SOTOVICTORppppppOKpppppOKOK85%

13ZUIGAMAURICIOppppppOKpppppOKOK85%

Hoja3

NAPELLIDONOMBRENota

1ALVAREZPATRICIA1.10

2CISTERNASPABLO1.00

3DIAZSERGIO1.40

4GAETEBLANCA2.60

5GAJARDOMARISOL2.20

6GARCAJOSE1.70

7GARRIDOMIGUEL2.50

8LETELIERIVONNE1.90

9LETELIEREDUARDO1.10

10MOYARICARDO1.40

11OKUINGHTTONSPATRICIO2.10

12SOTOVICTOR1.90

13ZUIGAMAURICIO2.90

NAPELLIDONOMBRERUTN1N2N3N4NF

11CISTERNASPABLO10.388.162-54.204.001.006.004.00

12DIAZSERGIO13.345.275-35.602.201.405.604.00libra componente por libra de alimento ganado

A. ganadoProteinasFibraCosto

US$/lb

Maz0.090.020.30

Similla Soya0.600.060.90

10580.1020793951

&C&12NOTAS FINALES&"Arial,Negrita"&9ADMINISTRACION DE LA PRODUCCION (VESPERTINO)

&LPrimer semestre 2001

ivas

IVAS

2001Folio Declaracin N 016625395Septiembre

Folio Declaracin N 017120415Octubre

Folio Declaracin N 018208675Noviembre

Folio Declaracin N 019305215Diciembre

2002Folio Declaracin N 020561795Enero

Febrero

Folio Declaracin 023218485Marzo

Folio Declaracin N 025973055Abril

Folio Declaracin N 026041275Mayo

Folio Declaracin N 027579945junio

Julio

Agosto

Septiembre

Octubre

Noviembre

Diciembre

PROGRAMACIN LINEALConstruccin de modelosLos requerimientos dietticos diarios de alimento especial estipulan por lo menos un 30% de protenas y cuando mucho un 5% de fibra. OF desea determinar el costo mnimo diario de la mezcla de alimento..?

PROGRAMACIN LINEALConstruccin de modelosSolucin: FormulacinPaso 1: Identificar el objetivo (meta) a optimizarMinimizar el costo diario total de la mezcla de alimento(C).{dlares/da}Paso 2: Identificar las variables de decisin que deseamos determinarX.libras de maiz en la mezcla diaria {lb./da}Y. Libras de semilla de soya en la mezcla diaria {lb./da}Paso 3: Identificar las restricciones del modeloR1) Requerimientos de alimentos de por lo menos 800 lbs.al daR2) Requerimiento de protenas de por lo menos un 30%R3) Requerimientos de fibra de cuando mucho un 5%.R4) No Negatividad.

PROGRAMACIN LINEALConstruccin de modelosPaso 4: Construccin del modelo matemticoF.ObjetivoM IN { C = 0.3X + 0.9Y }Sujeto a :R1) X + Y 800R2) 0.09X + 0.6Y 0.3(X + Y)R3)0.02 X + 0.06Y 0.05(X + Y)R4) X , Y 0

PROGRAMACIN LINEALConstruccin de modelosPaso 4.1: Construccin del modelo matemtico (ORDENADO)F.ObjetivoM IN { C = 0.3X + 0.9Y }Sujeto a :R1) X + Y 800R2) 0.21X - 0.30Y 0R3)0.03 X - 0.01Y 0R4) X , Y 0

PROGRAMACIN LINEALConstruccin de modelosPROBLEMA DE TRANSPORTEConsidere el problema que enfrenta el departamento de planificacin de la compaa DALLAS S.A. ,que tiene tres plantas y cuatro almacenes regionales. Cada mes se requiere de una lista de requerimientos de cada almacn y se conocen, tambien las capacidacdes de produccin de las plantas. Ademas se conoce el costo de transporte de cada planta a cada almacn. El problema es determinar qu plantas deben abastecer a que almacenes de manera que minimicen los costos totales de transporte. Consideremos que los costos de transporte entre dos ciudades cualquiera, son proporcionales a las cantidades embarcadas. Supongase que las capacidades mensuales de cada planta son 70, 90 y 180 respectivamente. Los requerimientos de cada almacn para el mes de Marzo son: 50, 80, 70 y 140. Los costos unitarios de transporte son los que se muestran en la tabla siguiente:

PROGRAMACIN LINEALConstruccin de modelosSe pide:Formular como un PPL.

notas test

ADMINISTRACION DE LA PRODUCCION

NOTAS

TEST 1TEST 2TEST 3*TEST 4TEST 5*TEST 6*TEST 7TEST 8*PromedioPruebas ParcialesPruebaPromedioCondicin

NAPELLIDONOMBRE19-Mar26-Mar2-Apr16-Apr14-May28-May19-Jun30-JunTestNota1Nota2GlobalFinalAlumno

1ALVAREZPATRICIA1.002.405.706.505.005.803.506.005.81.31.12.82.6REPROBADO

2CISTERNASPABLO6.301.004.003.801.001.001.006.004.24.01.06.04.0APROBADOAYUDA

3DIAZSERGIO6.801.004.003.806.005.504.005.505.62.21.45.64.0APROBADOAYUDA

4GAETEBLANCA3.803.205.504.006.005.804.006.505.62.32.66.34.2APROBADO

5GAJARDOMARISOL3.501.001.005.706.405.801.006.005.54.32.24.34.0APROBADO

6GARCAJOSE1.002.105.004.006.003.501.006.505.05.01.75.94.4APROBADO

7GARRIDOMIGUEL1.004.104.806.506.405.801.006.005.95.52.54.04.4APROBADO

8LETELIERIVONNE3.803.404.504.006.405.802.006.005.34.01.95.74.3APROBADO

9LETELIEREDUARDO1.003.305.703.806.803.503.506.505.33.11.13.03.0REPROBADO

10MOYARICARDO3.201.001.001.006.005.504.005.504.82.91.45.23.6REPROBADO

11OKUINGHTTONSPATRICIO3.502.206.004.006.803.804.206.505.52.32.15.54.0APROBADOAYUDA

12SOTOVICTOR3.304.005.804.006.806.004.206.505.91.11.94.04.0APROBADOAYUDA

13ZUIGAMAURICIO1.001.503.804.006.003.501.006.504.84.42.96.34.7APROBADO

Promedio Curso3.94

N de Aprobados10

* : Una tarea reemplaza el test.

&CNotas Adm. de la Produccin

&CPrimer semestre 2001

asistencia

ASISTENCIA SEM 1 -2001

ASISTENCIA

NAPELLIDONOMBRE12-Mar19-Mar26-Mar2-Apr9-Apr16-Apr23-Apr30-Apr7-May14-May28-May4-Jun18-Jun25-Jun30-Jun9-Jul%

1ALVAREZPATRICIAppppOKppOKOK46%

2CISTERNASPABLOpppppppOKpppOKOK77%

3DIAZSERGIOpppppppOKpppppOKOK92%

4LETELIEREDUARDOppppppOKppppOKOK77%

5GAETEBLANCApppppppOKppppppOKOK100%

6GAJARDOMARISOLppppppOKppppOKOK77%

7GARCAJOSEpppppOKppppOKOK69%

8GARRIDOMIGUELppppppOKpppppOKOK85%

9LETELIERIVONNEpppppppOKpppppOKOK92%

10MOYARICARDOpppppOKppppOKOK69%

11OKUINGHTTONSPATRICIOppppppOKpppppOKOK85%

12SOTOVICTORppppppOKpppppOKOK85%

13ZUIGAMAURICIOppppppOKpppppOKOK85%

Hoja3

NAPELLIDONOMBRENota

1ALVAREZPATRICIA1.10

2CISTERNASPABLO1.00

3DIAZSERGIO1.40

4GAETEBLANCA2.60

5GAJARDOMARISOL2.20

6GARCAJOSE1.70

7GARRIDOMIGUEL2.50

8LETELIERIVONNE1.90

9LETELIEREDUARDO1.10

10MOYARICARDO1.40

11OKUINGHTTONSPATRICIO2.10

12SOTOVICTOR1.90

13ZUIGAMAURICIO2.90

NAPELLIDONOMBRERUTN1N2N3N4NF

11CISTERNASPABLO10.388.162-54.204.001.006.004.00

12DIAZSERGIO13.345.275-35.602.201.405.604.00libra componente por libra de alimento ganado

A. ganadoProteinasFibraCosto

US$/lb

Maz0.090.020.30

Similla Soya0.600.060.90

10580.1020793951

PlantaAlmacn

1234

119305010

270304060

34087020

&C&12NOTAS FINALES&"Arial,Negrita"&9ADMINISTRACION DE LA PRODUCCION (VESPERTINO)

&LPrimer semestre 2001

ivas

IVAS

2001Folio Declaracin N 016625395Septiembre

Folio Declaracin N 017120415Octubre

Folio Declaracin N 018208675Noviembre

Folio Declaracin N 019305215Diciembre

2002Folio Declaracin N 020561795Enero

Febrero

Marzo

Abril

Mayo

junio

Julio

Agosto

Septiembre

Octubre

Noviembre

Diciembre

PROGRAMACIN LINEALConstruccin de modelosPaso 4.1: Construccin del modelo matemticoF.ObjetivoMin{C=19X11+70X21+40X31+30X12+30X22+8X32+50X13+40X23+70X33+10X14+60X24+20X34}Sujeto a :R1) X11+X12+X13+X14 70R2) X21+X22+X23+X24 90R3) X31+X32+X33+X34 180R4) X11+X21+X31 50R5) X12+X22+X32 80R6) X13+X23+X33 70R7) X14+X24+X34 140R8) Xij 0 i , j

8Modelo General de PL Definicin de variables:Sea xj = #.... ; j = 1, 2, 3....nFuncin objetivo:Max. o Min. z = C1X1 + C2X2 + ... + CjXj + ... + CnXn Sujeto a restricciones: i = 1, 2, 3, ... , ma11X1 + a12X2 + ... + a1jXj + ... + a1nXn = b1a21X1 + a22X2 + ... + a2jXj + ... + a2nXn = b2..ai1X1 + ai2X2 + ... + aijXj + ... + ainXn = bi..am1X1 + am2X2 + ... + amjXj + ... + amnXn = bm

Condiciones de signo para variables:toda xj 0m = # total de restricciones,n = # de variables de decisin (originales)Cj, aij y bi son constantes (o parmetros) dados.

8Mtodos de Resolucin Mtodo GrficoEmpleado principalmente para PPL con dos variables de decisin. Este mtodo se basa en la idea de obtener regiones de soluciones factibles (RSF), en las cuales se encontrara la combinacin de variables de decisin que optimizan el modelo.

Mtodo Algebraico (SIMPLEX)Empleado principalmente para PPL con ms de dos variables de decisin. Este mtodo se desarrollo con base en el mtodo grfico y corresponde a un sistema heurstico, por lo cual requiere de una solucin inicial factible para empezar a funcionar.

8Mtodos de ResolucinGRAFICO Sujeto a:R1)R2)R3)

10Mtodo de Resolucin: Paso 1Grficar las restricciones1,0002,0003,0001,0002,0003,000X2ABC0,0X1R1R2

PROGRAMACIN LINEALConstruccin de modelosSolucin: FormulacinPaso 1: Identificar el objetivo (meta) a optimizarMinimizar el costo total de transporte (C).{u.m/mes}Paso 2: Identificar las variables de decisin que deseamos determinarXij.Cantidad a enviar de la planta i al almacn j mensualmente {uds/mes} i = 1,2,3 / j = 1,2,3,4Paso 3: Identificar las restricciones del modeloR1) Capacidad mensual de produccin planta 1 de 70R2) Capacidad mensual de produccin planta 2 de 90R3) Capacidad mensual de produccin planta 3 de 180R4) Requerimientos del almacn 1 para Marzo de 50R5) Requerimientos del almacn 2 para Marzo de 80R6) Requerimientos del almacn 3 para Marzo de 70R7) Requerimientos del almacn 4 para Marzo de 140R8) No Negatividad.

111,0002,0003,0001,0002,0003,000X2X1ABC0,0R1R2Mtodo de Resolucin: Paso 1Grficar las restricciones

111,0002,0003,0001,0002,0003,000X2X1ABC0,0R1R2Mtodo de Resolucin: Paso 2 Obtener la RSFRSF

111,0002,0003,0001,0002,0003,000X2X1ABC0,0Mtodo de Resolucin: RSFPremisa: el punto optimo siempre se encuentra en uno de los vrtices de la RSF.

13Mtodo de Resolucin: Paso3 Encontrar el Punto Optimo: AlternativasAlternativa 1Encontrar todas las combinaciones de X1 y X2 que determinan los vrtices de la RSF, luego se evalan en la funcin objetivo y se elige la combinacin que maximice (o minimice) dicha funcin.Alternativa 2Grficar la F.O. dandose en valor arbitrario de Z (depende de la escala del grfico), luego la recta se desplaza en forma paralela en el sentido estricto de la optimizacin. El ultimo punto que tope la F.O al salir de la RSF corresponder a la solucin optima.

131,0002,0003,0001,0002,0003,000X2X1ABC0,0Mtodo de Resolucin: Paso3 Encontrar el Punto Optimo(1)Z=320.000

141,0002,0003,0001,0002,0003,000X2X1ABC0,0Optimal PointMtodo de Resolucin: Paso 3 Encontrar el Punto Optimo (2)

151,0002,0003,0001,0002,0003,000X2X1ABC0,0El punto optimo (B) se encuentra en la interseccin de las dos rectasMtodo de Resolucin: Paso 3 Encontrar el Punto Optimo (3)

16RESULTADOSX1=715X2=571 Z =742,800.

8Mtodos de ResolucinALGEBRAICO SIMPLEXEl mtodo smplex fue desarrollado en 1947 por el Dr. George Dantzig y conjuntamente con el desarrollo de la computadora hizo posible la solucin de problemas grandes planteados con la tcnica matemtica de programacin lineal.El algoritmo denominado smplex es la parte medular de este mtodo; el cual se basa en la solucin de un sistema de ecuaciones lineales con el conocido procedimiento de Gauss-Jordan y apoyado con criterios para el cambio de la solucin bsica que se resuelve en forma iterativa hasta que la solucin obtenida converge a lo que se conoce como ptimo..El conjunto de soluciones factibles para un problema de P.L. es un conjunto convexo.La solucin ptima del problema de programacin lineal , si existe, es un punto extremo (vrtice) del conjunto de soluciones factibles. El nmero mximo de puntos extremos (vrtices) por revisar en la bsqueda de la solucin ptima del problema es finito.

8Mtodos de ResolucinALGEBRAICO SIMPLEXForma Estndar de un PPLLa forma estndar pasa por realizar los siguientes cambios:

1 Conversin de desigualdades en igualdades (ecuaciones)

a.- Restriccin menor o igual ()Para transformar este tipo de restriccin a una ecuacin de tipo igualdad se debe aumentar su lado izquierdo con una variable de holgura. Esta representa la cantidad disponible del recurso que excede al empleo que le dan las actividades.Ej.6X1 + 4X2 24F.e6X1 + 4X2 + h1 = 24 (h1 cantidad no utilizada de recurso)h1 0

8Mtodos de ResolucinALGEBRAICO SIMPLEXb.- Restriccin mayor o igual ()Las restricciones de este tipo comnmente determinan requerimientos mnimos de especificaciones. En este caso se debe incorporar una variable de supervit que representa el requerimiento mnimo del lado izquierdo, sobre el requerimiento mnimo del derecho ( cuanto falta para cumplir con lo pedido).Ej.X1 + X2 800X1 + X2 - r1 = 800 r1 0

Sin embargo la F.E pasa por hacer un ajuste ms:F.EX1 + X2 - r1 + t1 = 800r1, t1 0t1 = variable artificial (se necesita para generar la solucin inicial del simplex)

8Mtodos de ResolucinALGEBRAICO SIMPLEXd.- Restriccin de igualdad (=)Aqu la estandarizacin pasa slo por incorporar una variable artificial.Ej.X1 + X2 = 800X1 + X2 + t1 = 800 t1 0

Como las variables artificiales no tienen sentido, es importante que el simplex las deje fuera al comienzo del procedimiento y esto se logra al penalizar la inclusin de las variables artificiales en la funcin objetivo con un coeficiente M muy grande que para el caso de maximizar es M y para el caso de minimizar es + M.

8Mtodos de ResolucinALGEBRAICO SIMPLEX2 Cambios de variablesa.- Variables no restringidasAlgunas veces las variables de decisin pueden tomar cualquier valor real.Xi s.r.sCambio de variableXi = Ui ViUi . Parte positiva de XiVi . Parte negativa de XiEj.X1 + X2 24X1 0, X2 s.r.sLuego X2 = U2 V2F.E.X1 + U2 V2 + h1 = 24

8Mtodos de ResolucinALGEBRAICO SIMPLEXb.- Variables negativasAlgunas veces las variables de decisin pueden tomar negativos.Xi 0Cambio de variableYi = Xi Donde Yi 0Ej.X1 + X2 40X1 0, X2 0Luego Y2 = X2, o bien X2 = - Y2F.E.X1 - Y2 + h1 = 40

8Mtodos de ResolucinALGEBRAICO SIMPLEX3 Cambio en criterio de optimizacinMuchas veces el objetivo no es maximizar.MIN (Z) Cambio de variable: Z* = -ZMIN Z = MAX ( Z*)Ej.MIN [ Z = X1 + X2 ]Z* = -ZF.EMAX [ Z* = -X1 X2]

8Mtodos de ResolucinALGEBRAICO SIMPLEXEJEMPLOMIN (Z = 15X1 + 10X2 20X3) S/AR1) X1+2X2+4X3 30R2) 5X1+5X2+3X3= 40R3) X1 + X2 + X3 70R4) X1 s.r.s; X20; X30

Cambios de variable:

Z* = -ZX1=U1-V1X2=-Y2

8Mtodos de ResolucinALGEBRAICO SIMPLEXForma Estndar

Z*+15U1-15V1-10Y2-20X3+Mt1+Mt2=0U1-V1-2Y2+4X3-r1+t1=305U1-5V1-25Y2+3X3+t2=40U1-V1-Y2+X3+h1=70

8Mtodos de ResolucinALGEBRAICO SIMPLEXForma Tabular

BASEZU1V1Y2X3r1t1t2h1SOLUCIONz115-15-10-200MM00t101-1-24-110030t205-5-253001040h101-1-11000170

8Mtodos de ResolucinALGEBRAICO SIMPLEXForma Tabular Especial

BASEU1V1Y2X3r1t1t2h1SOLUCIONz15-15-10-2000000M000001100t11-1-24-110030t25-5-253001040h11-1-11000170

8Mtodos de ResolucinALGEBRAICOSe una vez obtenida la F.E se esta en condiciones de iniciar el Simplex que nos permitir encontrar la (s) solucin (es) del PPL.Como el algoritmo se mueve de punto en punto extremo requiere que variables basicas entren y salgan. Las reglas para seleccionar las variables de entrada y salida se conocen como condiciones de optimalidad y factibilidad. Resumiendo:

C. Optimalidad: la variable de entrada en un problema de maximizacin es la variable no bsica que tiene el coeficiente mas negativo en el reglon de la F.O. los empates se rompen arbritariamente. Se llega al optimo en la iteracin donde todos coeficientes del reglon de la F.O. de las variables bsicas son positivos.C. Factibilidad: tanto para los problemas de maximizacin como minimizacin, la variable de salida es la variable bsica asociada con la razn no negativa ms pequea entre los lados derecho y los coeficientes de la columna entrante.

8Mtodos de ResolucinALGEBRAICOPasos del Simplex:

Paso 0: determinar la solucin factible inicial.Paso 1: seleccione la variable de entrada empleando la condicin de optimalidad. Detngase si no hay variable de entrada.Paso 2: seleccione una variable de salida utilizando la condicin de factibilidad.Paso 3: determine las nuevas soluciones bsicas empleando los calculos apropiados de Gauss Jordan, luego vuelva al paso 1.

8Mtodos de ResolucinALGEBRAICOEJEMPLOMax Z = 7x1 + 4x2 + 5x3

S/A2x1 + x2 303x1 + 2x2 + x3 25 x2 + 2x3 20x1 , x2 , x3 0

8Mtodos de ResolucinALGEBRAICO SIMPLEXForma Tabular Especial

BASEX1X2X3h1h2h3SOLUCIONz-7-4-50000h121010030h232101025h301200120

8Mtodos de ResolucinALGEBRAICO SIMPLEXForma Tabular Especial

BASEX1X2X3h1h2h3SOLUCIONz-7-4-50000h121010030h232101025h301200120

8Mtodos de ResolucinALGEBRAICO SIMPLEXForma Tabular Especial

BASEX1X2X3h1h2h3SOLUCIONz-7-4-50000Raznh12101003030 / 2h23210102525 / 3h301200120___

8Mtodos de ResolucinALGEBRAICO SIMPLEXForma Tabular Especial

BASEX1X2X3h1h2h3SOLUCIONz-7-4-50000Raznh12101003030 / 2h23210102525 / 3h301200120___

8Mtodos de ResolucinALGEBRAICO SIMPLEXForma Tabular Especial

BASEX1X2X3h1h2h3SOLUCIONz-7-4-50000Raznh12101003030 / 2h23210102525 / 3h301200120___

8Mtodos de ResolucinALGEBRAICO SIMPLEXForma Tabular EspecialPIVOTE

BASEX1X2X3h1h2h3SOLUCIONz-7-4-50000Raznh12101003030 / 2h23210102525 / 3h301200120___

8Mtodos de ResolucinALGEBRAICO SIMPLEXGauss JordanOptimo!

BASEX1X2X3h1h2h3SOLUCIONz02007/34/385h10001-2/31/320X111/2001/3-1/65h301/21001/210

8Mtodos de ResolucinALGEBRAICO SIMPLEXSOLUCIN

z85X15X20X30h120h20h310

8Mtodos de ResolucinDUAL SIMPLEXSe basa en la idea que todo PPL tiene un problema espejo, llamado DUAL. Esto provoca que se genere un segundo algoritmo de resolucion conocido como Metodo Dual Simplex, el cual funciona de la siguiente manera:Condicion de Factibilidad:La variable que sale es la variable basica que tiene el valor mas negativo, si todas las variables basicas son no negativas el proceso termina y se alcanza la solucion factible - optima.Condicion de Optimalidad:La variable entrante se escoge de la manera siguiente:Calcule la razon entre los coeficientes del reglon cero y los coeficientes de la fila asociada a la variable que sale, ignore coeficientes positivos o ceros. La variable que entra es la que posee la razon mas pequea si el problema es de minimizacion. Si todos los denominadores son cero o positivos el problema no tiene solucion factible.

8EJEMPLOMIN (Z = 2X1 + X2) S/AR1) 3X1+X2 3R2) 4X1+3X2 6R3) X1 + 2X2 3R4) X1 0 ; X2 0

Forma Estndar:

Mtodos de Resolucin DUAL SIMPLEX

8Forma EstndarMtodos de ResolucinDUAL SIMPLEX

Z+-2X1-X2=0-3X1-X2+r1=-3-4X1-3X2+r2=-6X1+2X2+h1=3

8Forma Tabular EspecialMtodos de ResolucinDUAL SIMPLEX

BASEX1X2r1r2h1SOLUCIONz-2-10000r1-3-1100-3r2-4-3010-6h1120013

8Sale mas negativaMtodos de ResolucinDUAL SIMPLEX

BASEX1X2r1r2h1SOLUCIONz-2-10000r1-3-1100-3r2-4-3010-6h1120013

8Mtodos de ResolucinDUAL SIMPLEX

RAZON2/41/3000BASEX1X2r1r2h1SOLUCIONz-2-10000r1-3-1100-3r2-4-3010-6h1120013

8Entra razon mas pequeaMtodos de ResolucinDUAL SIMPLEX

RAZON2/41/3000BASEX1X2r1r2h1SOLUCIONz-2-10000r1-3-1100-3r2-4-3010-6h1120013

8Entra razon mas pequeaMtodos de ResolucinDUAL SIMPLEX

RAZON2/41/3000BASEX1X2r1r2h1SOLUCIONz-2-10000r1-3-1100-3r2-4-3010-6h1120013

8Gauss JordanMtodos de ResolucinDUAL SIMPLEX

BASEX1X2r1r2h1SOLUCIONz-2/300-1/302r1-5/301-1/30-1X24/310-1/302h1-5/3002/31-1

8Mtodos de ResolucinDUAL SIMPLEX

BASEX1X2r1r2h1SOLUCIONz-2/300-1/302r1-5/301-1/30-1X24/310-1/302h1-5/3002/31-1

8Mtodos de ResolucinDUAL SIMPLEX

RAZON2/50010BASEX1X2r1r2h1SOLUCIONz-2/300-1/302r1-5/301-1/30-1X24/310-1/302h1-5/3002/31-1

8PivoteMtodos de ResolucinDUAL SIMPLEX

RAZON2/50010BASEX1X2r1r2h1SOLUCIONz-2/300-1/302r1-5/301-1/30-1X24/310-1/302h1-5/3002/31-1

8Gauss JordanOptimo Factible!!!Mtodos de ResolucinDUAL SIMPLEX

BASEX1X2R1r2h1SOLUCIONZ00-2/5-1/5012/5X111-3/51/503/5X2004/5-3/506/5h100-1110

8Solucin:Mtodos de ResolucinDUAL SIMPLEX

BASESOLUCIONZ12/5X13/5X26/5r10r20h10

8Ejercicio PropuestoMIN (Z = 5X1 + 4X2 + 8X3) S/AR1) X1+2X2+X3 15R2) 2X1+X2+X3 10R3) X1 + X2 +X3 20R4) X1 0 ; X2 0; X3 0

Mtodos de ResolucinDUAL SIMPLEX

*8*8*8*10*11*11*11*13*13*14*15*16*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8