Lista 01- Pesquisa Operacional INF280 UFV

Prévia do material em texto

Universidade Federal de Viçosa 
Departamento de Informática 
INF280 – Pesquisa Operacional I 
Lista de Exercícios 1 
Prof.: Renan José dos Santos Viana 
Data de entrega: 5 de setembro de 2016 
1° Parte: Modelagem 
Modelar todos os problemas apresentados a seguir. Para cada modelo, especifique claramente o significado 
das variáveis de decisão, da função objetivo e das restrições (coloque comentários no modelo). Resolva cada 
modelo utilizando o software de otimização Lindo e por meio dos relatórios gerados, escreva as respostas 
(soluções) dos problemas. Exemplo de resposta: “Para gerar o lucro de R$ 200,00 (lucro máximo), a fábrica 
deve produzir 20 unidades do produto x e 40 unidades do produto y”. 
1. Uma metalúrgica deseja maximizar sua receita bruta. A tabela abaixo ilustra a proporção de cada 
material na mistura para a obtenção das ligas passíveis de fabricação. O preço está cotado em reais 
por tonelada da liga fabricada. Também em toneladas estão expressas as restrições de 
disponibilidade de matéria-prima. 
 
 Liga Especial de Baixa 
Resistência (*) 
Liga Especial de Alta 
Resistência (*) 
Disponibilidade de 
Matéria-prima (Ton) 
Cobre 0,5 0,2 16 
Zinco 0,25 0,3 11 
Chumbo 0,25 0,5 15 
Preço de Venda R$ 3.000 R$ 5.000 (*) Ton de minério/Ton 
de liga 
 
2. A OilCo está construindo uma refinaria para fabricar quatro produtos: óleo diesel, gasolina, 
lubrificantes e combustível para jatos. A demanda mínima (em barris/dia) para cada um desses 
produtos é 14000, 30000, 10000 e 8000, respectivamente. A OilCo tem contratos de fornecimento 
de óleo cru para o Irã e Dubai. Por causa das cotas de produção especificadas pela Organização dos 
Países Exportadores de Petróleo (Opep), a nova refinaria pode receber no mínimo 40% do seu óleo 
cru do Irã e a quantidade restante de Dubai. A OilCo prevê que a demanda e as cotas de óleo cru 
permanecerão estáveis nos próximos dez anos. 
As especificações dos dois óleos crus resultam em duas misturas de produtos diferentes: um barril 
de óleo cru do Irã rende 0,2 barril de diesel, 0,25 barril de gasolina, 0,1 barril de lubrificante e 0,15 
barril de combustível para jatos. Os rendimentos correspondentes do óleo cru de Dubai são 0,1; 0,6; 
0,15; e 0,1, respectivamente. A OilCo precisa determinar a capacidade mínima da refinaria (em 
barris/dia). 
3. O setor de transporte de cargas das linhas aéreas SOL, operando em São Paulo, dispõe de 8 aviões B-
737, 15 aviões B-727 e 12 aviões Electra. Há um volume programado de cargas para amanhã 
correspondendo a 150 toneladas para o Rio de Janeiro e outras 100 toneladas para Porto Alegre. As 
capacidades e o custo de operação de cada avião para voar para cada uma das cidades é dado na 
tabela abaixo: 
 
Destino B-737 B-727 Electra 
Rio de Janeiro 23 mil 5 mil 1,4 mil 
Porto Alegre 58 mil 10 mil 3,8 mil 
Capacidades 45 t 7 t 4 t 
 
Formule o problema de Programação Linear (PL) objetivando minimizar os custos de transporte. Note 
que a demanda deve ser satisfeita e as variáveis de decisão devem especificar as quantidades de cada 
avião destinados às cidades. 
 
4. Uma determinada fábrica produz panelas de metal médias e grandes a partir de elementos circulares 
de diâmetros de 25 e 40 centímetros, respectivamente. A primeira operação para obter as panelas é 
um corte desses elementos circulares sobre chapas de dimensão de 1,20 x 0,50 metros. Os elementos 
planos circulares são transformados em panelas em uma segunda operação de estamparia. Para o 
corte existem quatro tipos de matrizes, conforme mostra a figura abaixo. A fábrica deseja uma 
produção mínima de 500 panelas médias e 350 grandes. Os custos em reais por chapa pelo uso de 
cada matriz de corte são respectivamente 1, 2, 3 e 2. Elaborar o modelo de PL que planeje a produção 
de modo a minimizar o custo com o uso das matrizes de corte. 
 
