簡単のためフルランクシンプレックス法の原理標準形 Ax b, x 0 A c BN ,x cB cN cT x B,Nに対応して分割 1 xB BxB xN cBT xB T B T N Nx N b 基底行列，正則 c NT x N 1 c B b B b 0 かつ c 2014/5/2 A : R m n (m n, rank A m) c T B x T N 1 T B 1 c B N xN c B N 0 B 1b 0 最適解 1 c T N T B 1 c B N c T N T B 0 でないとき 1 c B N k 0 なる要素に負のものがある非基底変数 xk を増加目的関数値が減少 xk をどこまで増加できるか？ 2014/5/2 2 xk : 0 0とすると目的関数 cBT B 1b 基底変数 xB c NT 1 B b cBT B 1 N xB k 1 B b と減少 1 B Ak 行列Aの第k列 xB 0 でなければならないので， b 1 B b, y 1 B Ak とおくと min bi yi yi 0 i 1, ,m まで大きくできる． 2014/5/2 3 xk : 0 0 としたとき bi yi に対応する基底変数 xi yi 0 xi 非基底変数基底変数の入れ替え xk 基底変数（ピボット操作） 0 となる i がない xB xB y 0 : いくらでも大きくできる目的関数をいくらでも小さくできる有界でない 2014/5/2 4 シンプレックス法の手順 B 1b,0 を選ぶ．b Step0 : 初期実行可能基底解 xB , xN Step1 : cNT cBT B 1 N 0 ならば終了．xB は最適解．そうでなければ，cNT cBT B 1 N k 0 なる非基底変数 xkを選ぶ． Step2 : y B 1 Ak を計算． Step3 : y 0 ならば終了．有界でない．そうでなければ，を計算し， Step4 : 非基底変数 xk 基底変数 xB bi yi なる i を求める． , そのほかの非基底変数は 0 のまま． b y と更新しStep1へ． min bi yi yi 2014/5/2 B 1b とおく． 0 i 1, ,m 5 例題 min 2 x1 3x2 max 2 x1 3x2 s.t. 2 x1 x2 6 x1 2 x2 6 x1 0, x2 s.t. 2 x1 0 x2 x3 6 x1 2 x2 x4 x1 , x2 , x3 , x4 0 6 標準形への変換 2014/5/2 6 【反復１】スラック変数を基底→基底行列は単位行列，目的関数値は０ Step0 : xB Step1 : c T N x3 , x4 とする T B Step2 : y Step3 : b1 y1 Step4 : x1 xB 0 1 , xB b B 1b 2, 3 x1を基底変数に入れる x1 , x2 c B N B 1 A1 B 2 1 1 2 1 どちらも負 1 0 2, 3 2,1 3, b2 y2 T 0,0 B 1 0 6 3, 6,6 T bi yi なる i 1 3 : 基底に入る x3 , x4 b y 6,6 T 3 2,1 T 0,3 T x3 : 非基底変数になる 2014/5/2 目的関数値は－６ 7 【反復２】 xB x1 , x4 Step1 : c T N b T B B b 1 c B N 3,3 , B 3,0 B 1 A2 Step3 : b1 y1 Step4 : x2 2 xB x1 , x4 2,0 B 1 / 2, 3 / 2 6, b2 y2 b T 1 1 1 2 0 2,1 0 2 2, y x4 : 非基底変数になる 2014/5/2 1 1 x2 , x3 x2を基底変数に入れる最適解ではない Step2 : y 2 0 T 1 3,3 T bi yi なる i 2 1 / 2,3 / 2 T 2 2,0 T 目的関数値は－10 8 【反復３】 xB x1 , x2 Step1 : c T N b T B 1 B b 1 c B N T 2,2 , B 0,0 2, 3 B 1 / 3,4 / 3 2 1 1 2 1 1 0 0 1 非負現在の x は最適解，終了．最適値は 10 2014/5/2 9 図で見るとシンプレックス法は，反復ごとに隣の頂点へ移動する． Δの幾何学的意味＝ある辺に沿ってどこまで進めるか x2 6 3 ③ c 2 3 x1 ① 0 2014/5/2 3 ② 6 10 実行時の問題点１．Step1において cNT cBT B 1 N k 0 となる k が複数ある →どれを選んでもよいが， cNT cBT B 1 N k が最小のものを選ぶと実用上有効（とされている）．２．Step3において bi yi となる i が複数ある →複数の基底変数が同時に0になる．負で絶対値最大退化(degenerate)している 2014/5/2 11 退化が起こると x2 6 3 目的関数値は変化しないが 3 x1 x2 9 基底の入れ替えがおこるという制約を追加同じ基底解で循環する． ↓ 循環を防ぐ方法：最小添字規則（Blandの規則） x1 0 3 6 3つの直線が交差→退化 2014/5/2 12 シンプレックス・タブローまたは，タブローシンプレックス法を，表を用いて計算する．【同じ例題】 min 2 x1 3x2 s.t. 2 x1 2014/5/2 x2 x3 6 x1 2 x2 x4 x1 , x2 , x3 , x4 0 6 13 初期タブロー TT x3 x4 2 2 ccN 3 1 T B c B N 0 1 0 0 A N 1 2 0B 1 x1 x2 1 x3 x4 0 6 6 b b B 1 目的関数値×（－１）基底変数 2014/5/2 14 Step1 : どちらも負なので，例えば x1 を選ぶ． 2 3 0 0 0 x3 2 1 1 0 6 x4 1 2 0 1 6 Step2,3 : bi yi を計算し，を求める． 2 x3 x4 2014/5/2 2 1 3 0 0 0 1 2 1 0 6 b1 / y1 0 1 6 b2 / y2 3 6 15 ピボット Step4 : 掃き出し演算 2 x3 x4 2 1 0 3 0 0 0 1 2 2 x1 1 1/ 2 x4 0 3/ 2 ①この行をピボットで割る 1 0 6 0 1 6 1 1/ 2 ②－2倍して引く ③1倍して引く 0 6 ピボット以外のピボット 0 3 列の要素を0にする 1/ 2 1 3 負の要素があるので Step1へ 2014/5/2 x1 が基底に入る反復を繰り返す 16 ピボット Step1 : x2を選ぶ 0 x1 x4 1 1/ 2 0 3/ 2 0 0 x1 1 0 x2 0 1 2014/5/2 2 1 0 6 1 / 2 0 3 b1 / y1 6 1 / 2 1 3 b2 / y2 2 すべて非負→最適（終了） 1/ 3 4 / 3 10 最適値は－10 2/3 1/ 3 2 x 2 1 1 / 3 2 / 3 2 最適解 x2 2 17 シンプレックス法のまとめ実行可能解の隣にある頂点を探索する方法 →頂点の数は有限個→有限回で終了計算機上ではタブローを用いて計算残っている問題点初期実行可能解？計算量？ 2014/5/2 18 演習課題次の例題の最適解をシンプレックス法（タブロー）を用いて求める．（締め切り：5月8日（木）16時，Ⅳ系事務室へ） max 3 x1 6 x2 s.t. 2014/5/2 0.1x1 0.3 x2 1.5 1.2 x1 0.5 x2 6 0.4 x1 0.3 x2 2 .4 x1 0, x2 0 19