Construção de modelos de programação linear e inteira : transparências de apoio à leccionação de aulas teóricas

Slide 1 Constru¸c˜ao de Modelos de Programa¸c˜ao Linear e Inteira Transparˆencias de apoio `a lecciona¸c˜ao de aulas te´oricas Vers˜ao 2 c °2000, 1998 Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Constru¸c˜ao de Modelos de Programa¸c˜ao Linear e Inteira 1 Slide 2 Modeliza¸c˜ao Os 10 princ´ıpios •N˜ao criar um modelo complicado quando um simples ´e suficiente. •N˜ao moldar o problema `a t´ecnica de resolu¸c˜ao que se pretende utilizar. •Resolver rigorosamente o modelo encontrado. S´o assim se saber´a se hipot´eticas inconsistˆencias das solu¸c˜oes do modelo com a realidade tˆem origem no pr´oprio modelo ou n˜ao. •Validar os modelos antes de os implementar. •O modelo n˜ao deve ser tomado literalmente pois nunca ´e a realidade. •O modelo n˜ao deve ser for¸cado a fazer, ou ser criticado por n˜ao fazer, aquilo para que n˜ao foi criado. •N˜ao sobrestimar os modelos. •Uma das principais vantagens da modeliza¸c˜ao ´e o processo de desenvolvimento do modelo. •Um modelo n˜ao pode ser melhor do que a informa¸c˜ao usada na sua constru¸c˜ao. •Os modelos nunca substituem os agentes de decis˜ao. Slide 3 Formula¸c˜ao de modelos matem´aticos em Investiga¸c˜ao Operacional Algoritmo para construir um modelo matem´atico para um problema de Investiga¸c˜ao Operacional: Passo I — Determinar, no problema concreto, aquilo que ´e fixo e n˜ao pode ser alterado e aquilo que se pode decidir (vari´aveis de decis˜ao). Representar essas vari´aveis de uma forma alg´ebrica. Passo II — Identificar as restri¸c˜oes do problema, isto ´e, aquilo que limita as nossas decis˜oes, e represent´a-las como igualdades ou desigualdades que sejam fun¸c˜oes das vari´aveis de decis˜ao. Passo III — Identificar o(s) objectivo(s) do problema e represent´a-lo(s) como uma fun¸c˜ao das vari´aveis de decis˜ao, que deve ser minimizada ou maximizada. Nota: S´o existe problema quando h´a mais do que uma solu¸c˜ao admiss´ıvel. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Constru¸c˜ao de Modelos de Programa¸c˜ao Linear e Inteira 2 Slide 4 Problema de Mistura de Produtos A companhia Electro & Dom´esticos pretende escalonar a produ¸c˜ao de um novo apetrecho de cozinha que requer dois recursos: m˜ao-de-obra e mat´eria-prima. A companhia considera a hip´otese de 3 modelos diferentes, tendo o seu departamento de engenharia fornecido os seguintes dados: Modelo A B C M˜ao-de-obra (horas por unidade) 7 3 6 Mat´eria-prima (quilos por unidade) 4 4 5 Lucro ($ por unidade) 4 2 3 O fornecimento de mat´eria-prima est´a limitado a 200 quilos/dia. Por dia est˜ao dispon´ıveis 150 horas de trabalho. O objectivo ´e maximizar o lucro total. Formule o modelo que permitiria resolver este problema. Slide 5 Problema de Mistura de Produtos Resolu¸c˜ao Passo I — O que se desconhece, e que se pretende determinar na fase de resolu¸c˜ao do modelo, s˜ao as quantidades a produzir diariamente de cada um dos modelos — as vari´aveis de decis˜ao. Representando-as algebricamente: xA−produ¸c˜ao di´aria do modelo A (node unidades) xB−produ¸c˜ao di´aria do modelo B (node unidades) xC−produ¸c˜ao di´aria do modelo A (node unidades) Passo II — Restri¸c˜oes do problema. N˜ao podemos produzir quantidades infinitas de A, B e C (o que daria um lucro infinito) porque estamos limitados pela mat´eria-prima (200) e m˜ao-de-obra (150) dispon´ıveis, valores que n˜ao podemos exceder. Ent˜ao, a m˜ao-de-obra necess´aria para produzir uma unidade do modelo A (7 horas), vezes o n´umero de unidades do modelo A a produzir (xA), Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Constru¸c˜ao de Modelos de Programa¸c˜ao Linear e Inteira 3 Slide 6 mais a m˜ao-de-obra necess´aria para produzir uma unidade do modelo B (3 horas), vezes o n´umero de unidades do modelo B que se resolva produzir (xB), mais a m˜ao-de-obra necess´aria para produzir uma unidade do modelo C (6 horas), vezes o n´umero de unidades do modelo C que se venha a produzir (xC), n˜ao poder˜ao exceder as 150 horas, isto ´e: 7xA+ 3xB+ 6xC≤150 Aplicando o mesmo racioc´ınio `a mat´eria-prima, obter-se-ia: 4xA+ 4xB+ 5xC≤200 As restri¸c˜oes que faltam ao problema dizem directamente respeito `as vari´aveis de decis˜ao, e s˜ao: xA≥0, xB≥0, xc≥0 ou seja, n˜ao se podem produzir quantidades negativas. Passo III — O objectivo do problema ´e maximizar o lucro total, isto ´e, o lucro obtido com os 3 modelos. Como cada unidade do modelo A d´a um Slide 7 lucro de 4, do modelo B d´a 2 e do modelo C d´a 3, a fun¸c˜ao objectivo ser´a: max LUCRO = 4xA+ 2xB+ 3xC O modelo do nosso problema ser´a ent˜ao: Encontrar os n´umeros xA,xBexCtais que: max LUCRO = 4xA+ 2xB+ 3xC sujeito a: 7xA+ 3xB+ 6xC≤150 4xA+ 4xB+ 5xC≤200 xA, xB, xC≥0 Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Constru¸c˜ao de Modelos de Programa¸c˜ao Linear e Inteira 4 Slide 8 Problema da refinaria de petr´oleo Uma refinaria de petr´oleo pode misturar 3 tipos de crude para produzir gasolina normal e super. Existem dispon´ıveis duas unidades de mistura. Para cada ciclo de produ¸c˜ao a unidade mais antiga usa 5 barris de crude A, 7 barris de crude B e 2 barris de crude C para produzir 9 tanques de gasolina normal e 7 de gasolina super. A unidade de mistura mais recente usa 3 barris de crude A, 9 de B e 4 de C para produzir, num ciclo de produ¸c˜ao, 5 tanques de gasolina normal e 9 de super. Devido a contratos j´a assinados, a refinaria tem que produzir, pelo menos, 500 tanques de normal e 300 tanques de super. Existem dispon´ıveis 1500 barris de crude A, 1900 de crude B e 1000 de crude C. Por cada tanque de gasolina normal produzida a refinaria ganha 6 unidades monet´arias e, por tanque de super, 9 unidades monet´arias. O problema ´e saber como utilizar as reservas de crude e as duas unidades de mistura, de forma a, respeitando os compromissos assumidos, maximizar o lucro da refinaria. Slide 9 Problema da refinaria de petr´oleo Resolu¸c˜ao Vari´aveis de decis˜ao x1−node ciclos de produ¸c˜ao a realizar na unidade antiga x2−node ciclos de produ¸c˜ao a realizar na unidade nova Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Constru¸c˜ao de Modelos de Programa¸c˜ao Linear e Inteira 5 Slide 10 Restri¸c˜oes Crude dispon´ıvel: Tipo A: 5x1 |{z} gasto na unidade antiga + 3x2 |{z} gasto na unidade nova ≤1500 Tipo B: 7x1+ 9x2≤1900 Tipo C: 2x1+ 4x2≤1000 Contratos assinados: Gasolina normal: 9x1 |{z} produzido na unidade antiga + 5x2 |{z} produzido na unidade nova ≥500 Gasolina super: 7x1+ 9x2≥300 Slide 11 E ainda: x1, x2≥0 Fun¸c˜ao objectivo max LUCRO = gasolina normal z}| { 6×( 9 |{z} node tanques por ciclo x1 |{z} node ciclos | {z } unidade antiga + 5x2 |{z} unidade nova ) + gasolina super z }| { 9×(7x1+ 9x2) Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Constru¸c˜ao de Modelos de Programa¸c˜ao Linear e Inteira 6 Slide 12 Arrendamento de espa¸co num armaz´em Uma empresa planeia arrendar espa¸co num armaz´em, sendo as suas necessidades para os pr´oximos 5 meses as seguintes: Mˆes Necessidade de espa¸co (m2) 1 1500 2 1000 3 2000 4 500 5 2500 Per´ıodo de arrendamento Custo por m2 (meses) ($) 1 2800 2 4500 3 6000 4 7300 5 8400 Construa um modelo que permita determinar o esquema de contratos a assinar, por forma a satisfazer as necessidades de espa¸co o mais economicamente poss´ıvel. Slide 13 Arrendamento de espa¸co num armaz´em Resolu¸c˜ao Vari´aveis de decis˜ao xij −espa¸co a arrendar no in´ıcio do mˆes ipor um per´ıodo de jmeses Restri¸c˜oes Que em cada mˆes esteja arrendado pelo menos o espa¸co necess´ario: (mˆes 1) P5 j=1 x1j≥1500 (mˆes 2) P5 j=2 x1j+P4 j=1 x2j≥1000 (mˆes 3) P5 j=3 x1j+P4 j=2 x2j+P3 j=1 x3j≥2000 (mˆes 4) P5 j=4 x1j+P4 j=3 x2j+P3 j=2 x3j+P2 j=1 x4j≥500 (mˆes 5) x15 +x24 +x33 +x42 +x51 ≥2500 xij ≥0 1≤i≤5,1≤j≤6−i Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Constru¸c˜ao de Modelos de Programa¸c˜ao Linear e Inteira 7 Slide 14 Fun¸c˜ao objectivo min CUSTO = custo de arrendar 1 m2por 1 mˆes z}|{ 2800 espa¸co arrendado por 1 mˆes (no in´ıcio do mˆes 1, 2, 3, 4 ou 5) z }| { 5 X i=1 xi1+ 4500 4 X i=1 xi2+ 6000 3 X i=1 xi3 + 7300 2 X i=1 xi4+ 8400 x15 Slide 15 Arrendamento de espa¸co num armaz´em Resolu¸c˜ao mais compacta Dados Cj−custo de arrendar 1m2por um per´ıodo de jmeses Ni−necessidade de espa¸co no mˆes i Vari´aveis de decis˜ao xij −espa¸co a arrendar no in´ıcio do mˆes ipor um per´ıodo de jmeses Restri¸c˜oes Que em cada mˆes esteja arrendado pelo menos o espa¸co necess´ario: ∀iP6−i j=1 xij +Pi−1 k=1 P6−k j=i+1−kxkj ≥Ni Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Constru¸c˜ao de Modelos de Programa¸c˜ao Linear e Inteira 8 Slide 16 Fun¸c˜ao objectivo 5 X j=1 Cj× 6−j X i=1 xij Slide 17 F´abrica de papel O papel ´e normalmente fabricado em rolos grandes (em largura e em diˆametro), que depois s˜ao dividos em rolos mais pequenos, que por sua vez poder˜ao ser directamente para clientes ou para cortar em formatos. Vejamos o seguinte exemplo. O papel ´e produzido em rolos com 6 metros de largura. A partir deste rolos ´e necess´ario produzir 30 rolos mais pequenos com 280cm, 60 rolos com 200cm e 48 rolos com 150cm. Assim sendo, um rolo de 6 metros pode ser dividido, por exemplo, em 2 rolos de 280, sobrando um “rolinho” de 40cm que ´e considerado desperd´ıcio. Assumindo que existem rolos grandes em quantidade suficiente para satisfazer esta encomenda, o problema consiste em determinar a forma de cortar os rolos grandes de forma a minimizar o desperd´ıcio. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Constru¸c˜ao de Modelos de Programa¸c˜ao Linear e Inteira 15 Slide 30 q− 3 X i=1 Avi −(1 −δ)A≤0 (2) δ∈ {0,1}(3) Para verificarmos que as inequa¸c˜oes (1–3) modelizam a implica¸c˜ao de condi¸c˜oes devemos relembrar que para que uma implica¸c˜ao a⇒bseja verdadeira ´e preciso que se afor verdadeira ent˜ao btamb´em o seja e que se b for falsa ent˜ao atamb´em o seja. De facto, se P3 i=1 Aei > p ent˜ao para que a restri¸c˜ao (1) se verifique ´e for¸coso que δ= 1. Ora δ= 1 transforma (2) em P3 i=1 Avi ≥q, como se pretendia. Se, por outro lado, P3 i=1 Avi < q ent˜ao, para que (2) se verifique ´e for¸coso que δ= 0. Com δ= 0 a restri¸c˜ao (1) fica P3 i=1 Aei ≤p, como se queria demonstrar. Nota: ´ E poss´ıvel ainda modelizar outras opera¸c˜oes l´ogicas entre condi¸c˜oes. Apresentam-se de seguida 3 casos distintos: Slide 31 1. Disjun¸c˜ao (apenas uma de duas restri¸c˜oes est´a activa) f(xi)≤0∨g(xi)≤0 Seja Mum n´umero “muito grande” e δuma vari´avel bin´aria:    f(xi)≤δM g(xi)≤(1 −δ)M 2. K, de entre N restri¸c˜oes, s˜ao verificadas f1(xi)≤d1 f2(xi)≤d2 . . . fN(xi)≤dN                                               f1(xi)≤d1+δ1M f2(xi)≤d2+δ2M . . . fN(xi)≤dN+δNM PN i=1 δi=N−K δi∈ {0,1} M=∞ Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Constru¸c˜ao de Modelos de Programa¸c˜ao Linear e Inteira 16 Slide 32 3. Fun¸c˜oes com apenas N valores poss´ıveis f(xi) = d1ou d2ou ... ou dN(f(xi)∈ {d1, d2,...,dN})        f(xi) = PN i=1 δidi PN i=1 δi= 1 δi∈ {0,1} Slide 33 Aeroporto Aletrop - Manuten¸c˜ao O aeroporto de Aletrop ´e a base dos avi˜oes da companhia a´erea PAT. Trata-se de um aeroporto moderno, e de uma empresa de avia¸c˜ao em expans˜ao, que pretende manter a sua competitividade num sector de actividade fortemente concorrencial. O aumento de competitividade passa, nomeadamente, pela realiza¸c˜ao de dois objectivos, a melhoria da qualidade de servi¸co e a redu¸c˜ao dos custos de opera¸c˜ao. Por outro lado, a seguran¸ca de uma companhia a´erea ´e um aspecto de primordial importˆancia, estando intimamente ligado `a manuten¸c˜ao. Para manter um avi˜ao em boas condi¸c˜oes t´ecnicas, procede-se `a manuten¸c˜ao preventiva aos aparelhos da PAT, atrav´es de pequenas inspec¸c˜oes entre aterragem e posterior descolagem. A direc¸c˜ao da empresa est´a tamb´em a considerar a hip´otese de oferecer estes servi¸cos de manuten¸c˜ao a outras companhias de avia¸c˜ao, mesmo que para tal tenha que aumentar `as equipas de manuten¸c˜ao. O elemento crucial nestas equipas ´e o chefe de manuten¸c˜ao, t´ecnico altamente qualificado, que necessita de fazer forma¸c˜ao espec´ıfica para cada tipo de avi˜ao e obter assim uma licen¸ca imprescind´ıvel para o desempenho dessas fun¸c˜oes. A cada licen¸ca corresponde uma categoria de avi˜oes, existindo 4 licen¸cas diferentes: Tipos de licen¸cas Avi˜oes 1 Boeing 717 (100 lugares) 2 Boeing 777 (300 a 500 lugares) 3 Airbus A319 (124 lugares) 4 Airbus A340 (350 lugares) Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Constru¸c˜ao de Modelos de Programa¸c˜ao Linear e Inteira 17 Slide 34 Cada t´ecnico pode ter no m´aximo 2 licen¸cas. A primeira licen¸ca demora v´arios anos a obter, sendo portanto mais cara para a empresa, enquanto a segunda licen¸ca demora menos anos a obter, ficando naturalmente mais barata. O custo da segunda licen¸ca depende ainda da licen¸ca anterior que o t´ecnico possui. Actualmente existem 9 equipas de manuten¸c˜ao, cada uma chefiada por um t´ecnico licenciado, que funcionam em 3 turnos. Custo (M$) Licen¸ca Licen¸ca a tirar anterior 1 2 3 4 0 2 4 2 4 1 - 1 2 3 2 1 - 2 3 3 1 3 - 2 4 1 2 1 - Turno Chefe de equipa Tipo de licen¸ca 1 1, 2 1 2 1 3 2 4 3, 4 2 5 2 6 3 7 4 3 8 3, 4 9 3 Para poder oferecer servi¸cos a outras companhias de avia¸c˜ao, a empresa pretende que existam 4 licen¸cas de cada tipo, no conjunto dos chefes de manuten¸c˜ao. Isto pode ser conseguido enviando para forma¸c˜ao actuais chefes de equipa (portanto t´ecnicos que j´a possuem 1 licen¸ca) ou outros t´ecnicos que ainda n˜ao possuem nenhuma licen¸ca. No entanto, de cada turno s´o poder´a sair, no m´aximo, 1 chefe de equipa para forma¸c˜ao. Escreva um modelo de programa¸c˜ao matem´atica que permita determinar a pol´ıtica de obten¸c˜ao de licen¸cas que minimiza os custos para a Aletrop. Slide 35 Aeroporto Aletrop - Manuten¸c˜ao Resolu¸c˜ao Vari´aveis de decis˜ao xij =   1 se t´ecnico itira licen¸ca j 0 se n˜ao A empresa pretende que existam 4 licen¸cas de cada tipo, num total de 16 licen¸cas. Como, no conjunto dos chefes de manuten¸c˜ao existentes, j´a existem 12 licen¸cas, s˜ao necess´arias mais 4 licen¸cas, que no limite poder˜ao ser todas obtidas por t´ecnicos novos. Nesse caso o n´umero m´aximo de t´ecnicos, ´ındice ina formula¸c˜ao, ser´a igual a 13, 9 j´a existentes e 4 novos. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Constru¸c˜ao de Modelos de Programa¸c˜ao Linear e Inteira 18 Slide 36 Restri¸c˜oes A empresa pretende que existam 4 licen¸cas de cada tipo, no conjunto dos chefes de manuten¸c˜ao: P13 i=1 xi1= 2 P13 i=1 xi2= 1 P13 i=1 xi3= 0 P13 i=1 xi4= 1 Um t´ecnico pode ter no m´aximo 2 licen¸cas e os t´ecnicos novos s´o poder˜ao obter nesta fase uma licen¸ca: (esta restri¸c˜ao n˜ao vem referida explicitamente no enunciado, no entanto pode-se inferir que n˜ao haver´a disponibilidade de tempo para que um t´ecnico novo obtenha duas licen¸cas) P4 j=1 xij ≤1∀i∈{2,3,5,6,7,9,10,11,12,13} P4 j=1 xij = 0 ∀i∈{1,4,8} Slide 37 De cada turno s´o poder´a sair, no m´aximo, 1 chefe de equipa para forma¸c˜ao: P4 j=1 P3 i=1 xij ≤1 P4 j=1 P6 i=4 xij ≤1 P4 j=1 P9 i=7 xij ≤1 Cada t´ecnico s´o pode obter 1 vez a mesma licen¸ca: x21 =x32 =x52 = 0 x63 =x74 =x93 = 0 Fun¸c˜ao objectivo ckj = custo de tirar licen¸ca jdado que j´a se tem licen¸ca k min 4 X j=1    13 X i=10 c0jxij +X i∈{6,9} c3jxij +X i∈{3,5} c2jxij +c1jx2j+c4jx7j   Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Constru¸c˜ao de Modelos de Programa¸c˜ao Linear e Inteira 19 Slide 38 Bibliografia •Hillier, Fraderick S. e Lieberman, Gerald (1995). Introduction to Operations Research, Mc Graw-Hill. •Oliveira, Jos´e Fernando (1996). Apontamentos de Investiga¸c˜ao Operacional 1. FEUP. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP