表形式のシンプレックス法を使用した生産問題の解決。 zlpを解くためのシンプレックス法

問題を解決する必要がある場合線形計画シンプレックステーブルを使用して、次にオンラインサービスあなたに大いに役立つでしょう。シンプレックス法は、領域のすべての頂点の順次列挙を意味します許容値関数が極値をとる頂点を見つけるため。最初の段階で、いくつかの解決策が見つかります。これは、後続の各ステップで改善されます。このソリューションは基本と呼ばれます。シンプレックス法を使用して線形計画問題を解くときの一連のアクションは次のとおりです。

最初の一歩。コンパイルされたテーブルでは、まず、無料のメンバーが含まれている列を確認する必要があります。負の要素が含まれている場合は、2番目のステップに進む必要があります。含まれていない場合は、5番目のステップに進む必要があります。

第二段階。 2番目のステップでは、シンプレックステーブルを再計算するために、基底から除外する変数と含める変数を決定する必要があります。これを行うには、無料のメンバーが含まれている列を調べて、その中の負の要素を見つけます。負の要素を持つ線は、リーディングラインと呼ばれます。その中に、絶対値の最大の負の要素、対応する列、つまりフォロアがあります。空きメンバーの間に負の値があるが、対応する行にはない場合、そのようなテーブルには解決策がありません。先頭の行を変更することにより、空きメンバーの列の1つが基準から除外され、先頭の列に対応する変数が基準に含まれます。

表1。

基本変数	制約のある無料メンバー	非基礎変数
基本変数	制約のある無料メンバー	x 1	x 2	...	x l	...	x n
x n + 1	b 1	11	12	...	1リットル	...	1n
x n + 2	b 2	21	22	...	2リットル	...	2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n + r	b2	r1	r2	...	rl	...	rn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n + m	b m	m1	m2	...	ml	...	mn
F（x）最大	F 0	-c 1	-c 2	...	-c 1	...	-c n

3番目のステップ。 3番目のステップでは、特別な式を使用してシンプレックステーブル全体を再計算します。これらの式は、を使用して確認できます。

4番目のステップ。再計算後、負の要素が空きメンバーの列に残っている場合は、最初のステップに進み、そのような要素がない場合は、5番目のステップに進みます。

5番目のステップ。 5番目のステップに到達した場合は、許容できる解決策を見つけました。ただし、これは最適であることを意味するものではありません。 F行のすべての要素が正の場合にのみ最適になります。そうでない場合は、ソリューションを改善する必要があります。次のアルゴリズムに従って、次の再計算のために先頭の行と列を見つけます。最初に、関数値を除いて、行Fで最小の負の数を見つけます。この番号の列が先頭になります。先頭の行を見つけるために、対応するフリーメンバーと先頭の列からの要素の比率を見つけます（正の場合）。最小の関係により、先頭の行を決定できます。数式を使用してテーブルを再計算します。手順3に進みます。

最適化問題を解く方法の1つ（ 通常、最小値または最大値を見つけることに関連しています）線形計画法が呼び出されます。 シンプレックス法線形計画問題を解決するためのアルゴリズムとメソッドのグループ全体が含まれています。初期データの記録と特別なテーブルへの再計算を提供するそのような方法の1つは、と呼ばれます。 表形式のシンプレックス法.

解の例を使用して、表形式のシンプレックス法のアルゴリズムを検討します。 生産タスク 、つまり、最大の利益をもたらす生産計画を見つけることになります。

シンプレックス法の問題の初期データ

企業は4種類の製品を製造し、3台のマシンで処理します。

マトリックスAで設定された、機械で製品を処理するための時間率（分/個）：

機械稼働時間基金（分）は、マトリックスBで指定されます。

製品の各ユニット（ルーブル/ピース）の販売からの利益は、マトリックスCで与えられます。

制作タスクの目的

企業の利益が最大になる生産計画を作成します。

表形式のシンプレックス法による問題の解決

(1) X1、X2、X3、X4に各タイプの製品の計画数量を指定しましょう。次に、目的の計画:( X1、X2、X3、X4)

(2) 連立方程式の形で計画の制約を書いてみましょう。

(3) 次に、目標利益：

つまり、生産計画の履行による利益を最大化する必要があります。

(4) 条件付き極値の結果として生じる問題を解決するために、追加の非負の変数を導入することにより、不等式のシステムを線形方程式のシステムに置き換えます（ X5、X6、X7).

(5) 次のことを考えてみましょう基本計画:

