b) Minimizar \mathrm{Z}=2 x_{1}+4 x_{2}+3 x_{3}
respeitando as restrições
\left\{\begin{array}{l} 2 x_{1}+3 x_{2}-x_{3} \geq 6 \\ 2 x_{1}+2 x_{2}+3 x_{3} \geq 16 \\ x_{1}+4 x_{2}+x_{3} \geq 18 \\ x_{1}, x_{2}, x_{3} \geq 0 \end{array}\right.

Passo 1

O que o enunciado pede e as informações dadas.
  • Pede minimizar a função objetivo \mathrm{Z}=2 x_{1}+4 x_{2}+3 x_{3} sujeita às restrições
\left\{\begin{array}{l} 2 x_{1}+3 x_{2}-x_{3} \geq 6,\\[4pt] 2 x_{1}+2 x_{2}+3 x_{3} \geq 16,\\[4pt] x_{1}+4 x_{2}+x_{3} \geq 18,\\[4pt] x_{1},x_{2},x_{3}\geq 0. \end{array}\right.
  • Informações relevantes:
    • É um problema de programação linear do tipo minimização.
    • Todas as restrições são do tipo \geq e as variáveis são não negativas.
    • Não há mais informações externas (por exemplo, figura ou tabela).]

Passo 2

Estratégia que vamos usar (explicação didática do conceito que vai resolver o problema).
  • Para problemas de minimização com restrições do tipo \geq é muito prático construir o problema dual (é uma técnica padrão: resolver o dual que é um problema de maximização com \leq facilita o trabalho).
  • Teorema útil (em palavras simples): se primal e dual são factíveis, seus ótimos coincidem (forte dualidade). Além disso, usando complementaridade (complementary slackness) podemos recuperar a solução primal ótima a partir da solução ótima do dual.
  • Vou então:
    1. Montar o dual e explicar o que cada variável do dual representa.
    2. Resolver o dual (problema de maximização com \leq) encontrando um vértice extremo ótimo.
    3. Usar complementaridade para obter a solução primal ótima e o valor mínimo \mathrm{Z}_{\min}.
  • Observação de método: o dual aqui tem só 3 variáveis; podemos procurar vértices extremos (intersecções de restrições ativas) e comparar valores — é um método sistemático e adequado sem precisar do Big‑M.

Passo 3

Construção do problema dual (explicação das regras).
  • Seja y_{1},y_{2},y_{3}\) as variáveis duales associadas às três restrições, respectivamente. - Regra (explicada): para um primal na forma \[\text{min } c^{T}x\quad\text{s.a.}\quad A x \ge b,\quad x\ge0,o dual é \text{max } b^{T}y\quad\text{s.a.}\quad A^{T}y \le c,\quad y\ge0.Aqui b são os termos à direita das restrições do primal e c os coeficientes da função objetivo primal.
  • Aplicando à nossa instância:
    • b=(6,16,18)^{T}.
    • c=(2,4,3)^{T}.
    • A matriz A tem linhas correspondentes às restrições.
  • Portanto o dual é:
\text{Maximizar } W=6y_{1}+16y_{2}+18y_{3}
sujeito a
\begin{cases} 2y_{1}+2y_{2}+y_{3}\le 2,\\[4pt] 3y_{1}+2y_{2}+4y_{3}\le 4,\\[4pt] -\,y_{1}+3y_{2}+y_{3}\le 3,\\[4pt] y_{1},y_{2},y_{3}\ge 0. \end{cases}
  • Interpretação rápida: cada desigualdade acima corresponde a uma variável primal (x_{1},x_{2},x_{3}] (por ordem).]

Passo 4

Como vamos resolver o dual (ideia e justificativa passo a passo).
  • O poliedro factível do dual está em \mathbb{R}^{3} com y\ge0 e três desigualdades lineares: seus vértices extremos são intersecções de duas ou três restrições ativas (igualdades) junto com possivelmente y_i=0.
  • Como há poucas variáveis, podemos procurar vértices extremos obtendo interseções de pares de restrições (fixando uma variável igual a zero e resolvendo duas igualdades) — isso gera um conjunto pequeno de candidatos; avaliamos W em cada candidato viável e escolhemos o maior.
  • Vamos enumerar os vértices obtidos ao anular uma variável de cada vez e resolvendo as igualdades das outras duas restrições.

Passo 5

Caso 1: suprimir y_{1}=0 e resolver as duas igualdades entre as restrições restantes.
  • Com y_{1}=0 as duas primeiras restrições tornam-se: \left\{\begin{array}{l} 2y_{2}+y_{3}=2,\\[4pt] 2y_{2}+4y_{3}=4. \end{array}\right.
  • Subtraindo a primeira da segunda: 3y_{3}=2 \Rightarrow y_{3}=\dfrac{2}{3}.
  • Então 2y_{2}+\dfrac{2}{3}=2 \Rightarrow 2y_{2}=\dfrac{4}{3}\Rightarrow y_{2}=\dfrac{2}{3}.
  • Temos o ponto candidato \left(y_{1},y_{2},y_{3}\right)=\left(0,\dfrac{2}{3},\dfrac{2}{3}\right).
  • Verificar todas as desigualdades do dual:
    • Primeira: 2\cdot0+2\cdot\dfrac{2}{3}+\dfrac{2}{3}= \dfrac{4}{3}+\dfrac{2}{3}=2 \le 2 (igualdade — ok).
    • Segunda: 3\cdot0+2\cdot\dfrac{2}{3}+4\cdot\dfrac{2}{3}= \dfrac{4}{3}+\dfrac{8}{3}=4 \le 4 (igualdade — ok).
    • Terceira: -0+3\cdot\dfrac{2}{3}+\dfrac{2}{3}=2+\dfrac{2}{3}=\dfrac{8}{3}\le 3 (estritamente menor, ainda é factível).
    • Não-negatividade: todas as componentes são \ge0.
  • Calcula-se W nesse ponto: W=6\cdot0+16\cdot\dfrac{2}{3}+18\cdot\dfrac{2}{3}=\dfrac{32}{3}+\dfrac{36}{3}=\dfrac{68}{3}.]

