Lista de Exerc cios I - Gabaritoioc-ufam.weebly.com/uploads/5/0/7/0/50702097/ioc201501... · ij jSj 1 (8S ˆV) (3) x ... na tabela a seguir. A˘ca Carne de frango Leite Carne de boi

UNIVERSIDADE FEDERAL DO AMAZONASINSTITUTO DE COMPUTACAO

ICC500 - Introducao a Otimizacao CombinatoriaPGINF566 - Otimizacao Combinatoria

Profa. Rosiane de Freitas

Lista de Exercıcios I - Gabarito

Questao 1. Correlacione a coluna da esquerda com a da direita.

(a) Programacao linear

(b) Variaveis de folga

(c) Metodo grafico

(d) Simplex

(e) Variaveis nao-basicas

(f) Folgas complementares

(g) Programacao inteira

(h) CPLEX

(i) Branch-and-bound

(j) Metodos de corte

(j) Adiciona restricoes a um problema relaxado

(d) Algoritmo para obter solucoes de programacao linear contınua

(i) Enumera subproblemas e limites para um problema discreto

(h) Software para solucao de modelos de programacao linear

(c) Obtem solucoes de programacao linear com ate duas variaveis

(f) Solucao do primal a partir do dual

(b) Variaveis usadas em inequacoes das restricoes

(a) Problemas com variaveis contınuas

(e) Variaveis com valor zero na solucao otima

(g) Problemas com variaveis discretas

Questao 2. Considere o cenario a seguir:

Uma pequena cooperativa de artigos artesanais de Manaus deseja efetuar a distribuicao de suas pecas em cidades doestado do Amazonas. Para isso, contratou um regateiro, que devera entregar os itens em um conjunto de localidadesdo interior. Para otimizar o processo, a empresa quer aproveitar o conhecimento do regateiro, a geografia amazonicae usar o setor de logıstica da empresa para determinar qual a rota que o regateiro deve fazer para minimizar os custosde deslocamento, sendo que, ao final, o regateiro permanecera na ultima localidade visitada. E se, apos as entregas,o mesmo retornar a sua cidade de origem? E se ele tivesse apenas uma localidade (p. ex., Anama) para entregar osprodutos? Analise os 3 problemas. A figura a seguir representa as ligacoes hidrograficas entre as cidades da regiao,considerando as distancias fluviais entre as cidades.

41km

37km

27km

44km 4km

45km

50km

25km

19km

Manaus Anamã

Iranduba Manacapuru

Novo Airão Caapiranga

a) Descreva teoricamente cada um dos 3 problemas.

A figura dada e um grafo nao-direcionado, onde as cidades sao os vertices e as arestas indicam as distancias entrepares de cidades, quando ha um caminho direto entre as duas cidades da aresta.

Quando o regateiro precisa visitar todas as cidades, sem retornar a origem, tem-se que, no grafo, deve-se determinarum caminho hamiltoniano de custo (distancia) mınimo. Determinar a existencia de tal caminho e um problemaNP-completo, e encontrar o menor caminho desse tipo e um problema NP-difıcil.

1

Se o regateiro retornar a sua cidade de origem, tem-se que a viagem dele forma um ciclo hamiltoniano, que eum caminho hamiltoniano adicionado de uma aresta extra entre o ponto final e o inicial do caminho, o que fechao ciclo. A determinacao do ciclo hamiltoniano de custo mınimo e equivalente ao problema do caixeiro viajante,um classico problema de otimizacao NP-difıcil.

Os problemas do caminho hamiltoniano mınimo e do caixeiro viajante sao equivalentes, uma vez que, adicionandoum vertice artificial adjacente a todos os outros e cuja distancia e 0 a todos os outros, tem-se que o ciclohamiltoniano obtido neste grafo aumentado e equivalente ao caminho hamiltoniano mınimo no grafo original,bastando remover o vertice artificial e as arestas incidentes ao mesmo do ciclo. A figura abaixo mostra comoficaria o grafo aumentado da figura do enunciado.

41km

37km

27km

44km 4km

45km

50km

25km

19km

Manaus Anamã

Iranduba Manacapuru

Novo Airão Caapiranga

0

Vértice artificial

0km

0km

0km

0km

0km0km

Por fim, se o regateiro precisar entregar em apenas uma cidade, sem retornar a origem, tem-se o problemado caminho mınimo, que, ao contrario dos anteriores, pertence a classe P, uma vez que possui algoritmospolinomiais conhecidos (algoritmos de Dijkstra, Bellman-Ford e Floyd-Warshall).

b) Forneca o modelo matematico para os 3 problemas, fazendo as consideracoes que julgar necessarias.

Primeiramente, sera mostrado o modelo para o caixeiro viajante. O grafo de entrada deve ser completo, logo, senao existir aresta entre dois vertices, deve-se adicionar uma aresta artificial de custo muito alto (matematicamente,custo infinito) de forma que elas nunca facam parte do ciclo otimo. As variaveis de decisao sao:

xij =

