4 巡回と退化，計算量 4.1 巡回と退化二段階単体法で線形計画問題を解くと，次のいずれかに達して終了する． (a) (b) (c) (d) 実行可能解が存在しない．（非有界解．（ phase2 ） phase1 ）最適解．？停止しない．巡回：同一の基底形式が再び現れる． * 巡回の起ることは確かにある．巡回の間目的関数 z の値は変わらない．退化（ 0 をとる基底変数の存在）が生じている．巡回の生起は取入れ変数／追い出し変数の選び方に関係する．［巡回対策］摂動法（ perturbation method ），辞書的順序則（ lexicographic rule ）：目的行において正係数をもつ index 最小の変数を取入最小添字則（ smallest subscript rule ）れ，b =a 最小の（ tie のときは index のより若い）基底変数を追い出す．（証明 R.G. Bland，1977 ） 0 0 ともかく，理論的には，巡回／退化を避けることができる．従って，二段階単体法は次の基本定理を構成的に証明していることになる．［基本定理］標準形の線形計画問題は (1) 最適解を持たない場合 =) 実行可能解ナシ／非有界解 (2) 実行可能解を持つ =) 実行可能基底解を持つ (3) 実行可能基底解をもち，最適解を持つ =) 最適基底解を持つ 4.2 計算量 4.3 巡回の起こる例題最大係数則で取入れ変数を選ぶと巡回の起る例 8 max z = 10x1; 57x2; 9x3 ;24x4 > > 0:5x1;5:5x2;2:5x3+ 9x4 < s.t. 0:5x1;1:5x2;0:5x3+ x4 > x1 > : x1 * 最大係数則（ largest b =a をもつ変数を取入れ， 0 0 x2 x3 x4 coe cient rule ）で取入れ変数を選んだとき巡回の起る例を作れる．最小の基底変数を追い出す（これは必然）やり方．tie-break { 12 { 0 0 1 0 rule 最大係数則とは，目的行において最大正係数としては index の若いものを選ぶ． 5 行列表現，改訂単体法，感度解析単体法の実行過程を行列によってコンパクトに表現する．拡大基底形式を直接表現したものと目的関数の表式に注目したもの．後者からは改訂単体法が導かれる．制約条件式の右辺値を変化させるとき，最適解の値はどのように変化するか？ 5.1 行列表現 8 max < : s.t. z = cT x Ax = b x 0 A = (a1 a2 : : : an ) ( A 2 M (m n) rank(A) = m ) 基底変数 fxi1 xi2 : : : xim g と非基底変数 fxj1 xj2 : : : xjn m g が与えられたとする． B：基底変数に対応する A の列ベクトルを取り出して並べたもの．（基底行列） B は正則で B x = b の解は非負． N ：非基底変数に対応する A の列ベクトルを取り出して並べたもの． A の列ベクトル，x，c を上記の順に並び換え，(P) を (P ) のように分離して書く． (P) ; 0 (P ) 0 8 max < : s.t. z = cB T xB +cTN xN B xB + N xN = b xB xN 0 現在の基底変数に対する拡大基底形式は以下のように書ける． ( B 1N xN = B 1b + (cTN ; cTB B 1N )xN = ;cTB B 1 b xB + ;z ; ; ; ; 5.2 simplex 乗数 z を xN だけで表わすため，B xB + N xN = b の各行に然るべき数を乗じて，目的行から引き，z の表式から xB を消去する．この制約式の各行に乗ずる値を \simplex 乗数" といい，u = (u1 u2 : : : um ) と書く． z xN だけで表わしたときの xN の係数を相対コストと呼ぶ． u の値は，連立方程式 cTB ; uB = 0 で決まる． u が決まると，相対コスト (cN )T = ( cj1 cj2 : : : cjn m ) が (cN )T = cTN ; uN と決まる． z0 = ub． cN が求まると取入れ変数（ j ）が決まる．（または，最適！）また，を 0 0 0 0 0 ; 0 { 13 { xj 列の係数列ベクトルは xB + B 1 ; aj = 0 N xN = B 1b より） B 1aj ; ，また定数列は b = 0 B 1b ; となる．（基底形式 ; 5.3 改訂単体法（改訂 simplex 法） simplex タブローの代わりに，simplex 乗数と基底行列の逆行列を用いる単体法［算法 revised simplex method ］ step1 可能基底行列 B = (ai1 ai2 : : : aim ) を定める． step2 uB = cTB を解いて，u を求める． T さらに (cN ) = cT N ; uN を求め，最適性の判断／取入れ変数（ xj ）の決定を行なう． step3 B aj = aj を解いて，aj を計算． step4 B b = b を解いて，b を計算し，追い出し変数（ xid ）を決定する． B (ai1 : : : aid 1 aj aid+1 : : : aim ) goto step2．［ B x = ~ ／ xB = ~ の計算］ 0 0 0 0 0 ; 5.4 感度解析目的関数の最大値 zo を，制約式右辺値 b1 : : : bm の関数と考える．これらが変動したとき zo がどのように変化するか？最適タブローを与えるであるから simplex 乗数を u = (u1 u2 : : : um) とする． @zo = u @bi i (i = 1 2 : : : m): ui > 0 のとき ui = 0 のとき ui < 0 のとき ~ ~ ~ ) 補遺 aij の変化するとき． c の変化するとき． { 14 { zo = u b このとき