Programação Linear

Motivação

No quotidiano de uma empresa, os gestores são confrontados com opções a tomar: dadas certas restrições e limitações quanto a recursos disponíveis, precisam de escolher rumos que maximizem o lucro da mesma - produzir mais circuitos de um tipo do que outro por serem mais rentáveis, por exemplo.

Da mesma forma, um partido político pode ter de escolher entre "secções estratégicas" a incluir no seu programa eleitoral - cada uma destas secções pode agradar a uma parte do eleitorado e ser pior aceite por outra parte, tendo então de haver uma escolha baseada nos efeitos esperados da inclusão de cada secção no programa.

A programação linear procura desconstruir e chegar a uma resposta concreta para estes problemas, maximizando o ganho consoante um dado conjunto de restrições.

O exemplo dos partidos políticos referido acima é bastante fácil de explicar com a ajuda de uma tabela. Tenhamos os seguintes efeitos da inclusão de certas políticas num programa eleitoral:

Urbano Suburbano Rural
Construção de Estradas 2-2 55 33
Legalização das Drogas Leves 88 22 5-5
Subsídios Agrícolas 00 00 1010
Impostos no Combustível 1010 00 2-2

Aqui, cada coluna corresponde a um círculo eleitoral, enquanto que cada linha corresponde a uma política. Cada círculo eleitoral tem, claro, número diferente de eleitores: respetivamente cem mil, duzentos mil e cinquenta mil eleitores recenseados. Cada entrada na matriz corresponde aos ganhos (em milhares de eleitores) por cada 10001000€ gastos em publicidades.

Como podemos observar, diferentes círculos eleitorais reagem de forma diferente à mesma medida: subsídios agrícolas, por exemplo, são recebidos com enorme satisfação pela população rural, diretamente beneficiada pelos mesmos, enquanto que os setores urbano e suburbano reagem com indiferença, visto que a medida não os afeta diretamente.

O objetivo passará, então, por tentar obter a maioria absoluta (pelo menos 50%50\% dos votos) minimizando os custos. A resposta, claro, será obtida através da programação linear. Antes de introduzir o conceito em si, tentemos formalizar o problema:

Temos que as quantias a gastar por medida em publicidade são dados, respetivamente, por x1,x2,x3x_1, x_2, x_3 e x4x_4. O nosso objetivo passa, então, por minimizar i=14xi\sum_{i=1}^4 x_i. Visto que queremos procurar satisfazer ao máximo o eleitorado, procuramos também que cada círculo eleitoral tenha, no mínimo, 50%50\% dos votos. Assim sendo, iríamos procurar a solução que minimize os custos sujeita às restrições:

2x1+8x2+0x3+10x4505x1+2x2+0x3+0x41003x15x2+10x3+2x425x1,x2,x3,x40.-2x_1 + 8x_2 + 0x_3 + 10x_4 \geq 50\\ 5x_1 + 2x_2 + 0x_3 + 0x_4 \geq 100\\ 3x_1 - 5x_2 + 10x_3 + -2x_4 \geq 25\\ x_1, x_2, x_3, x_4 \geq 0.

Formulações

Formulação Geral - Programação Linear

Procuramos, ao resolver problemas via programação linear, otimizar uma função linear sujeita a um conjunto de restrições (desigualdades) lineares.

Dados um conjunto de números reais [a1,...,an][a_1, ..., a_n] e um conjunto de variáveis [x1,...,xn][x_1, ..., x_n], podemos definir uma função linear para essas variáveis tal que:

f(x1,...,xn)=i=1naixi.f(x_1, ..., x_n) = \sum_{i=1}^n a_i x_i.

Uma função linear pode estar sujeita a um dado conjunto de restrições lineares, igualdades e/ou desigualdades lineares (em relação a um qualquer número real).

Temos que qualquer solução que satisfaça o conjunto de restrições de uma dada função é uma solução exequível, e que o conjunto de soluções deste género corresponde à região exequível da função. Por fim, diz-se que uma dada formulação é exequível se tiver pelo menos uma solução exequível (e não exequível caso contrário).

Tenhamos um conjunto de restrições tal que:

4x1x282x1+x2105x12x22x1,x204x_1 - x_2 \leq 8\\ 2x_1 + x_2 \leq 10\\ 5x_1 - 2x_2 \geq -2\\ x_1, x_2 \geq 0

Temos que a aplicação destas restrições resulta num gráfico tal que:

