Método Simplex: Teoria e Aplicação

Método Simplex Método Simplex É um método interativo utilizado para achar algebricamente a solução ótima de um problema de Programação Linear Método Simplex George Dantzig 1947 Muito utilizado Facilmente implementado como programa de computador Consegue resolver problemas com muitas variáveis milhares Produz variáveis auxiliares para análise de sensibilidade Convém saber resolver à mão para se compreender o seu funcionamento Método Simplex Introdução das variáveis de folga Usualmente as restrições de um problema de PO têm a seguinte estrutura lógica Utilização de recurso Disponibilidade Ex 2x 3y 60 x 4y 200 Se introduzirmos o conceito de Folga de recurso podemos reescrever a relação Utilização de recurso Disponibilidade da seguinte forma usando uma variável de folga Utilização Folga Disponibilidade Forma Canônica Ex 2x 3y 60 2x 3y z 60 Método Simplex Introdução das variáveis de folga Se a relação for invertida ou seja Utilização de recurso Disponibilidade Subtrairemos a variável de folga Utilização de recursos Folga Disponibilidade Forma Canônica Ex 2x 3y 60 2x 3y z 60 Método Simplex Introdução das variáveis de folga Método Simplex Passos INICIO Equações Lineares Forma de tabela Solução inicial É ótima Variável que entra Variável que sai Nova matriz de coeficientes FIM SIM NÃO Método Simplex Problema a Resolver Considere o modelo de programação linear abaixo Maximizar Z 3x1 5x2 0 Sujeito a X1 4 1 2x2 12 2 3x1 2x2 18 3 e x1 e x2 0 Método Simplex 1º passo Transformar o sistema de desigualdades lineares restritivas em um sistema de equações lineares INICIO Equações Lineares Forma de tabela Solução inicial É ótima Variável que entra Variável que sai Nova matriz de coeficientes FIM Método Simplex 1º passo Forma Canônica Eq 0 Z 3x1 5x2 Z 3x1 5x2 0 Eq 1 x1 4 x1 x3 4 Eq 2 2x2 12 2x2 x4 12 Eq 3 3x1 2x2 18 3x1 2x2 x5 18 Método Simplex Variáveis de Folga Variáveis básicas Formam as variáveis básicas iniciais do Simplex Cada uma aparece apenas numa das equações de restrição Têm coeficiente 1 onde ela aparece e coeficiente 0 nas outras equações Ficase com um problema aumentado onde temos as variáveis de decisão e as variáveis básicas Método Simplex 1º passo Z 3x1 5x2 0 x1 x3 4 2x2 x4 12 3x1 2x2 x5 18 Se assumirmos que as variáveis de decisão são 0 zero então as variáveis de folga são iguais a B Ax1 x2 B x20 Método Simplex 2º passo Colocar as equações em forma de tabela INICIO Equações Lineares Forma de tabela Solução inicial É ótima Variável que entra Variável que sai Nova matriz de coeficientes FIM Método Simplex 2º passo Colocar as equações em forma de tabela 1Z 3x1 5x2 0x3 0x4 0x5 0 0Z 1x1 0x2 1x3 0x4 0x5 4 0Z 0x1 2x2 0x3 1x4 0x5 12 0Z 3x1 2x2 0x3 0x4 1x5 18 Z 3x15x2 0 x1 x34 2x2 x412 3x12x2x518 Método Simplex 2º passo Var Básica Eq N Coeficientes Lado Direito Z x1 x2 x3 x4 x5 0 1 3 5 0 0 0 0 1 0 1 0 1 0 0 4 2 0 0 2 0 1 0 12 3 0 3 2 0 0 1 18 Colocar as equações em forma de tabela 1Z 3x1 5x2 0x3 0x4 0x5 0 0Z 1x1 0x2 1x3 0x4 0x5 4 0Z 0x1 2x2 0x3 1x4 0x5 12 0Z 3x1 2x2 0x3 0x4 1x5 18 Método Simplex 2º passo Var Básica Eq N Coeficientes Lado Direito Z x1 x2 x3 x4 x5 0 1 3 5 0 0 0 0 1 0 1 0 1 0 0 4 2 0 0 2 0 1 0 12 3 0 3 2 0 0 1 18 Método Simplex 3º passo Determinar uma solução inicial viável INICIO Equações Lineares Forma de tabela Solução inicial É ótima Variável que entra Variável que sai Nova matriz de coeficientes FIM Método Simplex 3º passo Solução Inicial As variáveis de decisão são 0 zero As variáveis não básicas da tabela são nulas x1 x2 0 As variáveis de folga são iguais à restrição As variáveis básicas têm o valor da última coluna x3 4 x4 12 x5 12 A função objetivo é 0 zero Z 0 Método Simplex 3º passo Solução inicial Var Básica Eq N Coeficiente de Lado Direito Z x1 x2 x3 x4 x5 Z 0 1 3 5 0 0 0 0 x3 1 0 1 0 1 0 0 4 x4 2 0 0 2 0 1 0 12 x5 3 0 3 2 0 0 1 18 x1 x2 0 Z 0 x3 4 x4 12 x5 12 Método Simplex 4º passo Verificar se a solução é ótima INICIO Equações Lineares Forma de tabela Solução inicial É ótima Variável que entra Variável que sai Nova matriz de coeficientes FIM Método Simplex Teste de Solução Ótima A atual solução básica é ótima se e somente se cada coeficiente da Eq 0 for não negativo 0 Se assim é pare Achou a solução ótima Senão vá para o passo iterativo Método Simplex 4º passo Var Básica Eq N Coeficiente de Lado Direito Z x1 x2 x3 x4 x5 Z 0 1 3 5 0 0 0 0 x3 1 0 1 0 1 0 0 4 x4 2 0 0 2 0 1 0 12 x5 3 0 3 2 0 0 1 18 Há coeficientes negativos na Equação da Função Objetivo Método Simplex Para se obter a próxima solução básica viável tem que transformar uma variável nãobásica numa variável básica e viceversa ou seja transformar uma variável de decisão em variável de folga e viceversa Método Simplex 5º passo Determinar a variável que entra variável de decisão INICIO Equações Lineares Forma de tabela Solução inicial É ótima Variável que entra Variável que sai Nova matriz de coeficientes FIM Método Simplex Ideia Geral para Melhorar a Solução Trocar de variáveis base Fazer crescer uma das variáveis não básicas que assim deixa de ser zero Escolher a que mais contribui para o lucro Essa variável passa a ser variável base Sacrificar uma das velhas variáveis básicas Escolher a variável que menos diminui com essa entrada Essa variável deixa de ser base e passa a ser zero Método Simplex Regra de Entrada Escolher a variável que na primeira linha tenha o coeficiente mais negativo é a que mais contribui para o lucro Método Simplex Regra de Entrada O exemplo tem dois coeficientes negativos na Eq 0 3 para x1 e 5 para x2 No exemplo o maior coeficiente negativo é 5 para x2 5 3 portanto x2 dever ser transformado numa variável básica Simplex 2º passo Var Básica Eq N Coeficiente de Lado Direito Z x1 x2 x3 x4 x5 Z 0 1 3 5 0 0 0 0 x3 1 0 1 0 1 0 0 4 x4 2 0 0 2 0 1 0 12 x5 3 0 3 2 0 0 1 18 PIVÔ Método Simplex 6º passo Determinar a variável que sai variável básica ou de folga INICIO Equações Lineares Forma de tabela Solução inicial É ótima Variável que entra Variável que sai Nova matriz de coeficientes FIM Método Simplex Regra de Saída Determine a variável básica que sai selecionando cada coeficiente na coluna circunscrita que seja estritamente positiva 0 dividindo o valor do lado direito de cada linha pelo coeficiente correspondente continua Simplex 2º passo Var Básic a Eq N Coeficiente de Lado Direito Z x1 x2 x3 x4 x5 Z 0 1 3 5 0 0 0 0 x3 1 0 1 0 1 0 0 4 x4 2 0 0 2 0 1 0 12 x5 3 0 3 2 0 0 1 18 40 1226 1829 Método Simplex Regra de Saída Determine a variável básica que sai continuando identificando as equações que tenham as menores destas razões selecionando a variável básica para esta equação Simplex 2º passo Var Básic a Eq N Coeficiente de Lado Direito Z x1 x2 x3 x4 x5 Z 0 1 3 5 0 0 0 0 x3 1 0 1 0 1 0 0 4 x4 2 0 0 2 0 1 0 12 x5 3 0 3 2 0 0 1 18 40 122 6 182 9 Método Simplex Número e Linha Pivô A linha circunscrita é chamada de linha pivô O número que está em ambos os retângulos no encontro de linha e coluna é chamado de número pivô Simplex Variável Básica Eq N Coeficiente de Lado Direito Z x1 x2 x3 x4 x5 Z 0 1 3 5 0 0 0 0 x3 1 0 1 0 1 0 0 4 x4 2 0 0 2 0 1 0 12 x5 3 0 3 2 0 0 1 18 Linha Pivô Número Pivô Método Simplex 7º passo Calcular a nova matriz de coeficientes INICIO Equações Lineares Forma de tabela Solução inicial É ótima Variável que entra Variável que sai Nova matriz de coeficientes FIM Método Simplex Novo Quadro Simplex Determinar a nova solução básica viável a partir da construção de um novo quadro Simplex abaixo do atual Método Simplex Novo Quadro Simplex O coeficiente da nova variável básica deverá ser mudado para 1 dividindose toda a linha pivô ou seja todos os números desta linha inclusive o lado direito pelo número pivô de modo que pivô Número Antiga linha pivô Nova linha pivô Iteração Variável Básica Eq N Coeficiente de Lado Direito Z x1 x2 x3 x4 x5 0 Z 0 1 3 5 0 0 0 0 x3 1 0 1 0 1 0 0 4 x4 2 0 0 2 0 1 0 12 x5 3 0 3 2 0 0 1 18 1 Z 0 1 x3 1 0 x2 2 0 0 1 0 12 0 6 x5 3 0 pivô Número Antiga linha pivô Nova linha pivô Simplex parte 3 As demais linhas são modificadas para o novo quadro usando a seguinte fórmula Nova linha Antiga linha Coeficiente da coluna pivô x Nova linha pivô Onde coeficiente da coluna pivô é o número nesta linha que está na coluna pivô Linha 0 L 0 3 5 0 0 0 0 5 x 0 1 0 ½ 0 6 Nova Linha 3 0 0 52 0 30 Nova linha Antiga linha Coeficiente da coluna pivô x Nova linha pivô Antiga Linha Nova Linha Pivô Nova Linha 350 551 050 0512 050 056 Linha 1 L 1 1 0 1 0 0 4 0 x 0 0 0 0 0 0 Nova Linha 1 0 1 0 0 4 Linha 3 L 3 3 2 0 0 1 18 2 x 0 1 0 ½ 0 6 Nova Linha 3 0 0 1 1 6 Nova tabela Iteração Variável Básica Eq N Coeficiente de Lado Direito Z x1 x2 x3 x4 x5 0 Z 0 1 3 5 0 0 0 0 x3 1 0 1 0 1 0 0 4 x4 2 0 0 2 0 1 0 12 x5 3 0 3 2 0 0 1 18 1 Z 0 1 3 0 0 52 0 30 x3 1 0 1 0 1 0 0 4 x2 2 0 0 1 0 ½ 0 6 x5 3 0 3 0 0 1 1 6 Uma vez que cada variável básica é igual ao lado direito de sua equação a nova solução básica viável é x10 x26 x34 x40 x56 com Z 30 Isto completa o passo iterativo Método Simplex 8º passo Repetir passos 4 a 7 até achar a solução ótima INICIO Equações Lineares Forma de tabela Solução inicial É ótima Variável que entra Variável que sai Nova matriz de coeficientes FIM A seguir verificaremos se a nova solução é ótima Como a nova Eq 0 ainda tem um coeficiente negativo 3 para x1 a regra indica que a solução não é ótima e assim retornamos ao passo iterativo para obter a próxima solução básica viável Iteração Var Básica Eq N Coeficiente de Lado Direito Z x1 x2 x 3 x4 x5 0 Z 0 1 3 5 0 0 0 0 x3 1 0 1 0 1 0 0 4 x4 2 0 0 2 0 1 0 12 x5 3 0 3 2 0 0 1 18 1 Z 0 1 3 0 0 0 30 x3 1 0 1 0 1 0 0 4 x2 2 0 0 1 0 0 6 x5 3 0 3 0 0 1 1 6 41 4 60 x 63 2 Iteração Variável Básica Eq N Coeficiente de Lado Direito Z x1 x2 x3 x4 x5 1 Z 0 1 3 0 0 5 0 30 x3 1 0 1 0 1 0 0 4 x2 2 0 0 1 0 1 0 6 x5 3 0 3 0 0 2 1 6 2 Z 0 1 0 0 0 32 1 36 x3 1 0 0 0 1 13 13 2 x2 2 0 0 1 0 12 0 6 X1 3 0 1 0 0 13 13 2 Iteração Variável Básica Eq N Coeficiente de Lado Direito Z x1 x2 x3 x4 x5 2 Z 0 1 0 0 0 32 1 36 x3 1 0 0 0 1 13 13 2 x2 2 0 0 1 0 12 0 6 X1 3 0 1 0 0 13 13 2 Solução final Há coeficientes negativos na Equação da Função Objetivo Solução final Iteração Variável Básica Eq N Coeficiente de Lado Direito Z x1 x2 x3 x4 x5 2 Z 0 1 0 0 0 32 1 36 x3 1 0 0 0 1 13 13 2 x2 2 0 0 1 0 12 0 6 X1 3 0 1 0 0 13 13 2 X1 2 X2 6 Z 36 X3 2 X4 0 X5 0 Variáveis de folga básicas Objetivo Variáveis de decisão não básicas Método Simplex Problema a Resolver Sendo X1 2 e X2 6 Maximizar Z 3x1 5x2 0 Z 32 56 36 Sujeito a X1 4 1 2 4 2x2 12 2 26 12 3x1 2x2 18 3 e 32 26 18 x1 e x2 0 Iteração Variável Básica Eq N Coeficiente de Lado Direito Z x1 x2 x3 x4 x5 2 Z 0 1 0 0 0 32 1 36 x3 1 0 0 0 1 13 13 2 x2 2 0 0 1 0 12 0 6 X1 3 0 1 0 0 13 13 2 Análise de Sensibilidade A primeira linha mostra as contribuições líquidas para o lucro caso as variáveis x4 e x5 venham a ter seus valores aumentados de 0 para 1