Programação linear, técnica de modelagem matemática, na qual uma função linear é maximizada ou minimizada quando sujeita a várias restrições. Essa técnica tem sido útil para orientar decisões quantitativas no planejamento de negócios, na engenharia industrial e - em menor grau - nas ciências sociais e físicas.
otimização: programação linear
Embora amplamente usada agora para resolver problemas de decisão cotidianos, a programação linear era comparativamente desconhecida antes de 1947. Nenhum trabalho de qualquer significado
A solução de um problema de programação linear se reduz a encontrar o valor ideal (maior ou menor, dependendo do problema) da expressão linear (chamada de função objetivo)
sujeito a um conjunto de restrições expressas como desigualdades:
Os a, b e c são constantes determinadas pelas capacidades, necessidades, custos, lucros e outros requisitos e restrições do problema. A suposição básica na aplicação deste método é que os vários relacionamentos entre demanda e disponibilidade são lineares; isto é, nenhum dos x i é elevado a uma potência diferente de 1. Para obter a solução para esse problema, é necessário encontrar a solução do sistema de desigualdades lineares (ou seja, o conjunto de n valores de as variáveis x i que simultaneamente satisfazem todas as desigualdades). A função objetivo é então avaliada substituindo os valores de x i na equação que define f.
As aplicações do método de programação linear foram tentadas seriamente no final da década de 1930 pelo matemático soviético Leonid Kantorovich e pelo economista americano Wassily Leontief nas áreas de cronogramas de fabricação e economia, respectivamente, mas seu trabalho foi ignorado por décadas. Durante a Segunda Guerra Mundial, a programação linear foi amplamente utilizada para lidar com transporte, programação e alocação de recursos sujeitos a certas restrições, como custos e disponibilidade. Essas aplicações fizeram muito para estabelecer a aceitabilidade desse método, que ganhou mais ímpeto em 1947 com a introdução do método simplex do matemático americano George Dantzig, que simplificou bastante a solução de problemas de programação linear.
No entanto, à medida que tentavam problemas cada vez mais complexos, envolvendo mais variáveis, o número de operações necessárias se expandia exponencialmente e excedia a capacidade computacional dos computadores mais poderosos. Então, em 1979, o matemático russo Leonid Khachiyan descobriu um algoritmo de tempo polinomial - no qual o número de etapas computacionais cresce como uma potência do número de variáveis, e não exponencialmente -, permitindo a solução de problemas até então inacessíveis. No entanto, o algoritmo de Khachiyan (chamado método elipsóide) foi mais lento que o método simplex quando praticamente aplicado. Em 1984, o matemático indiano Narendra Karmarkar descobriu outro algoritmo de tempo polinomial, o método do ponto interior, que se mostrou competitivo com o método simplex.
