Se você é engenheiro ou estudante de engenharia, deve saber o que significa otimizar.
Para obter o melhor resultado possível, é importante encontrar a melhor maneira de fazer as coisas.
Na programação linear, você pode usar uma solução básica para encontrar a melhor solução.
Mas o que é uma solução básica e por que é tão importante para os engenheiros conhecê-la? Neste artigo, falarei sobre o que são soluções básicas, por que são importantes na engenharia e como podem ser usadas para obter os melhores resultados em diferentes situações.
Então aperte o cinto e prepare-se para mergulhar no mundo das soluções básicas, onde vou desvendar os mistérios e mostrar o quão poderosa essa técnica pode ser.
Soluções Básicas em Programação Linear
Definição formal:
Uma solução para um modelo de programa linear que consiste em m equações em n variáveis é obtida resolvendo m variáveis em termos das variáveis restantes (nm) e definindo as variáveis (nm) iguais a zero.
Uma solução básica em programação linear é uma maneira de resolver um problema de programação linear que atende a certos requisitos técnicos.
Em particular, um vetor x é uma solução básica para um poliedro se os vetores {ai : xi = 0} são linearmente independentes.
Isso significa que as colunas de A que possuem variáveis xi diferentes de zero são linearmente independentes.
Uma solução básica com componentes não negativos é chamada de solução básica factível (BFS) (BFS).
Um BFS atende a todas as regras que definem um poliedro.
Cada BFS é um canto do poliedro de soluções viáveis do ponto de vista geométrico.
Para encontrar uma solução básica, você deve definir nm variáveis que não são básicas como zero e resolver as m variáveis que são básicas.
É possível que diferentes bases levem à mesma solução básica, o que significa que pode haver mais de uma maneira de resolver o mesmo problema.
O Método Simplex é um processo iterativo que se move de um BFS para o próximo BFS até encontrar o melhor BFS.
Depois de usar o método simplex para encontrar um BFS, podemos dizer se a solução é a melhor vendo se algum outro BFS próximo fornece um valor melhor para a função objetivo.
Se não houver tal BFS, então o BFS atual é o melhor.
Modelo de Programação Linear
Um modelo de programação linear envolve três componentes principais: variáveis de decisão, uma função objetivo e restrições.
Tanto a função objetivo quanto as restrições devem ser funções lineares e as variáveis de decisão devem ser contínuas.
A função objetivo é usada para aumentar ou diminuir um número que representa lucro, custo, número de produtos fabricados, etc.
Restrições são limites ou restrições na quantidade total de um determinado recurso que é necessário para fazer as tarefas que determinarão o nível de sucesso nas variáveis de decisão.
Além disso, alguns programas lineares exigem que todas as variáveis de decisão sejam não negativas.
Em modelos de programação linear, você também pode usar variáveis inteiras e binárias.
Variáveis binárias só podem ter um valor de 0 ou 1, então elas só podem ter um valor de 0 ou 1.
O Método Simplex
Uma das formas mais utilizadas para resolver problemas de programação linear é o Método Simplex.
As soluções básicas são importantes no método simplex porque correspondem aos pontos de canto da região viável, e o método simplex se move de um canto para outro até que uma solução ótima seja encontrada.
O método simplex é uma maneira rápida de encontrar a melhor resposta para um problema de programação linear usando as propriedades das soluções básicas.
Para usar o método simplex para encontrar o melhor BFS, precisamos encontrar uma base B para a matriz de restrição A e resolver o sistema Ax = b com todas as variáveis exceto a base definida como zero.
Os valores resultantes para as variáveis básicas formam um BFS.
Se existe uma solução ótima, então existe um BFS ótimo.
O Método Simplex se move de um BFS para um BFS adjacente até atingir um BFS ótimo usando procedimentos de pivô.
Comparação entre Soluções Básicas e Soluções Viáveis
A diferença entre uma solução básica e uma solução viável é que uma solução básica não precisa atender a nenhuma condição.
Em particular, ele deve ter vetores linearmente independentes e com valores diferentes de zero para xi, e x deve ser menor que 0.
Por outro lado, uma solução factível é qualquer ponto que caiba dentro dos limites do problema.
Mas nem todas as soluções viáveis são soluções viáveis básicas.
As soluções viáveis básicas (BFSs) são apenas aquelas que correspondem aos vértices do poliedro de soluções viáveis.
De volta ao básico: revelando o poder das soluções básicas em engenharia
Ainda difícil de entender? Deixe-me mudar um pouco o ponto de vista:
Você está cansado de usar métodos e algoritmos complicados para resolver problemas difíceis? Você gostaria que houvesse uma maneira mais simples e direta de lidar com seus problemas de modelo de programa linear?
Bem, não se preocupe, porque a resposta está aqui: resolva para m variáveis em termos das variáveis restantes (nm) e defina as variáveis (nm) como zero.
Quem precisa de algoritmos que pareçam sofisticados quando você pode voltar ao básico? Portanto, guarde suas calculadoras e vamos começar a aprender sobre soluções simples.
Ok, isso foi apenas uma piada feita para parecer um anúncio de TV.
Agora vamos voltar para a explicação.
Solução básica de programação linear
Dica: Ative o botão de legenda se precisar. Escolha “tradução automática” no botão de configurações, se você não estiver familiarizado com o idioma falado. Pode ser necessário clicar primeiro no idioma do vídeo antes que seu idioma favorito fique disponível para tradução.
Casos de uso
Usado em: | Descrição: |
---|---|
Alocação de recursos: | A solução básica pode ser usada em problemas de alocação de recursos, onde o objetivo é dividir recursos limitados entre necessidades concorrentes. Por exemplo, uma empresa pode precisar dividir seu orçamento entre diferentes departamentos ou projetos. Usando soluções básicas, eles podem descobrir a melhor maneira de usar seus recursos para ganhar mais dinheiro ou gastar o mínimo possível. |
Planejamento da Produção: | No planejamento da produção, a solução básica pode ser usada para descobrir o melhor mix de produtos a ser feito para ganhar mais dinheiro. As empresas podem encontrar o melhor mix de produção que traga mais dinheiro e custe menos usando a solução básica. |
Agendamento: | A solução básica pode ser usada para descobrir como agendar tarefas ou trabalhos para que possam ser executados da maneira mais eficiente. Por exemplo, uma empresa pode precisar planejar as horas de trabalho de seus funcionários para garantir que eles tenham funcionários suficientes quando os negócios estiverem ocupados. Usando uma solução básica, eles podem descobrir a melhor maneira de agendar as coisas para que haja o mínimo de tempo de inatividade possível e o máximo de trabalho possível. |
Gestão da Cadeia de Suprimentos: | No gerenciamento da cadeia de suprimentos, o objetivo é garantir que os bens e serviços se movam o mais suavemente possível do fornecedor para o cliente. Por exemplo, uma empresa pode precisar descobrir as melhores rotas para o transporte de mercadorias para que os custos sejam reduzidos ao mínimo e as mercadorias sejam entregues no prazo. Usando soluções básicas, eles podem encontrar o melhor plano para gerenciar a cadeia de suprimentos que mantém os custos baixos e os clientes satisfeitos. |
Otimização de Portfólio: | Na otimização de portfólio, onde o objetivo é encontrar o melhor mix de investimentos para ganhar mais dinheiro com o menor risco, soluções básicas podem ser usadas. Por exemplo, uma empresa de investimento pode precisar descobrir a melhor combinação de ações, títulos e outros títulos para ajudar seus clientes a atingirem suas metas de investimento. Usando uma solução simples, eles podem encontrar a melhor maneira de misturar seus portfólios para obter os melhores retornos com o mínimo de risco. |
Conclusão
Concluindo, a ideia de solução básica é muito importante na área de engenharia e pode ser utilizada de diversas formas.
Ao saber o que é uma solução básica e o que ela faz na programação linear, podemos melhorar as soluções, reduzir custos e torná-las mais eficientes.
Mas é importante lembrar que a solução básica não é uma solução única para todos, embora seja uma ferramenta poderosa.
Para obter os melhores resultados, cada problema precisa ser cuidadosamente analisado e pensado.
Como engenheiros, precisamos continuar analisando como as soluções básicas e outras técnicas de otimização podem nos ajudar a progredir e a ter novas ideias.
Então, vamos reconhecer o poder de soluções simples e continuar ultrapassando os limites do que é possível usando novas técnicas e estratégias.
Links e referências
Livros:
- Programação linear por Vasek Chvatal
- Modelando e resolvendo programação linear com R por Jose M. Sallan