Programação linear

Uma oficina produz quantidades $x$ e $y$ de dois produtos divisíveis. O lucro depende das quantidades e as capacidades limitam as combinações possíveis. A programação linear, ou LP, otimiza uma função linear sob restrições lineares, com variáveis reais que podem tomar valores fracionários.

Vamos conservar o mesmo plano desde a formulação até aos pivôs de Simplex e ao certificado dual. Cada transformação tem de preservar as decisões permitidas e o valor do objetivo, para que o certificado final fale do problema original.

Modelar um plano de produção

O lucro por unidade é 3 e 2. A capacidade conjunta é 4 unidades, a capacidade exclusiva do primeiro produto é 2 e a do segundo é 3. O modelo é

$$\max 3x+2y$$

sujeito a

$$x+y\le4,\qquad x\le2,\qquad y\le3,\qquad x,y\ge0.$$

Se só pudéssemos fabricar produtos inteiros, teríamos de acrescentar integridade, o tema da programação inteira. Uma restrição $xy\le4$ não é linear; uma multiplicação por uma constante, como $2x$, é.

O conjunto de pontos que respeitam as restrições é a região admissível, uma interseção de semiespaços. É convexa: o segmento entre dois pontos admissíveis também é admissível.

Vértice	Objetivo $3x+2y$
$(0,0)$	0
$(2,0)$	6
$(2,2)$	10
$(1,3)$	9
$(0,3)$	6

O ótimo é $(2,2)$, lucro 10. Numa região admissível não vazia em forma standard, se o objetivo tem ótimo finito, existe uma solução ótima num vértice. Isso não significa que todos os ótimos sejam vértices: uma função paralela a uma face pode ter uma face inteira de ótimos.

Viável, limitado e ótimo são factos diferentes

Um LP pode ser inviável, ter ótimo finito ou ter objetivo ilimitado. As restrições $x+y\le1$ e $x+y\ge3$ são incompatíveis, portanto inviáveis.

A região $x\ge1$, $y\ge0$ é ilimitada. Mesmo assim, minimizar $x+y$ tem ótimo finito 1 em $(1,0)$, enquanto maximizar $x+y$ é ilimitado. O tamanho geométrico da região não determina sozinho o comportamento do objetivo.

Se maximizarmos $x+y$ na região do exemplo, todos os pontos do segmento entre $(2,2)$ e $(1,3)$ atingem 4. Empates não autorizam escolher um ponto fora das restrições.

Forma standard

Usamos a convenção

$$\max c^Tx\quad\text{sujeito a }Ax\le b,\quad x\ge0.$$

$A$ tem $m$ linhas, uma por restrição, e $n$ colunas, uma por variável. $b$ guarda limites e $c$ coeficientes do objetivo. Para o plano,

$$A=\begin{pmatrix}1&1\\1&0\\0&1\end{pmatrix},\quad b=\begin{pmatrix}4\\2\\3\end{pmatrix},\quad c=\begin{pmatrix}3\\2\end{pmatrix}.$$

Podemos converter outras formas:

• Minimizar $c^Tx$ equivale a maximizar $-c^Tx$.
• Multiplicar uma desigualdade $a^Tx\ge b$ por $-1$ dá $-a^Tx\le-b$.
• Uma igualdade é o par de desigualdades opostas.
• Uma variável livre pode ser escrita como $x_j=x_j^+-x_j^-$, com as duas parcelas não negativas.

Por exemplo, minimizar $2x-y$ sujeito a $x+y=3$, $y\ge1$ e $x\ge0$, com $y$ livre de restrição de sinal explícita, pode escrever-se com $y=y^+-y^-$ e $y^+,y^-\ge0$:

$$\max -2x+y^+-y^-,$$ $$x+y^+-y^-\le3,\quad -x-y^++y^-\le-3,\quad -y^++y^-\le-1.$$

A igualdade deu duas desigualdades e o limite inferior mudou de sinal. Uma solução original dá uma solução nova tomando $y^+=\max(y,0)$ e $y^-=\max(-y,0)$. Uma solução nova recupera $y=y^+-y^-$. O objetivo novo é o negativo do original, logo maximizar um minimiza o outro.

A forma standard não exige $b\ge0$; esse sinal é relevante para a solução inicial de Simplex.

Forma slack e solução básica

Acrescentamos variáveis de folga não negativas:

$$s_1=4-x-y,\qquad s_2=2-x,\qquad s_3=3-y.$$

Inicialmente, $x,y$ são não básicas e fixadas a zero; as folgas são básicas e ficam $(4,2,3)$. Esta solução básica é admissível porque as folgas são não negativas. Os conjuntos de variáveis básicas $B$ e não básicas $N$ mudam em cada pivô; não são propriedades permanentes de uma variável.

Na forma slack, o objetivo é um valor constante mais uma combinação das não básicas. Aumentar uma não básica com coeficiente positivo melhora o objetivo num problema de maximização, até alguma básica chegar a zero.

Dois pivôs de Simplex

