3 - Resolução por programação linear

3 - Resolução por programação

linear

A primeira investigação geral do problema do casamento foi a teoria de Gale; Shapley (1962), isto é, o algoritmo de deferred acceptance, seguida de seu desenvolvimento pelos trabalhos dos próprios David Gale e Lloyd Shapley e, também, Alvin Roth, Marilda Sotomayor e outros pesquisadores.

Entretanto, a própria execução uma a uma das rodadas de propostas, descrita no capítulo anterior, não foi a única solução encontrada. Sendo assim, outro método de resolução, interessante para nossa discussão, é a formulação desse problema na forma de otimização linear.

Nossa apresentação será baseada no trabalho de John Vande Vate – como exposto em Gusfield; Irving (1989), mas, para tanto, faremos uma introdução breve à programação linear, sobre a qual o leitor encontrará maiores detalhes em Lins; Calôba (2006) e Brown; Sherbert (1984).

3.1 Programação linear

O exercício 37 de Brown; Sherbert (1984, p. 118) requer fazer e vender bolos, tortas e dúzias de biscoito de acordo com a seguinte proporção de ingredientes:

ingrediente\produto bolo torta dúzia de biscoitos maçãs 3 10 1 xícaras de açúcar 1 2 3 xícaras de farinha 2 3 1

Para isso, temos à disposição 840 maçãs, 630 xícaras de açúcar e 450 xícaras de farinha.

Por outro lado, os bolos são vendidos por R$ 8, as tortas por R$ 6 e os pacotes de uma dúzia de biscoitos por R$ 5. De modo a melhor utilizar os ingredientes, desejamos maximizar o valor das vendas, o que significa que desejamos maximizar a função objetivo V = 8x + 6y + 5z, sendo:

x = número de bolos;

y = número de tortas;

z = número de dúzias de biscoitos.

Observação: O valor total das vendas é a soma das quantidades vendidas multiplicadas pelos respectivos valores unitários. (Note que, se tivéssemos os custos unitários dos ingredientes, poderíamos calcular o custo total e subtraí-lo do valor das vendas, para tentar maximizar apenas o lucro líquido.)

Essa função V está definida em um domínio, isto é, uma região do espaço tridimensional Oxyz delimitada pelas seguintes inequações, devido ao fato de que, para produzirmos tais alimentos, estamos sujeitos às quantidades disponíveis dos ingredientes:

3x + 10y + 1z ≤ 840

1x + 2y + 3z ≤ 630

2x + 3y + 1z ≤ 450

e, por uma questão de lógica,

x, y, z ≥ 0.

A partir dessas equações, montamos uma matriz chamada "tableau", que explicamos a seguir:

A 1ª coluna é fixa; as 2ª, 3ª e 4ª colunas correspondem às proporções de uso dos ingredientes disponíveis em cada produto, respectivamente, bolos, tortas e dúzias de biscoito; as 5ª, 6ª e 7ª colunas correspondem às possíveis sobras de maçãs, açúcar e farinha, ou seja, são as quantidades adicionais (também consideradas como variáveis) necessárias para transformar as desigualdades em equações; a 8ª coluna considera o total de ingredientes disponíveis. Dessa forma, na 1ª linha, os valores se referem à função objetivo, mas com os sinais trocados porque, de fato, V – 8x – 6y – 5z = 0, enquanto que a 2ª linha é uma relação das informações sobre as maçãs; a 3ª com as informações sobre o açúcar e a 4ª com as informações sobre a farinha.

As variáveis que identificam as sobras dos ingredientes adquirem nomes variados na literatura, como "variáveis de folga" ou slack variables.

Uma vez montado o tableau, utilizamos o algoritmo Simplex para resolução do problema. É preciso notar que tanto o tableau que montamos como a descrição das etapas do Simplex são específicas a esse tipo de problema. Outras questões de otimização linear são resolvidas de modo diferente.

1º passo: Procurar pela entrada "mais negativa" na primeira linha e selecioná-la; chamamos sua coluna de "coluna pivô". Notamos que o número – 8 é a entrada mais negativa, por isso sua coluna será a "coluna pivô":

2º passo: Em separado, dividir as entradas da última coluna pelas entradas positivas da "coluna pivô" e procurar o menor quociente. Assim:

A linha do menor quociente obtido é, então, identificada como "linha pivô", sendo que a célula de interseção desta linha com a "coluna pivô" será chamada de pivô. Notamos que o quociente 225 é o menor, de forma que, sendo ele o quociente de 450 por 2, a última linha será a "linha pivô", assim como o número 2 é o pivô ao estar na célula em que a "coluna pivô" é interceptada pela "linha pivô":

3º passo: Em seguida, dividimos a linha pelo valor do pivô e usamos as operações de escalonamento para zerar o restante da coluna. Isto é, na 1ª linha, somamos a ela a multiplicação da nova 4ª linha por 8; na 2ª linha, subtraímos dela a multiplicação da nova 4ª linha por 3, enquanto que, na 3ª linha, somente subtraímos dela a nova 4ª linha:

Esses passos são repetidos até que não haja mais entradas negativas na primeira linha. No caso deste exemplo, ainda há uma entrada negativa – 1, localizada na 4ª coluna (nova "coluna pivô"). Então procuramos a nova "linha pivô", dividindo os valores da última coluna pelos positivos da nova "coluna pivô":

Como o menor quociente é 162, notamos que o novo pivô é 2,5.

Dessa forma, o próximo passo é dividir a nova "linha pivô" pelo valor do pivô 2,5 e, utilizando escalonamento, zerar os demais valores dessa coluna. Assim, na 1ª linha, somamos a nova 3ª linha; na 2ª linha, somamos o quociente da nova 3ª linha por 2, enquanto que, na 4ª linha, subtraímos o quociente da nova 3ª linha por 2. Temos, então:

