Programação Linear Inteira

P og amação Linea In ei a R Ru ui i A Al l e es s C Ca a a a i in na a D De el lg ga ad do o S Se e e em mb b o o d de e 1 19 99 97 7 APRESENTAÇÃO Es e ex o conc e iza uma ideia que já em alguns anos, mas que inha sendo adiada de ido a a aze es de di e sa na u eza. Dois ac os oco idos no ano lec i o de 1996/97 o am de e minan es na conc e- ização des e p ojec o: (i) a adopção, nas disciplinas de In es igação Ope acional de ambas as licencia u as, de um li o (In es igação Ope acional, de L. Valada es Ta a es e al., McG aw-Hill, 1996) que, embo a cob indo a ma é ia de P og amação Linea e de Filas de Espe a, é omisso no que oca à P og amação Linea In ei a e às Cadeias de Ma ko ; (ii) a con a ação da licenciada Ca a ina Delgado como assis en e es agiá ia das e e idas disciplinas. O ac o de os alunos dispo em de elemen os de es udos (no li o adop ado) sob e alguns pon os do p og ama o nou mais p emen e a conclusão des es ex os com o objec i o de uma in eg al cobe u a do p og ama. A disponibilidade da licenciada Ca a ina Delgado oi na ealidade c ucial (sem o seu abalho e o seu en usiasmo c eio que os ex os não e iam icado p on os), e o seu con ibu o jus i ica plenamen e a co- au o ia que lhe é de ida, pois a ela se de em a p imei a e são dos ex os, odos os exemplos p o usamen e ilus ados, e a inclusão de uma maio a iedade de p oblemas ípicos de P og amação In ei a. Res a-nos deseja que os alunos, des ina á ios úl imos des es abalhos, deles possam i a i a o desejado p o ei o. Todas as c í icas e suges ões são ben indas, sal agua dando que odos os e os e imp ecisões que os ex os possam e são da in ei a esponsabilidade dos au o es. Faculdade de Economia do Po o, Se emb o de 1997 P o . Dou o Rui Al es ÍNDICE 1. INTRODUÇÃO ..................................................................................................... 1 2. CONDIÇÕES EXPRESSAS ATRAVÉS DE VARIÁVEIS BINÁRIAS ............. 2 2.1. Gene alidades ......................................................................................................... 2 2.2. Res ições Mu uamen e Exclusi as ....................................................................... 2 2.3. Respei a k de m Res ições ............................................................................... 2 2.4. Funções com N Valo es Possí eis ....................................................................... 3 2.5. Res ições Condicionadas ...................................................................................... 4 2.6. Rep esen ação de Cus os Fixos .............................................................................. 4 2.7. Máximo de N Va iá eis ....................................................................................... 5 3. ALGUNS PROBLEMAS TÍPICOS DE PI ........................................................... 5 3.1. P oblema de A ec ação .......................................................................................... 5 3.2. P oblema do Caixei o Viajan e .............................................................................. 6 3.3. P oblema da Mochila ............................................................................................. 8 3.4. P oblema da Cobe u a e da Pa ição de Conjun os ............................................... 9 3.5. P oblema de Selecção de P ojec os ...................................................................... 10 3.6. P oblema de Localização ..................................................................................... 11 4. MÉTODOS DE RESOLUÇÃO ........................................................................... 12 4.1. Gene alidades ....................................................................................................... 12 4.2. Mé odo dos Planos de Co e ................................................................................ 14 4.3. Mé odo de Pa ição e A aliação Sucessi as ........................................................ 17 5. BIBLIOGRAFIA ................................................................................................. 22 1 1. INTRODUÇÃO Um p oblema de P og amação Linea In ei a (PLI) é um p oblema de P og ama- ção Linea (PL) em que odas ou alguma(s) das suas a iá eis são disc e as ( êm de as- sumi alo es in ei os). Quando odas as a iá eis es ão sujei as à condição de in e- g alidade es amos pe an e um p oblema de P og amação Linea In ei a Pu a (PLIP); e se apenas algumas o es ão a a-se de um p oblema de P og amação Linea In ei a Mis a (PLIM). Embo a a P og amação In ei a (PI) inclua ambém a P og amação Não-Linea In ei a, em p a icamen e odos os modelos da ida eal se p ese a a es u u a linea das unções, pelo que quase não exis e di e ença en e a PI e a PLI. Os modelos de PLI se ão en ão do ipo dos modelos de PL, sujei os a es ições adicionais indicando que algumas ou odas as a iá eis são disc e as, con o me se pode e no exemplo seguin e: Exis e um caso especial de a iá eis in ei as: as a iá eis biná ias que apenas po- dem oma os alo es 0 (ze o) ou 1 (um). Quando odas as a iá eis de um modelo são biná ias, o modelo diz-se de P og amação In ei a Biná ia. As a iá eis biná ias são mui o ú eis pa a exp imi em si uações dico ómicas (sim ou não, aze ou não aze , e c.), con o me se e á nos pon os 2 e 3. Es e ex o encon a-se o ganizado da seguin e o ma: no pon o 2 são es udadas di e sas condições que podem se exp essas com o auxílio de a iá eis biná ias e no pon o 3 são ap esen ados alguns p oblemas ípicos de P og amação In ei a. O pon o 4 é dedicado a passa em e is a os mé odos de esolução de modelos de PLI, sendo dada a enção especial ao mé odo de pa ição e a aliação sucessi as. Finalmen e, no pon o 5 é lis ada a bibliog a ia consul ada pa a a elabo ação do ex o e conside ada mais ele an e nes a ma é ia. max F = 4x1-5x2 suj. a: 2x1+3x2 ≤ 8 5x1+2x2 ≤ 11 x1, x2 ≥ 0 e in ei as O co esponden e p oblema de PL ( elaxação do PI, dado que se “ala ga” o domínio das a iá eis de decisão de |N0 pa a |R) é: max F = 4x1-5x2 suj. a: 2x1+3x2 ≤ 8 5x1+2x2 ≤ 11 x1, x2 ≥ 0 (PI) (PL) 2    3 x1 + 4 x2 ≤ 12 + M y 5 x1 + 2 x2 ≤ 10 + M (1-y) 2. CONDIÇÕES EXPRESSAS ATRAVÉS DE VARIÁVEIS BINÁRIAS 2.1. GENERALIDADES Con o me oi e e ido no pon o 1, as a iá eis biná ias são mui o ú eis pa a e- p esen a si uações dico ómicas, podendo desempenha dois papéis dis in os: (i) como a iá eis p incipais ou de decisão (decisões do ipo aze ou não aze , cons ui ou não cons ui , e c.); (ii) como a iá eis auxilia es, sendo u ilizadas pa a exp imi ce as condições. As si uações em que as a iá eis biná ias são u ilizadas como a iá eis de decisão são ap esen adas no pon o 3. Nes e pon o e emos a sua u ilização pa a exp imi di e sas condições, ais como es ições mu uamen e exclusi as, unções com á ios alo es possí eis, es ições condicionadas, ep esen ação de cus os ixos, e c. 2.2. RESTRIÇÕES MUTUAMENTE EXCLUSIVAS A si uação no mal de qualque p oblema de PI ou de PLI é a de as es ições se em sa is ei as simul aneamen e (daí ala -se no sis ema de es ições, a ando-se de um sis ema de (in)equações simul âneas). Pode acon ece , con udo, que haja duas es ições mu uamen e exclusi as, ou seja, das duas apenas uma em de se espei ada. Exis e aqui uma dico omia (uma es ição ou a ou a), que pode se exp essa po ecu so a uma a iá el biná ia. Vejamos o seguin e exemplo pa a duas es ições do ipo ≤: De inindo a a iá el biná ia y∈{0, 1}, e ede inindo as es ições como se segue (sendo M um núme o ão g ande quan o se quei a), as duas es ições cons a ão do modelo mas apenas uma das duas se á ga an idamen e espei ada (dependendo do alo que a a iá el y assumi ). É ácil deduzi como de e iam se ede inidas as es ições se as mesmas ossem do ipo ≥. Se uma ou ambas as es ições o em do ipo = podem as mesmas se desdo- b adas em duas desigualdades simul âneas (≤ e ≥), aplicando-se en ão os p incípios enunciados. 3 x1 + 4 x2 ≤ 12 ou5 x1 + 2 x2 ≤ 10 3 2.3. RESPEITAR k DE m RESTRIÇÕES No caso an e io p e endia-se espei a uma de duas es ições (podendo as es- ições se do ipo ≤ ou do ipo ≥). Uma ex ensão dessa si uação consis e em e de es- pei a k de m es ições (k<m). Nes e caso de em-se de ini an as a iá eis biná ias quan as as es ições, com o seguin e signi icado (pa a o caso das es ições se em do ipo Gj(x) ≤ 0): As es ições de em se ede inidas de modo semelhan e ao ap esen ado no pon o 2.2., ou seja, e pa a ga an i que apenas k es ições êm de se sa is ei as ac escen a-se a condição km my jj−= ∑ =1. 2.4. FUNÇÕES COM N VALORES POSSÍVEIS Habi ualmen e as es ições apenas êm um alo pa a o e mo independen e. Se hou e N alo es possí eis pa a o e mo independen e, essa es ição pode se esc i a com ecu so a N a iá eis biná ias, como se pode e no seguin e exemplo: De inem-se as a iá eis biná ias yk ais que: yk k N = ∑= 11, com cada yk ∈ {0, 1} A es ição se á en ão al e ada pa a ax ij jj ∑ = by ik k k N⋅ ∑ =1 yj=      0, se es ição j é álida (Gj(x) ≤ 0) 1, se não (Gj(x) ≤ M → es ição edundan e) G1(x) ≤ M y1 G2(x) ≤ M y2 … Gm(x) ≤ M ym Res ição j: ax ij jj ∑ = bi1 ou bi2 ou … biN 4 2.5. RESTRIÇÕES CONDICIONADAS Suponhamos que a es ição 1 só se pode e i ica se a es ição 2 se e i ica , ou seja, es ição 1 ⇒ es ição 2. Es a si uação é acilmen e esol ida se lemb a mos que uma implicação pode se semp e ep esen ada po uma disjunção, pelo que [ es ição 1 ⇒ es ição 2] é equi alen e a [não- es ição 1 ou es ição 2]. T a a-se en ão de exp imi es ições mu uamen e exclusi as, con o me oi já is o no pon o 2.1. 2.6. REPRESENTAÇÃO DE CUSTOS FIXOS Ou a si uação que pode se exp essa a a és de a iá eis biná ias é a ep esen a- ção de cus os ixos. Suponhamos que o cus o de p odução de um ce o p odu o em duas componen es: um cus o ixo (independen e da quan idade p oduzida) e um cus o a iá el que é p opo cional à quan idade ab icada. T a a-se de uma si uação di e en e da habi ual, na qual o cus o ixo é inco ido mesmo que não haja p odução; aqui, se não hou e p odução o cus o é ze o (em inglês é chamado de “ ixed cha ge” pa a o dis ingui de “ ixed cos ”). Como exemplo podemos conside a a si uação em que o cus o ixo co esponde ao cus o de p epa ação das máquinas, que não depende da quan idade que ai se ab icada mas só é inco ido se hou e p odução. Suponhamos que a quan idade a ab ica é ep esen ada pela a iá el x. De inimos a a iá el biná ia pelo que a unção cus o se esc e e á CT = (CM + CP x) y , ou CT = CM y + CP x É necessá io ac escen a uma es ição pa a ga an i que quando x > 0 en ão y = 1 e que quando y = 0 en ão x = 0: x ≤≤ M y, com M mui o g ande A p óp ia na u eza da unção objec i o az com que se x = 0 en ão y = 0, uma ez que se p e ende minimiza o cus o. y=      1, se hou e p odução (x>0) 0, se não hou e p odução (x=0) =      0, se x = 0 CM + CP x , se x > 0 A⇒⇒ B ⇔ ~A∨∨B 5 2.7. MÁXIMO DE N VARIÁVEIS O máximo de N a iá eis, Xmax = max {X1, X2, …, XN} pode se exp esso eco - endo-se a N a iá eis biná ias. De inem-se as a iá eis biná ias yk, k=1,…,N, ais que: e ac escen a-se a condição yk k N = ∑= 11, com cada yk ∈ {0, 1} que ga an e que Xmax apenas assume um alo . As es ições seguin es (1) Xmax ≥ Xk ∀k=1..N (2) Xmax ≤ Xk +M (1- yk) ga an em que Xmax i á igual ao máximo das a iá eis conside adas. 3. ALGUNS PROBLEMAS TÍPICOS DE PI 3.1. PROBLEMA DE AFECTAÇÃO O P oblema de A ec ação (em inglês, Assignmen P oblem) é conhecido po es e nome po se a ep esen ação de inúme as si uações em que é necessá io a ec a pessoas a luga es, a a e as ou a zonas de abalho, máquinas a a e as, e c. Apa ece mui as ezes como se a asse de um p oblema de PL mas, como e emos, as suas a iá eis de decisão são biná ias. Suponhamos que se p e ende a ec a n indi íduos a n a e as, sabendo que a medida de e iciência de a ec a o indi íduo i à a e a j é cij (que an o pode ep esen a um luc o como um cus o). P e ende-se de e mina a a ec ação dos indi íduos às a e as de modo a op imiza a e iciência o al. As a iá eis de decisão são as seguin es: yk=      1, se Xk é máximo 0, se Xk não é máximo Xij=     1, se o indi íduo i o a ec ado à a e a j 0, se o indi íduo i não o a ec ado à a e a j i=1, .., n j= 1,.., n 6 O modelo de PLI é como se segue : T a a-se, como se pode e , de um modelo mui o simples e cujo sis ema de es i- ções em uma es u u a pa icula com ce as p op iedades. Si uações em que o núme o de indi íduos é di e en e do núme o de a e as podem ambém se ep esen adas. Um p oblema que seja ep esen ado po um modelo com es a es u u a chama-se p oblema de a ec ação, independen emen e da si uação que es i e a se conside ada. Con o me e emos mais adian e, os p oblemas de a ec ação dispõem de um mé odo de esolução p óp io g aças à sua es u u a especial. 3.2. PROBLEMA DO CAIXEIRO VIAJANTE O P oblema do Caixei o Viajan e (em inglês, T a eling Salesman P oblem) é ou o ipo de p oblema que pode se ep esen ado po um modelo de PLI. Es e p oblema é acilmen e is o numa ede, em que as cidades co espondem aos nós ou é ices e os a cos ep esen am as ligações en e as cidades. Consis e em encon a um ci cui o que liga odas as cidades, ou seja, um conjun o de a cos que, pa indo de um de e minado é ice, passa po odos os ou os uma e uma só ez e e mina no é ice de pa ida. Conhecendo-se a dis ância ou o cus o en e cada pa de cidades ( é ices), p e ende-se de e mina o ci cui o óp imo. As a iá eis de decisão são as seguin es: O modelo de PLI é como se segue: Xij=     1, se a cidade j é isi ada imedia amen e após a cidade i 0, se a cidade j não é isi ada imedia amen e após a cidade i i=1, .., n j= 1,.., n min ou max cX ij ij ji ⋅ ∑∑      → op imiza a e iciência o al suj. a: 1. cada indi íduo só pode es a a ec ado a uma a e a: Xij j ∑ =∀= 1, i: i 1,2,3,4 2. cada a e a só de e se desempenhada po um indi íduo: Xij ij ∑ =∀1, j: =A, B, C, D Xij∈{0, 1} 13 2ª) A solução óp ima do p oblema de PL após o a edondamen o pode não se admissí el pa a o modelo de PLI (embo a o modelo de PLI enha soluções). Conside e-se o seguin e modelo cuja ep esen ação g á ica se encon a na Figu a 4.1: 3ª) A solução in ei a ( esul an e do a edondamen o da solução óp ima do p o- blema de PL) pode es a ela i amen e “a as ada” da solução óp ima do p oblema de PLI (sendo o “a as amen o” medido em e mos da unção objec- i o). Conside e-se o seguin e modelo cuja ep esen ação g á ica es á na Figu a 4.2: max F = 11 x1 + 10 x2 suj. a: 2.75 x1+10 x2 ≤ 21 - 2 x1 + 6 x2 ≥ 3 x1, x2 ≥ 0 e in ei as max F = 35 x1 + 70 x2 suj. a: 3 x1 + 7 x2 ≤ 17 14 x1 -11 x2 ≤ 18.2 x1, x2 ≥ 0 e in ei as 1230 x1 x2 0 1 2 sen ido do c escimen o de F(x1, x2) Solução óp ima do p oblema de PL (2.63, 1.38)(2.63, 1.38) Figu a 4.1 - Nenhuma das qua o soluções ob idas po a edondamen o é possí el 14 Conclui-se assim pela necessidade de mé odos que examinem apenas uma pa e do conjun o de soluções admissí eis e que ap o ei em as an agens do algo i mo Simplex. Exac amen e com es as ca ac e ís icas, exis em dois mé odos: o Mé odo dos Planos de Co es (Cu ing Planes) e o Mé odo de Pa ição e A aliação Sucessi as (B anch and Bound). De ac o, ambos u ilizam o algo i mo Simplex pa a chega à solução óp ima de p oblemas de PL cuja egião admissí el ai sendo sucessi amen e eduzida a é se alcança a solução do p oblema de PLI. Es es mé odos são ge ais, pois podem se aplicados a qualque modelo de PLI. Exis em ambém mé odos especí icos, que apenas pe mi em esol e o ipo de p oblemas pa a os quais o am concebidos. É o caso, po exemplo, do Mé odo Húnga o pa a o P oblema de A ec ação. Es e mé odo i a pa ido da es u u a especial do p oblema, sendo po isso mais e icien e que os mé odos ge ais. Finalmen e, exis em ambém mé odos heu ís icos pa a ce os ipos de p oblemas. Es es algo i mos são bas an e e icien es pa a ce os p oblemas mui o di íceis de esol e , embo a a solução po eles encon ada não seja ga an idamen e óp ima. Exis em, po exemplo, á ias heu ís icas pa a o P oblema do Caixei o Viajan e. Hoje em dia, g aças aos a anços da ecnologia in o má ica e a um con inuado es o ço de melho ia de e iciência dos algo i mos, é possí el esol e de o ma óp ima p oblemas cada ez maio es. 4.2. MÉTODO DOS PLANOS DE CORTE O mé odo dos Planos de Co e (Cu ing Planes, em inglês) oi o p imei o mé odo a se desen ol ido e de e-se a Gomo y (1958). Consis e em in oduzi sucessi amen e no as es ições na elaxação linea do PLI, es ições essas que co am o conjun o das soluções possí eis eliminando algumas delas e a p óp ia solução óp ima do PL (po isso se chamam planos de co e), sem con udo elimina qualque solução in ei a. sen ido do c escimen o de F(x1, x2) Solução a edondada F(2, 1)=140F(2, 1)=140 Solução óp ima do p oblema de PL F(2.4, 1.4)=182F(2.4, 1.4)=182 Figu a 4.2 - A solução in ei a (ob ida po a edondamen o) não é a solução óp ima do p oblema de PLI 1230 x1 x2 0 1 2 SOLUÇÃO INTEIRA ÓPTIMA F(1, 2)=175F(1, 2)=175 15 Conside emos o seguin e exemplo. An ónio, p op ie á io da emp esa de b inque- dos “Toys ’ ’ Tony”, decidiu c ia uma secção de b inquedos adicionais de madei a, começando po apenas dois ipos de b inquedos: pequenos ca alos de baloiço (luc o uni á io de 2400$) e comboios an igos (luc o uni á io de 1500$). Cada ca alo eque uma ho a de abalho e 9 m2 de madei a, enquan o que cada comboio eque uma ho a de abalho e 5 m2 de madei a. Supondo que es ão disponí eis 6 ho as de abalho e 45 m2 de madei a, que quan idades ab ica de o ma a maximiza o luc o? Va iá eis de Decisão: x1= núme o de ca alos de baloiço ab icados x2= núme o de comboios ab icados O p imei o passo consis e na esolução da elaxação linea do PLI, que co es- ponde ao quad o simplex da Figu a 4.3 e à ep esen ação g á ica da Figu a 4.4: Figu a 4.4 - Resolução da elaxação linea do p oblema de PLI Solução óp ima do p oblema de PL F(3.75, 2.25)=12375 x2 5 3 2 1 6 4 7 9 8 6 5 4 3 2 1 x1 x1x2 1 2 x110-1.25 0.25 3.75 x20 1 2.25 -0.25 2.25 -F 0 0 375 0.75 -12375 Figu a 4.3 - Quad o SIMPLEX óp imo pa a a elaxação linea do p oblema de PLI O p oblema (de PI) se á: max F = 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (ho as de abalho) 9x1 + 5 x2 ≤ 45 (madei a) x1, x2 ≥ 0 e in ei os 16 Como na solução óp ima da elaxação linea os alo es das a iá eis não são in- ei os, há que ge a um plano de co e. Pa a al, bas a conside a a es ição do quad o simplex óp imo da elaxação linea cujo e mo independen e enha a pa e accioná ia mais p óxima de 0.5, e eesc e e essa es ição sepa ando a pa e in ei a da pa e ac- cioná ia. No exemplo conside ado, qualque das es ições pode se conside ada, uma ez que as pa es accioná ias de 3.75 e de 2.25 se encon am igualmen e p óximas de 0.5. Escolhendo a p imei a es ição x1-1.25 1+0.25 2 = 3.75 e eesc e endo-a sob a o ma [memb o com coe icien es in ei os = memb o com coe icien es accioná ios] ica- se com x1-2 1-3 = 0.75-0.75 1-0.25 2. O no o plano de co e a ac escen a ao modelo aduz a es ição memb o com coe icien es accioná ios ≤ 0 , ou seja, 0.75 - 0.75 1 - 0.25 2 ≤≤ 0 3 x1 +2 x2 ≤≤15 O no o modelo de PL a esol e é en ão max F = 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (ho as de abalho) 9x1 + 5 x2 ≤ 45 (madei a) 3 x1 +2 x2 ≤≤15 (plano de co e) x1, x2 ≥ 0 Como se pode analisa na Figu a 4.5 a no a es ição “co ou” o conjun o das soluções possí eis, eliminando a solução óp ima da elaxação linea , mas não eliminando qualque solução in ei a. Como a solução óp ima des e no o modelo de PL é in ei a, ela é a solução óp ima do PLI. Se a solução encon ada ainda não osse in ei a, ge a -se-ia no o co e, e assim sucessi amen e. ⇓ ⇑ (pela de inição das a iá eis de olga, 1 =6-x 1 -x 2 e 2 =45-9x 1 -5x 2 ) Figu a 4.5 - Aplicação do plano de co e: a esolução do no o p oblema de PL conduz à solução óp ima do p oblema de PLI inicial (5, 0) x2 5 3 2 1 6 4 7 9 8 6 5 4 3 2 1 x1 Solução óp ima do no o p oblema F(5, 0)=12000 Solução óp ima do p oblema de PL F(3.75, 2.25)=12375 17 Qualque co e ge ado po es e mé odo em, en ão, duas p op iedades: 1ª) Qualque solução possí el do PLI sa is az o co e. 2ª) A solução óp ima da elaxação linea não sa is az o co e. Demons a-se (Gomo y, 1958) que se a inge a solução óp ima do PLI após um núme o ini o de co es. Apesa des a p op iedade o mé odo dos planos de co e caiu em desuso, sendo mui o pouco u ilizado de ido ao abalho compu acional en ol ido na esolução de p oblemas de g andes dimensões. Embo a o núme o de co es seja ini o, o seu núme o pode se mui o ele ado (cen enas ou milha es); de cada ez que se ge a um no o co e ac escen a-se uma no a es ição ao modelo o iginal, o que signi ica que a complexidade desse modelo é semp e c escen e, podendo o abalho compu acional i a o na -se p oibi i o apesa de se dispo de um algo i mo de esolução mui o e icien e como é o simplex. Ou a des an agem des e mé odo (quando compa ado com o mé odo de pa ição e a aliação sucessi as) é que se se in e ompe o mé odo an es de ele chega ao im não se dispõe de qualque solução in ei a, ainda que não seja óp ima. 4.3. MÉTODO DE PARTIÇÃO E AVALIAÇÃO SUCESSIVAS O mé odo “B anch and Bound” (li e almen e, mé odo de ami icação e limi ação) consis e na pa ição ( ami icação) sucessi a do conjun o de soluções possí eis do p oblema de PLI em subconjun os e na limi ação (a aliação) do alo óp imo da unção objec i o (limi e in e io se se a a de maximização, ou supe io se se a a de mini- mização), de modo a exclui os subconjun os que não con enham a solução óp ima. Pa indo da cons a ação de que se, na solução óp ima da elaxação linea dum p oblema de PLI, as a iá eis omam alo es in ei os, en ão essa solução é a solução óp ima do PLI, começa-se po esol e a elaxação linea do PLI inicial: se as a iá eis que no p oblema de PLI são in ei as omam, na solução óp ima do PL, alo es in ei os, en ão oi encon ada a solução óp ima do PLI; caso con á io, di ide-se o p oblema de PL em dois, a a és da in odução de es ições adicionais que azem a pa ição do conjun o das soluções possí eis. Vão-se en ão esol endo sucessi os p oblemas de PL, es abele- cendo-se limi es pa a o alo óp imo da unção objec i o e, assim, eliminando di e sos sub-conjun os, a é se alcança a solução óp ima do PLI. Ilus a-se seguidamen e es e mé odo e omando o exemplo já usado an e io men e, no qual An ónio, p op ie á io da emp esa de b inquedos “Toys ’ ’ Tony”, decidia c ia uma secção de b inquedos adicionais de madei a, começando po pequenos ca alos de baloiço e comboios an igos. As a iá eis e o modelo, a ás de inidos, e am os seguin es: Va iá eis de Decisão: x1= núme o de ca alos de baloiço ab icados x2= núme o de comboios ab icados 18 O p imei o passo consis e na esolução da elaxação linea do PLI, o que oi ei o g a icamen e na Figu a 4.6: Desde já se sabe que o alo óp imo da unção objec i o não pode excede 12375. Como na solução óp ima des e p oblema x1 e x2 não são in ei as, há a necessidade de e ec ua a sua pa ição, dando o igem a dois no os subp oblemas (A e B), pela in o- dução de no as es ições de eliminação de soluções não-in ei as: x1 ≤ 3 e x1 ≥ 4 (Figu a 4.7). Pode -se-ia escolhe aze a pa ição segundo a a iá el x2. A: max F = 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (ho as de abalho) 9x1 + 5 x2 ≤ 45 (madei a) x1≤3 x1, x2 ≥ 0 B: max F = 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (ho as de abalho) 9x1 + 5 x2 ≤ 45 (madei a) x1≥4 x1, x2 ≥ 0 x2 5321 64 7 9 8 6 5 4 3 2 1 x1 Solução óp ima do p oblema de PL F(3.75, 2.25)=12375 Figu a 4.6 - Resolução da elaxação linea do p oblema PLI max F = 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (ho as de abalho) 9x1 + 5 x2 ≤ 45 (madei a) x1, x2 ≥ 0 e in ei os 19 A solução óp ima do subp oblema A é in ei a, o que signi ica que se encon ou uma solução in ei a cujo alo da unção objec i o é 11700. O alo óp imo da unção objec i o es a á comp eendido en e es es dois limi es, 11700 ≤ F ≤ 12375. Como a solução óp ima do subp oblema B não é in ei a e o alo da unção objec i o é 12300 (>11700), es e subp oblema pode con e uma solução in ei a melho que a do subp o- blema A; logo, é necessá io e ec ua a sua pa ição, dando o igem aos subp oblemas B1 e B2, pela in odução das es ições x2 ≥ 2 e x2 ≤ 1 (Figu a 4.8). Os no os subp oblemas são da o ma: B1:max F= 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (ho as de abalho) 9x1 + 5 x2 ≤ 45 (madei a) x1≥4 x2≥2 x1, x2 ≥ 0 B2:max F = 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (ho as de abalho) 9x1 + 5 x2 ≤ 45 (madei a) x1≥4 x2≤1 x1, x2 ≥ 0 Figu a 4.7 - P imei a pa ição: in oduzindo, no p oblema de PL inicial, a es ição x1 ≤ 3 ob ém-se o subp oblema A(cuja solução óp ima é in ei a) e in oduzindo a es ição x1 ≥ 4 ob ém-se o subp oblema B (cuja solução óp ima ainda não é in ei a, pelo que se em de con inua a pa ição). x2 5321 64 7 9 8 6 5 4 3 2 1 x1 A B Solução óp ima do subp oblema B F(4, 1.8)=12300 Solução óp ima do subp oblema A F(3, 3)=11700 20 O subp oblema B1 não em soluções possí eis, sendo po isso excluído. O sub- p oblema B2, pelas mesmas azões do subp oblema B, é objec o de pa ição e dá o igem aos subp oblemas B21 e B22, pela in odução das es ições x1 ≤ 4 e x1 ≥ 5 (Figu a 4.9): B21:max F = 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (ho as de abalho) 9x1 + 5 x2 ≤ 45 (madei a) x1 ≥ 4 x2 ≤ 1 x1 ≤ 4 x1, x2 ≥ 0 B22:max F = 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (ho as de abalho) 9x1 + 5 x2 ≤ 45 (madei a) x1 ≥ 4 x2 ≤ 1 x1 ≥ 5 x1, x2 ≥ 0 x1 = 4 x1 ≥ 5 Figu a 4.8 - Segunda pa ição: in oduzindo, no subp oblema B, a es ição x2 ≥ 2 icamos com o sub- p oblema B1(solução impossí el) e in oduzindo a es ição x2 ≤ 1 icamos com o subp oblema B2 (solução ainda não é in ei a, pelo que se em de con inua a pa ição). x2 5321 64 7 9 8 6 5 4 3 2 1 x1 A B2 Solução óp ima do subp oblema B2 F(4.4, 1)=12167 Solução óp ima do subp oblema A F(3, 3)=11700 21 Que o subp oblema B21 que o subp oblema B22 êm soluções in ei as. O alo óp imo da unção objec i o do subp oblema B21 é 11100, meno que 11700, ou seja, pio do que a solução de que já dispúnhamos. O alo óp imo da unção objec i o do subp oblema B22 é 12000, logo ac ualizamos os limi es e e emos 12000 ≤ F ≤ 12000. A sequência o al das pa ições é pa icula men e e iden e no seguin e diag ama, es- u u ado em o ma de á o e (Figu a 4.10): (x1, x2)= (3.75, 2.25) F = 12375 BA B2 B1 B22 B21 x1≤ 3 x1≥≥ 4 x2≥≥ 2 x2≤ 1 x1≤ 4 x1≥≥ 5 (x1, x2)= (4, 1.8) F B = 12300 (x1, x2)= (3, 3) F A = 11700 (x1, x2)= (4.44, 1) F B2 = 12167 Subp oblema impossí el (x1, x2)= (5, 0) F B22 = 12000 (x1, x2)= (4, 1) F B21 = 11100 SOLUÇÃO ÓPTIMA Figu a 4.10 - Á o e inal do mé odo “B anch and Bound” pa a o exemplo ap esen ado Figu a 4.9 - Te cei a pa ição: in oduzindo, no subp oblema B2, a es ição x1 ≥ 5 icamos com o sub- p oblema B21 e in oduzindo a es ição x1 ≤ 4 icamos com o subp oblema B22: odas as soluções são já in ei as, não ha endo a necessidade de e ec ua mais nenhuma pa ição. A solução óp ima do p oblema de PLI é (x1, x2) = (5, 0). x2 5321 64 7 9 8 6 5 4 3 2 1 x1 ASolução óp ima do subp oblema B22 F(5, 0)=12000 Solução óp ima do subp oblema A F(3, 3)=11700 Solução óp ima do subp oblema B21 F(4, 1)=11100 22 À medida que se ai “descendo” na á o e da Figu a 4.10 ão-se ac ualizando os limi es in e io e supe io ao alo óp imo da unção objec i o (F*). No nó inicial ( aiz da á o e), 0 ≤ F* ≤ 12375. Ao ní el dos subp oblemas A e B, 11700 ≤ F* ≤ 12300. No ní el imedia amen e in e io , 11700 ≤ F* ≤ 12167. Po im, no qua o e úl imo ní el, 12000 ≤ F* ≤ 12000. Podemos en ão conclui que (x1, x2) = (5, 0), F* = 12000 é a solução óp ima, não azendo sen ido e ec ua qualque no a pa ição. Vemos assim que: (1) É e ec uada a pa ição de um subp oblema em cuja solução óp ima exis a pelo menos uma a iá el que, sendo uma a iá el in ei a no PLI inicial, assuma alo es não-in ei os, se esse subp oblema pude con e uma solução in ei a melho do que a já exis en e. (2) São logo eliminados os subp oblemas que não enham soluções possí eis ou que não possam con e uma solução possí el melho do que a já exis en e. Pa a além de se , de um modo ge al, menos abalhoso esol e um modelo de PLI a a és des e mé odo do que a a és do mé odo dos planos de co e, ele ap esen a a an agem de se possí el in e ompe o mé odo an es de encon a a solução óp ima e de dispo de uma solução in ei a, em elação à qual se pode e uma ideia de quão p óxima es a á da solução óp ima g aças aos limi es que se ão de e minando. 5. BIBLIOGRAFIA Ga inkel, Robe S. and Geo ge L. Nemhause (1972), In ege P og amming, John Wiley & Sons, Inc. Hadley, Geo ge (1974), Linea P og amming, Eigh h P in ing, Addison-Wesley. Hadley, Geo ge (1972), Nonlinea and Dynamic P og amming, Second P in ing, Addison-Wesley. Hillie , G. and J. Liebe man (1995), In oduc ion o Ope a ions Resea ch, Six h Edi ion, McG aw-Hill. Ramalhe e, Manuel, Jo ge Gue ei o e Alípio Magalhães (1984), P og amação Linea , Vol. I e Vol. II, Edi o a McG aw-Hill de Po ugal. Wins on, Wayne L. (1994), Ope a ions Resea ch – Applica ions and Algo i hms, Thi d Edi ion, Duxbu y P ess. Wu, Nesa and Richa d Coppins (1981), Linea P og amming and Ex ensions, McG aw- Hill.