Notas de Aula Pesquisa Operacional DCC-UFMG

Fazer download em pdf ou txt
Fazer download em pdf ou txt
Você está na página 1de 150

G. Coutinho e C. Arbex Valle DCC035 P.O.

Pesquisa Operacional
Notas de aula do curso de Pesquisa Operacional do
Dept. de Ciência da Computação da UFMG

Versão de 7 de junho de 2022

Bibliografia
A maior parte do material nestas notas de aula se baseiam em capı́tulos e passagens das
seguintes referências. Alguns exemplos foram copiados ipsis literis.

(i) Bertrand Guenin, Jochen Könemann, and Levent Tunçel. A gentle introduction to
optimization. Cambridge University Press, 2014.

(ii) Marco Cesar Goldbarg, and Henrique Pacca L. Luna. Otimização combinatória e pro-
gramação linear: modelos e algoritmos. Elsevier, 2005.

(iii) Christos Papadimitriou, and Kenneth Steiglitz. Combinatorial optimization: algo-


rithms and complexity. Courier Corporation, 1998.

(iv) Vasšek Chvátal. Linear programming. W.H. Freeman and Company, 1983.

(v) Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli. Integer programming.
Springer, 2014.

1
Sumário

1 Programações lineares 4
1.1 Introdução ao curso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Otimização neste curso . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Introdução à Programação linear . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Exemplo prático . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Programação linear - formalização . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Modelagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 Formas de apresentar uma PL . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6 Toda PL tem solução ótima? . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6.1 PLs inviáveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6.2 PLs ilimitadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.6.3 PLs com soluções ótimas . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.6.4 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2 Simplex 22
2.1 Começando a pensar no Simplex . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Uma base de soluções viáveis . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.1 Como encontrar um certificado de ilimitada . . . . . . . . . . . . . . 29
2.4 O simplex via tableaus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5 O problema de achar soluções viáveis - simplex fase 2 . . . . . . . . . . . . . 33
2.6 Pseudo-código e sutilezas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.6.1 Múltiplas soluções ótimas . . . . . . . . . . . . . . . . . . . . . . . . 36
2.6.2 Soluções degeneradas . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.7 Como achar certificados de ótimo e inviabilidade? . . . . . . . . . . . . . . . 40
2.8 Método Simplex Dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3 Dualidade 46
3.1 Dualidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2 A PL dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3 Teorema fraco da Dualidade . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4 Teorema Forte da Dualidade . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.5 PLs inviáveis ou ilimitadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.6 Folgas complementares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

2
G. Coutinho e C. Arbex Valle DCC035 P.O.

3.7 Análise de sensibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58


3.8 Teoria de jogos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.8.1 Estratégias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.8.2 Teorema Minimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.9 Interpretação econômica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

4 Geometria e teorema de alternativas 70


4.1 Geometria de poliedros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2 Teorema de alternativas e dualidade . . . . . . . . . . . . . . . . . . . . . . . 74
4.3 Geometria de otimização poliédrica . . . . . . . . . . . . . . . . . . . . . . . 77

5 Programações inteiras 78
5.1 Programações inteiras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.2 Modelagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.3 Escrevendo uma PI como uma PL . . . . . . . . . . . . . . . . . . . . . . . . 84
5.4 Planos de corte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.5 Branch and bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

6 Formulando programações inteiras 96


6.1 Problema do caixeiro viajante . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.1.1 Formulação matemática . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.1.2 Formulação alternativa: MTZ (opcional) . . . . . . . . . . . . . . . . 103
6.2 Problema da mochila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.3 Problema das “várias mochilas”, ou geração de colunas . . . . . . . . . . . . 107
6.4 Alguns truques de formulação . . . . . . . . . . . . . . . . . . . . . . . . . . 110

7 Otimização em grafos 113


7.1 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
7.2 Fluxos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
7.3 Matrizes totalmente unimodulares . . . . . . . . . . . . . . . . . . . . . . . . 119
7.3.1 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.4 O método de Ford e Fulkerson — um algoritmo primal-dual (leitura opcional) 123
7.5 Emparelhamentos e coberturas . . . . . . . . . . . . . . . . . . . . . . . . . . 128
7.5.1 Cobertura por vértices em grafos quaisquer . . . . . . . . . . . . . . . 132
7.5.2 Problema do transporte . . . . . . . . . . . . . . . . . . . . . . . . . 133
7.6 Um algoritmo primal-dual para emparelhamento perfeito de menor custo . . 135
7.7 Cobertura por conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
7.8 Um algoritmo primal-dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
7.9 Um algoritmo guloso para o problema de cobertura de conjuntos sem pesos . 143
7.10 Empacotamento, partição e coberturas — uma revisão . . . . . . . . . . . . 145
7.10.1 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
7.11 Colorações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
7.12 Localização de instalações (facility location) . . . . . . . . . . . . . . . . . . 148
7.12.1 Algoritmo primal-dual . . . . . . . . . . . . . . . . . . . . . . . . . . 149

3
Capı́tulo 1

Programações lineares

Aula 2
1.1 Introdução ao curso
Apesar de o nome do curso ser Pesquisa Operacional, talvez seria mais descritivo se fosse
chamado “Introdução à otimização”. Problemas de otimização são uma (grande) sub-área
da Pesquisa Operacional. Matematicamente falando, um problema de otimização é um
problema em que se busca achar o máximo ou o mı́nimo de uma função dentro de um
determinado conjunto. Por exemplo:

• Quais são os valores máximo e mı́nimo da função f (x) = x2 com x ∈ R?

• E se o intervalo for limitado a [1, 5]? Qual seu mı́nimo e máximo neste intervalo?

Chamamos o primeiro caso de um problema de otimização irrestrita, isto é, não há
condições restringindo o domı́nio. O segundo caso é conhecido como um problema de oti-
mização restrita uma vez que restrições são impostas no conjunto possı́vel de valores que
x pode assumir. Buscamos a solução ótima, isto é, o ponto onde a função atinge o valor
máximo ou mı́nimo dentre os valores possı́veis do domı́nio.
A dificuldade de um problema de otimização pode estar na descrição da função, ou na
compreensão do conjunto. Ou em ambos. Por exemplo:

• Qual o máximo da função f (x, y) = x2 /y y se x e y estão entre -1 e 1?

• Qual o máximo da função f (x) = sin(x) entre os números racionais?

Funções como as que descrevemos acima tipicamente necessitam do uso do cálculo para
estudarmos seus pontos de máximo e mı́nimo. Neste curso, entretanto, nossas funções serão
mais simples.

4
G. Coutinho e C. Arbex Valle DCC035 P.O.

1.1.1 Otimização neste curso


Neste curso estamos interessados em duas sub-áreas da Pesquisa Operacional, chamadas
Programação Linear (PL) e Programação Inteira (PI). Ambas estas técnicas buscam
reescrever matematicamente problemas do mundo real através de problemas de otimização
restritos. Um termo mais amplo que engloba tanto PL quanto PI é a Programação Ma-
temática, definido como a utilização de ferramentas matemáticas para a alocação ótima de
recursos limitados quando planejamos (programamos) atividades.
Tanto em PL quanto PI, estamos interessados somente em otimizar funções lineares.
Uma função f é linear se, para vetores x e y e um número a,

f (x + y) = f (x) + f (y) e f (a · x) = a · f (x)


Por exemplo,

f (x) = 2x f (x1 , x2 ) = 2x1 + 3x2 f (x1 , x2 , x3 ) = x1 − x2 + 5x3

são funções lineares, ao passo que

f (x) = x + 5 f (x1 , x2 ) = x1 x2 f (x1 , x2 , x3 ) = x21 + x3

não são.
Exercı́cio 1. Prove estes fatos.
Otimizar uma função linear (ou decidir que não é possı́vel achar o seu ótimo) é a princı́pio
uma tarefa simples. Por exemplo:

• Qual o máximo de f (x) = 2x?

• Qual o máximo da mesma função no intervalo [−4, 10]?

Problemas de otimização linear se tornam difı́ceis quando há mais variáveis. Neste caso, a
dificuldade estará sempre na compreensão do conjunto onde a função está sendo definida,
ou nas restrições que as variáveis da função devem satisfazer. Neste curso, essas restrições
serão também sempre lineares, mas ainda assim veremos que os problemas podem ser bem
difı́ceis.

1.2 Introdução à Programação linear


A primeira parte do curso trata apenas de Programação Linear (PL), o mais “simples” dos
modelos de programação matemática. Há centenas de aplicações práticas de PL em uma
vasta gama de áreas, incluindo problemas de logı́stica na indústria, mercados financeiros,
ciências sociais e naturais, e muitas outras. A teoria e suas aplicações começou por volta da
Segunda Guerra Mundial, com Leonid Kantorovich utilizando-a para modelar a economia
centralizada da União Soviética e George Dantzig utilizando-a para modelar problemas de
logı́stica decorrentes da guerra. Dantzig também desenvolveu o primeiro algoritmo efetivo
para resolver problemas de PL - o chamado algoritmo Simplex - que ainda hoje é largamente

5
G. Coutinho e C. Arbex Valle DCC035 P.O.

utilizado em solvers comerciais e open-source de problemas de programação matemática. O


enorme aumento de poder computacional nas últimas décadas permite hoje resolver eficien-
temente problemas de PL com centenas de milhares de variáveis.
Um problema de PL é descrito por três componentes importantes:

• Variáveis de decisão, que representam efetivamente a decisão que deve ser tomada
no problema modelado,

• Função objetivo, que representa em um valor numérico o benefı́cio ou custo asso-


ciado às decisões que devem ser tomadas. É a função que deve ser maximizada ou
minimizada.

• Restrições, que representam a limitação dos recursos do mundo real. As restrições


impõem que a solução deve obedecer certas regras.

Em um problema de PL, a função objetivo e as restrições são sempre lineares e as variáveis


de decisão são sempre variáveis reais (possivelmente dentro de um intervalo).

1.2.1 Exemplo
Ache o máximo da função f (x1 , x2 ) = x1 + x2 supondo que x1 e x2 satisfaçam

x1 ≥ 0 ; x2 ≥ 0 ; 2x1 + x2 ≤ 4 ; x1 + 2x2 ≤ 3.

No caso, as variáveis de decisão são dadas por x1 e x2 e a função objetivo é maximizar x1 +x2 .
Abaixo, reescrevemos este PL utilizando a notação mais comum:

max x1 + x 2
sujeito a 2x1 + x2 ≤ 4
x1 + 2x2 ≤ 3
x1 ≥ 0
x2 ≥ 0

Ao desenhar estas desigualdades no gráfico, a região delimitada é dada por:

6
G. Coutinho e C. Arbex Valle DCC035 P.O.

2x1 + x2 = 4
x2

x1 + 2x2 = 3

0
0 1 2 3 4
x1

Observe que qualquer ponto à direita da reta azul torna a desigualdade 2x1 +x2 ≤ 4 inválida.
Por exemplo, considere o ponto (2, 2) - neste caso temos que 6  4 e diz-se que a desigualdade
foi violada. Já para qualquer ponto à esquerda da reta azul o oposto ocorre. Por exemplo,
ao substituirmos o ponto (1, 1) na desigualdade obtemos 3 ≤ 4.
Desta forma, temos que:

• Apenas pontos à esquerda e abaixo da reta azul respeitam a desigualdade 2x1 + x2 ≤ 4,

• Apenas pontos à esquerda e abaixo da reta vermelha respeitam a desigualdade x1 +


2x2 ≤ 3,

• Apenas pontos à direita do eixo x2 respeitam a desigualdade x1 ≥ 0 e

• Apenas pontos acima do eixo x1 respeitam a desigualdade x2 ≥ 0.

A união destes conjuntos é chamada de região viável ou área viável e pode ser vista
no gráfico abaixo:

7
G. Coutinho e C. Arbex Valle DCC035 P.O.

2x1 + x2 = 4
x2

Área viável x1 + 2x2 = 3

0
0 1 2 3 4
x1

Todos os pontos da região viável são soluções válidas para o problema. A principal questão de
um problema de PL é encontrar, dentre todos os pontos válidos, qual é aquele que maximiza
ou minimiza a função objetivo desejada.
Exercı́cio 2. Dentro da área viável acima, qual par de pontos (x1 , x2 ) maximiza x1 + x2 ?
E 3x1 + x2 ? E x1 − x2 ? E minimizar?
Três comentários importantes:

(i) Se você prestou atenção, o máximo ou mı́nimo sempre acabou sendo um dos vértices.
Isto nem sempre é o caso, por exemplo, se quiséssemos o máximo de f (x1 , x2 ) = 2x1 +x2
ou o mı́nimo de f (x1 , x2 ) = x1 . Mas sempre será o caso de que o máximo ocorrerá num
ponto de fronteira entre o conjunto e o seu complemento.
(ii) Nem sempre problemas deste tipo terão solução, mas isto sempre dependerá do con-
junto em que estamos otimizando, nunca da função. Por exemplo, qual o máximo de
f (x1 , x2 ) = x1 + x2 no conjunto
x1 ≥ 0 ; x2 ≥ 0 ; x1 − x2 ≤ 2 ?
E em
x1 ≥ 0 ; x2 ≥ 0 ; x1 + x2 ≤ −2 ?

(iii) Problemas deste tipo possuem grande aplicabilidade prática. Veremos logo mais um
exemplo. Infelizmente, a grande parte dos problemas ocorre com muitas variáveis, ou
seja, é impossı́vel termos uma visualização gráfica fiel ao problema. Entretanto, procure
manter sempre uma intuição geométrica: dentro de um conjunto limitado por retas, ou
planos, ou hiperplanos, você estará procurando o canto onde um plano, ou hiperplano,
atinge seu máximo ou mı́nimo.

8
G. Coutinho e C. Arbex Valle DCC035 P.O.

1.2.2 Exemplo prático


Suponha uma empresa que produza 4 tipos de produto. A empresa possui duas máquinas
diferentes e a produção de cada produto requer horas em ambas as máquinas, além de horas
operacionais e horas em um processo de controle de qualidade. A tabela abaixo especifica,
para cada produto, quantas horas são necessárias em cada máquina/atividade. A tabela
inclui também o preço de venda (assuma demanda infinita):

Produto Máquina 1 Máquina 2 Operacional Qualidade Preço de venda


1 11 4 8 7 300
2 7 6 5 8 260
3 6 5 5 7 220
4 5 4 6 4 180

Por mês, a máquina 1 pode funcionar no máximo 700 horas, e a 2 por no máximo 500
horas. A empresa pode comprar no máximo 600 horas de trabalho operacional ao custo de 8
reais a hora, e 650 horas de controle de qualidade ao custo de 6 reais a hora. Quantos itens
de cada produto a empresa deve produzir de forma a maximizar seu lucro?
Vamos formular esse problema como uma PL.

(i) Variáveis de decisão: Temos que decidir quantas unidades de cada produto serão
produzidas. Para isso, vamos criar variáveis x1 , x2 , x3 , x4 representando estes valores.
Ou seja, x1 é uma variável ainda desconhecida cujo valor é o número de unidades que
devem ser produzidas do produto 1. Estas são as únicas incertezas a respeito deste
problema, e todos os demais valores associados (por exemplo: quantas horas usar de
uma determinada máquina?) serão determinados por x1 ,..,x4 .
Entretanto, muitas vezes o uso de variáveis adicionais facilita a compreensão e expressão
do problema. Neste caso, vamos introduzir variáveis y1 e y2 que representam as quan-
tidades de horas de trabalho operacional e controle de qualidade utilizadas. Ao final,
veremos também que teria sido possı́vel modelar o problema sem usar essas variáveis.
(ii) Função objetivo: A empresa busca maximizar o lucro. A função matemática que
representa o lucro é dada por:

300x1 + 260x2 + 220x3 + 180x4 − 8y1 − 6y2 .

(iii) Restrições:
Podemos utilizar no máximo 700 horas da máquina 1:

11x1 + 7x2 + 6x3 + 5x4 ≤ 700.

E no máximo 500 horas na máquina 2:

4x1 + 6x2 + 5x3 + 4x4 ≤ 500.

Trabalho operacional:
8x1 + 5x2 + 5x3 + 6x4 ≤ y1

9
G. Coutinho e C. Arbex Valle DCC035 P.O.

Controle de qualidade:
7x1 + 8x2 + 7x3 + 4x4 ≤ y2 .
As limitações na quantidade de horas que podem ser contratadas:

y1 ≤ 600 e y2 ≤ 650.

Não faz sentido que as variáveis possam ter valores negativos, logo:

x1 , x2 , x3 , x4 , y1 , y2 ≥ 0.

Estas últimas restrições são geralmente chamadas de restrições de não-negatividade.

Exercı́cio 3. Como ficaria este modelo caso optássemos por não utilizar as variáveis y1 e
y2 ?

Exercı́cio 4. Resolva esta PL.

1.3 Programação linear - formalização


Uma programação linear (PL) é definida como um um problema de maximizar ou minimizar
uma função linear (ou afim) sujeita a um número finito de restrições lineares. Considerando
o exemplo:

max 3x1 + 2x2 − x3 + 5 (1.1)


sujeito a x 1 + x2 ≤ 9
x3 ≤ 3
x1 , x2 , x3 ≥ 0,

estamos maximizando a função objetivo f (x1 , x2 , x3 ) = 3x1 + 2x2 − x3 + 5 sujeita às


restrições x1 + x2 ≤ 9, x3 ≤ 3, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

Importante: uma restrição linear é sempre uma inequação da forma

f (x) ≤ β , f (x) ≥ β , f (x) = β,

onde x é um vetor de variáveis e β é um escalar. Note que

3x1 + 5x2 − x3 + x4 < 5

não é uma restrição linear, já que a desigualdade é estrita.


Uma solução para a formulação (1.1) é uma atribuição de valores às variáveis (x1 , x2 , x3 ).
Uma solução é viável se possui a propriedade de que todas as restrições são satisfeitas. Uma
solução é ótima se é viável e maximiza (ou minimiza se o problema for de minimização) a
função objetivo.

10
G. Coutinho e C. Arbex Valle DCC035 P.O.

Aulas 3 e 4
1.4 Modelagem
Como dito anteriormente, a PL modela diversos problemas da vida real. Nesta seção, in-
cluı́mos alguns exercı́cios e exemplos de aplicações.

Exemplo 1. Considere o seguinte problema de demanda, armazenamento e distribuição.


Uma companhia local, Pompéu Insumos, de revenda de insumos agrı́colas prevê que nos
próximos meses, a demanda por seu principal insumo seja a seguinte:
mês 1 2 3 4
demanda em litros 5000 8000 9000 6000

No começo de cada mês, esta empresa pode comprar este insumo de um distribuidor regional
pelos seguintes valores:
mês 1 2 3 4
custo por litro 0.75 0.72 0.92 0.90

A Pompéu Insumos possui um tanque de armazenamento de 4000 litros, que atualmente


já contém 2000 litros. A empresa deseja saber quantos litros de insumo deve comprar no
começo de cada mês para suprir a demanda e ao mesmo tempo minimizar seus custos. Note
que se o insumo é comprado e revendido imediatamente, não é preciso armazená-lo no tanque.
Somente o excedente para o mês seguinte é armazenado. Para simplificar, assumimos que o
custo de armazenamento é zero (o que pode não ser verdade na prática).

• Variáveis de decisão: Cada mês, Pompéu Insumos precisa determinar (1) quantos litros
comprar e (2) quantos armazenar do insumo. Estes valores são incertos e devem ser
decididos pela empresa: são os candidatos ideais para as variáveis de decisão.
Introduzimos então 8 variáveis: p1 , ..., p4 referentes a quanto comprar, e t1 , ..., t4 refe-
rentes à capacidade ocupada do tanque. Note que já fomos informados que t1 = 2000.

• Função objetivo: Como informado, a Pompéu Insumos deseja minimizar o custo de


compra dos insumos. Então a função objetivo é

min 0.75p1 + 0.72p2 + 0.92p3 + 0.90p4 .

• Restrições: No começo do primeiro mês, a quantidade de insumos comprada, acrescida


da quantidade que já havia no tanque, deve ser igual ou exceder a demanda do primeiro
mês, e este excedente corresponde exatamente ao que é armazenado para o segundo
mês. Portanto
p1 + t1 = 5000 + t2 .
A restrição acima impõe a consistência dos valores envolvidos. Igualmente

p2 + t2 = 8000 + t3 , p3 + t3 = 9000 + t4 , p4 + t4 ≥ 6000.

11
G. Coutinho e C. Arbex Valle DCC035 P.O.

Exercı́cio 5. Termine de formular esta PL, incluindo condições iniciais e demais restrições,
e escreva no formato de (1.1). Qual você acredita ser a solução ótima para o problema?
Como o problema seria alterado se o custo de armazenamento fosse 0.10 por litro de insumo
por mês?

Exercı́cio 6. Considere a seguinte tabela nutricional de alguns tipos de comida:


Comida preço / porção calorias / p. gordura / p. proteı́na / p. carbs / p.
Cenoura 0.14 23 0.1 0.6 6
Batata 0.12 171 0.2 3.7 30
Pão integral 0.20 65 0.0 2.2 13
Queijo 0.75 112 9.3 7.0 0
Amendoim 0.15 188 16.0 7.7 2

Uma nutricionista deseja montar um cardápio que minimize os custos diários, ao mesmo
tempo que as seguintes demandas nutricionais são satisfeitas:

• pelo menos 2000 calorias

• pelo menos 50g de gordura

• pelo menos 100g de proteı́na

• pelo menos 250g de carbohidratos.

Modele este problema com uma PL (é possı́vel fracionar porções).

Exercı́cio 7. Um banco faz quatro tipos de empréstimos para seus clientes pessoais. Cada
tipo de empréstimo rende os seguintes juros anuais para o banco:

• Primeira hipoteca a 14%

• Segunda hipoteca a 20%

• Reforma residencial a 20%

• Empréstimos pessoais a 10%

O banco pode emprestar no máximo 250 milhões, sendo também restrito pelas seguintes
polı́ticas:

• A primeira hipoteca deve ser pelo menos 55% de todas as hipotecas e pelo menos 25%
de todos os empréstimos.

• A segunda hipoteca não deve exceder 25% de todos os empréstimos.

• Para evitar descontentamento do público, a taxa de juros média não deve exceder 15%.

12
G. Coutinho e C. Arbex Valle DCC035 P.O.

Formule o problema de empréstimos bancários como uma PL visando maximizar o rece-


bimento de juros e satisfazendo as limitações impostas.
Note que estas condições impostas potencialmente limitam o lucro que o banco pode
ter, mas também limitam sua exposição a risco em uma área particular. É um princı́pio
fundamental do gerenciamento de risco que o risco é reduzido ao dividir o dinheiro apropri-
adamente em diferentes áreas.

Exercı́cio 8. Uma refinaria processa três tipos diferentes de petróleo. Cada tipo de petróleo
possui uma planilha de custos diferente, expressando condições de transporte e preços na
origem. A planilha de custos e a quantidade máxima disponı́vel é dada abaixo:

Tipo de petróleo Quantidade máxima Custo por


disponı́vel (barril/dia) barril/dia
1 3500 19
2 2200 24
3 4200 20

Por outro lado, cada tipo de petróleo é mais ou menos apropriado para a produção de
três tipos de gasolina diferentes: amarela, azul e superazul. As especificações de cada tipo
de gasolina são dadas abaixo:

Tipo de gasolina Especificação preço de venda R$/barril


Amarela não mais que 70% de 1 22
não mais que 30% de 1
Azul 28
não menos que 10% de 2
não mais que 30% de 1
Superazul não menos que 40% de 2 35
não mais que 50% de 3

Formule este problema como uma PL que calcule quanto de cada gasolina a empresa deve
produzir, e quais tipos de petróleo deve utilizar em cada de forma a maximizar seus lucros.
Suponha que não há perda volumétrica no processo da refinaria.
DICA: use 9 variáveis, cada variável correspondendo a quanto de cada tipo de petróleo
será usado em cada tipo de gasolina.

Exercı́cio 9. Você administra uma empreiteira, e projeta construir uma casa. As seguintes
atividades devem ser feitas

• B - escavar e fazer a fundação.

• F - subir as paredes

• E - parte elétrica

• P - encanamento

• D - acabamento das paredes e pisos

13
G. Coutinho e C. Arbex Valle DCC035 P.O.

• L - jardim.
Você possui equipes na sua empreiteira que realizam cada uma das atividades. O tempo em
dias para concluir tudo é:
tarefa B F E P D L
tempo 3 2 3 4 1 2
Infelizmente as tarefas não podem ser realizadas todas simultaneamente. Se baseie na lista
de restrições abaixo e formule o problema de construir a casa no menor tempo possı́vel como
uma PL.
• F só pode começar após B.
• L só pode começar após B.
• E só pode começar após F.
• P só pode começar após F.
• D só pode começar após E e P.
Exercı́cio 10. Tente resolver o seguinte sistema de equações:
2x + y = −1
x+y =1
x + 3y =4
−2x + 4y =3
Tentou? Vamos então tentar encontrar os valores que mais se aproximam de ser uma solução
do sistema. Formule o problema de achar um vetor (x, y) que mais se aproxime de resolver
este sistema como uma PL. Ou seja, você deseja achar (x, y) tal que a soma
|2x + y + 1| + |x + y − 1| + |x + 3y − 4| + | − 2x + 4y − 3|
seja mı́nima.
E se ao invés de minimizar a soma, você desejasse minimizar o maior dos valores absolutos.
Ainda é possı́vel modelar como uma PL?
Exercı́cio 11. Em um restaurante, os funcionários trabalham 5 dias consecutivos e folgam
2. Como há dias de mais e menos movimento, a tabela abaixo indica quantos funcionários
devem trabalhar em cada dia da semana:
Dia Seg Ter Qua Qui Sex Sab Dom
Demanda 17 13 15 19 14 16 11
Qual o menor número de funcionários que o restaurante deve contratar de forma a su-
prir a demanda de trabalho? Modele este problema como uma PL (vamos permitir que
funcionários sejam “fracionários” por enquanto). E se o pagamento de funcionários que
trabalham domingo fosse 1.5 vezes o pagamento nos outros dias, como a empresa poderia
minimizar o custo?

14
G. Coutinho e C. Arbex Valle DCC035 P.O.

1.5 Formas de apresentar uma PL


Dado um vetor c ∈ Rn , uma matriz m × n A e um vetor b ∈ Rm , considere a seguinte PL

max cT x
sujeito a Ax ≤ b
x ≥ 0.

Significa que estamos procurando o vetor x ∈ Rn que maximiza o produto interno cT x


sujeito às desigualdades obtidas a partir de cada linha da matriz A, além de restrições de
não-negatividade.

Exemplo 2. Considere a PL

max x1 + x2
sujeito a x1 + 2x2 ≤ 2
2x1 + x2 ≤ 2
x1 , x2 ≥ 0.

Esta PL pode ser expressa na forma matricial descrita acima da seguinte maneira:
 
 x1
max 1 1 ·
x2
    
1 2 x1 2
sujeito a ≤
2 1 x2 2
x ≥ 0.

Também poderı́amos ter incorporado as restrições de não-negatividade na matriz, como


abaixo, mas esta não será nossa preferência geralmente.
 
 x1
max 1 1 ·
x2
   
1 2   2
 2 
1  x1  
sujeito a  ≤ 2
−1 0  x2 0
0 −1 0

Neste exemplo:
   
  1 2 2  
1  2 1 2 x1
c= , A=
−1
 , b= 
0 , x=
1 0 x2
0 −1 0

Exercı́cio 12. Resolva a PL acima.

15
G. Coutinho e C. Arbex Valle DCC035 P.O.

Exercı́cio 13. Considere o primeiro exemplo de PL, (1.1). Identifique naquele exemplo
quais são os vetores c, b, x e a matriz A.
Conforme você notou no exercı́cio, nem sempre o conjunto de desigualdades obtidos da
modelagem poderá ser imediatamente agrupado em um formato matricial, e então alguns
ajustes podem precisar ser feitos.
Como forma de padronizar a interpretação de PLs definimos a forma padrão de igual-
dades (FPI) a seguir.
Definição 1. Uma PL está na forma padrão de igualdades se existem vetores c,b e uma
matriz A tal que a PL se expressa como
max cT x
sujeito a Ax = b
x ≥ 0.
Em outras palavras, uma PL está na FPI se
• é um problema de maximização.
• com exceção das restrições de não-negatividade, todas as outras são igualdades.
• toda variável possui uma restrição de não negatividade.
Qualquer PL pode ser expressa na FPI. Em geral, quando uma inequação é obtida na
formulação, ela pode ser substituı́da por uma igualdade ao adicionarmos uma variável extra.
Exercı́cio 14. Expresse a desigualdade 2x + 3y ≤ 5 utilizando apenas igualdades e/ou
restrições de não-negatividade. Dica: adicione uma variável w.
Faça o mesmo para 8x − y + z ≥ 10.
Problemas de minimização também podem ser expressos como maximização.
Exercı́cio 15. Expresse
min x + y + z
como
max cT x.
Ou seja, diga quais são os vetores c e x.
Ainda pode haver um fator dificultador de que, ao modelarmos o problema, uma das
variáveis não possua uma restrição de não-negatividade. Neste caso, a variável em questão
deve ser substituı́da por duas outras. Note o exemplo abaixo.
Exemplo 3.
min x + y
sujeito a x − y ≤ 2
x + y ≥ −1
x≥0

16
G. Coutinho e C. Arbex Valle DCC035 P.O.

Note que não podemos simplesmente adicionar y ≥ 0, porque isto alteraria a solução da PL.
No caso, a PL dada possui mı́nimo igual a −1 referente à solução (x, y) = (0, −1), onde
y < 0. Para termos restrições de não-negatividade para todas as variáveis, vamos substituir
y por duas variáveis:
y = y+ − y−,
e agora exigimos y + , y − ≥ 0. No caso, quando y = −1, temos y + = 0 e y − = 1, ambos
não-negativos. A PL se torna então:

min x + y + − y −
sujeito a x − (y + − y − ) ≤ 2
x + (y + − y − ) ≥ −1
x, y + , y − ≥ 0

Há portanto três passos básicos a serem realizados para transformar uma PL para a FPI.

(i) Trocar min por max, se necessário, adicionando um sinal negativo em c (lembrando de
multiplicar o valor objetivo encontrado no final por −1).

(ii) Trocar todas as inequações por igualdades adicionando variáveis extras (sempre não-
negativas). Estas serão chamadas de variáveis de folga.

(iii) Trocar cada variável livre por duas variáveis não-negativas.

Exemplo 4. A PL do exemplo 3 se torna portanto:


 
x
 +
 y − 
max −1 −1 1 0 0 · 
y 

 z1 
z2
 
x
  y +   
1 −1 1 1 0   2
sujeito a · y− =
1 1 −1 0 −1   −1
z1 
z2
x, y + , y − , z1 , z2 ≥ 0

Exercı́cio 16. Expresse as PLs obtidas nos exercı́cios de modelagem na FPI.

17
G. Coutinho e C. Arbex Valle DCC035 P.O.

Aula 5
1.6 Toda PL tem solução ótima?
Já discutimos na primeira aula situações em que uma PL possui uma solução ótima, não
possui solução viável, ou é ilimitada. De fato, o Teorema Fundamental de Programações
Lineares estabelece que essas são as únicas possibilidades. Vamos discutir cada uma delas.
Para isto, a notação FPI é bastante útil.

1.6.1 PLs inviáveis


Como vimos, dada uma PL, um vetor x que satisfaça as restrições é chamado de solução
viável. Naturalmente, o objetivo de uma PL é encontrar a solução viável que maximiza ou
minimiza a função objetivo. Ocorre que nem sempre existem soluções viáveis, caso em que
a PL é chamada de inviável.
Exemplo 5. Suponha que o sistema abaixo foi retirado de uma PL em FPI e descreve todas
as suas restrições

4x1 + 10x2 − 6x3 − 2x4 = 6


−2x1 + 2x2 − 4x3 + x4 = 5
−7x1 − 2x2 + 4x4 = 3
x ≥ 0.

Você pode tentar resolver este sistema, mas notará que não é possı́vel. Como entretanto
provar isto?
A verificação de que uma PL é inviável não depende da função objetivo, dependendo
apenas do conjunto de restrições. Podemos provar que um sistema de equações com restrições
de não-negatividade não possui solução ao encontrarmos uma equação tal que

(i) esta equação seja consequência de operações elementares nas equações do sistema e
(ii) todos os coeficientes sejam não-negativos, mas o lado direito seja negativo.

Veja, por exemplo, o que acontece se multiplicarmos a primeira equação por y1 = 1, a


segunda por y2 = −2, a terceira por y3 = 1 e somarmos, obteremos

x1 + 4x2 + 2x3 = −1.

Naturalmente não há quaisquer valores de x1 , x2 , x3 , x4 ≥ 0 que satisfaçam isso.


O vetor y = (y1 , y2 , y3 ) obtido no exemplo acima é chamado de certificado de inviabi-
lidade. Em notação matricial, tı́nhamos
 
  x1    
4 10 −6 −2  x2  6 1
A=  −2 2 −4 1   
, x=  , b=  5 , y=  −2
x3
−7 −2 0 4 3 1
x4

18
G. Coutinho e C. Arbex Valle DCC035 P.O.

e concluı́mos que
Ax = b não é possı́vel pois, ao multiplicar por y, temos y T Ax = y T b,
y T Ax ≥ 0 e y T b < 0.
Exercı́cio 17. Ache um certificado de inviabilidade para o sistema determinado por
    
4 −5 x1 1
=
6 −2 x2 0
x1 , x2 ≥ 0.

1.6.2 PLs ilimitadas


Exemplo 6. Considere a PL dada por
max cT x
sujeito a Ax = b
x≥0
onde  
  x1  
 3 −2 −1 30
c = −2 2 3 A= x = x2 
 b= .
1 0 −1 10
x3
Esta PL possui solução viável? E solução ótima?
Note que x1 = 20, x2 = 10, x3 = 10 é uma solução viável. Entretanto, qualquer solução
da forma    
20 1
S(t) = 10 + t 1
10 1
com t ≥ 0 também será viável. Note que

−2 2 3 · S(t) = 10 + 3t,
portanto se t → ∞, então cT · S(t) → ∞. Não há portanto um máximo para esta PL, e ela
é chamada de ilimitada.

O vetor d = 1 1 1 encontrado acima é um certificado de que a PL é ilimitada. Note
que este vetor satisfaz as propriedades de que Ad = 0, d ≥ 0 e cT d > 0.
Exercı́cio 18. Demonstre que a PL abaixo é viável, porém ilimitada.
 
 x1
max 1 −1 −3 x2 
x3
    
1 −2 5 x1 4
sujeito a 2 −4 0 x2  = −2 ,
0 0 1 x3 1
x1 , x2 , x3 ≥ 0

19
G. Coutinho e C. Arbex Valle DCC035 P.O.

1.6.3 PLs com soluções ótimas


Exemplo 7. Agora considere a PL

max −1 3 −5 2 1 · x
   
1 −2 1 0 2 2
sujeito a x=
0 1 −1 1 3 4
x ≥ 0.

Suponha que alguém lhe informe que z = 2 0 0 4 0 é uma solução ótima desta PL.
Como provar isto?
Certamente z é solução viável. Mas para mostrar que também é ótima, precisamos
mostrar que para qualquer outra solução viável x, temos

cT · x ≤ cT · z = 6.

Isto é verdade?
De fato, se x é viável, então
   
 1 −2 1 0 2  2
−1 2 · x = −1 2 ·
0 1 −1 1 3 4

Logo 
−1 4 −3 2 4 x = 6.
Com esta informação, conseguimos mostrar que:

cT z − cT x ≥ 0
6 − cT x ≥ 0

−1 4 −3 2 4 x − cT x ≥ 0

