Questão
Considere o problema de programação linear inteira abaixo e responda:
Maximize
sujeito a:
(a) Determine a relaxação linear do problema. (b) Encontre a solução ótima da relaxação linear do problema usando o método gráfico.
(a) A relaxação linear do problema é obtida removendo a restrição de que e sejam inteiros. Assim, o problema se torna:
Maximize
sujeito a:
(b) Para encontrar a solução ótima da relaxação linear usando o método gráfico, primeiro traçamos as restrições no plano .
- A reta intercepta os eixos em (não relevante pois ) e .
- A reta intercepta os eixos em e .
O ponto de interseção das duas retas pode ser encontrado resolvendo o sistema:
-8x_1 + 10x_2 = 15 \\ 8x_1 + 6x_2 = 37 \end{cases}$$ Multiplicando a primeira equação por 4 e somando com a segunda, obtemos: $$40x_2 + 6x_2 = 97 \\ 46x_2 = 97 \\ x_2 = \frac{97}{46} \approx 2.109$$ Substituindo $x_2$ na primeira equação: $$-8x_1 + 10\left(\frac{97}{46}\right) = 15 \\ -8x_1 + \frac{970}{46} = 15 \\ -8x_1 = 15 - \frac{970}{46} \\ -8x_1 = \frac{690}{46} \\ x_1 = -\frac{690}{368} \approx 1.875$$ Portanto, o ponto de interseção é aproximadamente $(1.875, 2.109)$. Calculando $z$ neste ponto: $$z = 3(1.875) + 2(2.109) = 5.625 + 4.218 = 9.843$$ Assim, a solução ótima da relaxação linear é aproximadamente $(x_1, x_2) = (1.875, 2.109)$ com $z \approx 9.843$.(a) A relaxação linear é obtida ao permitir que as variáveis e sejam números reais não negativos, em vez de inteiros positivos. Isso simplifica o problema e permite o uso de métodos contínuos para encontrar soluções.
(b) O método gráfico envolve traçar as restrições no plano e identificar a região viável. As interseções das restrições com os eixos e entre si determinam os vértices da região viável. Calculamos o valor da função objetivo em cada vértice para encontrar o máximo. O ponto de interseção das restrições é calculado resolvendo o sistema de equações formado pelas restrições. A solução ótima é o ponto que maximiza dentro da região viável.