5. Um sitiante está planejando sua estratégia de plantio para o próximo ano. Por informações obtidas 
nos órgãos governamentais, sabe que as culturas de trigo, arroz e milho serão as mais rentáveis na 
próxima safra. Por experiência, é conhecida a produtividade de sua terra para as culturas desejadas. 
Cultura Produtividade em Kg por 𝒎𝟐 
(por experiência) 
Lucro por Kg de Produção 
(Informação do governo) 
Trigo 0,2 10,8 centavos 
Arroz 0,3 4,2 centavos 
Milho 0,4 2,03 centavos 
 
Por falta de um local de armazenamento próprio, a produção máxima, em toneladas, está limitada a 
60. A área cultivável do sítio é de 200.000 𝑚2. Para atender às demandas de seu próprio sítio, é 
imperativo que se plante 400 𝑚2 de trigo, 800 𝑚2 de arroz e 10.000 𝑚2 de milho. 
6. Uma cooperativa agrícola opera três fazendas que possuem produtividades aproximadamente iguais 
entre si. A produção total por fazenda depende fundamentalmente da área disponível para o plantio 
e da água de irrigação. A cooperativa procura diversificar sua produção de modo que vai plantar este 
ano três tipos de cultura em cada fazenda, a saber: milho, arroz e feijão. Cada tipo de cultura 
demanda por uma certa quantidade de água. Para reduzir o conflito no uso das colheitadeiras, que 
são alugadas pela cooperativa, estabeleceram-se limites de área de produção dentro de cada tipo de 
cultura. Para evitar a concorrência entre os cooperados, acordou-se que a proporção de área 
cultivada seja a mesma para cada uma das fazendas. As tabelas a seguir resumem os dados 
tecnológicos. Pede-se a elaboração de um programa de produção que defina a área de cada cultura 
que será plantada em cada fazenda, de modo a otimizar o lucro total da produção da cooperativa. 
 
 
Fazenda Área Total para Cultivo (Acres) Água disponível (Litros) 
1 400 1.800 
2 650 2.200 
3 350 950 
 
Cultura Área Máxima de 
Cultivo (Acres) 
Consumo de Água 
(Litros por Acre) 
Lucro (R$/ Acre) 
Milho 660 5,5 5.000 
Arroz 880 4 4.000 
Feijão 400 3,5 1.800 
 
7. Uma empresa siderúrgica possui 3 usinas e cada uma delas requer uma quantidade mensal mínima 
de minério para operar. A empresa adquire minério de 4 minas diferentes. Cada uma das minas tem 
uma capacidade máxima de produção mensal estabelecida. Por imposições contratuais, o custo do 
minério para a empresa é composto por um custo fixo mensal para cada mina (este valor é pago em 
caso de haver produção na mina), mais um custo de transporte (R$/t) que varia de acordo com a 
distância entre as minas e usinas (cada mina/usina tem um custo diferente). Os dados são mostrados 
na tabela a seguir: 
Minas Usina 1 Usina 2 Usina 3 Capacidade prod. 
Minas 
Mina 1 10 8 13 11.500 
Mina 2 7 9 14 14.500 
Mina 3 6,5 10,8 12,4 13.000 
Mina 4 8,5 12,7 9,8 12.300 
Qtd 
requerida 
- usinas 
10.000 15.400 13.300 
 
Construa um modelo de otimização para determinar a quantidade de minério a ser comprada de cada 
mina e levada a cada usina de forma a minimizar o custo total de compra do minério. 
 
8. Um alpinista está se preparando para uma longa escalada nos Alpes. Sua mochila tem capacidade 
máxima de 44 kg. Ele possui 6 itens diferentes que podem ser levados para a escalada. Cada item 𝑗 
pesa 𝑤𝑗 kg e possui um valor numérico 𝑐𝑗 que representa o valor de sobrevivência do item. O 
problema do alpinista consiste em escolher os itens de forma a maximizar a soma dos valores de 
sobrevivência levados na mochila. 
 
 Item 1 Item 2 Item 3 Item 4 Item 5 Item 6 