Ora, a interseção de todas estas restrições resulta num conjunto convexo como o que se apresenta na figura:

Tenhamos ainda que a função objetivo é f(x1,x2)=x1+x2f(x_1, x_2) = x_1 + x_2.

Visto que temos que a maximizar, vamos considerar aqui várias linhas tal que x1+x2=zx_1 + x_2 = z, onde zz é um número real. O objetivo será encontrar o maior número zz tal que a interseção da linha com o conjunto convexo apresentado acima não é vazio - aí, maximizamos o objetivo!

Observemos a imagem abaixo:

Aqui, o valor máximo de zz tal que a interseção da linha com o conjunto convexo apresentado acima não é vazio é 88: todas as retas "abaixo" dela têm valores menores, que não maximizam o objetivo, e nenhuma "acima" tem interseção não vazia com o conjunto convexo. Assim sendo, encontrámos a solução ótima: x1=2x_1 = 2 e x2=6x_2 = 6, com objetivo maximizado x1+x2=8x_1 + x_2 = 8.

Importa realçar que as soluções ótimas para este tipo de problemas encontram-se sempre nos vértices do conjunto convexo. Mais ainda, se a interseção da linha que maximiza o objetivo com o conjunto convexo for um segmento de reta, então os vértices desse segmento são ambos soluções ótimas.

O conjunto convexo, a região que andamos a referir tantas vezes, chama-se Simplex - nome este que vamos ouvir bastante durante esta secção.

São estudadas duas formas de especificar programas lineares - as formas Standard e Slack. Diferem quanto à especificação das respetivas restrições: a primeira opta por especificar as restrições como desigualdades, enquanto que a segunda opta por especificar as restrições como igualdades (exceto para os problemas que requerem variáveis necessariamente não negativas). Olhemos para ambas:

Forma Standard

A forma standard procura maximizar i=1naixi\sum_{i=1}^n a_i x_i, tendo em conta um conjunto de restrições tal que:

i=1naijxjbii{1,...,m}.xj0j{1,...,n}.\sum_{i=1}^n a_{ij} x_j \leq b_i \quad \forall i \in \{1, ..., m\}.\\ x_j \geq 0 \quad \forall j \in \{1, ..., n\}.

Mais ainda, notar que a forma standard requer variáveis com valor não negativo, e que todas as suas desigualdades sejam apresentadas tal que menor-ou-igual-a, não havendo lugar a restrições de igualdade (a importância da orientação do sinal da inequação será claro mais à frente).

Podemos representar o programa de forma mais compacta ainda, recorrendo a uma representação matricial do problema.

Ao criar uma matriz A=(aij)A = (a_{ij}), matriz essa m×nm \times n, e recorrendo a três vetores b=(bi)b = (b_i), c=(cj)c = (c_j) e x=(xj)x = (x_j), podemos representar o programa tal que procuramos maximizar cTxc^T x, tendo em conta as restrições:

Axbx0Ax \leq b \\ x \geq 0

Podemos reparar que as representações coincidem com as apresentadas anteriormente.