X1 = 0、X2 = 0、X3 = 0、X4 = 0、X5 = 252、X6 = 144、X7 = 80

(6) にデータを入力しましょうシンプレックステーブル:

最後の行に、目的関数の係数とその値自体を反対の符号で入力します。

(7) 最後の行で選択します最大 (モジュロ）負の数。

計算してみましょう b = N / Selected_Column_Elements

bの計算値の中から、少しでも.

選択した列と行の共通部分により、許可要素が得られます。基底を解決要素に対応する変数に変更します（ X5からX1).

解決要素自体は1になります。
分解線の要素の場合-aij（*）= a ij / RE（ つまり、各要素が解決要素の値で除算され、新しいデータが取得されます).
許容列要素の場合、それらは単純にゼロになります。
残りのテーブル要素は、長方形のルールに従って再計算されます。

a ij（*）= a ij-（A * B / RE）

ご覧のとおり、現在のセルを再計算し、セルに解像度要素を設定しています。それらは長方形の反対側の角を形成します。次に、この長方形の他の2つの角のセルからの値を乗算します。この作品（ NS * NS）は、解決要素（ NS）。そして、現在再計算されたセルから減算します（ a ij）どうした。私たちは新しい価値を手に入れます- a ij（*）.

(9) 最後の行をもう一度確認してください（ NS）オン負の数の存在..。それらがない場合は、最適な計画が見つかり、問題解決の最終段階に進みます。存在する場合、計画はまだ最適ではなく、シンプレックステーブルを再計算する必要があります。

最後の行に再び負の数があるので、計算の新しい反復を開始します。

(10) 最後の行にはネガティブな要素がないので、これは最適な生産計画を見つけたことを意味します！つまり、「基礎」の列に合格した製品、つまりX1とX2を生産します。私たちは、各生産単位の生産からの利益を知っています（ 行列C）。製品1と2の見つかった生産量に1個の利益を掛けるのはまだ残っており、最終的な（ 最大！ ）特定の生産計画の利益。

答え：

X1 = 32個、X2 = 20個、X3 = 0個、X4 = 0個

P = 48 * 32 + 33 * 20 = 2196ルーブル。

Galyautdinov R.R.

©資料のコピーは、への直接ハイパーリンクがある場合にのみ許可されます

x 1

x 2

S 1

x 1

x 2

S 2

x 1

x 2

S 3

変数が次の式に含まれている場合、その変数は特定の方程式の基本と呼ばれます。与えられた方程式係数は1で、残りの方程式には含まれていません（方程式の右側に正の数がある場合）。
各方程式に基底変数がある場合、システムには基底があると言われます。
基本的でない変数は自由変数と呼ばれます。（以下のシステムを参照）

シンプレックス法のアイデアは、ある基底から別の基底に移動し、少なくとも利用可能なもの以上の関数値を取得することです（各基底は単一の関数値に対応します）。
明らかに、問題のすべての可能なベースの数は有限です（そしてそれほど大きくはありません）。
したがって、遅かれ早かれ、答えが受け取られます。

ある基準から別の基準への移行はどのように実行されますか？
解を表の形式で記録する方が便利です。各行は、システムの方程式に相当します。強調表示された線は、関数の係数で構成されています（自分で比較してください）。これにより、毎回変数を書き換える必要がなくなり、時間を大幅に節約できます。
強調表示された行で、最大の正の係数を選択します。これは、少なくとも使用可能な値以上の関数の値を取得するために必要です。
選択された列。
選択した列の正の係数については、比率Θを考慮し、最小値を選択します。これは、変換後もフリーメンバー列が正のままであるために必要です。
行が選択されました。
その結果、基本となる要素が決定されました。次に、カウントします。

x 1

x 2

S 1

R 1

x 1

x 2

S 2

x 1

x 2

S 3

x 1 = 0 x 2 = 0 S 1 = 0
S 2 = 15 S 3 = 4 R 1 = 1

=> W = 1

ステップ1

x 1	x 2	S 1	S 2	S 3	R 1	NS。メンバー	Θ
-1	1	-1	0	0	1	1	1: 1 = 1
1	3	0	1	0	0	15	15: 3 = 5
-2	1	0	0	1	0	4	4: 1 = 4
1	-1	1	0	0	0	W-1
-1	1	-1	0	0	1	1
4	0	3	1	0	-3	12
-1	0	1	0	1	-1	3
0	0	0	0	0	1	W-0

x 1

x 2

S 1

x 1

S 1

S 2

x 1

S 1

