Otimização Combinatória | Dicionário | Índice remissivo

Apêndice C
Programação linear

Formular problemas de otimização combinatória como programas lineares é muito útil e revelador. Este apêndice faz uma rápida revisão dos conceitos e da terminologia básica da programação linear.

C.1 Programas lineares

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 $E$, uma matriz $A$ indexada por $V\times E$, e vetores $b$ e $c$ indexados por $V$ e $E$ respectivamente, encontrar um vetor $x$ que \begin{equation}\label{lp:basic} \begin{split} \text{maximize} \enspace cx & \\ \text{sob as restrições} \enspace Ax &\leq b\,\text{.} \end{split} \end{equation}

A expressão maximize $cx$ deve ser entendida assim: procuramos $x$ tal que $cx \geq cx'$ para todo $x'$ que satisfaça as restrições $Ax' \leq b$. Cada desigualdade $A[v,\all]\,x \leq b[v]$ é uma restrição do problema. O número $cx$ é o valor de $x$. O máximo de $cx$ é o valor ótimo do problema.

É usual supor que a matriz $A$ e os vetores $b$ e $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}{ccccc@{\hspace{3ex}}c} 11& 12& 13& 14& 15& 16\\ 21& 22& 23& 24& 25& 26\\ 31& 32& 33& 34& 35& 36\\ 41& 42& 43& 44& 45& 46\\[1.5ex] 51& 52& 53& 54& 55 \end{array} \]

O problema de maximizar $cx$ sujeito às restrições $Ax \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{split} 51x_1 + 52x_2 + 53x_3 + 54x_4 + 55x_5 \ &\ph{\leq \ 11} \end{split} \] enquanto satisfazem as restrições lineares \[ \begin{split} 11x_1 + 12 x_2 + 13 x_3 + 14 x_4 + 15 x_5 \ &\leq \ 16\\ 21x_1 + 22 x_2 + 23 x_3 + 24 x_4 + 25 x_5 \ &\leq \ 26\\ 31x_1 + 32 x_2 + 33 x_3 + 34 x_4 + 35 x_5 \ &\leq \ 36\\ 41x_1 + 42 x_2 + 43 x_3 + 44 x_4 + 45 x_5 \ &\leq \ 46\,\text{.} \end{split} \] (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 \eqref{lp:basic} pode ser escrito assim: encontrar um vetor $x$ indexado por $E$ que \begin{equation*} \begin{split} \text{maximize} \quad \textstyle\sum_{e\in E} c[e]\,x[e] & \\ \text{sujeito a} \quad \textstyle\sum_{e\in E} A[v,e]\,x[e] &\leq b[v] \quad \text{para todo $v$ em $V$.} \end{split} \end{equation*}

De acordo com a definição \eqref{lp:basic}, 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 $cx$ sob as restrições $Ax \leq b$. Esse problema equivale a maximizar $-cx$ sob as mesmas restrições. O segundo problema satisfaz a definição \eqref{lp:basic} de programa linear.

Exemplo C.3: Considere o problema de maximizar $cx$ sob as restrições $Ax \geq b$. Esse problema equivale a maximizar $cx$ sob as restrições $-Ax \leq -b$, que satisfaz a definição \eqref{lp:basic}.

Exemplo C.4: Considere o problema de encontrar um vetor $y$ que maximize $yb$ sob as restrições $yA \leq c$. Esse problema pode ser reescrito assim: maximize $by$ sujeito a $\tr{A} y \leq c$. Assim, o problema dado satisfaz a definição \eqref{lp:basic} de pl.

Exemplo C.5: Considere o problema de maximizar $cx$ sujeito a $Ax \leq b$ e $x \geq 0$. Isso equivale a maximizar $cx$ sob as restrições $Ax \leq b$ e $-\Id x \leq 0$, sendo $\Id$ a matriz identidade com linhas e colunas indexadas pelo conjunto de índices de $x$. Esse segundo problema tem a forma da definição \eqref{lp:basic} de pl: basta tomar a justaposição apropriada das matrizes $A$ e $-\Id$ 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 \eqref{lp:basic} e seja $P$ o poliedro $\conj{x : Ax \leq b}$. Uma solução viável (= feasible solution) do pl é qualquer vetor de $P$. Uma solução ótima do pl é qualquer vetor $x$ de $P$ para o qual $cx$ é máximo.  [Essa terminologia tradicional é um tanto ilógica. Como a definição do pl inclui a maximização de $cx$, 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 $cx$.]  O  pl pode não ter solução ótima porque $P$ é vazio ou porque $cx$ 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 $cx$ não tem máximo, dizemos que o pl é ilimitado (= unbounded).

Suponha agora que o pl \eqref{lp:basic} não é inviável nem ilimitado. Então, como veremos adiante, o pl tem uma solução ótima.

Exemplo C.6: Considere os dois pl's abaixo. O primeiro é inviável e o segundo é ilimitado.

\[ \begin{array}{rcl} \text{maximize} \enspace x_1 + x_2 & \\ \text{sob as restrições} \enspace x_1 + x_2 &\leq& 2\\ x_1 + x_2 &\geq& 3 \end{array} \qquad\qquad\qquad \begin{array}{rcl} \text{maximize} \enspace x_2 & \\ \text{sob as restrições} \enspace x_1 + x_2 &\leq& 3\\ x_1 + x_2 &\geq& 2 \end{array} \]

Exercícios C.1

  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 $cx$ sujeito às restrições $Ax \leq b$.
    \[ \begin{array}{rrrrr@{\qquad}r} -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.3ex] 1& 1& 1& 1& 1& \end{array} \]
  2. Considere o problema de maximizar $cx$ sob as restrições $Ax = b$. Mostre que esse problema satisfaz a definição \eqref{lp:basic} de programa linear.
  3. Considere o pl que consiste em maximizar $cx$ sujeito a $Ax \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\setm J] = 0$, sendo $J$ um subconjunto de $E$. Mostre que $s[J]$ é solução ótima do pl \[ \text{maximize} \enspace c[J]x \enspace \text{sujeito a} \enspace A[V,J]x \leq b\,\text{.} \]

