UNIVERSIDADE POLITÉCNICA
INSTITUTO SUPERIOR ABERTO
Licenciatura em Administração e Gestão de Empresas
Disciplina: Investigação Operacional
Método Simplex
Tutor: Momade Amisse Assane
04 de Maio a 29 de Junho de 2024
Método Simplex
É uma técnica utilizada para se achar, numericamente, a solução óptima de um modelo de
Programação Linear.
Solução básica
Uma solução básica é uma solução em ponto extrema aumentada.
Solução aumentada
Uma solução aumentada é uma solução para as variáveis originais (variáveis de decisão) que
foi aumentada pelos valores correspondentes das variáveis de folga.
Exemplo:
Forma original do modelo
Maximizar
Sujeito a {
Forma aumentada do modelo
Maximizar
Sujeito a {
Onde e são variáveis de folga.
Propriedades da solução básica
Uma solução básica possui as seguintes propriedades:
Cada variável é designada como uma variável básica ou uma variável não básica.
O número de variáveis básicas é igual ao número de restrições funcionais (equações).
Portanto, o número de variáveis não básicas é igual ao número total de variáveis menos o
número de restrições funcionais.
As variáveis não básicas são configuradas em zero.
Os valores das variáveis básicas são obtidos como a solução simultânea das equações
(restrições funcionais na forma aumentada). (O conjunto de variáveis básicas é normalmente
conhecido como base).
Se as variáveis satisfizerem as restrições de não negatividade, a solução básica é uma
solução básica viável.
2
Forma tabular do Método Simplex
A forma tabular do Método Simplex regista somente as informações essenciais, tais como:
Os coeficientes das variáveis;
As constantes dos lados direitos (soluções) das equações;
A variável básica que aparece em cada equação.
Passos do Método Simplex
Determine a variável básica que entra selecionando a variável (automaticamente uma
variável não básica) com o coeficiente negativo.
Determine a variável básica que sai aplicando o teste da razão mínima.
Selecione cada coeficiente na coluna pivó que seja estritamente positivo (Maior que
zero);
Divida cada um dos coeficientes da coluna denominada lado direito pelos coeficientes
da coluna pivó nas respectivas linhas;
Identifique a linha que possui o menor valor dessas razões;
A variável básica para esta linha é a variável básica que sai, portanto, substitua-a pela
variável básica que entra na coluna variável básica da próxima tabela simplex.
Achar a nova solução da variável básica usando operações elementares em linhas.
As operações elementares em linhas especificas que precisam ser realizadas são indicadas a
seguir:
Divida a linha pivó pelo número pivó. Use uma nova linha pivó nos passos e .
Para cada outra linha (inclusive a linha 1) que possua um coeficiente negativo na coluna
pivó, adicione a essa linha o produto do valor absoluto desse coeficiente pela nova linha pivó.
Para cada outra linha que tiver um coeficiente positivo na coluna pivo, subtraia dessa
linha o produto desse coeficiente pela nova linha pivó.
Observe os valores das restantes constantes destes cálculos. Se todos os valores da linha
da função objectivo forem positivos, então a solução achada é óptima. Se ao menos um dos
parâmetros for negativo, devem-se repetir todos os passos.
3
Exemplos:
Maximizar a função , pelo método simplex
Sujeito a {
Igualar a função objectivo a zero e transformar as restrições em igualdades adicionando
as folgas (onde , e são variáveis de folga).
Montagem da primeira tabela
Para montar a tabela simplex, colocamos os coeficientes das variáveis na
mesma.
Variável Solução
básica
Linha z
Linha
Linha
Linha
Observação: A coluna é coluna pivó e a linha é linha pivó, e são obtidas a partir do
valor mais negativo da linha , sempre sinalizadas como ilustra a tabela acima.
Definir o critério da variável não básica que vai entrar na base e a variável básica que vai
sair da base.
A variável não básica que vai entrar na base consiste em escolher o menor valor da linha da
função objectivo, neste caso ( e esta coluna chama-se coluna pivó.
Para definir a variável que vai sair da base, aplica-se o critério do quociente (ou critério da
razão), que consiste em dividir os elementos da coluna solução pelos elementos positivos da
coluna pivó (exceptuando os elementos negativos e zero) e escolhe-se o menor valor do
quociente efectuado, ou seja, ( ) ( . Desta forma o menor
entre os quocientes efectuados é , dai que temos a linha pivó a linha da folga , sendo
elemento comum entre a linha pivó e a coluna pivó, o elemento 2 e é chamado elemento
pivó.
4
Zerar os elementos da coluna pivó e transformar o elemento pivó em um, para isso, temos:
Nova linha Linha actual Linha pivo, isto é, Linha
Linha e Linha
Linha pivó ( ) é a divisão de todos os elementos da linha pivó pelo elemento pivó (elemento
comum entre a linha pivó e a coluna pivó).
Observação:
Os elementos da linha pivó são também elementos da variável que entra na base.
( ) ( )
( ( ( ) ( (
(
entra na base e sai da base
Montagem da Segunda Tabela
Variável Solução
básica
Como a função objectivo tem um valor negativo, repetimos todos os procedimentos dos
passos anteriores, escolhendo a variável não básica que entra na base e a variável básica que
sai da base, isso consiste primeiramente em escolher o menor valor da linha da função
objectivo neste caso ( e a regra do quociente para os valores relacionados com os valores
da coluna solução. Portanto, entra na base e sai da base.
Nova linha pivó: ( ) (
( ) ( . Assim, temos dois valores menores, deste modo levamos
a última linha, pois o elemento comum é um e não precisa ser transformado.
Nova linha Z:
( ( (
(
( ) (
( ) ( )
5
( ) ( )
( )
( ) (
( ) ( ) ( ) ( )
( )
Montagem da Terceira Tabela
Variável Solução
básica
Como a linha não tem valor negativo, então a solução do problema é , onde
e
Verificação:
Substituindo os valores de e na função objectivo, resulta:
Maximizar a função abaixo pelo método simplex
Maximizar
S.a {
Resolução
Forma aumentada
Sujeito a {
6
Primeira tabela
Variável Solução
básica
Linha Z
Linha
Linha
Teste de quociente (ou teste da razão), para analisar a variável que sai da base e a variável
que entra na base.
( ) ( ),
sai da base e entra na base
Cálculo da linha pivó:
Dividimos todos os elementos da linha pivó pelo elemento pivó
( ) ( )
Cálculo da nova linha
Nova linha Linha actual ( ( ( )
Nova linha ( ( ) ( )
Cálculo da nova linha
Nova linha Linha actual ( ( )
( ( ) ( ( )
( )
Segunda tabela
Variável Solução
básica
Teste de quociente, para analisar a variável que sai e entra na base.
7
( ) ( , O valor mínimo do quociente entre os elementos da coluna
solução e a coluna pivó, corresponde a variável que sai da base. deste modo sai da base e
entra na base.
Cálculo da nova linha pivó:
( ) ( )
Cálculo da nova linha
Nova linha ( )
( ) ( ) ( )
Cálculo da nova linha
Nova linha Linha actual
( ) ( ) ( ) ( )
( )
Terceira tabela
Variável Solução
básica
Como na linha Z não tem número negativo, a solução óptima é , com
Verificação
Substituindo e na função Objectivo, resulta:
8
Actividades
Considere o seguinte problema e resolva
Maximizar
Sujeito a {
Pelo método gráfico Pelo método simplex
Considere o seguinte problema e resolva
Maximizar
Sujeito a {
Pelo método gráfico Pelo método simplex
Considere o seguinte problema e resolva
Maximizar
Sujeito a {
Pelo método gráfico Pelo método simplex