0 1 2 0 3 x≥0

Explique por quê esta última desigualdade é verdadeira.



O vetor −1 2 (que por enquanto apareceu como mágica) é um certificado de otima-
lidade da PL. É um vetor que satisfaz as seguintes propriedades: há uma solução viável z
(candidata a ótima), um vetor y tais que y T A ≥ cT , e y T b = cT z.

Exercı́cio 19. Coloque a PL abaixo em FPI, ache uma candidata a solução ótima, e exiba
um certificado de otimalidade.

max 1 1 ·x
   
2 1 2
sujeito a x≤
1 2 2
x ≥ 0.

20
G. Coutinho e C. Arbex Valle DCC035 P.O.

1.6.4 Resumo
Dada uma PL em FPI

max cT x
sujeito a Ax = b
x ≥ 0,

esta PL é

• inviável se existir um vetor y tal que

y T A ≥ 0 e y T b < 0.

• ilimitada se for viável e se existir um vetor d tal que

Ad = 0 , d ≥ 0 e cT d > 0.

• solúvel com solução ótima z se z for viável e existir um vetor y tal que

y T A ≥ cT e y T b = cT z.

21
Capı́tulo 2

Simplex

Aula 6
2.1 Começando a pensar no Simplex
Considere a seguinte PL


max 3 2 0 0 0 x
   
2 1 1 0 0 8
sujeito a 1 2 0 1 0 x = 8
1 1 0 0 1 5
x ≥ 0.

Claramente z = 1 1 5 5 3 é uma solução viável. É possı́vel melhorá-la? Qualquer
solução que aumente z1 ou z2 vai melhorar a solução da PL. Vamos então manter z2 fixo e
aumentar z1 , mas para isso teremos que diminuir z3 , z4 e z5 . Teremos

z(t) = 1 + t 1 5 − 2t 5 − t 3 − t
permanece sendo uma solução viável desde que 5 − 2t ≥ 0, 5 − t ≥ 0 e 3 − t ≥ 0. O maior
valor de t possı́vel é, portanto t = 5/2. Daı́

7/2 1 0 5/2 1/2
é uma nova solução que melhora a solução anterior.
Podemos agora repetir este processo para a variável z2 ? Como proceder?

2.2 Uma base de soluções viáveis


Dada uma PL em FPI
max cT x
sujeito a Ax = b
x ≥ 0,

22
G. Coutinho e C. Arbex Valle DCC035 P.O.

podemos sempre assumir que a matriz A está em um formato especial. O objetivo dos
exercı́cios dirigidos a seguir é descobrirmos que formato é este.

Exercı́cio 20. Considere a PL abaixo



max 1 2 3 x
   
4 −1 0 7
1 0 −1   
sujeito a  x = 2
1 1 1 3
2 −2 0 2
x ≥ 0.

É possı́vel escrever uma PL equivalente a esta em que a matriz A possua menos linhas?

Exercı́cio 21. Considere a PL abaixo



max 1 2 3 1 1 x
   
1 1 1 1 1 5
sujeito a 2 1 
0 −1 −2 x =  0
3 1 −1 −3 −5 −5
x ≥ 0.

Qual o posto dessa matriz? Ou seja, quantas colunas linearmente independentes existem?
É possı́vel reduzir o número de linhas?

Exercı́cio 22. Considere a PL abaixo



max 2 3 1 x
   
1 2 1 2
sujeito a 2 4 −1 x = 1
3 6 0 3
x≥0

Elimine linhas, se for possı́vel, e identifique colunas da matriz que formem uma matriz
quadrada não-singular.

Exercı́cio 23. Considere a seguinte PL em FPI

max cT x
sujeito a Ax = b
x ≥ 0.

Suponha que A possui m linhas linearmente independentes, e n colunas. Explique por que
podemos assumir, sem qualquer prejuı́zo à solução da PL, que se n ≥ m, há precisamente m
colunas linearmente independentes em A.

23
G. Coutinho e C. Arbex Valle DCC035 P.O.

Ao longo dos exercı́cios acima, vimos que sempre que uma PL estiver em FPI, podemos
assumir que existe uma escolha de colunas para a matriz A que formam uma base para
o espaço, ou seja, m colunas linearmente independentes onde m é o número de linhas da
matriz.
Toda vez que isso ocorrer, haverá uma única solução para o sistema de equações em que
as variáveis correspondentes às colunas fora da base são todas iguais a 0, e que portanto as
variáveis correspondentes às colunas da base serão as únicas possivelmente diferentes de 0.
Esta solução será chamada de solução básica correspondente à base de colunas escolhida.
Abaixo, explicamos este fato formalmente:

• Por exemplo, se essas colunas forem as primeiras n colunas, a matriz A estará na forma
abaixo
 
|
A= AB | AN  (2.1)
|

onde AB é uma matriz quadrada não singular, e AN é uma matriz cujas colunas são
combinações lineares das colunas de AB . Note que podem haver diferentes escolhas
para as matrizes AB e AN (elas podem estar intercaladas), sempre dependendo da
matriz original A.
Quando temos Ax, podemos separar as variáveis que compõem o vetor x entre aquelas
indexadas pelas colunas linearmente independentes e as outras. As variáveis de x que
correspondem às colunas de AB são chamadas de variáveis básicas, ao passo que as
demais são as variáveis não-básicas. Sempre podemos dividir o vetor x como
 
xB
x= ,
xN

onde o vetor xB possui as variáveis básicas, e xN as não-básicas. Note que, mesmo


que as matrizes AB e AN estejam originalmente intercaladas em A, vale a igualdade
abaixo:
Ax = AB xB + AN xN .
Exercı́cio 24. No exercı́cio 22, identifique as matrizes AB e AN , e os vetores xB e
xN . Calcule AB xB e AN xN separadamente, e mostre que Ax = AB xB + AN xN .

Dada uma matriz A no formato de (2.1), e vetores x e b tais que

Ax = b,

observe que b é uma combinação linear das colunas em AB . No caso, b é tratado como
uma coluna extra de A que pode ser escrita como uma combinação linear das colunas
básicas de A. Então, existe um vetor z tal que Az = b, e

AB z B = b e z N = 0.

Um vetor z como descrito acima é chamado de uma solução básica da PL.

24
G. Coutinho e C. Arbex Valle DCC035 P.O.

Exercı́cio 25. Novamente no exercı́cio 22, ache uma solução básica.

Note que uma vez escolhida a matriz AB , existe uma única solução básica associada
z, e ela é definida por z B = A−1
B b, e z N = 0, com
 
zB
z= .
zN

Voltamos agora ao exemplo do fim da aula 3:



max 3 1 0 0 0 x
   
2 1 1 0 0 8
sujeito a 1  
2 0 1 0 x = 8
1 1 0 0 1 5
x ≥ 0.

Note que as colunas 3, 4 e 5 desta PL formam uma base, e que nesta base, AB = I, e as
entradas correspondentes de c são 0.

Definição 2. Uma PL em FPI tal que a base canônica do espaço de colunas aparece intei-
ramente como colunas da matriz A, e tal que as entradas correspondentes a estas colunas no
vetor c são todas iguais a 0, é uma PL em forma canônica.
Ou seja, será tal que AB = I (a menos de trocar as colunas de lugar), e cB = 0.

25
G. Coutinho e C. Arbex Valle DCC035 P.O.

Aulas 7 e 8
2.3 Simplex
Quando uma PL está em forma canônica e há uma solução básica viável, sempre é possı́vel
(tentar) melhorar a solução da maneira como fizemos no exemplo! Portanto o problema
de achar a solução ótima de uma PL se reduz ao problema de colocar uma PL em forma
canônica para uma solução básica viável. O exemplo abaixo deverá ser esclarecedor.
Exemplo 8. Começamos com

max 3 2 0 0 0 x
   
2 1 1 0 0 8
sujeito a 1  
2 0 1 0 x = 8
1 1 0 0 1 5
x ≥ 0.

(i) Esta PL já está em forma canônica.


T
(ii) Achamos a solução básica - no caso, x = 0 0 8 8 5 , cujo valor associado na
função objetivo é 0. Ela é viável uma vez que todo o vetor x ≥ 0, e portanto prosse-
guimos.

(iii) Identificamos no vetor c uma entrada positiva. Uma entrada positiva i em c em um


problema de maximização implica que se xi correspondente fosse maior, o valor da
função objetivo também seria maior. Escolhemos então esta entrada em c, que corres-
ponde a uma coluna. No caso, escolhemos arbitrariamente a primeira (poderia ter sido
a segunda).

(iv) O próximo passo é alterar a solução aumentando o valor da variável x1 , deixando x2


fixo e reduzindo os valores das variáveis básicas x3 , x4 , x5 .
Quanto maior o valor de x1 , maior será o aumento do valor da função objetivo. Porém,
x1 não pode aumentar indefinidamente pois temos que garantir que as variáveis básicas
continuem com valores viáveis, isto é, continuem sendo não-negativas. Devemos então
descobrir qual é o máximo valor possı́vel de x1 de forma que estas condições sejam
satisfeitas.
Para cada restrição, encontramos o maior valor que x1 pode obter de forma que a
variável básica correspondente (aquela que possui coeficiente 1 na restrição i na PL em
forma canônica) seja no mı́nimo zero:

• Restrição 1: Ignorando os coeficientes das variáveis não básicas fixas, temos que
2x1 + x3 = 8. O maior valor possı́vel de x1 = 4, senão x3 teria que ser negativo.
Este valor é obtido ao dividir o valor de b1 pelo coeficiente A11 , 8/2.
• Restrição 2: Temos que x1 + x4 = 8, o maior valor possı́vel de x1 = 8.
• Restrição 3: Temos que x1 + x5 = 5, o maior valor possı́vel de x1 = 5.

26
G. Coutinho e C. Arbex Valle DCC035 P.O.

O máximo que podemos aumentar em x1 é o mı́nimo dos três valores acima, 4. Com
este incremento, obtemos a nova solução

x= 4 0 0 4 1 ,

cujo valor associado na função objetivo é cT x = 12 (maior que a anterior).


Em resumo: para encontrar o maior incremento possı́vel da variável x1 , que entrará
na base, devemos calcular o mı́nimo bi /Ai1 para toda restrição i. Após recalcular os
valores das variáveis básicas, temos que x3 = 0. Neste
 caso ela deixa
 de ser básica,
sendo substituı́da por x1 . Assim, xTB = x1 x4 x5 e xTN = x2 x3 .
Observação importante: pode ser que para uma restrição i o coeficiente Aij da
nova variável xj a entrar na base seja negativo, neste caso bi /Aij < 0. Isto significa
que a restrição i não limitaria o valor máximo que xj pode obter. Portanto, o maior
incremento possı́vel de xj deve ser o mı́nimo bi /Aij para toda restrição i tal que Aij > 0.

(v) O próximo passo é garantir que esta nova solução se torne uma solução básica viável
para uma PL em forma canônica equivalente à original. Logo devemos alterar a PL de
modo que

(a) as colunas 1, 4 e 5 correspondam a uma matriz identidade.


(b) a função objetivo seja 0 nas entradas 1, 4 e 5.

Para (a), fazemos eliminação Gaussiana. Teremos



max 3 2 0 0 0 x
   
1 1/2 1/2 0 0 4
sujeito a   
0 3/2 −1/2 1 0 x = 4
0 1/2 −1/2 0 1 1
x ≥ 0.

Para (b), subtraı́mos a função objetivo por 3 vezes a primeira equação. Como isto
altera o valor da função objetivo, compensamos adicionando 3 × 4 = 12. Portanto o
problema de otimização não se altera, e teremos

max 0 1/2 −3/2 0 0 x + 12
   
1 1/2 1/2 0 0 4
sujeito a  0 3/2 −1/2 1 0 x = 4
 
0 1/2 −1/2 0 1 1
x ≥ 0.

Note que a função objetivo não é mais linear, mas a adição de uma constante não afeta
em qualquer maneira o problema de otimização. De fato, a solução básica

x= 4 0 0 4 1

satisfaz as equações da PL e possui valor objetivo igual a 12.

27
G. Coutinho e C. Arbex Valle DCC035 P.O.

(vi) Repetimos os itens (iii) e (iv). Agora só faz sentido aumentar x2 pois é a única cujo valor
na função objetivo é positivo, ou seja, a única que poderia contribuir para melhorar a
solução final. Calculando os valores dos coeficientes bi /Ai2 :

• Restrição 1: b1 /A12 = 4
1/2
= 8.
• Restrição 2: b2 /A22 = 4
3/2
= 8/3.
• Restrição 3: b3 /A32 = 1
1/2
= 2.

O mı́nimo dentre os valores é 2, correspondente à restrição 3. Assim, a nova solução


será 
x 3 2 0 1 0 ,

cujo novo valor na função


 objetivo atualizada
 é 13. A variável x5 deixa de ser básica,
T T
assim, xB = x1 x2 x4 e xN = x3 x5 .

(vii) Repetimos o item (v) - faça o passo a passo como exercı́cio!



max 0 0 −1 0 −1 x + 13
   
1 0 1 0 −1 3
sujeito a  0 1 −1 0 
2 x = 2 
0 0 1 1 −3 1
x ≥ 0.

Note que a solução básica 


x= 3 2 0 1 0
satisfaz as equações da PL e possui valor objetivo igual a 13.

(viii) Repetimos (ou tentamos repetir) os itens (iii) e (iv). Note entretanto que não existe
variável que faça sentido aumentar em x tendo em vista o atual formato do vetor c.

(ix) A PL está resolvida. Este foi o método simplex.

Exercı́cio 26. Refaça este exemplo, mas na primeira vez que chegar ao passo (iii), comece
aumentando x2 , deixando x1 fixo. Daı́ pra frente, faça como achar melhor. Note que no
final, o valor de ótimo precisa ser o mesmo.

Algumas observações:

(i) Este método sempre resolverá uma PL. Nós entretanto não demonstraremos isto for-
malmente agora.

(ii) Geometricamente, cada iteração dos pontos (ii)-(iv) correspondem a: achar uma solução
na região viável, caminhar até uma face aumentando o valor da função objetivo, depois
achar o melhor caminho para caminhar pela face até a próxima face.

(iii) Na próxima seção, veremos uma maneira esquemática de repetirmos esses passos.

28
G. Coutinho e C. Arbex Valle DCC035 P.O.

Exercı́cio 27. Considere o sistema de equações abaixo


   
1 1 0 2 1 1 1 2
0 2 2 0 0 −2 1 x = 2
1 2 1 5 4 3 3 6
e os vetores

(a) 1 1 0 0 0 0 0

(b) 2 −1 2 0 1 0 0

(c) 1 0 1 0 1 0 0

(d) 0 0 1 1 0 0 0

(e) 0 1/2 0 0 1/2 0 1
Para cada um deles, decida se é uma solução básica ou não, e se for, se é viável (≥ 0) ou
não.
Exercı́cio 28. Considere a PL em FPI abaixo.

max 1 −2 0 1 3 x
   
1 −1 2 −1 0 1
sujeito a x=
2 0 1 −1 1 −1
x ≥ 0.

Construa PL equivalente em forma canônica para as bases formadas pelas colunas {1, 4} e
pelas colunas {3, 5}. A solução básica correspondente é viável?
Decida se esta PL é viável ou inviável. Se for viável, construa uma PL equivalente em
forma canônica cuja solução básica associada seja viável. Se for inviável, apresente um
certificado.

2.3.1 Como encontrar um certificado de ilimitada


Vamos ver agora como é possı́vel encontrar um certificado de que a PL é ilimitada. Considere
a PL abaixo:

max 5 3 0 0 1 ·x
   
−2 4 1 0 1 1
sujeito a x=
−3 7 0 1 1 3
x ≥ 0.

Esta PL está na forma canônica para as colunas 3 e 4. Vamos aplicar o método simplex do
Exemplo (8) para resolvê-la.
Escolhemos a coluna com ci mais positivo. No caso, a 1a coluna com c1 = 5. Note porém
que os dois coeficientes são negativos. Isso significa que x1 pode crescer infinitamente, pois

29
G. Coutinho e C. Arbex Valle DCC035 P.O.

para todo valor positivo de x1 é possı́vel aumentar também os valores de x3 e x4 para


que a PL continue positiva. Isto implica que sempre que todos os coeficientes da coluna
correspondente de uma variável candidata forem não-positivos (ou sejam negativos ou zero),
a PL é ilimitada.
O certificado de ilimitada é, no caso, um vetor d = (d1 , d2 , d3 , d4 , d5 ) que satisfaz três
condições: Ad = 0, d ≥ 0 e cT d > 0. A partir da PL em forma canônica, podemos facilmente
encontra-lo. Note que para que Ad = 0, temos que:

−2d1 + 4d2 + d3 + d5 = 0
−3d1 + 7d2 + d4 + d5 = 0

Vamos começar colocando d1 = 1, isto é, na coluna que entraria como variável básica,
colocamos o valor 1. As variáveis básicas originais são x3 e x4 . Vamos fixar d2 = d5 = 0 e
colocar valores em d3 e d4 que garantem as igualdades acima: no caso, d3 = 2 e d4 = 3. Temos
que d = 1 0 2 3 0 . Note que este vetor satisfaz as três condições: Ad = 0, d ≥ 0 e
cT d = 5 > 0, sendo um certificado de ilimitada. Como a PL está na forma canônica, apenas
cT d = c1 neste caso pois os demais cj = 0 para todas as outras variáveis básicas cujo valor
dj > 0.
Encontrar o certificado nestas condições é fácil: estando a PL em forma canônica, e
encontrando um ci positivo cuja coluna Ai correspondente é toda não-positiva, então para
encontrar o certificado d basta colocar di = 1, dj = 0 para toda variável j não básica e
dk = −ali para toda variável básica k com valor 1 na restrição l correspondente.
Observação: Note
 que se toda a coluna correspondente a x1 fosse 0, com c1 > 0,
d = 1 0 0 0 0 seria um certificado válido.

30
G. Coutinho e C. Arbex Valle DCC035 P.O.

2.4 O simplex via tableaus


Nesta seção mostraremos como aplicar o simplex de modo mais enxuto.
Considere a PL

max w = 2 3 0 0 0 x + 0
   
1 1 1 0 0 6
sujeito a  2 1 0 1 0 x = 10
−1 1 0 0 1 4
x ≥ 0.

onde a variável w representa o valor objetivo. Note que esta PL já se encontra em forma
canônica para a base viável formada pelas colunas 3, 4 e 5. Vamos reescrever as equações e
a função objetivo como um sistema:
 
  w  
1 −2 −3 0 0 0  x
  1
 0
0 1 1 1 0 0  x2   6
   =  .
0 2 1 0 1 0   x3 
 10
0 −1 1 0 0 1  x4  4
x5

Note que a primeira linha da matriz corresponde a w − 2x1 − 3x2 = 0, ou w = 2x1 + 3x2 , que
é o valor objetivo. Escrevemos agora a matriz aumentada deste sistema, distinguindo a linha
da variável w, que só está nos ajudando a escrever a função objetivo como uma igualdade
envolvendo as outras variáveis:
 
1 −2 −3 0 0 0 0
 0 1 1 1 0 0 6 
T1 =  0 2

1 0 1 0 10 
0 −1 1 0 0 1 4

No simplex, escolhemos uma entrada de c que seja positiva. Como a matriz T1 possui −cT
na primeira linha, faremos agora:
(1) Escolhemos uma coluna cuja primeira entrada seja negativa. Digamos a 2a coluna.

(2) Escolhemos agora uma linha da 2a à 4a tal que a razão entre os elementos da última
coluna e da 2a coluna seja o menor possı́vel. No caso, 3a linha.

(3) Daı́ transformamos a 2a coluna usando eliminação Gaussiana, de modo que apenas o
elemento na 3a linha e 2a coluna seja igual a 1, e o resto seja 0. Isso se chama “pivotear”o
elemento (3,2).
 
1 0 −2 0 1 0 10
 0 0 1/2 1 −1/2 0 1 
T2 =  0 1 1/2 0

1/2 0 5 
0 0 3/2 0 1/2 1 9

31
G. Coutinho e C. Arbex Valle DCC035 P.O.

Repetimos agora na 3a coluna, pivoteando o elemento (2,3).


 
1 0 0 4 −1 0 14
 0 0 1 2 −1 0 2 
T2 =  0 1 0 −1


1 0 4
0 0 0 −3 2 1 6

Repetimos agora na 5a coluna, pivoteando o elemento (4,5).


 
1 0 0 5/2 0 1/2 17
 0 0 1 1/2 0 1/2 5 
T3 = 
 0 1 0

1/2 0 −1/2 1 
0 0 0 −3/2 1 1/2 3

Não há mais elementos negativos na 1a linha, e de fato, a função objetivo agora é
5 1
w = 17 − x3 − x5 ,
2 2
cujo valor máximo, igual a 17, ocorre com x3 = x5 = 0, e corresponde à solução básica viável
T
x= 1 5 0 3 0 ,

que é facilmente observada em T3 (basta pensar que cada uma dessas variáveis é um peso
multiplicando a coluna correspondente.)

Exercı́cio 29. Considere a PL em FPI com


 
    0
1 2 −2 0 2 3
A= b= c= 
1 .
0 1 3 1 5
0

(a) Aplique o método simplex a esta PL iniciando com a base de colunas 1 e 4.

(b) Ache um certificado de que a PL é ótima ou ilimitada (se for ótima, no olho mesmo, por
enquanto).

Exercı́cio 30. Considere a PL em FPI dada por



2
     1
−2 1 1 1 0 0 1  
−1
A =  1 −1 0 0 1 0 b = 2
 c= 
 0 .
2 −3 −1 0 0 1 6  
 0
0

Resolva a PL usando o simplex.

32
G. Coutinho e C. Arbex Valle DCC035 P.O.

2.5 O problema de achar soluções viáveis - simplex fase


2
Exemplo 9. Considere a PL

max 1 2 −1 3 x
   
1 5 2 1 7
sujeito a x=
−2 −9 0 3 −13
x ≥ 0.

Queremos apenas decidir por ora se esta PL é viável ou inviável. O primeiro passo é tornar
b ≥ 0, já que desejamos eventualmente encontrar uma base de colunas na forma da matriz
identidade, e que a solução correspondente a esta base seja viável. Fazemos então

max 1 2 −1 3 x
   
1 5 2 1 7
sujeito a x=
2 9 0 −3 13
x ≥ 0.

Agora, poderı́amos testar todas as possı́vel 42 escolhas de duas colunas, até acharmos (ou
não) uma que corresponda a uma base viável. Mas vamos mostrar abaixo um método mais
eficiente! Este método usará uma nova PL para encontrar este par de colunas.
Construı́mos uma nova PL, chamada de auxiliar, em FPI, e que satisfaz a seguintes
propriedades:

(a) Possui uma solução viável óbvia.

(b) É limitada, e nenhuma solução ótima pode ter valor objetivo maior que 0.

(c) Uma solução ótima da nova PL de valor objetivo igual a 0 é uma solução viável da PL
original, e se o ótimo for menor que 0, a PL original é inviável.

Considere a PL aplicada a vetores x agora com 6 variáveis, ou seja, criamos duas variáveis
novas:

max 0 0 0 0 −1 −1 x
   
1 5 2 1 1 0 7
sujeito a x=
2 9 0 −3 0 1 13
x ≥ 0.

Pare por um momento para entender como esta PL foi obtida da original. Claramente

(a) x = 0 0 0 0 7 13 é solução viável para esta PL (note que aqui foi extremamente
importante que b ≥ 0). Esta solução é básica, mas usa apenas as variáveis novas, e
portanto sempre terá valor objetivo negativo (veja como o novo vetor c foi construı́do).

33
G. Coutinho e C. Arbex Valle DCC035 P.O.

(b) Esta PL é limitada e nenhuma solução desta PL pode ter valor objetivo maior que 0, já
que x ≥ 0 e o novo c é ≤ 0.
(c) Usando o simplex (faça como exercı́cio), descobriremos que

x= 2 1 0 0 0 0
é uma solução ótima para a PL auxiliar, e, portanto, como x5 = x6 = 0, esta solução
leva à solução viável da PL original.
T
x= 2 1 0 0

Exemplo 10. Considere agora a PL



max 6 1 −1 x
   
5 1 1 1
sujeito a x=
−1 1 2 5
x ≥ 0.
Novamente, fazemos

max 0 0 0 −1 −1 x
   
5 1 1 1 0 1
sujeito a x=
−1 1 2 0 1 5
x ≥ 0.
Esta PL é viável e limitada, e seu valor ótimo pode ser no máximo 0. Entretanto, ao
resolvermos esta PL, obteremos o ótimo
T
x= 0 0 1 0 3 ,
cujo valor objetivo é −3. Podemos então concluir que a PL original deste exemplo é inviável,
uma vez que qualquer solução viável para a PL original corresponderia a uma solução para
a PL auxiliar com valor objetivo 0. Como seu ótimo foi −3, esta solução não existe.
Ademais, um certificado de otimalidade desta PL para uma solução ótima x é um vetor
y tal que
(a) cT − y T A ≤ 0.
(b) y T b = cT x = −3, logo < 0.

Escolhendo y = 2 −1 teremos um certificado de otimalidade para a PL auxiliar, que é
ao mesmo tempo um certificado de inviabilidade para a PL original.
Resumindo: dada uma PL
max cT x
sujeito a Ax = b
x ≥ 0,

34
G. Coutinho e C. Arbex Valle DCC035 P.O.

onde A é m × n e b ≥ 0, então construı́mos a PL auxiliar



max 0 ···0 | −1 · · · −1 x

sujeito a A | I x=b
x ≥ 0,

onde há precisamente m (−1)s na função objetivo, e a matrix identidade ao lado de A é de


tamanho m × m. Esta PL auxiliar é viável, seu ótimo é no máximo 0. A solução básica
inicial usa as variáveis recém criadas. Rodamos então o simplex. Se seu ótimo é menor que
0, a PL original é inviável, e se seu ótimo for igual a 0, então qualquer vetor que atinja esse
ótimo corresponde a uma solução básica viável da PL original, e a partir dela, poderemos
então iniciar o simplex na PL original para achar seu ótimo.

Exercı́cio 31. A PL abaixo é viável ou inviável?



max 2 −1 2 x
   
−1 −2 1 −1
sujeito a x=
1 −1 1 3
x ≥ 0.

Exercı́cio 32. Suponha que uma dada PL seja inviável. Prove que um certificado de oti-
malidade para a PL auxiliar é também um certificado de inviabilidade para a PL original.

35
G. Coutinho e C. Arbex Valle DCC035 P.O.

2.6 Pseudo-código e sutilezas


Apenas para formalizar, segue o SIMPLEX em pseudo-código. Há também, em seguida,
alguns comentários sobre sutilezas e nuances do algoritmo.

Método Simplex
Input: Uma PL e uma base viável de colunas B.
Output: Uma solução ótima, ou um certificado de que a PL é ilimitada.
1: Reescreva a PL para a forma canônica com respeito à base B.
Seja x a solução básica viável associada.
2: Se cN ≤ 0, então pare. x é ótima.
3: Escolha um k ∈ N tal que ck > 0.
4: Se Ak ≤ 0, então pare. A PL é ilimitada.
5: Seja r o ı́ndice j tal que o mı́nimo abaixo ocorre:
bj
t = min : Ajk > 0 .
Ajk
6: Troque a r-ésima (na ordem da matriz identidade) coluna de B pela coluna k.
7: Volte para 1.

Este algoritmo passeia de solução básica em solução básica até encontrar a melhor. Cada
solução básica corresponde a precisamente um valor objetivo, e como há um número finito
de soluções básicas, se garantirmos que a cada rodada o algoritmo pára ou aumenta o valor
objetivo, então teremos que este algoritmo sempre termina.

Exercı́cio 33. Dada a PL

max cT x
sujeito a Ax ≤ b
x ≥ 0,

e um vetor y tal que y ≥ 0 e y T A ≥ cT , mostre que nenhuma solução da PL pode ter valor
objetivo maior que y T b.

Exercı́cio 34. Escreva um algoritmo baseado no simplex que resolve a PL

min cT x
sujeito a Ax = b
x≥0

sem precisar convertê-la para um problema de maximização.

2.6.1 Múltiplas soluções ótimas


Considere a PL abaixo:

36
G. Coutinho e C. Arbex Valle DCC035 P.O.

1
max x1 + x2
2
sujeito a 2x1 + x2 ≤ 4
x1 + 2x2 ≤ 3
x1 , x2 ≥ 0

Primeiro escrevemos esta PL em FPI:

1
max x1 + x2
2
sujeito a 2x1 + x2 + x3 = 4
x1 + 2x2 + x4 = 3
x1 , x2 , x3 , x4 ≥ 0

Agora, vamos resolve-la via Simplex. Iniciamos com a base xB = x3 , x4 :


 
1 −1 −1/2 0 0 0
 0 2 1 1 0 4 
0 1 2 0 1 3

A solução viável básica no caso é x = 0 0 4 3 com valor 0 na função objetivo. Esco-
lhemos x1 para entrar na base, com x3 saindo. O próximo tableau é dado por:
 
1 0 0 1/2 0 2
 0 1 1/2 1/2 0 2 
0 0 3/2 −1/2 1 1

A solução ótima é dada por x = 2 0 0 1 . Como não há elemento negativo na função
objetivo, encontramos a solução ótima. Porém, note que c2 = 0, isto é se aumentarmos o
valor de x2 e reduzirmos apropriadamente os valores de x1 e x4 , não alteraremos o valor da
função objetivo. Como exemplo, vamos entrar com x2 na base (no caso, x4 sai):
 
1 0 0 1/2 0 2
 0 1 0 2/3 −1/3 5/3 
0 0 1 −1/3 2/3 2/3

A solução x = 5/3 2/3 0 0 também é ótima. Note que no novo tableau, c4 = 0, o que
indica que podemos voltar com x4 à base no lugar de x2 e obter a mesma solução anterior.
Em resumo: caso encontremos a solução ótima e no tableau final o coeficiente de uma
variável não-básica seja zero, a entrada desta variável na base não pioraria o valor da função
objetivo. Porém, pode ser que esta variável não possa entrar na base (não há elemento válido
a ser pivoteado). Caso possa, a PL possui múltiplas soluções ótimas: não apenas as duas
soluções básicas, mas também todos os pontos no segmento que une estas duas soluções.
Exercı́cio 35. Como o problema acima no formato original possui apenas duas variáveis,
verifique graficamente a razão de existirem múltiplas soluções.

37
G. Coutinho e C. Arbex Valle DCC035 P.O.

2.6.2 Soluções degeneradas


Considere agora a seguinte PL:

max 2x1 + x2
sujeito a 3x1 + x2 ≤ 6
x1 − x2 ≤ 2
x2 ≤ 3
x1 , x2 ≥ 0
Vamos novamente resolve-la usando o Simplex. O primeiro tableau com ela já em FPI é
dado por:
 
1 −2 −1 0 0 0 0
 0 1 1 0 0 6 
 3  Base: x3 = 6, x4 = 2, x5 = 3
 0 1 −1 0 1 0 2  Fora da base: x1 = x2 = 0
0 0 1 0 0 1 3
Escolhemos x1 para entrar na base. Há um empate nas variáveis candidatas a sair da base
(x3 → 6/3 = 2 e x4 → 2/1 = 2). Escolhemos arbitrariamente a segunda restrição (terceira
linha do tableau). O segundo tableau é dado por:
 
1 0 −3 0 2 0 4
 0 0 4 1 −3 0 0 
  Base: x1 = 2, x3 = 0, x5 = 3
 0 1 −1 0 1 0 2  Fora da base: x2 = x4 = 0
0 0 1 0 0 1 3
Observe que esta solução básica possui uma variável básica igual a zero (x3 ). Quando isto
ocorre, dizemos que a solução básica é degenerada. Isto deve ser motivo de preocupação?
Vamos continuar com o Simplex. A variável x2 deve entrar na base, e a razão mı́nima é dada
pela primeira restrição (segunda linha da tabela): 0/4 = 0. Assim x3 sai da base:
 
1 0 0 3/4 −1/4 0 4
 0 0 1 1/4 −3/4 0 0 
  Base: x1 = 2, x2 = 0, x5 = 3
 0 1 0 1/4 1/4 0 2  Fora da base: x3 = x4 = 0
0 0 0 −1/4 3/4 1 3
Obtivemos quase que exatamente a mesma solução, com o mesmo valor e com apenas uma
troca em uma variável básica. Ainda há elemento negativo na função objetivo, então conti-
nuamos o processo. A variável x4 entra na base, enquanto que a variável x5 sai:
 
1 0 0 2/3 0 1/3 5
 0 0 1 1 3 
 0 0  Base: x1 = 1, x2 = 3, x4 = 4
 0 1 0 1/3 0 −1/3 1  Fora da base: x3 = x5 = 0
0 0 0 −1/3 1 4/3 4
A solução acima é ótima. Então, neste caso, a degeneração não impediu que o Simplex
encontrasse o ótimo, ela apenas atrasou um pouco até que isto acontecesse. Porém, é possı́vel

38
G. Coutinho e C. Arbex Valle DCC035 P.O.

criar exemplos em que a degeneração leva à ciclagem, isto é, uma sequência de pivôs que
repete periodicamente os mesmos tableaus e que continua indefinidamente, entrando em loop
infinito. Esta situação pode ser evitada pela seguinte regra:

Regra de Bland:

• Se para algum r ∈ B, br = 0, escolha a variável de menor ı́ndice dentre aquelas que


podem entrar na base (com custo negativo). Na hora de escolher a variável que vai
sair da base, em caso de empate escolha também a de menor ı́ndice.

Neste link (em inglês), é possı́vel ver um exemplo de uma situação em que a regra de Bland
evita a ciclagem.
Esta regra, apesar de garantir a não ocorrência da ciclagem, pode ser por vezes ineficiente.
Na prática, por mais que a degeneração seja relativamente comum, em solvers comerciais e
open-source nenhum esforço é dedicado a evitar a ciclagem, pois:

• Apesar da degeneração ser frequente, a ciclagem é extremamente rara.

• A precisão da aritmética computacional acaba cuidando da ciclagem por si só: erros


de arredondamento se acumulam e eventualmente o método sai da ciclagem.

Exercı́cio 36. De novo, como o problema acima possui apenas duas variáveis, interprete
graficamente a degeneração.

39
G. Coutinho e C. Arbex Valle DCC035 P.O.

Aula 9
2.7 Como achar certificados de ótimo e inviabilidade?
Considere uma PL em FPI
max cT x
sujeito a Ax = b
x≥0
Assuma por enquanto que ela tem ótimo, e que portanto o simplex encontrará este ótimo.
Se z é uma solução ótima, então y é certificado se
(a) y T A − cT ≥ 0
(b) y T b = cT z.
Ao resolvermos o simplex (usando o tableaux), começamos como na esquerda abaixo, e
eventualmente terminamos na direita
1 −cT 0 1 cT v.o.
7→
A b A b

Os vetores c, b e a matriz A foram obtidos após a realização de operações elementares de


linhas. Necessariamente cT ≥ 0.
• Imagine tenha havido apenas uma única rodada no simplex, resultando em solução z,
e que, por exemplo, o vetor c foi simplesmente −c somado à primeira
 linha da matriz
A. A primeira linha da matriz A é simplesmente 1 0 ... 0 · A. Daı́ teremos

cT = −c + 1 0 ... 0 A ≥ 0

• Se este tivesse sido o caso, o valor objetivo teria sido simplesmente 1 0 ... 0 · b =
cT z.

