O que é programação linear? como resolver problemas com essa ferramenta?

#Lógica de Programação

O problema de otimizar uma função linear, sujeita a restrições, teve origem com os estudos de Fourier sobre sistemas lineares de inequações em 1826 (Método de Eliminação de Fourier–Motzkin.).

No entanto só em 1939 Kantorovich faz notar a importância prática destes problemas, tendo criado um algoritmo para a sua solução (Foi laureado com o Prêmio de Ciências Econômicas em Memória de Alfred Nobel de 1975).

Durante a segunda guerra, pelas gerencias militares britânicas e americanas para lidar com recursos escassos: de natureza logística, natureza tática e natureza militar. Os problemas eram complexos com necessidade de envolvimento de técnicas matemáticas complexas; transferência do conhecimento para áreas civil com o fim do conflito.

A origem da programação linear atinge o seu clímax com os estudos de George Dantzig, por volta de 1940, e com o prêmio Nobel da economia entregue a George Stigler. Dantzig não só formula problemas de programação linear, mas também cria o algoritmo Simplex em 1947.

O desenvolvimento da programação linear tem sido classificado entre os mais importantes avanços científicos dos meados do século XX. Seu impacto desde 1950 tem sido extraordinário. Hoje é uma ferramenta padrão que poupou milhares de dólares para muitas empresas ou até mesmo negócios de porte médio em diversos países industrializados ao redor do mundo (HILLIER; LIEBERMAN, 2013).

Algumas áreas de aplicação da programação linear.

Alocação de recursos
programação de produção
armazenagem
projeto de layout
agendamento de transporte
localização facilitada
gestão da cadeia de abastecimento
Seleção de modelos
Aprendizado de Máquina
Sensor de compressão
programação de tripulação de voo
otimização de portfólio
correspondência de fluxo de caixa
arbitragem de câmbio
agendamento de colheita
balanceamento de dieta
estimativa de parâmetros

Neste artigo iremos resolver um exemplo para mostrar o poder desta ferramenta.

EXEMPLO: Escolha da Mistura para Rações

Objetivos: formular uma ração formada a partir da mistura dos grãos que atenda às necessidades mínimas e máximas de nutrientes e tenha um custo mínimo.

Resolver pelo método simplex, pelo solver e gerar o modelo dual.

Escrevendo todo o modelo de programação linear do nosso exemplo

Minimizar Z = 41*X1 + 35*X2 + 96*X3 Função Objetivo

Sujeito as restrições:

2*X1 + 3*X2 + 7*X3 >= 1250,0 Nutriente A

1*X1 + 1*X2 + 0*X3 >= 250,0 Nutriente B

5*X1 + 3*X2 + 0*X3 >= 900,0 Nutriente C

0,6*X1 + 0,25*X2 + 1*X3 >= 232,5 Nutriente D

X1, X2 e X3 >= 0

Como é um problema de minimização deve-se utilizar o modelo dual.

Fazendo o modelo dual temos:

MAX w = 1250*Y1 + 250*Y2 + 900*Y3 + 232,5*Y4