Solucione pelo método simplex, em sua forma de algoritmo, os problemas de otimização linear a seguir, indicando o valor ótimo
da função objetivo, o valor ótimo
do vetor de variáveis de decisão e a base ótima
. Indique, em cada caso, se a solução é ótima finita única, ótima finita múltipla ou ilimitada. Caso seja múltipla ou ilimitada, mostre o formato geral da solução, tanto para as variáveis de decisão quanto para a função objetivo. Compare, caso possível, cada iteração com os vértices encontrados na respectiva solução geométrica do mesmo problema.
suj a
suj a
Passo 1
O enunciado pede: resolver por simplex (algoritmo) o problema de programação linear e indicar (1) o valor ótimo
, (2) o vetor ótimo
das variáveis de decisão, (3) a(s) base(s) ótima(s)
, e (4) se a solução é ótima finita única, ótima finita múltipla ou ilimitada. Se for múltipla ou ilimitada, mostrar a forma geral da solução (variáveis e função objetivo).\n
Informações dadas:
Informações dadas:
Passo 2
Passo inicial: transformar para a forma padrão (igualdades) adicionando variáveis de folga (slack)
A função objetivo em forma de equação (para o tableau) é
Inicialmente escolhemos a base formada pelas folgas
,
,
,
.]
Passo 3
Breve explicação do método simplex (algoritmo) que vou usar, passo a passo (sem pular etapas):
- Montamos o tableau com variáveis na ordem
e o RHS. - A linha da função (linha
) está na forma . No critério de entrada, para maximização, escolhemos a variável não-básica com coeficiente negativo mais “favorável” na linha (pois esse coeficiente indica quanto aumenta ao aumentar a variável). - Para a variável escolhida como entrante, aplicamos o teste da razão mínima
para decidir qual variável básica sai (garante factibilidade). - Fazemos pivot (normalização da linha pivô e eliminação nas outras linhas).
- Repetimos até que não haja coeficientes negativos na linha
(condição de otimalidade para maximização com esta convenção). - Se na otimalidade existir alguma variável não-básica com coeficiente zero na linha
, então há soluções ótimas múltiplas ao longo de um segmento; se alguma coluna permitir razão mínima infinita (nenhuma entrada positiva), o problema é ilimitado.
Passo 4
Tableau inicial (base
, ordem das colunas
):
A solução básica atual é
com
.
Passo 5
Olho a linha
: coeficientes
. Para maximização escolho a variável com coeficiente mais negativo:
(coeficiente
) como entrante.
Teste de razão para coluna
(considero apenas linhas com coeficiente positivo na coluna):
A menor razão é
(linha de
), logo
sai; pivot em posição linha
, coluna
.
Fazendo operações de linha (dividir a linha pivô por 1 e zerar a coluna nas outras linhas) obtemos o novo tableau:
Interpretação imediata: nova solução básica (com
,
por serem não-básicas) é
,
,
, com
RHS da linha
=
. Geometricamente, o simplex saiu do vértice
e foi para o vértice
.
Passo 6
Na linha
os coeficientes agora são
. Procuramos coeficientes negativos para maximizar; o mais negativo é
associado a
. Logo
entra.
Teste de razão na coluna
(apenas linhas com coeficiente positivo):
Menor razão é
(linha de
), então
sai; pivot na entrada (linha
, coluna
).
Normalizando a linha
e eliminando a coluna
nas outras linhas, obtemos o tableau final:
Agora a linha
não tem coeficientes negativos nas colunas de variáveis originais
(todos são zero nesta forma), portanto a condição de otimalidade é satisfeita: chegamos a uma solução ótima.
A solução básica correspondente (colocando as não-básicas igual a zero: aqui as não-básicas são
) é
com valor objetivo
Geometricamente, o simplex passou pelos vértices
.
Passo 7
Na tabela final, observe que a coluna de
na linha
tem coeficiente zero (entrada
). Isso significa que a variável não-básica
tem custo reduzido zero: podemos aumentar
sem alterar o valor de
até que alguma variável básica fique em zero (restrição de factibilidade). Vamos explorar esse movimento:
Usando o sistema representado pelo tableau final (leitura das equações básicas):
Se fixarmos as folgas
(mantendo as correspondentes não-básicas como zero) e deixarmos
variável, as equações reduzem para
Para manter factibilidade precisamos de
, logo
. Assim obtemos um conjunto de soluções factíveis e todas com mesmo valor objetivo
. Portanto as soluções ótimas são infinitas ao longo do segmento parametrizado por
:
e para todo
neste intervalo
. Verificação rápida nas restrições:
ou seja, todas as soluções do tipo acima são factíveis e de mesma qualidade. Em particular os extremos do segmento são:
Conclusão: existe uma aresta do politopo ótimo entre os dois vértices acima; o simplex encontrou um dos vértices extremos e a tabela revela a existência de ótimos múltiplos (coeficiente zero para variável não-básica).]
Passo 8
- Valor ótimo:
. - Conjunto de soluções ótimas (infinitas):
. - Uma base ótima encontrada pelo simplex é
(índices na ordem que usamos). Outro vértice ótimo extremo tem base (índices ). - Tipo de solução: ótima finita múltipla (infinitas soluções ótimas ao longo de um segmento).
Resposta
Solução ótima: ótima finita múltipla.