Otimização ajuda você a encontrar o melhor resultado que traz lucro, reduz custos ou define um parâmetro que causa falhas nos processos de negócios.
Esse processo também é chamado de programação matemática. Ele resolve o problema de determinar a distribuição de recursos limitados necessários para atingir a meta estabelecida pelo chefe do problema de otimização. De todas as opções possíveis, é desejável encontrar aquela que maximize (ou reduza) o parâmetro de controle, por exemplo, lucro ou custo. Os modelos de otimização também são chamados de prescritivos ou normativos porque buscam encontrar uma estratégia viável para o negócio.
Histórico de desenvolvimento
Programação linear (PL) trabalha com uma classe de problemas de otimização onde todas as restrições são lineares.
Apresentando um breve histórico do desenvolvimento do LP:
- Em 1762, Lagrange resolveu problemas simples de otimização com restrições de igualdade.
- Em 1820, Gauss decidiusistema linear de equações usando eliminação.
- Em 1866, Wilhelm Jordan aperfeiçoou o método de encontrar erros de mínimos quadrados como critério de ajuste. Isso agora é chamado de método de Gauss-Jordan.
- O computador digital surgiu em 1945.
- Danzig inventou métodos simplex em 1947.
- Em 1968, Fiacco e McCormick introduziram o método Inside Point.
- Em 1984, Karmarkar aplicou o método interior para resolver programas lineares, acrescentando sua análise inovadora.
LP provou ser uma ferramenta extremamente poderosa tanto para modelar problemas do mundo real quanto como uma teoria matemática amplamente aplicada. No entanto, muitos problemas de otimização interessantes não são lineares.
O que fazer neste caso? O estudo de tais problemas envolve uma mistura variada de álgebra linear, cálculo multivariado, análise numérica e métodos computacionais. Os cientistas estão desenvolvendo algoritmos computacionais, incluindo métodos de pontos interiores para programação linear, geometria, análise de conjuntos e funções convexas e o estudo de problemas especialmente estruturados, como programação quadrática.
Otimização não linear fornece uma compreensão fundamental da análise matemática e é amplamente utilizada em vários campos, como engenharia, análise de regressão, gerenciamento de recursos, exploração geofísica e economia.
Classificação de problemas de otimização
Um passo importante naO processo de otimização é a classificação de modelos, pois seus algoritmos de solução são adaptados a um determinado tipo.
1. Problemas com otimização discreta e contínua. Alguns modelos só fazem sentido se as variáveis tomarem valores de um subconjunto discreto de inteiros. Outros contêm dados que podem assumir qualquer valor real. Geralmente são mais fáceis de resolver. Melhorias nos algoritmos, combinadas com avanços na tecnologia de computadores, aumentaram drasticamente o tamanho e a complexidade de um problema de otimização de programação linear.
2. Otimização ilimitada e limitada. Outra diferença importante são as tarefas em que não há restrição de variáveis. Ele pode variar amplamente de estimadores simples a sistemas de igualdades e desigualdades que modelam relacionamentos complexos entre dados. Tais problemas de otimização podem ainda ser classificados de acordo com a natureza das funções (lineares e não lineares, convexas e suaves, diferenciáveis e não diferenciáveis).
3. Tarefas de viabilidade. O objetivo deles é encontrar valores de variáveis que satisfaçam as restrições do modelo sem nenhum objetivo de otimização específico.
4. Tarefas de complementaridade. Eles são amplamente utilizados em tecnologia e economia. O objetivo é encontrar uma solução que satisfaça as condições de complementaridade. Na prática, tarefas com vários objetivos são muitas vezes reformuladas em objetivos únicos.
5. Otimização determinística versus estocástica. A otimização determinística assume que os dados paraatribuições são completamente precisas. No entanto, em muitas questões atuais, eles não podem ser conhecidos por várias razões.
O primeiro tem a ver com um simples erro de medição. A segunda razão é mais fundamental. Está no fato de que alguns dados representam informações sobre o futuro, por exemplo, a demanda por um produto ou o preço para um período de tempo futuro. Ao otimizar sob condições de otimização estocástica, a incerteza é incluída no modelo.
Componentes Principais
A função objetivo é aquela a ser minimizada ou maximizada. A maioria dos tipos de problemas de otimização tem uma função objetivo. Caso contrário, eles podem ser reformulados para funcionar.
Duas exceções a esta regra:
1. Tarefa de pesquisa de destino. Na maioria dos aplicativos de negócios, o gerente deseja atingir uma meta específica enquanto satisfaz as restrições do modelo. O usuário não quer particularmente otimizar algo, então não faz sentido definir uma função objetivo. Esse tipo é comumente chamado de problema de satisfatibilidade.
2. Muitos recursos objetivos. Muitas vezes, um usuário gostaria de otimizar vários objetivos diferentes de uma só vez. Geralmente são incompatíveis. Variáveis que otimizam para um objetivo podem não ser as melhores para outros.
Tipos de componentes:
- Uma entrada controlada é um conjunto de variáveis de decisão que afetam o valor de uma função objetivo. Em uma tarefa de produção, as variáveis podem incluir a distribuição dos vários recursos disponíveis ou a mão de obra necessária paracada ação.
- Restrições são relações entre variáveis de decisão e parâmetros. Para um problema de produção, não faz sentido gastar muito tempo em qualquer atividade, então limite todas as variáveis "temporárias".
- Soluções possíveis e ótimas. O valor da decisão para variáveis, sob o qual todas as restrições são satisfeitas, é chamado de satisfatível. A maioria dos algoritmos primeiro o encontra e depois tenta melhorá-lo. Finalmente, eles mudam as variáveis para passar de uma solução viável para outra. Esse processo é repetido até que a função objetivo atinja seu máximo ou mínimo. Esse resultado é chamado de solução ótima.
Algoritmos de problemas de otimização desenvolvidos para os seguintes programas matemáticos são amplamente utilizados:
- Convexo.
- Separável.
- Quadratic.
- Geometric.
Google Linear Solvers
Otimização linear ou programação é o nome dado ao processo computacional de solução ótima de um problema. Ele é modelado como um conjunto de relações lineares que surgem em muitas disciplinas científicas e de engenharia.
O Google oferece três maneiras de resolver problemas de otimização linear:
- Biblioteca de código aberto Glop.
- Complemento de otimização linear para o Planilhas Google.
- Linear Optimization Service no Google Apps Script.
Glop está integrado ao Googlesolucionador linear. Está disponível em código aberto. Você pode acessar o Glop através do wrapper linear solver OR-Tools, que é um wrapper para Glop.
O módulo de otimização linear para o Planilhas Google permite que você execute uma declaração linear do problema de otimização inserindo dados em uma planilha.
Programação Quadrática
A plataforma Premium Solver usa uma versão estendida LP/Quadratic do método Simplex com limites de processamento de problemas LP e QP de até 2.000 variáveis de decisão.
SQP Solver para problemas de grande escala usa uma implementação moderna do método de conjunto ativo com esparsidade para resolver problemas de programação quadrática (QP). O mecanismo XPRESS Solver usa uma extensão natural do método "Interior Point" ou Newton Barrier para resolver problemas de QP.
MOSEK Solver aplica métodos "Inside Point" incorporados e auto-dual. Isso é especialmente eficaz para problemas de QP fracamente acoplados. Ele também pode resolver os problemas de Restrição Quadrática de Escala (QCP) e Programação de Cone de Segunda Ordem (SOCP).
Cálculos multi-operação
Eles são usados com bastante sucesso com o uso de recursos do Microsoft Office, por exemplo, resolvendo problemas de otimização no Excel.
Na tabela acima, os símbolos são:
- K1 - K6 - clientes que precisam fornecer mercadorias.
- S1 - S6 são locais de produção potenciais que podem ser construídos para isso. Pode ser criado1, 2, 3, 4, 5 ou todos os 6 locais.
Existem custos fixos para cada instalação listada na coluna I (Correção).
Se a localização não mudar nada, não contará. Então não haverá custos fixos.
Identifique possíveis locais para obter o menor custo.
Nestas condições, a localização é estabelecida ou não. Esses dois estados são: "TRUE - FALSE" ou "1 - 0". Há seis estados para seis locais, por exemplo, 000001 é definido como apenas o sexto, 111111 é definido como todos.
No sistema de numeração binário, existem exatamente 63 opções diferentes de 000001 (1) a 111111 (63).
L2-L64 deve agora ler {=MÚLTIPLA OPERAÇÃO (K1)}, estes são os resultados de todas as soluções alternativas. Então o valor mínimo é=Min (L) e a alternativa correspondente é INDEX (K).
Programação inteira CPLEX
Às vezes, um relacionamento linear não é suficiente para chegar ao cerne de um problema de negócios. Isso é especialmente verdadeiro quando as decisões envolvem escolhas discretas, como abrir ou não um depósito em um determinado local. Nessas situações, deve-se usar programação inteira.
Se o problema envolve escolhas discretas e contínuas, é um programa inteiro misto. Pode ter problemas quadráticos lineares e convexos e as mesmas restrições de segunda ordem.
Os programas inteiros são muito mais complexos do que os programas lineares, mas têm importantes aplicações comerciais. ProgramasO software CPLEX usa métodos matemáticos complexos para resolver problemas de números inteiros. Seus métodos envolvem a busca sistemática de possíveis combinações de variáveis discretas usando relaxações de software lineares ou quadráticas para calcular os limites do valor da solução ótima.
Eles também usam PL e outros métodos de resolução de problemas de otimização para calcular restrições.
Padrão Microsoft Excel Solver
Esta tecnologia usa a implementação básica do método Simplex principal para resolver problemas de PL. É limitado a 200 variáveis. O "Premium Solver" usa um método simplex primário aprimorado com limites de dupla face para variáveis. A plataforma Premium Solver usa uma versão estendida do LP/Quadratic Simplex Solver para resolver um problema de otimização com até 2.000 variáveis de decisão.
LP em grande escala para a plataforma Premium Solver aplica uma implementação de última geração do método simplex simples e duplo, que usa a esparsidade no modelo LP para economizar tempo e memória, estratégias avançadas de atualização e matrizes de refatoração, preços e rotações múltiplas e parciais e para superar a degeneração. Este mecanismo está disponível em três versões (capaz de lidar com até 8.000, 32.000 ou variáveis e limites ilimitados).
MOSEK Solver inclui simplex primário e dual, um método que também explora a dispersão e usa estratégias avançadas para atualização e "refatorização" de matrizes. Resolve problemas de tamanho ilimitado, foitestado em problemas de programação linear com milhões de variáveis de decisão.
Exemplo passo a passo em EXCEL
Para definir o modelo do problema de otimização no Excel, execute os seguintes passos:
- Organize os dados do problema em uma planilha de forma lógica.
- Selecione uma célula para armazenar cada variável.
- Crie na célula uma fórmula para calcular o modelo matemático alvo do problema de otimização.
- Crie fórmulas para calcular o lado esquerdo de cada restrição.
- Use as caixas de diálogo no Excel para informar ao Solver sobre variáveis de decisão, alvos, restrições e limites desejados nesses parâmetros.
- Execute o "Solver" para encontrar a solução ideal.
- Crie uma planilha do Excel.
- Organize os dados do problema no Excel onde é calculada a fórmula para a função objetivo e a restrição.
Na tabela acima, as células B4, C4, D4 e E4 foram reservadas para representar as variáveis de decisão X 1, X 2, X 3 e X 4. Exemplos de decisão:
- O modelo de mix de produtos (US$ 450, US$ 1.150, US$ 800 e US$ 400 de lucro por produto) foi inserido nas células B5, C5, D5 e E5, respectivamente. Isso permite que o destino seja calculado em F5=B5B4 + C5C4 + D5D4 + E5E4 ou F5:=SUMPRODUCT (B5: E5, B4: E4).
- Em B8 insira a quantidade de recursos necessários para fabricar cada tipo de produto.
- Fórmula para F8:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Copie issofórmula em F9. Os cifrões em $B$4:$E$4 indicam que este intervalo de células permanece constante.
- No G8 insira a quantidade disponível de recursos de cada tipo, correspondendo aos valores das restrições à direita. Isso permite expressá-los assim: F11<=G8: G11.
- Isto equivale a quatro limites F8<=G8, F9 <=G9, F10 <=G10 e F11=0
Campos de aplicação prática do método
Otimização linear tem muitas aplicações práticas como exemplo de um problema de otimização:
Uma empresa pode fabricar vários produtos com margem de contribuição conhecida. A produção de uma unidade de cada item requer uma quantidade conhecida de recursos limitados. A tarefa é criar um programa de produção para determinar quanto de cada produto deve ser produzido para que o lucro da empresa seja maximizado sem violar as restrições de recursos.
Problemas de mistura são a solução para problemas de otimização relacionados à combinação de ingredientes no produto final. Um exemplo disso é o problema da dieta estudado por George Danzig em 1947. São fornecidas várias matérias-primas, como aveia, porco e óleo de girassol, juntamente com seu conteúdo nutricional, como proteína, gordura, vitamina A, e seu preço por quilo. O desafio é misturar um ou mais produtos finais a partir de matérias-primas com o menor custo possível, respeitando os limites mínimo e máximo de seu valor nutricional.
Uma aplicação clássica de um problema de otimização linear é determinar o roteamento para as necessidadestráfego nas redes de telecomunicações ou de transporte. Ao mesmo tempo, os fluxos devem ser roteados pela rede de forma que todos os requisitos de tráfego sejam atendidos sem violar as condições de largura de banda.
Na teoria matemática, a otimização linear pode ser usada para calcular estratégias ótimas em jogos de soma zero para duas pessoas. Nesse caso, é calculada a distribuição de probabilidade para cada participante, que é o coeficiente de mistura aleatória de suas estratégias.
Nenhum processo de negócios bem-sucedido no mundo é possível sem otimização. Existem muitos algoritmos de otimização disponíveis. Alguns métodos são adequados apenas para certos tipos de problemas. É importante ser capaz de reconhecer suas características e selecionar o método de solução adequado.
