Nelson Tunala
Rio de Janeiro, RJ

Recentemente, um jovem aluno de graduação em Matemática pediu-me que o ajudasse a solucionar a última questão da prova de Matemática, proposta no Concurso Público ao Magistério Estadual do Rio de Janeiro, realizado em 1990 (veja as questões dessa prova nas RPMs 19 e 20).

No conjunto dos vértices do polígono convexo definido por:

x+ y 3, x+ y 1, x 0 e y 0, a soma k = 3x+2y

tem como valor máximo o número:

A) 2           B) 3           C) 6           D) 9           E) 12

Uma sugestão e alguns lembretes foram o bastante para que nosso colega rapidamente elaborasse a solução e se desse por satisfeito.

Encontrado o conjunto V = {(0,1), (0,3), (1,0), (3,0)} dos vértices do polígono, verifica-se facilmente, por inspeção, que o valor máximo da função linear k (x,y) = 3x+ 2y ocorre para (x,y) = (3,0). Assim, o valor máximo procurado é k (3,0) = 9 (opção D).

Da maneira como foi proposta, a questão não apresenta grandes dificuldades, uma vez que o conjunto onde se deseja maximizar a função linear k é facilmente determinado e, além disso, possui apenas quatro elementos.

Em nossa opinião, o problema ficaria muito mais interessante, exigindo inclusive um maior exercício de investigação, se o início do enunciado fosse alterado para: Na região poligonal convexa definida por... Curiosamente, como veremos, a solução ótima obtida não será alterada, já que nenhum ponto interior de uma região poligonal convexa pode ser extremante de uma função linear restrita a esse domínio. Com efeito, se existe um extremante, ele é, via de regra, um vértice do polígono; excepcionalmente, todos os pontos de um lado do polígono podem ser extremantes da função.

Problemas dessa natureza pertencem a um ramo fascinante da Matemática Aplicada denominado Programação Linear.

De um modo geral, um problema de otimizaçâo de uma função sujeita a vínculos estabelecidos pode sempre ser reduzido a um equivalente de maximização. De fato, um problema de minimização pode sempre ser transformado em um outro de maximização, uma vez que se assume seu valor mínimo em x₀ do seu domínio D, isto é, se  (x₀) (x), x D, então a função toma seu valor máximo também em x₀ e

Diante do exposto, problemas de otimização de uma função linear de duas variáveis reais, sujeita a vínculos de restrição igualmente lineares, possuem a seguinte formulação:

onde , , a_i, b_i, c_i (1 i m) são reais.

A função linear é conhecida por função objetivo e a região simultânea R é o conjunto das soluções viáveis. As inequações x 0 e y 0 são as restrições de nâo-negatividade. O sentido foi adotado arbitrariamente para as demais desigualdades lineares, uma vez que nenhuma perda de generalidade resulta desse procedimento; com efeito, se isso for desejável, basta multiplicar por 1 as de sentido .

A título de ilustração, considere-se, no plano, o problema de otimização acima.

A solução geométrica é facilmente obtida, se utilizarmos o seguinte algoritmo:

P1. Esboce a região R definida pelas desigualdades.

P2. Desenhe o vetor = (, ) onde e são os coeficientes de x e y na função . Esse vetor indica o sentido de crescimento de (x, y). As vezes é conveniente utilizar um fator de escala  t > 0 e escrever = (t, t) para reduzir o tamanho desse vetor.

P3. Variando c em  x + y + y = c,  obtenha o feixe de retas perpendiculares à direção associada a . Sendo S o subconjunto do feixe, cujos elementos são retas não disjuntas com a região R, percorra — no sentido de — elementos de S, na busca do ponto Q = (x*, y*) da região R, por onde passa o último (mais extremo) representante (r) de S. Eventualmente, o ponto Q poderá não ser único; basta que esse mais extremo representante de S seja suporte de um lado da região poligonal.

O ponto Q = (x*, y*) é o maximizante do problema, de modo que a solução ótima (máximo de )  é  (Q) = x* + y* + y.

Os exemplos a seguir ilustram a utilização de algoritmo.

 

Exemplos

1 - Considere o programa linear: Maximizar (x,y) = 3x + 5y sujeito a:

Do passo 1 do algoritmo, resulta a região R de soluções viáveis (figura acima).

Executando-se os passos seguintes do algoritmo, construímos, sucessivamente, o segmento orientado = (1, 5/3) e o feixe de retas perpendiculares a essa direção vetorial.

Com a intenção de simplificar a figura, utilizamos o fator de escala t= 1/3, uma vez que a escolha natural (3, 5) para , deixaria P no interior da região.

No passo 2, lembremos que o par (x*, y*) que minimiza (x,y) = x + 2y é o mesmo que maximiza ()(x,y)= x 2y . Segue-se, nesse caso, que = (1,2). O gráfico acima, à direita, resulta da execução do passo 3.

Embora o subconjunto S seja ilimitado no sentido contrário a  , no sentido de estão bem definidos a reta limitante r e o ponto Q = (1 ,0) de R r, maximizante de e minimizante de . Assim, a solução ótima do problema (mínimo de )  é  (1,0) = 1.

Observe que, com os mesmos dados, se esse problema fosse de maximização, a solução ótima não seria finita (exercício 13.5 de [1]).

Apresentamos neste artigo uma pequena introdução aos problemas de Otimização Linear no plano, com um procedimento geométrico para solucioná-los.

Excelentes leituras adicionais dos tópicos aqui apresentados podem ser encontradas na seção 13 de [1] ou no capítulo 1 de [2] e [3].

Referências Bibliográficas

[1]   LIMA, E.L. Coordenadas no Plano. Rio de Janeiro: IMPA/VITAE, 1992.

[2]  MACHADO, H.V. Programação Linear. Rio de Janeiro: IMPA e 10.° Colóquio Brasileiro de Matemática, 1975.

[3]  MACULAN, N. e PEREIRA, M.V.F. Programação Linear. São Paulo: Atlas, 1990.