Programação Linear Inteira e Binária

Prévia do material em texto

EAD 350EAD 350
Pesquisa OperacionalPesquisa Operacional
Aula 06Aula 06
Prof. Hiroo Takaoka
takaoka@usp.br
FEA/USP
Aula 06 Aula 06 -- ObjetivosObjetivosAula 06 Aula 06 -- ObjetivosObjetivos
• Apresentar a diferença entre a Programação Linear e a 
Programação Linear Inteira
• Apresentar como modelar a Programação Linear Inteira no 
Solver do Excel
• Apresentar os conceitos da Programação Binária e Mista
• Apresentar como modelar a Programação Binária e Mista no 
Solver do Excel
• Exercitar a Programação Binária e Mista no Solver por meio 
das atividades 6a, 6b e 6c
Resolução das Resolução das 
Atividades Atividades 5d5d
AtivAtiv 5d 5d –– Resolução Resolução AtivAtiv 5d 5d –– Resolução Resolução 
• O supervisor do centro de suporte da empresa Alpha precisa elaborar a escala de seu pessoal. O 
centro de suporte fica aberto das 8 da manhã até meia-noite. O supervisor monitorou as quantidades 
de chamados por período e determinou que o seguinte número de analistas seriam necessários por 
período.
• Podem ser contratados dois tipos de analistas: em tempo integral e estagiários tempo parcial. Os 
analistas em tempo integral trabalham por oito horas seguidas em três tipos de turno (8h às 16h, 12h 
às 20h ou 16h às 00h) e recebem $14 por hora. Os estagiários em tempo parcial podem ser 
contratados para os períodos de 4 horas indicados na tabela anterior e recebem $12 por hora.
• Durante qualquer período, deve haver pelo menos dois analistas tempo integral para cada estagiário 
em tempo parcial.
• Como atender a esses requisitos com o custo mínimo? 
• Elaborar e escrever o modelo matemático (na própria planilha)
• Elaborar a o modelo em Excel e resolver com o Solver – gerar o relatório de análise de sensibilidade
Período do dia Número mínimo de analistas de plantão 
08h – 12h 4
12h – 16h 8
16h – 20h 10
20h – 24h 6
A tabela abaixo indica as variáveis de decisão e1, e2, e3 e e4 referentes aos 
estagiários (tempo parcial) em cada um dos turnos de 4 horas e as variáveis a1, a2
e a3 referentes aos analistas em cada um dos turnos de 8 horas, bem como as 
quantidades mínimas para cada turno de 4 horas
O modelo matemático pode então ser assim descrito:
Minimizar o custo: ((e1+e2+e3+e4) x 12 x 4) + ((a1+a2+a3) x 14 x 8)
Sujeito a:
e1+a1>=4
e2+a1+a2>=8
e3+a2+a3 >=10
e4+a3>=6
a1 - 2e1 >= 0
a1+a2 - 2e2 >= 0
a2+a3 – 2e3 >=0
a3 – 2e4 >=0
Nota importante: as últimas quatro 
restrições NÃO poderiam ser deixadas 
escritas como:
a1/e1 >= 2
(a1+a2) / e2 >= 2
(a2+a3) / e3 >= 2
a3 / e4 >= 2
Pois essa formulação infringe as regras da 
programação linear
Nro. Mínimo 
de atendentes
Mínimo de 2 
analistas para 
cada estagiário 
no turno
AtivAtiv 5d 5d –– Resolução Resolução –– Modelo MatemáticoModelo Matemático
Período do 
dia Estagiário
Analista 
manhã
Analista 
tarde
Analista 
noite
Número 
mínimo de 
atendentes
8h – 12h e1
a1
--- --- 4
12h – 16h e2
a2
--- 8
16h – 20h e3 ---
a3
10
20h – 24h e4 --- --- 6
AtivAtiv 5d 5d –– Resolução Resolução –– PlanilhaPlanilha Excel (veja Excel (veja 
arquivo no erudito)arquivo no erudito)
Soluções não inteiras
Programação Linear InteiraProgramação Linear InteiraProgramação Linear InteiraProgramação Linear Inteira
• Como pode ser percebido na solução da atividade 5d, 
a Programação Linear fornece soluções com valores 
contínuos (isso é, não necessariamente inteiros)
• Isso pode ser um problema quando é necessário que 
os valores sejam inteiros, como é o caso da atividade 
5d (não é possível contratar 1,3333 estagiários para o 
primeiro turno, por exemplo)
• Simplesmente “arredondar” os valores para cima ou 
para baixo não resolve o problema, pois a solução 
arredondada pode não ser viável (infringir alguma das 
restrições) ou pode não ser a ótima
Programação Linear InteiraProgramação Linear InteiraProgramação Linear InteiraProgramação Linear Inteira
• Por exemplo, arredondando os valores do 
exercício 5d para cima ou para baixo 
(considerando o valor mais próximo) temos a 
tabela abaixo, com Z (custo) mínimo R$ 1.552:
• Esta não é a solução ótima possível com 
valores inteiros. Vamos realizar novamente o 
procedimento do Solver, agora impondo a 
solução inteira e verificar os resultados 
(descrito nos próximos slides, passo a passo)
Programação Linear Inteira no Programação Linear Inteira no 
ExcelExcel
Programação Linear Inteira no Programação Linear Inteira no 
ExcelExcel
• No solver, a programação 
linear inteira é obtida 
acrescentando-se mais uma 
restrição, aplicada às células 
que contêm os valores das 
variáveis de decisão
• 1) Abra a planilha “Atividade 
5 Soluções.xlxs” do Erudito
• 2) Na aba “Alpha escala” 
está a planilha com os 
dados do exercício
• 3) Abra a janela de 
parâmetros do Solver e 
clique no adicionar 
restrições
Programação Linear Inteira no Programação Linear Inteira no 
ExcelExcel
Programação Linear Inteira no Programação Linear Inteira no 
ExcelExcel
• 4) na caixa “referencia de célula” 
marque a área correspondente às 
variáveis de decisão (B27 a H27)
• 5) Na caixa dropdown para o tipo de 
restrição, note que além do “<=“, 
“=“ e “>=“ que já conhecemos, há 
também duas outras opções:
– núm – especifica números 
inteiros
– Bin – especifica números 
binários (0 ou 1)
• 6) Selecione a opção “núm” e clique 
no OK
• 7) Note que uma restrição 
“= número” é adicionada
• OBS – No Excel mais recente, a opção 
para números inteiros é “int”, e não 
“núm”.
Programação Linear Inteira no Programação Linear Inteira no 
ExcelExcel
Programação Linear Inteira no Programação Linear Inteira no 
ExcelExcel
• 8) Se o Excel for posterior a 2007, antes de 
executar o Solver, verifique na janela de 
opções se a opção “ignorar restrições de 
números inteiros” está desmarcada (clique 
no botão opções na janela de parâmetros do 
solver). 
• 9) Clique no “Resolver”
• 10) Note que no caso da programação linear 
inteira, não é gerado relatório de 
sensibilidade
Esta opção não consta no 
Excel 2007.
AtivAtiv 5d 5d –– Resposta com Programação Linear Resposta com Programação Linear 
InteiraInteira Veja o resultado
ótimo inteiro
Diferente de 1552 
obtido através do 
arredondamento.
Programação Linear Programação Linear Inteira Inteira -- ExemploExemploProgramação Linear Programação Linear Inteira Inteira -- ExemploExemplo
Max Z = x1 + 4x2
Sujeito a
2x1 + 4x2 < 7
10x1 + 3x2 < 15
x1 > 0, x2 > 0, inteiros
1
2
1 2
2x1 + 4x2 < 7
10x1 + 3x2 < 15 
Z = x1 + 4x2
x1
x2
A
B
C
D
(0; 1,75)
Solução não Solução não inteira inteira -- Método SimplexMétodo SimplexSolução não Solução não inteira inteira -- Método SimplexMétodo Simplex
0
Max Z = x1 + 4x2
Sujeito a
2x1 + 4x2 < 7
10x1 + 3x2 < 15
x1 > 0, x2 > 0
Solução 
ótima
1
2
1 2
2x1 + 4x2 < 7
10x1 + 3x2 < 15 
Z = x1 + 4x2
x1
x2
A
B
C
D
(0; 1,75)
Solução Solução inteira inteira -- Método de Método de BranchBranch--andand--BoundBoundSolução Solução inteira inteira -- Método de Método de BranchBranch--andand--BoundBound
(1; 1)
0
Max Z = x1 + 4x2
Sujeito a
2x1 + 4x2 < 7
10x1 + 3x2 < 15
x1 > 0, x2 > 0, inteiros
Note que a solução ótima ao problema não está 
em um dos pontos extremos do conjunto de 
soluções viáveis. Portanto, o relatório de 
sensibilidade não é significativo. 
Solução 
ótima
PLI PLI –– Método de Método de BranchBranch--andand--BoundBoundPLI PLI –– Método de Método de BranchBranch--andand--BoundBound
• Cada vez que uma variável resulta não 
inteira, ramifica-se com duas opções de 
restrição adicional – o inteiro logo acima e o 
inteiro logo abaixo. A cada restrição adicional 
o valor de Z decresce.
• Consiste em observar que, se após encontraro ponto ótimo de um problema, introduzirmos 
restrições adicionais, o novo ótimo será não 
melhor que o anterior sem as restrições 
adicionais.
PLI PLI –– Método de Método de BranchBranch--andand--BoundBoundPLI PLI –– Método de Método de BranchBranch--andand--BoundBound
x1 = 0
x2 = 1,75
Z = 7 x2 < 1 x2 > 2
1
2x1 + 4x2 < 7
10x1 + 3x2 < 15
x1 > 0, x2 > 0, inteiros 
Inteiro logo 
abaixo
Inteiro logo 
acima
Variável 
não inteira
PLI PLI –– Método de Método de BranchBranch--andand--BoundBoundPLI PLI –– Método de Método de BranchBranch--andand--BoundBound
1
2
1 2
2x1 + 4x2 < 7
10x1 + 3x2 < 15 
Z = x1 + 4x2
1
x2 < 1
x1
x2
0
2(1,2; 1)
Max Z = x1 + 4x2
Sujeito a
2x1 + 4x2 < 7
10x1 + 3x2 < 15
x2 < 1
x1 > 0, x2 > 0, inteiros
Ramo 2
A
B
C
D
Variável 
não inteira
PLI PLI –– Método de Método de BranchBranch--andand--BoundBoundPLI PLI –– Método de Método de BranchBranch--andand--BoundBound
1
2
1 2
2x1 + 4x2 < 7
10x1 + 3x2 < 15 
Z = x1 + 4x2
1
x2 > 2
x1
x2
0
Max Z = x1 + 4x2
Sujeito a
2x1 + 4x2 < 7
10x1 + 3x2 < 15
x2 > 2
x1 > 0, x2 > 0, inteiros
Não viável
Ramo 3
A
B
C
D
PLI PLI –– Método de Método de BranchBranch--andand--BoundBoundPLI PLI –– Método de Método de BranchBranch--andand--BoundBound
x1 = 0
x2 = 1,75
Z = 7 
Não
viável
x1 = 1,2
x2 = 1
Z = 5,2
x2 < 1 x2 > 2
x1 < 1 x1 > 2
1
2 3
2x1 + 4x2 < 7
10x1 + 3x2 < 15
x1 > 0, x2 > 0, inteiros 
Inteiro logo 
abaixo
Inteiro logo 
acima
Variável 
não é 
inteira
Inteiro logo 
abaixo Inteiro logo 
acima
Variável 
não é 
inteira
PLI PLI –– Método de Método de BranchBranch--andand--BoundBoundPLI PLI –– Método de Método de BranchBranch--andand--BoundBound
1
2
1 2
2x1 + 4x2 < 7
10x1 + 3x2 < 15 
Z = x1 + 4x2
1
2 x2 < 1 
x1< 1
4
x1
x2
0
Max Z = x1 + 4x2
Sujeito a
2x1 + 4x2 < 7
10x1 + 3x2 < 15
x2 < 1
x1 < 1
x1 > 0, x2 > 0, inteiros
Ramo 4
A
B
C
D
(1; 1)
Variáveis 
inteiras
PLI PLI –– Método de Método de BranchBranch--andand--BoundBoundPLI PLI –– Método de Método de BranchBranch--andand--BoundBound
1
2
1 2
2x1 + 4x2 < 7
10x1 + 3x2 < 15 
Z = x1 + 4x2
1
2 x2 < 1 
x1 > 2
x1
x2
A
B
C
D
Max Z = x1 + 4x2
Sujeito a
2x1 + 4x2 < 7
10x1 + 3x2 < 15
x2 < 1
x1 > 2
x1 > 0, x2 > 0, inteiros
Não viável
Ramo 5
PLI PLI –– Método de Método de BranchBranch--andand--BoundBoundPLI PLI –– Método de Método de BranchBranch--andand--BoundBound
x1 = 0
x2 = 1,75
Z = 7 
Não
viável
x1 = 1,2
x2 = 1
Z = 5,2
x1 = 1
x2 = 1
Z = 5 
Não
viável
x2 < 1 x2 > 2
x1 < 1 x1 > 2
1
2 3
4 5
2x1 + 4x2 < 7
10x1 + 3x2 < 15
x1 > 0, x2 > 0, inteiros 
Inteiro logo 
abaixo
Inteiro logo 
acima
Variável 
não é 
inteira
Inteiro logo 
abaixo Inteiro logo 
acima
Variável 
não é 
inteira
Solução (Variáveis são inteiras)
Programação BináriaProgramação Binária
Programação Binária Programação Binária -- ConceitoConceitoProgramação Binária Programação Binária -- ConceitoConceito
• A programação binária é um caso especial da 
programação inteira
• Quando as variáveis de decisão em um problema só são 
permitidas a assumir valores 0 ou 1, tem-se o caso de 
programação binária.
• O número de aplicações para este tipo de problema é 
muito grande: sempre que se deseja indicar como solução 
um conjunto de decisões do tipo sim/não 
interdependentes pode-se aplicar a programação binária
• Uma decisão do tipo sim/não pode ser modelada por uma 
variável binária, fazendo-se 1=sim e 0=não
Programação Binária Programação Binária -- ConceitoConceitoProgramação Binária Programação Binária -- ConceitoConceito
• De n possibilidades selecionar não mais do que k alternativas. 
Suponha xi = 0 ou 1 p/ i=1,...,n. A restrição x1 + x2 + ... + xn <
k significa que, no máximo, k alternativas de n possibilidades 
podem ser escolhidas.
• De n possibilidades selecionar k alternativas. Suponha xi = 0 ou 1
p/ i=1,...,n. A restrição x1 + x2 + ... + xn = k significa que k
alternativas de n possibilidades devem ser escolhidas.
• Decisões dependentes. Não selecionar a alternativa k a não ser 
que seja selecionada antes a alternativa m. A restrição xk < xm ou
xk - xm < 0 impõe esta condição.
• Negação. A negação de xk é representada como: (1 – xk).
Programação Binária Programação Binária -- ExemploExemploProgramação Binária Programação Binária -- ExemploExemplo
• Uma empresa está considerando uma expansão por meio de uma 
nova fábrica em Los Angeles ou São Francisco (ou em ambas as 
cidades). Também está considerando construir armazéns, mas, 
somente na(s) cidade(s) em que também houver construído uma 
fábrica. A empresa pode investir até $ 10 milhões nesses projetos
• A tabela a seguir mostra o VPL (valor presente líquido), ou seja o 
resultado, e o investimento necessário para cada um dos projetos
• Quais devem ser os projetos executados, considerando-se a 
restrição de capital e interrelações entre as decisões (somente 
construir depósito em cidade em que for construída fábrica)?
Decisão
VPL (valor presente 
líquido) Investimento
Construir fábrica em Los Angeles $ 9 milhões $ 6 milhões
Construir fábrica em São Francisco $ 5 milhões $ 3 milhões
Construir depósito em Los Angeles $ 6 milhões $ 5 milhões
Construir depósito em São Francisco $ 4 milhões $ 2 milhões
Programação Binária Programação Binária -- ExemploExemploProgramação Binária Programação Binária -- ExemploExemplo
• Para modelar esse problema com a programação binária utilizaremos 4 variáveis 
binárias representando a decisão (0=não faz o projeto; 1 = faz o projeto)
• A partir daí, elabora-se o modelo matemático:
– Função Objetivo: Max Z (VPL) = 9X1+5X2+6X3+4X4
– Restrições:
• Capital: 
6X1+3X2+5X3+2X4 <= 10
• Depósito somente onde há fábricas: 
X3 <= X1  -X1+X3 <=0 (depósito (X3) depende da fábrica (X1))
X4 <= X2  -X2+X4 <=0 (depósito (X4) depende da fábrica (X2))
• Variáveis X1, X2, X3 e X4 Binárias
Variável 
Binária Decisão
VPL (valor presente 
líquido) Investimento
X1
0= Não Construir fábrica em Los Angeles 1= 
Construir fábrica em Los Angeles $ 9 milhões $ 6 milhões
X2
0 = Não Construir fábrica em São Francisco 
1= Construir fábrica em São Francisco $ 5 milhões $ 3 milhões
X3
0= Não Construir depósito em Los Angeles 1= 
Construir depósito em Los Angeles $ 6 milhões $ 5 milhões
X4
0 = Não Construir depósito em São Francisco 
1= Construir depósito em São Francisco $ 4 milhões $ 2 milhões
Programação Binária no ExcelProgramação Binária no ExcelProgramação Binária no ExcelProgramação Binária no Excel
• No solver, a programação Binária 
também é obtida acrescentando-se 
mais uma restrição, aplicada às 
células que contêm os valores das 
variáveis de decisão
• Em vez de selecionar “núm” deve-se 
selecionar “bin” para a restrição 
adicionada
• Se o Excel for posterior a 2007, 
antes de executar o Solver, verifique 
na janela de opções se a opção 
“ignorar restrições de números 
inteiros” está desmarcada (clique no 
botão opções na janela de 
parâmetros do solver)
Programação Programação BináriaBinária
Exemplo : Seleção Exemplo : Seleção de de InvestimentoInvestimento
Programação Programação BináriaBinária
Exemplo : Seleção Exemplo : Seleção de de InvestimentoInvestimento
Opções Retorno(VPL)
A
Capital Necessário por Ano
1 2 3 4 5
400 100 50 200 100 0
B 700 300 200 100 100 100
C 800 100 200 270 200 100
D 1000 200 100 400 200 200
Capital
Disponível
por Ano
500 450 700 400 300
Deseja-se selecionar projetos de investimentos que maximizem o retorno. Os 
retornos e as limitações de capital por ano parao investimento são dados no 
quadro abaixo: 
Programação Binária Programação Binária 
Exemplo: Exemplo: Seleção Seleção de Investimentode Investimento
Programação Binária Programação Binária 
Exemplo: Exemplo: Seleção Seleção de Investimentode Investimento
Max Z = 400xA + 700xB + 800xC + 1000xD
Sujeito a
100xA + 300xB + 100xC + 200xD < 500
50xA + 200xB + 200xC + 100xD < 450
200xA + 100xB + 270xC + 400xD < 700
100xA + 100xB + 200xC + 200xD < 400
0xA + 100xB + 100xC + 200xD < 300
xi = 0 ou 1; i=A, B, C, D 
Variáveis de decisão
xi = 1 se for selecionado o investimento i, xi = 0 se não
for selecionado o investimento i. (i = A, B, C, D)
Programação Programação MistaMista
Exemplo: Localização Exemplo: Localização de Depósitode Depósito
Programação Programação MistaMista
Exemplo: Localização Exemplo: Localização de Depósitode Depósito
Um atacadista aluga seus depósitos regionais. 
Atualmente há uma lista de três depósitos (A, B e C) 
que podem ser alugados. Formular o modelo de 
programação binária que minimize os custos de aluguel 
e de transporte de bens de seus depósitos A, B e C para 
os locais 1, 2, 3 e 4. Os custos de aluguel e os custos de 
mandar um caminhão de um depósito para um local são 
dados na tabela seguinte.
Programação Programação MistaMista
Exemplo: Localização Exemplo: Localização de Depósitode Depósito
Programação Programação MistaMista
Exemplo: Localização Exemplo: Localização de Depósitode Depósito
Depósito
Local Capacidade
(em número
de caminhões)
Aluguel
mensal1 2 43
170 40 16070
150 195 10100
100 240 60140
100 90 60110
A
B
C
Demanda
(em número
de caminhões)
200 7750
250 4000
300 5500
Programação Programação MistaMista
Exemplo: Localização Exemplo: Localização de Depósitode Depósito
Programação Programação MistaMista
Exemplo: Localização Exemplo: Localização de Depósitode Depósito
yi = 1 se alugar o depósito i, yi = 0 se não alugar o 
depósito i. (i = A, B, C)
xij = número de caminhões de depósito i para
local j. (i = A, B, C; j = 1, 2, 3, 4)
Custo de transporte
170xA1 + 40xA2 + 70xA3 + ... + 60xC4
Aluguel 
7750yA + 4000yB + 5500yC 
Custo Total = Custo de transporte + Aluguel
Programação Programação MistaMista
Localização Localização de Depósitode Depósito
Programação Programação MistaMista
Localização Localização de Depósitode Depósito
Min Z = 170xA1 + 40xA2 + 70xA3 + ... + 60xC4 +
7750yA + 4000yB + 5500yC
Sujeito a
xA1 + xB1 + xC1 = 100
xA2 + xB2 + xC2 = 90
xA3 + xB3 + xC3 =110
xA4 + xB4 + xC4 = 60
xA1 + xA2 + xA3 + xA4 < 200yA xA1 + xA2 + xA3 + xA4 - 200yA < 0
xB1 + xB2 + xB3 + xB4 < 250yB xB1 + xB2 + xB3 + xB4 - 250yB < 0
xC1 + xC2 + xC3 + xC4 < 300yC xC1 + xC2 + xC3 + xC4 - 300yC < 0
yi = 0 ou 1 (binário); i = A, B, C
xij > 0; i = A, B, C; j = 1 ... 4
Programação Programação MistaMista-- SolverSolver
Localização Localização de Depósitode Depósito
Programação Programação MistaMista-- SolverSolver
Localização Localização de Depósitode Depósito
Todas as variáveis
Programação Programação MistaMista-- SolverSolver
Localização Localização de Depósitode Depósito
Programação Programação MistaMista-- SolverSolver
Localização Localização de Depósitode Depósito
• Elabore a planilha Excel com o modelo matemático e a solução 
em solver para o problema apresentado como exemplo:
• Uma empresa está considerando uma expansão por meio de uma nova 
fábrica em Los Angeles ou São Francisco (ou em ambas as cidades). 
Também está considerando construir armazéns, mas, somente na(s) 
cidade(s) em que também houver construído uma fábrica. A empresa 
pode investir até $ 10 milhões nesses projetos
• A tabela a seguir mostra o VPL (valor presente líquido), ou seja o 
resultado, e o investimento necessário para cada um dos projetos
• Quais devem ser os projetos executados, considerando-se a restrição de 
capital e interrelações entre as decisões (somente construir depósito em 
cidade em que for construída fábrica)?
AtivAtiv. 6a. 6a–– Resolver em Excel HOJE em AULA Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito –– Duplas ou Trios Duplas ou Trios 
AtivAtiv. 6a. 6a–– Resolver em Excel HOJE em AULA Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito –– Duplas ou Trios Duplas ou Trios 
Decisão
VPL (valor presente 
líquido) Investimento
Construir fábrica em Los Angeles $ 9 milhões $ 6 milhões
Construir fábrica em São Francisco $ 5 milhões $ 3 milhões
Construir depósito em Los Angeles $ 6 milhões $ 5 milhões
Construir depósito em São Francisco $ 4 milhões $ 2 milhões
AtivAtiv. 6a . 6a -- continuaçãocontinuaçãoAtivAtiv. 6a . 6a -- continuaçãocontinuação
• Para modelar esse problema com a programação binária utilizaremos 4 variáveis 
binárias representando a decisão (0=não faz o projeto; 1 = faz o projeto)
• A partir daí, elabora-se o modelo matemático:
– Função Objetivo: Max Z (VPL) = 9X1+5X2+6X3+4X4
– Restrições:
• Capital: 
6X1+3X2+5X3+2X4 <= 10
• Depósito somente onde há fábricas: 
X3 <= X1  -X1+X3 <=0 (depósito (X3) depende da fábrica (X1))
X4 <= X2  -X2+X4 <=0 (depósito (X4) depende da fábrica (X2))
• Variáveis X1, X2, X3 e X4 Binárias
Variável 
Binária Decisão
VPL (valor presente 
líquido) Investimento
X1
0= Não Construir fábrica em Los Angeles 1= 
Construir fábrica em Los Angeles $ 9 milhões $ 6 milhões
X2
0 = Não Construir fábrica em São Francisco 
1= Construir fábrica em São Francisco $ 5 milhões $ 3 milhões
X3
0= Não Construir depósito em Los Angeles 1= 
Construir depósito em Los Angeles $ 6 milhões $ 5 milhões
X4
0 = Não Construir depósito em São Francisco 
1= Construir depósito em São Francisco $ 4 milhões $ 2 milhões
Deseja-se selecionar projetos de investimentos que maximizem o 
retorno. Os retornos e as limitações de capital por ano para o 
investimento são dados no quadro abaixo: 
Opções Retorno (VPL) 
Capital necessário por ano
1 2 3 4 5
A 400 100 50 200 100 0
B 700 300 200 100 100 100
C 800 100 200 270 200 100
D 1000 200 100 400 200 200
Capital 
disponível 
por ano
500 450 700 400 300
AtivAtiv. 6b . 6b –– Resolver em Excel HOJE em AULA Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito –– Duplas ou Trios Duplas ou Trios 
AtivAtiv. 6b . 6b –– Resolver em Excel HOJE em AULA Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito –– Duplas ou Trios Duplas ou Trios 
AtivAtiv. 6b . 6b -- cotinuaçãocotinuaçãoAtivAtiv. 6b . 6b -- cotinuaçãocotinuação
Max Z = 400xA + 700xB + 800xC + 1000xD
Sujeito a
100xA + 300xB + 100xC + 200xD < 500
50xA + 200xB + 200xC + 100xD < 450
200xA + 100xB + 270xC + 400xD < 700
100xA + 100xB + 200xC + 200xD < 400
0xA + 100xB + 100xC + 200xD < 300
xi = 0 ou 1; i=A, B, C, D 
Variáveis de decisão
xi = 1 se for selecionado o investimento i, xi = 0 se não
for selecionado o investimento i. (i = A, B, C, D)
Uma companhia distribuidora quer minimizar o custo de transporte de bens de 
seus depósitos A, B e C para as lojas de varejo 1, 2 e 3. Os custos para 
transportar uma unidade de um depósito para uma loja de varejo são dados 
na tabela abaixo:
Os custos fixos de operar os depósitos A, B e C são 5.000, 750 e 600 
respectivamente. Pelo menos dois deles devem operar. Os depósitos podem ser 
considerados como tendo capacidade ilimitada de armazenamento (usar qualquer 
valor maior do que 525). Formule um modelo de programação binária para 
decidir quais depósitos devem operar e a quantidade a ser transportada de cada 
depósito para cada loja de varejo.
Lojas de varejo
Depósito 1 2 3
A 15 32 21
B 9 7 6
C 11 18 5
Demanda 200 150 175
AtivAtiv. 6c. 6c–– Resolver em Excel HOJE em AULA Resolver em Excel HOJE em AULA ––
Entregarpelo Erudito Entregar pelo Erudito –– Duplas ou Trios Duplas ou Trios 
AtivAtiv. 6c. 6c–– Resolver em Excel HOJE em AULA Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito –– Duplas ou Trios Duplas ou Trios