2.1 アルゴリズム

1. 各枝の適合性チェック
   繰り返すようであるが、相補性の定理から最適巡回時に各枝がとるべき状態は次の３つのどれかである。
   • L : C_ij > 0 かつ X_ij = l_ij
   • B : C_ij = 0 かつ l_ij ≦ X_ij ≦ K_ij
   • K : C_ij < 0 かつ X_ij = K_ij
   即ち状態Ｌの枝は損であるから、要求された下限の流量しか流さない事とし、Ｂの枝は最短路を構成しているから、許容範囲内で任意の値を取れる。そしてＫの枝は大変得であるから目いっぱい流す事とする。
   このようにしてネットワーク内のすべての枝がＬ、Ｂ、Ｋ、のどれかの状態を取るとすると、それは最適な巡回と言えるであろう。そこで、これらの枝の状態を最小費用という目的に適っているという意味で適合（In-kilter）な枝と呼ぶ。
   次に最適巡回に到達していない時点における任意の巡回においては、何本かの枝は次の６種類の状態のどれかを取っている。これらは不適合（Out-of-kilter）な枝と呼ばれる。
   
   • L1 : C_ij > 0 かつ X_ij < l_ij
   • L2 : C_ij > 0 かつ X_ij > l_ij
   • B1 : C_ij = 0 かつ X_ij < l_ij
   • B2 : C_ij = 0 かつ X_ij > K_ij
   • K1 : C_ij < 0 かつ X_ij < K_ij
   • K2 : C_ij < 0 かつ X_ij > K_ij
   これら不適合な枝は次に述べる方法を施すと適合な状態に追い込むことができる場合が多い。第一の方法は流れを変えることであり、第二の方法は原価（ポテンシャル）を強制的に変化させて、その結果として流れを変えることである。そこで、例えばある枝がＬ１の状態の場合、その流れを l_ijまで増流（l_ij - X_ij ）すれば適合な状態にすることができる。この（l_ij - X_ij ）を不適合な枝の偏差または"Kilter Numbers"（適合にするには、あと流れを何単位増減すれば良いかという数値）と呼ぶ。従って最終的にすべての枝の偏差を０にすれば、それは最適巡回といえるであろう。

2. ラベリング
   前項で枝の偏差を０にするため流れを変えることを述べたが、それを実行する手段として強力なのがラベリングである。

   図６
   

   

   
   ある枝ｉ→ｊが不適合だと仮定し、その枝の流量を１単位増加したいとする。そのためには、例えば点ｊからｊ→ａ→ｂ→ｃ→ｄ→ｉ, というような巡回を考える。そのとき巡回を構成するいかなる枝の偏差をも増加しないよう注意しなければならない。このような巡回を構成できたならば、ラベリングと同じ方法の枝（枝ｉｊ、枝ｊａ、枝ｃｄ）に対しては流量を１単位増加する。逆方向の枝（枝ｂａ，枝ｃｂ、枝ｄｉ）に対しては流量を１単位減らす。他方、枝ｉ→ｊ の流量を１単位減らしたときは、点ｉからラベリングを始めｉ→ｅ→ｆ→ｇ→ｊ というような巡回を構成する。勿論、各枝の偏差は増大しないようにすべきである。後は増流巡回と同様その巡回に含まれる各枝の流量をその矢印に従って増減する。このように流量変化のための巡回を見つけることをラベリング手順という。

3. ラベリング手順
   1. 不適合な枝を見つけたら、増流、減流の目的に従い、ラベリングを始める点を０、終点をｎとする。
   2. 始点０にラベル（" ",∞）をつける。ラベルの前の数字は、その点にどの点から ラベルがついたかを示し、後の数字その点までにどの位の流量を増加させる事ができる かを示す。
   3. ある点ｉに点ｈからラベル（ｈ、α_i）がついたものとする。点ｉに 枝をもっている点で、まだラベリングされていないすべての点ｊを考えるとき、それら の間の枝が次のような状態であれば、その点ｊに対しラベリングする事ができる。

      ----------------------------------------------
      図７
      

      (ｉ，Min[αi，ｌij−ｘij]) (ｉ，Min[αi，ｋij−ｘij]) (ｉ，Min[αi，ｘij−ｌij]) (ｉ，Min[αi，ｘij−ｋij]) ラベリング不能

      ラベリングされている.....→.....ラベリングしようとする点
      ----------------------------------------------
      λ：C_ij ＞ 0 かつ X_ij ＜ l_ij
      μ：C_ij ≦ 0 かつ X_ij ＜ k_ij
      ν：C_ij ≧ 0 かつ X_ij ＞ l_ij
      ρ：C_ij ＜ 0 かつ X_ij ＞ k_ij
      新しくラベリングされた各点の増加可能流量はそれぞれ
      Min[α_i，ｌ_ij−ｘ_ij]、 Min[α_i，ｋ_ij−ｘ_ij]、
      Min[α_i，ｘ_ij−ｌ_ij]、 Min[α_i，ｘ_ij−ｋ_ij]となる。

   4. この手順で終点ｎがラベリング［ｌ，α_n］されたとすると、その巡回 （０→ａ→ｂ→……→ｉ→ｊ→……→ｎ）において、 順方向の矢印を持つ枝はα_n増流し、逆方向の枝はα_n減流 することができる。こうして構成された巡回の中では、いかなる枝の流量をα_n 増減しても、その枝の偏差が増加しないことは明白であろう。それどころか、いくつか の不適合な枝はその偏差を減少する。
   5. もし終点ｎがラベリングできないときは、次に述べる原価（ポテンシャル） 変更の原価を強制的に操作する方法を使って、最終的に流量変更のための巡回を 作り出す工夫をする。

