MÉTODO SIMPLEX_ALGÉBRICO_Passo a passo

Prévia do material em texto

<p>MÉTODO SIMPLEX – PASSO A PASSO</p><p>1) Verificar se</p><p>- Função objetivo é maximizar</p><p>- As restrições são menores ou iguais.</p><p>- Restrições de Não negatividade maior ou igual a zero. Em programação</p><p>linear, as restrições de não negatividade são condições que exigem que as</p><p>variáveis de decisão assumam valores não negativos. Isso significa que as</p><p>variáveis não podem ser menores que zero.</p><p>Variáveis Básicas:</p><p>• Definição: São as variáveis que assumem valores positivos na solução</p><p>atual do problema, compondo a base do sistema de equações lineares.</p><p>• Número: O número de variáveis básicas é sempre igual ao número</p><p>de restrições no problema.</p><p>• Função: As variáveis básicas determinam o valor da função objetivo na</p><p>solução atual.</p><p>• Representação: Na tabela simplex, as variáveis básicas são representadas</p><p>pelas colunas da matriz identidade.</p><p>Variáveis Não Básicas:</p><p>• Definição: São as variáveis que assumem o valor zero na solução atual do</p><p>problema, não participando da base do sistema de equações.</p><p>• Número: O número de variáveis não básicas é igual à diferença entre o</p><p>número total de variáveis e o número de restrições.</p><p>• Função: As variáveis não básicas não influenciam o valor da função</p><p>objetivo na solução atual.</p><p>• Representação: Na tabela simplex, as variáveis não básicas são</p><p>representadas pelas colunas da matriz de coeficientes.</p><p>2) - Transformar a função objetivo igualando a zero.</p><p>- Igualar as restrições a zero, acrescentando as variáveis de folga (XF1, xF2, ...)</p><p>3) Montar a tabela na sequência: z, x1, x2, x3, xF1, xF2, xF3, b</p><p>4) Variável que ENTRA na base</p><p>- Entra na base a variável com coeficiente negativo de maior valor absoluto.</p><p>5) Variável que SAI</p><p>- Dividir os elementos independentes, na coluna b, com os respectivos</p><p>coeficientes positivos da variável que entra. Considerar a linha que possuir</p><p>o menor resultado positivo. O menor valor indica que a variável básica</p><p>dessa linha é a que primeiro se anula e sairá da base. Essa linha é também</p><p>chamada linha pivô. (NLP)</p><p>10 /4 = 2,5 CONSIDERAR O MENOR RESULTADO POSITIVO (Linha 1, veja</p><p>na tabela abaixo)</p><p>20/6 = 3,33</p><p>30/-1 = não considerar</p><p>6) Elemento PIVÔ</p><p>A coluna da variável que entra e a linha da variável que sai identificam</p><p>um elemento chamado PIVÔ. No exemplo, será o número 4.</p><p>7) Calculando a nova solução:</p><p>Exemplo</p><p>Dividimos a linha pivô pelo valor do elemento pivô, obtendo uma nova</p><p>linha com pivô unitário.</p><p>8) Reescrever cada uma das outras linhas:</p><p>a) Multiplicar os elementos da nova linha pivô pelo coeficiente da</p><p>variável que entra da outra linha, com sinal trocado.</p><p>b) Somar termo a termo com os elementos da outra linha.</p><p>A função objetivo na nova solução está escrita em termos das variáveis não</p><p>básicas x1 e xF1. As variáveis básicas têm coeficientes nulos.</p><p>A solução obtida tem z = 12,5, contra z = 0 da solução inicial. É melhor, mas ainda</p><p>NÃO É ÓTIMA, pois o coeficiente de x1 na função objetivo é negativo.</p><p>Então devemos fazer o cálculo da nova solução, até encontrarmos todos os</p><p>valores positivos na função objetivo.</p><p>A partir da nova tabela, procurar a solução ótima, fazendo todos os passos acima.</p><p>A solução será ÓTIMA, quando todos os valores da linha Z (função objetivo)</p><p>forem positivos.</p>