Programação linear: conceitos básicos

O problema de programação linear consiste em encontrar um vetor de um dado poliedro que maximize uma dada função linear. Mais especificamente, o problema de programação linear consiste no seguinte: Dados conjuntos finitos

V

E

, uma matriz

A

indexada por

V \times E

, e vetores

b

c

indexados por

V

E

respectivamente, encontrar um vetor

x

que

\begin{matrix} (1) & \begin{aligned} maximize c x \\ sob as restrições A x & \leq b . \end{aligned} \end{matrix}

A expressão maximize

c x

deve ser entendida assim: procuramos

x

tal que

c x \geq c x^{'}

para todo

x^{'}

que satisfaça as restrições

A x^{'} \leq b

. Cada desigualdade

A [v, *] x \leq b [v]

é uma restrição do problema. O número

c x

é o valor de

x

. O máximo de

c x

é o valor ótimo do problema.

É usual supor que a matriz

A

e os vetores

b

c

são reais, mas poderíamos nos restringir às matrizes e vetores racionais, uma vez que computadores digitais desconhecem números irracionais.

Exemplo C.1: Considere a matriz $A$ e os vetores $b$ e $c$ representados abaixo, com $b$ na vertical à direita da matriz e $c$ na horizontal abaixo da matriz:

\begin{array}{ccccccc} 11 & 12 & 13 & 14 & 15 & 16 \\ 21 & 22 & 23 & 24 & 25 & 26 \\ 31 & 32 & 33 & 34 & 35 & 36 \\ 41 & 42 & 43 & 44 & 45 & 46 \\ 51 & 52 & 53 & 54 & 55 \end{array}

O problema de maximizar $c x$ sujeito às restrições $A x \leq b$ pode ser escrito explicitamente assim: encontrar números $x_{1}$ , $x_{2}$ , $x_{3}$ , $x_{4}$ , $x_{5}$ que maximizem o valor da combinação linear $\begin{aligned} 51 x_{1} + 52 x_{2} + 53 x_{3} + 54 x_{4} + 55 x_{5} \end{aligned}$ enquanto satisfazem as restrições lineares $\begin{aligned} 11 x_{1} + 12 x_{2} + 13 x_{3} + 14 x_{4} + 15 x_{5} & \leq 16 \\ 21 x_{1} + 22 x_{2} + 23 x_{3} + 24 x_{4} + 25 x_{5} & \leq 26 \\ 31 x_{1} + 32 x_{2} + 33 x_{3} + 34 x_{4} + 35 x_{5} & \leq 36 \\ 41 x_{1} + 42 x_{2} + 43 x_{3} + 44 x_{4} + 45 x_{5} & \leq 46 . \end{aligned}$ (Todos os coeficientes nesse exemplo são inteiros positivos, mas isso é mero acidente.)

O problema de programação linear é muitas vezes chamado de programa linear (= linear program). Usamos a expressão pl como abreviatura de programa linear.

O pl dado na definição

(1)

pode ser escrito assim: encontrar um vetor

x

indexado por

E

que

\begin{aligned} maximize \sum_{e \in E} c [e] x [e] \\ sujeito a \sum_{e \in E} A [v, e] x [e] & \leq b [v] para todo v em V . \end{aligned}

De acordo com a definição

(1)

, um programa linear é um problema de maximização. Mas a definição é suficientemente flexível para incluir problemas de minimização: basta trocar

c

por

- c

Exemplo C.2: Considere o problema de minimizar $c x$ sob as restrições $A x \leq b$ . Esse problema equivale a maximizar $- c x$ sob as mesmas restrições. O segundo problema satisfaz a definição $(1)$ de programa linear.

Exemplo C.3: Considere o problema de maximizar $c x$ sob as restrições $A x \geq b$ . Esse problema equivale a maximizar $c x$ sob as restrições $- A x \leq - b$ , que satisfaz a definição $(1)$ .

Exemplo C.4: Considere o problema de encontrar um vetor $y$ que maximize $y b$ sob as restrições $y A \leq c$ . Esse problema pode ser reescrito assim: maximize $b y$ sujeito a $A^{T} y \leq c$ . Assim, o problema dado satisfaz a definição $(1)$ de pl.

Exemplo C.5: Considere o problema de maximizar $c x$ sujeito a $A x \leq b$ e $x \geq 0$ . Isso equivale a maximizar $c x$ sob as restrições $A x \leq b$ e $- I x \leq 0$ , sendo $I$ a matriz identidade com linhas e colunas indexadas pelo conjunto de índices de $x$ . Esse segundo problema tem a forma da definição $(1)$ de pl: basta tomar a justaposição apropriada das matrizes $A$ e $- I$ e dos vetores $b$ e $0$ . Podemos dizer, então, que o problema original é um pl.

C.1.1 Soluções de programas lineares

Considere o pl

(1)

e seja

P

o poliedro

{x : A x \leq b}

. Uma solução viável (= feasible solution) do pl é qualquer vetor de

P

. Uma solução ótima do pl é qualquer vetor

x

P

para o qual

c x

é máximo. [Essa terminologia tradicional é um tanto ilógica. Como a definição do pl inclui a maximização de

c x

, o ótima da expressão solução ótima é redundante. Além disso, uma solução viável não é, a rigor, uma solução do pl pois não maximiza

c x

.] O pl pode não ter solução ótima porque

P

é vazio ou porque

c x

não tem máximo (ou seja, porque o máximo é infinito). Se

P

é vazio, dizemos que o pl é inviável (= infeasible). Caso contrário, dizemos que o pl é viável (= feasible). Se

P

não é vazio mas

c x

não tem máximo, dizemos que o pl é ilimitado (= unbounded).

Suponha agora que o pl

(1)

não é inviável nem ilimitado. Então, como veremos adiante, o pl tem uma solução ótima.

Exercícios C.1

Seja $A$ a matriz representada abaixo, $b$ o vetor representado à direita de $A$ e $c$ o vetor representado abaixo de $A$ . Escreva por extenso o seguinte pl: minimize $c x$ sujeito às restrições $A x \leq b$ .
$\begin{array}{rrrrrr} - 1 & 0 & + 1 & - 1 & 0 & + 2 \\ 0 & - 1 & 0 & 0 & 0 & - 2 \\ + 1 & + 1 & 0 & 0 & - 1 & 0 \\ 0 & 0 & - 1 & + 1 & + 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \end{array}$
Considere o problema de maximizar $c x$ sob as restrições $A x = b$ . Mostre que esse problema satisfaz a definição $(1)$ de programa linear.
Considere o pl que consiste em maximizar $c x$ sujeito a $A x \leq b$ , sendo $A$ é uma matriz indexada por $V \times E$ , $b$ um vetor indexado por $V$ e $c$ um vetor indexado por $E$ . Suponha que $s$ é uma solução ótima do pl e $s [V ∖ J] = 0$ , sendo $J$ um subconjunto de $E$ . Mostre que $s [J]$ é solução ótima do pl $maximize c [J] x sujeito a A [V, J] x \leq b .$

C.2 Dualidade em programação linear

Há uma fundamental relação dualidade entre programas lineares. Considere, por exemplo, o programa linear

\begin{matrix} (2) & \begin{aligned} maximize c x \\ sujeito a A x & \leq b . \end{aligned} \end{matrix}

O dual desse pl consiste em encontrar um vetor

y

que

\begin{matrix} (3) & \begin{aligned} minimize y b \\ sujeito a y A & = c e \\ y & \geq 0 . \end{aligned} \end{matrix}

A relação básica entre os pl's

(2)

(3)

é conhecida como teorema fraco da dualidade. Ela dá uma delimitação superior para a expressão que queremos maximizar e, ao mesmo tempo, uma delimitação inferior para a expressão que queremos minimizar:

O lema tem a seguinte consequência: se

c x = y b

então

x

é solução ótima do pl primal e

y

é solução ótima do pl dual. Portanto, para mostrar que uma solução viável

x

do primal é ótima, basta exibir uma solução viável

y

do dual tal que

c x = y b

. A recíproca dessa observação é garantida pelo teorema forte da dualidade:

A prova do teorema é algorítmica: o algoritmo Simplex recebe

A

b

c

, decide se os dois pl's são viáveis e, em caso afirmativo, devolve

x

y

tais que

c x = y b

Exemplo C.7: Considere o seguinte par dual de pl's. Verifique que ambos são inviáveis.

\begin{array}{rcl} maximize 2 x_{1} + x_{2} \\ sujeito a - x_{1} + x_{2} & \leq & 4 \\ x_{1} - x_{2} & \leq & 2 \\ x & \geq & 0 \end{array} \begin{array}{rcl} minimize - 4 y_{1} + 2 y_{2} \\ sujeito a - y_{1} + y_{2} & \geq & 2 \\ y_{1} - y_{2} & \geq & 1 \\ y & \geq & 0 \end{array}

Exemplo C.8: Considere o seguinte par dual de pl's. Verifique que o primeiro é inviável e o segundo é ilimitado.

\begin{array}{rcl} maximize 2 x_{1} + x_{2} \\ sujeito a - x_{1} - x_{2} & \leq & - 4 \\ x_{1} + x_{2} & \leq & 2 \\ x & \geq & 0 \end{array} \begin{array}{rcl} minimize - 4 y_{1} + 2 y_{2} \\ sujeito a - y_{1} + y_{2} & \geq & 2 \\ y_{1} + y_{2} & \geq & 1 \\ y & \geq & 0 \end{array}

Exemplo C.9: Considere o seguinte par dual de pl's. Verifique que o primeiro é ilimitado e o segundo é inviável.

\begin{array}{rcl} maximize 2 x_{1} + x_{2} \\ sujeito a x_{1} - x_{2} & \leq & 4 \\ x_{1} - x_{2} & \leq & 2 \\ x & \geq & 0 \end{array} \begin{array}{rcl} minimize 4 y_{1} + 2 y_{2} \\ sujeito a y_{1} + y_{2} & \geq & 2 \\ - y_{1} - y_{2} & \geq & 1 \\ y & \geq & 0 \end{array}

Exemplo C.10: Considere o seguinte par dual de pl's. Verifique que ambos são viáveis. (Mostre uma solução ótima de cada um.)

\begin{array}{rcl} maximize 2 x_{1} + x_{2} \\ sujeito a x_{1} + x_{2} & \leq & 4 \\ x_{1} - x_{2} & \leq & 2 \\ x & \geq & 0 \end{array} \begin{array}{rcl} minimize 4 y_{1} + 2 y_{2} \\ sujeito a y_{1} + y_{2} & \geq & 2 \\ y_{1} - y_{2} & \geq & 1 \\ y & \geq & 0 \end{array}

Exercícios C.2

Considere o problema de encontrar $x$ que maximize $c x$ sob as restrições $A x = b$ e $x \geq 0$ . Enuncie o pl dual. Verifique o teorema fraco da dualidade para esse par de pl's. Enuncie o teorema forte da dualidade para esse par de pl's.
Considere o problema de encontrar $x$ que maximize $x_{1} + 2 x_{2} + 3 x_{3}$ sob as restrições $x_{1} \geq 0$ , $x_{2} \geq 0$ , $x_{3} \geq 0$ ,
$\begin{array}{rcl} x_{1} + x_{2} + x_{3} & = & - 10 e \\ x_{1} + 4 x_{3} & = & - 20 . \end{array}$

Qual o dual desse pl? O dual é viável? inviável? ilimitado?
Considere o seguinte pl: encontrar $x$ que maximize $c x$ sob as restrições $A x \leq b$ e $x \geq 0$ . Mostre que o dual desse pl pede um vetor $y$ que minimize $y b$ sob as restrições $y A \geq c$ e $y \geq 0$ .
Prove o corolário C.3.
Prove o corolário C.4.
Sejam $L$ , $M$ , $N$ , $O$ , $P$ , $Q$ conjuntos finitos disjuntos entre si. Sejam $A$ , $B$ , $C$ , $D$ , $E$ , $F$ , $G$ , $H$ , $K$ matrizes reais indexadas por
$\begin{array}{lll} L \times O, & L \times P, & L \times Q, \\ M \times O, & M \times P, & M \times Q, \\ N \times O, & N \times P, & N \times Q, \end{array}$

respectivamente. Sejam $a$ , $b$ , $c$ vetores reais indexados por $L$ , $M$ e $N$ , respectivamente. Sejam $d$ , $e$ , $f$ vetores reais indexados por $O$ , $P$ e $Q$ , respectivamente. Seja $X$ o conjunto de todos os vetores reais $(x, y, z)$ que satisfazem as restrições abaixo à esquerda e $Y$ o conjunto de todos os vetores reais $(u, v, w)$ que satisfazem as restrições abaixo à direita. $\begin{aligned} A x + B y + C z & \leq a \\ D x + E y + F z & = b \\ G x + H y + K z & \geq c \\ x & \geq 0 \\ z & \leq 0 \end{aligned} \begin{aligned} u A + v D + w G & \geq d \\ u B + v E + w H & = e \\ u C + v F + w K & \leq f \\ u & \geq 0 \\ w & \leq 0 \end{aligned}$ Suponha que $X \neq \emptyset$ e $Y \neq \emptyset$ e prove que $max {d x + e y + f z : (x, y, z) \in X} = min {u a + v b + w c : (u, v, w) \in Y}$ . [CCPS A.8]

C.3 Folgas complementares

Seja

A

uma matriz indexada por

V \times E

b

um vetor indexado por

V

, e

c

um vetor indexado por

E

. Seja

x

uma solução viável do pl

(2)

y

uma solução viável do pl

(3)

. Para cada índice

i

V

, dizemos que

x

é justo em

i

(A x) [i] = b [i]

e folgado em

i

(A x) [i] < b [i]

. Analogamente,

y

é justo em

i

y [i] = 0

e folgado em

i

y [i] > 0

. (Nesse par dual de pl's, as folgas envolvem apenas os índices das linhas de

A

. Em outros pl's, as folgas podem envolver também os índices das colunas.)

x

é justo sempre que

y

é folgado (ou, equivalentemente,

y

é justo sempre que

x

é folgado), dizemos que as folgas de

x

y

são complementares (= complementary slackness). No caso dos pl's

(2)

(3)

, as folgas de

x

y

são complementares se, para cada índice

i

\begin{matrix} (5) & (A x) [i] = b [i] ou y [i] = 0 . \end{matrix}

(O ou não é exclusivo, pois podemos ter

(A x) [i] = b [i]

y [i] = 0

para alguns valores de

i

.) Essa definição de complementaridade de folgas também pode ser formulada assim: para cada índice

i

Exercícios C.3

★ Dados números não-negativos $a_{1}, a_{2}, \dots, a_{m}$ e $b_{1}, b_{2}, \dots, b_{m}$ , suponha que $a_{1} b_{1} + a_{2} b_{2} + \dots + a_{m} b_{m} = 0$ . É verdade que $a_{1} = \dots = a_{m} = 0$ ou $b_{1} = \dots = b_{m} = 0$ ? Mostre que, para cada $i$ , $a_{i} = 0$ ou $b_{i} = 0$ .
★ Folgas complementares. Sejam $a$ , $b$ e $c$ vetores indexados por um conjunto $E$ . Suponha que $a \geq 0$ e $b \leq c$ . Prove que $a b = a c$ se e somente se, para cada $e$ em $E$ , tem-se $a_{e} = 0$ ou $b_{e} = c_{e}$ .
Prove o lema C.5. (Veja a prova do lema fraco da dualidade e o exercício acima).
Considere o seguinte pl: minimizar $c x$ sob as restrições $A x = b$ e $x \geq 0$ . Enuncie as condições de folgas complementares.
Considere o seguinte pl: maximizar $c x$ sob as restrições $A x = b$ e $x \geq 0$ . Enuncie o pl dual. Enuncie as condições de folgas complementares para o par de pl's.
Considere o seguinte pl: maximizar $c x$ sujeito às restrições $A x \leq b$ e $x \geq 0$ . Enuncie o pl dual. Prove o teorema fraco da dualidade para esse par de pl's. Enuncie as condições de folgas complementares. Enuncie o teorema forte da dualidade.
Considere o problema de encontrar $x$ que maximize $c x$ sob as restrições $A x = b$ e $x \geq 0$ . Considere também o dual desse pl. Suponha que $x$ é uma solução viável do primeiro pl e $y$ é uma solução viável do segundo. O que significam as expressões $x$ é justo em $j$ e $y$ é justo em $j$ ? Enuncie as condições de folgas complementares para o par dual de pl's. Prove que, para qualquer $x$ viável no primeiro pl e qualquer $y$ viável no segundo, temos $c x = y b$ se e somente se as folgas de $x$ e $y$ são complementares.

C.4 Algoritmos para programas lineares

Existem vários algoritmos para o problema de programação linear. Todo algoritmo para o problema de maximizar

c x

sob as restrições

A x \leq b

recebe uma matriz racional

A

, um vetor racional

b

, e um vetor racional

c

e devolve

Ademais, se o poliedro

{x : A x \leq b}

tiver algum vértice então o vetor

x

do caso (a) é um vértice.

O algoritmo de programação linear mais célebre é o Simplex. (Veja o livro de Chvátal \cite{chvatal}.) Um algoritmo mais complexo é o do elipsóide (= ellipsoid algorithm). Outro, também complexo, é o algoritmo do ponto interior (= interior point method).

Os dois últimos algoritmos são polinomiais: consomem tempo limitado por um polinômio em

n

m

, sendo

m

o número de linhas e

n

o número de colunas de

A

. O Simplex não é polinomial, mas muito usado na prática porque as instâncias que consomem tempo excessivo são raras.

C.5 Lema de Farkas

Considere, mais uma vez, o programa linear

(2)

. Como tornar evidente que uma dada instância do pl é inviável? Um vetor de inviabilidade para o pl

(2)

é qualquer vetor

y^{'}

indexado por

V

tal que

\begin{matrix} (6) & y^{'} A = 0 e y^{'} \geq 0 e y^{'} b < 0 . \end{matrix}

Um tal vetor é um certificado (computacionalmente verificável) da inviabilidade do pl:

Resultados análogos valem para o pl dual. Um vetor de inviabilidade para o pl

(3)

é qualquer vetor

x^{'}

indexado por

E

tal que

\begin{matrix} (7) & A x^{'} \leq 0 e c x^{'} > 0 . \end{matrix}

Um tal vetor é um certificado da inviabilidade do pl

(3)

por razões análogas à do lema C.6. Vale também a versão apropriada do lema de Farkas.

Exercícios C.5

Mostre que um vetor de inviabilidade para o pl $(2)$ poderia ter sido definido pelas condições $y^{'} A = 0$ , $y^{'} \leq 0$ e $y^{'} b > 0$ .
★ Qual a definição apropriada de vetor de inviabilidade para o seguinte pl: encontrar um vetor $x$ que minimize $c x$ sob as restrições $A x = b$ , $1 x = 1$ e $x \geq 0$ ? (Aqui, o segundo $1$ é o número $1$ e o primeiro $1$ representa um vetor cujos elementos são todos iguais a $1$ e cujos índices são os mesmos de $x$ .)
Mostre vetores de inviabilidade para os exemplos C.7 a C.9.
Considere o problema de encontrar $x \geq 0$ que maximize $x_{1} + 2 x_{2} + 3 x_{3}$ sob as restrições abaixo. Mostre que o pl é inviável e calcule um vetor de inviabilidade.
$\begin{array}{rcl} x_{1} + x_{2} + x_{3} & = & - 10 \\ x_{1} + 4 x_{3} & = & - 20 \end{array}$
Suponha dado um vetor de inviabilidade para o pl $(2)$ . Mostre que o pl dual $(3)$ é inviável ou ilimitado.
Suponha dado um vetor de inviabilidade para o pl $(3)$ . Mostre que o pl dual $(2)$ é inviável ou ilimitado.
Deduza o lema de Farkas do teorema forte da dualidade.

C.6 Programação inteira

Dada uma matriz real

A

, um vetor real

b

, e um vetor real

c

, o problema de programação inteira consiste em encontrar um vetor inteiro

z

que

\begin{matrix} (8) & \begin{aligned} maximize c z \\ sob as restrições A z & \leq b . \end{aligned} \end{matrix}

Muitos problemas de otimização combinatória são naturalmente representados por programas lineares inteiros. A restrição de integralidade torna o problema muito difícil. Não se conhecem algoritmos polinomiais para o problema. O problema é NP-difícil.

A relaxação linear de um programa inteiro é o pl que se obtém quando a restrição de integralidade é removida.

Apêndice C
Programação linear

C.1 Programas lineares

C.1.1 Soluções de programas lineares

Exercícios C.1

C.2 Dualidade em programação linear

Exercícios C.2

C.3 Folgas complementares

Exercícios C.3

C.4 Algoritmos para programas lineares

C.5 Lema de Farkas

Exercícios C.5

C.6 Programação inteira

Apêndice CProgramação linear

C.1 Programas lineares

C.1.1 Soluções de programas lineares

Exercícios C.1

C.2 Dualidade em programação linear

Exercícios C.2

C.3 Folgas complementares

Exercícios C.3

C.4 Algoritmos para programas lineares

C.5 Lema de Farkas

Exercícios C.5

C.6 Programação inteira

Apêndice C
Programação linear