Passo 6

Outros casos (suprimir y_{2}=0 ou y_{3}=0) e comparação.
  • Caso y_{2}=0. Resolver as duas igualdades (primeira e segunda) dá: \left\{\begin{array}{l} 2y_{1}+y_{3}=2,\\[4pt] 3y_{1}+4y_{3}=4, \end{array}\right.solução \left(y_{1},y_{3}\right)=\left(\dfrac{4}{5},\dfrac{2}{5}\right). Isso dá W=6\cdot\dfrac{4}{5}+18\cdot\dfrac{2}{5}= \dfrac{24}{5}+\dfrac{36}{5}=\dfrac{60}{5}=12, menos que \dfrac{68}{3}.
  • Caso y_{3}=0. Resolver interseções relevantes leva por exemplo ao ponto \left(0,1,0\right) com W=16, também menor.
  • Outros vértices possíveis (onde duas desigualdades entre B e C são iguais, ou vértices com duas componentes zero) foram verificados e ou são inviáveis ou geram valores menores de W.
  • Conclusão: o melhor candidato encontrado é \left(0,\dfrac{2}{3},\dfrac{2}{3}\right) com W=\dfrac{68}{3}. Como o dual é factível e encontramos um vértice extremo, esse é o ótimo do dual.]

Passo 7

Recuperando a solução primal ótima via complementaridade (explicação do conceito e aplicação).
  • Complementary slackness (regra prática): para primal x\) e dual \(y\) ótimos, vale: - Para cada restrição dual (cada variável primal \(x_{i}\)): se a desigualdade do dual associada a \(x_{i}\) for estrita (ou seja, não for igualdade), então \(x_{i}=0\). Se a desigualdade do dual for igualdade, \(x_{i}\) pode ser positiva. - Para cada variável dual \(y_{j}\): se \(y_{j}>0\) então a restrição primal \(j\) é ativa (igualdade); se \(y_{j}=0\) então a restrição primal \(j\) pode ter folga. - Aplicando ao nosso caso com \(y^{*}=(0,\tfrac{2}{3},\tfrac{2}{3})\): - Verificar desigualdades do dual: \[\begin{array}{l} 2y_{1}+2y_{2}+y_{3}=2\quad\text{(igualdade)}\\[3pt] 3y_{1}+2y_{2}+4y_{3}=4\quad\text{(igualdade)}\\[3pt] -y_{1}+3y_{2}+y_{3}=\dfrac{8}{3}<3\quad\text{(estrita)} \end{array}
    • Pelo item acima, para a terceira desigualdade estrita temos x_{3}=0.
    • Como y_{2}>0 e y_{3}>0, as restrições primais 2 e 3 são ativas (igualdades). A restrição primal 1 tem y_{1}=0, logo pode ter folga.
  • Agora imponha as restrições primais 2 e 3 como igualdades e x_{3}=0: \begin{cases} 2x_{1}+2x_{2}+3x_{3}=16,\\[4pt] x_{1}+4x_{2}+x_{3}=18,\\[4pt] x_{3}=0. \end{cases}Substituindo x_{3}=0\]: \[\begin{cases} 2x_{1}+2x_{2}=16,\\[4pt] x_{1}+4x_{2}=18. \end{cases}\] - Resolver o sistema: - Da primeira: \(x_{1}+x_{2}=8.
    - Subtrair da segunda: (x_{1}+4x_{2})-(x_{1}+x_{2})=18-8 \Rightarrow 3x_{2}=10\Rightarrow x_{2}=\dfrac{10}{3}.
    - Então x_{1}=8-\dfrac{10}{3}=\dfrac{24-10}{3}=\dfrac{14}{3}.
    - Obtém-se a solução primal candidata x^{*}=\left(\dfrac{14}{3},\dfrac{10}{3},0\right),que satisfaz x_{i}\ge0. Verifique rapidamente a primeira restrição primal (pode ter folga): 2x_{1}+3x_{2}-x_{3}=2\cdot\dfrac{14}{3}+3\cdot\dfrac{10}{3}-0=\dfrac{28+30}{3}=\dfrac{58}{3}\approx 19{,}33\ge 6,portanto está satisfeita (com folga).]

Passo 8

Calcular o valor ótimo da função objetivo primal e verificar coerência com o dual (forte dualidade).
  • Calcule \mathrm{Z} em x^{*}: \mathrm{Z}(x^{*})=2\cdot\dfrac{14}{3}+4\cdot\dfrac{10}{3}+3\cdot 0=\dfrac{28+40}{3}=\dfrac{68}{3}.
  • Este valor coincide com o valor ótimo do dual W^{*}=\dfrac{68}{3}, confirmando a optimalidade por forte dualidade.

Resposta

x_{1}=\dfrac{14}{3},\quad x_{2}=\dfrac{10}{3},\quad x_{3}=0,\quad \mathrm{Z}_{\min}=\dfrac{68}{3}

Exercícios relacionados