Uma companhia possui 3 unidades de fábricas próximas a um rio ( 1,2,3 ).
Cada uma emite dois tipos de poluentes (A e B). Se o resíduo de cada fábrica for tratado, a poluição do rio pode ser reduzida.
Custa \ 15$ para tratar uma tonelada de resíduo da fábrica 1 , e cada tonelada tratada reduz a quantidade de poluente A em 0,1 tonelada e a quantidade de poluente B em 0,45 toneladas.
Custa \ 10$ para tratar uma tonelada de resíduo da fábrica 2 , e cada tonelada tratada reduz a quantidade de poluente A em 0,2 tonelada e a quantidade de poluente B em 0,25 toneladas.
Custa \ 20 para tratar uma tonelada de resíduo da fábrica 3 , e cada tonelada tratada reduz a quantidade de poluenteíáA em 0,40 tonelada e a quantidade de poluenteB$ em 0,30 toneladas.
A companhia pretende reduzir a quantidade de poluente A no rio em pelo menos 30 toneladas e de poluente B em 40 toneladas.
Determine o custo mínimo que reduza a poluição nas quantidades desejadas.
Obs: Use os métodos ensinadas na disciplina.
A) Monte um problema de otimização.
B) Monte e simule em Scilab o problema de otimização.
(Não risque esta folha)

Passo 1

O enunciado pede para reduzir a poluição do rio tratando resíduos nas fábricas 1,2,3 ao menor custo, respeitando as metas mínimas de redução de poluentes. Perguntas explícitas do enunciado:
A) Montar um problema de otimização.
B) Montar e simular em Scilab o problema, obtendo a solução (quantas toneladas tratar em cada fábrica) e o custo mínimo.
Dados fornecidos (vou listar tudo com cuidado):
  • Variáveis (não resolvo ainda, só declaro para ficar claro): \;x_1 = toneladas tratadas na fábrica 1, \;x_2 = toneladas tratadas na fábrica 2, \;x_3 = toneladas tratadas na fábrica 3. Todas com \;x_i \ge 0.
  • Custos por tonelada: \$15 na fábrica 1, \$10 na fábrica 2, \$20 na fábrica 3.
  • Redução de poluentes por tonelada tratada:
    • Fábrica 1: reduz poluente A em 0{,}1 t/ton e B em 0{,}45 t/ton.
    • Fábrica 2: reduz A em 0{,}2 t/ton e B em 0{,}25 t/ton.
    • Fábrica 3: reduz A em 0{,}4 t/ton e B em 0{,}3 t/ton.
  • Metas: reduzir poluente A em pelo menos 30 toneladas e poluente B em pelo menos 40 toneladas.
A resolução começa de verdade no próximo passo.

Passo 2

Formulação matemática do problema (a parte solicitada em A). Vou escrever a função objetivo e as restrições claramente.
Função objetivo (minimizar custo total):
\min\; Z = 15\,x_{1} + 10\,x_{2} + 20\,x_{3}
Restrições de redução de poluentes (cada tonelada tratada contribui à redução acumulada):
0{,}1\,x_{1} + 0{,}2\,x_{2} + 0{,}4\,x_{3} \ge 30
0{,}45\,x_{1} + 0{,}25\,x_{2} + 0{,}3\,x_{3} \ge 40
Restrições de não negatividade:
x_{1} \ge 0,\quad x_{2} \ge 0,\quad x_{3} \ge 0.
Isto é um problema de programação linear (LP) com 3 variáveis e 2 desigualdades.

Passo 3

Breve aula intuitiva sobre como resolver esse LP sem programador externo (mas que também será usado para simular): por que a solução ótima aparece numa “vértice”?
  • O conjunto das soluções factíveis definido por desigualdades lineares é um poliedro convexo.
  • Em problemas de programação linear com objetivo linear, um teorema básico diz que existe uma solução ótima em algum vértice (canto) desse poliedro — ou seja, onde pelo menos m restrições são ativas (iguais), com m o número de restrições independentes (aqui m=2).
  • Logo, podemos procurar entre os pontos onde duas restrições (entre as duas de poluentes e as restrições x_i\ge0) são simultaneamente ativas. No nosso caso, os possíveis vértices úteis são: soluções onde duas das restrições (as duas de poluentes) são iguais e uma das variáveis é zero; ou pontos em que duas variáveis são zero (soluções com apenas uma variável positiva). Assim, para 3 variáveis e 2 restrições, é prático enumerar todos os casos básicos possíveis (faço isso passo a passo).

Passo 4

Estratégia de busca explícita (simplificada e prática para prova): vou enumerar as combinações possíveis de pontos básicos factíveis:
  • Casos com duas equações de poluentes ativas e uma variável igual a zero (três subcasos: x_1=0, x_2=0, x_3=0). Para cada um resolvo o sistema linear de 2\times2.
  • Casos com duas variáveis zero (três subcasos: apenas x_1>0, apenas x_2>0, apenas x_3>0). Para cada verif. a menor quantidade dessa variável que satisfaz ambas as metas (isto é, o máximo entre as exigências de A e B para essa variável).
  • Entre todos os pontos factíveis resultantes, calcule o custo e escolha o menor.
