Baixe o app para aproveitar ainda mais
Prévia do material em texto
Algoritmo Simplex – Segunda Aula Pesquisa Operacional I Jhoab Negreiros 1 ALGORITMO SIMPLEX Segunda aula 1 Introdução O algoritmo Simplex é a ferramenta básica da programação linear. O objetivo do algoritmo é transformar uma matriz dada em outra equivalente que contenha certo “desenho” ou “padrão”. Este capítulo faz um esboço do Simplex, destacando seu parentesco com o algoritmo de Gauss-Jordan discutido no capítulo três. 2 Conversão de desigualdade em uma equação Em restrições , o lado direito pode ser considerado como a representação do limite imposto à 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 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 primeiro membro da restrição. Exemplo 1. Dada a seguinte desigualdade: 3 2 12x y . Para transformar em uma equação adicionamos a variável de folga 1F e logo temos: 1 13 2 12, 0x y F com F Algoritmo Simplex – Segunda Aula Pesquisa Operacional I Jhoab Negreiros 2 De forma semelhante, uma restrição estabelece um limite inferior para as atividades do modelo de programação linear, de modo que a quantidade pela qual o lado esquerdo excede o limite mínimo representa uma sobra. Consegue-se a conversão de em uma igualdade com a subtração de uma variável de sobra não negativa do lado esquerdo da desigualdade. Exemplo 2. Dada a seguinte desigualdade: 100x y . Para transformar em uma equação subtraímos a variável de folga 2F e logo temos: 2 2100, 0x y F com F A última possibilidade restante é que o lado direito da equação resultante seja negativo. A condição sempre pode ser satisfeita multiplicando-se ambos os lados da equação resultante por 1 . Exemplo 3. Dada a seguinte desigualdade: 2 20x y . Para transformar em uma equação adicionamos a variável de folga 3F e logo temos: 3 32 20, 0x y F com F Agora, multiplicando ambos os lados por 1 , teremos um lado direito não negativo, como desejado, isto é: 32 20x y F 3 Transição da Solução Gráfica para a Solução Algébrica As idéias transmitidas pela solução gráfica do problema de programação linear lançam as bases para o desenvolvimento do método algébrico simplex. No método gráfico, a região de soluções é delineada pelos meios-espaços, que representam as restrições, e, no método simplex, a região de soluções é representada por m equações lineares simultâneas e n variáveis não negativas. A figura a seguir traça um paralelo entre os dois métodos. Algoritmo Simplex – Segunda Aula Pesquisa Operacional I Jhoab Negreiros 3 Método Gráfico Método Algébrico Represente todas as restrições em gráfico, entre elas as restrições de não-negatividade. Represente a região de soluções por m equações em n variáveis e restrinjam todas as variáveis a valores não negativos,m n . Identifique os pontos extremos viáveis da região de soluções. Determine as soluções básicas viáveis das equações. Candidatos à solução ótima são dados por um número finito de pontos extremos. Candidatas à solução ótima são dadas por um número finito de soluções básicas viáveis. Use a função objetivo para determinar o ponto extremo ótimo entre todos os candidatos. Use a função objetivo para determinar a solução básica viável ótima entre todos os candidatos. Podemos verificar visualmente pelo gráfico por que a região de soluções tem um número infinito de pontos de solução, mas como podemos tirar a mesma conclusão da representação algébrica de soluções? A resposta é que na representação algébrica o número de equações m é sempre menor do que ou igual ao número de variáveis n . Se m n , e as equações forem consistentes, o sistema tem somente uma solução; mas se m n (o que representa a maioria dos problemas de PL), então o sistema de equações, novamente, se consistente, dará como resultado um número infinito de soluções. Exemplo 4. A equação 2x tem 1m n e a solução é obviamente única. 2S , mas para a equação 1x y , temos 1m e 2n , que resulta em um número infinito de soluções: 1 ,S y y para todo ∈ ℝ. 4 Determinação Algébrica dos Pontos Extremos Em um conjunto de m n equações ( )m n , se igualarmos ( )n m variáveis a zero, e depois resolvermos as m equações para as m variáveis restantes, a solução resultante, se for única, é denominada solução básica e deve corresponder a um ponto extremo (viável ou inviável) da região de soluções. Isso significa que o número máximo de pontos extremos é: , ! !( )!n m nC m n m Algoritmo Simplex – Segunda Aula Pesquisa Operacional I Jhoab Negreiros 4 Exemplo 5. Considere o seguinte problema de PL com duas variáveis: , 2 3 2 4 2 5 , 0 Maximizar f x y x y Restrições x y x y x y Em linguagem algébrica, a região de soluções do problema de programação PL é representado por: 1 2 1 1 2 4 2 5 , , , 0 x y F x y F x y F F O sistema tem 2m equações e 4n variáveis. Assim, de acordo com a regra dada, os pontos extremos podem ser determinados algebricamente igualando 4 2 2n m variáveis a zero e depois, resolvendo para as 2m variáveis restantes. Se fizermos 0x e 0y , as equações dão a solução (básica) única: 1 24, 5F F .(Esta solução corresponde ao ponto A.) Um outro ponto pode ser determinado, fazendo 1 0F e 2 0F . Então resolvendo as duas equações: Algoritmo Simplex – Segunda Aula Pesquisa Operacional I Jhoab Negreiros 5 2 4 2 5 x y x y , o que dá como resultado a solução básica 1x e 2y , que é o ponto C na figura. É provável que você esteja imaginando como podemos decidir quais n m variáveis devem ser igualadas a zero para chegar a um ponto extremo específico. Sem o auxílio da solução gráfica, não podemos dizer quais n m variáveis zero estão associadas com quais pontos extremos. Mas isso não nos impede de enumerar todos os pontos extremos da região de soluções. Apenas considere todas as combinações nas quais n m variáveis sejam igualadas a zero e resolva as equações resultantes. Isso feito, a solução ótima é a solução básica viável (pontos extremos) que resultar no melhor valor para a função objetivo. Neste exemplo temos: 4,2 4 3 62!C pontos extremos. Examinando a figura podemos localizar os quatro pontos A, B, C, D, E e F, todos são soluções para o problema, mas os dois últimos são não viáveis, porque não satisfazem todas as restrições. Para resumir a transição da solução gráfica para a solução algébrica, as m n variáveis zero são conhecidas como variáveis não básicas. As restantes m variáveis são denominadas variáveis básicas e sua solução é denominada solução básica. Variáveis não básicas Variáveis básicas Solução básica Pontos extremos Viáveis ou não viáveis Valor da f.o. (x, y) (F1, F2) (4, 5) A Sim 0 (x, F1) (y, F2) (4, –3) F Não --(x, F2) (y, F1) (5/2, 3/2) B Sim 7,5 (y, F1) (x, F2) (2, 3) D Sim 4 (y, F1) (x, F1) (5, –6) E Não -- (F1, F2) (x, y) (1, 2) C Sim 8 (ótimo) 5 Natureza Iterativa do Método Simplex Em vez de enumerar todas as soluções básicas (pontos extremos) do problema de PL (como fizemos na tabela acima), o método simplex investiga somente algumas dessas soluções. Algoritmo Simplex – Segunda Aula Pesquisa Operacional I Jhoab Negreiros 6 Normalmente o método simplex começa na origem, onde 0x y . Nesse ponto de partida, o valor da função objetivo é zero, e a pergunta lógica é se um aumento em x e/ou y não básicas acima de seus valores zero atuais pode melhorar o valor da f.o., basta investigar o valor da mesma. Maximizar: ( , ) 2 3f x y x y . A função mostra que um aumento em x ou y (ou em ambas) acima de seus valores zero atuais melhorará o seu valor. O 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 para a f.o. (com isso chegamos ao ponto B). Portanto, no ponto B o método simplex aumentará o valor de x para alcançar o ponto extremo melhorado C, que é a solução ótima. Assim, o caminho do método simplex é definido como A B C . Cada ponto extremo ao longo do caminho é associado a uma iteração. É importante observar que o método simplex percorre as bordas da região de soluções, o que significa que o método não pode atravessar a região de soluções e ir de A para C diretamente. 6 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. Exemplo 6. Usaremos o problema de PL a seguir: : 5 4 : 6 4 24 2 6 1 2 , 0 Maximizar z x y Restrições x y x y x y y x y O problema é expresso na forma de equações como: Algoritmo Simplex – Segunda Aula Pesquisa Operacional I Jhoab Negreiros 7 1 2 3 4 1 2 3 4 1 2 3 4 : 5 4 0 0 0 0 : 6 4 24 2 6 1 2 , , , , , 0 Maximizar z x y F F F F Restrições x y F x y F x y F y F x y F F F F As variáveis 1 2 3, ,F F F e 4F são as folgas associadas às respectivas restrições. Em seguida, escrevemos a função objetivo como: 5 4 0z x y . Dessa maneira, a tabela simplex inicial pode ser representada da seguinte maneira: Base Z X Y F1 F2 F3 F4 Solução Z 1 -5 -4 0 0 0 0 0 Linha Z F1 0 6 4 1 0 0 0 24 Linha F1 F2 0 1 2 0 1 0 0 6 Linha F2 F3 0 -1 1 0 0 1 0 1 Linha F3 F4 0 0 1 0 0 0 1 2 Linha F4 O arranjo da tabela específica e o conjunto de variáveis básicas e não básicas, apresenta a solução associada com a iteração inicial. Variáveis não básicas (zero) em A: ( , )x y . Variáveis básicas: ( 1, 2, 3, 4)F F F F . A solução inicial é ótima? A função objetivo: 5 4z x y mostra que a solução pode ser melhorada, aumentando x ou y . Coeficiente da f.o. mais positivo é selecionado como a variável ao entrar na base. Essa regra é denominada condição de otimalidade. A 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 na base x . Entrando Razão Base X Solução (ou intercepto) F1 6 24 X = 24/6 = 4 (Mínimo) F2 1 6 X = 6/1 = 6 F3 -1 1 X = 1/-1 = -1 (Ignorar) F4 0 2 X = 2/0 (Ignorar) Conclusão: X entra, F1 sai. Algoritmo Simplex – Segunda Aula Pesquisa Operacional I Jhoab Negreiros 8 Observem que os valores das razões calculadas são as interseções das restrições com o eixo x da variável que entra na base. A regra associada com os cálculos das razões é denominada condição de viabilidade. O novo ponto de solução B é determinado pela troca entre a variável que entra na base X e a variável que sai da base F1 na tabela simplex para produzir os seguintes conjuntos de variáveis não básicas e básicas. Variáveis não básicas (zero) em B: ( 1, )F y . Variáveis básicas: ( , 2, 3, 4)x F F F . O processo de troca é baseado nas operações de Gauss-Jordan, 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ô. Os cálculos serão aplicados a primeira tabela da seguinte forma: Substituir F1 na coluna base por X; Nova linha X = Linha F1 atual 6; Nova linha Z = Linha Z atual – ( – 5 ) Nova linha X; Nova linha F2 = Linha F2 atual – ( 1 ) Nova linha X; Nova linha F3 = Linha F3 atual – ( – 1 ) Nova linha X; Nova linha F4 = Linha F4 atual – ( 0 ) Nova linha X. Algoritmo Simplex – Segunda Aula Pesquisa Operacional I Jhoab Negreiros 9 Base Z X Y F1 F2 F3 F4 Solução Z 1 0 -2/3 5/6 0 0 0 20 Linha Z X 0 1 2/3 1/6 0 0 0 4 Linha F1 F2 0 0 4/3 -1/6 1 0 0 2 Linha F2 F3 0 0 5/3 1/6 0 1 0 5 Linha F3 F4 0 0 1 0 0 0 1 2 Linha F4 Observe que a nova tabela tem as mesmas propriedades da tabela inicial. O novo valor da função objetivo é igual a 20. Pela condição de otimalidade mostra que Y é a variável que deve entrar na base. A condição de viabilidade produz o seguinte: Entrando Razão Base Y Solução (ou intercepto) X 2/3 4 Y = 4:2/3 = 6 F2 4/3 2 Y = 2:4/3 = 1,5 (Mínimo) F3 5/3 5 Y = 5:5/3 = 3 F4 1 2 Y = 2:1 = 2 Conclusão: Y entra, F2 sai. Substituindo F2 na coluna base por Y que entra, as seguintes operações de filas por Gauss- Jordan são aplicadas: Substituir F2 na coluna base por Y; Nova linha Y = Linha F2 atual 4/3; Nova linha Z = Linha Z atual – ( – 2/3 ) Nova linha Y; Nova linha X = Linha X atual – ( 2/3 ) Nova linha Y; Nova linha F3 = Linha F3 atual – ( 5/3 ) Nova linha Y; Nova linha F4 = Linha F4 atual – ( 1 ) Nova linha Y. Esses cálculos produzem a tabela a seguir. Base Z X Y F1 F2 F3 F4 Solução Z 1 0 0 3/4 1/2 0 0 21 Linha Z X 0 1 0 1/4 -1/2 0 0 3 Linha X Y 0 0 1 -1/8 3/4 0 0 3/2 Linha Y F3 0 0 0 3/8 -5/4 1 0 5/2 Linha F3 F4 0 0 0 1/8 -3/4 0 1 1/2 Linha F4 Algoritmo Simplex – Segunda Aula Pesquisa Operacional I Jhoab Negreiros 10 Com base na condição de otimalidade, nenhum dos coeficientes da linha Z associados com as variáveis não básicas F1 e F2, é negativo. Assim, essa tabela simplex é ótima. A solução ótima pode ser lida na tabela simplex da seguinte maneira: Variável Valor Recomendação de decisão ótimo X 3 Produzir 3t diárias de tintas para exteriores. Y 1,5 Produzir 1,5t diárias de tintas para interiores. Z 21 Lucro diário é $ 21,00. A solução também fornece informações dos recursos. Um recurso é designado como escasso se as atividades (variáveis) do modelo o usarem totalmente. Caso contrário, o recurso é denominado abundante. Essa informação é obtida da tabela ótima pela verificação do valor da variável de folga associada à restrição que representa o recurso. Se a folga for zero, o recursoé totalmente utilizado e, por conseguinte, é classificado como escasso. Ao contrário, uma folga positiva indica que o recurso é abundante. Classificação das restrições do modelo: Recurso Valor da Folga Condição Matéria-prima, M1 F1 Escasso Matéria-prima, M2 F2 Escasso Limite de Mercado F3 Abundante Limite da demanda F4 Abundante 7 Método das duas Fases Os problemas de PL nos quais todas as restrições são ( ) com lados direitos não negativos oferecem uma solução básica inicial viável conveniente na qual todas as variáveis são de folga. Isso não acontece com modelos que envolvem restrições ( ) e ( ) . O procedimento para iniciar a resolução de problemas de PL com as restrições ( ) e ( ) é usar variáveis artificiais que desempenham o papel de folgas na primeira iteração e então, descartá- las legitimamente em iterações posteriores. Usaremos o exemplo para desenvolver o método: Algoritmo Simplex – Segunda Aula Pesquisa Operacional I Jhoab Negreiros 11 Exemplo 7. Minimizar a função: 4 5Z x y , sujeito a restrições: 3 3 4 3 6 2 4 , 0 x y x y x y x y Fase I Usando F1 como uma sobra na segunda restrição e F2 como folga na terceira restrição. A terceira equação tem sua variável de folga, F2, mas a primeira e a segunda equação não têm, adicionamos as variáveis artificiais R1 e R2 nas duas primeiras equações, e a forma de equações do problema é dada como: : 1 2Minimizar r R R Sujeito a: 3 1 3 4 3 1 2 6 2 2 4 , , 1, 2, 1, 2 0 x y R x y F R x y F x y F F R R A tabela associada é dada: Base X Y F1 R1 R2 F2 Solução r 0 0 0 -1 -1 0 0 Linha r R1 3 1 0 1 0 0 3 Linha R1 R2 4 3 -1 0 1 0 6 Linha R2 F2 1 2 0 0 0 1 4 Linha F2 Antes de continuar com os cálculos do método simplex, precisamos tornar a linha r consistente com o resto da tabela. Especificamente, na tabela, 1 0x y F , o que resulta na solução básica 1 3R , 2 6R e 2 4F , o que resulta na solução básica: 3 6 9r (em vez de 0, como mostra a tabela acima). Para isso são substituídas na linha r , usando os seguintes cálculos: Algoritmo Simplex – Segunda Aula Pesquisa Operacional I Jhoab Negreiros 12 (1 1 1 2)Nova linha r linha velha r linha R linha R . Base X Y F1 R1 R2 F2 Solução r 7 4 -1 0 0 0 9 Linha r R1 3 1 0 1 0 0 3 Linha R1 R2 4 3 -1 0 1 0 6 Linha R2 F2 1 2 0 0 0 1 4 Linha F2 Entrando X e saindo da base R1. Base X Y F1 R1 R2 F2 Solução r 0 5/3 -1 -7/3 0 0 2 Linha r X 1 1/3 0 1/3 0 0 1 Linha X R2 0 5/3 -1 -4/3 1 0 2 Linha R2 F2 0 5/3 0 -1/3 0 1 3 Linha F2 Entrando Y e saindo da base R2. Base X Y F1 R1 R2 F2 Solução r 0 0 0 -1 -1 0 0 Linha r X 1 0 1/5 9/15 -1/5 0 3/5 Linha X Y 0 1 -3/5 -4/5 3/5 0 6/5 Linha Y F2 0 0 1 1 -1 1 1 Linha F2 Como mínimo 0r , a Fase I produz a solução básica viável 35x , 6 5y e 2 1F . Nesse ponto, as variáveis artificiais concluíram sua missão e podemos eliminar totalmente suas colunas da tabela e passar para a Fase II. Fase II Após eliminar as colunas artificiais, escrevemos o problema original como: : 4Minimizar Z x y Algoritmo Simplex – Segunda Aula Pesquisa Operacional I Jhoab Negreiros 13 Sujeito a: 1 315 5 3 615 5 1 2 1 , , 1, 2 0 x F y F F F x y F F Base X Y F1 F2 Solução Z -4 -1 0 0 0 Linha Z X 1 0 1/5 0 3/5 Linha X Y 0 1 -3/5 0 6/5 Linha Y F2 0 0 1 1 1 Linha F2 Novamente, como as variáveis básicas x e y têm coeficientes não zero na linha Z, elas devem ser substituídas com a utilização dos seguintes cálculos: (4 1 )Nova linha Z linha velha Z linha x linha y Portanto, a tabela inicial da Fase II é dada como: Base X Y F1 F2 Solução Z 0 0 1/5 0 18/5 Linha Z X 1 0 1/5 0 3/5 Linha X Y 0 1 -3/5 0 6/5 Linha Y F2 0 0 1 1 1 Linha F2 Como estamos minimizando F1, devemos entrar na solução. Base X Y F1 F2 Solução Z 0 0 0 -1/5 17/5 Linha Z X 1 0 0 -1/5 2/5 Linha X Y 0 1 0 3/5 9/5 Linha Y F1 0 0 1 1 1 Linha F1 Resumo do método das duas fases: Fase 1: Expresse o problema na forma de equações e adicione as variáveis artificiais necessárias às restrições para garantir uma solução básica inicial. Em seguida, ache uma solução básica com as equações resultantes que, independentemente do problema de PL ser de maximização ou minimização, sempre minimizará a soma das variáveis artificiais. Se o valor mínimo da soma for positivo, o problema de PL não tem nenhuma solução viável, o que encerra o processo (lembre-se de que uma variável artificial positiva significa que uma restrição original não foi satisfeita). Fase 2: Use a solução viável da Fase 1 como uma solução básica viável inicial para o problema original. Algoritmo Simplex – Segunda Aula Pesquisa Operacional I Jhoab Negreiros 14 8 Atividades Exercício 1. Sabendo que a função objetivo de um problema de programação linear é dada por ( , ) 4 5f x y x y , determine o valor máximo (a),(b) e (c) e mínimo (d) desta função sobre as restrições utilizando o método simplex. (a) 0, 0 2 15 2 15 x y x y x y (b) 0, 0 60, 50 2 120 x y x y x y (c) 0, 0 25 5 x y x y x y (d) 0, 0 3 12 3 4 30 2 7 28 x y x y x y x y Exercício 2. Uma fábrica produz dois artigos A e B, que devem passar por duas máquinas diferentes M1 e M2. M1 tem 12 horas de capacidade diária disponível e M2 tem 5 horas. Cada unidade de produto A requer 2 horas em ambas as máquinas. Cada unidade de produto B requer 3 horas em M1 e 1 hora em M2. O lucro líquido de A é de R$ 60,00 por unidade e o de B, R$ 70,00 por unidade. Determinar a quantidade a ser produzida de A e B a fim de se ter um lucro máximo. Exercício 3. Uma pequena fábrica de papel toalha manufatura três tipos de produtos A, B e C. A fábrica recebe o papel em grandes rolos. O papel é cortado, dobrado e empacotado. Dada a pequena escala da fábrica, o mercado absorverá qualquer produção a um preço constante. O lucro unitário de cada produto é respectivamente R$ 1,00, R$ 1,50, e R$ 2,00. O quadro abaixo identifica o tempo requerido para operação (em horas) em cada seção da fábrica, bem como a quantidade de máquinas disponíveis, que trabalham 40 horas por semana. Planeje a produção semanal da fábrica. Algoritmo Simplex – Segunda Aula Pesquisa Operacional I Jhoab Negreiros 15 Seção Produto A Produto B Produto C Quantidade de Máquina Corte 8 5 2 3 Dobra 5 10 4 10 Empacotamento 0,7 1 2 2 Exercício 4. Um criador de coelhos alimenta os animais com cinco tipos de ração, cuja composição de nutrientes (unidades/Kg) está mostrada abaixo: Nutrientes Ração A Ração B Ração C Ração D Ração E Proteínas 30 20 15 80 20 Carboidratos 60 20 60 20 20 Gordura 5 10 5 3 2 Custo/Kg 0,20 0,30 0,40 0,50 0,25 Ele calculou as necessidades diárias de alimentação de cada animal em, pelo menos, 80 unidades de proteína, 120 unidades de carboidratos e 30 unidades de gordura. Qual deve ser a mistura das rações acima a custo mínimo? Exercício 5. Desejamosotimizar o lucro pela utilização de até quatro opções de culturas (milho, trigo, soja e açúcar). As restrições referem-se ao espaço utilizado, gastos com preparo do terreno e utilização de mão-de-obra. Tem-se disponível 400 ha de terra para o cultivo. A matriz abaixo apresenta os dados referentes a cada cultura: Atividade Milho Trigo Soja Açúcar Disponível Preparo do terreno (R$/ha) 1.000,00 1.200,00 1.500,00 1.200,00 500.000,00 Mão-de-obra (homens/dia) 20 30 25 28 10.000 Lucro (R$/ha) 600,00 800,00 900,00 500,00 Exercício 6. Uma empresa produz televisão em 3 fábricas: São Paulo, João Pessoa e Manaus. Os pontos principais de revenda, com as respectivas encomendas mensais são: Algoritmo Simplex – Segunda Aula Pesquisa Operacional I Jhoab Negreiros 16 Rio de Janeiro 6.000 unidades Salvador 5.000 unidades Aracajú 2.000 unidades Maceió 1.000 unidades Recife 3.000 unidades A produção máxima mensal em cada fábrica é: São Paulo 10.000 unidades João Pessoa 5.000 unidades Manaus 6.000 unidades O custo de transportes das fábricas até as revendas é dado pelo quadro abaixo: R$ por 1.000 unidades de TV. Para De Rio de Janeiro (1) Salvador (2) Aracaju (3) Maceió (4) Recife (5) (1) São Paulo 1.000 2.000 3.000 3.500 4.000 (2) João Pessoa 4.000 2.000 1.500 1.200 1.000 (3) Manaus 6.000 4.000 3.500 3.000 2.000 Determinar o número de unidades produzidas em cada fábrica e entregues a cada revenda, a fim de minimizar o custo de transporte.
Compartilhar