Com base neste último tableau, como não temos mais entradas negativas na primeira linha, chegamos à tabela final. Sua interpretação é a seguinte: sua última coluna contém o valor máximo de V e os valores das variáveis x, y, z, identificadas a partir das colunas que formam a matriz identidade, sendo que as demais variáveis são nulas.

Neste exemplo, descobrimos que, ao maximizar as vendas, ganhamos R$ 1962 (brutos). Para isso, fazemos e vendemos 144 bolos: percebemos que na 2ª coluna, dos bolos, ocorre somente uma única vez o número 1; a interseção de sua linha com a última coluna determina a quantidade de bolos feitos. Também fazemos e vendemos 162 dúzias de biscoito: percebemos que, na 4ª coluna dos biscoitos, ocorre somente uma única vez o número 1; a interseção de sua linha com a última coluna determina a quantidade de dúzias de biscoito feitas.

Entretanto, não fazemos nenhuma torta, dado que sua coluna (3ª coluna) não é composta por zeros e um único 1. Contudo, a 5ª coluna, das sobras de maçãs, tem esse formato. Consequentemente, a interseção da linha restante (2ª linha) com a última coluna determina o saldo de 246 maçãs, isto é, que sobraram.

Como funciona e quando não funciona

O algoritmo Simplex é só quinze anos mais velho que o de Gale-Shapley e tem sido estudado profusamente. Faremos somente um resumo de considerações sobre seu funcionamento, mas, para entender melhor o mecanismo, veja textos especializados como Lins; Calôba (2006, caps. 4 e 5). (Cumpre notar que textos diferentes se servem de formulações diversas em que o processo é análogo, mas não idêntico. Por exemplo, Lins e Calôba preferem a linha da função objetivo como última no tableau. Autores que buscam minimizar a função objetivo podem formulá-la inversamente e usar entradas positivas para determinar a "coluna pivô".)

Note, no exemplo, que cada tableau (seja o inicial ou após uma rodada completa dos três passos) também pode ser interpretado como fizemos com o último; obtemos, respectivamente: 0 bolos, 0 tortas e 0 dúzias de biscoitos, restando 840 maçãs, 630 xícaras de açúcar e 450 xícaras de farinha. 225 bolos, 0 tortas e 0 dúzias de biscoitos, restando 165 maçãs, 405 xícaras de açúcar e 0 xícaras de farinha. (Confira que esses bolos são feitos precisamente com os ingredientes subtraídos das quantidades originais.)

144 bolos, 0 tortas e 162 dúzias de biscoitos, restando 246 maçãs, 0 xícaras de açúcar e 0 xícaras de farinha. (Desistimos de fazer tantos bolos, consumindo menos maçãs e mais açúcar para fazer biscoito.)

Por outro lado, ao delimitarmos a região do espaço tridimensional Oxyz pelas inequações lineares do problema, obtemos um poliedro convexo (sólido com faces e arestas planas e sem concavidade) do qual os pontos (0,0,0), (225,0,0) e (144,0,162) são alguns dos vértices.

Para entendermos a relevância dos vértices, note, primeiramente, que V = 8x + 6y + 5z está definida em todo o espaço Oxyz; no cálculo básico universitário, mostra-se que V cresce mais rapidamente na direção e sentido do vetor (8,6,5), chamado ∇V ("gradiente de V"). Podemos imaginar, então, uma pequena bolinha presa

dentro do poliedro delimitado pelas restrições do problema linear, mas sobre a qual atua uma força identificada com esse vetor. Assim como se sujeita à força gravitacional, a bolinha tenderia a ir para o ponto mais baixo de um recipiente; naquela situação, ela também tende a deslocar-se para os "últimos" pontos do poliedro, em que o valor de V seja o mais alto. E, assim como no caso do recipiente, cujo fundo pode ser chato ou em forma de uma cunha, esses pontos podem constituir toda uma face ou uma aresta do poliedro, mas, forçosamente, incluem um vértice.

O Simplex foi elaborado, portanto, para procurar o ponto de otimização entre os vértices. Em cada tableau, o algoritmo apresentou-nos um desses vértices e, em sequência, foi ao próximo vértice enquanto o valor da função objetivo V progressivamente aumentou. De fato, na primeira linha, ao eliminarmos as entradas negativas, a última entrada em geral aumenta e nunca diminui (às vezes, pode não aumentar, caso em que o pivô sendo trabalhado é chamado degenerado). Como essa linha corresponde à equação formada pela definição de V, sua última entrada é o valor correspondente de V nesse momento.

(A escolha da entrada "mais negativa" na primeira linha busca aumentar o valor de V o mais rápido possível em uma pivotagem, embora isso não aconteça necessariamente e outras técnicas possam ser usadas.)

Nesse ínterim, a escolha do menor quociente positivo mantém a última coluna não negativa, subtraindo de cada entrada original um valor menor (nas linhas com quociente positivo) ou somando propriamente (nas linhas com quociente negativo, como a da função objetivo). Isso preserva a factibilidade das variáveis em estudo. Se remontarmos o sistema a partir do tableau, veremos que quaisquer outros valores não negativos para as variáveis acabarão por subtrair algo de V, de modo que o valor obtido realmente é máximo.

Porém, duas possibilidades podem atrapalhar a execução do Simplex: não encontrarmos um pivô, ou encontrarmos o mesmo tableau duas vezes.

O primeiro caso é quando uma coluna pivô não tem entradas positivas. Nesse caso, é possível mostrar que a variável correspondente a essa coluna fica livre, ou seja, pode ter um valor positivo arbitrário; então, o poliedro definido pelas inequações é um sólido ilimitado e, portanto, a função V também é ilimitada.