( 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:
  • 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:
\begin{aligned} \text{minimizar } & c^T x\\\ \text{sujeito a } & A x = b\\\ & x \ge 0, \end{aligned}
onde A é uma matriz m\times n, b\in\mathbb{R}^m, c\in\mathbb{R}^n.
Explicando cada coisa:
  • x é o vetor de variáveis que queremos escolher.
  • A x = b são as restrições lineares em forma de igualdade (padrão do simplex).
  • x \ge 0 indica que cada componente de x é não-negativa.
    No simplex trabalhamos com uma base B (colunas de A correspondentes às variáveis básicas) e as não-básicas.

Passo 3

Definições importantes que precisamos entender:
  • B é a matriz formada pelas colunas básicas de A. B é m\times m e assumimos invertível.
  • c_B é o vetor dos custos (componentes de c) correspondentes às variáveis básicas.
  • Para uma coluna não-básica j, denote a_j a coluna j de A e c_j o custo associado.
  • As variáveis básicas valem x_B = B^{-1} b. Se alguma componente de x_B for negativa, a solução é primalmente inviável (situação típica do dual simplex).
  • Definimos a solução dual associada à base por
y^T = c_B^T B^{-1}.
Aqui y\in\mathbb{R}^m é 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 j. A fórmula é
\bar c_j = c_j - y^T a_j.
Explicando os termos:
  • c_j é o custo original da variável x_j.
  • y^T a_j é o preço sombra (valor dual) associado à coluna a_j.
  • Assim \bar c_j mede quanto a função objetivo varia (no sentido da minimização) se aumentarmos a variável não-básica x_j a partir de zero, mantendo as básicas ajustadas para preservar Ax=b.

Passo 5

Relação com a dualidade e a verificação de viabilidade dual. O problema dual do LP dado é
\begin{aligned} \text{maximizar } & b^T y\\\ \text{sujeito a } & A^T y \le c. \end{aligned}
Uma solução y é dualmente viável se e somente se todas as desigualdades A^T y \le c forem satisfeitas. Reescrevendo essa condição componente a componente:
c_j - a_j^T y \ge 0\quad\text{para todo } j.
Mas observe que c_j - a_j^T y é exatamente \bar c_j. Portanto a condição A^T y \le c é equivalente a:
\bar c_j \ge 0\quad\text{para todo } j.
Concluímos: dado o vetor dual y definido por y^T = c_B^T B^{-1}, a base atual é dualmente viável se e só se todos os custos reduzidos \bar c_j 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 ( \bar c_j \ge 0 para todas as j), mas primalmente inviável (alguma componente de x_B = B^{-1} b é 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 \bar c_j \ge 0 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 Ax=b,\;x\ge0. 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 \bar c_j \ge 0 é a correta.

Resposta

Verdadeiro.

Exercícios relacionados