線形最適化のシンプレックス法は簡単に説明されています

線形最適化とは、希少なリソースをさまざまな用途に最適に割り当てることです。不足しているリソースは、たとえば、機械の容量や商品のスペース要件などです。最適なものは数学的に決定され、多くの場合シンプレックス法の助けを借ります。

線形計画法のモデリング

線形計画法をモデル化する場合、次のようなさまざまなパラメータ NS。ワークの処理時間や機械の能力を判断できます。次に、特定の制約の下で最大化される目的関数が定義されます。純利益を最大化することが企業の主要な目的であるため、目的関数は多くの場合利益関数です。制約は、リソースの不足によって説明されます（例： NS。容量、時間、スペース）。その後、シンプレックス法を使用して問題を解決できます。

簡単な例を作成すると、線形モデルを作成する手順を特に簡単に学ぶことができます。3台のマシンがあると仮定しますM₁、 NS₂ そしてM₃ その上で2つの製品P₁ およびP₂ 作成する必要があります。機械の能力は異なり、特定の製品の処理には時間がかかりますさまざまな時間のマシンで、完成した最終製品はさまざまな利益を生み出しますあちらへ。
私たちは現在、最大の利益をもたらす生産プログラム、つまり最大の利益を達成する生産プログラムを探しています。

数値の例とシンプレックス法の紹介

次のステップでは、問題をモデル化するための具体的な数値が必要です。 Pを編集するために₁ Mに₁ Mで2時間発生₂ 3時間とM₃ 4時間。 Pの場合₂ Mに落ちる₁ 4時間、Mで₂ 5時間とM₃ 3時間。 Mの機械容量₁ 500時間、Mの場合₂ 300時間、M3の場合は600時間。完成した最終製品の利益P₁ 完成した最終製品の場合、3ユーロ/個ですP₂ 4ユーロ/個。

3行3列のテーブルを作成し、行と列の見出し用のスペースを追加することをお勧めします。列を残す必要があります。たとえば、Pの処理時間は「列1と行1」フィールドにあります₁ Mに₁、「列2と行3」のフィールドで、Pの処理時間₂ Mに₃. 列3は、3台のマシンのマシン容量を示しています。

一次方程式で説明される線形連立方程式のガウスアルゴリズム

中学校で初めて線形連立方程式に遭遇します...

ここで、2つの変数xが必要です。₁、 NS₂ Pの生産量を定義する₁ およびP₂ 一致。
したがって、制約は2倍になります
instagram viewer
₁+ 4x₂ ≤500（マシン1）、3x₁+ 5x₂ ≤300（マシン2）および4x₁+ 3x₂ ≤600（マシン3）。いずれの場合も、容量を完全に使い果たす必要がないため、不平等があります。
最大化される目的関数（利益）はG（x₁、 NS₂）= 3x₁+ 4x₂ ->最大
さらに、xの非負の条件が生産量に適用されます₁、 NS₂ ≥ 0. ご覧のとおり、すべての方程式は線形方程式です。それらを一緒に見ると、線形最適化の問題が発生します。

線形最適化とシンプレックス法の適用

線形計画法を解くためのアイデアは、「スラック変数」を導入することによって不等式を排除することです。方程式修正された最適化問題はLGSとして解かれます。したがって、シンプレックス法は、LGSを解くためのガウスアルゴリズムと非常によく似ています。

例：飛行機は3つの商品Gで分割されます₁、 NS₂、 NS₃ 可能な限り高い総運賃値でロードされます。これらのスペース要件は1、0.2、または 6 dm³、1、0、4の重みを持ち、 8 kg、値10、3または 50ユーロ。貨物スペースが2000dmの場合、航空機はどのように理想的に積載されますか³ そしてそれは最大3000kgの貨物を運ぶことができますか？
xを定義します₁、 NS₂、 NS₃ 商品の数量としてG₁、 NS₂、 NS₃.
これで、次のようにスラック変数を使用して制約を設定できます。x₁+ 0.4x₂+ 8x₃+ x₄ = 3000およびx₁+ 0.2x₂+ 6x₃+ x₅ = 2000. 目的関数（総貨物額）はG（x₁、 NS₂、 NS₃）= 10x₁+ 3x₂+ 50x₃ ->最大これは、すべての変数を1ページにまとめることで変更できます（G-10x₁-3倍₂-50倍₃ = 0).
次に、シンプレックスパネルを設定します。 3行7列です。左側の列にxを入力します₁、 NS₂、 NS₃、 NS₄、 NS₅ 見出しとしてG。右側では、bが唯一の列です。これは、商品の最適な数量と可能な限り最高の総貨物価格がリストされている場所です。 3行目はターゲット行です。（チェック：上記の見出しのある3行には、番号があります：行1：1、0.4、8、1、0、0、3000、行2：1、0.2 6、0、1、0、2000 3行目：-10、-3、-50、0、0、1、0）。
次に、ガウスの方法を使用してLGSを解くときと同じように進めます。最初のステップでは、1行目を変更します。行2は送信され、他の行に追加されて、「行1 +列1」に1のみが表示され、「行2+列1」に0が表示されます。その結果、ターゲットラインの値も自動的に変更されます。
この場合、たとえば、行2に-1を掛けて、それを行1に追加し、行2に10を掛けることができます。 3行目に追加します（コントロール：1行目：0、0.2、2、1、-1、0、1000、2行目は同じまま、3行目：0、-1、10、0、10、1、 20.000).
2番目のステップでは、列2を取得し、「行2 +列2」を変換して0を作成し、次に「行1と列2」で1を作成します。繰り返しますが、ターゲットラインがどのように変化するかに注意する必要があります。
変換手順は、たとえば、行1に-1を掛けて、行2に追加し、行1を5に追加して、行3に追加することです。（チェック：両方のステップを実行した後、結果は次のようになります：行1：0、1、10、5、-5、0、5000、行2：1、0、4、-1、2、0、1000および行3 ：0、0、20、5、5、1、 25.000).
これで、パネルの右側にあるソリューションを読むことができます。これにより、合計運賃は25,000ユーロになり、5000ユニットの商品1、1000ユニットの商品2が輸送され、商品3のユニットは輸送されません。