B - IIT - Universidad Pontificia Comillas
Contents
1. Oferta en el origen Ci Coste unitario de transporte del origen al destino j w PO Se supone que la oferta es igual a la demanda Xa gt b COMILLAS A muaa ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 23 Problema del transporte Formulaci n Q Variables de decisi n Xj Unidades transportadas desde el origen al destino j UNIVERSIDAD a PONTIF 0 ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 24 Problema del transporte Propiedades Y Si Ya gt b se a ade un sumidero universal con coste nulo i l j l v Si gt a lt gt b se a ade una fuente universal con coste elevado i j l v La matriz de restricciones es totalmente unimodular todos los determinantes de las submatrices valen 0 1 1 v Por lo tanto si los coeficientes de oferta a y demanda b son enteros la soluci n ptima es un vector entero gt T E Z Yi J UNIVERSIDAD PONTIFICIA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 25 Problema del transbordo Definici n Q Transportar un producto en una red satisfaciendo la demanda con el m nimo coste posible b Cantidad de producto disponible en el nodo i v oferta b gt 0 v demanda b lt 0 v transbordo b 0 C Coste unita2. a una disyunci n D v Se procede de forma an loga para bloques de ecuaciones ICAI COMILLAS LA a o ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 43 Selecci n entre varios valores Q La funci n fha de tomar uno de los valores de la siguiente lista 2 a T a E d y Q La formulaci n ser a N Fx TA gt d r i 1 Sa i i l PONTI FICLA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 44 restricciones 1 gt gt ax lt b j Y az lt b M 6 j am Eb gt 0 gt 1 a ji J 6 1 gt ax gt b j D gt b4 Ee m e 2 gt b m 1 6 0021 A jj J D lt b e M e 6 d 1 ax b a jj J 2 lt b M 1 6 205 gt b m 1 20 0 l PO UNIVERSIDAD NTIF ICI ICAI ICADE Donde m lt gt aT b lt M y E gt 0 ez0 COMILLAS OR ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL 205 gt b e m e j 205 lt b e M e 5 lt 1 Implicaciones entre variables binarias y Modelado en optimizaci n 45 Implicaciones Q La implicaci n f x lt 0 g x lt 0 se puede descomponer como f 1 lt 0 gt 6 1 y 6 1 g x lt 0 y aplicar las relaciones de la transparencia anterior Q La doble implicaci n f x lt 0 lt g x l
3. b e R a Ly TQ Ly Ta Ta aty by x gt 0 n t Jedorde vector de T vardabes c coeficientes a c de coste m b A Ain l 1 vector de Al matriz de b i i o demandas A restricciones b pidii ICAI Hipa E ml mn m COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 15 Modelos generales de optimizaci n Programaci n entera IP minc z d y z Z ye R ce R deRr A E RP B R b E R v Si l 0 Programaci n entera pura PIP Y Si l gt 0 Programaci n entera mixta MIP VERSIDAD PONTI FIG ICAI ICADE COMILLAS RAM E ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 16 Modelos generales de optimizaci n Programaci n binaria BIP E 0 1 c c R A c R ber IDAD p Eo CoO re ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 17 Programaci n cuadr tica QP TER CER ACR Q R b pR IDAD C En Pe ma ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelos generales de optimizaci n Modelado en optimizaci n 18 Modelos generales de optimizaci n Programaci n no lineal NLP IDAD p Eo CoO re ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUST
4. il 0 en otro caso QU Formulaci n De cada ciudad se sale una vez A cada ciudad se llega una vez a di us En cada etapa se a a I hs Lo recorre un tramo En cada etapa se Je gt ad Vj k OR sale de la ciudad a aP que se ha llegado en la etapa anterior T E 0 1 Yi jk 1 n NIVERSIDAD PONTI Er FICLA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 37 Modelado con variables binarias Q Conversi n de entera a binarias Q Disyunciones Q Disyunciones por bloques UU Cumplimiento de un n mero de ecuaciones Q Selecci n entre varios valores Q Implicaciones entre variables binarias y restricciones Q Implicaciones Q Relaciones sencillas entre variables binarias U Productos PONTI FICLA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 38 Conversi n de entera a binarias Q Se quiere descomponer la variable entera x en variables binarias y Yo v Se busca una cota superior u O0 lt rt lt u v Se determina N tal que P Lyg v La descomposici n es N s z gt 9_ 2y 1 0 v Se ha de sustituir en el modelo x por dicha expresi n a adiendo a y 0 1 Yi ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 39 Ta
5. CAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 3 Modelo Q Representaci n simplificada de la realidad generalmente de forma matem tica que facilita su comprensi n y el estudio de su comportamiento Q Un buen modelo debe mantener un equilibrio entre sencillez y capacidad de representaci n Q Se requiere una interacci n constante entre el modelador creador del modelo y el experto conocedor del problema real Q Es a la vez una ciencia y un arte PONTI FICLA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 4 Etapas en el desarrollo de un modelo Identificaci n del problema Especificaci n matem tica y formulaci n Resoluci n Verificaci n validaci n y refinamiento Interpretaci n y an lisis de resultados Implantaci n documentaci n y mantenimiento DODOOO O Q El tiempo empleado en realizar correctamente una etapa facilitar de forma notable las etapas sucesivas PONTI FICLA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 5 Identificaci n del problema U Recolecci n de informaci n relevante Q Planteamiento general del problema v Qu se quiere optimizar v De qu alternativas se dispone v Qu limitaciones se tienen A Interpretac
6. E ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 33 Problema de la partici n A An logo al problema del empaquetado pero seleccionando exactamente una vez cada elemento Cada elemento seleccionado una vez PONTI FICLA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 34 Recubrimiento partici n empaquetado RECUBRIMIENTO PARTICI N EMPAQUETADO CA S RAM E ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 35 Problema del viajante Formulaci n 1 Q Realizar un circuito que pase por n ciudades sin repetir ninguna volviendo a la ciudad de partida de manera que la distancia o tiempo o coste total sea m nima C Distancia de la ciudad a la ciudad j 1 si se va de la ciudad 1 a la ciudad 7 Variables en otro caso Formulaci n A cada ciudad se L llega una vez p Na 1 Blan De cada ciudad se gt Na 1 Vi 1 n j sale una vez i 2 z TE lt C No se permiten ty 2 lt card U 1 VU C 1 1nj 2 lt card U lt n 2 OMIC subciclos z 0 1 TTEA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 36 Problema del viajante Formulaci n 2 1 si se va de la ciudad 2 a la ciudad 3 en la etapa k del circuito Q Variables z A
7. F Seattle 1 1 1 1 LA Chicago 2 2 3 2 3 LA SF 2 3 9 9 Chicago Denver 313 4 Chicago Seattle 313 31 13 4 Denver SF 2 4 4 5 Denver Chicago 2 2 2 Seattle SF 2 4 4 5 EE Seattle LA 2 2 414 2 Pa io Coste M6 2134 6 757 899 8 9 COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 31 Problema del recubrimiento Ejemplo l 1 si se asigna la secuencia j Q Variables g O en cualquier otro caso Q Formulaci n mny tarn tA CU e Fot T a FS ur FIt etr FIT z g r 221 SF LA A A aL SF Denver T 2 2 0 21 SF Seattle 12 LT 3 Dispone de tres tripulaciones j 1 PENE e O UNIvERSID ONTIFICI ICAI ICADE EA gt 1 ComiLLAS ESCUELA T CNICA SUPERIOR DE INGENIER A 1 a 12 DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 32 Problema del empaquetado Q Se dispone de un conjunto de m elementos y una colecci n de n subconjuntos A Se desea elegir los subconjuntos que den el m ximo beneficio total sin que ning n elemento aparezca m s de una vez c gt Beneficio del subconjunto j a gt Indica si el elemento pertenece al subconjunto j 1 s O no Q Variables x f si se elige el subconjunto j X 0 si no U Formulaci n Cada elemento seleccionado como mmm mucho una vez PONTIF Cla ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO D
8. PARTAMENTO DE ORGANIZACI N INDUSTRIAL y20 y lt M y lt z y gt 1 M6 M donde z lt M Modelado en optimizaci n 54 Modelado de funciones objetivo no lineales Q Problemas con coste fijo fixed charge Q Problemas con costes variables por tramos Q Funci n objetivo minimax o maximin PONTI FICLA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 55 Problemas con coste fijo Q Cada variable x lleva asociado un coste fijo k y un coste unitario Cj 0 r 0 LaS D A e 0 I v Se introduce una variable binaria y por cada x que cumpla B 1 T gt 0 I 0 T 0 v Para ello se a aden restricciones de la forma y x lt M y y 0 1 x gt 0 M grande J v La funci n objetivo queda n n min gt f x k UE 2 FONA 1 93 j 1 j 1 COMILLAS FICIA ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 56 Problemas con costes variables por tramos A La variable x lleva asociados costes c cf cM en los tramos p p p p pY pY Y Se introducen N variables continuas y N variables binarias de la siguiente forma T sia pp A l sizx gt 0 T 0 si no 0 12 0 v En la funci n objetivo se introduce el sumando N CT o g k 1 Y Se a aden las restricciones N a Ds k 1 p pej l
9. RIAL Modelado en optimizaci n 19 Modelos generales de optimizaci n Programaci n multiobjetivo s T x E R c e R A e R b eR f x R R VERSIDAD COMILLAS LA a o ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 20 Modelos generales de optimizaci n Especiales Optimizaci n no lineal sin Ea Hz restricciones f R R Ajuste no lineal m nimo cuadr tico F x 0 Problema mixto complementario MCP TER F R R PONTI FICLA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 21 Modelos especificos de programaci n lineal entera Q Problema del transporte Q Problema del transbordo U Problema de asignaci n Q Problema de la mochila knapsack Q Problema del recubrimiento set covering Q Problema del empaquetado set packing Q Problema de la partici n set partitioning Q Problema del viajante TSP SIDAD COMILLAS LA a o ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 22 Problema del transporte Definici n Q Minimizar el coste total de transporte de un producto desde los or genes a los destinos satisfaciendo la demanda de cada destino sin superar la oferta disponible en cada origen b D a 2 Demanda en el destino j
10. a Y ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n Jos Mar a Ferrer Caja Universidad Pontificia Comillas Optimizaci n Q Encontrar el valor que deben tomar las variables del problema para hacer ptima la funci n objetivo y de forma que se satisfagan las restricciones PONTI FICLA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 1 Componentes de un problema de optimizaci n Q Funci n objetivo v Medida cuantitativa del funcionamiento del sistema que se desea optimizar maximizar o minimizar O Variables v Representan las decisiones que se pueden adoptar y de las que depende el valor de la funci n objetivo v Variables de control y de estado Q Restricciones v Relaciones que las variables deben satisfacer v Igualdades y desigualdades PONTI FICLA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 2 Clasificaci n de modelos Q Funci n objetivo v Lineal cuadr tica no lineal no diferenciable multiobjetivo estoc stica sin funci n objetivo OU Restricciones v Sin restricciones lineales no lineales no diferenciables acotadas disyuntivas probabil sticas O Variables Y Continuas enteras binarias UNIVERSIDAD a PONTIE1 0 I
11. bla de equivalencias l gicas RSIDAD ICAI ICADE ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 40 COMILLAS LA a o Disyunciones g x lt 0 se modela mediante lt MS g 1 lt MU Y Mes suficientemente grande Lo ideal es que la M de cada restricci n sea la cota m s ajustada para cada restricci n v La implicaci n f x gt 0 g x lt 0 es equivalente a fF1 lt 0 gz lt 0 O fa lt o fo 0 1 JU Ejemplo 34 2y 2 lt 3 gt x 4y 22 gt 1 gt 3I 2y4 2 3 gt 0 gt x 4y 2 1 lt 0 gt 32 2y 2 3 lt 06 r 4y 2 1 lt 0 gt VERSIDAD PONTIE IC 3T 2 z 3 lt M ICA ICADE y d 0 1 COMILLAS a 4y 2 1 lt M 1 mas ESCUELA T CNICA SUPERIOR DE INGENIER A Modelado en optimizaci n 41 DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Disyunciones por bloques f x lt 0 g x lt 0 o j6 lt 0 6 lg x lt 0 se modela mediante f x lt 0 aa 0 f x lt M6 f z lt M6 lt MaA 8 E 10 1 g x lt MU v Este m todo es apropiado para regiones factibles no convexas p O ICADE o ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 42 Cumplimiento de un n mero de ecuaciones Q Se deben cumplir al menos k de las N ecuaciones A A o Ed 0 Q La formulaci n ser a CA lt Mo N T do 2 Dil MO v Elcaso N 2 k 1 equivale
12. e las formulaciones En O ICADE K M VJ COMILLAS ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 49 Ejemplo de baloncesto Planteamiento Q Un entrenador de baloncesto tiene 9 jugadores a los que ha evaluado de 1 a 3 de acuerdo con su manejo de pelota tiro rebote y defensa seg n se indica en la tabla adjunta Rebote o Be e tro Be A a VERSIDAD PONTE uN ICAI ICADE aa ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 50 Ejemplo de baloncesto Planteamiento Q El equipo titular de 5 jugadores debe tener la m xima capacidad defensiva y satisfacer las siguientes condiciones v Al menos dos jugadores deben estar en disposici n de actuar de p vot dos de alero y uno de base v Su nivel medio en el manejo de pelota en tiro y en rebote debe ser por lo menos 2 v Si juega el jugador 3 entonces el jugador 6 no puede jugar v Si juega el jugador 1 tambi n deber jugar el 4 el 5 pero no los dos a la vez Y El jugador 8 el 9 pero no los dos a la vez deben jugar Q Formular un programa lineal que facilite la selecci n del equipo UNIVERSIDAD PON TIFICIA t t u a r C ICAI LAS ma ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 51 Ejemplo de baloncesto Formulaci n Q Variables i 1 si se incluye el
13. ecesidades Y En la definici n v En la formulaci n Y En la implementaci n PONTI FICLA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 9 Interpretaci n y an lisis de resultados Q An lisis de sensibilidad de la soluci n obtenida frente a cambios en los par metros Detecci n de soluciones robustas PONTI FICLA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 10 Implantaci n documentaci n y mantenimiento Q Documentaci n clara precisa y completa Q El c digo debe estar escrito de forma ordenada y debe incluir comentarios que faciliten las operaciones de mantenimiento Q Elaboraci n de un manual de usuario con especificaciones matem ticas e inform ticas UY Formaci n de usuarios PONTI FICLA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 11 Ejemplo de la dieta Planteamiento O La alimentaci n diaria de una ternera debe contener al menos v 700 g de prote nas v 28 g de calcio v 150 mg de vitaminas U Se dispone de pienso y forraje con coste por kg de 30 y 35 c ntimos de euro Q La composici n nutritiva por kg de alimento es Prote nas g Calcio g Vitaminas mg Pienso Forraje 45 1 5 Q Se trata de dete
14. i n y traducci n a t rminos precisos de los datos y elementos del problema Q Fase fundamental para que las futuras decisiones sean tiles PONTI FICLA ICAI ICADE ma ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 6 Especificaci n matem tica y formulaci n Q Definici n en t rminos matem ticos adecuados de los elementos del problema v Funci n objetivo v Variables v Restricciones v Par metros AU Identificaci n del tipo s de modelo general que se puede aplicar Q Formulaci n clara y elegante Q An lisis del tama o y estructura del problema formulado PONTI FICLA C ICAI LAS ma ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 7 Resoluci n U Elecci n del tipo de m todo de soluci n y de algoritmos adecuados Q Implementaci n en un lenguaje inform tico adecuado de los algoritmos elegidos Q Obtenci n de la soluci n ptima o de soluciones suficientemente satisfactorias Q Eltiempo de resoluci n depender de la formulaci n propuesta PONTI FICLA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 8 Verificaci n validaci n y refinamiento Ud Comprobaci n de coherencia con la realidad Q Detecci n y correcci n de errores de codificaci n Q Mejora y ampliaci n por nuevas n
15. jugador j en el equipo 1 si se incluye el jugador j en posici n k 4 J 0 en otro caso Jk 0 en otro caso j 3 4 5 6 7 1 J 1 9 k p a b s lo los necesarios Q Funci n objetivo maxon PA Fa ta A E F a ot Q Restricciones Li T T T T T tT T I 5 mm 5 jugadores en el equipo Cr NL MN e Al menos 2 p vots La H Lao F Ts Tea E Y gt 2 Al menos 2 aleros DADA Al menos 1 base UNIVERSIDAD a PONTIE1 0 ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 52 Ejemplo de baloncesto Formulaci n 27 32 22 2 2 3 32 22 32 210 T ar ten ton Forn E t2 E A gt 10 JEFE taa He 20 20 38 ta 10 4 Nivel medio al menos 2 en manejo tiro y rebote T lt 1 mm Equivalea r 1 gt x 0 per TA Equivalen a r 1 gt x 2 1 z r 1 lt Deben jugar 8 9 pero no ambos Tay F Ty Tg 0 TFT T7 50 T FT T50 E Lg TTo T 0 Ey HT 2 1 0 Coherencia entre puestos para los jugadores polivalentes VERSIDAD PONTI EI C ICAI T Uh E fo 1 VJ k pacos ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 53 Productos 0 0 Reemplazar 0 0 por 0 6 10 1 1590 1y0 1 Reemplazar I por Y o U gt 4 0 2 UNIVERSIDAD a PONTIE1 0 ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DE
16. rio de transporte del nodo al nodo j Se supone que la oferta es igual a la demanda Xb 0 i l PONTI FICLA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 26 Problema del transbordo Formulaci n Q Variables de decisi n Xj Unidades transportadas desde el nodo al nodo j conservaci n del flujo v Matriz totalmente unimodular b E Z Vi gt o E Z Vi J v El problema del transbordo generaliza al problema del transporte UNIVERSIDAD a PONTIF 0 C ICAI LAS puras ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 27 Problema de asignaci n Q Asignar n tareas a n m quinas de forma que el coste total sea m nimo C Coste de asignar la tarea a la m quina j sise asigna la tarea i a la m quina j O Variables x i g 0 si no U Formulaci n Cada tarea ha de ser realizada por una a S m quina Cada m quina ha de realizar una tarea v Caso particular del problema del transporte AD PO UNIvERSID NTIFIC1A ca E cora Y La restricci n 2 e 0 1 puede sustituirse por 7 20 COMILLAS MEDIA ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 28 Problema de la mochila Q Elegir objetos de los n disponibles de forma que el valor total sea m ximo sin sobrepasar el vol
17. rminar la cantidad diaria de cada alimento para minimizar el coste total de la alimentaci n PONTE ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 12 Ejemplo de la dieta Formulaci n gen rica A ndices i tipo de alimento pienso y forraje j tipo de nutriente prote nas calcio y vitaminas O Par metros b cantidad m nima diaria requerida del nutriente j a gt cantidad de nutriente j por kg de alimento c gt coste por kg del alimento OU Variables X cantidad diaria de alimento por ternera A Funci n objetivo Mn _ cz O Restricciones o De satisfacci n de la cantidad de nutrientes Do gt b VJ De no negatividad x gt 0 Vi i UNIVERSIDAD a PONTIFIC a ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 13 Ejemplo de la dieta Formulaci n num rica min 30 392 Ti T2 30x 45x gt 700 prote nas 2x1 1 gt 28 calcio 10x 5x gt 150 vitaminas 2 206 Ty 20 RSIDAD ICAI ICADE COMILLAS LA a o ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 14 Modelos generales de optimizaci n Programaci n lineal LP m Z cxr 0C72 gt C 1 1 2 2 n n T minc T sa Ax b di Fa aTa x R c R A R
18. t 0 se puede descomponer como f 1 lt 0S6 1 y 6 1 lt 3 g 1 lt 0 y aplicar las relaciones de la transparencia anterior RSIDAD ICAI ICADE COMILLAS LA a o ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 46 Relaciones sencillas entre variables binarias 6 1 gt 6 16 6 6 1 6 gt 26 k 1 v Sienvezde 1 se tiene 0 en la expresi n equivalente se sustituye por 1 6 UNIVERSIDAD a PONTIF 0 ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 47 Ejemplo de fabricaci n Formulaci n 1 Q Si se fabrica alguno de los productos A o B entonces debe fabricarse tambi n al menos uno de los productos C DoE je A B C D E 1 sise fabrica el producto j i Jo si no 166 1 gt 6 166 166 1 0 1 gt 06 160 160 1 g E a 04 0 00 20 pd up quie a qu RSIDAD ICAI ICADE ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 48 COMILLAS LA a o Ejemplo de fabricaci n Formulaci n 2 6 1685 1 gt 6 166 166 1 y 6 46 gt 1 gt 8 6 6 gt 1 6 6 gt 1 gt 6 1 6 1 gt 8 6 0 gt 1 26 gt 6 0 6 0 6 gt 6 v Hay que a adir las restricciones 0 1 a las variables binarias Y Si xes la cantidad de producto j que se fabrica habr a que a adir en cualquiera d
19. t r lt p Vk 1 N 6t e 0 1 Vk 1 N k 1 M ES 1 PONTI FICLA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE NGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 57 Funci n objetivo minimax o maximin min f x Ar b f z maxlclz d c32 d C18 d siendo P r gt o0 CCC R ASA E R x R A R b e R Q El problema se puede reformular como AD PO yNIvERSID NTIF ICI ca UY o v An logo para funci n objetivo maximin COMILLAS MAA ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 58
20. umen disponible c gt Volumen que ocupa el objeto j v gt Valor del objeto j b Volumen total disponible l si li l objeto j a Variables a 4 si se elige el objeto j 0 si no U Formulaci n PONTI FIG r ICAI ICADE ma ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 29 Problema del recubrimiento Q Se dispone de un conjunto de m elementos y una colecci n de n subconjuntos Q Se desea elegir subconjuntos que cubran todos los elementos al menos una vez y con el m nimo coste c gt Coste del subconjunto j gt Indica si el elemento pertenece al subconjunto j 1 s O no si se elige el subconjunto j si no O Variables s U Formulaci n Cada elemento menos una vez IFICIA ICAI ICADE COMILLAS ESCUELA T CNICA SUPERIOR DE INGENIER A DEPARTAMENTO DE ORGANIZACI N INDUSTRIAL Modelado en optimizaci n 30 Problema del recubrimiento Ejemplo Q Una compa a a rea con base en San Francisco quiere cubrir todos sus vuelos asignando tres tripulaciones a algunas de las 12 secuencias factibles de vuelos que se indican en la siguiente tabla Q El objetivo es minimizar el coste de la asignaci n Los costes de las diferentes secuencias aparecen en la ltima fila Secuencias factibles IA AA ES ES ISA LOA TO 12 SF LA 1 1 1 1 SF Denver 1 1 1 1 S
Download Pdf Manuals
Related Search