{1, se a aresta (i, j) faz parte do ciclo0, caso contrario.

Como o grafo nao e direcionado, a versao do problema do caixeiro viajante abordada e simetrica, ou seja,(i, j) = (j, i) e dij = dji. Assim, so existirao variaveis xij quando j > i (∀i, j ∈ V ). O modelo entao e oseguinte:

Minimizar∑

(i,j)∈E

dijxij (1)

Sujeito a∑

j∈V : (i,j)∈E

xij +∑

j∈V : (i,j)∈E

xji = 2 (i ∈ V ) (2)

∑i,j∈S : (i,j)∈E

xij ≤ |S| − 1 (∀S ⊂ V ) (3)

xij ∈ {0, 1} (∀i, j ∈ V | j > i) (4)

A funcao objetivo (1) envolve a minizacao da distancia total percorrida no ciclo hamiltoniano. O conjunto derestricoes (2) faz com que, para cada vertice, existam pelo menos duas arestas incidentes ao mesmo no ciclo (de

2

forma a fechar o ciclo). Ja o conjunto de restricoes (3) consiste nas restricoes de eliminacao de sub-rota, deforma que, para todo subconjunto S dos vertices, existam, no maximo |S| − 1 arestas entre eles, o que impedeque um ciclo seja formado apenas com os vertices de S. Por fim, as restricoes (4) sao de integralidade.

Para o problema do caminho hamiltoniano mınimo, como mostrado anteriormente, deve-se encontrar um ciclohamiltoniano mınimo no grafo adicionado de um vertice artificial adjacente a todos os outros e com distanciazero. Sendo 0 o tal vertice, o modelo matematico fica como o anterior, fazendo as seguintes alteracoes:

– V ′ = V ∪ {0}.– E′ = E ∪ {(0, l) | l ∈ V }.

Que devem ser usadas no modelo:

Minimizar∑

(i,j)∈E′

dijxij (1)

Sujeito a∑

j∈V ′ : (i,j)∈E′

xij +∑

j∈V ′ : (i,j)∈E′

xji = 2 (i ∈ V ′) (2)

∑i,j∈S : (i,j)∈E′

xij ≤ |S| − 1 (∀S ⊂ V ′) (3)

xij ∈ {0, 1} (∀i, j ∈ V ′ | j > i) (4)

Para o problema do caminho mınimo, a formulacao tambem e ligeiramente parecida, observando-se as seguintescaracterısticas:

– Nao ha eliminacao de sub-rotas, uma vez que nao exige que o caminho passe por todos os vertices uma vezso.

– Sendo s o vertice inicial e f o final do caminho, tem-se que o numero de arestas incidentes a s deve serexatamente 1, sendo o mesmo exigido para f .

– Para os outros vertices, a quantidade de arestas incidentes deve respeitar a propriedade de que a quantidadede arestas que entram no vertice deve ser igual a quantidade das que saem (conservacao de fluxo). Pode-seobservar que, para os vertices i ∈ V − {s, f}, tal quantidade de arestas incidentes sera 0 ou 2.

A funcao objetivo e as variaveis de decisao sao as mesmas do caixeiro viajante, no entanto, sera consideradoque, para cada par i, j ∈ V , existira uma variavel xij indicando se o caminho contem a aresta (i, j), como feitoanteriormente, tambem tomando proveito de o grafo poder ser completado com arestas artificiais. O modeloentao e o seguinte:

Minimizar∑

(i,j)∈E

dijxij (1)

Sujeito a∑i∈V

xsi −∑j∈V

xjs = 1 (2)

∑i∈V

xfi −∑j∈V

xjf = 1 (3)

∑i∈V

xip −∑j∈V

xjp = 0 (∀p ∈ V − {s, f}) (4)

xij ∈ {0, 1} (∀i, j ∈ V ) (5)

A restricao (2) garante que haja apenas uma aresta incidente ao vertice de inıcio. A restricao (3) garante a mesmacoisa em relacao ao vertice final. Ja o conjunto de restricoes (4) diz respeito a conservacao de fluxo. Por fim, asrestricoes (5) sao de integralidade.

c) Quais os problemas classicos associados a este cenario? Existe algoritmo eficiente (polinomial) para algum deles?Justifique.

3

Como abordado na letra a), os problemas sao: caminho hamiltoniano mınimo, caixeiro viajante e caminho mınimoentre dois vertices. Dentre eles, apenas o problema do caminho mınimo admite algoritmo polinomial (algoritmosde Dijkstra, Bellman-Ford e Floyd-Warshall).

Questao 3. Uma pessoa, sentindo-se sempre muito cansada e com a pele palida, procurou um medico e foi diagnosti-cada com anemia ferropriva. Para melhora do quadro, o medico informou que o paciente deveria ingerir uma quantidademınima de ferro, necessario para producao de hemoglobina, uma metaloproteına utilizada para transporte de oxigenio nosangue, alem de vitamina C, que aumenta a absorcao do ferro ingerido. O paciente, entao, procurou um nutricionista,que forneceu a ele informacoes sobre a quantidade de ferro e vitamina C em diversos alimentos. Apos isso, o pacienteprocurou, em um supermercado local, os precos dos alimentos indicados. Considere que os dados resultantes1 sao dadosna tabela a seguir.

Acaı Carne de frango Leite Carne de boi Brocolis Necessidade

Vitamina C 3mg 4mg 4mg 6mg 2mg 30mg

Ferro 1mg 2mg 6mg 4mg 3mg 45mg

Preco (R$) 5,00 7,00 4,00 8,00 1,00 –

a) Forneca o modelo matematico para o problema, fazendo as consideracoes que achar necessarias.

– Variaveis de decisao:

∗ xA: quantidade de acaı.

∗ xF : quantidade de carne de frango.

∗ xL: quantidade de leite.

∗ xC : quantidade de carne de boi.

∗ xB: quantidade de brocolis.

∗ Todas as variaveis maiores ou iguais a zero.

– Funcao objetivo: minimizacao do custo da alimentacao, equivalente a soma dos custos por unidade de cadaalimento multiplicado pela quantidade do mesmo:

Minimizar z = 5xA + 7xF + 4xL + 8xC + xB

– Restricoes:

∗ Necessidade mınima de vitamina C: 30mg.

3xA + 4xF + 4xL + 6xC + 2xB ≥ 30

∗ Necessidade mınima de ferro: 45mg.

xA + 2xF + 6xL + 4xC + 3xB ≥ 45

O modelo fica, entao, da seguinte forma:


Sujeito a 3xA + 4xF + 4xL + 6xC + 2xB ≥ 30

xA + 2xF + 6xL + 4xC + 3xB ≥ 45

xA, xF , xL, xC , xB ≥ 0

b) Apresente o dual do modelo matematico.

Para facilitar o entendimento do dual, as variaveis e restricoes do mesmo serao denotadas do seguinte modo:

1Nao necessariamente realistas.

4

– Variaveis de decisao:

∗ uC : variavel dual relacionada a restricao de vitamina C no primal.

∗ uF : variavel dual relacionada a restricao de ferro no primal.

– Restricoes:

∗ Restricao associada a variavel do acaı no primal:

3uC + uF ≤ 5

∗ Restricao associada a variavel da carne de frango no primal:

4uC + 2uF ≤ 7

∗ Restricao associada a variavel do leite no primal:

4uC + 6uF ≤ 4

∗ Restricao associada a variavel da carne de boi no primal:

6uC + 4uF ≤ 8

∗ Restricao associada a variavel do brocolis no primal:

2uC + 3uF ≤ 1

O dual do modelo, entao, fica da seguinte forma:

Maximizar w = 30uC + 45uF

Sujeito a 3uC + uF ≤ 5

4uC + 2uF ≤ 7

4uC + 6uF ≤ 4

6uC + 4uF ≤ 8

2uC + 3uF ≤ 1

uC , uF ≥ 0

c) Resolva o dual utilizando o metodo grafico.

Para cada reta definida pelas restricoes no dual, deve-se descobrir dois pontos para que seja possıvel tracejar asmesmas:

– Restricao 1: 3uC + uF ≤ 5 ⇒ reta 3uC + uF = 5.

∗ Para uC = 0: uF = 5 ⇒ ponto (0, 5).

∗ Para uF = 0: 3uF = 5 → uF = 53 = 1, 666 ⇒ ponto (53 , 0).

– Restricao 2: 4uC + 2uF ≤ 7 ⇒ reta 4uC + 2uF = 7.

∗ Para uC = 0: 2uF = 7 → uF = 72 = 3, 5 ⇒ ponto (0, 72).

∗ Para uF = 0: 4uC = 7 → uC = 74 = 1, 75 ⇒ ponto (74 , 0).



∗ Para uF = 0: 4uC = 4 → uC = 1 ⇒ ponto (1, 0).


∗ Para uC = 0: 4uF = 8 → uF = 2 ⇒ ponto (0, 2).


5




O grafico entao e desenhado como na figura a seguir.

u F

0

1

2

3

4

5

uC

0 0,5 1 1,5 2