C.2 Dualidade em programação linear

Há uma fundamental relação dualidade entre programas lineares. Considere, por exemplo, o programa linear \begin{equation}\label{lp:reference-primal} \begin{split} \text{maximize} \enspace \ cx & \\ \text{sujeito a} \enspace \ Ax &\leq b\,\text{.} \end{split} \end{equation}

O dual desse pl consiste em encontrar um vetor $y$ que \begin{equation}\label{lp:reference-dual} \begin{split} \text{minimize} \enspace \ yb & \\ \text{sujeito a} \enspace \ yA &= c \ \enspace \text{ e}\\ y &\geq 0\,\text{.} \end{split} \end{equation} A relação básica entre os pl's \eqref{lp:reference-primal} e \eqref{lp:reference-dual} é 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:

Lema C.1 (teorema fraco da dualidade) Para qualquer solução viável $x$ do programa primal \eqref{lp:reference-primal} e qualquer solução viável $y$ do programa dual \eqref{lp:reference-dual} tem-se  $cx \leq yb$.

Prova: A prova da desigualdade decorre da associatividade do produto entre matrizes e vetores: \begin{equation}\label{eq:proof-of-cx-leq-yb} cx \ = \ (yA)x \ = \ y(Ax) \ \leq \ yb\:\text{.} \end{equation} (Note que a prova usa todas as restrições dos dois pl's.) ■

O lema tem a seguinte consequência: se $cx=yb$ 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 $cx=yb$. A recíproca dessa observação é garantida pelo teorema forte da dualidade:

Teorema C.2 (von Neumann) Se os programas lineares \eqref{lp:reference-primal} e \eqref{lp:reference-dual} são viáveis então existe uma solução viável $x$ do primeiro e uma solução viável $y$ do segundo tais que $cx=yb$. Se um dos programas lineares é inviável então o outro é inviável ou ilimitado. ■

A prova do teorema é algorítmica: o algoritmo Simplex recebe $A$, $b$ e $c$, decide se os dois pl's são viáveis e, em caso afirmativo, devolve $x$ e $y$ tais que $cx=yb$.

Corolário C.3 Se o poliedro $\conj{x : Ax \leq b}$ do programa linear \eqref{lp:reference-primal} não é vazio nem ilimitado então o programa tem uma solução ótima que é vértice do poliedro. ■

Corolário C.4 Se $v$ é um vértice do poliedro $\conj{x : Ax \leq b}$ então existe um vetor $c$ tal que $v$ é a única solução do programa linear \eqref{lp:reference-primal}. ■

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

\[ \begin{array}{rcl} \text{maximize} \enspace 2x_1 + x_2 & \\ \text{sujeito a} \enspace -x_1 + x_2 &\leq& 4\\ x_1 - x_2 &\leq& 2\\ x &\geq& 0 \end{array} \qquad\qquad \begin{array}{rcl} \text{minimize} \enspace -4y_1 + 2y_2 & \\ \text{sujeito a} \enspace -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} \text{maximize} \enspace 2x_1 + x_2 & \\ \text{sujeito a} \enspace -x_1 - x_2 &\leq& -4\\ x_1 + x_2 &\leq& 2\\ x &\geq& 0 \end{array} \qquad\qquad\qquad \begin{array}{rcl} \text{minimize} \enspace -4y_1 + 2y_2 & \\ \text{sujeito a} \enspace -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} \text{maximize} \enspace 2x_1 + x_2 & \\ \text{sujeito a} \enspace x_1 - x_2 &\leq& 4\\ % redundante! x_1 - x_2 &\leq& 2\\ % x &\geq& 0 \end{array} \qquad\qquad\qquad \begin{array}{rcl} \text{minimize} \enspace 4y_1 + 2y_2 & \\ \text{sujeito a} \enspace 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} \text{maximize} \enspace 2x_1 + x_2 & \\ \text{sujeito a} \enspace x_1 + x_2 &\leq& 4\\ x_1 - x_2 &\leq& 2\\ x &\geq& 0 \end{array} \qquad\qquad\qquad \begin{array}{rcl} \text{minimize} \enspace 4y_1 + 2y_2 & \\ \text{sujeito a} \enspace y_1 + y_2 &\geq& 2\\ y_1 - y_2 &\geq& 1\\ y &\geq& 0 \end{array} \]

