Exemplo 10: A Blacktop Refining extrai minerais de minérios provenientes de dois locais diferentes em Montana.
- Cada tonelada do minério tipo 1 contém
de cobre,
de zinco e
de magnésio.
- Cada tonelada do minério tipo 2 contém
de cobre,
de zinco e
de magnésio.
O minério tipo 1 custa US
120) por tonelada.
A Blacktop deseja comprar minério suficiente para extrair pelo menos 8 toneladas de cobre, 6 toneladas de zinco e 5 toneladas de magnésio, da maneira menos custosa possível.
Questões: a. Formule um modelo de programação linear (PL) para este problema. b. Esboce a região viável para este problema. c. Encontre a solução ótima.
Passo 1
O enunciado pede três coisas:
a. Formular um modelo de programação linear (PL) que minimize o custo de compra dos dois tipos de minério, garantindo pelo menos as quantidades mínimas de metais extraídos;
b. Esboçar a região viável do PL;
c. Encontrar a solução ótima (quantidade de cada minério a comprar e custo mínimo).
a. Formular um modelo de programação linear (PL) que minimize o custo de compra dos dois tipos de minério, garantindo pelo menos as quantidades mínimas de metais extraídos;
b. Esboçar a região viável do PL;
c. Encontrar a solução ótima (quantidade de cada minério a comprar e custo mínimo).
Dados fornecidos (vou listar exatamente os números do enunciado):
- Teor por tonelada do minério tipo 1:
- cobre:
- zinco:
- magnésio:
- cobre:
- Teor por tonelada do minério tipo 2:
- cobre:
- zinco:
- magnésio:
- cobre:
- Preço:
- minério tipo 1: US$
por tonelada - minério tipo 2: US$
por tonelada
- minério tipo 1: US$
- Necessidades mínimas:
- cobre: pelo menos
toneladas - zinco: pelo menos
toneladas - magnésio: pelo menos
toneladas
- cobre: pelo menos
Estas são todas as informações relevantes do enunciado.
Passo 2
Escolha de variáveis (muito importante em PL):
- Seja
a quantidade (em toneladas) do minério tipo 1 a comprar. - Seja
a quantidade (em toneladas) do minério tipo 2 a comprar.
Explicação do porquê: cada tonelada de minério fornece certas frações (percentuais) de metal; multiplicando a quantidade de tonelada pelo percentual (como número decimal) obtemos toneladas do metal extraído.
Conversão dos percentuais em coeficientes decimais:
Agora transformamos cada exigência mínima em uma desigualdade linear:
- Cobre: cada tonelada de tipo 1 dá
t de cobre e cada tonelada de tipo 2 dá t. Queremos pelo menos t: - Zinco: cada tonelada de tipo 1 dá
t e tipo 2 dá t; pelo menos t: - Magnésio: cada tonelada de tipo 1 dá
t e tipo 2 dá t; pelo menos t:
Condição natural de não negatividade:
Passo 3
Função objetivo (o que queremos minimizar):
- Custo total
custo por tonelada do tipo 1 vezes mais custo por tonelada do tipo 2 vezes . - Isto é:
Explanação: minimizar
significa comprar as quantidades de
que satisfazem todas as restrições e que produzem o menor gasto possível.
Passo 4
Modelo de programação linear completo (resposta da alínea a):
sujeito a
Passo 5
Como esboçar a região viável (resposta da alínea b) — procedimento e cálculos para desenhar as linhas limites:
Regra prática: para esboçar cada desigualdade do tipo
no primeiro quadrante, primeiro desenha-se a reta de igualdade
encontrando os interceptos com os eixos e depois determina-se qual lado da reta satisfaz a desigualdade (testando um ponto simples, normalmente
ou outro).
Vamos obter os interceptos (quando
e quando
) para cada reta:
-
Reta do cobre:
. - Se
: . - Se
:
- Se
-
Reta do zinco:
. - Se
: . - Se
: .
- Se
-
Reta do magnésio:
. - Se
: - Se
: .
- Se
Para saber para que lado da reta é a região viável (o semiplano que satisfaz
), teste o ponto
:
- Para cobre:
→ NÃO satisfaz, logo a região viável está do outro lado da reta (o lado mais afastado da origem). - Mesma conclusão para as outras duas restrições (todas têm RHS positivo e LHS em
é zero), então para cada reta o semiplano viável é o que está “para cima/à direita” da reta.
Portanto, ao desenhar no primeiro quadrante as três retas com os interceptos acima, a região viável é a interseção dos três semiplanos “acima/à direita” dessas retas. Essa região é não-vazia e é um conjunto convexo cujo bordo “inferior” (a fronteira mais próxima da origem) é formado por segmentos das retas, com vértices onde duas dessas retas (ou uma reta e um eixo) se intersectam. A região é não limitada (estende-se para cima/à direita), mas tem um “recanto” inferior com vértices que vamos agora determinar.
Passo 6
Encontrar os pontos extremo candidatos (vértices) — interseções das retas entre si e com os eixos, com cálculo passo a passo:
Interseções entre pares de restrições (resolver sistemas de duas equações lineares):
- Interseção entre cobre e zinco:
Subtraindo a segunda da primeira:
Substituindo em, por exemplo, a primeira:
Resultado: [(x_1,x_2)=(-20,40)), que é inválido pois
. Portanto essa interseção não pertence ao primeiro quadrante e não é um vértice viável.
- Interseção entre cobre e magnésio:
Multiplique a segunda equação por
:
Subtraindo a primeira (aqui: segunda vezes 3 menos primeira):
Agora substitua em
:
Resultado:
. Esse ponto é no primeiro quadrante e satisfaz as duas igualdades, logo é um vértice candidato.
- Interseção entre zinco e magnésio:
Multiplique a primeira por
(ou faça outro método); aqui uso eliminação através de multiplicações por números inteiros: multiplique a primeira por
e a segunda por
:
Subtraindo a segunda da primeira:
Valor negativo de (x_2] → interseção fora do primeiro quadrante → não viável.
Interseções com os eixos (já calculadas ao listar interceptos) que podem ser vértices candidatos:
- Interseção da reta do cobre com
: . - Interseção da reta do magnésio com
: .
(Outras interseções com eixos comoda reta do zinco não são viáveis porque não satisfazem todas as restrições simultaneamente; o ponto viável sobre o eixo deve satisfazer todas as desigualdades, então as únicas extremidades relevantes no primeiro quadrante são e .)
Resumo dos vértices candidatos viáveis (no primeiro quadrante):
-
— obtido quando só o cobre está justo e . -
— obtido quando só o magnésio está justo e . -
— interseção das retas do cobre e do magnésio (ambas justas).]
Passo 7
Avaliar a função objetivo
em cada vértice candidato (passo essencial: por teorema fundamental da PL, para um problema linear em número finito de variáveis, o ótimo ocorre em um vértice extremo do politopo viável):
- Em
:
- Em
:
- Em
:
Comparação:
. Portanto, o menor custo entre esses vértices é
em
.
Passo 8
Verificação final de que
realmente satisfaz todas as restrições (para garantir que não houve erro de cálculo):
- Cobre:
→ OK (igual a 8). - Zinco:
→ OK. - Magnésio:
→ OK (igual a 5).
Conclusão:
é factível e fornece o custo mínimo
. A solução é única entre os vértices considerados — se houvesse uma aresta inteira de ótimos, teríamos dois vértices com mesmo custo; não é o caso aqui.
Resposta
(a) Modelo PL:
sujeito a
(b) Região viável: interseção dos semiplanos definidos por
Esboço/descrição: no primeiro quadrante, desenhar as retas com interceptos
O conjunto viável é o semiplano acima/à direita de cada reta; o bordo inferior relevante tem vértices
e a região é não limitada (estende-se para cima/à direita).
(c) Solução ótima: comprar
toneladas do minério tipo 1 e
toneladas do minério tipo 2; custo mínimo
.