4. 原価（ポテンシャル）の変更
   前項で述べたラベリング手順によって常に終点ｎがラベリングできれば良いが、どうしてもこれ以上ラベリングできないという事態が生じることがある。
   例えば点ｉまでラベリングでき、その後点ｊにラベリングできなくなったと仮定する。
   ----------------------------
   図８
   

   この時の状態は次の２種類のどちらかになる。 λ：Cij ＞ 0 かつ Xij ＞ lij μ：Cij ≦ 0 かつ Xij ≧ kij

   ラベリングされている→されていない
   ----------------------------
   この状態は、それぞれラベリングできる状態λ、μの反対（流れがとる範囲） の関係になることから分かっていただけると思う。ところでこのとき、状態μ はいかなる工夫をしても流量増加が偏差の増大につながる。しかし状態λ の場合は、C_ijを０にすれば流量を増加できる可能性を秘めている。 即ちラベリングされる可能性を持っている。
   -------------------------------
   図９
   

   同様に図９において、点ｊがラベリングされて、そこに流入している枝をもつ点ｉがラベリングできないと仮定すると、枝ｉ→ｊは次の状態のどれかになる。 ν：Cij ≧ 0 かつ Xij ≦ lij ρ：Cij ＜ 0 かつ Xij ≦ kij

   ラベリングされていない→されている
   -------------------------------
   状態νは、どのようにしても減流できないが、ρの場合は、C_ij を０にすれば、流量が下限制約（l_ij ）を超えている分だけ減らすことができる。この二つの枝の状態λとρ はラベリングが進まなくなった時点において、重用な解決策を与えている。
   そこで、どうしてもこれ以上ラベリングが進まないという局面において、Ｉ をラベリングされた点の集合、Ｉをラベリングできない点の集合とする。そして そこに行き交う枝をもってカットを形成する。このカットに属する枝のうち次の 状態を持つ枝の集合を考える。
   S₁=｛(ｉ,ｊ)｜ｉ∈Ｉ，ｊ∈Ｉ，Ｃ_ij＞０，Ｘ_ij≦ｋ_ij｝
   S₂=｛(ｉ,ｊ)｜ｉ∈Ｉ，ｊ∈Ｉ，Ｃ_ij＜０，Ｘ_ij≧ｌ_ij｝
   S₁は増流できる可能性を持った枝λの集合を意味し、Ｓ₂ は減流できる可能性を持った枝ρの集合である。そして原価変更する値θ を次のように定める。
   θ＝Min［S₁集合：Min（C_ij），S₂集合：Min（-C_ij）］
   Ｓ₁＝Ｓ₂＝０のとき　θ＝∞
   もしカットにおいてラベリングを続ける可能性のある枝がない（Ｓ₁＝Ｓ₂＝０） とすれば、この問題は解を持たない。又、もしθをある値に設定できるならば、 カットに接するラベリングされた各点ｉの原価を、状態S₁、S₂ に従って強制的にθ上げ下げする（ポテンシャルをθ変化させる）。
   この結果新しいポテンシャルを得る。
   

   Ｕ_i＝Ｕ_i＋θ　　ｉ∈Ｉ　

   Ｕ_i＝Ｕ_i　　　　　ｉ∈Ｉ　

   又、Ｃ_ijの新しい値は
   

   Ｃ_ij＝Ｃ_ij＋θ　　：(ｉ,j)∈（Ｉ，Ｉ）　

   Ｃ_ij＝Ｃ_ijーθ　　：(ｉ,j)∈（Ｉ，Ｉ）　

   Ｃ_ij＝Ｃ_ij　　　　　：その他の枝　

   枝の損得を判断するＣ_ijが変化し、Ｓ₁かＳ₂ のうち少なくとも１本の枝（Ｓ₁のときは状態μに、Ｓ₂ のときは状態νに）はラベリング可能な枝に変化する。このようにＣ_ij を操作することによりラベリングできる点を増加し、何回かの後、目的とする流量 変化の巡回を完成する訳である。
   またθの選択は状態Ｓ₁の枝については本来Ｃ_ij＞ 0 で、流れを増やすと損である。しかし強制的にＣ_ijを０［送り 側（売り手）が原価を割引したとする］に変え、損はないとして増流する訳である から、その変化量（費用増加分）θは最小とすべきである。同様に状態Ｓ₂ の枝についても、本来Ｃ_ij＜０で得た枝であるから、上限一杯 に流したい枝の筈である。しかしわざとＣ_ijを０［受取側（買い手） が原価が安いと振舞う］に変え、得はないとして減流しようとする訳であるから、 その変化量（値上がり分）θはやはり最小にすべきであることがわかる。
   このように不適合なすべての枝についてラベリング手順を施し、流量変化と原価 （ポテンシャル）の変更を適宜繰返しながら一本つづ適合な枝に変え、ついには最適 巡回に到達することができる。

5. Out-of-Kilter法 フローチャート