É 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:
Montar o dual e explicar o que cada variável do dual representa.
Resolver o dual (problema de maximização com \leq) encontrando um vértice extremo ótimo.
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.
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).
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 candidatax^{*}=\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.