S 3

ステップ1

x 1	x 2	S 1	S 2	S 3	NS。メンバー	Θ
-1	1	-1	0	0	1
4	0	3	1	0	12	12: 4 = 3
-1	0	1	0	1	3
4	0	1	0	0	F-1
-1	1	-1	0	0	1
1	0	3/4	1/4	0	3
-1	0	1	0	1	3
4	0	1	0	0	F-1
0	1	-1/4	1/4	0	4
1	0	3/4	1/4	0	3
0	0	7/4	1/4	1	6
0	0	-2	-1	0	F-13

S 1 = 0 S 2 = 0
x 1 = 3 x 2 = 4 S 3 = 6

=> F-13 = 0 => F = 13

選択した行係数の中に正の係数はありません。その結果、関数Fの最大値が見つかります。

シンプレックス法で問題を解く例と解く例を考えます。デュアルタスク.

タスク

3つのグループの商品を販売する場合、営利企業には、b 1 = 240、b 2 = 200、b 3 = 160ユニットの3種類の限られた材料と金銭的リソースがあります。同時に、1グループの商品を1,000ルーブルで販売します。売上高は、11 = 2ユニットの量の最初のタイプのリソース、21 = 4ユニットの量の2番目のタイプのリソース、31 = 4の量の3番目のタイプのリソースに費やされます。単位。 1000ルーブルの商品の2つおよび3つのグループの販売のため。売上高は、それぞれ、12 = 3、13 = 6ユニットの量の最初のタイプのリソース、22 = 2、23 = 4ユニットの量の2番目のタイプのリソース、リソースに費やされます。 32 = 6、33 = 8ユニットの量の3番目のタイプの..。 1000ルーブルの商品の3つのグループの販売からの利益。売上高は、それぞれc 1 = 4、c 2 = 5、c 3 = 4（千ルーブル）です。取引企業の利益が最大になるように、売上高の計画量と構造を決定します。

売上高を計画するという直接的なタスクに、 シンプレックス法で解ける、化粧 デュアルタスク線形計画。
インストール 変数の共役ペア直接および二重のタスク。
変数の共役ペアに従って、直接問題の解から、次のようになります。 双対問題の解決策その中で リソース評価商品の販売に費やされた。

シンプレックス法による問題の解決

x 1、x 2、x 3-販売された商品の数（千ルーブル）、それぞれ1、2、3-彼女のグループとします。その場合、問題の数学的モデルは次の形式になります。

F = 4 x 1 + 5 x 2 + 4 x3->最大

0）））（〜） "title ="（！LANG：delim（lbrace）（matrix（4）（1）（（2x_1 + 3x_2 + 6x_3 = 0）））（〜）">!}

シンプレックス法を解きます。

追加の変数x4≥0、x5≥0、x6≥0を導入して、不等式を等式に変換します。

x 4 = 240を基準とします。 x 5 = 200; x 6 = 160。

データをに入力します シンプレックステーブル

シンプレックステーブル番号1

目的関数：

0240 + 0200 + 0160 = 0

次の式を使用してスコアを計算します。

Δ1= 0 2 + 0 4 + 0 4-4 = -4
Δ2= 0 3 + 0 2 + 0 6-5 = -5
Δ3= 0 6 + 0 4 + 0 8-4 = -4
Δ4= 0 1 + 0 0 + 0 0-0 = 0
Δ5= 0 0 + 0 1 + 0 0-0 = 0
Δ6= 0 0 + 0 0 + 0 1-0 = 0

マイナスの評価があるため、計画は最適ではありません。最低点：

変数x2を基底に導入します。

基底を離れる変数を定義します。これを行うには、列x2の最小の非負の比率を見つけます。

= 26.667

最小の非負：Q 3 = 26.667。基礎から変数x6を導出します

3行目を6で割ります。
1行目から3行目を引き、3を掛けます
2行目から、3行目を減算し、2を掛けます

私たちは計算します：

我々が得る新しいテーブル:

シンプレックステーブル番号2

目的関数：

0160 + 0 440/3 + 5 80/3 = 400/3

次の式を使用してスコアを計算します。

Δ1= 0 0 + 0 8/3 + 5 2 / 3-4 = -2 / 3
Δ2= 0 0 + 0 0 + 5 1-5 = 0
Δ3= 0 2 + 0 4/3 + 5 4 / 3-4 = 8/3
Δ4= 0 1 + 0 0 + 5 0-0 = 0
Δ5= 0 0 + 0 1 + 5 0-0 = 0
Δ6= 0（-1）/ 2 + 0（-1）/ 3 + 5 1 / 6-0 = 5/6