Restrição 1 - 3uC + uF ≤ 5Restrição 2 - 4uC + 2uF ≤ 7Restrição 3 - 4uC + 6uF ≤ 6Restrição 4 - 6uC + 4uF ≤ 8Restrição 5 - 2uC + 3uF ≤ 1

Região factível

A

O B

Observe que, apesar da quantidade de restricoes, a regiao factıvel e determinada apenas pela interseccao da retada restricao 5 com os eixos de uC e uF - todos os coeficientes das restricoes sao positivos e sao inequacoes demenor ou igual, logo, a regiao factıvel correspondente a cada restricao esta a esquerda e abaixo da reta (lembrandoque isto nao e geral!).

Para facilitar a visualizacao da regiao factıvel, a figura a seguir mostra o grafico em uma escala diferente.

u F

0

0,2

0,4

0,6

0,8

1

uC

0 0,5 1 1,5 2

A

B

Restrição 1 - 3uC + uF ≤ 5Restrição 2 - 4uC + 2uF ≤ 7Restrição 3 - 4uC + 6uF ≤ 6Restrição 4 - 6uC + 4uF ≤ 8Restrição 5 - 2uC + 3uF ≤ 1

Região factível

O

Deve-se entao analisar os pontos extremos (vertices) da regiao factıvel, denotados no grafico por O, A e B.

– Ponto O: origem (O = (0, 0)).

∗ Aplicando na funcao objetivo: z = (30× 0) + (45× 0) → z = 0.

– Ponto A: interseccao do eixo de uF (ou seja, uC = 0) e a reta da restricao 5.

∗ Este ponto foi calculado anteriormente para tracar a reta da restricao 5 ⇒ A = (0, 13).

∗ Aplicando na funcao objetivo: z = (30× 0) + (45× 13) → z = 45

3 = 15.

– Ponto B: interseccao do eixo de uC (ou seja, uF = 0) e a reta da restricao 5.

∗ Este ponto foi calculado anteriormente para tracar a reta da restricao 5 ⇒ B = (0, 12).

6

∗ Aplicando na funcao objetivo: z = (30× 12) + (45× 0) → z = 30

2 = 15.

Ambos os pontos A = (0, 13) e B = (0, 12) possuem o mesmo valor de funcao objetivo, que e o maximo possıvel.Assim, qualquer um dos dois e solucao otima do problema dual, com z = 15.

d) Resolva o primal utilizando o algoritmo simplex.

O modelo primal, fornecido na letra a), tem a seguinte forma:


Sujeito a 3xA + 4xF + 4xL + 6xC + 2xB ≥ 30

xA + 2xF + 6xL + 4xC + 3xB ≥ 45

xA, xF , xL, xC , xB ≥ 0

Para utilizacao do metodo simplex, deve-se colocar o problema no formato padrao. Cada restricao e uma de-sigualdade do tipo ≥, portanto, serao adicionadas variaveis de folga com coeficiente -1 para transforma-las emigualdades (caso fossem ≤, os coeficientes seriam 1).

Minimizar z = 5xA + 7xF + 4xL + 8xC + xB + 0s1 + 0s2

Sujeito a 3xA + 4xF + 4xL + 6xC + 2xB − s1 + 0s2 = 30

xA + 2xF + 6xL + 4xC + 3xB + 0s1 − s2 = 45

xA, xF , xL, xC , xB, s1, s2 ≥ 0

Outra caracterıstica a ser verificada e que, quando temos um problema de maximizacao, os coeficientes dasvariaveis na funcao objetivo devem entrar no quadro simplex com o sinal trocado. No caso do problema destaquestao, o problema e de minimizacao. Minimizar z e equivalente ao oposto da maximizacao de −z. Portanto,pode-se transformar a minimizacao na maximizacao da funcao objetivo com os coeficientes multiplicados por -1.Porem, como estamos maximizando −z e nao z, o valor otimo da funcao objetivo do problema de maximizacaodevera ser multiplicado por −1 para obtermos o mınimo de z.

O problema a ser considerado entao sera:

−Maximizar − z = −5xA − 7xF − 4xL − 8xC − xB + 0s1 + 0s2

Sujeito a 3xA + 4xF + 4xL + 6xC + 2xB − s1 + 0s2 = 30

xA + 2xF + 6xL + 4xC + 3xB + 0s1 − s2 = 45

xA, xF , xL, xC , xB, s1, s2 ≥ 0

O quadro simplex inicial para este problema, considerando as variaveis de folga como a base inicial (uma vez queas colunas das mesmas sao linearmente independentes) seria:

Linha (L) BASE xA xF xL xC xB s1 s2 b

1 a1 3 4 4 6 2 −1 0 30

2 a2 1 2 6 4 3 0 −1 45

3 −z 5 7 4 8 1 0 0 0

Olhando os custos reduzidos iniciais (ou seja, os coeficientes da funcao objetivo), verifica-se que todos sao maioresou iguais a zero, o que faz parecer que a solucao inicial com s1 = 30, s2 = 45 e xA = xF = xL = xC = xB = 0,com z = 0, e otima. Porem, essa leitura do quadro e incorreta, como mostrado a seguir. Como xA = xF = xL =xC = xB = 0, tem-se, pela restricao 1:

3xA + 4xF + 4xL + 6xC + 2xB − s1 + 0s2 = 30 → 0 + 0 + 0 + 0 + 0− s1 + 0 = 30 ⇒ s1 = −30

Porem, tem-se que todas as variaveis do problema sao maiores ou iguais a zero, logo, nao e possıvel trabalhar comeste quadro. A leitura incorreta se deve ao fato de que a base utilizada tem valores negativos e nao e canonica -

7

para que o valor da variavel seja diretamente o valor na mesma linha da variavel e na coluna b, a base utilizadadeve ser canonica. O mesmo acontece com a linha 2 da restricao 2, que fornece s2 = −45.

Para resolver isso, serao usadas variaveis artificiais com o metodo do big-M, que envolve a adicao de novasvariaveis (uma por restricao que necessite de uma variavel com coeficiente 1 para formar a base canonica) comcustos muito ruins (denotado por um numero M muito grande), de forma que elas saiam o mais depressa possıvelda base e nao entrem mais. Se a solucao final do problema contiver pelo menos uma delas, o problema originale infactıvel, caso contrario, e solucao otima do problema original.

Se as variaveis artificiais forem colocadas no problema original de minimizacao, tem-se que os custos delas nafuncao objetivo tem de ser muito altos (ou seja, +M), pois se deseja-se minimizar o valor, elas estao penalizandofortemente se tiverem valor acima de 0. Como as duas restricoes precisam de variaveis com coeficiente 1 paraformar a base canonica, tem-se que serao usadas duas variaveis artificiais, deixando o problema da seguinte forma:

Minimizar z = 5xA + 7xF + 4xL + 8xC + xB + 0s1 + 0s2 +Ma1 +Ma2

Sujeito a 3xA + 4xF + 4xL + 6xC + 2xB − s1 + 0s2 + a1 + 0a2 = 30