• Note então que este vetor 1 0 ... 0 que registrou apenas o quanto de A foi adici-
onado a −c teria sido nosso certificado de ótimo (veja que ele satisfaz (a) e (b)).
No geral, todas as operações nas linhas de A que eventualmente serão somadas ao −c
podem ser contempladas em um único vetor. Por exemplo, se A tivesse 3 linhas, e se
tivéssemos somado 2 vezes a 1a na 2a linha de A, e depois disso tivéssemos somado ao −c
2 vezes a 1a, -1 vezes a 2a, e 3 vezes a 3a, terı́amos

cT = 0 −1 3 A − cT ,
 
e como cT ≥ 0 e 0 −1 3 b é o valor objetivo, igual a cT z, terı́amos que 0 −1 3
seria o certificado de ótimo. Para resumir, o vetor que registra quais linhas de A foram
somadas a −c para obtermos ≥ 0 é precisamente o certificado de ótimo. Abaixo, veremos
como registrar isso de forma sistemática durante a execução do simplex. Para isso, vamos
alugar a parte esquerda da matriz, onde antes havia uma inútil coluna.

40
G. Coutinho e C. Arbex Valle DCC035 P.O.

Exemplo 11. Vamos resolver a PL:



max −1 3 1 2 x
   
1 2 −2 0 2
sujeito a x=
0 1 3 1 5
x ≥ 0.

Olhando para a matriz, vemos que já temos uma base viável de colunas, mas a PL não está
em forma canônica. Começaremos escrevendo o tableaux em sua nova versão — a versão
estendida de registro de operações (VERO™).

0 0 1 −3 −1 −2 0
1 0 1 2 −2 0 2
0 1 0 1 3 1 5

Começaremos zerando as entradas do vetor −c.

−1 2 0 −3 7 0 8
1 0 1 2 −2 0 2
0 1 0 1 3 1 5

Note que −1 2 registra precisamente que somamos ao −c −1 vezes a 1a linha de A, e 2
vezes a 2a. Agora SIMPLEX. Pivotearemos o 2 abaixo do −3.

−1 2 0 −3 7 0 8 1/2 2 3/2 0 4 0 11
1/2 0 1/2 1 −1 0 1 → 1/2 0 1/2 1 −1 0 1
0 1 0 1 3 1 5 −1/2 1 −1/2 0 4 1 4

Note que ao termos registrado que multiplicamos a 1a linha por 1/2 quando normalizamos
o 2 no primeiro tableaux, automaticamente pudemos saber que adicionamos 3 · (1/2) da 1a
linha original à linha do c. Enfim, chegamos ao ótimo. E agora temos:
T
z= 0 1 0 4 v.o. = cT z = 11

e o certificado de ótimo T
y = 1/2 2 .
De fato:   
y T A − cT = 1/2 3 5 2 − −1 3 1 2 = 3/20 4 0
que é exatamente o que aparece sobre o tableaux, assim como
 
T
 2
y b = 1/2 2 = 11.
5

O exemplo acima deve ter sido esclarecedor. Vamos ver agora o que aconteceria se
tivéssemos registrado as operações ao resolvermos uma PL auxiliar.

41
G. Coutinho e C. Arbex Valle DCC035 P.O.

Exemplo 12. Vamos resolver a PL:



max 6 −5 1 x
   
1 −3 7 −1
sujeito a x=
−1 5 −10 1
x ≥ 0.

Não está claro qual seria uma base viável. Logo, vamos para a PL auxiliar. A primeira
coisa que faremos é multiplicar a 1a linha por −1, e portanto já registraremos esta operação.
Depois montamos a PL auxiliar.

0 0 0 0 0 1 1 0 1 −1 2 −8 17 0 0 −2
−1 0 −1 3 −7 1 0 1 → −1 0 −1 3 −7 1 0 1
0 1 −1 5 −10 0 1 1 0 1 −1 5 −10 0 1 1

1 −1 2 −8 17 0 0 −2
−1 0 −1 3 −7 1 0 1 →
0 1/5 −1/5 1 −2 0 1/5 1/5
1 3/5 2/5 0 1 0 8/5 −2/5
−1 −3/5 −2/5 0 −1 1 −3/5 2/5
0 1/5 −1/5 1 2 0 1/5 1/5
Como o ótimo da PL auxiliar é negativo,
 a PL original é inviável. Mais importante que isso
T
neste momento, seja y = 1 3/5 , ou seja, o certificado de ótimo da PL auxiliar. Note que
 
T
 1 −3 7 
y A = 1 3/5 = 2/5 0 1 ,
−1 5 −10

exatamente o que aparece na linha de cima do tableaux, e que é ≥ 0 já que o tableaux está
em estado de ótimo. Ademais
 
T
 −1
y b = 1 3/5 = −2/5 < 0,
1

portanto y é um certificado de inviabilidade.


Ou seja, acabamos de ver na prática que o certificado de ótimo de uma PL auxiliar que
resultou num ótimo negativo é precisamente igual a um certificado de inviabilidade da PL
original!

A partir de agora, tente resolver todas as suas PLs com a VERO™.

42
G. Coutinho e C. Arbex Valle DCC035 P.O.

2.8 Método Simplex Dual


Suponha que você queira resolver a seguinte PL:

max −4 −8 −9 x
   
2 −1 5 1
(P) sujeito a  3 −4 
1 x≤  3
−1 0 −2 −8
x ≥ 0.
Ao escrevê-la em FPI, notaremos um fato inconveniente. A base de variáveis de folga
não será viável, pois a última entrada do vetor b é negativa. Isso significa que primeiro
precisaremos escrever a PL auxiliar para decidir se (P) é viável, e então eventualmente achar
uma base viável para então colocarmos (P) em forma canônica.
Em compensação, veja como ficaria o tableau.
 
0 0 0 4 8 9 0 0 0 0
 1 0 0 2 −1 5 1 0 0 1 
 
 0 1 0 3 −4 1 0 1 0 3 
0 0 1 −1 0 −2 0 0 1 −8
Adicionamos o registro de operações à esquerda que nos permite, ao final, obter um certifi-
cado de otimalidade (caso  a PL possua ótimo). No tableau, possuı́mos uma solução básica
x = 0 0 0 1 3 −8 que é inviável, pois x6 < 0.
Vamos agora fazer modificações do tipo pivoteamento, de modo que o c permaneça ≥ 0,
mas mudemos o sinal das entradas problemáticas de b. Olhamos então a última linha, onde
b é negativo, e selecionamos a entrada negativa que minimiza
ci
.
−A3,i

Teremos i = 1. Daı́ fazemos pivoteamento:


   
0 0 0 4 8 9 0 0 0 0 0 0 4 0 8 1 0 0 4 −32
 1 0 0 2 −1 5 1 0 0 1   1 0 2 0 −1 1 1 0 2 −15 
 → 
 0 1 0 3 −4 1 0 1 0 3   0 1 3 0 −4 −5 0 1 3 −21 
0 0 1 -1 0 −2 0 0 1 −8 0 0 −1 1 0 2 0 0 −1 8

Obtivemos outra solução básica inviável para o problema: x = 8 0 0 −15 −21 0 ,
mas note que o valor objetivo diminuiu. Vamos continuar o processo. Agora duas entradas
de b são negativas. Escolhemos a primeira, e na sua linha, há uma única entrada negativa,
no caso será na coluna i = 3. Teremos

   
0 0 4 0 8 1 0 0 4 −32 8 0 20 0 0 9 8 0 20 −152
 1 0 2 0 -1 1 1 0 
2 −15   −1 0 −2 0 1 −1 −1 0 −2 15 
 → 
 0 1 3 0 −4 −5 0 1 3 −21   −4 1 −5 0 0 −9 −4 1 −5 39 
0 0 −1 1 0 2 0 0 −1 8 0 0 −1 1 0 2 0 0 −1 8

43
G. Coutinho e C. Arbex Valle DCC035 P.O.

Note que agora b ≥ 0 e cT ≤ 0, o que faz com que a base das colunas 1, 2 e 5 seja não
apenas viável, mas também ótima! Em particular

x = 8 15 0

é ótimo para o problema, e note que no registro de operações realizadas à esquerda, obtivemos
um certificado de otimalidade:

y = 8 0 20
Como a PL original estava em forma canônica para a base das últimas três colunas
(variáveis de folga), as operações realizadas ao vetor c também registraram os mesmos valores
(poderı́amos ter economizado nas contas).
Resumindo, sabemos que B é uma base viável e ótima para uma PL se
(1) c ≤ 0 e cB = 0.
(2) b ≥ 0.
A filosofia do simplex (versão primal) é a seguinte:

(i) Encontra solução viável para a PL, ou seja, uma base satisfazendo (2) acima.
(ii) Modifica esta solução em direção a (1), mantendo (2) verdade.

A filosofia do simplex (versão dual) é a seguinte:

(i) Encontra solução satisfazendo (1).


(ii) Modifica esta solução em direção a (2), mantendo (1).

No simplex dual, utilizamos o tableau para caminhar entre soluções básicas inviáveis mas
que, em certo sentido, já apontam na direção ótima, até que cheguemos em uma solução
básica viável. Veremos mais à frente que há uma programação linear dual de cada PL, e que
se ambas possuem ótimos, esses ótimos são iguais. Ademais, o certificado de ótimo de uma
PL é a solução ótima da sua dual, e o que o método simplex dual faz nada mais é do que
começar com uma solução básica viável para a programação linear dual e ir melhorando ela,
mantendo a viabilidade.
Exercı́cio 37. Resolva a PL

min 2 3 4 5 x
   
1 −1 1 −1 10
sujeito a 1 
−2 3 −4 x ≥  6
3 −4 5 −6 15
x ≥ 0.

Note que ao colocá-la em FPI, teremos uma situação perfeita para aplicar o método simplex
dual.

44
G. Coutinho e C. Arbex Valle DCC035 P.O.

Exercı́cio 38. Resolva a PL



max 5 4 3 x
   
2 3 1 5
sujeito a 4 1 2 x ≤ 11
3 4 2 8
x ≥ 0,

usando o método simplex primal.


Uma vez que sua solução esteja pronta, suponha que você receba uma nova restrição
adicional: 
1 1 1 x ≤ 1.
Qual a maneira mais eficiente de aproveitar a sua solução antiga para achar uma solução
para a nova PL?

Exercı́cio 39. Faça o mesmo no exercı́cio 37. Suponha que após resolver a PL, o cliente
chega e lhe diz que esqueceu a restrição mais importante, que é

x1 + 2x2 + 3x3 − 4x4 ≤ 8.

Resolva a nova PL.

45
Capı́tulo 3

Dualidade

Aulas 10 e 11
3.1 Dualidade
Nesta seção, estudaremos um importantı́ssimo aspecto das programações lineares. Descobri-
remos que para toda programação linear, poderemos definir uma outra, intimamente rela-
cionada, chamada de programação dual (motivo pelo qual a PL original é costumeiramente
chamada de primal).
Considere a PL:

max 7x1 + 5x2 + 6x3


sujeito a 2x1 + x2 + x3 ≤ 2
x1 + 2x2 + 3x3 ≤ 2
x1 , x2 , x3 ≥ 0.

Note que ao multiplicarmos a primeira restrição por 3 e somarmos à segunda, obtemos

7x1 + 5x2 + 6x3 ≤ 8.

Ou seja, a função objetivo não pode ser maior do que 8. Sendo assim, caso o sistema abaixo
possua alguma solução:

2x1 + x2 + x3 = 2
x1 + 2x2 + 3x3 = 2
x1 , x2 , x3 ≥ 0

encontraremos uma solução ótima. Por exemplo, no caso, x1 = x2 = 2/3, x3 = 0.


Nem sempre entretanto é possı́vel expressar a função objetivo como combinação das

46
G. Coutinho e C. Arbex Valle DCC035 P.O.

restrições. Por exemplo


max 4x1 + 5x2 + 6x3
sujeito a 2x1 + x2 + x3 ≤ 3
x1 + 2x2 + 3x3 ≤ 2
x1 , x2 , x3 ≥ 0.
Não podemos expressar a função objetivo como uma combinação das inequações (por que?),
mas suponha que existam y1 , y2 ≥ 0 que, quando multiplicados às restrições do problema:
max 4x1 + 5x2 + 6x3
sujeito a (2x1 + x2 + x3 )y1 ≤ 3y1
(x1 + 2x2 + 3x3 )y2 ≤ 2y2
x1 , x2 , x3 ≥ 0.
nos garanta que:
4x1 + 5x2 + 6x3 ≤ y1 (2x1 + x2 + x3 ) + y2 (x1 + 2x2 + 3x3 ).
Então saberemos que 4x1 + 5x2 + 6x3 ≤ 3y1 + 2y2 .
Por exemplo, para y1 = 6 e y2 = 0, teremos
4x1 + 5x2 + 6x3 ≤ 12x1 + 6x2 + 6x3 ≤ 18,
já que x1 , x2 , x3 ≥ 0 e os coeficientes são não-negativos.
Com y1 = 0 e y2 = 4, temos
4x1 + 5x2 + 6x3 ≤ 4x1 + 8x2 + 12x3 ≤ 8.
Com y1 = 1 e y2 = 2, temos
4x1 + 5x2 + 6x3 ≤ 4x1 + 5x2 + 7x3 ≤ 7.

Uma boa escolha de y1 e y2 nos fornece um limite superior ao valor que a solução ótima
do problema pode obter. Naturalmente, gostarı́amos de encontrar o menor limite superior
possı́vel. É mais valioso dizer que a solução ótima do problema é ≤ 7 que ≤ 18, por exemplo.
Procuramos então y1 e y2 , não-negativos, tais que 3y1 + 2y2 seja o menor possı́vel, e ainda
assim tenhamos 2y1 + y2 ≥ 4, y1 + 2y2 ≥ 5, e y1 + 3y3 ≥ 6. Parece familiar?
Exercı́cio 40. Escreva uma programação linear cuja otimização busca limitar os valores
objetivos da PL

max 1 1 1 x
   
1 1 2 4
sujeito a x≤
2 1 1 4
x ≥ 0.
Otimize ambas.

47
G. Coutinho e C. Arbex Valle DCC035 P.O.

3.2 A PL dual
Considere uma PL, que chamamos de primal, dada por
max cT x
(P) sujeito a Ax ≤ b
x ≥ 0.
Como vimos na seção anterior, é possı́vel escrever uma PL, doravante chamada de dual, em
que
cada restrição da primal corresponde a uma variável da dual.
Será um problema de minimização. O valor objetivo será calculado em termos de b. O vetor
c é o limite inferior das restrições. E tudo ainda precisa ser não-negativo. Ou seja

min bT y
(D) sujeito a y T A ≥ cT (ou equivalentemente AT y ≥ c)
y ≥ 0.

Note que este formato é especı́fico para uma PL que esteja exatamente no formato de
(P ) acima. Como fazer por exemplo se a PL (P ) estiver em FPI?
Originalmente, no exemplo acima, tı́nhamos 2x1 + x2 + x3 ≤ 3. Ao multiplicarmos ambos
os lados por y1 , precisamos que y1 ≥ 0 para que o sinal da desigualdade não se invertesse.
Se contudo tivéssemos 2x1 + x2 + x3 = 3, então y1 poderia ter sido qualquer número e a
igualdade não se alteraria. Temos portanto a seguinte formulação de dualidade para uma
PL em FPI:
max cT x min bT y
(P) sujeito a Ax = b (D) sujeito a AT y ≥ c
x≥0 y livre.
Mais geralmente, temos a seguinte tabela que nos ensina como construir a dual de uma
PL qualquer:
Primal Dual
restrição ≤ variável ≥ 0
max T
c x restrição = variável livre min bT y
sujeita a restrição ≥ variável ≤ 0 sujeita a
Ax ? b variável ≥ 0 restrição ≥ AT y ? c
x? 0 variável livre restrição = y? 0
variável ≤ 0 restrição ≤

Esta tabela é um bom guia, mas é mais eficiente que você...

(i) entenda a lógica da dualidade,

(ii) converta a primal para a FPI ou para o formato de (P) acima,

48
G. Coutinho e C. Arbex Valle DCC035 P.O.

(iii) memorize a dual desses formatos.

Exercı́cio 41. Considere a programação linear



max 3 2 x
   
2 1 8
(P) sujeito a 1 2 x ≤ 8
1 1 5
x ≥ 0.

(i) Escreva em FPI.

(ii) Escreva a dual.

(iii) Escreva a dual em FPI.

(iv) Escreva a dual da dual, e a coloque em FPI. O que aconteceu?

(v) Ache soluções viáveis para a primal (P) e a sua dual (D).

(vi) Verifique que o valor objetivo da solução viável da primal é menor ou igual que o valor
objetivo da solução viável da dual.

(vii) Calcule o valor ótimo de cada PL.

Faça o mesmo para a PL



max 2 3 x
   
1 1 6
(P) sujeito a  2 1 x ≤ 10
−1 1 4
x ≥ 0.
Exercı́cio 42. Usando a tabela acima, mostre que a dual da dual é sempre igual a primal.

3.3 Teorema fraco da Dualidade


Como vimos, a dual é construı́da de modo que seu valor objetivo seja sempre um limi-
tante superior para o valor objetivo da primal. Formalizamos isso no teorema abaixo, onde
assumimos que a primal está escrita em FPI.

Teorema 1 (Teorema fraco da dualidade). Sejam (P ) e (D) um par primal-dual de pro-


gramações lineares, (P ) em formato FPI, e seja x e y soluções viáveis para (P ) e (D),
respectivamente. Então:

(i) cT x ≤ bT y.

(ii) Se cT x = bT y, então x é solução ótima para (P ), e y é solução ótima para (D).

49
G. Coutinho e C. Arbex Valle DCC035 P.O.

Demonstração.

(i) Já que x é viável para (P ), segue que

y T Ax = y T b.

Já que y é viável em (D), ou seja, y T A ≥ cT , segue que, para todo x ≥ 0,

y T Ax ≥ cT x.

Temos portanto
bT y = xT Ay ≥ cT x.

(ii) É uma consequência imediata do item (i).

Note que este teorema ainda não está dizendo que se ambas as PLs tem ótimos,
então estes ótimos são iguais. Isso de fato é verdade, e veremos logo mais, reforçando
ainda mais o motivo pelo qual definimos duais como tal. Contudo, por enquanto, a única
coisa que sabemos é que se a primal e a dual possuı́rem soluções viáveis de mesmo valor
objetivo, então essas soluções são respectivos ótimos de cada PL. Note aqui que uma solução
da dual com mesmo valor objetivo que uma solução da primal é exatamente o que estávamos
chamando de certificado de otimalidade.

Corolário 2. Seja (P ) e (D) um par primal-dual de PLs.

(i) Se (P ) é ilimitada, então (D) é inviável.

(ii) Se (D) é ilimitada, então (P ) é inviável.

(iii) Se (P ) e (D) são viáveis, então ambas são limitadas.

Exercı́cio 43. Considere a PL



max 3 2 4 x
   
1 1 2 5
sujeito a 2 0 3 x ≤ 4
2 1 3 7
x ≥ 0.

(i) Ache o ótimo.

(ii) Ache um certificado de otimalidade (ou seja, um vetor y tal que cT ≤ y T A e y T b =


cT z, onde z é ótimo).

(iii) Escreva a dual.

50
G. Coutinho e C. Arbex Valle DCC035 P.O.

(iv) Ache o ótimo da dual sem realizar o simplex novamente.


Exercı́cio 44. Escreva a dual da PL abaixo

max 1 3 −1 x
   
2 2 −1 10
sujeito a 3 −2  
1 x ≤ 10
1 −3 1 10
x ≥ 0.

Mostre que a dual é inviável de duas formas diferentes:


(i) Mostrando que a primal é ilimitada.
(ii) Usando uma PL auxiliar.
Considere novamente a PL primal:

max 3 2 x
   
2 1 8
(P) sujeito a 1 2 x ≤ 8
1 1 5
x ≥ 0.

Ao resolva-la com o Simplex a partir da base inicial x3 , x4 e x5 e pivoteando inicialmente


na primeira coluna, obtemos a seguinte sequência de tableaus:
 
0 0 0 −3 −2 0 0 0 0
 1 0 0 2 1 1 0 0 8 
 
 0 1 0 1 2 0 1 0 8 
0 0 1 1 1 0 0 1 5
 
3/2 0 0 0 −1/2 3/2 0 0 12
 1/2 0 0 1 1/2 1/2 0 0 4 
 
 −1/2 1 0 0 3/2 −1/2 1 0 4 
 
−1/2 0 1 0 1/2 −1/2 0 1 1
 
1 0 1 0 0 1 0 1 13
 1 0 −1 1 0 1 0 −1 3 
 
 1 1 −3 0 0 1 1 −3 1 
−1 0 2 0 1 −1 0 2 2

O valor objetivo ótimo da primal é 13 e a solução ótima x = 3 2 0 1 0 . Desta
forma, a base viável ótima é formada pelas colunas 1, 4 e 2. A ordem x1 , x4 , x2 indica quais
variáveis são definidas pelas primeira, segunda e terceira restrições respectivamente.
Agora suponha que alguém lhe dissesse de antemão que esta base inicial (x1 , x4 e x2 ) era
válida e viável, e que te recomendasse começar o tableau a partir dela. Partimos do tableau
inicial:

51
G. Coutinho e C. Arbex Valle DCC035 P.O.

 
0 0 0 −3 −2 0 0 0 0
 1 0 0 2 1 1 0 0 8 
 
 0 1 0 1 2 0 1 0 8 
0 0 1 1 1 0 0 1 5
A quarta coluna (a segunda da base) já está em forma canônica. Faremos o processo na 1a
coluna, pivoteando o elemento relativo à primeira restrição, e na 2a coluna, pivoteando o
elemento relativo à 3a restrição:
 
3/2 0 0 0 −1/2 3/2 0 0 12
 1/2 0 0 1 1/2 1/2 0 0 4 
 
 −1/2 1 0 0 3/2 −1/2 1 0 4 
−1/2 0 1 0 1/2 −1/2 0 1 1
 
1 0 1 0 0 1 0 1 13
 1 0 −1 1 0 1 0 −1 3 
 
 1 1 −3 0 0 1 1 −3 1 
−1 0 2 0 1 −1 0 2 2
Obtivemos o mesmo tableau final que quando começamos o simplex a partir da base (x3 , x4 , x5 ).
Isto não é coincidência, pois não importa a ordem das operações, ao final só haverá um ta-
bleau possı́vel para uma certa base. Suponha sem perda de generalidade que tivéssemos
reorganizado as colunas da matriz A na ordem (1, 4, 2, 3, 5), reorganizando também acima o
vetor cT . Neste caso, podemos dividir a matriz A em AB representando a base e AN com as
colunas das variáveis que não são parte da base. O tableau inicial ficaria da seguinte forma:
0 −cTB −cTN 0

I AB AN b

Ao colocar o tableau na forma canônica, estamos obtendo uma matriz identidade no lugar
de AB . Se vocês se lembram bem de Álgebra Linear, A−1 B AB = I. Isto implica também
que na matriz original identidade à esquerda, obteremos a inversa da base A−1
B . Fazendo as
mesmas operações nas demais colunas, obtemos o tableau temporário, ainda não totalmente
na forma canônica:
0 −cTB −cTN 0

A−1
B A−1
B AB = I A−1
B AN A−1
B b

Para completar a forma canônica, precisamos zerar cTB . Para isso, multiplicamos A−1 B AB
por cTB e somamos em −cTB . Claro, repetimos as operações nas outras partes do tableau:
cTB A−1
B cTB A−1 T
B AB − c B = 0 cTB A−1 T
B AN − c N cTB A−1
B b

A−1
B A−1
B AB = I A−1
B AN A−1
B b

52
G. Coutinho e C. Arbex Valle DCC035 P.O.

Juntando novamente as matrizes AB e AN em uma matriz única A:

cTB A−1
B cTB A−1
B A−c
T
cTB A−1
B b

A−1
B A−1
B A A−1
B b

Se a base escolhida é a base ótima, teremos que (como o tableau é invertido) que
cTB A−1
B A − c
T
≥ 0, onde os termos relativos à base são precisamente iguais a zero. O
valor ótimo do problema é dado por cTB A−1
B b.

3.4 Teorema Forte da Dualidade


Como já vimos em exemplos acima, quando as PLs em um par primal-dual são viáveis
e limitadas, os valores ótimos podem ser, de fato iguais. Os exemplos não foram uma
coincidência. Este fato é particularmente relevante, tanto de um ponto de vista prático
como teórico.

Teorema 3. Sejam (P ) e (D) um par primal-dual de PLs, e suponha que (P ) está em FPI.
Se existe uma solução ótima para (P ), então existe uma solução ótima para (D), e, ademais,
o valor objetivo ótimo de (P ) e (D) é igual.

Demonstração. Temos
max cT x
min bT y
(P) sujeito a Ax = b (D)
sujeito a AT y ≥ c
x≥0

Sabemos que existe uma solução ótima para (P ) que é básica. Seja z uma solução ótima
básica de (P ) para uma base B. Aplicamos uma rodada do simplex, e obteremos uma PL
em forma canônica. Como vimos anteriormente, esta PL é obtida multiplicando Ax = b por
A−1
B , e usando os coeficientes de cB para somar as linhas da nova matriz de modo que cB se
torne 0 e cN se torne não-positivo (agora, sem o tableau invertido). Ou seja

cT − cTB A−1
B A ≤ 0,

de modo que
(cT − cTB A−1
B A)z = 0.

Como Az = b, segue que o valor ótimo é precisamente

cTB A−1 T −1
B Az = cB AB b.

Considere y T = cTB A−1


B . Vamos mostrar que y é solução viável para (D) com mesmo
valor objetivo que z em (P ).

(i) Como cT − cTB A−1 T T T


B A ≤ 0, segue que c − y A ≤ 0, logo A y ≥ c. Logo y é viável.

53
G. Coutinho e C. Arbex Valle DCC035 P.O.

(ii) Como cTB A−1 T


B b = y b, segue que o valor objetivo de y em (D) é igual ao valor objetivo
de z em (P ).

Pelo teorema fraco da dualidade, segue que o ótimo de (D) não pode ser menor que o
ótimo de (P ), e portanto eles tem que ser iguais.

Exercı́cio 45. Considere o par a seguir de PLs:



max −3 α 13 x
   
4 2 2 ≤ β
(P) sujeito a  1 2 −1 x ≤  5
−1 3 3 = 5
x≥0

min β 5 5 y
   
4 1 −1 −3
(D) sujeito a  2 2 
3 y≥  α
2 −1 3 13
y1 , y2 ≥ 0
 
Existe α e β tais que x = 1 2 0 e y = 0 2 5 são respectivos ótimos? Se sim, ache.
Se não, explique.

Exercı́cio 46. Considere a PL



min 1 α 10 25/2 x
   
1 0 5 6 ≥ 1
sujeito a x
2 6 0 1 ≤ 2
x1 ≥ 0, x2 ≤ 0, x3 livre, x4 ≥ 0.

Escreva a dual, e determine para quais valores de α a solução 1 0 0 0 é ótima para
a PL acima.

3.5 PLs inviáveis ou ilimitadas


Nós sabemos que toda PL satisfaz uma das três possibilidades abaixo:

(i) É inviável.

(ii) É viável e ilimitada.

(iii) É viável e limitada, e possui uma solução ótima.

Nós agora podemos relacionar essas possibilidades para um par primal-dual de PLs.

Corolário 4. Sejam (P ) e (D) um par primal-dual de PLs. Há precisamente quatro casos:

54
G. Coutinho e C. Arbex Valle DCC035 P.O.

(i) Ambas são inviáveis.

(ii) (P ) é viável e ilimitada, e então (D) é inviável.

(iii) (D) é viável e ilimitada, e então (P ) é inviável.

(iv) Ambas são viáveis, e então ambas possuem soluções ótimas.

Demonstração. Consequência direta do fato que toda solução da primal é um limitante


para a dual e vice-versa, e que se uma PL possui ótimo, então sua dual também possui.

Exercı́cio 47. Considere as quatro PLs primais abaixo, e as quatro PLs duais em seguida.
Associe os pares corretamente, e em seguida decida qual caso do corolário acima se aplica a
cada par. Apresente certificados.
max 2x1 + x2 max 2x1 + x2
sujeito a x1 + x2 ≤ 4 sujeito a x1 − x2 ≤ 4
x1 − x 2 ≤ 2 x1 − x2 ≤ 2
x1 , x2 ≥ 0 x1 , x2 ≥ 0

max 2x1 + x2 max 2x1 + x2


sujeito a x1 + x2 ≥ 4 sujeito a x1 − x2 ≥ 4
x1 + x2 ≤ 2 x1 − x2 ≤ 2
x1 , x2 ≥ 0 x1 , x2 ≥ 0

min − 4y1 + 2y2 min 4y1 + 2y2


sujeito a y1 − y2 ≤ −2 sujeito a y1 + y2 ≥ 2
y1 − y2 ≤ −1 y1 − y2 ≥ 1
y1 , y2 ≥ 0 y1 , y2 ≥ 0

min − 4y1 + 2y2 min 4y1 + 2y2


sujeito a − y1 + y2 ≥ 2 sujeito a y1 + y2 ≥ 2
y1 − y2 ≥ 1 − y1 − y2 ≥ −1
y1 , y2 ≥ 0 y1 , y2 ≥ 0

Exercı́cio 48. Considere a PL

max a1 x1 + a2 x2
   
1 −3 −2
sujeito a x≥
−1 3 3
x livre.

55
G. Coutinho e C. Arbex Valle DCC035 P.O.

(i) Mostre que é inviável.

(ii) Escreva sua dual.

(iii) Ache todos os valores de a1 e a2 tais que a dual seja (1) viável (2) inviável (3) viável e
ilimitada.

(iv) A dual pode ser viável e limitada?

3.6 Folgas complementares


Considere a programação linear
max cT x
(P) sujeito a Ax ≤ b
x ≥ 0.
cuja dual é
min bT y
(D) sujeito a AT y ≥ c
y ≥ 0.
Suponha que adicionemos a (P ) variáveis que representem as diferenças de Ax para b. Ou
seja, as folgas. Seja u o vetor que contém tais variáveis. Teremos então
max cT x
(P) sujeito a Ax + u = b
x, u ≥ 0.
Sejam agora x e y soluções viáveis para o par primal-dual, e u as variáveis de folga corres-
pondentes a x. Segue que

y T b = y T (Ax + u)
= (y T A)x + y T u
≥ cT x + y T u.

Esta última desigualdade segue do fato que x ≥ 0 e y T A ≥ cT .


Suponha agora que x e y fossem soluções ótimas. Então pelo Teorema Forte da Duali-
dade, temos y T b = cT x. Logo
y T u ≤ 0.
Como ambos os vetores são não-negativos, isso só é possı́vel se, para cada ı́ndice i, ou y i = 0
ou ui = 0. Toda essa análise serve também para o dual, e independe da forma em que a PL
é apresentada.
Soluções viáveis x e y para um par primal-dual de PLs (P ) e (D) satisfazem as condições
das folgas complementares se

56
G. Coutinho e C. Arbex Valle DCC035 P.O.

• Ou xj = 0, ou a j-ésima restrição de (D) é satisfeita com igualdade.

• Ou y i = 0, ou a i-ésima restrição de (P ) é satisfeita com igualdade.

Vimos que se x e y são ótimas, essas condições são satisfeitas. O converso também é
verdadeiro, ou seja...

Teorema 5 (Teorema das Folgas Complementares). Dado um par primal-dual (P ) e (D)


de PLs, e soluções viáveis x e y, então x e y são ótimas se, e somente se, as condições de
folgas complementares são satisfeitas.

Exercı́cio 49. Considere o seguinte par primal-dual


 min2 4 −1 y
max 5 3 5 x    
    1 3 −1 5
(P) 1 2 −1 2 (D) sujeito a  2 1 1 y = 3
 
sujeito a  3 1 
2 x≤  4 −1 2 1 5
−1 1 1 −1
y≥0
 
Prove que x = 1 −1 1 e y = 0 2 1 são soluções ótimas de duas maneiras diferen-
tes. Uma usando o Teorema Fraco da Dualidade, e a outra usando o Teorema das Folgas
Complementares.
Faça o mesmo para o par

 
max 12 26 20 x min −1 2 13 y
       
1 2 1 ≤ −1 1 4 2 ≥ 12
(P) sujeito a 4 6 5 x ≤  2 (D) sujeito a 2 6 −1 y = 36
2 −1 −3 = 13 1 5 −3 ≥ 20
x1 , x3 ≥ 0 y1 , y2 ≥ 0,
 
com as soluções x = 5 −3 0 e y = 0 4 −2 .

Exercı́cio 50. Prove que a PL

max cT x
sujeito a Ax = b

possui solução ótima se, e somente se, existe uma combinação linear das linhas de A que é
igual a c.

57
G. Coutinho e C. Arbex Valle DCC035 P.O.

Aula 12
3.7 Análise de sensibilidade
Com tudo o que já vimos até agora, podemos compreender como alterações realizadas a
posteriori na formulação da PL afetam a solução ótima encontrada para o problema original.
Para isso, será sempre útil ter a matriz que codifica as operações realizadas pelo simplex para
achar a base viável ótima. Como referência, vimos antes que, dada uma base B qualquer, o
tableau estendido final obtido para aquela base é dado por:

cTB A−1
B cTB A−1
B A−c
T
cTB A−1
B b

A−1
B A−1
B A A−1
B b

Vamos agora estudar como alterações a posteriori alteram a solução ótima de uma PL.
Observe o seguinte exemplo.


max 1 1 x
   
1 0 3
sujeito a x≤
2 3 24
x ≥ 0.

que possui o seguinte tableau inicial:


 
0 0 −1 −1 0 0 0
 1 0 1 0 1 0 3 
0 1 2 3 0 1 24
Este caso está apropriado para o método simplex primal. Procedemos:
 
1 0 0 −1 1 0 3
 1 0 1 0 1 0 3 
−2 1 0 3 −2 1 18
 
1/3 1/3 0 0 1/3 1/3 9
 1 0 1 0 1 0 3 
−2/3 1/3 0 1 −2/3 1/3 6
O que aprendemos com isso? Várias coisas:

(i) A base viável ótima é formada por colunas 1 e 2. Isolando essas colunas, podemos
calcular....

58
G. Coutinho e C. Arbex Valle DCC035 P.O.

(ii) ... a solução ótima, que é tal que


   
1 0 3
x= ,
0 1 6

ou seja, xT = 3 6 .
(iii) O valor objetivo é 9.
(iv) Também calculamos a solução ótima da dual, que
 está em cima, ao lado esquerdo da
T
barra tripla. De fato, note que y = 1/3 1/3 é uma solução viável para a PL dual

min 3 24 y
 
1 2 
(D) sujeito a y≥ 1 1
0 3
y ≥ 0,
com valor objetivo igual a 9.
(v) Note que as condições de folga complementares são satisfeitas (e não poderia ser di-
ferente). Ambas as soluções não possuem entradas iguais a 0, mas ambas satisfazem
suas restrições com igualdade.
(vi) A matriz 2 × 2 ao lado esquerdo da barra tripla codifica as operações realizadas na PL.
Como vimos anteriormente, ela nada mais é do que a inversa da matriz formada pelas
colunas 1 e 2 originais. De fato, note que:
    
1 0 1 0 1 0 1 0 1 0
= ,
−2/3 1/3 2 3 0 1 0 1 −2/3 1/3
e que     
1 0 3 3
= .
−2/3 1/3 24 6
Este último ponto é extremamente relevante. Suponha que ao término desta resolução, seu
cliente lhe informe que na verdade houve um erro, e que as restrições deveriam ter sido
x1 ≤ 3 e 2x1 + 3x2 ≤ 18.
Você então pensa da seguinte forma. “Se eu tivesse realizado as mesmas operações com este
vetor, eu teria obtido”     
1 0 3 3
= .
−2/3 1/3 18 4
Ou seja, o tableau final seria
 
1/3 1/3 0 0 1/3 1/3 ?
 1 0 1 0 1 0 3 .
