あなたがエンジニアまたは工学の学生であれば、最適化の意味を知っているかもしれません。
可能な限り最高の結果を得るには、最善の方法を見つけることが重要です。
線形計画法では、基本的な解を使用して最適な解を見つけることができます。
しかし、基本的な解決策とは何であり、エンジニアがそれらについて知ることがなぜそれほど重要なのでしょうか? この記事では、基本的なソリューションとは何か、それらがエンジニアリングで重要な理由、さまざまな状況で最良の結果を得るためにどのように使用できるかについて説明します。
腰を締めて、基本的なソリューションの世界に飛び込む準備をしてください。そこで、謎を解き明かし、このテクニックがどれほど強力であるかをお見せします.
線形計画法における基本的なソリューション
正式な定義:
n 変数の m 方程式からなる線形計画法モデルの解は、残りの (nm) 変数に関して m 変数を解き、(nm) 変数をゼロに設定することによって得られます。
線形計画法の基本的な解決策は、特定の技術要件を満たす線形計画法の問題を解決する方法です。
特に、ベクトル {ai : xi = 0} が線形独立である場合、ベクトル x は多面体の基本的な解です。
これは、ゼロでない変数 xi をもつ A の列が線形独立であることを意味します。
非負の要素を持つ基本的な解は、基本実行可能解 (BFS) (BFS) と呼ばれます。
BFS は、多面体を定義するすべての規則を満たしています。
各 BFS は、幾何学的な観点から見た実行可能なソリューションの多面体のコーナーです。
基本的な解を見つけるには、基本的でない nm 変数をゼロに設定し、基本的な m 変数を解かなければなりません。
異なるベースが同じ基本的な解決策につながる可能性があります。つまり、同じ問題を解決する方法が複数ある可能性があります。
シンプレックス方式は、最適な BFS が見つかるまで、ある BFS から次の BFS に移動する反復プロセスです。
シンプレックス法を使用して BFS を見つけた後、近くにある他の BFS が目的関数により良い値を与えるかどうかを確認することで、解が最適な解であるかどうかを判断できます。
そのような BFS がない場合は、現在の BFS が最適です。
線形計画法モデル
線形計画法モデルには、決定変数、目的関数、および制約という 3 つの主要コンポーネントが含まれます。
目的関数と制約の両方が線形関数でなければならず、決定変数は連続でなければなりません。
目的関数は、利益、コスト、製造された製品の数などを表す数値を増減するために使用されます。
制約は、決定変数の成功レベルを決定するタスクを実行するために必要な特定のリソースの総量に対する制限または制限です。
さらに、一部の線形計画では、すべての決定変数が非負である必要があります。
線形計画法モデルでは、整数変数とバイナリ変数も使用できます。
バイナリ変数は 0 または 1 の値しか持てないため、0 または 1 の値しか持てません。
シンプレックス法
線形計画法の問題を解決する最もよく使用される方法の 1 つは、シンプレックス法です。
基本解はシンプレックス法では重要です。なぜなら、それらは実行可能領域のコーナー ポイントに対応し、シンプレックス法は最適解が見つかるまで 1 つのコーナーから別のコーナーに移動するからです。
シンプレックス法は、基本的な解の特性を使用して、線形計画問題の最良の解をすばやく見つける方法です。
シンプレックス法を使用して最適な BFS を見つけるには、制約行列 A の基底 B を見つけ、基底以外のすべての変数をゼロに設定して系 Ax = b を解く必要があります。
基本変数の結果の値は、BFS を形成します。
最適解が存在する場合、最適 BFS が存在します。
シンプレックス方式は、ピボット手順を使用して、最適な BFS に到達するまで、1 つの BFS から隣接する BFS に移動します。
ベーシックソリューションとフィージブルソリューションの比較
基本的な解決策と実行可能な解決策の違いは、基本的な解決策は条件を満たさなくてもよいということです。
特に、線形独立で xi の値が 0 でないベクトルを持たなければならず、x は 0 未満でなければなりません。
一方、実行可能な解は、問題の範囲内に収まる任意の点です。
しかし、すべての実行可能なソリューションが基本的な実行可能なソリューションであるとは限りません。
基本実行可能解 (BFS) は、実行可能解の多面体の角に一致するもののみです。
基本に戻る: エンジニアリングにおける基本的なソリューションの力を解き放つ
まだわかりにくい？少し視点を変えてみましょう：
難しい問題を解決するために複雑な方法やアルゴリズムを使用することにうんざりしていませんか? 線形計画法モデルの問題を処理するための、より単純で直接的な方法があればいいのにと思いませんか?
心配はいりません。答えはここにあります。 M 個の変数を残りの (nm) 個の変数に関して解き、(nm) 個の変数をゼロに設定します。
基本に立ち返ることができるのに、派手に聞こえるアルゴリズムが必要な人はいません。それでは、電卓を片付けて、簡単な解決策について学び始めましょう。
わかりました、それはテレビコマーシャルのように見せかけた冗談です。
では、説明に戻りましょう。
基本的なソリューション 線形計画法
ヒント: 必要に応じてキャプション ボタンをオンにします。話し言葉に慣れていない場合は、設定ボタンで「自動翻訳」を選択してください。お気に入りの言語が翻訳可能になる前に、まずビデオの言語をクリックする必要がある場合があります。
ユースケース
| で使われる： | 説明： |
|---|---|
| 資源配分： | 基本的なソリューションは、限られたリソースを競合するニーズに分割することを目標とするリソース割り当て問題で使用できます。たとえば、企業は予算をさまざまな部門またはプロジェクトに分割する必要がある場合があります。基本的なソリューションを使用することで、リソースを使用して最大限の収益を上げるか、支出を最小限に抑える最善の方法を見つけることができます。 |
| 生産計画: | 生産計画では、基本的なソリューションを使用して、最大の利益を得るために製造する製品の最適な組み合わせを把握できます。企業は、基本的なソリューションを使用することで、最大の収益と最小のコストをもたらす最適な生産構成を見つけることができます。 |
| スケジューリング: | 基本的なソリューションを使用して、最も効率的な方法でタスクまたはジョブをスケジュールする方法を理解できます。たとえば、会社は、ビジネスが忙しいときに十分な従業員を確保するために、従業員の勤務時間を計画する必要がある場合があります。基本的なソリューションを使用することで、可能な限りダウンタイムを減らし、できるだけ多くの作業を完了できるようにスケジュールを設定する最善の方法を見つけ出すことができます。 |
| サプライチェーンの管理: | サプライ チェーン管理の目標は、商品やサービスがサプライヤーから顧客にできるだけスムーズに移動するようにすることです。たとえば、企業は、コストを最小限に抑え、商品を時間どおりに配達するために、商品を輸送するための最適なルートを見つける必要がある場合があります。基本的なソリューションを使用することで、コストを低く抑え、顧客を満足させるサプライ チェーンを管理するための最適な計画を見つけることができます。 |
| ポートフォリオの最適化: | ポートフォリオの最適化では、リスクを最小限に抑えながら最大の利益を上げるための投資の最適な組み合わせを見つけることが目標であり、基本的なソリューションを使用できます。たとえば、投資会社は、クライアントが投資目標を達成できるように、株式、債券、およびその他の証券の最適な組み合わせを見つけ出す必要がある場合があります。シンプルなソリューションを使用することで、リスクを最小限に抑えながら最高のリターンを得るために、ポートフォリオを組み合わせる最善の方法を見つけることができます。 |
結論
結論として、基本的なソリューションのアイデアは、エンジニアリングの分野で非常に重要であり、さまざまな方法で使用できます。
基本的なソリューションとは何か、線形計画法でそれが何をするかを知ることで、ソリューションを改善し、コストを削減し、より効率的にすることができます。
ただし、基本的なソリューションは強力なツールですが、万能のソリューションではないことを覚えておくことが重要です。
最良の結果を得るには、それぞれの問題を注意深く見て検討する必要があります。
エンジニアとして、私たちは基本的な解決策やその他の最適化手法が進歩を遂げ、新しいアイデアを生み出すのにどのように役立つかを調べ続ける必要があります。
ですから、シンプルなソリューションの力を認識し、新しいテクニックと戦略を使用して可能なことの限界を押し上げ続けましょう.
リンクと参照
書籍:
- Vasek Chvatalによる線形計画法
- Jose M. Sallan による R による線形計画法のモデル化と解法
共有…
