Pesquisa Operacional - Programação Linear Inteira
Lista 9
qualquer erro, favor enviar e-mail para [email protected]
1) Um casal, Eve e Steven querem dividir suas tarefas domésticas (fazer compras, cozinhar, lavar
louças e lavar roupas) entre eles, de tal maneira que cada um tenha 2 tarefas e o tempo total gasto
para realizar tais tarefas seja mínimo. Suas eficiências sobre estas tarefas diferem de acordo com
a tabela abaixo:
Tempo Necessário por semana
Fazer Compras
Cozinhar Lavar Louça
Lavar Roupa
(A)
(B)
(C)
(D)
Eve (1)
4.5 hs
7.8 hs
3.6 hs
2.9 hs
Steven (2)
4.9 hs
7.2 hs
4.3 hs
3.1 hs
Formule o modelo de Programação Linear Inteira para este problema.
2) Uma companhia está estudando um projeto de expansão que consiste em construir uma nova
fábrica em Los Angeles ou San Francisco, ou mesmo talvez em ambas as cidades. A companhia
está considerando também a construção de um novo estoque, mas a escolha da localização é
restrita a cidade onde a nova fábrica será construída. O lucro total previsto com a construção em
cada cidade e o capital requerido é dado na tabela abaixo:
Variável Lucro Previsto
(em milhões $)
Capital Requerido
(em milhões $)
Fábrica Los Angeles
x1
9
6
Fábrica San Francisco
x2
5
3
Estoque Los Angeles
x3
6
5
Estoque San Francisco
x4
4
2
A companhia dispõe de apenas $10 milhões para investir. Escreva o modelo para este problema.
Qual combinação de alternativas maximiza o lucro previsto total?
3) Um porto carrega navios com 4 tipos de produtos líquidos através de um único duto. Após o
abastecimento de cada um dos produtos, faz-se necessário realizar operações de limpeza do duto
devido a problemas de reações químicas, que por sua vez podem ocasionar corrosões no casco
dos navios e no próprio duto. Após o carregamento de um navio, o processo se reinicia para
Notas de Aula - Fernando Nogueira
Pesquisa Operacional - Programação Linear Inteira
outro navio. Os produtos são denominados W, Y, B e R e a tabela abaixo resume o tempo gasto
na operação de limpeza do duto entre dois produtos. Uma limitação técnica do porto impede que
o último produto carregado em um navio seja o primeiro produto a ser carregado no próximo
navio. Uma vez que não faz sentido carregar o mesmo produto duas vezes no mesmo navio, os
tempos gastos para a limpeza entre dois produtos iguais são infinitos.
Próximo produto a ser carregado
Produto carregado W
Y
B
R
W
∞
10
17
15
Y
20
∞
19
18
B
50
44
∞
25
R
45
40
20
∞
A figura mostra a representação esquemática da rede.
Representação esquemática da rede.
Qual a seqüência que os produtos devem ser carregados em um navio de tal forma que minimize
o tempo total gasto na limpeza do duto?
Notas de Aula - Fernando Nogueira
Pesquisa Operacional - Programação Linear Inteira
4) Implementar um programa, na linguagem de sua escolha, que forneça a solução ótima inteira
para um problema qualquer de programação linear.
Respostas
1)
Min Z = 4.5x 1A + 7.8x 1B + 3.6 x 1C + 2.9 x 1D + 4.9 x 2 A + 7.2 x 2 B + 4.3x 2C + 3.1x 2 D
⎧x 1A + x 1B + x 1C + x 1D = 2
⎪
⎪x 2 A + x 2 B + x 2C + x 2 D = 2
⎪x + x = 1
1A
2A
⎪⎪
sujeito a ⎨x 1B + x 2 B = 1
⎪x + x = 1
2C
⎪ 1C
⎪x 1D + x 2 D = 1
⎪
⎪⎩x ij ∈ Ι
2)
Max Z = 9x 1 + 5x 2 + 6x 3 + 4x 4
⎧
⎪
⎪
⎪6x + 3x + 5x + 2x ≤ 10
2
3
4
⎪ 1
⎪x 3 + x 4 ≤ 1
⎪
sujeito a ⎨− x 1 + x 3 ≤ 0
⎪− x + x ≤ 0
4
⎪ 2
⎪x i ≤ 1 ⎫
⎪
⎪
⎪x i ≥ 0⎬x i binário
⎪x ∈ Ι ⎪
⎭
⎩ i
Construir fábricas em ambas as cidades, mas sem estoques.
Por ser um problema pequeno, pode-se obter a solução ótima x1 = x2 = 1 e x3 = x4 = 0 por "força
bruta", ou seja, testar todas as combinações possíveis de x1, x2, x3 e x4 = 0 ou 1 no modelo acima.
Notas de Aula - Fernando Nogueira
Pesquisa Operacional - Programação Linear Inteira
Código LINDO
MAX 9X1 + 5X2 + 6X3 + 4X4
SUBJECT TO
R1) 6X1 + 3X2 + 5X3 + 2X4 <= 10
R2) X3 + X4 <= 1
R3) -X1 + X3 <= 0
R4) -X2 + X4 <= 0
R5) X1 <=1
R6) X2 <=1
R7) X3 <=1
R8) X4 <=1
END
INT 4
3) W-Y-R-B-W
Tempo total = 98
Notas de Aula - Fernando Nogueira