Vou agora calcular cada candidato, mostrando passo a passo as contas.

Passo 5

Caso 1: x_1=0\). Resolve-se o sistema (tirado das restrições fazendo igualdades): \[\begin{cases} 0{,}2\,x_{2} + 0{,}4\,x_{3} = 30,\\[2pt] 0{,}25\,x_{2} + 0{,}3\,x_{3} = 40. \end{cases}
Multiplico a primeira por 5\] para simplificar: \[x_{2} + 2\,x_{3} = 150. \tag{1}\] Multiplico a segunda por \(20:
5\,x_{2} + 6\,x_{3} = 800. \tag{2}
Da equação (1): x_{2} = 150 - 2x_{3}. Substituo em (2):
5(150 - 2x_{3}) + 6x_{3} = 800
750 -10x_{3} + 6x_{3} = 800
-4x_{3} = 50 \implies x_{3} = -12{,}5.
Obtemos x_{3}<0, logo esse ponto é inviável (não satisfaz x_{3}\ge0). Portanto descartamos x_1=0.]

Passo 6

Caso 2: x_2=0\). Sistema \[\begin{cases} 0{,}1\,x_{1} + 0{,}4\,x_{3} = 30,\\[2pt] 0{,}45\,x_{1} + 0{,}3\,x_{3} = 40. \end{cases}
Multiplico a primeira por (10]:
x_{1} + 4x_{3} = 300 \implies x_{1} = 300 - 4x_{3}.
Substituo na segunda:
0{,}45(300 - 4x_{3}) + 0{,}3x_{3} = 40
135 -1{,}8x_{3} + 0{,}3x_{3} = 40
135 -1{,}5x_{3} = 40 \implies -1{,}5x_{3} = -95
x_{3} = \frac{95}{1{,}5} = \frac{190}{3} \approx 63{,}3333.
Então x_{1} = 300 - 4\cdot\frac{190}{3} = \frac{140}{3} \approx 46{,}6667. Ambos não-negativos, logo ponto factível:
(x_{1},x_{2},x_{3}) = \left(\frac{140}{3},\,0,\,\frac{190}{3}\right).
Custo:
Z = 15\cdot\frac{140}{3} + 10\cdot 0 + 20\cdot\frac{190}{3} = \frac{5900}{3} \approx 1966{,}6667.]

Passo 7

Caso 3: x_3=0\). Sistema \[\begin{cases} 0{,}1\,x_{1} + 0{,}2\,x_{2} = 30,\\[2pt] 0{,}45\,x_{1} + 0{,}25\,x_{2} = 40. \end{cases}
Multiplico a primeira por (10]:
x_{1} + 2x_{2} = 300 \implies x_{1} = 300 - 2x_{2}.
Substituo na segunda:
0{,}45(300 - 2x_{2}) + 0{,}25x_{2} = 40
135 -0{,}9x_{2} + 0{,}25x_{2} = 40
135 -0{,}65x_{2} = 40 \implies -0{,}65x_{2} = -95
x_{2} = \frac{95}{0{,}65} = \frac{1900}{13} \approx 146{,}153846.
Então x_{1} = 300 - 2\cdot\frac{1900}{13} = \frac{100}{13} \approx 7{,}6923077. Ambos não-negativos, logo ponto factível:
(x_{1},x_{2},x_{3}) = \left(\frac{100}{13},\,\frac{1900}{13},\,0\right).
Custo:
Z = 15\cdot\frac{100}{13} + 10\cdot\frac{1900}{13} + 20\cdot 0 = \frac{20500}{13} \approx 1576{,}9230769.]

Passo 8

Agora os casos com duas variáveis zero (apenas uma variável positiva). Para cada variável x_i escolhemos a menor quantidade que satisfaça ambas as metas (isto é, o máximo exigido por A e por B para aquela variável).
  • Apenas x_1>0: das restrições 0{,}1x_{1} \ge 30 \implies x_{1} \ge 300,
0{,}45x_{1} \ge 40 \implies x_{1} \ge \frac{40}{0{,}45} \approx 88{,}8889.
Então o mínimo factível é x_{1}=300. Custo Z=15\cdot 300 = 4500.
  • Apenas x_2>0: 0{,}2x_{2} \ge 30 \implies x_{2} \ge 150,
0{,}25x_{2} \ge 40 \implies x_{2} \ge 160.
Então x_{2}=160 é o mínimo factível. Custo Z=10\cdot 160 = 1600.
  • Apenas x_3>0: 0{,}4x_{3} \ge 30 \implies x_{3} \ge 75,
