Provas_Template

Prévia do material em texto

Universidade Federal de Ouro Preto
Instituto de Cieˆncias Exatas e Aplicadas
Departamento de Engenharia de Produc¸a˜o
ENP160 - Otimizac¸a˜o Combinato´ria
Questo˜es de Provas
1 Complexidade
1. Defina e relacione as classes de complexidade dos problemas de otimizac¸a˜o combinato´ria.
Soluc¸a˜o:
Se P e Q ∈ NP e existe um algoritmo que converta qualquer instaˆncia de Q em uma
instaˆncia de P em tempo polinomial, enta˜o dizemos que Q e´ redut´ıvel polinomial-
mente a P.
NPC e´ a classe de problemas NP - completo, i.e., e´ o subconjunto de problemas P
(P ∈ NP) para os quais todos os problemas Q (∈ NP) sa˜o redut´ıveis polinomial-
mente a P.
Um problema de otimizac¸a˜o combinato´ria para o qual o problema de decisa˜o associ-
ado e´ NPC, e´ chamado de NP-dif´ıcil (NP-hard).
2. Explique o conceito de reduc¸a˜o de problemas e cite dois problemas que pertencem a`
classe NP - completo.
Soluc¸a˜o:
Reduzir um problema A em um problema B significa transformar A em B de forma
que A passa a ser resolvido atrave´s do metodo de soluc¸a˜o de B ( Ex NP - completo:
Problema da Machila e Problema do carteiro viajante.
3. Defina e diferencie as classes de problemas P , NP e NP - completo.
Soluc¸a˜o:
P : conjunto de todos os problemas polinomiais onde Fa(n) = O(np) para um pro-
blema P .
NP - Non determinant polinomial: classe para os quais a resposta e´ sim ou na˜o e
pode ser verificada rapidamente.
NP - completo: subconjunto de problemas P onde (P ∈ NP) para os quais todos
problemas (Q ∈ NP) sa˜o redutivas polinomiais a P .
Questo˜es de Provas Pa´gina 1 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
4. Em 1982, os brasileiros Gabriel Bitran e Hora´cio Yanasse apresentaram reduc¸o˜es do
Problema da Mochila para diferentes parametrizac¸o˜es do Problema da Definic¸a˜o do
Tamanho do Lote Capacitado (CLSP). Sobre este fato responda:
(a) Explique o que e´ uma reduc¸a˜o.
(b) Sabendo que o Problema da Mochila pertence a` classe NPC, qual a implicac¸a˜o
dos resultados obtidos pelos autores?
Soluc¸a˜o:
(a) Reduc¸a˜o e´ uma tranformac¸a˜o de um problema em outro, este me´todo e´
utilizado para definir classes de complexidade. Se reduzir um problema A
em B, e se B na˜o e´ mais dif´ıcil que A, se na˜o houver algoritmo eficiente
para B, na˜o ha´ algoritmo eficiente para A.
(b) Implica que, como o problema da mochila pode ser reduzido ao CLSP,
na˜o e´ mais fa´cil que o problema da mochila, uma vez que o problema da
mochila e´ NPC, o CLSP tambe´m e´.
5. Corrija as sentenc¸as a seguir:
(a) Os problemas de decisa˜o pertencentes a` classe NPC sa˜o problemas que na˜o
podem ser resolvidos em tempo polinomial.
(b) O SAT e´ um problema de decisa˜o que pertence a` classe P .
Soluc¸a˜o:
(a) Os NPC sa˜o problemas que podem ser reduzidos polinomialmente a P .
(b) SAT e´ um problema de busca que pertence a NPC, encontrar uma soluc¸a˜o
que torne a resposta de uma fo´rmula booleana verdadeira ou mostrar que
ela na˜o existe.
6. Explique o conceito de reduc¸a˜o dentro da teoria da complexidade.
Soluc¸a˜o:
A reduc¸a˜o de A em um outro problema B significa mostrar que B na˜o e´ mais dif´ıcil que
A. Isto e´, se na˜o houver algoritmo eficiente para B, enta˜o tambe´m na˜o ha´ algoritmo
eficiente para A.
Questo˜es de Provas Pa´gina 2 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
7. Marque verdadeiro(v) ou falso (f) para as afirmativas abaixo e justifique quando a
sentenc¸a na˜o for verdadeira.
(a) Na˜o e´ poss´ıvel garantir a soluc¸a˜o de problemas de PLIM pertencentes a` classe
NP-Dif´ıcil em tempo polinomial.
(b) Problemas da classe NP sa˜o problemas para os quais na˜o se conhece algoritmo
polinomial para a soluc¸a˜o.
(c) A classe de problemas P na˜o possui elementos comuns a` classe NPC.
Soluc¸a˜o:
(a) Verdadeiro.
(b) Falso, um problema pode ter sua soluc¸a˜o determinada em tempo polino-
mial pelo algoritmo de SAT (busca).
(c) Falso, a classe P e´ um subconjunto da classe NPC
Questo˜es de Provas Pa´gina 3 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
2 Regia˜o de Viabilidade, Envolto´ria Convexa e For-
mulac¸a˜o Ideal
8. Dado o conjunto de pontos X = {(1,4), (2,4), (2,3), (3,3), (3,2), (4,2), (3,1), (4,1), (4,0)},
fac¸a:
(a) Represente graficamente a envolto´ria convexa de X;
(b) Descreva a formulac¸a˜o ideal para X.
Soluc¸a˜o:
(a) Envolto´ria convexa de X.
(b) Encontrar equac¸o˜es: x1 = x2a+ b
Para (1,4) e (3,1)
{
1 = 4a+ b
3 = a+ b
a =
−2
3
; b =
11
3
(1)
Primeira equac¸a˜o: 3x1 + 2x2 ≥ 11 (2)
Para (3,1) e (4,0)
{
3 = a+ b
4 = 0 + b
a = −1; b = 4 (3)
Segunda equac¸a˜o: x1 + x2 ≥ 4 (4)
Questo˜es de Provas Pa´gina 4 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
Para (2,4) e (4,2)
{
2 = 4a+ b
4 = 2a+ b
a = −1; b = 6 (5)
Terceira equac¸a˜o: x1 + x2 ≤ 6 (6)
Formulac¸a˜o Ideal:
3x1 + 2x2 ≥ 11 (7)
x1 + x2 ≥ 4 (8)
x1 + x2 ≤ 6 (9)
x1 ≤ 4 (10)
x2 ≤ 4 (11)
x1, x2 ∈ Z2+ (12)
9. Dados o poliedro P := {x ∈ R2|8x1 + 4x2 ≤ 40; 15x1 + 30x2 ≤ 200;x1 ≥ 2}, o conjunto
X := {x ∈ Z2+|x ∈ P} e o PPLI representado por (13-14), em um mesmo gra´fico,
represente:
max 10x1 + 15x2 (13)
sujeito a: x1, x2 ∈ X (14)
(a) A regia˜o de viabilidade da relaxac¸a˜o linear do PPLI (13-14), isto e´, a regia˜o de
viabilidade do PPL associado ao PPLI.
(b) O conjunto que representa a viabilidade do PPLI (13-14).
(c) A envolto´ria convexa do conjunto via´vel do PPLI (13-14).
Questo˜es de Provas Pa´gina 5 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
Soluc¸a˜o:
(a) Regia˜o de Viabilidade do PLLI e´ toda regia˜o preenchida da figura.
(b) {(2,0), (2,1), (2,2), (2,3), (2,4), (2,5), (3,0), (3,1), (3,2), (3,3), (3,4), (4,0),
(4,1), (4,2), (5,0)}.
(c) A envolto´ria convexa e´ a regia˜o com contorno preto na figura.
10. Dados o poliedro P := {x ∈ R2|x1+2x2 ≥ 4; 3x1−x2 ≤ 10; 4x1+6x2 ≤ 36;−2x1+3x2 ≤
3}, o conjunto X := {x ∈ Z2+|x ∈ P} e o PPLI representado por (15-16), em um mesmo
gra´fico, represente:
max c′x (15)
sujeito a: x ∈ X (16)
(a) A regia˜o de viabilidade da relaxac¸a˜o linear do PPLI (15-16), isto e´, a regia˜o de
viabilidade do PPL associado ao PPLI.
(b) O conjunto que representa a viabilidade do PPLI (15-16).
(c) A envolto´ria convexa do conjunto via´vel do PPLI (15-16).
Questo˜es de Provas Pa´gina 6 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
Soluc¸a˜o:
(a) Regia˜o de Viabilidade do PLLI e´ toda regia˜o preenchida da figura.
(b) {(2,1), (2,2), (3,1), (3,2), (3,3), (4,2), (4,3)}
(c) A envolto´ria convexa e´ a regia˜o com contorno preto na figura.
11. Considere os Problemas PLIM 1 e PLIM 2 definidos pelas formulac¸o˜es apresentadas na
Tabela 1 e responda:
PL1 PL2
-x1 + 2x2 ≤ 15(17)
x1 + 2x2 ≤ 12(18)
5x1 + 3x2 ≤ 45(19)
x1, x2 ∈ Z+(20)
-x1 + x2 ≤ 6(21)
x1 + 0.5x2 ≤ 8(22)
x2 ≤ 8(23)
x1, x2 ∈ Z+(24)
Tabela 1: Formulac¸o˜es para Questa˜o 11
(a) Encontre o conjunto vabilidade para o PLI 1.
(b) O PLI 2 e´ uma formulac¸a˜o para o PLI 1? Justifique.
(c) Descreva a formulac¸a˜o que define a envolto´ria convexa para o PLI 1.
Questo˜es de Provas Pa´gina 7 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
Soluc¸a˜o:
(a) Regia˜o de Viabilidade do PLI 1 e´ toda regia˜o preenchida da figura.
(b) O PLI 2 na˜o e´ uma formulac¸a˜o para o PLI 1, pois ha´ pontos inteiros no
PLI 1 que na˜o esta˜o contidos no PLI 2.
Questo˜es de Provas Pa´gina 8 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
(c) Encontrar equac¸o˜es: x1 = x2a+ b
Para (0,7) e (1,8)
{
0 = 7a+ b
1 = 8a+ b
a = 1; b = −7 (25)
Primeira equac¸a˜o: x1 − x2 ≤ −7 (26)
Para (1,8) e (3,9)
{
1 = 8a+ b
3 = 9a+ b
a = 2; b = −15 (27)
Segunda equac¸a˜o: x1− 2x2 ≤ −15 (28)
Para (3,9) e (4,8)
{
3 = 9a+ b
4 = 8a+ b
a = −1; b = 12 (29)
Terceira equac¸a˜o: x1 + x2 ≤ 12 (30)
Para (4,8) e (6,5)
{
4 = 8a+ b
6 = 5a+ b
a =
−2
3
; b =
28
3
(31)
Quarta equac¸a˜o: x1 +
2
3
x2 ≤ 28
3
(32)
Para (6,5) e (9,0)
{
6 = 5a+ b
9 = 0 + b
a =
−3
5
; b = 9 (33)
Quinta equac¸a˜o: x1 +
3
5
x2 ≤ 9 (34)
Formulac¸a˜o Ideal:
x1 − x2 ≤ −7 (35)
x1 − 2x2 ≤ −15 (36)
x1 + x2 ≤ 12 (37)
x1 +
2
3
x2 ≤ 28
3
(38)
x1 +
3
5
x2 ≤ 9 (39)
x1, x2 ∈ Z2+ (40)
Questo˜es de Provas Pa´gina 9 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
12. Relacione os conceitos (i) Regia˜o de Viabilidade; (ii) Envolto´ria Convexa de um Conjunto
de Pontos e (iii) Formulac¸a˜o ideal para um PPLIM. Com base nesta relac¸a˜o, qual a
motivac¸a˜o de se obter uma formulac¸a˜o mais justa para um PPLIM?
Soluc¸a˜o:
Toda regia˜o de um problema de programac¸a˜o linear e´ um poliedro convexo.
A envolto´ria convexa e´ o conjunto de todas as combinac¸o˜es convexas de x1, x2, ..., Xk ∈
X, ∀X ∈ R, ou seja, a envolto´ria convexa e´ a regia˜o de viabilidade do problema, que
conte´m todas combinac¸o˜es viao problema.
A formulac¸a˜o ideal de um PPLIM corresponde a envolto´ria convexa dos pontos in-
teiros.
A regia˜o de viabilidade de um PPLIM e´ uma regia˜o convexa formada pelos pontos
inteiro internos ao poliedro que determina a regia˜o de vialidade do PPL associado.
Uma formulac¸a˜o e´ dita ideal se ela garante que a soluc¸a˜o do PPL associado ao PPLIM
seja a soluc¸a˜o do PPLIM. Em uma formulac¸a˜o ideal P1, todos os pontos extremos
de P1 pertencem a` regia˜o de viabilidade do PPLIM.
A envolto´ria convexa esta´ contida na regia˜o de vialidade e a formualac¸a˜o ideal e´ o
conjunto de restric¸o˜es baseado na envolto´ria convexa. A ideia de se obter uma for-
mulac¸a˜o mais justa se da´ pelo fato de garantir que a soluc¸a˜o do PPL associado ao
PPLIM seja a soluc¸a˜o do PPLIM.
13. Dados a regia˜o A = {(x1, x2) ∈ R2| − x1 + x2 ≤ 4; 3x1 − 2x2 ≤ 3, se x1 ≤ 3; 6x1 + 4x2 ≤
36;x1 + x2 ≥ 6, se x1 ≥ 3} no plano de R2, fac¸a o que se pede:
(a) Desenhe a regia˜o A. Essa regia˜o e´ convexa?
(b) Seja r ∈ {0, 1} uma varia´vel bina´ria. Utilize essa varia´vel para modelar a
disjunc¸a˜o representa pela regia˜o A.
(c) Desenhe a regia˜o de viabilidade do problema (lembre-se que voceˆ possui 3
varia´veis).
Questo˜es de Provas Pa´gina 10 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
Soluc¸a˜o:
(a) Regia˜o A na˜o e´ convexa.
(b) Disjunc¸a˜o da regia˜o A.
−x1 + x2 ≤ 4 (41)
6x1 + 4x2 ≤ 36− (1− r)M (42)
x1 + x2 ≥ 6− (1− r)M (43)
x1 ≤ 3 +Mr (44)
Questo˜es de Provas Pa´gina 11 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
(c) Regia˜o de viabilidade.
14. Corrija as sentenc¸as a seguir:
(a) A regia˜o de viabilidade de um PPLIM e´ uma regia˜o convexa formada pelos
pontos internos ao polie´dro que determina a regia˜o de viabilidade do PPL
associado.
(b) Uma matriz totalmente unimodular garante em um PPLIM que sua regia˜o de
viabilidade e´ a mesma do PPL associado.
Soluc¸a˜o:
(a) A regia˜o de viabilidade de um PPLIM e´ uma regia˜o convexa formada pelos
pontos inteiros ao polie´dro que determina a regia˜o de viabilidade do PPL
associado.
(b) Uma matriz totalmente unimodular garante que a envolto´ria dessa e´ igual
ao poliedro P associaco a um PPLIM.
15. Dado o conjunto de pontos X = {(1,1), (2,1), (3,1),(1,2), (2,2), (3,2), (2,3)}, fac¸a:
(a) Represente graficamente a envolto´ria convexa de X;
(b) Descreva a formulac¸a˜o ideal para X.
Questo˜es de Provas Pa´gina 12 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
Soluc¸a˜o:
(a) Envolto´ria convexa.
(b) Encontrar equac¸o˜es: x1 = x2a+ b
Para (1,2) e (2,3) {
1 = 2a+ b
2 = 3a+ b
a = 1; b = −1 (45)
Primeira equac¸a˜o: x1 − x2 ≥ −1 (46)
Para (2,3) e (3,2) {
2 = 3a+ b
3 = 2a+ b
a = −1; b = 5 (47)
Segunda equac¸a˜o: x1 + x2 ≤ 5 (48)
Formulac¸a˜o Ideal:
x1 − x2 ≥ −1 (49)
x1 + x2 ≤ 5 (50)
x1 ≥ 1 (51)
x1 ≤ 3 (52)
x2 ≥ 1 (53)
x1, x2 ∈ Z2+ (54)
Questo˜es de Provas Pa´gina 13 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
16. Para o PPLI (55-58), represente:
max 3x1 + 4x2 (55)
sujeito a: 0.4x1 + 2x2 ≤ 3 (56)
0.4x1 − 0.4x2 ≤ 1 (57)
(x1, x2) ∈ Z2+ (58)
(a) A regia˜o de viabilidade da relaxac¸a˜o linear.
(b) O conjunto que representa a viabilidade.
(c) A envolto´ria convexa do conjunto via´vel.
Soluc¸a˜o:
(a) Regia˜o de Viabilidade.
(b) {(0,0), (0,1), (1,0), (1,1), (2,0), (2,1)}
(c) A envolto´ria convexa e´ a regia˜o com contorno preto na figura.
17. Marque verdadeiro(v) ou falso (f) para as afirmativas abaixo e justifique quando a
sentenc¸a na˜o for verdadeira.
(a) Os pontos que formam a regiz ao de viabilidade de um PPLIM podem ser
representados por um conjunto convexo.
(b) O Me´todo simplex na˜o pode ser utilizado para resolver problemas de pro-
gramac¸a˜o inteira uma vez que suas soluc¸o˜es sempre tera˜o valores fracionados.
(c) Envoltoria convexa e´ o nome que se da´ ao poliedro formado pela regia˜o de
viabilidade da relaxac¸a˜o linear de um PPLIM.
(d) Existem problemas de otimizac¸a˜o combinatoria que podem ser resolvidos por
enumerac¸a˜o das soluc¸o˜es no espac¸o de soluc¸o˜es.
Questo˜es de Provas Pa´gina 14 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
Soluc¸a˜o:
(a) Verdadeiro.
(b) Falso, nem sempre as soluc¸o˜es do simples sa˜o fracionadas.
(c) Falso, a envolto´ria convexa e´ o conjunto de todas as combinac¸o˜es convexas
de x1, x2, ..., xk ∈ X.
(d) Verdadeiro.
18. O poliedro P = {x1 + 2x2 ≤ 8; 2x1 − 2x2 ≤ 5;x1 ≥ 1;x2 ≥ 1} uma formulac¸a˜o para o
conjunto de pontos X = {(1,1), (2,1), (3,1), (1,2), (2,2), (3,2), (1,3), (2,3)}? Justifique.
Soluc¸a˜o:
Regia˜o de Viabilidade.
x1 + 2x+ 2 = 8 ; x1 = 5/2 (59)
2x1 − 2x2 = 5 ; x2 = −5/2 (60)
O poliedro e´ uma formulac¸a˜o, pois conte´m todo o conjunto de pontos de X.
Questo˜es de Provas Pa´gina 15 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
19. Qual e´ o interesse de se obter uma formulac¸a˜o ideal para um PPLIM?
Soluc¸a˜o:
O interesse em se obter uma formulac¸a˜o ideal para PPLIM e´ a reduzir o conjunto de
busca e dessa forma diminuir o custo computacional.
20. Marque verdadeiro(v) ou falso (f) para as afirmativas abaixo e justifique quando a
sentenc¸a na˜o for verdadeira.
(a) Os pontos extremos de um poliedro convexo podem gerar qualquer ponto in-
terno ao mesmo.
(b) Um politopo e´ a face de maior valor da func¸a˜o objetivo em um poliedro forma
a regia˜o de viabilidade de um PPLIM.
(c) No caso de um problema de maximizac¸a˜o, o valor da func¸a˜o objetivo obtido
para a soluc¸a˜o o´tima do PL associado a um PPLIM e´ maior que o valor da
soluc¸a˜o o´tima do PPLIM.
Soluc¸a˜o:
(a) Verdadeiro.
(b) Falso, a func¸a˜o objetivo forma um valor e na˜o uma face.
(c) Falso, a soluc¸a˜o o´tima do PL associado a um PPLIM pode ser maior ou
igual ao valor da soluc¸a˜o o´tima do PPLIM.
Questo˜es de Provas Pa´gina 16 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
3 Modelagem
21. Considere uma situac¸a˜o onde existem |M | mochilas e |I| itens para serem alocados
nestas. Todos os itens devem ser alocados a uma mochila e deve-se respeitar a capacidade
volume´trica da mochila. Visando o balanceamento da carga de cada mochila, o objetivo
do problema e´ minimizar o peso ma´ximo atribuido a uma delas. Sendo pi e vi o peso e o
volume de cada item i ∈ I, respectivamente. Sendo xim uma varia´vel bina´ria que indica
a alocac¸a˜o do item i ∈ I a` mochila m ∈M e Pmax uma varia´vel cont´ınua que representa
o peso ma´ximo atribu´ıdo a uma mochila, fac¸a o que se pede.
(a) Quais sa˜o os elementose conjuntos utilizados na formulac¸a˜o deste problema?
(b) Quais sa˜o os paraˆmetros do problema?
(c) Escreva matematicamente o conjunto de restric¸o˜es que garantem que todos os
itens devem ser alocados a uma mochila.
(d) Escreva matematicamente o conjunto de restric¸o˜es que garantem a na˜o violac¸a˜o
da capacidade volume´trica de cada mochila.
(e) Escreva matematicamente o conjunto de restric¸o˜es que garantem que Pmax
representara´ o peso ma´ximo atribu´ıdo a uma mochila.
(f) Escreva o objetivo do problema.
(g) Crie uma instaˆncia com 2 mochilas e 6 itens.
(h) Encontre uma soluc¸a˜o via´vel para a instaˆncia definida em (0g). Defina o valor
de todas as varia´veis e da func¸a˜o objetivo para a soluc¸a˜o encontrada.
Soluc¸a˜o:
(a) Elementos:
- mochilas (m);
- itens (i).
Conjuntos:
- de mochilas (M);
- de itens (I).
(b) Paraˆmetros:
- peso do item (pi);
- volume do item (vi);
- peso ma´ximo (Pmax);
- volume ma´ximo (V max).
(c) ∑
i∈I
xim = 1,∀m ∈M (61)
(d) ∑
i∈I
vixim = V
max,∀m ∈M (62)
Questo˜es de Provas Pa´gina 17 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
(e) ∑
i∈I
pixim = P
max,∀m ∈M (63)
(f)
min
∑
i∈I
ximpi (64)
(g)
Pmax V max
m1 100 50
m2 60 30
Peso Volume
i1 10 5
i2 25 10
i3 20 5
i4 40 15
i5 30 10
i6 50 10
(h) ∑
i∈I
xim = 1 (65)
m1 m2
i1 0 1
i2 1 0
i3 0 1
i4 0 1
i5 1 0
i6 1 0
∑
i∈I
ximvi ≤ V max (66)
m1 = (x11v1) + (x21v2) + (x31v3) + (x41v4) + (x51v5) + (x61v6)
m1 = (0 ∗ 5) + (1 ∗ 10) + (0 ∗ 5) + (0 ∗ 15) + (1 ∗ 10) + (1 ∗ 10) = 30
m2 = (x12v1) + (x22v2) + (x32v3) + (x42v4) + (x52v5) + (x62v6)
m2 = (1 ∗ 5) + (0 ∗ 10) + (1 ∗ 5) + (1 ∗ 15) + (0 ∗ 10) + (0 ∗ 10) = 30
Questo˜es de Provas Pa´gina 18 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
Func¸a˜o objetivo: ∑
i∈I
ximpi = (67)
= (x11p1)+(x21p2)+(x31p3)+(x41p4)+(x51p5)+(x61p6)+x12p1)+(x22p2)+
(x32p3)+(x42p4)+(x52p5)+(x62p6) = (0∗10)+(1∗25)+(0∗20)+(0∗40)+
(1∗30)+(1∗50)+(1∗10)+(0∗25)+(1∗20)+(1∗10)+(0∗25)+(0∗50) = 125
22. Para atender demandas de pec¸as de diferentes tamanhos a partir do corte em barras de
tamanho padra˜o, deve-se decidir quantos cortes de cada pec¸a deve-se realizar em cada
barra de forma a minimizar o total de barras utilizadas. Uma formulac¸a˜o ba´sica para
este problema foi proposto por Kantorovich e Zalgaller (1951). Com base na formulac¸a˜o
e na situac¸a˜o descrita, fac¸a o que se pede:
Formulac¸a˜o de Kantorovich e Zalgaller (1951):
min
∑
k∈K
yk (68)
sujeito a:
∑
k∈K
yik ≥ bi,∀i ∈ I (69)∑
i∈I
wixik ≤Wyk,∀k ∈ k (70)
yk ∈ {0, 1},∀k ∈ K (71)
xik ∈ Z+,∀k ∈ K, ∀i ∈ I (72)
(a) Quais sa˜o os elementos e conjuntos utilizados na formulac¸a˜o deste problema?
(b) Qual e´ o significado das varia´veis xik e yk?
(c) Explique o significado das restric¸o˜es 69.
(d) Explique o significado das restric¸o˜es 70.
(e) Suponha que existam barras de diferentes tipos de materiais e que cada pec¸a
deve ser feita de um material espec´ıfico, altere o modelo de forma a contemplar
esta situac¸a˜o.
(f) Crie uma instaˆncia com 2 barras e 6 tipos de pec¸as para o problema original.
(g) Encontre uma soluc¸a˜o via´vel para a instaˆncia definida em (0f). Defina o valor
de todas as varia´veis e da func¸a˜o objetivo para a soluc¸a˜o encontrada.
Soluc¸a˜o:
(a) Elementos:
- pec¸as (i);
- barras (k).
Conjuntos:
- de pec¸as (I);
- de barras (K).
Questo˜es de Provas Pa´gina 19 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
(b) xik - quantidades de pec¸as i ∈ I produzidas a partir da barra k ∈ K;
yk - se a barra k ∈ K e´ utilizada ou na˜o.
(c) O somato´rio de todas as pec¸as i ∈ I produzidas deve ser maior ou igual a
demanda de pec¸as i ∈ I.
(d) A soma do comprimento de todas as pec¸as produzidas a partir da barra
k ∈ K devera´ ser menor ou igual que o comprimento da barra k ∈ K, se
ela for utilizada.
(e)
min
∑
k∈K
yik (73)
sujeito a:
∑
k∈K
xik ≥ bi (74)
wixik ≤ wyk,∀k ∈ K,∀i ∈ I (75)
yk ∈ Z+∀k ∈ K (76)
xik ∈ Z+∀k ∈ K,∀i ∈ I (77)
(f) K = [1,2]
I = [1,2,3,4,5,6]
W=[100]
w=[2,4,5,6,7,8]
(g) x11 = 4, x21 = 3, x31 = 2, x41 = 3,x51 = 2, x61 = 1
y1 = 1, y2 = 0
23. Em 1957, Koopmans e Beckmann 1 apresentaram, pela primeira vez, o problema de
alocac¸a˜o quadra´tica - PAQ. Uma formulac¸a˜o ba´sica para este problema e´ dada por
(78-81). Com base na formulac¸a˜o do PAQ e na situac¸a˜o descrita abaixo, fac¸a o que se
pede:
Situac¸a˜o: O problema de leiaute de fa´brica pode ser resolvido atrave´s do PAQ. Para
tanto, deve-se considerar a existeˆncia de n locais (l) candidatos a` instalac¸a˜o de n
ma´quinas (m). Entre duas ma´quinas ha´ um fluxo de material (tm1m2) e entre dois locais
ha´ um custo de transporte (cl1l2). O Objetivo e´ determinar a alocac¸a˜o de ma´quinas em
locais de forma a minimizar o custo total de transporte de material.
Formulac¸a˜o:
min
∑
l1∈L
∑
l2∈L:l1 6=l2
∑
m1∈M
∑
m2∈M :m1 6=m2
cl1l2tm1m2xm1l1xm2l2 (78)
sujeito a:
∑
l∈L
xml = 1,∀m ∈M (79)∑
m∈M
xml = 1,∀l ∈ L (80)
xml ∈ {0, 1},∀m ∈M, ∀l ∈ L (81)
xik ∈ Z+,∀k ∈ K, ∀i ∈ I (82)
Questo˜es de Provas Pa´gina 20 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
(a) Quais sa˜o os elementos e conjuntos utilizados na formulac¸a˜o deste problema?
(b) Qual e´ o significado da varia´vel xml?
(c) Explique o significado das restric¸o˜es 79.
(d) Explique o significado das restric¸o˜es 80.
(e) Na forma (78-81), uma vez que a func¸a˜o objetivo e´ formada por uma expressa˜o
na˜o-linear em x, este problema na˜o e´ um PPLIM. Altere o problema de forma
a linearizar sua func¸a˜o objetivo. (Dica: introduza uma nova varia´vel para
representar a multiplicac¸a˜o e crie restric¸o˜es para definir seu valor).
(f) Suponha que uma vez que uma ma´quina m1 e´ instalada em um local l1, as
instalac¸o˜es de outras ma´quinas (m2 ∈ M\{m1}) ficariam restritas aos locais
contidos em Lm2m1l1 . Acrescente ao modelo restric¸o˜es para contemplar esta si-
tuac¸a˜o.
(g) Crie uma instaˆncia de tamanho 3 (treˆs ma´quinas e treˆs locais) para o problema
original.
(h) Encontre uma soluc¸a˜o via´vel para a instaˆncia definida em (0g). Defina o valor
de todas as varia´veis e da func¸a˜o objetivo para a soluc¸a˜o encontrada.
Soluc¸a˜o:
(a) Elementos:
- locais (l);
- ma´quinas (m).
Conjuntos:
- de locais (L);
- de ma´quinas (M).
(b) Utilizac¸a˜o das ma´quinas m ∈M nos locais l ∈ L.
(c) A ma´quina deve ser instalada em apenas um local.
(d) O local pode receber apenas uma ma´quina.
(e) ym1l1m2l2 ≤ xm1l1
ym1l1m2l2 ≤ xm2l2
ym1l1m2l2 ≥ xm1l1 + xm2l2 − 1
y ∈ {0, 1}
(f) ∑
l∈L
m2
m1xm2l1 + xm1l1 ≤ 1 (83)
(g) tm1m2 = 50
tm1m3 = 100
tm2m3 = 80
Questo˜es de Provas Pa´gina 21 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
cl1l2 = 3
cl1l3 = 1
cl2l3 = 2
(h) ∑
i∈I
xml = 1 (84)
 1 0 00 1 0
0 0 1

∑
m∈M
xml = 1 (85)
 1 0 00 1 0
0 0 1

24. No Problema da definic¸a˜o do tamanho do lote na˜o-capacitado (ULSP) deve-se decidir
quanto, quando produzir e quanto deve ser estocado de um produto. O objetivo e´
minimizar o custo total de produc¸a˜o formado pelos custos de estoque e de produc¸a˜o que
podem variar ao longo dos per´ıodos. Em cada per´ıodo, a empresa deve atender uma
demanda (dt) atrave´s da produc¸a˜o ou do estoque. Considerando s0 um paraˆmetro que
representa o estoque inicial no per´ıodo 0, pt o custo unita´rio de produc¸a˜o no per´ıodo t,λt
o custo unita´rio de estoque em t, dt a demanda em t e partindo da formulac¸a˜o ba´sica
para este problema dada por (86-88), fac¸a o que se pede:
Formulac¸a˜o:
min
∑
t∈T
ptxt + λtst (86)
sujeito a: st−1 + xt − dt = st,∀t ∈ T (87)
xt, st ∈ Z+,∀t ∈ T (88)
(a) Quais sa˜o os elementos e conjuntos utilizados na formulac¸a˜o deste problema?
(b)Qual e´ o significado das varia´veis xt? E das varia´veis st?
(c) Explique o significado das restric¸o˜es 87.
(d) O ULSP e´ um problema que pode ser resolvido em tempo polinomial, utili-
zando, por exemplo, o algoritmo proposto por Wagner e Whitin(1958). No
entanto, a versa˜o capacitada deste problema e´ muito mais complexa. Altere a
formulac¸a˜o para introduzir uma capacidade de produc¸a˜o Ct em cada per´ıodo
t.
(e) Considerando a resposta da letra 0d, modifique o problema para cobrar um
custo fixo f em todos os per´ıodos em que houver produc¸a˜o.
(f) Considerando a resposta da letra 0d, altere o problema para considerar mu´ltiplos
itens.
Questo˜es de Provas Pa´gina 22 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
Soluc¸a˜o:
(a) Elementos:
- per´ıodo (t);
Conjuntos:
- de per´ıodos (T);
(b) xt - indica a quantidade a ser produzida no per´ıodo t ∈ T .
st - indica a quantidade estocada no per´ıodo t ∈ T .
(c) Essa restric¸a˜o indica que o estoque do per´ıodo anterior mais a quantidade
produzida menos a demana tem que ser igual ao estoque atual.
(d) Introduzir uma capacidade de produc¸a˜o Ct em cada t ∈ T :
∑
t∈T
xt ≥ (1− yt)M + 1,∀t ∈ T (89)∑
t∈T
Ct ≥ ytdt − st−1,∀t ∈ T (90)
yt ∈ {0, 1},∀t ∈ T (91)
(e) Cobrar um custo fixo (CF) em todos os per´ıodos que houver produc¸a˜o.
min
∑
t∈T
ptxt + λtst + CFtyt (92)
(f) Considerar multiplos itens: para isso e´ necessa´rio indexar um i ∈ I que
acompanha o t ∈ T para todas as restric¸o˜es i varia de 1 a n→ {1, 2, ..., n}.
min
∑
i∈I
∑
t∈T
ptixti + λtisti + CFtiyti (93)
sujeito a: st−1 + xti − dti = sti,∀t ∈ T, ∀i ∈ I (94)∑
t∈T
∑
i∈I
xit ≥ (1− yitM + 1 (95)∑
t∈T
∑
i∈I
Cit ≥ ytidti − st−1 (96)
xti, sti ∈ Z+,∀t ∈ T, ∀i ∈ I (97)
yti ∈ {0, 1},∀t ∈ T, ∀i ∈ I (98)
25. 25. A partir da caracterizac¸a˜o e do modelo (99-109) apresentados para o problema de
sequenciamento de atividades em ma´quinas paralelas, fac¸a o que se pede.
Situac¸a˜o:
Uma unidade fabril possui diversas ma´quinas (m ∈ M) capazes de realizar as mesmas
atividades (i ∈ I). Com o objetivo de minimizar o custo de total de atraso destas
atividades, o gerente de produc¸a˜o deve alocar atividades a`s ma´quinas e decidir em qual
Questo˜es de Provas Pa´gina 23 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
ordem executa´-las. Cada atividade possui: um custo de atraso por unidade de tempo
(δi) transcorrido entre o te´rmino de sua execuc¸a˜o e sua data acertada de entrega (di);
um tempo de processamento (pim) que depende da ma´quina onde sera´ executado e uma
data de liberac¸a˜o, isto e´, momento a partir do qual a atividade podera´ ser executada
(ri). Uma vez que G representa um nu´mero muito grande, o modelo de PLIM (99-109)
representa a situac¸a˜o.
(a) Quais sa˜o os elementos utilizados neste modelo?
(b) Qual e´ o significado da varia´vel yim?
(c) Qual e´ o significado da varia´vel xij?
(d) Explique o significado das restric¸o˜es 100.
(e) Explique o significado das restric¸o˜es 101.
(f) Explique o significado das restric¸o˜es 102.
(g) Explique o significado das restric¸o˜es 103.
(h) Explique o significado das restric¸o˜es 105.
(i) Suponha que para executar uma atividade i logo apo´s uma atividade j em uma
ma´quina m tenha que se realizar a preparac¸a˜o de ma´quina que demanda um
tempo sijm. Escreva textualmente as implicac¸o˜es desta alterac¸a˜o na formulac¸a˜o
do problema (o que devera´ ser alterado?).
(j) Com base na situac¸a˜o descrita em 0i, reescreva a formulac¸a˜o do problema.
(k) Dado a Tabela 2 abaixo que refere-se a uma instaˆncia do problema com 2
ma´quinas e 4 atividades, apresente uma soluc¸a˜o via´vel para o problema e seu
respectivo custo.
(l) Para a instaˆncia apresentada na Tabela 2 qual seria um valor poss´ıvel para G?
Explique.
Formulac¸a˜o:
min
∑
i∈I
δiti (99)
sujeito a:
∑
m∈M
yim = 1,∀i ∈ I (100)
xij + xji ≤ 1,∀(i, j) ∈ I × I (101)
yim +
∑
m′∈M :m′ 6=m
yim′ + xij + xji ≤ 2,∀(i, j) ∈ IxI,∀m ∈M (102)
ti ≥ ci − di,∀i ∈ I (103)
ci + pjm −G(3− xij − yim − yjm) ≤ cj ,∀(i, j) ∈ IxI,∀m ∈M (104)
ri + pimyim ≤ ci,∀i ∈ I, ∀m ∈M (105)
yim ∈ {0, 1},∀i ∈ I, ∀m ∈M (106)
xij ∈ {0, 1},∀i ∈ I, ∀j ∈ I (107)
ti ≥ 0,∀i ∈ I (108)
ci ≥ 0,∀i ∈ I (109)
Questo˜es de Provas Pa´gina 24 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
Atv pi1 pi2 ri di δi
a1 2 1.5 1 3 0.5
a2 3 3 0 5 1.0
a3 1 1.5 0 3 1.0
a4 0.5 1.0 0 2 1.0
Tabela 2: Instaˆncia para o problema.
Soluc¸a˜o:
(a) Elementos:
- ma´quinas (m);
- atividades (i).
Conjuntos:
- de ma´quinas (M);
- de atividades (I).
(b) yim - varia´vel bina´ria que liga as ma´quinas a`s atividades. Indica que a
atividade i ∈ I esta´ alocada a` ma´quina m ∈M .
(c) xij - atividade i ∈ I que precede a atividade j ∈ J
(d) Tem-se que alocar exatamente uma ma´quina para cada atividade.
(e) Uma mesma atividade, independente de sua sequeˆncia, so´ pode ser alocada
no ma´ximo uma vez.
(f) 2 atividades so´ podem serem feitas em sequeˆncia se elas forem feitas na
mesma ma´quina.
(g) Indica que o atraso da atividade i ∈ I vai ser maior ou igual a data de
te´rmino da atividade i ∈ I menos a data acertada da entrega.
(h) Independente da ma´quina a ser alocada para a atividade i ∈ I, a sua data
de liberac¸a˜o somado a seu tempo de processamento sera´ sempre menor ou
igual a data de te´rmino da atividade i ∈ I.
(i) Deveria ser acrescentado o tempo de setup.
(j) Ci + Sijm + pjm −G(3− xij − yim − yjm) ≤ C + i
(k) Data de entrega (Ci):
C1 = 2, 5
C2 = 3
C3 = 4
C4 = 4, 5
Data acertada (di):
d1 = 3
d2 = 5
Questo˜es de Provas Pa´gina 25 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
d3 = 3
d4 = 2
Ci − di = ti
4− 3 = 1
4, 5− 2 = 2, 5
min
∑
i∈I
δiti = 1 ∗ 1 + 2, 5 ∗ 1 = 1 + 2, 5 = 3, 5 (110)
(l) Um valor poss´ıvel seria 8, pois ele e´ grande o suficiente para anular a
restric¸a˜o quando necessa´rio.
26. No Problema das Mochilas Mu´ltiplas (PMM) deve-se decidir se um item deve ser alocado
e em qual mochila de forma a maximizar a utilizade total. O problema considera um
limite de capacidade em termos de peso diferente para cada mochila e um peso associado
a cada item. Uma formulac¸a˜o ba´sica para este problema e´ dada por (111-114). Com
base na formulac¸a˜o do PMM, fac¸a o que se pede:
Formulac¸a˜o:
max
∑
m∈M
∑
i∈I
uimxim (111)
sujeito a:
∑
i∈I
pixmi ≤ Pm,∀m ∈M (112)∑
m∈M
xmi ≤ 1,∀i ∈ I (113)
xmi ∈ {0, 1},∀m ∈M,∀i ∈ I (114)
(a) Quais sa˜o os elementos e conjuntos utilizados na formulac¸a˜o deste problema?
(b) Qual e´ o significado da varia´vel xmi?
(c) Explique o significado das restric¸o˜es 112.
(d) Explique o significado das restric¸o˜es 113.
(e) Suponha que se tenha diferentes categorias de itens e, por algum motivo, deseja-
se possuir no mı´nimo um item de cada categoria. Altere a formulac¸a˜o de forma
a contemplar esta situac¸a˜o.
(f) Voltando ao problema original, suponha agora que todos os itens devam ser
carregados e que o objetivo passe a ser a minimizac¸a˜o do peso ma´ximo alocado
a uma mochila. Altere a formulac¸a˜o de forma a contemplar esta situac¸a˜o.
(g) Crie uma instaˆncia com 2 mochilas e 6 itens para o problema original.
(h) Encontre uma soluc¸a˜o via´vel para a instaˆncia definida em (0g). Defina o valor
de todas as varia´veis e da func¸a˜o objetivo para a soluc¸a˜o encontrada.
Questo˜es de Provas Pa´gina 26 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
(i) Encontre uma soluc¸a˜o via´vel do problema definido em (0f) para a instaˆncia
definida em (0g). Defina o valor de todas as varia´veis e da func¸a˜o objetivo para
a soluc¸a˜o encontrada.
Soluc¸a˜o:
(a) Elementos:
- mochilas (m);
- itens (i).
Conjuntos:
- de mochilas (M);
- de itens (I).
(b) xmi e´ uma varia´vel bina´riaque representa se o item i ∈ I vai ou na˜o ser
alocado a mochila m ∈M .
(c) O somato´rio dos pesos dos itens que va˜o para a mochila tem que ser menor
ou igual ao peso suportado por ela, para todo m ∈M .
(d) O item i ∈ I so´ pode ser alocado em uma mochila m ∈M .
(e)
max
∑
m∈M
∑
i∈I
∑
j∈J
uimjximj (115)
sujeito a:
∑
i∈I
∑
j∈J
pijxmij ≤ Pm,∀m ∈M (116)∑
m∈M
∑
j∈J
xmij ≥ 1,∀i ∈ I (117)
(f)
min
∑
m∈M
Pm (118)
sujeito a:
∑
i∈I
pi ≤ Pm,∀m ∈M (119)∑
m∈M
xmi = 1,∀i ∈ I (120)
xmi ∈ {0, 1},∀m ∈M,∀i ∈ I (121)
(g)
Mochila Pm
1 100
2 50
Questo˜es de Provas Pa´gina 27 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
Itens Peso
1 5
2 10
3 15
4 20
5 25
6 30
∑
m∈M
xmi ≤ 1 (122)
m1 m2
x1 0 1
x2 1 0
x3 0 1
x4 0 1
x5 1 0
x6 1 0
(h) ∑
i∈I
pixmi ≤ Pm,∀m ∈M (123)
m1 → 0 ∗ 5 + 1 ∗ 10 + 0 ∗ 15 + 0 ∗ 20 + 1 ∗ 25 + 1 ∗ 30 = 65
m2 → 1 ∗ 5 + 0 ∗ 10 + 1 ∗ 15 + 1 ∗ 20 + 0 ∗ 25 + 0 ∗ 30 = 40
max
∑
m∈M
∑
i∈I
uimxim (124)
m1 → 0 ∗ 1 + 1 ∗ 2 + 0 ∗ 3 + 0 ∗ 4 + 1 ∗ 5 + 1 ∗ 6 = 13
m2 → 1 ∗ 1 + 0 ∗ 2 + 1 ∗ 3 + 1 ∗ 4 + 0 ∗ 5 + 0 ∗ 6 = 8
(i) Peso total do item = 105kg.
Dividindo proporcionalmente: m1 = 70, m2 = 35
m1 → 1 ∗ 5 + 1 ∗ 10 + 0 ∗ 15 + 0 ∗ 20 + 1 ∗ 25 + 1 ∗ 30 = 70
m2 → 0 ∗ 5 + 0 ∗ 10 + 1 ∗ 15 + 1 ∗ 20 + 0 ∗ 25 + 0 ∗ 30 = 35
Questo˜es de Provas Pa´gina 28 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
27. A partir da caracterizac¸a˜o e do modelo (125-127) apresentados para o problema de
sequenciamento de aeronaves, fac¸a o que se pede.
Situac¸a˜o:
Considerando um voo (v ∈ V ) como o percurso de uma aeronave entre uma origem e
um destino em determinado hora´rio, e como rota (r ∈ R) um caminho alternativo a
ser percorrido por esta ao longo de um dia, o problema de sequenciamento de aeronaves
consiste em escolher a rota de menor custo de forma a garantir o atendimento a` demanda
por voos. Uma rota cobrira´ um determinado voo se λrv possuir valor 1 e zero caso
contra´rio. Sendo cr o custo da rota r o modelo representado pelas equac¸o˜es 125-127
representa a situac¸a˜o.
(a) Qual e´ o significado da varia´vel xr?
(b) Explique o significado das restric¸o˜es 126.
(c) Suponha que a empresa possua |A| aeronaves e para cada uma delas exista um
custo cra de atribuir a a ∈ A a rota r ∈ R. Desta forma, rescreva o problema
para garantir que o mesmo ira´ considerar tais alterac¸o˜es. Observe que apenas
uma aeronave podera´ realizar cada voo.
(d) Crie um conjunto de dados que possa representar uma situac¸a˜o real para o
problema.
Formulac¸a˜o:
min
∑
r∈R
crxr (125)
sujeito a:
∑
r∈R
λrvxr = 1,∀v ∈ V (126)
xr ∈ {0, 1},∀r ∈ R (127)
Soluc¸a˜o:
(a) xr - varia´vel bina´ria que indica se a rota esta´ sendo utilizada ou na˜o.
(b) Todo voo v ∈ V so´ podera´ ser atendido por uma rota r ∈ R.
(c) cra - custo para se atribuir uma aeronave a` rota r ∈ R.
tra - varia´vel bina´ria que indica se a aeronave esta´ sendo utilizada.
min
∑
r∈R
crxr +
∑
r∈R
∑
a∈A cratra (128)
sujeito a:
∑
r∈R
λrvxr = 1,∀v ∈ V (129)∑
a∈A
tra = 1,∀r ∈ R (130)
xr ∈ {0, 1},∀r ∈ R (131)
tra ∈ {0, 1},∀r ∈ R,∀a ∈ A (132)
Questo˜es de Provas Pa´gina 29 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
(d) V = {1, 2, 3}; R = {1, 2}; cr = {50, 100}
r1 r2
v1 1 0
v2 0 1
v3 0 1
28. A partir da caracterizac¸a˜o e do modelo (133-138) apresentados para o problema na˜o
capacitado de localizac¸a˜o de instalac¸o˜es, fac¸a o que se pede.
Situac¸a˜o:
Para melhorar o n´ıvel de servic¸o log´ıstico e diminuir os custos de transporte, uma em-
presa deve decidir onde e quantos armaze´ns deve abrir dentre uma se´rie de cidades
candidatas(s ∈ S). Cada candidata possui um custo fixo de abertura (fs), isto e´, um
custo associado a` sua construc¸a˜o, que so´ e´ cobrado uma u´nica vez. O armaze´m existe
para atender a demanda dos clientes da empresa (c ∈ C). Para cada cliente e´ definido
um tempo ma´ximo de entrega (tmaxc ) e um volume associado (em toneladas/ano) (vc).
O cliente pode ser atendido diretamente da fa´brica ou a partir de um armaze´m. Tendo
conhecimento do custo (por tonelada) e do prazo de se entregar em um determinado
cliente a partir de cada sede candidata e tambe´m da fa´brica (csc, tsc, cic e tic, respecti-
vamente), o modelo modelo (133-138) representa a situac¸a˜o.
Formulac¸a˜o:
min
∑
s∈S
fsys +
∑
s∈S
∑
c∈C
cscvcxsc +
∑
c∈C
cicvcxic (133)
sujeito a:
∑
s∈S
xsc + xic = 1,∀c ∈ C (134)∑
s∈S
tscxsc + ticxic ≤ tc,∀c ∈ C (135)∑
c∈C
xsc ≤ ys|C|,∀s ∈ S (136)
ys ∈ {0, 1},∀s ∈ S (137)
xsc ∈ {0, 1},∀s ∈ S, ∀c ∈ C (138)
(a) Quais sa˜o os elementos utilizados neste modelo?
(b) Qual e´ o signficado da varia´vel ys?
(c) Qual e´ o significado da varia´vel xsc?
(d) Explique o significado das restric¸o˜es 134.
(e) Explique o significado das restric¸o˜es 135.
(f) Explique o significado das restric¸o˜es 136.
(g) Suponha que o modelo em questa˜o passe a ser capacitado, isto e´, os armaze´ns
passem a possuir um limite de capacidade anual qs. Considerando que a fa´brica
na˜o possui limite de capacidade, escreva textualmente as implicac¸o˜es desta
alterac¸a˜o na formulac¸a˜o do problema.
(h) Com base na situac¸a˜o descrita em (0g), reescreva a formulac¸a˜o do problema.
Questo˜es de Provas Pa´gina 30 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
(i) Retornando a` formulac¸a˜o original, suponha que exista a possibilidade de re-
alizar a entrega para um cliente a partir de diferentes modais de transportes
(rodovia´rio, ferrovia´rio, ae´reo...) a partir de qualquer ponto de partida para
qualquer cliente. Escreva textualmente as implicac¸o˜es desta alterac¸a˜o na for-
mulac¸a˜o do problema.
(j) Com base na situac¸a˜o descrita em (0i), reescreva a formulac¸a˜o do problema.
Soluc¸a˜o:
(a) Elementos:
- clientes (c);
- cidades candidatas (s);
- fa´bricas (i).
(b) ys - varia´vel de decisa˜o, se ira´ ser cobrado ou na˜o um custo fixo quando
um armaze´m for aberto.
(c) xsc - se o cliente c ∈ C for atendido pelo armaze´m ou na˜o.
(d) O cliente deve ser atendido uma u´nica vez, ou diretamente pela fa´brica
ou pelo armaze´m.
(e) O tempo ma´ximo de entrega deve ser respeitado, sendo que a mercadoria
deve ser entregue ou pelo armaze´m ou pela fa´brica.
(f) So´ e´ poss´ıvel realizar a entrega da mercadoria de um armaze´m se ele estiver
aberto.
(g) Deveria ser criado um paraˆmetro para definir a capacidade do armaze´m
(qi) e tambe´m ser criado uma restric¸a˜o na qual a quantidade de demanda
dos produtos a serem entregues pelo armaze´m aos clientes seja menos que
sua capacidade.
(h)
min
∑
s∈S
fsys +
∑
s∈S
∑
c∈C
cscvcxsc +
∑
c∈C
cicvcxic (139)
sujeito a:
∑
s∈S
xsc + xic = 1,∀c ∈ C (140)∑
c∈C
xsc ≤ ys|C|,∀s ∈ S (141)∑
c∈C
vcxsc ≤ qsys,∀s ∈ S (142)
(i) Deveria criar um novo elemento modal de transporte (m) que sera´ associ-
ado ao custo de entrega dos armaze´ns e das fa´bricas para os clientes. Com
isso, dois paraˆmetros sera˜o alterados, o Cicm sera´ o custo de entrega da
Questo˜es de Provas Pa´gina 31 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
fa´brica i ∈ I ao cliente c ∈ C atrave´s do modal m ∈ M . O mesmo acon-
tece com Cscm, que e´ o cust dos armaze´ns. Esse custo sera´ direcionado a
func¸a˜o objetivo afim de minimiza´-lo.
(j)
min
∑
s∈S
fsys +
∑
s∈S
∑
m∈M
∑
c∈C
cscmvcx
m
sc +
∑
c∈C
∑
m∈M
cicmvcx
m
ic (143)
sujeito a:
∑
s∈S
∑
m∈M
xmsc + x
m
ic = 1,∀c ∈ C (144)∑
s∈S
∑
m∈M
tscx
m
sc + ticx
m
ic ≤ tc,∀c ∈ C (145)∑
c∈C
∑
m∈M
xmsc ≤ ys|C|,∀s ∈ S (146)
ys ∈ {0, 1},∀s ∈ S (147)
xsc ∈ {0, 1},∀s ∈ S, ∀c ∈ C (148)
Questo˜es de Provas Pa´gina 32 de 50
ENP160 - Otimizac¸a˜o Combinato´ria2018/1 Questo˜es de Provas
4 Relaxac¸a˜o Lagrangeana
29. Relaxac¸a˜o Lagrangeana:
max 3x1 + 4x2 + 2x3 + x4 + 2x5 (149)
sujeito a: 2x1 − x2 + x3 + x4 + x5 ≤ 1 (150)
−x1 + 3x2 + x3 − x4 − 2x5 ≤ 1 (151)
2x1 + x2 − x3 + x4 + 3x5 ≤ 1 (152)
x1, x2, x3 ∈ {0, 1} (153)
x4, x5 ≥ 0 (154)
(a) Relaxe a restric¸a˜o 1 (231) e escreva o Problema Dual Lagrangeano.
(b) Suponha que durante a k-e´sima iterac¸a˜o do Me´todo do Subgradiente, o valor
da varia´vel dual utilizada como penalidade na letra (0a) seja u1k = 2, o stepsize
seja = 0, 5 e a soluc¸a˜o corrente x∗k(u
1
k) = (0 0 0 0
1
3
). Encontre o valor de uk+11 .
(c) Explique o objetivo do uso da Relaxac¸a˜o Lagrangeana.
Soluc¸a˜o:
(a)
min−3x1 − 4x2 − 2x3 − x4 − 2x5 (155)
sujeito a: −2x1 + x2 − x3 − x4 − x5 ≤ −1 (156)
x1 − 3x2 − x3 + x4 + 2x5 ≤ −1 (157)
−2x1 − x2 + x3 − x4 − 3x5 ≤ −1 (158)
x1, x2, x3 ∈ {0, 1} (159)
x4, x5 ≥ 0 (160)
min−3x1 − 4x2 − 2x3 − x4 − 2x5 − U(−2x1 + x2 − x3 − x4 − x5 + 1)(161)
sujeito a: x1 − 3x2 − x3 + x4 + 2x5 ≤ −1 (162)
−2x1 − x2 + x3 − x4 − 3x5 ≤ −1 (163)
x1, x2, x3 ∈ {0, 1} (164)
x4, x5 ≥ 0 (165)
U ∈ R (166)
(b) uk+11 = uk − γkx(d−D∗x(uk))
uk+11 = 2− 0, 5(2x0− 0 + 0 + 0 + 13 ≤ 1)
uk+11 = 2− 0, 5(23)
uk+11 =
5
3
Questo˜es de Provas Pa´gina 33 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
(c) A relaxac¸a˜o Lagrangiana e´ usada para reformular problemas a fim de
encontrar soluc¸a˜o de maneira mais fa´cil ou reformular o problema para
melhorar o limite.
30. Corrija as sentenc¸as a seguir:
(a) A Relaxac¸a˜o Lagrangiana de um PPLIM tem como objetivo encontrar uma
soluc¸a˜o o´tima para o mesmo.
(b) No Me´todo de Balas, todas as varia´veis inativas sa˜o candidatas a ativac¸a˜o, isto
e´, a receber o valor 1.
(c) O crite´rio de parada de me´todo do branch and bound. e´ um nu´mero ma´ximo
de iterac¸o˜es estabelecidos previamente.
(d) Os cortes de Gomory sa˜o va´lidos por na˜o eliminar soluc¸o˜es via´veis do problema
relaxado.
Soluc¸a˜o:
(a) A Relaxac¸a˜o Lagrangiana de um PPLIM tem como objetivo encontrar
uma soluc¸a˜o o´tima para o mesmo de maneira mais fa´cil ou reformular o
problema para melhorar os limites.
(b) No me´todo de Balas, apenas as varia´veis livres sa˜o candidatas a ativac¸a˜o,
isto e´, a receber o valor 1.
(c) No me´todo branch and bound os crite´rios de parada sa˜o poda por otima-
lidade, poda por inviabilidade, poda por limite ou um nu´mero ma´ximo de
iterac¸o˜es pre´-estabelecidas.
(d) Os cortes de gomory sc¸ao va´lidos por eliminar soluc¸o˜es via´veis que na˜o
sa˜o inteiras, restringindo a regia˜o de viabilidade do problema relaxado
Questo˜es de Provas Pa´gina 34 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
31. A partir da formulac¸a˜o de Kantorovich e Zalgaller (1951) para o problema de corte uni-
dimensional (1-5) apresentado, Escolha uma restric¸a˜o para relaxar e escreva o Problema
Dual Lagrangeano.
Formulac¸a˜o de Kantorovich e Zalgaller (1951):
min
∑
k∈K
yk (167)
sujeito a:
∑
k∈K
yik ≥ bi,∀i ∈ I (168)∑
i∈I
wixik ≤Wyk,∀k ∈ k (169)
yk ∈ {0, 1},∀k ∈ K (170)
xik ∈ Z+,∀k ∈ K, ∀i ∈ I (171)
K conjunto de barras
I conjunto de pec¸as
bi demanda por i
W comprimento das barras
wi comprimento das pecc¸as
yk indica o uso da barra k
xik quantidade pec¸as i no corte da barra k
Soluc¸a˜o:
min
∑
k∈K
yk − Ui(bi + (
∑
k∈K
xik)) (172)
sujeito a:
∑
i∈I
wixik ≤Wyk,∀k ∈ K (173)
yk ∈ 0, 1,∀k ∈ K (174)
xik ∈ Z+,∀k ∈ K,∀i ∈ I (175)
Ui ∈ R+,∀i ∈ I (176)
32. Relaxac¸a˜o Lagrangeana:
(a) Como pode ser feita a atualizac¸a˜o do stepsize no me´todo do subgradiente?
(b) Qual a regra de atualizac¸a˜o das varia´veis duais em um problema escrito na
forma padra˜o (maximizac¸a˜o, ≤)?
(c) Explique como a Relaxac¸a˜o Lagrangeana pode ser utilizada para auxiliar na
busca pela soluc¸a˜o o´tima.
(d) Explique o que e´ uma Heur´ıstica Lagrangeana.
Questo˜es de Provas Pa´gina 35 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
Soluc¸a˜o:
(a) O me´todo usual e´ dividir γk por dois apo´s m interac¸o˜es sem melhora o
limite superior do dual lagrangeano.
(b) E´ utilizar γk =
Z∗(uk)−DˆL
||d−Dx(uk)||2 onde DˆL pode ser substituido por um limite
inferior, mas se o limite for ruim, o me´todo na˜o ira´ convergir.
(c) Com a relaxc¸a˜o lagrangeana podemos obter um limite de relaxc¸a˜o mais
estreito que o limite linear, com isso a a´rea de soluc¸o˜es via´veis ira´ diminuir.
(d) O me´todo da relaxac¸a˜o lagrangeana na˜o garante que a soluc¸a˜o encontrada
seja via´vel para o problema, mas mesmo encontrada na˜o quer dizer que ela
e´ o´tima, mas com a estrtura da relaxac¸a˜o lagrangeana podemos obter uma
soluc¸a˜o que pode ser ta˜o boa quanto a o´tima do problema denominada de
heur´ıstica lagrangeana.
33. Marque verdadeiro(v) ou falso (f) para as afirmativas abaixo e justifique quando a
sentenc¸a na˜o for verdadeira.
(a) A resposta gerada pela Relaxac¸a˜o Lagrangiana de um PPLIM e´ uma soluc¸a˜o
o´tima para o mesmo.
(b) O uso do Me´todo do Subgradiente na Relaxac¸a˜o Lagrangiana tem como obje-
tivo encontrar o valor o´timo da varia´vel dual associada a`s restric¸o˜es dualizadas.
Soluc¸a˜o:
(a) Falso, o me´todo da Relaxac¸a˜o Lagrangeana de um PPLIM na˜o garante
que se encontre um soluc¸a˜o via´vel para o problema. Mesmo quando uma
soluc¸a˜o via´vel e´ encontrada, ela na˜o e´, necessariamente, o´tima.
(b) Verdadeiro.
Questo˜es de Provas Pa´gina 36 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
34. A partir da modelo (177-181) apresentado, escolha uma restric¸a˜o para relaxar e escreva
o Problema Dual Lagrangiano.
Formulac¸a˜o:
min 4x1 + 6x2 + 2x3 + 6x4 + 7x5 − 7x6 (177)
sujeito a: 6x1 − 4x2 − 6x4 + 2x6 ≥ 0 (178)
3x1 + x2 + 7x3 + 7x4 + 8x5 − 8x6 ≥ 17 (179)
−9x1 + 4x2 + 5x3 + 2x4 + 8x5 − 8x6 ≥ 15 (180)
xi ∈ {0, 1},∀i ∈ {1, ..., 6} (181)
Soluc¸a˜o:
Restric¸a˜o escolhida para relaxar e´ 177
max−4x1 − 6x2 − 2x3 − 6x4 − 7x5 + 7x6 + U ∗ (17− 3x1 + x2 + 7x3 + 7x4 + 8x5 − 8x6)(182)
sujeito a: −6x1 + 4x2 + 6x4 − 2x6 ≤ 0 (183)
9x1 − 4x2 − 5x3 − 2x4 − 8x5 + 8x6 ≤ 15 (184)
xi ∈ {0, 1},∀i (185)
Questo˜es de Provas Pa´gina 37 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
5 Branch and Bound
35. Para o PPLIM definido por (235-191) e o quadro final do simplex de sua relaxac¸a˜o linear
(235), fac¸a o que se pede:
max 3x1 + 4x2 + 2x3 + x4 + 2x5 (186)
sujeito a: 2x1 − x2 + x3 + x4 + x5 ≤ 1 (187)
−x1 + 3x2 + x3 − x4 − 2x5 ≤ 1 (188)
2x1 + x2 − x3 + x4 + 3x5 ≤ 1 (189)
x1, x2, x3 ∈ {0, 1} (190)
x4, x5 ≥ 0 (191)
Eq vb Z x1 x2 x3 x4 x5 f1 f2 f3 f4 f5 f6 LD
(0) Z 1 1 0 0 0,25 0 1,625 1,5 1,125 0 0 0 4,25
(1) x2 1 0 1 0 -0,125 0 -0,0625 0,25 0,1875 0 0 0 0,375
(2) x3 0 1 0 1 0,375 0 0,6875 0,25 -0,0625 0 0 0 0,875
(3) x5 0 2 0 0 0,5 1 0,25 0 0,25 0 0 0 0,5
(4) f4 0 1 0 0 0 0 0 0 0 1 0 0 1
(5) f5 0 0 0 0 0,125 0 0,0625 -0,25 -0,1875 0 1 0 0,625
(6) f6 0 -1 0 0 -0,375 0 -0,6875 -0,25 0,0625 0 0 1 0,125
(a) Escolha uma varia´vel para fazer o branch e justifique sua escolha.
(b) Escreva os dois novos sub-problemas encontrados apo´s o branch realizado na
letra (0a).
(c) Cite e explique as treˆs formas de poda no me´todo branch and bound.
(d) Escolha uma restric¸a˜o e crie um Corte de Gomory para o problema.
(e) Escreva a nova linha do quadro Simplex.
(f) Qual varia´vel devera´ sair da base? E qual varia´vel devera´ entrar?
(g) Realize uma iterac¸a˜o do me´todo dos Cortes de Gommory para o resultado final
da relaxac¸a˜o linear.
(h) Escreva a formulac¸a˜o do novo problema apo´s o corte.
(i) Para o novo quadro gerado em 0g, escolha uma varia´vel para fazer o branching
e escreva um dos subproblema gerados.
(j) Incorpore a restric¸a˜o de branching no quadro final do simplex e encontre o novo
o´timo para osubproblema.
(k) Qual nome se da´ ao procedimento esta´ sendo utilizado para solucionar o pro-
blema nesta questa˜o (passos das letras 0g-0j)?
Soluc¸a˜o:
(a) Escolha X2 pois dentre as varia´veis de decisa˜o ela e´ a mais fracionada.
Questo˜es de Provas Pa´gina 38 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
(b)
(c) i. Poda por limite - Ocorre Quando o limite superior para um determi-
nado subproblema e´ menor que o melhor limite inferior conhecido.
ii. Poda por inviabilidade - Ocorre quando o subproblema e´ invia´vel
iii. Poda por otimalidade - Ocorre qiando se dete´m uma soluc¸a˜o o´tima
inteira para um subproblema relaxado
(d) O corte sera´ feito na restric¸a˜o x2 pois ela e´ a restric¸a˜o fraciona´ria com
valor mais pro´ximo de 0,5.
O corte ficara´:
(−0, 0625−b−0, 0625c)∗f1+(0, 25−b0, 25c)∗f2+(0, 1875−b0, 1875c)∗
f3 + (0− b0c) ∗ f4 + (0− b0c) ∗ f5 + (0− b0c) ∗ f6 ≤ (0, 375− b0, 375c)
S = −0, 0625∗f1+0, 25∗f2+0, 1875∗f3+0∗f4+0∗f5+0∗f6 ≤ 0, 375
(e) Nova linha simplex.
Eq vb Z x1 x2 x3 x4 x5 f1 f2 f3 f4 f5 f6 S LD
(0) Z 1 1 0 0 0,25 0 1,625 1,5 1,125 0 0 0 0 4,25
(1) x2 1 0 1 0 -0,125 0 -0,0625 0,25 0,1875 0 0 0 0 0,375
(2) x3 0 1 0 1 0,375 0 0,6875 0,25 -0,0625 0 0 0 0 0,875
(3) x5 0 2 0 0 0,5 1 0,25 0 0,25 0 0 0 0 0,5
(4) f4 0 1 0 0 0 0 0 0 0 1 0 0 0 1
(5) f5 0 0 0 0 0,125 0 0,0625 -0,25 -0,1875 0 1 0 0 0,625
(6) f6 0 -1 0 0 -0,375 0 -0,6875 -0,25 0,0625 0 0 1 0 0,125
(7) S 0 0 0 0 0 0 -0,0625 0,25 0,1875 0 0 0 1 0,375
(f) A varia´vel que vai entrar na base sera´ a f1 e a que vai sair sera´ a x5.
(g) Responsa´vel: [Aluno 3]
(h) Responsa´vel: [Aluno 3]
(i) Responsa´vel: [Aluno 3]
(j) Responsa´vel: [Aluno 3]
(k) Responsa´vel: [Aluno 3]
Questo˜es de Provas Pa´gina 39 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
36. Explique o que e´ Branch and Cut.
Soluc¸a˜o:
E´ um algoritmo de Branch and Bound onde planos de corte sa˜o gerados ao longo da
a´rvore de subproblemas. A ideia e´ inicialmente tornar os subproblemas mais justos
e quando os cortes na˜o surtirem mais efeito, voltar ao Branch and Bound.
37. Corrija as sentenc¸as a seguir:
(a) O crite´rio de parada de me´todo do Branch and Bound e´ um nu´mero ma´ximo
de iterac¸o˜es estabelecidos previamente.
Soluc¸a˜o:
Os crite´rios de parada do me´todo do Branch and Bound sa˜o: nu´mero ma´ximo de
iterac¸o˜es estabelecidos previamente, poda por limite, poda por inviabilidade e poda
por otimalidade.
38. Resolva a relaxac¸a˜o linear do problema definido pelo modelo (192-195) pelo me´todo
gra´fico, Escolha uma varia´vel para realizar o branching e represente graficamente os dois
subproblemas.
Formulac¸a˜o:
max 10x1 + 15x2 (192)
sujeito a: 8x1 + 4x2 ≤ 40 (193)
15x1 + 30x2 ≤ 200 (194)
x1, x2 ∈ Z+ (195)
Questo˜es de Provas Pa´gina 40 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
Soluc¸a˜o:
Branching => x1 ≤ 2 x1 ≥ 3
39. Marque verdadeiro(v) ou falso (f) para as afirmativas abaixo e justifique quando a
sentenc¸a na˜o for verdadeira.
(a) O me´todo Branch and Bound na˜o e´ um algoritmo polinomial.
(b) No me´todo de Branch and Cut, Cortes de Gomory sa˜o feitos em cada no´ da
a´rvore de busca do Branch and Bound.
Soluc¸a˜o:
(a) Verdadeiro.
(b) Verdadeiro.
Questo˜es de Provas Pa´gina 41 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
40. Resolva a relaxac¸a˜o linear do problema definido pelo modelo (196-201) pelo me´todo
gra´fico, escolha uma varia´vel para realizar o branching e represente graficamente os dois
subproblemas.
Formulac¸a˜o:
max 4x1 + 6x2 (196)
sujeito a: x1 + 2x2 ≤ 8 (197)
2x1 − 2x2 ≤ 5 (198)
x1 ≥ 1 (199)
x2 ≥ 1 (200)
x1, x2 ∈ Z+ (201)
Soluc¸a˜o:
Solucao 1:
Utilizando o me´todo gra´fico a reta vermelha mostra que a soluc¸a˜o se encontra no
ponto c com os valores de x1 = 4, 3333 e x2 = 1, 83333. Como buscamos a soluc¸a˜o
o´tima inteira devemos realizar o branching onde olhando para a variavel x1 temos ou
x1 ≤ 4 ou x1 ≥ 5. Sendo x1 ≥ 5 infact´ıvel escolhemos x1 ≤ 4, e acrescentamos essa
restric¸a˜o ao problema original e resolvemos novamente utilizando o metodo gra´fico
na soluc¸a˜o 2 com soluc¸a˜o otima inteira no ponto c onde x1 = 4 e x2 = 1.
Questo˜es de Provas Pa´gina 42 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
Solucao 2:
Questo˜es de Provas Pa´gina 43 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
41. Branch and Bound:
max 3x1 + 4x2 (202)
sujeito a: 0, 4x1 + 2x2 ≤ 3 (203)
0, 4x1 − 0, 4x2 ≤ 1 (204)
x1, x2 ∈ Z2+ (205)
(a) Resolva graficamente a relaxac¸a˜o linear do problema (202-205).
(b) Escolha uma varia´vel para fazer o branch e, no mesmo gra´fico, represente os
dois novos subproblemas.
Soluc¸a˜o:
(a) Relaxac¸a˜o linear do problema.
(b) {
0, 4x1 + 2x2 = 3
0, 4x1 − 0, 4x2 = 1 (−1) (206)
2, 4x2 = 2 ;x2 = 0, 83 (207)
0, 4x1 − 0, 4 ∗ 0, 83 = 1 ;x1 = 3, 33 (208)
42. Sobre o me´todo de Branch and Bound :
(a) Explique como e´ feita divisa˜o de problema em subproblemas filhos, isto e´, a
etapa de Branch.
(b) Enumere e explique os tipos de poda da a´rvore de soluc¸a˜o.
(c) Qual e´ o crite´rio de parada do me´todo?
Questo˜es de Provas Pa´gina 44 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
Soluc¸a˜o:
(a) Os subproblemas sa˜o gerados a partir do problema original, onde cada
subproblema e´ obtido atrave´s do arredondamento de varia´veis na soluc¸a˜o
do problema relaxado.
(b) Os 3 me´todos sa˜o:
• Poda por otimilidade: ocorre quando se obte´m uma soluc¸a˜o o´tima
para um problema relaxado;
• Poda por inviabilidade: ocorre quando o subproblema e´ invia´vel;
• Poda por limite: ocorre quando o limite superior para um determi-
nado subproblema e´ menos que o melhor limite inrior conhecido.
(c) O crite´rio de parada e´ quando todos os subproblemas esta˜o solucionados,
ou seja, foram ”podados”por alguma das 3 podas.
43. Resolva a relaxac¸a˜o do problema representado pelas inequac¸o˜es (209-214) pelo simples
e realize um primeiro corte por branch and bound ou planos cortantes.
Formulac¸a˜o:
max 4x1 + 6x2 (209)
sujeito a: x1 + 2x2 ≤ 8 (210)
2x1 − 2x2 ≤ 5 (211)
x1 ≥ 1 (212)
x2 ≥ 1 (213)
x1, x2 ∈ Z+ (214)
Soluc¸a˜o:
max 4x1 + 6x2 (215)
sujeito a: x1 + 2x2 + x3 = 8 (216)
2x1 − 2x2 + x4 = 5 (217)
x1 − x4 +A1 = 1 (218)
x2 − x5 +A2 = 1 (219)
Lb P0 P1 P2 P3 P4 P5 P6 P7 P8
0 8 1 2 1 0 0 0 0 0
0 5 2 -2 0 1 0 0 0 0
-1 1 1 0 0 0 -1 0 1 0
-1 1 1 0 0 0 0 -1 0 1
Z -2 -1 -1 0 0 1 1 0 0
Questo˜es de Provas Pa´gina 45 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
Lb P0 P1 P2 P3 P4 P5 P6 P7 P8
0 7 0 2 1 0 1 0 -1 0
0 3 0 -2 0 1 2 0 -2 0
0 1 1 0 0 0 -1 0 1 0
-1 1 0 1 0 0 0 -1 0 1
Z -1 0 -1 0 0 0 1 1 0
Lb P0 P1 P2 P3 P4 P5 P6 P7 P8
0 5 0 0 1 0 1 2 -1 -2
0 5 0 0 0 1 2 -2 -2 2
0 1 1 0 0 0 -1 0 1 0
0 1 0 1 0 0 0 -1 0 1
Z 0 0 0 0 0 0 0 1 1
Fase II:
Lb P0 P1 P2 P3 P4 P5 P6
0 5 0 0 1 0 1 2
0 5 0 0 0 1 2 -2
4 1 1 0 0 0 -1 0
6 1 0 1 0 0 0 -1
Z 10 0 0 0 0 -4 -6
Lb P0 P1 P2 P3 P4 P5 P6
0 5
2
0 0 1
2
0 1
2
1
0 10 0 0 1 1 3 0
4 1 1 0 0 0 -1 0
6 7
2
0 1 1
2
0 1
2
0
Z 25 0 0 3 0 -1 0
Lb P0 P1 P2 P3 P4 P5 P6
0 5
6
0 0 1
3
−1
6
0 1
0 10
3
0 0 1
3
1
3
1 0
4 13
3
1 0 1
3
1
3
0 0
6 11
6
0 1 1
3
−1
6
0 0
Z 85
3
0 0 10
3
1
3
0 0
x1 =
13
3
→ dx1e = 5, bx1c = 4
x2 =
11
6
→ dx2e = 2, bx2c = 1
Z = 85
3
Questo˜es de Provas Pa´gina 46 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
6 Me´todos de planos cortantes
44. Seja o poliedro P := {∑i∈I aixi ≥ b, xi ∈ {0, 1},∀i ∈ I}. Dado h > 0, prove que o corte
gerado pela inequac¸a˜o 221 e´ va´lido para P.∑
i∈I
⌈ai
h
⌉
xi ≥
⌈b
h
⌉
(220)
Soluc¸a˜o:
E´ sabido que o
⌈
ai
h
⌉
xi ≥ aih onde o teto ∈ Z. Ale´m disso, foi informado que o xi e´ o
bina´rio (0 ou 1), enta˜o podemos afirmar que:
∑
i∈I
⌈ai
h
⌉
xi ≥
∑
i∈I
ai
h
xi ≥
⌈
b
h
⌉
(221)
45. Mostre que para o poliedro P := {(x1, x2, x3)|21, 5x1 + 43x2 + 86x3 ≥ 45, x1, x2, x3 ∈{0, 1}} possui a inequac¸a˜o 222 como desigualdade va´lida.∑
i∈I
x1 + x2 + 2x3 ≥ 2 (222)
Soluc¸a˜o:
Calculando o teto de cada parcela e depois testar
⌈
21, 5
43
⌉
x1 +
⌈
43
43
⌉
x2 +
⌈
86
43
⌉
x3 ≥
⌈
45
43
⌉
(223)
1 + 1 + 2 ≥ 2 (224)
46. A partir do quadro final do Simplex da relaxac¸a˜o linear de um PPLIM representado na
tabela, fac¸a o que se pede:
Eq vb Z x1 x2 f1 f2 f3 LD
(0) Z 1 10 0 0 5
2
0 50
(1) f1 0 2 0 1
−1
4
0 15
(2) x2 0 1 1 0
1
8
0 5
2
(3) f3 0 -2 0 0
−1
4
1 5
(a) Escreva um corte de Gomory para essa soluc¸a˜o.
Questo˜es de Provas Pa´gina 47 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
(b) Represente o corte em termo das varia´veis originais do problema (x1, x2).
(c) Escreva o novo quadro simplex.
(d) Discuta sobre a viabilidade primal e dual e sobre a viabilidade da nova soluc¸a˜o.
Soluc¸a˜o:
Responsa´vel: [Aluno 3]
47. Escreva a inequac¸a˜o que representa um corte de gommory e explique com suas palavras
o funcionamento do me´todo.
Soluc¸a˜o:
Para qualquer u ∈ R+m e para todo x que satisfaz:
k∑
j=1
aijxj ≤ bi,∀i = 1, 2, 3...,m (225)
Temos que:
m∑
i=1
ui
k∑
j=1
aijxj ≤
m∑
i=1
uibi (226)
Desse modo, todas as soluc¸o˜es que satisfazem (225) e xj ≥ 0 tambe´m satisfazem:
k∑
j=1
⌈
m∑
i=1
uiaij
⌉
xj ≤
m∑
i=1
uibi (227)
Tendo:
k∑
j=1
⌈
m∑
i=1
uiaij
⌉
xj ≤
m∑
i=1
uibi (228)
E considerando que xj ∈ Z obtemos o Plano de Corte de Chva´tal-Gomory:
k∑
j=1
⌈
m∑
i=1
uiaij
⌉
xj ≤
⌈
m∑
i=1
uibi
⌉
(229)
O me´todo busca refinar o conjunto via´vel de um PPLI e a cada iterac¸a˜o o algoritmo
adiciona uma restric¸a˜o linear que e´ satisfeita por uma soluc¸a˜o inteira do problema
original eliminando as partes fraciona´rias da soluc¸a˜o na˜o inteira. O algoritmo chega
ao fim quando uma soluc¸a˜o inteira e´ obtida.
Questo˜es de Provas Pa´gina 48 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
48. Pre´-processamento:
max 3x1 + 4x2 + 2x3 + x4 + 2x5 (230)
sujeito a: 2x1 − x2 + x3 + x4 + x5 ≤ 1 (231)
−x1 + 3x2 + x3 − x4 − 2x5 ≤ 1 (232)
2x1 + x2 − x3 + x4 + 3x5 ≤ 1 (233)
x1, x2, x3 ∈ {0, 1} (234)
x4, x5 ≥ 0 (235)
(a) Verifique os limites superiores e inferiores para as varia´veis x4 e x5
(b) Apo´s a definic¸a˜o dos novos limites, verifique a viabilidade do problema.
(c) Apo´s a definic¸a˜o dos novos limites, verifique se a restric¸a˜o 1 (231) e´ redundante.
Soluc¸a˜o:
(a)
min−3x1 − 4x2 − 2x3 − x4 − 2x5 (236)
sujeito a: 2x1 − x2 + x3 + x4 + x5 ≤ 1 (237)
−x1 + 3x2 + x3 − x4 − 2x5 ≤ 1 (238)
2x1 + x2 − x3 + x4 + 3x5 ≤ 1 (239)
x1, x2, x3 ∈ {0, 1} (240)
x4, x5 ≥ 0 (241)
Limite Inferior Limite Superior
0 1
0 1
0 1
0 2
0 2
3
x4 : R1 => x4 ≤ 1−2x1+x2−x3−x51 x4 ≤ 1−0+1−0−01 x4 ≤ 2
R2 => −x4 ≥ 1+x1−3x2−x3+x51 −x4 ≥ 1+1−0−0+∞1 x4 ≤ −∞
R3 => x4 ≤ 1−2x1−x2+x3−3x51 x4 ≤ 1−0−0+1−01 x4 ≤ 2
x5 : R1 => x5 ≤ 1−2x1+x2−x3−x41 x5 ≤ 1−0+1−0−01 x5 ≤ 2
R2 => −x5 ≥ 1+x1−3x2−x3+x41 −x5 ≥ 1+1−0−0+21 x5 ≤ −2
R3 => x5 ≤ 1−2x1−x2+x3−x41 x5 ≤ 1−0−0+1−01 x5 ≤ 23
Questo˜es de Provas Pa´gina 49 de 50
ENP160 - Otimizac¸a˜o Combinato´ria 2018/1 Questo˜es de Provas
(b) R1 => LI => 2(0)− (0) + (0) + 0 ≤ 1
0 ≤ 1 => OK
R1 => LS => 2(1)− (1) + (1) + 2 + 23 ≤ 1
14
3
≤ 1→ Invia´vel
(c) 2x1 − x2 + x3 + x4 + x5 ≤ 1
2(1)− 0 + 1 + 2 + 2
3
≤ 1
17
3
≤ 1→ A restric¸a˜o na˜o e´ redundante
49. 49. Sobre o me´todo de Gomory:
(a) O me´todo e´ capaz de gerar a soluc¸a˜o o´tima para um PPLIM? Justifique.
(b) A partir do quadro final do Simplex da Relaxac¸a˜o Linear do PPLIM, explique
os procedimentos de uma iterac¸a˜o do me´todo.
(c) Uma vez que uma varia´vel e´ integrlizada, isto e´, passa a ter um valor inteiro apo´s
um corte, seu valor continuara´ sendo inteiro nos cortes seguintes? Justifique.
Soluc¸a˜o:
(a) Sim. O me´todo iterativo e´ capaz de encontrar uma soluc¸a˜o primal via´vel,
ou seja, inteira atrace´s do dual simplex, que e´ o´tima para o novo problema
modelado.
(b) Deve-se escolher a varia´vel ba´sica mais fracionada, realizar o corte e
representa-lo em termos das varia´veis originais do problema. Se a soluc¸a˜o
na˜o for primal via´vel, mas for dual via´vel, devemos iterar o dual sim-
plex para encontrar uma soluc¸a˜o primal via´vel. Se for o´tima pare, sena˜o,
adicione outro corte.
(c) Na˜o se pode garantir, pois e´ poss´ıvel que haja outras iterac¸o˜es que podem
alterar novamente o valor da varia´vel.
Questo˜es de Provas Pa´gina 50 de 50
	Complexidade
	Região de Viabilidade, Envoltória Convexa e Formulação Ideal
	Modelagem
	Relaxação Lagrangeana
	Branch and Bound
	Métodos de planos cortantes