xA + 2xF + 6xL + 4xC + 3xB + 0s1 − s2 + 0a1 + a2 = 45

xA, xF , xL, xC , xB, s1, s2, a1, a2 ≥ 0

No problema modificado para maximizacao, as variaveis artificiais devem ter custos muito baixos (ou seja, −M),pois tambem devem penalizar o valor maximo para que saiam da base depressa, deixando o problema da seguinteforma (que equivale a modificar diretamente o problema de minimizacao com as variaveis artificiais dado acima):

−Maximizar − z = −5xA − 7xF − 4xL − 8xC − xB + 0s1 + 0s2 −Ma1 −Ma2

Sujeito a 3xA + 4xF + 4xL + 6xC + 2xB − s1 + 0s2 + a1 + 0a2 = 30

xA + 2xF + 6xL + 4xC + 3xB + 0s1 − s2 + 0a1 + a2 = 45

xA, xF , xL, xC , xB, s1, s2, a1, a2 ≥ 0

O quadro inicial para o problema entao, usando as variaveis artificiais como base, e:

Linha (L) BASE xA xF xL xC xB s1 s2 a1 a2 b

1 a1 3 4 4 6 2 −1 0 1 0 30

2 a2 1 2 6 4 3 0 −1 0 1 45

3 −z 5 7 4 8 1 0 0 M M 0

Antes de aplicar o simplex propriamente dito, deve-se consertar o valor da funcao objetivo. Tem-se que −z = 0,porem, ao aplicar a1 = 30 e a2 = 45, com todas as outras variaveis como zero, tem-se que:

−z = 0 + 0 + 0 + 0 + 0 + 0 + 0− 30M − 45M ⇒ −z = −75M

Para solucionar essa inconsistencia, deve-se transformar os custos reduzidos das variaveis artificiais em zero, ouseja, na linha 3 (do −z), deve-se efetuar operacoes entre linhas de forma que o valor nas colunas de a1 e a2passem a ser zero. Isso pode ser feito efetuando a seguinte operacao:

L3 = L3 −ML1 −ML2

Que deixa o quadro da seguinte forma:


1 a1 3 4 4 6 2 −1 0 1 0 30

2 a2 1 2 6 4 3 0 −1 0 1 45

3 −z 5− 4M 7− 6M 4− 10M 8− 10M 1− 5M M M 0 0 −75M

Considerando M = 20 (que da um custo pior que o das outras variaveis), o quadro fica:

8


1 a1 3 4 4 6 2 −1 0 1 0 30

2 a2 1 2 6 4 3 0 −1 0 1 45

3 −z −75 −113 −196 −192 −99 20 20 0 0 −1500

Agora, pode-se aplicar o metodo simplex normalmente. A variavel de menor custo reduzido (negativo) e xL,portanto, ela entrara na base. Para determinar quem saira da base, deve-se calcular os quocientes entre oelemento da coluna b na linha de uma variavel basica e o elemento da coluna na variavel que entrara na base namesma linha, sendo que quem sai da base e a variavel cujo quociente e o menor.

– Para a1:30

6= 15.

– Para a2:45

3= 15.

Ambas as variaveis possuem o mesmo quociente, logo, sera escolhida a de menor ındice (a1). O pivo entao seraa interseccao da linha da variavel que saira com a coluna da variavel que entrara, ou seja, 4. Na coluna davariavel entrante, o pivo deve ser transformado em 1 e todos outros elementos da coluna em zero. Para isso,serao aplicadas as seguintes operacoes entre linhas:

– Lnova1 =

1

4L1.

– Lnova2 = L2 − 6Lnova

1 .

– Lnova3 = L3 + 196Lnova

1 .

O proximo quadro, entao, sera:


1 xL 0, 75 1 1 1, 5 0, 5 −0, 25 0 0, 25 0 7, 5

2 a2 −3, 5 −4 0 −5 0 1, 5 −1 1, 5 1 0

3 −z 72 83 0 102 −1 −29 20 0 0 −30

A variavel de menor custo reduzido (negativo) e s1, portanto, ela entrara na base. Os quocientes para verificacaode quem saira da base sao:

– Para xL:7, 5

−0, 25= −30 (negativo, nao saira da base).

– Para a2:0

1, 5= 0.

Tem-se que a variavel a sair da base e a2. O pivo entao sera 1, 5 e, na coluna de s1 (que entrara na base), paratransformar o pivo em 1 e os outros elementos da coluna em zero, serao feitas as seguintes operacoes:

– Lnova2 =

1

1, 5L2.

– Lnova1 = L1 +

1

4Lnova2 .

– Lnova3 = L3 + 29Lnova

2 .



1 xL 0, 166 0, 333 1 0, 666 0, 5 0 0, 166 0, 5 0, 166 7, 5

2 s1 −2, 333 −2, 666 0 3, 333 0 1 −0, 666 1 0, 666 0

3 −z 4, 333 5, 666 0 198, 666 −1 0 0, 666 29 19, 333 −30

9

A variavel de menor custo reduzido (negativo) e xB, portanto, ela entrara na base. Os quocientes para verificacaode quem saira da base sao:

– Para xL:7, 5

0, 5= 15

– Para s1:0

0= indeterminado (nao saira da base).

Tem-se que a variavel a sair da base e xL. O pivo entao sera 1. Na coluna de xB (que entrara na base), paratransformar os outros elementos da coluna em zero, serao feitas as seguintes operacoes:

– Lnova1 = 2L1.

– Lnova2 = L2.

– Lnova3 = L3 + Lnova

1 .



1 xB 0, 333 0, 666 2 1, 333 1 0 −0, 333 1 0, 333 15

2 s1 −2, 333 −2, 666 0 3, 333 0 1 −0, 666 1 0, 666 0

3 −z 4, 666 6, 333 2 200 0 0 0, 333 30 19, 666 −15

Todos os custos reduzidos sao maiores ou iguais a zero, e nao ha variaveis artificiais na base, logo, este quadrodefine a solucao otima para o problema, com xB = 15, todas as outras variaveis como 0 e −z = −15 ⇒ z = 15.Observe que o valor da funcao objetivo e o mesmo da calculada para o dual no item anterior.

e) Utilizando o teorema das folgas complementares, mostre que, partindo da solucao dual do item c), pode-se obtera solucao primal do item d).

A solucao dual do item c) foi uC = 0 e uF = 0, 333 OU uC = 0, 5 e uF = 0, ambos com w = 15. Pelo teoremadas folgas complementares, tem-se:

u(Ax− b) = 0 ⇒{

0 = 00, 333xA + 0, 666xF + 2xL + 1, 333xC + xB − 15) = 0

Para determinar quais variaveis tem valor zero, utiliza-se a outra equacao do teorema das folgas complementares:

(c− uA)x = 0 ⇒

(5− 3uC − uF )xA = 0(7− 4uC − 2uF )xF = 0(4− 4uC − 6uF )xL = 0(8− 6uC − 4uF )xC = 0(1− 2uC − 3uF )xB = 0

