Metodo Simplex e Solver para Programacao Linear - Guia Completo

DESCRIÇÃO O método simplex para a solução de modelos de programação linear e a utilização do solver na solução de problemas de programação linear PROPÓSITO Dominar a solução de problemas de programação linear seja por meio do método simplex ou pela utilização de softwares permitirá que você aplique a técnica de modelagem no processo de decisão de problemas complexos de diversas origens em especial em sua atuação profissional PREPARAÇÃO Para o conteúdo deste tema são necessários uma calculadora e um software editor de planilhas eletrônicas com o addin do solver habilitado OBJETIVOS MÓDULO 1 Empregar o método simplex para a solução de problemas de programação linear MÓDULO 2 Aplicar o solver para solução de problemas de programação linear INTRODUÇÃO A modelagem matemática nos permite representar de forma simplificada um problema complexo por meio de linguagem matemática Com isso conseguimos analisar diferentes cenários de forma mais rápida e barata do que se a situação fosse avaliada na realidade auxiliandonos assim no processo de tomada de decisão No contexto da programação linear que se aplica por exemplo no planejamento de redes logísticas há métodos como o método gráfico que se restringem à solução de problemas com apenas duas ou no máximo três variáveis de decisão Como solucionar então problemas mais complexos com maior número de variáveis de decisão Este é o assunto a ser tratado neste tema A seguir abordaremos o método simplex para a solução de problemas de programação linear e aprenderemos a utilizar o solver do Excel para a solução desse tipo de problema MÓDULO 1 Empregar o método simplex para a solução de problemas de programação linear APRESENTAÇÃO DO TEMA O vídeo aborda o método simplex e sua importância para a resolução de problemas O MÉTODO SIMPLEX PARA A SOLUÇÃO DE MODELOS DE PROGRAMAÇÃO LINEAR Podemos resolver de forma simples problemas de programação linear com duas variáveis de decisão por meio do método gráfico Entretanto são poucos os problemas de programação linear no mundo real que envolvem apenas duas variáveis de decisão de modo que a aplicação do método gráfico é bastante limitada ENTÃO COMO FAZEMOS PARA SOLUCIONAR PROBLEMAS MAIS COMPLEXOS COM UM MAIOR NÚMERO DE VARIÁVEIS DE DECISÃO Existe uma série de técnicas matemáticas para resolver problemas de programação linear com qualquer número de variáveis sem a necessidade de visualizar em gráficos as regiões viáveis Dentre tais técnicas destacase o algoritmo simplex que foi o primeiro método desenvolvido para resolver problemas de programação linear O algoritmo simplex foi desenvolvido por George B Dantzig em 1947 enquanto trabalhava como consultor em matemática para o controle da Força Aérea norteamericana O método simplex é específico para a solução de problemas de otimização linear equações ou inequações lineares Tratase de um algoritmo eficiente que se baseia na solução sucessiva de sistemas de equações indeterminados em que sistemas adjacentes são avaliados de forma iterativa sendo assim adaptável ao cálculo computacional Na época os computadores estavam começando a surgir e a resolução desse tipo de problema se tornava importante na prática O simplex é considerado uma das grandes contribuições à programação matemática Antes de estudarmos o algoritmo simplex é importante entendermos o conceito do simplex e recordarmos alguns pontos sobre a solução de problemas de programação linear com duas variáveis de decisão por meio do método gráfico O QUE É UM SIMPLEX Um simplex é um polígono convexo ou seja com propriedade especial uma reta que passe por quaisquer dois pontos pertencentes a um simplex deve estar contida inteiramente dentro do simplex Logo na figura a seguir observase que o polígono representado em a não é convexo enquanto o ilustrado em b é um simplex Polígono não convexo e polígono simplex As restrições de um problema de programação linear sempre definem hiperespaços convexos Esta é a premissa do algoritmo simplex e de boa parte da teoria de otimização convexa Assim o espaço de soluções de um problema de programação linear ou seja a área formada pela interseção das restrições do problema é uma forma geométrica simplex MÉTODO GRÁFICO Para encontrar a solução ótima pelo método gráfico precisamos seguir os seguintes passos Desenhe as retas correspondentes às restrições do problema e encontre o espaço de soluções Desenhe o vetor z função objetivo Desenhe linhas ortogonais ao vetor z Essas são as linhas de isocusto isto é são as retas que têm o mesmo valor de z Calcule o valor de z no ponto ótimo ou seja a linha de isocusto com maior z que ainda pertence ao espaço de soluções Em um caso bidimensional o espaço de soluções viáveis é um plano e a função objetivo é representada por um vetor Assim por meio do método gráfico buscamos a reta x2 z ax1 perpendicular ao vetor da função objetivo com o maior ou menor z possível dentro do espaço de soluções Como o espaço de soluções é simplex a reta x2 z ax1 para z ótimo que corta o plano obrigatoriamente corta as retas de restrições Ainda como nos pontos de interseção vértices temos mudança de inclinação retas diferentes garantese que a solução ótima se dá na interseção entre retas de restrições nos vértices de modo que o algoritmo simplex analisa apenas os pontos de interseção do espaço de soluções Na verdade esta foi a grande ideia de Dantzig para o desenvolvimento do algoritmo simplex dado que a solução ótima está em um vértice do espaço de soluções viáveis por que não percorrêlos em busca da melhor solução possível MÉTODO SIMPLEX Conforme verificamos a chave do algoritmo simplex está no formato da região limitada pelas restrições Portanto apesar de ser um procedimento algébrico os conceitos subjacentes ao método simplex são geométricos O simplex é um algoritmo iterativo que se utiliza de um ferramental baseado em álgebra linear para a resolução sucessiva de sistemas de equações embora as restrições de problemas de programação matemática sejam tipicamente inequações Desse modo a primeira etapa do método simplex consiste em converter as restrições de desigualdade em restrições de igualdade equivalente O algoritmo simplex só pode ser rodado se o problema estiver escrito na forma canônica que é a forma de se representar programas matemáticos por meio de equações Para isso precisamos criar as chamadas variáveis de folga ou de excesso VARIÁVEIS DE FOLGA F Exemplo forma canônica X₁ 10 X₁ F₁ 10 Atenção Para visualização completa da equação utilize a rolagem horizontal f₁ Variável de folga Assim se X₁ 8 então teríamos que a variável de folga f₁ seria igual a 2 Se X₁ 3 então teríamos que a variável de folga f₁ seria igual a 7 VARIÁVEIS DE EXCESSO E Exemplo forma canônica X₁ 10 X₁ E₁ 10 Atenção Para visualização completa da equação utilize a rolagem horizontal e₁ Variável de excesso Assim se X₁ 12 então teríamos que a variável de excesso e1 seria igual a 2 Se X₁ 15 então teríamos que a variável de excesso e₁ seria igual a 5 Veja o caso do problema da Fitwear apresentado a seguir Será que conseguimos escrevêlo em sua forma canônica Caso Fitwear SA A Fitwear SA é uma confecção de roupas esportivas tendo uma linha fitness feminina na qual produz roupas de ginástica exclusivas para mulheres como tops e calças de lycra Cada top de ginástica é vendido por R8000 e utiliza R2000 de matériaprima como tecido e alinhamentos e R3200 de mão de obra Trinta minutos de corte e 15 minutos de costura são demandados para a confecção de um top de ginástica Cada calça de ginástica é vendida por R12000 e utiliza R3500 de matériaprima como tecido e alinhamentos e R4000 de mão de obra Quinze minutos de corte e 30 minutos de costura são demandados para a confecção de uma calça de ginástica A Fitwear só pode contar com 100 horas de corte por semana e 160 horas de costura A confecção não tem problemas no fornecimento de matériasprimas de modo que seu suprimento pode ser considerado ilimitado bem como a demanda semanal de seus produtos A Fitwear deseja planejar sua produção semanal de modo a maximizar seus lucros Quando modelamos o problema consideramos as seguintes variáveis de decisão X₁ Número de tops de ginástica confeccionados a cada semana X₂ Número de calças de ginástica confeccionadas a cada semana Assim chegamos à seguinte formulação matemática em sua formapadrão MÁX Z 28 X₁ 40X₂ SUJEITO A FORMAPADRÃO 05X₁ 025X₂ 100 RESTRIÇÃO DE HORAS DE CORTE 025X₁ 05X₂ 160 RESTRIÇÃO DE HORAS DE COSTURA X₁ X₂ 0 RESTRIÇÃO DE NÃO NEGATIVIDADE DAS VARIÁVEIS DE DECISÃO Atenção Para visualização completa da equação utilize a rolagem horizontal Observe que tanto a restrição referente às horas de corte quanto a restrição referente às horas de costura são do tipo Logo precisaremos de duas variáveis de folga f₁ e f₂ para passar o problema para sua forma canônica MÁX Z 28 X₁ 40X₂ Atenção Para visualização completa da equação utilize a rolagem horizontal Sujeito à forma canônica 05X₁ 025X₂ F₁ 100 025X₁ 05X₂ F₂ 160 X₁ X₂ 0 Atenção Para visualização completa da equação utilize a rolagem horizontal Uma vez adicionadas as variáveis de folga o problema da Fitwear é dito no formato canônico e pronto para ser resolvido pelo método simplex Para resolver o problema de programação linear o algoritmo simplex se baseia na solução sucessiva de sistemas de equações utilizandose do conceito de variáveis básicas e não básicas VARIÁVEIS BÁSICAS São aquelas para as quais o sistema de equações é resolvido VARIÁVEIS NÃO BÁSICAS São aquelas que são zeradas para que o sistema de equações apresente uma solução ou seja para que o número de equações seja igual ao número de variáveis permitindo assim a solução do sistema de equações No problema da Fitwear por exemplo temos quatro variáveis x1 x2 f1 e f2 e apenas duas equações restrições Entretanto para que um sistema de equações lineares seja resolvido é necessário que o número de equações seja igual ao número de variáveis De tal modo para resolver o problema da Fitwear devemos considerar duas variáveis como nulas não básicas e resolver o problema para outras duas variáveis básicas e assim fazemos por iterações sucessivas até que encontremos o par de variáveis básicas que nos dá a solução ótima Em linhas gerais o algoritmo simplex parte de uma solução viável do sistema de equações que constituem as restrições do problema de programação linear solução essa normalmente extrema vértice A partir dessa solução inicial o algoritmo adota um critério de escolhas para encontrar novos e melhores vértices da envoltória convexa do problema e outro critério para determinar se o vértice escolhido solução básica é ou não um vértice ótimo GOLDBARG LUNA 2005 Assim pelo método simplex devemos 1 Transformar o modelo em sua forma canônica ou seja transformar o sistema de inequações em sistema de equações Determinar uma solução básica inicial que será iterativamente melhorada 2 3 Realizar o teste da otimalidade ou seja verificar se a iteração atual é ótima ou se outras variáveis não base ou seja que estão zeradas devem entrar na base pois têm potencial para contribuir para melhorar a solução Realizar o teste da mínima razão que determinará qual variável básica deve sair da base ou seja verificará quais das variáveis devem passar a ser nulas para que a nova variável entre na base 4 5 Calcular a nova solução básica e voltar ao passo 3 Arenales et al 2007 descrevem o algoritmo simplex em duas fases A fase 1 traz o procedimento de como determinar uma solução inicial enquanto o método simplex propriamente dito é apresentado na fase 2 PASSO 1 Escreva o problema na forma canônica cT x Ax b sendo A uma matriz mxn x 0 PASSO 2 Determine inicialmente uma partição básica factível A B N ou seja com dois vetores de índices básicos e não básicos B1 B2 Bm e N1 N2 Nn m Faça iteração1 Fase 2 início da iteração simplex PASSO 1 CÁLCULO DA SOLUÇÃO BÁSICA xb B¹b equivalentemente resolva o sistema Bxb b xn 0 PASSO 2 CÁLCULO DOS CUSTOS RELATIVOS vetor multiplicador simplex λT cBT B¹ EQUIVALENTEMENTE RESOLVA O SISTEMA BT λ cB Atenção Para visualização completa da equação utilize a rolagem horizontal custos relativos cNJ cNJ λT ANJ J 1 2 N M Atenção Para visualização completa da equação utilize a rolagem horizontal cNJ MÍNIMO cNJ J 1 2 N M A VARIÁVEL XNK ENTRA NA BASE Atenção Para visualização completa da equação utilize a rolagem horizontal PASSO 3 TESTE DA OTIMALIDADE Se cNJ 0 ENTÃO PARE SOLUÇÃO NA ITERAÇÃO ATUAL É ÓTIMA Atenção Para visualização completa da equação utilize a rolagem horizontal PASSO 4 CÁLCULO DA DIREÇÃO SIMPLEX Y B¹ ANK EQUIVALENTEMENTE RESOLVA O SISTEMA BY ANK Atenção Para visualização completa da equação utilize a rolagem horizontal PASSO 5 DETERMINAÇÃO DO PASSO E VARIÁVEL A SAIR DA BASE Se y 0 então pare problema não tem solução ótima finita fx Caso contrário determine a variável a sair da base pela razão mínima Ê xBL yL MÍNIMO xBI yI TAL QUE YI 0 YI 0 I 1 2 M A VARIÁVEL XBL SAI DA BASE Atenção Para visualização completa da equação utilize a rolagem horizontal PASSO 6 ATUALIZAÇÃO NOVA VARIÁVEL BÁSICA TROQUE A LÉSIMA COLUNA DE B PELA KÉSIMA COLUNA DE N Matriz básica nova B AB1 ABLK ANK ABL 1 ABM Atenção Para visualização completa da equação utilize a rolagem horizontal Matriz não básica nova N AN1 ANK1 ABL ANK 1 ANNM Atenção Para visualização completa da equação utilize a rolagem horizontal Iteração iteração 1 Retorne ao passo 1 fim da iteração simplex Na forma de algoritmo como apresentado por Arenales et al 2007 o método simplex pode parecer difícil mas vamos entender o que Dantzig propôs por meio de um exemplo Caso da empresa Glass Co A empresa Glass Co que possui três fábricas produz janelas e portas de vidro As esquadrias e ferragens em aço são feitas na fábrica 1 as esquadrias de madeira são produzidas na fábrica 2 e a fábrica 3 produz o vidro e monta os produtos A direção da empresa decidiu modernizar sua linha de produtos e propôs o lançamento de dois novos produtos Produto 1 porta de vidro de 25m com esquadria de alumínio Produto 2 janela adornada com esquadria de madeira 12m x 18m O produto 1 requer capacidade produtiva das fábricas 1 e 3 O produto 2 precisa das fábricas 2 e 3 A divisão de marketing concluiu que a empresa poderia vender tanto quanto fosse possível produzir desses produtos por essas fábricas Porém ambos os produtos competem por capacidade produtiva da fábrica 3 não estando claro qual mix dos dois seria mais lucrativo Determine quais devem ser as taxas de produção para maximizar o lucro total sujeitas às restrições impostas pela capacidade produtiva Fábrica Tempo de produção por lote em horas Produtos 1 2 Tempo de produção disponível por semana horas 1 1 0 4 2 0 2 12 3 3 2 18 Lucro por lote R300000 R500000 Atenção Para visualização completa da tabela utilize a rolagem horizontal Produção empresa Glass Co Extraída de Hillier e Lieberman 2013 pág 21 Inicialmente devemos escrever o modelo matemático para o problema da Glass Co seguindo os passos do procedimento para construção do modelo de programação linear Identificação das variáveis de decisão Identificação da função objetivo Identificação do conjunto de restrições A seguir vamos seguir cada um dos passos indicados IDENTIFICAÇÃO DAS VARIÁVEIS DE DECISÃO No caso da Glass Co a empresa deve decidir os produtos a serem fabricados Logo a definição da variável de decisão seria xi quantidade de produto i confeccionada Assim temos x1 Quantidade de lotes produtos 1 fabricados x2 Quantidade de lotes produtos 2 fabricados IDENTIFICAÇÃO DA FUNÇÃO OBJETIVO No caso da Glass Co a empresa deseja maximizar seu lucro total Determine quais devem ser as taxas de produção para maximizar o lucro total Para cada lote de portas de vidro de 25m com esquadria de alumínio produto 1 vendido a empresa lucra R3000000 enquanto o lucro de venda de cada lote de janela adornada com esquadria de madeira 12m x 18m produto 2 equivale a R500000 Logo o lucro total é igual a 3000x1 5000x2 de modo que a função objetivo para o problema é MAX Z 3X1 5X2 Atenção Para visualização completa da equação utilize a rolagem horizontal IDENTIFICAÇÃO DO CONJUNTO DE RESTRIÇÕES No caso do problema da Glass Co foram consideradas ilimitadas a demanda por seus produtos e a oferta de matériaprima de modo que não entram como restrições no modelo matemático Porém há restrições relacionadas ao tempo de produção disponível por semana em cada fábrica Fábrica Tempo de produção por lote em horas Produtos 1 2 Tempo de produção disponível por semana horas 1 1 0 4 2 0 2 12 3 3 2 18 Atenção Para visualização completa da tabela utilize a rolagem horizontal Produção empresa Glass Co Extraída de Hillier e Lieberman 2013 pág 21 Há ainda a restrição de não negatividade das variáveis de decisão uma vez que não se pode produzir um número negativo de portas ou janelas Logo a restrição 4 é dada por x1 x2 0 Logo temos as seguintes restrições x1 4 2x2 12 x2 6 3x1 2x2 18 Enfim temos o seguinte modelo matemático para o problema da Glass Co MAX Z 3X1 5X2 SA x1 4 2X2 12 3X1 2X2 18 x1 x2 0 x1 x2 0 Atenção Para visualização completa da equação utilize a rolagem horizontal MAS QUAL É O MIX DE PRODUÇÃO QUE NOS DÁ A SOLUÇÃO ÓTIMA O primeiro passo do algoritmo simplex é transformar o modelo em seu formato canônico Passando para o formato canônico temos Como as taxas de crescimento são positivas 3 e 5 e este é um problema de maximização concluímos que a solução inicial 0 0 4 12 18 não é a solução ótima Já sabemos que a solução básica inicial não é ótima então uma variável não básica x₁ ou x₂ deve entrar na base Porém devemos aumentar x₁ ou x₂ Para determinar isso devemos verificar a direção de deslocamento Observe que para cada unidade que aumentarmos x₁ temos uma taxa de crescimento em Z de 3 Ao mesmo tempo para cada unidade que aumentarmos x1 temos uma taxa de crescimento em Z de 5 Sendo 5 3 devemos optar por x₂ para crescer Logo x₂ é a variável básica que entra Entretanto para que x₂ passe a ser uma variável básica uma das variáveisbase da solução inicial f₁ f₂ e f₃ precisa sair da base Porém como determinar qual delas Para essa etapa devemos ter em mente que ao aumentar x₂ elevase Z Contudo não podemos sair do espaço de soluções ou seja da região de soluções viáveis Assim devemos aumentar x₂ mantendo a variável não básica x₁ 0 e respeitando que todas as variáveis sejam não negativas X₁ 0 VARIÁVEL NÃO BÁSICA X₁ F₁ 4 F₁ 4 2X₂ F₂ 12 F₂ 12 2X₂ 3X₁ 2X₂ F₃ 18 F₃ 18 2X₂ Atenção Para visualização completa da equação utilize a rolagem horizontal Como x₁ x₂ f₁ f₂ f₃ 0 Teste da mínima razão F₁ 4 NÃO IMPLICA EM LIMITE SUPERIOR EM X₂ F₂ 12 2X₂ 0 X₂ 122 6 MÍNIMO F₃ 18 2X₂ 0 X₂ 182 9 MAX Z 3X₁ 5X₂ SA X₁ F₁ 4 RESTRIÇÃO 1 2X₂ F₂ 12 RESTRIÇÃO 2 3X₁ 2X₂ F₃ 18 RESTRIÇÃO 3 X₁ X₂ F₁ F₂ F₃ 0 Atenção Para visualização completa da equação utilize a rolagem horizontal Em seguida devemos escolher uma solução básica inicial Observe que temos três equações no sistema de equações e cinco variáveis Dessa forma devemos ter três variáveisbase e duas não base O modo mais fácil de resolver esta etapa é escolher as variáveis x₁ e x₂ como variáveis não básicas uma vez que essa opção elimina o trabalho necessário para encontrar a solução quando as variáveis básicas são as variáveis de folga ou excesso f₁ f₂ e f₃ Nesse caso se x₁ 0 e x₂ 0 z seria igual a zero também enquanto f₁ 4 f₂ 12 e f₃ 18 Função objetivo Z 3x₁ 5x₂ logo para a solução inicial de x₁ 0 e x₂ 0 temos Z 0 Atenção Para visualização completa da equação utilize a rolagem horizontal Restrição 1 x₁ f₁ 4 0 f₁ 4 f₁ 4 Atenção Para visualização completa da equação utilize a rolagem horizontal Restrição 2 2x₂ f₂ 12 0 f₂ 12 f₂ 12 Atenção Para visualização completa da equação utilize a rolagem horizontal Restrição 3 3x₁ 2x₂ f₃ 18 0 0 f₃ 18 f₂ 18 Atenção Para visualização completa da equação utilize a rolagem horizontal Portanto temos a solução inicial de 0 0 4 12 18 Passamos então para o teste da otimalidade Como Z 3x₁ 5x₂ verificamos que o coeficiente de cada variável não básica x₁ e x₂ é positivo Logo o aumento de x₁ ou x₂ implica em aumento da taxa de crescimento em Z Atenção Para visualização completa da equação utilize a rolagem horizontal Verificamos então que x2 passa a receber o valor de 6 enquanto f2 se torna uma variável não base e nula Assim deduzimos intuitivamente o teste da mínima razão O objetivo do teste da mínima razão é determinar qual variável básica cai a zero primeiro à medida que a variável básica que entra é aumentada Podemos descartar imediatamente a variável básica em qualquer equação cujo coeficiente da variável básica que entra é zero ou negativo já que uma variável básica não decresceria à medida que a variável básica que entra aumentasse No caso do problema da Glass Co ao aumentarmos o valor de x2 de 0 a 6 temos mudanças na solução SOLUÇÃO INICIAL x₁ 0 x₂ 0 F₁ 4 F₂ 12 F₃ 18 NOVA SOLUÇÃO x₁ 0 x₂ 6 F₁ F₂ 0 F₃ Temos que x₂ é igual a 6 e x₁ continua sendo zero Portanto temos que Z 3x₁ 5x₂ 3 0 5 6 30 Devemos determinar então os valores de f₁ f₂ e f₃ X₁ F₁ 4 0 F₁ 4 F₁ 4 2X₂ F₂ 12 2 6 F₂ 12 F₂ 0 3X₁ 2X₂ F₃ 18 3 0 2 6 F₃ 18 F₃ 6 A nova solução é 0 6 4 0 6 e Z 30 Atenção Para visualização completa da equação utilize a rolagem horizontal Então devemos verificar se essa solução é ótima ou não por meio do teste de otimalidade Sendo Z 3x₁ 5x₂ verificamos que x₁ tem o coeficiente positivo 3 de modo que aumentar x₁ implica em aumentar Z Portanto a solução atual não é ótima e devemos realizar nova iteração analisando a entrada de x₁ como variável básica Dessa forma devemos realizar o teste da mínima razão para verificar qual variável básica deve se tornar nula saindo então da base para permitir a entrada de x₁ Z 3X1 2 5X2 30 X1 F1 4 2X2 F2 12 3X1 2X2 F3 18 Teste da mínima razão F1 4 X1 0 X1 41 X1 4 F2 12 2X2 0 NENHUM LIMITE SUPERIOR EM X1 F3 6 3X1 0 X 63 X1 2 MÍNIMA RAZÃO Atenção Para visualização completa da equação utilize a rolagem horizontal Logo f3 sai da base para x1 entrar com o valor igual a 2 Porém ao aumentarmos o valor de x1 de 0 a 2 temos mudanças na solução SOLUÇÃO INICIAL x1 0 x2 6 F1 4 F2 0 F3 18 NOVA SOLUÇÃO x1 2 x2 6 F2 0 F3 Temos que x2 é igual a 6 e x1 equivale a 2 Logo temos que Z 3x1 5x2 3 2 5 6 36 Devemos determinar então os valores de f1 f2 e f3 X1 F1 4 2 F1 4 F1 2 2X2 F2 12 2 6 F2 12 F2 0 3X1 2X2 F3 18 3 2 2 6 F3 18 F3 0 Atenção Para visualização completa da equação utilize a rolagem horizontal Portanto concluímos que x1 substitui f3 como variável básica sendo a nova solução igual a 2 6 2 0 0 e Z 36 As variáveis não básicas agora são f2 e f3 Verificamos que aumentar as atuais variáveis não básicas não implica em aumento em Z o que garante que esta é a solução ótima MÉTODO SIMPLEX EM SUA FORMA TABULAR Aprendemos até agora a forma algébrica do simplex que é a melhor para aprender a lógica por trás do algoritmo Porém não é a forma mais conveniente para realizar cálculos necessários As operações realizadas no método simplex podem ser organizadas em tabelas chamadas tabelas simplex Essa organização é a mais indicada para quando estivermos resolvendo um problema de programação linear manualmente Considere um problema de otimização linear MINIMIZAR F X CX AX B X 0 Atenção Para visualização completa da equação utilize a rolagem horizontal F2 0 F3 Temos que x2 é igual a 6 e x1 equivale a 2 Logo temos que Z 3x1 5x2 3 2 5 6 36 Devemos determinar então os valores de f1 f2 e f3 X1 F1 4 2 F1 4 F1 2 2X2 F2 12 2 6 F2 12 F2 0 3X1 2X2 F3 18 3 2 2 6 F3 18 F3 0 Atenção Para visualização completa da equação utilize a rolagem horizontal Portanto concluímos que x1 substitui f3 como variável básica sendo a nova solução igual a 2 6 2 0 0 e Z 36 As variáveis não básicas agora são f2 e f3 Verificamos que aumentar as atuais variáveis não básicas não implica em aumento em Z o que garante que esta é a solução ótima MÉTODO SIMPLEX EM SUA FORMA TABULAR Aprendemos até agora a forma algébrica do simplex que é a melhor para aprender a lógica por trás do algoritmo Porém não é a forma mais conveniente para realizar cálculos necessários As operações realizadas no método simplex podem ser organizadas em tabelas chamadas tabelas simplex Essa organização é a mais indicada para quando estivermos resolvendo um problema de programação linear manualmente Considere um problema de otimização linear MINIMIZAR F X CX AX B X 0 Atenção Para visualização completa da equação utilize a rolagem horizontal Nesse problema temos as variáveis x1 x2 xn Os coeficientes da função objetivo são c1 c2 cn Os coeficientes das restrições são a1 a2 an e b Arenales et al 2007 descrevem as operações realizadas em cada iteração do algoritmo simplex em tabelas em duas fases Fase 1 Determine a tabela simplex inicial A matriz dos coeficientes contém uma matriz identidade mxm m é o número de equações e o vetor independente b 0 A função objetivo é escrita em termos das variáveis não básicas isto é os coeficientes das variáveis básicas são nulos Faça a iteração 0 Fase 2 Determine o menor dos custos relativos ck mínimo cj para toda variável não básica Se ck 0 então pare a solução básica na iteração é ótima Se não a variável xk entra na base Se aik 0 i 1 m então f e o problema não tem solução ótima finita Nesse caso pare Se não determine biaik mínimo tal que aik 0 i 1 m a variável básica da linha I sai da base Atualize a tabela simplex pivoteamento do elemento I k A variável xk passa a ser a variável básica na linha I Faça a iteração iteração 1 e retorne ao passo 1 Na forma de algoritmo como apresentado por Arenales et al 2007 o método simplex tabular pode parecer difícil mas vamos entendêlo resolvendo o exemplo da Glass Co cujo modelo em formato canônico é apresentado a seguir MAX Z 3X1 5X2 SA X1 F1 4 RESTRIÇÃO 1 2X2 F2 12 RESTRIÇÃO 2 3X1 2X2 F3 18 RESTRIÇÃO 3 X1 X2 F1 F2 F3 0 Atenção Para visualização completa da equação utilize a rolagem horizontal Inicialmente vamos definir o formato da tabela de maneira a facilitar sua compreensão A tabela simplex tem do lado esquerdo as variáveis básicas e do lado direito as constantes das equações No meio da tabela ficam todos os coeficientes das restrições e da função objetivo Por padronização colocaremos na primeira linha zero a equação que representa a função objetivo conforme apresentado na figura a seguir zj cj cB B1 aj cj z cB b xB yj B1 aj b B1 b Tabela simplex Uma escolha viável para a primeira base para o problema da Glass Co seria f1 f2 f3 pois facilitaria o preenchimento da tabela simplex inicial dado que B I e B1 I MAX Z 3X1 5X2 X1 F1 4 2X2 F2 12 3X1 2X2 F3 18 A3 A4 A5 A1 A2 A B N 1 0 0 1 0 0 1 0 0 2 0 0 1 3 2 F1 F2 F3 X1 X2 B 1 0 0 0 1 0 0 0 1 B1 1 0 0 0 1 0 0 0 1 Atenção Para visualização completa da equação utilize a rolagem horizontal Quando as variáveis de folga constituem a primeira base na primeira linha da tabela simplex apenas escrevemos o negativo dos coeficientes de custo das variáveis não básicas Como zj cj representa a potencial melhoria no valor de z da função objetivo representada pela jésima variável as variáveis atualmente básicas devem receber o valor zero pois já se encontram na base Assim a primeira linha da tabela simplex para o exemplo da Glass Co é x1 x2 f1 f2 f3 RHS Z 3 5 0 0 0 Z0 Atenção Para visualização completa da tabela utilize a rolagem horizontal O valor atual de z z0 para esta primeira tabela com as variáveis básicas sendo f1 f2 f3 seria igual a zero pois Z 3x1 5x2 e x1 x2 0 Assim atualizando a tabela temse x1 x2 f1 f2 f3 RHS Z 3 5 0 0 0 0 Atenção Para visualização completa da tabela utilize a rolagem horizontal Em seguida devemse escrever as linhas que compõem as restrições da tabela simplex conforme indicado na figura a seguir zj cj cB B1 aj cj z cB b xB yj B1 aj b B1 b Restrições da tabela simplex Para cada variável do problema devese determinar yj Como as variáveis de folga foram escolhidas como a primeira base temos B I e B1 I Logo temos yj aj de modo que as linhas que compõem as restrições no tableau são copiadas diretamente do problema Ainda as variáveis atualmente na base f1 f2 f3 são identificadas à esquerda da tabela simplex como pode ser identificado na figura a seguir Max Z 3x1 5x2 s a Variáveis básicas Preenchendo a tabela simplex para o problema da Glass Co Observase por meio da figura anterior que os únicos elementos faltantes estão do lado direito da tabela simplex e correspondem à fórmula B B1 B IB B Atenção Para visualização completa da equação utilize a rolagem horizontal Desse modo para a tabela inicial basta copiar os valores de b no lado direito da tabela conforme apresentado na figura a seguir Max Z 3x1 5x2 s a x1 f1 4 2x2 f2 12 3x1 2x2 f1 18 Tabela simplex inicial para o problema da Glass Co Uma vez preenchida a tabela inicial devemos identificar as variáveis candidatas a entrar na base na primeira linha da tabela Para isso devemos analisar os valores dos coeficientes de cada variável apresentados na segunda linha da tabela simplex levando em consideração o tipo de problema apresentado maximização ou minimização Problema de maximização Em um problema de maximização a variável cujo coeficiente é negativo e apresenta o maior valor absoluto é aquela que entrará na base Problema de minimização Em um problema de minimização a variável a entrar na base será a que tiver o maior valor positivo Por meio da figura da Tabela simplex inicial para o problema da Glass Co observamos que a variável a entrar na base no problema da Glass Co é x2 uma vez que tanto xx quanto x2 têm valores negativos na segunda linha da tabela sendo 5 3 Depois de identificarmos a variável que entra na base é preciso determinar a variável básica que deve dar lugar para que x2 entre na base Para isso aplicamos o teste da mínima razão conforme indicado na figura a seguir Observase que o menor valor é 6 de modo que a variável a sair da base é f2 Teste da mínima razão para o problema da Glass Co Para completar a iteração do simplex devemos então proceder com as operações elementares que utilizam a linha que contém o elemento de pivot de modo que a coluna x2 da variável entrante assuma a configuração da coluna f2 variável que sai da base Observe na figura a seguir que a linha pivot é a quarta linha da tabela atual linha do f2 no lado esquerdo da tabela e que os valores para as colunas x2 e f2 não coincidem de modo que é necessário executar a operação elementar Portanto sendo a linha 3 a tabela 3 após a operação elementar temse que a operação que transformará 2 em 1 é 3 32 Operações com a linha pivot para o problema da Glass Co Observe na segunda tabela da figura anterior que para a coluna x2 assumir a configuração anterior da coluna f2 é preciso ainda realizar operações elementares nas linhas 1 e 4 da tabela simplex Assim para a linha 4 é preciso que 4 4 2 3 enquanto para a linha 1 devemos fazer 1 1 5 3 conforme indicado na próxima figura DICA Para a linha 2 não é preciso realizar nenhuma operação uma vez que os valores para as colunas x2 e f2 já são coincidentes Renata Albergaria de Mello Bandeira Verifique na figura anterior que a coluna x1 ainda apresenta um valor negativo na segunda linha da tabela simplex de modo que esta variável deve entrar na base sendo necessária então mais uma iteração Logo fazse o teste da mínima razão conforme indicado na figura a seguir sendo verificado que a variável a sair da base para que x1 entre é f3 Portanto são necessárias as operações elementares para que a coluna x1 receba os valores da coluna f3 Teste da mínima razão para o problema da Glass Co 2a iteração Observase na figura do Teste da mínima razão para o problema da Glass Co 2a iteração que a quinta linha 4 da tabela a pivot Assim para que a coluna x1 receba os valores da coluna f3 a primeira operação elementar a ser feita é 4 43 tal como apresentado na figura a seguir Primeira operação elementar linha 4 para o problema da Glass Co 2a iteração Para a coluna x1 assumir a configuração anterior da coluna f3 ainda é preciso realizar operações elementares nas linhas 1 e 2 da tabela simplex Assim para a linha 2 é preciso que 2 2 4 enquanto para a linha 1 devemos fazer 1 1 3 4 conforme indicado na próxima figura DICA Para a linha 3 não é preciso realizar nenhuma operação uma vez que os valores para as colunas x1 e f3 já são coincidentes nesta linha Operações com a linha pivot para o problema da Glass Co 2a iteração ATENÇÃO Verifique na figura anterior que não há mais valores negativos na segunda linha da tabela simplex 1 de modo que não há mais variáveis para entrar na base Logo concluímos que a solução ótima para o problema da Glass Co é x1 2 x2 6 e z 36 tal como apresentado na seção método simplex quando resolvemos este mesmo problema por meio do método simplex em sua forma analítica VERIFICANDO O APRENDIZADO MÓDULO 2 Aplicar o solver para solução de problemas de programação linear UTILIZAÇÃO DO SOLVER PARA SOLUÇÃO DE PROBLEMAS DE PROGRAMAÇÃO LINEAR No módulo 1 aprendemos a resolver problemas de programação linear por meio do método simplex tanto o analítico quanto o tabular Aplicamos essas técnicas em alguns exemplos de modo a entender a lógica do algoritmo Porém pudemos verificar que são muitos os cálculos que precisam ser feitos para resolvermos problemas de programação linear manualmente e apenas um erro em uma conta nos levaria a um resultado errado Contudo felizmente existem diversos softwares de computador que podem ser utilizados para nos auxiliar a encontrar a solução ótima para problemas de programação matemática por exemplo LINDO CPLEX AIMMS GAMS MATHPRO Usando o software de computador adequado podemos resolver facilmente quaisquer problemas de programação linear As técnicas para a solução de problemas de programação linear são inclusive desenvolvidas por meio de pacotes de planilhas eletrônicas Assim sendo aprenderemos nesta seção a utilizar o solver do pacote de planilhas eletrônicas Excel para solução de problemas de programação linear DICA Os mesmos conceitos e técnicas que apresentaremos a seguir também podem ser aplicados em outros pacotes de planilhas dadas as necessidades de alterações em detalhes de implementação PASSOS PARA IMPLEMENTAR UM PROBLEMA DE PROGRAMAÇÃO LINEAR EM PLANILHA Ragsdale 2009 apresenta cinco passos que devem ser feitos para implementar qualquer problema de programação linear em uma planilha 1 Organize os dados para o modelo os coeficientes das restrições os coeficientes da função objetivo etc na planilha Reserve as células separadas na planilha para representar cada variável de decisão do modelo algébrico Isso é útil na determinação de fórmulas para a função e restrições do objetivo 2 3 Crie uma fórmula para cada célula da planilha que corresponda à função objetivo no modelo algébrico Para cada restrição crie uma fórmula em uma célula separada na planilha Muitas das fórmulas de restrição têm estrutura semelhante de modo que quando possível crie fórmulas de restrição que possam ser copiadas para implementar outras fórmulas de restrição 4 5 Use sombras e cores de fundo eou bordas para identificar as células que representam as variáveis de decisão restrições e funções objetivos do modelo INSTALANDO O SOLVER Demonstraremos neste módulo como usar o solver do Excel resolvendo o problema enfrentado pela Fitwear No entanto antes de solução do problema é preciso instalar o solver nos pacotes de planilhas eletrônicas Excel Para isso siga o passo a passo Clique em arquivos opções no Excel conforme indicado na figura Instalando o solver Passo 1 Captura do Excel O segundo passo é clicar em suplementos na tela que foi aberta Instalando o solver Passo 2 Captura do Excel Na tela seguinte clique no botão ir em gerenciar suplementos do Excel Instalando o solver Passo 3 Captura do Excel Na próxima tela clique na opção solver Instalando o solver Passo 4 Captura do Excel Para finalizar basta clicar na aba dados para visualizar a opção solver Instalando o solver Passo 5 Captura do Excel UTILIZANDO O SOLVER Agora que já temos o solver instalado no nosso Excel vamos iniciar a resolução do problema da Fitwear visto no módulo 1 DICA Caso seja necessário retorne ao módulo anterior e relembre como desenvolvemos o modelo matemático do problema Observe a seguir o modelo matemático considerando as variáveis de decisão x1 Número de tops de ginástica confeccionados a cada semana x2 Número de calças de ginástica confeccionadas a cada semana Crie a equação matemática em sua formapadrão MÁX Z 28 X1 40X2 SUJEITO A 0 5X1 0 25X2 100 RESTRIÇÃO DE HORAS DE CORTE 0 25X 0 5X 160 RESTRIÇÃO DE HORAS DE COSTURA X1 X2 0 RESTRIÇÃO DE NÃO NEGATIVIDADE DAS VARIÁVEIS DE DECISÃO Atenção Para visualização completa da equação utilize a rolagem horizontal Uma das primeiras etapas para a solução do problema deve ser a organização dos dados Vamos começar representando as variáveis de decisão como indicado na figura a seguir Observe que descrevemos as variáveis de decisão na planilha bem como os ganhos semanais com a venda de cada produto x1 e x2 deixando destacado em amarelo as células variáveis ou ajustáveis que reservamos na planilha para representar as variáveis de decisão do modelo Variáveis de decisão Captura de tela do Excel O próximo passo é criar uma fórmula que represente a função objetivo de acordo com as variáveis de decisão indicadas na figura Para isso devemos utilizar a função somarproduto do Excel que faz o produto escalar entre dois vetores Função somarproduto Captura de tela do Excel A figura a seguir ilustra como inserimos a função objetivo na planilha eletrônica no caso do problema da Fitwear Observe que fizemos a função somarproduto entre o vetor 2840 que corresponde aos coeficientes da função objetivo e as células que destinamos para receber o valor das variáveis de decisão Com isso teremos que a célula destacada em amarelo para a função objetivo recebeu a fórmula 28 x1 40 x2 Função objetivo Captura de tela do Excel De maneira análoga à que fizemos a representação da função objetivo precisamos representar as restrições Para isso também vamos utilizar a função somarproduto do Excel Veja a seguir como inserimos as duas restrições para o problema da Fitwear na planilha eletrônica RESTRIÇÃO DE HORAS DE CORTE Observe que fizemos a função somarproduto entre os vetores que indicam os coeficientes das restrições e as células que destinamos para receber o valor das variáveis de decisão Com isso teremos que a célula destacada em amarelo na figura restrição de horas de corte recebeu a fórmula 0 5x1 0 25x2 Restrição de horas de corte Captura de tela do Excel RESTRIÇÃO DE HORAS DE COSTURA Observe que a célula destacada em amarelo na figura restrição de horas de costura recebeu a fórmula 0 25x1 0 5x2 Restrição de horas de costura Captura de tela do Excel FINALMENTE TERMINAMOS A IMPLEMENTAÇÃO DO MODELO DO PROBLEMA DE PROGRAMAÇÃO LINEAR DA FITWEAR NO EXCEL ENTRETANTO AINDA PRECISAMOS RESOLVÊLO Para isso é preciso indicar para o solver o que cada célula da planilha representa A FUNÇÃO OBJETIVO AS VARIÁVEIS DE DECISÃO AS RESTRIÇÕES Assim sendo devemos definir a célula de destino ou seja aquela que representa a função objetivo na caixa de diálogo parâmetros do solver como indicado na próxima figura Observe que a célula E9 contém a fórmula que representa a função objetivo para o nosso problema como havíamos preparado anteriormente Neste momento devemos instruir também o solver para tentar maximizar seu valor especificando o botão max Definindo a função objetivo na célula de destino Captura de tela do Excel O próximo passo consiste em indicar as células que representam as variáveis de decisão no modelo Observe na figura a seguir que as células C8 e D8 em nossa planilha representam as variáveis de decisão para o modelo O solver determinará os valores ótimos para essas células Definindo as variáveis de decisão Captura de tela do Excel A seguir devemos definir as células de restrição na planilha e as restrições que se aplicam a essas células ATENÇÃO As células de restrição são aquelas em que implementamos as fórmulas para cada restrição Clique no botão incluir Especificando as células de restrição passo 1 Captura de tela do Excel Preencha a caixa de diálogo incluir restrições Especificando as células de restrição passo 2 Captura de tela do Excel Observe que as células E13 e E14 representam as células de restrição cujos valores devem ser menores ou iguais aos indicados nas células G13 e G14 respectivamente Especificando as células de restrição passo 3 Captura de tela do Excel Já especificamos as restrições mas ainda precisamos determinar que as variáveis de decisão devem ser iguais ou maiores do que zero Para isso basta clicar em tornar variáveis irrestritas não negativas na caixa de diálogo parâmetros do solver conforme indicado na figura a seguir Enfim para encontrarmos a solução ótima para o problema basta clicar no botão resolver Condições de não negatividade Captura de tela do Excel A figura a seguir apresenta a tela de saída do Excel com a solução ótima para o problema da Fitwear Solução ótima para o problema da Fitwear Captura de tela do Excel Observe que x1 deve ser 5333 x2 recebe 293333 e o valor ótimo de z é igual a 1322667 UTILIZAÇÃO DO SOLVER PARA A SOLUÇÃO DE PROBLEMAS DE PROGRAMAÇÃO LINEAR O vídeo mostra um passo a passo para a resolução de um problema de programação linear no solver do Excel VERIFICANDO O APRENDIZADO CONCLUSÃO CONSIDERAÇÕES FINAIS A pesquisa operacional pode nos auxiliar no apoio a processos de decisão em especial para problemas complexos Estudamos o método simplex tanto pelo modo analítico quanto pelo tabular por meio do qual aprendemos a resolver problemas de programação linear encontrando a solução ótima para este tipo de problema Contudo resolvêlos manualmente é muito trabalhoso envolvendo um grande número de cálculos Um simples erro em uma das contas requeridas implica encontrar uma solução equivocada para o problema Por isso é muito importante conhecer softwares computacionais que permitem a solução de problemas de programação matemática São muitos os softwares computacionais dedicados à solução de problemas de programação matemática como o CPLEx o GAMS o LINDO o LINGO etc No entanto problemas de programação linear podem ser resolvidos pelo solver de pacotes de planilhas eletrônicas Aprendemos a solucionar problemas de programação linear por meio do solver do Excel Isso certamente facilitará que consigamos aplicar a Pesquisa Operacional para a solução de problemas reais PODCAST PODCAST Ouça o podcast com um resumo dos conteúdos estudados REFERÊNCIAS ARENALES M et al Pesquisa operacional Rio de Janeiro Elsevier 2007 FOGLIATO F Pesquisa operacional Porto Alegre 2006 Notas de aula GOLDBARG M C LUNA H P Otimização combinatória e programação linear 2 ed São Paulo Campus 2005 LACHTERMACHER G Pesquisa operacional na tomada de decisões Rio de Janeiro Campus 2009 RAGSDALE C T Modelagem e análise de decisão São Paulo Cengage Learning 2014 RODRIGUES L H AHLERT F LACERDA D P CAMARGO L F R LIMA P Pesquisa operacional programação linear passo a passo do entendimento do problema à interpretação da solução São Leopoldo Unisinos 2014 EXPLORE Para saber mais sobre os assuntos tratados nesta aula leia Conheça métodos preparatórios utilizados antes do emprego do simplex para resolver problemas diferentes do padrão de maximização com restrições do tipo menor ou igual no capítulo 4 do livro Operations research applications and algorithms Vol 3 de Winston e Goldberg 2004 Para se aprofundar na utilização do solver para a solução de problemas de programação linear sugerimos a leitura do capítulo 3 do livro Modelagem e análise de decisão de Ragsdale 2009 CONTEUDISTA Renata Albergaria de Mello Bandeira CURRÍCULO LATTES