Exercícios C.2

  1. Considere o problema de encontrar $x$ que maximize $cx$ sob as restrições $Ax= 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.
  2. Considere o problema de encontrar $x$ que maximize $x_1+2x_2+3x_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 \enspace \text{e}\\ x_1 + \ph{x_2 +} 4x_3 & = & -20\,\text{.} \end{array} \]

    Qual o dual desse pl? O dual é viável? inviável? ilimitado?

  3. Considere o seguinte pl: encontrar $x$ que maximize $cx$ sob as restrições $Ax \leq b$ e $x\geq 0$. Mostre que o dual desse pl pede um vetor $y$ que minimize $yb$ sob as restrições $yA \geq c$ e $y \geq 0$.
  4. Prove o corolário C.3.
  5. Prove o corolário C.4.
  6. 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{split} Ax + By + Cz &\leq a\\ Dx + Ey + Fz &= b\\ Gx + Hy + Kz &\geq c\\ x &\geq 0\\ z &\leq 0 \end{split} \qquad\qquad \begin{split} uA + vD + wG &\geq d\\ uB + vE + wH &= e\\ uC + vF + wK &\leq f\\ u &\geq 0\\ w &\leq 0 \end{split} \] Suponha que $X\neq\emptyset$ e $Y\neq\emptyset$ e prove que $\max\,\conj{ dx + ey + fz : (x,y,z) \in X} = \min\,\conj{ua + vb + wc : (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 \eqref{lp:reference-primal} e $y$ uma solução viável do pl \eqref{lp:reference-dual}. Para cada índice $i$ em $V$, dizemos que $x$ é justo em $i$ se $(Ax)[i] = b[i]$ e folgado em $i$ se $(Ax)[i] \lt b[i]$. Analogamente, $y$ é justo em $i$ se $y[i] = 0$ e folgado em $i$ se $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.)

Se $x$ é justo sempre que $y$ é folgado (ou, equivalentemente, $y$ é justo sempre que $x$ é folgado), dizemos que as folgas de $x$ e $y$ são complementares (= complementary slack­ness). No caso dos pl's \eqref{lp:reference-primal} e \eqref{lp:reference-dual}, as folgas de $x$ e $y$ são complementares se, para cada índice $i$, \begin{equation}\label{eq:complementary-slackness} (Ax)[i] = b[i] \quad \text{ou} \quad y[i] = 0\,\text{.} \end{equation}

(O ou não é exclusivo, pois podemos ter $(Ax)[i] = b[i]$ e $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$,

se  $(Ax)[i] \lt b[i]$  então  $y[i] = 0\,\text{.}$

O seguinte lema é consequência imediata de \eqref{eq:proof-of-cx-leq-yb}:

Lema C.5 (das folgas complementares) Para qualquer $x$ viável no pl \eqref{lp:reference-primal} e qualquer $y$ viável no pl \eqref{lp:reference-dual}, a igualdade  $cx = yb$  vale se e somente se as folgas de $x$ e $y$ são complementares. ■

Exercícios C.3

  1. ★ Dados números não-negativos $a_1,a_2,\ldots,a_m$ e $b_1,b_2,\ldots,b_m$, suponha que $a_1b_1+a_2b_2+\cdots + a_mb_m = 0$. É verdade que $a_1=\cdots=a_m=0$ ou $b_1=\cdots=b_m=0$? Mostre que, para cada $i$,  $a_i=0$ ou $b_i=0$.
  2. ★ Folgas complementares. Sejam $a$, $b$ e $c$ vetores indexados por um conjunto $E$. Suponha que $a\geq 0$ e $b\leq c$. Prove que $ab = ac$ se e somente se, para cada $e$ em $E$, tem-se $a_e=0$ ou $b_e=c_e$.
  3. Prove o lema C.5. (Veja a prova do lema fraco da dualidade e o exercício acima).
  4. Considere o seguinte pl: minimizar $cx$ sob as restrições $Ax= b$ e $x \geq 0$. Enuncie as condições de folgas complementares.
  5. Considere o seguinte pl: maximizar $cx$ sob as restrições $Ax= b$ e $x \geq 0$. Enuncie o pl dual. Enuncie as condições de folgas complementares para o par de pl's.
  6. Considere o seguinte pl: maximizar $cx$ sujeito às restrições $Ax \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.
  7. Considere o problema de encontrar $x$ que maximize $cx$ sob as restrições $Ax = 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 $cx = yb$ 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  $cx$  sob as restrições  $Ax \leq b$  recebe uma matriz racional $A$, um vetor racional $b$, e um vetor racional $c$ e devolve

  1. um vetor racional $x$ que é solução ótima do problema ou
  2. a informação de que o problema é inviável ou
  3. a informação de que o problema é ilimitado.

Ademais, se o poliedro $\conj{x :Ax \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 al­go­rithm).  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$ e $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 \eqref{lp:reference-primal}. Como tornar evidente que uma dada instância do pl é inviável?  Um vetor de inviabilidade para o pl \eqref{lp:reference-primal} é qualquer vetor $y'$ indexado por $V$ tal que \begin{equation}\label{eq:primal-infeasibility} y'A = 0 \quad \text{e} \quad y' \geq 0 \quad \text{e} \quad y'b \lt 0\text{.} \end{equation}

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

Lema C.6 Se existe um vetor de inviabilidade para o pl \eqref{lp:reference-primal} então o pl é inviável.

Prova: Seja $y'$ um vetor de inviabilidade. Se existisse um vetor $x$ tal que $Ax \leq b$ teríamos \[ 0 = (y'A)x = y' (Ax) \leq y' b \lt 0\text{.} \] A contradição $0 \lt 0$ mostra que um tal vetor $x$ não existe. ■