⇒

4, 666xA = 0 → xA = 06, 333xF = 0 → xB = 02xL = 0 → xL = 06, 666xC = 0 → xC = 00xB = 0 → xB =?

Tem-se entao que todas as variaveis, exceto xB, sao zero. Aplicando no sistema obtido anteriormente:{0 = 00, 333xA + 0, 666xF + 2xL + 1, 333xC + xB − 15) = 0

⇒

⇒ xB − 15 = 0 → xB = 15

Que e a mesma solucao do primal obtida pelo simplex.

10

Questao 4. Considere o seguinte problema de programacao inteira:

Maximizar z = 5x1 + x2 (1)

Sujeito a − x1 + 2x2 ≤ 4 (2)

x1 − x2 ≤ 1 (3)

4x1 + x2 ≤ 12 (4)

x1, x2 ≥ 0 (5)

x1, x2 ∈ Z (6)

a) Removendo a restricao (6), que exige que as variaveis sejam inteiras, tem-se um problema de programacao linearcontınua. Resolva o problema sem tal restricao.

Tal problema possui apenas duas restricoes, logo, pode ser resolvido pelo metodo grafico, como visto a seguir.

Para cada reta definida pelas restricoes, deve-se descobrir dois pontos para que seja possıvel tracejar as mesmas:

– Restricao 1: −x1 + 2x2 ≤ 4 ⇒ reta −x1 + 2x2 = 4.

∗ Para x1 = 0: 2x2 = 4 → x2 = 2 ⇒ ponto (0, 2).

∗ Para x2 = 0: −x1 = 4 → x1 = −4 ⇒ ponto (−4, 0).– Restricao 2: x1 − x2 ≤ 1 ⇒ reta x1 − x2 = 1.

∗ Para x1 = 0: −x2 = 1 → x2 = −1 ⇒ ponto (0,−1).∗ Para x2 = 0: x1 = 1 ⇒ ponto (1, 0).

– Restricao 3: 4x1 + x2 ≤ 12 ⇒ reta 4x1 + x2 = 12.

∗ Para x1 = 0: x2 = 12 ⇒ ponto (0, 12).

∗ Para x2 = 0: 4x1 = 12 → x1 = 3 ⇒ ponto (3, 0).

O grafico entao e desenhado como na figura a seguir.

x 2

0

1

2

3

4

x1

0 1 2 3

Restrição 1: -x1 + 2x2 ≤ 4Restrição 2: x1 - x2 ≤ 1Restrição 3: 4x1 + x2 ≤ 12

A

D

C

O

Região factível

B

Deve-se entao analisar os pontos extremos (vertices) da regiao factıvel, denotados no grafico por O, A, B, C e D.

– Ponto O: origem (O = (0, 0)).

∗ Aplicando na funcao objetivo: z = (5× 0) + 0 → z = 0.

11

– Ponto A: interseccao do eixo de x2 (ou seja, x1 = 0) e a reta da restricao 1.

∗ Este ponto foi calculado anteriormente para tracar a reta da restricao 1 ⇒ A = (0, 2).


– Ponto B: interseccao do eixo de x1 (ou seja, x2 = 0) e a reta da restricao 2.

∗ Este ponto foi calculado anteriormente para tracar a reta da restricao 2 ⇒ B = (1, 0).


– Ponto C: interseccao da reta da restricao 1 e a reta da restricao 3.

∗ Para determinar este ponto, deve-se resolver o sistema composto das equacoes das retas das restricoes:{−x1 + 2x2 = 44x1 + x2 = 12

Cuja solucao e x1 =209 = 2, 222 e x2 =

289 = 3, 111.

∗ Aplicando na funcao objetivo: z = (5× 209 ) +

289 → z = 128

9 = 14, 222.

– Ponto D: interseccao da reta da restricao 2 e a reta da restricao 3.

∗ Para determinar este ponto, deve-se resolver o sistema composto das equacoes das retas das restricoes:{x1 − x2 = 14x1 + x2 = 12

Cuja solucao e x1 =135 = 2, 166 e x2 =

85 = 1, 6.

∗ Aplicando na funcao objetivo: z = (5× 135 ) +

85 → z = 73

5 = 14, 6.

Como o problema e de maximizacao, a solucao otima e o ponto cujo valor da funcao objetivo e o maior dentretodos. Assim, tem-se que a solucao otima da relaxacao linear e x1 = 13

5 = 2, 166 e x2 = 85 = 1, 6, com

z = 735 = 14, 6.

b) A partir da solucao obtida no item b) anterior, aplique arredondamento e truncamento na mesma para obtersolucoes inteiras. As mesmas sao factıveis?

– Solucao obtida por arredondamento:

∗ xA1 = d2, 166e → xA1 = 3.

∗ xA1 = d1, 6e → xA1 = 2.

Testando factibilidade:

∗ −xA1 + 2xA2 ≤ 4 → −3 + (2× 2) ≤ 4 → −3 + 4 ≤ 4 → 1 ≤ 4 ⇒ OK.

∗ xA1 − xA2 ≤ 1 → 3− 2 ≤ 1 → 1 ≤ 1 ⇒ OK.

∗ 4xA1 + 2xA2 ≤ 12 → (4× 3) + (2× 2) ≤ 12 → 12 + 4 ≤ 12 → 16 ≤ 12 ⇒ infactıvel.

– Solucao obtida por truncamento:

∗ xT1 = b2, 166c → xA1 = 2.

∗ xT1 = b1, 6c → xA1 = 1.

Testando factibilidade:

∗ −xT1 + 2xT2 ≤ 4 → −2 + (2× 1) ≤ 4 → −2 + 2 ≤ 4 → 0 ≤ 4 ⇒ OK.

∗ xT1 − xT2 ≤ 1 → 2− 1 ≤ 1 → 1 ≤ 1 ⇒ OK.

∗ 4xT1 + 2xT2 ≤ 12 → (4× 2) + (2× 1) ≤ 12 → 8 + 2 ≤ 12 → 10 ≤ 12 ⇒ OK.

c) Mostre, graficamente, as solucoes (pontos) que satisfazem todas as restricoes do problema original (variaveisinteiras), identificando as solucoes calculadas no item b).

Na figura abaixo, os pontos inteiros da regiao factıvel sao denotados por Ik. A solucao obtida por arredondamentoe denotada por A e a obtida por truncamento e denotada por T .

12

x 2

0

1

2

3

4

x1

0 1 2 3

Restrição 1: -x1 + 2x2 ≤ 4Restrição 2: x1 - x2 ≤ 1Restrição 3: 4x1 + x2 ≤ 12Região factível

I3

I2

I1 I4

I5

I6

I7 = T

I8

I9

A

Os pontos inteiros da regiao factıvel sao:

– I1 = (0, 0).

– I2 = (0, 1).

– I3 = (0, 2).

– I4 = (1, 0).

– I5 = (1, 1).

– I6 = (1, 2).

– I7 = (2, 1).

– I8 = (2, 2).

– I9 = (2, 3).

