Programacao Linear e Pesquisa Operacional - Introducao e Metodos de Resolucao

1º Aula Programação Linaer e suas Formas de Resolução Objetivos de aprendizagem Ao término desta aula vocês serão capazes de entender o que é a pesquisa operacional conhecer a metodologia utilizada na pesquisa operacional entender o que é modelagem entender o que é programação linear entender o que é e como usar o método SIMPLEX aprender a usar o Solver do Excel para resolver problemas de PO Prezadosas alunosas Nesta primeira aula estudaremos um pouco da história da pesquisa operacional e também vamos entender como a pesquisa operacional pode ser útil em nosso dia a dia apresentando dois casos de modelagem usando pesquisa operacional Também estudaremos as formas de resolução de problemas de Pesquisa Operacional Bons estudos 6 Pesquisa Operacional Seções de estudo 1 Origem e defi nições da pesquisa operacional 2 Programação Linear equações e solução gráfi ca 3 Modelo de PL em forma de equação simplex 4 Solução com computador com o excel solver 1 Origem e defi nições da pesquisa operacional O termo pesquisa operacional PO é uma tradução para o português brasileiro da expressão inglesa operational research As primeiras atividades formais de PO foram iniciadas na Inglaterra durante a segunda guerra mundial quando um grupo de cientistas britânicos decidiu tomar decisões com base científi ca sobre a melhor utilização de material de guerra mais especifi camente aos radares O termo pesquisa operacional é atribuído ao superintendente da estação APRowe que em 1938 coordenava equipes para examinar a efi ciência de técnicas de operações advindas de experimentos com intercepção de radar Em 1941 foi inaugurada a Seção de Pesquisa Operacional do Comando da Força Aérea de Combate ARENALES et al 2015 Em 1952 foi fundada a sociedade científi ca americana de pesquisa operacional ORSA Operations Research Society of America e em 1953 foi fundada a sociedade inglesa de pesquisa operacional ORS Operational Research Society e a americana de ciências e administração TIMS The Institute of Manegement Sciences Em 1995 a ORSA e TIMS foram agregadas pelo INFORMS Institute for Operational Research and the Manegement Sciences que se mantém até os dias atuais ARENALES et al 2015 No Brasil a pesquisa operacional teve sua primeira aparição formal em 1968 no primeiro simpósio brasileiro de pesquisa operacional realizado no ITA Instituto Tecnológico de Aeronáutica em São José dos Campos No ano seguinte em 1969 foi fundada a SOBRAPO Sociedade Brasileira de Pesquisa Operacional que publica o periódico científi co Pesquisa Operacional aqui no Brasil Tratandose de defi nição a SOBRAPO se refere a Pesquisa Operacional como a área de conhecimento que estuda desenvolve e aplica métodos analíticos avançados para auxiliar na tomada de melhores decisões nas mais diversas áreas de atuação humana Já a INFORMS defi ne PO como uma disciplina profi ssional que trata de aplicação da tecnologia da informação para a tomada de decisão informada ARENALES et al 2015 12 Solução do Modelo de Po Em PO não temos uma única técnica para resolver todos os modelos matemáticos que podem surgir na prática onde a técnica mais utilizada é a programação linear Ela é aplicada a modelos cujas funções objetivo e restrição são lineares Outras técnicas são a programação inteira na qual as variáveis assumem valores inteiros a programação dinâmica na qual o modelo original pode ser decomposto em subproblemas mais fáceis de tratar a otimização em redes na qual o problema pode ser modelado como uma rede e a programação não linear na qual as funções do modelo são não lineares Estas são apenas algumas das muitas ferramentas de PO disponíveis TAHA 2008 13 Arte da modelagem De acordo com Taha 2008 os modelos hipotéticos são representações verdadeiras de situações reais Essa é uma ocorrência rara em PO porque de modo geral a maioria das aplicações envolve graus variados de aproximações Abstraímos o mundo real considerado da situação real concentrandonos nas variáveis dominantes que controlam o comportamento do sistema real O modelo expressa de maneira tratável as funções matemáticas que representam o comportamento do mundo real considerado Geralmente a atividade de uma equipe de PO envolve as seguintes fases Identifi cação do problema e coleta de dados Formulação de um modelo matemático modelagem matemática Obtenção da solução com base no modelo Teste do modelo e avaliação da solução Implantação e acompanhamento da solução Devese salientar que tais fases não são distintas superpondose e interagindo entre si na tentativa de se obter uma melhor identifi cação entre o modelo e o real 2 Programação Linear equações e solução gráfi ca Os problemas de Programação Linear PL buscam a distribuição efi ciente de recursos limitados para atender a um determinado objetivo em geral maximizar lucros ou minimizar custos Em se tratando de PL esse objetivo é expresso através de uma função linear denominada de Função Objetivo 22 Modelo de Pl de duas variáveis Embora seja raro existirem problemas de duas variáveis na prática seu tratamento proporciona uma forma didática de apresentar os conceitos de resolução de problemas envolvendo PO Na prática geralmente encontramos problemas com muitas variáveis Porém aqui iremos apresentar dois exemplos de problemas de duas variáveis para facilitar o entendimento um de maximização e um de minimização 23 Resolvendo um problema de maximização Para exemplifi car como resolvemos um problema de maximização usaremos um exemplo fi ctício adaptado de 7 Taha 2008 de uma fábrica de tintas que busca maximizar seus lucros 231 A fábrica de tintas Aquarela Tintas A Aquarela Tintas produz tintas para interiores e exteriores com base em duas matériasprimas M1 e M2 A Tabela 1 apresenta os dados básicos do problema Tabela 1 Produção de tintas da Aquarela Tintas Tonelada de matéria prima por tonelada de Disponi bilidade máxima diária ton Tinta para exteriores Tinta para interiores Matériaprima M1 6 4 24 Matériaprima M2 1 2 6 Lucro por tonelada R 100000 5 4 Fonte adaptado de Taha 2008 Uma pesquisa de mercado indica que a demanda diária de tintas para interiores não pode ultrapassar a de tintas para exteriores por mais de 1 tonelada Além disso a demanda máxima diária de tinta para interiores é 2 t A Aquarela Tintas quer determinar o mix ótimo o melhor de produtos de tintas para interiores e exteriores que maximize o lucro total diário De acordo com Taha 2008 o modelo de PL como qualquer modelo de PO tem três componentes básicos 1 Variáveis de decisão que procuramos determinar 2 Objetivo meta que precisamos otimizar maximizar ou minimizar 3 Restrições que a solução deve satisfazer A definição adequada das variáveis de decisão é uma primeira etapa essencial no desenvolvimento do modelo Uma vez concluída a tarefa de construir a função objetivo e as restrições tornase mais direta Para o problema da Aquarela Tintas precisamos determinar as quantidades diárias a produzir de tintas para exteriores e interiores Assim as variáveis do modelo são definidas como x1 toneladas de tinta para exteriores produzidas diariamente x2 toneladas de tinta para interiores produzidas diariamente Para construir a função objetivo observe que a empresa quer maximizar isto é aumentar o máximo possível o lucro total diário para as duas tintas Dado que os lucros por tonelada de tintas para exteriores e interiores são de 5 e 4 mil dólares respectivamente decorre que Lucro total da tinta para exteriores 5x1 mil dólares Lucro total da tinta para interiores 4x2 mil dólares Representando o lucro total diário em milhares de dólares por z o objetivo da empresa é Maximizar z 5x1 4x2 Em seguida construímos as restrições que limitam a utilização da matériaprima e a demanda do produto As restrições sobre a matériaprima são expressas em palavras como Utilização de uma matériaprima para ambas as tintas Máxima disponibilidade de matériaprima A utilização por dia da matériaprima M1 é de 6 t por tonelada de tinta para exteriores e de 4 t por tonelada de tinta para interiores Assim Utilização da matériaprima M1 para tinta para exteriores 6x1 tdia Utilização da matériaprima M1 para tinta para interiores 4x2 tdia Então temos que Utilização da matériaprima M1 para ambas as tintas 6x1 4x2 tdia De maneira semelhante Utilização da matériaprima M2 para ambas as tintas 1x1 2x2 tdia Como as disponibilidades diárias das matériasprimas M1 e M2 estão limitadas a 24 e 6 ton respectivamente as restrições relacionadas são dadas como 6x1 4x2 24 matériaprima M1 x1 2x2 6 matériaprima M2 A primeira restrição relacionada à demanda estipula que o excesso da produção diária de tinta para interiores em relação à de tinta para exteriores x2 x1 não deve ultrapassar 1 ton o que poderia ser traduzido para x2 x1 1 limite de mercado A segunda restrição relacionada à demanda estipula que a demanda diária máxima de tinta para interiores está limitada a 2 ton o que é traduzido para x2 2 limite de demanda Ainda de acordo com Taha 2008 uma restrição implícita é que as variáveis x1 e x2 não podem assumir valores negativos As restrições de nãonegatividade x1 0 x2 0 são as responsáveis por esse requisito O modelo completo da Aquarela Tintas é Maximizar z 5x1 4x2 sujeito a 1 6x1 4x2 24 2 x1 2x2 6 3 x1 x2 1 4 x2 2 5 x1 0 6 x2 0 Quaisquer valores de x1 e x2 que satisfaçam todas as cinco restrições constituem uma solução viável Caso contrário a solução é inviável Por exemplo a solução x1 3 td e x2 1 td é viávelporque não viola nenhuma das restrições entre elas as de nãonegatividade Para verificar esse resultado substitua x1 3 x2 1 no lado esquerdo de cada restrição Na restrição 1 temos 6x1 4x2 6 x 3 4 x 1 22 que é menor do que o lado direito da restrição 24 As restrições 2 a 6 resultarão em conclusões semelhantes Verifique Por outro lado a solução x1 4 8 Pesquisa Operacional e x2 1 é inviável porque não satisfaz a restrição 1 ou seja 6 x 4 4 x 1 28 que é maior do que o lado direito 24 24 Solução Gráfi ca em PL Para exemplifi car como resolvemos um problema de PL com solução gráfi ca usaremos o exemplo da fábrica de tintas Aquarela Tintas De acordo com Taha 2008 o procedimento para resolução com gráfi co inclui duas etapas 1 Determinação da região de soluções viáveis 2 Determinação da solução ótima entre todo da região de soluções dos pontos viáveis O procedimento utiliza dois exemplos para mostrar como a maximização e a minimização das funções objetivo são tratadas Vamos então resolver o modelo da Aquarela Tintas do Exemplo 241 Etapa 1 determinação da região de soluções viáveis Seguindo Taha 2008 em primeiro lugar levamos em conta as restrições de nãonegatividade x1 0 e x2 0 Na Figura 1 o eixo horizontal x1 e o eixo vertical x2 representam as variáveis tinta para exteriores e tinta para interiores respectivamente Assim a não negatividade das variáveis restringe a área da região de soluções ao primeiro quadrante que se encontra acima do eixo x1 e à direita do eixo x2 Figura 1 Representação gráfi ca do problema da fábrica de tintas Fonte Taha 2008 Para levar em conta as quatro restrições restantes em primeiro lugar substitua cada desigualdade por uma equação e depois represente em gráfi co a linha reta resultante localizando dois pontos distintos nela Por exemplo após substituir 6x1 4x2 24 pela linha reta 6x1 4x2 24 podemos determinar dois pontos distintos primeiro ao fazer x1 O para obter x2 244 6 e após ao fazer x2 O para obter x1 246 4 Assim a reta passa pelos dois pontos 0 6 e 4 0 como mostra a reta 1 na Figura 1 Ainda de acordo com Taha 2008 na sequência considere o efeito da desigualdade Tudo que ela faz é dividir o plano x1 x2 em dois meiosespaços um de cada lado da reta representada no gráfi co Só uma dessas duas metades satisfaz a desigualdade Para determinar o lado correto tome 0 0 como um ponto de referência Se ele satisfi zer a desigualdade o lado no qual ele se encontra é a meiaregião viável caso contrário o viável é o outro lado A utilização do ponto de referência 00 é ilustrada com a restrição 6x1 4x2 24 Como 6 x 0 4 x 0 0 é menor do que 24 a meiaregião que representa a desigualdade inclui a origem como é mostrado pela seta na Figura 1 Em termos de cálculo é conveniente selecionar 0 0 como o ponto de referência a menos que por acaso a reta passe pela origem quando então qualquer outro ponto pode ser usado Por exemplo se usarmos o ponto de referência 6 0 o lado esquerdo da primeira restrição é 6 x 6 4 x 0 36 que é maior do que seu lado direito 24 o que signifi ca que o lado no qual 60 se encontra não é viável para a desigualdade 6x1 4x2 5 24 A conclusão é consistente com a baseada no ponto de referência 00 A aplicação do procedimento do ponto de referência a todas as restrições do modelo produz as restrições mostradas na Figura 1 A região de soluções viáveis do problema representa a área do primeiro quadrante na qual todas as restrições são satisfeitas simultaneamente Na Figura 1 qualquer ponto que esteja dentro ou sobre o contorno da área ABCDEF é parte da região de soluções viáveis Todos os pontos fora dessa área são inviáveis TAHA 2008 242 Etapa 2 determinação da solução ótimo Seguindo o raciocínio exposto por Taha 2008 vemos que a região viável da Figura 1 é delimitada pelos segmentos de reta que unem os pontos A B C D E e F Qualquer ponto dentro ou sobre o contorno do espaço ABCDEF é viável Como a região viável ABCDEF consiste em um número infi nito de pontos precisamos de um procedimento sistemático para identifi car a solução ótima A determinação da solução ótima requer identifi car a direção na qual a função lucro z 5x1 4x2 aumenta lembrese de que estamos maximizando z Podemos fazer isso designando valores crescentes arbitrários a z Por exemplo usar z 10 e z 15 equivaleria a representar em gráfi co as duas retas 5x1 4x2 10 e 5x1 4x2 15 Assim a direção do aumento de z é a mostrada na Figura 2 A solução ótima ocorre em C que é o ponto na região de soluções além do qual qualquer aumento adicional levará z para fora dos contornos de ABCDEF Os valores de x1 e x2 relacionados com o ponto ótimo C são determinados pela resolução das equações relacionadas com as retas 1 e 2 isto é 6x1 4x2 24 x1 2x2 6 A solução é x1 3 e x 2 15com z 5 x 3 4 x 15 21 Isso representa um mix de produto diário de 3 t de tinta para exteriores e 15 t de tinta para interiores O lucro diário associado é 21000 Figura 2 solução ótima do exemplo da fábrica de tintas 9 Fonte Taha 2008 De acordo com Taha 2008 uma característica importante da solução ótima de PL e que ela sempre está relacionada com um ponto extremo da região de soluções em que duas retas se cruzam Isso é válido até se por acaso a função objetivo for paralela a uma restrição Por exemplo se a função objetivo for z 6x1 4x2 que é paralela à restrição 1 sempre podemos dizer que a solução ótima ocorre no ponto extremo B ou no ponto extremo C Na verdade qualquer ponto sobre o segmento de reta BC será uma alternativa mas a observação importante aqui é que o segmento de reta BC é totalmente definido pelos pontos extremos B e C A observação de que a solução ótima em PL está sempre associada a um ponto extremo significa que a solução ótima pode ser encontrada pela simples enumeração de todos os pontos extremos como mostra a Tabela 2 Tabela 2 Pontos e solução ótima do problema da fábrica de tintas Ponto extremo x1 x2 z A 00 0 B 40 20 C 315 21 Ótimo D 22 18 E 12 13 F 01 4 Fonte adaptado de Taha 2008 À medida que o número de restrições e variáveis aumenta o número de pontos extremos também aumenta e o procedimento de enumeração proposto tornase menos viável em termos de cálculo Não obstante a ideia mostra que do ponto de vista da determinação da solução ótima em PL o espaço de solução ABCDEF com seu número infinito de soluções pode de fato ser substituído por um número finito de soluções ou seja os pontos extremos A B C D E e F TAHA 2008 25 Solução de um modelo de minimização Para exemplificar o problema de minimização usaremos um exemplo adaptado de Taha 2008 de modelo de dieta aqui apresentado como diminuir os custos de ração de uma fazenda mas atendendo às restrições nutricionais da dieta da ração A Fazenda São João usa no mínimo 800 lb de ração especial por dia Essa ração especial é uma mistura de milho e soja com as composições elencadas na Tabela 3 Tabela 3 Composição da ração na Fazenda São João lb por lb de ração Ração Proteína Fibra Custo R lb Milho 009 002 03 Soja 06 006 09 Fonte adaptado de Taha 2008 Os requisitos nutricionais da ração especial são de no mínimo 30 de proteína e de no máximo 5 de fibra A Fazenda São João quer determinar a mistura que gera a ração de mínimo custo diário Como a ração consiste em milho e preparado de soja as variáveis de decisão do modelo são definidas como x1 lb de milho na mistura diária x2 lb de preparado de soja na mistura diária A função objetivo procura minimizar o custo total diário da ração e por isso é expressa como Minimizar z 03x1 09x2 As restrições do modelo refletem a quantidade diária necessária e os requisitos nutricionais Como a Fazenda São João precisa de no mínimo 800 lb de ração por dia a restrição associada pode ser expressa como x1 x2 800 Quanto à restrição ao requisito nutricional de proteína a quantidade de proteína presente em x1 lb de milho e x2 lb de preparado de soja é 009x1 06x2 lb Essa quantidade deve ser igual a no mínimo 30 do total da mistura das rações x1 x2 lb isto é 009x1 06x2 03x1 x2 De modo semelhante o requisito de no máximo 5 de libras é expresso por 002x1 006x2 005x1 x2 Podemos simplificar as restrições passando os termos em x1 e x2 para o lado esquerdo de cada desigualdade deixando somente uma constante no lado direito Assim o modelo completo se torna Minimizar z 03x1 09x2 Sujeito a x1 x2 800 021x1 030x2 0 003x1 001x2 0 X1 x2 0 10 Pesquisa Operacional Figura 3 Solução gráfi ca para o modelo da dieta Fonte Taha 2008 A Figura 3 apresenta a solução gráfi ca do modelo Diferente das restrições do modelo da Aquarela Tintas a segunda e a terceira restrições passam pela origem Para representar em gráfi co as retas associadas precisamos de um ponto adicional que pode ser obtido com a designação de um valor a uma das variáveis e depois com a resolução para a outra variável Por exemplo na segunda restrição x1 200 fará 021 x 200 03x2 0 ou x2 140 Isso signifi ca que a linha reta 021x1 03x2 0 passa por 0 0 e 200 140 Observe também que 00 não pode ser usado como um ponto de referência para as restrições 2 e 3 porque ambas as retas passam pela origem Em vez disso podese usar um outro ponto por exemplo 1000 ou 0 100 para essa fi nalidade Solução Como o presente modelo busca a minimização da função objetivo precisamos reduzir o valor de Z o máximo possível na direção mostrada na Figura 3 A solução ótima e o extremo das duas retas x1 x2 800 e 021x1 03x2 0 o que dá como resultado x1 47059 lb e x2 32941 lb O custo da ração e z 03 x 47059 09 x 32942 43765 por dia 3 Modelo de PL em forma de equação simplex Nem sempre os problemas de PL são de fácil solução através de gráfi cos e o dia a dia do engenheiro não permite fi car à mercê desse fato Para resolver essa limitação foi padronizado uma metodologia matemática para resolução dos problemas de programação linear chamado de método simplex De acordo com Taha 2008 o desenvolvimento dos cálculos do método simplex é facilitado pela imposição de novos requisitos às restrições do problema 1 Todas as restrições com exceção da não negatividade das variáveis são equações cujos lados direitos são não negativos 2 Todas as variáveis são não negativas Aqui a fi nalidade primordial desses dois requisitos e padronizar e tornar mais efi cientes os cálculos do método simplex É importante saber que todos os pacotes comerciais aceitam diretamente restrições de desigualdade Lados direitos não negativos e variáveis irrestritas Qualquer precondicionamento necessário do modelo é realizado internamente no software antes de o método simplex resolver o problema 32 Conversão de desigualdades em equações com o lado direito não negativo De acordo com Taha 2008 em restrições o lado direito pode ser considerado como a representação do limite imposto a disponibilidade de um recurso caso em que o lado esquerdo representaria a utilização desse recurso limitado pelas atividades variáveis do modelo Assim a diferença entre o lado direito e o lado esquerdo da restrição resultaria na quantidade do recurso não utilizada ou folga Para converter uma desigualdade é em uma equação uma variável de folga não negativa é adicionada ao lado esquerdo da restrição Por exemplo no modelo da Fazenda São João a restrição associada com a utilização da matéria prima M1 é dada como 6x1 4x2 24 Defi nase S1 como a folga ou a quantidade não utilizada de M1 a restrição pode ser convertida na seguinte equação 6x1 4x2 51 24 S1 0 De forma semelhante uma restrição estabelece um limite inferior para as atividades do modelo de PL de modo que a quantidade pela qual o lado esquerdo excede o limite mínimo representa uma sobra TAHA 2008 Conseguese a conversão de em com a subtração de uma variável de sobra não negativa do lado esquerdo da desigualdade Por exemplo no modelo da dieta a restrição que representa os requisitos mínimos da ração é x1 x2 800 Defi nase S1 como a variável de sobra a restrição pode ser convertida na seguinte equação x1 x2 S1 800 S1 0 O único requisito restante é que o lado direito da equação resultante seja não negativo A condição sempre pode ser satisfeita multiplicandose ambos os lados da equação resultante por 1 onde necessário Por exemplo a restrição x1 x2 3 é equivalente a equação x1 x2 S1 3 S1 O Agora multiplicando ambos os lados por 1 teremos um lado direito não negativo como desejado isto é x1 x2 s1 3 33 Detalhes de cálculo do algoritmo simplex Esta seção apresenta os detalhes de cálculo de uma iteração do método simplex incluindo as regras para determinar as variáveis que entram na base e que saem da base bem como as regras para interromper os cálculos quando a solução ótima tiver sido alcançada A explicação se dará por meio de um exemplo numérico Usamos o modelo da Fazenda São João para explicar os detalhes do método simplex O problema é expresso na forma de equações como Maximizar z 5x1 4x2 0s1 0s2 0s3 0s4 11 sujeito a 6x1 4x2 s1 24 matériaprima M1 x1 2x2 s2 6 matériaprima M2 x1 x2 s3 1 limite de mercado x2 s4 2 limite da demanda x1x2s1s2s3s4 0 As variáveis s1 s2 s3 e s4 são as folgas associadas às respectivas restrições Em seguida escrevemos a função objetivo como z 5x1 4x2 0 Dessa maneira a tabela simplex inicial pode ser representada da seguinte maneira Base z x1 x2 s1 s2 s3 s4 Solução z 1 5 4 0 0 0 0 0 linha z s1 0 6 4 1 0 0 0 24 linha s1 s2 0 1 2 0 1 0 0 6 linha s2 s3 0 1 1 0 0 1 0 1 linha s3 s4 0 0 1 0 0 0 1 2 linha s4 Fonte Taha 2008 O arranjo da tabela especifica o conjunto de variáveis básicas e não básicas bem como apresenta a solução associada com a iteração inicial As iterações simplex começam na origem x1 x2 00 cujos conjuntos associados de variáveis não básicas e básicas são definidos como Variáveis zero não básicas x1 x2 Variáveis básicas s1s2s3s4 Substituindo as variáveis não básicas x1 x2 00 a seguinte solução está imediatamente disponível sem nenhum cálculo z 0 s124 s2 6 s3 1 s4 2 Essa informação é mostrada na tabela pela listagem das variáveis básicas na coluna da extrema esquerda Base e seus valores aparecem na coluna da extrema direita Solução Na verdade a tabela define o ponto extremo atual especificando suas variáveis básicas e seus valores bem como o valor correspondente da função objetivo z Lembrese de que as variáveis não básicas as que não aparecem na lista da coluna Base sempre são iguais a zero A solução inicial é ótima Não pois a função objetivo z 5x1 4x2 mostra que um aumento em x1 ou x2 ou em ambas acima de seus valores zero atuais melhorará o valor de z O projeto do método simplex exige o aumento de uma variável por vez sendo que a variável selecionada será aquela que tiver a maior taxa de melhoria em z O valor de z aumentará em 5 para cada unidade de aumento de x1 e em 4 para cada unidade de aumento em x2 Isso significa que a taxa de melhoria no valor de z é 5 para x1 e 4 para x2 Assim optamos por aumentar x1 a variável que tem a maior taxa de melhoria Essa regra é denominada condição de otimalidade A mecânica da determinação da variável que sai com base na tabela simplex exige o cálculo das razões não negativas entre o lado direito das equações coluna Solução e o coeficiente de restrição correspondente da variável que entra x1 como mostra a tabela Entrando Base x1 Solução Razão s1 6 24 x1 266 mínimo s2 1 6 x1 61 6 s3 1 1 x1 11 1 ignorar s4 0 2 x1 20 ignorar Conclusão x1 entra e s1 sai A razão mínima não negativa identifica automaticamente a variável s1 como a variável que sai da base e designa a variável que entra na base x1 o valor de 4 Segundo Taha 2008 o processo de troca é baseado nas operações de GaussJordan que identifica a coluna da variável que entra na base como a coluna do pivô e a linha da variável que sai como a linha do pivô A interseção da coluna do pivô com a linha do pivô é denominada elemento pivô A tabela seguinte é uma reafirmação da tabela do começo com sua coluna e linhas dos pivôs em destaque Entra Base z x1 x2 s1 s2 s3 s4 Solução Z 1 5 4 0 0 0 0 0 Sai s1 0 6 4 1 0 0 0 24 Linha pivô s2 0 1 2 0 1 0 0 6 s3 0 1 1 0 0 1 0 1 s4 0 0 1 0 0 0 1 2 Coluna Pivô Os cálculos por GaussJordan necessários para produzir a nova solução básica são de dois tipos 1 Linha do pivô b Substituir variável que sai da base na coluna Base pela variável que entra na base c Nova linha do pivô Linha do pivô atual Elemento pivô 2 Todas as outras linhas incluindo z Nova linha Linha atual Seu coeficiente de coluna do pivô xNova linha do pivô Base z x1 x2 s1 s2 s3 s4 Solução Z 1 0 23 56 0 0 0 20 x1 0 1 23 16 0 0 0 4 s2 0 0 43 16 1 0 0 2 s3 0 0 53 16 0 1 0 5 12 Pesquisa Operacional s4 0 0 1 0 0 0 1 2 Observe que a nova tabela tem as mesmas propriedades da tabela inicial Quando igualamos as novas variáveis não básicas x2 e s1 a zero a coluna Solução dá automaticamente a nova solução básica x1 4 s2 2 s3 5 s4 2 Esse condicionamento da tabela é o resultado da aplicação das operações de linha por GaussJordan O novo valor da função objetivo correspondente e z 20 que é consistente com Novo z Velho z Novo valor x1 x Seu coefi ciente na função objetivo 0 4 x 5 20 Na última tabela a condição de otimalidade mostra que x2 é a variável que deve entrar na base A condição de viabilidade produz o seguinte Entrando Base x2 Solução Razão x1 23 4 x2 223 6 s2 43 2 x2 243 15 mínimo s3 53 5 x2 553 3 s4 1 2 x2 21 2 Assim s2 sai da solução básica e o novo valor de x2 é 15 o que da z 20 1 21 Substituindo s2 na coluna Base por x2 que entra as seguintes operações de fi la por GaussJordan são aplicadas Base z x1 x2 s1 s2 s3 s4 Solução Z 1 0 0 34 12 0 0 21 x1 0 1 0 14 12 0 0 3 x2 0 0 1 18 34 0 0 32 s3 0 0 0 38 54 1 0 52 s4 0 0 0 18 34 0 1 12 Com base na condição de otimalidade nenhum dos coefi cientes da linha z associados com as variáveis não básicas s1 e sz é negativo Assim essa tabela simplex é ótima A solução ótima pode ser lida na tabela simplex da seguinte maneira os valores ótimos das variáveis na coluna Base são dados na coluna Solução do lado direito da tabela e podem ser interpretados como demonstrado na tabela a seguir Variável de decisão Valor ótimo Recomendação x1 3 Produzir 3 ton diárias de tintas para exterio res x2 32 Produzir 15 ton diária de tintas para interio res z 21 Lucro diário é de 2100000 4 Solução com computador com o excel solver Na prática quando vamos resolver um problema de programação linear geralmente encontramos muitas variáveis e restrições inviabilizando a resolução pelo método gráfi co Nesses casos o modo viável para resolução é a utilização de computador Existem vários softwares que auxiliam a resolução de problemas de programação linear dentre eles podemos citar Excel Solver a linguagem AMPL o WhatsBest e o Lingo A seguir usaremos o exemplo da fábrica de tintas para demonstrar a forma de solução usando o Solver A planilha do excel deve contar os dados de entrada como função objetivo e as restrições Veja na Figura 4 abaixo um exemplo de como montar essa planilha de entrada de dados Figura 4 exemplo de como montar essa planilha de entrada de dados Fonte adaptado de Taha 2008 Essa planilha é apenas um modelo demonstrando como inserir os dados A Tabela 4 mostra as funções da programação linear e seu posicionamento adequado nas células Tabela 4 funções a serem inseridas no modelo apresentado na Figura 4 Expressão algébrica Fórmula na planilha Inserida na célula Objetivo z 5x1 4x2 C5C16D16D5 E5 Restrição 1 6x1 4x2 C9C16D16D9 E9 Restrição 2 x1 2x2 C10C16D16D10 E10 Restrição 3 x1 x2 C11C16D16D11 E11 Restrição 4 0x1 x2 C12C16D16D12 E12 Fonte adaptado de Taha 2008 Agora com a planilha montada vamos utilizar o solver do excel para achar a solução ótima Para adicionar o solver em seu excel primeiramente clique em Arquivo e em seguida Opções conforme a Figura 5 Na sequência vá em Suplementos e adicione o Solver conforme a Figura 6 13 Figura 5 Opções do Excel Fonte o autor Figura 6 Suplementos do Excel Fonte o autor Após o solver devidamente adicionado em seu Excel clique na aba dados e em seguida abra a opção solver conforme a Figura 7 Figura 7 Solver no Excel Fonte o autor 14 Pesquisa Operacional Conforme mostra a Figura 8 aberta a janela Parâmetros do Solver primeiramente clique a opção Defi nir objetivo e selecione a célula E5 que é a função objetivo a ser maximizada Em seguida clique na opção Max de maximização e por último clique na opção Alterando Células Variáveis e selecione as células C16 e D16 instruindo assim o Solver a alterar os valores dessas células para achar o ponto ótimo de z No método de solução opte p ela opção LP Simplex Figura 8 janela de parâmetros do solver Fonte o autor Após isso temos que inserir as restrições na janela do solver Fazemos isso clicando no botão adicionar Ao abrir o popup do botão adicionar faremos conforme a Figura 6 selecionando as células C16 e D16 selecionando o sinal e no campo restrição digitaremos o valor 0 zero Dessa forma informaremos que os valores que o solver deve nos passar tem que ser não negativos Na sequência devemos clicar novamente no botão adicionar para inserir as restrições do problema No campo referência de célula devemos selecionar de uma só vez as células E9 E10 E11 e E12 clicando e arrastando O sinal é o mesmo da planilha e no campo restrição devemos selecionar os valores da coluna limite G9 G10 G11 e G12 Figura 9 programando restrições do solver Fonte o autor Inseridas as restrições basta clicar em ok e em seguida no botão resolver O Excel irá automaticamente preencher os valores das células C16 e D16 com a solução ótima que maximize o valor da célula E5 Ao chegar ao fi nal da primeira aula vamos recordar o que aprendemos Retomando a aula 1 Origem e defi nições da pesquisa operacional Nesta seção iniciamos vendo a origem e defi nições de pesquisa operacional PO Vimos que teve suas inspirações na Segunda Guerra Mundial e depois foi se desvinculando aos poucos da origem militar Na sequência falamos um pouco sobre modelagem e vimos exemplos de problemas reais de aplicação de PO 2 Programação Linear equações e solução gráfi ca Na segunda seção da aula falamos da Programação Linear PL que é a espinha dorsal da maioria dos problemas de PO Vimos exemplos de maximização e minimização além de uma técnica de resolução muito útil principalmente no mercado de trabalho que é a resolução gráfi ca 3 Modelo de Pl em forma de equação simplex Na terceira parte da aula vimos uma forma mais elaborada de resolução de problemas de PL que é o algoritmo SIMPLEX que é muito utilizado academicamente e também em criação de softwares por ser mais conceitual 4 Solução com computador com o excel solver Finalmente na quarta parte da aula vimos a solução computacional através do Excel que é mais comum de ser utilizada no dia a dia de um engenheiro em seu local de trabalho ARENALES M ARMENTANO V A MORABITO R YANASSE H H Pesquisa operacional Rio de Janeiro CampusElsevier 2015 HILLIER FS e Lieberman GJ Introdução à Pesquisa Operacional 8ª edição São Paulo McGrawHill 2006 LACHTERMACHER G Pesquisa operacional na tomada de decisões 5ª edição São Paulo Prentice Hall 2016 TAHA H A Pesquisa Operacional 8ª edição São Paulo Pearson 2008 Vale a pena ler Vale a pena 15 Disponível em httpswwwinformsorg Acesso em 09 dez 2019 Disponível em httpswwwsobrapoorgbr Acesso em 09 dez 2019 Vale a pena acessar Minhas anotações