0{,}3x_{3} \ge 40 \implies x_{3} \ge \frac{40}{0{,}3} = 133{,}333\ldots
Então x_{3} = \frac{40}{0{,}3} = \frac{400}{3} \approx 133{,}3333. Custo Z=20\cdot \frac{400}{3} = \frac{8000}{3}\approx 2666{,}6667.

Passo 9

Compilando todos os candidatos factíveis com seus custos:
  • x=(\tfrac{140}{3},0,\tfrac{190}{3}) com Z=\tfrac{5900}{3}\approx 1966{,}67.
  • x=(\tfrac{100}{13},\tfrac{1900}{13},0) com Z=\tfrac{20500}{13}\approx 1576{,}92.
  • x=(300,0,0) com Z=4500.
  • x=(0,160,0) com Z=1600.
  • x=(0,0,\tfrac{400}{3}) com Z=\tfrac{8000}{3}\approx 2666{,}67.
O menor custo entre esses é
Z_{\min} = \frac{20500}{13} \approx 1576{,}9230769,
obtido em
(x_{1},x_{2},x_{3}) = \left(\frac{100}{13},\;\frac{1900}{13},\;0\right) \approx (7{,}6923077,\;146{,}153846,\;0).
Interpretação prática: tratar aproximadamente 7{,}69 toneladas na fábrica 1 e 146{,}15 toneladas na fábrica 2, não tratar na fábrica 3, dá exatamente as metas de redução de A e B e minimiza custo.

Passo 10

Montagem da simulação em Scilab (solução solicitada em B). Abaixo um script Scilab que replica a enumeração dos vértices que fiz acima e imprime a solução ótima. Você pode copiar e colar no Scilab e executar. O script faz exatamente o que calculei: resolve sistemas 2\times2 nos casos x_i=0 e testa as soluções com duas variáveis zero.
/* Script Scilab para encontrar a solução ótima do LP do enunciado */
clear;
c = [15; 10; 20]; // custos

A = [0.1 0.2 0.4; 0.45 0.25 0.3];
b = [30; 40];

candidatos = [];
custos = [];

//
// Casos com uma variável zerada: resolver A(:,J)*xJ = b
//
/* x1 = 0 */
A12 = A(:,2:3);
x12 = A12 \ b; // resolve 2x2
x = [0; x12(1); x12(2)];
if min(x) >= -1e-8 then
    candidatos = [candidatos, x];
    custos = [custos, c' * x];
end

/* x2 = 0 */
A13 = A(:,[1,3]);
x13 = A13 \ b;
x = [x13(1); 0; x13(2)];
if min(x) >= -1e-8 then
    candidatos = [candidatos, x];
    custos = [custos, c' * x];
end

/* x3 = 0 */
A11 = A(:,1:2);
x11 = A11 \ b;
x = [x11(1); x11(2); 0];
if min(x) >= -1e-8 then
    candidatos = [candidatos, x];
    custos = [custos, c' * x];
end

//
// Casos com duas variáveis zero: apenas xi > 0
//
/* apenas x1 > 0 */
x1 = max( b(1) / A(1,1), b(2) / A(2,1) );
x = [x1; 0; 0];
candidatos = [candidatos, x];
custos = [custos, c' * x];

/* apenas x2 > 0 */
x2 = max( b(1) / A(1,2), b(2) / A(2,2) );
x = [0; x2; 0];
candidatos = [candidatos, x];
custos = [custos, c' * x];

/* apenas x3 > 0 */
x3 = max( b(1) / A(1,3), b(2) / A(2,3) );
x = [0; 0; x3];
candidatos = [candidatos, x];
custos = [custos, c' * x];

//
// Seleciona o mínimo
//
[Zmin, idx] = min(custos);
xopt = candidatos(:, idx);

disp("Solucoes candidatas (colunas):");
disp(candidatos);
disp("Custos correspondentes:");
disp(custos);
disp("Solução ótima x*:");
disp(xopt');
disp("Custo mínimo Z*:");
disp(Zmin);
Se executar, obterá (valores numéricos aproximados) a solução
x^{*} \approx (7{,}6923077,\;146{,}153846,\;0)
com custo Z^{*}\approx 1576{,}9230769. Isso confirma os cálculos manuais anteriores.

Resposta

A) Modelo LP: \min Z=15x_1+10x_2+20x_3 sujeito a \;0{,}1x_1+0{,}2x_2+0{,}4x_3\ge30,\;0{,}45x_1+0{,}25x_2+0{,}3x_3\ge40,\;x_i\ge0.
B) Solução ótima (Scilab e cálculo): (x_1,x_2,x_3)=\left(\dfrac{100}{13},\dfrac{1900}{13},0\right)\approx(7{,}6923077,\;146{,}153846,\;0) com custo mínimo Z_{\min}=\dfrac{20500}{13}\approx1576{,}9230769.

Exercícios relacionados