エンジニアリングにおける基本的な実行可能なソリューションの紹介

工学部の学生またはエンジニアであれば、可能な限り最高の結果を得るためにシステムを最適化することの意味を知っています。

ソリューションの最適化は、ブリッジの構築からソフトウェアの作成まで、すべてにおいて成功への鍵です。

この時点で、基本的な実行可能なソリューションのアイデアが生まれます。

これは線形計画法における基本的な考え方であり、考えられる一連の解のうちどれが最適かを判断できます。

しかし、なぜそれほど重要なのですか？この記事では、基本的な実行可能なソリューションと、それらを実際のエンジニアリングの問題を解決するために使用する方法について説明します。

それらを見つける方法、それらが何でできているか、そしてなぜそれらが重要なのかについてお話します.

ですから、あなたが経験豊富なエンジニアであろうと、初心者であろうと、一緒に基本的な実行可能なソリューションの世界に飛び込み、線形計画法の力を使用する方法を示します。

基本的な実行可能なソリューションを理解する

正式な定義:

すべての変数が非負である線形計画法モデルの基本的なソリューション。

基本実行可能解 (BFS) は、最適な解を見つけるのに役立つ線形計画法の重要なアイデアです。

BFS は、ゼロ以外の変数の数が可能な限り少ないソリューションです。

それは、実行可能な解の多面体の一角です。

つまり、BFS は非負の制約を満たし、実行可能領域または問題領域にある基本的なソリューションです。

最適な基本実行可能解を見つける

最適な BFS を見つけるには、次のことを行う必要があります。

• 線形シーケンスの標準形式でプログラムを記述します。
• 不等式を拡張行列に変換します。
• どの変数が基本的でどれがそうでないかを把握します。
• 他の変数に関して、基本的な変数が何であるかを把握します。
• これらの式を目的関数に入れて、基本的でない変数のみの関数を取得します。
• 制約を壊さずに増やすことができ、目的関数をより良くする非基本変数を見つけます。

この変数は基本変数になり、他の基本変数の 1 つが基本変数ではなくなりました。

最適な解がある場合、それは解が可能な領域の端または頂点の 1 つになければなりません。

したがって、LP に最適解がある場合は、実行可能セットの極値に最適解があります。

また、最適な解が存在する場合、常に最適な BFS が存在します。

シンプレックス法を使用して最適な BFS を見つける

シンプレックス法は、線形計画法の問題を解くためのアルゴリズムです。

ピボット手順を使用して、1 つの BFS から「隣接する」BFS に移動します。

ピボット手順では、非基本変数が選択されて基本変数になり、現在の BFS を使用して新しい基本変数が解決されます。

目的関数を改善するために非基本変数を変更できない場合、アルゴリズムは終了します。

複雑なエンジニアリングの問題を解決するために基本的な実行可能なソリューションが重要な理由

まだわかりにくい？少し視点を変えてみましょう：

とにかく、シンプルで実行可能な答えが必要なのは誰ですか? すべてを一緒に投げて、最高のものを願ってください。

結局のところ、カオスの方がはるかに楽しいのに、誰が最適化を必要としているでしょうか? すべてが単なる提案であり、失敗はほぼ確実な非負変数の世界へようこそ。

またはそれは？

基本的な実行可能な解決策の一見基本的な概念が基本的なものではない理由と、最も複雑な工学的問題を解決するための鍵となる理由を探ってみましょう。

わかりました、それはテレビコマーシャルのように見せかけた冗談です。

では、説明に戻りましょう。

基本的な実行可能な解決策を見つける

基本実行可能解 (BFS) は、すべての制約を満たし、ゼロ以外の変数の数が最も少ない線形最適化問題の解です。

各 BFS は、幾何学的な観点から見た実行可能なソリューションの多面体のコーナーです。

最善の解決策があれば、最善の最初のステップもあるはずです。

この記事では、初期の基本実行可能解を見つける方法、すべての基本実行可能解を見つける方法、およびスラック変数のない基本実行可能解を見つける方法について説明します。

初期の基本的な実行可能な解決策を見つける

問題の設定方法に応じて、さまざまな方法を使用して、線形最適化問題で機能する初期の基本的な解を見つけることができます。

1 つの方法は、不等式の制約にスラック変数を追加し、他のすべての変数をゼロに設定することです。

スラック変数は基本変数になり、残りは非基本変数になります。

2 フェーズ シンプレックス法は、この問題を解決するもう 1 つの方法です。

この方法では、余分な線形計画問題を解いて、実行可能な初期の基本解を見つけます。