As duas solucoes obtidas por arredondamento e truncamento:

– A = (3, 2).

– T = I7 = (2, 1).

d) Determine a solucao otima do problema original usando o metodo branch-and-bound.

Resposta:

Primeiramente, observe o criterio que sera usado na selecao de subproblemas: subproblemas encontrados anteri-ormente serao resolvidos antes dos posteriores (ou seja, a cada ramificacao, e resolvido cada subproblema e depoisos subproblemas dos subproblemas). Este criterio e semelhante ao algoritmo de busca em largura em grafos esera usado tambem em outras questoes de branch-and-bound deste gabarito para melhor visualizacao da arvorede enumeracao. Considere que o ındice de cada subproblema Pi indica a ordem de resolucao de mesmo.

13

P0: Problema original relaxado:

Maximizar z = 5x1 + x2

Sujeito a:

− x1 + 2x2 ≤ 4

x1 − x2 ≤ 1

4x1 + x2 ≤ 12

0 ≤ x1, x2 ≥ 0

Solucao de P0:

– x1 = 2, 6

– x2 = 1, 6

– z = 14, 6

Ramificacao na variavel x1: P1 tera a restricao x1 ≥ 3e P2 tera x2 ≤ 2.

P1: Problema P0 com restricao adicional x1 ≥ 3:


Sujeito a:

− x1 + 2x2 ≤ 4

x1 − x2 ≤ 1

4x1 + x2 ≤ 12

x1 ≥ 3

0 ≤ x1, x2 ≥ 0

Solucao de P1: InfactıvelNo podado.

P2: Problema P0 com restricao adicional x1 ≤ 2:


Sujeito a:

− x1 + 2x2 ≤ 4

x1 − x2 ≤ 1

4x1 + x2 ≤ 12

x1 ≤ 2

0 ≤ x1, x2 ≥ 0

Solucao de P2:

– x1 = 2

– x2 = 3

– z = 13

Primeira solucao incumbente (inteira): limite inferiorpassa a ser 13. Como nao ha mais ramificacoes, estae a unica incumbente gerada por este branch-and-bound.

P0

P1 P2

IncumbenteSolução ótima

x1 = 2,6x2 = 1,6z = 14,6

x1 ≥ 3 x1 ≤ 2

Infactívelx1 = 2x2 = 3z = 3

0

1

2

3

4

x1

0 1 2 3

Restrição 1: -x1 + 2x2 ≤ 4

x1 ≤ 2 x1 ≥ 3

Restrição 2: x1 - x2 ≤ 1Restrição 3: 4x1 + x2 ≤ 12

Ótimo darelaxação

4

P1

P2

Ótimointeiro

P0

∪

x 2

Questao 5. Para o problema abaixo, responda o que se pede.

Maximizar z = 9x1 + 7x2 + 5x3 + 2x4

Sujeito a: 5x1 + 4x2 + 3x3 + 2x4 ≤ 7

x1, x2, x3, x4 ∈ {0, 1}

14

a) Qual o problema classico associado? Existe algoritmo eficiente (polinomial) para o mesmo, apesar de ser modeladocomo PI? Justifique.

Resposta:

O problema classico e o da mochila 0/1. A funcao objetivo consiste em maximizar o lucro dos itens colocados namochila. A restricao do problema diz que o peso dos itens (os coeficientes das variaveis na restricao) colocadosna mochila nao deve ultrapassar a capacidade da mesma (no problema dado, pode-se verificar que a capacidadee 7).

A mochila 0/1 e um problema classico de otimizacao NP-difıcil, logo, nao e conhecido nenhum algoritmo polinomialpara o mesmo. No entanto, o problema admite algoritmo pseudopolinomial (ou seja, polinomial no numero deitens da entrada, mas exponencial nos valores numericos da mesma) de tempo O(nC) (onde n e o numero deitens e C e a capacidade da mochila) utilizando programacao dinamica.

b) Resolva o modelo utilizando o metodo branch-and-bound. Dica: nao e necessario usar o simplex, pois cadavariavel so pode assumir um entre dois valores (0 ou 1).

Resposta:

Pode-se verificar, pelo modelo dado e pela formulacao generica do problema, que tem-se 4 itens a serem colocadosem uma mochila de capacidade 7. Os lucros e pesos dos itens sao resumidos na tabela abaixo:

Item (i) Lucro (ì) Peso (pi)1 9 5

2 7 4

3 5 3

4 2 2

A relaxacao linear do problema da mochila 0/1 e o problema da mochila fracionaria, para o qual existe umalgoritmo guloso eficiente para resolver a relaxacao de forma otima. Portanto, tal algoritmo sera usado no lugardo simplex para computar os limites superiores.

O algoritmo para o problema da mochila fracionaria requer o calculo das densidades dos itens. A densidade de

um item i, denotada por di e dada pela divisao de seu lucro pelo seu peso, isto e, di =ìpi

. A seguinte tabela

completa a anterior com as densidades de cada item:

Item (i) Lucro (ì) Peso (pi) Densidade (di)1 9 5 1,8

2 7 4 1,75

3 5 3 1,6667

4 2 2 1

O metodo consiste, entao, em procurar o item de maior densidade e o inserir na mochila, diminuindo o valor dacapacidade C de acordo com o peso do item inserido. Repete-se esta operacao para o resto dos itens ate que oitem de maior densidade nao caiba inteiro na mochila. Nesse caso, coloca-se a maior parte possıvel do item parapreencher a capacidade da mochila. Abaixo tem-se o pseudocodigo desse algoritmo.

Require: conjunto I de itens, onde o item i tem lucro ì e peso pi; capacidade C da mochila.1: function Guloso-MochilaFracionaria(I, `, p, C)2: itensMochila← ∅3: Crestante ← 04: lucro← 05: I ′ ← I . Conjunto de itens fora da mochila

15

6: for cada i ∈ I do

7: di ←ìpi

. Calculo das densidades

8: end for9: while Crestante > 0 do

10: imax ← 111: for cada i ∈ I ′ do . determinacao do item de maior densidade em I ′

12: if di > dimax then13: imax ← i14: end if15: end for16: if pi < Crestante then17: itensMochila← itensMochila ∪ {imax}18: Crestante = Crestante − pimax

19: lucro← lucro+ ìmax

20: else

21: fracaoItem← Crestante

pimax

22: itensMochila← itensMochila ∪ {fracaoItem× imax} . coloca apenas uma porcao do itemna mochila

23: Crestante = Crestante − (fracaoItem× pimax)24: lucro← lucro+ (fracaoItem× ìmax)25: end if26: end while27: return itensMochila e lucro28: end function

E importante ressaltar que tambem pode-se usar o simplex e resolver a relaxacao linear do modelo matematicoao inves desse algoritmo.

Para a determinacao de um limite inferior inicial (ao inves de iniciar com LI = −∞), pode-se usar uma heurısticagulosa para a mochila 0/1, o que pode levar a podas mais cedo no algoritmo e, consequentemente, a uma eco-nomia de tempo na enumeracao. A heurıstica e similar ao algoritmo anterior e consiste em inserir na mochila oitem de maior densidade dentre os que ainda caibam nela (ou seja, nao ha a possibilidade de inserir somente aparte de um item na mochila). O algoritmo fica como se segue.

Require: conjunto I de itens, onde o item i tem lucro ì e peso pi; capacidade C da mochila.1: function Guloso-Mochila0/1(I, `, p, C)2: itensMochila← ∅3: Crestante ← 04: lucro← 05: I ′ ← I . Conjunto de itens fora da mochila6: parar ← falso . Utilizado para determinar se nenhum item restante cabe na mochila7: for cada i ∈ I do

