Atividade de Programação Linear

UNIVERSIDADE FEDERAL DE OURO PRETO DEENP ICEA GRADUAÇÃO EM ENGA DE PRODUÇÃO 20242 ENP160 Otimização Combinatória Lista de Exercícios de Programação Linear Método Simplex Teoria da Dualidade Princípio de Decomposição de DantzigWolfe Parte Ia Programação Linear Algoritmo SIMPLEX Questão 1 Seja o problema abaixo onde se lê os estados inicial e final do algoritmo SIMPLEX nas tabela2 1 e 2 Perguntase a Considerando o que o algoritmo SIMPLEX é sempre escrito para minimização isto é que custos reduzidos positivos indicam potencial de melhora a partir da base corrente porque se pode afirmar que a tabela 2 é ótima b Escreva as condições de complementariadade de folgas para o problema Sabendo os valores ótimos para as variáveis primais x é possível calcular os valores ótimos das variaveis duais u Como É possível ler diretamente os valores ótimos das variáveis duais na tabela 2 Onde Porquê c Baseandose na ideia de que restrições folgadas correspondem a variáveis duais nulas na solução ótima qual restrição está folgada É possível ler isso diretamente na tabela d Quanto o preço do produto 3 precisaria subir para que o mesmo estivesse no mix de produção ótimo Qual é o custo de produção desse ítem e E se tentassemos considerar um produto 4 tal que a4 3 2 1T Ele seria economicamente viável a partir de qual preço de mercado f Em caso de choque de demanda qual seria o valor de demanda máxima para centenas de caixas de copos de 6 oz que alteraria a solução corrente E no cenário oposto qual seria o impacto se a demanda total por copos de 6 oz aumentasse de 8 para 14 centenas de caixas Onde investir para ganhar mais g Qual seria o significado de obter um custo reduzido de uma variável nãobásica igual a zero Questão 2 Considerando o Programa Linear dado abaixo Seja ainda a solução x 3 92 0 1 32 cujo valor de x0 é 36 Responda a Esta solução é ótima b Esta solução é é básica Questão 3 Dado o programa linear abaixo prove que o espaço de soluções do mesmo é não vazio e que todas as suas variáveis x são limitadas superiormente Parte Ib Teoria da Dualidade em Programação Linear Questão 1 Seja um Programa Linear PL P genérico escrito em forma canônica Aplique a Teoria da Dualidade ao PL P acima e obtenha as condições de otimalidade para Programação Linear Questão 2 Partindo do PL P genérico dado na questão 1 prove que o dual do dual de P é o próprio P Questão 3 Sabendose que o estado de uma restrição Dual de um PL genérico P é folgado qual será o valor da variável Primal correspondente Sabendose que o estado de uma variável Dual é nãobásica o que se pode afirmar sobre o valor da variável de folga da restrição Primal correspondente Parte Ic Produzindo o Programa Linear Dual Questão 1 Sejam as formulações dadas abaixo Produza os programas duais de suas relaxações de PL a Facility Location Problem Considere a Relaxação Linear b Problema de Transbordo c Problema de Atribuição d Problema de Fluxo Máximo e Problema de Caminho Mínimo f Problema de Atribuição Generalizado g Problema de Projeto de Redes com Carga Fixa Parte II Otimização de Grande Escala e Princípio de Decomposição Questão 1 Obtendo as formas algébricas do Programa Mestre de DantzigWolfe e o do Subproblema Gerador de Collunas a Seja o problema de LotSizing Capacitado Multiproduto Considerando as restrições 29 como complicantes produza o ProgramaMestre de DantzigWolfe e o Subproblema Gerador de Colunas para 26210 b Para a formulação de Localização de Hubs abaixo considerando as restrições 3 como complicantes repita o procedimento da questão a Questão 2 a Seja o PL de estrutura blocodiagonal generalizado dado a seguir Produza as expressões do Programa Mestre e do Subproblema de DantzigWolfe para o Mesmo b Faça o mesmo para os problemas dados a seguir i ii iii Instruções de Execução Ao trabalhar a lista de exercícios o estudante precisa ter em mente que ele deve comprender a solução dos exercícios com profundidade Auf Wiedersehen Senhores Problema de Programacao Linear Funcao Objetivo Maximizar z 5x1 45x2 6x3 em centenas de dolares Restricoes 6x1 5x2 8x3 60 capacidade de producao horas 10x1 20x2 10x3 150 capacidade de armazenamento centenas de pes quadrados x1 8 demanda para copos de 6 oz centenas de caixas x1 x2 x3 0 naonegatividade Tableau Inicial Variaveis Basicas Valores Atuais x1 x2 x3 x4 x5 x6 x4 60 6 5 8 1 0 0 x5 150 10 20 10 0 1 0 x6 8 1 0 0 0 0 1 z 0 5 45 6 0 0 0 Tableau Final Variaveis Basicas Valores Atuais x1 x2 x3 x4 x5 x6 x2 4 2 7 1 2 7 1 7 3 35 1 x6 1 4 7 11 7 2 7 1 14 1 x1 6 3 7 1 11 7 2 7 1 14 1 z 51 3 7 4 7 11 14 1 35 1 1 Resolucao Considere o problema de maximizacao Maximizar z 5x1 45x2 6x3 em centenas de dolares sujeito a 6x1 5x2 8x3 60 capacidade de producao em horas 10x1 20x2 10x3 150 capacidade de armazenamento em centenas de pes quadrados x1 8 demanda para copos de 6 oz em centenas de caixas x1 x2 x3 0 Na formulacao do SIMPLEX introduzimos as variaveis de folga x4 x5 x6 para transformar as restricoes em igualdades obtendo o tableau inicial Em seguida apos algumas iteracoes obtemos o Tableau 2 solucao final cuja parte relevante e ilustrada a seguir Variaveis Basicas Valores Atuais x1 x2 x3 x4 x5 x6 x2 4 2 7 1 2 7 1 7 3 35 1 x6 1 4 7 11 7 2 7 1 14 1 x1 6 3 7 1 11 7 2 7 1 14 1 z 51 3 7 4 7 11 14 1 35 1 Nos itens seguintes utilizaremos este tableau e os valores nele contidos para justificar cada resposta a Otimalidade do Tableau 2 No algoritmo SIMPLEX na forma minimizacao a condicao de otimalidade e satisfeita quando nenhum dos custos reduzidos coeficientes na linha z e positivo Ou seja se escrevemos a funcao objetivo na forma z um coefi ciente positivo indicaria que ao introduzir a variavel correspondente na base poderıamos melhorar no sentido de diminuir z ou aumentar z o valor da funcao objetivo Na Tabela 2 observamos que o coeficiente da coluna x3 na linha z e 4 7 e os demais tambem nao sao positivos Assim nao existe direcao de melhoria Portanto podemos afirmar que a solucao corrente e otima 2 b Condicoes de Complementaridade e Val ores Duais Condicoes de Complementaridade Para cada restricao do problema suponha que os multiplicadores ou precos sombra sejam u1 u2 e u3 associados respectivamente as restricoes label6x1 5x2 8x3 60 capacidade de producao 10x1 20x2 10x3 150 capacidade de armazenamento x1 8 demanda para copos de 6 oz As condicoes de complementaridade ou de folga dizem que ui folga da restricao i 0 i 1 2 3 Ou seja se uma restricao e apertada folga igual a zero o respectivo ui pode ser positivo se a restricao e folgada folga positiva entao ui 0 Calculo dos Valores Duais Os valores otimos dos duais podem ser obtidos a partir da linha z do tableau final Em problemas formulados na forma padrao ou adaptados para minimizacao os coeficientes das colunas dos slacks variaveis de folga nao basicas na linha z com sinal invertido correspondem aos precos sombra Por exemplo se o slack x4 associado a restricao 1 nao estiver na base e o seu coeficiente na linha z for 11 14 entao u1 11 14 Contudo se a variavel de folga estiver na base como ocorre em alguns ca sos o preco sombra associado e zero por complementaridade Assim nem sempre os valores duais podem ser lidos diretamente do tableau para todas as restricoes c Identificacao da Restricao Folgada Temos as trˆes restricoes Observe que na solucao otima x1 63 7 obtido na Tabela 2 3 A restricao de demanda para copos de 6 oz e x1 8 Calculando a folga Folga 8 63 7 11 7 0 Portanto a restricao relativa a x1 8 esta folgada e pela condicao de complementaridade o preco sombra u3 associado deve ser zero Leitura no Tableau Na Tabela 2 o slack associado a restricao de demanda e a variavel x6 Como x6 aparece como variavel basica nao se pode identificar diretamente o valor de u3 na linha z Assim concluise que pela complementaridade u3 0 d Sensibilidade do Preco do Produto 3 e o Custo de Producao O produto 3 tem na funcao objetivo coeficiente c3 6 centenas de dolares Na Tabela 2 x3 e naobasica ou seja x3 0 e seu custo reduzido na linha z e c3 4 7 Lembrese que na forma de minimizacao um custo reduzido positivo indica que ha potencial de melhoria ao entrar na base Neste caso como o custo reduzido e negativo entendese que a solucao otima nao inclui o produto 3 Para que o produto 3 entre na base e necessario que o seu custo reduzido se torne zero Em termos de sensibilidade deve ocorrer cnovo 3 custo dos recursos 0 O custo dos recursos para o produto 3 e dado pela combinacao dos precos sombra dos recursos consumidos Se o produto 3 consome por exemplo 8 unidades do recurso 1 e 10 unidades do recurso 2 conforme o coeficiente na restricao entao Custo dos recursos 8u1 10u2 4 Utilizando os valores do tableau suponha u1 1114 u2 135 Calculando 8u1 10u2 81114 10135 8814 1035 447 27 467 6571 O custo reduzido de x3 é c3 8u1 10u2 6 467 47 Assim para que esse custo reduzido se torne zero o coeficiente c3 deve aumentar em Δc3 47 centenas de dólares o que equivale aproximadamente a 5714 dólares Custo de produção do item 3 Pode ser interpretado como o custo dos recursos consumidos isto é Custo de produção 8u1 10u2 467 centenas de dólares e Viabilidade Econômica do Produto 4 Considere um produto 4 com vetor de coeficientes a4 3 2 1T Para que este produto seja economicamente viável o seu preço de mercado ou lucro unitário c4 deve ser no mínimo igual ao custo dos recursos consumidos ou seja c4 3u1 2u2 1u3 Como vimos a restrição 3 está folgada e portanto u3 0 Utilizando os mesmos valores para u1 e u2 3u1 2u2 31114 2135 3314 235 Para somar escrevemos em denominador comum 3314 33570 16570 235 2270 470 Logo 3u1 2u2 16570 470 16970 24143 centenas de dólares Portanto o produto 4 será economicamente viável se o seu preço de mercado for no mínimo 16970 centenas de dólares aproximadamente 24143 dólares f Impacto de Choques na Demanda A restrição referente à demanda para copos de 6 oz é x1 8 centenas de caixas Na solução ótima temos x1 6 37 643 centenas Portanto a folga nesta restrição é 8 6 37 117 157 centenas de caixas Choque para Redução da Demanda Se a demanda diminuir o lado direito RHS da restrição poderá se tornar menor do que o valor ótimo atual de x1 A solução corrente será afetada se o novo RHS for inferior a 6 37 Assim a demanda máxima no sentido de redução que manteria a solução é exatamente 8 117 6 37 centenas de caixas Choque para Aumento da Demanda Se a demanda aumentar por exemplo de 8 para 14 centenas de caixas a restricao permanece folgada pois x1 continua sendo 63 7 isto indica que a restricao de demanda nao esta limitando a solucao Assim o aumento da demanda nao altera a solucao otima Investimento para Aumentar o Lucro Como as restricoes que deter minam a producao otima sao as de capacidade de producao e armazenamento que estao apertadas investir em ampliar esses recursos podera permitir pro duzir mais produtos com maior contribuicao ao lucro g Interpretacao de um Custo Reduzido Zero para Variavel NaoBasica Quando o custo reduzido de uma variavel naobasica e igual a zero isso significa que 123 A solucao otima corrente e indiferente a entrada desta variavel na base ou seja sua entrada nao altera o valor otimo da funcao objetivo Existe multiplicidade de solucoes otimas podemos encontrar outras solucoes otimas em que essa variavel assume valor positivo sem que haja alteracao no valor de z Portanto um custo reduzido igual a zero indica que ha alternativas otimas e que o problema possui solucoes degeneradas quanto a escolha das variaveis basicas Resumo 1 Otimalidade A Tabela 2 e otima porque na forma de minimizacao do SIMPLEX nao ha nenhum custo reduzido positivo entre as variaveis naobasicas 2 Complementaridade e Duais 7 As condicoes de complementaridade sao uifolga da restricao i 0 para i 1 2 3 Os valores duais podem ser obtidos a partir da linha z para os slacks naobasicos com sinal invertido Se o slack estiver na base o respectivo ui e zero 3 Restricao Folgada A restricao x1 8 esta folgada pois x1 6 3 7 implicando u3 0 Essa informacao nao e lida diretamente do tableau pois o slack x6 esta na base 4 Produto 3 O custo reduzido de x3 e 4 7 Assim para que x3 entre na base seu coeficiente c3 deve aumentar em 4 7 centenas de dolares aprox imadamente 5714 dolares O custo de producao custo dos recursos do item 3 e 8u110u2 46 7 centenas de dolares 5 Produto 4 Um produto 4 com vetor a4 3 2 1T sera economica mente viavel se o seu preco c4 for no mınimo 3u1 2u2 1u3 169 70 aproximadamente 24143 dolares 6 Choques na Demanda Se a demanda para x1 copos de 6 oz cair abaixo de 63 7 centenas a solucao otima sera alterada Se a demanda aumentar a restricao permanece folgada e a solucao nao muda Para aumentar o lucro convem investir na ampliacao dos recursos das restricoes que estao limitando producao e ar mazenamento 7 Custo Reduzido Zero Um custo reduzido nulo para uma variavel naobasica indica que a entrada dessa variavel na base nao alteraria o valor otimo da funcao objetivo sinalizando a existˆencia de multiplas solucoes otimas 8 QUESTAO 2 Considere o seguinte Programa Linear P Maximizar x0 6x1 4x2 sujeito às restrições 3x1 2x2 x3 18 1 x1 x4 4 2 x2 x5 6 3 com xj 0 j 1 2 3 4 5 Considere ainda a solução x x1 x2 x3 x4 x5T 3 92 0 1 32T a qual produz o valor objetivo x0 6 3 4 92 18 18 36 Responda labelEsta solução é ótima Esta solução é básica 2 Restricao 2 3 1 4 3 Restricao 3 9 2 3 2 12 2 6 Como todas as restricoes sao satisfeitas a solucao e factıvel a Otimalidade da Solucao Note que as variaveis x3 x4 e x5 sao variaveis de folga ou artificiais que transformam o sistema de desigualdades em igualdades Assim podemos interpretar o problema nos termos das variaveis originais x1 e x2 observando que Da restricao 2 x1 x4 4 e como x4 0 obtemos x1 4 Da restricao 3 x2 x5 6 e como x5 0 obtemos x2 6 Da restricao 1 3x12x2x3 18 e como x3 0 temos 3x12x2 18 Assim o problema equivalente em x1 x2 e Maximizar 6x1 4x2 sujeito a x1 4 x2 6 3x1 2x2 18 x1 x2 0 Observamos que o gradiente da funcao objetivo e 6 4 e o gradiente da restricao 3x1 2x2 18 e 3 2 Note que 6 4 2 3 2 ou seja a funcao objetivo e linearmente dependente da restricao ativa 3x1 2x2 18 Isso implica que todos os pontos que satisfazem 3x1 2x2 18 dentro da regiao factıvel produzem o mesmo valor de x0 Verifiquemos isso em dois extremos da face 10 1 Se x1 4 então 34 2x2 18 x2 18 12 2 3 O valor objetivo é 6 4 4 3 24 12 36 2 Se x2 6 então 3x1 26 18 3x1 6 x1 2 O valor objetivo é 6 2 4 6 12 24 36 Portanto todos os pontos da reta 3x1 2x2 18 que estiverem na região factível atingem o valor x0 36 A solução proposta possui x1 3 x2 92 45 e satisfaz 33 2 92 9 9 18 Logo ela pertence à face ótima Conclusão a A solução é ótima pois é factível e atinge o valor máximo x0 36 b Basicidade da Solução Em problemas lineares na forma padrão com m equações e n variáveis aqui m 3 e n 5 uma solução básica ou extremal é obtida ao selecionar um conjunto de m colunas linearmente independentes chamadas de variáveis básicas atribuindo o valor zero às demais variáveis nãobásicas Em uma solução básica não degenerada teremos exatamente m variáveis positivas Na solução proposta temos x1 3 0 x2 45 0 x3 0 x4 1 0 x5 15 0 Observase que quatro variaveis sao positivas ou seja ha mais de m 3 variaveis positivas Mesmo considerando degenerescˆencia em que alguma variavel basica pode ser zero o numero de variaveis basicas nao pode exceder m Geometricamente ao analisarmos o espaco x1 x2 a regiao factıvel e um polıgono convexo Os vertices ou extremos desse polıgono correspondem as solucoes basicas A face otima identificada e o segmento de reta entre os pontos extremos 4 3 e 2 6 Como a solucao 3 45 e uma combinacao convexa desses extremos ela nao corresponde a um vertice da regiao factıvel Conclusao b A solucao nao e basica pois nao corresponde a um vertice extremo do conjunto factıvel QUESTAO 3 Considere o seguinte problema linear P Maximizar z 4x1 3x2 2x3 3x4 x5 sujeito a 3x1 2x2 x3 2x4 x5 13 5x1 4x2 3x3 4x4 x5 25 xj 0 j 1 2 3 4 5 1 Espaco de Solucoes Nao Vazio Para provar que o conjunto de solucoes e nao vazio basta encontrar uma solucao factıvel Passo 1 Subtraımos a primeira equacao da segunda 5x1 4x2 3x3 4x4 x5 3x1 2x2 x3 2x4 x5 25 13 2x1 2x2 2x3 2x4 12 x1 x2 x3 x4 6 Passo 2 Da primeira equacao temos x5 13 3x1 2x2 x3 2x4 Escolhemos por exemplo x1 0 x2 6 x3 0 x4 0 12 Verificase que x1 x2 x3 x4 6 Calculando x5 x5 13 3 0 2 6 0 2 0 13 12 1 Como x5 1 0 e todos os xj 0 esta e uma solucao factıvel Portanto o espaco de solucoes nao e vazio 2 Variaveis Limitadas Superiormente Para x1 x2 x3 e x4 Da equacao x1 x2 x3 x4 6 temos que como cada xj 0 para j 1 2 3 4 cada uma destas variaveis deve ser no maximo 6 Assim 0 xj 6 j 1 2 3 4 Para x5 Da equacao x5 13 3x1 2x2 x3 2x4 como x1 x2 x3 x4 0 temos x5 13 Portanto 0 x5 13 Conclusao O conjunto de solucoes e nao vazio e as variaveis x1 x2 x3 x4 sao limitadas superiormente por 6 enquanto x5 e limitada por 13 Parte Ib Teoria da Dualidade em Programacao Linear 01 QUESTAO 1 Considere o problema primal P min cTx sujeito a Ax b x 0 13 onde x Rn é o vetor de variáveis c Rn é o vetor de custos A Rmn é a matriz dos coeficientes b Rm é o vetor do lado direito 1 Formulação do Problema Dual O problema dual associado é max bT y sujeito a AT y c y 0 onde y Rm é o vetor de variáveis dual 2 Condições de Otimalidade Sejam x e y soluções ótimas do primal e do dual respectivamente Então as condições de otimalidade são a Viabilidade Primal A x b e x 0 b Viabilidade Dual AT y c e y 0 c Condições de Complementaridade yi A xi bi 0 para i 1 2 m xj cj AT yj 0 para j 1 2 n Estas condições são necessárias e suficientes para que x e y sejam respectivamente soluções ótimas do problema primal e do dual conforme estabelecido pela Dualidade Forte em Programação Linear QUESTAO 2 Seja o problema primal P min cTx sujeito a Ax b x 0 com x Rn c Rn A Rmn e b Rm O dual de P e D max bTy sujeito a ATy c y 0 com y Rm Passo 1 Obtencao do Dual de D Escrevemos o Lagrangiano de D Ly x bTy xTc ATy xTc yTb Ax onde x Rn sao os multiplicadores associados as restricoes ATy c Para que a maximizacao em y com y 0 seja finita devese ter b Ax 0 Ax b Com essa condicao a maximizacao em y resulta em sup y0 Ly x xTc Passo 2 Formulacao do Dual do Dual Portanto o dual de D e min xTc sujeito a Ax b x 0 Observase que essa formulacao coincide exatamente com a do problema P Conclusao O dual do dual de P e o proprio P o que demonstra a propriedade de involutividade da dualidade em Programacao Linear 15 Questão 3 As condições de complementaridade entre um problema primal e seu dual dizem que xj cj AT yj 0 j 1 n yi A xi bi 0 i 1 m a Restrição Dual Folgada Se uma restrição dual está folgada isto é para algum índice j AT yj cj temos cj AT yj 0 Pela condição complementar de xj xj cj AT yj 0 concluímos que para que o produto seja zero deve ser xj 0 Portanto se a restrição dual está folgada a variável primal correspondente é igual a zero b Variável Dual NãoBásica Considere agora que uma variável dual yi está nãobásica ou seja yi 0 No problema primal suponha que a restrição i com A xi bi seja convertida em igualdade adicionando uma variável de folga si A xi si bi si 0 A condição complementar associada é yi si 0 Como yi 0 essa igualdade é satisfeita independentemente do valor de si Contudo em uma solução ótima típica não degenerada se o dual yi é nãobásico ou seja yi 0 isso indica que a restrição primal correspondente não está ativa ou seja a folga é estritamente positiva si 0 Em resumo se a variável dual é nãobásica a variável de folga da restrição primal correspondente normalmente terá valor positivo Parte Ic Produzindo o Programa Linear Dual a Facility Location Problem Primal minxy sumi1m sumj1n cij xij sumi1m fi yi sujeito a sumi1m xij 1 j1n xij leq yi i1m j1n xij geq 0 yi geq 0 Dual Usando uj para as igualdades e vij geq 0 para xij leq yi maxuv sumj1n uj sujeito a uj vij leq cij forall i1m j1n sumj1n vij leq fi forall i1m vij geq 0 uj in R b Problema de Transbordo Primal minx sumi1m sumj1m cij xij sujeito a sumj1m xij sumk1m xki bi i1m xij geq 0 forall ij Dual Usando yi livre para cada equilíbrio maxy sumi1m bi yi sujeito a yi yj leq cij forall ij yi in R c Problema de Atribuição Primal minx sumi1m sumj1m cij xij sujeito a sumj1m xij 1 i1m sumi1m xij 1 j1m xij geq 0 forall ij Dual Usando ui e vj para as restrições das linhas e colunas respectivamente maxuv sumi1m ui sumj1m vj sujeito a ui vj leq cij forall ij uivj in R d Problema de Fluxo Máximo Primal maxxf f sujeito a sumj1m xij sumk1m xki begincases f i1 0 i2m1 f im endcases xij leq uij xij geq 0 Dual A dual deste LP resulta na formulação do min cut Usando vi para as equações de conservação e zij geq 0 para as capacidades minzv sumij uij zij sujeito a vi vj zij geq 0 forall ij v1 vm 1 zij geq 0 vi in R e Problema de Caminho Mínimo Primal minx sumi1m sumj1m cij xij sujeito a sumj1m xij sumk1m xki begincases 1 i1 0 i2m1 1 im endcases xij geq 0 forall ij Dual Usando yi para cada nó maxy y1 ym sujeito a yi yj leq cij forall ij yi in R f Problema de Atribuição Generalizado Primal minx i1m j1n cij xij sujeito a i1m xij 1 j1n j1n aij xij bi i1m xij 0 ij Dual Usando uj para as igualdades e vi 0 para as desigualdades maxuv j1n uj i1m bi vi sujeito a uj cij aij vi i1m j1n vi 0 uj R g Problema de Projeto de Redes com Carga Fixa Primal minxy ijA kK cijk xijk fij yij sujeito a jijA xijk jjiA xjik dk i Ok 0 i OkDk dk i Dk k K i xijk dk yij ij A k K xijk 0 ij A k K yij 0 Variáveis dual Para cada fluxo de commodity k e nó i associe uik R Para cada desigualdade xijk dk yij associe vijk 0 20 Dual maxuv kK dk uOkk uDkk sujeito a cijk uik ujk vijk 0 ij A k K fij kK dk vijk 0 ij A vijk 0 uik R 1 Parte II Otimização de Grande Escala e Princípio de Decomposição 11 Questão 1 Obtendo as formas algébricas do Programa Mestre de DantzigWolfe e o do Subproblema Gerador de Collunas 12 ITEM B As restrições mmk xijmk m xijkm wij yk ij N k H 4 são tratadas como complicantes isto é as que dificultam a resolução do problema A ideia central da decomposição de DantzigWolfe é separar essas restrições de ligação das demais que definem uma estrutura fácil ou decomponível 21 2 Formulação Original do Problema O modelo de Localização de Hubs considerado é dado por min kH ak yk iN jN kH mH cijkm xijkm 5 sujeito a mmk xijkm mH xijkm wij yk ij N k H 6 kH mH xijkm wij ij N 7 xijkm 0 ij N km H 8 yk 01 k H 9 Nas restrições 6 as variáveis x relacionadas ao fluxo estão ligadas às variáveis y decisão de abertura de hubs Essa ligação dificulta a resolução direta do problema 3 Passo a Passo Decomposição de DantzigWolfe Para aplicar a decomposição realizamos os seguintes passos 31 i Identificação da Estrutura Fácil os Subproblemas Note que se relaxarmos as restrições complicantes 6 para cada par de nós ij N N os fluxos xijkm devem satisfazer kH mH xijkm wij xijkm 0 Esse conjunto denotado por Xij xij RHH kH mH xijkm wij 22 é basicamente um simplex escalado Seus pontos extremos são bastante simples para cada i j cada ponto extremo corresponde a enviar todo o fluxo wij através de um único par k m Denotamos por Pij o conjunto dos índices das colunas ou pontos extremos para a commodity i j Para cada p Pij identificamos a coluna com o par kp mp e definimos xijpkm wij se km kp mp 0 caso contrário Dessa forma qualquer solução viável para a commodity i j pode ser escrita como uma combinação convexa desses pontos extremos xijkm pPij λijp xijpkm com pPij λijp 1 λijp 0 32 ii Reescrevendo as Restrições Complicantes A restrição complicante 6 para cada i j N e k H é mk xijmk mH xijkm wij yk Substituindo a decomposição dos x pela combinação convexa temos pPij λijp 1kpk fluxo saindo de k 1kpk e mpk fluxo chegando em k wij wij yk Assumindo wij 0 dividindo ambos os lados por wij obtemos pPij λijp 1kpk 1kpk e mpk yk i j N k H 10 Essa restrição é a que liga as decisões locais variáveis λijp com a decisão global de abertura dos hubs yk 33 iii Formulação do Programa Mestre A formulação do Programa Mestre que combina as soluções dos subproblemas tornase min kH ak yk ijN² pPij λijp cijp 11 sujeito a pPij λijp 1 ij N² 12 pPij λijp 1kpk 1kp k e mp k yk ij N² k H 13 λijp 0 ij N² p Pij 14 yk 01 k H 15 onde cijp cijkpmp wij é o custo de enviar o fluxo wij utilizando a rota definida pelo par kp mp 34 iv Definição do Subproblema Gerador de Colunas Após resolver a relaxação por exemplo a relaxação linear do Programa Mestre ou durante um esquema de branchandprice é necessário verificar se existe alguma coluna isto é uma solução local para uma commodity i j que possa melhorar o valor da função objetivo Para tanto definimos os multiplicadores preços duais σij associado à restrição de convexidade 12 para cada i j πijk associado à restrição de ligação 13 para cada i j e para cada k H Para cada commodity i j uma coluna pura corresponde a escolher um par k m isto é utilizar a coluna p com kp k e mp m que tem custo cijkm wij e que contribui com coeficiente 1 na restrição para yk se kp k e com coeficiente 1 na restrição para ym se mp m e m k Assim o custo reduzido associado à coluna k m é dado por cijkm cijkm wij σij πijk πijm se m k 0 se m k 16 O subproblema gerador de colunas para a commodity i j consiste em minkmHH cijkm wij πijk πijm 1mk σij 17 Se o valor ótimo deste subproblema for negativo a coluna correspondente isto é o par k m encontrado deve ser adicionada ao Programa Mestre 4 Resumo Final Para resumir os passos para a aplicação da decomposição de DantzigWolfe ao problema de Localização de Hubs são os seguintes 1 Reformulação dos Fluxos Para cada commodity i j representamos os fluxos xijkm como uma combinação convexa dos pontos extremos do conjunto Xij xijkm pPij λijp xijpkm pPij λijp 1 λijp 0 2 Programa Mestre O modelo reformulado onde as restrições complicantes de ligação com as variáveis yk aparecem na forma pPij λijp 1kpk 1kp k e mp k yk i j N k H e o objetivo tornase min kH ak yk ijN² pPij λijp cijp 3 Subproblema Gerador de Colunas Para cada commodity ij dado os multiplicadores σij e πijk resolvese minkmHH cijkm wijm πijk πijm 1mk σij Se o custo reduzido for negativo a coluna associada ao par km é adicionada ao Programa Mestre 5 QUESTAO 2 A formulação do Programa Mestre Master Problem e dos Subproblemas utilizando a decomposição de DantzigWolfe para a Um problema linear PL com estrutura blocodiagonal generalizada b Três exercícios específicos i Exercise 22 ii Exercise 26 iii Exercise 24 Em cada caso as variáveis são separadas em blocos de forma que as restrições locais envolvendo apenas um conjunto de variáveis sejam tratadas separadamente enquanto as restrições que conectam as variáveis de diferentes blocos são tratadas no nível do programa mestre 6 Item a Problema Geral com Estrutura BlocoDiagonal Generalizada Considere o seguinte problema linear minimize k1r ckT xk sujeito a k1r Ek xk fk k1r k1r Ak xk b 0 xk xkup k1r Passo 1 Representação dos Conjuntos Viáveis Para cada bloco k defina o conjunto viável Xk xk Rnk Ek xk fk 0 xk xkup Supondo que cada Xk seja um politopo podemos representálo como a convexe de seus vértices Xk conv xjk j Jk Assim qualquer xk pode ser escrito como xk jJk λjk xjk jJk λjk 1 λjk 0 Passo 2 Formulação do Programa Mestre MP Substituindo a representação acima no problema 1 obtemos minimize k1r jJk cjkT xjk λjk sujeito a k1r jJk Ak xjk λjk b jJk λjk 1 k1r λjk 0 j Jk k1r MP Passo 3 Formulação dos Subproblemas Para cada bloco k considerando os multiplicadores π associados à restrição de ligação k1r Ak xk b o subproblema é minimize ck AkT π T xk sujeito a Ek xk fk 0 xk xkup SPk Cada subproblema busca para o bloco k um vértice cuja entrada no MP através do custo reduzido possa melhorar a solução atual 7 Item bi Exercise 22 Problema Original minimize z 2x1 x2 x3 x4 sujeito a 1 x1 2x2 5 2 x3 x4 2 3 2x3 x4 6 4 x1 x3 2 5 x1 x2 2x4 3 x1 x2 x3 x4 0 Passo 1 Decomposição em Blocos Dividimos as variáveis em dois blocos x1 x1 x2 Restrição local 1 x1 2x2 5 x2 x3 x4 Restrições locais 2 x3 x4 2 e 3 2x3 x4 6 As restrições que ligam os blocos são 4 x1 x3 2 envolvendo x1 e x3 5 x1 x2 2x4 3 envolvendo x1 x2 e x4 O vetor de custos se decompõe como c1 2 1 c2 1 1 Definimos os conjuntos viáveis X1 x1 x2 0 x12x2 5 X2 x3 x4 0 x3x4 2 2x3x4 6 Passo 2 Programa Mestre Representando cada conjunto Xk como a convex de seus vértices denotados por xjk com j Jk o MP fica minimize j J12x1jx2jλj1 j J2x3j x4jλj2 sujeito a j J1 x1j λj1 j J2 x3j λj2 2 j J1 x1j x2j λj1 j J2 2x4j λj2 3 MPbi j J1 λj1 1 j J2 λj2 1 λjk 0 j k 1 2 Passo 3 Subproblemas Sejam π1 e π2 os multiplicadores associados às restrições de ligação 4 e 5 respectivamente Subproblema para o Bloco 1 minimize 2 π1 π2 x1 1 π2 x2 sujeito a x1 2x2 5 x1 x2 0 SP1bi Subproblema para o Bloco 2 minimize 1 π1 x3 1 2π2 x4 sujeito a x3 x4 2 2x3 x4 6 x3 x4 0 SP2bi Cada subproblema busca a partir dos multiplicadores atuais gerar uma coluna vértice com custo reduzido negativo para inclusão no MP 8 Item bii Exercise 26 Problema Original minimize z 2x1 x2 x3 x4 sujeito a 1 x1 x2 0 2 x1 2x2 3 3 x3 x4 0 4 3x3 x4 4 5 x1 x3 2 6 x1 4x2 2x4 7 x1 x2 x3 x4 0 Passo 1 Decomposição em Blocos Dividimos as variáveis em dois blocos x1 x1 x2 Restrições locais 1 x1 x2 0 e 2 x1 2x2 3 x2 x3 x4 Restrições locais 3 x3 x4 0 e 4 3x3 x4 4 As restrições de ligação são 5 x1 x3 2 envolvendo x1 e x3 6 x1 4x2 2x4 7 envolvendo x1 x2 e x4 Os vetores de custo ficam c1 2 1 c2 1 1 Os conjuntos viáveis são X1 x1 x2 0 x1 x2 0 x1 2x2 3 X2 x3 x4 0 x3 x4 0 3x3 x4 4 Passo 2 Programa Mestre Utilizando a representação em vértices para cada Xk o MP fica minimize jJ12x1j x2j λj1 jJ2x3j x4j λj2 sujeito a jJ1 x1j λj1 jJ2 x3j λj2 2 jJ1 x1j 4x2j λj1 jJ2 2x4j λj2 7 jJ1 λj1 1 jJ2 λj2 1 λjk 0 j k 1 2 Passo 3 Subproblemas Sejam π1 e π2 os multiplicadores associados às restrições de ligação 5 e 6 respectivamente Subproblema para o Bloco 1 minimize 2 π1 π2 x1 1 4π2 x2 sujeito a x1 x2 0 x1 2x2 3 x1 x2 0 Subproblema para o Bloco 2 minimize 1 π1 x3 1 2π2 x4 sujeito a x3 x4 0 3x3 x4 4 x3 x4 0 9 Item biii Exercise 24 Problema Original minimize z 4x1 x4 6x7 sujeito a 1 x1 x2 1 2 x1 x3 2 3 x4 x5 1 4 x4 x6 2 5 x7 x8 1 6 x7 x9 2 7 3x1 2x4 4x7 x10 17 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 0 Passo 1 Decomposicao em Blocos Observase que leftmargin2cmx1 x1 x2 x3 com restricoes x1 x2 1 x1 x3 2 x2 x4 x5 x6 com restricoes x4 x5 1 x4 x6 2 x3 x7 x8 x9 com restricoes x7 x8 1 x7 x9 2 x4 x10 com a restricao x10 0 A restricao de ligacao e a 7 3x1 2x4 4x7 x10 17 que conecta os blocos Os coeficientes do objetivo se decompoem em c1 4 0 0 c2 1 0 0 c3 6 0 0 c4 0 33 Definindo os conjuntos X1 x1 x2 x3 0 x1 x2 1 x1 x3 2 X2 x4 x5 x6 0 x4 x5 1 x4 x6 2 X3 x7 x8 x9 0 x7 x8 1 x7 x9 2 X4 x10 0 Passo 2 Programa Mestre Representando cada Xk como a convexe de seus vértices xjk com j Jk o MP é minimize k14 jJk ckT xjk λjk sujeito a jJ1 3x1j λj1 jJ2 2x4j λj2 jJ3 4x7j λj3 jJ4 x10j λj4 17 jJk λjk 1 k 1 2 3 4 λjk 0 j k 1 2 3 4 Passo 3 Subproblemas Seja π o multiplicador associado à restrição de ligação 7 Então para cada bloco os subproblemas são Subproblema para o Bloco 1 minimize 4 3π x1 sujeito a x1 x2 1 x1 x3 2 x1 x2 x3 0 Subproblema para o Bloco 2 minimize 1 2π x4 sujeito a x4 x5 1 x4 x6 2 x4 x5 x6 0 SP2biii Subproblema para o Bloco 3 minimize 6 4π x7 sujeito a x7 x8 1 x7 x9 2 x7 x8 x9 0 SP3biii Subproblema para o Bloco 4 minimize π x10 sujeito a x10 0 SP4biii Cada subproblema e resolvido para verificar se ha uma coluna vertice com custo reduzido negativo Se sim ela e adicionada ao MP caso contrario a solucao atual e otima 35