Resolução-Aula-3-PO-II

Prévia do material em texto

CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA CELSO 
SUCKOW DA FONSECA 
 
 
 
 
Pesquisa Operacional II 
Exercício Resolvido - Aula 3 
 
 
 
 
Tutor: 
Breno Assis 
 
 
 
 
 
Rio de Janeiro 
Março de 2018 
Sumário 
Questão 1) ........................................................................................................................................... 3 
1.1) Solução pelo método gráfico .................................................................................................... 3 
Letra (a) Busca em profundidade com backtracking ................................................................... 3 
Letra (b) Busca em largura ........................................................................................................ 13 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Questão 1) 
1.1) Solução pelo método gráfico 
Letra (a) Busca em profundidade com backtracking 
Nodo 0 (nodo raiz): 
Inicia-se com a obtenção da solução ótima da RPL. O gradiente da função objetivo fornece o valor 
ótimo no ponto de interseção entre as retas −2𝑥1 + 2𝑥2 = 3 e 7𝑥1 + 3𝑥2 = 22. Note pela figura 
abaixo que a direção de otimização é denotada por uma seta, e as curvas de nível estão tracejadas em 
vermelho. Caminhando-se na direção de otimização, a curva de nível que caracteriza a solução ótima 
intercepta a região viável no vértice 3. 
 
