PESC/COPPE/UFRJ - 1a Lista - Otimização - 2015.2
Prof. Luidi Simonetti
1. Problema das tintas: Uma empresa de tintas produz 2 tipos de tintas:
SR e SN. Ambos usam 2 componentes: SE e COR. A empresa tem a
disposição para comprar 4 misturas para compor as tintas:
• Solução A: 30% SE e 70% COR a R$ 1,5 por litro
• Solução B: 60% SE e 40% COR a R$ 1,0 por litro
• C.SE: 100% SE a R$ 4,0 por litro
• C.COR: 100% COR a R$ 6,0 por litro
Sabendo que para compor o SR temos que ter no mı́nimo 25% de SE e
no mı́nimo 50% de COR. Já para o SN temos que ter um mı́nimo de 20%
de SE e 50% de COR. Qual a quantidade de produtos a serem comprados
para se produzir 1000l de SR e 250l de SN com o menor custo.
2. Problema de Transporte: Os depósitos possuem demandas que devem
ser atendidas. As fábricas possuem ofertas para atender os depósitos. Cij
é o custo de transporte entre a fabrica i e o depósito j. Queremos atender
as demandas com um custo mı́nimo.
Fab.\Dep.
1
2
3
1
8
15
3
2
5
10
9
3
6
12
10
3. Problema do Fluxo Máximo: Um produtor de gás natural S precisa
enviar a maior quantidade de gás para a fabrica T através dos dutos. Cada
duto (i, j) é direcionado e possui uma capacidade associada.
4. Problema das misturas de petróleo: Uma refinaria processa vários
tipos de petróleo. Cada tipo de petróleo possui uma planilha de custos,
expressando condições de transporte e preços na origem. Cada tipo de
petróleo representa uma configuração diferente de subprodutos para a gasolina. Na medida em que cada tipo de petróleo é utilizado na mistura
para a produção da gasolina, é possı́vel programar a octanagem e outros
requisitos de cada tipo de gasolina produzida. Estes tipos definem a gasolina obtida.
Suponha que a refinaria utilize 4 tipos de petróleo e deseja produzir 3
tipos de gasolina. Programe a mistura dos tipos de petróleo de modo a
maximizar o lucro.
Disponibilidade
Custo
Petróleo
Gasolina Especificações
(barris/dia)
(barril/dia)
P1
3500
14
≤ 30% de P1
P2
2200
24
S
≥ 40% de P2
P3
4200
20
≤ 50% de P3
P4
1800
27
≤ 30% de P1
AZ
≥ 10% de P2
AM
≤ 70% de P1
5. Considere o seguinte problema de programação linear :
max −3x1 − 2x2
x1 + x2 ≤ 8
(1)
8x1 + 3x2 ≥ −24
(2)
3x1 + 5x2 ≥ 15
(3)
x1 ≤ 4
(4)
x2 ≥ 0
(5)
−6x1 + 8x2 ≤ 48
(6)
(a) Resolver o problema graficamente.
(b) Resolver o problema usando eliminação de Fourier.
(c) Coloque o problema na forma padrão e resolva pelo método simplex
a partir da base gerada pelas variáveis de folga.
6. Qual das seguintes inequações é válida para todo poliedro P ⊂ Rn ?
(a) 1T x ≥ 0
(b) 0T x ≤ −1
(c) 0T x ≤ 1
7. Suponha P ⊆ Rn , n ≥ 2, é um poliedro não vazio que contém o ponto
1T = (1, . . . , 1) e suponha que as inequações xi ≤ 1, i = 1, . . . , n, são
válidas para P . Qual das seguintes desigualdades é válida e ativa em 1.
(a) 1T x ≤ n
Preço
(barril)
35
28
22
(b) 1T x ≤ 1
(c) 0T x ≤ 1
8. Suponha P ⊆ Rn , n ≥ 2, é um poliedro não vazio, onde as inequações xi ≤
1, i = 1, . . . , n, são válidas para P . A seguinte afirmação é verdadeira?
“Se xT = {1, . . . , 1} é um elemento de P, então xT é um vértice de P ”.
9. Dado os pontos (xi , yi ), i = 1, 2, ..., p, onde xi e yi são números reais.
Gostarı́amos de escrever que y = ax + b tal que os parâmetros a e b
forneçam o mı́nimo de maxi=1...p {|yi − (axi + b)|}. Determinar um PPL
que encontre esses parâmetros a e b. Justificar.
10. Modele o problema do caminho mı́nimo entre os vértices s e t em um PPL
com variáveis representando arcos de um grafo direcionado G = (V, A).
Dica: Fluxo
11. Suponha que o seguinte problema de programação linear tem solução
ótima finita.
(P ) min
s.a.
cT x
Ax = b
x≥0
Mostre que se substituirmos o vetor b por b0 , o novo problema obtido ou
será inviável ou terá solução ótima finita.