(1.5 pontos) Considere o problema de maximização a seguir. Seja
a variável dual associada à primeira restrição. Encontre o dual do problema e, em seguida, marque a opção correta.
A.
é 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 (
).
D. O problema dual é inviável.
E. w é uma variável não-negativa.
B. A função objetiva do dual é min 7 w
C. Soluções viáveis precisam satisfazer (
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
a variável dual associada à primeira restrição) e, a partir disso, escolher qual das opções (A–E) é correta.
Dados do primal:
Informações relevantes extraídas do enunciado:
- A primeira restrição tem lado direito
e é do tipo (essa é a restrição associada à variável dual ). - A segunda restrição é
. - A terceira restrição é
. - 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 é
então a variável dual é ; - se a restrição primal é
então a variável dual é ; - se a restrição primal é igualdade, a variável dual é livre.
- se a restrição primal é
- Cada variável do primal gera uma restrição no dual; o tipo dessa restrição depende do sinal da variável primal:
- se
(primal) então a restrição dual correspondente é do tipo ; - se
então a restrição dual correspondente é do tipo ; - se
é livre então a restrição dual é igualdade.
- se
- 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:
-
associado à primeira restrição . - Chamo
a variável dual associada à segunda restrição . - Chamo
a variável dual associada à terceira restrição .
Agora determinamos os sinais das variáveis dual pelos tipos das restrições primais:
- A primeira restrição é do tipo
, portanto - A segunda restrição é do tipo
, portanto - A terceira restrição é do tipo
, portanto
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
,
e
(das restrições 1, 2 e 3, respectivamente). Então a função objetivo do dual é
que simplifica para
Passo 5
Montamos as restrições do dual (uma por cada variável primal), usando os coeficientes das restrições do primal:
Para
: os coeficientes nas três restrições do primal são
(primeira),
(segunda) e
(terceira). Como
(variável primal não-positiva), a restrição dual correspondente é do tipo
. O termo do objetivo primal correspondente a
é
. Logo a restrição é
Para
: os coeficientes nas três restrições do primal são
(primeira),
(segunda) e
(terceira). Como
(variável primal não-negativa), a restrição dual correspondente é do tipo
. O termo do objetivo primal correspondente a
é
. Logo a restrição é
Passo 6
Listando o dual completo com as restrições de sinal:
(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:
Mas sabemos que
. Portanto é necessário que
Da primeira restrição:
e como
isso impõe
ou
, que é menos restritivo que
. Assim a condição essencial para existência de soluções viáveis é
. Portanto o dual tem soluções viáveis (por exemplo
com
e
é factível).
Passo 8
Análise do objetivo (unboundedness): a função objetivo é
. Como as soluções factíveis satisfazem
e não há limite inferior para
nas restrições (podemos tomar
arbitrariamente negativo e ajustar
para igualar
, que fica também arbitrariamente negativo e é permitido porque
), o valor objetivo pode ficar arbitrariamente pequeno (tender a
). Portanto o dual é factível e ilimitado abaixo (infinitamente negativo).
Passo 9
Verificação das alternativas:
A. Diz:
é uma solução viável para o dual com custo
.
- Teste: tomando
, escolher e . - Primeira restrição:
ok. - Segunda restrição:
ok. - Sinais:
, , . Tudo ok. - Custo:
.
Logo A é verdadeira.
- Primeira restrição:
B. Diz: A função objetiva do dual é
.
- Pelo passo 4 a função objetiva é
. Logo B é falsa.
C. Diz: Soluções viáveis precisam satisfazer
.
- Pelo passo 7 vimos que soluções viáveis exigem
. Logo C é falsa.
D. Diz: O problema dual é inviável.
- Pelo passo 7 exibimos uma solução factível (
), portanto o dual é viável. D é falsa.
E. Diz:
é uma variável não-negativa.
- Pelo passo 3 vimos
(não-positiva). Logo E é falsa.
Resposta
A