(1.5 pontos) Considere o problema de maximização a seguir. Seja w a variável dual associada à primeira restrição. Encontre o dual do problema e, em seguida, marque a opção correta.
\begin{aligned} \max & 7 x_{1}+5 x_{2} \\\ \text { sa } & x_{1}-x_{2} \geq 10 \\\ & x_{1} \leq 0 \\\ & x_{2} \geq 0 \end{aligned}
A. (\mathrm{w}=-5) é uma solução viável para o dual com custo -50.
B. A função objetiva do dual é min 7 w
C. Soluções viáveis precisam satisfazer ( w \geq 5 ).
D. O problema dual é inviável.
E. w é uma variável não-negativa.

Passo 1

O enunciado pede: encontrar o dual do problema primal abaixo (sendo w a variável dual associada à primeira restrição) e, a partir disso, escolher qual das opções (A–E) é correta.
Dados do primal:
\begin{aligned} \max\\ & 7 x_{1}+5 x_{2}\\\ \text{s.a. } & x_{1}-x_{2}\geq 10\\\ & x_{1}\leq 0\\\ & x_{2}\geq 0 \end{aligned}
Informações relevantes extraídas do enunciado:
  • A primeira restrição tem lado direito 10 e é do tipo \geq (essa é a restrição associada à variável dual w).
  • A segunda restrição é x_{1}\leq 0.
  • A terceira restrição é x_{2}\geq 0.
  • O objetivo é maximizar; portanto o dual será um problema de minimização.

Passo 2

Regra prática para construir o dual (explicação didática):
  • Cada restrição do primal gera uma variável do dual; o sinal da variável do dual depende do tipo da restrição primal:
    • se a restrição primal é \leq então a variável dual é \geq 0;
    • se a restrição primal é \geq então a variável dual é \leq 0;
    • se a restrição primal é igualdade, a variável dual é livre.
  • Cada variável do primal gera uma restrição no dual; o tipo dessa restrição depende do sinal da variável primal:
    • se x_j\ge 0 (primal) então a restrição dual correspondente é do tipo \geq;
    • se x_j\le 0 então a restrição dual correspondente é do tipo \leq;
    • se x_j é livre então a restrição dual é igualdade.
  • O vetor de termos independentes do dual vem dos lados direitos das restrições do primal; o objetivo do dual será minimizar a combinação linear desses lados direitos pelas variáveis dual.
Vou aplicar essas regras passo a passo ao problema.

Passo 3

Definimos variáveis do dual:
  • w associado à primeira restrição x_{1}-x_{2}\geq 10.
  • Chamo y_{2} a variável dual associada à segunda restrição x_{1}\leq 0.
  • Chamo y_{3} a variável dual associada à terceira restrição x_{2}\geq 0.
Agora determinamos os sinais das variáveis dual pelos tipos das restrições primais:
  • A primeira restrição é do tipo \geq, portanto w \leq 0.
  • A segunda restrição é do tipo \leq, portanto y_{2} \geq 0.
  • A terceira restrição é do tipo \geq, portanto y_{3} \leq 0.

Passo 4

Montamos a função objetivo do dual: é a minimização da combinação linear dos lados direitos do primal pelos coeficientes das variáveis dual. Os lados direitos do primal são 10, 0 e 0 (das restrições 1, 2 e 3, respectivamente). Então a função objetivo do dual é
\min\\\ 10\,w + 0\cdot y_{2} + 0\cdot y_{3},
que simplifica para
\min\\\ 10\,w.

Passo 5

Montamos as restrições do dual (uma por cada variável primal), usando os coeficientes das restrições do primal:
Para x_{1}: os coeficientes nas três restrições do primal são 1 (primeira), 1 (segunda) e 0 (terceira). Como x_{1}\leq 0 (variável primal não-positiva), a restrição dual correspondente é do tipo \leq. O termo do objetivo primal correspondente a x_{1} é 7. Logo a restrição é
w + y_{2} \leq 7.
Para x_{2}: os coeficientes nas três restrições do primal são -1 (primeira), 0 (segunda) e 1 (terceira). Como x_{2}\geq 0 (variável primal não-negativa), a restrição dual correspondente é do tipo \geq. O termo do objetivo primal correspondente a x_{2} é 5. Logo a restrição é
-\,w + y_{3} \geq 5.

Passo 6

Listando o dual completo com as restrições de sinal:
\begin{aligned} \min\\ & 10\,w\\\ \text{s.a. } & w + y_{2} \leq 7\\\ & -w + y_{3} \geq 5\\\ & w \leq 0,\quad y_{2}\geq 0,\quad y_{3}\leq 0. \end{aligned}
(Isto é o dual correto do primal dado.)

Passo 7

Análise de viabilidade e implicações úteis para responder as alternativas (explicando passo a passo):
Da segunda restrição do dual:
-\,w + y_{3} \geq 5 \quad\Longrightarrow\quad y_{3} \geq 5 + w.
Mas sabemos que y_{3}\leq 0. Portanto é necessário que
5 + w \leq 0 \quad\Longrightarrow\quad w \leq -5.
Da primeira restrição:
w + y_{2} \leq 7 \quad\Longrightarrow\quad y_{2} \leq 7 - w,
e como y_{2}\ge 0 isso impõe 7-w\ge 0 ou w\le 7, que é menos restritivo que w\le -5. Assim a condição essencial para existência de soluções viáveis é w\le -5. Portanto o dual tem soluções viáveis (por exemplo w=-5 com y_{2}=0 e y_{3}=0 é factível).

Passo 8

Análise do objetivo (unboundedness): a função objetivo é \min 10\,w. Como as soluções factíveis satisfazem w\le -5 e não há limite inferior para w nas restrições (podemos tomar w arbitrariamente negativo e ajustar y_{3} para igualar 5+w, que fica também arbitrariamente negativo e é permitido porque y_{3}\le 0), o valor objetivo pode ficar arbitrariamente pequeno (tender a -\infty). Portanto o dual é factível e ilimitado abaixo (infinitamente negativo).

Passo 9

Verificação das alternativas:
A. Diz: (w=-5) é uma solução viável para o dual com custo -50.
  • Teste: tomando w=-5, escolher y_{2}=0 e y_{3}=0.
    • Primeira restrição: w+y_{2}=-5+0=-5\le 7 ok.
    • Segunda restrição: -w+y_{3}=5+0=5\ge 5 ok.
    • Sinais: w=-5\le 0, y_{2}=0\ge0, y_{3}=0\le0. Tudo ok.
    • Custo: 10\,w = 10\cdot(-5) = -50.
      Logo A é verdadeira.
B. Diz: A função objetiva do dual é \min 7 w.
  • Pelo passo 4 a função objetiva é \min 10 w. Logo B é falsa.
C. Diz: Soluções viáveis precisam satisfazer w\ge 5.
  • Pelo passo 7 vimos que soluções viáveis exigem w\le -5. Logo C é falsa.
D. Diz: O problema dual é inviável.
  • Pelo passo 7 exibimos uma solução factível ( w=-5,y_{2}=0,y_{3}=0), portanto o dual é viável. D é falsa.
E. Diz: w é uma variável não-negativa.
  • Pelo passo 3 vimos w\le 0 (não-positiva). Logo E é falsa.

Resposta

A

Exercícios relacionados