Você sabe o que significa otimizar um sistema para obter o melhor resultado possível se for um estudante de engenharia ou um engenheiro.
Otimizar uma solução é a chave para o sucesso em tudo, desde a construção de pontes até a criação de software.
A ideia de uma solução viável básica surge neste ponto.
É uma ideia básica em programação linear que permite descobrir qual de um conjunto de possíveis soluções é a melhor.
Mas por que isso importa tanto? Neste artigo, falarei sobre soluções viáveis básicas e como elas podem ser usadas para resolver problemas de engenharia no mundo real.
Falarei sobre como encontrá-los, do que são feitos e por que são importantes.
Então, se você é um engenheiro experiente ou um estudante apenas começando, venha conosco enquanto eu mergulho no mundo das soluções básicas viáveis e mostro como usar o poder da programação linear.
Compreendendo a solução viável básica
Definição formal:
Uma solução básica para um modelo de programa linear no qual todas as variáveis são não negativas.
Uma solução viável básica (BFS) é uma ideia-chave na programação linear que ajuda a encontrar as melhores soluções.
Um BFS é uma solução com o menor número possível de variáveis diferentes de zero.
É um canto do poliedro de soluções viáveis.
Em outras palavras, um BFS é uma solução básica que atende às restrições não negativas e está na região viável ou na área do problema.
Encontrar uma solução viável básica ideal
Para encontrar o melhor BFS, precisamos fazer o seguinte:
- Escreva o programa na forma padrão para uma sequência linear.
- Transforme o sistema de desigualdades em uma matriz aumentada.
- Descubra quais variáveis são básicas e quais não são.
- Descubra quais são as variáveis básicas em termos das outras variáveis.
- Coloque essas expressões na função objetivo para obter uma função apenas das variáveis que não são básicas.
- Encontre uma variável não básica que possa ser aumentada sem quebrar nenhuma restrição e que torne a função objetivo melhor.
Essa variável agora é uma variável básica e uma das outras variáveis básicas não é mais uma variável básica.
Se houver uma solução ótima, ela deve estar em uma das extremidades, ou vértices, da região onde as soluções são possíveis.
Assim, se um PL tem uma solução ótima, ele tem uma solução ótima em um ponto extremo do conjunto factível.
Além disso, há sempre um BFS ótimo se houver uma solução ótima.
Usando o Método Simplex para Encontrar um BFS Ótimo
O Método Simplex é um algoritmo para resolução de problemas em programação linear.
Ele se move de um BFS para um BFS "adjacente" usando o procedimento de pivô.
No procedimento de pivô, uma variável não básica é escolhida para se tornar uma variável básica e, em seguida, o BFS atual é usado para resolver as novas variáveis básicas.
Quando nenhuma variável não básica pode ser alterada para melhorar a função objetivo, o algoritmo é concluído.
Por que soluções viáveis básicas são cruciais para resolver problemas complexos de engenharia
Ainda difícil de entender? Deixe-me mudar um pouco o ponto de vista:
Afinal, quem precisa de respostas simples e viáveis? Basta jogar tudo junto e esperar o melhor.
Afinal, quem precisa de otimização quando o caos é muito mais divertido? Bem-vindo ao mundo das variáveis não negativas, onde tudo é apenas uma sugestão e o fracasso é quase certo.
Ou é?
Vamos explorar por que o conceito aparentemente básico de soluções viáveis básicas é tudo menos básico e por que elas podem ser a chave para resolver até mesmo os problemas de engenharia mais complexos.
Ok, isso foi apenas uma piada feita para parecer um anúncio de TV.
Agora vamos voltar para a explicação.
Encontrar uma solução viável básica
Uma solução viável básica (BFS) é uma solução para um problema de otimização linear que atende a todas as restrições e tem o menor número de variáveis diferentes de zero.
Cada BFS é um canto do poliedro de soluções viáveis do ponto de vista geométrico.
Se existe uma melhor solução, deve haver também um melhor primeiro passo.
Neste artigo, falaremos sobre como encontrar uma solução viável básica inicial, como encontrar todas as soluções viáveis básicas e como encontrar uma solução viável básica sem variáveis de folga.
Encontrar uma solução inicial viável básica
Podemos usar métodos diferentes, dependendo de como o problema é configurado, para encontrar uma solução básica inicial que funcione para um problema de otimização linear.
Uma maneira é adicionar variáveis de folga às restrições de desigualdades e definir todas as outras variáveis como zero.
As variáveis de folga tornam-se as variáveis básicas e o restante são variáveis não básicas.
O Método Simplex de duas fases é outra maneira de resolver o problema.
Este método envolve a resolução de um problema de programação linear extra para encontrar uma solução básica inicial que seja viável.
Uma vez encontrada uma solução viável básica inicial, o Método Simplex pode ser usado para passar de uma solução viável básica para a seguinte e depois para a melhor solução.
Encontrando todas as soluções básicas viáveis
Pode haver mais de uma solução básica que funcione para um programa linear.
Podemos alterar o sistema adicionando variáveis de folga e então usar o novo sistema para encontrar todas as soluções básicas viáveis para um programa linear.
Então, essas soluções básicas viáveis são usadas para encontrar as soluções básicas viáveis para o problema original.
Encontrar uma solução viável básica sem variáveis de folga
Precisamos usar variáveis de folga para eliminar as restrições de menor que, para que possamos encontrar uma solução básica que funcione sem variáveis de folga.
Uma variável de folga é apenas a diferença entre o lado direito de uma restrição e o lado esquerdo.
Por exemplo, para a primeira restrição, definimos uma variável de folga x4 = 14 - 2x1 - x2 - x3. Em termos dessa nova variável, a primeira restrição é equivalente simplesmente a x4 ≥ 0, que é uma restrição de positividade para x4.
Quando adicionamos essas variáveis de folga, obtemos um programa linear que é igual ao original, exceto que todas as restrições são equações ou restrições que dizem que algo é positivo.
O conjunto de variáveis básicas, que possuem valores diferentes de zero na solução básica, é chamado de base.
As variáveis que têm valor zero na solução básica não são variáveis básicas.
Para encontrar a melhor solução, precisamos encontrar um vetor x que atenda a todas as regras e obtenha o maior ou menor valor para o objetivo.
Mas encontrar a melhor solução exige mais etapas do que apenas encontrar uma solução que funcione e não tenha variáveis de folga.
Nem sempre é possível encontrar uma solução básica sem variáveis de folga, especialmente para problemas com restrições menores que.
Para encontrar uma solução viável básica, você precisa usar o método simplex ou outro algoritmo de programação linear para procurar uma solução que atenda a todas as restrições e tenha o menor número de variáveis diferentes de zero.
Propriedades e significado da solução viável básica
Propriedades da Solução Viável Básica
Uma solução básica factível tem no máximo m variáveis que não são zero e pelo menos nm variáveis que são zero, onde n é o número de variáveis de decisão e m é o número de restrições.
Um BFS é um canto do poliedro de soluções possíveis, e cada BFS tem n restrições ativas que são linearmente independentes.
Se existe uma melhor solução, deve haver também um melhor primeiro passo.
A coisa mais importante sobre as soluções viáveis básicas é que elas são as extremidades do conjunto de soluções convexas para um problema de programação linear.
Para encontrar a melhor resposta, o algoritmo simplex passa por uma série de BFSs.
O Algoritmo Simplex pesquisa todas as soluções básicas possíveis de forma organizada para encontrar a melhor.
Significado da Solução Viável Básica
Encontrar uma solução básica possível é importante porque ajuda a encontrar a melhor resposta para problemas de programação linear.
Ele também fornece um ponto de partida para algoritmos complexos e pode ser usado para descobrir se um programa linear é possível ou não.
Para encontrar todas as soluções viáveis básicas para um programa linear, você pode alterar o sistema adicionando variáveis de folga e, em seguida, usar o sistema alterado para encontrar todas as soluções viáveis básicas.
Então, essas soluções básicas viáveis são usadas para encontrar as soluções básicas viáveis para o problema original.
Vídeo: soluções viáveis básicas
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: | O BFS pode ser usado para dividir recursos limitados entre vários projetos para que o máximo possa ser feito com o mínimo. Este método pode ser usado em muitos campos diferentes, como transporte, agricultura e finanças. |
| Otimização da Rede: | O BFS pode ser usado para melhorar o funcionamento das redes de comunicação, transporte e logística. A BFS pode ajudar a encontrar as melhores rotas para mercadorias e serviços, reduzir o tempo e o dinheiro gastos com transporte, agilizar e fazer entregas mais precisas. |
| Planejamento da Produção: | O BFS pode ser usado para planejar a produção de forma que recursos como mão de obra, matéria-prima e equipamentos sejam utilizados da melhor forma possível para aproveitá-los ao máximo. O BFS pode ajudar a reduzir os custos de produção, reduzir o desperdício e melhorar a eficiência. |
| Planejamento financeiro: | No planejamento financeiro, o BFS pode ser usado para otimizar portfólios de investimentos, reduzir riscos e obter o máximo de retorno. A BFS pode ajudar a encontrar a melhor maneira de dividir os ativos, reduzir os custos de transação e ganhar mais dinheiro. |
| Gestão da Cadeia de Suprimentos: | O BFS pode ser usado para melhorar o fluxo de bens e serviços de fornecedores para clientes como parte do gerenciamento da cadeia de suprimentos. O BFS pode ajudar a descobrir a melhor quantidade de estoque a ser mantida, reduzir os prazos de entrega e melhorar o atendimento ao cliente. |
Conclusão
À medida que esta análise das soluções básicas viáveis chega ao fim, fica claro que elas são uma ferramenta importante para qualquer engenheiro ou estudante de engenharia.
Desde descobrir a melhor maneira de construir um sistema complicado até aproveitar ao máximo os recursos disponíveis, as soluções básicas viáveis fornecem uma estrutura para obter o melhor resultado possível.
Porém, mais do que úteis, eles mostram como a matemática pode ser elegante e bonita.
É incrível que você possa reduzir problemas complicados a um conjunto simples de equações e depois usar essas equações para resolver problemas no mundo real.
É um bom lembrete de que a engenharia trata de resolver problemas e que, usando o poder da matemática, podemos encontrar respostas que antes eram consideradas impossíveis.
Portanto, ao aprender mais sobre engenharia, lembre-se do que aprendeu sobre soluções simples que funcionam e use-as para tornar o mundo um lugar melhor e mais eficiente.
Links e referências
Livros:
- Programação Linear: Fundamentos e Extensões
- Programação Linear: Teoria e Aplicações
Compartilhar no…
