aula3 - O Método Simplex

Prévia do material em texto

MÉTODO SIMPLEX
O Método Simplex foi desenvolvido em 1947 por George B. Dantzig.
Vamos relembrar os teoremas que foram enunciados na última aula:
Teorema 1-Se o problema de programação linear tem solução ótima, então esta solução está em, pelo menos, um ponto extremo do poliedro de soluções viáveis.
Teorema 2-Se a região de soluções viáveis de um problema de programação linear é não vazia, então existe uma solução ótima.
Teorema 3 - O conjunto de soluções viáveis de um problema de programação linear é um conjunto convexo.
Teorema 4- O conjunto de soluções viáveis de um problema de programação linear tem um número finito de pontos extremos (vértices).
Sabemos então que o conjunto de todas as soluções do problema de programação linear é um conjunto convexo cujos vértices, ou seja, cujos pontos extremos correspondem a soluções ditas básicas viáveis.
Sabemos ainda que, se a função objetivo possui um máximo finito, então, pelo menos uma solução ótima é um ponto extremo do conjunto convexo.
Uma pequena metalúrgica deseja maximizar sua receita com a venda de dois tipos de finas fitas de aço que se diferenciam em qualidade no acabamento de corte. As fitas são produzidas a partir do corte de bobinas de grande largura. Existem duas máquinas em operação. Uma das máquinas é mais antiga e permite o corte diário de 4.000 m de fita. A outra, mais nova, corta até 6.000 m. A venda das chapas no mercado varia de acordo com a qualidade de cada uma. Fitas produzidas na máquina antiga permitem um lucro de 3 u.m por mil metros de produção. Fitas cortadas na máquina mais moderna produzem um lucro de 5 u.m por mil metros de produção.
Cada mil metros de fita cortada na máquina antiga consome 3 homens x hora de mão de obra. Na máquina moderna são gastos apenas 2 homens x hora. Diariamente, são disponíveis 18 homens x hora para a operação de ambas as máquinas. Determine a produção que otimiza o lucro da metalúrgica.
O quadro Q.1 não é ótimo, pois temos na linha da função objetivo – linha 1 - dois valores negativos: -3 e -5.  O quadro é ótimo quando todos os valores, nessa linha, são positivos.
Variável que entra na coluna da base: X2 (procure o menor valor numérico)
Variável que sai da coluna da base: X4 (menor valor encontrado na divisão)
Avance a tela e monte o próximo quadro realizando a troca do anterior.
Localize no quadro anterior – na linha da variável que foi selecionada para sair da coluna da base (linha 3)  – o elemento pivô.
O elemento pivô está localizado na coluna da variável selecionada para entrar na coluna da base. 
O pivô deverá ser 1 para facilitar os cálculos.
Quando ele é 1 basta transferir a linha da variável selecionada para sair da coluna da base toda para o próximo quadro na mesma posição.
O pivô localizado no Q.1  é 1, logo a linha 3 foi toda transferida para o Q.2. A linha 3 é a linha do pivô.
Agora devemos zerar a coluna do pivô, isto é, zerar os quadrados acima e abaixo do pivô.
O quadro Q.2 não é ótimo, pois ainda temos um valor negativo na linha da função objetivo – linha 1.
 
Variável que entra na coluna da base: X1 (procure o menor valor numérico  - na linha 1: -3)
Variável que sai da coluna da base: X5 (menor valor encontrado na divisão)
Avance a tela e monte o próximo quadro – Q.3 - realizando a troca acima.
Localize no quadro anterior – Q.2 - na linha da variável que foi selecionada para sair da coluna da base (linha 4)  – o elemento pivô. 
O elemento pivô está localizado na coluna da variável selecionada para entrar na coluna da base. 
O pivô deverá ser 1 para facilitar os cálculos. Nesse caso, o pivô não é 1 e sim 3. 
A linha da variável deverá ser dividida por 3 para transformar o pivô em 1. 
Essa nova linha deverá ser transferida para o quadro Q.3 na mesma posição – linha 4. 
A linha 4 é a linha do pivô.
Problema de Minimização
E quando temos um problema de minimização?
Basta transformarmos o problema de minimização em um problema equivalente de maximização e, então, utilizamos o Simplex.
Essa transformação consiste em maximizar MENOS a função objetivo original. 
Min Z = Max (-Z)
Depois de resolvê-lo pelo Simplex, encontrando (-Z), basta trocarmos o seu sinal.
Chegamos a final da nossa aula. É importante que você tenha compreendido bem o conteúdo. Não esqueça de testar seus conhecimentos no Registro de Participação!
1.Resolva cada Problema de Programação Linear (PPL) geometricamente: Resposta D
 Parte inferior do formulário
Resolva o Problema de Programação Linear (PPL) geometricamente: Resposta C