負の推定値Δ1= -2 / 3があるため、計画は最適ではありません。

変数x1を基底に導入します。

基底を離れる変数を定義します。これを行うには、列x1の最小の非負の比率を見つけます。

最小の非負：Q 3 = 40。変数x2を基底から導出します。

3行目を2/3で割ります。
2行目から3行目を引き、8/3を掛けます

私たちは計算します：

新しいテーブルを取得します。

シンプレックステーブル番号3

目的関数：

0160 + 0 40 + 4 40 = 160

次の式を使用してスコアを計算します。

Δ1= 0 0 + 0 0 + 4 1-4 = 0
Δ2= 0 0 + 0（-4）+ 4 3 / 2-5 = 1
Δ3= 0 2 + 0（-4）+ 4 2-4 = 4
Δ4= 0 1 + 0 0 + 4 0-0 = 0
Δ5= 0 0 + 0 1 + 4 0-0 = 0
Δ6= 0（-1）/ 2 + 0（-1）+ 4 1 / 4-0 = 1

否定的な評価がないので、計画は最適です。

問題の解決策：

答え

x 1 = 40; x 2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x 6 = 0; F max = 160

つまり、最初のタイプの商品を4万ルーブルで販売する必要があります。 2番目と3番目のタイプの商品を販売する必要はありません。この場合、最大利益はF max = 160千ルーブルになります。

双対問題の解決

二重の問題は次のとおりです。

Z = 240 y 1 + 200 y 2 + 160 y3->分

Title = "（！LANG：delim（lbrace）（matrix（4）（1）（（2y_1 + 4y_2 + 4y_3> = 4）（3y_1 + 2y_2 + 6y_3> = 5）（6y_1 + 4y_2 + 8y_3> = 4）（y_1、y_2、y_3> = 0）））（〜）">!}

追加の変数y4≥0、y5≥0、y6≥0を導入して、不等式を等式に変換します。

直接問題と二重問題の変数の共役ペアは、次の形式になります。

直接問題の表3の最後のシンプレックスから、双対問題の解決策を見つけます。

Z min = F max = 160;
y 1 =Δ4= 0; y 2 =Δ5= 0; y 3 =Δ6= 1; y 4 =Δ1= 0; y 5 =Δ2= 1; y 6 =Δ3= 4;

検討 シンプレックス法線形計画問題（LP）を解くため。これは、あるベースライン計画から別のベースライン計画への移行に基づいており、目的関数の値が増加します。

シンプレックス法のアルゴリズムは次のとおりです。

追加の変数を導入することにより、元の問題を標準形に変換します。 ≤の形式の不等式の場合、追加の変数が（+）記号で導入されますが、形式≥の場合、（-）記号で導入されます。追加の変数が目的関数に導入され、係数が等しい対応する符号が付けられます。 0 以来目的関数はその経済的意味を変えるべきではありません。
ベクトルが書き出されます P i変数の係数と自由項の列から。このアクションは、単位ベクトルの数を決定します。規則は、制約のシステムに不等式があるのと同じ数の単位ベクトルが存在する必要があるということです。
その後、元のデータがシンプレックステーブルに入力されます。単位ベクトルが基底に導入され、それらを基底から除外することにより、最適な解が見つかります。目的関数係数は反対の符号で書かれています。
LP問題の最適性基準は、次の場合に解が最適であるということです。 NS-連続して、すべての係数が正です。列検索ルールを許可する-検索済み NS-負の要素の中から行と最小のものが選択されます。ベクター P iその含有は許容的になります。分解要素の選択規則-ベクトルの要素に対する分解列の正の要素の比率がコンパイルされます P 0そして、最小の比率を与える数は、シンプレックステーブルが再計算されることに関して解決要素になります。この要素を含む文字列は、解決文字列と呼ばれます。解決列に正の要素がない場合、問題は解決されません。解決要素を決定したら、次のステップは新しいシンプレックステーブルを再計算することです。
新しいシンプレックステーブルに入力するためのルール。解決要素の代わりに、1つが配置され、他の要素は等しいと見なされます 0 ..。分解ベクトルが基底に導入され、対応するゼロベクトルが除外され、残りの基底ベクトルは変更されずに記録されます。分解線の要素は分解要素で除算され、残りの要素は長方形の規則に従って再計算されます。
これはまで行われます NS-連続して、すべての要素が正になるわけではありません。