Começamos com $z=3x+2y$. Fazemos $x$ entrar. Para aumentar $x$, as restrições com coeficiente que o limita dão razões $4/1$ para $s_1$ e $2/1$ para $s_2$. A menor é 2, portanto $s_2$ sai. A folga $s_3=3-y$ não limita $x$, porque o coeficiente de $x$ nessa linha é $0$; razões só usam linhas onde a entrada tem coeficiente positivo. Se nenhuma linha limitasse $x$, o objetivo seria ilimitado nessa direção.

Isola $x=2-s_2$ e substitui em todas as equações:

$$s_1=2+s_2-y,\qquad s_3=3-y,\qquad z=6-3s_2+2y.$$

Com não básicas $s_2=y=0$, temos $x=2$, $s_1=2$, $s_3=3$, objetivo 6. Agora $y$ tem coeficiente positivo. As razões que limitam o aumento são 2 por $s_1$ e 3 por $s_3$. $s_1$ sai e $y$ entra:

$$y=2+s_2-s_1,\qquad x=2-s_2,$$ $$s_3=1-s_2+s_1,\qquad z=10-s_2-2s_1.$$

Com $s_1=s_2=0$, obtemos $x=y=2$, $s_3=1$ e $z=10$. Todos os coeficientes das não básicas no objetivo são não positivos, e como são variáveis não negativas, não há solução admissível com objetivo superior a 10 neste dicionário.

Regra da razão e casos especiais

A variável que sai minimiza a razão entre valor atual da básica e o coeficiente positivo que limita a entrada. Ignora coeficientes que não limitam um aumento. Se nenhum limita uma variável que melhora o objetivo, podemos aumentá-la sem fim e o objetivo é ilimitado.

Razões empatadas podem produzir vários pivôs válidos. Uma básica já a zero pode sair sem melhorar o objetivo, um pivô degenerado. Isso pode originar ciclos com certas regras. A regra de Bland escolhe a variável elegível de menor índice para entrar e, nos empates da razão, a de menor índice para sair; evita ciclos. Simplex é muito usado, mas tem pior caso exponencial. Existem algoritmos polinomiais para LP, por exemplo métodos de ponto interior, sob o modelo de entrada racional.

Encontrar uma solução inicial

Se algum termo independente for negativo, fixar as não básicas a zero pode dar uma folga negativa. Isso não prova que o LP é inviável: prova apenas que esta base inicial não serve.

Uma fase I introduz variáveis artificiais e otimiza um objetivo auxiliar que mede a violação necessária para obter uma base admissível. Se o melhor ainda exigir uma quantidade artificial positiva, o problema original é inviável. Se a quantidade artificial pode chegar a zero, retira as artificiais, ajusta a base quando necessário e repõe o objetivo original para a fase II.

Por exemplo, $x\ge2$ escreve-se $-x\le-2$. A folga inicial seria $s=x-2=-2$ em $x=0$, mas $x=2$ é admissível. Declarar inviabilidade só pelo termo negativo rejeitaria esta solução válida.

Para iniciar a fase I deste exemplo, escreve $x-s+a=2$, com $x,s,a\ge0$ e artificial $a$. A base $a=2$, com $x=s=0$, é admissível para o problema auxiliar que minimiza $a$. Aumentar $x$ até 2 leva $a$ a zero; retirando $a$, fica $x-s=2$, uma base admissível para o problema original. Se o mínimo auxiliar fosse positivo, não conseguiríamos satisfazer a igualdade sem a artificial.

Dualidade

Ao primal $\max c^Tx$ com $Ax\le b$, $x\ge0$, corresponde o dual

$$\min b^Ty\quad\text{sujeito a }A^Ty\ge c,\quad y\ge0.$$

As variáveis duais podem ser vistas como preços dos recursos. O preço combinado dos recursos necessários a um produto deve cobrir o seu lucro, criando um limite superior para o lucro total.

Para qualquer primal admissível $x$ e dual admissível $y$,

$$c^Tx\le y^TAx\le y^Tb.$$

A primeira desigualdade usa $A^Ty\ge c$ e $x\ge0$; a segunda usa $Ax\le b$ e $y\ge0$. Esta é a dualidade fraca. Se encontramos soluções admissíveis com os mesmos objetivos, ambas são ótimas. A dualidade forte garante a igualdade dos ótimos quando há ótimo finito nas condições usuais de LP.

No exemplo, o dual minimiza $4y_1+2y_2+3y_3$, sujeito a $y_1+y_2\ge3$ e $y_1+y_3\ge2$, com $y_i\ge0$. A solução $(2,1,0)$ dá 10. O primal $(x,y)=(2,2)$ também dá 10; isto certifica o ótimo sem depender da sequência de pivôs.

A folga complementar liga restrições e preços: um recurso com folga positiva tem preço dual zero numa solução ótima; uma variável primal positiva exige que a restrição dual correspondente esteja em igualdade. Aqui sobrou uma unidade do terceiro recurso e $y_3=0$.

Como verificar um modelo

Substitui a solução em todas as restrições e calcula o objetivo nas unidades originais. Confirma se frações são admissíveis, se limites são superiores ou inferiores e se faltam decisões, como um produto obrigatório ou um custo de ativação. Um solver resolve o modelo fornecido; não deteta por si só que omitiste uma regra do problema.