8: di ←ìpi

. Calculo das densidades

9: end for10: while parar = falso do11: imax ← 112: parar ← verdadeiro13: for cada i ∈ I ′ do . determinacao do item de maior densidade em I ′ que ainda caiba14: if pi < Crestante then15: parar ← falso16: if di > dimax then17: imax ← i18: end if

16

19: end if20: end for21: if parar = falso then22: itensMochila← itensMochila ∪ {imax}23: Crestante = Crestante − pimax

24: lucro← lucro+ ìmax

25: end if26: end while27: return itensMochila e lucro28: end function

Os algoritmos serao aplicados agora para determinacao dos limites. Inicialmente sera calculado o limite superior:

– Iteracao #0: capacidade restante 7, itens na mochila = ∅, lucro = 0. O item de maior densidade e 1, logo,ele entrara na mochila.

– Iteracao #1: capacidade restante 2, itens na mochila = {1}, lucro = 9. O item de maior densidade e 2,

logo, ele entrara na mochila. Como ele nao cabe inteiro, sera colocadoCrestante

p2=

2

4= 0, 5 do item na

mochila.

– A solucao para o problema relaxado, entao, consiste no item 1 inteiro e 0, 5 do item 2, com lucro de 12,5.Equivalentemente, x1 = 1; x2 = 0, 5; x3 = x4 = 0. O limite superior entao e 12,5.

Agora, a determinacao do limite inferior inicial:

– Iteracao #0: capacidade restante 7, itens na mochila = ∅, lucro = 0. O item de maior densidade que cabena mochila e 1, logo, ele entrara na mochila.

– Iteracao #1: capacidade restante 2, itens na mochila = {1}, lucro = 9. O item de maior densidade quecabe na mochila e 4, logo, ele entrara na mochila.

– Nenhum outro item cabe na mochila. A solucao obtida pela heurıstica, entao, consiste nos itens 1 e 4 namochila com lucro de 11. Equivalentemente, x1 = 1; x2 = x3 = 0; x4 = 1. O limite inferior entao e 11.

A partir desses dados, o branch-and-bound sera aplicado.

P0: Problema original relaxado:


Sujeito a:

5x1 + 4x2 + 3x3 + 2x4 ≤ 7

0 ≤ x1, x2, x3, x4 ≤ 1

Solucao de P0:

– x1 = 1

– x2 = 0, 5

– z = 12, 5

Ramificacao na variavel x2: P1 tera a restricao x2 = 0e P2 tera x2 = 1.

P1: Problema P0 com restricao adicional x2 = 0:


Sujeito a:

5x1 + 4x2 + 3x3 + 2x4 ≤ 7

x2 = 0

0 ≤ x1, x2, x3, x4 ≤ 1

Solucao de P1:

– x1 = 1

– x3 = 0, 6667

– z = 12, 3333


17



Sujeito a:

5x1 + 4x2 + 3x3 + 2x4 ≤ 7

x2 = 1

0 ≤ x1, x2, x3, x4 ≤ 1

Solucao de P2:

– x1 = 0, 6

– x2 = 1

– z = 12, 4




Sujeito a:

5x1 + 4x2 + 3x3 + 2x4 ≤ 7

x2 = 0

x3 = 0

0 ≤ x1, x2, x3, x4 ≤ 1

Solucao de P3:

– x1 = 1

– x4 = 1

– z = 11

Solucao incumbente: valor igual ao limite inferior.Observe que essa solucao obtida e a mesma da heu-rıstica.



Sujeito a:

5x1 + 4x2 + 3x3 + 2x4 ≤ 7

x2 = 0

x3 = 1

0 ≤ x1, x2, x3, x4 ≤ 1

Solucao de P4:

– x1 = 0, 8

– x3 = 1

– z = 12, 2




Sujeito a:

5x1 + 4x2 + 3x3 + 2x4 ≤ 7

x2 = 1

x1 = 0

0 ≤ x1, x2, x3, x4 ≤ 1

Solucao de P5:

– x2 = 1

– x3 = 1

– z = 12

Solucao incumbente (inteira): valor de z e maior queo limite inferior.Assim, essa passa a ser a nova melhor solucao e onovo limite inferior e 12.



Sujeito a:

5x1 + 4x2 + 3x3 + 2x4 ≤ 7

x2 = 1

x1 = 1

0 ≤ x1, x2, x3, x4 ≤ 1


18



Sujeito a:

5x1 + 4x2 + 3x3 + 2x4 ≤ 7

x2 = 0

x3 = 1

x1 = 0

0 ≤ x1, x2, x3, x4 ≤ 1

Solucao de P7:

– x3 = 1

– x4 = 1

– z = 7

Solucao incumbente (inteira): valor de z e menor queo limite inferior.O limite inferior nao e alterado.



Sujeito a:

5x1 + 4x2 + 3x3 + 2x4 ≤ 7

x2 = 0

x3 = 1

x1 = 1

0 ≤ x1, x2, x3, x4 ≤ 1


A solucao otima, entao, consiste em adicionar os itens 2 e 3 na mochila.

P0

P1 P2

P3

Incumbente IncumbenteSolução ótimaP7

Incumbente

x1 = 0 x3 = 1

P8

x3 = 1x4 = 1z = 7

x1 = 1x2 = 0,5z = 12,5

x2 = 0 x2 = 1

x1 = 1x3 = 0,667z = 12,333

x1 = 0,6x2 = 1

z = 12,4

x3 = 0 x3 = 1

P4

x1 = 1x4 = 1z = 11

x1 = 0,8x3 = 1

z = 12,2

P5

x2 = 1x3 = 1z = 12

x1 = 0 x1 = 1

Infactível

P6

Infactível

Solucao otima: x1 = 0, x2 = 1, x3 = 1, x4 = 1, z = 12.

Questao 6. Considere o seguinte problema de programacao inteira:

Maximizar z = x1 + x2

Sujeito a: 3x1 + 2x2 ≤ 6

− 3x1 + 2x2 ≤ 0

x1, x2 ∈ Z

19

O quadro otimo obtido apos a aplicacao do algoritmo simplex em sua relaxacao linear (onde x3 e x4 sao as variaveisde folga associadas a primeira e segunda restricoes, respectivamente) e dado por:

BASE x1 x2 x3 x4 b

x1 1 0 1/6 -1/6 1x2 0 1 1/4 1/4 3/2

