Programacao Linear e Optimizacao Nao Linear - Notas de Aula

Programação Linear e rudimentos de otimização não linear notas de aula 202204270917 Jerônimo C Pellegrini id f93aaba815d225ccfdb4bad9460cb46676306532 ii Este trabalho está disponível sob a licença Cre ative Commons Attribution NonCommercial ShareAlike versão 40 httpscreativecommonsorglicensesbyncsa40deedptBR Apresentação Esta é uma introdução à Otimização com ênfase em Programação Linear e aplicações mas expondo também alguns rudimentos de Otimização Não Linear Os prérequisitos para a leitura são Álgebra Linear para as partes I e II e Cálculo em Várias Variáveis para os Capítulos de Programação Quadrática e Otimização não linear iii iv Sumário Sumário v I Programação Linear 1 1 Programação Linear 3 11 Forma padrão 5 12 Interpretação geométrica 7 13 Fluxo em redes 10 2 Modelagem 15 21 Programação Linear 15 211 Exemplos básicos 15 212 Valores absolutos 24 213 Objetivo minimax 28 22 Programação Fracionária 29 221 Transformação em programa linear 31 23 Programação Inteira 33 231 Valores descontínuos 35 232 Restrições condicionais 36 233 Eliminando produtos de variáveis 36 24 Programação NãoLinear 37 3 Conjuntos Convexos e Soluções Viáveis 41 31 Conjuntos convexos 41 32 Soluções viáveis para programas lineares 54 33 Funções Convexas 65 v vi SUMÁRIO 4 O Método Simplex 73 41 Exemplo inicial 73 42 Formulação 75 43 Intuição geométrica 76 44 Coeficientes reduzidos de custo 78 441 Primeira definição 78 442 Segunda definição 80 443 Representação no tableau 81 444 Exemplo 82 45 A operação de mudança de base 83 46 Que variável entra na base 84 47 Que variável sai da base 87 471 Intuição 87 472 Elaboração com rigor 90 48 Método Simplex algoritmo 92 49 Obtendo uma solução viável básica inicial 95 491 O método das duas fases 95 492 O método do M grande 101 410 Minimização e desigualdades do tipo 103 411 Soluções degeneradas 105 412 Método Simplex Revisado 109 5 Dualidade 121 51 Interpretação do dual 123 52 Lema de Farkas 123 53 Teoremas de dualidade 127 54 Algoritmo simplex dual 133 541 Quem sai 134 542 Quem entra 135 543 Base inicial 137 544 Resumo e exemplos 140 6 Análise de Sensibilidade 147 61 Mudanças no objetivo 147 62 Mudanças no vetor b de termos independentes 151 63 Nova variável 156 64 Nova restrição 158 SUMÁRIO vii 7 Outros Métodos 163 71 O método do elipsoide 163 711 O algoritmo 163 712 Resolvendo problemas de programação linear 167 72 Pontos interiores 169 721 Affine scaling 169 8 Programação Inteira 177 81 Planos de corte 180 82 Branchandbound 185 83 Variantes branchandcut branchandprice 187 84 Unimodularidade e poliedros integrais 187 II Aplicações 191 9 Problemas de Transporte 193 91 Solução básica inicial 196 92 Solução inteira 198 93 Algoritmo para solução do problema de transporte 198 94 Bases degeneradas 205 95 O problema de atribuição 206 10 Teoria dos Jogos 213 101 Jogos de soma zero 213 102 Estratégia mista 215 1021 Formulação como programa linear 215 11 Controle Discreto 221 111 Programação Dinâmica 221 1111 Aplicabilidade do Algoritmo 223 112 Processo Markoviano de Decisão 223 113 Horizonte infinito e convergência 225 1131 Convergência 225 114 Formulação como Programa Linear 227 115 Variantes de MDPs 229 1151 Tempo contínuo 229 1152 Parâmetros imprecisos 230 1153 Observabilidade parcial 230 viii SUMÁRIO III Tópicos Relacionados 235 12 O Algoritmo PrimalDual e suas Aplicações 237 121 O algoritmo primaldual 237 122 237 13 Programação Quadrática 239 131 Problemas modelados como programas quadráticos 239 132 Representação 241 133 Soluções ótimas para programas quadráticos 243 134 Método de Beale 244 135 Pontos interiores 251 14 Otimização Não Linear 253 141 Otimização sem restrições 254 1411 Condições de otimalidade 255 1412 Métodos 259 142 Otimização com restrições 259 1421 O Lagrangeano 260 1422 Dualidade 261 1423 Condições de otimalidade 261 1424 Métodos 264 143 Otimização linear e dualidade 264 IV Apêndices 265 A Solução Inteira para Problemas de Transporte demonstração sem unimodularidade 267 B Respostas e Dicas 271 Ficha Técnica 277 Bibliografia 279 Índice Remissivo 284 Notação Negrito é usado para vetores inclusive colunas de matrizes quando tra tadas isoladamente arg maxi é o índice dentre todos os i que determina o máximo do conjunto usamos arg min de forma análoga A notação x é para chão de x ou maior inteiro menor ou igual a x Similarmente x é usado para o conceito simétrico menor inteiro maior ou igual a x ou teto de x1 É usada a notação sa para sujeito a Neste texto o índice j é usado para colunas da matriz A que descreve as restrições do programa linear Neste contexto uso j m e j m como formas abreviadas de j pertencente à base e j fora da base 1O leitor possivelmente conhece a notação x e x 1 2 SUMÁRIO Parte I Programação Linear 1 pode ser descrito de forma mais compacta como max cx sa Ax b x 0 Exemplo 13 Para descrever o problema do exemplo 12 renomeamos as variáveis x₁ y₁ x₂ y₂ v y₃ w y₄ s₁ y₅ s₂ y₆ e o programa linear pode ser reescrito como max cy sujeito a Ay b y 0 com y y₁ y₂ y₃ y₄ y₅ y₆ c 1 3 5 5 0 0 b 10 20 15 A 4 1 0 0 1 0 1 0 3 3 0 1 0 1 1 1 0 0 12 Interpretação geométrica Nesta seção damos a interpretação geométrica de problemas de programação linear e um método para solução de programação linear por inspeção do gráfico Este método não deve ser visto como ferramenta prática já que só é viável para problemas com duas variáveis e poucas restrições Além disso Normalmente qualquer ferramenta computacional produzirá resultados mais rapidamente do que este método Ele é no entanto útil para aprofundar a compreensão do que é um problema de programação linear e quais são suas soluções A função objetivo define um hiperplano uma reta em ℝ² um plano em ℝ³ Note que queremos maximizála ou minimizála portanto não nos fará diferença se a modificarmos adicionando uma constante maximizar z 2x₁ 3x₂ Capítulo 1 Programação Linear Problema de programação linear é o nome dado a alguns problemas de otimização Um problema deste tipo consiste em encontraro melhorvalor possível para uma função linear de n variáveis respeitando uma série de restrições descritas como desigualdades lineares Damos um exemplo inicial que ilustra a origem dos problemas de pro gramação linear Uma fábrica produz dois tipos de tinta t1 e t2 Queremos determinar a quantidade ótima de cada tinta para maximizar o lucro da empresa Cada tinta tem um custo por litro e um determinado lucro e há também res trições relacionadas aos níveis de produção de cada uma As tintas t1 e t2 tem custo de produção por litro igual a 5 e 4 res pectivamente Os lucros da empresa com as tintas são de 6 e 55 O orçamento da empresa só permite gastar 1400 com a produção de tintas Um contrato de fornecimento com uma outra empresa exige que pelo menos 60 litros da tinta t1 seja produzido A empresa pode produzir no máximo 250 litros da tinta t2 por mês por restrição do fornecedor que não consegue atender a demanda maior que essa Passamos agora à modelagem deste problema encontraremos uma descrição formal dele que facilitará a obtenção da solução O lucro que queremos maximizar é dado pela função 6t1 55t2 Esta é nossa função objetivo As restrições que impomos à solução são 3 4 CAPÍTULO 1 PROGRAMAÇÃO LINEAR 5t1 4t2 1400 orçamento t1 60 contrato t2 250 oferta do fornecedor de pigmento t1 t2 0 a empresa não pode desfazer tinta Como tanto o objetivo como as restrições são lineares nas variáveis t1 e t2 que queremos determinar dizemos que este é um problema de otimização linear ou de programação linear Na maior parte deste livro trataremos de problemas deste tipo Em alguns Capítulos abordaremos também problemas de otimização não linear onde a função objetivo e as restrições não precisam ser funções lineares Este é um exemplo bastante prático e aplicado Há outros problemas completamente diferentes deste que podem ser modelados como pro gramação linear inclusive problemas mais abstratos e sem uma ligação aparente tão clara com aplicações práticas Mais exemplos de aplicação modelagem serão dados no final deste Capítulo Definição 11 problema de programação linear Um problema de progra mação linear consiste de uma função objetivo linear em n variáveis e um conjunto de restrições representadas porm desigualdades ou igualdades lineares Uma solução para o problema é um vetor em Rn Uma solução é viável se satisfaz as restrições e inviável caso contrário Um problema pode ser de maximização ou de minimização A solução ótima para o problema é a solução viável que dá o maior valor possível à função objetivo quando o problema é de maximização ou aquela que dá o menor valor ao objetivo se o problema é de minimização Problemas de programação linear são normalmente descritos em uma forma padrão detalhada na próxima seção 11 FORMA PADRÃO 5 11 Forma padrão Na maior parte do tempo presumiremos que o programa linear está na seguinte forma max c1x1 c2x2 cnxn sa a11x1 a12x2 a1nxn b1 a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bm e xi 0 para alguns i Mostramos agora como transformar qualquer programa linear em ou tro equivalente na forma padrão Maximizaçãominimização notamos que min cTx é o mesmo que max cTx Desigualdades considere a restrição ai1x1 ai2x2 ainxn bi Esta desigualdade pode ser transformada em ai1x1 ai2x2 ainxn si bi si 0 Chamamos si de variável de folga quando a desigualdade vale com o lado direito igual ao esquerdo temos si 0 Quando o lado direito da desigualdade é menor que o esquerdo temos si 0 Da mesma forma podemos transformar ai1x1 ai2x2 ainxn bi em ai1x1 ai2x2 ainxn ui bi Variáveis com valores negativos se em uma solução uma variável xi puder ser negativa usamos duas variáveis positivas para representá la Fazemos xi p q com p q 0 6 CAPÍTULO 1 PROGRAMAÇÃO LINEAR Exemplo 12 Ilustramos as técnicas descritas transformando o seguinte problema para a forma padrão min x1 3x2 5x3 sa 4x1 x2 10 x1 3x3 20 x3 x2 15 x1 x2 0 Observe que x3 não está restrita a valores positivos Para transformar o problema de minimização em maximização mul tiplicamos a função objetivo por 1 max x1 3x2 5x3 Incluímos uma variável nova a cada desigualdade obtendo 4x1 x2 s1 10 x1 3x3 s2 20 Finalmente determinamos x3 v w com v w 0 O programa linear é então max x1 3x2 5v 5w sa 4x1 x2 s1 10 x1 3v 3w s2 20 v w x2 15 xi v w sj 0 Também será conveniente representar programas lineares usando no tação matricial Claramente um problema max c1x1 c2x2 cnxn sa a11x1 a12x2 a1nxn b1 a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bm xi 0 Verificamos que o ponto C nos dá o maior valor portanto a solução 43 é ótima com valor 11 13 Fluxo em redes Tratamos nesta seção de uma aplicação onde a correspondência entre os objetos modelados e as variáveis do programa linear não são tão imediatamente óbvias como no caso de mistura ótima Informalmente uma rede é semelhante a um conjunto de tubos por onde escoamos algum fluido Queremos decidir quanto de fluido devemos passar em cada tubo a fim de maximizar o fluxo entre dois pontos Para definir redes de fluxo com mais rigor precisaremos definir grafos dirigidos Um grafo é um conjunto de nós ou vértices ligado por arestas Usamos grafos por exemplo para representar locais e caminhos entre eles Definição 15 grafo dirigido Um grafo direcionado consiste de um conjunto não vazio de vértices V e um conjunto de arestas E O conjunto de arestas representa ligações entre os vértices de forma que E V² Denotamos por uv a aresta que leva do vértice u ao vértice v Em um grafo com peso nas arestas cada aresta tem um valor associado dado por uma função w E ℝ Exemplo 16 A seguir mostramos um grafo e sua representação de um grafo como diagrama V a b c d e E ab bc ca dc de ae Note que a disposição dos vértices e arestas no diagrama é arbitrária O grafo seria o mesmo se movêssemos estes vértices e arestas de lugar mantendo as ligações entre eles 8 CAPÍTULO 1 PROGRAMAÇÃO LINEAR é o mesmo que maximizar z 2x1 3x2 50 A função objetivo da forma como foi definida passa pela origem Quando somamos a ela um valor constante ela se afasta dali Cada restrição define um semiespaço em R2 um dos lados de uma reta em R3 um dos lados de um plano Queremos o maiorvalorda função objetivo dentro da região definida pelas restrições Apequena seta na próxima figura mostra o gradiente da função objetivo Se nos movermos a partir da reta definida pela função objetivo na direção de seu gradiente mantendonos dentro da região viável conseguiremos soluções cada vez melhores Isso é o mesmo que mover a reta definida pela função objetivo na direção de seu gradiente até que não possa mais ser empurrada O último ponto em que ela tocar a região viável é a solu ção ótima para o problema 12 INTERPRETAÇÃO GEOMÉTRICA 9 Ainda podemos fazeroutra observação importante vemos claramente que se uma solução ótima existe ela ocorrerá em um dos pontos extremos cantos da região viável ou seja na interseção de duas restrições Disso podemos extrair um método para obter a solução ótima de pro gramas lineares por inspeção do gráfico desde que tenhamos apenas duas variáveis o que não é comum em problemas reais Exemplo 14 Resolveremos o seguinte problema de programação linear max 2x1 x2 sa 3x1 x2 15 x2 6 x1 x2 7 x1 92 x 0 Plotamos apenas as restrições e verificamos que formam uma região fe chada no plano 1 2 3 4 5 2 4 6 8 10 12 14 16 A B C D 0 E x1 x2 Notamos que há poucas restrições portanto podemos simplesmente cal cular os pontos onde as retas se interceptam e verificar qual desses pontos nos dá o maior valor para a função objetivo ponto valor A 0 6 6 B 1 6 8 C 4 3 11 D 92 32 105 E 92 0 9 CAPÍTULO 1 PROGRAMAÇÃO LINEAR Exemplo 17 A seguir mostramos um grafo com pesos nas arestas O grafo pode ser descrito da seguinte maneira Definição 18 Rede de fluxo Uma rede de fluxo é um grafo dirigido acíclico onde são identificados dois vértices um é a fonte e o outro é o destino Não há arestas chegando à fonte e não há arestas saindo do destino O peso em cada aresta representa uma capacidade Um fluxo em uma rede é uma atribuição de um número o fluxo a cada aresta o fluxo deve ser menor ou igual à capacidade da aresta Um problema de fluxo em rede consiste em encontrar em uma rede dentre todos os fluxos possíveis aquele com maior valor total Seja xij o fluxo do vértice vi para o vértice vj O fluxo entrando em um nó i deve ser igual ao fluxo saindo dele Os fluxos saindo da fonte e chegando ao destino são iguais O fluxo em uma aresta deve ser menor ou igual que a capacidade da aresta Concluímos portanto que o fluxo ótimo na rede é dado pela solução ótima do problema de programação linear a seguir onde s e d são a fonte e o destino Exemplo 19 Considere a rede de fluxo a seguir Sua solução ótima é também a solução ótima do programa linear a seguir 13 FLUXO EM REDES 13 para simplificar a notação fazemos v0 s e v6 d max cTx sa x01 x10 0 x12 x21 0 x56 x65 0 x01 x02 x36 x46 x56 0 x01 5 x02 4 x13 5 x24 3 x25 2 x32 1 x36 4 x43 3 x46 3 x56 3 x 0 Notas Os exemplos dados neste Capítulo não foram apresentados de forma de talhada sua função aqui é apenas ilustrar a utilidade da modelagem de problemas como programas lineares Programação linear não é o melhor método para resolver problemas de fluxo em redes mas é útil para entender a estrutura dos problemas e como para modelagem e solução rápida de pequenos exemplos O livro de Cormen Leiserson Rivest e Stein Cor09 contém um capítulo sobre fluxo em redes O livro de Bazaraa Jarvis e Sherali BSS06 trata mais ex tensivamente do assunto Exercícios Ex 1 Resolva os programas lineares usando o método gráfico 14 CAPÍTULO 1 PROGRAMAÇÃO LINEAR min x1 2x2 sa 3x1 x2 6 2x1 x2 9 x1 x2 0 min x1 3x2 sa x1 2x2 50 2x1 4x2 30 x1 4x2 15 x1 x2 0 min x1 3x2 sa x1 x2 10 x1 x2 5 2x1 3x2 10 x1 x2 0 Ex 2 Converta o programa linear a seguir para a forma padrão de pro blema de maximização min x1 3x2 5x3 sa 8x1 x2 x3 100 2x1 x2 4x3 120 x1 x2 x3 x1 x2 0 Ex 3 Converta o programa linearapresentado na introdução para a forma padrão de problema de maximização Ex 4 Como seria a formulação como programa linear de uma rede de fluxo onde i não há conservação de fluxo nos nós ou seja cada nó vi pode produzir ou consumir uma quantidade fixa fi de fluxo e ii onde cada canal além de ter um fluxo máximo suportado tem também um mínimo Capítulo 2 Modelagem Nesta Capítulo descrevemos a modelagem de alguns problemas de otimi zação Estes devem ser tratados como exemplos e não constituem uma lista exaustiva de técnicas de modelagem porque esta é uma atividade cri ativa e não teríamos como catalogar todas as formas diferentes de pensar a modelagem de problemas No entanto dividimos o capítulo em seções Cada seção contém exem plos de problemas modelados em grandes categorias A primeira é pro gramação linear simples e as outras são variantes desta fracionária onde a função objetivo é uma função racional inteira onde só são admitidos va lores inteiros para variáveis e convexa Em algumas seções apresentamos alguns truques simples de modelagem 21 Programação Linear Nesta seção apresentamos alguns exemplos importantes de aplicação de programação linear Deixamos de lado tres deles que apresentamos em mais detalhes mais adiante o Capítulo 9 trata detalhadamente da estru tura de problemas de transporte e de algoritmos para resolvêlos já o Ca pítulo 10 aborda a modelagem de problemas em Teoria de Jogos final mente o Capítulo 11 mostra como alguns problemas de controle podem ser resolvidos com o uso de programação linear 211 Exemplos básicos Exemplo 21 Mistura ótima É comum que se queira determinar a pro porção ótima de mistura de diferentes ingredientes insumos recursos 15 16 CAPÍTULO 2 MODELAGEM etc a fim de otimizar alguma função Dizemos que estes são problemas de mistura ótima O problema apresentado no início do Capítulo um é de mistura ótima procurase determinar a proporção ideal de dois produtos para maximizar seu valor Damos aqui outro exemplo de mistura ótima Exemplo 22 Dieta O problema da dieta foi um dos primeiros a serem es tudados no contexto da otimização linear A idéia é tentar conseguir uma dieta que ofereça o mínimo necessário para manter saudáveis milhares de soldados reduzindo tanto quanto possível o custo da dieta O problema claro pode ser traduzido para outros contextos Um nutricionista determinou que pra um de seus pacientes as neces sidades diárias de alguns itens alimentares são como na tabela a seguir min max carboidratos 268 387 fibras 25 50 proteínas 50 100 Ca 1000 2500 B1 12 B6 13 100 Suponha e esta é de fato uma suposição não realista e não uma recomen dação de dieta que nutricionista e paciente tenham chegado a um acordo quanto aos alimentos que serão usados na dieta A composição desses ali mentos e seus preços são dados na próxima tabela Todos os valores são por 100g de cada alimento1 ch g fibra g prot Ca mg B1 B6 preço arroz 1 281 16 25 4 Tr Tr 025 pão 746 34 105 19 038 Tr 15 far rosca 758 48 114 35 025 009 06 batata 119 13 12 4 005 008 025 brócolis 44 34 21 51 004 Tr 13 tomate 31 12 11 7 012 002 05 b nanica 238 19 14 3 Tr 014 025 figo 102 18 10 27 005 Tr 06 merluza 0 266 36 005 Tr 22 pto frango 0 315 5 01 Tr 12 1O valor nutricional foi obtido da tabela de composição de alimentos do NEPAUni camp Lim06 21 PROGRAMAÇÃO LINEAR 17 Tentaremos construir uma dieta de preço mínimo que respeite as restri ções de nutrição dadas e usando esses alimentos Nosso objetivo é mini mizar o preço portanto min 025a15p06fa025ba13br05t025bn06fi22m12fr As restrições dadas são mostradas abaixo 268 281a 746p 758fa 119ba 44br 31t 238bn 102fi 387 25 16a 34p 48fa 13ba 34br 12t 19bn 18fi 50 50 25a 105p 114fa 12ba 21br 11t 14bn 10fi 266m 315fr 100 1000 4a 19p 35fa 4ba 51br 7t 3bn 27fi 36m 5fr 2500 12 038p 025fa 005ba 004br 012t 005fi 005m 01fr 13 009fa 008ba 002t 014bn 100 a p fa ba br t bn fi m fr 18 A última restrição determina que a quantidade não seja maior que 1800g cada variável nos dá a quantidade de porções de 100g de alimento Como já temos a função objetivo e as restrições o modelo está pronto Exemplo 23 Planejamento de produção Um produtor de leite precisa planejar sua produção ao longo do ano Há capacidade para produzir 900ℓ por mês sem pagamento de hora extra e 1100ℓ por mês pagando hora extra O custo de produção de 100ℓ de leite é 10 sem hora extra e 13 com hora extra O custo de armazenamento de 100ℓ de leite quando não é vendido no mesmo mês é de 15 O produtor tem dados históricos com a demanda típica de cada mês mês demanda mês demanda 1 500 7 540 2 350 8 450 3 550 9 400 4 400 10 400 5 600 11 400 6 600 12 500 As variáveis cujos valores precisamos determinar são pi a produção no mes i ei a produção com hora extra no mês i ai a quantidade de leite produzido no mes i e armazenada para o mes seguinte Como a demanda do ano todo não deve variar muito o produtor precisa apenas minimizar o custo de produção dessa demanda dado por As restrições são Se a demanda em um mês é x então a sobra do mês anterior mais produção do mes atual menos o que é levado ao próximo mês é igual a x Já temos agora o modelo completo que mostramos a seguir min 10 pi 15 ei 15 ai i i i sa pi 900 uma restrição para cada i ei 200 uma restrição para cada i p1 e1 a1 500 p2 e2 a2 a1 350 p3 e3 a3 a2 550 p4 e4 a4 a3 550 p5 e5 a5 a4 550 p6 e6 a6 a5 550 p7 e7 a7 a6 550 p8 e8 a8 a7 550 p9 e9 a9 a8 550 p10 e10 a10 a9 550 p11 e11 a11 a10 400 p12 e12 a11 500 pi ei ai 0 Exemplo 24 Geometria Em sua introdução à Programação Linear MG06 Jiri Matousek e Bernd Gartner dão um interessante exemplo em geometria que elaboramos também neste exemplo Um polígono convexo em R2 pode ser descrito por um número de retas Como cada reta é da forma y ax b o polígono é descrito por y a1x b1 y a2x b2 y anx bn Queremos saber qual é a maior circunferência que podemos descrever dentro desse polígono A circunferência é descrita por centro e raio portanto três variáveis x y r Nem sempre é possível que a circunferência toque em todas as restrições na figura acima ela não toca nas restrições à direita e à esquerda Claramente para maximizar a área temos que maximizar o raio portanto já temos nossa função objetivo As restrições devem descrever uma única limitação para cada parede do poligono o raio deve ser menor que a distância do centro até a parede A distância do centro a cada uma das paredes é di y aix bi ai2 1 Uma das paredes do polígono estará acima ou abaixo de todos os pontos no interior do polígono como mostra a figura a seguir a parede destacada em negrito está acima de todos os pontos no interior do polígono alguns deles são mostrados O valor dentro do módulo na fórmula 21 será positivo quando a linha estiver abaixo do centro ou de qualquer ponto dentro do polígono e negativa quando a linha estiver acima do centro Sem perda de generalidade suponha que as linhas 1 2 k estejam abaixo do centro e que as linhas k1 k2 n estejam acima do centro Com estas condições nossas restrições serão y aix biai2 1 r para i k y aix biai2 1 r para i k Reorganizando as desigualdades temos 1ai2 1 y aiai2 1 x r biai2 1 para i k 1ai2 1 y aiai2 1 x r biai2 1 para i k Note que os valores entre parenteses são constantes porque fazem parte da descrição do polígono O modelo completo é mostrado a seguir max r sa 1ai21y aiai21x r biai21 para i k 1ai21y aiai21x r biai21 para i k x y r 0 Damos um exemplo simples tomamos o triângulo definido pelas retas y x y x5 y x 3 y x 3 y x y x5 A descrição das retas é dada pelos pares ai bi a seguir 10 15 15 0 21 PROGRAMAÇÃO LINEAR Para 15 por exemplo temos 1ai21y aiai21x r biai21 1121y 1121x r 5121 12y 12x r 52 A construção das restrições para os outros pontos é semelhante O modelo final é mostrado a seguir max r sa 12y 12x r 0 12y 12x r 52 526y 126x r 0 x y r 0 x y r ℝ O ótimo para este problema é x y 25 13376 r 0821687 A próxima figura mostra a circunferência inscrita no triângulo2 2O posicionamento da circunferência na página foi de fato calculado através do programa linear que apresentamos Embora Matousek e Gartner tenham apresentado este problema apenas abstratamente como como otimização em geometria é fácil perceber sua aplicabilidade prática poderíamos ter que determinar por exemplo quão largo pode ser um cilindro que queremos encaixar em um dado local delimitado por superfícies planas em um trabalho de engenharia 212 Valores absolutos Quando queremos otimizar o valor absoluto de uma variável xi mas não restringíla a valores positivos podemos expressar xi como a diferença de duas outras variáveis ambas positivas xi xip xin Necessariamente teremos sempre um dentre xip xin igual a zero e xi xip xin Exemplo 25 Regressão linear Se tivermos diversos dados obtidos experimentalmente é possível tentarmos determinar uma curva que melhor aproxima esses dados Os dados estão na forma xi yi Quando a curva é na verdade uma reta damos ao processo de obtêla o nome de regressão linear Apresentaremos dois métodos para obter a esta reta um deles consiste em minimizar o quadrado do erro e o outro consiste em modelar como um problema de otimização linear Minimização do quadrado do erro Se decidirmos por uma reta definida por ax b o erro em cada ponto será zi axi b yi Não podemos simplesmente minimizar o erro porque ele pode ser negativo Podemos minimizar o quadrado do erro min Σi axi b yi2 Derivamos i αxi b yi 2 com relação às variáveis α e b e igualamos a zero Primeiro com relação a b b i αxi b yi 2 b αx1 b y1 2 αxn b yn 2 2αx1 b y1 2αxn b yn Agora com rlação a α α i αxi b yi 2 b αx1 b y1 2 αxn b yn 2 2x1 αx1 b y1 2xn αxn b yn Igualamos ambas a zero obtendo um sistema linear com duas equações e duas variáveis 2 αxi b yi 0 2 xi αxi b yi 0 que pode ser reescrito como nb a xi yi b xi a xi2 xi yi Isolando a e b e denotando por x y as médias de xi e yi temos uma forma fechada para os coeficientes a xi x yi xi x2 b y a x chamado de sistema de equações normais de regressão linear Modelagem como problema de otimização linear Minimizar o quadrado do erro nos traz um problema quando o módulo do erro é maior que um seu quadrado é maior que ele quando é menor que um seu quadrado é menor que ele Assim introduzimos um viés Podemos minimizar o valor absoluto do erro de forma a não introducir viés min i αxi b yi Representamos cada erro explicitamente como zi portanto a função objetivo é min z1 z2 zn ou representando as partes positiva e negativa min z1 z1 z2 z2 zn zn Construiremos as restrições da seguinte maneira αxi b zi zi yi Como tanto a como b devem ser irrestritos positivos ou negativos reescrevemos a xi a xi b b zi zi yi O modelo é finalmente min z1 z1 z2 z2 zn zn sa a x1 a x1 b b z1 z1 y1 a x2 a x2 b b z2 z2 y2 a xn a xn b b zn zn yn onde a a b zi zi são as variáveis a serem determinadas e os xi e yi são dados Exemplo concreto suponha que tenhamos obtido os seguintes pontos a partir de um experimento 19 28 35 46 51 62 O programa linear que determina a reta que melhor aproxima os pontos usando o critério do valor absoluto do erro total é min i16 zi zi sa 1 a 1 a b b z1 z1 9 2 a 2 a b b z2 z2 8 3 a 3 a b b z3 z3 5 4 a 4 a b b z4 z4 6 5 a 5 a b b z5 z5 1 6 a 6 a b b z6 z6 2 A solução deste programa linear é z2 4 z3 12 z4 12 z5 24 a 14 b 204 ou seja z2 04 z3 12 z4 12 z5 24 a 14 b 104 A reta é portanto y 14 x 104 Para comparação o método apresentado anteriormente nos dá outra reta a xi x yi y xi x2 55 35 15714 b y a x 31 6 7 2 a 32 3 106666 portanto a reta obtida é y 15714 x 106666 Na figura r é a reta obtida pelo programa linear e s a reta obtida minimizando o erro quadrático A diferença entre as retas pode ser maior para outros conjuntos de dados 213 Objetivo minimax Podemos querer também minimizar o máximo ou maximizar o mínimo de um conjunto de funções min maxq cqi xi Em um programa linear na forma padrão não podemos descrever min max mas podemos criar uma nova variável w que representa o máximo a ser minimizado w maxq cqi xi Para cada q adicionamos uma restrição sumi cqi xi w Desta forma ao minimizarmos z As restrições garantem que w será maior que a maior das somas para cada q Como minimizamos w ele não será maior que nenhuma das somas Exemplo 26 regressão linear No exemplo 25 minimizamos a soma dos erros Se quisermos minimizar o maior dos erros teremos o objetivo mini max a xi b yi 22 PROGRAMAÇÃO FRACIONÁRIA 29 ou min max i z i z i Podemos criar uma nova variável w que representa o máximo a ser mini mizado w max i z i z i E construimos nosso modelo minimizando w min w sa axi axi b b z i z i yi para todo i w z 1 z 1 z n z n As variáveis são a a b b w z i z i 22 Programação Fracionária No problema a seguir a função objetivo não é linear mas é dado pelo quo ciente de duas funções afim min cTx d gTx f 22 sa Ax b x 0 Damos o nome a este tipo de problema de problema de programação fra cionária Podemos chegar a formulação de problemas deste tipo quando quisermos levar em consideração na função objetivo uma relação cus tobenefício como por exemplo o o quociente entre lucro por unidade de produto e custo de cada unidade Exemplo 27 mistura ótima Há uma variante do problema de mistura ótima que é formulada como problema de programação fracionária Suponha que uma fábrica precise produziruma liga metálica contendo entre 06 e 21 de Carbono e no mínimo 7 de Tungstênio Molibdênio e Vanádio3 Esta liga será vendida por 240kg Ele pretende misturar outras 3Uma liga como esta é chamada de Aço Rápido muito usado na produção de ferra mentas duras brocas alicates etc 30 CAPÍTULO 2 MODELAGEM quatro ligas disponíveis cuja quantidade de Carbono Ca Tungstênio W Molibdênio Mo e Vanádio V é dada na tabela a seguir L1 L2 L3 L4 Fe 25 20 20 20 W 20 10 40 05 Mo 20 10 30 10 V 10 10 30 00 qtde 100 150 100 200 custo 180 100 280 190 Para determinar a mistura ideal das quatro ligas definimos as variáveis x1 x2 x3 x4 que expressam a quantidade de cada uma O custo será dado por 180x1 100x2 280x3 190x4 Como a liga será vendida por 240kg o retorno será de 240x1 x2 x3 x4 Isto nos dá o objetivo 240x1 240x2 240x3 240x4 180x1 100x2 280x3 190x4 As restrições são 06 Fe 21 W Mo V 7 ou seja 0006 25x1 20x2 20x3 20x4 x1 x2 x3 x4 0021 25x1 20x2 20x3 20x4 x1 x2 x3 x4 007 20 20 10x1 10 10 10x2 40 30 30x3 05 10x4 x1 x2 x3 x4 22 PROGRAMAÇÃO FRACIONÁRIA Resolvemos o sistema e reescrevemos as restrições obtendo o modelo max 240x1 240x2 240x3 240x4 180x1 100x2 280x3 190x4 sa 15x1 x2 x3 x4 0 redundante 4x1 x2 x3 x4 0 2x1 4x2 3x3 55x4 0 x1 100 x2 150 x3 100 x4 200 x 0 221 Transformação em programa linear Todo problema de programação fracionária pode ser transformado em um programa linear mas este método é ineficiente resultando em um problema maior que o necessário Pode ser usado no entanto na modelagem de problemas pequenos O problema a seguir é equivalente ao problema apresentado no início da seção min cT y dz sa A y z b 0 gT y f z 1 y 0 onde as variáveis são y e z Teorema 28 A solução ótima para o problema 23 é ótima para 22 com y 1 gT x f x z 1 gT x f Demonstração A função objetivo minimizada em 23 é cT y dz cT 1gT x f y d 1gT x f cT x d gT x f que é a função objetivo minimizada em 22 As restrições em 22 são A x b A z x zb A y zb zx y A y bz 0 Finalmente z z1 1 z gT x f 1 z gT x z f 1 gT y f z 1 zx y sempre com y 0 y 1 gT x f x z 1 gT x f Exemplo 29 A seguir temos um problema de programação fracionária linear min 2x1 x2 3 x1 x2 2 sa x1 x2 10 2x1 x2 5 x 0 23 PROGRAMAÇÃO INTEIRA Temos min cT x d gT x f sa Ax b x 0 com A 1 1 2 1 b 10 5 c 2 1 g 1 1 d 3 f 2 O problema de programação linear equivalente é min cT y dz sa Ay zb 0 gT y fz 1 y 0 ou seja min 2y1 y2 3z sa y1 y2 10z 0 2y1 y2 5z 0 y2 y 2 2z 1 y 0 23 Programação Inteira Muitas vezes queremos resolver um problema de otimização linear onde só nos interessam as soluções inteiras Um problema de programação inteira é semelhante a um problema de programação linear mas restringindo parte das variáveis a valores inteiros max cT x sa Ax b x 0 xj Z se j K onde o conjunto K contém os índices das variáveis inteiras 34 CAPÍTULO 2 MODELAGEM Exemplo 210 mistura ótima inteira Uma empresa produz três produtos A B e C feitos em três máquinas M1 M2 e M3 Todas as máquinas podem produzir todos os produtos exceto que a máquina M3 não pode ser usada para fabricar o produto C A tabela a seguir mostra quanto cada produto usa do tempo de cada máquina para a fabricação de uma unidade e quanto é o lucro de cada produto por unidade bem como o tempo disponível em cada máquina produto tempo necessário lucro A 4 1 1 7 B 7 3 3 25 C 2 2 0 6 tempo disponível 230 170 40 Além disso a empresa se comprometeu a entregar 10 unidades de A e 5 unidades de B Para decidir quanto produzir de A B e C maximizando o lucro total formulamos o problema como programa linear Denominaremos a quantidade de produtos a na máquina Mi por ami As máquinas não podem fabricar parcialmente um produto portanto exigimos que cada uma destas variáveis tenha valor inteiro A função objetivo expressa a maximização do lucro obtido com a produção dos três produtos max 7A 25B 6C ou já especificando quando cada máquina produzirá max 7i ami qtde de A 25i bmi qtde de B 6i cmi qtde de C As restrições são de dois tipos limite de tempo e mínimo necessário de cada produto Os limites de tempo são 4am1 7bm1 2cm1 230 am2 3bm2 2cm2 170 am3 3bm3 40 23 PROGRAMAÇÃO INTEIRA 35 Já os limites mínimos de produção são am1 am2 am3 10 bm1 bm2 5 O modelo está pronto max 7am1 7am2 7am3 25bm1 25bm2 25bm3 6cm1 6cm2 6cm3 sa 4am1 7bm1 2cm1 230 am2 3bm2 2cm2 170 am3 3bm3 40 am1 am2 am3 10 bm1 bm2 5 ami bmi cmi Z soluções inteiras positivas É comum escrever o modelo de forma mais compacta max 7i ami 25i bmi 6i cmi sa 4am1 7bm1 2cm1 230 am2 3bm2 2cm2 170 am3 3bm3 40 i ami 10 i bmi 5 ami bmi cmi Z 231 Valores descontínuos No processo de modelagem pode acontecer de nos darmos conta de que uma determinada variável possa assumir valores em um conjunto descontínuo por exemplo ou zero ou em 3 5 0 3 5 This page contains only the page number 40 and the chapter title CAPÍTULO 2 MODELAGEM 24 PROGRAMAÇÃO NÃOLINEAR 37 Com isso temos x1 x2 y x1x2 1 1 1 1 0 0 0 1 0 0 0 0 Quando o produto é de uma variável binária x1 com uma contínua x2 e há a restrição x2 K introduzimos a variável y x1x2 e as restrições y Kx1 y x2 y x2 K1 x1 y 0 Exemplo 213 24 Programação NãoLinear Quando a função objetivo ou as restrições não são descritas por funções lineares temos um problema de programação não linear Notas O problema da dieta foi proposto nos anos 40 por George Stigler tratava se de tentar encontrar a mais barata dieta que pudesse manter saudá vel um homem adulto de constituição física usual Stigler usando uma heurística encontrou uma dieta que custava somente 3993 dólares por homem e por ano a dieta custaria pouco mais de 500 dólares no ano 2000 George Dantzig depois de criar o método Simplex para resolver problemas de programação linear aplicouo ao problema original da di eta encontrando a solução ótima que custava somente 24 centavos me nos que a de Stigler por ano O próprio George Dantzig em um artigo de 1990 Dan90 conta a história do problema da dieta Anos depois de ter publicado o modelo seu médico teria recomendado que ele perdesse peso e ele então tentou modelar sua própria dieta e seguir o resultado produzido por um computador mas por diversas vezes deparouse com soluções absurdas que cladamente indicavam problemas na modelagem como a recomendação do consumo diário de quinhentos galões de vina gre duzentos cubos de caldo de carne e 900g de farinha ou melaço 38 CAPÍTULO 2 MODELAGEM Alguns dos exemplos desde Capítulo são adaptados do manual do texto de Bisschop Bis14 O método dado neste Capítulo para programação linear fracionária é simples mas resulta em um aumento do problema a ser resolvido Há mé todos mais eficientes Os livros de BajalinovEri03 e de StancuMinasian Sta97 trazem exemplos de modelagem e desenvolvem a teoria da programação linear fracionária Exercícios Ex 5 Suponha que uma fábrica possa produzir dois produtos diferen tes jaquetas e calças de poliéster Cada lote de jaquetas resulta em lucro de 500 para a empresa e cada lote de calças resulta em lucro de 700 Cada lote de jaquetas custa 10 e cada lote de calças custa 15 O or çamento mensal da empresa que pode ser destinado à produção é igual a 400 O lucro só é realizado muito mais tarde e cada lote deve ser pago antes da produção iniciar isso significa que há um limite para a quantidade de lotes produzidos em um mês Cada lote de jaquetas leva um dia para ser produzido e cada lote de calças precisa de dois dias A fábrica tem 22 dias por mês disponíveis para a produção A empresa tem um contrato com o governo que a obriga a produzir no mínimo 5 lotes de jaquetas por mês Além disso há baixa oferta de fechos para as calças somente um fornecedor com capacidade limitada e isto limita a produção de calças a 10 lotes por mês Formule o problema Ex 6 Um fazendeiro está estudando a divisão de sua propriedade nas seguintes atividades produtivas A Arrendamento Destinar certa quantidade de alqueires para a plantação de canadeaçúcar a uma usina local que se encarrega da atividade e paga pelo aluguel da terra 30000 por alqueire por ano P Pecuária Usar outra parte para a criação de gado de corte A re cuperação das pastagens requer adubação 100KgAlq e irrigação 100000 litros de águaAlq por ano O lucro estimado nessa ativi dade é de 40000 por alqueire por ano 24 PROGRAMAÇÃO NÃOLINEAR 39 S Plantio de Milho Usar uma terceira parte para o plantio de milho Essa cultura requer 200Kg por alqueire de adubos 200000 litros de águaAlq para irrigação por ano O lucro estimado nessa atividade é de 50000alqueire no ano A disponibilidade de recursos por ano é 12750000 litros de água 14000 Kg de adubo e 100 alqueires de terra O fazendeiro quer determinar quan tos alqueires deverá destinar a cada atividade para proporcionar o melhor retorno Formule o problema como programa linear Ex 7 Um veículo tem 100 unidades de combustível e deve andar por um labirinto acíclico Caminhos diferentes consomem mais ou menos combustível e dão ao veículo recompensas diferentes Sabendo o mapa e os custos e recompensas o veículo deve usar da melhor maneira possível suas 100 unidades de combustível Modele este problema como programa linear Ex 8 No exercício 7 exigimos que o labirinto e consequentemente o grafo que o representa fosse acíclico Explique porque e diga o que acon teceria com seu modelo de programa linear se o grafo tivesse ciclos Ex 9 Demonstre a equivalência dos dois problemas mostrados na Se ção 22 Ex 10 Generalize o exemplo para usar uma função nãolinear qual quer ao invés de um polinômio Nesta situação é útil criar uma nova variável por exemplo y que chamamos de variável indicadora cujo valor determina em qual dos intervalos está o valor da variável descontínua no nosso exemplo x y 0 se x 0 1 se x a b Tendo criado a nova variável as restrições passam a ser x by x ay y 0 1 Com isso temos y 0 0a x 0b x 0 y 1 1a x 1b a x b O modelo passa a ser de programação inteira porque y é binária Exemplo 211 232 Restrições condicionais Exemplo 212 233 Eliminando produtos de variáveis É possível que ao formularmos um problema como programação inteira tenhamos que usar no objetivo ou alguma restrição o produto de duas variáveis resultando em um problema de programação não linear No entanto em algumas situações é possível reformular o problema como programa linear Se o produto é de duas variáveis binárias x1 e x2 podemos substituir o produto por uma nova variável y com as seguintes restrições y x1 y x2 y x1 x2 1 y 0 1 Capítulo 3 Conjuntos Convexos e Soluções Viáveis O conjunto das soluções viáveis para um programa linear é um conjunto convexo Iniciamos este Capítulo com uma breve introdução à convexi dade e depois abordamos algumas propriedades das soluções de progra mas lineares 31 Conjuntos convexos Definição 31 Conjunto aberto Um conjunto X é aberto se para todo ponto x X há uma distância ϵ tal que qualquer ponto y cuja distância de x seja menor que ϵ também pertence a X A próxima figura mostra o intervalo 0 1 que é um conjunto aberto de números reais Com zero e um não pertencem ao intervalo temos que Para qualquer x 0 1 há alguma distância ϵ tal que podemos encon trar algum y 0 1 que fica não mais longe que ϵ de x Isto claramente acontece porque nem zero nem um pertencem ao conjunto e sempre po demos escolher algum número entre x e zero ou entre x e um x y 0 1 ϵ 04 Já o intervalo 0 1 não é aberto porque para x 1 e x 0 não conse guimos uma vizinhança ϵ totalmente contida no intervalo 41 42 CAPÍTULO 3 CONJUNTOS CONVEXOS E SOLUÇÕES VIÁVEIS Definição 32 Conjunto fechado Um conjunto é fechado se seu comple mento é aberto Exemplo 33 Os pontos internos de uma circunferência sem a borda que satisfazem x2 y2 r2 formam um conjunto aberto Já os pontos internos da circunferência determinados por x2y2 r2 formam um conjunto fechado A seguir mostramos os dois casos os pontos de uma circunferência sem a borda A e com a borda B A B aberto não aberto Mostramos a seguir os complementos desses conjuntos Note que como estamos trabalhando em R2 os retângulos não significam que os comple mentos são limitados complemento não aberto complemento aberto A B Afigura da esquerda mostra que o complemento do conjunto não é aberto portanto o conjunto A não é fechado Ada direita tem complemento aberto logo o conjunto B é fechado 31 CONJUNTOS CONVEXOS 43 Observe que um conjunto pode serfechado e aberto ao mesmo tempo e também pode não ser nem fechado e nem aberto Exemplo 34 O conjunto 0 1 não é aberto para x 1 escolha qualquer distância ϵ Não há valor δ 0 com δ ϵ e 1 δ 0 1 0 1 complemento Mas o conjunto também não é fechado porque seu complemento 0 1 não é aberto teremos o mesmo problema na fronteira do zero Exemplo 35 O espaço Rn é aberto porque para qualquer x Rn e dis tância ϵ há um y Rn cuja distância de x é menor que ϵ O complemento de Rn é o vazio E o vazio é também aberto por va cuidade a afirmaçãopara todo x sempre é verdadeira Assim Rn é fechado e também aberto Trabalharemos com problemas de otimização que são bem definidos em conjuntos fechados no conjunto x 0 1 por exemplo não pode mos selecionar o maior elemento Definição 36 Combinação afim Uma combinação afim de x1 x2 xn é uma combinação linear dos xi com a soma dos coeficientes igual a um Exemplo 37 Sejam x1 x2 x3 elementos quaisquer Então 01x1 04x2 07x3 é combinação afim de x1 x2 x3 porque 01 04 07 1 Definição 38 envoltória afim A envoltória afim de um conjunto X Rn denotada affX é o conjunto de todas as combinações afim dos elemen tos de X Exemplo 39 Aenvoltória afim de dois pontos diferentes é a reta passando por eles seja A x y com x 1 12 e y 2 1 A envoltória afim dos dois pontos é affX αx 1 αy α R Estes são os pontos da forma α 2 2α α2 1 α 2 α 2 α2 Por exemplo α 02 02 2 1 022 18 09 affX α 15 15 2 1 152 05 025 affX Como não temos restrição aos valores de α podemos dizer que os pontos são da forma a a2 a R Como está claro na figura os pontos da envoltória afim não são apenas aqueles entre os dois pontos x e y mas toda a reta passando pelos dois Exemplo 310 A envoltória afim de quatro ou mais pontos não coplanares em R³ é todo o R³ Seja B x y z com x 1 1 y 1 2 e z 3 1 Temos portanto affB αx βy 1 α βz α β R α α β 2β 3 3α β 1 α β A envoltória afim de três ou mais pontos não colineares mas coplanares é o plano em que eles estão Definição 311 Combinação convexa Uma combinação convexa de x₁ x₂ xₙ é uma combinação afim com coeficientes não negativos 31 CONJUNTOS CONVEXOS Exemplo 312 O Exemplo 39 identifica a envoltória afim dos pontos x 1 12 e y 2 1 Agora determinamos a envoltória convexa dos mesmos pontos Estes são os pontos da forma α 2 2α α2 1 α 2 α 2 α2 com α 0 1 α 0 ou seja α 0 α 1 O ponto 18 09 que identificamos na envoltória afim no Exemplo 39 também pertence à envoltória convexa porque usamos α 02 para calculálo Já 05 025 que havíamos verificado estar na envoltória afim não pertence à envoltória convexa porque foi calculo usando α 15 Apenas os pontos no segmento de reta entre x e y compõem a envoltória convexa Exemplo 313 Sejam x1 x2 x3 elementos quaisquer Então 02x1 03x2 05x3 é combinação convexa de x1 x2 x3 Exemplo 314 Em R2 a envoltória convexa do conjunto A 1 2 2 1 3 3 é composta de todos os pontos internos do triângulo formado pelos três pontos 46 CAPÍTULO 3 CONJUNTOS CONVEXOS E SOLUÇÕES VIÁVEIS 1 2 3 1 2 3 Definição 315 Conjunto convexo X Rn é convexo se x y X todas as combinações convexas de x e y também estão em X Alternativamente podemos dizer que um conjunto S de pontos é con vexo se para toda reta r S r é conexo ou seja S r forma um único segmento ou reta Exemplo 316 Qualquer intervalo fechado a b R é convexo Suponha que x y a b e x y Claramente temos a x y Então para qualquer combinação convexa z λx 1 λy temos x z y que implica que a z b e a combinação z a b Lembramos que os intervalos b e a são fechados Exemplo 317 Damos exemplos de conjuntos convexos e não convexos em R2 São convexos Os seguintes conjuntos de pontos não são convexos e em cada um há a indicação de dois pontos com combinação convexa fora do conjunto 31 CONJUNTOS CONVEXOS 47 Definição 318 Envoltória Convexa Aenvoltória convexa de um conjunto X Rn é o menor subconjunto convexo de Rn contendo X Denotamos a envoltória convexa de X por X Note que em muitos textos de Álgebra Linear usase X para o subes paço gerado por X todas as combinações lineares de vetores de X o que é diferente da envoltória convexa A figura a seguir ilustra um conjunto de pontos e sua envoltória con vexa em R2 Teorema 319 X é igual ao conjunto de todas as combinações convexas de subconjuntos finitos de X Demonstração Primeiro notamos que o menor conjunto convexo con tenxo X é o mesmo que a interseção de todos os conjuntos convexos contendo X Temos C Yi onde Yi são conjuntos convexos contendo X C é o conjunto de combinações convexas finitas de pontos de X C C basta verificar que C é convexo porque X C se X C então C contém o menor conjunto convexo contendo X Sejam x y C Mostraremos que qualquer combinação convexa de x e y também está em C ou seja qualquer combinação convexa de x e y é uma combinação convexa de pontos de X Sabemos que x y são combinações convexas de pontos de X x ap 1 aq p q X a 0 1 y bf 1 bg f g X b 0 1 CAPÍTULO 3 CONJUNTOS CONVEXOS E SOLUÇÕES VIÁVEIS Seja t 01 Então tx 1 ty é combinação convexa de pontos de X tx 1 ty tap 1 aq 1 tbf 1 bg atp 1 atq b1 tf 1 b1 tg Os pontos são p q f g e a soma dos coeficientes é at 1 at b1 t 1 b1 t a 1 at b 1 b1 t t 1 t 1 Podese por indução no número de pontos generalizar este resultado para combinações com mais pontos Assim como qualquer combinação convexa de pontos de C está em C ou seja é combinação convexa de pontos de x temos que C é convexo C C realizamos a prova por indução no número de pontos que denotaremos por m A base pode ser verificada trivialmente para m 1 e m 2 Para o passo consideramos m 3 Nossa hipótese de indução diz que todo ponto em C que é combinação convexa de m 1 pontos de X também está em todos os conjuntos convexos contendo X está em C Seja x t1x1 tmxm Note que x C Se tm 1 então x xm e o resultado vale trivialmente Se tm 1 seja então ti ti 1 tm i 1 2 m 1 Então temos ti ti 1 tm ti tm 1 tm 1 tm 1 tm 1 31 CONJUNTOS CONVEXOS 49 Então x t 1x1 t 2x2 t m1xm1 é combinação convexa de x1 x2 xm1 Pela hipótese de indução x C Como xm X então xm C Então x 1 tmx tmxm é combinação convexa de dois pontos em C e como C é convexo x C Cada restrição de um programa lineardefine uma região do espaço que chamamos de semiespaço Definimos a seguir hiperplano e semiespaço Definição 320 hiperplano Seja X um conjunto de pontos X Rn tal que para todo x X existem ai e b com pelo menos um ai diferente de zero a1x1 a2x2 anxn b Então X é um hiperplano em Rn Exemplo 321 Retas são hiperplanos em R2 e planos são hiperplanos em R3 Similarmente pontos são hiperplanos em R Definição 322 semiespaço Em Rn um semiespaço é a região de um dos lados de um hiperplano Em outras palavras são os pontos x tais que a1x1 a2x2 anxn b para determinados ai b R Exemplo 323 O conjunto x R x k com k constante é o intervalo k que é um semiespaço de R Exemplo 324 As soluções para uma desigualdade em Rn definem um semiespaço Semiespaços são convexos se S é o conjunto de pontos de um dos la dos de uma reta as combinações convexas de pontos de S também estarão naquele mesmo lado da reta Definição 325 Epigrafo Seja f Rn R uma função O epigrafo de f é o conjunto de pontos x1 x2 xn xn1 Rn1 tais que xn1 fx1 x2 xn CAPÍTULO 3 CONJUNTOS CONVEXOS E SOLUÇÕES VIÁVEIS A figura a seguir mostra o epigrafo da função fx x330 32 x 4 Definição 326 Ponto extremo de conjunto convexo Um ponto x S convexo é um ponto extremo de S se não é combinação convexa de outros pontos de S Exemplo 327 Qualquer ponto de uma parábola é ponto extremo de seu epigrafo Exemplo 328 Ilustramos alguns dos pontos extremos não todos nos conjuntos a seguir Teorema 329 Sejam S1 S2 Sn conjuntos convexos Então também são convexos Si Si e αSi α R 31 CONJUNTOS CONVEXOS 51 Demonstração Demonstramos apenas o caso da soma Os outros são pe didos no exercício 13 Sejam a b Si Sj Então a a1 a2 e b b1 b2 com a1 b1 Si e a2 b2 Sj Para 0 λ 1 λa 1 λb λa1 a2 1 λb1 b2 λa1 λa2 1 λb1 1 λb2 λa1 1 λb1 λa2 1 λb2 λa1 1 λb1 λa2 1 λb2 que está em Si Sj Definição 330 poliedro A interseção de um número finito de semies paços em Rn é um poliedro Podemos reescrever esta definição Definição 331 poliedro Um conjunto de pontos P Rn é um poliedro se e somente se pode ser descrito como P x Rn Ax b onde A é uma matriz m n e b Rn Um poliedro pode não ser limitado como por exemplo o poliedro de finido pelas inequações 5x1 2x2 2 6x1 25x2 27 2 ilustrado na figura a seguir x1 x2 1 0 1 2 3 4 1 0 1 2 3 4 5x1 2x2 2 6x1 25x2 27 2 Definição 332 Politopo Um politopo é um poliedro limitado Exemplo 333 Semiespaços e epígrafos de funções não são politopos Um polígono convexo triângulo quadrado pentágono etc em R² é um politopo A noção de dependência linear estendese naturalmente para combinações afim e convexas Definição 334 afimindependente Um conjunto de pontos é afimindependente quando nenhum deles é combinação afim dos outros Exemplo 335 Os pontos 1 1 e 2 3 são afimindependentes Se tentarmos escrever um como combinação afim do outro teremos 1 1 λ2 3 o que seria impossível já que precisaríamos de uma solução para o sistema 2λ 1 3λ 1 Os pontos 2 2 e 6 6 também são afimindependentes mesmo sendo linearmente dependentes se 6 6 λ2 2 temos o sistema 2λ 6 2λ 6 e deveríamos ter λ 3 mas para que a combinação fosse afim λ teria que ser um Exemplo 336 Os pontos 1 2 2 2 e 54 1 são afimdependentes Para verificar mostraremos que existem a b com a b 1 tais que 1 2 a2 2 b54 1 Para obter os coeficientes resolvemos o sistema 2a 54 b 1 2a b 2 a b 1 O sistema tem solução a 13 e b 43 e portanto 1 2 é combinação afim de 2 2 e 54 1 31 CONJUNTOS CONVEXOS 53 Definição 337 Dimensão de um politopo Um politopo P tem dimensão igual a d se d 1 é o maior número de pontos afimindependentes que podem existir em P Exemplo 338 Um ponto tem dimensão zero porque é um conjunto de um 01 único ponto Uma reta é um politopo de dimensão um porque um terceiro ponto sempre pode ser descrito como combinação afim de dois 11 outros na mesma reta Um triângulo tem dimensão dois porque um quarto ponto pode ser descrito como combinação afim de outros três 21 no mesmo plano Teorema 339 Um politopo P tem dimensão igual à dimensão de affP Exemplo 340 Sabemos que um triângulo tem dimensão dois De fato a envoltória afim do triângulo é R2 com dimensão dois Teorema 341 da separação pode hiperplano variante Sejam S e T dois subconjuntos convexos e disjuntos de Rn S T sendo pelo menos um deles limitado Então existem a Rn a 0 e b R tais que i aTx b para todo x S e ii aTx b para todo y T O Teorema 341 afirma que dois conjuntos convexos distintos podem serseparados porum hiperplano de forma que cada um deles esteja com pletamente contido em um semiespaço S T a Será útil percorrer idéias chave da demonstração antes de abordála O vetor a determina unicamente os ângulos entre o hiperplano e os eixos o valor b determina a distância da origem até o hiperplano O ângulo entre a e um vetor x é θ tal que cos θ aTx a x O sinal de cos θ é o mesmo sinal do produto aTx já que a x 0 Mas cos θ é positivo quando θ está no intervalo π2 π2 e negativo 54 CAPÍTULO 3 CONJUNTOS CONVEXOS E SOLUÇÕES VIÁVEIS quanto está em π2 3π2 O que significa que cos θ e consequen temente o produto aTx será negativo quando o ângulo entre x e a estiver em π2 3π2 Assim o sinal de produto aTx b determina em que semiespaço o vetor x está Definimos a distância entre dois conjuntos como a menor distância entre pontos entre eles Definição 342 A distância entre dois conjuntos convexos disjuntos S e T pelo menos um deles limitado é dS T inf sS tT s t Demonstração Definimos uma função f que caracteriza o hiperplano que o Teorema afirma existir já determinando o vetor a a q r b q2 r2 2 fx aTx b 32 Soluções viáveis para programas lineares Teorema 343 O conjunto S de soluções viáveis para um programa linear é fechado convexo e limitado por baixo Demonstração Pela restrição x 0 S é limitado por baixo Além disso S é interseção dos semiespaços definidos pelas restrições do problema e pela restrição de não negatividade Como os semiespaços são convexos e fechados S também é Teorema 344 Seja S o conjunto de soluções viáveis para um programa linear Então se existe solução ótima para o programa linear existe um ponto extremo em S com o valor ótimo Antes de elaborarmos a demonstração formal deste Teorema nota mos que é intuitivamente simples perceber o que está sendo enunciado Escolhemos um ponto dentro do poliedro Traçamos neste ponto um hi perplano ortogonal ao gradiente do objetivo e movemos esse hiperplano na direção do gradiente Há uma distância máxima que esse movimento pode ser feito sem que o hiperplano fique completamente fora do poliedro Quando essa distância é máxima o hiperplano toca o poliedro em um ponto extremo pode tocar em uma aresta ou face mas ainda assim ele toca um ponto extremo A figura a seguir ilustra graficamente esta intuição A seguir damos uma demonstração formal desse Teorema Demonstração do Teorema 344 S tem um número finito de pontos extremos que denotamos 1 x₁ x₂ xp Seja x₀ um ponto viável maximizando cᵀx em S x S cᵀx₀ cᵀx Suponha que x₀ não é ponto extremo Então x₀ pode ser descrito como combinação convexa dos pontos extremos de S x₀ Σ i1 até p λᵢ xᵢ λᵢ 0 Σ λᵢ 1 ¹Insistimos em mostrar os pontos como vetores Seja então xᵣ o ponto extremo com maior valor objetivo Então cᵀx₀ cᵀ Σ i1 até p λᵢ xᵢ Σ i1 até p λᵢ cᵀ xᵢ Σ i1 até p λᵢ cᵀ xᵣ cᵀ xᵣ Σ i1 até p λᵢ cᵀ xᵣ Temos então cᵀ x₀ cᵀ xᵣ Como x₀ é ótimo cᵀ x₀ cᵀ xᵣ e existe o ponto extremo xᵣ onde o valor do objetivo é ótimo Representamos as restrições de um problema na forma matricial como Ax b Exemplo 345 As restrições x₁ x₂ 10 x₁ x₃ 55 x₁ 2x₂ x₃ 20 são reescritas como igualdades adicionando variáveis de folga x₄ x₅ x₆ x₁ x₂ x₄ 10 x₁ x₃ x₅ 55 x₁ 2x₂ x₃ x₆ 20 Representamos as restrições portanto como 1 1 0 1 0 0 1 0 1 0 1 0 2 2 1 0 0 1 x₁ x₂ x₃ x₄ x₅ x₆ 10 55 20 32 SOLUÇÕES VIÁVEIS PARA PROGRAMAS LINEARES 57 A matriz A normalmente terá m linhas e n colunas com n m Presumiremos que o posto da matriz é m caso não seja sempre podemos eliminar uma das restrições Cada coluna de A representa uma variável Como a matriz tem posto m podemos tomar m colunas LI ou m variáveis formando uma matriz quadrada B de ordem m e resolver o sistema BxB b onde xB é o vetor composto pelas variáveis relacionadas às colunas em B Exemplo 346 Dando continuidade ao Exemplo 345 podemos escolher x1 x2 e x4 para compor a matriz B x1 x2 x3 x4 x5 x6 1 1 0 1 0 0 1 0 1 0 1 0 2 2 1 0 0 1 O sistema que representa as restrições passa a ser 1 1 1 1 0 0 2 2 0 B x1 x2 x4 xB 10 55 20 b A solução para este sistema é x1 55 x2 45 x4 0 No entanto esta não é ainda uma solução ótima para um problema de otimização porque nem sequer definimos uma função objetivo ainda A matriz B tem posto completo portanto o sistema sempre terá solução As variáveis representadas pelas colunas que usamos para formar B são chamadas de variáveis básicas e as outras são as variáveis não básicas Ao resolver o sistema determinamos valores para m variáveis Se fizermos as outras variáveis iguais a zero teremos uma solução para Ax b Exemplo 347 Finalizamos os Exemplos 345 e 346 uma possível solução para o sistema é x1 55 x2 45 x3 0 x4 0 x5 0 x6 0 Estão destacadas as variáveis que não foram usadas na construção da matriz B e que fixamos em zero 58 CAPÍTULO 3 CONJUNTOS CONVEXOS E SOLUÇÕES VIÁVEIS Formalizamos agora a definição de solução básica Definição 348 solução básica Seja Ax b o conjunto de restrições de um problema de programação linear onde A tem m linhas e n colunas Seja B uma matriz formada por m colunas linearmente independentes de A Então os vetores x tais que Bx b são chamados de soluções básicas para o problema Suponha que a matriz A tenha posto m A matriz B com m colunas LI é uma base para o espaçocoluna de A daí o nome solução básica Definição 349 solução viável básica x ℝⁿ é solução viável básica para um problema de programação linear se é viável e também básica Exemplo 350 Suponha que as restrições de um PL sejam 2x₁ 3x₂ 8 x₁ 2x₂ 2 Na forma padrão estas duas restrições são 2x₁ 3x₂ x₃ 8 x₁ 2x₂ x₄ 2 Estas restrições podem ser descritas como Ax b com A 2 3 1 0 1 2 0 1 x x₁ x₂ x₃ x₄ b 8 2 Como as duas linhas são LI claramente o espaço coluna de A é igual a ℝ² Tomamos duas colunas LI de A e obtemos uma base para seu espaçocoluna B 2 1 1 0 Qualquer solução para 2 1 1 0 x₁ x₃ 8 2 ou para qualquer outro sistema obtido da mesma forma com colunas LI de A é uma solução básica para o problema de programação linear Observe que não usamos x₂ Em uma solução básica gerada por esta base sempre teremos x₂ 0 Se mudarmos a base x₂ poderá ser positiva 32 SOLUÇÕES VIÁVEIS PARA PROGRAMAS LINEARES 59 Teorema 351 Seja S o conjunto de soluções viáveis para um programa linear Então uma solução viável x S é básica se e somente se é um ponto extremo de S Demonstração Seja x ponto extremo de S e sem perda de generalidade presuma que x₁ x₂ xₖ 0 e xₖ₁ xₙ 0 Mostraremos que as k primeiras colunas formam um conjunto LI sendo portanto uma solução viável básica Denotando a jésima coluna de A por aj temos a₁x₁ a₂x₂ aₖxₖ b 31 Suponha que a₁ aₖ são linearmente dependentes Então pela definição de dependência linear α₁ α₂ αₖ αi ai 0 32 com algum αi 0 Usaremos os coeficientes desta combinação linear para descrever o ponto xtremo x como combinação linear de outros pontos o que seria uma contradição Seja ε 0 Sejam x¹ x₁ εα₁ x₂ εα₂ xₖ εαₖ 0 0 0T x² x₁ εα₁ x₂ εα₂ xₖ εαₖ 0 0 0T Temos xj 0 para j k Então existe ε 0 tal que os primeiros k elementos de x¹ e x² são maiores que zero xj εαj 0 xj εαj 0 Podese verificar que 0 ε minj xj αj αj 0 satisfaz estas condições Temos portanto x¹ e x² viáveis ambos maiores que zero Mas x 12 x¹ 12 x² e x é combinação convexa de x¹ e x² não pode ser ponto extremo Concluímos que nossa hipótese era falsa a1 ak é linearmente independente e a solução é básica Suponha que x é uma solução viável básica com componentes x1 x2 xm 00 0 O valor dos xi é dado por j m aijxj bi i 12 m 33 Como a1 a2 am é linearmente independente as soluções são únicas Suponha que x não é ponto extremo de S Então deve ser combinação linear de duas soluções viáveis x1 e x2 diferentes entre si xj λx1j 1 λx2j j m 0 λx1j 1 λx2j j m para 0 λ 1 Como x1j x2j 0 então x1j x2j 0 para j m Restam os x1j e x2j com j m Como as soluções para o sistema 33 são únicas necessariamente temos xj x1j x2j mas havíamos presumido x1 x2 Concluímos então que x não pode ser descrito como combinação linear de pontos de S é um ponto extremo Exemplo 352 Novamente tomamos como exemplo um sistema com restrições Ax b e A 2 3 1 0 1 2 0 1 x x1 x2 x3 x4 b 8 2 Estamos portanto otimizando alguma função objetivo com as restrições 2x1 3x2 8 x1 2x2 2 A figura a seguir mostra a região viável Usando a base B 2 3 1 2 2 3 1 2 x1 x2 8 2 tem solução x1 227 x2 47 A solução é viável básica e na figura a seguir podemos observar que está em um ponto extremo Observe que uma solução viável que não esteja em um ponto extremo não é básica seja x1 1 x2 1 x3 3 x4 3 Esta solução é viável porque todas as variáveis são positivas e respeitam as restrições 62 CAPÍTULO 3 CONJUNTOS CONVEXOS E SOLUÇÕES VIÁVEIS x1 x2 1 83 1 1 folga x3 folga x4 No entanto não está em ponto extremo logo não é básica A figura mostra também que é as variáveis x3 e x4 tem folga a reta passando por 0 83 representa a restrição 2x1 3x2 8 que reescrevemos como 2x1 3x2 x3 8 Assim a distância mostrada é a folga da variável x3 o valor que poderia ser removido de x3 sem sair da região viável da mesma forma a reta passando por 0 1 representa a restrição x1 2x2 2 que reescrevemos como x1 2x2 x4 2 A distância mostrada é a folga de x4 Teorema 353 O conjunto de soluções ótimas para um programa linear é um conjunto convexo Demonstração Seja K o conjunto de soluções ótimas S o conjunto de so luções viáveis e x 1 x 2 K e z o valor ótimo da função objetivo dentro da região viável Então cTx 1 cTx 2 z Como são viáveis x 1 x 2 S e S é convexo portanto λx 1 1 λx 2 S 0 λ 1 Temos então cTx 1 x 2 λcTx 1 1 λcTx 2 λz 1 λz z Assim λx 1 1 λx 2 K para 0 λ 1 e K é convexo 32 SOLUÇÕES VIÁVEIS PARA PROGRAMAS LINEARES 63 Corolário 354 Se há mais de uma solução ótima para um programa linear há uma quantidade infinita e não enumerável delas Claramente o conjunto de soluções ótimas contém um único ponto se for um ponto extremo isolado ou infinitos pontos se for a envoltória convexa de alguns pontos extremos Exemplo 355 Analisaremos as soluções básicas do programa linear a se guir max 2x1 3x2 sa x1 15 x1 15 x1 3x2 2 3 x 0 Este programa linear tem cinco soluções básicas com os seguintes valores para a função objetivo x1 x2 valor 0 0 0 15 0 3 0 15 45 15 1 6 075 15 6 x1 x2 075 15 15 1 Dentre as soluções básicas duas são ótimas x1 15 x2 1 e x1 075 x2 15 Todas as combinações convexas delas o segmento entre os pontos 15 1 e 075 15 também tem o valor ótimo Teorema 356 Se existe solução viável para um programa linear então também existe solução viável básica Intuitivamente se há solução viável existe pelo menos um ponto na região viável Se isso acontece e sabendo que a região é convexa sabemos que deve haver também um ponto extremo viável A seguir está a demonstração Demonstração Sejam a1 a2 an as colunas de A e x x1 x2 xn viável x1a1 x2a2 b Suponha sem perda de generalidade que as k primeiras variáveis de x são maiores que zero e portanto x1a1 x2a2 xkak b Trataremos dois casos no primeiro a1 ak são linearmente independente No segundo são linearmente dependentes Primeiro caso colunas LI nesta situação k m porque A tem posto completo Se k m a solução é por definição básica Se k m então m k colunas podem ser obtidas de A para formar uma matriz m m com colunas a1 ak am todas LI Segundo caso colunas LD se a1 ak são LD então existem α1 αk com pelo menos um αj 0 tais que αjaj 0 Multiplicamos a equação por ε j1 to k εαjaj 0 34 Temos também da definição do programa linear que j1 to k xjaj b 35 Calculamos agora 35 34j1k xj aj ε αj aj bj1k aj xj ε αj b e portanto os xi ε αi formam uma solução para o sistema Ax b Para garantir que a solução é viável escolhemos ε minj xi αi αi 0 Seja p o índice do mínimo definido acima de forma que ε xp αp Para p xp ε αp xp xp αp αp 0 Para i p xi ε αi xi xp αi αp Como xi 0 e xp αi αp xi temos xi 0 não teremos uma solução inviável A variável de índice p tornase zero e a nova solução x x1 ε α1 xk1 ε αk1 0 0 tem então no máximo k 1 variáveis positivas Se as colunas associadas com estas k 1 variáveis ainda forem LD repetimos a operação senão o primeiro caso se aplica 33 Funções Convexas Nesta seção tratamos brevemente de funções convexas que são importantes para o desenvolvimento da teoria de otimização não linear Definição 357 Função convexa Uma função é convexa se seu epígrafo é convexo Uma função f é côncava se f é convexa A figura a seguir mostra o epígrafo da função convexa fx x² 3x 3 66 CAPÍTULO 3 CONJUNTOS CONVEXOS E SOLUÇÕES VIÁVEIS Teorema 358 Se f ℝⁿ ℝ é convexa e Domf é convexo então λ fx 1 λ fy fλ x 1 λ y para todos x y Domf e todo λ 0 1 Teorema 359 Se f1 f2 fm ℝⁿ ℝ são convexas então também são convexas gx max fix hx fix O teorema 360 nos dá uma segunda caracterização de funções convexas Teorema 360 Uma função f com domínio D ℝⁿ é convexa se e somente se para todos x₁ x₂ D e para todo λ 0 1 fλ x₁ 1 λ x₂ λ fx₁ 1 λ fx₂ Definição 361 Seja A uma matriz quadrada simétrica A é semidefinida positiva se xᵀ A x 0 para todo x A é definida positiva se xᵀ A x 0 para todo x 0 E A é indefinida se xᵀ A x assume valores positivos e negativos Teorema 362 Uma matriz quadrada é semidefinida positiva se todos seus autovalores são nãonegativos 33 FUNÇÕES CONVEXAS 67 Exemplo 363 A matriz A 1 1 1 1 2 3 1 3 6 é semidefinida positiva Observamos que x A x 6 x3² 2 x2² x1² 6 x2 x3 2 x1 x3 2 x1 x2 Como não é imediatamente óbvio que este valor é sempre positivo verificamos os autovalores da matriz que são λ1 4 15 λ2 4 15 λ3 1 todos positivos Exemplo 364 Seja A 1 2 2 1 Os autovalores de A são 1 e 3 portanto A não é semidefinida positiva Realmente se tomarmos os dois vetores x 1 1 y 1 1 como x A x 6 y A y 2 vemos claramente que a matriz A é indefinida Definição 365 Matriz Hessiana Seja f ℝⁿ ℝ duas vezes diferenciável A matriz Hessiana de f em x denotada por Hfx ou ² fx é a forma bilinear ² xij ² fx xi xj ou ² fx ² f x1² x ² f x1 x2 x ² f x1 xn x ² f x2 x1 x ² f x2² x ² f x2 xn x ² f xn x1 x ² f xn x2 x ² f xn² x Exemplo 366 Seja fR² R tal que fx y cosy 2x²y A Hessiana de f é ²f 4y 4x 4x cosy Lema 367 Seja S um subconjunto não vazio aberto e convexo de Rⁿ Seja f S R diferenciável Então f é convexa se e somente se para todos x x Rⁿ fx fx fxᵀx x O Lema 367 nos diz que f é convexa se e somente se seu gráfico está sempre acima de qualquer plano tangente a ele ou seja que seu epígrafo é convexo Exemplo 368 A função fx 2x² 1 é convexa já que sua Hessiana é ²fx 4 Verificamos que de fato fx fxᵀx x fx 4xx x 2x² 4xx x 2x² 4xx x 2x² 4xx 4x² 2x² Além de verificar algebricamente observamos o gráfico de fx e percebemos que realmente os planos tangentes sempre ficam abaixo do gráfico Exemplo 369 A função fx x³ x² x 1 não é convexa Vemos que o plano tangente não fica sempre acima de todos os pontos do gráfico como é possível perceber na figura a seguir Teorema 370 Seja f D R com D Rⁿ não vazio aberto e convexo e f contínua e duas vezes diferenciável f é convexa se e somente se ²fx é semidefinida positiva para todo x Domf Exemplo 371 Seja fa b a⁴ b² Temos ²fa b 12a² 0 0 2 Já podemos perceber que os autovalores da Hessiana são a constante dois e 12a² que são sempre positivos e a função é convexa Podemos também verificar que xᵀ²fa bx é sempre positivo Para qualquer x R² xᵀ²fa bx 12a²x₁ 2x₂x₁ x₂ 12a²x₁² 2x₂² 0 portanto f é convexa em R² Exemplo 372 Seja fa b eᵃ eᵇ Então ²fa b eᵃ 0 0 eᵇ Novamente notamos que os autovalores são positivos a função é convexa Para qualquer x R² xᵀ²fa bx x₁eᵃ x₂eᵇx₁ x₂ x₁²eᵃ x₂²eᵇ 0 portanto f é convexa em R² Poderíamos também ter observado que f é a soma de eᵃ com eᵇ duas funções convexas e a soma de funções convexas sempre é convexa Exemplo 373 Seja fa b a b² Então ²fa b 2 2 2 2 Para qualquer x R² xᵀ²fa bx 2x₁ 2x₂ 2x₁ 2x₂x₁ x₂ 2x₁² 2x₂² 4x₁x₂ A função quadrática 2x₁² 2x₂² 4x₁x₂ é sempre positiva portanto f é convexa em R² Os autovalores da Hessiana são 0 e 4 Exemplo 374 Seja fa b a³ b² Construímos a Hessiana no ponto a b ²fa b 6a 0 0 2 Os autovalores são 6a e 2 Quando a for menor que zero o primeiro autovalor será negativo e f não é convexa No entanto podemos dizer que f é convexa se tiver seu domínio restrito a a 0 33 FUNÇÕES CONVEXAS Notas Normalmente livros abordando Otimização Convexa inclusive Programação Linear tratam de Análise Convexa e sua relação com otimização Por exemplo os livros de Sinha Sin06 Matousek MG06 e Luenberger Lue10 tratam do assunto O Teorema 370 é demonstrado em diversos livros de otimização não linear por exemplo nos livros de Mokhtar Bazaraa Hanif Sherali e C M Shetty BSS06 e de Andrzej Ruszczyski Rus06 Os livros de Alexander Barvinok Bar02 e de Steven Lay Lay07 abordam detalhadamente o tópico de Convexidade O livro de Dimitri Bertsekas e Angelia Nedic BN03 também aborda convexidade e sua relação com otimização Uma discussão em maior densidade de conjuntos e funções convexas é encontrada no livro de Rockafellar Roc96 Exercícios Ex 11 Mostre como construir um poliedro com nkm vértices para qualquer 1 k n e quaisquer nn com n m descrevendo o poliedro como interseção de semiespaços Ex 12 Dissemos que um conjunto S de pontos é convexo se e somente se para toda reta r S r é um único segmento de reta ou seja conexo Demonstre que esta definição é equivalente à definição 315 Ex 13 Demonstre o que falta do Teorema 329 Ex 14 Mostre que para quaisquer a b c α β γ com a α 0 a interseção dos conjuntos xy y αx² bx c e xy y αx² βx γ em R² é convexa Ex 15 Sejam a e b dois pontos O conjunto de pontos que não são mais próximos de b do que a é xdistxa distxb Este conjunto é convexo Ex 16 Determine precisamente quando um subconjunto de R² definido por um conjunto de inequações quadráticas xy y ax² bx c é convexo Generalize para mais que duas dimensões Ex 17 Prove o lema 367 72 CAPÍTULO 3 CONJUNTOS CONVEXOS E SOLUÇÕES VIÁVEIS Ex 18 Mostre que o conjunto de todas as matrizes semidefinidas posi tivas é convexo Ex 19 Mostre que uma função f em Rn é linear se e somente se f é con vexa e côncava Ex 20 Mostre que nenhuma função polinomial de grau ímpar maior ou igual a 3 e em uma variável é convexa Ex 21 Determine se são convexas i fa b ea logb ii ga b ea logb iii ha b eaeb iv ja b loga logb Ex 22 Prove que fx x2 1x2 é convexa em R2 onde x2 0 Ex 23 Identifique subdomínios onde as funções são convexas i fx y senx cosy ii gx y senx cosy iii hx x logx iv jx y z ex z logy v kx y z ex logxy z2 Ex 24 Prove o Teorema 358 Ex 25 Prove o Teorema 359 Ex 26 Suponha que queiramos otimizar uma função linear sujeita a restrições estritamente não lineares Se soubermos que a região viável é convexa quantas soluções ótimas podemos ter no máximo E se a região viável não for convexa Ex 27 Suponha que saibamos que um problema de programação linear é viável e limitado e portanto tem solução ótima Sem tentar resolvêlo há como verificar se ele tem somente uma ou infinitas soluções ótimas Ex 28 Seja Rx o conjunto de todos os polinômios em x com coefici entes reais Seja S o subconjunto de Rx que são positivos no intervalo 0 1 Mostre que S é convexo Capítulo 4 O Método Simplex Neste Capítulo tratamos do método mais conhecido para resolver proble mas de Programação Linear o método Simplex 41 Exemplo inicial Introduzimos o método com um exemplo Considere o problema de pro gramação linear max x1 2x2 sujeito a x1 x2 10 2x1 3 4x2 5 x1 x2 3 Transformamos o problema para que as restrições fiquem na forma de igualdades x1 x2 x3 10 2x1 3 4x2 x4 5 x1 x2 x5 3 e usaremos agora alguns passos do algoritmo Simplex Temos cinco variáveis e queremos inicialmente uma solução básica viável Olhando para o problema notamos que podemos usar x3 10 x4 5 e x5 3 com as outras variáveis iguais a zero Temos então três 73 74 CAPÍTULO 4 O MÉTODO SIMPLEX variáveis não zero e a solução é claramente viável Temos uma solução viável básica e o valor da função objetivo para essa solução é zero x₁ 2x₂ 0 0 Note que os coeficientes das variáveis não zero x₃ x₄ x₅ é um e os manteremos assim durante toda a execução do algoritmo Simplex Representaremos o sistema de equações na forma de matriz a base está destacada x₁ x₂ x₃ x₄ x₅ b 1 1 1 0 0 10 2 34 0 1 0 5 1 1 0 0 1 3 e podemos então reescrever as variáveis da forma como quisermos simplesmente usando operações elementares semelhante aos passos de eliminação de Gauss exceto que nosso objetivo não é transformar a matriz em forma triangular O objetivo é escrever as variáveis básicas como função das não básicas No tableau anterior a segunda linha por exemplo significa 2x₁ 34x₂ 0x₃ x₄ 0x₅ 5 Isolando x₄ que é a única variável básica com coeficiente diferente de zero nesta linha x₄ 52x₁ 34x₂ Neste momento a solução atual dá o valor 500 5 para x₄ A representação da linha nesta forma nos ajuda a compreender o que acontecerá quando dermos valores positivos a x₁ e x₂ Todo tableau Simplex pode ser lido portanto como uma expressão das variáveis básicas ou da solução atual em função das nãobásicas Agora introduzimos x₂ na base retirando x₅ Reescreveremos o sistema de forma que a coluna relativa a x₂ tornese igual à coluna que agora representa x₅ Conceitualmente tomaremos a linha onde tínhamos x₅ representada como função das outras e isolaremos x₂ que passará a ser então representada como função das não básicas Para isso usamos operações elementares de forma a tornar a₃₂ 1 e a₁₂ a₂₂ 0 Primeiro dividimos a linha 3 por a₃₂ 1 e obtemos 1 1 0 0 1 3 42 FORMULAÇÃO 75 Somamos múltiplos desta linha às outras para obter zeros no resto da coluna dois somamos 34 da linha 3 à linha 2 e somamos 1 vezes a linha 3 à linha 1 x₁ x₂ x₃ x₄ x₅ b 2 0 1 0 1 7 54 0 0 1 34 114 1 1 0 0 1 3 A nova base está destacada na matriz Temos agora x₁ x₅ 0 x₂ 3 x₃ 7 e x₄ 114 O valor do objetivo para esta solução é x₁ 2x₂ 6 Representamos também a função objetivo como um vetor coluna c 1 2 0 0 0ᵀ e a solução x 0 3 7 114 0ᵀ Assim podemos expressar cᵀx 1 2 0 0 0 0 3 7 114 0 6 Conseguimos uma solução com x₂ 3 melhor que a inicial Se incluirmos x₁ também na base a solução será ainda melhor O algoritmo Simplex determina quais variáveis devemos incluir e excluir da base a cada passo de forma que cada solução seja melhor que a anterior e que todas sejam viáveis garantindo assim que após um número finito de passos obterhamos a solução ótima 42 Formulação No resto do texto usaremos uma matriz A m n e vetores coluna b com m elementos e c com n elementos de forma que programas lineares sejam descritos como max cᵀx sa Ax b x 0 sendo x um vetor coluna com n elementos representando as variáveis para as quais queremos obter valores que maximizem cᵀx Será útil dividir estes objetos matriz A e vetores c e x em duas partes as que se referem às variáveis da base AB cB xB e as que se referem às variáveis fora da base AN cN xN Presumimos que as colunas de A e os elementos de x e c sempre são reordenados de forma que as variáveis da base estejam à esquerda das outras isso nos garante que a base é representada por uma submatriz m m no lado esquerdo de A isso apenas facilita a exposição do assunto não interferindo em nada mais A AB AN cT cBT cNT x xB xN Isto significa que a matriz AN e os vetores cN e xN tem índices iniciando em m 1 AN am1 am2 an cNT cm1 cm2 cn xN xm1 xm2 xn 43 Intuição geométrica No capítulo 3 verificamos que as soluções viáveis básicas para um problema de programação linear são os pontos extremos do poliedro definido pelas restrições Nas próximas seções desenvolveremos o método Simplex que verifica uma sequência de pontos extremos ou de soluções viáveis básicas para o problema até chegar à solução ótima Damos aqui uma intuição simples de como é o funcionamento do Simplex Saindo de alguma solução viável básica ponto extremo o Simplex procura outra solução que possa obter trocando uma única coluna da base portanto algum ponto extremos adjacente ao atual e que ofereça vantagem ou seja cujo valor objetivo seja melhor que o da solução atual Prossegue assim até o momento em que não haja pontos extremos adjacentes com valor melhor que o atual que portanto deve ser ótimo Exemplo 41 Ilustraremos esta idéia com o seguinte problema com duas variáveis max 2x1 x2 sa x2 3 2x1 x2 4 3x1 x2 1 x 0 43 INTUIÇÃO GEOMÉTRICA 77 A representação gráfica da região viável deste problema é dada a seguir x2 x1 x2 3 2x1 x2 4 3x1 x2 1 Começamos com a solução viável básica x1 0 x2 0 ou seja x 0 e mudamos uma coluna da base por vez primeiro para 13 0 e depois para a solução ótima 1 2 Tínhamos inicialmente uma base com variáveis de folga Na primeira mu dança de 0 0 para 13 0 retiramos a folga da restrição 3x1 x2 1 e determinamos para x1 o maior valor possível respeitando a restrição che gamos a uma nova base onde a folga desta restrição é zero e o valor de x1 é 13 Depois retiramos a folga da restrição 2x1 x2 4 e aumentamos o valor de x2 chegando à solução ótima 1 2 As derivadas parciais do objetivo no ponto 1 2 e na direção de seus pontos extremos vizinhos são todas negativas portanto não há como me lhorar a solução 44 Coeficientes reduzidos de custo Embora possamos facilmente identificar de maneira visual a restrição e consequentemente a coluna que deve entrar na base no próximo passo do Simplex em problemas com duas variáveis esta intuição visual não é suficiente para implementar o algoritmo que deve funcionar para dimensões arbitrárias Para cada variável não básica em um tableau Simplex existe um número que usaremos para decidir se ela deve ou não entrar na base Daremos duas definições diferentes mas equivalentes para estes números chamados de coeficientes reduzidos de custo 441 Primeira definição Nossa primeira definição para coeficiente reduzido de custo é como a derivada do objetivo na direção de cada variável não básica porque com elas poderemos determinar exatamente quais variáveis melhorarão o objetivo se as incluirmos na base O valor do objetivo usando apenas as variáveis básicas é dado por z0 cBT xB Agora partimos do sistema Ax b Ax b AB xB AN xN b Como sempre manteremos as variáveis básicas com coeficientes unitários sempre teremos AB I xB b AN xN cBT xB cBT b cBT AN xN Seja z cBT AN de forma que zj c1 a1j c2 a2j cn amj para j m lembrese que os índices das colunas de AN começam com m 1 z cBT AN c1 c2 cm a1m1 a1m2 a1n amm1 amn zm1 zm2 zn onde zj i m ci aij Indexamos z a partir de m 1 porque tem n m elementos um para cada variável não básica Então cBT xB cBT b z xN z0 z xN porque z xN 0 o vetor xN com variáveis não básicas vale zero Mesmo que esta expressão valha zero a manteremos ali porque posteriormente ela será importante quando quisermos saber o que acontece quando mudamos o valor de alguma variável não básica Assim j m cj xj z0 j m zj xj Temos somente as variáveis básicas no lado esquerdo Se somarmos as não básicas obteremos cT x Assim somamos j m cj xj aos dois lados da equação obtendo cT x z0 j m cj xj j m zj xj z0 j m cj zj xj Podemos então descrever o valor da função objetivo usando apenas z0 o valor calculado usando as variáveis básicas e os valores das variáveis não básicas cT x z0 j m cj zj xj Esta equação é importante porque mostra o quanto o valor da função objetivo aumenta se aumentarmos o valor de uma das variáveis não básicas se aumentarmos uma variável não básica xj de zero para k o objetivo aumentará em kcj zj Esta informação será usada para determinar que variáveis devem ter seu valor aumentado pelo algoritmo Simplex Observe também que cT x xj cj zj e que os valores de cj zj nos dizem as direções em que podemos melhorar o valor da função objetivo 80 CAPÍTULO 4 O MÉTODO SIMPLEX Definição 42 Coeficiente reduzido de custo Em um programa linear os valores rj cTx xj cj zj são chamados de coeficientes reduzidos ou relativos de custo e deter minam em quanto cada variável não básica melhora o objetivo quando seu valor é aumentado em uma unidade 442 Segunda definição A segunda definição de coeficiente reduzido de custo equivalente à pri meira é como a diferença de valor que uma coluna tem na base e fora dela ou seja quanto ganhamos se a incluirmos na base Também podemos definir o coeficiente reduzido de custo de outra maneira Chamamos AB de base porque ela é de fato base para o espaço coluna de A Qualquer coluna de A pode portanto ser escrita como com binação linear das colunas de AB Podemos facilmente calcular o valor de uma variável quando ela está na base basta olhar para seu coeficiente cj no objetivo Quando a variável não está na base podemos calcular o valor de sua coluna se a escrevermos como combinação linear da base usandos os va lores das colunas básicas Por exemplo suponha que uma coluna aj esteja fora da base Então aj α1a1 α1am α1 a11 am1 αm a1m amm Para obter o valor da coluna não básica aj usamos sua expressão como combinação linear da base e multiplicamos cada elemento por seu custo cj c1α1a1 cmα1am c1α1 a11 am1 cmαm a1m amm cT BAB 44 COEFICIENTES REDUZIDOS DE CUSTO 81 Este é o valor de uma coluna de AN Quando fazemos o mesmo com todas as colunas temos z cT BABAN e se mantivermos a base representada como identidade temos z cT BAN Assim enquanto cj nos dá o valor de uma variável quando ela está na base zj nos dá seu valor quando a construímos sinteticamente quando ela não está na base O coeficiente reduzido de custo rj cj zj é a diferença entre os dois e nos informa quanto poderemos ganharincluindo a variável na base Claramente quando todos os rj forem negativos não há como melhorar a solução 443 Representação no tableau Adicionamos a equação que dá o valor do objetivo ao sistema Ax b a11x1 a12x2 a1nxn b1 a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bm c1x1 c2x2 cnxn z z0 Reescrevendo a última linha usando apenas as variáveis não básicas z z0 rm1x1 rm2x2 rnxn obtemos a11x1 a1mxm a1m1xm1 a1nxn 0 b1 a21x1 a2mxm a2m1xm1 a2nxn 0 b2 am1x1 ammxm amm1xm1 amnxn 0 bm 0 0 rm1xm1 rnxn z z0 onde rj cj zj A coluna 0 0 zT nunca será parte de uma base portanto não a representaremos nos tableaux 444 Exemplo Damos agora um exemplo do cálculo dos coeficientes reduzidos de custo Exemplo 43 Suponha que um programa linear tenha como objetivo maximizar a função 2x1 3x2 x3 Duas variáveis x4 e x5 foram adicionadas para transformar restrições de desigualdade em igualdade Suponha que o seguinte tableau tenha sido encontrado durante a execução do método Simplex x1 x2 x3 x4 x5 b 1 3 0 1 0 4 0 1 0 2 1 5 0 4 1 3 0 12 A base é formada por x1 x3 e x5 mas a ordem das colunas da base é x1 x5 x3 porque as colunas da base são x1 x3 x5 1 0 0 0 0 1 0 1 0 Se as reorganizarmos para formar a identidade chegamos a AB x1 x5 x3 1 0 0 0 1 0 0 0 1 Assim o vetor de custos deve ter as variáveis na mesma ordem cBT x1 x5 x3 2 0 1 Isto porque usaremos não somente índices de colunas mas também de linhas para facilitar o desenvolvimento mais adiante A iésima variável básica tem sua coluna igual a ei o iésimo vetor da base canônica Os coeficientes reduzidos de custo da base são zero Para obter os coeficientes reduzidos de custo de x2 e x4 calculamos zT cBTAN e r c z cBTAN 2 0 1 3 1 1 2 4 3 10 1 Temos portanto z2 10 z4 1 45 A OPERAÇÃO DE MUDANÇA DE BASE 83 e os coeficientes são r2 c2 z2 3 10 7 r4 c4 z4 0 1 1 O tableau completo tem os coeficientes reduzidos de custo das variáveis não básicas na última linha e o valor do objetivo na última posição com sinal trocado x11 x23 x30 x4 1 x50 b 4 0 1 0 2 1 5 0 4 1 3 0 12 0 7 0 1 0 20 Os coeficientes reduzidos de custo são z x2 c2 z2 7 z x4 c4 z4 1 Como os coeficientes reduzidos de custo são todos negativos 7 e 1 a solução já é ótima não há variáveis que possam ser incluidas na base au mentando o valor da solução 45 A operação de mudança de base Outra maneira de visualizar o tableau Simplex AB AN b cT B cT N z0 Queremos percorrerdiferentes bases do programa linear sempre aumen tando o valor da função objetivo Manteremos as colunas da base sempre formando uma matriz identidade mm Como já vimos antes isto repre senta a descrição de cada uma das variáveis básicas em função das não básicas Suponha agora que queiramos incluir uma variável xq na base reti rando xp Podemos escreverxq em função das variáveis não básicas inclu sive xp Para isso basta operarmos as linhas do tableau forçando a coluna aq a ficar igual a ap Para isso podese usar a operação definida a seguir A fim de simplificar as referências ao tableau usaremos ain1 para bi e am1j para rj 84 CAPÍTULO 4 O MÉTODO SIMPLEX Proposição 44 Seja um tableau Simplex representando o programa linear definido por A b e c Seja ap uma coluna da base e aq uma coluna fora da base Então a seguinte operação modifica a coluna aq de forma que fique idêntica a ap podendo substituíla na base e modifica também todas as colunas de AN inclusive ap de maneira que as soluções de Ax b sejam as mesmas Para todo elemento aij inclusive na coluna b e na linha do objetivo faça a pj apj apq a ij aij apjaiq apq i p Demonstração A coluna ap tinha zeros exceto em app onde tinha um Para aq temos a pq apqapq 1 e podese verificar que para todo i p a iq 0 A operação não muda as soluções a primeira é multiplicação de linha por escalar e a segunda é soma de múltiplo de linha a outra 46 Que variável entra na base Sabemos como retiraruma coluna ap da base trocandoa poroutra coluna aq Agora tratamos de como escolher a coluna ou seja a variável que deve ser incluída na base Já sabemos que os coeficientes reduzidos de custo dados por rj cj zj nos informam quanto uma unidade de cada variável não básica xj aumenta a função objetivo e podemos portanto escolher alguma variável com rj 0 presumindo que estamos maximizando se estivermos mini mizando escolhemos rj 0 tendo assim a garantia de que melhoraremos a solução Este raciocínio é formalizado no teorema 45 Teorema 45 Seja x uma solução viável não degenerada para um pro blema de programação onde queiramos maximizar o objetivo sendo z o valor de x Se o programa linear é limitado e existe j tal que cj zj 0 então há uma solução viável x com valor z z e x pode ser obtida in cluindo aj na base Demonstração Temos x x1 x2 xm 0 0 Suponha sem perda de generalidade que j m 1 Seja então x x 1 x 2 x m x m1 0 0 com xm1 0 uma solução viável Temos z z Σjm cj zj xj Como nesta soma somente xm1 0 z z cm1 zm1 xm1 Mas tanto cm1 zm1 como xm1 são positivos portanto z z0 0 e z z Os dois corolários a seguir são consequências simples do teorema 45 Corolário 46 Se cj zj 0 para todo j a solução representada no tableau é ótima Corolário 47 Se cj zj 0 para alguma variável não básica xj então há mais de uma solução viável básica ótima e consequentemente infinitas soluções ótimas Proposição 48 Se aij 0 para todos i e j o problema é ilimitado Pode haver mais de um j tal que cj zj 0 e nem sempre o maior deles é a melhor opção Precisamos de um critério de escolha Dentre os critérios que podem ser usados merecem ser mencionados os seguintes Maior coeficiente reduzido de custo a regra proposta originalmente por George Dantzig Maior aumento absoluto no objetivo Verificase quanto uma unidade de cada variável xj valeria e multiplicase por cj O maior valor é escolhido Aresta mais íngreme com o maior aumento no valor do objetivo para cada unidade de distância Se a solução viável básica atual é x e estamos considerando outra x então a diferença entre os valores de objetivo é cT x cT x ou cT x x A distância percorrida de x até x é a norma de x x Assim escolhemos maxx cT x x x x Regra de Bland escolha a variável com menor índice A única vantagem desta regra é a de garantir que não haverá ciclos Escolha aleatória que pode ser uma boa escolha por resultar em baixa probabilidade de ciclos usualmente convergindo mais rápido que quando a regra de Bland é usada Estritamente falando nenhuma das regras é melhor que as outras podese construir exemplos onde cada uma delas leva a convergência mais lenta que alguma outra regra Exemplo 49 Suponha que em um problema com vetor de custos cT 1 2 3 1 tenhamos o seguinte tableau x1 x2 x3 x4 x5 x6 x7 b 1 0 6 0 1 2 1 10 12 1 1 0 0 12 12 5 12 0 1 1 0 12 12 10 20 A base é formada por x5 x2 e x4 AB x5 x2 x4 1 0 0 0 1 0 0 0 1 O vetor de custos das básicas é cBT x5 x2 x4 0 2 1 As colunas não básicas de A são AN x1 x3 x6 x7 1 6 2 1 12 1 12 12 12 1 12 12 e portanto z cBTAN 0 2 1 1 6 2 1 12 1 12 12 12 1 12 12 x1 x3 x6 x7 32 3 32 12 47 QUE VARIÁVEL SAI DA BASE 87 Finalmente temos cN1 z1 1 32 12 cN2 z2 3 3 6 cN3 z3 0 32 32 cN4 z4 0 12 12 Inserimos os coeficientes reduzidos de custo no tableau x1 1 x20 x36 x40 x51 x62 x7 1 b 10 12 1 1 0 0 12 12 5 12 0 1 1 0 12 12 10 12 0 6 0 0 32 12 20 Dentre as não básicas somente x3 e x6 tem coefciente reduzido de custo positivo portanto é uma destas que deve entrar na base 47 Que variável sai da base Sabendo a coluna que entrará na base nos resta escolher uma coluna da base para remover Como estaremos retirando um valor que contribui para o objetivo devemos escolher uma variável que ao ser removida re moverá do objetivo o menor valor possível para problemas de maximiza ção para minimização todo o raciocínio é simétrico 471 Intuição Esta seção passa a intuição que fundamenta o raciocínio da remoção de variáveis da base em um tableau Simplex Não é demonstração formal porque é feita com pouco rigor e apenas para R2 mas deve ajudar a com preender a explanação rigorosa na seção seguinte Podemos interpretar todas as variáveis em um problema como se fos sem de folga Como primeiro exemplo temos um problema extrema mente simples max x1 x2 sa x1 2 x2 1 x 0 88 CAPÍTULO 4 O MÉTODO SIMPLEX Podemos reescrever este problema explicitando cada uma das restrições de nãonegatividade apenas para maior clareza max x1 x2 sa x1 2 x2 1 x1 0 x2 0 Suponha que tenhamos começado com a solução viável básica x1 x2 0 A folga da restrição x1 0 é zero Quando aumentamos o valor de x1 para 2 estamos aumentando a folga desta restrição 1 2 Temos portanto claro agora que toda vez que incluímos uma variável na base podemos entender que estamos aumentando a folga de uma restri ção Nos resta determinar quanto podemos avançar em uma dada direção Considere o seguinte problema max x1 x2 sa x1 x2 3 x1 2 x2 2 x1 x2 1 x 0 Mostramos a seguir a região viável Suponha que estejamos conside rando o ponto extremo 0 0 e que queiramos incluir x1 na base A figura mostra os pontos extremos onde podemos chegar mudando o valor de x1 O ponto 00 toca nas restrições x₁ 0 e x₂ 0 portanto estas tem folga zero e as outras folgas estão na base com valor positivo Se retirarmos a folga da restrição x₁ x₂ 3 estaremos aumentando o valor de x₁ até tocarmos nesta restrição mas então chegaremos ao ponto 03 que está fora da região viável Se removermos a folga da restrição x₁ x₂ 1 estaríamos diminuindo o valor de x₁ porque é a única maneira de chegar na reta x₁x₂ 1 saindo de 00 Além de cairmos fora da região viável estaríamos indo no sentido oposto ao que queremos iríamos na direção contrária à da derivada direcional zx₁ A opção correta é portanto retirar a folga da variável que representa o ponto mais próximo na direção em que estamos nos movendo ou seja a variável cuja folga é a menor dentre as folgas positivas Em nosso exemplo queremos aumentar x₁ somente até chegar na restrição x₁ 2 Sabendo que incluiremos a variável xᵢ na base precisamos então calcular os valores das folgas para cada variável que poderíamos retirar Isso é feito observando o tableau Suponha que queiramos incluir a variável xq na base Ela deixará de ser zero e a folga de alguma restrição passará a ser aumentada nesse valor Assim para cada possível variável xₚ a sair da base verificamos qual seria o valor de xq se xₚ saísse basta determinar o pivô no tableau e escolhemos o menor dos positivos Procuramos portanto dentre todos os valores positivos bᵢaᵢⱼ o menor Se a variável a entrar na base é xq então a variável a sair é xₚ onde p argmini mxᵢaᵢq aᵢq 0 472 Elaboração com rigor Seja x x₁ x₂ xm0 0 uma solução viável básica a₁x₁ a₂x₂ am xm b 41 Queremos introduzir aq na base Quem sai Observamos que como AB é base para o espaçocoluna de A aq pode ser descrita como combinação linear de colunas de AB Mais ainda a base que usamos é canônica é a matriz identidade Assim temos a₁q a₁ a₂q a₂ amq am aq 42 Exemplo 410 Suponha que a matriz de coeficientes seja A x₁1 0 2 1 x₂0 1 5 7 e que a base seja formada pelas duas primeiras colunas AB x₁1 0 x₂0 1 Queremos escrever a coluna a₃ da matriz 25 2 10 5 01 Agora escolha um ε 0 Calculamos 41 ε42 a₁x₁ a₁q ε amxm amq ε b ε aq ε aq a₁x₁ a₁q ε amxm amq ε b e portanto ε aq Σi m ai xi ε aiq b Temos agora m1 variáveis diferentes de zero porque introduzimos a coluna aq e consequentemente a variável xq Deixamos de ter uma base porque temos colunas LD As variáveis do novo sistema são xi ε aiq Podemos remover uma das colunas tornando uma dessas variáveis zero e faremos isto variando ε a partir do zero Para ε suficientemente pequeno mas não zero xi ε aiq é uma solução viável mas não básica com ε 0 temos a solução básica da qual partimos x Queremos aumentar ε tanto quanto pudermos mas sem tornar nenhum xi ε aiq negativo porque assim tornaríamos a solução inviável Além disso observamos que se aiq 0 não adianta tentar aumentar ε aquela coluna não sairá da base Queremos então que i m xi ε aiq 0 xi ε aiq xiaiq ε Assim escolhemos para deixar a base a coluna ap tal que p seja o índice que minimiza xiaiq p argmini m xiaiq aiq 0 Se todos os aiq forem negativos o programa linear é ilimitado Exemplo 411 Suponha que cT 1 1 2 e considere o seguinte tableau x₁1 x₂3 x₃0 x₄1 x₅0 b4 0 1 0 2 1 5 0 2 1 3 0 12 0 3 0 7 0 20 A coluna a₂ entrará na base verificaremos qual coluna deverá sair Dividimos cada xi pelos elementos de a₄ b₁a₁₂ 4 3 43 b₂a₂₂ 5 1 5 b₃a₃₂ 12 2 6 Descartamos os valores negativos e determinamos que a primeira variável básica x₁ deve sair da base 48 Método Simplex algoritmo O algoritmo Simplex é mostrado a seguir em pseudocódigo Nesta descrição o critério de seleção de variável a entrar na base não é explicitado Ao escolher a coluna a sair da base usamos bi já que por enquanto representamos a base como identidade e nesta situação xi bi construa o tableau de uma solução viável básica enquanto existe rj 0 selecione q tal que rq 0 xq entrará na base calcule biaiq ptodo aiq 0 e i m se todo biaiq é 0 PARE problema ilimitado p mini m biaiq aiq 0 faça xq entrar na base retirando xp apj apj apq aij aij apj aiq apq i p retorne xB solução ótima Exemplo 412 Considere o problema a seguir max 2x1 x2 sa x1 x2 2 3 2x1 3x2 20 x 0 Adicionamos variáveis de folga para transformar as desigualdades em igualdades obtendo max 2x1 x2 sa x1 x2 2 x3 3 2x1 3x2 x4 20 x 0 Montamos então o tableau Simplex x1 x2 x3 x4 1 12 1 0 3 2 3 0 1 20 2 1 0 0 0 48 MÉTODO SIMPLEX ALGORITMO 93 Todas as variáveis não básicas tem coeficientes reduzidos positivos por tanto podemos escolher qualquer uma delas Escolhemos x1 Para deter minar a coluna a sair dividimos cada xi básica pelos elementos corres pondentes da coluna que entrará a1 31 3 202 10 O menor deles é o primeiro portanto retiraremos então a coluna atual mente ocupada pela primeira variável básica x3 1 x2 12 1 x40 3 2 3 0 1 20 2 1 0 0 0 As setas indicam as colunas a entrar e sair da base Usamos operações elementares nas linhas do tableau para tornar a primeira coluna igual à coluna a3 como a11 que está marcado no tableau já é um só precisamos tornar a21 igual a zero Então subtraímos da segunda linha duas vezes a primeira O tableau resultante é x11 x2 12 x31 x40 3 0 4 2 1 14 0 2 2 0 6 Note que agora temos apenas uma variável com coeficiente reduzido po sitivo Ela entrará na base Para determinar a coluna a sair calculamos 312 6 0 144 72 A segunda variável básica x4 portanto sai da base x11 12 x31 0 3 0 4 2 1 14 0 2 2 0 6 O elemento marcado a22 4 será transformado em um usando ope rações elementares O tableau resultante é x11 x20 x3 34 x4 18 194 0 1 12 14 72 0 0 1 12 13 Como agora os coeficientes reduzidos de custo são todos negativos chegamos a uma solução ótima com x1 194 x2 72 e valor do objetivo igual a 13 Exemplo 413 Mostramos agora que quando não seguimos o método de escolha da variável a sair da base podemos chegar a uma solução inviável No exemplo 412 a primeira variável que escolhemos para entrar na base foi x1 O tableau era x2 x3 x4 1 12 1 0 3 2 3 0 1 20 2 1 0 0 0 Para escolher a variável a sair calculamos 31 1 e 202 10 devendo portanto escolher a primeira coluna da base Se fizermos o contrário e escolhermos a segunda coluna teremos que multiplicar a segunda linha por 12 e depois subtraíla da primeira O resultado será x1 x2 x3 x4 0 2 1 12 7 1 32 0 12 10 No entanto esta solução é inviável porque determina x3 7 A variável x3 é de folga e se atribuirmos a ela valor negativo estaríamos violando uma desigualdade Teorema 414 Se após a execução do método Simplex uma solução ótima tiver sido encontrada e houver coeficientes reduzidos de custo com valor zero então há múltiplas infinitas soluções ótimas para o problema Exemplo 415 O seguinte problema tem uma restrição ortogonal ao gradiente do objetivo max x1 2x2 sa x1 2x2 20 x1 10 x 0 O tableau final para este problema é x1 x2 x3 x4 0 1 12 12 5 1 0 0 1 10 0 0 1 0 20 49 OBTENDO UMA SOLUÇÃO VIÁVEL BÁSICA INICIAL 95 e a solução ótima é x1 10 x2 5 Temos zero no coeficiente reduzido de custo de x4 a folga da segunda restrição Se a incluírmos na base obtemos outro tableau x1 12 x21 x3 12 x40 10 1 0 0 1 10 0 0 1 0 20 com outra solução ótima x1 0 x2 10 Todas as combinações convexas das duas soluções ótimas são também ótimas A figura a seguir mostra a região viável as duas soluções e o gradiente do objetivo 10 10 20 10 5 Como o gradiente é ortogonal à restrição x1 2x2 20 todos os pontos viáveis da reta x1 2x2 20 são ótimos A partir da próxima seção deixaremos de incluir os nomes das variá veis no tableau 49 Obtendo uma solução viável básica inicial Para problemas do tipo max cTx sa Ax b as variáveis de folga nos permitiram formar facilmente uma solução básica inicial Nem todo pro blema terá uma variável de folga para cada restrição que nos permita obter de maneira simples uma solução inicial 491 O método das duas fases Considere agora o problema max cTx 43 sa Ax b x 0 Uma maneira de obter uma solução viável básica é criar variáveis artificiais não de folga variáveis sem qualquer significado cuja única razão de existir é permitirnos encontrar uma solução inicial para o tableau Simplex Veja por exemplo o problema a seguir min yi 44 sa Ax y b x y 0 Proposição 416 O problema 43 é viável se e somente se 44 tem ótimo com y 0 Demonstração Trivialmente se 43 é viável 44 também tem ótimo com y 0 Se y 0 claramente podemos desprezar y obtendo solução viável para 43 Se 44 tem ótimo com y 0 não há como diminuir y mantendo a solução viável note que as variáveis yi funcionam como variáveis de folga para o problema original 43 a11x1 a12x2 a1nxn a1n1y1 b1 e se houver algum yi 0 temos uma variável de folga sendo usada Isso significa que o lado esquerdo de uma das restrições deve ser estritamente menor que o direito a11x1 a12x2 a1nxn b1 mas o problema original 43 não tem estas variáveis de folga e portanto é inviável Resolver 44 é fácil com solução básica inicial x 0 e y b A solução final se houver não terá variáveis yi na base porque o mínimo do objetivo se dá com y 0 e portanto serve para 43 Exemplo 417 Temos agora o seguinte problema max x1 2x2 sa x1 x2 1 x1 12 x2 1 x 0 49 OBTENDO UMA SOLUÇÃO VIÁVEL BÁSICA INICIAL 97 2 1 1 x2 x1 Como a primeira restrição torna a origem inviável podemos adicionar um vetor artificial y que minimizaremos max y1 y2 sa x1 x2 y1 1 x1 1 2x2 y2 1 x y 0 Passamos o problema para a forma padrão max y1 y2 sa x1 x2 x3 y1 1 x1 1 2x2 x4 y2 1 x y 0 e construimos o tableau 1 1 1 0 1 0 1 1 12 0 1 0 1 1 No entanto percebemos que só precisávamos da variável y1 porque a co luna 0 1T incluída para a variável y2 não nos ajuda já havia a coluna 0 1T de x4 Eliminamos y2 e damos o nome y à única variável adicio 98 CAPÍTULO 4 O MÉTODO SIMPLEX nada max y sa x1 x2 x3 y 1 x1 1 2x2 x4 1 x y 0 Construimos novamente o tableau A base inicial é com y 1 x4 1 e as outras variáveis x1 x2 x3 com valor zero 1 1 1 0 1 1 1 12 0 1 0 1 Calculamos os coeficientes reduzidos de custo 1 1 1 0 1 1 1 12 0 1 0 1 1 1 1 0 0 1 Incluiremos x2 Como 1 1 1 1 12 2 removeremos y da base o que é bom porque estamos minimizando y e seu valor passará a ser zero 1 1 1 0 1 1 12 0 12 1 12 12 0 0 0 0 1 E o tableau agora é ótimo Temos a solução viável básica x1 0 x2 1 x3 0 x4 12 y 0 49 OBTENDO UMA SOLUÇÃO VIÁVEL BÁSICA INICIAL 99 Podemos aproveitar o tableau para resolver o problema original e usamos a base x2 x4 1 1 1 0 1 12 0 12 1 12 0 Agora temos que recalcular os coeficientes reduzidos de custo porque nosso vetor c mudou cT 1 2 O tableau com os novos coeficientes é 1 1 1 0 1 12 0 12 1 12 1 0 2 0 2 Neste momento estamos no ponto extremo x1 0 x2 1 Incluímos x3 na base removendo x4 2 1 0 2 2 1 0 1 2 1 3 0 0 4 4 Os coeficientes de custo são todos negativos portanto temos a solução ótima com valor 4 e x1 0 x2 2 x3 1 x4 0 A próxima figura mostra o caminho feito desde que começamos a fase II 1 1 2 O tableau anterior nos colocava no ponto 0 1 que foi o ponto encon trado na fase I Após um passo do Simplex mudamos para o ponto ótimo 0 2 100 CAPÍTULO 4 O MÉTODO SIMPLEX Exemplo 418 Temos agora o seguinte problema max x1 x2 sa x1 2x2 2 3x1 4x2 12 x 0 Ao montarmos o tableau percebemos que não há uma base óbvia que possamos usar 1 2 1 0 2 3 4 0 1 12 Adicionamos uma variável extra y1 porque não precisamos de duas po demos usar a folga da primeira linha e minimizamos y obtendo o tableau 1 2 1 0 0 2 3 4 0 1 1 12 Como estamos minimizando y podemos simplesmente maximizar y O vetor c será 0 0 0 0 1 1 2 1 0 0 2 3 4 0 1 1 12 3 4 0 1 0 incluiremos x1 na base Verificamos quem deveria sair 2 1 2 12 3 4 Retiramos a primeira básica s1 1 2 1 0 0 2 0 2 3 1 1 6 0 2 3 1 0 A solução para este problema é ótima mas com y1 6 Isto significa que não há solução para Ax b e o problema original não tem solução viável 49 OBTENDO UMA SOLUÇÃO VIÁVEL BÁSICA INICIAL 101 492 O método do M grande O método do grande M realiza a mesma coisa que o método das duas fases de uma única vez max cTx 45 sa Ax b x 0 No objetivo subtraímos do vetor x um outro vetor y com coeficientes muito grandes Multiplicaremos um valor grande M por um vetor de va riáveis artificiais y max cTx M1Ty 46 sa Ax y b x y 0 Exemplo 419 O problema a seguir tem uma restrição que nos impede de usar a origem como solução inicial básica max x1 2x2 sa x1 1 x1 x2 3 x 0 A representação gráfica deste problema é mostrada na próxima figura 1 3 3 2 Observe que a origem não é viável por isso não podemos usar 0 0 como solução viável básica 102 CAPÍTULO 4 O MÉTODO SIMPLEX Usando o método do M grande com M 10 obtemos um novo pro blema max x1 2x2 10y1 y2 sa x1 y1 1 x1 x2 y2 3 x y 0 Observe que as variáveis yi aparecem no objetivo com sinal negativo e multiplicadas pelo valor M muito grande assim quando M for sufici entemente grande teremos a solução ótima com y 0 e o problema tornase equivalente ao problema original de onde partimos O funcionamento do método do M grande é garantido pelas proposi ções a seguir Proposição 420 Se 46 é ilimitado e 45 é viável então 45 é ilimitado Proposição 421 Se 45 é viável e tem solução ótima finita então existe um M 0 tal que o tableau final do Simplex para 46 terá as variáveis artificiais fora da base Proposição 422 Se 45 é inviável então não existe M 0 para o qual o tableau final do Simplex para 46 terá as variáveis artificiais fora da base Exemplo 423 max 2x1 5x2 3x3 x4 sa 2x1 2x2 x3 2x4 2 x2 x3 x4 4 4x1 2x2 8x3 4x4 8 x 0 Usando o método do M grande com M 500 reescrevemos o problema da forma a seguir min 2x1 5x2 3x3 x4 500y1 500y2 500y3 sa 2x1 2x2 x3 2x4 y1 2 x2 x3 x4 y2 4 4x1 2x2 8x3 4x4 y3 8 x y 0 Obtemos a solução ótima x 0 569 103 509T e y 0 410 MINIMIZAÇÃO E DESIGUALDADES DO TIPO 103 410 Minimização e desigualdades do tipo Até agora mantivemos o foco em problemas de maximização com desi gualdades do tipo Era simples obter para esses problemas um tableau Simplex inicial porque as variáveis de folga das restrições formavam no tableau uma submatriz identidade Em problemas de minimização que usualmente tem restrições do tipo esta solução não seria possível por que as variáveis de folga tem coeficiente 1 e o que surge no tableau é a identidade multiplicada por 1 Na última seção mostramos como li darcom esta situação adicionando variáveis artificiais Agora ilustraremos aquelas técnicas em problemas de minimização O simplex funciona da mesma forma em problemas de maximização e minimização A única diferença na execução do algoritmo é que como queremos minimizar o objetivo escolheremos os coeficientes reduzidos de custo com valor negativo ao escolher a coluna a entrar na base e te remos uma solução ótima quando só houver coeficientes reduzidos de custo positivos Exemplo 424 Resolveremos o seguinte problema de minimização min 2x1 x2 x3 sa x1 x2 2 x2 x3 3 x 0 Com as variáveis de folga o problema é reescrito da seguinte maneira min 2x1 x2 x3 sa x1 x2 x4 2 x2 x3 x5 3 x 0 Se montarmos o tableau Simplex não teremos uma escolha simples de base inicial 1 1 0 1 0 2 1 0 1 0 1 3 Não podemos usar as variáveis de folga porque elas tem coeficientes ne gativos no tableau e portanto seus valores são negativos x4 2 x5 411 SOLUÇÕES DEGENERADAS 107 Montamos o tableau Simplex para o problema 1 1 1 0 0 0 3 1 1 0 1 0 0 3 1 0 0 0 1 0 6 3 1 0 0 0 1 15 1 1 0 0 0 0 0 Podemos escolher tanto x1 como x2 para entrar na base Escolhemos x1 Para determinar a variável a sair calculamos 3 1 3 3 1 3 6 1 6 15 3 5 e escolhemos a primeira variável não básica x3 O novo tableau é 1 1 1 0 0 0 3 0 0 1 1 0 0 6 0 1 1 0 1 0 3 0 2 3 0 0 1 6 0 2 1 0 0 0 3 Agora só podemos incluir x2 na base porque é a única não básica com coeficiente reduzido de custo acima de zero Para determinar a variável a sair da base novamente calculamos 3 1 3 6 0 A 3 1 3 6 2 3 Temos um empate entre x5 e x6 Estas são as variáveis de folga das duas restrições que tocam o ponto 3 6 uma delas redundante lembre que a última restrição de folga x6 é combinação linear da primeira com a ter ceira e a terceira tem folga x3 O fato de podermos retirar qualquer uma destas variáveis da base sig nifica que podemos retirar a folga de qualquer uma das duas restrições para incluir x2 108 CAPÍTULO 4 O MÉTODO SIMPLEX Escolhemos x6 para sair da base ou seja retiramos a folga da última restrição encostando na restrição e o novo tableau é 1 0 12 0 0 12 6 0 0 1 1 0 0 6 0 0 12 0 1 12 0 0 1 32 0 0 12 3 0 0 2 0 0 1 9 O valor de x5 é zero e a solução é degenerada A variável x5 é a folga da ter ceira restrição Ela é zero porque ao encostar na última restrição tam bém tocamos na terceira Agora incluiremos x3 folga da primeira restrição porque é nossa única opção 6 12 12 6 1 6 0 12 0 3 32 2 A variável a sair é x5 e o novo tableau é 1 0 0 0 1 0 6 0 0 0 1 2 1 6 0 0 1 0 2 1 0 0 1 0 0 3 1 3 0 0 0 0 4 1 9 O valor de x3 é zero e temos outra solução degenerada Observe que o valor do objetivo não mudou Incluiremos x6 A variável a sair será x4 e o tableau final é 1 0 0 0 1 0 6 0 0 0 1 2 1 6 0 0 1 1 0 0 6 0 1 0 1 1 0 9 0 0 0 1 2 0 15 Todos os coeficientes reduzidos de custo são negativos portanto temos uma solução ótima com x1 6 x2 9 e valor 15 Teorema 428 Um problema de programação linear com uma restrição redundante que toca o politopo é degenerado 412 MÉTODO SIMPLEX REVISADO 109 Teorema 429 O uso da regra de Bland para escolher a coluna a entrar na base elimina a possibilidade de ciclos Teorema 430 Se a coluna a entrar na base for escolhida aleatoriamente a probabilidade de ocorrência de ciclos tende a zero quando a quantidade de iterações tede a 412 Método Simplex Revisado O método Simplex mantém em memória e percorre a cada passo uma matriz com n colunas e m linhas buscando por uma base ideal Quando a quantidade n de variáveis é muito maior que a quantidade m de res trições muitas dessas colunas não são usadas durante a execução do al goritmo Geometricamente o caminho da solução inicial até a ótima não percorre todos os pontos extremos mas apenas um pequeno número de les e isto é particularmente relevante quando a dimensão do politopo é alta Cada vez que uma coluna entra na base todas as colunas de AN são atualizadas mesmo que nunca venham a ser usadas O método Simplex revisado foi desenvolvido como uma forma de evitar o armazenamento e processamento dessa informação desnecessária Antes de mais nada listamos a informação de que o Simplex precisa para cada operação Coeficientes reduzidos de custo para selecionar a coluna a entrar na base e para verificar otimalidade de soluções Acoluna que entra na base e os valores de xB para selecionara coluna a sair da base Os valores das variáveis básicas para que possamos reportar a solu ção ótima quando a encontrarmos Tudo mais é desnecessário Relembramos momentaneamente um fato que usaremos para desen volver o algoritmo simplex revisado um método bastante conhecido para o cálculo da inversa de uma matriz A é escrever A e a identidade I lado a lado por exemplo I à esquerda e A à direita e realizar as mesmas operações elementares em ambas até que a matriz da esquerda que era I tornese igual a A Quando isso acontece a matriz à direita será A1 110 CAPÍTULO 4 O MÉTODO SIMPLEX I A A1 I op elementares idênticas Mas isto é o que acontece no tableau simplex o algoritmo começa marcando uma base que é representada como a matriz identidade À medida que bases diferentes são visitadas a submatriz que original mente era a identidade vai sendo modificada também Em um dado mo mento encontramos a base que queremos Ab que é representada como a identidade depois de passar por operações elementares portanto a sub matriz que era a base no tableau original e qe era a identidade agora é a inversa de Ab Isso vale mesmo que as duas submatrizes tenham colunas em comum Exemplo 431 Resolveremos o seguinte problema mantendo marcada a submatriz que representava no tableau original a inversa da base max 2x1 x2 sa x1 3 x2 1 2x1 3x2 2 x 0 Marcamos a base no tableau inicial onde já incluímos as variáveis de folga x3 x4 x5 1 0 1 0 0 3 0 1 0 1 0 1 2 3 0 0 1 2 2 1 0 0 0 0 Neste momento temos ABx b mas como AB é a identidade x b Após a variável x1 entrar na base o tableau muda 1 0 1 0 0 3 0 1 0 1 0 1 0 3 2 0 1 8 0 1 2 0 0 0 412 MÉTODO SIMPLEX REVISADO 111 Como a solução é tal que ABx b sendo AB e b como no tableau inicial calculamos x A1 B b usando a matriz A1 B que acabamos de calcular e o vetor b que estava no tableau inicial a base é x1 x4 x5 portanto AB x11 x40 x50 0 1 0 2 0 1 A1 B x11 x40 x50 0 1 0 2 0 1 x A1 B b 1 0 0 0 1 0 2 0 1 3 1 2 3 1 8 A base é portanto x1 3 x4 1 e x5 8 como também podemos visua lizar diretamente no tableau As duas matrizes AB e A1 B compartilham uma coluna no tableau Após a entrada de x2 na base o tableau muda novamente 1 0 1 0 0 3 0 1 0 1 0 1 0 0 2 3 1 5 0 0 2 10 0 0 Agora a base é x1 x2 x5 Tomando AB do tableau inicial e A1 B do tableau final temos AB x11 x20 x50 0 1 0 2 3 1 A1 B x11 x20 x50 0 1 0 2 3 1 Novamente x A1 B b 1 0 0 0 1 0 2 3 1 3 1 2 3 1 5 412 MÉTODO SIMPLEX REVISADO 113 Temos no tableau original n 1 colunas e cada vez que trocarmos uma variável da base modificaremos todas elas O algoritmo para o método Simplex revisado guarda apenas A1 B sem ter que guardar AN que pode ser muito grande Podemos fazer isso por que A1 B nos permite gerar qualquer informação do tableau que precise mos inclusive os valores de cj e xj A1 B A1 B b cT BA1 B z0 Observe que ao descrevero algoritmo Simplex primal tínhamos uma base que consistia em diferentes colunas do tableau em posição não fixa Quando descrevemos o Simplex revisado A1 B é a inversa da base formada pelas colunas da base inicial apenas Temos agora um tableau com m 1 colunas Detalhamos a seguir as operações que o Simplex fará usando esta representação Denotamos por a iq o iésimo elemento do vetor coluna a q a q a1q a2q amq Coeficientes reduzidos de custo para a variável xj observamos que cj zj cj cT BA1 B aj e portanto rT N cN cT BA1 B AN A coluna da variável xq a entrar na base basta escrevêla usando a nova base A1 B a q A1 B aq Atualização do tableau para atualizar todos os valores efetuamos pivoteamento em a pq o elemento na pésima linha do vetor coluna aq Os valores das variáveis são x A1 B b 412 MÉTODO SIMPLEX REVISADO 117 Temos finalmente a solução ótima com x1 10 x2 20 É comum que implementações não armazenem A1 B explicitamente mas sim por sua fatoração LU A fatoração LU de A1 B é apenas atualizada sendo recalculada apenas de tempos em tempos Isso traz um equilíbrio entre eficiência e precisão numérica Exercícios Ex 29 Resolva os problemas a seguir usando o método Simplex Re solva cada um usando a regra de Bland e também alguma outra regra i max x1 x2 3x3 sa x1 x2 4 2x1 x3 6 3x2 1 2x3 5 x 0 ii max x1 2x2 sa x1 2x2 1 x1 1 x2 1 x 0 iii max x1 x2 2x3 sa x1 x2 5 x2 2x3 5 2x1 x2 x3 9 x 0 iv max 3x1 4x2 2x3 sa x1 x2 8 x1 x2 x3 112 x1 2x2 10 x 0 v max x1 x2 sa x1 x2 12 2 3x1 x2 23 x2 32 x 0 vi max x1 2x2 x3 3x4 x5 sa 2x1 x3 x4 x5 22 3x2 x3 10 x 0 118 CAPÍTULO 4 O MÉTODO SIMPLEX vii max x1 x2 sa x1 x2 4 x1 x2 1 2x1 3x2 2 x 0 viii max x1 2x2 x3 sa x1 x2 10 x1 x2 1 x1 2x2 6 x 0 Ex 30 Coloque os problemas na forma padrão para que possam ser re solvidos pelo método Simplex e depois use o Simplex para resolvêlos mostrando os tableaux intermediários i max 2x1 x2 3x3 sa x1 x2 5 2x1 x3 10 x2 2x3 9 x 0 ii max 3x1 2x2 sa x1 1 x1 2 x2 1 x2 2 x 0 iii max 2x1 x2 x3 sa x1 x2 3 2x2 x3 5 x1 3x3 4 x 0 iv max 2x1 x2 sa x1 x2 3 2x2 x3 5 x 0 v max x1 x2 x3 sa x1 x2 7 x1 x2 6 2x1 2x2 6 x1 x3 7 x 0 Ex 31 Coloque os problemas na forma padrão para que possam ser re 412 MÉTODO SIMPLEX REVISADO 119 solvidos pelo método Simplex e depois use o Simplex para resolvêlos mostrando os tableaux intermediários Use o método das duas fases em dois problemas e o do M grande em dois outros i min 2x1 4x2 8x3 sa x1 x2 5 x1 x3 4 3x2 x3 5 x 0 ii min 2x1 x2 sa x1 2 x1 4 x2 2 x2 4 x 0 iii min x1 x2 2x3 sa x1 x2 5 x2 3x3 8 x1 x3 4 x 0 iv min 8x1 3x2 sa 5x1 x2 3 x2 3x3 5 x 0 Ex 32 Implemente o método Simplex primeiro apenas para restrições na forma de desigualdade Ax b Depois permitindo igualdades usando a técnica descrita neste Capítulo para obter soluções viáveis básicas inici ais Posteriormente experimente com diferentes métodos para escolher a coluna a entrar na base Ex 33 Demonstre rigorosamente os Corolários 46 e 47 Ex 34 Demonstre a Proposição 48 É realmente necessário verificar to dos os aij em A Explique Ex 35 Seja x1 x2 xn uma solução viável básica Prove que xj mαm1β onde α max ij aij β max jm bj 120 CAPÍTULO 4 O MÉTODO SIMPLEX Ex 36 Considere o problema max cTx sujeito a Ax b com solução ótima de valor v Suponha que o problema min cTx sujeito a Ax b tenha ótimo com o mesmo valor v Podese concluir que existe um único ponto ótimo para os dois Como é geometricamente a região viável Ex 37 Prove que quando usamos o método Simplex em um problema não degenerado uma coluna que sai da base não pode voltar a ser básica na iteração seguinte Ex 38 Prove que se um problema tem região viável ilimitada existe para ele uma função objetivo que não permite resolver o problema e uma que permite obter uma solução ótima Ex 39 O que acontece quando a mesma solução viável básica pode ser descrita por mais de uma base Ex 40 O que acontece quando usamos o método do M grande em um problema inviável E em um problema ilimitado Ex 41 Suponha que tenhamos usado o método das duas fases para re solver um problema Se após a fase I uma variável artificial sai da base ela pode novamente entrar Ex 42 Resolva usando o método Simplex revisado max x1 x2 2x3 4x4 x5 2x6 x7 sa x1 x2 x3 x4 x5 x6 50 2x1 x2 3x3 2x4 x5 x6 2x7 40 x 0 Capítulo 5 Dualidade A todo problema de maximização podese associar um problema de mi nimização chamado de dual do problema Neste Capítulo estudamos a dualidade em programas lineares Definição 51 Primal e dual Considere o seguinte programa linear max cTx sa Ax b x 0 Damos o nome a este PL de primal e dizemos que o PL a seguir é seu dual min bTy sa ATy c y 0 Se um problema tem restrições em forma de igualdade podemos cons truir seu dual primeiro passando o problema para a forma de desigual dade observando que a restrição ai1x1 ainxn bi pode ser reescrita como ai1x1 ainxn bi ai1x1 ainxn bi 121 52 LEMA DE FARKAS 125 O Lema de Farkas Lema 57 representa a essência da dualidade em programação linear O Lema diz geometricamente que dados n vetores um vetor qualquer x pode estar dentro do cone e neste caso será com binação positiva dos outros ou fora do cone quando é combinação não positiva dos outros e nunca ambos ao mesmo tempo Em essencia o Lema de Farkas diz que o vetor b pode pertencer ao cone gerado por A ou não Seja S a revião viável definida por um programa linear Ax b Então exatamente uma das duas situações ocorre i b pertence ao cone gerado por A portanto temos Ax b com x 0 porque para pertencer ao cone deve ser combinação positiva das colunas de A a1 an b ii b não pertence ao cone gerado por A Neste caso deve haver algum z formando ângulo menor que 90o com b mas formando mais de 90o com o cone definido por A a1 an z b Mostramos na figura apenas a1 e an os outros vetores ai estão entre eles o semiespaço determinado pela linha leve consiste dos vetores com ângulo menor que 90o com b o cone à esquerda e abaixo é for mado pelos vetores com ângulo maior ou igual que 90o com o cone de A Assim existe z tal que 126 CAPÍTULO 5 DUALIDADE o ângulo entre colunas de A e z é maior que 90o logo ATz 0 o ângulo entre b e z é menor que 90o logo bTz 0 Se tomarmos y z teremos então ATy 0 para algum y tal que bTy 0 Embora a discussão geométrica até este ponto possa ser convincente para o caso em que tratamos de vetores em R2 enunciamos e demonstra mos algebricamente a seguir o Lema de Farkas Lema 57 de Farkas Sejam A uma matriz e b um vetor sendo que o nú mero de linhas de A é igual à quantidade de elementos de b Então exata mente um dos dois sistemas a seguir tem solução i Ax b para algum x 0 ii yTA 0 para algum y tal que bTy 0 Esta demonstração está incompleta Outra demonstração diferente será usada em uma futura versão do texto Demonstração i não ii Suponha que i valha e Ax b tenha solução positiva Se existe y tal que yTA 0 então yTA 0T yTAx 0Tx 0 porque x Ay 0 yTb 0 Ax b e o sistema ii não pode ter solução não i ii esta parte é omitida por ora Fica claro do enunciado do Lema de Farkas que ele tem forte rela ção com o conceito de dualidade o produto ATy com y não restrito a positivos é parte da descrição do dual de Ax b Exemplo 58 Sejam A 1 3 2 0 1 4 2 1 5 b 3 5 1 128 CAPÍTULO 5 DUALIDADE Corolário 511 Se x0 e y0 são soluções para o primal e o dual e cTx0 bTy0 então ambas são soluções ótimas Demonstração Seja x solução viável para o primal Então cTx bTy0 cTx0 As restrições de um programa linear max cTx sa Ax b são da forma aix bi onde ai é a iésima linha de A Estas restrições podem ser visua lizadas como hiperplanos cada um definindo um semiespaço A solução ótima está exatamente na interseção das restrições a3 a2 a1 Na figura anterior a solução ótima é a interseção das restrições a1x b1 e a2x b2 e a3 é redundante Lema 512 Se o ponto ótimo de um programa linear não pertence ao hi perplano definido por uma das restrições ela é redundante e pode ser removida sem que a solução ótima mude Teorema 513 dualidade forte Se o primal ou o dual de um programa linear tem solução ótima o outro também tem e os valores das soluções ótimas são iguais Demonstração Sejam max cTx sa Ax b o primal de um programa linear e min bTy sa ATy c seu dual Suponha que o primal tem solução ótima x com valor v cTx O hiperplano cTx v toca no poliedro apenas no ponto ótimo x ou nos pontos ótimos se houver mais de um a1x b1 a2x b2 c cTx v 54 ALGORITMO SIMPLEX DUAL 133 54 Algoritmo simplex dual Considere o primal e o dual de um programa linear como os que são da dos a seguir maximize cTx sa Ax b x 0 minimize bTy sa ATy c y 0 O método Simplex quando aplicado ao primal procura por várias solu ções viáveis sempre obedecendo as restrições e básicas cada uma com valor objetivo maior até encontrar a solução ótima Observando a for mulação do dual podemos imaginar que se executarmos nele o mesmo algoritmo o que sempre se mantém é a condição de otimalidade porque c agora está no lugar de b e que o que buscamos é uma solução cada vez mais próxima da viabilidade Isto é o que faz o algoritmo dualsimplex Suponha que tenhamos uma solução básica para o primal que tenha valor melhor que qualquer ponto do politopo mas que não seja viável Representamos esta solução pela base AB tal que xB A1 B b Manteremos o tempo todo a condição de viabilidade dual a solução sempre será ótima para o primal cN z 0 Começamos com uma solução que é inviável para o primal há algum bi 0 Se em alguma iteração tivermos conseguido viabilidade primal todos os bi 0 então teremos uma solução ótima e viável para o primal No método Simplex primal a cada passo escolhemos 1 a variável a entrar na base usando uma dentre várias regras porque queremos que a solução se aproxime do máximo ou seja primeiro decidimos como caminhar rumo à otimalidade 2 a variável a sair da base e neste caso só há uma possibilidade porque é necesrio escolher a variável que ao sair mantém a viabilidade ou seja em segundo lugar verificamos como manter a viabilidade 136 CAPÍTULO 5 DUALIDADE Exemplo 521 O Exemplo 520 funcionou perfeitamente Verificamos agora o que acontece quando não respeitamos a regra que determina a variável a entrar na base Novamente usamos o tableau do Exemplo 520 com função objetivo 2x1 x2 sendo minimizada 1 0 1 0 0 10 1 2 0 1 0 1 1 2 0 0 1 30 2 1 0 0 0 0 Novamente escolhemos a primeira linha para a variável a sair da base Ao contrário do que fizemos no Exemplo 520 escolhemos transformar 1 em novo pivô para que algum elemento a1q entre na base Mas desta vez o novo tableau será 0 2 1 0 1 20 0 4 0 1 1 31 1 2 0 0 1 30 0 2 0 0 3 30 Novamente o valor do lado direito 30 é positivo porque resulta da di visão de b1 que era negativo por a11 que também era No entanto o ta belau já não é ótimo para o primal porque um dos coeficientes reduzidos de custo é negativo e a solução que tem valor igual a 30 poderia ser me lhorada Como o tableau não é ótimo para o primal não podemos seguir usando o método dualsimplex Mas o tableau também não é viável para o primal portanto não podemos usar o método primalsimplex 10 0 30 15 138 CAPÍTULO 5 DUALIDADE Exemplo 523 Usaremos como exemplo o seguinte problema max 2x1 x2 sa x1 20x2 60 3x1 2x2 15 x1 10 x 0 O tableau inicial é 1 20 1 0 0 60 3 2 0 1 0 15 1 0 0 0 1 10 2 1 0 0 0 0 com base x3 x4 x5 Esta solução não é ótima e nem viável para o primal ela corresponde ao ponto 0 0 que não é viável porque uma das restri ções o elimina e não é ótimo já que estamos maximizando Adicionamos portanto a restrição x1 x2 M 10 5 0 M M 3 Esta restrição define um semiespaço contendo toda a região viável O novo tableau terá x6 também na base 1 1 0 0 0 1 M 1 20 1 0 0 0 60 3 2 0 1 0 0 15 1 0 0 0 1 0 10 2 1 0 0 0 0 0 54 ALGORITMO SIMPLEX DUAL 139 Agora removemos x6 da base incluindo x1 que tem o maior coefici ente reduzido de custo 1 1 0 0 0 1 M 0 21 1 0 0 1 60 M 0 5 0 1 0 3 15 3M 0 1 0 0 1 1 10 M 1 0 0 0 2 M O tableau resultante é ótimo para o primal os coeficientes reduzidos de custo são 1 e 2 Como ainda é inviável para o primal podemos usar o algoritmo Simplexdual a partir daqui O que fizemos foi usar a nova restrição para obter uma base que re presenta um ponto inviável no lado oposto da região viável 10 5 0 M M 3 Após resolver o problema usando o algoritmo Simplex dual o resul tado final poderá ser i xn1 na base a solução é ótima Essa é a situação ilustrada no Exem plo 523 a nova restrição deve ter uma folga porque está a uma dis tância da região viável ii xn1 fora da base com coeficiente reduzido de custo zero a solução é ótima e o M escolhido é justo 142 CAPÍTULO 5 DUALIDADE Exemplo 525 Resolveremos agora o problema a seguir usando o algo ritmo dualSimplex max x1 2x2 sa x1 2x2 6 x1 x2 2 x2 2 x1 3 x 0 Um tableau inicial para o primal é mostrado apenas para referência a seguir ele não será usado 1 2 1 0 0 0 6 1 1 0 1 0 0 2 0 1 0 0 1 0 2 1 0 0 0 0 1 3 Começamos com a base x1 x4 x5 x6 mostrada no tableau a seguir 1 2 1 0 0 0 6 0 3 1 1 0 0 4 0 1 0 0 1 0 2 0 2 1 0 0 1 3 0 0 1 0 0 0 Esta solução é evidentemente inviável x4 4 x6 3 mas ótima os coeficientes reduzidos de custo são negativos Escolhemos primeiro a coluna a sair o menor dos elementos negativos no lado direito é 4 na segunda linha portanto a segunda coluna da base x4 sairá 0 3 0 1 1 1 A coluna de x2 entrará na base 1 0 13 23 0 0 103 0 1 13 13 0 0 43 0 0 13 13 1 0 23 0 0 13 23 0 1 13 0 0 1 0 0 0 54 ALGORITMO SIMPLEX DUAL 143 Ainda precisamos remover a variável x6 da base porque ela tem valor 13 1 1 3 3 0 2 3 0 A coluna de x4 entra na base 1 0 0 0 0 1 3 0 1 12 0 0 12 32 0 0 12 0 1 12 12 0 0 12 1 0 32 12 0 0 1 0 0 0 A figura a seguir mostra o caminho feito pelo algoritmo dualSimplex Partimos de uma solução básica não viável interseção de restrições fora da região viável e mudamos a base sempre diminuindo a distância até a viabilidade 2 3 6 2 3 Exemplo 526 Este exemplo mostra a aplicação do algoritmo Simplex dual em um problema ilimitado max x1 x2 sa x1 1 x1 x2 0 x 0 144 CAPÍTULO 5 DUALIDADE 1 A região viável é ilimitada na direção de x2 Usaremos o método dual Simplex para verificar como o tableau termina Usaremos a restrição artificial x1 x2 M e nosso tableau inicial é mostrado a seguir 1 1 0 0 1 M 1 0 1 0 0 1 1 1 0 1 0 0 1 1 0 0 0 0 Retiramos xn1 da base incluíndo x1 1 1 0 0 1 M 0 1 1 0 1 1 M 0 2 0 1 1 M 0 0 0 0 1 M Note que agora a solução é inviável mas ótima para o primal 1 Retiramos a segunda variável da base Quem entra é x2 1 0 1 0 0 1 0 1 1 0 1 M 1 0 0 2 1 1 M 2 0 0 0 0 1 M 54 ALGORITMO SIMPLEX DUAL 145 Observamos que temos um tableau teoricamente ótimo porque todos os bi são positivos No entanto a variável artificial xn1 que foi incluída para obtermos uma solução primalinviável está fora da base Isto signi fica que a restrição x1 x2 M está sem folga temos x1x2 M para M tão grande quanto queiramos e a solução pode ter valor menorse incluírmos esta folga na base porque o coeficiente de custo de xn1 é 1 Concluimos que o problema é ilimitado A figura a seguir ilustra graficamente o problema a seta indica o gra diente da função objetivo 1 Notas A demonstração do teorema forte da dualidade Teorema 513 dada neste texto é semelhante àquela apresentada por Alexander Schrijver Sch98 Exercícios Ex 43 Mostre o dual dos problemas a seguir i max x1 x2 3x3 sa x1 2x2 5 x1 x3 10 3x2 4x3 9 ii min 3x1 2x2 sa x1 x2 1 x1 x2 2 146 CAPÍTULO 5 DUALIDADE iii max 2x1 2x2 3x3 sa 2x1 3x2 3 5x2 5x3 5 9x1 2x3 4 iv min 2x1 5x2 sa 2x1 7x2 5 2x2 x3 1 Ex 44 Resolva os problemas do exercício 43 usando o método Simplex dual Ex 45 Mostre que o problema max cTx sa Ax b x 0 tem solução se e somente se cT é combinação linear das linhas de A Ex 46 Implemente o algoritmo Simplex dual Inicialmente represente o tableau inteiro depois tente usar as idéias do Simplex revisado mas com o algoritmo dual Ex 47 Antes do Lema 512 mencionamos que uma condição necessá ria para que um programa linear tenha solução ótima é que o gradiente do objetivo possa ser expresso como combinação linear não negativa das restrições Demonstre rigorosamente isto Ex 48 Prove o Lema 512 Ex 49 Prove o Teorema 53 Ex 50 Se a solução ótima do dual é degenerada o que se pode dizer sobre a solução ótima do primal Ex 51 Suponha que eu tenha resolvido o dual de um problema e en contrei uma solução degenerada com k variáveis básicas assumindo valor zero O que posso dizer sobre o conjunto de soluções ótimas do primal Ex 52 Desenvolva os detalhes da seção 542 conforme mencionado ali tratase de raciocínio semelhante ao usado para escolha da coluna a sair no algoritmo Simplex primal Ex 53 Prove a Proposição 522 Capítulo 6 Análise de Sensibilidade Suponha que tenhamos encontrado a solução x ótima para o programa linear max cTx sa Ax b Verificaremos o quanto podemos mudar no problema sem mudar sua so lução ótima que já encontramos A isso damos o nome de análise de sen sibilidade 61 Mudanças no objetivo Mudar coeficientes no vetor que define a função objetivo terá um único efeito importante o gradiente mudará de direção Se o ângulo for su ficientemente grande a solução ótima pode mudar Na próxima figura as duas setas representam dois possíveis gradientes da função objetivo e duas soluções ótimas diferentes uma para cada um dos objetivos dife rentes 147 150 CAPÍTULO 6 ANÁLISE DE SENSIBILIDADE Exemplo 62 Considere o problema a seguir max 3x 4y sa 2x y 7 x 2y 8 x y 3 x y 0 O tableau final é 1 0 23 13 0 2 0 1 13 23 0 3 0 0 1 1 1 112 0 0 23 53 0 18 com x y e a variável s3 na base Suponha que queiramos mudar o coefici ente de x de modo que a função objetivo passe a ser z0 3 x 4y Aplicando o Teorema obtemos os seguintes limites para Para j 3 como a13 23 0 temos 23 23 1 Para j 4 como a14 13 0 temos 53 13 5 62 MUDANÇAS NO VETOR B DE TERMOS INDEPENDENTES 151 Assim com 1 5 garantimos a otimalidade da solução que já tí nhamos De fato para qualquer função objetivo entre 2x4y e 8x4y ou seja da forma 2 8x 4y a solução x 2 e y 3 continua ótima mas fora desse intervalo não Exemplo 63 Agora trabalharemos no problema a seguir max 2x 3y sa 2x y 4 x y 5 x y 1 x y 0 O tableau final é 3 0 1 0 1 3 3 0 1 1 0 9 2 1 1 0 0 4 8 0 3 0 0 12 representando a solução x 0 y 4 A base tem s3 s2 y Queremos mudar o coeficiente de x max2 x 3y Como x não está na base 8 8 Para este problema qualquer função objetivo da forma 6x 3y nos levará à mesma solução ótima x 0 y 4 Quando o coeficiente de x é maior que 6 a solução muda 62 Mudanças no vetor b de termos independentes Uma mudança no vetor b é um deslocamento paralelo de uma das restri ções como mostra a próxima figura 152 CAPÍTULO 6 ANÁLISE DE SENSIBILIDADE A figura mostra que nas duas soluções a base é a mesma tanto x como y estão presentes mas o valor de x e de y muda Se a distancia para a nova restrição for muito grande pode ser que a base mude como ilustra a figura a seguir A mudança em b não afeta o critério de otimalidade cj zj 0 para nossa base se ela continuar representando uma solução viável a base continuará sendo ótima mas os valores das variáveis podem mudar Teorema 64 Suponha que tenhamos resolvido um problema e obtido uma solução ótima x com base AB Se um valor é somado ao coefi ciente bk resultando em b A base AB continuará sendo ótima mas só 154 CAPÍTULO 6 ANÁLISE DE SENSIBILIDADE 1 1 2 2 O tableau final é 1 0 13 0 13 1 0 0 0 1 1 2 0 1 13 0 23 2 13 83 4 A solução é x1 1 x2 2 A submatriz do tableau com a inversa da base1 A1 B 13 0 13 0 1 1 13 0 23 Note que os valores de x1 e x2 estão nas posições 1 e 3 do vetor ao lado direito do tableau mas também podemos obter a solução calculando A1 B b 13 0 13 0 1 1 13 0 23 4 1 1 1 2 2 Consideramos mudar b3 para b3 Queremos que para todo i x i A1 B i3 0 ou seja x i A1 B i3 1A base tem x1 x4 x2 nesta ordem portanto a base usando os coeficientes do tableau inicial é AB 2 0 1 1 1 1 1 0 1 A submatriz que identificamos no tableau é inversa desta 156 CAPÍTULO 6 ANÁLISE DE SENSIBILIDADE 1 1 2 2 As linhas tracejadas representam a restrição que foi deslocada 63 Nova variável Se uma nova variável xn1 é adicionada ao problema sem mudanças nos coeficientes já existentes em A b e c teremos uma nova coluna an1 em A e um novo elemento cn1 em c Podemos tomar o tableau que usamos para obter x e adicionar a nova coluna com an1 e cn1 Teremos também que calcular cn1 zn1 Isso já nos dará a informação que queremos a solução x continuará sendo ótima somente se cn1zn1 0 Caso não seja podemos imediatamente incluir an1 na base e usar o algoritmo Simplex para obter uma nova solu ção ótima No entanto há um problema quando incluimos a nova variável te mos seus coeficientes na descrição inicial do problema e não no tableau final Temos que calcular a coluna an1 primeiro e só depois determinar o coeficiente reduzido de custo da nova variável Exemplo 66 Exemplificamos com o seguinte problema max x1 2x2 sa x1 x2 10 3x1 5x2 15 x2 5 x 0 63 NOVA VARIÁVEL 157 Os tableaux inicial e final para este problema são mostrados a seguir 1 1 1 0 0 10 3 5 0 1 0 15 0 1 0 0 1 5 1 2 0 0 0 0 1 0 1 0 1 5 0 0 3 1 8 5 0 1 0 0 1 5 0 0 1 0 1 15 61 A inversa da base está nas colunas 3 4 5 no tableau final temos portanto A1 B 1 0 1 3 1 8 0 0 1 Agora incluímos uma nova variável x3 no problema max x1 2x23x3 sa x1 x2 x3 10 3x1 5x2 2x3 15 x2 x3 5 x 0 A coluna de x3 no tableau inicial seria a3 1 2 1 Queremos incluir a coluna de x3 no tableau final o da direita em 61 com a solução ótima para o problema original que ainda não tinha x3 Calcu lamos a 3 A1 B a3 1 0 1 3 1 8 0 0 1 1 2 1 0 3 1 Incluímos a nova coluna no tableau 1 0 1 0 1 0 5 0 0 3 1 8 3 5 0 1 0 0 1 1 5 0 0 1 0 1 1 15 z cT BAN 1 0 2 1 1 0 3 8 3 0 1 1 1 1 2 cT N z 0 0 3 1 1 2 1 1 1 158 CAPÍTULO 6 ANÁLISE DE SENSIBILIDADE Como o coeficiente reduzido de custo de x3 é 1 devemos incluíla na base 1 0 1 0 1 0 5 0 3 3 1 5 0 20 0 1 0 0 1 1 5 0 1 1 0 2 0 20 z cT BAN 1 0 3 0 1 1 3 3 5 1 0 1 3 1 2 cT N z 2 0 0 3 1 2 1 1 2 Temos agora uma solução ótima x1 5 x2 0 x3 5 com valor x1 2x2 3x3 1 5 3 5 20 A inclusão de uma variável nova pode tornar o problema ilimitado ou inviável 64 Nova restrição Suponha agora que uma nova restrição tenha sido adicionada ao problema Se a solução ótima x satisfizer a restrição ela será ótima para o novo pro blema Trataremos então do que acontece quando nossa antiga solução não obedece a nova restrição não é mais viável no novo problema A solução ótima foi removida pela nova restrição mas ainda se encon tra na interseção de semiespaços definidos pelo problema É portanto básica além de ótima e inviável e devemos portnto poder usar o mé todo dualSimplex para obter uma nova solução ótima para o problema 160 CAPÍTULO 6 ANÁLISE DE SENSIBILIDADE Adicionamos mais uma restrição x1 2x2 6 A solução anterior já não é mais viável Adicionamos a restrição ao tableau que tem a antiga solução ótima 0 1 14 14 0 72 1 0 0 1 0 4 1 2 0 0 1 6 Temos agora uma nova base para a mesma solução a diferença é que a base inclui uma nova variável de folga para a nova restrição No entanto neste tableau a base não é mais representada pela matriz identidade ela é AB 0 1 0 1 0 0 1 2 1 É de fato uma base mas torna mais trabalhoso o cálculo dos coeficientes reduzidos de custo Podemos usar operações elementares para tornála igual à identidade 64 NOVA RESTRIÇÃO 161 0 1 14 14 0 72 1 0 0 1 0 4 0 0 12 32 1 5 0 0 34 54 0 312 z cT BAN 3 1 0 14 14 0 1 12 32 34 54 cT N z 0 0 34 54 34 54 Agora temos um tableau que para o primal é ótimo porque cj zj 0 para todo j e inviável porque x5 5 0 e podemos usar o método dualsimplex para obtera nova solução ótima De fato neste caso somente um passo é necessário retiramos x5 a folga da nova restrição da base incluindo x4 e o novo tableau é otimo e viável 0 1 16 0 16 83 1 0 13 0 23 23 0 0 13 1 23 103 16 76 263 z cT BAN 3 1 0 16 16 13 23 13 23 16 76 cT N z 0 0 16 76 16 76 A solução ótima é x1 23 x2 83 com valor 263 Notas Sinha Sin06 e Vanderbei Van07 discutem também Programação Para métrica que trata de problemas de programação linear onde as mudan ças não são discretas como as de que tratamos aqui mas contínuas por exemplo o vetor c pode variar continuamente com uma função c c0 τd onde c0 e d são vetores Exercícios Ex 54 Faça a análise de sensibilidade dos problemas apresentados no primeiro Capítulo escolha elementos de c b e modifique verificando para que intervalos as soluções continuam ótimas inclua novas variáveis nos problemas verificando se a solução ótima muda ou não 162 CAPÍTULO 6 ANÁLISE DE SENSIBILIDADE Ex 55 Suponha que tenhamos resolvido um problema de maximiza ção e encontrado a solução ótima x com valor v Em que situação é possível multiplicar uma linha i inteira da matriz A por 1 mantendo a otimalidade da solução Ex 56 Suponha que um programa lineartenha uma única solução ótima x Quanto podemos mudar um coeficiente da função objetivo de forma que x continue sendo a única solução ótima Ex 57 O que acontece com a solução ótima se removermos uma variá vel ou uma restrição de um problema de programação linear Quando ela continua viável E quando continua ótima Ex 58 Suponha que eu tenha resolvido um problema de programação linear e chegado a um tableau ótimo com uma solução em Rn Agora de cidi removeruma das variáveis simplesmente eliminandoa do problema mantendo o resto das restrições logo agora estarei procurando por uma solução em Rn1 Como posso levar a solução anterior em Rn1 garan tindo que será uma solução viável básica Há como garantir que a nova solução será ótima Explique geometricamente Ex 59 No Exemplo 67 apenas um passo do algoritmo dual simplex foi necessário para obtar uma nova solução ótima após uma nova restrição ser adicionada Também poderíamos ter resolvido o problema usando o simplex primal ignorando a solução antiga e fazendo novamente todo o trabalho mas sar o dual foi mais rápido Isso sempre acontecerá Expli que Ex 60 ASeção 64 abordou a situação em que uma nova restrição é adi cionada a um problema No entanto ali se presume que a restrição é uma desigualdade e a variável de folga dessa desigualdade completa a base agora que há uma nova linha a base precisa também de uma nova co luna Mostre como realizar um procedimento semelhante após adicionar uma igualdade 168 CAPÍTULO 7 OUTROS MÉTODOS Usamos o método do elipsoide para obter uma solução para este sistema e teremos assim uma solução x ótima para o problema de programação linear Exemplo 75 Considere o problema a seguir max 3x1 2x2 sa x1 3x2 4 4x1 x2 12 x 0 O dual deste problema é min 4y1 12y2 sa y1 4y2 3 3y1 y2 2 y 0 O problema para ser resolvido pelo método do elipsóide é posto na se guinte forma x1 3x2 4 4x1 x2 12 y1 4y2 3 3y1 y2 2 3x1 2x2 4y1 12y2 0 x 0 y 0 O algoritmo do elipsoide precisa de 6nn 1L iterações no pior caso Infelizmente o pior caso é o que quase sempre acontece na prática O mé todo Simplex cujo pior caso roda em tempo exponencial é quase sempre mais rápido que o elipsoide 72 PONTOS INTERIORES 169 72 Pontos interiores O método Simplex percorre diferentes pontos extremos do poliedro até encontrar a solução ótima para um programa linear Há métodos para resolução de problemas de programação linear que trabalham somente com pontos interiores do poliedro 721 Affine scaling Suponha que o problema esteja na forma max cTx sa Ax b O algoritmo começa com um ponto viável muda a escala de forma que o ponto passe a ser um vetor unitário e o move na direção do gradiente do objetivo garantindo que o valor da nova solução será melhor e que o novo ponto também será viável Em cada iteração temos um ponto viável x Mostraremos como obter o próximo ponto x Primeiro mudamos a escala do problema para que o ponto passe a ser o vetor unitário se x x1 x2 xn então definimos D x1 0 0 0 x2 0 0 0 xn O ponto modificado é y D1x de forma que y D1x 1 1 1 e Dizemos que o algoritmo trabalhará tanto no espaçox como no espaçoy Temos portanto o problema ADy b ou ADy b Fazemos S AD e o novo programa linear é max cTy sa Sy b y 0 72 PONTOS INTERIORES 175 gradiente do obejtivo Determine que funções nãolineares poderiam ser otimizadas por este algoritmo Ex 63 Implemente o algoritmo affine scaling Capítulo 8 Programação Inteira Como mencionamos na seção 23 é comum precisarmos resolverum pro blema de otimização linear onde só nos interessam as soluções inteiras Um problema de programação inteira é como um problema de pro gramação linear exceto que restringimos parte das variáveis a valores in teiros max cTx sa Ax b x 0 xj Z se j K onde o conjunto K contém os índices das variáveis inteiras Exemplo 81 Considere o problema a seguir max x1 x2 sa 3x1 2x2 8 x1 2x2 6 x1 x2 2 x 0 x Z2 Note que tanto x1 como x2 devem ser inteiros As restrições são mostradas na figura a seguir Os pontos viáveis no entanto são somente os pontos inteiros dentro da região 177 178 CAPÍTULO 8 PROGRAMAÇÃO INTEIRA 1 2 3 4 5 1 2 3 4 0 x1 x2 Os únicos pontos viáveis são 0 0 1 0 2 0 0 1 0 2 0 3 1 1 1 2 2 1 Veja que dentre os extremos do poliedro somente alguns são inteiros 0 0 2 0 0 3 1 25 24 04 Em particular se desconsiderarmos a exigencia de integralidade o ótimo seria 1 25 que não é inteiro O melhor ponto inteiro de acordo com a função objetivo dada é 1 2 Exemplo 82 Considere o problema a seguir max x1 x2 sa 3x1 2x2 24 x1 5 x1 x2 4 x 0 x1 Z x2 R Neste problema x1 assume valores inteirose x2 é real Isto significa que a região viável é a união das linhas verticais na figura a seguir 179 2 4 6 2 4 6 8 10 0 x1 x2 Os pontos viáveis são aqueles nos segmentos de reta 0 0 0 12 1 0 1 105 2 0 2 90 3 0 3 75 4 0 4 60 5 1 5 45 Neste texto trataremos de dois métodos para resolver programas in teiros O primeiro é o método dos planos de corte que consiste em de terminar novas desigualdades que reduzam o poliedro das soluções viá 180 CAPÍTULO 8 PROGRAMAÇÃO INTEIRA veis facilitando a obtenção de uma solução inteira O segundo é o método branchandbound que enumera de forma inteligente as soluções 81 Planos de corte Suponha que queiramos resolver um programa linear inteiro de minimi zação e que a região viável seja como a que é mostrada na próxima figura A seta mostra a direção para a qual o valor da função objetivo f decresce 1 2 3 4 5 6 1 2 3 4 5 6 0 x1 x2 f Suponha que queiramos tentar resolver o problema relaxando a restri ção de integralidade e usando por exemplo o método Simplex Obtemos uma solução não inteira A partir dela temos duas opções Se tentarmos usar a solução inteira mais próxima chegaremos ao ponto 5 1 fora do politopo e portanto inviável Se tentarmos percorrer o politopo procurando uma solução inteira viável teremos que andar uma grande distância já que a solução in teira viável ótima 2 5 está longe de 5 1 Podemos tentar adicionar restrições ao programa linear de forma que a região viável fique menor mas que nenhuma solução inteira seja remo vida Essas restrições são chamadas de planos de corte ou simplesmente cortes 182 CAPÍTULO 8 PROGRAMAÇÃO INTEIRA Demonstração Se bi não era inteiro então bi 0 e o tableau agora tem a linha s bi e portanto é inviável para o primal Aviabilidade para o dual segue trivialmente do fato de não termos mo dificado a última linha do tableau onde estão os coeficientes relativos de custo cj zj que são a solução para o dual Podemos então prosseguir com o método Simplex dual obtendo uma nova solução Se a nova solução for inteira encontramos o ótimo Se for fracionária recomeçamos e adicionamos um novo corte Se não houver solução viável é porque não há solução inteira para o problema original É possível garantir que o método dos planos de corte sempre termine em tempo finito usando determinada disciplina nas escolhas feitas du rante a execução do método Simplex Não faremos a demonstração neste texto Exemplo 85 Mostraremos neste exemplo a adição de um plano de corte ao programa linear a seguir que exige solução inteira min x1 5x2 sa x2 6 05x1 2x2 64 11x1 x2 67 x 0 x Z2 Quando resolvemos o problema sem as restrições de integralidade obte mos a solução 4117 2110 No entanto como podemos ver na figura a seguir esta solução está longe da única solução inteira para o problema 81 PLANOS DE CORTE 183 1 2 3 4 5 1 2 3 4 5 6 0 x1 x2 Escolhemos uma variável para adicionar o corte de Gomory O tableau Simplex é x1 x2 w1 w2 w3 bi 0 0 1 0323529 0294118 382941 0 1 0 0323529 0294118 217059 1 0 0 0294118 117647 411765 0 0 0 191176 264706 673529 A linha de x1 no tableau é x1 0294118w2 1176472w3 411765 Construimos o corte de Gomory 0294118 0294118w2 117647 117647w3 411765 411765 0294118w2 017647w3 011765 0294118w2 017647w3 s 011765 0294118w2 017647w3 s 011765 A nova variável de folga é s 011765 0294118w2 017647w3 184 CAPÍTULO 8 PROGRAMAÇÃO INTEIRA Podemos visualizara nova restrição marcada com se pudermos escrevê la usando apenas x1 e x2 Usando o problema original substituímos w2 64 05x1 2x2 w3 67 11x1 x2 Assim obtemos a restrição 0411766x2 0047058x1 07000062 011765 é mostrada no gráfico da região viável a seguir 1 2 3 4 5 1 2 3 4 5 6 0 x1 x2 Observe que como já demonstramos o corte de Gomory não exclui solu ção inteira da região viável Por outro lado ele exclui a solução ótima não inteira Agora adicionamos a restrição ao tableau Com isso adicionamos a variável s básica com valor 011765 tornando a solução inviável para o primal x1 x2 w1 w2 w3 s bi 0 0 1 0323529 0294118 0 382941 0 1 0 0323529 0294118 0 217059 1 0 0 0294118 117647 0 411765 0 0 0 0294118 017647 1 011765 0 0 0 191176 264706 0 673529 82 BRANCHANDBOUND 185 Para continuar observamos que o tableau ainda é viável para o dual mas que não é ótimo para ele porque se fosse seria ótimo para o primal e portanto viável aos dois Após obter nova solução usando o dual verificamos se é inteira Se não for obtemos um novo corte de Gomory e repetimos o processo 82 Branchandbound Suponha que tenhamos resolvido a versão relaxada de um programa in teiro e que a solução obtida x tem um elemento não inteiro xi Resol vemos então dois problemas um presumindo que xi xi 1 e outro presumindo que xi xi max cTx sa Ax b x 0 xj Z se j K xi xi max cTx sa Ax b x 0 xj Z se j K xi xi 1 Exemplo 86 As duas figuras a seguir ilustram como a região viável é divi dida em duas Na primeira figura a solução fracionária 43 24 é obtida A variável x2 é escolhida para criar uma ramificação e na segunda figura temos as regiões viáveis para os dois programas lineares um com x3 2 e outra com x2 3 186 CAPÍTULO 8 PROGRAMAÇÃO INTEIRA 1 2 3 4 5 1 2 3 4 5 0 x1 x2 1 2 3 4 5 1 2 3 4 5 0 x1 x2 x2 3 x2 2 Cada vez que dividimos o problema criamos dois outros derivados do primeiro Isto é naturalmente representado como uma árvore binária onde cada nó é um problema de programação linear A ramificação do exemplo que demos é representada como árvore a seguir x2 3 x2 2 Um limite superior para o valor do objetivo do problema original é ob tido facilmente da solução de qualquer um dos problemas relaxados Um limite inferior para o valor do objetivo do problema original é ob tido quando um dos problemas relaxados tem solução inteira podese ainda usar diversas técnicas para obter uma solução inteira viável a partir de uma solução fracionária Suponha que para um nó a da árvore tenhamos determinado que a melhor solução possível é α e que para outro nó b tenhamos verificado que a pior solução terá valor no mínimo β α Podemos evidentemente abandonar o nó α já que qualquer solução que pudesse ser obtida ali será pior ou no máximo tão boa quanto as soluções obtidas a partir de β Há escolhas que podem interferir na eficiência do algoritmo Tendo uma árvore com vários nós a partir de qual deles faremos a próxima ramificação 83 VARIANTES BRANCHANDCUT BRANCHANDPRICE 187 Uma vez que tenhamos escolhido um nó da árvore deveremos es colher uma das variáveis com valor não inteiro para criar a próxima ramificação 83 Variantes branchandcut branchandprice O nome branchandcut é dado à combinação das técnicas descritas ante riormente planos de corte e branchandbound Após resolver uma ver são relaxada do problema podese adicionar um corte ou uma ramifica ção Um corte gera uma nova linha no tableau Simplex Podese também gerar novas colunas este é o método chamado de pricing que quando combinado com branchandbound é chamado de branchandprice 84 Unimodularidade e poliedros integrais Há também uma classe de problemas para os quais a região viável sem pre é um poliedro cujos pontos extremos tem coordenadas inteiras Um exemplo são os problemas de transporte abordados no Capítulo 9 Nesta Seção tratamos brevemente desses problemas Definição 87 Um poliedro em Rn é integral se seus pontos extremos per tencem a Zn Definição 88 Uma matriz é totalmente unimodular se todos os seus sub determinantes são iguais a 1 1 ou 0 Claramente todos os elementos de uma matriz totalmente unimodu lar devem ser 1 1 ou 0 caso contrário a submatriz 1 1 com cada ele mento não seria unimodular No entanto nem toda matriz com elementos 1 1 e 0 é totalmente unimodular por exemplo a matriz a seguir tem determinante igual a 2 1 0 1 1 1 0 0 1 1 Teorema 89 Se A é totalmente unimodular então também o são A transposta de A As matrizes obtidas removendo linhas ou colunas inteiras de A 188 CAPÍTULO 8 PROGRAMAÇÃO INTEIRA As matrizes obtidas multiplicando linhas ou colunas inteiras por 1 As matrizes obtidas por reordenação de linhas ou colunas As matrizes obtidas por operação de pivoteamento passo do Sim plex A I Lema 810 Se A e b tem apenas valores inteiros então Ax b tem solução integral quando detA 1 Demonstração Usamos a regra de Cramer seja Aj a matriz A onde a j ésima coluna foi trocada pelo vetor b então xj detAj detA Quando detA é 1 xj tem o mesmo valorabsoluto que detAj Como os elementos de A e de b são inteiros detAj é inteiro e também o serão todos os xj Teorema 811 Se A é totalmente unimodular e b Zn então os pontos extremos do poliedro x Ax b são inteiros Demonstração Os vértices de Ax b são definidos por A uma sub matriz quadrada de A Como A é totalmente unimodular A também é Ax b tem solução inteira quando detA 1 e portanto x é inte gral Teorema 812 Uma matriz A é totalmente unimodular se i todos seus elementos são 0 1 ou 1 ii cada coluna tem no máximo dois elementos nãozero iii as linhas podem serparticionadas em dois conjuntos A e B de forma que para cada coluna com dois elementos nãozero a soma dos ele mentos em A é igual à soma dos elementos em B Exemplo 813 A matriz A 1 0 1 0 1 1 1 0 1 0 0 1 1 0 0 é totalmente unimodular porque satisfaz as condições do Teorema 811 particione as linhas em 1 2 3 Logo a solução ótima para max Ax b deve também ser inteira se b for inteiro 84 UNIMODULARIDADE E POLIEDROS INTEGRAIS 189 Exemplo 814 A matriz A 1 0 1 0 1 1 0 1 0 1 1 0 não é unimodular o determinante da submatriz quadrada 3 3 formada pelas tres primeiras colunas é det 1 0 1 1 1 0 0 1 1 2 Assim embora a matriz satisfaça os critérios i e ii do Teorema 812 não é unimodular e não satisfaz o critério iii não há como particionar as linhas da forma como determina o Teorema O Teorema 812 é condição suficiente mas não necessária para unimo dularidade Exemplo 815 A matriz 1 0 1 1 0 1 1 1 1 É unimodular e não satisfaz os critérios ii e iii do Teorema Notas O livro de Papadimitriou e Steiglitz PS98 dá uma boa introdução à Progra mação Linear Inteira incluindo os métodos de planos de corte e branch andbound Há também o livro de Laurence Wolsey Wol98 o de Wolsey e Nemhauser WN99 e o de Korte KV12 Para uma visão mais completa da área veja o livro de Schriver Sch03 O livro de Goldbarg e Luna GL00 cita numerosas técnicas usadas no desenvolvimento dos detalhes do al goritmo de branchandbound O método dos planos de corte foi desenvolvido porR GomoryGom58 O método de branchandbound no contexto de Otimização Combi natória foi proposto por Land e Doig LD60 é semelhante à técnica de busca usando cortes α β usada em Inteligência Artificial NR10 O método de branchandprice foi descrito porBarnhart Johnson Nemhau ser Savelsbergh e Vance Bar98 190 CAPÍTULO 8 PROGRAMAÇÃO INTEIRA O livro de Alexander Schriver Sch03 elabora o tópico da unimodula ridade de matrizes e sua conexão com programação inteira Politopos relacionados a diferentes classes de problemas são estuda dos no volume editado porDavid Avis David Bremnere Antoine Deza ABD09 Exercícios Ex 64 Calcule e plote os outros dois cortes de Gomory que não foram feitos no exemplo 85 Ex 65 Implemente o algoritmo dos planos de corte Ex 66 A recíproca do Teorema 811 vale Ex 67 Prove o Teorema 89 Ex 68 Suponha que um poliedro P definido por um programa linear seja integral ou seja b é inteiro e A é totalmente unimodular Prove que após a execução do método Simplex os coeficientes reduzidos de custo do programa linear são inteiros Ex 69 Prove o Teorema 812 Ex 70 Suponha que A não é totalmente unimodular mas tem coefi cientes inteiros e que b seja integral Quando a solução para Ax b é integral Responda para matrizes quadradas de ordem 2 e 3 Ex 71 Prove que a matriz de incidência de um grafo bipartido é total mente unimodular Ex 72 Unimodularidade total é fechada para multiplicação de matri zes Para potência de matriz Ex 73 Desenvolva um algoritmo para gerar matrizes aleatóreas total mente unimodulares respeitando o critério do teorema 812 Ex 74 Desenvolva um algoritmo para gerar matrizes aleatóreas total mente unimodulares não respeitando o critério do teorema 812 Não é necessário garantir que seu algoritmo gere as matrizes com distribuição uniforme 195 e A 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 0 1 0 1 b 4 10 6 12 8 Ao escrevermos o problema na forma matricial observamos que a ma triz das restrições tem a seguinte estrutura x11 x12 x1n f1 x21 x22 x2n f2 fm x11 x21 d1 x12 x22 dn x1n x2n dn 92 Ou seja A 1T 1T 1T I I I I A matriz do exemplo 91 por exemplo é A 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 0 1 0 1 Qualquerproblema que possa serdescrito dessa forma é chamado de pro blema de transporte Mostramos agora que todo problema de transporte tem solução ótima porque todos tem solução viável e todos são limitados Teorema 92 Todo problema de transporte tem uma solução viável 198 CAPÍTULO 9 PROBLEMAS DE TRANSPORTE 92 Solução inteira O último Teorema desta seção é importante porque identifica os proble mas de transporte como uma classe de problemas para as quais podemos obter soluções inteiras de forma eficiente isto é relevante porque de ma neira geral obter soluções inteiras para problemas de otimização linear é difícil veja o Capítulo 8 Teorema 96 Todo problema de transporte com ofertas e demandas in teiras tem solução inteira Demonstração A matriz de coeficientes do programa linear é totalmente unimodular aplicase o teorema 812 particione a matriz em linhas de restrição de demanda e linhas de restrição de oferta Podese também demonstrar este Teorema sem usar a unimodulari dade da matriz veja o Apêndice A 93 Algoritmo para solução do problema de transporte O método Simplex pode ser adaptado para explorar a estrutura dos pro blemas de transporte O diagrama a seguir representa de forma geral a matriz de coeficientes das restrições do primal de um problema de transporte e a de seu dual Os retângulos em cinza vetores com uns estão alinhados com as submatrizes identidade 1T 1T 1T I I I 1 I 1 I 1 I 200 CAPÍTULO 9 PROBLEMAS DE TRANSPORTE Seu dual é max bTw ATw c Note que AT 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 0 0 1 0 1 Ou seja o dual é max 4u1 10u2 6u3 12v1 8v2 sa u1 v1 4 u1 v2 7 u2 v1 9 u2 v2 5 u3 v1 5 u3 v2 4 ui vi R O Teorema das folgas complementares nos garante que uma solução x para o primal e a solução u v correspondente para o dual são ótimas se e somente se yTAx b 0 tij ui vj 0 xTATy c 0 xijtij ui vj 0 O coeficiente reduzido de custo da variável primal xij é rij tij ui vj As restrições do dual são as condições de otimalidade e elas nos dizem exatamente que os coeficientes reduzidos de custo do primal devem ser positivos o primal é um problema de minimização Assim para que a solução seja ótima se xij está na base com xij 0 então seu coeficiente reduzido de custo é necessariamente zero tij ui vj 0 Se tivermos uma solução viável básica com xij 0 ela será ótima se tij ui vj 0 i j na base Como temos m n variáveis xij esta última expressão representa um sis tema com m n 1 equações e m n variáveis Será útil representar em um tableau tanto o problema primal como o dual O diagrama abaixo mostra o tableau que usaremos acima e à es querda manteremos os valores dos ui e vj que modificaremos em cada 202 CAPÍTULO 9 PROBLEMAS DE TRANSPORTE maticame à direita temos já os tij xij fi dj preenchidos v1 v2 u1 x11 t11 x12 t12 f1 u2 t21 r21 x22 t22 f2 u3 t31 r31 x32 t32 f3 d1 d2 v1 v2 u1 4 5 2 4 6 u2 3 r21 8 5 8 u3 4 r31 5 3 5 4 15 Temos quatro variáveis básicas e cinco nãobásicas t11 u1 v1 0 t12 u1 v2 0 t22 u2 v2 0 t32 u3 v2 0 Se determinarmos u1 0 teremos uma solução para o sistema u1 0 u2 9 u3 1 v1 5 v2 4 Chegamos ao tableau parcial a seguir Temos agora os valores de ui e vj 5 4 0 5 4 2 4 6 9 3 r21 8 5 8 1 4 r31 5 3 5 4 15 Agora calculamos os coeficientes reduzidos de custo r21 t21 u2 v1 r31 t31 u3 v1 93 ALGORITMO PARA SOLUÇÃO DO PROBLEMA DE TRANSPORTE 203 Com isto temos o tableau completo 5 4 0 5 4 2 4 6 9 3 7 8 5 8 1 4 0 5 3 5 4 15 Por acaso observamos que como todos os coeficientes reduzidos de custo são nãonegativos r21 7 r31 0 o tableau é ótimo Depois de obter uma solução viável básica para um problema de trans porte executamos o seguinte método 1 Calculamos ui vj para cada variável xij básica 2 Calculamos os coeficientes reduzidos de custo para as variáveis não básicas Sabemos que rij tij uu vj e já calculamos ui vj para todos i j no passo anterior 3 Se houver algum rij 0 a solução pode ser melhorada lembramos que o problema é de minimização Senão a solução é ótima 4 Após melhorar a solução recomeçamos Suponha que o coeficiente reduzido de custo negativo seja o da variável xpq Aumentamos xpq em uma quantidade Θ Com isso a solução torna se inviável já que as somas de linhas e colunas devem ser iguais aos fi e dj Alguma variável na mesma linha ou na mesma coluna que xpq deve ser reduzida em Θ Retiramos portanto Θ de uma variável na mesma linha que xpq Agora haverá uma outra coluna onde falta Θ Modificamos esta coluna e assim sucessivamente até que tenhamos chegado novamente à linha p formando um ciclo 204 CAPÍTULO 9 PROBLEMAS DE TRANSPORTE encontre uma solução viável básica x repita determine ui vj ptodos i j na base fixe ui 0 resolva tij ui vj 0 calcule rij tij ui vj para i j fora da base se há i j tais que rij 0 seja p q a posição com menor rij aumente xpq em Θ enquanto solução não é viável corrija removendo ou adicionando Θ a outra variável básica senao PARE solução ótima Exemplo 99 T 15 18 10 10 12 16 13 15 17 f 5 15 20 d 10 12 18 Começamos montando o tableau e aplicando a regra do canto noroeste depois calculando ui uj e rij 15 17 19 0 5 15 18 1 10 9 5 5 5 10 10 12 16 0 15 2 13 0 2 15 18 17 20 10 12 18 O coeficiente 9 é o único rij negativo portanto é o que escolhemos So maremos Θ a x13 com isso teremos que remover Θ de x11 consequen temente somaremos Θ a x21 removemos de x22 somamos a x32 e final 94 BASES DEGENERADAS 205 mente removemos de x33 15 17 19 0 5 Θ 15 18 1 Θ 10 9 5 5 5 Θ 10 10 Θ 12 16 0 15 2 13 0 2 Θ 15 18 Θ 17 20 10 12 18 O maior valor que mantém a viabilidade é claramente Θ 5 10 12 14 0 15 5 18 6 5 10 5 0 10 10 5 12 16 2 15 3 13 0 7 15 13 17 20 10 12 18 Como todos os coeficientes reduzidos de custo agora são positivos o ta bleau é ótimo e a solução é x13 5 x32 7 x21 10 x33 13 x22 5 94 Bases degeneradas É possível durante a execução do algoritmo para problemas de transporte encontrar bases degeneradas Se isto acontecer podemos usar o método da perturbação quando uma variável com valor zero entra na base mo dificamos seu valor para algum ε 0 suficientemente pequeno Quando a variável sair da base mudamos novamente seu valor para zero Exemplo 910 208 CAPÍTULO 9 PROBLEMAS DE TRANSPORTE adicionar Q às linhas cobertas adicionar Q às colunas cobertas é equivalente a esta outra subtrair Q das linhas não cobertas somar Q às interseções de traços Esta operação será usada nesta segunda forma pelo algoritmo O método Húngaro é listado a seguir em pseudocódigo para toda linha i λi mínimo da linha i tij tij λi para toda coluna j κj mínimo da coluna j tij tij κj repita cubra os zeros com o menor número R de traços se R n PARE seja Q a menor quantidade não coberta pelos traços subtraia Q das linhas não cobertas some Q ás interseções de traços Exemplo 914 Suponha que queiramos resolver o problema de atribuição com a seguinte matriz de custos 21 26 22 28 14 18 20 17 18 17 21 25 21 20 23 24 95 O PROBLEMA DE ATRIBUIÇÃO 209 Seguimos os passos do algoritmo Húngaro 21 26 22 28 14 18 20 17 18 17 21 25 21 20 23 24 21 14 17 20 0 5 1 7 0 4 6 3 1 0 4 8 1 0 3 4 0 0 1 3 0 5 0 4 0 4 5 0 1 0 3 5 1 0 2 1 0 5 0 4 0 4 5 0 1 0 3 5 1 0 2 1 Conseguimos cobrir os zeros com menos de quatro traços O menor ele mento não coberto é um subtraímos este valor dos elementos não coo bertos e o adicionamos aos elementos de interseção traços 0 6 0 4 0 5 5 0 0 0 2 4 0 0 1 0 Tentamos novamente cobrir a matriz com traços 0 6 0 4 0 5 5 0 0 0 2 4 0 0 1 0 Agora o número mínimo de traços para cobrir a matriz é n 4 e che gamos à solução ótima Só precisamos determinar quatro zeros sem que dois estejam em mesma linha ou mesma coluna 0 6 0 4 0 5 5 0 0 0 2 4 0 0 1 0 Os valores da atribuição ótima são um onde temos quatro tij independen 212 CAPÍTULO 9 PROBLEMAS DE TRANSPORTE Ex 85 Explique brevemente o significado do dual de um problema de transporte o que são as variáveis e que significam as restrições E os co eficientes de cada variável no objetivo Ex 86 Resolva os problemas de atribuição com as matrizes de custos 10 20 30 40 25 15 25 20 30 20 15 30 20 25 30 10 40 75 55 85 15 85 65 60 105 95 30 100 45 100 90 90 35 39 33 40 26 16 16 30 20 10 5 20 5 15 20 5 Ex 87 Demonstre a Proposição 913 Capítulo 10 Teoria dos Jogos O objeto de estudo da Teoria dos Jogos são situações envolvendo conflito de interesse entre diversas partes Modelamos estas situações como jo gos onde cada parte é um jogador que tem algumas estratégias a escolher Usamos a suposição de que podemos quantificar o que uma estratégia traz de desejável ou indesejável a cada jogador 101 Jogos de soma zero Uma categoria importante de jogo é a dos jogos de soma zero Um jogo é dito de soma zero se o pagamento de um jogador sempre implica em perda da mesma quantidade pelos outros jogadores de tal ma neira que ao somarmos o saldo de todos os jogadores ao final do jogo ob teremos zero presumindo claro que o saldo inicial de cada um também era zero Como exemplos de jogos de soma zero temos diversos jogos re creativos entre duas pessoas como xadrez damas pôquer e outros jogos semelhantes Os jogos de soma zero não tem no entanto sua relevância limitada a jogos recreativos diversas situações diferentes podem ser modeladas como jogos de soma zero Descrevemos um jogo de soma zero com dois participantes por uma matriz de pagamentos as linhas representam as possíveis estratégias do jogador A e as colunas representam as possíveis estratégias do jogador B A posição i j da matriz descreve o quanto o jogador A recebe e conse quentemente quanto B paga quando A escolhe a estratégia i e B escolhe a estratégia j Em uma versão simples de jogo com soma zero os dois jogadores não 213 214 CAPÍTULO 10 TEORIA DOS JOGOS se comunicam conhecem a matriz de pagamentos e cada um escolhe sua estratégia sem conhecimento da estratégia do oponente Após a escolha das estratégias os jogadores recebem ou pagam de acordo com o resul tado Exemplo 101 O jogo a seguir nos dá um primeiro exemplo O jogador A e o jogador B devem escolher entre duas cores preto e branco em cada rodada Quando as cores coincidem o jogador A ganha Quando não coincidem o jogador B ganha A matriz de pagamentos é mostrada a seguir Chamamos o jogador A de jogador linha porque suas opções estão à esquerda uma por linha O jogador B é o jogador coluna porque suas escolhas estão acima uma por coluna preto branco preto 1 1 branco 1 1 Exemplo 102 Damos agora um exemplo mais elaborado O jogador A tem quatro opções de estratégia e o jogador b tem três b1 b2 b3 min a1 2 4 8 2 a2 1 3 4 1 a3 3 6 5 6 a4 1 3 2 1 O menor valor em cada linha é o menor valor que resulta daquela estraté gia e portanto fi minj cij representa o valor mínimo assegurado pela estratégia i A estratégia a1 garante retorno de no mínimo 2 a2 garante retorno mínimo de 1 e assim por diante Jogando de forma pessimista o jogador A claramente quer o maior dos retornos mínimos ou seja arg max i min j aij A estratégia a2 é a que garante o maior retorno mínimo para A O me nor valor que o jogadorlinha pode garantir para si então é maxi minj aij chamado de valor maxinmin Presumindo que A sempre usará a mesma estratégia sua melhor opção é escolher sempre a estratégia a2 O jogadorB realiza a mesma análise e escolhe sua estratégia mini maxj aij 218 CAPÍTULO 10 TEORIA DOS JOGOS podese ter um só jogador em um jogo contra a natureza ou diver sos jogadores há jogos com informação imperfeita onde a informação a respeito dos movimentos anteriores não é completo quanto aos pagamentos além de soma zero há jogos com soma cons tante e jogos com soma variável Uma exposição mais ampla da Teoria dos Jogos pode ser encontrada no livro de Martin Osborne e Ariel Rubinstein OR94 ou em uma segunda leitura no livro de Drew Fudenberg e Jean Tirole FT91 Exercícios Ex 88 seria possível caracterizar o jogo de parouímpar como jogo de soma zero Se não for possível o que deveria ser modificado Ex 89 Sabemos que no jogodavelha após os dois jogadores escolhe rem suas primeiras jogadas o primeiro X e o primeiro O o resultado do jogo já estará determinado se nenhum deles cometer nenhum erro dali para a frente Mostre a matriz de pagamentos para este jogo levando em consideração apenas a primeira escolha de cada um dos jogadores e pre sumindo que esta jogada inicial é feita simultaneamente pelos dois joga dores sem que um saiba a jogada do outro Ex 90 No jogo de palitinho ou porrinha1 dois jogadores tem à sua disposição três palitos para cada um Cada jogador põe as mãos atrás do corpo e esconde zero um dois ou três palitos em uma das mãos e de pois que cada jogador escondeu seus palitos ambos dão seus palpites a respeito da quantidade total de palitos que existe em suas mãos que será um número entre zero e seis Ambos abrem as mãos e o jogador que tiver acertado o palpite ganha Normalmente um jogador dá o primeiro palpite e o outro dá seu palpite em seguida Supondo que ambos dessem seus palpites sem conhecer o palpite do outro como seria a matriz de paga mentos do jogo Ex 91 Verifique que o dual do programa linear que define a estratégia de um jogador em um jogo de soma zero é o programa linear que define 1Muito provavelmente derivado do jogo romano morra onde os jogadores usam os dedos das mãos ao invés de palitos 102 ESTRATÉGIA MISTA 219 a estratégia de seu oponente Capítulo 11 Controle Discreto Este Capítulo trata de problemas de controle em tempo discreto um pro blema que pode ser naturalmente modelado como programa linear Uma vez que o problema também pode ser resolvido usando a técnica de pro gramação dinâmica esta também é explorada Em algumas áreas da Ma temática Aplicada controle discreto e programação dinâmica são tratados como um só tópico 111 Programação Dinâmica Programação Dinâmica é o nome de uma técnica geral de resolução de problemas Iniciamos com um subproblema pequeno achamos a solução ótima para esta subproblema e depois a usamos para construir soluções para subproblemas maiores Considere a seguinte situação temos diversos itens x1 x2 xn cada um com um peso w1 wn e um valor v1 vn Temos uma mochila com capacidade C e queremos incluir na mochila itens que maximizem o valor sem exceder a capacidade da mochila O problema da mochila pode serformulado como um programa linear max vTx sa wTx C x 0 Esta formulação só faz sentido no entanto se os diversos itens puderem ser fracionados Se exigirmos que as quantidades sejam inteiras teremos um problema de programação inteira 221 112 PROCESSO MARKOVIANO DE DECISÃO 223 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 4 4 4 4 4 4 2 0 3 3 4 7 7 7 7 7 3 0 3 3 4 8 11 11 12 15 4 0 3 3 4 8 11 11 12 15 1111 Aplicabilidade do Algoritmo A técnica de programação dinâmica é interessante quando o problema a ser resolvido apresenta as duas características a seguir Subestrutura ótima uma solução ótima para o problema pode ser construída a partirde soluções ótimas para subproblemas No exem plo do problema da mochila os subproblemas consistiam em ma ximizar o valor dos itens que poderíamos acomodar em mochilas menores Subproblemas não completamente isolados uma solução para um subproblema pode ser usada mais de uma vez porque há diferentes subproblemas maiores que a usam No exemplo da mochila após calcularmos o valor máximo para uma mochila de tamanho 3 usa mos este dado na construção das soluções para mochilas de tama nho 4 5 etc 112 Processo Markoviano de Decisão Há problemas de otimização que podem ser formulados como programas lineares mas que também podem ser resolvidos por programação dinâ mica No restante deste Capítulo analisamos os processos Markovianos de decisão O seguinte problema é frequentemente usado para ilustrar o conceito de processo Markoviano de decisão um empresário produz um único tipo de produto O empresário deve todo mês verificar seu estoque e decidir quantas unidades adicionais deve encomendar para a fábrica sabendo além da quantidade que tem em estoque a probabilidade de que cada unidade seja vendida e o custo de armazenamento por unidade O em presário quer maximizar o lucro nos próximos meses 115 VARIANTES DE MDPS 231 percebe além de sua recompensa uma observação vinda do ambiente o conjunto de observações é finito Após obter a recompensa e verificar a observação o tomador de decisões atualiza internamente uma estatística suficiente a respeito do sistema Esta estatística representa de certa forma sua crença e é chamada de estado de informação porque não representa o estado do sistema e sim o estado da informação que se tem a respeito do sistema ambiente política estimador de estados o observação a ação executada nova estatística Um POMDP pode ser descrito da mesma forma que um MDP pelos conjuntos S A e funções T R além de Ω o conjunto de possíveis observações O S A Ω 0 1 dá a probabilidade da observação o ser recebida após a ação a ser executada em um estado s Há dois exemplos relevantes de estatística suficiente Histórico completo a sequência completa de ações observações e recompensas desde o primeiro momento é uma estatística sufici ente Distribuição de probabilidades sobre estados o tomador de deci sões pode também manter uma distribuição de probabilidade so bre os estados e atualizála após cada estágio A representação de políticas para POMDPs não pode ser feita direta mente porque seria necessário mapear uma quantidade infinita e não enumerável de distribuições em valores Podese definir no entanto um MDP sobre um conjunto infinito de estados de crença e a função valor tornase convexa e linear por partes O número de hiperplanos usado em cada época de decisão é exponencial em Ω e portanto a quantidade de 232 CAPÍTULO 11 CONTROLE DISCRETO vetores para z épocas de decisão é duplamente exponencial em z O algo ritmo de programação dinâmica quando aplicado diretamente a POMDPs tem complexidade de tempo OSAΩz O problema é PESPAÇO com pleto Há outras formas de representarpolíticas para POMDPs como porexem plo controladores autômatos de Buchi estocásticos Notas O problema de Programação Dinâmica foi popularizado por Richard Bell man Bel03 e Ronald Howard How60 O livro de Martin Puterman trata detalhadamente do problema de de cisões em sequência Put05 inclusive a formulação como programa li near A abordagem moderna para programação dinâmica envolve méto dos diferentes da programação linear Bertsekas aborda o mesmo tema de forma diferente Ber07 BT96 o livro de Sutton e Barto apresenta mé todos biologicamente inspirados SB98 o livro de Warren Powell trata de métodos para a resolução de grandes problemas de programação dinâ mica Pow11 O livro de Robert Stengel é uma boa introdução à Teoria do Controle Ótimo Ste94 também indicado ao leitorinteressado no assunto O algoritmo de programação dinâmica elaborado para resolver um problemas de Controle Ótimo mostrouse útil também em outros con textos tornandose tópico obrigatório de estudo em Ciência da Compu tação Cor09 DPV06 Os SMDPs foram estudados inicialmente porW S Jewell Jew63 Howard How71 e deCani Can64 e são discutidos nos livros de Martin Puterman Put05 e de Dimitri Bertsekas Ber07 A demonstração de que o problema de resolver POMDPs é PESPAÇO difícil foi dada por Christos Papadimitriou e John Tsitsiklis PT87 MDPIPs são discutidos em diversos artigos SL70 IE94 Fil07 e há também POMDPs com parâmetros imprecisos chamados de POMDPIPs IN07 Exercícios Ex 92 Implemente o algoritmo de programação dinâmica para o pro blema da mochila Ex 93 Implemente o algoritmo de programação dinâmica para MDPs 115 VARIANTES DE MDPS 233 Ex 94 Se os pesos wi e a capacidade C em uma instância do problema da mochila são todos muito grandes é possível reescrever o problema de forma que exija tempo de execução menor do algoritmo de programação dinâmica Ex 95 Mostre como resolveras seguintes do problema da mochila usando programação dinâmica k N é parâmetro de entrada i que funcione permitindo repetição de itens ii que permita até k itens do mesmo tipo iii que permita que até 1k do peso total seja de itens do mesmo tipo iv que permita que até 1k do valor total seja de itens do mesmo tipo v que maximize a quantidade de itens e não seus valores Diga como fica a complexidade de cada um dos seus algoritmos Ex 96 Tente formular os algoritmos do Exercício 95 como programas lineares Ex 97 O algoritmo dado neste Capítulo usando programação dinâmica para o problema de mochila apenas determina o valor máximo que pode ser acomodado na mochila e não os itens Mostre como modificálo para que inclua também os itens Mostre como fica a complexidade do seu algoritmo modificado Ex 98 Uma fábrica usa uma máquina que se comporta da seguinte ma neira quando a máquina está em perfeito estado ela produz 200 por se mana A máquina pode apresentar um problema típico que a fará produ zir apenas 100 por semana A manutenção preventiva da máquina custa 10 por semana A cada semana sem manutenção preventiva a probabili dade da máquina apresentar esse defeito é 02 Acada semana com manu tenção preventiva a probabilidade da máquina apresentar o defeito é 01 Se a máquina estiver com esse defeito podese pagar 300 a um técnico para consertála Se a máquina estiver com defeito ela também pode que brar completamente na semana seguinte com probabilidade 008 Nesse caso uma nova máquina precisa ser comprada por 10000 Um gerente da fábrica precisa decidir quando realizar manutenção preventiva e quando consertar máquinas defeituosas Ex 99 Usando a formalização de SMDPs dada neste Capítulo descreva MDPs possivelmente modificando pequena parte daquele formalismo 234 CAPÍTULO 11 CONTROLE DISCRETO Ex 100 Descreva claramente a relação entre o algoritmo para o pro blema da mochila e o princípio da indução matemática a versão forte Ex 101 Imagine um processo de decisão de Markov com horizonte fi nito onde a recompensa é definida probabilisticamente em função do tempo temos Rs a t h onde t é o tempo e h é o horizonte fixo ao invés de Rs a Você ainda pode determinar a equação de otimalidade Ela pode ria ser usada para modelar este problema como programa linear Ex 102 Mostre como modelar MDPs de horizonte finito como progra mas lineares Capítulo 12 O Algoritmo PrimalDual e suas Aplicações Neste Capítulo descrevemos o algoritmo PrimalDual para resolução de programas lineares A importância deste método está não em sua aplica bilidade em programas lineares comuns mas sim no seu uso para o de senvolvimento de algoritmos de otimização combinatória 121 O algoritmo primaldual Definição 121 primal restrito 122 Exercícios 237 238 CAPÍTULO 12 O ALGORITMO PRIMALDUAL E SUAS APLICAÇÕES 132 REPRESENTAÇÃO 241 132 Representação Na forma mais geral um programa quadrático é usualmente definido por min zλ x λcTx 1 2xTQx sa Ax b x 0 onde λ é um parâmetro escalar e x é um vetor com n elementos λcTx descreve a parte linear da função quadrática Q é uma matriz quadrada de ordem n descrevendo uma função qua drática A e b descrevem as restrições A é uma matriz m n e b é um vetor com m elementos É comum exigir que Q seja semidefinida positiva para garantir que a função sendo otimizada é convexa Exemplo 134 A função fvex 2x2 1 x2 3 x1x2 4x2x3 x1 3x2 é descrita por λ 1 e c 1 3 0 Q 4 1 0 1 0 4 0 4 2 jé que cTx 1 2xTQx 2x2 1 x2 3 x1x2 4x2x3 x1 3x2 Podese também adotar uma descrição mais compacta min zx 1 2xTQx sa Ax b x 0 Proposição 135 Qualquer função quadrática com n1 variáveis pode ser descrita por uma única matriz simétrica Q de ordem n 133 SOLUÇÕES ÓTIMAS PARA PROGRAMAS QUADRÁTICOS 243 133 Soluções ótimas para programas quadráticos Observamos que como somente a função objetivo é quadrática a região viável continua sendo um poliedro da mesma forma que em programa ção linear E similarmente podemos usar o gradiente da função objetivo para determinar a solução ótima A próxima figura mostra um exemplo de programa quadrático o po liedro da região viável tem arestas sólidas e as curvas de nível da função objetivo zx são pontilhadas x1 x2 z Se a função objetivo de um problema de minimização é convexa e o vértice do parabolóide está dentro da região viável ele é a solução ótima Se a função objetivo de um problema de minimização é côncava ou seja zx é convexa a solução ótima estará na borda do poliedro mas não necessariamente em um ponto extremo Observamos também que a função pode não ser convexa e nem côn cava e neste caso terá pontos de sela 244 CAPÍTULO 13 PROGRAMAÇÃO QUADRÁTICA 134 Método de Beale As restrições impostas ao problema são lineares e portanto descritas como Ax b como em um proglema de programação linear Só temos uma função quadrática no objetivo cujas derivadas direcionais podemos calcu lar de forma semelhante ao que fizemos no método Simplex No entanto para cada função quadrática de uma variável o gradiente aponta para dire ções opostas em lados diferentes do véretice da parábola no caso linear o gradiente do obejtivo é constante porque é uma função linear e a direção de maior aumento é fixa Já no caso quadrático a direção muda porque o gradiente de uma função quadrática é linear Isto significa que seguir cegamente o gradiente pode não levar ao ótimo Exemplo 137 Para um primeiro exemplo minimalista temos o seguinte problema min x 12 sa x 2 x 0 A figura a seguir mostra a região viável e a função objetivo 134 MÉTODO DE BEALE 245 0 1 2 3 4 0 1 2 3 4 x z 0 1 2 3 4 f f x Observe que neste exemplo o poliedro tem dimensão um como mostra parte de baixo da figura ele é o segmento de reta entre x 0 e x 2 Na parte superior da figura usamos o plano para representar somente a função objetivo Os pontos 0 e 2 são os únicos pontos extremos do poliedro e clara mente o ponto ótimo x 1 não é um deles O que ocorre no exemplo 137 pode acontecer cada vez que uma va riável não básica e que portanto valia zero é selecionada para entrar na base O método de Beale é uma adaptação simples do algoritmo Simplex que leva em consideração esta situação Começamos em um vértice da região viável que é um poliedro exatamente como em problemas de progra mação linear Depois seguimos por diferentes soluções viáveis básicas Quando observarmos que uma derivada muda de sinal entre dois pontos extremos modificamos o problema de forma a garantir que a solução en contrada não estará em nenhum dos dois pontos extremos mas sim onde aquela derivada é zero 248 CAPÍTULO 13 PROGRAMAÇÃO QUADRÁTICA 2 Escreva as variáveis básicas em função das não básicas no tableau isto é o mesmo que usar a matriz identidade como base 3 Expresse a função objetivo em função das variáveis não básicas 4 Verifique as derivadas parciais de cada variável não básica xk 5 Se nenhuma derivada parcial indica que poderia haver melhora no objetivo a solução é ótima 6 Se há alguma derivada parcial que indica que há vantagem em intro duzir uma variável nãobásica na base aumentamos a variável não básica até que uma das duas situações a seguir se concertize a uma das básicas chega em zero b a derivada parcial fzk muda de sinal Se a acontecer escolha uma coluna para deixar a base como no método Simplex Se b ocorrer insira na base a variável ui 1 2 zk f 7 Repita o processo até que as derivadas parciais das variáveis originais do problema indiquem otimalidade e que as variáveis artificiais in troduzidas sejam todas zero Exemplo 139 Considere o problema min x1 2x2 2x2 2 sa x1 x2 2 2x1 x2 4 x 0 Pomos o problema na forma padrão min x1 2x2 2x2 2 sa x1 x2 x3 2 2x1 x2 x4 4 x 0 135 PONTOS INTERIORES 251 135 Pontos interiores Métodos de pontos interiores podem ser usados na resolução de proble mas de programação quadrática O método de affine scaling descrito na seção 721 adaptase à programação quadrática o gradiente do objetivo projetado no espaço nulo de A muda a cada iteração porque depende do ponto Além disso não basta que projetemos no espaço nulo de A porque se o ótimo for ponto interior o algoritmo andará de lado a lado da região viável sem chegar ao ótimo Notas Os primeiros métodos para resolução de programas quadráticos foram desenvolvidos por Wolfe Wol59 Dantzig Dan61 e Beale Bea55 Méto dos modernos para otimização de funções convexas em geral são descri tos por Luenberger Lue10 O método do elipsoide pode ser usado para programas quadráticos quando a função objetivo é convexa Quando a função objetivo não é con vexa o problema é NPdifícil PS91 Exercícios Ex 103 Converta os problemas do início do Capítulo para a forma min xTQx sa Ax b Ex 104 Desenvolva um programa que leia uma expressão quadrática e mostre Q tal que xTQx seja equivalente à expressão dada este poderia ser um módulo de entrara para um sistema de otimização Ex 105 Use o método de Beale para obter uma solução ótima para os 252 CAPÍTULO 13 PROGRAMAÇÃO QUADRÁTICA seguintes problemas i min x1 2x2 x2 2 sa x1 2x2 4 3x1 2x2 6 x 0 ii max 3x1 6x2 4x2 1 4x1x2 x2 2 sa x1 4x2 9 x1 x2 3 x 0 Ex 106 Implemente o método de Beale Ex 107 O método de Beale pode ser usado com qualquer função obje tivo convexa Mostre como usálo com funções diferenciáveis convexas não quadráticas Ex 108 Implemente o método de affine scaling para programação qua drática Capítulo 14 Otimização Não Linear Neste Capítulo abordamos otimização não linear Além de ser um tópico importante por sua aplicabilidade também permite compreender melhor os casos mais restritos de programação linear e quadrática Um problema de programação não linear consiste em minimizar uma função qualquer fx sujeito a restrições quaisquer gix min fx sa gix 0 i 1 k hjx 0 j 1 l onde f Rn R gi Rn R e hj Rn R são funções quaisquer Podemos também descrever um problema de otimização não linear apenas com as restrições de desigualdade já que cada igualdade é equi valente a duas desigualdades Definimos a seguir os conceitos de ótimo local e global Definição 141 Ótimo local Seja f Rn R O ponto x é um mínimo local de f se fx fx para todo x em alguma vizinhança de x Um máximo local é definido de forma análoga Definição 142 Ótimo global Seja f Rn R O ponto x é o mínimo global de f se fx fx para todo x Domf O máximo global é definido de forma análoga Tratamos neste Capítulo de dois casos diferentes otimizações sem res trições quando as restrições não existem e com restrições Em ambos os casos tratamos primeiro da caracterização dos pontos ótimos as condi ções de otimalidade e depois dos métodos 253 141 OTIMIZAÇÃO SEM RESTRIÇÕES 255 1 0 1 2 3 2 0 2 1 05 0 O gráfico da função mostra que pode haveruma grande quantidade de óti mos locais em uma função não convexa o que é uma grande dificuldade para os métodos de otimização 1411 Condições de otimalidade Nesta seção abordamos as condições necessárias e suficientes para que um ponto seja ótimo local Tratamos separadamente de condições de pri meira ordem que envolve o gradiente do objetivo e de segunda ordem onde a matriz Hessiana é usada Para demonstrar as condições necessárias de otimalidade usamos o Teorema de Taylor Teorema 144 de Taylor Seja f Rn R contínua e diferenciável e seja y Rn Então existe t 0 1 tal que fx y fx fx tyTy Além disso se f é duas vezes diferenciável fx y fx fxTy 1 2yT2fx tyy Teorema 145 Condição necessária de otimalidade de primeira ordem Seja f Rn R Se f é diferenciável em x e x é ótimo máximo ou mínimo local de f então fx 0 Intuitivamente o gradiente em x deve ser zero de outra forma ele indicaria uma direção para onde f teria valores ainda melhores Este raci ocínio é formalizado a seguir 256 CAPÍTULO 14 OTIMIZAÇÃO NÃO LINEAR Demonstração Suponha que x seja um mínimo local em um problema de minimização com função objetivo f Rn R Suponha também por contradição que fx 0 Então seja d x Temos portanto dTfx igual a fx2 que é menor que zero Como o gradiente de f é contínuo perto de x deve existir algum k R tal que para todo t 0 k dTfx td 0 No entanto pelo teorema de Taylor para qualquer s 0 k existe algum r tal que fx sd fx sdTfx rd e fx sd fx para todo s 0 k e portanto há uma direção a partir de x na qual f decresce mas como presumimos inicialmente que x é mínimo local concluímos que nossa suposição de que fx 0 é falsa Para problemas de maximização o raciocínio é semelhante A recíproca do Teorema 145 não vale se estivermos minimizando po deremos encontrar fx 0 em um máximo local ou ponto de sela Exemplo 146 A figura a seguir mostra a função fx x3 3x2 3x 1 x fx 1 1 2 3 2 4 6 No ponto x 1 temos o gradiente igual a zero fx fx 3x2 6x 3 3 6 3 substituindo x 1 0 141 OTIMIZAÇÃO SEM RESTRIÇÕES 257 No entanto não se trata de um mínimo local De fato como esta função é estritamente crescente2 ela não tem mínimos locais ou globais Se a função é convexa todo mínimo local é mínimo global e o teste do gradiente enunciado nas condições de primeira ordem é também sufici ente Em outros casos precisamos de testes adicionais Teorema 147 Condição necessária de otimalidade de segunda ordem Seja f Rn R Então Se x é mínimo local então 2fx é semidefinida positiva Se x é máximo local então 2fx é semidefinida negativa Demonstração Suponha que 2fx não é semidefinida positiva Então deve haver algum d Rn tal que dT2fxd 0 Como 2f é contínua perto de x deve haver algum k R tal que para todo r 0 k dT2fx rdd 0 Fazendo uma expansão de Taylor para todo s 0 k existe algum r tal que fx sd fx sdTfx 1 2s2dT2fx rdd fx 1 2s2dT2fx rdd fx 0 Teorema 145 fx e encontramos uma direção a partir de x na qual f decresce Se f é convexa a matriz hessiana de f será positiva definida para todo o domínio de f O Teorema 148 dá condições suficientes para que um ponto seja ótimo local A demonstração é pedida no Exercício 110 Teorema 148 Condições suficientes de otimalidade de segunda ordem Seja f Rn R uma função contínua e duas vezes diferenciável suponha que 2f é contínua em uma vizinhança aberta de x e que fx 0 Então 2Verificase facilmente tratase de fx x132 que é x3 transladada para a direita em 1 e para cima em 2 264 CAPÍTULO 14 OTIMIZAÇÃO NÃO LINEAR 1424 Métodos 143 Otimização linear e dualidade Claramente um problema de programação linear é um caso particular de otimização não linear Notas Ademonstração do Teorema 144 de Taylor pode serencontrada em livros de Cálculo de Várias Variáveis CJ99 Apo69 Os livros de Luenberger Lue10 Boyd e Vandenberghe BV04 e de Nocedal NW06 são boas introduções ao assunto e contém demonstra ções detalhadas das condições de KarushKuhnTucker Os livros de Ba zaraa BSS06 e Griva GNS09 são bons como segunda leitura Exercícios Ex 109 Reescreva o primeiro exemplo como problema de minimização e mostre as condições de otimalidade para o problema modificado Ex 110 Demonstre o Teorema 148 Ex 111 Mostre como foram obtidos λ1 e λ2 no exemplo 1415 Ex 112 Considere novamente o exemplo 1410 Suponha que tenhamos mudado o problema mantendo a mesma função objetivo e as mesmas restrições mas agora queremos minimizar Faça uma análise semelhante àquela feita no exemplo 1415 mostrando a solução ótima os multiplica dores de Lagrange e o valor da Hessiana Ex 113 Considere o seguinte problema min x2 y2 sa x2 y2 x y 1 cosx xy i Mostre o dual do problema ii Descreva o Lagrangeano e as condições de KarushKuhnTucker iii Determine se 0 0T é solução ótima Ex 114 Mostre a forma geral do dual de um programa quadrático 268APÊNDICE A SOLUÇÃO INTEIRAPARAPROBLEMAS DE TRANSPORTE DEMONSTRAÇÃO SEM UNIMODULARIDADE Como os coeficientes αk são zero nos interessam os coeficientes βj Mas na parte inferior da matriz cada xlj aparece uma única vez e portanto precisamos também que todos os βj sejam zero Assim a única combinação linear que resulta em zero é com αi 0 e βj 0 i j portanto as m n 1 linhas são linearmente independentes e o posto da matriz de restrições é m n 1 Observe que isto significa que durante a execução do método Simplex teríamos também m n 1 variáveis básicas Definição A2 Uma matriz A é triangular se puder ter suas linhas reorde nadas de forma que aij 0 sempre que i j Teorema A3 A base para um problema de transporte é triangular Demonstração Considere a tabela de transporte 93 Ela mostra clara mente a solução viável básica que estivermos trabalhando portanto po demos usála para representar uma base Suponha que tenhamos alocado valores em um conjunto de células obtendo uma solução viável básica Mostraremos que cada linha ou coluna tem o valor de exatamente uma variável básica primeiro mostramos que deve haver pelo menos uma va riável básica em cada linhacoluna e depois argumentamos que deve ha ver ao menos uma linha ou coluna onde não há mais que uma variável básica alocada e que o resultado deve valer para o sistema que resulta de sua remoção Primeiro notamos que não há linha ou coluna sem variável básica ou seja sem célula alocada porque os ai e bj são positivos Suponha por absurdo que cada linha e cada coluna tenham pelo me nos duas variáveis básicas alocadas O número de variáveis básicas é então k 2m k 2n E portanto k m n mas temos somente m n 1 variáveis básicas porque este é o posto da matriz de restrições Assim existe ao menos uma linha ou coluna onde há somente uma variável básica alocada Se removermos esta linha ou coluna obteremos um sistema reduzido e o argumento pode ser repetido Como podemos obter os valores de cada variável básica uma a uma neste processo por simples substituição concluímos que a matriz é tri angular 269 Além do fato da base ser triangular os coeficientes nela são unitários e disso concluímos o Teorema a seguir Teorema A4 Quando todos os ai e bj são inteiros os valores das variáveis básicas para qualquer base serão também inteiros Exercícios Ex 115 O Teorema A1 pode ser mostrado extraindo de A uma matriz quadrada de ordem m n 1 e observando seu determinante Elabore esta demonstração 270APÊNDICE A SOLUÇÃO INTEIRAPARAPROBLEMAS DE TRANSPORTE DEMONSTRAÇÃO SEM UNIMODULARIDADE 274 APÊNDICE B RESPOSTAS E DICAS Resp Ex 35 Dica Se xj não está na base a proposiçõ vale trivialmente Se xj está na base xj é componente do vetor x A1 B b logo é o produto de m elementos de A1 B por elementos de b Já B1 é um determinante de ordem m 1 dividido por um determinante de ordem m Resp Ex 36 i não ii É um hiperplano com dimensão m 1 Todo ponto viável é ótimo Resp Ex 39 O problema é degenerado Resp Ex 42 x4 30 x6 20 O valor do objetivo é 160 Resp Ex 45 Escreva o dual e observe que Mv w significa que w é combinação linear das colunas de M com coeficientes em v Resp Ex 49 O Exemplo 52 mostra como obter o dual com uma va riável a mais Tente fazer uma troca de variáveis no dual obtido daquela forma Resp Ex 50 Não será única Resp Ex 58 Para garantir uma solução viável básica faça projeção pa ralela a uma aresta que liga o ponto extremo atual para um em Rn1 Resp Ex 59 Não porque a nova restrição pode eliminar várioas solu ções viáveis básicas e isso faria com que o trabalho usando o dual fosse maior do que reiniciar o primal Resp Ex 68 O poliedro definido pelo dual também é integral Resp Ex 90 As opções de cada jogador são a quantidade de palitos 0 p 3 a esconder e seu palpite 0 a 6 Uma formulação in Ficha Técnica Este texto foi produzido inteiramente em LATEX em um sistema GNULi nux Os diagramas foram criados sem editor gráfico usando diretamente o pacote TikZ O ambiente Emacs foi usado para edição do texto LATEX 277 Bibliografia ABD09 David Avis David Bremner e Antoine Deza Polyhedral Compu tation AMS 2009 ISBN 9780821846339 Apo69 Tom M Apostol Calculus Vol 2 MultiVariable Calculus and Linear Algebra with Applications to Differential Equations and Probability Wiley 1969 ISBN 9780471000075 Bar98 Cynthia Barnhart et al BranchandPrice column generation for solving huge integer programs Em Operations Research 463 1998 pp 316329 Bar02 Alexander Barvinok A Course in Convexity AMS 2002 ISBN 9780821829684 Bea55 E M L Beale On Minimizing a Convex Function Subject to Li near Inequalities Em Journal of the Royal Statistics Society B 17 1955 pp 173184 Bel03 Richard Bellman Dynamic Programming Dover 2003 ISBN 9780486428093 Ber07 Dimitri P Bertsekas Dynamic Programming and Optimal Con trol 2007 ISBN 9781886529083 Bis14 Johannes Bisschop AIIMS optimization modelling 2014 ISBN 9781847539120 BJ77 Mokhtar S Bazaraa e John J Jarvis Linear Programming and Network Flows Wiley 1977 ISBN 0471060151 BN03 Dimitri Bertsekas e Angelia Nedic Convex Analysis and Opti mization Athena Scientific 2003 ISBN 9781886529458 BSS06 Mokhtar S Bazaraa Hanif D Sherali e C M Shetty Nonlinear Programming Theoryand Algorithms WileyInsterscience 2006 ISBN 9780471486008 279 280 BIBLIOGRAFIA BT96 Dimitri P Bertsekas e John Tsitsiklis NeuroDynamic Program ming Athena Scientific 1996 ISBN 9781886529106 BV04 Stephen Boyd e Lieven Vandenberghe Convex Optimization Cambridge 2004 ISBN 9780521833783 Can64 J S De Cani A dynamic programming algorithm for embed ded Markov chains when the planning horizon is at infinity Em Management Science 10 1964 p 716 CJ99 Richard Courant e Fritz John Introduction to Calculus and Analy sis Vol II1 Springer 1999 ISBN 9783540665694 Cor09 Thomas Cormen et al Introduction to Algorithms 3ª ed MIT Press 2009 Dan61 George B Dantzig Quadratic Programming AVariant of the Wolfe Markovitz Algorithms Rel técn OCR612 Operations Research Center University of California Berkeley 1961 Dan90 George B Dantzig The Diet Problem Em Interfaces 204 1990 pp 4347 DPV06 Sanjoy Dasgupta Christos Papadimitriou e Umesh Vazirani Al gorithms McGrawHill 2006 ISBN 0073523402 Dym07 Harry Dym Linear Algebra in Action AMS 2007 ISBN 9780 821838136 Eri03 BajalinovErik B LinearFractional Programming theory methods applications and software Springer 1003 ISBN 978146134822 1 Fil07 Ricardo Shirota Filho et al Multilinear and Integer Program ming for Markov Decision Processes with Imprecise Probabili ties Em Proceedings of the 5th International Symposium on Imprecise Probability Theories and Applications 2007 FT91 Drew Fudenberg e Jean Tirole Game Theory MIT Press 1991 ISBN 9780262061414 GL00 Marco Cesar Goldbarg e Henrique Pacca L Luna Otimização Combinatória e Programação Linear modelos e algoritmos Cam pus 2000 ISBN 8535205411 GNS09 Igor Griva Stephen G Nash e Ariela Sofer Linear and Nonlinear optimization SIAM 2009 ISBN 9780898716610 BIBLIOGRAFIA 281 Gom58 R E Gomory Outline of an Algorithm for Integer Solution to Linear Programs Em Bulletin of the American Mathematical Society 645 1958 How60 Ronald A Howard Dynamic Programming and MarkovProces ses MIT Press 1960 How71 R A Howard SemiMarkovian decision processes Proc In tern Stat Inst Ottawa Canada 1963 1971 IE94 C C White III e H K ElDeib Markov decision processes with imprecise transition probabilities Em Operations Research 424 1994 pp 739749 IN07 Hideaki Itoh e Kiyohiko Nakamura Partially observable Mar kov decision processes with imprecise parameters Em Artifi cial Intelligence 17189 2007 pp 453490 Jew63 W S Jewell Markovrenewal programming I Formulation fi nite return models Markovrenewal programming II infinite return models example Em Operations Research 11 1963 pp 938 971 Kar84 Narendra Karmarkar A New Polynomial Time Algorithm for Linear Programming Em Combinatorica 44 1984 pp 373 395 Kuh55 H W Kuhn The Hungarian Method for the Assignment Pro blem Em Naval Research in Logistic Quarterly 2 1955 pp 83 97 KV12 Bernhard Korte e Jens Vygen Combinatorial Optimization The ory and Algorithms Springer 2012 ISBN 9783642244872 Lay07 Steven R Lay Convex Sets and Their Applications Dover 2007 ISBN 9780486458038 LD60 A H Land e A G Doig An automatic method of solving dis crete programming problems Em Econometrica 283 1960 pp 497520 Lim06 Dag Mendonça Lima et al Tabela Brasileira de Composição de Alimentos TACO 2006 Lue10 David G Luenberger Linearand NonlinearProgramming Sprin ger 2010 ISBN 9781441945044 MG06 Jiri Matousek e Bernd Gärtner Understanding and Using Linear Programming Springer 2006 ISBN 9783540306979 282 BIBLIOGRAFIA NM07 John von Neumann e Oskar Morgenstern Theoryof Games and Economic Behavior Princeton UniversityPress 2007 ISBN 978 0691130613 NR10 Peter Norvig e Stuart Russel Artificial Intelligence a modern approach Pearson 2010 ISBN 0136042597 NW06 Jorge Nocedal e Stephen Wright Numerical Optimization Sprin ger 2006 ISBN 9780387303031 OR94 Martin J Osborne e Ariel Rubinstein A Course in Game Theory MIT Press 1994 ISBN 9780262650403 Pow11 Warren B Powell Approximate Dynamic Programming Sol ving the Curses of Dimensionality Wiley 2011 ISBN 9780470604458 PS91 Panos M Pardalos e Vavasis Stephen A Quadratic program ming with one negative eigenvalue is NPhard Em Journal of Global Optimization 11 1991 pp 1522 PS98 Christos Papadimitriou e Kenneth Steiglitz Combinatorial Op timization Dover 1998 ISBN 0486402584 PT87 Christos H Papadimitriou e John N Tsitsiklis The complexity of Markov decision processes Em Mathematics of Operations Research 123 1987 pp 441450 Put05 Martin L Puterman Markov Decision Processes Discrete Sto chastic Dynamic Programming WileyInterscience 2005 ISBN 9780471727828 Roc96 Ralph Tyrell Rockafellar Convex Analysis Princeton University Press 1996 ISBN 9780691015866 Rus06 Andrzej Ruszczyski NonlinearOptimization Princeton Univer sity Press 2006 ISBN 9780691119151 SB98 Richard S Sutton e Andrew G Barto Reinforcement Learning An Introduction MIT Press 1998 ISBN 9780262193986 Sch03 AlexanderSchrijver Combinatorial Optimization Springer 2003 ISBN 9783540443896 Sch98 AlexanderSchrijver Theoryof Linearand IntegerProgramming Wiley 1998 ISBN 9780471982326 Sin06 S M Sinha Mathematical Programming theory and methods Elsevier 2006 ISBN 9788131203767 BIBLIOGRAFIA 283 SL70 J K Satia e R E Lave Markovian decision processes with un certain transition probabilities Em Operations Research 21 1970 pp 728740 Sta97 I N StancuMinasian Fractional Programming theory methods and applications Kluwer 1997 ISBN 9789401065047 Ste94 Robert F Stengel Optimal Control and Estimation Dover 1994 ISBN 9780486682006 Van07 Robert J Vanderbei Linear Programming foundations and ex tensions Springer 2007 ISBN 9780387743875 WN99 Laurence A Wolsey e George L Nemhauser Integer and Com binatorial Optimization WileyInsterscience 1999 ISBN 978 0471359432 Wol59 Philip Wolfe The Simplex Method forQuadratic Programming Em Econometrica 273 1959 Wol98 Laurence Wolsey Integer Programming WileyInsterscience 1998 ISBN 9780471283669 Índice Remissivo aberto 41 affine scaling 169 afimindependente 52 análise de sensibilidade 147 aresta 10 atribuição problema de 206 branchandbound 185 branchandcut 187 branchandprice 189 coeficiente reduzido de custo 78 80 combinação afim 43 combinação convexa 44 condições de otimalidade otimiza ção não linearsem restrições255 otimização não linear com restrições261 contração 226 controle discreto 221 convexo conjunto 46 corte de Gomory 181 cortes α β 189 definida positiva matriz 66 degenerada solução 105 degenerado problema 105 dual 121 dual de problema não linear 261 dualidade 121 em otimização não linear 261 elipsoide método do 163 envoltória afim 43 envoltória convexa 47 epigrafo 49 espaço de Banach 226 estratégia mista em jogos de soma zero 215 fechado 42 fluxo em redes 10 folgas complementares 131 função convexa 65 função côncava 65 grafo dirigido 10 Hessiana matriz 67 hiperplano 49 Húngaro algoritmo 206 indefinida matriz 66 interpretação do dual 123 jogo de soma zero 213 jogos de soma zero 284 ÍNDICE REMISSIVO 285 formulação como programa li near 215 KarushKuhnTucker condições de otimalidade 261 Lagrangeano 260 261 matriz triangular 268 maximização 4 MDPIP 230 minimização 4 mistura ótima 15 mochila problema da 221 multiplicadores de Lagrange 260 máximo global 253 máximo local 253 método das duas fases para obter tableau Simplex inicial 95 método do M grande para obter ta bleau Simplex inicial 101 mínimo global 253 mínimo local 253 mínimos quadrados 239 objetivo 4 otimização não linear 253 otimização não linearcom restrições 259 otimização não linearsem restrições 254 peso em arestas 10 planos de corte 180 poliedro 51 politopo 52 dimensão de 53 POMDP 230 POMDPIP 232 ponto extremo 50 pontos interiores método de 169 portfólio otimização de 240 primal 121 processo Markoviano de decisão 223 programação dinâmica 221 programação fracionária 29 programação inteira 33 177 programação linear problema de 4 programação quadrática 239 rede de fluxo 11 regressão linear 24 sa 1 semidefinida positiva matriz 66 semiespaço 49 sequência de Cauchy 226 simplex método 73 simplex dual algoritmo 133 simplex revisado método 109 SMDP 229 solução básica 58 viável 4 viável básica 58 ótima 4 teoria os jogos 213 totalmente unimodular matriz 187 transporte problema de 193 unimodularidade 187 286 ÍNDICE REMISSIVO variável de folga 5 vértice 10 ótimo global 253 ótimo local 253