Resolva
Maxz z=8 x_{1}+5 x_{2}
s.a
\begin{aligned} x_{1}+x_{2} & \leq 6 \\\\ 9 x_{1}+5 x_{2} & \leq 45 \\\ x_{1}, x_{2} & \geq 0 \\\ x_{1}, x_{2} & \text { inteiros } \end{aligned}

Passo 1

O enunciado pede: maximizar a função objetivo z=8x_{1}+5x_{2} sujeita às restrições
\begin{aligned} x_{1}+x_{2} & \leq 6,\\\\ 9x_{1}+5x_{2} & \leq 45,\\\ x_{1},x_{2} & \geq 0,\\\ x_{1},x_{2} & \text{ inteiros.} \end{aligned}
Informações relevantes que temos:
\;x_{1} e \;x_{2} são variáveis inteiras não-negativas; as duas primeiras inequações definem a região viável; queremos o valor máximo de z e os valores de x_{1},x_{2} que o atingem.

Passo 2

Estratégia que vou usar (explicada como se eu estivesse te orientando na prova): primeiro resolvemos a versão relaxada (ou seja, sem a exigência de integridade — as variáveis podem ser reais) para identificar o máximo contínuo e os vértices da região viável. Isso é útil porque, para problemas lineares, o ótimo relaxado ocorre em um vértice da região poligonal. Depois, como as variáveis devem ser inteiras, fazemos uma busca discreta simples restrita aos possíveis valores inteiros (a região é pequena), comparando os valores de z. Essa abordagem é rápida em prova quando as variáveis têm limites baixos. Vou explicar cada etapa com calma.
A região viável (relaxada) é o polígono definido por x_{1}+x_{2}\leq6, 9x_{1}+5x_{2}\leq45 e x_{1},x_{2}\geq0. Os vértices possíveis vêm das interseções dessas retas/semirretas. Calculamos os vértices relevantes:
Interseção entre x_{1}+x_{2}=6 e 9x_{1}+5x_{2}=45. Substituímos x_{2}=6-x_{1} em 9x_{1}+5x_{2}=45:
9x_{1}+5(6-x_{1})=45.
Desenvolvendo,
9x_{1}+30-5x_{1}=45,
4x_{1}=15,
x_{1}=\frac{15}{4}.
Então
x_{2}=6-\frac{15}{4}=\frac{24-15}{4}=\frac{9}{4}.
Logo um vértice é \left(\frac{15}{4},\frac{9}{4}\right).
Interseções com eixos (avaliando quais são factíveis):
  • Com x_{2}=0: as restrições dão x_{1}\leq6 e 9x_{1}\leq45\Rightarrow x_{1}\leq5. Então o ponto extremo na abscissa é (5,0) (o (6,0) não é viável porque viola 9x_{1}+5x_{2}\leq45).
  • Com x_{1}=0: as restrições dão x_{2}\leq6 e 5x_{2}\leq45\Rightarrow x_{2}\leq9. Então o extremo na ordenada é (0,6).
Os vértices relevantes da região viável são, portanto:
(0,0),\quad (5,0),\quad \left(\frac{15}{4},\frac{9}{4}\right),\quad (0,6).
Calculamos z=8x_{1}+5x_{2} nesses vértices:
z(5,0)=8\cdot5+5\cdot0=40,
z\!\left(\frac{15}{4},\frac{9}{4}\right)=8\cdot\frac{15}{4}+5\cdot\frac{9}{4}=\frac{120+45}{4}=\frac{165}{4}=41{,}25,
z(0,6)=8\cdot0+5\cdot6=30,
z(0,0)=0.
Assim, o ótimo relaxado (variáveis reais) é z=41{,}25 em \left(\frac{15}{4},\frac{9}{4}\right). Como queremos variáveis inteiras, esse ponto não é admissível; precisamos procurar a melhor solução inteira na vizinhança viável.

Passo 3

Agora tratamos a versão inteira. Observação prática: x_{1} não pode exceder 5 porque 9x_{1}\leq45\Rightarrow x_{1}\leq5. Além disso x_{1}+x_{2}\leq6\Rightarrow x_{2}\leq6-x_{1}. Então x_{1} é um inteiro entre 0 e 5. Para cada inteiro x_{1} calculamos o máximo inteiro possível de x_{2} compatível com ambas as restrições:
o limite real para x_{2} é \min\!\bigl(6-x_{1},\;\frac{45-9x_{1}}{5}\bigr); o maior inteiro admissível é a parte inteira (floor) desse mínimo. Vou calcular para cada x_{1}=0,1,2,3,4,5:
  • Para x_{1}=0: x_{2}\leq\min(6,\frac{45}{5}=9)=6. Então x_{2}=6 z=8\cdot0+5\cdot6=30.
  • Para x_{1}=1: x_{2}\leq\min(5,\frac{45-9}{5}=\frac{36}{5}=7{,}2)=5. x_{2}=5 z=8\cdot1+5\cdot5=8+25=33.
  • Para x_{1}=2: x_{2}\leq\min(4,\frac{45-18}{5}=\frac{27}{5}=5{,}4)=4. x_{2}=4 z=8\cdot2+5\cdot4=16+20=36.
  • Para x_{1}=3: x_{2}\leq\min(3,\frac{45-27}{5}=\frac{18}{5}=3{,}6)=3. x_{2}=3 z=8\cdot3+5\cdot3=24+15=39.
  • Para x_{1}=4: x_{2}\leq\min(2,\frac{45-36}{5}=\frac{9}{5}=1{,}8)=1{,}8. Como x_{2} é inteiro, x_{2}\leq1. Então x_{2}=1 z=8\cdot4+5\cdot1=32+5=37.
  • Para x_{1}=5: x_{2}\leq\min(1,\frac{45-45}{5}=0)=0. Então x_{2}=0 z=8\cdot5+5\cdot0=40.
Compilando os melhores valores inteiros por x_{1}: z\in\{30,33,36,39,37,40\}. O maior é 40, obtido em (x_{1},x_{2})=(5,0).

Passo 4

Comentário didático e rápido motivo: o ponto relaxado ótimo \left(\frac{15}{4},\frac{9}{4}\right) z=41{,}25, mas não é inteiro. O ponto inteiro mais próximo em termos de componentes, (4,2), seria atraente pois 8\cdot4+5\cdot2=42, porém verifica-se que (4,2) viola a restrição 9x_{1}+5x_{2}\leq45 porque 9\cdot4+5\cdot2=36+10=46>45. Assim o melhor possível entre os inteiros viáveis é (5,0) com z=40. Dica de prova: quando as variáveis têm limites pequenos, esta enumeração controlada por x_{1} (ou x_{2}) é rápida e segura.

Resposta

x_{1}=5,\;x_{2}=0
z_{\max}=40

Exercícios relacionados