Notas de Aula de Programação Linear (PDF)

Capı́tulo 1 Programações lineares 1.1 Introdução ao curso Apesar de o nome do curso ser Pesquisa Operacional, talvez seria mais descritivo se fosse chamado “Introdução à otimização”. Problemas de otimização são uma (grande) sub-área da Pesquisa Operacional. Matematicamente faland...

Capı́tulo 1 Programações lineares 1.1 Introdução ao curso Apesar de o nome do curso ser Pesquisa Operacional, talvez seria mais descritivo se fosse chamado “Introdução à otimização”. Problemas de otimização são uma (grande) sub-área da Pesquisa Operacional. Matematicamente falando, um problema de otimização é um problema em que se busca achar o máximo ou o mı́nimo de uma função dentro de um determinado conjunto. Por exemplo: Quais são os valores máximo e mı́nimo da função f (x) = x2 com x ∈ R? E se o intervalo for limitado a [1, 5]? Qual seu mı́nimo e máximo neste intervalo? Chamamos o primeiro caso de um problema de otimização irrestrita, isto é, não há condições restringindo o domı́nio. O segundo caso é conhecido como um problema de otimização restrita uma vez que restrições são impostas no conjunto possı́vel de valores que x pode assumir. Buscamos a solução ótima, isto é, o ponto onde a função atinge o valor máximo ou mı́nimo dentre os valores possı́veis do domı́nio. A dificuldade de um problema de otimização pode estar na descrição da função, ou na compre- ensão do conjunto. Ou em ambos. Por exemplo: Qual o máximo da função f (x, y) = x2 /y y se x e y estão entre -1 e 1? Qual o máximo da função f (x) = sin(x) entre os números racionais? Funções como as que descrevemos acima tipicamente necessitam do uso do cálculo para estudarmos seus pontos de máximo e mı́nimo. Neste curso, entretanto, nossas funções serão mais simples. 1.1.1 Otimização neste curso Neste curso estamos interessados em duas sub-áreas da Pesquisa Operacional, chamadas Pro- gramação Linear (PL) e Programação Inteira (PI). Ambas estas técnicas buscam reescrever matematicamente problemas do mundo real através de problemas de otimização restritos. Um termo mais amplo que engloba tanto PL quanto PI é a Programação Matemática, definido como a utilização de ferramentas matemáticas para a alocação ótima de recursos limitados quando planejamos (programamos) atividades. 5 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Tanto em PL quanto PI, estamos interessados somente em otimizar funções lineares. Uma função f é linear se, para vetores x e y e um número a, f (x + y) = f (x) + f (y) e f (a · x) = a · f (x) Por exemplo, f (x) = 2x f (x1 , x2 ) = 2x1 + 3x2 f (x1 , x2 , x3 ) = x1 − x2 + 5x3 são funções lineares, ao passo que f (x) = x + 5 f (x1 , x2 ) = x1 x2 f (x1 , x2 , x3 ) = x21 + x3 não são. Exercı́cio 1. Prove estes fatos. Otimizar uma função linear (ou decidir que não é possı́vel achar o seu ótimo) é a princı́pio uma tarefa simples. Por exemplo: Qual o máximo de f (x) = 2x? Qual o máximo da mesma função no intervalo [−4, 10]? Problemas de otimização linear se tornam difı́ceis quando há mais variáveis. Neste caso, a di- ficuldade estará sempre na compreensão do conjunto onde a função está sendo definida, ou nas restrições que as variáveis da função devem satisfazer. Neste curso, essas restrições serão também sempre lineares, mas ainda assim veremos que os problemas podem ser bem difı́ceis. 1.2 Introdução à Programação linear A primeira parte do curso trata apenas de Programação Linear (PL), o mais “simples” dos modelos de programação matemática. Há centenas de aplicações práticas de PL em uma vasta gama de áreas, incluindo problemas de logı́stica na indústria, mercados financeiros, ciências sociais e naturais, e muitas outras. A teoria e suas aplicações começou por volta da Segunda Guerra Mundial, com Leonid Kantorovich utilizando-a para modelar a economia centralizada da União Soviética e George Dantzig utilizando-a para modelar problemas de logı́stica decorrentes da guerra. Dantzig também desenvolveu o primeiro algoritmo efetivo para resolver problemas de PL - o chamado algoritmo Simplex - que ainda hoje é largamente utilizado em solvers comerciais e open- source de problemas de programação matemática. O enorme aumento de poder computacional nas últimas décadas permite hoje resolver eficientemente problemas de PL com centenas de milhares de variáveis. Um problema de PL é descrito por três componentes importantes: Variáveis de decisão, que representam efetivamente a decisão que deve ser tomada no problema modelado, Função objetivo, que representa em um valor numérico o benefı́cio ou custo associado às decisões que devem ser tomadas. É a função que deve ser maximizada ou minimizada. Restrições, que representam a limitação dos recursos do mundo real. As restrições impõem que a solução deve obedecer certas regras. Em um problema de PL, a função objetivo e as restrições são sempre lineares e as variáveis de decisão são sempre variáveis reais (possivelmente dentro de um intervalo). 6 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional 1.2.1 Exemplo Ache o máximo da função f (x1 , x2 ) = x1 + x2 supondo que x1 e x2 satisfaçam x1 ≥ 0 ; x2 ≥ 0 ; 2x1 + x2 ≤ 4 ; x1 + 2x2 ≤ 3. No caso, as variáveis de decisão são dadas por x1 e x2 e a função objetivo é maximizar x1 + x2. Abaixo, reescrevemos este PL utilizando a notação mais comum: max x1 + x 2 sujeito a 2x1 + x2 ≤ 4 x1 + 2x2 ≤ 3 x1 ≥ 0 x2 ≥ 0 Ao desenhar estas desigualdades no gráfico, a região delimitada é dada por: 4 3 2x1 + x2 = 4 x2 2 1 x1 + 2x2 = 3 0 0 1 2 3 4 x1 Observe que qualquer ponto à direita da reta azul torna a desigualdade 2x1 + x2 ≤ 4 inválida. Por exemplo, considere o ponto (2, 2) - neste caso temos que 6 ≰ 4 e diz-se que a desigualdade foi violada. Já para qualquer ponto à esquerda da reta azul o oposto ocorre. Por exemplo, ao substituirmos o ponto (1, 1) na desigualdade obtemos 3 ≤ 4. Desta forma, temos que: Apenas pontos à esquerda e abaixo da reta azul respeitam a desigualdade 2x1 + x2 ≤ 4, Apenas pontos à esquerda e abaixo da reta vermelha respeitam a desigualdade x1 + 2x2 ≤ 3, Apenas pontos à direita do eixo x2 respeitam a desigualdade x1 ≥ 0 e 7 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Apenas pontos acima do eixo x1 respeitam a desigualdade x2 ≥ 0. A união destes conjuntos é chamada de região viável ou área viável e pode ser vista no gráfico abaixo: 4 3 2x1 + x2 = 4 x2 2 1 Área viável x1 + 2x2 = 3 0 0 1 2 3 4 x1 Todos os pontos da região viável são soluções válidas para o problema. A principal questão de um problema de PL é encontrar, dentre todos os pontos válidos, qual é aquele que maximiza ou minimiza a função objetivo desejada. Exercı́cio 2. Dentro da área viável acima, qual par de pontos (x1 , x2 ) maximiza x1 + x2 ? E 3x1 + x2 ? E x1 − x2 ? E minimizar? Três comentários importantes: (i) Se você prestou atenção, o máximo ou mı́nimo sempre acabou sendo um dos vértices. Isto nem sempre é o caso, por exemplo, se quiséssemos o máximo de f (x1 , x2 ) = 2x1 + x2 ou o mı́nimo de f (x1 , x2 ) = x1. Mas sempre será o caso de que o máximo ocorrerá num ponto de fronteira entre o conjunto e o seu complemento. (ii) Nem sempre problemas deste tipo terão solução, mas isto sempre dependerá do conjunto em que estamos otimizando, nunca da função. Por exemplo, qual o máximo de f (x1 , x2 ) = x1 +x2 no conjunto x1 ≥ 0 ; x2 ≥ 0 ; x 1 − x2 ≤ 2 ? E em x1 ≥ 0 ; x2 ≥ 0 ; x1 + x2 ≤ −2 ? (iii) Problemas deste tipo possuem grande aplicabilidade prática. Veremos logo mais um exemplo. Infelizmente, a grande parte dos problemas ocorre com muitas variáveis, ou seja, é impossı́vel termos uma visualização gráfica fiel ao problema. Entretanto, procure manter sempre uma intuição geométrica: dentro de um conjunto limitado por retas, ou planos, ou hiperplanos, você estará procurando o canto onde um plano, ou hiperplano, atinge seu máximo ou mı́nimo. 8 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional 1.2.2 Exemplo prático Suponha uma empresa que produza 4 tipos de produto. A empresa possui duas máquinas diferentes e a produção de cada produto requer horas em ambas as máquinas, além de horas operacionais e horas em um processo de controle de qualidade. A tabela abaixo especifica, para cada produto, quantas horas são necessárias em cada máquina/atividade. A tabela inclui também o preço de venda (assuma demanda infinita): Produto Máquina 1 Máquina 2 Operacional Qualidade Preço de venda 1 11 4 8 7 300 2 7 6 5 8 260 3 6 5 5 7 220 4 5 4 6 4 180 Por mês, a máquina 1 pode funcionar no máximo 700 horas, e a 2 por no máximo 500 horas. A empresa pode comprar no máximo 600 horas de trabalho operacional ao custo de 8 reais a hora, e 650 horas de controle de qualidade ao custo de 6 reais a hora. Quantos itens de cada produto a empresa deve produzir de forma a maximizar seu lucro? Vamos formular esse problema como uma PL. (i) Variáveis de decisão: Temos que decidir quantas unidades de cada produto serão produzi- das. Para isso, vamos criar variáveis x1 , x2 , x3 , x4 representando estes valores. Ou seja, x1 é uma variável ainda desconhecida cujo valor é o número de unidades que devem ser produzidas do produto 1. Estas são as únicas incertezas a respeito deste problema, e todos os demais valores associados (por exemplo: quantas horas usar de uma determinada máquina?) serão determinados por x1 ,..,x4. Entretanto, muitas vezes o uso de variáveis adicionais facilita a compreensão e expressão do problema. Neste caso, vamos introduzir variáveis y1 e y2 que representam as quantidades de horas de trabalho operacional e controle de qualidade utilizadas. Ao final, veremos também que teria sido possı́vel modelar o problema sem usar essas variáveis. (ii) Função objetivo: A empresa busca maximizar o lucro. A função matemática que representa o lucro é dada por: 300x1 + 260x2 + 220x3 + 180x4 − 8y1 − 6y2. (iii) Restrições: Podemos utilizar no máximo 700 horas da máquina 1: 11x1 + 7x2 + 6x3 + 5x4 ≤ 700. E no máximo 500 horas na máquina 2: 4x1 + 6x2 + 5x3 + 4x4 ≤ 500. Trabalho operacional: 8x1 + 5x2 + 5x3 + 6x4 ≤ y1 Controle de qualidade: 7x1 + 8x2 + 7x3 + 4x4 ≤ y2. 9 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional As limitações na quantidade de horas que podem ser contratadas: y1 ≤ 600 e y2 ≤ 650. Não faz sentido que as variáveis possam ter valores negativos, logo: x1 , x2 , x3 , x4 , y1 , y2 ≥ 0. Estas últimas restrições são geralmente chamadas de restrições de não-negatividade. Exercı́cio 3. Como ficaria este modelo caso optássemos por não utilizar as variáveis y1 e y2 ? Exercı́cio 4. Resolva esta PL. 1.3 Programação linear - formalização Uma programação linear (PL) é definida como um problema de maximizar ou minimizar uma função linear (ou afim) sujeita a um número finito de restrições lineares. Considerando o exemplo: max 3x1 + 2x2 − x3 + 5 (1.1) sujeito a x 1 + x2 ≤ 9 x3 ≤ 3 x1 , x2 , x3 ≥ 0, estamos maximizando a função objetivo f (x1 , x2 , x3 ) = 3x1 + 2x2 − x3 + 5 sujeita às restrições x1 + x2 ≤ 9, x3 ≤ 3, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. Importante: uma restrição linear é sempre uma inequação da forma f (x) ≤ β , f (x) ≥ β , f (x) = β, onde x é um vetor de variáveis e β é um escalar. Note que 3x1 + 5x2 − x3 + x4 < 5 não é uma restrição linear, já que a desigualdade é estrita. Uma solução para a formulação (1.1) é uma atribuição de valores às variáveis (x1 , x2 , x3 ). Uma solução é viável se possui a propriedade de que todas as restrições são satisfeitas. Uma solução é ótima se é viável e maximiza (ou minimiza se o problema for de minimização) a função objetivo. 1.4 Modelagem Como dito anteriormente, a PL modela diversos problemas da vida real. Nesta seção, incluı́mos alguns exercı́cios e exemplos de aplicações. Exemplo 1. Considere o seguinte problema de demanda, armazenamento e distribuição. Uma companhia local, Pompéu Insumos, de revenda de insumos agrı́colas prevê que nos próximos meses, a demanda por seu principal insumo seja a seguinte: 10 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional mês 1 2 3 4 demanda em litros 5000 8000 9000 6000 No começo de cada mês, esta empresa pode comprar este insumo de um distribuidor regional pelos seguintes valores: mês 1 2 3 4 custo por litro 0.75 0.72 0.92 0.90 A Pompéu Insumos possui um tanque de armazenamento de 4000 litros, que atualmente já contém 2000 litros. A empresa deseja saber quantos litros de insumo deve comprar no começo de cada mês para suprir a demanda e ao mesmo tempo minimizar seus custos. Note que se o insumo é comprado e revendido imediatamente, não é preciso armazená-lo no tanque. Somente o excedente para o mês seguinte é armazenado. Para simplificar, assumimos que o custo de armazenamento é zero (o que pode não ser verdade na prática). Variáveis de decisão: Cada mês, Pompéu Insumos precisa determinar (1) quantos litros comprar e (2) quantos armazenar do insumo. Estes valores são incertos e devem ser decididos pela empresa: são os candidatos ideais para as variáveis de decisão. Introduzimos então 8 variáveis: p1 ,..., p4 referentes a quanto comprar, e t1 ,..., t4 referentes à capacidade ocupada do tanque. Note que já fomos informados que t1 = 2000. Função objetivo: Como informado, a Pompéu Insumos deseja minimizar o custo de compra dos insumos. Então a função objetivo é min 0.75p1 + 0.72p2 + 0.92p3 + 0.90p4. Restrições: No começo do primeiro mês, a quantidade de insumos comprada, acrescida da quantidade que já havia no tanque, deve ser igual ou exceder a demanda do primeiro mês, e este excedente corresponde exatamente ao que é armazenado para o segundo mês. Portanto p1 + t1 = 5000 + t2. A restrição acima impõe a consistência dos valores envolvidos. Igualmente p2 + t2 = 8000 + t3 , p3 + t3 = 9000 + t4 , p4 + t4 ≥ 6000. Exercı́cio 5. Termine de formular esta PL, incluindo condições iniciais e demais restrições, e escreva no formato de (1.1). Qual você acredita ser a solução ótima para o problema? Como o problema seria alterado se o custo de armazenamento fosse 0.10 por litro de insumo por mês? Exercı́cio 6. Considere a seguinte tabela nutricional de alguns tipos de comida: Comida preço / porção calorias / p. gordura / p. proteı́na / p. carbs / p. Cenoura 0.14 23 0.1 0.6 6 Batata 0.12 171 0.2 3.7 30 Pão integral 0.20 65 0.0 2.2 13 Queijo 0.75 112 9.3 7.0 0 Amendoim 0.15 188 16.0 7.7 2 11 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Uma nutricionista deseja montar um cardápio que minimize os custos diários, ao mesmo tempo que as seguintes demandas nutricionais são satisfeitas: pelo menos 2000 calorias pelo menos 50g de gordura pelo menos 100g de proteı́na pelo menos 250g de carboidratos. Modele este problema com uma PL (é possı́vel fracionar porções). Exercı́cio 7. Um banco faz quatro tipos de empréstimos para seus clientes pessoais. Cada tipo de empréstimo rende os seguintes juros anuais para o banco: Primeira hipoteca a 14% Segunda hipoteca a 20% Reforma residencial a 20% Empréstimos pessoais a 10% O banco pode emprestar no máximo 250 milhões, sendo também restrito pelas seguintes polı́ticas: A primeira hipoteca deve ser pelo menos 55% de todas as hipotecas e pelo menos 25% de todos os empréstimos. A segunda hipoteca não deve exceder 25% de todos os empréstimos. Para evitar descontentamento do público, a taxa de juros média não deve exceder 15%. Formule o problema de empréstimos bancários como uma PL visando maximizar o recebimento de juros e satisfazendo as limitações impostas. Note que estas condições impostas potencialmente limitam o lucro que o banco pode ter, mas também limitam sua exposição a risco em uma área particular. É um princı́pio fundamental do gerenciamento de risco que o risco é reduzido ao dividir o dinheiro apropriadamente em diferentes áreas. Exercı́cio 8. Uma refinaria processa três tipos diferentes de petróleo. Cada tipo de petróleo possui uma planilha de custos diferente, expressando condições de transporte e preços na origem. A planilha de custos e a quantidade máxima disponı́vel é dada abaixo: Tipo de petróleo Quantidade máxima Custo por disponı́vel (barril/dia) barril/dia 1 3500 19 2 2200 24 3 4200 20 12 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Por outro lado, cada tipo de petróleo é mais ou menos apropriado para a produção de três tipos de gasolina diferentes: amarela, azul e superazul. As especificações de cada tipo de gasolina são dadas abaixo: Tipo de gasolina Especificação preço de venda R$/barril Amarela não mais que 70% de 1 22 não mais que 30% de 1 Azul 28 não menos que 10% de 2 não mais que 30% de 1 Superazul não menos que 40% de 2 35 não mais que 50% de 3 Formule este problema como uma PL que calcule quanto de cada gasolina a empresa deve produzir, e quais tipos de petróleo deve utilizar em cada de forma a maximizar seus lucros. Suponha que não há perda volumétrica no processo da refinaria. DICA: use 9 variáveis, cada variável correspondendo a quanto de cada tipo de petróleo será usado em cada tipo de gasolina. Exercı́cio 9. Você administra uma empreiteira, e projeta construir uma casa. As seguintes ativi- dades devem ser feitas B - escavar e fazer a fundação. F - subir as paredes E - parte elétrica P - encanamento D - acabamento das paredes e pisos L - jardim. Você possui equipes na sua empreiteira que realizam cada uma das atividades. O tempo em dias para concluir tudo é: tarefa B F E P D L tempo 3 2 3 4 1 2 Infelizmente as tarefas não podem ser realizadas todas simultaneamente. Se baseie na lista de restrições abaixo e formule o problema de construir a casa no menor tempo possı́vel como uma PL. F só pode começar após B. L só pode começar após B. E só pode começar após F. P só pode começar após F. D só pode começar após E e P. 13 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Exercı́cio 10. Tente resolver o seguinte sistema de equações: 2x + y = −1 x+y =1 x + 3y =4 −2x + 4y =3 Tentou? Vamos então tentar encontrar os valores que mais se aproximam de ser uma solução do sistema. Formule o problema de achar um vetor (x, y) que mais se aproxime de resolver este sistema como uma PL. Ou seja, você deseja achar (x, y) tal que a soma |2x + y + 1| + |x + y − 1| + |x + 3y − 4| + | − 2x + 4y − 3| seja mı́nima. E se ao invés de minimizar a soma, você desejasse minimizar o maior dos valores absolutos. Ainda é possı́vel modelar como uma PL? Exercı́cio 11. Em um restaurante, os funcionários trabalham 5 dias consecutivos e folgam 2. Como há dias de mais e menos movimento, a tabela abaixo indica quantos funcionários devem trabalhar em cada dia da semana: Dia Seg Ter Qua Qui Sex Sab Dom Demanda 17 13 15 19 14 16 11 Qual o menor número de funcionários que o restaurante deve contratar de forma a suprir a demanda de trabalho? Modele este problema como uma PL (vamos permitir que funcionários sejam “fracionários” por enquanto). E se o pagamento de funcionários que trabalham domingo fosse 1.5 vezes o pagamento nos outros dias, como a empresa poderia minimizar o custo? 1.5 Possibilidades para uma PL Vimos, no exemplo gráfico da Seção 1.2, o caso de uma PL que possui uma solução ótima clara. Nem toda PL, porém, possui uma solução ótima, como veremos nos exemplos a seguir. 1.5.1 PLs inviáveis Pode ser que uma PL não possua solução viável. Neste caso, dizemos que a PL é inviável. Considere o problema: min 2x1 + x2 sujeito a x1 + x2 ≤ 4 x2 ≥ 5 x1 , x2 ≥ 0 Como pode ser facilmente observado na Figura 1.5.1, não há nenhum ponto que satisfaça todas as 4 restrições. O problema é inviável. 14 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Figura 1.5.1: Exemplo de PL inviável 1.5.2 PLs ilimitadas Considere o problema: max x1 + x2 sujeito a x1 + x2 ≥ 1 −x1 + x2 ≤ 2 x1 − 2x2 ≤ 2 x1 , x2 ≥ 0 O exemplo é ilustrado na Figura 1.5.2. No gráfico, foram desenhadas linhas de contorno para diferentes valores da função objetivo. Pelo diagrama, é evidente que existem soluções viáveis para a PL com valores muito altos. Uma PL de maximização é ilimitada se existem soluções viáveis com valores arbitrariamente grandes na função objetivo. Uma PL de minimização é ilimitada se existem soluções viáveis com valores negativos arbitrariamente pequenos na função objetivo. Note que, por mais que uma PL possa ser matematicamente ilimitada, na vida real, uma mensagem de um solver indicando que o problema é ilimitado muito provavelmente indica algum erro do usuário na formulação matemática do problema. Tipicamente trata-se da omissão de uma ou mais restrições. 1.5.3 Resultados possı́veis de uma PL Para qualquer PL, ocorre exatamente um dos resultados a seguir: O problema possui solução ótima, O problema é inviável, O problema é ilimitado. 15 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Figura 1.5.2: Exemplo de PL ilimitada A afirmação acima, verdadeira para PLs, pode ser falsa para problemas de otimização que não são lineares. Por exemplo, considere o seguinte problema de otimização não-linear: min x2 sujeito a x1 · x 2 ≥ 1 x1 , x2 ≥ 0 A região viável é a área acima da hipérbole da Equação x1 · x2 = 1, vista na Figura 1.5.3. Podemos observar que o problema é viável (exemplo: o ponto x = (1, 1) é uma solução viável) e não é ilimitado, uma vez que é um problema de minimização e não possui solução menor que zero. Porém, o problema não possui solução ótima, uma vez que não há solução viável de valor zero, e ainda assim há soluções viáveis onde o valor de x2 pode chegar arbitrariamente próximo a zero. 1.6 Forma padronizada Dado um vetor c ∈ Rn , uma matriz m × n A e um vetor b ∈ Rm , considere a seguinte PL max cT x sujeito a Ax ≤ b x ≥ 0. Significa que estamos procurando o vetor x ∈ Rn que maximiza o produto interno cT x sujeito às desigualdades obtidas a partir de cada linha da matriz A, além de restrições de não-negatividade. 16 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Figura 1.5.3: Exemplo de problema de otimização não-linear Exemplo 2. Considere a PL max x1 + x2 sujeito a x1 + 2x2 ≤ 2 2x1 + x2 ≤ 2 x1 , x2 ≥ 0. Esta PL pode ser expressa na forma matricial descrita acima da seguinte maneira:  
x1 max 1 1 · x2      1 2 x1 2 sujeito a ≤ 2 1 x2 2 x ≥ 0. Também poderı́amos ter incorporado as restrições de não-negatividade na matriz, como abaixo, mas esta não será nossa preferência geralmente.  
x1 max 1 1 · x2     1 2   2  2  1  x1   sujeito a  ≤ 2 −1 0  x2 0 0 −1 0 Neste exemplo:       1 2 2   1  2 1 2 x1 c= , A= −1  , b=  0 , x= 1 0 x2 0 −1 0 17 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Exercı́cio 12. Resolva a PL acima. Exercı́cio 13. Considere o primeiro exemplo de PL, (1.1). Identifique naquele exemplo quais são os vetores c, b, x e a matriz A. Conforme você notou no exercı́cio, nem sempre o conjunto de desigualdades obtidos da mode- lagem poderá ser imediatamente agrupado em um formato matricial, e então alguns ajustes podem precisar ser feitos. Como forma de padronizar a interpretação de PLs definimos a forma padrão de igualdades (FPI) a seguir. Definição 1. Uma PL está na forma padrão de igualdades se existem vetores c, b e uma matriz A tal que a PL se expressa como max cT x sujeito a Ax = b x ≥ 0. Em outras palavras, uma PL está na FPI se é um problema de maximização. com exceção das restrições de não-negatividade, todas as outras são igualdades. toda variável possui uma restrição de não negatividade. Qualquer PL pode ser expressa na FPI. Em geral, quando uma inequação é obtida na for- mulação, ela pode ser substituı́da por uma igualdade ao adicionarmos uma variável extra. Exercı́cio 14. Expresse a desigualdade 2x + 3y ≤ 5 utilizando apenas igualdades e/ou restrições de não-negatividade. Dica: adicione uma variável w. Faça o mesmo para 8x − y + z ≥ 10. Problemas de minimização também podem ser expressos como maximização. Exercı́cio 15. Expresse min x + y + z como max cT x. Ou seja, diga quais são os vetores c e x. Ainda pode haver um fator dificultador de que, ao modelarmos o problema, uma das variáveis não possua uma restrição de não-negatividade. Neste caso, a variável em questão deve ser subs- tituı́da por duas outras. Note o exemplo abaixo. Exemplo 3. min x + y sujeito a x − y ≤ 2 x + y ≥ −1 x≥0 18 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Note que não podemos simplesmente adicionar y ≥ 0, porque isto alteraria a solução da PL. No caso, a PL dada possui mı́nimo igual a −1 referente à solução (x, y) = (0, −1), onde y < 0. Para termos restrições de não-negatividade para todas as variáveis, vamos substituir y por duas variáveis: y = y+ − y−, e agora exigimos y + , y − ≥ 0. No caso, quando y = −1, temos y + = 0 e y − = 1, ambos não- negativos. A PL se torna então: min x + y + − y − sujeito a x − (y + − y − ) ≤ 2 x + (y + − y − ) ≥ −1 x, y + , y − ≥ 0 Há portanto três passos básicos a serem realizados para transformar uma PL para a FPI. (i) Trocar min por max, se necessário, adicionando um sinal negativo em c (lembrando de multiplicar o valor objetivo encontrado no final por −1). (ii) Trocar todas as inequações por igualdades adicionando variáveis extras (sempre não-negativas). Estas serão chamadas de variáveis de folga. (iii) Trocar cada variável livre por duas variáveis não-negativas. Exemplo 4. A PL do exemplo 3 se torna portanto:   x  +
y −  max −1 −1 1 0 0 ·  y    z1  z2   x   y +    1 −1 1 1 0   2 sujeito a · y −  = −1 1 1 −1 0 −1   z1  z2 x, y + , y − , z1 , z2 ≥ 0 Exercı́cio 16. Expresse as PLs obtidas nos exercı́cios de modelagem na FPI. 1.7 Certificados Como vimos, ou uma PL possui solução ótima, ou não possui solução viável, ou é ilimitada. De fato, o Teorema Fundamental de Programações Lineares estabelece que essas são as únicas possibilidades. Nesta seção, vamos mostrar, mas não demonstrar, que existem “certificados” que são suficientes para determinar em qual dos três casos a PL se encaixa. 19 Capı́tulo 5 Programações inteiras 5.1 Programações inteiras Considere o problema de otimização abaixo: max 12x1 + 2x2 sujeito a x2 ≤ 4 3x1 − 2x2 ≤ 3 10x1 + 2x2 ≤ 23 x1 , x2 ≥ 0 x1 , x2 ∈ Z. Se ignorarmos a última restrição (que diz que as variáveis devem ser inteiras), a PL correspondente pode ser representada graficamente pela figura abaixo: 5.0 x2 = 4 3x1 − 2x2 = 3 x2 2.5 0.0 10x1 + 2x2 = 23 0 2 4 6 x1 83 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Os vértices do poliedro que define a área viável são (0, 0), (1, 0), (2, 32 ), ( 32 , 4), (0, 4). A figura também inclui, em vermelho, os pontos dentro da área viável que são inteiros. O ótimo (da PL) está no ponto (2, 23 ). O problema é que ele é fracionário, isto é, a solução não satisfaz a condição de integralidade imposta. Observe a figura abaixo: 5.0 x2 = 4 (1,4) 3x1 − 2x2 = 3 x2 2.5 3 (2, ) 2 0.0 10x1 + 2x2 = 23 0 2 4 6 x1 Os pontos inteiros viáveis mais próximos da solução ótima da PL são (1, 1) e (1, 2). Porém, como podemos ver na figura, o ótimo inteiro é o ponto (1, 4). As linhas verdes pontilhadas representam a função objetivo passando pelo ponto ótimo da PL (com valor 27) e pelo ponto ótimo do problema inteiro (com valor 20). Este exemplo dá uma ideia da dificuldade que é lidar com problemas de programação inteira: a solução ótima não é necessariamente próxima da solução ótima da PL obtida quando ignoramos a restrição de integralidade. Quando consideramos mais variáveis (mais dimensões), o problema se torna ainda mais crı́tico. Apontamos alguns fatos relevantes: (i) O ótimo de uma programação inteira não está necessariamente na fronteira do poliedro. (ii) Se a programação é um problema de maximização, o ótimo da PL é sempre maior ou igual que o ótimo da PI. No exemplo acima, o ótimo da PL era 27, e da PI 20. (iii) O que acontece com dualidade? (iv) Se todos os vértices do poliedro são pontos de coordenadas inteiras, então esses ótimos irão coincidir. Em relação ao ponto (iv) acima, veremos mais pra frente que algumas PIs com um tipo de estrutura especı́fica podem ser resolvidas facilmente. Porém, a grande maioria das PIs não possui tal estrutura, e é um problema em aberto se é possı́vel resolve-las com algoritmos polinomiais ou não. 84 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Veremos em breve dois algoritmos que resolvem PIs. Ambos os algoritmos possuem complexi- dade exponencial, porém funcionam rapidamente na prática em diversos casos (mas não todos!). Porém, inicialmente, vamos apresentar alguns exemplos de problemas que podem ser modelados como PIs. 5.2 Modelagem Vimos nas aulas anteriores várias PLs onde faria sentido se, na verdade, tivessem sido modeladas como PIs. Por exemplo, ao planejar a produção de uma empresa, permitimos que a solução final sugerisse produzir uma quantidade fracionária de um certo produto ao invés de unidades inteiras. Outro exemplo é o problema da dieta, onde a solução pode indicar a compra de “5.3 ovos” ou “10.2 porções de carne”. Na prática, faria sentido impor que as porções devem ser inteiras para diversos alimentos (com exceção daqueles que compramos a granel, por exemplo). Nesta seção, veremos exemplos de problemas onde somente faz sentido utilizar programação inteira. Exemplo 17. Uma empresa possui N projetos nos quais pode investir. Cada projeto i ∈ N possui retorno esperado positivo ci (em reais). Porém, devido a restrições orçamentárias, não é possı́vel investir em todos. No caso, cada projeto i requer que a empresa faça aportes financeiros ait nos tempos t = 1,... , T. O orçamento disponı́vel para estes aportes no tempo t é bt (previamente conhecido ou estimado). Formule este problema como um problema de programação inteira. Variáveis de decisão: Devemos decidir em quais projetos a empresa irá investir. Não faz sentido “investir em meio projeto”, ou “investir duas vezes no mesmo projeto”. Ou seja, a decisão é binária: para cada projeto i, ou investe, ou não investe. Assim, vamos propor variáveis xi que terão o valor 1 se optarmos por investir no projeto i, ou o valor 0, caso contrário. Este tipo de variável é geralmente chamado de variável binária. É uma variável inteira limitada pelos valores 0 ≤ xi ≤ 1. É bastante utilizada em situações onde devemos tomar decisões binárias, sim ou não. A grande maioria dos problemas mais interessantes de PI requer variáveis binárias. Função objetivo: Tendo decidido as variáveis, a empresa busca maximizar o retorno esperado dos investimentos: X N max ci x i i=1 Note que o retorno esperado do projeto i, ci , será positivo na função objetivo apenas caso xi seja 1. Restrições: Para cada perı́odo de tempo t = 1,... , T possuı́mos um orçamento limitado que não pode ser ultrapassado: X N ait xi ≤ bt t = 1,... , T i=1 Observe que a formulação possui T restrições, uma para cada perı́odo de tempo. O modelo completo é dado abaixo: 85 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional X N max ci x i i=1 X N sujeito a ait xi ≤ bt t = 1,... , T i=1 0 ≤ xi ≤ 1, xi inteiro, i = 1,... , N É comum também utilizarmos a notação xi ∈ B para dizer que uma variável pode ter apenas os valores 0 ou 1. No problema acima, assumimos que ci é conhecido. Na prática, o retorno esperado é uma estimativa cuja incerteza pode ser alta (alto risco). Existem diversos modelos de otimização que buscam gerenciar o risco ao controlar a incerteza enquanto busca-se maximizar o retorno esperado. Exercı́cio 65. Suponha que a empresa possua três condições adicionais: (a) Os projetos 3 e 4 são concorrentes, não é possı́vel investir em ambos ao mesmo tempo. (b) Se a empresa investir no projeto 2, então deve obrigatoriamente investir no projeto 5. (c) Se a empresa investir nos projeto 1 e 4, então deve obrigatoriamente investir no projeto 6. Acrescente restrições à formulação acima de forma a garantir que estas condições sejam respeitadas. Exemplo 18. Uma empresa possui N tarefas urgentes que devem ser cumpridas. Cada tarefa exige um funcionário (há também N funcionários disponı́veis). Todo funcionário pode fazer toda tarefa, mas como cada funcionário tem um nı́vel de capacitação diferente, o tempo gasto varia. Já sabemos de antemão que o funcionário i precisa de cij horas para executar a tarefa j. A empresa busca minimizar o tempo total gasto nas tarefas e quer que todos os funcionários fiquem ocupados (ninguém deve ficar a toa). Formule este problema como uma PI. Variáveis de decisão: Temos xij = 1 se o funcionário i executa a tarefa j, xij = 0 caso contrário. Formulação: O problema é formulado da seguinte forma: X N X N min cij xij i=1 j=1 X N sujeito a xij = 1 i = 1,... , N j=1 X N xij = 1 j = 1,... , N i=1 xij ∈ B i = 1,... , N, j = 1,... , N O primeiro conjunto de restrições garante que todo funcionário será alocado a uma tarefa, e o segundo conjunto garante que toda tarefa será executada por um funcionário. 86 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Este problema é conhecido como o problema da atribuição (assignment). Veremos mais pra frente que esta é uma PI “fácil” de ser resolvida. Exercı́cio 66. Altere a formulação acima de acordo com os detalhes abaixo: (a) As tarefas 3, 4, e 5 serão executadas na mesma sala. O funcionário 3 recentemente descobriu que o funcionário 2 é amante de sua esposa, o que fez com que chegassem às vias de fato em pleno ambiente de trabalho. A empresa obviamente não quer que os dois fiquem na mesma sala. Adicione esta restrição à formulação acima. (b) Os funcionários 4 e 5 trabalham bem em conjunto, e seria interessante que ou eles fizessem as tarefas 1 e 2 (pois são relacionadas), ou fizessem as tarefas 6 e 7 (que também são relaci- onadas). Altere a formulação para garantir que um dos casos acima será verdadeiro. Dica: utilize uma variável binária extra. (c) Ao invés de minimizar o tempo total das tarefas, a empresa quer finalizar os trabalhos o mais cedo possı́vel, ou seja, ela quer que a última tarefa a ser finalizada termine o quanto antes. Altere a formulação acima para atender este caso. Exercı́cio 67. O governo de Minas deve decidir onde construir novos quartéis do corpo de bom- beiros. Há uma região com 6 cidades no norte do Estado que atualmente que não é atendida por nenhum quartel em menos de 45 minutos. O governo gostaria de garantir que há um corpo de bombeiros a no máximo 15 minutos de distância de cada uma destas 6 cidades. Abaixo, uma tabela com o tempo necessário para dirigir da cidade i até a cidade j (a tabela não é necessariamente simétrica): De/para 1 2 3 4 5 6 1 0 10 20 30 30 20 2 10 0 25 35 20 10 3 20 25 0 15 30 20 4 30 35 15 0 15 25 5 20 20 30 15 0 14 6 20 10 20 25 14 0 Devido ao orçamento apertado, o governo gostaria de construir o menor número possı́vel de quartéis. Formule este problema como uma PI. Exercı́cio 68. Você quer resolver um problema de machine learning e possui N features dis- ponı́veis. Você acha que N features são demais e gostaria de reduzir este conjunto para K < N features, sendo K um valor fixo previamente decidido. O ideal é que as features selecionadas se- jam pouco correlacionadas, ou seja, queremos minimizar a soma das correlações entre todas as K features selecionadas. O valor cij representa a correlação entre as features i e j. Formule este problema utilizando Programação Inteira Linear Mista (neste caso, podem haver variáveis inteiras e variáveis não inteiras). Exercı́cio 69. Uma empresa produz mapas do mundo que são vendidos em bancas de jornal. Cada um dos N paı́ses do mapa deve ser colorido com uma cor, porém paı́ses vizinhos não podem ter cores iguais. Devido aos altos custos dos cartuchos de tinta, a empresa gostaria de utilizar o menor número possı́vel de cores no mapa. Considere que há C cores disponı́veis e que já sabemos 87 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional de antemão quais paı́ses são vizinhos, isto é, temos uma matriz Bij = 1 se os paı́ses i e j são vizinhos, 0 caso contrário. Formule o problema de encontrar o menor número possı́vel de cores a serem utilizadas em um mapa como um problema de programação inteira. Exercı́cio 70. Desafio O Brasileirão possui 20 equipes e é disputado utilizando-se uma fórmula de pontos corridos, onde todas as equipes se enfrentam duas vezes (uma em casa, uma fora), totalizando 38 jogos por equipe. Idealmente, as equipes devem alternar entre jogar uma partida em casa, uma fora de casa, e assim vai. Não é interessante para o torcedor que uma equipe jogue 3 partidas seguidas em casa, por exemplo, ou que jogue 5 partidas seguidas fora de casa. Por isto, estas situações nunca devem ocorrer. Matematicamente, porém, não sabemos se existe uma solução onde nenhuma equipe jogue duas partidas seguidas em casa ou duas seguidas fora (quando isto ocorre, temos uma quebra). (a) Considere inicialmente que cada equipe jogará apenas uma vez contra as demais (19 jogos cada). Formule este problema como uma PI que minimiza o número de quebras. (b) Adicione uma restrição que impõe que se na primeira rodada uma equipe jogou em casa, então deve jogar fora de casa na última rodada. (c) O que você deve fazer para resolver agora o problema com 38 rodadas, onde se a equipe i enfrentou j em casa na rodada t, deve então enfrenta-la fora de casa na rodada t + 19 (tabela com dois turnos simétricos)? 5.3 Escrevendo uma PI como uma PL Até agora tratamos PIs da seguinte forma. Apresentamos uma PL do tipo max cT x sujeito a Ax = b x ≥ 0, e adicionamos uma restrição x ∈ Zn. Nosso objetivo nesta semana é ser capaz de formular uma PI sem precisar codificar a restrição de integralidade da maneira acima. Nesta semana, aprenderemos como, ao sermos apresentados a uma matriz A qualquer, fazer pequenas modificações de modo que o ótimo da PL seja um ótimo da PI correspondente. Exemplo 19. Considere
max 1 1 x     2 1 7  1 2  7 sujeito a  x ≤   −1 −4  −4 −1 0 −1/2 x inteiro. Cada uma das restrições corresponde às retas (1), (2), (3) e (4) abaixo, e a região verde é portanto a região de viabilidade da relaxação linear. 88 Capı́tulo 2 Simplex Neste capı́tulo, apresentaremos o método Simplex, amplamento difundido para a resolução de problemas de programação linear. Começamos com algumas definições matemáticas importantes. 2.1 Poliedros e convexidade Um poliedro é uma região do espaço delimitada por restrições lineares. Pode ser formalmente descrito como a interseção de um número finito de subespaços definidos pelos conjuntos de pontos que satisfazem equações ou desigualdades lineares. Por exemplo, em Rn , uma equação linear do tipo aT x = b define um hiperplano que é um subespaço do espaço Rn. Os dois principais tipos de subespaços observados em uma PL são: Subespaço de Equações Lineares: Dado um sistema de equações lineares Ax = b, o conjunto de soluções que satisfaz o sistema forma um subespaço de Rn. Esse subespaço pode ser visualizado como um hiperplano, um plano, uma reta ou um ponto no espaço, dependendo da dimensão do sistema. Subespaço de Desigualdades Lineares: Cada desigualdade linear define um semi-espaço, que é uma parte do espaço limitada por um hiperplano. A interseção de vários semi-espaços forma uma região no espaço onde todas as desigualdades são satisfeitas simultaneamente. Para visualizar o conceito de poliedro, considere um problema simples em duas variáveis, x1 e x2 , com as desigualdades: x1 + x2 ≤ 5, x1 ≥ 0, x2 ≥ 0. Cada uma dessas desigualdades define um semi-espaço no plano R2. A interseção desses semi- espaços define uma região finita no plano, que chamamos de polı́gono (um poliedro em duas dimensões). Poliedros generalizam polı́gonos em problemas de maior dimensão, com múltiplas variáveis. Observe que as restrições lineares de uma PL sempre são da forma aT x ≤ β ou aT x = β ou aT x ≥ β. Note que aT x ≥ β é equivalente a (−aT )x ≤ −β, e que aT x = β é equivalente a simultaneamente termos aT x ≤ β e (−aT )x ≤ −β. Portanto as restrições de uma PL sempre podem ser expressas usando ≤, e ao juntarmos todas elas, teremos Ax ≤ b (∗) para uma certa matriz A e um vetor b. O conjunto de vetores x satisfazendo (∗) é um poliedro. 24 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional 2.1.1 Convexidade Uma combinação convexa de dois ou mais pontos x1 , x2 ,... , xk ∈ Rn é uma combinação linear desses pontos na qual os coeficientes são não-negativos e somam 1. Formalmente, temos: x = λ1 x1 + λ2 x2 + · · · + λk xk P onde λi ≥ 0 para todo i = 1,... , k e ki=1 λi = 1. Em outras palavras, uma combinação convexa é uma média ponderada dos pontos que garante que o ponto x resultante estará “entre” os pontos x1 , x2 ,... , xk. Uma função f : R → R é convexa em um intervalo [a, b] se, para quaisquer dois pontos x1 , x2 ∈ [a, b], a função avaliada em qualquer ponto entre eles está abaixo ou sobre o segmento de reta que liga (x1 , f (x1 )) e (x2 , f (x2 )). Formalmente, temos: f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ), para todo λ ∈ [0, 1] Isto significa que no intervalo [a, b] a função não apresenta concavidade entre dois pontos quaisquer, e que a reta secante entre dois pontos no gráfico da função não fica abaixo do próprio gráfico. Um caso particular é o das funções lineares, onde a igualdade acima vale para todo λ e para [a, b] = [−∞, ∞]. Um conjunto C ⊆ Rn é convexo se, para quaisquer dois pontos x1 , x2 ∈ C, o segmento de reta que os conecta também pertence ao conjunto. Ou seja, para qualquer λ ∈ [0, 1]: λx1 + (1 − λ)x2 ∈ C. Em outras palavras, um conjunto convexo é aquele onde toda combinação convexa de dois pontos no conjunto ainda pertence ao conjunto. Como vimos, um poliedro é definido como a interseção de um número finito de subespaços e semi-espaços. Cada subespaço ou semi-espaço é descrito por equações ou desigualdades lineares. Temos então o seguinte teorema: Teorema 1. Poliedros são conjuntos convexos. Demonstração. Sejam x1 e x2 pontos satisfazendo Ax ≤ b. Temos que, para todo λ tal que 0 ≤ λ ≤ 1, A(λx1 + (1 − λ)x2 ) ≤ λb + (1 − λ)b = b. 2.1.2 Pontos extremos Uma vez estabelecido que poliedros são conjuntos convexos, introduzimos o conceito de ponto extremo de um poliedro. Esse conceito será essencial para compreender como o método Simplex navega pelas soluções viáveis em busca de uma solução ótima. Dizemos que um ponto x∗ ∈ P (onde P é um poliedro) é um ponto extremo de P se ele não pode ser expresso como uma combinação convexa de dois outros pontos distintos de P. Ou seja, se não existem x1 , x2 ∈ P , com x1 ̸= x2 , e λ ∈ [0, 1], tal que: x∗ = λx1 + (1 − λ)x2. 25 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Um ponto extremo é aquele que não pode ser “dividido” em outros dois pontos do poliedro. Ele se localiza nas bordas do poliedro, e não no interior de um segmento de reta formado por dois outros pontos do conjunto. Para ilustrar isso de maneira intuitiva, pense em um poliedro tridimensional como um cubo. Os pontos extremos do cubo são seus vértices. Nenhum vértice do cubo pode ser expresso como uma combinação convexa de outros dois vértices. No entanto, qualquer ponto ao longo de uma aresta do cubo pode ser escrito como uma combinação convexa dos dois vértices que formam essa aresta. Assim, somente os vértices são pontos extremos. Uma propriedade importante de poliedros, que não demonstraremos aqui, é que qualquer ponto do poliedro pode ser escrito como uma combinação convexa de seus pontos extremos1. Conside agora uma PL com função objetivo cT x, onde c ∈ Rn é um vetor de coeficientes e x ∈ Rn é o vetor de variáveis de decisão. Suponha que o conjunto de soluções viáveis seja representado por um poliedro P ⊆ Rn , ou seja, o conjunto de pontos x que satisfazem as restrições lineares do problema. A função objetivo pode ser expressa como: w = cT x. Teorema 2. Se existe um ponto x∗ ∈ P que maximiza w em P , então pelo menos um ponto extremo de P é um ponto de máximo. Demonstração. Suponha que x∗ maximiza w sobre o poliedro P. Se x∗ for um ponto extremo de P , já provamos o que queremos. Se x∗ não for um ponto extremo, ele pode ser escrito como uma combinação convexa de pontos extremos (como mencionado anteriormente). Seja x1 ,... , xk ∈P P o conjunto finito de k de pontos extremos de P , e sejam λ1 ,... , λk ∈ [0, 1] coeficientes tais que ki=1 λi = 1. Temos então que: x∗ = λ1 x1 + λ2 x2 + · · · + λk xk. Como a função objetivo é linear, temos: cT x∗ = λ1 cT x1 + λ2 cT x2 + · · · + λk cT xk. Ou seja, o valor da função objetivo em x∗ é uma média ponderada dos valores da função objetivo nos pontos extremos x1 ,... , xk. Como x∗ é um ponto de máximo, o valor de cT x∗ é maior ou igual ao valor em qualquer outro ponto do poliedro, o que implica que: cT x∗ ≥ cT xi para todo i = 1,... , k. Isso só é possı́vel se pelo menos um dos pontos extremos xi satisfizer cT xi = cT x∗. Logo, um dos pontos extremos de P também maximiza a função objetivo. 2.2 Soluções básicas Dada uma PL em FPI max cT x sujeito a Ax = b x ≥ 0, podemos sempre assumir que a matriz A está em um formato especial. O objetivo dos exercı́cios dirigidos a seguir é descobrirmos que formato é este. 1 A demonstração é consequência direta do Teorema de Carathéodory. 26 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Exercı́cio 20. Considere a PL abaixo
max 1 2 3 x     4 −1 0 7 1 0 −1    sujeito a  x = 2 1 1 1 3 2 −2 0 2 x ≥ 0. É possı́vel escrever uma PL equivalente a esta em que a matriz A possua menos linhas? Exercı́cio 21. Considere a PL abaixo
max 1 2 3 1 1 x     1 1 1 1 1 5 sujeito a 2 1  0 −1 −2 x =  0 3 1 −1 −3 −5 −5 x ≥ 0. Qual o posto dessa matriz? Ou seja, quantas colunas linearmente independentes existem? É possı́vel reduzir o número de linhas? Exercı́cio 22. Considere a PL abaixo
max 2 3 1 x     1 2 1 2 sujeito a 2   4 −1 x = 1 3 6 0 3 x≥0 Elimine linhas, se for possı́vel, e identifique colunas da matriz que formem uma matriz quadrada não-singular. Exercı́cio 23. Considere a seguinte PL em FPI max cT x sujeito a Ax = b x ≥ 0. Suponha que A possua m linhas linearmente independentes, e n colunas. Explique por que pode- mos assumir, sem qualquer prejuı́zo à solução da PL, que se n ≥ m, há precisamente m colunas linearmente independentes em A. Ao longo dos exercı́cios acima, vimos que sempre que uma PL estiver em FPI, podemos assumir que todas as m linhas são linearmente independentes (LI) e, consequentemente, que existe uma escolha de colunas para a matriz A que formam uma base para o espaço, ou seja, m colunas LI. Suponha que identificamos uma base de m colunas para o espaço. Podemos então construir uma solução para a PL ao: 27 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Resolver o sistema linear com apenas as colunas da base, Fixar as demais variáveis (relativas a colunas fora da base) em zero. Esta solução é chamada de solução básica, referente à base de colunas escolhida. Por exemplo, se as colunas da base são as as primeiras m colunas de A, então A estará na forma abaixo:   | A= AB | AN  (2.1) | onde AB é uma matriz quadrada não singular, e AN é uma matriz cujas colunas são combinações lineares das colunas de AB. Note que podem haver diferentes escolhas para as matrizes AB e AN (elas podem estar intercaladas), sempre dependendo da matriz original A. Quando temos Ax, podemos separar as variáveis que compõem o vetor x entre aquelas inde- xadas pelas colunas linearmente independentes e as outras. As variáveis de x que correspondem às colunas de AB são chamadas de variáveis básicas, ao passo que as demais são as variáveis não-básicas. Sempre podemos dividir o vetor x como   xB x= , xN onde o vetor xB possui as variáveis básicas, e xN as não-básicas. Note que, mesmo que as matrizes AB e AN estejam originalmente intercaladas em A, vale a igualdade abaixo: Ax = AB xB + AN xN. Exercı́cio 24. No exercı́cio 22, identifique as matrizes AB e AN , e os vetores xB e xN. Calcule AB xB e AN xN separadamente, e mostre que Ax = AB xB + AN xN. Dada uma matriz A no formato (2.1), e vetores x e b tais que Ax = b, observe que b é uma combinação linear das colunas em AB. No caso, b é tratado como uma coluna extra de A que pode ser escrita como uma combinação linear das colunas básicas de A. Então, existe um vetor z tal que Az = b, e AB z B = b e z N = 0. O vetor z como descrito acima é chamado de uma solução básica da PL. Exercı́cio 25. Novamente no exercı́cio 22, ache uma solução básica. Note que uma vez escolhida a matriz AB , existe uma única solução básica associada a z, e ela é definida por z B = A−1 B b, e z N = 0, com   zB z=. zN Considere então a solução básica z B = A−1 B b, e z N = 0: 28 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Se z B ≥ 0, então a solução é básica e viável. Se existe pelo menos um zi ∈ z B tal que zi < 0, então a solução é básica e inviável, uma vez que as restrições de não-negatividade da PL em FPI não são atendidas. Para os próximos dois teoremas, considere a PL em FPI: max cT x sujeito a Ax = b x ≥ 0, onde x ∈ Rn , A é uma matriz m × n com m restrições e n variáveis, m > n, e b ∈ Rm. Teorema 3. Qualquer solução básica viável de uma programação linear (PL) é um ponto extremo do poliedro definido pela área viável Ax = b, x ≥ 0. Demonstração. Suponha que x∗ seja uma solução básica viável, mas não seja um ponto extremo. Então, para 0 < λ < 1, podemos escrever: x∗ = λx1 + (1 − λ)x2 onde x1 ̸= x2 são soluções viáveis distintas. Como x∗ é uma solução básica, ela pode ser decomposta em um vetor x∗B (tal que AB x∗B = b) e outro x∗N = 0. As soluções x1 e x2 também podem ser decompostas em (x1B , x1N ) e (x2B , x2N ). Temos então que: x∗N = λx1N + (1 − λ)x2N Como x∗N = 0, x1N ≥ 0 e x2N ≥ 0, a relação acima só pode ser verdade para x1N = x2N = 0. Temos também que: x∗B = λx1B + (1 − λ)x2B Porém, como as colunas da base são linearmente independentes, x∗B é a solução única do sistema AB xB = b. Como x1 e x2 são viáveis e x1N = x2N = 0, temos também que AB x1B = b e AB x2B = b. Pela unicidade da solução deste sistema, a única forma disto ser verdade é se x∗B = x1B = x2B , contradizendo a hipótese de que x∗ não é um ponto extremo. Teorema 4. Todo ponto extremo do poliedro Ax = b, x ≥ 0 é uma solução básica. Demonstração. Suponha que um ponto extremo x∗ seja uma solução não básica viável (satisfa- zendo Ax∗ = b e x ≥ 0) com k > m colunas não nulas. Seja AK a submatriz retangular k × m contendo as colunas relativas às variáveis não nulas. Como o posto de AK é m, é possı́vel escrever uma combinação linear d de AK tal que AK d = 0 e d seja não-nulo. Para um ε pequeno, x∗ + εd e x∗ − εd continuam satisfazendo Ax = b, pois A (x∗ ± εd) = Ax∗ ± εAd = Ax∗ ± 0 = b. Como ε é pequeno, também temos que x∗ ± εd ≥ 0. Isto nos permite escrever x∗ como a seguinte combinação convexa: 1 ∗ 1 x∗ = (x + εd) + (x∗ − εd) 2 2 o que contradiz a premissa inicial de que x∗ é um ponto extremo. 29 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Para melhor visualizar esta demonstração, veja o exemplo numérico a seguir. Exemplo 8. Considere o poliedro: x1 + x2 ≤ 6 2x1 + x3 ≤ 8 x≥0 em FPI, fica:     1 1 1 0 6 x= 2 1 0 1 8 x ≥ 0.