−2/3 1/3 0 1 −2/3 1/3 4
Este tableau corresponde a uma solução básica e viável,
 já que b ≥ 0, e ótima, já que está
na forma canônica com c ≤ 0. Ou seja, x = 3 4 é ótima, com valor objetivo cT x = 7.
T

Note que o ótimo do dual não se alterou.

59
G. Coutinho e C. Arbex Valle DCC035 P.O.


Exercı́cio 51. Determine o menor valor w para que, se bT = 3 w , a base de colunas 1 e
2 permaneça viável e ótima.

Exercı́cio 52. Como resolver agora se bT = 2 3 ? Dica: use o simplex dual.

Exercı́cio 53. Resolva a PL



max 3 2 x
   
1 0 4
2 1  
sujeito a  x ≤ 11 .
1 1  9
4 1 17

Após sua resolução, encontre 2 restrições que podem ser eliminadas sem alterar a solução
ótima.
Dica: use a dual.

Este último exercı́cio nos mostra que restrições cuja variável dual correspondente na
solução ótima é igual a zero podem ser eliminadas sem alteração na solução ótima de PL
primal.
Dualmente, variáveis que são iguais a zero na solução ótima da PL primal podem ser
eliminadas da sua programação sem alteração no valor ótimo.
Por fim, incluı́mos mais dois exemplos.

Exemplo 13. Considere a PL dual do exercı́cio anterior (mas agora não pense nela como
dual, e sim como uma PL primal):

min 4 11 9 17 y
   
1 2 1 4 3
sujeito a y≥
0 1 1 1 2
y ≥ 0.

Você aplica o simplex nesta PL (de fato: aplique, pratique!), e após sua solução você encontra
o tableau  
2 0 0 2 2 7 −20
 1 1 0 3 −1 1 1 
−1 0 1 −2 1 −2 1
Note que temos −20 porque estávamos fazendo max(−cT )y ao invés de min cT y. Tudo
funciona igual, mas o valor objetivo fica multiplicado por −1.
Continuando.... Suponha agora que seu cliente lhe diz: “esqueça a variável y2 ”. Você fica
chateado porque a variável y2 era básica, mas mesmo assim você a apaga do seu tableau,
obtendo:  
2 0 2 2 7 −20
 1 0 3 −1 1 1 
−1 1 −2 1 −2 1
Como ajustar agora para acharmos o ótimo?

60
G. Coutinho e C. Arbex Valle DCC035 P.O.

O problema perdeu uma variável básica. Isto indica também que o dual deste problema
(que seria o primal do exemplo anterior!) perdeu uma restrição apertada. Ou seja, o pro-
blema dual continua viável, mas não é mais necessariamente ótimo. Vamos então reotimizar
o problema através do simplex dual. Para facilitar, vamos começar multiplicando a primeira
linha, que perdeu sua variável básica, por −1:
 
2 0 2 2 7 −20
 −1 0 −3 1 −1 −1 
−1 1 −2 1 −2 1
Podemos aplicar (como visto anteriormente) o simplex dual escolhendo o mı́nimo:
ci
.
−A1,i
A idéia é sempre fazer a operação de pivoteamento correta que (1) não torna a solução
inviável (2) não leva c a ficar ≤ 0. No caso, i = 3. Teremos então
 
4/3 0 0 8/3 19/3 −62/3
 1/3 0 1 −1/3 1/3 1/3 
−1/3 1 0 1/3 −8/3 5/3
Note que este novo tableau é ótimo para a base viável de colunas 2 e 3!
Poderı́amos também ter evitado a multiplicação da primeira linha por −1 e escolhido,
neste caso, o mı́nimo
ci
.
A1,i
Isto apenas nos pouparia um pouco de trabalho.

Por último, estudamos o que fazer quando uma variável é adicionada:

Exemplo 14.

max 1 2 7 x
   
1 0 2 4
sujeito a  0 1 3 x ≤ 5
 
−1 1 0 0
x ≥ 0.

Seu tableau estendido, que registra as operações realizadas, é:


 
0 0 0 −1 −2 −7 0 0 0 0
 1 0 0 1 0 2 1 0 0 4 
 
 0 1 0 0 1 3 0 1 0 5 
0 0 1 −1 1 0 0 0 1 0

61
G. Coutinho e C. Arbex Valle DCC035 P.O.

Que, apos sua solução, leva a


 
2 1 1 0 0 0 2 1 1 13
 3 −2 2 1 0 0 3 −2 2 2 
 
 −1 1 −1 0 0 1 −1 1 −1 1 
3 −2 3 0 1 0 3 −2 3 2
Suponha agora que somos informados que uma variável foi omitida da formulação incorre-
tamente. Na verdade, o problema original deveria ter sido:

max 1 2 7 4 x
   
1 0 2 0 4
sujeito a  0 1 3 1 x ≤ 5
−1 1 0 2 0
x ≥ 0.
Como proceder?
Ora, sabemos que após as mesmas operações realizadas originalmente, a coluna corres-
pondente à nova variável será
    
3 −2 2 0 2
 −1 1 −1    
1 = −1 ,
3 −2 3 2 4

e que seu valor no vetor c, dado por cTB A−1 T


B A4 − c (onde A4 é a coluna da nova variável
x4 ), será  
 0
2 1 1 1 + (−4) = −1.
2
Note o -4 devido ao tableau inverter o valor do c4 original. O tableau então será
 
2 1 1 0 0 0 −1 2 1 1 13
 3 −2 2 1 0 0 2 3 −2 2 2 
 
 −1 1 −1 0 0 1 −1 −1 1 −1 1 
3 −2 3 0 1 0 4 3 −2 3 2
Então neste caso, basta aplicarmos o pivoteamento do simplex primal:
 
2 1 1 0 0 0 −1 2 1 1 13
 3 −2 2 1 0 0 2 3 −2 2 2 
 
 −1 1 −1 0 0 1 −1 −1 1 −1 1 
3 −2 3 0 1 0 4 3 −2 3 2
levando a
 
11/4 1/2 7/4 0 1/4 0 0 11/4 1/2 7/4 27/2
 3/2 −1 1/2 1 −1/2 0 0 3/2 −1 1/2 1 
 
 −1/4 1/2 −1/4 0 1/4 1 0 −1/4 1/2 −1/4 3/2 
3/4 −1/2 3/4 0 1/4 0 1 3/4 −1/2 3/4 1/2

62
G. Coutinho e C. Arbex Valle DCC035 P.O.

Resumindo: esteja confortável com o método simplex primal e dual. E


então....

(i) Ao adicionarmos uma restrição após a solução: (1) eliminação Gaussiana para que a
nova PL permaneça na base antiga (2) aplicar o simplex dual para achar uma nova
base viável.

(ii) Variação no vetor b: aplica a matriz de operações ao novo vetor b. Se viável, maravilha.
Se não, simplex dual.

(iii) Para remover restrições, cheque as entradas iguais a 0 na solução dual ótima.

(iv) Para remover variáveis: se for não-básica, nada muda, apenas remove. Se for básica,
remove, e aplica uma espécie de simplex dual na linha correspondente com o sinal
invertido.

(v) Para adicionar variáveis: aplica no vetor correspondente a matriz de operações da


solução, incluindo as mudanças na entrada de c. Se não estiver ótima, aplica-se o
simplex primal.

Exercı́cio 54. Explique como adaptar a solução de uma PL se houver uma mudança na
função objetivo.

Aula 13
3.8 Teoria de jogos
Nesta aula vamos dar um gostinho de teoria de jogos, e mostrar uma aplicação clássica do
Teorema Forte da Dualidade.
Aqui vamos tentar formalizar a definição de um jogo. Vamos começar com pedra-papel-
tesoura. Em cada rodada, dois jogadores fazem escolhas independentes, e a comparação das
estratégias escolhidas define o resultado. Pedra-papel-tesoura é um jogo de soma zero: se
jogador A ganha, jogador B perde, ou vice-versa. Não há como ambos ganharem ou ambos
perderem. Um jogo como este pode ser formalizado como uma matriz:

Pedra Papel Tesoura


Pedra 0 -1 1
.
Papel 1 0 -1
Tesoura -1 1 0

Esta matriz M representa a pontuação recebida pelo jogador A, onde sua escolha é a linha, e
a escolha de B é a coluna. Como este é um jogo de soma 0, a matriz que indica a pontuação
de B é exatamente −1 vezes a transposta da matriz acima: se A ganha −1 em a12 , então B
ganha 1 em a12 , etc.

63
G. Coutinho e C. Arbex Valle DCC035 P.O.

Suponha que A e B fazem suas escolhas seguindo uma certa probabilidade. Por exemplo,
A pode escolher x = (1/2, 1/4, 1/4), indicando que em 50% dos casos ele escolhe pedra, e os
outros 50% ele divide igualmente entre papel e tesoura. Já B pode fazer y = (1/3, 1/3, 1/3),
ou seja, mesma chance pra todos. Com essas escolhas feitas, podemos calcular o valor
esperado do jogo para A:

X
3 X
3
xi y j mij , que é igual a xT My.
i=1 j=1

O negativo deste valor é o valor esperado para B. Ou seja, A ganha

xT My = 0.

E portanto B também ganharia 0. Por outro lado, se as escolhas tivessem sido x = (1, 0, 0)
e y = (0, 0, 1), então
xT My = 1,
indicando que A ganharia sempre +1, e B ganharia sempre −1 (o que é de se esperar, já
que A estaria garantindo que escolheria sempre pedra, e B escolheria sempre tesoura).

3.8.1 Estratégias
Imagine agora a situação em que A e B jogam, mas A anuncia sua estratégia probabilı́stica
antes do jogo para B. Será que isso dá alguma vantagem a B?
• A resposta é que depende da estratégia. Por exemplo, se A anuncia x = (1, 0, 0),
então B sabiamente escolheria y = (0, 1, 0) para ganhar. Mas note que se A escolher
x = (1/3, 1/3, 1/3), então não importa o que B faça, A vai acabar sorteando inde-
pendentemente a sua escolha. Ou seja, há uma escolha de probabilidades para A que,
mesmo que B tenha acesso a ela de antemão, ele não ganha qualquer vantagem.
Imagine agora outro jogo, chamado “Exemplo da Wikipedia”. Neste jogo, A tem duas
escolhas, e B tem três. A matriz que quantifica o pagamento para A a partir das combinações
é a seguinte:
1 2 3
1 30 −10 20
2 −10 20 −20
Aı́ A pensa assim: “se eu escolher 2, eu posso até ganhar 20, mas aı́ eu perco 10 ou 20, nas
outras possibilidades. Por outro lado, escolher 1 me dá chance de ganhar 30 ou 20, e eu só
perderia 10. Então vou escolher 1.”Mas aı́ B se liga nisso e escolheria 2. Então A se toca
que B pensaria assim, e na verdade escolhe 2 pra surpreender B. B que não é besta imagina
que A pensaria nisso, e aı́ pega 3 pra ganhar 20 de A. E assim sucessivamente.... Qual a
melhor estratégia?
• B decide então tomar uma atitude drástica: ele vai deixar que a sorte escolha. Mas
não totalmente. Ele escolhe as probabilidades. Após muito refletir, B decide que
y = (0, 1/2, 1/2) parece razoável. E se sentindo confiante, decide avisar a A de antemão

64
G. Coutinho e C. Arbex Valle DCC035 P.O.

que é assim que ele vai agir. O que A deveria fazer? Ora, A agora vai escolher sua
probabilidade, ou seja, A escolhe x = (x1 , x2 ), com x1 + x2 = 1, e o ganho final do jogo
para A será
 
  0  
 30 −10 20    5
x1 x2 1/2 = x1 x2 = 5x1 .
−10 20 −20 0
1/2
Ou seja, sabendo das probabilidades de B, A vai sempre escolher 1, e maximizará
assim sua esperança de ganho. B, se sentindo injustiçado, decide jogar de novo. Mas
dessa vez, ele quer forçar A a escolher suas probabilidades antes e anunciá-las. O que
acontece?
• A, que não é besta e aprendeu das coisas comigo, manda pra B a seguinte escolha de
probabilidades: x = (4/7, 3/7). B vai lá fazer suas continhas, pra achar y = (y1 , y2 , y3 ),
com y1 + y2 + y3 = 1. Daı́ temos
   
  y1
 30 −10 20    y1 90 20 20
4/7 3/7 y2 = 90/7 20/7 20/7 y2  = y1 + y2 + y3 .
−10 20 −20 7 7 7
y3 y3

Ou seja, não importa o que B fizer, a esperança de ganho para A será pelo menos 20/7!
Exercı́cio 55. Suponha que em um dado jogo, a melhor estratégia probabilı́stica para Alice
é o vetor x, e que 
xT M = −1 2 3 −2 0 .
Qual a estratégia ótima para Bob?

3.8.2 Teorema Minimax


Não foi surpresa alguma que no jogo anterior A foi capaz de ganhar mesmo tendo que
anunciar sua estratégia probabilı́stica de antemão. A verdade é que: não importa!!!
Seja M a matriz do problema que dá os ganhos de A.
Vamos formular o problema supondo que A vai mandar sua distribuição para B. O
jogador A sabe que B calculará xT M e escolherá a menor entrada deste vetor para concentrar
suas probabilidades. No exemplo acima, A ganhou porque a menor entrada deste vetor era
positiva, igual a 20/7. Portanto A deseja maximizar a menor entrada de xT M. Formulamos
este problema como uma PL usando uma variável extra ` ∈ R, da seguinte forma:

max `
sujeito a ` ≤ 30x1 − 10x2
` ≤ −10x1 + 20x2
` ≤ 20x1 + 20x2
x1 + x2 + x3 = 1
x ≥ 0.

65
G. Coutinho e C. Arbex Valle DCC035 P.O.

Utilizando notação matricial e reordenando os termos, temos a PL:

max `
sujeito a MT x − `1 ≥ 0
1T x = 1
x ≥ 0.

onde 1 é um vetor de 1’s de dimensão apropriada.


Equivalentemente, se for B o primeiro a escolher as probabilidades, B estará resolvendo
a PL

min ω
sujeito a ω ≥ 30y1 − 10y2 + 20y3
ω ≥ −10y1 + 20y2 − 20y3
y1 + y2 + y3 = 1
y ≥ 0.

que em notação matricial pode ser escrita como:

min ω
sujeito a My − ω1 ≤ 0
1T y = 1
y ≥ 0.

Agora que vem a graça


 da coisa toda:
 as duas PLs acima são duais uma da outra!! De
fato, seja x0T = xT ` , y 0T = y T ω , e seja
 T 
M −1
N= .
1T 0
Então a primeira PL é
 
 x
max 0 0 ... 0 1
`
sujeito a
 
≥ 0
 T   ≥ 0
 
M −1 x .. ..
T . .
1 0 `  
≥ 0
= 1
x ≥ 0.

66
G. Coutinho e C. Arbex Valle DCC035 P.O.

Sua dual será


 
 y
min 0 0 ... 0 1
k
sujeito a
 
≥ 0
   ≥ 0
 
M 1 y .. ..
T . .
−1 0 k  
≥ 0
= 1
y ≤ 0.

Trocando y por −z, teremos exatamente a formulação


 
 −z
min 0 0 ... 0 1
k
sujeito a
 
≤ 0
   ≤ 0
 
M −1 z .. ..
. .
1T 0 k  
≤ 0
= 1
z ≥ 0.

Conclusão?
Teorema 6 (von Neumann). Em um jogo de soma zero entre duas pessoas, o valor máximo
do ganho esperado mı́nimo de um jogador é IGUAL ao valor mı́nimo da perda esperada
máxima do outro jogador. Ademais, cada jogador possui uma estratégia probabilı́stica que
satisfaz esta igualdade. Ou seja
   
max min x Ay = min max xT Ay .
T
x y y x

O valor descrito no teorema acima é o famoso equilı́brio de Nash do jogo. John Nash
publicou este teorema em sua tese de doutorado, e este trabalho lhe rendeu o Prêmio Nobel
de Economia em 1994.
Exercı́cio 56. Considere o seguinte jogo. Alice e Bob decidem que a cor azul vale 10 reais,
e que a cor verde vale 6 reais. Cada um deles escolhe uma cor. Se derem iguais, Bob paga
a Alice o valor somado das duas cores (16). Se der diferente, Alice paga a Bob duas vezes o
valor da cor que ela escolheu (20 ou 12).
(i) Este jogo é melhor pra quem? Calcule o equilı́brio de Nash.

(ii) Há alguma escolha de valores para as cores em que este jogo se torna justo?

67
G. Coutinho e C. Arbex Valle DCC035 P.O.

3.9 Interpretação econômica


Considere a seguinte situação. Uma indústria X produz n produtos, e cada produto i dá
um lucro de ci . Para produzir estes produtos, a empresa usa m recursos, e há um máximo
de bj para cada recurso j. Finalmente, se usa Aji quantidades do recurso j para produzir o
produto i.
A pergunta, naturalmente, é quanto produzir de cada produto para maximizar o lucro
total? Agrupando esses dados em vetores e matrizes, temos naturalmente a programação
linear:

max cT x
sujeito a Ax ≤ b
x ≥ 0.

Vamos agora ver um exemplo do significado do dual. Suponha que até então esta empresa
era um monopólio, e adquiria os recursos a um preço muito baixo do único produtor Z.
Uma segunda indústria Y , mais poderosa talvez, deseja entrar no mercado. Após suces-
sivas tentativas frustradas de comprar a indústria X, ela decide eliminá-la secando a fonte
dela, ou seja, comprando todos os recursos disponı́veis de Z. Como estabelecer uma proposta
de preços para cada recurso de modo a minimizar o custo total, porém de modo que a oferta
a Z seja irrecusável?
A empresa Y pensa assim. Para cada recurso j, com j de 1 a m, vamos propor o preço
de y m . Queremos minimizar o custo da compra de todos os recursos, ou seja

min bT y.

Para que nossa oferta a Z seja irrecusável, vamos oferecer um preço que cubra o que o
X jamais conseguiria ganhar com a venda de seus produtos. Dessa forma, Z pensará que
mesmo que X reformule sua produção, nossa oferta ainda será superior. Note que, com a
produção de uma unidade do produto i, X gasta
X
m
Aji
j=1

recursos. Cada uma dessas unidades rende a X um lucro de ci . Então vamos colocar preços
de modo que ao comprar a mesma quantidade de recursos, Z receba pelo menos o que X
receberia na venda do produto, ou seja
X
m
Aji y j ≥ ci .
j=1

Juntando todas elas para cada produto, temos exatamente

AT y ≥ c.

68
G. Coutinho e C. Arbex Valle DCC035 P.O.

Obviamente, os preços, devem ser não-negativos, e então aparece a formulação:

min bT y
sujeito a AT y ≥ c
y ≥ 0.

Esta é precisamente a PL dual. O mais impressionante, talvez, é que por conta do Teorema
da Dualidade, a solução ótima para Y é exatamente o máximo que X conseguiria vender.
Nem mais, nem menos.
A idéia aqui, obviamente, é limitada no sentido em que preços no mundo real não são
determinados de modo tão simples. Este modelo ignora a existência de outros fatores,
como demais concorrentes ou outros fornecedores de recursos. Mas ele estabelece uma idéia
importante: a de que dado um certo processo de produção, os recursos usados possuem um
preço inerente somente ao processo, também chamado de preço interno ou “shadow price”.
E as condições de folga complementares, o que diriam? Nesta lógica, se um determinado
recurso não é completamente usado por X, então Y pode oferecer qualquer valor a Z pelo
excedente. Em certo sentido, Z estaria disposta a até mesmo dar de graça para poder fechar
o negócio. Nessa lógica, a variável correspondente em y é 0.
Note também que uma pequena variação na quantidade disponı́vel de cada recurso pro-
vavelmente não alterará o preço deste recurso. De fato, como vimos, alterações no vetor b
podem, muitas vezes, não alterar o processo de solução no simplex. Ou seja, a solução dual
permanece a mesma!
Considere agora o seguinte problema.

Exercı́cio 57. Um estudante está decidindo o que comprar de uma padaria para um lanche.
Há duas opções: brownies e cheesecakes, ao preço de 5 ou 8 reais, respectivamente (é possı́vel
comprar frações do lanche). A padaria usa 100 gramas de chocolate no cheesecake, 60g de
açúcar no brownie e 120g no cheesecake, e 60g de creme no brownie e 150g no cheesecake.
O estudante, seguindo a dieta do nutricionista, quer no mı́nimo 180g de chocolate, 300g de
açúcar e 240g de creme. O objetivo, naturalmente, é gastar o mı́nimo possı́vel.

(a) Formule a PL correspondente.

(b) Imagine agora que você é o distribuidor que vende à padaria chocolate, açúcar e creme. A
padaria te informa precisamente o mı́nimo de cada ingrediente que ela precisa comprar
para satisfazer o estudante, assim como quanto é gasto em cada lanche. Explique a
interpretação econômica de dualidade, ou seja, qual a lógica do distribuidor para realizar
essa venda, e como a PL dual captura isso?

(c) Usando as condições de folga complementares, explique qual seria a lógica se uma das
variáveis na solução ótima da dual for zero, ou seja, o que explicaria o distribuidor vender
algo de graça a padaria?

69
Capı́tulo 4

Geometria e teorema de alternativas

4.1 Geometria de poliedros


Dado um vetor a ∈ Rn , o conjunto de vetores x que satisfaz

aT x = 0

é um hiperplano, ou seja, um subespaço de Rn de dimensão n − 1. O vetor a é o vetor


diretor do hiperplano, ortogonal a todos os vetores que lá se encontram. Ao trocarmos =
por ≤ ou ≥, passamos a considerar a metade do Rn que se encontra de um lado ou de outro
do hiperplano. Por exemplo, o conjunto dos x tais que

aT x ≥ 0

é o conjunto de todos os vetores x tais que o ângulo entre x e a está entre 0 e π/2. Tais
conjuntos são chamados de hiperespaços. Ao adicionarmos uma constante, por exemplo

aT x ≥ β,

estamos apenas transladando o hiperplano que serve de fronteira entre o hiperespaço e o seu
complemento.
As restrições lineares de uma PL sempre são da forma

aT x ≤ β ou aT x = β ou aT x ≥ β.

Note que aT x ≥ β é equivalente a (−aT )x ≤ −β, e que aT x = β é equivalente a simultane-


amente termos aT x ≤ β e (−aT )x ≤ −β. Portanto as restrições de uma PL sempre podem
ser expressas usando ≤, e ao juntarmos todas elas, teremos

Ax ≤ b (∗)

para uma certa matriz A e um vetor b. Conjuntos de vetores x satisfazendo (∗) são chamados
de poliedros. Todo poliedro é uma interseção finita de hiperespaços.
Toda PL consiste em otimizar uma função afim (linear adicionada de uma
possı́vel constante) em um poliedro.

70
G. Coutinho e C. Arbex Valle DCC035 P.O.

Dados dois pontos x1 , x2 ∈ Rn , o segmento de reta entre eles pode ser expresso como
x ∈ Rn : x = λx1 + (1 − λ)x2 com 0 ≤ λ ≤ 1.
Um conjunto C de pontos é chamado de convexo se para quaisquer dois pontos no conjunto,
o segmento de reta entre eles também pertence ao conjunto.
Teorema 7. Poliedros são convexos.
Demonstração. Sejam x1 e x2 pontos satisfazendo Ax ≤ b. Daı́ teremos que, para todo
λ tal que 0 ≤ λ ≤ 1,
A(λx1 + (1 − λ)x2 ) ≤ λb + (1 − λ)b = b.

Exercı́cio 58. A reta entre dois pontos x1 e x2 é definida como


x ∈ Rn : x = λx1 + (1 − λ)x2 com λ ∈ R.
Por que não podemos usar a demonstração acima para mostrar que a reta entre dois pontos
de um poliedro está sempre contida no poliedro?
Um ponto x em um poliedro P é chamado de ponto extremo se não há qualquer segmento
em P que tenha x como um ponto em seu interior. É interessante notar que se um ponto x
não é extremo, então ele não pode ser a única solução ótima de uma PL.
Exercı́cio 59. Suponha que estamos maximizando cT x, com Ax ≤ b. Assuma que z 1 e
z 2 são soluções viáveis. Seja z = λz 1 + (1 − λ)z 2 , com λ entre 0 e 1. Mostre que o valor
objetivo de z não pode ser estritamente maior que ambos os valores objetivos de z 1 e z 2 , e
que se z 1 e z 2 são soluções ótimas, então z também é.
Nosso objetivo agora é entender como podemos identificar os pontos extremos de um
poliedro olhando apenas para o conjunto de desigualdades Ax ≤ b que o define. Se x1 é um
ponto especı́fico que satisfaz essas desigualdades, definimos como A= a matriz associada a
x1 que contempla todas as linhas em que a inequação é uma igualdade, e analogamente b= .
Ou seja, A= x1 = b= .
Teorema 8. Seja P = {x ∈ Rn : Ax ≤ b} um poliedro, e suponha que x1 ∈ P . Seja
A= x1 = b= o conjunto de restrições com igualdade para x1 . Então x1 é um ponto extremo
de P se, e somente se, o posto de A= é igual a n.
Antes da demonstração, vamos ver um exemplo.
Exemplo 15. Considere o poliedro definido por
   
1 1 3
 1 0  
 2
 0 1  
  x ≤ 2 ,
−1 0  0
0 −1 0

cuja região correspondente no R2 é dada por

71
G. Coutinho e C. Arbex Valle DCC035 P.O.


Pegamos por exemplo o ponto x = 1 1 . Segue que
   
2 3
 1 2
   
Ax =    
 1 ≤ 2 ,
−1 0
−1 0
e portanto nenhuma das linhas corresponde a uma restrição com igualdade. Segue que A=
é a matriz vazia, de posto 0, ex não é ponto extremo.
Considere agora x = 1 0 . Teremos
   
1 3
 1 2
   
Ax =    
 0 ≤ 2 ,
−1 0
0 0
 
portanto a última linha é uma restrição com igualdade, e A= = 0 −1 e b= = 0 . Como
o posto de A= é igual a 1, e não
 2, este ponto x não é um ponto extremo.
Considere agora x = 2 1 . Segue que
   
3 3
 2 2
   
Ax =    
 1 ≤ 2 ,
−2 0
−1 0
portanto as duas primeiras linhas são restrições com igualdade, e daı́ teremos
   
= 1 1 = 3
A = eb = .
1 0 2

72
G. Coutinho e C. Arbex Valle DCC035 P.O.

Como o posto de A= é 2, este ponto x é um ponto extremo.

Apresentamos a demonstração do teorema.

Demonstração. Suponha que o posto de A= é n, e suponha por contradição que x não é


ponto extremo, logo existem x1 e x2 distintos, e um λ entre 0 e 1, tais que x = λx1 +(1−λ)x2 .
Segue que
b= = A= x = A= (λx1 + (1 − λ)x2 ) ≤ λb= + (1 − λ)b= = b= .
Portanto o sinal de desigualdade é uma igualdade, e daı́ segue que

A= x1 = A= x2 = b= ,

logo A= (x1 − x2 ) = 0, uma contradição ao fato de que A tem posto n.


Suponha agora que o posto de A= seja menor que n, e portanto existe um vetor d 6= 0
tal que A= d = 0. Para todo  > 0, segue que x é ponto médio entre x1 = x + d e
x2 = x − d. Vamos mostrar agora que tanto x1 como x2 estão em P . Note primeiro que
A= x1 = A= x2 = b= , já que A= d = 0, daı́ as únicas desigualdades em Ax1 ≤ b e Ax2 ≤ b
que faltam ser testadas são aquelas em que Ax ≤ b ocorria como desigualdade estrita. Mas
aı́ basta escolhermos  pequeno o suficiente para que a influência de Ad nestas desigualdades
não seja relevante.

Neste momento, é bem conveniente interpretar os resultados acima no âmbito de PLs em


FPI. Primeiro, o exercı́cio abaixo.

Exercı́cio 60. Considere o poliedro


     
4 1 3 1 0 2
P = x∈R : x= , x ≥ 0. .
2 2 0 1 1
T
Note que z = 0 0 2 1 é uma solução básica viável.

(i) Reescreva as restrições que definem P para que apareçam apenas restrições com ≤.

(ii) Use o Teorema (8) para mostrar que z é um ponto extremo do poliedro.

Exercı́cio 61. O objetivo deste exercı́cio é compreender melhor a geometria da região viável
de uma PL em FPI. Considere

max cT x
sujeito a Ax = b
x ≥ 0,

e suponha que seja viável e limitada. Suponha que A é uma matriz m × n, n ≥ m, e seu
posto é igual a m.

(a) Suponha que z 1 e z 2 são soluções viáveis. Verifique diretamente que o segmento de reta
entre elas é composto de soluções viáveis.

73
G. Coutinho e C. Arbex Valle DCC035 P.O.

Lembre-se que para uma PL em FPI, uma solução viável x é chamada de básica se o
suporte das entradas não nulas de x corresponde a um subconjunto de colunas de A
contidas em uma base. Para a próxima letra, converta a expressão da PL para algo da
forma Mx ≤ d, e use o teorema anterior.

(b) Mostre que x é solução viável básica se e somente se x é um ponto extremo.

Também é possı́vel demonstrar a letra acima diretamente. As letras abaixo são um passo-
a-passo. É um excelente exercı́cio fazer as letras abaixo sem olhar para a demonstração
do teorema acima.

(c) Assuma que z 1 e z 2 são soluções viáveis distintas, e z = λz 1 + (1 − λ)z 2 . Mostre que se
0 < λ < 1, z não pode ser uma solução básica viável da PL.

(d) Mostre que se w > 0 (ou seja, um vetor em que todas as entradas são positivas) e w é
viável, então existem w1 6= w2 soluções viáveis tais que w = 1/2(w1 + w2 ), a não ser
possivelmente no caso em que n = m.

(e) Mostre que todo ponto extremo do poliedro (ou seja, os pontos que não pertencem a um
segmento viável não-trivial) são exatamente as soluções básicas viáveis.
Por fim, seja x1 , ..., xm um conjunto de pontos no Rn . Uma combinação convexa desses
pontos é um ponto x que satisfaz

x = λ1 x1 + ... + λm xm ,

onde 0 ≤ λi ≤ 1 para todo i, e λ1 + ... + λm = 1.


Exercı́cio 62.
(i) Considere três pontos não-colineares. Geometricamente, o que é o conjunto de todas
as combinações convexas desses pontos?

(ii) Mostre que se três pontos pertencem a conjunto convexo, então todas as combinações
convexas também pertencem.

(iii) Se convença, mas tente me convencer também, que um poliedro que não contenha uma
semi-reta (ou se você preferir, um poliedro limitado, também chamado de politopo) é
precisamente o conjunto de combinações convexas dos seus pontos extremos.

4.2 Teorema de alternativas e dualidade


Dados A e b, um grande e importante problema é decidir se o poliedro determinado pelas
desigualdades Ax ≤ b é vazio ou não. Para tanto, introduzimos o Teorema das Alternativas,
em cuja demonstração apresentamos o esquema de eliminação de Fourier-Motzkin.
Teorema 9. Dados A e b, exatamente uma das seguintes sentenças é verdadeira.
(1) O sistema Ax ≤ b tem solução.

74
G. Coutinho e C. Arbex Valle DCC035 P.O.

(2) Existe z com z ≥ 0, z T A = 0, e bT z < 0.


Demonstração. Claramente, ambos não podem ser verdadeiros ao mesmo tempo. Portanto,
devemos mostrar que ambos não podem ser falsos ao mesmo tempo. A prova é por indução
no número de colunas de A. Dentro da indução existe um algoritmo implı́cito conhecido
como procedimento de eliminação de Fourier-Motzkin.
Para o caso base, note que se A tem zero colunas, então (1) simplesmente declara que
b ≥ 0. Se isso falhar, uma coordenada é negativa, digamos i-ésima, então simplesmente
escolha z = ei .
Suponha que o teorema seja válido para qualquer matriz com n − 1 colunas. Considere
agora A uma matriz m × n. Suponha sem perda de generalidade que as desigualdades foram
escalonadas de modo que a magnitude dos coeficientes diferentes de zero de xn seja 1. Sejam
I+ os ı́ndices de linha correspondentes aos coeficientes positivos de xn , I− aos negativos e I0
aos coeficientes 0. Portanto, o sistema se escreve como

X
n−1
Aik xk + xn ≤ bi , para todo i ∈ I+ ,
k=1
X
n−1
Aik xk − xn ≤ bi , para todo i ∈ I− ,
k=1
X
n−1
Aik xk ≤ bi , para todo i ∈ I0 .
k=1

Isso implica que ! !


X
n−1 X
n−1
max Aik − bi ≤ min bi − Aik ,
i∈I− i∈I+
k=1 k=1
então o sistema original tem solução se e somente se o seguinte sistema também tem
X
n−1
(Aik + Ajk )xk ≤ bi + bj , para i ∈ I− e j ∈ I+ ,
k=1
X
n−1
Aik xk ≤ bi , para i ∈ I0 .
k=1

Note que o número de variáveis diminuiu, mas o número de inequações aumentou terrivel-
mente. Isso contudo não é um problema para a nossa indução (mas seria um problema se
estivéssemos usando este método para resolver PLs).
Se o sistema original não tem solução, o anterior também não tem, e, por indução, existem
coeficientes wij , para i ∈ Ii e j ∈ I+ , e coeficientes vi , para i ∈ I0 , de modo que, para todos
os ı́ndices, wij ≥ 0, vi ≥ 0, e
X X
(Aik + Ajk )wij + Aik vi = 0, para todo k,
i∈I− ,j∈I+ i∈I0

75
G. Coutinho e C. Arbex Valle DCC035 P.O.

e X X
(bi + bj )wij + bi vi < 0.
i∈I− ,j∈I+ i∈I0

Assim, simplesmente definimos z por


X
zi = wij , para i ∈ I− ,
j∈I+
X
zj = wij , para j ∈ I+ ,
i∈I−

zi = vi , para i ∈ I0 .

Satisfaz z ≥ 0, z T A = 0, e bT z < 0.
Exercı́cio 63. O lema de Farkas diz que Ax = b e x ≥ 0 não tem solução se e somente se
houver y de modo que y T A ≥ 0 e bT y < 0. Prove isso (usando o Teorema das Alternativas).
Lembre-se que vimos que o certificado de inviabilidade nada mais é do que o ótimo da
dual da PL auxiliar. Não é difı́cil verificar que sua existência implica que o ótimo de PLs
duais coincide.
Teorema 10 (Teorema Forte da Dualidade). Considere o seguinte par primal-dual de pro-
gramações lineares
T min bT y
max c x
(P) (D) sujeito a AT y = c
sujeito a Ax ≤ b
y ≥ 0.
Se o problema dual (D) é viável e limitado, então (P) também é, e os ótimos coincidem.
Demonstração. Já sabemos por dualidade fraca que cT x ≤ bT y. Seja w solução ótima
para (D). Considere o sistema de inequações lienares
   
A b
x≤ .
−cT −bT w
Note que se ele for viável, então existe x viável para (P) tal que cT x ≥ bT w, e portanto
cT x = bT w. Suponha então, para efeito de contradição, que o sistema é inviável. Pelo Lema
de Farkas, existe (z, z0 ) ≥ 0 tal que
   
T
 A T
 b
z z0 =0 e z z0 < 0.
−cT −bT w
Se z0 = 0, note então que z seria uma certificado de ilimitada para (D), uma contradição.
Se z0 > 0, então note que
1 T 1 T
z A = cT , e z b < bT w,
z0 z0
contrariando o fato que w era ótimo para (D).
Assim, concluı́mos que (P) é viável, e seu ótimo é igual ao de (D).
É um exercı́cio interessante verificar que (algumas d)as demais formulações equivalentes
de dualidade também satisfazem o teorema forte acima.

