( 0.5 pontos) Dado um problema de minimização, no método dual simplex, podemos verificar se uma solução é dual viável quando todos os valores dos custos reduzidos são não-negativos.
Passo 1
O enunciado dá uma afirmação sobre o método dual simplex aplicada a um problema de minimização e pede que verifiquemos se ela é verdadeira ou falsa. A afirmação é: “Dado um problema de minimização, no método dual simplex, podemos verificar se uma solução é dual viável quando todos os valores dos custos reduzidos são não-negativos.”
Informações relevantes do enunciado:
Informações relevantes do enunciado:
- O problema é de minimização.
- A afirmação refere-se ao método dual simplex.
- A condição proposta para dual viabilidade é: todos os custos reduzidos são não-negativos.
Passo 2
Vamos definir com calma os objetos que vamos usar (sem pular etapas). Considere o problema primal na forma canônica para minimização:
onde
é uma matriz
,
,
.
Explicando cada coisa:
Explicando cada coisa:
-
é o vetor de variáveis que queremos escolher. -
são as restrições lineares em forma de igualdade (padrão do simplex). -
indica que cada componente de é não-negativa.
No simplex trabalhamos com uma base(colunas de correspondentes às variáveis básicas) e as não-básicas.
Passo 3
Definições importantes que precisamos entender:
-
é a matriz formada pelas colunas básicas de . é e assumimos invertível. -
é o vetor dos custos (componentes de ) correspondentes às variáveis básicas. - Para uma coluna não-básica
, denote a coluna de e o custo associado. - As variáveis básicas valem
. Se alguma componente de for negativa, a solução é primalmente inviável (situação típica do dual simplex). - Definimos a solução dual associada à base por
Aqui
é o vetor de variáveis duais construído a partir da base atual. Vou explicar por que isso aparece.
Passo 4
Agora definimos o custo reduzido (ou custo relativo) de uma coluna não-básica
. A fórmula é
Explicando os termos:
-
é o custo original da variável . -
é o preço sombra (valor dual) associado à coluna . - Assim
mede quanto a função objetivo varia (no sentido da minimização) se aumentarmos a variável não-básica a partir de zero, mantendo as básicas ajustadas para preservar .
Passo 5
Relação com a dualidade e a verificação de viabilidade dual. O problema dual do LP dado é
Uma solução
é dualmente viável se e somente se todas as desigualdades
forem satisfeitas. Reescrevendo essa condição componente a componente:
Mas observe que
é exatamente
. Portanto a condição
é equivalente a:
Concluímos: dado o vetor dual
definido por
, a base atual é dualmente viável se e só se todos os custos reduzidos
são não-negativos.
Passo 6
Interpretação na prática do método dual simplex:
- No método dual simplex começamos normalmente com uma base que é dualmente viável (
para todas as ), mas primalmente inviável (alguma componente de é negativa). - O critério de pivô do dual simplex escolhe uma variável básica com valor negativo para deixar a base (corrige primal inviabilidade) e realiza pivôs que preservam a dualidade (mantêm
para todas as não-básicas após cada pivô).
Portanto, verificar se todos os custos reduzidos são não-negativos é exatamente o mesmo que verificar se a solução é dualmente viável.
Passo 7
Observação sobre o sinal: tudo acima está escrito para o caso de minimização com a forma canônica
. Se você estivesse resolvendo um problema de maximização com a formulação padrão do simplex, o critério de otimalidade (e, consequentemente, a condição de viabilidade dual) muda de sinal — por isso é importante sempre saber se o problema é min ou max e qual é a forma canônica usada. No enunciado o problema é de minimização, então a condição de
é a correta.
Resposta
Verdadeiro.