Possuı́mos uma base trivial em x3 x4 , mas considere a solução não básica x∗T = 0 1 5 7
, que claramente satisfaz a área viável definida pelo poliedro. As variáveis não nulas são x2 x3 x4. Então, seja:   1 1 0 AK = 1 0 1
Através do vetor dT = −1 1 1 , temos que AK d = 0. Seja ε = 0.1. Observe que:       1 −1 0.9 ∗   xK + εd = 5 + 0.1    1 = 5.1 7 1 7.1       1 −1 1.1 ∗   xK − εd = 5 − 0.1  1 = 4.9   7 1 6.9 Note que ambos os pontos satisfazem AK x = b, e que:       1 0.9 1.1 5 = 1 5.1 + 1 4.9 2 2 7 7.1 6.9 Como pode ser escrito
como combinação convexa de outros dois pontos distintos, sabemos que o ponto 0 1 5 7 não é extremo. A conclusão que podemos tirar das últimas duas seções é que se uma PL possuir solução ótima, então pelo menos uma solução básica será ótima. Assim, podemos concentrar nossa busca pelo ótimo apenas nas soluções básicas viáveis. É exatamente isso que o método Simplex faz, como veremos na próxima seção. 30 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional 2.3 Simplex Considere a seguinte PL de exemplo: max 3x1 + 2x2 sujeito a 2x1 + x2 ≤ 8 x1 + 2x2 ≤ 8 x 1 + x2 ≤ 5 x ≥ 0 Definição 2. Uma PL em FPI tal que a base canônica do espaço de colunas aparece inteiramente como colunas da matriz A, e tal que as entradas correspondentes a estas colunas no vetor c são todas iguais a 0, é uma PL em forma canônica. Ou seja, será tal que AB = I (as colunas podem estar trocadas), e cB = 0. Quando uma PL está em forma canônica e há uma solução básica viável, sempre é possı́vel (tentar) melhorar a solução! Portanto o problema de achar a solução ótima de uma PL se reduz ao problema de colocar uma PL em forma canônica para uma solução básica viável. Confira como no exemplo abaixo. Exemplo 9. Começamos colocando a PL em FPI. No caso, basta adicionar uma variável de folga por restrição:
max w = 3 2 0 0 0 x     2 1 1 0 0 8 sujeito a 1 2 0 1 0 x = 8 1 1 0 0 1 5 x ≥ 0. (i) Esta PL já está em forma canônica. Note que as colunas 3, 4 e 5 formam uma base, e que nesta base, AB = I, e as entradas correspondentes de c são 0.
T (ii) Achamos a solução básica - no caso, x = 0 0 8 8 5 , cujo valor associado na função objetivo é w = 0. Ela é viável uma vez que todo o vetor x ≥ 0, e portanto prosseguimos. (iii) Identificamos no vetor c uma entrada positiva. Uma entrada positiva i em c em um problema de maximização implica que se xi correspondente fosse maior, o valor da função objetivo também seria maior. Escolhemos então esta entrada em c, que corresponde a uma coluna. No caso, escolhemos arbitrariamente a primeira (poderia ter sido a segunda). (iv) O próximo passo é alterar a solução aumentando o valor da variável x1 , deixando x2 fixo e reduzindo os valores das variáveis básicas x3 , x4 , x5. Quanto maior o valor de x1 , maior será o aumento do valor da função objetivo. Porém, x1 não pode aumentar indefinidamente pois temos que garantir que as variáveis básicas continuem com valores viáveis, isto é, continuem sendo não-negativas. Devemos então descobrir qual é o máximo valor possı́vel de x1 de forma que estas condições sejam satisfeitas. Para cada restrição, encontramos o maior valor que x1 pode obter de forma que a variável básica correspondente (aquela que possui coeficiente 1 na restrição i na PL em forma canônica) seja no mı́nimo zero: 31 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Restrição 1: Ignorando os coeficientes das variáveis não básicas fixas, temos que 2x1 + x3 = 8. O maior valor possı́vel de x1 = 4, senão x3 teria que ser negativo. Este valor é obtido ao dividir o valor de b1 pelo coeficiente A11 , 8/2. Restrição 2: Temos que x1 + x4 = 8, o maior valor possı́vel de x1 = 8. Restrição 3: Temos que x1 + x5 = 5, o maior valor possı́vel de x1 = 5. O máximo que podemos aumentar em x1 é o mı́nimo dos três valores acima, 4. Com este incremento, obtemos a nova solução
x= 4 0 0 4 1 , cujo valor associado na função objetivo é cT x = 12 (maior que a anterior). Em resumo: para encontrar o maior incremento possı́vel da variável x1 , que entrará na base, devemos calcular o mı́nimo bi /Ai1 para toda restrição i. Após recalcular os valores das variáveis básicas, temos que x
3 = 0. Neste caso
ela deixa de ser básica, sendo substituı́da por x1. Assim, xTB = x1 x4 x5 e xTN = x2 x3. Observação importante: pode ser que para uma restrição i o coeficiente Aij da nova variável xj a entrar na base seja negativo, neste caso bi /Aij < 0. Isto significa que a restrição i não limitaria o valor máximo que xj pode obter. Portanto, o maior incremento possı́vel de xj deve ser o mı́nimo bi /Aij para toda restrição i tal que Aij > 0. (v) O próximo passo é garantir que esta nova solução se torne uma solução básica viável para uma PL em forma canônica equivalente à original. Logo devemos alterar a PL de modo que (a) as colunas 1, 4 e 5 correspondam a uma matriz identidade. (b) a função objetivo seja 0 nas entradas 1, 4 e 5. Para (a), fazemos eliminação Gaussiana. Teremos
max 3 2 0 0 0 x=w     1 1/2 1/2 0 0 4 sujeito a 0 3/2 −1/2 1 0 x = 4 0 1/2 −1/2 0 1 1 x ≥ 0. Para (b), subtraı́mos a função objetivo por 3 vezes a primeira equação. Como isto altera o valor da função objetivo, compensamos adicionando 3 × 4 = 12. Portanto o problema de otimização não se altera, e teremos
max 0 1/2 −3/2 0 0 x = w − 12     1 1/2 1/2 0 0 4 sujeito a  0 3/2 −1/2 1 0 x = 4   0 1/2 −1/2 0 1 1 x ≥ 0. Note que a função objetivo não é mais linear, mas a adição de uma constante não afeta em qualquer maneira o problema de otimização. De fato, a solução básica
x= 4 0 0 4 1 satisfaz as equações da PL e possui valor objetivo igual a w = 12. 32 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional (vi) Repetimos os itens (iii) e (iv). Agora só faz sentido aumentar x2 pois é a única cujo valor na função objetivo é positivo, ou seja, a única que poderia contribuir para melhorar a solução final. Calculando os valores dos coeficientes bi /Ai2 : Restrição 1: b1 /A12 = 4 1/2 = 8. Restrição 2: b2 /A22 = 4 3/2 = 8/3. Restrição 3: b3 /A32 = 1 1/2 = 2. O mı́nimo dentre os valores é 2, correspondente à restrição 3. Assim, a nova solução será
x 3 2 0 1 0 , cujo novo valor na função
objetivo atualizada
é w = 13. A variável x5 deixa de ser básica, T T assim, xB = x1 x2 x4 e xN = x3 x5. (vii) Repetimos o item (v) - faça o passo a passo como exercı́cio!
max 0 0 −1 0 −1 x = w − 13     1 0 1 0 −1 3 sujeito a  0 1 −1 0 2 x = 2   0 0 1 1 −3 1 x ≥ 0. Note que a solução básica
x= 3 2 0 1 0 satisfaz as equações da PL e possui valor objetivo igual a w = 13. (viii) Repetimos (ou tentamos repetir) os itens (iii) e (iv). Note entretanto que não existe variável que faça sentido aumentar em x tendo em vista o atual formato do vetor c. (ix) A PL está resolvida. Este foi o método Simplex. Exercı́cio 26. Refaça este exemplo, mas na primeira vez que chegar ao passo (iii), comece au- mentando x2 , deixando x1 fixo. Daı́ pra frente, faça como achar melhor. Note que no final, o valor de ótimo precisa ser o mesmo. Algumas observações: (i) Este método sempre resolverá uma PL. Nós entretanto não demonstraremos isto formalmente agora. (ii) Geometricamente, cada iteração dos pontos (ii)-(iv) correspondem a: achar uma solução na região viável, caminhar até uma face aumentando o valor da função objetivo, depois achar o melhor caminho para caminhar pela face até a próxima face. (iii) Na próxima seção, veremos uma maneira esquemática de repetirmos esses passos. 33 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Exercı́cio 27. Considere o sistema de equações abaixo     1 1 0 2 1 1 1 2 0 2 2 0 0 −2 1 x = 2 1 2 1 5 4 3 3 6 e os vetores
(a) 1 1 0 0 0 0 0
(b) 2 −1 2 0 1 0 0
(c) 1 0 1 0 1 0 0
(d) 0 0 1 1 0 0 0
(e) 0 1/2 0 0 1/2 0 1 Para cada um deles, decida se é uma solução básica ou não, e se for, se é viável (≥ 0) ou não. Exercı́cio 28. Considere a PL em FPI abaixo.
max 1 −2 0 1 3 x     1 −1 2 −1 0 1 sujeito a x= 2 0 1 −1 1 −1 x ≥ 0. Construa PL equivalente em forma canônica para as bases formadas pelas colunas {1, 4} e pelas colunas {3, 5}. A solução básica correspondente é viável? Decida se esta PL é viável ou inviável. Se for viável, construa uma PL equivalente em forma canônica cuja solução básica associada seja viável. Se for inviável, apresente um certificado. 2.4 PLs ilimitadas Vamos ver agora como é possı́vel, através do método Simplex, identificar que uma PL é ilimitada. Considere o exemplo abaixo:
max 5 3 0 0 1 ·x     −2 4 1 0 1 1 sujeito a x= −3 7 0 1 1 3 x ≥ 0. Esta PL está na forma canônica para as colunas 3 e 4. Vamos aplicar o método Simplex do Exemplo (9) para resolvê-la. Escolhemos a coluna com ci mais positivo. No caso, a 1a coluna com c1 = 5. Note porém que os dois coeficientes são negativos. Isso significa que x1 pode crescer infinitamente, pois para todo valor positivo de x1 é possı́vel aumentar também os valores de x3 e x4 para que a PL continue positiva. Isto implica que sempre que todos os coeficientes da coluna correspondente de uma variável candidata forem não-positivos (ou sejam negativos ou zero), a PL é ilimitada. 34 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional 2.4.1 Como encontrar um certificado de ilimitada O certificado de ilimitada é, no caso, um vetor d = (d1 , d2 , d3 , d4 , d5 ) que satisfaz três condições: Ad = 0, d ≥ 0 e cT d > 0. A partir da PL em forma canônica, podemos facilmente encontra-lo. Note que para que Ad = 0, temos que: −2d1 + 4d2 + d3 + d5 = 0 −3d1 + 7d2 + d4 + d5 = 0 Vamos começar colocando d1 = 1, isto é, na coluna que entraria como variável básica, colocamos o valor 1. As variáveis básicas originais são x3 e x4. Vamos fixar d2 = d5 = 0 e colocar valores em d
3 e d4 que garantem as igualdades acima: no caso, d3 = 2 e d4 = 3. Temos que d = 1 0 2 3 0. Note que este vetor satisfaz as três condições: Ad = 0, d ≥ 0 e cT d = 5 > 0, sendo um certificado de ilimitada. Como a PL está na forma canônica, apenas cT d = c1 neste caso pois os demais cj = 0 para todas as outras variáveis básicas cujo valor dj > 0. Encontrar o certificado nestas condições é fácil: estando a PL em forma canônica, e encontrando um ci positivo cuja coluna Ai correspondente é toda não-positiva, então para encontrar o certificado d basta colocar di = 1, dj = 0 para toda variável j não básica e dk = −ali para toda variável básica k com valor 1 na restrição l correspondente. Observação:
Note que se toda a coluna correspondente a x1 fosse 0, com c1 > 0, d = 1 0 0 0 0 seria um certificado válido. 2.5 Formalização do Simplex Nesta seção, formalizamos a execução do algoritmo Simplex através de notação matricial. Consi- dere o problema em FPI: max w = cT x sujeito a Ax = b x ≥ 0. Se A possui mais colunas que linhas, o problema possui infinitas soluções (desde que seja viável). Se A possui mais linhas que colunhas, muito provavelmente não possui solução. Vamos assumir, a partir daqui, que A possui m linhas e n columnas, com m ≤ n. Vamos então nos concentrar nas soluções básicas, que, como já sabemos, nos levará à solução
quadrada m × m de A nos fornece, potencialmente, uma ótima caso ela exista. Cada submatriz n solução básica. Sabemos que há m possı́veis submatrizes quadradas. Seja B o conjunto de colunas escolhido. Vamos então separar os componentes da PL em uma parte básica B, e uma parte não básica N. A = ( A B | AN )   xB x= xN
c = cTB | cTN T 35 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional Vamos assumir que AB é não-singular. Podemos reescrever a PL como:   T T
xB max w = cB | cN xN     xB bB sujeito a ( AB | AN ) = xN bN x ≥ 0. Ou simplesmente: max w = cTB xB + cTN xN sujeito a AB xB + AN xN = b x ≥ 0, Ao fazer xN = 0, obtemos uma solução básica ao resolver AB xB = b. Como AB é não-singular, podemos multiplicar a inversa dos dois lados para obter: xB = A−1 B b Vamos assumir que xB ≥ 0, ou seja, a solução básica é viável em relação à PL original. O próximo passo é descobrir se a solução é ótima. Note que: AB x B + AN x N =b A−1 −1 B AB x B + A B AN x N = A−1 B b xB + A−1B AN x N = A−1 B b xB = A−1 −1 B b − A B AN x N A manipulação algébrica acima por enquanto não trouxe nada de novo, já que xN = 0! Mas vamos ver como as coisas ficam quando substituı́mos a expressão acima na função objetivo: w = cTB xB + cN xN w = cTB (A−1 −1 B b − AB AN xN ) + cN xN w = cTB A−1 T −1 B b − cB AB AN xN + cN xN w = cTB A−1 T −1 B b + (cN − cB AB AN )xN Note que w = cTB A−1 B b é o valor da função objetivo. Vamos agora nos concentrar na expressão (cN − cTB A−1 B AN )xN. Considere uma variável não- básica j ∈ N , para a qual temos (cj − cTB A−1 B A j )x j - nesta expressão, cj é o coeficiente de j na função objetivo e Aj é a j-ésima coluna de A. A expressão: zj = cj − cTB A−1 B Aj é chamada de custo reduzido de j. Se seu valor é positivo, então poderı́amos aumentar o valor de xj , que atualmente é zero, aumentando consequentemente o valor da função objetivo w. Se os custos reduzidos de todas variáveis não-básicas j é negativo, então não há nada que podemos fazer para melhorar a função objetivo, e encontramos a solução ótima. Vamos assumir então que o custo reduzido de j é positivo, ou seja, podemos melhorar a solução ao colocá-la na base. A questão é: o quanto podemos colocar em xj ? Sejam xi , i ∈ B, as variáveis 36 Gabriel Coutinho e Cristiano Arbex Valle DCC035 - Pesquisa Operacional básicas, todas ≥ 0. Ao aumentar xj , vamos reduzir proporcionalmente todas xi. Lembre-se que nenhum xi pode virar negativo, assim temos um limite natural para o quanto xj pode aumentar. Conforme acima, temos que: xB = A−1 −1 B b − AB A N x N Especificamente para as variáveis i básica e j não-básica, temos que: xi = A−1 −1 B b i − AB Aj x j Como nenhum dos xi pode ficar negativo, o máximo que podemos aumentar xj é: A−1 B bi xj = min −1 i∈B A Aj B Seja B uma base ótima. Ao final, temos que: w = cTB xB é o valor ótimo da função objetivo xB = A−1B b são os valores ótimos das variáveis básicas xN =0 são os valores das variáveis não-básicas zN = cN − cTB A−1 B AN são os custos reduzidos, nenhum positivo, das variáveis não-básicas Mais pra frente, depois que estivermos resolvendo o Simplex em tableaus, voltaremos a esta notação. 2.6 O Simplex via tableaus Nesta seção mostraremos como aplicar o Simplex de modo mais enxuto. Considere a PL
max w = 2 3 0 0 0 x     1 1 1 0 0 6 sujeito a   2 1 0 1 0 x = 10  −1 1 0 0 1 4 x ≥ 0. onde a variável w representa o valor objetivo. Note que esta PL já se encontra em forma canônica para a base viável formada pelas colunas 3, 4 e 5. Vamos reescrever as equações e a função objetivo como um sistema:     w   1 −2 −3 0 0 0  x   1  0 0 1  