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 \ 20para tratar uma tonelada de resíduo da fábrica 3 , e cada tonelada tratada reduz a quantidade de poluenteAem 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):
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
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ções0{,}1x_{1} \ge 30 \implies x_{1} \ge 300,
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.