76
G. Coutinho e C. Arbex Valle DCC035 P.O.

4.3 Geometria de otimização poliédrica


O cone gerado por um conjunto de vetores v 1 ,...,v k é o conjunto
( k )
X
C= λi v i : λi ≥ 0 .
i=1

Dado um poliedro P = {x : Ax ≤ b}, e x1 ∈ P , lembre da definição de A= e b= . O


cone das restrições de igualdade é o cone gerado pelas linhas de A= .

Exercı́cio 64. Volte ao Exemplo 15 e calcule o cone de restrições de igualdade para os três
pontos apresentados.

Apresentamos então uma caracterização de otimalidade.

Teorema 11. Seja x uma solução viável de max{cT x : Ax ≤ b}. Então x é ótima se e
somente c pertence ao cone de restrições de igualdade de x.

Demonstração. Vamos começar escrevendo o problema com variáveis de folga, o problema


dual, e relembrando as condições de folga complementares. No caso, temos
max cT x min bT y
(P) sujeito a Ax + u = b (D) sujeito a AT y = c
u≥0 y ≥ 0,
e, sem dificuldades, temos dualidade fraca:

cT x = y T Ax = y T (b − u) ≤ y T b,

com igualdade se e somente se y T u = 0, caso em que x e y formam um par primal dual de


soluções ótimas.
Suponha que c pertence ao cone de restrições de igualdade de x. Ou seja, existe y ≥ 0
tal que y T A= = c. Estendendo y com variáveis iguais a 0 para as demais linhas de A, temos
(abusando a notação) que y T A = c, ou seja, y é viável para (D), e, sem muitas dificuldades,
segue que y é diferente de 0 precisamente onde Ax ≤ b não tem folga, ou seja, onde a
entrada de u é 0, e daı́ temos que y T u = 0.
Se x (e folgas u) são ótimas para (P), o teorema forte da dualidade garante a existência de
y viável para (D) e com y T u = 0. É imediato verificar que y T A é portanto uma combinação
dos coeficientes positivos de y vezes as linhas de A= , e portanto c pertence ao cone de
restrições de igualdade de x.

77
Capı́tulo 5

Programações inteiras

78
G. Coutinho e C. Arbex Valle DCC035 P.O.

Aulas 14 e 15
5.1 Programações inteiras
Considere o problema de otimização abaixo:

max 12x1 + 2x2


sujeito a x2 ≤ 4
3x1 − 2x2 ≤ 3
10x1 + 2x2 ≤ 23
x1 , x2 ≥ 0
x1 , x2 ∈ Z.

Se ignorarmos a última restrição (que diz que as variáveis devem ser inteiras), a PL corres-
pondente pode ser representada graficamente pela figura abaixo:

5.0

x2 = 4

3x1 − 2x2 = 3
x2

2.5

0.0

10x1 + 2x2 = 23

0 2 4 6
x1

Os vértices do poliedro que define a área viável são (0, 0), (1, 0), (2, 32 ), ( 32 , 4), (0, 4). A figura
também inclui, em vermelho, os pontos dentro da área viável que são inteiros.
O ótimo (da PL) está no ponto (2, 32 ). O problema é que ele é fracionário, isto é, a solução
não satisfaz a condição de integralidade imposta. Observe a figura abaixo:

79
G. Coutinho e C. Arbex Valle DCC035 P.O.

5.0

x2 = 4
(1,4)

3x1 − 2x2 = 3
x2

2.5

3
(2, )
2

0.0

10x1 + 2x2 = 23

0 2 4 6
x1

Os pontos inteiros viáveis mais próximos da solução ótima da PL são (1, 1) e (1, 2). Porém,
como podemos ver na figura, o ótimo inteiro é o ponto (1, 4). As linhas verdes pontilhadas
representam a função objetivo passando pelo ponto ótimo da PL (com valor 27) e pelo ponto
ótimo do problema inteiro (com valor 20).
Este exemplo dá uma ideia da dificuldade que é lidar com problemas de programação
inteira: a solução ótima não é necessariamente próxima da solução ótima da PL obtida
quando ignoramos a restrição de integralidade. Quando consideramos mais variáveis (mais
dimensões), o problema se torna ainda mais crı́tico. Apontamos alguns fatos relevantes:
(i) O ótimo de uma programação inteira não está necessariamente na fronteira do poliedro.
(ii) Se a programação é um problema de maximização, o ótimo da PL é sempre maior ou
igual que o ótimo da PI. No exemplo acima, o ótimo da PL era 27, e da PI 20.
(iii) O que acontece com dualidade?
(iv) Se todos os vértices do poliedro são pontos de coordenadas inteiras, então esses ótimos
irão coincidir.
Em relação ao ponto (iv) acima, veremos mais pra frente que algumas PIs com um tipo
de estrutura especı́fica podem ser resolvidas facilmente. Porém, a grande maioria das PIs
não possui tal estrutura, e é um problema em aberto se é possı́vel resolve-las com algoritmos
polinomiais ou não.
Veremos em breve dois algoritmos que resolvem PIs. Ambos os algoritmos possuem
complexidade exponencial, porém funcionam rapidamente na prática em diversos casos (mas
não todos!). Porém, inicialmente, vamos apresentar alguns exemplos de problemas que
podem ser modelados como PIs.

80
G. Coutinho e C. Arbex Valle DCC035 P.O.

5.2 Modelagem
Vimos nas aulas anteriores várias PLs onde faria sentido se, na verdade, tivessem sido mo-
deladas como PIs. Por exemplo, ao planejar a produção de uma empresa, permitimos que
a solução final sugerisse produzir uma quantidade fracionária de um certo produto ao invés
de unidades inteiras. Outro exemplo é o problema da dieta, onde a solução pode indicar a
compra de “5.3 ovos” ou “10.2 porções de carne”. Na prática, faria sentido impor que as
porções devem ser inteiras para diversos alimentos (com exceção daqueles que compramos a
granel, por exemplo).
Nesta seção, veremos exemplos de problemas onde somente faz sentido utilizar pro-
gramação inteira.
Exemplo 16. Uma empresa possui N projetos nos quais pode investir. Cada projeto i ∈ N
possui retorno esperado positivo ci (em reais). Porém, devido a restrições orçamentárias,
não é possı́vel investir em todos. No caso, cada projeto i requer que a empresa faça aportes
financeiros ait nos tempos t = 1, . . . , T . O orçamento disponı́vel para estes aportes no tempo
t é bt (previamente conhecido ou estimado). Formule este problema como um problema de
programação inteira.

Variáveis de decisão: Devemos decidir em quais projetos a empresa irá investir. Não faz
sentido “investir em meio projeto”, ou “investir duas vezes no mesmo projeto”. Ou seja,
a decisão é binária: para cada projeto i, ou investe, ou não investe. Assim, vamos propor
variáveis xi que terão o valor 1 se optarmos por investir no projeto i, ou o valor 0, caso
contrário.
Este tipo de variável é geralmente chamado de variável binária. É uma variável inteira
limitada pelos valores 0 ≤ xi ≤ 1. É bastante utilizada em situações onde devemos tomar
decisões binárias, sim ou não. A grande maioria dos problemas mais interessantes de PI
requer variáveis binárias.

Função objetivo: Tendo decidido as variáveis, a empresa busca maximizar o retorno


esperado dos investimentos:

X
N
max ci x i
i=1

Note que o retorno esperado do projeto i, ci , será positivo na função objetivo apenas caso
xi seja 1.

Restrições: Para cada perı́odo de tempo t = 1, . . . , T possuı́mos um orçamento limitado


que não pode ser ultrapassado:

X
N
ait xi ≤ bt t = 1, . . . , T
i=1

Observe que a formulação possui T restrições, uma para cada perı́odo de tempo. O modelo
completo é dado abaixo:

81
G. Coutinho e C. Arbex Valle DCC035 P.O.

X
N
max ci x i
i=1
X
N
sujeito a ait xi ≤ bt t = 1, . . . , T
i=1
0 ≤ xi ≤ 1, xi inteiro, i = 1, . . . , N

É comum também utilizarmos a notação xi ∈ B para dizer que uma variável pode ter apenas
os valores 0 ou 1.
No problema acima, assumimos que ci é conhecido. Na prática, o retorno esperado é uma
estimativa cuja incerteza pode ser alta (alto risco). Existem diversos modelos de otimização
que buscam gerenciar o risco ao controlar a incerteza enquanto busca-se maximizar o retorno
esperado.

Exercı́cio 65. Suponha que a empresa possua três condições adicionais:

(a) Os projetos 3 e 4 são concorrentes, não é possı́vel investir em ambos ao mesmo tempo.

(b) Se a empresa investir no projeto 2, então deve obrigatoriamente investir no projeto 5.

(c) Se a empresa investir nos projeto 1 e 4, então deve obrigatoriamente investir no projeto
6.

Acrescente restrições à formulação acima de forma a garantir que estas condições sejam
respeitadas.

Exemplo 17. Uma empresa possui N tarefas urgentes que devem ser cumpridas. Cada
tarefa exige um funcionário (há também N funcionários disponı́veis). Todo funcionário pode
fazer toda tarefa, mas como cada funcionário tem um nı́vel de capacitação diferente, o tempo
gasto varia. Já sabemos de antemão que o funcionário i precisa de cij horas para executar
a tarefa j. A empresa busca minimizar o tempo total gasto nas tarefas e quer que todos os
funcionários fiquem ocupados (ninguém deve ficar a toa). Formule este problema como uma
PI.

Variáveis de decisão: Temos xij = 1 se o funcionário i executa a tarefa j, xij = 0 caso


contrário.

Formulação: O problema é formulado da seguinte forma:

82
G. Coutinho e C. Arbex Valle DCC035 P.O.

X
N X
N
min cij xij
i=1 j=1

X
N
sujeito a xij = 1 i = 1, . . . , N
j=1

X
N
xij = 1 j = 1, . . . , N
i=1
xij ∈ B i = 1, . . . , N, j = 1, . . . , N

O primeiro conjunto de restrições garante que todo funcionário será alocado a uma tarefa, e
o segundo conjunto garante que toda tarefa será executada por um funcionário.
Este problema é conhecido como o problema da atribuição (assignment). Veremos
mais pra frente que esta é uma PI “fácil” de ser resolvida.
Exercı́cio 66. Altere a formulação acima de acordo com os detalhes abaixo:

(a) As tarefas 3, 4, e 5 serão executadas na mesma sala. O funcionário 3 recentemente


descobriu que o funcionário 2 é amante de sua esposa, o que fez com que chegassem às
vias de fato em pleno ambiente de trabalho. A empresa obviamente não quer que os
dois fiquem na mesma sala. Adicione esta restrição à formulação acima.
(b) Os funcionários 4 e 5 trabalham bem em conjunto, e seria interessante que ou eles
fizessem as tarefas 1 e 2 (pois são relacionadas), ou fizessem as tarefas 6 e 7 (que
também são relacionadas). Altere a formulação para garantir que um dos casos acima
será verdadeiro. Dica: utilize uma variável binária extra.
(c) Ao invés de minimizar o tempo total das tarefas, a empresa quer finalizar os trabalhos
o mais cedo possı́vel, ou seja, ela quer que a última tarefa a ser finalizada termine o
quanto antes. Altere a formulação acima para atender este caso.

Exercı́cio 67. O governo de Minas deve decidir onde construir novos quartéis do corpo
de bombeiros. Há uma região com 6 cidades no norte do Estado que atualmente que não
é atendida por nenhum quartel em menos de 45 minutos. O governo gostaria de garantir
que há um corpo de bombeiros a no máximo 15 minutos de distância de cada uma destas 6
cidades. Abaixo, uma tabela com o tempo necessário para dirigir da cidade i até a cidade j
(a tabela não é necessariamente simétrica):

De/para 1 2 3 4 5 6
1 0 10 20 30 30 20
2 10 0 25 35 20 10
3 20 25 0 15 30 20
4 30 35 15 0 15 25
5 20 20 30 15 0 14
6 20 10 20 25 14 0

83
G. Coutinho e C. Arbex Valle DCC035 P.O.

Devido ao orçamento apertado, o governo gostaria de construir o menor número possı́vel


de quartéis. Formule este problema como uma PI.
Exercı́cio 68. Você quer resolver um problema de machine learning e possui N features
disponı́veis. Você acha que N features são demais e gostaria de reduzir este conjunto para
K < N features, sendo K um valor fixo previamente decidido. O ideal é que as features sele-
cionadas sejam pouco correlacionadas, ou seja, queremos minimizar a soma das correlações
entre todas as K features selecionadas. O valor cij representa a correlação entre as features i
e j. Formule este problema utilizando Programação Inteira Linear Mista (neste caso, podem
haver variáveis inteiras e variáveis não inteiras).
Exercı́cio 69. Uma empresa produz mapas do mundo que são vendidos em bancas de jornal.
Cada um dos N paı́ses do mapa deve ser colorido com uma cor, porém paı́ses vizinhos não
podem ter cores iguais. Devido aos altos custos dos cartuchos de tinta, a empresa gostaria
de utilizar o menor número possı́vel de cores no mapa. Considere que há C cores disponı́veis
e que já sabemos de antemão quais paı́ses são vizinhos, isto é, temos uma matriz Bij = 1 se
os paı́ses i e j são vizinhos, 0 caso contrário.
Formule o problema de encontrar o menor número possı́vel de cores a serem utilizadas
em um mapa como um problema de programação inteira.
Exercı́cio 70. Desafio O Brasileirão possui 20 equipes e é disputado utilizando-se uma
fórmula de pontos corridos, onde todas as equipes se enfrentam duas vezes (uma em casa,
uma fora), totalizando 38 jogos por equipe. Idealmente, as equipes devem alternar entre jogar
uma partida em casa, uma fora de casa, e assim vai. Não é interessante para o torcedor que
uma equipe jogue 3 partidas seguidas em casa, por exemplo, ou que jogue 5 partidas seguidas
fora de casa. Por isto, estas situações nunca devem ocorrer. Matematicamente, porém, não
sabemos se existe uma solução onde nenhuma equipe jogue duas partidas seguidas em casa
ou duas seguidas fora (quando isto ocorre, temos uma quebra).

(a) Considere inicialmente que cada equipe jogará apenas uma vez contra as demais (19
jogos cada). Formule este problema como uma PI que minimiza o número de quebras.

(b) Adicione uma restrição que impõe que se na primeira rodada uma equipe jogou em
casa, então deve jogar fora de casa na última rodada.

(c) O que você deve fazer para resolver agora o problema com 38 rodadas, onde se a equipe
i enfrentou j em casa na rodada t, deve então enfrenta-la fora de casa na rodada t + 19
(tabela com dois turnos simétricos)?

5.3 Escrevendo uma PI como uma PL


Até agora tratamos PIs da seguinte forma. Apresentamos uma PL do tipo

max cT x
sujeito a Ax = b
x ≥ 0,

84
G. Coutinho e C. Arbex Valle DCC035 P.O.

e adicionamos uma restrição


x ∈ Zn .
Nosso objetivo nesta semana é ser capaz de formular uma PI sem precisar codificar a res-
trição de integralidade da maneira acima. Nesta semana, aprenderemos como, ao sermos
apresentados a uma matriz A qualquer, fazer pequenas modificações de modo que o ótimo
da PL seja um ótimo da PI correspondente.

Exemplo 18. Considere



max 1 1 x
   
2 1 7
 1 2  7
sujeito a  x ≤  
−1 −4  −4
−1 0 −1/2
x inteiro.

Cada uma das restrições corresponde às retas (1), (2), (3) e (4) abaixo, e a região verde é
portanto a região de viabilidade da relaxação linear.


O ótimo da PL é o ponto x = 7/3 7/3 . Suponha que agora foi adicionada a restrição
abaixo, que corresponde à reta (c) da figura.

1 1 x ≤ 4.

Originalmente, havia 6 pontos inteiros que eram viáveis. Eram eles


     
1 1 , 1 2 , 1 3 , 2 1 , 2 2 , 3 1

85
G. Coutinho e C. Arbex Valle DCC035 P.O.

 
Note que todos eles permanecem satisfazendo 1 1 x ≤ 4, mas que o ponto x = 7/3 7/3
não satisfaz. Daı́ consideramos a PI que adiciona esta restrição:

max 1 1 x
   
2 1 7
 1 2  7
   
sujeito a 
 −1 −4  x ≤  −4
  
−1 0 −1/2
1 1 4
x inteiro.

O ótimo desta PI ainda será o mesmo que o da PI original, já que não retiramos qualquer
ponto inteiro da região de viabilidade. Porém ao olharmos para a relaxação
 linear, saberemos
que o seu ótimo será diferente. Basicamente: cortamos x = 7/3 7/3 fora, sem mudar os
pontos inteiros.

• De fato, a relaxação linear da nova PI tem 3 soluções ótimas inteiras.

Esta será nossa estratégia. Acrescentar desigualdades à formulação, chamadas de planos


de corte, de modo que eventualmente o ótimo da relaxação linear se torne inteiro. Corte, no
caso, costuma ser utilizado como sinônimo de restrição.
Observe na figura anterior os cortes (a), (b) e (c). Eles foram adicionados de forma que
todos os pontos extremos do poliedro sejam inteiros. Ao resolver a PL correspondente (cuja
área viável é a área vermelha na figura), obteremos a solução ótima da PI original. A PL
que não corta nenhuma solução inteira da PI original e cujos pontos extremos são todos
inteiros é chamada de envoltória convexa (convex hull) da PI. No caso geral, um número
exponencial (em relação ao número de variáveis do problema) de cortes é necessário para
representar totalmente a envoltória convexa de uma PI.

86
G. Coutinho e C. Arbex Valle DCC035 P.O.

Aula 16
5.4 Planos de corte
Considere o seguinte exemplo.

max 2 5 x
   
1 4 8
sujeito a x≤
1 1 4
x ≥ 0, x inteiro.

A relaxação linear da PI acima pode ser resolvida normalmente, e encontramos a solução


ótima 
x = 8/3 4/3 .
Claramente esta solução não é uma solução da PI. Portanto nosso objetivo agora é encontrar
uma desigualdade do tipo
a1 x 1 + a2 x 2 ≤ b
que seja satisfeita por qualquer solução inteira do problema, mas que não seja satisfeita por
x1 = 8/3 e x2 = 4/3. Uma desigualdade deste tipo será chamada de plano de corte.

No caso, a desigualdade aqui será x1 + 3x2 ≤ 6, correspondente à reta (?) acima. Como
achá-la em geral? Ao resolvermos o simplex na relaxação linear do problema original, teremos
   
1 −2 −5 0 0 0 1 0 0 1 1 12
 0 1 4 1 0 8  ⇒  0 1 0 −1/3 4/3 8/3 
0 1 1 0 1 4 0 0 1 1/3 −1/3 4/3

A segunda linha do tableau significa que


1 4 8
x 1 − x3 + x4 = .
3 3 3

87
G. Coutinho e C. Arbex Valle DCC035 P.O.

Qualquer solução satisfaz essa igualdade! Como as variáveis são não-negativas, reduzir os
coeficientes significa reduzir o valor da soma. Daı́
   
−1 4 8
x1 + x3 + x4 ≤ .
3 3 3

Ou seja
8
x1 − x3 + x4 ≤ .
3
Contudo, estamos preocupado apenas com soluções inteiras. Uma soma de número inteiros
menor ou igual que 8/3 será também menor ou igual a 2. Teremos finalmente a inequação
abaixo, que necessariamente será satisfeita por qualquer solução viável inteira do problema
original:
x1 − x3 + x4 ≤ 2.

Observe que esta desigualdade é violada pela solução ótima da PL, x = 8/3 4/3 . De
fato, um corte obtido desta forma sempre será violado pela solução atual da PL (por que?).
Acrescentamos esta inequação e resolvemos de novo. Ou seja, o novo tableau será:
   
1 0 0 1 1 0 12 1 0 0 1 1 0 12
 0 1 0 −1/3 4/3 0 8/3   8/3 
  ⇒  0 1 0 −1/3 4/3 0 ,
 0 0 1 1/3 −1/3 0 4/3   0 0 1 1/3 −1/3 0 4/3 
0 1 0 −1 1 1 2 0 0 0 −2/3 −1/3 1 −2/3

que resolveremos usando o método dual do simplex!!!


Resumindo...

(i) Resolvemos a relaxação linear original.

(ii) Escolhemos uma das equações que indique uma solução fracionária para uma das
variáveis do problema - necessariamente será uma linha onde o b foi uma fração.

(iii) Trocamos todos os coeficientes desta inequação por b c (cuidado com os negativos!!).

(iv) Acrescentamos a nova equação, e resolvemos o simplex novamente (método dual será
sempre a melhor estratégia).

(v) Se a solução for inteira, acaba. Se não for, repete o passo (ii).

Este algoritmo foi proposto por Ralph Gomory nos anos 50 e estes cortes possuem hoje
o nome de cortes de Gomory. De inı́cio, porém, não era considerado muito prático (até pelo
próprio Gomory) devido a instabilidades numéricas e devido ao enorme número de cortes que
eram necessários no geral para resolver uma PI. A partir dos anos 90, o método foi revisitado
e combinado com o próximo algoritmo que veremos, chamado Branch-and-bound, para
formar o que chamamos de algoritmos Branch-and-cut, bastante efetivos para diversos
problemas. Hoje em dia, todos os solvers implementam cortes de Gomory de uma forma ou
outra.

88
G. Coutinho e C. Arbex Valle DCC035 P.O.

Exercı́cio 71. Suponha que ao resolver a relaxação linear de uma PI, chegamos no seguinte
tableau:  
1 0 0 0 17/12 1/12 5/12 140
 0 1 0 0 111/60 −13/12 −1/60 9/2 
 
 0 0 1 0 1/10 1/2 −1/10 1 
0 0 0 1 2 11/2 −1/12 11/10
Quais inequações podem ser usadas para acharmos planos de corte? Para cada uma delas,
qual o plano de corte correspondente?

Exercı́cio 72. Resolva a PI abaixo pelo método dos planos de corte.



max 3 2 4 x
   
1 1 2 4
sujeito a 2 0 3 x ≤ 5
2 1 3 7
x ≥ 0, x inteiro.

5.5 Branch and bound


Nesta seção, vamos ver outra estratégia para resolver PIs. Suponha que tenhamos o problema
abaixo, a qual nos referiremos como Problema 1.

max 60x1 + 50x2


   
3/2 1 6
sujeito a x≤
9 11 45
x ≥ 0, x inteiro.

O ótimo da relaxação linear deste problema é



x = 14/5 9/5 , valor objetivo 258.

Imaginamos então que o ótimo inteiro tenha valores próximos desses. Vimos que isso
nem sempre é verdade, mas pode ser verdade em alguns casos. Pegamos então uma variável
cujo resultado tenha sido fracionário, e dividimos em dois casos. Por exemplo, a variável x1 .
Claramente x1 ≤ 2 ou x1 ≥ 3. Desta forma, criamos dois subproblemas:

Subproblema 2: Problema 1 + restrição x1 ≥ 3.

Subproblema 3: Problema 1 + restrição x1 ≤ 2.

Temos agora mais duas PLs para resolver, os subproblemas 2 e 3. Sabemos que a solução
inteira ótima é parte de algum destes dois problemas. Podemos visualizar os problemas como
uma árvore, de acordo com a figura abaixo:

89
G. Coutinho e C. Arbex Valle DCC035 P.O.

Prob. original

x1 = 2.8, x2 = 1.8

Valor: 258
x1 ≥ 3 x1 ≤ 2

Subproblema 2 Subproblema 3

Devemos então escolher um dos dois para começar. Vamos escolher o Subproblema 2.
Como já relembramos nesta semana, resolver uma PL após adicionar uma única restrição não
é muito custoso, podemos continuar a partir do tableau do problema  original. Ao resolver,
descobrimos que o ótimo do Subproblema 2 é x = 3 3/2 com valor objetivo 255. A
variável x1 agora é inteira, mas a variável x2 continua fracionária. Podemos então criar mais
dois problemas:

Subproblema 4: Subproblema 2 + restrição x2 ≤ 1.

Subproblema 5: Subproblema 2 + restrição x2 ≥ 2.

A árvore abaixo indica o estágio atual:

Prob. original

x1 = 2.8, x2 = 1.8

Valor: 258
x1 ≥ 3 x1 ≤ 2

Subproblema 2

x1 = 3, x2 = 1.5 Subproblema 3
Valor: 255
x2 ≤ 1 x2 ≥ 2

Subproblema 4 Subproblema 5

Agora possuimos três subproblemas na fila para serem resolvidos, 3, 4 e 5. Vamos seguir
onde estávamos e resolver agora o Subproblema 4. Obtemos como solução x = 10/3 1
com valor objetivo 250. A variável x2 passou a ser inteira, mas x1 voltou a ser fracionária.
Podemos criar então mais dois subproblemas ao ramificar a árvore em x1 :

90
G. Coutinho e C. Arbex Valle DCC035 P.O.

Subproblema 6: Problema 4 + restrição x1 ≤ 3.


Subproblema 7: Problema 4 + restrição x1 ≥ 4.
Novamente, a árvore abaixo mostra a situação atual:

Prob. original

x1 = 2.8, x2 = 1.8

Valor: 258
x1 ≥ 3 x1 ≤ 2

Subproblema 2

x1 = 3, x2 = 1.5 Subproblema 3
Valor: 255
x2 ≤ 1 x2 ≥ 2

Subproblema 4

x1 = 10/3, x2 = 1 Subproblema 5
Valor: 250
x1 ≤ 3 x1 ≥ 4

Subproblema 6 Subproblema 7

Note que o Subproblema 6 é formado pelo problema original mais as restrições x1 ≥ 3, x2 ≤ 1