Resolvendo-se o sistema de equações lineares correspondente, tem-se: 
{
−2𝑥1 + 2𝑥2 = 3 ∗ (7)
7𝑥1 + 3𝑥2 = 22 ∗ (2)
 ⇒ {
−14𝑥1 + 14𝑥2 = 21
14𝑥1 + 6𝑥2 = 44 
 ⇒ 20𝑥2 = 65 ⇒ 𝑥2 =
13
4⁄ 
 ⇒ 14𝑥1 + 6 ∙
13
4⁄ = 44 ⇒ 14𝑥1 =
49
2⁄ ⇒ 𝑥1 =
7
4⁄ 
Obtém-se então a seguinte solução ótima para a RPL: (�̅�1, �̅�2)= (
7
4⁄ ,
13
4⁄ ), de valor 𝑧�̅�𝑃𝐿 = 5. 
Uma vez que a solução não é (inteira) viável, deve-se forçar a integralidade através da inserção de 
uma disjunção que elimine as partes fracionárias do espaço de busca no entorno da solução relaxada. 
Escolhe-se então a variável a variável “mais fracionária”, 𝑥𝑘, tal que 𝑘 = argmax𝑗{𝑓𝑗}, e 𝑓𝑗 =
min{⌈�̅�𝑗⌉ − �̅�𝑗 , �̅�𝑗 − ⌊�̅�𝑗⌋}. Na ocorrência de empates, escolha a variável 𝑥𝑘 de menor índice 𝑘. 
 
7
4
,
13
4
 
�̅�1 =
7
4⁄ , 𝑓1 = min {{⌈1
3
4⁄ ⌉ − 1
3
4⁄ }, {1
3
4⁄ − 1}} =
1
4⁄ 
�̅�2 =
13
4⁄ , 𝑓2 = min {{⌈3
1
4⁄ ⌉ − 3
1
4⁄ }, {3
1
4⁄ − ⌊3
1
4⁄ ⌋}} =
1
4⁄ 
Como 𝑓1 = 𝑓2 e 𝑥1 tem menor índice que 𝑥2, ramifica-se a variável 𝑥1 através com a inserção da 
disjunção 𝑥1 ≤ 1 e 𝑥1 ≥ 2, como pode ser observado na árvore e na figura abaixo: 
 
 
Nos passos seguintes repete-se o processo de seleção iterativa dos nós não explorados segundo a 
estratégia de busca em profundidade. Como os nós 1 e 2 se encontram no mesmo nível árvore de 
busca, escolhe-se o nó esquerdo primeiro (nada impede de fazer o contrário). 
Nodo 1: O gradiente da função objetivo fornece o valor ótimo no ponto de interseção entre as retas 
−2𝑥1 + 2𝑥2 = 3 e 𝑥1 = 1, no ponto 3. Pela resolução deste sistema de equações lineares, obtém-se: 
{
−2𝑥1 + 2𝑥2 = 3
𝑥1 = 1
 ⇒ −2 ∙ 1 + 2𝑥2 = 3 ⇒ 𝑥2 =
5
2⁄ 
Solução ótima do problema no nodo 1 𝑧̅1 = 7 2⁄ , (𝑥1, 𝑥2) = (1,
5
2
). 
𝑥1 ≤ 1
𝑥1 ≥ 2
1 2 
0 
5
𝑥1 ≤ 1 𝑥1 ≥ 2
 
 
A próxima variável a ser ramificada é 𝑥2, com a inserção das restrições das restrições 𝑥2 ≤ 2 e 𝑥2 ≥
3, como pode ser observado na árvore abaixo. Como os nós 3 e 4 se encontram no mesmo nível 
árvore de busca, escolhe-se o nó esquerdo primeiro (nada impede de fazer o contrário). 
 
 
 
Nodo 3: O gradiente da função objetivo fornece o valor ótimo no ponto de interseção das retas 𝑥2 =
2 e 𝑥1 = 1, no vértice definido no ponto 4. A solução ótima do subproblema no nodo 3 é 
 (𝑥1
∗, 𝑥2
∗) = (1,2), que vale 𝑧̅3 = 3. 
𝑥1 ≤ 1
 1∗, 5 2⁄
∗
 
1 2 
0 
5
𝑥1 ≤ 1 𝑥1 ≥ 2
3 4 
𝑥2 ≤ 2 𝑥2 ≥ 3
7
2⁄
𝑥2 ≤ 2
𝑥2 ≥ 3
𝑥1 ≤ 1
 
Poda-se o nodo 3 pelo critério de otimalidade e em seguida explora-se o nodo 4 (backtracking), 
como pode ser observado na árvore abaixo: 
 
 
Nodo 4: Pela observação gráfica é possível verificar que não existe interseção entre o espaço de 
solução anterior e a nova restrição incluída, 𝑥2 ≥ 3. A seguir é apresentada a solução analítica para 
verificar se o ponto obtido encontra-se no espaço de solução do nodo 1: 
3
1 2 
0 
5
𝑥1 ≤ 1 𝑥1 ≥ 2
3 4 
𝑥2 ≤ 2 𝑥2 ≥ 3
7
2⁄
𝑥1 ≤ 1
(1∗, 2∗)
𝑥2 ≤ 2
{
7𝑥1 + 3𝑥2 ≤ 22 
−2𝑥1 + 2𝑥2 ≤ 3
𝑥1 = 1
𝑥2 = 3
→ 
7 ∙ 1 + 3 ∙ 3 ≤ 22 → 16 ≤ 22 (OK!)
−2 ∙ 1 + 2 ∙ 3 ≤ 3 → 8 ≤ 3 (Falso!)
 
Como não houve interseção entre o conjunto de restrições, a Solução do problema no nodo 4 é 𝑧̅4 =
−∞. Poda-se o nodo 4 pelo critério de inviabilidade e em seguida explora-se o nodo 2, como pode 
ser observado na árvore abaixo: 
 
 
 
Nodo 2: O gradiente da função objetivo fornece o valor ótimo no ponto de interseção das retas 7𝑥1 +
3𝑥2 = 22 e 𝑥1 = 2, no vértice definido no ponto 2. A solução ótima do subproblema no nodo 2 é 
 (𝑥1
∗, 𝑥2
∗) = (2, 8 3⁄ ), que vale 𝑧̅
2 = 14 3⁄ .
−∞3
1 2 
0 
5
𝑥1 ≤ 1 𝑥1 ≥ 2
3 4 
𝑥2 ≤ 2 𝑥2 ≥ 3
7
2⁄
𝑥1 ≤ 1
𝑥1 ≥ 2
 
A próxima variável a ser ramificada é 𝑥2, com a inserção das restrições das restrições 𝑥2 ≤ 2 e 𝑥2 ≥
3, como pode ser observado na árvore abaixo. Como os nós 5 e 6 se encontram no mesmo nível 
árvore de busca, escolhe-se o nó esquerdo primeiro (nada impede de fazer o contrário). 
 
 
 
Nodo 5: O gradiente da função objetivo fornece o valor ótimo no ponto de interseção das retas 7𝑥1 +
3𝑥2 = 22 e 𝑥2 = 2, no vértice definido no ponto 3. A solução ótima do subproblema no nodo 5 é 
 (𝑥1
∗, 𝑥2
∗) = (16 7⁄ , 2), que vale 𝑧̅
5 = 30 7⁄ . 
 
𝑥1 ≥ 2
 2∗, 8 3⁄
∗
 
0 
5
𝑥1 ≤ 1
𝑥1 ≥ 2
−∞3
1 
3 4 
𝑥2 ≤ 2 𝑥2 ≥ 3
7
2⁄
2 
5 6 
𝑥2 ≤ 2
𝑥2 ≥ 3
14
3⁄ 𝑥2 ≤ 2
𝑥2 ≥ 3
𝑥1 ≥ 2
 
A próxima variável a ser ramificada é 𝑥1, com a inserção das restrições das restrições 𝑥1 ≤ 2 e 𝑥1 ≥
3, como pode ser observado na árvore abaixo. Como os nós 7 e 8 se encontram no mesmo nível 
árvore de busca, escolhe-se o nó esquerdo primeiro (nada impede de fazer o contrário). 
 
 
𝑥1 ≥ 2
 16 7⁄
∗
, 2∗ 
𝑥2 ≤ 2
𝑥1 = 2
𝑥1 ≥ 3
𝑥2 ≤ 2
 
Nodo 7: O gradiente da função objetivo fornece o valor ótimo no ponto de interseção das retas 𝑥1 =
2 e 𝑥2 = 2, no vértice definido no ponto 1. A solução ótima do subproblema no nodo 7 é 
 (𝑥1
∗, 𝑥2
∗) = (2,2), que vale 𝑧̅7 = 4. 
 
 
Poda-se o nodo 7 pelo critério de otimalidade e em seguida explora-se o nodo 8 (backtracking), 
como pode ser observado na árvore abaixo: 
 
0 
5
𝑥1 ≤ 1 𝑥1 ≥ 2
−∞3
1 
3 4 
𝑥2 ≤ 2 𝑥2 ≥ 3
7
2⁄
2 
6 
𝑥2 ≤ 2 𝑥2 ≥ 3
14
3⁄
5 
7 8 
𝑥1 ≤ 2 𝑥1 ≥ 3
30
7⁄
𝑥1 = 2
(2∗, 2∗)
𝑥2 ≤ 2
 
Nodo 8: O gradiente da função objetivo fornece o valor ótimo no ponto de interseção das retas 7𝑥1 +
3𝑥2 = 22 e 𝑥1 = 3, no vértice definido no ponto 2. A solução ótima do subproblema no nodo 8 é 
 (𝑥1
∗, 𝑥2
∗) = (3, 1 3⁄ ), que vale 𝑧̅
8 = 10 3⁄ . 
 
 
0 
5
𝑥1 ≤ 1 𝑥1 ≥ 2
−∞3
1 
3 4 
𝑥2 ≤ 2 𝑥2 ≥ 3
7
2⁄
2 
6 
𝑥2 ≤ 2 𝑥2 ≥ 3
14
3⁄
5 
7 8 
𝑥1 ≤ 2 𝑥1 ≥ 3
30
7⁄
4
 3∗, 1 3⁄
∗
 
𝑥1 ≥ 3
Poda-se o nodo 8 pelo critério de qualidade (melhor limitante) e em seguida explora-se o nodo 6, 
como pode ser observado na árvore abaixo: 
 
 
Nodo 6: Pela observação gráfica é possível verificar que não existe interseção entre o espaço de 
solução anterior e a nova restrição incluída, 𝑥2 ≥ 3. A seguir é apresentada a solução analítica para 
verificar se o ponto obtido encontra-se no espaço de solução do nodo 0: 
{
7𝑥1 + 3𝑥2 ≤ 22 
−2𝑥1 + 2𝑥2 ≤ 3
𝑥1 = 2
𝑥2 = 3
→ 
7 ∙ 2 + 3 ∙ 3 ≤ 22 → 23 ≤ 22 (Falso!)
−2 ∙ 2 + 2 ∙ 3 ≤ 3 → 2 ≤ 3 (OK!)
 
Como não houve interseção entre o conjunto de restrições, a Solução do problema no nodo 6 é 𝑧̅6 =
−∞. Poda-se o nodo 6 pelo critério de inviabilidade e então encerra-se a busca pela árvore de 
branch-and-bound, como pode ser observado na árvore abaixo: 
0 
5
𝑥1 ≤ 1 𝑥1 ≥ 2−∞3
1 
3 4 
𝑥2 ≤ 2 𝑥2 ≥ 3
7
2⁄
2 
6 
𝑥2 ≤ 2 𝑥2 ≥ 3
14
3⁄
5 
7 8 
𝑥1 ≤ 2 𝑥1 ≥ 3
30
7⁄
4 10
3⁄
 
 
Letra (b) Busca em largura 
Nodo 0 (nodo raiz): 
Inicia-se com a obtenção da solução ótima da RPL. O gradiente da função objetivo fornece o valor 
ótimo no ponto de interseção entre as retas −2𝑥1 + 2𝑥2 = 3 e 7𝑥1 + 3𝑥2 = 22. Note pela figura 
abaixo que a direção de otimização é denotada por uma seta, e as curvas de nível estão tracejadas em 
vermelho. Caminhando-se na direção de otimização, a curva de nível que caracteriza a solução ótima 
intercepta a região viável no vértice 3. 
0 
5
𝑥1 ≤ 1 𝑥1 ≥ 2
−∞3
1 
3 4 
𝑥2 ≤ 2 𝑥2 ≥ 3
7
2⁄
2 
6 
𝑥2 ≤ 2 𝑥2 ≥ 3
14
3⁄
5 
7 8 
𝑥1 ≤ 2 𝑥1 ≥ 3
30
7⁄
4 10
3⁄
−∞
 
Resolvendo-se o sistema de equações lineares correspondente, tem-se: 
{
−2𝑥1 + 2𝑥2 = 3 ∗ (7)
7𝑥1 + 3𝑥2 = 22 ∗ (2)
 ⇒ {
−14𝑥1 + 14𝑥2 = 21
14𝑥1 + 6𝑥2 = 44 
 ⇒ 20𝑥2 = 65 ⇒ 𝑥2 =
13
4⁄ 
 ⇒ 14𝑥1 + 6 ∙
13
4⁄ = 44 ⇒ 14𝑥1 =
49
2⁄ ⇒ 𝑥1 =
7
4⁄ 
Obtém-se então a seguinte solução ótima para a RPL: (�̅�1, �̅�2)= (
7
4⁄ ,
13
4⁄ ), de valor 𝑧�̅�𝑃𝐿 = 5. 
Uma vez que a solução não é (inteira) viável, deve-se forçar a integralidade através da inserção de 
uma disjunção que elimine as partes fracionárias do espaço de busca no entorno da solução relaxada. 
Escolhe-se então a variável a variável “mais fracionária”, 𝑥𝑘, tal que 𝑘 = argmax𝑗{𝑓𝑗}, e 𝑓𝑗 =
min{⌈�̅�𝑗⌉ − �̅�𝑗 , �̅�𝑗 − ⌊�̅�𝑗⌋}. Na ocorrência de empates, escolha a variável 𝑥𝑘 de menor índice 𝑘. 
�̅�1 =
7
4⁄ , 𝑓1 = min {{⌈1
3
4⁄ ⌉ − 1
3
4⁄ }, {1
3
4⁄ − 1}} =
1
4⁄ 
�̅�2 =
13
4⁄ , 𝑓2 = min {{⌈3
1
4⁄ ⌉ − 3
1
4⁄ }, {3
1
4⁄ − ⌊3
1
4⁄ ⌋}} =
1
4⁄ 
Como 𝑓1 = 𝑓2 e 𝑥1 tem menor índice que 𝑥2, ramifica-se a variável 𝑥1 através com a inserção da 
disjunção 𝑥1 ≤ 1 e 𝑥1 ≥ 2, como pode ser observado na árvore e na figura abaixo: 
 
 
7
4
,
13
4
 
 
Nos passos seguintes repete-se o processo de seleção iterativa dos nós não explorados segundo a 
estratégia de busca em largura. Como os nós 1 e 2 se encontram no mesmo nível árvore de busca 
(mesmo limitante superior), escolhe-se o nó esquerdo primeiro (nada impede de fazer o contrário). 
Nodo 1: O gradiente da função objetivo fornece o valor ótimo no ponto de interseção entre as retas 
−2𝑥1 + 2𝑥2 = 3 e 𝑥1 = 1, no ponto 3. Pela resolução deste sistema de equações lineares, obtém-se: 
{
−2𝑥1 + 2𝑥2 = 3
𝑥1 = 1
 ⇒ −2 ∙ 1 + 2𝑥2 = 3 ⇒ 𝑥2 =
5
2⁄ 
Solução ótima do problema no nodo 1 𝑧̅1 = 7 2⁄ , (𝑥1, 𝑥2) = (1,
5
2
). 
 
 
𝑥1 ≤ 1
𝑥1 ≥ 2
𝑥1 ≤ 1
 1∗, 5 2⁄
∗
 
1 2 
0 
5
𝑥1 ≤ 1 𝑥1 ≥ 2
A próxima variável a ser ramificada é 𝑥2, com a inserção das restrições das restrições 𝑥2 ≤ 2 e 𝑥2 ≥
3, como pode ser observado na árvore abaixo. Como o limitante do nodo 1 é inferior que o limitante 
do nodo 0 e sabendo que um nodo-filho tem limitante, no máximo, igual ao do pai, explora-se a 
seguir o nodo 2. 
 
 
 
Nodo 2: O gradiente da função objetivo fornece o valor ótimo no ponto de interseção das retas 7𝑥1 +
3𝑥2 = 22 e 𝑥1 = 2, no vértice definido no ponto 2. A solução ótima do subproblema no nodo 2 é 
 (𝑥1
∗, 𝑥2
∗) = (2, 8 3⁄ ), que vale 𝑧̅
2 = 14 3⁄ .
1 2 
0 
5
𝑥1 ≤ 1 𝑥1 ≥ 2
3 4 
𝑥2 ≤ 2 𝑥2 ≥ 3
7
2⁄
𝑥2 ≤ 2
𝑥2 ≥ 3
𝑥1 ≤ 1
 
A próxima variável a ser ramificada é 𝑥2, com a inserção das restrições das restrições 𝑥2 ≤ 2 e 𝑥2 ≥
3, como pode ser observado na árvore abaixo. Como o limitante do nó 2 é melhor que o limitante do 
nodo 1, a escolhe-se explorar os nós 5 ou 6. Como os nós 5 e 6 se encontram no mesmo nível árvore 
de busca, escolhe-se o nó esquerdo primeiro (nada impede de fazer o contrário). 
 
 
Nodo 5: O gradiente da função objetivo fornece o valor ótimo no ponto de interseção das retas 7𝑥1 +
3𝑥2 = 22 e 𝑥2 = 2, no vértice definido no ponto 3. A solução ótima do subproblema no nodo 5 é 
 (𝑥1
∗, 𝑥2
∗) = (16 7⁄ , 2), que vale 𝑧̅
5 = 30 7⁄ . 
 
𝑥1 ≥ 2
 2∗, 8 3⁄
∗
 
0 
5
𝑥1 ≤ 1
𝑥1 ≥ 2
1 
3 4 
𝑥2 ≤ 2 𝑥2 ≥ 3
7
2⁄
2 
5 6 
𝑥2 ≤ 2
𝑥2 ≥ 3
14
3⁄ 𝑥2 ≤ 2
𝑥2 ≥ 3
𝑥1 ≥ 2
 
A próxima variável a ser ramificada é 𝑥1, com a inserção das restrições das restrições 𝑥1 ≤ 2 e 𝑥1 ≥
3, como pode ser observado na árvore abaixo. Como o nodo 2 tem melhor limitante, escolhe-se o 
nodo 6 para ser explorado. 
 
𝑥1 ≥ 2
 16 7⁄
∗
, 2∗ 
𝑥2 ≤ 2
𝑥1 = 2
𝑥1 ≥ 3
𝑥2 ≤ 2
 
 
Nodo 6: Pela observação gráfica é possível verificar que não existe interseção entre o espaço de 
solução anterior e a nova restrição incluída, 𝑥2 ≥ 3. A seguir é apresentada a solução analítica para 
verificar se o ponto obtido encontra-se no espaço de solução do nodo 0: 
{
7𝑥1 + 3𝑥2 ≤ 22 
−2𝑥1 + 2𝑥2 ≤ 3
𝑥1 = 2
𝑥2 = 3
→ 
7 ∙ 2 + 3 ∙ 3 ≤ 22 → 23 ≤ 22 (Falso!)
−2 ∙ 2 + 2 ∙ 3 ≤ 3 → 2 ≤ 3 (OK!)
 
Como não houve interseção entre o conjunto de restrições, a Solução do problema no nodo 6 é 𝑧̅6 =
−∞. Poda-se o nodo 6 pelo critério de inviabilidade, como pode ser observado na árvore abaixo: 
Como o nodo 5 tem melhor limitante, escolhe-se o nodo 7 ou 8 para ser explorado. O nodo 7 foi 
escolhido arbitrariamente. 
0 
5
𝑥1 ≤ 1 𝑥1 ≥ 2
1 
3 4 
𝑥2 ≤ 2 𝑥2 ≥ 3
7
2⁄
2 
6 
𝑥2 ≤ 2 𝑥2 ≥ 3
14
3⁄
5 
7 8 
𝑥1 ≤ 2 𝑥1 ≥ 3
30
7⁄
 
 
Nodo 7: O gradiente da função objetivo fornece o valor ótimo no ponto de interseção das retas 𝑥1 =
2 e 𝑥2 = 2, no vértice definido no ponto 1. A solução ótima do subproblema no nodo 7 é 
 (𝑥1
∗, 𝑥2
∗) = (2,2), que vale 𝑧̅7 = 4. 
 
 
Poda-se o nodo 7 pelo critério de otimalidade e em seguida poda-se os nodos 3, 4 e 8 por possuírem 
limitante piores ou iguais a melhor solução encontrada, como pode ser observado na árvore abaixo: 
0 
5
𝑥1 ≤ 1 𝑥1 ≥ 2
1 
3 4 
𝑥2 ≤ 2 𝑥2 ≥ 3
7
2⁄
2 
6 
𝑥2 ≤ 2 𝑥2 ≥ 3
14
3⁄
5 
7 8 
𝑥1 ≤ 2 𝑥1 ≥ 3
30
7⁄ −∞
𝑥1 = 2
(2∗, 2∗)
𝑥2 ≤ 2
 
 
 
Resumo das árvores de Branch: 
Busca em Profundidade 
 
 
0 
5
𝑥1 ≤ 1 𝑥1 ≥ 2
1 
3 4 
𝑥2 ≤ 2 𝑥2 ≥ 3
7
2⁄
2 
6 
𝑥2 ≤ 2 𝑥2 ≥ 3
14
3⁄
5 
7 8 
𝑥1 ≤ 2 𝑥1 ≥ 3
30
7⁄
4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
−∞
 
 
Busca em Largura 
 
 
 
Note que, para este caso, o número de nodos explorados através da busca por profundidade e 
por largura é o mesmo, ou seja, em ambos os casos o número de nodos explorados é igual a 
9 e, portanto. Entretanto, não há garantia de que tal fato sempre ocorra! 
Note ainda que, apesar das árvores encontradas serem iguais (mesmo número de nodos 
explorados), o número de iterações para se podar toda a árvore é menor na busca em largura 
(diferem em três iterações). Como a solução ótima encontrada na busca em largura é melhor 
que os limitantes dos nodos 1 e 5, quando o nodo 7 é podado por otimalidade os demais 
nodos-filhos são podados por limite.