Resoluçaõ de exercícios de Programação Linear Inteira
Carlos Eduardo Ramisch - N.º Cartão: 134657
PESQUISA OPERACIONAL I (ADM01120) – Turma B
Professor Denis Borenstein
19 de junho de 2006
Problema 1: Exercício 1 da Lista de Exercícios
1) Uma certa indústria decidiu se expandir, construindo uma nova fábrica em Los Angeles ou em
San Francisco. Também está sendo considerada a construção de um novo depósito na cidade que for
selecionada para a nova fábrica. O valor presente líquido (lucraticviadade total considerando o valor
do dinheiro no tempo) de cada uma destas alternativas está apresentado na tabela abaixo. A última
coluna dá o capital requerido para os respectivos investimentos, onde o capital total disponível é de
US$ 25.000.000,00*. O objetivo é encontar a combinação viável de alternativas que maximize o
valor presente líquido total.
Decisão
Valor presente líquido
Capital Requerido
Fábrica em Los Angeles
7 milhões
20 milhões
Fábrica em San Francisco
5 milhões
15 milhões
Depósito em Los Angeles
4 milhões
12 milhões
Depósito em San Francisco
3 milhões
10 milhões
Modelagem:
Considerando as seguintes variáveis de decisão:
FL = 1, se a fábrica é construída em Los Angeles.
0, caso contrário.
FS = 1, se a fábrica é construída em San Francisco.
0, caso contrário.
DL = 1, se o depósito é construído em Los Angeles.
0, caso contrário.
DS = 1, se o depósito é construído em San Francisco.
0, caso contrário.
O modelo proposto é (considerando os coeficientes e constantes medidos em milhões de dólares):
MAXIMIZE 7FL + 5FS + 4DL + 3DS
SUBJECT TO
20FL + 15FS + 12DL + 10DS <= 25
FL + FS = 1 !impede fábrica em S.F. e em L.A.
DL + DS = 1 !impede depósito em S.F. e em L.A.
FL + DS = 1 !impede fábrica em L.A. e depósito em S.F.
FS + DL = 1 !mpede fábrica em S.F. e depósito em L.A.
FL <= 1
FS <= 1
DL <= 1
DS <= 1
END
GIN 4
* No enunciado, o valor é de US$ 25.000,00, porém foi alterado para que o problema tivesse solução. Com US$
25.000,00, seria impossível expandir a indústria, fosse em Los Angeles, fosse em San Francisco.
Resolução:
A resolução do problema pelo método simplex no programa LINDO é mostrada a seguir:
LP OPTIMUM FOUND AT STEP
2
OBJECTIVE VALUE = 8.00000000
NEW INTEGER SOLUTION OF 8.00000000 AT BRANCH
0 PIVOT
BOUND ON OPTIMUM: 8.000000
ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS=
2
2
LAST INTEGER SOLUTION IS THE BEST FOUND
RE-INSTALLING BEST SOLUTION...
OBJECTIVE FUNCTION VALUE
1)
8.000000
VARIABLE
FL
FS
DL
DS
VALUE
0.000000
1.000000
0.000000
1.000000
REDUCED COST
-7.000000
-5.000000
-4.000000
-3.000000
ROW SLACK OR SURPLUS DUAL PRICES
2)
0.000000
0.000000
3)
0.000000
0.000000
4)
0.000000
0.000000
5)
0.000000
0.000000
6)
0.000000
0.000000
7)
1.000000
0.000000
8)
0.000000
0.000000
9)
1.000000
0.000000
10)
0.000000
0.000000
NO. ITERATIONS=
2
BRANCHES= 0 DETERM.= 1.000E
0
Interpretação:
A melhor alternativa é construir a fábrica e o depósito em San Francisco, uma vez que o objetivo é
maximizar o valor presente líquido.
Problema 2: Exercício 2 da Lista de Exercícios
2) Um jovem casal, Eva e Estêvão, quer dividir suas principais tarefas domésticas (compras,
cozinhar, lavar pratos e lavar roupas) entre si, de modo que cada um tenha duas tarefas, mas que o
tempo total gasto em tarefas domésticas seja mínimo. Suas eficiências nessas tarefas diferem, sendo
que o tempo que cada um gastaria para desempenhar uma tarefa dado pela seguinte tabela:
Agente
Compras
Cozinhar
Lavar Pratos
Lavar Roupas
Eva
3,2
7,4
4,1
2,5
Estêvão
3,9
6,8
4,5
2,7
Modelagem:
Considerando as seguintes variáveis de decisão:
EVCOM =
1, se a agente Eva é designada para a tarefa Compras.
0, caso contrário.
EVCOZ =
1, se a agente Eva é designada para a tarefa Cozinhar.
0, caso contrário.
EVPRA =
1, se a agente Eva é designada para a tarefa Lavar Pratos.
0, caso contrário.
EVROU =
1, se a agente Eva é designada para a tarefa Lavar Roupas.
0, caso contrário.
ESCOM =
1, se o agente Estêvão é designado para a tarefa Compras.
0, caso contrário.
ESCOZ =
1, se o agente Estêvão é designado para a tarefa Cozinhar.
0, caso contrário.
ESPRA =
1, se o agente Estêvão é designado para a tarefa Lavar Pratos.
0, caso contrário.
ESROU =
1, se o agente Estêvão é designado para a tarefa Lavar Roupas.
0, caso contrário.
O modelo proposto é:
MINIMIZE
3.2EVCOZ + 7.4EVCOZ + 4.1EVPRA + 2.5EVROU +
3.9ESCOZ + 6.8ESCOZ + 4.5ESPRA + 2.7ESROU
SUBJECT TO
EVCOM + ESCOM = 1
!somente um deles pode fazer compras
EVCOZ + ESCOZ = 1
!somente um deles pode cozinhar
EVPRA + ESPRA = 1
!somente um deles pode lavar os pratos
EVROU + ESROU = 1
!somente um deles pode lavar as roupas
EVROU + EVPRA + EVCOZ + EVCOM = 2
!Eva precisa realizar duas tarefas
ESROU + ESPRA + ESCOZ + ESCOM = 2
!Estêvão precisa realizar duas tarefas
EVROU <= 1
EVPRA <= 1
EVCOM <= 1
EVCOZ <= 1
ESPRA <= 1
ESROU <= 1
ESCOM <= 1
ESCOZ <= 1
END
GIN 8
Resolução:
A resolução do problema pelo método simplex no programa LINDO é mostrada a seguir:
LP OPTIMUM FOUND AT STEP
3
OBJECTIVE VALUE = 17.2999992
FIX ALL VARS.(
3) WITH RC > 0.000000E+00
NEW INTEGER SOLUTION OF 17.2999992 AT BRANCH
0 PIVOT
BOUND ON OPTIMUM: 17.30000
ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS=
4
LAST INTEGER SOLUTION IS THE BEST FOUND
RE-INSTALLING BEST SOLUTION...
OBJECTIVE FUNCTION VALUE
1)
17.30000
VARIABLE
EVCOZ
EVPRA
EVROU
ESCOZ
ESPRA
ESROU
EVCOM
ESCOM
VALUE
0.000000
1.000000
1.000000
1.000000
0.000000
0.000000
0.000000
1.000000
REDUCED COST
10.600000
4.100000
2.500000
10.700001
4.500000
2.700000
0.000000
0.000000
ROW SLACK OR SURPLUS DUAL PRICES
2)
0.000000
0.000000
3)
0.000000
0.000000
4)
0.000000
0.000000
5)
0.000000
0.000000
6)
0.000000
0.000000
7)
0.000000
0.000000
8)
0.000000
0.000000
9)
0.000000
0.000000
10)
1.000000
0.000000
11)
1.000000
0.000000
12)
1.000000
0.000000
13)
1.000000
0.000000
14)
0.000000
0.000000
15)
0.000000
0.000000
NO. ITERATIONS=
4
BRANCHES= 0 DETERM.= 1.000E
0
Interpretação:
Eva deve realizar as seguintes tarefas: Lavar pratos e Lavar Roupas.
Estêvão deve realizar as seguintes tarefas: Fazer compras e Cozinhar.
Dessa forma, o tempo gasto por ambos em tarefas domésticas é igual a 17.3 (mínimo).
4
Problema 3: Exercício 3 da Lista de Exercícios
3) Formule o problema 2 como um problema de designação e encontre a solução que minimize o
custo.
Modelagem:
Um modelo de designação é um modelo no seguinte formato:
N
MINIMIZE
∑ x ij cij
i=1
SUBJECT TO
m
∑ x ij=1 ∀ i=1..m
j =1
n
∑ x ij=1 ∀ j=1..n
i=1
Portanto, para transformar o problema 2 num modelo de designação, precisamos eliminar a variável
2 do lado direito de duas restrições. Isso pode ser feito se adicionarmos à tabela de custos mais duas
linhas, ou seja, dois agentes artificiais para realizarem essas tarefas. Esses agentes serão Eva' e
Estêvão', que irão funcionar como “clones” de Eva e Estêvão. Dessa forma, Eva realiza apenas uma
tarefa, enquanto seu clone Eva' realiza também apenas uma tarefa. Ao final, teremos encontrado que
Eva realiza duas tarefas, uma vez que ela e seu clone são, no mundo real, a mesma pessoa. O
raciocínio análogo é feito para Estêvão e Estêvão'. O modelo proposto considera as variáveis do
problema 2 adicionadas de mais oito variáveis para os agentes artificiais, nomeadas com um “2” no
após as duas primeiras letras do nome da variável para indicar que a variável se refere ao agente
clone. Por exemplo, EV2COZ vale 1 se o clone de Eva realiza a tarefa Cozinhar, e vale 0 caso
contrário. O modelo fica da seguinte forma:
MINIMIZE
3.2EVCOZ + 7.4EVCOZ + 4.1EVPRA + 2.5EVROU +
3.9ESCOZ + 6.8ESCOZ + 4.5ESPRA + 2.7ESROU +
3.2EV2COZ + 7.4EV2COZ + 4.1EV2PRA + 2.5EV2ROU +
3.9ES2COZ + 6.8ES2COZ + 4.5ES2PRA + 2.7ES2ROU
SUBJECT TO
EVCOM + ESCOM + EV2COM + ES2COM = 1 !somente um deles pode fazer compras
EVCOZ + ESCOZ + EV2COZ + ES2COZ = 1
!somente um deles pode cozinhar
EVPRA + ESPRA + EV2PRA + ES2PRA= 1
!somente um deles pode lavar os pratos
EVROU + ESROU + EV2ROU + ES2ROU= 1
!somente um deles pode lavar as roupas
EVROU + EVPRA + EVCOZ + EVCOM = 1
!Eva deve fazer uma tarefa
ESROU + ESPRA + ESCOZ + ESCOM = 1
!Estêvão deve fazer uma tarefa
EV2ROU + EV2PRA + EV2COZ + EV2COM = 1 !o clone de Eva deve fazer uma tarefa
ES2ROU + ES2PRA + ES2COZ + ES2COM = 1 !o clone de Estêvão deve fazer uma tarefa
EVROU <= 1
EVPRA <= 1
EVCOM <= 1
EVCOZ <= 1
ESPRA <= 1
ESROU <= 1
ESCOM <= 1
ESCOZ <= 1
END
GIN 16
EV2ROU <= 1
EV2PRA <= 1
EV2COM <= 1
EV2COZ <= 1
ES2PRA <= 1
ES2ROU <= 1
ES2COM <= 1
ES2COZ <= 1
Resolução:
A resolução do problema pelo método simplex no programa LINDO é mostrada a seguir:
LP OPTIMUM FOUND AT STEP 16
OBJECTIVE VALUE = 17.2999992
NEW INTEGER SOLUTION OF 17.2999992 AT BRANCH
0 PIVOT
18
BOUND ON OPTIMUM: 17.30000
ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS=
18
LAST INTEGER SOLUTION IS THE BEST
FOUND
ROW
RE-INSTALLING BEST SOLUTION...
PRICES
2)
OBJECTIVE FUNCTION VALUE
3)
4)
1)
17.30000
5)
6)
VARIABLE
VALUE
REDUCED
7)
COST
8)
EVCOZ
0.000000
10.600000
9)
EVPRA
1.000000
4.100000
10)
EVROU
0.000000
2.500000
11)
ESCOZ
1.000000
10.700001
12)
ESPRA
0.000000
4.500000
13)
ESROU
0.000000
2.700000
14)
EV2COZ
0.000000
10.600000
15)
EV2PRA
0.000000
4.100000
16)
EV2ROU
1.000000
2.500000
17)
ES2COZ
0.000000
10.700001
18)
ES2PRA
0.000000
4.500000
19)
ES2ROU
0.000000
2.700000
20)
EVCOM
0.000000
0.000000
21)
ESCOM
0.000000
0.000000
22)
EV2COM
0.000000
0.000000
23)
ES2COM
1.000000
0.000000
24)
25)
NO. ITERATIONS=
18
BRANCHES= 0 DETERM.= 1.000E
SLACK OR SURPLUS
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
1.000000
0.000000
1.000000
1.000000
1.000000
1.000000
1.000000
0.000000
0.000000
1.000000
1.000000
1.000000
1.000000
1.000000
0.000000
1.000000
DUAL
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0
Uma vez que este é um modelo de designação, uma forma alternativa de se resolver o problema é
utilizando o método húngaro. Utilizaremos esse método para conferir a resposta encontrada pelo
LINDO.
Método Húngaro:
1.a) Mínimo das linhas:
1.b) Máximo das colunas:
2) Retas para cobrir zeros
3,2 7,4 4,1 2,5
2,5
0,7 4,9 1,6 0
0 0,8 0 0
3,9 6,8 4,5 2,7
2,7
1,2 4,1 1,8 0
0,5 0 0,2 0
3,2 7,4 4,1 2,5
2,5
0,7 4,9 1,6 0
0 0,8 0 0
3,9 6,8 4,5 2,7
2,7
1,2 4,1 1,8 0
0,5 0 0,2 0
0,7 4,1 1,6 0
Interpretação:
Pela solução do simplex:
Eva realiza a tarefa Lavar Pratos, Estêvão a tarefa Cozinhar, Eva' a tarefa Lavar Roupas e Estêvão' a
tarefa Fazer compras. Uma vez que no mundo real Eva e Eva' são a mesma pessoa, bem como
Estêvão e seu clone Estêvão', podemos afirmar que:
Eva deve realizar as seguintes tarefas: Lavar pratos e Lavar Roupas.
Estêvão deve realizar as seguintes tarefas: Fazer compras e Cozinhar.
Pela solução do método húngaro:
Eva pode Fazer Compras, Lavar Pratos ou Lavar Roupas.
Estêvão pode Fazer Compras ou Cozinhar.
Uma vez que estêvão necessita de duas tarefas, Eva não pode fazer compras. Portanto, Eva é
designada para as tarefas Lavar Pratos ou Lavar Roupas enquanto Estêvão é designado para as
tarefas Fazer Compras e Cozinhar.
Ambas as respostas são exatamente iguais à resposta do problema 2, com o mesmo valor para a
função objetivo na resolução do Simplex (17.3), como era esperado.
Problema 4: Problema da evacuação (ditado em aula)
Numa certa região existe uma usina nuclear para geração de energia elétrica. Face à possibilidade
da ocorrência de vazamento de material radioativo, é necessária a preparação de um plano de
evacuação de emergência para a região circumvizinha. O plano deverá prever a retirada segura de
pessoas, animais e patrimônio essencial antes que os mesmos possam sofrer os efeitos nocivos da
exposição radioativa. O modelo proposto para a evacuação idealiza a concentração das pessoas,
animais e patrimônio em um centro de triagem e evacuação. A determinação do número de centros
de triagem transcende a dimensão econômica. Se por um lado, um número excessivo de centros
dificulta a coordenação da evacuação e aumenta o risco da exposição dos seres humanos, por outro,
um número pequeno ocasionará certamente insuficiência no atendimento. As unidades de
discretização possuem as seguintes demandas:
pi = número de pessoas na área i
vi = número de animais na área i
oi = número de unidades de patrimônio na área i
Cada centro de evacuação pode atender g pessoas, k animais e l unidades de patrimônio. Formule o
problema de minimizar o número de centros de triagem do sistema de evacuação.
Modelagem
Considerando que o problema nos dá apenas informações genéricas sobre o problema, num
primeiro momento iremos construir um modelo abstrato, e atribuiremos valores fictícios para a
demonstração do modelo num segundo momento.
Modelo Abstrato:
Considerando as seguintes variáveis e parâmetros:
m = número de áreas
n = número de centros de triagem
aij = 1, se o local j cobre a área i
0, caso contrário
xj = 1, se o local j é escolhido para a abertura de um centro de evacuação
0, caso contrário.
O modelo proposto é:
n
MINIMIZE
∑ x ij
j=1
SUBJECT TO
n
∑ a ij x j≥1 ∀ i=1..m
j=1
n
∑ a ij x j pi ≤g ∀ j=1..n
j=1
n
∑ a ij x j v i≤k ∀ j=1..n
j=1
n
∑ a ij x j oi≤l ∀ j=1..n
j=1
A primeira restrição garante que todas as áreas são cobertas e as três restantes garantem que a
demanda das áreas obedece à capacidade dos centros de evacuação.
Modelo Exemplificado:
A tabela abaixo modela os valores para aij e para as demandas pi, vi e oi.
Locais (índice j)
Áreas (índice i)
L1 L2 L3 L4 pi vi oi
Var. decisão
A1
1
A2
1
A3
1
1
1
A4 1
x1
10 2
8
15 7
5
20 12 11
27 3
x2
x3
9
x4
Considerando os limites g = 30, k = 15 e l = 20, podemos formular o seguinte modelo para
exemplificar:
MINIMIZE x1 + x2 + x3 + x4
SUBJECT TO
x2 + x3 >= 1
x2 >= 1
x3 + x4 >= 1
x1 >= 1
27x1 <= 30
3x1 <= 15
9x1 <= 20
10x2 + 15x2 <= 30
2x2 + 7x2 <= 15
8x2 + 5x2 <= 20
10x3 + 12x3 <= 30
2x3 + 12x3 <= 15
8x3 + 11x3 <= 20
20x4<=30
12x4<=15
11x4<= 20
x1 <= 1
x2 <= 1
x3 <= 1
x4 <= 1
END
GIN 4
Resolução:
A resolução do problema pelo método simplex no programa LINDO é mostrada a seguir:
LP OPTIMUM FOUND AT STEP
6
OBJECTIVE VALUE = 3.00000000
FIX ALL VARS.(
1) WITH RC > 0.000000E+00
NEW INTEGER SOLUTION OF 3.00000000 AT BRANCH
0 PIVOT
BOUND ON OPTIMUM: 3.000000
ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS=
9
9
LAST INTEGER SOLUTION IS THE BEST FOUND
RE-INSTALLING BEST SOLUTION...
OBJECTIVE FUNCTION VALUE
1)
3.000000
VARIABLE
X1
X2
X3
X4
VALUE
1.000000
1.000000
0.000000
1.000000
REDUCED COST
1.000000
1.000000
1.000000
1.000000
ROW SLACK OR SURPLUS DUAL PRICES
2)
0.000000
0.000000
3)
0.000000
0.000000
4)
0.000000
0.000000
5)
0.000000
0.000000
6)
3.000000
0.000000
7)
12.000000
0.000000
8)
11.000000
0.000000
9)
5.000000
0.000000
10)
6.000000
0.000000
11)
7.000000
0.000000
12)
30.000000
0.000000
13)
15.000000
0.000000
14)
20.000000
0.000000
15)
10.000000
0.000000
16)
3.000000
0.000000
17)
9.000000
0.000000
18)
0.000000
0.000000
19)
0.000000
0.000000
20)
1.000000
0.000000
21)
0.000000
0.000000
NO. ITERATIONS=
9
BRANCHES= 0 DETERM.= 1.000E 0
Interpretação:
Os locais L1, L2 e L4 devem ser escolhidos para a abertura de centros de evacuação, de forma que
todas as áreas sejam cobertas, as restrições de demanda e capacidade sejam obedecidas e o número
de centros seja mínimo.