Programação Linear Inteira

Programação Linear Inteira R Ru ui i A Al lv ve es s C Ca at ta ar ri in na a D De el lg ga ad do o S Se et te em mb br ro o d de e 1 19 99 97 7 APRESENTAÇÃO Este texto concretiza uma ideia que já tem alguns anos, mas que vinha sendo adiada devido a afazeres de diversa natureza. Dois factos ocorridos no ano lectivo de 1996/97 foram determinantes na concretização deste projecto: (i) a adopção, nas disciplinas de Investigação Operacional de ambas as licenciaturas, de um livro (Investigação Operacional, de L. Valadares Tavares et al., McGraw-Hill, 1996) que, embora cobrindo a matéria de Programação Linear e de Filas de Espera, é omisso no que toca à Programação Linear Inteira e às Cadeias de Markov; (ii) a contratação da licenciada Catarina Delgado como assistente estagiária das referidas disciplinas. O facto de os alunos disporem de elementos de estudos (no livro adoptado) sobre alguns pontos do programa tornou mais premente a conclusão destes textos com o objectivo de uma integral cobertura do programa. A disponibilidade da licenciada Catarina Delgado foi na realidade crucial (sem o seu trabalho e o seu entusiasmo creio que os textos não teriam ficado prontos), e o seu contributo justifica plenamente a coautoria que lhe é devida, pois a ela se devem a primeira versão dos textos, todos os exemplos profusamente ilustrados, e a inclusão de uma maior variedade de problemas típicos de Programação Inteira. Resta-nos desejar que os alunos, destinatários últimos destes trabalhos, deles possam vir a tirar o desejado proveito. Todas as críticas e sugestões são benvindas, salvaguardando que todos os erros e imprecisões que os textos possam ter são da inteira responsabilidade dos autores. Faculdade de Economia do Porto, Setembro de 1997 Prof. Doutor Rui Alves ÍNDICE 1. INTRODUÇÃO ..................................................................................................... 1 2. CONDIÇÕES EXPRESSAS ATRAVÉS DE VARIÁVEIS BINÁRIAS ............. 2 2.1. Generalidades ......................................................................................................... 2 2.2. Restrições Mutuamente Exclusivas ....................................................................... 2 2.3. Respeitar k de m Restrições ............................................................................... 2 2.4. Funções com N Valores Possíveis ....................................................................... 3 2.5. Restrições Condicionadas ...................................................................................... 4 2.6. Representação de Custos Fixos .............................................................................. 4 2.7. Máximo de N Variáveis ....................................................................................... 5 3. ALGUNS PROBLEMAS TÍPICOS DE PI ........................................................... 5 3.1. Problema de Afectação .......................................................................................... 5 3.2. Problema do Caixeiro Viajante .............................................................................. 6 3.3. Problema da Mochila ............................................................................................. 8 3.4. Problema da Cobertura e da Partição de Conjuntos ............................................... 9 3.5. Problema de Selecção de Projectos ...................................................................... 10 3.6. Problema de Localização ..................................................................................... 11 4. MÉTODOS DE RESOLUÇÃO ........................................................................... 12 4.1. Generalidades ....................................................................................................... 12 4.2. Método dos Planos de Corte ................................................................................ 14 4.3. Método de Partição e Avaliação Sucessivas ........................................................ 17 5. BIBLIOGRAFIA ................................................................................................. 22 1 1. INTRODUÇÃO Um problema de Programação Linear Inteira (PLI) é um problema de Programação Linear (PL) em que todas ou alguma(s) das suas variáveis são discretas (têm de assumir valores inteiros). Quando todas as variáveis estão sujeitas à condição de integralidade estamos perante um problema de Programação Linear Inteira Pura (PLIP); e se apenas algumas o estão trata-se de um problema de Programação Linear Inteira Mista (PLIM). Embora a Programação Inteira (PI) inclua também a Programação Não-Linear Inteira, em praticamente todos os modelos da vida real se preserva a estrutura linear das funções, pelo que quase não existe diferença entre a PI e a PLI. Os modelos de PLI serão então do tipo dos modelos de PL, sujeitos a restrições adicionais indicando que algumas ou todas as variáveis são discretas, conforme se pode ver no exemplo seguinte: Existe um caso especial de variáveis inteiras: as variáveis binárias que apenas podem tomar os valores 0 (zero) ou 1 (um). Quando todas as variáveis de um modelo são binárias, o modelo diz-se de Programação Inteira Binária. As variáveis binárias são muito úteis para exprimirem situações dicotómicas (sim ou não, fazer ou não fazer, etc.), conforme se verá nos pontos 2 e 3. Este texto encontra-se organizado da seguinte forma: no ponto 2 são estudadas diversas condições que podem ser expressas com o auxílio de variáveis binárias e no ponto 3 são apresentados alguns problemas típicos de Programação Inteira. O ponto 4 é dedicado a passar em revista os métodos de resolução de modelos de PLI, sendo dada atenção especial ao método de partição e avaliação sucessivas. Finalmente, no ponto 5 é listada a bibliografia consultada para a elaboração do texto e considerada mais relevante nesta matéria. max F = 4x1-5x2 suj. a: 2x1+3x2 ≤ 8 5x1+2x2 ≤ 11 x1, x2 ≥ 0 e inteiras O correspondente problema de PL (relaxação do PI, dado que se “alarga” o domínio das variáveis de decisão de |N0 para |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 Conforme foi referido no ponto 1, as variáveis binárias são muito úteis para representar situações dicotómicas, podendo desempenhar dois papéis distintos: (i) como variáveis principais ou de decisão (decisões do tipo fazer ou não fazer, construir ou não construir, etc.); (ii) como variáveis auxiliares, sendo utilizadas para exprimir certas condições. As situações em que as variáveis binárias são utilizadas como variáveis de decisão são apresentadas no ponto 3. Neste ponto veremos a sua utilização para exprimir diversas condições, tais como restrições mutuamente exclusivas, funções com vários valores possíveis, restrições condicionadas, representação de custos fixos, etc. 2.2. RESTRIÇÕES MUTUAMENTE EXCLUSIVAS A situação normal de qualquer problema de PI ou de PLI é a de as restrições serem satisfeitas simultaneamente (daí falar-se no sistema de restrições, tratando-se de um sistema de (in)equações simultâneas). Pode acontecer, contudo, que haja duas restrições mutuamente exclusivas, ou seja, das duas apenas uma tem de ser respeitada. Existe aqui uma dicotomia (uma restrição ou a outra), que pode ser expressa por recurso a uma variável binária. Vejamos o seguinte exemplo para duas restrições do tipo ≤: Definindo a variável binária y∈{0, 1}, e redefinindo as restrições como se segue (sendo M um número tão grande quanto se queira), as duas restrições constarão do modelo mas apenas uma das duas será garantidamente respeitada (dependendo do valor que a variável y assumir). É fácil deduzir como deveriam ser redefinidas as restrições se as mesmas fossem do tipo ≥. Se uma ou ambas as restrições forem do tipo = podem as mesmas ser desdobradas em duas desigualdades simultâneas (≤ e ≥), aplicando-se então os princípios enunciados. 3 x1 + 4 x2 ≤ 12 ou5 x1 + 2 x2 ≤ 10 3 2.3. RESPEITAR k DE m RESTRIÇÕES No caso anterior pretendia-se respeitar uma de duas restrições (podendo as restrições ser do tipo ≤ ou do tipo ≥). Uma extensão dessa situação consiste em ter de respeitar k de m restrições (k<m). Neste caso devem-se definir tantas variáveis binárias quantas as restrições, com o seguinte significado (para o caso das restrições serem do tipo Gj(x) ≤ 0): As restrições devem ser redefinidas de modo semelhante ao apresentado no ponto 2.2., ou seja, e para garantir que apenas k restrições têm de ser satisfeitas acrescenta-se a condição km my jj−= ∑ =1. 2.4. FUNÇÕES COM N VALORES POSSÍVEIS Habitualmente as restrições apenas têm um valor para o termo independente. Se houver N valores possíveis para o termo independente, essa restrição pode ser escrita com recurso a N variáveis binárias, como se pode ver no seguinte exemplo: Definem-se as variáveis binárias yk tais que: yk k N = ∑= 11, com cada yk ∈ {0, 1} A restrição será então alterada para ax ij jj ∑ = by ik k k N⋅ ∑ =1 yj=      0, se restrição j é válida (Gj(x) ≤ 0) 1, se não (Gj(x) ≤ M → restrição redundante) G1(x) ≤ M y1 G2(x) ≤ M y2 … Gm(x) ≤ M ym Restrição j: ax ij jj ∑ = bi1 ou bi2 ou … biN 4 2.5. RESTRIÇÕES CONDICIONADAS Suponhamos que a restrição 1 só se pode verificar se a restrição 2 se verificar, ou seja, restrição 1 ⇒ restrição 2. Esta situação é facilmente resolvida se lembrarmos que uma implicação pode ser sempre representada por uma disjunção, pelo que [restrição 1 ⇒ restrição 2] é equivalente a [não-restrição 1 ou restrição 2]. Trata-se então de exprimir restrições mutuamente exclusivas, conforme foi já visto no ponto 2.1. 2.6. REPRESENTAÇÃO DE CUSTOS FIXOS Outra situação que pode ser expressa através de variáveis binárias é a representação de custos fixos. Suponhamos que o custo de produção de um certo produto tem duas componentes: um custo fixo (independente da quantidade produzida) e um custo variável que é proporcional à quantidade fabricada. Trata-se de uma situação diferente da habitual, na qual o custo fixo é incorrido mesmo que não haja produção; aqui, se não houver produção o custo é zero (em inglês é chamado de “fixed charge” para o distinguir de “fixed cost”). Como exemplo podemos considerar a situação em que o custo fixo corresponde ao custo de preparação das máquinas, que não depende da quantidade que vai ser fabricada mas só é incorrido se houver produção. Suponhamos que a quantidade a fabricar é representada pela variável x. Definimos a variável binária pelo que a função custo se escreverá CT = (CM + CP x) y , ou CT = CM y + CP x É necessário acrescentar uma restrição para garantir que quando x > 0 então y = 1 e que quando y = 0 então x = 0: x ≤≤ M y, com M muito grande A própria natureza da função objectivo faz com que se x = 0 então y = 0, uma vez que se pretende minimizar o custo. y=      1, se houver produção (x>0) 0, se não houver produçã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 variáveis, Xmax = max {X1, X2, …, XN} pode ser expresso recorrendo-se a N variáveis binárias. Definem-se as variáveis binárias yk, k=1,…,N, tais que: e acrescenta-se a condição yk k N = ∑= 11, com cada yk ∈ {0, 1} que garante que Xmax apenas assume um valor. As restrições seguintes (1) Xmax ≥ Xk ∀k=1..N (2) Xmax ≤ Xk +M (1yk) garantem que Xmax virá igual ao máximo das variáveis consideradas. 3. ALGUNS PROBLEMAS TÍPICOS DE PI 3.1. PROBLEMA DE AFECTAÇÃO O Problema de Afectação (em inglês, Assignment Problem) é conhecido por este nome por ser a representação de inúmeras situações em que é necessário afectar pessoas a lugares, a tarefas ou a zonas de trabalho, máquinas a tarefas, etc. Aparece muitas vezes como se tratasse de um problema de PL mas, como veremos, as suas variáveis de decisão são binárias. Suponhamos que se pretende afectar n indivíduos a n tarefas, sabendo que a medida de eficiência de afectar o indivíduo i à tarefa j é cij (que tanto pode representar um lucro como um custo). Pretende-se determinar a afectação dos indivíduos às tarefas de modo a optimizar a eficiência total. As variáveis de decisão são as seguintes: yk=      1, se Xk é máximo 0, se Xk não é máximo Xij=     1, se o indivíduo i for afectado à tarefa j 0, se o indivíduo i não for afectado à tarefa j i=1, .., n j= 1,.., n 6 O modelo de PLI é como se segue : Trata-se, como se pode ver, de um modelo muito simples e cujo sistema de restrições tem uma estrutura particular com certas propriedades. Situações em que o número de indivíduos é diferente do número de tarefas podem também ser representadas. Um problema que seja representado por um modelo com esta estrutura chama-se problema de afectação, independentemente da situação que estiver a ser considerada. Conforme veremos mais adiante, os problemas de afectação dispõem de um método de resolução próprio graças à sua estrutura especial. 3.2. PROBLEMA DO CAIXEIRO VIAJANTE O Problema do Caixeiro Viajante (em inglês, Traveling Salesman Problem) é outro tipo de problema que pode ser representado por um modelo de PLI. Este problema é facilmente visto numa rede, em que as cidades correspondem aos nós ou vértices e os arcos representam as ligações entre as cidades. Consiste em encontrar um circuito que liga todas as cidades, ou seja, um conjunto de arcos que, partindo de um determinado vértice, passa por todos os outros uma e uma só vez e termina no vértice de partida. Conhecendo-se a distância ou o custo entre cada par de cidades (vértices), pretende-se determinar o circuito óptimo. As variáveis de decisão são as seguintes: O modelo de PLI é como se segue: Xij=     1, se a cidade j é visitada imediatamente após a cidade i 0, se a cidade j não é visitada imediatamente após a cidade i i=1, .., n j= 1,.., n min ou max cX ij ij ji ⋅ ∑∑      → optimizar a eficiência total suj. a: 1. cada indivíduo só pode estar afectado a uma tarefa: Xij j ∑ =∀= 1, i: i 1,2,3,4 2. cada tarefa só deve ser desempenhada por um indivíduo: Xij ij ∑ =∀1, j: =A, B, C, D Xij∈{0, 1} 13 2ª) A solução óptima do problema de PL após o arredondamento pode não ser admissível para o modelo de PLI (embora o modelo de PLI tenha soluções). Considere-se o seguinte modelo cuja representação gráfica se encontra na Figura 4.1: 3ª) A solução inteira (resultante do arredondamento da solução óptima do problema de PL) pode estar relativamente “afastada” da solução óptima do problema de PLI (sendo o “afastamento” medido em termos da função objectivo). Considere-se o seguinte modelo cuja representação gráfica está na Figura 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 inteiras max F = 35 x1 + 70 x2 suj. a: 3 x1 + 7 x2 ≤ 17 14 x1 -11 x2 ≤ 18.2 x1, x2 ≥ 0 e inteiras 1230 x1 x2 0 1 2 sentido do crescimento de F(x1, x2) Solução óptima do problema de PL (2.63, 1.38)(2.63, 1.38) Figura 4.1 - Nenhuma das quatro soluções obtidas por arredondamento é possível 14 Conclui-se assim pela necessidade de métodos que examinem apenas uma parte do conjunto de soluções admissíveis e que aproveitem as vantagens do algoritmo Simplex. Exactamente com estas características, existem dois métodos: o Método dos Planos de Cortes (Cutting Planes) e o Método de Partição e Avaliação Sucessivas (Branch and Bound). De facto, ambos utilizam o algoritmo Simplex para chegar à solução óptima de problemas de PL cuja região admissível vai sendo sucessivamente reduzida até se alcançar a solução do problema de PLI. Estes métodos são gerais, pois podem ser aplicados a qualquer modelo de PLI. Existem também métodos específicos, que apenas permitem resolver o tipo de problemas para os quais foram concebidos. É o caso, por exemplo, do Método Húngaro para o Problema de Afectação. Este método tira partido da estrutura especial do problema, sendo por isso mais eficiente que os métodos gerais. Finalmente, existem também métodos heurísticos para certos tipos de problemas. Estes algoritmos são bastante eficientes para certos problemas muito difíceis de resolver, embora a solução por eles encontrada não seja garantidamente óptima. Existem, por exemplo, várias heurísticas para o Problema do Caixeiro Viajante. Hoje em dia, graças aos avanços da tecnologia informática e a um continuado esforço de melhoria de eficiência dos algoritmos, é possível resolver de forma óptima problemas cada vez maiores. 4.2. MÉTODO DOS PLANOS DE CORTE O método dos Planos de Corte (Cutting Planes, em inglês) foi o primeiro método a ser desenvolvido e deve-se a Gomory (1958). Consiste em introduzir sucessivamente novas restrições na relaxação linear do PLI, restrições essas que cortam o conjunto das soluções possíveis eliminando algumas delas e a própria solução óptima do PL (por isso se chamam planos de corte), sem contudo eliminar qualquer solução inteira. sentido do crescimento de F(x1, x2) Solução arredondada F(2, 1)=140F(2, 1)=140 Solução óptima do problema de PL F(2.4, 1.4)=182F(2.4, 1.4)=182 Figura 4.2 - A solução inteira (obtida por arredondamento) não é a solução óptima do problema de PLI 1230 x1 x2 0 1 2 SOLUÇÃO INTEIRA ÓPTIMA F(1, 2)=175F(1, 2)=175 15 Consideremos o seguinte exemplo. António, proprietário da empresa de brinquedos “Toys ’r’ Tony”, decidiu criar uma secção de brinquedos tradicionais de madeira, começando por apenas dois tipos de brinquedos: pequenos cavalos de baloiço (lucro unitário de 2400$) e comboios antigos (lucro unitário de 1500$). Cada cavalo requer uma hora de trabalho e 9 m2 de madeira, enquanto que cada comboio requer uma hora de trabalho e 5 m2 de madeira. Supondo que estão disponíveis 6 horas de trabalho e 45 m2 de madeira, que quantidades fabricar de forma a maximizar o lucro? Variáveis de Decisão: x1= número de cavalos de baloiço fabricados x2= número de comboios fabricados O primeiro passo consiste na resolução da relaxação linear do PLI, que corresponde ao quadro simplex da Figura 4.3 e à representação gráfica da Figura 4.4: Figura 4.4 - Resolução da relaxação linear do problema de PLI Solução óptima do problema 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 x1x2f1f2 x110-1.25 0.25 3.75 x20 1 2.25 -0.25 2.25 -F 0 0 375 0.75 -12375 Figura 4.3 - Quadro SIMPLEX óptimo para a relaxação linear do problema de PLI O problema (de PI) será: max F = 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (horas de trabalho) 9x1 + 5 x2 ≤ 45 (madeira) x1, x2 ≥ 0 e inteiros 16 Como na solução óptima da relaxação linear os valores das variáveis não são inteiros, há que gerar um plano de corte. Para tal, basta considerar a restrição do quadro simplex óptimo da relaxação linear cujo termo independente tenha a parte fraccionária mais próxima de 0.5, e reescrever essa restrição separando a parte inteira da parte fraccionária. No exemplo considerado, qualquer das restrições pode ser considerada, uma vez que as partes fraccionárias de 3.75 e de 2.25 se encontram igualmente próximas de 0.5. Escolhendo a primeira restrição x1-1.25f1+0.25f2 = 3.75 e reescrevendo-a sob a forma [membro com coeficientes inteiros = membro com coeficientes fraccionários] ficase com x1-2f1-3 = 0.75-0.75f1-0.25f2. O novo plano de corte a acrescentar ao modelo traduz a restrição membro com coeficientes fraccionários ≤ 0 , ou seja, 0.75 - 0.75 f1 - 0.25 f2 ≤≤ 0 3 x1 +2 x2 ≤≤15 O novo modelo de PL a resolver é então max F = 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (horas de trabalho) 9x1 + 5 x2 ≤ 45 (madeira) 3 x1 +2 x2 ≤≤15 (plano de corte) x1, x2 ≥ 0 Como se pode analisar na Figura 4.5 a nova restrição “cortou” o conjunto das soluções possíveis, eliminando a solução óptima da relaxação linear, mas não eliminando qualquer solução inteira. Como a solução óptima deste novo modelo de PL é inteira, ela é a solução óptima do PLI. Se a solução encontrada ainda não fosse inteira, gerar-se-ia novo corte, e assim sucessivamente. ⇓ ⇑ (pela definição das variáveis de folga, f 1 =6-x 1 -x 2 e f 2 =45-9x 1 -5x 2 ) Figura 4.5 - Aplicação do plano de corte: a resolução do novo problema de PL conduz à solução óptima do problema de PLI inicial (5, 0) x2 5 3 2 1 6 4 7 9 8 6 5 4 3 2 1 x1 Solução óptima do novo problema F(5, 0)=12000 Solução óptima do problema de PL F(3.75, 2.25)=12375 17 Qualquer corte gerado por este método tem, então, duas propriedades: 1ª) Qualquer solução possível do PLI satisfaz o corte. 2ª) A solução óptima da relaxação linear não satisfaz o corte. Demonstra-se (Gomory, 1958) que se atinge a solução óptima do PLI após um número finito de cortes. Apesar desta propriedade o método dos planos de corte caiu em desuso, sendo muito pouco utilizado devido ao trabalho computacional envolvido na resolução de problemas de grandes dimensões. Embora o número de cortes seja finito, o seu número pode ser muito elevado (centenas ou milhares); de cada vez que se gera um novo corte acrescenta-se uma nova restrição ao modelo original, o que significa que a complexidade desse modelo é sempre crescente, podendo o trabalho computacional vir a tornar-se proibitivo apesar de se dispor de um algoritmo de resolução muito eficiente como é o simplex. Outra desvantagem deste método (quando comparado com o método de partição e avaliação sucessivas) é que se se interromper o método antes de ele chegar ao fim não se dispõe de qualquer solução inteira, ainda que não seja óptima. 4.3. MÉTODO DE PARTIÇÃO E AVALIAÇÃO SUCESSIVAS O método “Branch and Bound” (literalmente, método de ramificação e limitação) consiste na partição (ramificação) sucessiva do conjunto de soluções possíveis do problema de PLI em subconjuntos e na limitação (avaliação) do valor óptimo da função objectivo (limite inferior se se tratar de maximização, ou superior se se tratar de minimização), de modo a excluir os subconjuntos que não contenham a solução óptima. Partindo da constatação de que se, na solução óptima da relaxação linear dum problema de PLI, as variáveis tomam valores inteiros, então essa solução é a solução óptima do PLI, começa-se por resolver a relaxação linear do PLI inicial: se as variáveis que no problema de PLI são inteiras tomam, na solução óptima do PL, valores inteiros, então foi encontrada a solução óptima do PLI; caso contrário, divide-se o problema de PL em dois, através da introdução de restrições adicionais que fazem a partição do conjunto das soluções possíveis. Vão-se então resolvendo sucessivos problemas de PL, estabelecendo-se limites para o valor óptimo da função objectivo e, assim, eliminando diversos sub-conjuntos, até se alcançar a solução óptima do PLI. Ilustra-se seguidamente este método retomando o exemplo já usado anteriormente, no qual António, proprietário da empresa de brinquedos “Toys ’r’ Tony”, decidia criar uma secção de brinquedos tradicionais de madeira, começando por pequenos cavalos de baloiço e comboios antigos. As variáveis e o modelo, atrás definidos, eram os seguintes: Variáveis de Decisão: x1= número de cavalos de baloiço fabricados x2= número de comboios fabricados 18 O primeiro passo consiste na resolução da relaxação linear do PLI, o que foi feito graficamente na Figura 4.6: Desde já se sabe que o valor óptimo da função objectivo não pode exceder 12375. Como na solução óptima deste problema x1 e x2 não são inteiras, há a necessidade de efectuar a sua partição, dando origem a dois novos subproblemas (A e B), pela introdução de novas restrições de eliminação de soluções não-inteiras: x1 ≤ 3 e x1 ≥ 4 (Figura 4.7). Poder-se-ia escolher fazer a partição segundo a variável x2. A: max F = 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (horas de trabalho) 9x1 + 5 x2 ≤ 45 (madeira) x1≤3 x1, x2 ≥ 0 B: max F = 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (horas de trabalho) 9x1 + 5 x2 ≤ 45 (madeira) x1≥4 x1, x2 ≥ 0 x2 5321 64 7 9 8 6 5 4 3 2 1 x1 Solução óptima do problema de PL F(3.75, 2.25)=12375 Figura 4.6 - Resolução da relaxação linear do problema PLI max F = 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (horas de trabalho) 9x1 + 5 x2 ≤ 45 (madeira) x1, x2 ≥ 0 e inteiros 19 A solução óptima do subproblema A é inteira, o que significa que se encontrou uma solução inteira cujo valor da função objectivo é 11700. O valor óptimo da função objectivo estará compreendido entre estes dois limites, 11700 ≤ F ≤ 12375. Como a solução óptima do subproblema B não é inteira e o valor da função objectivo é 12300 (>11700), este subproblema pode conter uma solução inteira melhor que a do subproblema A; logo, é necessário efectuar a sua partição, dando origem aos subproblemas B1 e B2, pela introdução das restrições x2 ≥ 2 e x2 ≤ 1 (Figura 4.8). Os novos subproblemas são da forma: B1:max F= 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (horas de trabalho) 9x1 + 5 x2 ≤ 45 (madeira) x1≥4 x2≥2 x1, x2 ≥ 0 B2:max F = 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (horas de trabalho) 9x1 + 5 x2 ≤ 45 (madeira) x1≥4 x2≤1 x1, x2 ≥ 0 Figura 4.7 - Primeira partição: introduzindo, no problema de PL inicial, a restrição x1 ≤ 3 obtém-se o subproblema A(cuja solução óptima é inteira) e introduzindo a restrição x1 ≥ 4 obtém-se o subproblema B (cuja solução óptima ainda não é inteira, pelo que se tem de continuar a partição). x2 5321 64 7 9 8 6 5 4 3 2 1 x1 A B Solução óptima do subproblema B F(4, 1.8)=12300 Solução óptima do subproblema A F(3, 3)=11700 20 O subproblema B1 não tem soluções possíveis, sendo por isso excluído. O subproblema B2, pelas mesmas razões do subproblema B, é objecto de partição e dá origem aos subproblemas B21 e B22, pela introdução das restrições x1 ≤ 4 e x1 ≥ 5 (Figura 4.9): B21:max F = 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (horas de trabalho) 9x1 + 5 x2 ≤ 45 (madeira) x1 ≥ 4 x2 ≤ 1 x1 ≤ 4 x1, x2 ≥ 0 B22:max F = 2400 x1 +1500 x2 suj. a: x1 + x2 ≤ 6 (horas de trabalho) 9x1 + 5 x2 ≤ 45 (madeira) x1 ≥ 4 x2 ≤ 1 x1 ≥ 5 x1, x2 ≥ 0 x1 = 4 x1 ≥ 5 Figura 4.8 - Segunda partição: introduzindo, no subproblema B, a restrição x2 ≥ 2 ficamos com o subproblema B1(solução impossível) e introduzindo a restrição x2 ≤ 1 ficamos com o subproblema B2 (solução ainda não é inteira, pelo que se tem de continuar a partição). x2 5321 64 7 9 8 6 5 4 3 2 1 x1 A B2 Solução óptima do subproblema B2 F(4.4, 1)=12167 Solução óptima do subproblema A F(3, 3)=11700 21 Quer o subproblema B21 quer o subproblema B22 têm soluções inteiras. O valor óptimo da função objectivo do subproblema B21 é 11100, menor que 11700, ou seja, pior do que a solução de que já dispúnhamos. O valor óptimo da função objectivo do subproblema B22 é 12000, logo actualizamos os limites e teremos 12000 ≤ F ≤ 12000. A sequência total das partições é particularmente evidente no seguinte diagrama, estruturado em forma de árvore (Figura 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 Subproblema impossível (x1, x2)= (5, 0) F B22 = 12000 (x1, x2)= (4, 1) F B21 = 11100 SOLUÇÃO ÓPTIMA Figura 4.10 - Árvore final do método “Branch and Bound” para o exemplo apresentado Figura 4.9 - Terceira partição: introduzindo, no subproblema B2, a restrição x1 ≥ 5 ficamos com o subproblema B21 e introduzindo a restrição x1 ≤ 4 ficamos com o subproblema B22: todas as soluções são já inteiras, não havendo a necessidade de efectuar mais nenhuma partição. A solução óptima do problema de PLI é (x1, x2) = (5, 0). x2 5321 64 7 9 8 6 5 4 3 2 1 x1 ASolução óptima do subproblema B22 F(5, 0)=12000 Solução óptima do subproblema A F(3, 3)=11700 Solução óptima do subproblema B21 F(4, 1)=11100 22 À medida que se vai “descendo” na árvore da Figura 4.10 vão-se actualizando os limites inferior e superior ao valor óptimo da função objectivo (F*). No nó inicial (raiz da árvore), 0 ≤ F* ≤ 12375. Ao nível dos subproblemas A e B, 11700 ≤ F* ≤ 12300. No nível imediatamente inferior, 11700 ≤ F* ≤ 12167. Por fim, no quarto e último nível, 12000 ≤ F* ≤ 12000. Podemos então concluir que (x1, x2) = (5, 0), F* = 12000 é a solução óptima, não fazendo sentido efectuar qualquer nova partição. Vemos assim que: (1) É efectuada a partição de um subproblema em cuja solução óptima exista pelo menos uma variável que, sendo uma variável inteira no PLI inicial, assuma valores não-inteiros, se esse subproblema puder conter uma solução inteira melhor do que a já existente. (2) São logo eliminados os subproblemas que não tenham soluções possíveis ou que não possam conter uma solução possível melhor do que a já existente. Para além de ser, de um modo geral, menos trabalhoso resolver um modelo de PLI através deste método do que através do método dos planos de corte, ele apresenta a vantagem de ser possível interromper o método antes de encontrar a solução óptima e de dispor de uma solução inteira, em relação à qual se pode ter uma ideia de quão próxima estará da solução óptima graças aos limites que se vão determinando. 5. BIBLIOGRAFIA Garfinkel, Robert S. and George L. Nemhauser (1972), Integer Programming, John Wiley & Sons, Inc. Hadley, George (1974), Linear Programming, Eighth Printing, Addison-Wesley. Hadley, George (1972), Nonlinear and Dynamic Programming, Second Printing, Addison-Wesley. Hillier, G. and J. Lieberman (1995), Introduction to Operations Research, Sixth Edition, McGraw-Hill. Ramalhete, Manuel, Jorge Guerreiro e Alípio Magalhães (1984), Programação Linear, Vol. I e Vol. II, Editora McGraw-Hill de Portugal. Winston, Wayne L. (1994), Operations Research – Applications and Algorithms, Third Edition, Duxbury Press. Wu, Nesa and Richard Coppins (1981), Linear Programming and Extensions, McGrawHill.