A recíproca desse lema é conhecida como lema de Farkas e decorre do teorema forte da dualidade:

Lema C.7 (Farkas) Se o programa linear \eqref{lp:reference-primal} é inviável então existe um vetor de inviabilidade para \eqref{lp:reference-primal}. ■

Resultados análogos valem para o pl dual. Um vetor de inviabilidade para o pl \eqref{lp:reference-dual} é qualquer vetor $x'$ indexado por $E$ tal que \begin{equation}\label{eq:dual-infeasibility} Ax' \leq 0 \quad \text{e} \quad cx' > 0\text{.} \end{equation}

Um tal vetor é um certificado da inviabilidade do pl \eqref{lp:reference-dual} por razões análogas à do lema C.6. Vale também a versão apropriada do lema de Farkas.

Exercícios C.5

  1. Mostre que um vetor de inviabilidade para o pl \eqref{lp:reference-primal} poderia ter sido definido pelas condições  $y'A = 0$, $y' \leq 0$ e $y'b > 0$.
  2. ★ Qual a definição apropriada de vetor de inviabilidade para o seguinte pl: encontrar um vetor $x$ que minimize $cx$ sob as restrições $Ax=b$, $1x = 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$.)
  3. Mostre vetores de inviabilidade para os exemplos C.7 a C.9.
  4. Considere o problema de encontrar $x \geq 0$ que maximize $x_1+2x_2+3x_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 + \ph{x_2 +} 4x_3 & = & -20 \end{array} \]
  5. Suponha dado um vetor de inviabilidade para o pl \eqref{lp:reference-primal}. Mostre que o pl dual \eqref{lp:reference-dual} é inviável ou ilimitado.
  6. Suponha dado um vetor de inviabilidade para o pl \eqref{lp:reference-dual}. Mostre que o pl dual \eqref{lp:reference-primal} é inviável ou ilimitado.
  7. 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{equation}\label{lp:basic-integral-lp} \begin{split} \text{maximize} \enspace cz & \\ \text{sob as restrições} \enspace Az &\leq b\,\text{.} \end{split} \end{equation}

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.

www.ime.usp.br/~pf/otimizacao-combinatoria/
Atualizado em 2023-10-01
© Paulo Feofiloff
DCC  |  IME  |  USP