初期の基本実行可能解が見つかったら、シンプレックス法を使用して、1 つの基本実行可能解から次の基本実行可能解に移動し、次に最適解に移動できます。

すべての基本的な実行可能なソリューションを見つける

線形計画法で機能する基本的な解が複数存在する場合があります。

スラック変数を追加してシステムを変更し、新しいシステムを使用して、線形プログラムのすべての基本的な実行可能なソリューションを見つけることができます。

次に、これらの基本的な実行可能解を使用して、元の問題の基本的な実行可能解を見つけます。

スラック変数のない基本的な実行可能なソリューションを見つける

スラック変数を使用せずに機能する基本的なソリューションを見つけることができるように、スラック変数を使用してより少ない制約を取り除く必要があります。

スラック変数は、制約の右側と左側の違いです。

たとえば、最初の制約では、スラック変数 x4 = 14 - 2x1 - x2 - x3 を定義します。この新しい変数に関して、最初の制約は単純に x4 ≥ 0 と同等であり、これは x4 の正の制約です。

これらのスラック変数を追加すると、元のプログラムと同じ線形プログラムが得られますが、すべての制約が、何かが正であるという方程式または制約のいずれかである点が異なります。

基本解でゼロ以外の値を持つ基本変数のセットは、基底と呼ばれます。

基本解でゼロの値を持つ変数は、基本変数ではありません。

最適解を見つけるには、すべてのルールを満たし、目的の最大値または最小値を取得するベクトル x を見つける必要があります。

ただし、最適なソリューションを見つけるには、機能し、スラック変数のないソリューションを見つけるだけではなく、さらに多くの手順が必要です。

スラック変数のない基本的なソリューションを見つけることが常に可能であるとは限りません。特に、制約が少ない問題の場合はそうです。

基本的な実行可能な解を見つけるには、シンプレックス法または別の線形計画法アルゴリズムを使用して、すべての制約を満たし、ゼロ以外の変数が最も少ない解を探す必要があります。

基本実行可能解の性質と意義

基本実行可能解の性質

基本的な実行可能解には、ゼロでない変数が最大で m 個、ゼロである変数が少なくとも nm 個あります。ここで、n は決定変数の数、m は制約の数です。

BFS は、可能なソリューションの多面体のコーナーであり、各 BFS には、線形に独立した n 個のアクティブな制約があります。

最善の解決策があれば、最善の最初のステップもあるはずです。

基本的な実行可能解について最も重要なことは、それらが線形計画問題の一連の凸解の端点であるということです。

最良の答えを見つけるために、シンプレックス アルゴリズムは一連の BFS を通過します。

シンプレックス アルゴリズムは、すべての基本的な可能なソリューションを整理された方法で検索して、最適なソリューションを見つけます。

基本的な実現可能なソリューションの意義

可能な基本的な解を見つけることは、線形計画法の問題に対する最良の解を見つけるのに役立つため、重要です。

また、複雑なアルゴリズムを開始する場所を提供し、線形プログラムが可能かどうかを判断するために使用できます。

線形計画法のすべての基本的な実行可能解を見つけるには、スラック変数を追加してシステムを変更し、変更されたシステムを使用してすべての基本的な実行可能解を見つけることができます。

次に、これらの基本的な実行可能解を使用して、元の問題の基本的な実行可能解を見つけます。

ビデオ: 基本的な実行可能なソリューション

ヒント: 必要に応じてキャプション ボタンをオンにします。話し言葉に慣れていない場合は、設定ボタンで「自動翻訳」を選択してください。お気に入りの言語が翻訳可能になる前に、まずビデオの言語をクリックする必要がある場合があります。

ユースケース

結論

基本的な実行可能なソリューションの考察が終わりに近づくにつれて、それらがエンジニアや工学部の学生にとって重要なツールであることは明らかです。

複雑なシステムを構築する最善の方法を見つけ出すことから、利用可能なリソースを最大限に活用することまで、基本的な実行可能なソリューションは、可能な限り最高の結果を得るためのフレームワークを提供します。

しかし、それらは単に有用であるだけでなく、数学がいかにエレガントで美しいかを示しています。

複雑な問題を単純な一連の方程式に要約し、それらの方程式を使用して現実世界の問題を解決できることは驚くべきことです。

エンジニアリングとは問題を解決することであり、数学の力を利用することで、かつて不可能と考えられていた答えを見つけることができることを思い出させてくれます。

したがって、エンジニアリングについてさらに学ぶときは、世界をより良く、より効率的な場所にするために機能し、それらを使用する単純なソリューションについて学んだことを心に留めておいてください。

リンクと参照

書籍:

• 線形計画法: 基礎と拡張
• 線形計画法: 理論と応用