O que é otimização

Otimização

História

O método do gradiente ("gradient descent"), ou "método da descida mais íngreme" ("steepest descent"), e o método dos mínimos quadrados são técnicas de otimização que remontam a Gauss. Historicamente, a terminologia programação linear("linear programming"), criada por George Dantzig, foi a primeira utilizada, embora muito da teoria tivesse sido introduzida por Leonid Kantorovich, em 1939. Dantzig publicou o algoritmo simplex, em 1947, e John Von Neumann desenvolveu a teoria da dualidade no mesmo ano. Nesse contexto, "programação" não se refere a programação de computadores (apesar de estes serem extensivamente usados hoje em dia para resolver problemas matemáticos), mas ao termo "programa", utilizado pelos militares norteamericanos para referirem-se à agenda proposta de horários para treinamentos e açõeslogísticas, que eram os problemas que Dantzig estava estudando à época. (Além disso, mais tarde, a utilização do termo "programação" foi aparentemente importante para obtenção de financiamento público, pois estava associada a áreas de pesquisa de alta tecnologia consideradas importantes).

*A figura é Ilustração do método do gradiente

Outros importantes matemáticos no campo da otimização são:

• Richard Bellman

• Ronald A. Howard

• Leonid Kantorovich

• Narendra Karmarkar

• William Karush

• Leonid Khachiyan

• Bernard Koopman

• Harold Kuhn

• Joseph Louis Lagrange

• László Lovász

• Arkadii Nemirovskii

• Yurii Nesterov

• John Von Neumann

• Boris Polyak

• Lev Pontryagin

• James Renegar

• R. Tyrrell Rockafellar

• Cornelis Roos

• Naum Z. Shor

• Michael J. Todd

• Albert Tucker

O que é otimização

Encurtar um caminho para ganhar tempo, economizar para compar algo, tomar decisão com base em investimentos, sempre estamos interessados nas formas ótimas de aplicarmos nossos recursos. Resolver um problema de otimização, significa, sobretudo procurar a solução de um problema de forma a se maximizar algo ou a minimizar algo. Esse algo tem uma representação matemática que recebe o nome de função objetivo ou índice de performance. Assim, por exemplo, se a fabricação de uma peça depende de dois materiais cujos nomes podem ser (apropriados) x1 e x2, o custo total dessa peça é a soma dos custos unitários. Então se x1 custa $5 e x2 custa $2, o custo de uma peça é 5x1+2x2. Se quisermos fabricar muitas peças, o problema da otimização é descobrir qual a quantidade de cada material (x1,x2)l é necessária para a fabricação das peças. Da mesma forma x1 pode ser o código de uma ação e x2 o código de outra ação, de forma que 5x1+2x2 é o rendimento do portfólio. Essa soma as vezes pode ser representada pela letra Z ou no caso da engenharia pela letra J, ou seja,

Z=5x1+2x2

As restrições

A restrição natural, por exemplo, no caso das ações, é que nunca ocorrerão compras negativas de ações (claro, a menos a título de empréstimo, mas a representação é outra). Então a restrição natural é que x1 e x2 devem ser positivos ou no pior dos casos zero. Suponhamos ainda que um cliente exigente não quer comprar mais de 3 ações de x1, nem mais de 4 ações de x2. E ainda impõe a restrição que se a ação x2 chegar a $2 e a ação x1 ficar em $1 então ele não permite a compra de mais de 9 ações. E por fim, claro, ele quer o maior rendimento desse portfólio.

A representação matemática - Modelagem

A representação é uma forma filosófica de não nomear ninguém, mas impor um símbolo que represente alguém. O problema do quadro anterior, então fica assim:

Deseja-se

Ainda parece muito estranho essas variáveis, mas a representação geométrica ilustra o sentido dessa representação conhecida com algébrica. Na verdade temos toda a história do problema que pode ser contada na forma de retas. Por isso a otimização linear recebe os nomes de "Programação Linear" ou de "Pesquisa Operacional".

Nas figuras abaixo, a geometria se desponta e mostra a beleza escondida atrás das equações anteriores. Talvez por isso os geômetras dominaram o mundo matemático por quase 3 mil anos. Naquela época, o que não se podia ver, não se podia provar.

A primeira restrição que diz que x1 não pode passar de 3 é uma reta perpendicular ao eixo x1. Qualquer solução que venha a ser encontrada não poderá ultrapassar essa reta perpendicular. A segunda restrição se refere ao eixo de x2 e por isso a reta é perpendicular a esse eixo, ou seja, agora temos 4 restrições (x1 e x2 positivos são as outras duas). Então qualquer solução ótima deve estar dentro desse quadarado formado pelas restrições.

Finalmente a última restrição é formada pela reta com inclinação que corta as retas perpendiculares, ou seja, a reta x1+2x2=9. Aqui vem um comentário importante sobre o sinal menor ou igual. Esse sinal indica que apenas os valores abaixo ou atrás das retas é que valem. Assim como o sinal positivo que indica que apenas os valores acima e a direita do eixo é que valem para a resposta.

E pronto, temos então nossa região cohecida como região de soluções viáveis, ou seja, são pontos que resolvem o problema com as inequações, mas não necessariamente são os melhores.

A última figura apresenta a região hachurada onde pode-se buscar a solução de diversas maneiras, seja ela gráfica ou então via algoritmo de manipulação de matrizes conhecido com Simplex.