z 0 0 5/12 1/12 5/2

Qual o corte de Gomory associado a este quadro? Expresse este corte em termos das variaveis originais do problema.Reotimize e expresse o novo corte de Gomory, se houver.

Resposta:

A forma padrao do problema e dada a seguir:


Sujeito a: 3x1 + 2x2 + x3 = 6

− 3x1 + 2x2 + x4 = 0

x1, x2, x3, x4 ∈ Z

De acordo com o quadro, a variavel x2 tem valor 32 = 1, 5. Logo, o corte sera formulado em torno da linha desta

variavel basica. Tal linha define a seguinte restricao:

x2 +1

4x3 +

1

4x4 =

3

2

Equivalentemente, da forma vista em sala de aula, temos que o valor variavel x2 e dado por (onde N e o conjunto devariaveis nao-basicas):

x2 = b2 −∑j∈N

a2jxj ⇒ x2 =3

2− 1

4x3 −

1

4x4

Separando a equacao em partes inteiras e fracionarias (onde todas as partes fracionarias sao positivas ou 0):

x2 = (1− 0x3 − 0x4) +

(1

2− 1

4x3 −

1

4x4

)Como a parte fracionaria e estritamente menor que 1, para que ela seja inteira, a mesma deve ser menor ou igual azero. Assim, temos o corte:

1

2− 1

4x3 −

1

4x4 ≤ 0 ⇒ −1

4x3 −

1

4x4 ≤ −

1

2⇒ −1

4x3 −

1

4x4 + x5 = −

1

2

Teremos entao o seguinte problema cuja relaxacao linear contınua sera resolvida pelo simplex:


Sujeito a: 3x1 + 2x2 + x3 = 6

− 3x1 + 2x2 + x4 = 0

− 14x3 −

14x4 + x5 = −1

2

x1, x2, x3, x4, x5 ∈ Z

O quadro otimo do novo problema e dado abaixo:

BASE x1 x2 x3 x4 x5 b

x1 1 0 1/3 0 -2/3 4/3x2 0 1 0 0 1 1x4 0 0 1 1 -4 2

z 0 0 1/3 0 1/3 7/3

20

Tal solucao continua sem ser inteira. A variavel x1 tem valor fracionario, logo, o corte sera obtido na linha de talvariavel. A linha de x1 define a seguinte equacao:

x1 +1

3x3 −

2

3x5 =

4

3⇒ x1 =

4

3− 1

3x3 −

(−2

3x5

)Separando em partes inteiras e fracionarias (onde estas ultimas sao nao negativas):

x1 =4

3− 1

3x3 −

(−2

3x5

)⇒ x1 = (1− 0x3 + x5) +

(1

3− 1

3x3 −

1

3x5

)O novo corte sera, entao:

−1

3x3 −

1

3x5 + x6 = −

1

3

E o novo problema:


Sujeito a: 3x1 + 2x2 + x3 = 6

− 3x1 + 2x2 + x4 = 0

− 14x3 −

14x4 + x5 = −1

2

− 13x3 −

13x5 + x6 = −1

3

x1, x2, x3, x4, x5, x6 ∈ Z

Cujo quadro otimo e:

BASE x1 x2 x3 x4 x5 x6 b

x1 1 0 13/15 0 0 -8/5 2x2 0 1 -4/5 0 0 12/5 0x4 0 0 5 1 0 -12 6x5 0 0 1 0 1 -3 1

z 0 0 1/15 0 0 4/5 2

Esta solucao e inteira, portanto, e a solucao otima do problema original de programacao inteira.

Solucao otima: x1 = 2, x2 = 0, z = 2.

QUESTOES SOMENTE PARA O PPGI (opcional para a graduacao)

Questao 7. O problema de cobertura de vertices pode ser definido como se segue. Seja G = (V,E) um grafo simplesnao direcionado com n vertices. Uma cobertura de vertices de G consiste em um subconjunto V ∗ ⊆ V tal que, paracada aresta (i, j) ∈ E, tem-se que ou i ∈ V ∗, ou j ∈ V ∗ ou entao ambos i, j ∈ V ∗. O problema consiste, entao,em determinar a menor cobertura de vertices possıvel para G. O modelo matematico de PI para o problema e dado aseguir.

Minimizar∑i∈V

xi

Sujeito a: xi + xj ≥ 1 ∀(i, j) ∈ E

xi ∈ {0, 1} ∀i ∈ V

a) Forneca um algoritmo 2-aproximativo para o problema.

Resposta:

21

Um algoritmo aproximativo para o problema consiste em avaliar as arestas do grafo em uma ordem qualquer. Acada aresta (i, j) nao coberta, deve-se adicionar ambos i e j a cobertura. O pseudocodigo deste procedimento edado abaixo.

1: function CoberturaVertices-2Apr(V, E)2: cobertura← ∅3: E′ ← E4: while E′ 6= ∅ do5: (i, j)← aresta arbitraria de E′

6: cobertura← cobertura ∪ {i, j}7: Remover de E′ todas as arestas incidentes a i ou j8: end while9: return cobertura

10: end function

b) Prove a razao de aproximacao do algoritmo dado no item anterior.

Resposta:

Seja A o conjunto de todas as arestas selecionadas na linha 5 do algoritmo dado no item anterior e C a coberturagerada. Observe que, para cobrir as arestas em A qualquer cobertura de vertices deve incluir pelo menos umdos vertices (i ou j) de cada aresta (i, j) ∈ A. No entanto, as arestas em A nao possuem vertices em comum,uma vez que toda vez que uma aresta (i, j) e selecionada na linha 5, as outras arestas incidentes a i ou a j saodescartadas. Logo, quaisquer duas arestas em A nao sao cobertas pelo mesmo vertice, o que fornece um limiteinferior para a cobertura otima, isto e:

OPT ≥ |A|

Onde OPT e o tamanho da menor cobertura de vertices de G. Quando uma aresta de A e selecionada, saoadicionados dois vertices para a cobertura, ou seja:

|C| = 2× |A|

Portanto:

|C| = 2× |A| ≤ 2×OPT ⇒ |C| ≤ 2×OPT

c) Qual a relacao do algoritmo 2-aproximativo com outro problema classico de otimizacao envolvendo grafos?

Resposta:

O algoritmo dado no item a) consiste em determinar um emparelhamento maximal (maximal matching) no grafo.O problema de emparelhamento consiste em determinar um subconjunto de arestas tais que, para qualquer parde arestas (i, j) e (k, l) no subconjunto, tem-se que i 6= k, i 6= l, j 6= k e j 6= l (ou seja, nao possuemvertices em comum). Existem algoritmos polinomiais para a determinacao de emparelhamentos maximos (todoemparelhamento maximo e maximal, mas o inverso nem sempre e verdade).

22

Documents

Lista de Exerc cios I - Gabaritoioc-ufam.weebly.com/uploads/5/0/7/0/50702097/ioc201501... · ij jSj 1 (8S ˆV) (3) x ... na tabela a seguir. A˘ca Carne de frango Leite Carne de boi