A conversão de um programa linear para a forma standard pode não ser trivial: podemos enfrentar problemas com resolução não óbvia.

  • Caso o objetivo seja minimizar o objetivo (em vez de procurar a maximização do mesmo), a solução passa por inverter o sinal de todos os coeficientes da função objetivo (mantendo os das restrições), procurando agora a maximização desse novo objetivo. Por exemplo, minimizar uma função objetivo 3x117x2+4x33x_1 - 17x_2 + 4x_3 seria o mesmo que maximizar 3x1+17x24x3-3x_1 + 17x_2 - 4x_3 (não havendo quaisquer alterações nos coeficientes das restrições).

  • Caso haja variáveis que possam ser negativas, essas mesmas variáveis são substituídas pela diferença de duas variáveis auxiliares, essas sim com a restrição de serem não negativas. Por exemplo, no programa abaixo:

    • Objetivo: Maximizar 2x13x22x_1 - 3x_2
    • Restrições:
      • x1+x2=7x_1 + x_2 = 7
      • x12x24x_1 - 2x_2 \leq 4
      • x10x_1 \geq 0

    Aqui, x2x_2 não apresenta a restrição requerida. Assim sendo, substituímo-la por x2=x2x2x_2 = x_2' - x_2'', ficando então com o programa linear:

    • Objetivo: Maximizar 2x13(x2x2)2x_1 - 3(x_2' - x_2'')
    • Restrições:
      • x1+x2x2=7x_1 + x_2' - x_2'' = 7
      • x12(x2x2)4x_1 - 2(x_2' - x_2'') \leq 4
      • x1,x2,x20x_1, x_2', x_2'' \geq 0
  • Caso haja restrições via igualdade, ao invés de desigualdades, estas são substituídas por um par de desigualdades. Ter f(x1,x2,x3)=bf(x_1, x_2, x_3) = b é equivalente a ter x1+x2+x3bx1+x2+x3bx_1 + x_2 + x_3 \leq b \wedge x_1 + x_2 + x_3 \geq b, pelo que podemos pegar no exemplo imediatamente acima e reescrevê-lo tal que:

    • Objetivo: Maximizar 2x13(x2x2)2x_1 - 3(x_2' - x_2'')
    • Restrições:
      • x1+x2x27x_1 + x_2' - x_2'' \leq 7
      • x1+x2x27x_1 + x_2' - x_2'' \geq 7
      • x12(x2x2)4x_1 - 2(x_2' - x_2'') \leq 4
      • x1,x2,x20x_1, x_2', x_2'' \geq 0
  • Caso haja restrições via desigualdade maior-ou-igual-a, basta apenas trocar os sinais em ambos os lados. Pegando no programa acima, ficaríamos com:

    • Objetivo: Maximizar 2x13(x2x2)2x_1 - 3(x_2' - x_2'')
    • Restrições:
      • x1+x2x27x_1 + x_2' - x_2'' \leq 7
      • x1x2+x27-x_1 - x_2' + x_2'' \leq -7
      • x12(x2x2)4x_1 - 2(x_2' - x_2'') \leq 4
      • x1,x2,x20x_1, x_2', x_2'' \geq 0

    De realçar que a restrição que obriga as variáveis a ser não negativas é mantida.

Por fim, as variáveis com apóstrofes acabariam por ser renomeadas, ficando então com:

  • Objetivo: Maximizar 2x13(x2x3)2x_1 - 3(x_2 - x_3)
  • Restrições:
    • x1+x2x37x_1 + x_2 - x_3 \leq 7
    • x1x2+x37-x_1 - x_2 + x_3 \leq -7
    • x12(x2x3)4x_1 - 2(x_2 - x_3) \leq 4
    • x1,x2,x30x_1, x_2, x_3 \geq 0

Forma Slack

O tratamento que estamos a fazer ao programa não é despropositado - é fulcral para o algoritmo Simplex, abordado mais abaixo, resolver o problema de forma eficiente. O algoritmo, contudo, prefere ainda uma forma diferente de expressar o programa: todas as restrições (exceto as das variáveis serem não negativas) devem ser expressadas sob a forma de igualdade. Para tal, recorremos a ss, uma variável de slack que representa a diferença entre ambos os lados da nova igualdade - a inequação passou a equação, logo algo teve necessariamente de mudar para deixar de ser uma inequação.

Por exemplo, tendo a restrição

i=1naijxjbi\sum_{i=1}^{n} a_{ij}x_j \leq b_i

convertê-la-íamos para a forma Slack tal que:

s=bii=1naijxjs0s = b_i - \sum_{i=1}^{n} a_{ij}x_j\\ s \geq 0

Na forma slack, optamos por escrever as novas igualdades sob a notação xn+ix_{n + i}, ao invés de ss. O exemplo utilizado na forma standard ficaria então:

  • Objetivo: Maximizar 2x13(x2x3)2x_1 - 3(x_2 - x_3)
  • Restrições:
    • x4=7(x1+x2x3)x_4 = 7 - (x_1 + x_2 - x_3)
    • x5=7(x1x2+x3)x_5 = -7 - (-x_1 - x_2 + x_3)
    • x6=4(x12(x2x3))x_6 = 4 - (x_1 - 2(x_2 - x_3))
    • x1,x2,x3,x4,x5,x60x_1, x_2, x_3, x_4, x_5, x_6 \geq 0

Podemos reparar num pormenor interessante: estamos a procurar sempre escrever os xn+ix_{n + i} em função de outras variáveis - neste caso em função das "variáveis iniciais", as da função que pretendemos maximizar. Dizemos que estas variáveis auxiliares (as do lado esquerdo das equações, portanto) são as variáveis básicas, que dependem das outras, e que as restantes são as variáveis não-básicas. Mais ainda, tal como no exemplo do gráfico que foi utilizado acima onde denotámos x1+x2=zx_1 + x_2 = z, temos que na forma slack a função objetivo está definida como

z=i=1ncjxj,z = \sum_{i=1}^{n} c_{j}x_{j},

e que portanto o programa acima na forma slack seria escrito tal que:

z=2x13(x2x3)x4=7(x1+x2x3)x5=7(x1x2+x3)x6=4(x12(x2x3))\begin{aligned} z &= 2x_1 - 3(x_2 - x_3)\\ x_4 &= 7 - (x_1 + x_2 - x_3)\\ x_5 &= -7 - (-x_1 - x_2 + x_3)\\ x_6 &= 4 - (x_1 - 2(x_2 - x_3)) \end{aligned}

Formalizando por fim, a forma slack pode ser então descrita tal que:

  • NN corresponde ao conjunto de índices das variáveis não-básicas;

  • BB corresponde ao conjunto de índices das variáveis básicas;

  • NB=1,2,...,n+mN \cup B = {1, 2, ..., n + m}, com N=n|N| = n e B=m|B| = m;

z=v+i=1ncjxjxi=bii=1naijxjpara iBz = v + \sum_{i=1}^{n} c_{j}x_{j}\\ x_{i} = b_i - \sum_{i=1}^{n} a_{ij}x_j \quad \text{para } i \in B\\

Na função objetivo, vv corresponde a uma constante, cuja utilidade será aparente mais à frente.

Exemplo - Representação Matricial

Tenhamos o seguinte programa na forma slack:

z=28x36x562x63x1=8+x36+x56x63x2=48x332x53+x63x4=18x32+x52\begin{aligned} z &= 28 - \frac{x_3}{6} - \frac{x_5}{6} - \frac{2x_6}{3}\\ x_1 &= 8 + \frac{x_3}{6} + \frac{x_5}{6} - \frac{x_6}{3}\\ x_2 &= 4 - \frac{8x_3}{3} - \frac{2x_5}{3} + \frac{x_6}{3}\\ x_4 &= 18 - \frac{x_3}{2} + \frac{x_5}{2}\\ \end{aligned}

Ora, temos aqui que N={3,5,6}N = \{3, 5, 6\} (as variáveis não-básicas) e B={1,2,4}B = \{1, 2, 4\} (as variáveis básicas).

Voltando a pegar na representação matricial abordada inicialmente na forma Standard, podemos então escrever:

A=(a13a15a16a23a25a26a43a45a46)=(16161383231312120)b=(b1b2b4)=(8418)c=(c3c5c6)T=(161623)Tv=28.\begin{aligned} A &= \begin{pmatrix} a_{13} & a_{15} & a_{16}\\ a_{23} & a_{25} & a_{26}\\ a_{43} & a_{45} & a_{46}\\ \end{pmatrix} = \begin{pmatrix} \frac{-1}{6} & \frac{-1}{6} & \frac{1}{3}\\ \frac{8}{3} & \frac{2}{3} & \frac{-1}{3}\\ \frac{1}{2} & \frac{-1}{2} & 0\\ \end{pmatrix}\\ b &= \begin{pmatrix} b_1\\ b_2\\ b_4\\ \end{pmatrix} = \begin{pmatrix} 8\\ 4\\ 18\\ \end{pmatrix}\\ c &= \begin{pmatrix} c_3 & c_5 & c_6\\ \end{pmatrix}^T = \begin{pmatrix} \frac{-1}{6} & \frac{-1}{6} & \frac{-2}{3}\\ \end{pmatrix}^T\\ v &= 28. \end{aligned}

Podemos então notar que, de forma sucinta:

  • As colunas de AA correspondem às variáveis não-básicas, NN;
  • As linhas de AA correspondem às variáveis básicas, BB;
  • As entradas de AA correspondem aos coeficientes de cada variável não básica na equação associada a cada variável básica do conjunto de restrições;

Mais ainda, as linhas da matriz vertical bb correspondem à variável de slack de cada igualdade do conjunto de restrições associada a cada variável básica. Para além disso, c3,c5,c6c_3, c_5, c_6 em cc correspondem aos coeficientes de cada variável não básica na função objetivo.

Algoritmo Simplex

O Algoritmo Simplex corresponde à abordagem clássica para resolver problemas de otimização linear. Tem por base a interpretação geométrica (o conjunto convexo) apresentada no início desta página. Funciona como uma espécie de "eliminação de Gauss-Jordan" para inequações.

A ideia por detrás do algoritmo poderá ser entendida mais facilmente com a ajuda de um exemplo. Tenhamos o seguinte programa linear na forma slack:

z=3x1+x2+2x3x4=30x1x23x3x5=242x12x23x3x6=364x1x22x3\begin{aligned} z &= 3x_1 + x_2 + 2x_3\\ x_4 &= 30 - x_1 - x_2 - 3x_3\\ x_5 &= 24 - 2x_1 - 2x_2 - 3x_3\\ x_6 &= 36 - 4x_1 - x_2 - 2x_3 \end{aligned}

Inicialmente, olhamos para a solução básica para o problema: colocamos todas as variáveis não-básicas a zero, ficando com a solução igual a (0,0,0,30,24,36)(0, 0, 0, 30, 24, 36), z=30+10+20=0z = 3 \cdot 0 + 1 \cdot 0 + 2 \cdot 0 = 0. Se for exequível, dizemos que o programa tem uma uma solução básica exequível.

O algoritmo procura, a cada iteração, reescrever as equações do programa, de forma a encontrar diferentes soluções para o mesmo. Além disso, temos que as alterações que faremos serão sempre com vista a não decrescer zz - não tem necessariamente de aumentar, mas nunca irá diminuir entre iterações.

Para reescrever as igualdades, pegamos na variável não-básica do programa cujo coeficiente no objetivo é mais positivo e olhamos para as variáveis básicas, procurando pensar "qual é o máximo que posso aumentar a variável não-básica sem que as variáveis básicas se tornem negativas". Mais ainda, temos que o algoritmo termina quando todas as variáveis não-básicas do objetivo tiverem coeficientes negativos. Temos então de olhar para cada uma das restrições e procurar qual a variável a alterar (e como) em relação ao programa acima, qual é o máximo que podemos aumentar x1x_1 (já que tem o coeficiente mais positivo)?

  • x4=30x1x23x3x_4 = 30 - x_1 - x_2 - 3x_3. Igualando todas as variáveis exceto x1x_1 a zero, obtemos uma maximização de x1x_1 para esta restrição: x1=30x_1 = 30;

  • x5=242x12x25x3x_5 = 24 - 2x_1 - 2x_2 - 5x_3 - fazemos o mesmo que acima, ficando com x1=12x_1 = 12;

  • x6=364x1x22x3x_6 = 36 - 4x_1 - x_2 - 2x_3 - fazemos o mesmo que acima, ficando com x1=9x_1 = 9. Esta é a restrição mais apertada, dando então o máximo que podemos aumentar x1x_1.

Temos, então, que uma restrição no programa reescrito será x1=9x24x32x64x_1 = 9 - \frac{x_2}{4} - \frac{x_3}{2} - \frac{x_6}{4} (vem da última restrição, a que considerámos apertada, escrita agora com x1x_1 em função das outras variáveis).

Descoberta a restrição mais apertada, trocamos os papéis de x1x_1 e x6x_6, tanto nas restrições como no objetivo, ficando com um programa tal que:

z=27+x24+x323x64x1=9x24x32x64x4=213x245x32+x64x5=63x224x3+x62\begin{aligned} z &= 27 + \frac{x_2}{4} + \frac{x_3}{2} - \frac{3x_6}{4}\\ x_1 &= 9 - \frac{x_2}{4} - \frac{x_3}{2} - \frac{x_6}{4}\\ x_4 &= 21 - \frac{3x_2}{4} - \frac{5x_3}{2} + \frac{x_6}{4}\\ x_5 &= 6 - \frac{3x_2}{2} - 4x_3 + \frac{x_6}{2} \end{aligned}

De realçar que as duas últimas restrições e o objetivo foram obtidos substituindo x1x_1 pelo lado direito da nova igualdade que envolve x1x_1 como variável básica: 9x24x32x649 - \frac{x_2}{4} - \frac{x_3}{2} - \frac{x_6}{4}.

A operação que foi agora realizada, esta troca entre uma variável básica e uma não-básica, é a Operação Pivot. Numa pivotagem, consideramos a variável não-básica x1x_1 a variável de entrada (vai entrar no conjunto das variáveis básicas), e a variável básica x6x_6 a variável de saída (vai sair do conjunto de variáveis básicas). O algoritmo Simplex procura, então, realizar pivotagens sucessivas até não haver mais soluções básicas exequíveis - até todos os coeficientes das variáveis não-básicas na função objetivo serem negativos.

Voltamos então a igualar todas as variáveis não-básicas a zero, ficando com solução igual a (9,0,0,21,6,0)(9, 0, 0, 21, 6, 0) e z=27z = 27.

De seguida, procuramos reescrever novamente o problema: desta vez, foquemo-nos na variável x3x_3, a variável não-básica com coeficiente mais positivo no objetivo. Aqui, a terceira restrição (a que tem x5x_5 como variável básica) é a mais apertada, restringindo x3x_3 a 66. Assim sendo, o programa reescrito será (e tendo em conta agora x3=323x28x54+x68x_3 = \frac{3}{2} - \frac{3x_2}{8} - \frac{x_5}{4} + \frac{x_6}{8}):

z=1114+x216x5811x616x1=334x216+x585x616x3=323x28x54+x68x4=694+3x216+5x58x616\begin{aligned} z &= \frac{111}{4} + \frac{x_2}{16} - \frac{x_5}{8} - \frac{11x_6}{16}\\ x_1 &= \frac{33}{4} - \frac{x_2}{16} + \frac{x_5}{8} - \frac{5x_6}{16}\\ x_3 &= \frac{3}{2} - \frac{3x_2}{8} - \frac{x_5}{4} + \frac{x_6}{8}\\ x_4 &= \frac{69}{4} + \frac{3x_2}{16} + \frac{5x_5}{8} - \frac{x_6}{16} \end{aligned}

O objetivo zz é, então, aumentado para 1114\frac{111}{4}.

Por fim, reescrevemos o programa tendo em conta x2x_2 (a única variável não-básica com coeficiente positivo restante), ficando com:

z=28x36x562x63x1=8+x36+x56x63x2=48x332x53+x63x4=18x32+x52.\begin{aligned} z &= 28 - \frac{x_3}{6} - \frac{x_5}{6} - \frac{2x_6}{3}\\ x_1 &= 8 + \frac{x_3}{6} + \frac{x_5}{6} - \frac{x_6}{3}\\ x_2 &= 4 - \frac{8x_3}{3} - \frac{2x_5}{3} + \frac{x_6}{3}\\ x_4 &= 18 - \frac{x_3}{2} + \frac{x_5}{2}. \end{aligned}

Chegámos, assim, a um ponto em que todas as variáveis não-básicas na função objetivo têm coeficiente negativo. Assim sendo, podemos dar o algoritmo por terminado, dizendo que a solução ótima para o programa é (8,4,0,18,0,0)(8, 4, 0, 18, 0, 0), com z=28z = 28.

Solução Exequível Inicial

A conversão de um programa linear para a forma slack nem sempre é simples. Vejamos o caso abaixo:

  • Objetivo: Maximizar 2x1x22x_1 - x_2;
  • Restrições:
    2x1x22x15x24x1,x20.2x_1 - x_2 \leq 2\\ x_1 - 5x_2 \leq -4\\ x_1, x_2 \geq 0.

Ao igualar x1x_1 e x2x_2 a 00, a segunda restrição é desrespeitada (ficamos com 040 \leq -4) - não há uma solução exequível inicial. Podemos, contudo, verificar se o programa tem alguma solução exequível, recorrendo a um programa auxiliar.

Seja LL um programa linear na forma standard, LauxL_{aux} é definido tal que:

  • Objetivo: Maximizar x0-x_0;
  • Restrições:
    i=1naijxjx0bi,i=1,2,...,mxj0,j=0,1,2,...,n. \sum_{i=1}^{n} a_{ij}x_j - x_0 \leq b_i, \quad i = 1, 2, ..., m\\ x_j \geq 0, \quad j = 0, 1, 2, ..., n.

Temos assim que LL só é exequível caso o valor ótimo para o objetivo de LauxL_{aux} seja 00 (a prova será adicionada num futuro próximo).

Comecemos com o programa linear inicial abaixo:

  • Objetivo: Maximizar 2x1x22x_1 - x_2;
  • Restrições:
    2x1x22x15x24x1,x20.2x_1 - x_2 \leq 2\\ x_1 - 5x_2 \leq -4\\ x_1, x_2 \geq 0.

Temos que a solução básica não é exequível (ficaríamos com 040 \leq -4). Assim sendo, construímos um programa linear auxiliar tal que:

  • Objetivo: Maximizar x0-x_0;
  • Restrições:
    2x1x2x02x15x2x04x1,x2,x00.2x_1 - x_2 - x_0 \leq 2\\ x_1 - 5x_2 - x_0 \leq -4\\ x_1, x_2, x_0 \geq 0.

O programa encontra-se atualmente na forma standard. A sua conversão para a forma slack é trivial:

z=x0x3=22x1+x2+x0x4=4x1+5x2+x0x1,x2,x0,x3,x40.z = -x_0\\ x_3 = 2 - 2x_1 + x_2 + x_0\\ x_4 = -4 - x_1 + 5x_2 + x_0\\ x_1, x_2, x_0, x_3, x_4 \geq 0.

O primeiro passo ao resolver os programas auxiliares passa sempre por pivotar x0x_0 - o algoritmo estaria concluído caso contrário, já temos o z=x0z = -x_0 pretendido. Optamos, aqui, por pivotar x0x_0 com a restrição que contiver a constante mais negativa - neste caso, pivotando x0x_0 com a restrição que contém x4x_4 como variável básica, tal que:

z=4x1+5x2x4x0=4+x15x2+x4x3=6x14x2+x4\begin{aligned} z &= -4 - x_1 + 5x_2 - x_4\\ x_0 &= 4 + x_1 - 5x_2 + x_4\\ x_3 &= 6 - x_1 - 4x_2 + x_4\\ \end{aligned}

Este programa apresenta solução básica exequível! Aplicaríamos agora o algoritmo Simplex normalmente até obter uma solução para este programa auxiliar tal que z=x0z = -x_0: caso tal solução exista, o programa original é exequível, e partiremos da solução aqui encontrada quando voltarmos ao programa original. A solução para o programa auxiliar seria (depois de alguns passos):

z=x0x2=45x05+x15+x45x3=145+4x059x15+x45\begin{aligned} &z = -x_0\\ &x_2 = \frac{4}{5} - \frac{x_0}{5} + \frac{x_1}{5} + \frac{x_4}{5}\\ &x_3 = \frac{14}{5} + \frac{4x_0}{5} - \frac{9x_1}{5} + \frac{x_4}{5} \end{aligned}

Teríamos, então, uma solução tal que (0,45,145,0)(0, \frac{4}{5}, \frac{14}{5}, 0).

Para resolver o problema inicial, substituiríamos o objetivo z=x0z = x_0 pelo original (substituindo x2x_2 no objetivo pela restrição x2x_2 acima), e mantendo o conjunto de restrições praticamente intacto, com exceção da remoção de qualquer referência a x0x_0 nas mesmas. Procuraríamos, então, resolver:

z=2x1x2=2x1(45+x15+x45)=45+9x15x45x2=45+x15+x45x3=1459x15+x45\begin{aligned} &z = 2x_1 - x_2 = 2x_1 - (\frac{4}{5} + \frac{x_1}{5} + \frac{x_4}{5}) = - \frac{4}{5} + \frac{9x_1}{5} - \frac{x_4}{5}\\ &x_2 = \frac{4}{5} + \frac{x_1}{5} + \frac{x_4}{5}\\ &x_3 = \frac{14}{5} - \frac{9x_1}{5} + \frac{x_4}{5} \end{aligned}

A partir daqui, resolveríamos este programa linear com a ajuda do algoritmo Simplex.

Teorema Fundamental da Programação Linear

Pegando num qualquer programa linear na forma standard, este tem três possibilidades (só podendo pertencer a uma delas):

  • Tem uma solução ótima com valor objetivo finito, valor esse que pode ser obtido num dos vértices da respetiva região exequível;

  • É não exequível;

  • É unbounded, não limitado: o valor objetivo pode ser arbitrariamente maximizado.

Abaixo encontra-se o gráfico correspondente a um programa linear unbounded. Podemos notar que há infinitas retas que maximizam o valor objetivo, cada uma com zz arbitrariamente maior que a anterior, e todas elas cuja interseção com a região exequível é não vazia:

Como nota final, resta afirmar que caso após (n+mn)\binom{n + m}{n} iterações o algoritmo ainda não tenha terminado, podemos admitir que este está em ciclo. Há, ao todo, n+mn + m variáveis e mm formas de escolher BB, pelo que há (n+mn)\binom{n + m}{n} formas de slack únicas - mais que isso e o algoritmo está em ciclo. São raros, mas existem, e para os eliminar recorre-se à Regra de Bland: em caso de empate na escolha de variáveis, escolhe-se sempre a variável com menor índice.

Dualidade

Em programação linear, a dualidade é uma propriedade associada à própria análise de um problema: podemos exprimir um programa de duas maneiras diferentes, com soluções equivalentes, com a diferença principal entre elas a ser o objetivo pretendido: maximizar ou minimizar um dado objetivo. Vamos, nesta secção, finalmente aproveitar a representação matricial de um programa linear introduzida mais acima.

Pensemos então num exemplo concreto. Uma empresa procura maximizar o lucro obtido ao vender dois produtos, xx e yy, sendo que:

  • vende uma unidade do produto xx por 11 euro e uma unidade do produto yy por 66 euros (consideremos que produzir o produto não tem qualquer custo monetário);
  • gasta uma hora a produzir 11 produto (seja ele xx ou yy);
  • pode gastar no máximo 200200 horas a produzir xx;
  • pode gastar no máximo 300300 horas a produzir yy;
  • ao todo, a combinação das horas gastas para produzir xx e yy não pode ultrapassar 400400 horas.

Podemos procurar escrever o problema apresentado como um programa linear, tal que:

maxx+6ys.a:x200y300x+y400x,y0\begin{aligned} max \quad&x + 6y\\ s.a: \quad&x \leq 200\\ &y \leq 300\\ &x + y \leq 400\\ &x, y \geq 0 \end{aligned}

Chamemos a este programa o programa Primal. A aplicação do algoritmo Simplex neste programa levaria a uma solução ótima com x=100y=300    z=1900x = 100 \wedge y = 300 \implies z = 1900. Podemos, contudo, tentar perceber de maneira diferente no problema: e se o nosso objetivo for minimizar as horas de produção despendidas, tendo em conta certas margens de lucro que queremos ter? A dualidade entra precisamente aqui: vamos procurar construir um outro programa, o respetivo programa Dual, que procurará representar esse mesmo espelho de restrições:

min200λ1+300λ2+400λ3s.a:λ1+λ31λ2+λ36λ1,λ2,λ30\begin{aligned} min \quad &200\lambda_1 + 300\lambda_2 + 400\lambda_3\\ s.a: \quad&\lambda_1 + \lambda_3 \geq 1\\ &\lambda_2 + \lambda_3 \geq 6\\ &\lambda_1, \lambda_2, \lambda_3 \geq 0 \end{aligned}

A solução ótima também seria aqui 19001900: (λ1,λ2,λ3)=(0,5,1)(\lambda_1, \lambda_2, \lambda_3) = (0, 5, 1) leva ao objetivo 0+3005+4001=19000 + 300 * 5 + 400 * 1 = 1900, que bate certo com a solução ótima do programa Primal.

Há uma mnemónica relativamente simples a ter em conta para esta transformação:

Primal Dual
Variáveis Restrições
Restrições Variáveis
Max Min

A regra, pegando então na representação matricial do programa, é a seguinte:

maxcTxs.a:Axbx0DualminyTbs.a:yTAcTy0\begin{aligned} max \quad& c^T x\\ s.a: \quad&A x \leq b\\ &x \geq 0 \end{aligned} \xRightarrow{\text{Dual}} \begin{aligned} min \quad& y^T b\\ s.a: \quad&y^T A \geq c^T\\ &y \geq 0 \end{aligned}

Pela Dualidade Fraca, sendo xx^* uma solução do programa Primal e yy^* uma solução do respetivo Dual, então

cTx(y)Tb.c^T x^* \leq (y^*)^T b.

Podemos olhar para o que está a acontecer através de um esboço das hipotéticas regiões exequíveis de um programa Primal e respetivo Dual:

Fica então aparente que os programas são em tudo semelhantes (em espelho): um deles procura minimizar um dado objetivo, o Dual, e vai minimizá-lo tanto quanto possível, até um ponto em que coincide com a solução ótima do programa Primal.

Por fim, olhamos para a Dualidade Forte, que nos diz que:

  • a solução ótima do programa Primal coincide com a solução ótima do programa Dual, caso ela exista;

  • o programa Primal tem solução se e apenas se o respetivo Dual tem solução.