𝑐𝑗 51 20 29 6 4 6 
(𝑤𝑗) 25 10 15 4 3 5 
 
 
2° Parte: Solução pelo método gráfico 
1. Dados os seguintes modelos de Programação Linear: 
Modelo 1: 
Max 𝑧(𝑥) = 6𝑥1 + 4𝑥2 
S.a. 
2𝑥1 + 3𝑥2 ≤ 18 
5𝑥1 + 4𝑥2 ≤ 40 
𝑥1 ≤ 6 
𝑥2 ≤ 8 
𝑥1, 𝑥2 ≥ 0 
Modelo 2: 
Min 𝑧(𝑥) = 10𝑥1 + 6𝑥2S.a. 
4𝑥1 + 3𝑥2 ≥ 24 
2𝑥1 + 5𝑥2 ≥ 20 
𝑥1 ≤ 8 
𝑥2 ≤ 6 
𝑥1, 𝑥2 ≥ 0 
a) Resolva graficamente os modelos. Confira a sua resposta com o software Lindo. 
b) Escreva os modelos na forma padrão. 
c) Para cada um dos modelos, qual o número máximo de soluções básicas? 
d) Para cada um dos modelos, determine todas as soluções básicas (viáveis e inviáveis) e calcule o valor 
da função objetivo. Apresente a solução ótima do modelo. 
 
 
3° Parte: Método Simplex 
1. Diante da crise econômica uma pequena fábrica de móveis artesanais notou que ultimamente os 
clientes só procuram três tipos de produtos, que chamaremos de A, B e C. O modelo de programação 
linear abaixo foi feito para decidir que quantidade deve ser produzida de cada produto para 
maximizar o lucro da fábrica, considerando os seguintes dados: 
- Os produtos A, B e C dão lucro respectivamente de 40, 30 e 60 reais por unidade, e gastam 
respectivamente 3, 1 e 3 m³ de madeira; 
- Os produtos A e B gastam ainda 2 e 3 Kg de tinta para o acabamento, mas o produto C não necessita 
acabamento com tinta; 
- A fábrica não tem equipamentos para paralelizar o trabalho, e por isso fabrica apenas um produto 
a cada hora; 
- Os fornecedores entregam diariamente 30m³ de madeira e 40Kg de tinta; 
- A fábrica funciona durante 18 horas por dia. 
 
Max 𝑧 = 40𝑥1 + 30𝑥2 + 60𝑥3 (Lucro) 
S.a. 
3𝑥1 + 𝑥2 + 3𝑥3 ≤ 30 (Madeira) 
2𝑥1 + 3𝑥2 ≤ 40 (Tinta) 
𝑥1 + 𝑥2 + 𝑥3 ≤ 18 (Horas) 
𝑥1, 𝑥2, 𝑥3 ≥ 0 
 
a) Monte o quadro inicial do método simplex e resolva o problema por esse método. Mostre todos 
os quadros intermediários do método até o quadro final, indicando qual variável entra e qual 
variável sai da base em cada passo. 
b) Interprete a solução encontrada: O que deve ser produzido e em quantas unidades? Qual o lucro 
máximo? Há sobra de algum recurso? 
c) Pela solução encontrada, é possível prever que a fábrica teria um lucro maior se recebesse mais 
tinta? E se funcionasse por mais horas? 
d) Na tabela ótima obtida, indique quais são os valores dos custos reduzidos e das variáveis duais 
(preços duais). 
 
2. Considere o seguinte modelo de Programação Linear: 
Max 𝑧 = 24𝑥1 + 22𝑥2 + 45𝑥3 
S.a. 
2𝑥1 + 𝑥2 + 3𝑥3 ≤ 42 
2𝑥1 + 𝑥2 + 2𝑥3 ≤ 40 
𝑥1 + 0.5𝑥2 + 𝑥3 ≤ 45 
𝑥1, 𝑥2, 𝑥3 ≥ 0 
 
a) Escreva o modelo na forma padrão: Max 𝑐𝑥, S.a: 𝐴𝑥 = 𝑏, 𝑥 ≥ 0. Identifique os vetores/matrizes 
x, c, A e b (represente o modelo na forma matricial). Indique a dimensão de cada vetor/matriz. 
Qual é a dimensão da base B? 
b) Qual é o número máximo de soluções básicas que podem ser encontradas para o modelo? 
c) Resolva o modelo utilizando o método simplex em tabelas e confira os resultados com o solver 
Lindo. Na tabela do simplex obtida identifique os preços duais e os custos reduzidos e a matriz 
𝐵−1. 
d) Para a solução ótima obtida no item anterior, apresente a base correspondente (matriz B) e sua 
inversa 𝐵−1. 
e) Na tabela ótima obtida, indique quais são os valores dos custos reduzidos e das variáveis duais 
(preços duais).