e x1 ≤ 3 (ou seja, x1 = 3). Vamos resolver este subproblema. 
Ao resolve-lo, encontramos a solução ótima x = 3 1 com valor objetivo 230. Esta
solução é inteira e torna-se nossa primeira candidata a solução inteira ótima. Neste momento,
sabemos que a solução ótima não é menor que 230, mas também sabemos que ela não é maior
que 258. Para tal, verificamos todos os nós da árvore cujos filhos ainda não foram totalmente
resolvidos. O máximo dentre estes valores é o melhor limite superior que possuı́mos no
momento em relação à solução ótima. Neste momento, sabemos que o gap de otimalidade
é 258−230
258
= 10.85%.
Não é mais necessário ramificar a árvore abaixo do Subproblema 6 pois a solução da
relaxação linear já é inteira. Qualquer restrição adicional no caso só poderia piorar a solução
da relaxação ou, na melhor das hipóteses, mante-la no mesmo valor. 
Passamos então ao Subproblema 7. Ao resolve-lo, obtemos a solução ótima x = 4 0
com valor 240. Ela também é inteira e melhor que a solução anterior. Por isso, atualizamos
nossa melhor solução e sabemos agora que o novo gap de otimalidade é 258−240 258
= 7.5%.
Neste lado da árvore, não é necessário descer mais. Voltamos ao problema 5 e, ao resolve-
lo, notamos que ele é inviável (não há solução onde x1 ≥ 3 e x2 ≥ 2. Não precisamos mais
ramificar a árvore neste nó. No momento, a árvore está da seguinte forma:

91
G. Coutinho e C. Arbex Valle DCC035 P.O.

Prob. original

x1 = 2.8, x2 = 1.8

Valor: 258
x1 ≥ 3 x1 ≤ 2

Subproblema 2

x1 = 3, x2 = 1.5 Subproblema 3
Valor: 255
x2 ≤ 1 x2 ≥ 2

Subproblema 4 Subproblema 5

x1 = 10/3, x2 = 1 inviável
Valor: 250
x1 ≤ 3 x1 ≥ 4

Subproblema 6 Subproblema 7

x1 = 3, x2 = 1 x1 = 4, x2 = 0

Valor: 230 Valor: 240

Só nos resta


 agora expandir a árvore no Subproblema 3. O ótimo deste subproblema é
x = 2 2.45 com valor objetivo 242.73. Observe que devemos ramificar a árvore neste nó,
porém note que estamos mais perto da solução ótima: sabemos que o valor ótimo não pode
ser maior que 242.73, o que nos dá um gap de otimalidade de 1.1% apenas. Ramificando no
nó, criamos mais dois problemas:

Subproblema 8: Problema 3 + restrição x2 ≤ 2.

Subproblema 9: Problema 3 + restrição x2 ≥ 3.



Ao resolver o Subproblema 8 obtemos a solução ótima x = 2 2 com valor objetivo 220.
A solução é inteira, não precisa ser ramificada e é pior que a melhor que temos (cujo valor é
240). Podemos descarta-lo e passar para o próximo nó. 
Resolvemos o Subproblema 9 e obtemos a solução x = 4/3 3 com valor objetivo 230.
Esta solução é fracionária e em teoria deverı́amos ramificar a árvore aqui. Porém, será mesmo
necessário? Se já possuı́mos uma solução inteira com valor 240 e sabemos que a inclusão de
novas restrições no Subproblema 9 não melhora a solução, então podemos descartar este nó
pois dali nunca virá uma solução inteira com valor > 240. Este processo é conhecido em
Inglês como pruning the tree, em Português um termo apropriado talvez seja “podar a
árvore”.
Assim, encontramos a solução ótima para o problema. A árvore final pode ser vista
abaixo:

92
G. Coutinho e C. Arbex Valle DCC035 P.O.

Prob. original

x1 = 2.8, x2 = 1.8

Valor: 258
x1 ≥ 3 x1 ≤ 2

Subproblema 2 Subproblema 3
x1 = 3, x2 = 1.5 x1 = 2, x2 = 2.45

Valor: 255 Valor: 242.73


x2 ≤ 1 x2 ≥ 2
x2 ≤ 2 x2 ≥ 3

×
Subproblema 4 Subproblema 5 Subproblema 8 Subproblema 9
x1 = 10/3, x2 = 1 inviável x1 = 2, x3 = 2 x1 = 4/3, x2 = 3

Valor: 250 Valor: 220 Valor: 230


x1 ≤ 3 x1 ≥ 4

Subproblema 6 Subproblema 7

x1 = 3, x2 = 1 x1 = 4, x2 = 0

Valor: 230 Valor: 240

Alguns comentários:

(i) Várias escolhas no processo acima foram arbitrárias. Preferimos fazer uma busca em
profundidade antes, sempre descendo na árvore quando possı́vel. Também escolhemos
começar ramificando em x1 ao invés de x2 . Podemos implementar a mesma idéia com
variações, e estas decisões podem influenciar fortemente na performance do algoritmo.
A busca em profundidade costuma encontrar soluções inteiras mais rapidamente, mas
demora mais para reduzir limite superior e, consequentemente, o gap de otimalidade.
A busca em largura é o oposto.

(ii) O passo em que decidimos não seguir no subproblema 9 é o grande diferencial desde
algoritmo, em comparação a uma simples busca em todos os pontos inteiros. Ele usa
o fato que o ótimo da PI nunca é melhor que o da sua relaxação linear para eliminar a
necessidade de testar vários casos. Pode fazer uma diferença enorme na prática.

(iii) Muitos dos melhores algoritmos comerciais para resolver PIs usam métodos mistos
que combinam branch-and-bound e planos de corte. São os chamados branch-and-cut,
cutting-and-branch, etc. Para grande parte dos problemas inteiros, esta combinação
é hoje a técnica de maior sucesso na resolução destes problemas. A maior instância
já resolvida para o caixeiro viajante possui 85900 cidades e a solução ótima foi obtida
com um branch-and-cut.

(iv) Ainda assim, muitos problemas são desafiadores do ponto de vista computacional. O
branch-and-bound é um algoritmo de enumeração com complexidade exponencial no

93
G. Coutinho e C. Arbex Valle DCC035 P.O.

pior caso. Uma grande área de pesquisa é o desenvolvimento de algoritmos especializa-


dos para resolver PIs especı́ficas. Estes algoritmos podem explorar novas formulações,
novos tipos de cortes, novas regras de ramificação, etc. Podem também utilizar in-
formação do dual da relaxação linear, decompor o problema em problemas menores.
Podem também explorar heurı́sticas para prover uma solução inicial ao branch-and-
bound, o que pode facilitar as podas da árvore.

(v) Em todas as aplicações nesta semana, corremos o risco de precisar resolver um grande
número de PLs. Em todos os casos, usar o método simplex dual é mais eficiente que o
primal - portanto o ganho final de usar este método é enorme.

Exercı́cio 73. Suponha que a árvore abaixo mostra o atual estado na solução de uma PI
via branch and bound. Já é possı́vel determinar a solução final do problema?

Exercı́cio 74. Suponha que se deseja resolver a PI abaixo, cuja região de viabilidade está
desenhada ao lado, em um quadriculado onde cada quadrado tem lado 1/2. Lembre-se que
o ótimo de uma PL sempre se encontra em um vértice da região de viabilidade.

94
G. Coutinho e C. Arbex Valle DCC035 P.O.

3
 
  x
max 8 10  
y
2
sujeita a 2y + x ≤ 6
2x + 2y ≤ 7
1
y + 2x ≤ 6
x, y ≥ 0, x, y ∈ Z.
0

0 1 2 3

Resolva a PI efetuando “branch and bound”.

Exercı́cio 75. Usando branch and bound, resolva a PI abaixo:



max 18 10 6 4 x

sujeito a 12 10 8 6 x ≤ 18
0 ≤ x ≤ 1, x inteiro.

Use o fato que


18/12 > 10/10 > 6/8 > 4/6.

Exercı́cio 76 (Desafio). Considere a PI abaixo, onde n é um inteiro positivo e ı́mpar.

min xn+1
sujeito a 2(x1 + x2 + ... + xn ) + xn+1 = n
0 ≤ x ≤ 1, x inteiro.

Mostre que o método de branch and bound precisa examinar, no caso de piores escolhas
possı́veis, pelo menos 2bn/2c subproblemas antes de resolver o problema.

95
Capı́tulo 6

Formulando programações inteiras

Aula 17
6.1 Problema do caixeiro viajante
Considere o seguinte problema:

• Um caixeiro viajante precisa visitar as cidades 1, 2, ..., n em alguma ordem, e voltar


para a cidade de inı́cio. O custo para ir da cidade i para a cidade j é dada por cij .
Qual volta pelas n cidades possui custo mı́nimo?

Este é o problema do caixeiro viajante, ou TSP (travelling salesman problem). É um dos


problemas mais estudados da Ciência da Computação e foi formulado pela primeira vez pelo
matemático irlandês W. R. Hamilton nos anos 1800s. Em homenagem a ele, uma solução
para o problema que parte da cidade de origem, visita cada uma das n − 1 cidades restantes
uma vez e que volta à cidade de origem é chamada de ciclo Hamiltoniano.
O problema foi formalizado nos anos 1930 (recebendo o nome que tem hoje) e em 1954
Dantzig (o mesmo do Simplex), Fulkerson (do algoritmo de Ford-Fulkerson) e Johnson (deve
ter feito outras coisas boas) publicaram um artigo resolvendo “na mão” uma instância com 49
cidades. Eles formularam o problema como uma PI com diversas restrições especı́ficas para
esta instância em particular e provaram a otimalidade da solução encontrada. Basicamente,
eles adicionaram alguns cortes e fizeram um processo de fixação de valor de algumas variáveis
inteiras em 0 ou 1. Este artigo não descreveu um algoritmo genérico para o TSP, apenas
resolveu esta instância em particular, mas foi um embrião para algoritmos de planos de
corte e provavelmente a primeira vez que um algoritmo semelhante ao branch-and-bound foi
executado. Foi um enorme feito para a época, visto que o número de possı́veis soluções para
o TSP com 49 cidades é 48! ≈ 1.24 × 1061 .

6.1.1 Formulação matemática


Considere que o mapa das cidades que devem ser visitadas pelo caixeiro viajante é modelado
como um grafo direcionado G(V, A) onde V é o conjunto de cidades e A o conjunto de arcos.
Assuma um grafo completo onde para todo par de cidades i, j existam arcos (i, j) e (j, i)

96
G. Coutinho e C. Arbex Valle DCC035 P.O.

conectando as cidades nas duas direções. A cada arco é associada um custo cij e não há
necessariamente simetria nos custos - isto é, pode ser que cij 6= cji .
Caso o grafo real do problema não seja completo (por exemplo, não existe rota direta
entre Rio e Brası́lia sem passar por BH), podemos criar um arco artificial nas duas direções
onde o custo entre Rio e Brası́lia é dada pelo menor custo de um caminho entre as duas
cidades. Seja |V | o número de vértices do grafo (esta notação é geralmente utilizada para
representar a cardinalidade de um conjunto).
Esta versão do problema é chamada de TSP assimétrico. Vamos agora formula-lo como
uma PI:

Variáveis de decisão: Considerando um grafo completo, podemos definir variáveis xij , i, j ∈


V, i 6= j onde xij = 1 se o caixeiro segue de i direto para j, e xij = 0 caso contrário.

Formulação: Gostarı́amos de minimizar o custo total, e garantir que toda cidade será
visitada. Veja o modelo abaixo:

X X
min cij xij
i∈V j∈V,j6=i
X
sujeito a xij = 1, ∀i ∈ V
j∈V,j6=i
X
xij = 1, ∀j ∈ V
i∈V,i6=j

xij ∈ {0, 1}.

As restrições do problema indicam que a partir de toda cidade i o caixeiro viajante deve
seguir viagem para alguma cidade j. Igualmente, se o caixeiro chegou em j, ele tem que ter
vindo de alguma cidade i. Ou seja, em toda cidade, o caixeiro vem de algum lugar e vai para
algum lugar. A formulação está completa?

Infelizmente ainda não! Por exemplo, considere |V | = 6 e assuma a solução x12 = x23 =
x31 = 1, x45 = x56 = x64 = 1 e todos os demais xij = 0. Esta representa uma solução viável
de acordo com o modelo acima, porém não representa um ciclo Hamiltoniano. Diz-se que a
solução acima possui subciclos. Como podemos garantir que o caso acima não aconteça?
Uma possı́vel ideia é adicionar a seguinte restrição ao problema:

x14 + x15 + x16 + x24 + x25 + x26 + x34 + x35 + x36 ≥ 1


A restrição acima diz que o caixeiro deve ir de alguma cidade do lado 1, 2, 3 para outra
cidade do lado 4, 5, 6. Assim, evitarı́amos o subciclo mostrado no exemplo. Claro, precisamos
também garantir que o caixeiro volte de 4, 5, 6 para 1, 2, 3. Porém, ao adicionar apenas a
restrição acima ao modelo, garantimos também que a volta irá acontecer (por que?).

De forma geral, podem haver subciclos envolvendo qualquer subconjunto de V . O subciclo


poderia ocorrer entre 1, 2 e 3, 4, 5, 6, ou poderia ocorrer entre 1, 3, 5 e 2, 4, 6. Temos então

97
G. Coutinho e C. Arbex Valle DCC035 P.O.

que garantir que para todo subcojunto de vértices, pelo menos um arco saia dele em direção
ao complemento desse subconjunto. Podemos adicionar o seguinte conjunto de restrições:
X
xij ≥ 1, ∀W ⊆ V, 1 < |W | < |V | − 1 (6.1)
i∈W, j ∈W
/

O modelo completo fica assim: /


X X
min cij xij
i∈V j∈V,j6=i
X
sujeito a xij = 1, ∀i ∈ V
j∈V,j6=i
X
xij = 1, ∀j ∈ V
i∈V,i6=j
X
xij ≥ 1, ∀W ⊆ V, 1 < |W | < |V | − 1
i∈W, j ∈W
/

xij ∈ {0, 1}.

Para todo subconjunto W de tamanho entre 2 e |V | − 1, garantimos que pelo menos um arco
sairá dele e consequentemente nenhum subciclo ocorrerá.
Uma forma alternativa de representar as mesmas desigualdades de eliminação de subciclos
é através das inequações:
X
xij ≤ |W | − 1, ∀W ⊂ V, 1 < |W | < |V | − 1 (6.2)
(i,j)∈W

Nesta versão, dizemos que o número de arcos entre vértices de W que fazem parte da solução
(xij = 1) deve ser no máximo |W | − 1. Se houvesse |W | ou mais arcos entre vértices do
mesmo subconjunto, obrigatoriamente terı́amos um subciclo.

Exercı́cio 77. Teremos algum problema para obter a relaxação linear da formulação acima?

Neste momento vem a questão: como resolver esta formulação se, mesmo para V relativa-
mente baixo, o número de restrições é tão alto que nem conseguimos escreve-las na memória
do computador mais poderoso que se conhece?

Pela mesma lógica do algoritmo de planos de corte! Geralmente um número exponencial


de planos de corte são necessários para descrever completamente a envoltória convexa de um
problema inteiro. Mas na prática conseguimos em muitos casos encontrar a solução ótima
inteira ao adicionar apenas uma fração dos planos de corte. No caso do TSP, vale a mesma
lógica. Assim temos o seguinte algoritmo Branch-and-cut:

1. Inicie o branch-and-bound para a formulação do TSP sem incluir as desigualdades de


eliminação de subciclos.

2. Resolva o subproblema atual do Branch-and-bound.

98
G. Coutinho e C. Arbex Valle DCC035 P.O.

3. Verifique se pelo menos uma restrição de eliminação de subciclos é violada pela solução
da relaxação linear do subproblema resolvido.

(a) Caso sim, adicione ao modelo uma ou mais dentre as restrições violadas identifi-
cadas e volte ao passo 2, resolvendo novamente o subproblema.
(b) Senão, continue com o branching normalmente.

O que vemos na prática é que é possı́vel terminar o branch-and-bound e provar a otima-


lidade de instâncias de tamanho considerável ao adicionar apenas uma fração pequena do
conjunto completo de desigualdades de eliminação de subciclos. Algoritmos branch-and-cut
baseados nesta formulação são os melhores algoritmos exatos conhecidos para o TSP. Para
mais detalhes, dê uma olhada em:

http://www.math.uwaterloo.ca/tsp/

Ficou apenas uma dúvida: como descobrir se alguma restrição de eliminação de subciclos
é violada pela solução da relaxação linear do subproblema atual? Este problema é chamado
de problema de separação e necessitamos de um algoritmo capaz de resolve-lo. Para o
TSP, há dois casos possı́veis.
Caso 1: Durante a resolução de algum subproblema do branch-and-bound, podemos obter
uma solução desconectada e inteira. Neste caso devemos verificar se o grafo induzido por
aquela solução é conectado. Senão for, podemos utilizar um algoritmo de busca em largura
ou busca em profundidade para encontrar as componentes desconectadas do grafo. Por
exemplo, considere a seguinte solução inteira para o TSP relaxado:

= 1
4 45
1 =

5
46

1
31 = 1
56 = 1
6
1 =

3 8
= 1
1 =
21

78
98

= 1 7
2 23
9
97 = 1

O grafo induzido é aquele que mantém apenas os arcos (i, j) cujo valor xij = 1. No exem-
plo acima, o grafo original é completo, mas todas os arcos omitidos tiveram, na solução
encontrada, xij = 0.

99
G. Coutinho e C. Arbex Valle DCC035 P.O.

Ao realizar a busca em profundidade ou largura, encontraremos três componentes co-


nexas, compostas por W1 = {1, 2, 3}, W2 = {4, 5, 6} e W3 = {7, 8, 9}. Considerando que o
vértice 1 seja a origem do caixeiro, podemos extrair os seguintes cortes para cada componente
conexa:

X X
xij ≤ 2 (6.3)
i∈W2 j∈W2 ,i6=j
X X
xij ≤ 2 (6.4)
i∈W3 j∈W3 ,i6=j

O corte (6.3) indica que no máximo duas arestas devem ser escolhidas no subconjunto W2 ,
senão obteremos um ciclo (como mostrado no exemplo). O corte (6.4) diz o mesmo para o
subconjunto W3 .
Podemos também combinar W2 e W3 fazendo W = W2 ∪ W3 e adicionando:

X X
xij ≤ 5 (6.5)
i∈W j∈W,i6=j

Note que a solução inteira acima, contendo subciclos, viola todas estas restrições. Podemos
adicionar uma restrição para cada componente conexa que não contém a origem, ou uma
restrição geral contendo a união de todas as componentes conexas. A tendência é que a
primeira opção diminua mais a chance de outros subciclos acontecerem, mas pode tornar o
modelo mais pesado por conter mais restrições (no exemplo, adicionarı́amos (6.3) e (6.4). A
segunda opção é o contrário. Por exemplo, se adicionarmos apenas a restrição (6.5), podemos
obter a solução abaixo:

= 1
4 45
1 =

5
46

1
31 = 1
56 = 1
6
1 =

3 8
= 1
1 =
21

78
98

7
2 93 = 1 9
27 = 1

que não viola (6.5) nem (6.4), mas viola (6.3). Se adicionarmos apenas (6.3) e (6.4), a solução
acima não poderia acontecer.

100
G. Coutinho e C. Arbex Valle DCC035 P.O.

Adicionamos a(s) restrição(ões) ao subproblema atual do branch-and-bound e resolvemos


novamente a relaxação linear. Continuamos neste processo enquanto não encontrarmos uma
solução conectada. Além disso, as restrições são adicionadas globalmente, ou seja, elas
valem para todos os subproblemas ainda não explorados. Assim, se ao final do branch-and-
bound encontrarmos uma solução inteira conectada, ela é ótima. A lógica de adicionar o
corte globalmente é que as mesmas componentes desconectadas podem reaparecer em outros
subproblemas da árvore.
Caso 2: Agora imagine que, ao resolvermos a relaxação linear de uma instância de 4 vértices
do TSP sem as restrições (6.2), obtivéssemos o seguinte grafo induzido:

3
1 3

2 2 2 2

3 3 3 3

1 1

3 3

2 4
1

Note que a solução acima não viola nenhuma das demais restrições do TSP: em todo vértice,
entra 1 e sai 1. Porém, observe que se considerarmos W = {3, 4}, obtemos a seguinte
desigualdade do tipo (6.2):

x34 + x43 ≤ 1 (6.6)

Ao substituirmos os valores da relaxação linear, veremos que ela é violada:


2 2 4
+ = >1
3 3 3
Alternativamente, podemos obter a seguinte desigualdade do tipo (6.1):

x41 + x42 + x31 + x32 ≥ 1 (6.7)

Ao substituirmos os valores da relaxação linear, veremos que ela também é violada:


1 1 2
+0+0+ = <1
3 3 3
Porém, todo o grafo é conectado. Existe alguma forma de encontrar possı́veis restrições
violadas em grafos conectados, mas fracionários?

101
G. Coutinho e C. Arbex Valle DCC035 P.O.

A resposta é que sim: no caso do TSP, sabemos que o algoritmo que resolve o problema
de fluxo máximo pode ser utilizado para encontrar estas desigualdades. Como conhecemos
algoritmos polinomiais para resolver este problema, a separação de cortes é polinomial. Veja
abaixo o algoritmo de separação completo, expandindo o passo 3 visto acima:

3. Verificação se restrição de eliminação de subciclos é violada:

(i) Começamos com uma solução viável x para a relaxação da (PI) atual do branch.

(ii) Criamos um grafo dirigido, cada vértice é uma cidade.

(iii) Para cada xij > 0, adicionamos um arco de i para j com capacidade xij .

(iv) Verificamos se o grafo é desconectado a se a solução obtida é inteira. Se ambos os


casos forem verdade, adicionamos os cortes necessários e voltamos ao passo 2. Senão,
continue.

(v) Se 1 é o vértice de origem, calculamos o fluxo máximo de 1 para todos os demais


vértices u do grafo.

(a) Se o fluxo é menor que 1, significa que o corte mı́nimo entre esses vértices é menor
que 1, e portanto existe um subconjunto U contendo u e não contendo 1 tal que
X
xij < 1.
i∈U, j ∈U
/

Neste caso, adicionamos apenas esta restrição à relaxação da (PI) e repetimos.


(b) Se o fluxo é maior que 1, significa que o corte mı́nimo entre esses vértices é maior
que 1, e portanto para todos os subconjuntos U contendo u e não contendo 1,
temos X
xij ≥ 1.
i∈U, j ∈U
/

(vi) Ao final, a depender do que ocorreu, retornaremos ao passo 2. descrito acima, ou


continuaremos com o branch normalmente.

O algoritmo de fluxo máximo é executado muitas vezes: para cada relaxação linear re-
solvida e cujo grafo induzido é conectado e fracionário, resolvemos |V | − 1 vezes o fluxo
máximo. Isto não parece tão eficiente, e na verdade nem é obrigatório: se apenas adicionar-
mos restrições quando encontrarmos soluções inteiras desconectadas, resolvemos o problema
do mesmo jeito. Porém, na prática observamos que uma boa implementação do problema
de separação utilizando fluxo máximo é capaz de acelerar consideravelmente a resolução do
TSP.

Exercı́cio 78. Considere agora um grafo não direcionado G = (V, A) onde há apenas uma
aresta entre i e j com distância dij . Este exemplo implica a simetria nas distâncias entre i, j
e j, i. Reescreva a formulação do TSP baseada em um número exponencial de restrições de
eliminação de subciclos para este caso. Utilize uma notação matemática apropriada.

102
G. Coutinho e C. Arbex Valle DCC035 P.O.

Exercı́cio 79. Desafio Imagine o mapa de uma cidade onde as esquinas são vértices e as
ruas conectando as esquinas são arcos. Pense em algo parecido com um grid. Este grafo
claramente não é completo. Também pode ter ruas que são mão mas não são contra-mão, etc.
Considere um grafo G(V, A) não completo que modele este mapa. Considere também um
caminhão que deve partir de um ponto de origem, entregar encomendas em um subconjunto
K de vértices na cidade (K < V ) e voltar ao ponto de origem.
Escreva uma formulação inteira que não assuma um grafo completo e que encontre a rota
mı́nima para o caminhão. Considere que pode não haver ligação direta entre dois pontos
quaisquer de K.

6.1.2 Formulação alternativa: MTZ (opcional)


A formulação acima, que possui um número exponencial de restrições, é a única forma de
resolver o TSP via Programação Inteira? Na verdade não: existem formulações para o
TSP que possuem um número de restrições polinomial em relação a |V |. Chamamos tais
formulações de compactas, no sentido de que “para instâncias moderadas ou relativamente
grandes, suas restrições cabem inteiramente na memória de um computador comum”. Para
tentar resolver estas formulações, não é necessário um algoritmo branch-and-cut contendo
algoritmos de separação. Porém, veremos nesta seção que uma formulação compacta não é
necessariamente melhor que uma formulação com um número exponencial de restrições.
Em 1960, Miller, Tucker e Zimler propuseram uma formulação compacta que viria a ser
conhecida como formulação MTZ para o TSP. Eles utilizaram variáveis inteiras adicionais
que permitiram reformular o problema com menos restrições. Em conjunto com as variáveis
xij , incluı́ram variáveis inteiras (mas não binárias) ui para todo vértice i ∈ V .
A ideia é a seguinte: Suponha sem perda de generalidade que o caixeiro sempre comece
da cidade 1. Então, u1 = 1. A segunda cidade visitada, chamada de i, deve ter ui = 2.
A terceira visitada, j deve ter uj = 3, e assim sucessivamente. A última cidade k visitada
antes de voltar à origem deve ter uk = |V |. O seguinte conjunto de restrições, que substitui
as desigualdades de eliminação de subciclos acima, garante que isso aconteça:

u1 = 1
2 ≤ ui ≤ |V | ∀i ∈ V, i 6= 1
ui − uj + 1 ≤ (|V | − 1)(1 − xij ) ∀(i, j) ∈ A, i 6= 1, j 6= 1

As primeiras restrições garantem que os ui ’s devem ter valores entre 1 e |V |, com u1 = 1. O


último conjunto de restrições é menos intuitivo, mas verifique você mesmo que ela garante a
sequência de números correta:

• Se xij = 1, isto é, atravessamos o arco (i, j), então o lado direito é zero e temos que
ui + 1 ≤ uj . Ou seja, uj deve ser pelo menos uma unidade maior que ui . O conjuto
completo destas restrições em conjunto com as restrições de limite garantem que se
xij = 1, a diferença uj − ui será efetivamente 1. A sequência será preservada pois
nunca ocorrerão ui ’s repetidos.

103
G. Coutinho e C. Arbex Valle DCC035 P.O.

• Se xij = 0, então temos que a diferença entre ui e uj é pelo menos |V | − 2. Todo par
ui , uj entre 2 e |V | respeita este caso.

Exercı́cio 80. Mostre que o número máximo de restrições que garantem a não ocorrência
de subciclos na formulação MTZ é |V |2 − 2|V | + 1.

Comparação entre formulações


Qual formulação é melhor? Se você tivesse que resolver o TSP, qual escolheria?

Nem sempre é fácil responder a esta pergunta, mas no caso dessas duas formulações para
o TSP possuı́mos uma resposta. Contra-intuitivamente, como mencionado no inı́cio desta
seção, sabemos que a formulação original é objetivamente melhor que a MTZ.
Uma forma objetiva de comparar duas formulações é medir o quão próximo do ótimo
está o valor da relaxação linear de cada uma delas. Vamos fazer isso indiretamente. Ignore
no momento a questão do número exponencial de restrições de eliminação de subciclos na
primeira formulação.
Vamos começar, na MTZ, reordenando os termos das restrições que garantem a sequência
correta dos ui . Considere um arco (i, j) qualquer:

ui − uj + 1 ≤ (|V | − 1)(1 − xij )


ui − uj + 1
≤ 1 − xij
|V | − 1
 
ui − uj + 1
xij ≤ 1 −
|V | − 1
   
uj − ui 1
xij ≤ + 1−
|V | − 1 |V | − 1

Agora imagine um ciclo formado por vértices em um subconjunto W . Este ciclo possui |W |
arcos. Ao somar a restrição acima para todos os arcos do ciclo, temos que:
X  
1
xij ≤ 1 − |W | (6.8)
|V | − 1
(i,j) no ciclo
 
uj −ui
Observe que os termos |V |−1 se cancelam. Para verificar, considere W = (i, j, k) com um
ciclo formado pelos arcos (i, j), (j, k), (k, i). Ao somar os termos:
     
uj − ui uk − uj ui − uk
+ + =0
|V | − 1 |V | − 1 |V | − 1
Agora vamos lembrar a segunda versão da restrição de eliminação de subciclos da primeira
formulação, para o mesmo subconjunto W :

104
G. Coutinho e C. Arbex Valle DCC035 P.O.

X
xij ≤ |W | − 1
(i,j)∈W

Observe como o lado direito da desigualdade (6.2) é mais apertado que o da desigualdade
(6.8). Em especial, 1 > |V|W|−1
|
pois |W | < |V |−1. Restrições mais apertadas podem ser vistas
como uma melhor aproximação da envoltória convexa do problema, e consequentemente
proveem valores de relaxação linear mais próximos do ótimo inteiro.
Geometricamente, ao adicionarmos as variáveis ui , estamos aumentando a dimensão do
problema, o que por outro lado nos permite reduzir o número de restrições. Se para todo
subconjunto W ⊂ V fizermos a mesma soma acima, estamos eliminando totalmente as
variáveis ui da formulação e reescrevendo a mesma como uma formulação com um número
exponencial de desigualdades, mas com dimensão menor. Diz-se que estamos projetando
uma formulação com dimensão maior em uma outra com dimensão menor e a projeção é
equivalente à formulação MTZ original. Como as desigualdades de eliminação de subciclos
são mais apertadas na primeira que na projeção da segunda, podemos inferir que a primeira
formulação é mais forte.
A MTZ não é a única formulação do TSP com um número polinomial de restrições. Há
também, por exemplo, formulações baseadas em fluxo de uma ou múltiplas commodities.
Porém, nenhuma delas é mais forte que a formulação original vista acima.

105
G. Coutinho e C. Arbex Valle DCC035 P.O.

Aulas 18 e 19
6.2 Problema da mochila
Suponha que uma mochila pode carregar o peso máximo b. Existem n tipos de itens, e cada
item tem peso ai > 0, e valor ci . Queremos escolher itens para carregar na mochila que
maximizem o seu valor. Ou seja,
max cT x
X
n
sujeito a ai x i ≤ b
i=1
x ≥ 0, x inteiro.
Exercı́cio 81. Prove que é impossı́vel carregar a mochila com um valor maior do que (ci /ai )b
para todo i. Ache o ótimo da relaxação linear.
Se apenas um item de cada tipo pode ser selecionado, então precisamos forçar x ≤ 1.
Este é o problema da mochila 0-1. Definimos
( )
Xn
K = x ∈ {0, 1}n : ai x i ≤ b .
i=1

Exercı́cio 82.
(a) No problema 0-1, imagine que o item j só tem valor se o item i for levado também.
Como representar este fato na formulação?
(b) Imagine que é necessário levar ao menos i ou j. Como representar isso?
(c) Agora, não podemos levar i e j juntos. Como formular?
Vamos agora apresentar uma formulação alternativa. Um subconjunto C ⊂ {1, ..., n} é
uma cobertura para a mochila se X
ai > b,
i∈C
ou seja, é um subconjunto tal que nem todos os itens cabem na mochila ao mesmo tempo.
O subconjunto C é uma cobertura minimal se, para todo j ∈ C, vale que
X
ai ≤ b.
i∈C\{j}

Em palavras, se removermos qualquer elemento de C, é possı́vel colocar todos os itens res-


tantes na mochila. Considere agora
( )
X
R = x ∈ {0, 1}n : Para todo C cobertura minimal de K, (1 − xi ) ≥ 1.
i∈C
P P
As restrições i∈C (1−xi ) ≥ 1 podem ser equivalentemente reescritas como i∈C xi ≤ |C|−1.

106
G. Coutinho e C. Arbex Valle DCC035 P.O.

Exercı́cio 83. Seja K = {x ∈ {0, 1}3 : 3(x1 + x2 + x3 ) ≤ 5}.


(i) Calcule todos os pontos de K.
(ii) Quais são todas as coberturas minimais?
(iii) Expresse as desigualdades que definem todas as coberturas minimais.
(iv) Expresse todos os pontos de R.
(v) Conclua que otimizar em K é a mesma coisa que otimizar em R.
(vi) Mostre entretanto que as relaxações lineares de K e R são diferentes. Se você fosse
resolver a PI da mochila usando os algoritmos vistos, qual formulação teria sido melhor?
Exercı́cio
 84. Considere
 um problema da mochila 0-1 com n = 3 produtos, pesos a =
3 2 3 , c = 1 1 1 e capacidade da mochila b = 6.
(i) Escreva a formulação tradicional de programação inteira para resolver este problema.
(ii) Escreva a formulação baseada em coberturas minimais para o mesmo problema.
(iii) Calcule (na mão) os valores das relaxações lineares das duas formulações e diga qual é
a mais forte.
Exercı́cio 85. Mostre que, independente do exemplo, sempre teremos que K = R.
Estes exercı́cios mostraram que não existe uma única forma possı́vel de modelar o pro-
blema da mochila, e que a formulação do tipo R, baseada em coberturas minimais, apresenta
um limite de relaxação linear mais apertados que a formulação K, original. Porém, a for-
mulação do tipo R pode possuir um número enorme de restrições, uma para cada possı́vel
cobertura minimal.
Na prática, podemos nos aproveitar das duas formulações utilizando um branch-and-
cut. Em cada nó do branch-and-bound, resolvemos a relaxação linear. Porém, antes de
prosseguir com o branching, executamos um algoritmo de separação para verificar se há
alguma cobertura minimal cuja restrição associada é violada pela solução da relaxação linear.
Se encontrarmos, podemos adiciona-la ao modelo e resolver o mesmo nó novamente, obtendo
um valor menor e que pode reduzir nosso gap de otimalidade, facilitando a poda da árvore
pelo branch-and-bound.

6.3 Problema das “várias mochilas”, ou geração de co-


lunas
Considere o seguinte problema. Um chapa de metal de largura W é cortada em tiras mais
finas. A indústria pode cortar tiras de m larguras diferentes. Ela recebe uma encomenda
de bi tiras de largura wi . Qual o número mı́nimo de chapas ela precisará para cumprir a
demanda?
Vamos supor que p seja um número muito grande, maior do que a quantidade de chapas
que será necessária.

107
G. Coutinho e C. Arbex Valle DCC035 P.O.

Exercı́cio 86. Dê um exemplo de um valor razoável para p.


Temos então que p é o número de chapas disponı́veis, onde assumimos que toda a demanda
pode ser cumprida. Para modelar o problema, podemos definir variáveis de decisão zij que
indicam quantas chapas de largura wi serão cortadas na chapa j, onde i vai de 1 a m e j de
1 a p. Vamos definir também variáveis yj que indicam se a chapa j será utilizada ou não.
Exemplo 19. Imagine que W = 10, m = 3, w1 = 3, w2 = 4, e w3 = 5. Digamos b1 = 4,
b2 = 3 e b3 = 3. Certamente usaremos no máximo 10 chapas. Então teremos variáveis zij
indicando quantas tiras do tipo i serão cortadas da chapa j, e variáveis yj indicando quais
das 10 chapas serão utilizadas. Daı́ teremos:

min y1 + ... + y10


sujeito a 3z1j + 4z2j + 5z3j ≤ 10yj para todo j = 1, ..., 10
zi1 + ... + zi10 ≥ bi , para i = 1, 2, 3
y ∈ {0, 1} z ≥ 0 z ∈ Z.

Ou seja, minimizamos as chapas usadas, garantimos que cada chapa usada seja cortada de
acordo com seu limite, cortamos o mı́nimo de cada tira que precisamos, e garantimos que as
variáveis são inteiros que fazem sentido.
Exercı́cio 87. Escreva a formulação em geral para este problema.
Infelizmente a formulação que você inventou acima não é muito boa na prática. O ótimo
da PI costuma ficar muito longe do ótimo da relaxação linear.
Exercı́cio 88. Por sinal, qual o ótimo da relaxação linear?
Vamos inventar uma nova formulação para o problema. Definimos o conjunto:
( )
Xm
S = s ∈ Zm : wT s ≤ W, s ≥ 0.
i=1

Ou seja, S representa o conjunto de todas as possı́veis maneiras que podemos cortar a chapa
de metal nas larguras limitadas.
Exercı́cio 89. No exemplo acima, liste todos os vetores em S.
Sejam agora xs variáveis inteiras de decisão que indicam quantas vezes utilizaremos a
forma s ∈ S para cortar uma chapa. Então temos a seguinte formulação:

X
min xs
s∈S
X
sujeito a si xs ≥ bi para todo i = 1, . . . , m
s∈S
x ≥ 0 x inteiro.

108
G. Coutinho e C. Arbex Valle DCC035 P.O.

Exercı́cio 90. Pare para ler e entender a formulação acima. Qual o problema desta for-
mulação?
A parte boa é que, na prática, o ótimo da relaxação linear costuma estar muito perto
do ótimo inteiro. As vezes basta apenas arrendondar o ótimo da relaxação linear. Vamos
entender uma estratégia para resolver este problema.
Exercı́cio 91. Escreva a relaxação linear da formulação acima e a sua dual (use variáveis
duais ui para i = 1, ..., m). Note que teremos uma restrição para cada s ∈ S.
O problema dual não possui um número potencialmente enorme de variáveis, mas possui um
número enorme de restrições. Imagine então que no problema original utilizamos apenas um
subconjunto de S, digamos S 0 , para definir variáveis - ou seja, estamos relaxando o problema
ao eliminar diversas variáveis. Então na dual teremos apenas as restrições indexadas por S 0 .
Assuma que resolvemos as relaxações lineares do modelo acima contando apenas com
as colunas em S 0 . Sejam x e u um par primal-dual de soluções ótimas para os problemas
indexados por S 0 . Estendemos x para uma solução viável da relaxação linear fazendo xs = 0
para todo s ∈ S\S 0 .
Exercı́cio 92. Por que esta solução ainda é viável? Por que ela não é necessariamente
ótima?
Exercı́cio 93. Argumente que se u é viável para a dual original, então a nova x estendida
é ótima para a relaxação original (teorema forte? folgas complementares?).
Observe que, no problema dual, relaxamos as seguintes restrições:
X
m
si ui ≤ 1 ∀s ∈ S \ S 0
i=1
Note então que u será ótima para a relaxação original do dual se e somente se o valor
abaixo é no máximo 1 (senão, uma restrição deixada de fora do dual foi violada).

X
max ui si
sujeito a s ∈ S
No dual, u são variáveis e si parâmetros (si diz quantas tiras de tamanho wi serão tiradas
quando utilizarmos a maneira s de cortar uma chapa). Agora, vamos pensar diferente: como
conhecemos a solução do dual u, vamosPtratar os s como variáveis. Queremos encontrar
alguma forma de cortar a chapa s onde si ui > 1, com a condição de que a forma s seja
fisicamente possı́vel de ser executada. Para isso escrevemos o modelo abaixo:

X
max ui si
X
m
sujeito a wi si ≤ W
i=1
s ≥ 0 s inteiro.

109
G. Coutinho e C. Arbex Valle DCC035 P.O.

Observe que temos exatamente o problema da mochila com valores iguais a u, pesos iguais
a w e capacidade igual a W !
Digamos que s∗ seja a solução ótima deste problema. Se o valor da função objetivo de s∗
for maior que 1, então encontramos a restrição do dual que é mais violada pela candidata a
ótimo u. Então adicionamos à variável xs∗ à formulação restrita de (P), ou seja, S 0 = S 0 ∪ s∗ .
Em seguida, repetimos o processo, resolvendo a primal de novo, obtendo o valor dual e
verificando se o ótimo do problema da mochila correspondente é menor ou igual a um.
Exemplo 20. Volte ao exemplo corrente desta seção. Comece com um conjunto S 0 =
{(0, 0, 2), (2, 1, 0)}.
(i) Resolva o programa (P) e (D) de acordo com S 0 , ou seja, resolva o par

min x1 + x2
max 4u1 + 3u2 + 3u3
sujeito a 0x1 + 2x2 ≥ 4
sujeito a 2u3 ≤ 1
(P) 0x1 + 1x2 ≥ 3 (D)
2u1 + 1u2 ≤ 1
2x1 + 0x2 ≥ 3
u ≥ 0.
x ≥ 0.

(ii) Note que o ótimo é x = (3/2, 3) e u = (0, 1, 1/2)


(iii) Resolva agora a PI
max 0s1 + 1s2 + (1/2)s3
sujeito a 3s1 + 4s2 + 5s3 ≤ 10
s ≥ 0 s inteiro.

(iv) Note que o ótimo é s∗ = (0, 2, 0), de valor objetivo 2. Maior do que 1. Portanto
precisamos adicionar este elemento no conjunto S 0 e recomeçar.
(v) Exercı́cio: faça mais uma iteração.

6.4 Alguns truques de formulação


Nesta breve seção, iremos fazer uma revisão de como formular como programação linear ou
inteira algumas funções objetivas.

Valor absoluto
Considere:
X
max cj |xj |
sujeito a Ax ≤ b
x livre.
Como reescrever a PL acima para que seja linear? Dica: transforme cada xj em duas
variáveis.

110
G. Coutinho e C. Arbex Valle DCC035 P.O.

Máximos ou mı́nimos dentro da função objetiva


Imagine que temos várias funções objetivas c1 , ..., cm , e calculamos, para todo k = 1, ..., m,

max ck x
sujeito a Ax ≤ b
x ≥ 0.

Dentre todos eles, queremos o mı́nimo. Ou seja, estamos procurando


m
min max ck x
k=1
sujeito a Ax ≤ b
x ≥ 0.

Como modelar o problema acima como uma única programação linear? Dica: crie uma única
nova variável que limite todas as programações de máximo originais.
Exercı́cio 94. No problema abaixo, estamos procurando o vetor x que satisfaz as restrições
e possui a maior entrada possı́vel.
n
max max xn
k=1
sujeito a Ax ≤ b
x ≥ 0.

Como adaptar o que vimos acima para este problema? Ou seja, quem são os ck ?

Função objetivo fracionária


 
cT x + α
min
dT x + β
sujeito a Ax ≤ b
x ≥ 0.

No caso, α e β são constantes na função objetivo. A função objetivo é não linear, mas
é possı́vel lineariza-la utilizando a transformação de Charnes-Cooper, de 1962. Defina uma
nova variável:
1
t= T
d x+β
Isto não altera as restrições, mas transforma a função objetivo em

min(cT x + α)t
Continuamos tendo um termo não linear. Porém agora podemos definir variáveis y = t · x.
Multiplicando as restrições por t, a formulação passa a ser:

111
G. Coutinho e C. Arbex Valle DCC035 P.O.

min cT y + αt
sujeito a Ay ≤ bt
y≥0
t≥0

Como y ≥ 0 e x ≥ 0, t ≥ 0. Temos também:


1
t= T
=⇒ (dT x + β)t = 1 =⇒ dT y + βt = 1
d x+β
O modelo completo fica:

min cT y + αt
sujeito a Ay ≤ bt
dT y + βt = 1
y≥0
t≥0

Temos agora um problema de programação linear! Ao final, obtemos o vetor solução (y, t).
y
Podemos obter o valor x original ao fazer x = t .

112
Capı́tulo 7

Otimização em grafos

Aula 20
7.1 Grafos
Esta seção está aqui apenas para estabelecer uma notação geral sobre grafos, reutilizando
também a notação introduzida na última seção. Estes conceitos serão utilizados nas próximas
aulas.
Um grafo G(V, E) é um conjunto V de vértices e um conjunto E de arestas entre pares de
vértices. Essas arestas podem ou não ter pesos associados. Se há uma aresta (de peso dife-
rente de 0) entre dois vértices, eles são chamados de vizinhos. A soma dos pesos das arestas
incidentes a um vértice é o seu grau. Se as arestas tem peso unitário, o grau corresponde ao
número de vizinhos do vértice.

1 2
2

Caminhos
Dados dois vértices a e b, um caminho entre a e b é uma sequência de vértices

v0 v1 v2 ...vn

tais que v0 = a, vi é vizinho de vi+1 e vn = b. Um ciclo é um caminho entre a e a tal que


o único vértice que aparece duas vezes é a. O comprimento de um caminho (ou ciclo) é o
número de arestas contido na sua extensão.
Um grafo conexo é um grafo tal que entre quaisquer dois vértices há pelo menos um
caminho. Uma árvore é um grafo conexo sem ciclos.

113
G. Coutinho e C. Arbex Valle DCC035 P.O.

Direcionado
Um grafo é direcionado se cada aresta possui uma direção. Uma aresta com direção é
chamada de arco. Para cada par de vértices definindo um arco, um deles é chamado de
cauda e o outro de cabeça. Neste caso, utilizamos a notação G(V, A) para representar um
grafo com conjunto de vértices V e arcos A.

Matrizes
Nossa maneira favorita de representar grafos será usando matrizes. Há essencialmente dois
tipos de matrizes que representam grafos. Numa matriz de adjacência, linhas e colunas são
indexadas por vértices, e as entradas são 0 se eles não são vizinhos, ou 1 se eles são. No caso
de grafos com peso, trocamos 1 pelo peso da aresta correspondente.
0 1
0 1 1 0 0
B1 0 1 1 0C
B C
A=B B 1 1 0 0 1 C
C
@0 1 0 0 1A
0 0 1 1 0

Alternativamente, podemos representar um grafo com uma matriz de incidência. Neste


caso, linhas são indexadas por vértices, colunas por arestas, e entradas são diferentes de 0
se o vértice incide à aresta. A vantagem desta maneira é que ela permite codificar grafos
dirigidos mais naturalmente. Neste caso, colocamos −1 se o vértice é a cauda do arco, e +1
se é a cabeça.
0 1
+1 1 0 0 0 0
B 1 0 +1 +1 0 0C
B C
N =B B 0 +1 1 0 0 1C
C
@0 0 0 1 +1 0 A
0 0 0 0 1 +1

Cortes
Vamos considerar a seguinte notação. Se S ⊂ V , então δ(S) é o conjunto de arestas que são
incidentes a exatamente um vértice de S (e portanto a um vértice fora de S). Se v ∈ V ,
então δ(v) será simplesmente o conjunto de arestas incidente a v.
Considere o grafo abaixo:

114
G. Coutinho e C. Arbex Valle DCC035 P.O.

Exercı́cio 95. Descreva o conjunto δ({s, a}).


Um st-corte é um conjunto de arestas da forma δ(U ), onde s ∈ U mas t ∈/ U . Note que,
necessariamente, a remoção de um st-corte desconectará s de t no grafo.
Exercı́cio 96. Expresse todos os st-cortes do grafo acima.

Fluxos
Um fluxo em um grafo G(V, A) é uma atribuição de valores para os arcos de um grafo
dirigido tal que, com exceção de uma fonte e um sorvedouro, a entrada é igual à saı́da em
todos os vértices. Ou seja, um vértice, tipicamente chamado s, envia um fluxo através de
cada arco em direção a um vértice t. Todos os vértices do grafo recebem e repassam este
fluxo, sem adicionar ou remover qualquer parte dele. Cada arco, a princı́pio, só transmite
o fluxo em uma determinada direção - portanto o problema é geralmente modelado em um
grafo direcionado, onde os pesos dos arcos representam a capacidade máxima de transmissão.
Considere a figura abaixo:
a
30 25

s 30 10 t
20 15
b

Emparelhamentos
Dado um grafo G = (V, E), um subconjunto M de arestas satisfazendo a propriedade que
nenhum par de arestas de M é incidente a um mesmo vértice é chamado de um empare-
lhamento. Ou seja, M define uma coleção de pares disjuntos de vértices do grafo. Um
emparelhamento é chamado perfeito se todo vértice é incidente a uma aresta de M .

115
G. Coutinho e C. Arbex Valle DCC035 P.O.

Vários problemas podem ser modelados como o problema de achar emparelhamentos em


grafos. Por exemplo, imagine um grafo bipartido onde uma parte são cursos que devem ser
ministrados num determinado horário, e a outra parte são as salas de aula disponı́veis. Uma
aresta existe se a sala tem tamanho suficiente para o curso correspondente. O problema de
alocar cada curso em uma sala é o problema de encontrar um emparelhamento neste grafo.

Coberturas
Uma cobertura por vértices das arestas é uma escolha de alguns vértices tais que todas as
arestas do grafo sejam incidentes a pelo menos um vértice da escolha.
Como exemplo de aplicação, considere as arestas como ruas e os vértices como esquinas.
Queremos colocar câmeras nas esquinas de forma a cobrir o máximo número de ruas. Ao
encontrar a cobertura por vértices mı́nima, escolhemos onde instalar as câmeras com menor
custo.

Exercı́cio 97. Argumente que um tamanho máximo de um emparelhamento é sempre menor


ou igual ao tamanho mı́nimo de uma cobertura por vértices.

Um grafo é chamado de regular se todos os vértices tem o mesmo grau. Um grafo é


bipartido se o conjunto de seus vértices pode ser particionado em dois conjuntos, e dentro
de cada conjunto não há qualquer aresta.

Exercı́cio 98. Prove que um grafo é bipartido se, e somente se, não há qualquer ciclo com
um número ı́mpar de vértices.

Considere nos exercı́cios abaixo a matriz de incidência N como vista acima. Porém, no caso
de um grafo não direcionado, substituı́mos os componentes -1 por 1.

Exercı́cio 99. Dado um grafo G = (V, E) com pesos ce > 0 para cada aresta, formule como
uma PI o problema de achar um emparelhamento que tenha peso máximo (o emparelhamento
não precisa ser perfeito).

Exercı́cio 100. Dado um grafo G = (V, E) e pesos ce > 0, uma cobertura por arestas é um
conjunto de arestas tal que cada vértice do grafo é incidente a pelo menos uma aresta do
conjunto. Formule como uma PI o problema de achar uma cobertura por arestas de peso
mı́nimo.

Exercı́cio 101. Dado um grafo G = (V, E) (sem peso algum), uma cobertura por vértices é
um conjunto de vértices tal que cada aresta do grafo é incidente a pelo menos um vértice do
conjunto. Formule o problema de encontrar uma cobertura por vértices de menor tamanho
possı́vel como uma PI.

Exercı́cio 102. Use dualidade para mostrar que o tamanho máximo de um emparelhamento
é menor ou igual à quantidade mı́nima de vértices necessária para formar uma cobertura por
vértices.

116
G. Coutinho e C. Arbex Valle DCC035 P.O.

Aulas 21 e 22
7.2 Fluxos
Considere a seguinte situação: você deseja ter uma video-conferência com sua colega que se
encontra no Japão. Supondo que vocês não tenham acesso direto a um dos cabos submarinos
que atravessam o Pacı́fico, os dados dessa vı́deo conferência deverão percorrer uma rede de
servidores através do planeta. A questão é: qual a maior quantidade de dados que podem
atravessar a rede?
Naturalmente, modelamos este problema como um problema em grafos. Um vértice,
tipicamente chamado s, envia um fluxo através de cada arco em direção a um vértice t. Todos
os vértices do grafo recebem e repassam este fluxo, sem adicionar ou remover qualquer parte
dele. Cada arco, a princı́pio, só transmite o fluxo em uma determinada direção - portanto
o problema será modelado em um grafo direcionado, e possui uma capacidade máxima de
transmissão. Considere a figura abaixo:

a
30 25

s 30 10 t
20 15
b

Em termos da matriz de incidência, codificamos da seguinte forma. Se um arco “chega”


em um vértice, ela incide como +1. Se ela “sai”de um vértice, ela incide como −1. Dessa
forma, ao olharmos para a matriz, sabemos exatamente a direção de cada arco (e esses sinais
também serão convenientes da modelagem do problema como uma PL):
 
−1 −1 0 0 0 0
+1 0 −1 +1 −1 0
N=  0 +1 +1 −1
.
0 −1
0 0 0 0 +1 +1
As linhas representam na ordem os vértices s, a, b, t.
Um fluxo é uma atribuição de valores para cada arco, digamos dada por um vetor x ∈ B|A| ,
e deve satisfazer duas propriedades: deve ser menor que a capacidade do arco, e com exceção
dos vértices s e t, o fluxo que entra deve ser igual ao que sai. Seja N0 a matriz de incidência
do grafo que tem as linhas correspondentes a s e t removidas. Quando dizemos que para
todos os outros vértices o fluxo que entra é igual ao que sai, estamos dizendo que
 
0 0
Nx= .
0
Dizer que o fluxo é menor do que a capacidade é equivalente a

117
G. Coutinho e C. Arbex Valle DCC035 P.O.

T
x ≤ 30 20 30 10 25 15 .
A função objetivo é o fluxo que sai de s (e que será igual ao que chega em t). Ou seja, o
problema se torna

max xsa + xsb


sujeito a xsa − xab + xba − xat = 0
xsb + xab − xba − xbt = 0
T
0 ≤ x ≤ 30 20 30 10 25 15

Note agora que para cada conjunto de vértices U contendo s e não contendo t, o fluxo máximo
de s para t não pode ser maior que a capacidade das arestas indo de dentro para fora de U .

s t

Em outras palavras: o menor valor possı́vel de todos os st-cortes é um limitante superior


para o valor máximo de um st-fluxo. Veremos a seguir dois fatos extremamente importantes:

(i) Se as capacidades de cada arco são números inteiros, então sempre existe um st-fluxo
de valor máximo em que todo fluxo é inteiro!

(ii) O valor máximo de um st-fluxo é igual ao valor mı́nimo de um st-corte.

Exercı́cio 103. Ache o maior st-fluxo que você consiga no grafo abaixo.

u 1 v
3 3

s 1 2 t
8 2
3
3
w 5 z

Ache o menor st-corte. Deu o mesmo valor? Se sim, é possı́vel melhorar algum deles?

118
G. Coutinho e C. Arbex Valle DCC035 P.O.

7.3 Matrizes totalmente unimodulares


Dada uma matriz qualquer A, dizemos que B é uma submatriz de A se B for obtida após
algumas linhas e/ou colunas de A serem deletadas.
Exercı́cio 104. Escreva todas as submatrizes de tamanho 2 × 2 da matriz abaixo
 
2 1 0
−1 3 4
−2 5 −3
Exercı́cio 105. Quantas submatrizes 2 × 2 uma matriz n × m possui?

• Dizemos que A é uma matriz totalmente unimodular (TU) se o determinante de qual-


quer submatriz quadrada de A não-singular for igual a +1 ou −1. Uma matriz TU
pode ter também submatrizes singulares com determinante igual a zero.

Exercı́cio 106. Quais são os possı́veis números que podem ser entradas de uma matriz
totalmente unimodular?
Exercı́cio 107. Quais são as possı́veis submatrizes 2×2 que podem aparecer em uma matriz
totalmente unimodular?
Exercı́cio 108. A matriz abaixo é totalmente unimodular?
 
1 −1 0
 0 1 1
−1 0 1
Por que se importar com matrizes totalmente unimodulares? Por conta da Regra de
Gabriel1 . A regra diz que:

det(Ai )
Ax = b ⇐⇒ x = A−1 b ⇐⇒ ∀i : xi =
det(A)
onde Ai representa a matriz original A mas com a i-ésima coluna trocada por b.
Note que se a matriz A for totalmente unimodular e o vetor b for inteiro, então toda
solução básica do sistema Ax = b será inteira. Isto ocorre pois para qualquer submatriz
quadrada formando uma base AB , o determinante será −1 ou 1 (considerando o posto
completo da base) e o determinante de AiB será também inteiro.
Desta forma, se possuı́mos uma PI com matriz de restrições A totalmente unimodular e
vetor b inteiro, então ao resolver sua relaxação linear obteremos uma solução básica ótima
que será inteira e resolverá a PL original.

Exercı́cio 109. Encontre todas as soluções do sistema abaixo em que no máximo duas
variáveis sejam diferentes de 0.
   
1 −1 1 0 4
x=
−1 1 0 1 5
1
Gabriel... Cramer

119
G. Coutinho e C. Arbex Valle DCC035 P.O.

Teorema 12. A matriz de incidência de um grafo dirigido é totalmente unimodular.

Demonstração. Vamos mostrar por indução. No caso base, note que todas as matrizes
1 × 1 tem determinante igual a 0, +1 ou −1. Agora suponha que todas as submatrizes de
tamanho r × r tem determinante 0, +1 ou −1. Considere B uma matriz (r + 1) × (r + 1).
Três casos:

• Alguma coluna de B é nula. Então B tem determinante zero.

• Alguma coluna de B tem uma única entrada não-nula. Então fazendo a expansão de
Laplace por coluna, o determinante de B será ± o determinante de uma matriz r × r,
e portanto o de B será 0, +1 ou −1.

• Todas as colunas de B possuem duas entradas não nulas. Neste caso a soma de todas
as linhas de B é 0, e portanto o determinante de B é 0.

Exemplo 21. Considere a matriz do exemplo anterior:


 
−1 −1 0 0 0 0
+1 0 −1 +1 −1 0
N=  0 +1 +1 −1
.
0 −1
0 0 0 0 +1 +1

Teorema 13. Seja M uma matriz totalmente unimodular. Então

(i) MT é totalmente unimodular.

(ii) (M|I) é totalmente unimodular.

(iii) (M|0) é totalmente unimodular.

(iv) Qualquer submatriz de M é totalmente unimodular.

Agora vamos formalizar o resultado discutido anteriormente para alguns tipos de PLs:

Teorema 14. Seja M uma matriz totalmente unimodular. Se cada uma das PLs abaixo for
limitada e viável, então existem soluções ótimas que são inteiras.

(i) max cT x com Mx = b e x ≥ 0, desde que b seja inteiro.

(ii) max cT x com Mx = 0 e 0 ≤ x ≤ d, desde que d seja inteiro.

(iii) min dT y com (M|I)y ≥ c, desde que c seja inteiro.

120
G. Coutinho e C. Arbex Valle DCC035 P.O.

A idéia do teorema acima é que as soluções ótimas básicas das PLs são obtidas resolvendo
sistemas de equações formados por submatrizes de M quadradas, isto é, com o mesmo número
de variáveis e equações, e portanto unimodulares. Se o lado direito é inteiro, soluções desses
sistemas só podem ser inteiras devido à Regra de Cramer.

Teorema 15. Em um problema de achar o fluxo máximo com capacidades inteiras nos arcos,
qualquer solução básica ótima será um fluxo inteiro.

Demonstração. Segue basicamente do fato que o problema é modelado com uma PL do


tipo

max dT x
sujeito a Mx = 0
0 ≤ x ≤ c,

onde M é uma matriz totalmente unimodular.

7.3.1 Exemplo
Exercı́cio 110. Escreva a PL seguinte, correspondente à figura abaixo, no formato matricial.
Em seguida escreva a sua dual.

max x1 + x2
sujeito a x1 − x3 + x4 − x5 = 0
x2 + x3 − x4 − x6 = 0
T
0 ≤ x ≤ 30 20 30 10 25 15

a
30 25

s 30 10 t
20 15
b

121
G. Coutinho e C. Arbex Valle DCC035 P.O.

Teremos

max 1 1 0 0 0 0 x
   
1 0 −1 1 −1 0 = 0
0 1 1 −1 0 −1 =  0
   
1 0 0 0 0 0 ≤ 30
   
0 1 0 0 0 0 ≤ 20
sujeito a  x  
0 0 1 0 0 0 ≤ 30
   
0 0 0 1 0 0 ≤ 10
   
0 0 0 0 1 0 ≤ 25
0 0 0 0 0 1 ≤ 15
x ≥ 0.
Cuja formulação dual é:
T
min 0 0 30 20 30 10 25 15 y
   
1 0 1 0 0 0 0 0 1
 0 1 0 1 0 0 0 0  
 1
−1 1 0 0 1 0 0 0  
sujeito a  y ≥ 0
 1 −1 0 0 0 1 0 0 0
   
−1 0 0 0 0 0 1 0 0
0 −1 0 0 0 0 0 1 0
y 1 , y 2 livres, e y 3 , ..., y 8 ≥ 0
Note os fatos a seguir a respeito do dual:
(i) Está no formato do item (iii) do Teorema 14, logo qualquer solução básica ótima será
inteira. Ou seja, os itens (ii) e (iii) são um par primal-dual.
(ii) Pela regra de Cramer e uma vez que o vetor de restrições só tem entradas iguais a +1
ou 0, os valores da solução serão +1 ou 0.
(iii) As duas primeiras colunas da matriz correspondem aos dois vértices diferentes de s e
t (no caso, a e b) e as demais à cada arco do grafo. Seja U o conjunto de vértices cujo
valor foi igual a +1, adicionado de s.
(iv) As linhas da matriz correspondem aos arcos. Se u ∈ U (ou seja, y u = 1) então a
linha correspondente a qualquer arco saindo de u terá um −1. Se o vértice de chegada
também está em U , então fica −1 + 1 = 0, ok. Se o vértice de chegada não está em U ,
teremos que adicionar a variável correspondente a este arco.
(v) Ou seja: as entradas iguais a +1 na solução identificarão um conjunto de vértices U e
um conjunto de arcos que vão de dentro pra fora deste conjunto, ou seja, δ − (U )2 , que
é exatamente um st-corte. O valor objetivo da solução será precisamente a soma das
capacidades deste conjunto.
2
Se em um grafo não direcionado δ(U ) é o conjunto de arestas entre U e o complemento de U , em um
grafo direcionado podemos extrapolar a notação e definir δ − (U ) como os arcos que saem de U para seu
complemento e δ + (U ) como os arcos que chegam em U vindos do complemento.

122
G. Coutinho e C. Arbex Valle DCC035 P.O.

(vi) Se as capacidades não fossem necessariamente inteiras, toda a análise das regiões viáveis
acima valeria - a única diferença é que o valor objetivo do corte seria possivelmente
não-inteiro.

Através do exemplo acima, o teorema a seguir fica claro:


Teorema 16. O valor máximo de um st-fluxo é igual ao valor mı́nimo de um st-corte.
Exercı́cio 111. Volte ao exercı́cio 103. Escreva as PI’s correspondentes aos problemas de
achar um st-fluxo máximo e um st-corte mı́nimo, em formatos correspondentes ao Teorema
14. Exiba as soluções x e y, e verifique que (1) x é inteira; (2) y identifica um corte, como
feito acima; (3) ambos os ótimos das PLs são iguais.
Exercı́cio 112. Se um arco pertence a um st-corte de capacidade mı́nima, o que podemos
dizer a respeito do fluxo através deste arco em um st-fluxo de valor máximo?
Exercı́cio 113. É verdade que os arcos cujo fluxo é igual à sua capacidade são os que
pertencem a um corte mı́nimo?

7.4 O método de Ford e Fulkerson — um algoritmo


primal-dual (leitura opcional)
Como vimos, para resolver um problema de fluxo-máximo em uma rede direcionada, é sufi-
ciente resolver a programação linear. Isso pode ser feito de forma satisfatoriamente eficiente,
através do simplex, por exemplo. Entretanto, por ser um problema tão relevante e ubı́quo,
métodos especı́ficos para o problema de fluxo máximo existem. O mais antigo e famoso deles
é o método de Ford e Fulkerson.
Explicaremos a seguir como funciona. Primeiro, faremos a descrição combinatória. De-
pois entenderemos como este método na verdade pode ser visto como uma maneira de resolver
as programações primais e duais baseados nas condições de folga complementares.

(a) Como entrada do problema, temos um grafo dirigido G, com uma fonte s e sorvedouro
t. Todos os arcos possuem uma capacidade.

a 4 b

10 10

S 2 8 6 T

10
10
c 9 d

(b) Começamos com um fluxo viável. No caso, o óbvio: o fluxo em todos os arcos igual
a 0. Para auxı́lio na visualização, colocarei ao lado direito o grafo com a capacidade
disponı́vel.

123
G. Coutinho e C. Arbex Valle DCC035 P.O.

a b a b
0 4
0 0 10 10

S 0 0 0 T S 2 8 6 T

0 0 10
0 9 10
c d c d

(c) Encontramos então um caminho de s para t cuja capacidade disponı́vel seja positiva
em todos os arcos. Aumentamos o fluxo o máximo possı́vel, e diminuı́mos a capacidade
disponı́vel de acordo.

a b a b
0 4
8 0 2 10

S 0 8 0 T S 2 0 6 T

0 8 10
0 9 2
c d c d

(d) Repetimos.

a b a b
0 4
8 0 2 10

S 0 8 0 T S 2 0 6 T

2 8
2 10 7 0
c d c d

(e) O ponto crucial do algoritmo de Ford e Fulkerson é que estes caminhos não precisam
ter a mesma direção dos arcos. De fato, podemos achar um arco no sentido oposto ao
caminho, e ao invés de aumentarmos o fluxo neste arco, iremos diminuir. Portanto: nos
arcos na mesma direção do caminho, precisamos ter capacidade disponı́vel (logo algo
> 0 no grafo da direita). Nos arcos no sentido oposto, precisamos ter fluxo disponı́vel
para retirar (logo algo > 0 no grafo original, na esquerda).

124
G. Coutinho e C. Arbex Valle DCC035 P.O.

a b a b
4 4 0
8 2 6

S 0 4 0 T S 2 4 6 T

6 4
6 10 3 0
c d c d

(f) Concluı́mos então repetindo os passos acima, sempre que possı́vel. No caso abaixo,
acabamos escolhendo mais dois caminhos onde somente fizemos aumentar o fluxo em
qualquer arco.

a b a b
4 6 0
10 0 4

S 0 6 2 T S 2 2 4 T

6 4
6 10 3 0
c d c d

a b a b
4 9 0 1
10 0

S 0 6 5 T S 2 2 1 T

9 1
9 10 0 0
c d c d

Observação: Os passos de “encontrar o caminho”foram descritos de modo abstrato,


motivo pelo qual nos referimos ao Método de Ford e Fulkerson, e não Algoritmo. Ao
fazer estas escolhas, determinamos qual foi a prioridade para escolher os caminhos. Por
exemplo, se usarmos BFS, o algortimo é então conhecido como Edmonds-Karp, e tem
complexidade O(|E|2 |V |).

Note que em cada passo, o algoritmo sempre aumenta o valor do fluxo em pelo menos
uma unidade. Portanto não é possı́vel que ele não termine.
Vamos agora entender como este algoritmo pode ser visto como um algoritmo de atua-
lização de valores de variáveis primal-dual.

125
G. Coutinho e C. Arbex Valle DCC035 P.O.

Neste exemplo acima, temos:



max 1 1 0 0 0 0 0 0 0 x
   
1 0 −1 −1 −1 0 0 0 0 = 0
0 0 0 1 0 0 1 −1 0 =  0
   
0 1 1 0 0 −1 0 0 0 =  0
   
0 0 0 0 1 1 −1 0 −1 =  0
   
1 0 0 0 0 0 0 0 0 ≤ 10
   
0 1 0 0 0 0 0 0 0 ≤ 10
   
sujeito a 0 0 1 0 0 0 0 0 0 ≤  2
 x  
0 0 0 1 0 0 0 0 0 ≤  4
   
0 0 0 0 1 0 0 0 0 ≤  8
   
0 0 0 0 0 1 0 0 0 ≤  9
   
0 0 0 0 0 0 1 0 0 ≤ 10
   
0 0 0 0 0 0 0 1 0 ≤  6
0 0 0 0 0 0 0 0 1 ≤ 10
x ≥ 0.
Cuja formulação dual é:
T
min 0 0 0 0 10 10 2 4 8 9 10 6 10 y
   
1 0 0 0 1 0 0 0 0 0 0 0 0 1
 0 0 1 0 0 1 0 0 0 0 0 0 0  1
   
 −1 0 1 0 0 0 1 0 0 0 0 0 0  0
   
 −1 1 0 0 0 0 0 1 0 0 0 0 0  0
   
sujeito a  −1 0 0 1 0 0 0 0 1 0 0 0 0  y ≥ 0
   
 0 0 −1 1 0 0 0 0 0 1 0 0 0  0
   
 0 1 0 −1 0 0 0 0 0 0 1 0 0  0
   
 0 −1 0 0 0 0 0 0 0 0 0 1 0  0
0 0 0 −1 0 0 0 0 0 0 0 0 1 0
y 1 , ..., y 4 livres, e y 3 , ..., y 11 ≥ 0
(a) Começamos com as soluções abaixo, de mesmo valor objetivo.

xT = 0 0 0 0 0 0 0 0 0

yT = 1 1 1 1 0 0 0 0 0 0 0 0 0
Note que as condições de folga complementares estão “satisfeitas”, mas que y não é
viável. Lembre-se que as primeiras quatro variáveis do y correspondem a vértices. O
fato de eles serem 1 indicam para nós que este vértice é “alcançável”a partir de s. Iremos
agora atualizar ambas as soluções, de modo que as CFC permaneçam “satisfeitas”, mas
que y se aproxime de ser viável.
(b) Aumentamos o x. Ainda não é possı́vel alterar o y.

xT = 8 0 0 0 8 0 0 0 8

yT = 1 1 1 1 0 0 0 0 0 0 0 0 0

126
G. Coutinho e C. Arbex Valle DCC035 P.O.

(c) Sempre que possı́vel, atualizaremos o y para que se torne mais viável.

xT = 8 2 0 0 8 2 0 0 10

yT = 1 1 1 1 0 0 0 0 0 0 0 0 1

(d) Nada se altera no y. Todos os vértices permanecem “alcançáveis”, e não é possı́vel


aumentar a penúltima variável sem destruir as CFC.

xT = 8 6 0 4 4 6 0 4 10

yT = 1 1 1 1 0 0 0 0 0 0 0 0 1

(e) O vértice (a) deixou de ser “alcançável”. Seu 1 é removido. Para não piorar a viabilidade,
podemos adicionar uma aresta, e nota que isso não piora as CFC (pois (a) deixou de ser
alcançável com uma aresta que ficou satisfeita com igualdade).

xT = 10 6 0 4 6 6 2 6 10

yT = 0 1 1 1 1 0 0 0 0 0 0 0 1

(f) Os vértices (d) e (b) deixaram de ser “alcançáveis”. Seus 1s são removidos. Note que (d)
ainda é “vizinho”de vértices alcançável, portanto precisamos compensar aquela aresta.
Os vértices não alcançáveis porque não tem vizinhos alcançáveis não criam problemas.
A aresta que havia sido adicionada para o (d) deve ser removida junto com ele.

xT = 10 9 0 4 6 9 5 9 10

yT = 0 0 1 0 1 0 0 0 0 1 0 0 0

Note que as CFC permanecem válidas, mas y ficou viável. Ademais, o vetor y indica
precisamente um corte de valor mı́nimo: U = {S, c} com as arestas 1a e 6a definindo o
corte, de valor 19.

127
G. Coutinho e C. Arbex Valle DCC035 P.O.

Aulas 23 e 24
7.5 Emparelhamentos e coberturas
Relembrando:

• Dado um grafo G = (V, E), não direcionado, um emparelhamento M é um subconjunto


de E tal que nenhum vértice do grafo é incidente a duas arestas de M .

Um emparelhamento é chamado de perfeito se todo vértice do grafo é incidente a exata-


mente uma aresta do emparelhamento. Em geral, estaremos interessados em dois tipos de
questões acerca de emparelhamentos:

(i) Qual é o emparelhamento máximo? Aqui, “máximo”pode significar “de maior tama-
nho”ou “de maior custo”.

(ii) Qual é o emparelhamento perfeito de custo mı́nimo? Aqui, assumimos que existe um
emparelhamento perfeito, e dentre todos eles procuramos o de custo mı́nimo.

Seja N a matriz de incidência do grafo não direcionado. Por exemplo, para o grafo:

a matriz correspondente é:


 
1 1 0 0 0 0
0 0 1 1 0 0
 
0 0 0 0 1 1
N=
1

 0 0 0 0 1

0 1 1 0 0 0
0 0 0 1 1 0
A matriz de incidências em um grafo não direcionado não é necessariamente totalmente
unimodular. Por exemplo, note que a matriz de incidências de um grafo completo com três
vértices possui determinante igual a 2:
 
1 1 0
N = 1 0 1
0 1 1
Para responder a pergunta (i) ali em cima, formulamos a PI:

128
G. Coutinho e C. Arbex Valle DCC035 P.O.

max cT x
sujeito a Nx ≤ 1
x≥0
x inteiro.
No caso, x é vetor de variáveis de decisão indicando se a aresta e ∈ E faz parte do empare-
lhamento ou não.
Quando c = 1, estamos basicamente buscando o emparelhamento de maior cardinalidade.
As desigualdades Nx ≤ 1 dizem precisamente que para cada vértice, a soma das variáveis
em x correspondentes às arestas incidentes àquele vértice é menor ou igual a 1. Se essas
variáveis forem 0 ou 1, então necessariamente apenas uma delas poderá ser positiva, e esta
será a aresta escolhida para o emparelhamento.
No caso da segunda pergunta, a formulação será

min cT x
sujeito a Nx = 1
x≥0
x inteiro.
Aqui codificamos o fato de que o emparelhamento procurado é perfeito, uma vez que Nx = 1
diz que para cada vértice, exatamente uma aresta incidente a ele será escolhida. Note que
se tivéssemos escrito simplesmente Nx ≤ 1, a solução da PL seria trivialmente x = 0.

Dual - cobertura por vértices


No problema da cobertura por vértices, estamos interessados em escolher vértices de modo
que todas as arestas do grafo sejam incidentes a pelo menos um vértice da escolha. Ou seja,
vamos atribuir valores de 0 ou 1 para os vértices, e para cada aresta, vamos somar os dois
valores dos vértices nos quais ela incide. Essa soma precisa ser pelo menos 1. Neste problema
de otimização, a pergunta natural é: qual a cobertura por vértices de menor tamanho?

min 1T y
sujeito a NT y ≥ 1
y≥0
y inteiro.
Note que, ignorando as restrições de integralidade, a formulação acima é precisamente
a dual da relaxação linear do problema de emparelhamento de cardinalidade máxima. Pelo
teorema fraco da dualidade, temos que:
cardinalidade de emparelhamento máximo ≤ cardinalidade de cobertura mı́nima.
Vamos ver abaixo uma classe abrangente de grafos onde a relação acima é, na verdade,
uma igualdade. O motivo será, novamente, a total unimodularidade.

129
G. Coutinho e C. Arbex Valle DCC035 P.O.

Grafos bipartidos
Vamos relembrar o problema de atribuição. Considere F funcionários para os quais T tarefas
são atribuı́das (|F | = |T |). Cada funcionário i gasta cij horas para executar cada tarefa j.
Relembrando a formulação, temos variáveis xij = 1 caso o funcionário i seja atribuı́do à
tarefa j, 0 caso contrário. A formulação é dada por:

XX
min cij xij
i∈F j∈T
X
sujeito a xij = 1 ∀i ∈ F
j∈T
X
xij = 1 ∀j ∈ T
i∈F
x ∈ B.

Observe que podemos modelar este problema como um problema em grafos ao definirmos
um grafo G = (V, E) onde V = F ∪ T e para cada possı́vel atribuição de funcionário à tarefa
criamos uma aresta e ∈ E conectando um vértice em F a um vértice em T . O problema de
atribuição se resume a encontrar um emparelhamento perfeito de custo mı́nimo neste grafo
(confira que a formulação acima é equivalente à formulação discutida anteriormente).
Observe que em G não há arestas conectando vértices em F e nem arestas conectando
vértices em T . Diz-se que o grafo correspondente é portanto bipartido. O grafo mostrado
na figura acima é um exemplo de grafo bipartido (repetido aqui por conveniência):

Estes grafos são importantes pois sua matriz de incidência possui a propriedade de total
unimodularidade.

Teorema 17. Se G é um grafo bipartido e N é a sua matriz de incidência vértice × aresta,


então N é totalmente unimodular.

Demonstração. Vamos mais uma vez provar por indução. Novamente suponha que todas
as submatrizes de tamanho r × r possuem determinante 0, +1 ou −1 e considere B uma
matriz (r + 1) × (r + 1) No caso base, toda matriz 1 × 1 possui determinante 1 ou 0. De
novo, temos três possibilidades para B:

• B possui uma coluna com apenas zeros: Então o determinante é zero.

130
G. Coutinho e C. Arbex Valle DCC035 P.O.

• B possui alguma coluna com exatamente um 1: Então pela expansão de Laplace por
colunas, o determinante de B será ± o determinante de uma matriz r × r, e portanto
o de B será 0, +1 ou −1
• B possui todas as colunas com dois 1’s e os demais elementos iguais a zero. Como o
grafo é bipartido, podemos particionar a matriz B em duas onde todos os elementos
de um lado do grafo estão numa partição e todos do outro estão em outra partição, de
forma que cada partição contenha apenas um valor 1 por coluna. Multiplicamos uma
das partições por −1 e somamos todas as linhas de ambas as partições. O resultado é
zero e com isso mostramos que as linhas são linearmente dependentes e o determinante
é zero.
Por conta do teorema acima, sabemos que sempre será possı́vel encontrar soluções ótimas
para problemas de otimização de emparelhamentos em grafos bipartidos resolvendo as re-
laxações lineares das PIs correspondentes. Temos então o Teorema de Konig:
Teorema 18. Em um grafo bipartido, o tamanho de um emparelhamento máximo é igual
ao tamanho de uma cobertura por vértice mı́nima.
Demonstração. Considere as programações lineares abaixo:
max 1T x min 1T y
(P) sujeito a Nx ≤ 1 (D) sujeito a NT y ≥ 1
x≥0 y ≥ 0.
A matriz N é totalmente unimodular, assim como N T . Logo há soluções ótimas que são
inteiras para ambas as programações, portanto o valor objetivo ótimo de (P) é o tamanho
de um emparelhamento máximo, ao passo que o valor objetivo ótimo de (D) é o tamanho
de uma cobertura por vértices mı́nima. Como este é um par primal-dual, estes valores são
iguais.
Apesar do fato de que resolver PLs é suficiente para resolver problemas de emparelha-
mento em grafos bipartidos, há algoritmos famosos. O mais tradicional é o método Húngaro
(década de 50), que usa uma estratégia primal-dual para encontrar um emparelhamento
perfeito de custo mı́nimo.

Grafos gerais (não necessariamente bipartidos)


Para grafos gerais, a relaxação linear da PI possui vértices que não são inteiros. Por exemplo,
considere um grafo completo com 3 vértices (um triângulo). A solução da relaxação linear da
formulação que busca o emparelhamento de cardinalidade máxima e e matriz de incidência
N do grafo são dadas por:

131
G. Coutinho e C. Arbex Valle DCC035 P.O.

A solução inteira é 1, mas a solução da relaxação é 32 .


É possı́vel provar, porém, que existe uma solução ótima para a relaxação onde todas as
variáveis possuem valores 0, 1 ou 12 . A partir disto é possı́vel descrever todas as desigualdades
que delimitam os pontos inteiros, mas se fizermos isto obteremos um número exponencial
de desigualdades. Entretanto, há um famoso algoritmo (Algoritmo Blossom de Edmonds de
1961) que resolve o problema de achar emparelhamentos máximos em grafos quaisquer em
O(|V |2 |E|).

7.5.1 Cobertura por vértices em grafos quaisquer


(este é um material de leitura opcional)
Considere a relaxação linear da PI que procura a cobertura mı́nima por vértices

min 1T y
sujeito a NT y ≥ 1
y ≥ 0.

Assuma que y seja uma solução viável, e assuma que existe uma entrada de y que é diferente
de 0, 1/2 ou 1. Ou seja, existe v ∈ V (G) tal que

yv ∈
/ {0, 1/2, 1}.

Seja V + = {v ∈ V (G) : 1/2 < y v < 1}, e V − = {v ∈ V (G) : 0 < y v < 1/2}. Seja  pequeno
o suficiente, e defina dois vetores z + e z − tais que

 y v +  se v ∈ V + ,
+
zv = y −  se v ∈ V − ,
 v
yv caso contrário.

 y v −  se v ∈ V + ,

zv = y +  se v ∈ V − ,
 v
yv caso contrário.
Note que

(i) z + é viável. De fato, se  for pequeno o suficiente, então z + ≥ 0. Ademais, seja uv


uma aresta. Se originalmente y u + y v > 1, então com  pequeno o suficiente, ainda
teremos z + +
u + z v > 1. Se y u + y v = 1, então ou ambos eram iguais a 1/2, e neste caso
nada mudou em z + , ou um deles era maior 1/2 e o outro menor. Mas então z + somou
e subtraiu , e nada mudou.

(ii) O mesmo vale para z − .

(iii) y é combinação convexa de z + e z − . Portanto y não pode ser vértice do poliedro.

Exercı́cio 114. Como exatamente você escreve y como combinação convexa de z + e z − ?

132
G. Coutinho e C. Arbex Valle DCC035 P.O.

Como consequência da discussão acima, temos que as soluções ótimas de

min 1T y
sujeito a NT y ≥ 1
y ≥ 0.

tem entradas iguais a 0, 1/2 ou 1.

Exercı́cio 115. Mostre como é possı́vel usar a informação acima para achar uma cobertura
por vértices das arestas de tamanho no máximo duas vezes a ótima, resolvendo apenas uma
programação linear.

7.5.2 Problema do transporte


Suponha que uma companhia possua m centros de distribuição e n pontos de varejo, e
deseje transportar produtos dos centros de distribuição para os pontos de varejo. Cada
um dos centros de distribuição possui um estoque, cada um dos pontos de varejo possui
uma demanda, e o custo de transportar produtos entre cada centro de distribuição para
cada ponto de varejo são conhecidos. Como, portanto, modelar o problema de realizar essa
distribuição com custo mı́nimo?

• Suponha que o estoque de cada centro seja dado por Si , com i = 1, ..., m.

• Suponha que a demanda de cada ponto seja dada por Dj , com j = 1, ..., n.

• Suponha que o custo de transportar um produto do centro i para o ponto j seja dado
por cij .

• Defina variáveis xij que determinarão quanto será transportado de i para j, onde
i = 1, ..., m e j = 1, ..., n.

Com as definições acima, fica fácil modelar o problema:


X
m X
n
min xij cij
i=1 j=1
X
m
sujeito a xij ≥ Dj para todo j = 1, .., n,
i=1
X
n
xij ≤ Si para todo i = 1, ..., m,
j=1

xij ≥ 0,
xij ∈ Z.

Exercı́cio 116. Seja D a demanda total, ou seja, D = D1 + ... + Dn , e seja S o estoque


total, ou seja, S = S1 + ... + Sm . Naturalmente, se a empresa consegue suprir a demanda em
cada ponto, então S ≥ D. Assuma que a empresa pode descartar o excesso de estoque, ou

133
G. Coutinho e C. Arbex Valle DCC035 P.O.

seja, assuma que S = D. Mostre que, neste caso, podemos reescrever a formulação acima
trocando todas as desigualdades por igualdades sem qualquer prejuı́zo na modelagem do
problema.

Pelo exercı́cio acima, a formulação do problema de transporte pode ser expressa por
X
m X
n
min xij cij
i=1 j=1
Xm
sujeito a xij = Dj para todo j = 1, .., n,
i=1
Xn
xij = Si para todo i = 1, ..., m,
j=1

xij ≥ 0,
xij ∈ Z.

Exercı́cio 117. Considere um grafo dirigido com dois tipos de vértices: um representa os
centros, e o outro representa os pontos de venda. Conecte com arcos dirigidos todos os
centros aos pontos de venda. Seja N a matriz de incidência deste grafo dirigido.

(i) Modele a PI acima no formato:

min cT x
sujeito a Nx = b
x≥0
x inteiro.

Ou seja, explicite o que significam c, x e b.

(ii) Mostre que as soluções da relaxação linear são inteiras se os estoques e demandas forem
inteiros.

Exercı́cio 118. Reduza o problema de transporte a um problema de fluxo entre dois vértices
s e t.

134
G. Coutinho e C. Arbex Valle DCC035 P.O.

7.6 Um algoritmo primal-dual para emparelhamento


perfeito de menor custo
Um dos exercı́cios da lista 8 era o conhecido Teorema de Hall, que caracteriza grafos bipar-
tidos que possuem emparelhamentos perfeitos:

Teorema 19 (Hall). Em um grafo bipartido, seja A e B os conjuntos de vértices de cada


lado. Suponha que |A| = |B|.

Então existe um emparelhamento perfeito se, e somente se, para todo subconjunto S
de vértices em A, o número total de vizinhos desses vértices em B é maior ou igual
que |S|.

Vamos agora usar este resultado e uma estratégia primal-dual para resolvermos (exata-
mente) o problema de encontrar um emparelhamento perfeito de grau mı́nimo em um grafo
bipartido. Relembre a formulação como PI deste problema (suponha que c ≥ 0).

min cT x
sujeito a Nx = 1
x≥0
x inteiro.

A dual da relaxação linear:

max 1T y
sujeito a NT y ≤ c
y livre.

Exercı́cio 119. Explique com palavras o que a dual está encontrando no grafo.

Lembre-se agora que a matriz N é totalmente unimodular. Logo, se a PI for viável,


há soluções ótimas para a sua relaxação linear que são inteiras, e portanto satisfarão as
condições de folga complementares com um ótimo da dual.

Exercı́cio 120. O que dizem as condições de folga complementares?

Exercı́cio 121. Encontre uma solução viável para a dual que não seja muito besta.

Seja G = (V, E) um grafo bipartido, e sejam A e B os subconjuntos de vértices que forma


a bipartição. Assuma que |A| = |B|. Para um subconjunto S ⊂ A, seja NG (S) os vizinhos
de S em B.

Algoritmo:

(1) Seja α o menor valor dentre os custos c. Faça y v = α/2 para todo v ∈ V . Note que é
viável para a dual do problema de emparelhamento.

135
G. Coutinho e C. Arbex Valle DCC035 P.O.

(2) Seja H um grafo com os mesmos vértices de G, e cujas arestas são aquelas uv ∈ E(G)
tais que y u + y v = cuv .

(3) Se H possui um emparelhamento perfeito, PARE. Neste caso, este emparelhamento é


um emparelhamento perfeito de custo mı́nimo no grafo G (por que?!).

(4) Caso contrário, existe um conjunto S ⊂ A tal que |NH (S)| < |S| (por que?!)

(5) Se |NG (S)| < |S|, PARE. Neste caso, não existe qualquer emparelhamento perfeito em
G (por que?!)

(6) Escolha  maior possı́vel que permita aumentar a variável y de cada vértice de S por
, diminuir a variável y de cada vértice de NH (S) por , e deixar as demais constantes;
mas garantindo que y permaneça viável em G. Note que  > 0 (por que?!).

(7) Volte para (2).

Exercı́cio 122. Responda os “por que”s.

Exercı́cio 123. Qual ponto do algoritmo acima é o mais delicado (do ponto de vista de
complexidade).

Exercı́cio 124. Aplique o algoritmo ao grafo abaixo.

Exercı́cio 125. Considere um grafo bipartido completo cujos pesos são dados na tabela
abaixo. Ache um emparelhamento perfeito de custo máximo usando o algoritmo visto.

Exercı́cio 126. Mostre que se os pesos são positivos, então um algoritmo que encontre um
emparelhamento perfeito de custo máximo pode ser usado para encontrar um emparelha-
mento máximo de custo máximo.

136
G. Coutinho e C. Arbex Valle DCC035 P.O.

Exercı́cio 127. Considere a PL

max 0
sujeito a Nx = 1
x≥0

. Seja G um grafo bipartido, e S subconjunto de uma das partições. Mostre que se |S| >
|N (S)|, então a dual da PL acima é ilimitada (e portanto a PL é inviável). Dica: olhe para
o algoritmo visto.

7.7 Cobertura por conjuntos


Imagine agora que o problema seja o seguinte. Dada uma coleção de n elementos, e m sub-
conjuntos S1 , ..., Sm , como achar a menor quantidade possı́vel de subconjuntos tais que cada
elemento pertença a pelo menos 1? Ou seja, como achar a menor cobertura por conjuntos
possı́vel? Definimos os vetores caracterı́sticos de cada conjunto - a1 ,...,am . Cada vetor pos-
sui dimensão n e é formado por 0s (caso o elemento não pertença ao conjunto) e 1s (caso
pertença). Agrupamos estes vetores como colunas de uma matriz A.
A formulação do problema de minimizar o número de conjuntos suficientes para cobrir
todos os elementos é dada por:

min 1T y
sujeito a Ay ≥ 1
y ∈ Bm .

Exemplo 22. Além dos médicos de plantão no pronto socorro, um hospital precisa manter
outros médicos em stand-by. Isto é necessário pois o hospital precisa garantir que haverá
um indivı́duo qualificado para executar qualquer procedimento cirúrgico que possa ser ne-
cessário. Para cada um dos diversos médicos disponı́veis para stand-by, o salário adicional
e os procedimentos que é capaz de executar são conhecidos. O objetivo é escolher médicos
tais que todos os procedimentos são cobertos ao custo mı́nimo.
Considere a tabela abaixo:

Med. 1 Med. 2 Med. 3 Med. 4 Med. 5 Med. 6


Proc. 1
Proc. 2
Proc. 3
Proc. 4
Proc. 5
Proc. 6

Cada médico j = 1, . . . , m representa um subconjunto cujos elementos são os procedimentos


i = 1, . . . , n que pode executar. A tabela representa a matriz A e, por exemplo, o vetor

137
G. Coutinho e C. Arbex Valle DCC035 P.O.

T
a1 = 1 1 0 1 0 0 . Considere cj o salário adicional do médico j caso fique em stand-
by.
Escolhemos variáveis de decisão yj se o médico ficará de stand-by ou não. Temos a
seguinte formulação:

X
m
min cj y j
j=1
X
m
sujeito a aij yj ≥ 1 ∀i = 1, . . . , n
j=1

y ∈ Bm .

Observe como, se tivermos mesmo salário cj para todos, temos exatamente a formulação
vista acima: o cálculo do menor número de médicos de forma que todo procedimento seja
coberto.

Este é o problema da cobertura por conjuntos, ou set covering problem em inglês.

Exercı́cio 128. Formule o problema de cobertura por conjuntos como um problema de


achar uma certa cobertura por vértices em um grafo bipartido. A matriz de incidência de
um grafo bipartido é totalmente unimodular. Sendo assim, o problema de cobertura de
conjuntos pode ser resolvido eficientemente?

O problema de cobertura por conjuntos possui uma infinidade de aplicações práticas


(além da vista acima).

1. Imagine que um programador da área de segurança está escrevendo um anti-vı́rus.


Após estudar um conjunto de 15000 vı́rus conhecidos, ele deseja encontrar substrings
de no máximo 20 bytes consecutivos que estejam presentes nestes vı́rus. Ele então
seleciona 5000 strings de 20 bytes. Ao tentar achar o menor número de strings tal
que para cada vı́rus, ao menos uma delas pertença ao vı́rus, este programador estará
precisamente resolvendo um problema de cobertura por conjuntos.

2. Posicionamento de prestadores de serviço para cobrir regiões de um mapa: delegacias


ou hospitais em uma cidade, armazéns de uma companhia distribuidora, etc.

O problema de cobertura por conjunto é NP-difı́cil. De fato, ele é um dos problemas


originais apresentados por Karp na década de 70. Abaixo veremos um algoritmo para lidar
com ele. Vamos antes, porém, apresentar alguns problemas relacionados.

Exercı́cio 129. Escreva a dual da relaxação da formulação do problema de cobertura de


conjuntos. Tente achar uma interpretação combinatória quando adiciona-se restrições de
integralidade.

138
G. Coutinho e C. Arbex Valle DCC035 P.O.

O problema do exercı́cio é o chamado problema de empacotamento de conjuntos (set


packing). O que estamos observando nesses exemplos é a clássica dualidade entre empa-
cotamento e cobertura. A palavra “empacotar” - no caso - se refere ao fato de que ao
adicionarmos um ponto, o espaço disponı́vel para adicionarmos mais pontos se reduz. E
cobertura porque queremos que os subconjuntos unidos contenham todos os pontos.
Aplicações do problema de empacotamento não são tão óbvias, mas diversos problemas
possuem caracterı́sticas de empacotamento de conjuntos como parte de um modelo mais
completo.
Se as restrições de cobertura são igualdades, temos o problema de partição de conjuntos
- set partitioning. Por exemplo:

max cT y
sujeito a Ay = 1
y ∈ B.

No problema de partição de conjuntos, cada elemento deve estar presente em exatamente


um conjunto (nem mais, nem menos). Assumimos um custo associado a um conjunto. Uma
de suas aplicações mais conhecidas é no problema de alocação de tripulação a voos.

Exemplo 23. O custo com pessoal é o segundo maior de uma companhia aérea, perdendo
apenas para custos com combustı́vel. O uso efetivo de tripulações pode resultar em economias
enormes de custos. Há, porém, diversas regulações impostas por sindicatos e órgãos de
controle (tipo a ANAC no Brasil ou FAA nos EUA). Por exemplo, há horas de descanso
mı́nimas, ou tripulações maiores para ciclos de voos mais longos, etc.
No final dos anos 80, a American Airlines desenvolveu para este problema um sistema
de otimização que veio a se tornar extremamente lucrativo para a empresa. Na formulação
que desenvolveram, uma variável binária xi é atribuı́da para cada possı́vel trajeto que uma
tripulação pode legalmente voar. Por exemplo, podemos ter um trajeto onde a tripulação
sai de São Paulo 7:00 e chega ao Rio de Janeiro às 8:00. Saem do Rio às 9:00 em direção a
Belo Horizonte, chegando às 10:00. Saindo às 11:00, chega em São Paulo 12:00, terminando
o percurso. Outro trajeto é sair de São Paulo à Londres, esperar 36 horas (obrigatórias pela
legislação) e voltar a São Paulo.
Assim, cada possı́vel trajeto representa um conjunto, e cada voo individual um elemento.
Cada voo deve ser parte de exatamente um conjunto na solução final. Suponha que um
determinado voo esteja nos possı́veis trajetos i, j, k e l. Então teremos que:

xi + xj + xk + xl = 1
Teremos uma restrição deste tipo para cada voo. O problema de particionamento de con-
juntos é então minimizar os custos dos trajetos de forma que todo voo seja coberto por exa-
tamente um trajeto. As regulamentações às quais as tripulações estão sujeitas são implı́citas
pois apenas trajetos válidos são considerados.

Naturalmente, no exemplo acima podem haver um número enorme de trajetos - com-


binações de voos que “fazem sentido”. Isto leva a um número enorme de variáveis de forma

139
G. Coutinho e C. Arbex Valle DCC035 P.O.

que talvez nem seja possı́vel expressar todas na memória disponı́vel. Como então resolver
este problema?
Através de um algoritmo chamado geração de colunas. Lembra-se que no branch-and-
cut relaxamos o modelo para conter menos restrições e vamos adicionando as restrições aos
poucos, na medida em que são violadas? A geração de colunas é semelhante: iniciamos a
resolução do branch-and-bound com um modelo relaxado, com menos variáveis. Na medida
em que vamos resolvendo o problema, devemos verificar se há variáveis que deveriam entrar
no modelo. A esperança é que conseguiremos provar a otimalidade da solução acrescentando
apenas uma fração das muitas variáveis deixadas de fora.
E como verificar se uma variável deve entrar no modelo? Lembre-se que para cada
variável (coluna) no primal, temos uma restrição (linha) no dual. Uma variável deve entrar
no problema caso sua restrição correspondente seja violada no dual. Assim resolvemos um
problema de separação no dual, encontramos uma restrição violada e acrescentamos a variável
correspondente àquela restrição no primal.
Na verdade, o problema de separação no dual recebe o nome de problema de preci-
ficação, pois busca encontrar os custos reduzidos das variáveis que não estão no modelo
para ver se alguma entraria na base ótima da relaxação linear. Em caso de uma PI, resolve-
mos a precificação em cada nó da árvore do branch-and-bound. O algoritmo correspondente
é chamado de branch-and-price. É possı́vel ir além e misturar planos de corte, branch-
and-bound e geração de colunas, formando algoritmos branch-and-cut-and-price.
Diversas PIs podem ser resolvidas com algoritmos de geração de colunas, e em certos
casos estes algoritmos são os melhores conhecidos para tais problemas.

7.8 Um algoritmo primal-dual


Voltamos agora ao problema de cobertura de conjuntos. Suponha que em um dado conjunto
de pontos e subconjuntos, o maior número de vezes que qualquer um dos pontos pertence a
diferentes subconjuntos é f . Por exemplo, no sistema abaixo, f = 3.

O algoritmo que vamos apresentar agora é um algoritmo de aproximação. Significa que ele
não necessariamente achará o ótimo, mas sim uma solução que está garantidamente próxima
do ótimo. O fator de aproximação mede o quão bom o algoritmo é. Neste caso, o algoritmo
achará uma solução que é no máximo f vezes maior que a melhor possı́vel.
É uma estratégia simples e gulosa. Dado um conjunto de n pontos U e subconjuntos
S1 , ..., Sm desses pontos:

140
G. Coutinho e C. Arbex Valle DCC035 P.O.

(i) Comece considerando uma coleção vazia destes subconjuntos.

(ii) Ache um elemento a ∈ U que não esteja coberto por qualquer subconjunto da coleção.
Dentre os subconjuntos que contêm a, adicione aquele de menor custo, ou que contenha
mais elementos não cobertos, à coleção.

(iii) Repita o passo (ii) até não haverem mais elementos não cobertos.

Esta estratégia provavelmente adicionará mais conjuntos do que o necessário, mas quão
mais? Mostraremos agora duas coisas simultaneamente: como realizar uma análise cautelosa
do desempenho deste algoritmo, e como adaptá-lo para resolver a versão com pesos do
problema da cobertura por conjuntos. Ambas as coisas serão feitas utilizando dualidade e
folgas complementares.
Considere a formulação de programação inteira do problema com pesos

min cT y
sujeito a Ay ≥ 1
y≥0
y ∈ Zm .

Considere a relaxação linear da PI acima e a sua dual:


min cT y max 1T x
(P) sujeito a Ay ≥ 1 (D) sujeito a AT x ≤ c
y≥0 x ≥ 0.
Dada qualquer coleção C de subconjuntos, seja y C o vetor 0-1 de dimensão m correspondente,
ou seja, 1 se o subconjunto pertence a C, e 0 caso contrário.

Entrada: elementos de um conjunto U e subconjuntos S1 , ..., Sm destes elementos.

Saı́da: uma coleção C de subconjuntos que cobrem os elementos, e uma solução viável
x para (D).

(i) Faça x = 0 e C = ∅. Note que x é viável para (D), mas y C é inviável para (P).

(ii) Enquanto existir a ∈ U que não esteja coberto por qualquer subconjunto de C, faça:

(a) Aumente xa ao máximo de modo que x permaneça viável, ou seja, AT x ≤ c.


(b) Identifique alguma linha de AT x ≤ c onde ocorreu a igualdade. Esta linha
corresponde a um conjunto S.
(c) Adicione S a C.

(iii) Retorne C e x.

Exercı́cio 130. Aplique no problema abaixo:

141
G. Coutinho e C. Arbex Valle DCC035 P.O.

R= 3 T= 7
S=1

5 =P a b c

1 =Q d e f

4=W g h i

O algoritmo acima é do tipo primal-dual. Ele começa com uma solução inviável da
primal e uma solução viável da dual. A cada rodada ele implementa mudanças em ambas
as soluções. Essas mudanças satisfazem algumas propriedades

(i) A solução da dual permanece viável.

(ii) A solução da primal vai se aproximando cada vez mais de ser viável, inclusive se man-
tendo sempre inteira.

(iii) Condições de folgas complementares vão sendo satisfeitas. Em particular, temos dois
tipos de condição:
P
(a) Se y i > 0, então a a∈Si xa = ci .
P
(b) Se xa > 0, então Si 3a y i = 1.

Obviamente se todas as condições de ambos os tipos fossem satisfeitas, as soluções


seriam ótimas para as PLs. Então nos contentamos ao longo da solução do algoritmo
em forçar que todas as condições do primeiro tipo sejam satisfeitas, ignorando as do
segundo tipo.

O teorema a seguir estabelece um limite para quão distante do ótimo o algoritmo nos
leva.

Teorema 20. Se f é a maior quantidade de subconjuntos que contém um mesmo elemento


de U , então o algoritmo acima possui fator de aproximação no máximo igual a f .

Demonstração. Seja y Z o vetor caracterı́stico dos conjuntos escolhidos no algoritmo (a


solução primal final no algoritmo), ou seja, y Z tem dimensão m, e yiZ = 1 se Si foi escolhido,
e yiZ = 0 caso contrário.
Sejam y I o ótimo da PI da cobertura por conjuntos, y L um ótimo da PL (P), e x o vetor
obtido do algoritmo viável para a dual. Segue que

cT y Z ≥ cT y I ≥ cT y L ≥ 1T x. (∗)

142
G. Coutinho e C. Arbex Valle DCC035 P.O.

Note agora que, por conta do ponto (a) acima (complementaridade de folga), cada conjunto
Si que foi adicionado a C satisfaz X
x a = ci .
a∈Si

Ou seja, XX
cT y Z = xa .
S∈C a∈S

Para cada a ∈ U , a variável xa aparece no máximo f vezes na soma acima - uma para cada
conjunto S que a contém. Logo
cT y Z ≤ f · 1T x.
Por outro lado, por conta de (∗), temos f · 1T x ≤ f · cT y I . Segue portanto que

cT y Z ≤ f · c T y I ,

ou seja, a solução encontrada é no máximo f vezes o ótimo da PI.


Exercı́cio 131. O problema de cobertura por vértices é um sub-caso do problema de co-
bertura por conjuntos: cada vértice determina um subconjunto de arestas do grafo - aquelas
que são a ele incidentes. Usando o algoritmo acima, qual o fator de aproximação que conse-
guiremos ao resolver o problema de cobertura por vértices em um grafo arbitrário?
Exercı́cio 132. Use o algoritmo acima para encontrar uma cobertura por vértices nos grafos
abaixo:
4 4
3
2 2 2 2
3 2

2
4
4 3 4 3

7.9 Um algoritmo guloso para o problema de cobertura


de conjuntos sem pesos
Vamos agora apresentar um algoritmo guloso para resolver a versão sem pesos do cobertura
por conjuntos. Ou seja, queremos resolver

min 1T y
sujeito a Ay ≥ 1
y≥0
y ∈ Zm .

Procedemos com um algoritmo guloso bem simples:

143
G. Coutinho e C. Arbex Valle DCC035 P.O.

(i) Enquanto há elementos descobertos, escolha o subconjunto que contém mais elementos
descobertos.

Para cada inteiro m, seja


X
n
1
Hn = .
k=1
k

Teorema 21. O algoritmo guloso é no máximo H(n) vezes o ótimo.

Exercı́cio 133. Qual o ótimo do problema abaixo?

E o que o algoritmo guloso encontra?

Algumas observações:

(i) Para problemas em que cada elemento aparece em no máximo poucos conjuntos, o
algoritmo primal-dual acima é muito bom.

(ii) Em particular, é provado que uma aproximação melhor do que ≈ 1, 36 para o problema
da cobertura por vértices implicaria que P = NP.

(iii) Algumas pessoas acreditam haver motivos razoavelmente fortes para acreditar que 2 é
o melhor possı́vel, a não ser, novamente, que P = NP.

(iv) Em termos de n, é provado que a aproximação em O(log(n)) do algoritmo guloso é


essencialmente a melhor possı́vel, a não ser que P = NP.

144
G. Coutinho e C. Arbex Valle DCC035 P.O.

Aulas 25 e 26
7.10 Empacotamento, partição e coberturas — uma
revisão
Dados um conjunto P = {1, ..., n} de pontos e uma famı́lia F = {F1 , ..., Fm } de subconjuntos
de P , um subconjunto S de P é chamado de...

(i) empacotador se S intersecta cada Fi no máximo uma vez;

(ii) particionador se S intersecta cada Fi exatamente uma vez;

(iii) cobertor se S intersecta cada Fi pelo menos uma vez.

Se N é a matriz de incidência do sistema, ou seja, uma matriz 01 em que cada linha é


indexada por P e cada coluna por F , e uma entrada é 1 se e somente se o ponto da linha
pertence ao subconjunto da coluna, então as coleções de todos os conjuntos...

(i) empacotadores é determinada por S E = {x ∈ {0, 1}n : Nx ≤ 1};

(ii) particionadores é determinada por S P = {x ∈ {0, 1}n : Nx = 1};

(iii) cobertores é determinada por S C = {x ∈ {0, 1}n : Nx ≥ 1}.

Em geral, a não ser que N possua uma estrutura especial, otimizar em conjuntos das
formas acima são problemas difı́ceis.

Exemplo 24. Atenção! Note que originalmente quando falamos de coberturas, estávamos
cobrindo pontos escolhendo subconjuntos. Aqui é ao contrário, ou ao menos assim parece
à primeira vista: estamos cobrindo os subconjuntos escolhendo pontos (ou fazendo hitting).
Os dois problemas são contudo equivalentes: basta inverter os nomes do que é ponto e o que
é subconjunto, mantendo a mesma regra de incidência...

7.10.1 Grafos
Considere um grafo G, vértices V e arestas E.

Exercı́cio 134.

(a) Um emparelhamento em um grafo é uma estrutura de qual tipo acima? Quem são os
pontos e os subconjuntos?

(b) Uma cobertura por vértices de arestas em um grafo é uma estrutura de qual tipo acima?
Quem são os pontos e os subconjuntos?

(c) Uma coloração em um grafo é uma estrutura de qual tipo acima? Quem são os pontos
e os subconjuntos?

145
G. Coutinho e C. Arbex Valle DCC035 P.O.

(d) Um conjunto independente em um grafo é um problema de qual tipo acima? Quem são
os pontos e os subconjuntos?

(e) Um clique em um grafo é um problema de qual tipo acima? Quem são os pontos e os
subconjuntos?

Como visto acima, um conjunto S de vértices é chamado de independente se nenhum par


dentro do conjunto são vizinhos. Ou seja, se N é a matriz de incidência vértice × aresta do
grafo, então o coleção de todos os conjuntos independentes é determinado por

stab(G) = {x ∈ {0, 1}n : Nx ≤ 1.}

O problema de achar um conjunto independente de tamanho máximo é geral formulado


como max{1T x : x ∈ stab(G)}, ou seja

max 1T x
sujeito a Nx ≤ 1
x ≥ 0 x inteiro.

Vamos discutir abaixo como trocar as desigualdades Nx ≤ 1 por outras mais restritas, que
tornem a relaxação linear mais próxima da programação inteira.
Seja K um clique (conjunto de vértices em que todos se ligam a todos), e seja v K seu
vetor de incidência (vetor de n entradas 01 que indica quais vértices pertencem a K). Note
que se x é um conjunto independente, então necessariamente teremos

v KT x ≤ 1.

Ou seja, todo conjunto independente possui no máximo um vértice de cada clique.

Exercı́cio 135. Considere o grafo que possui três vértices a, b e c, e todos são conectados.
Mostre que há soluções 0 ≤ x ≤ 1 fracionárias que satisfazem Nx ≤ 1 mas que não
satisfazem xa + xb + xc ≤ 1. Conclua que a formulação das desigualdades lineares para o
problema de achar conjuntos independentes em um grafo é mais restrita se usarmos uma
desigualdade para cada clique, ao invés de uma desigualdade para cada aresta.

Exercı́cio 136.

(a) Demonstre que o número cromático de um grafo é sempre maior ou igual do que o
tamanho do maior clique do grafo.

(b) Mostre que mesmo o ótimo da relaxação linear da formulação do problema de coloração
como no Exercı́cio 134 ainda é maior ou igual que o tamanho do maior clique de um
grafo.

146
G. Coutinho e C. Arbex Valle DCC035 P.O.

7.11 Colorações
Vamos agora olhar para mais um problema em grafos. Suponha que desejamos colorir os
vértices de um grafo de modo que vértices vizinhos recebam cores diferentes.

O primeiro é uma boa coloração com 4 cores, o segundo é uma má coloração, e o terceiro
é uma boa coloração com 3 cores. Parece fácil, até que tornamos isso em um problema de
otimização:

• Qual o mı́nimo número de cores necessário para colorir os vértices de um grafo de modo
que vizinhos não recebam a mesma cor?

Exercı́cio 137. Quais são os grafos que podem ser coloridos com duas cores?

Exercı́cio 138. Dê exemplo de um grafo com 6 vértices que precise exatamente de 6 cores
para ser colorido.

Por exemplo, imagine que os vértices representem eventos. Cada aresta representa even-
tos que não podem ocorrer simultaneamente, por exemplo, porque dependem dos mesmos
participantes. O problema da coloração portanto é a modelagem combinatória do problema
de encontrar o menor número possı́vel de horários para sediar todos os eventos!
Note que o problema de coloração é, em certo sentido, um problema de cobertura. Es-
pecificamente: desejamos cobrir os vértices do grafo com escolhas de conjuntos de vértices
que sejam independentes! Se I é o conjunto de todos os conjuntos independentes do grafo,
então rapidamente chegamos à clássica formulação do problema de cobertura:
X
min xI
I∈I
X
sujeito a xI ≥ 1 para todo v ∈ V (G)
v∈I
xI ≥ 0
xI ∈ Z.

Exercı́cio 139. Fora ser uma formulação com restrições de integralidade, qual um grave
problema da restrição acima?

De fato, achar o ótimo da relaxação linear da PI acima é um problema NP-difı́cil!!

Exercı́cio 140. Como formular o problema de achar uma coloração de um grafo com um
número mı́nimo de cores como uma PI com um número “pequeno”de restrições?

147
G. Coutinho e C. Arbex Valle DCC035 P.O.

• Dica: suponha que você tem n vértices. Claramente n cores seriam suficientes. Pode-
mos fazer com menos? Bem, use dois tipos de variáveis: variáveis yk , com k = 1, ..., n,
que indicariam se a cor k seria utilizada. E use variáveis xik que indicariam se a cor k
será ou não aplicada no vértice i.
• Escreva a função objetivo, as restrições especı́ficas (são 3 tipos), as restrições de não
negatividade e as de integralidade.
Exercı́cio 141. Qual o ótimo da relaxação linear da PI acima?
Exercı́cio 142. Se um grafo G tem grau máximo ∆, ache um algoritmo guloso que colore
G com no máximo ∆ + 1 cores.
Exercı́cio 143. Ache um grafo de grau máximo 6 mas que só precisa de duas cores para ser
colorido.

7.12 Localização de instalações (facility location)


Lembre-se do exercı́cio na parte de modelagem sobre a decisão de onde abrir quartéis do
corpo de bombeiros para atender cidades. Alternativamente, pense por exemplo em uma
empresa de logı́stica deseja abrir alguns armazéns para atender a alguns pontos de venda no
varejo. Ambos os problemas podem ser modelados formalmente da seguinte forma:
(i) Um grafo G, com vértices V e arestas E.
(ii) Um subconjunto dos vértices chamados de instalações, digamos, F ⊆ V .
(iii) Um subconjunto dos vértices chamados de clientes, digamos, C ⊆ V . Podemos assumir
que V = F ∪ C.
(iv) Uma função custo em cada uma das arestas (por exemplo, o custo de transporte ou
a distância), ou seja, c ∈ RE . No caso especial que discutimos aqui, esta função será
uma métrica, ou seja, o custo de conectar i a j não é maior do que o de conectar i a
j1 , j1 a i2 e i2 a j.
(v) Um custo para abrir cada uma das instalações, ou seja, f ∈ RF .
Após a escolha de um subconjunto possı́vel das instalações, cada cliente será pareado
com uma instalação aberta, e o custo do pareamento será o custo do caminho mı́nimo no
grafo entre eles. O objetivo é minimizar o custo total de abertura das instalações, e o custo
total dos pareamentos. Ou seja, temos variáveis yi para cada i ∈ F que indicarão a abertura
ou não da instalação, e variáveis xij que indicarão se o cliente j é pareado com a instalação
i. Daı́
X X
min fi y i + cij xij
i∈F i∈F, j∈C
X
sujeito a xij ≥ 1, ∀ j ∈ C,
i∈F
xij ≤ yi , ∀ i ∈ F, j ∈ C,
x e y ≥ 0, e inteiros.

148
G. Coutinho e C. Arbex Valle DCC035 P.O.

Começamos escrevendo
P a programação dual da relaxação linear. Teremos variáveis para cada
restrição do tipo xij ≥ 1, digamos uj , e outras para cada xij ≤ yi , digamos vij . Daı́
X
max uj
j∈C

sujeito a uj − vij ≤ cij , ∀ i ∈ F, j ∈ C,


X
vij ≤ fi , ∀ i ∈ F,
j∈C

u e v ≥ 0.

É possı́vel interpretar a dual como um problema em que cada cliente está pagando para
a abertura das instalações. Assim, uma possı́vel interpretação para as variáveis duais é a
seguinte:
(i) Cada uj é quanto cada cliente está disposto a pagar no total.
(ii) Cada vij é quanto está disposto a pagar para abrir a instalação i.
De fato, se (x, y) e (u, v) formam um par primal-dual viável e ótimo, as condições de
folga complementar implicam que
P
(i) Se yi > 0, então vij = fi , ou seja, instalações abertas foram pagadas inteiramente
pelos clientes.
(ii) Se vij > 0, então yi = xij , ou seja, se o cliente j para por i, então ele a utiliza.
(iii) Se xij > 0, então uj = cij + vij , ou seja, se o cliente j usa i, então o total que ele gasta
é exatamente o custo do pareamento mais a sua fração na abertura de i.

7.12.1 Algoritmo primal-dual


Descrevemos agora um método primal-dual para o problema de localização de instalações.

(1) Começamos com y = 0, e u = 0.


(2) Aumentamos os valores de uj para cada cliente que não esteja ainda conectado, de modo
constante e uniforme.
(3) Inicialmente, todas as instalações ainda estão fechadas.
(4) Quando uj ultrapassa cij para algum i, começamos a aumentar os valores de vij , de
modo constante e uniforme. Lembre-se que precisamos de uj ≤ cij + vij .
P
(5) Quando j vij = fi , abrimos a instalação i, e conectamos todos os clientes j desconec-
tados e com uj ≥ cij para a instalação i. Seja i(j) a instalação que o cliente j conectou.
(6) Voltamos a aumentar cada uj . Dessa vez, assim que uj atingir algum cij de um i já
aberto, conectamos j a i, e paramos de aumentar uj , e definimos esta i como i(j). Caso
contrário, voltamos para (4).

149
G. Coutinho e C. Arbex Valle DCC035 P.O.

Ao término, cada cliente estará “conectado”a uma única instalação. Entretanto, mais ins-
talações do que o necessário foram abertas, e clientes estão contribuindo para instalações as
quais não conectaram. Vamos descrever agora um esquema que fechará algumas delas.

(a) Crie um grafo cujos vértices são as instalações abertas, e duas delas vizinhas se e somente
se há um cliente que contribui para abrir ambas.

(b) Ache um conjunto independente maximal neste grafo, digamos, T , começando na or-
dem em que as instalações foram temporariamente abertas. Este será o conjunto de
instalações oficialmente abertas.

(c) Para cada cliente j, se i(j) está em T , declare então j oficialmente pareado com i(j).
/ T , seja i0 a instalação de T que conflita com i(j) (e que, portanto, foi aberta
Se i(j) ∈
antes que i(j)). Declare j oficialmente pareado a i0 .

Temos alguns fatos:

(i) Nenhum cliente j contribui para duas instalações oficialmente abertas.

(ii) Se i ∈ T , e S ⊆ C são os clientes j tais que i(j) = i, então


X X
fi + cij = uj .
j∈S j∈S

De fato, temos, por construção da primeira parte do algoritmo, que


X
fi = vij .
j∈S

Como vij = uj − cij , a equação é verdadeira.

(iii) Se j está oficialmente conectado a i ∈ T , mas i(j) 6= i, então

cij ≤ 3uj .

Para ver este, note que precisa haver j 0 que contribui originalmente para i e para i(j),
logo uj 0 ≥ cij 0 e ≥ ci(j)j 0 . Também sabemos que uj ≥ ci(j)j . Como i abriu antes que
i(j) (e portanto ficou em T ...), e como os us aumentam juntos e de modo uniforme,
teremos que uj 0 ≤ uj . Logo

cij ≤ ci(j)j + ci(j)j 0 + cij 0 ≤ uj + uj 0 + uj 0 ≤ 3uj .


P
Segue portanto que o custo total da solução inteira é no, máximo, 3 j∈C uj , que é no
máximo 3 vezes o ótimo da dual da relaxação linear. Portanto a solução inteira encontrada
é, no pior caso possı́vel, 3 vezes o ótimo inteiro do problema!

150

Você também pode gostar