Ruben Fernandes N 21

Ruben Fernandes nº21
12ºG

Otimização

O que é?
Em matemática, o termo otimização, ou programação matemática, refere-se ao estudo de problemas em que se procura minimizar ou maximizar uma função através da escolha sistemática dos valores de variáveis reais ou inteiros dentro de um conjunto viável.

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 destes serem extensivamente usados hoje em dia para resolver problemas matemáticos), mas ao termo "programa", utilizado pelos militares norte-americanos para referirem-se à agenda proposta de horários para treinamentos e ações logí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.)

Introdução à otimização
Imagine duas pessoas, o Alexandre e o João, jogando o jogo que passamos a descrever. O Alexandre escolhe um número i (entre 1 e m) e o João escolhe um número j (entre 1 e n) sem saber que número escolheu o Alexandre. Revelam, então, os números que escolheram e o Alexandre paga ao João um montante definido pela componente na posição (i, j) de uma matriz m × n fixada antecipadamente por aqueles dois amigos. Por exemplo, se essa matriz A = [aij ] fosse

Então, se o Alexandre tivesse escolhido 2 e o João 1, o Alexandre deveria pagar ao João e1. Por outro