【しっかり学ぶ数理最適化】2.2.3~2.2.4

2025年後期輪読会 #2(10/16) しっかり学ぶ数理最適化 京都大学 工学部 情報学科 B3 宮前明生 0

アジェンダ ◼ 単体法の概略 ◼ 単体法の原理 1

アジェンダ ◼ 単体法の概略 ◼ 単体法の原理 2

単体法の概略 単体法の解法（まずは行列を使わずに） Step1. 標準系の最適化問題にスラック変数を導入する Step2. 初期の実行可能基底解を試す Step3. 目的関数を改善できるように基底変数と非基底変数を入れ替える Step4. 目的関数を改善ができなくなるまでStep3を繰り返す 3

単体法の概略：Step1. 標準系の最適化問題にスラック変数を導入する max 𝑥1 + 2𝑥2 s.t. 𝑥1 ≥ 0 max 𝑥1 + 2𝑥2 s.t. 𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥2 ≥ 0 𝑥1 + 𝑥2 + 𝑥3 = 6, 𝑥1 + 𝑥2 ≤ 6 𝑥1 + 3𝑥2 ≤ 12 2𝑥1 + 𝑥2 ≤ 10 𝑥1 + 3𝑥2 + 𝑥4 = 12, 2𝑥1 + 𝑥2 + 𝑥5 = 10, 𝑥3 , 𝑥4 , 𝑥5 ≥ 0. • それぞれ制約条件に対する余裕としてスラック変数を導入する スラック変数 • 標準系の線形計画問題の変数がn個、制約条件がm個であれば、スラック変数を導入すると 変数の合計はn+m個 • 変数n+m個のうちn個が0の解は基底解と呼ぶ（例: 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 = (0,0,6,12,10)） • 基底解が制約条件を満たせば実行可能基底解と呼ぶ 非基底変数 基底変数 • 基底解のうち0に固定した変数を非基底変数、 0ではない変数を基底変数と呼ぶ 4

単体法の概略：Step2. 初期の実行可能基底解を試す max z = 𝑥1 + 2𝑥2 max s.t. 𝑥1 + 𝑥2 + 𝑥3 = 6, s.t. いずれもzを z = 𝑥1 + 2𝑥2 改善できる 𝑥3 = 6 − 𝑥1 − 𝑥2 , 𝑥1 + 3𝑥2 + 𝑥4 = 12, 𝑥4 = 12 − 𝑥1 − 3𝑥2 , 2𝑥1 + 𝑥2 + 𝑥5 = 10, 𝑥5 = 10 − 2𝑥1 − 𝑥2 , 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0. 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0. 𝑥3 , 𝑥4 , 𝑥5 について解く • まず、基底解 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 = (0,0,6,12,10)を考える。目的関数zの値は0 • 基底解を定めたら、基底変数𝑥3 , 𝑥4 , 𝑥5 について解く（この関係式を辞書と呼ぶ） • ここから、基底変数と非基底変数を1つずつ入れ替えて目的関数を最大化する（ピボット操作） • 入れ替える非基底変数は0から制約の上限まで増加させるので、目的関数zの変数の係数が正で あればzは改善され、変数の係数が負であれば改善されない • 目的関数zの係数が正の変数から入れ替える非基底変数を選ぶ 5

単体法の概略：Step3. 目的関数を改善できるように基底変数と非基底変数を入れ替える max z = 𝑥1 + 2𝑥2 s.t. 𝑥3 = 6 − 𝑥1 − 𝑥2 , 𝑥4 = 12 − 𝑥1 − 3𝑥2 , 𝑥5 = 10 − 2𝑥1 − 𝑥2 , 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0. • 入れ替える非基底変数を𝑥2 とする（ 𝑥1 = 0 でそのまま） • 𝑥2 が制約の中で最大化するには、𝑥1 = 0を代入して𝑥3 , 𝑥4 , 𝑥5 ≥ 0を満たせばいい 𝑥3 = 6 − 𝑥2 ≥ 0, 𝑥4 = 12 − 3𝑥2 ≥ 0, 𝑥5 = 10 − 𝑥2 ≥ 0, ⇔ 6 ≥ 𝑥2 , 4 ≥ 𝑥2 , 10 ≥ 𝑥2 , この制約条件下での𝑥2 の最大値は4であり、このとき𝑥4 = 0 → 非基底変数𝑥2 と基底変数𝑥4 を入れ替える • 更新した基底解は 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 = (0,4,2,0,6)。目的関数はz = 8 𝑥3 , 𝑥5 は 𝑥1 , 𝑥2 , 𝑥4 = (0,4,0)を条件に代入して求める 6

単体法の概略： Step3. 目的関数を改善できるように基底変数と非基底変数を入れ替える max max z = 𝑥1 + 2𝑥2 s.t. 𝑥3 = 6 − 𝑥1 − 𝑥2 , 𝑥 = 4 − 1 𝑥 − 1 𝑥 2 3 1 3 4 s.t. 𝑥4 = 12 − 𝑥1 − 3𝑥2 , 𝑥5 = 10 − 2𝑥1 − 𝑥2 , 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0. 1 3 2 3 z = 8 + 𝑥1 − 𝑥4 2 1 𝑥1 は𝑧を改善できる 𝑥3 = 2 − 𝑥1 + 𝑥4 , 3 3 1 1 𝑥2 = 4 − 𝑥1 − 𝑥4 , 3 3 5 1 𝑥5 = 6 − 𝑥1 + 𝑥4 3 3 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0. • 新たに𝑥2 を基底変数、 𝑥4 を非基底変数と更新した • 目的関数を非基底関数𝑥1 , 𝑥4 で表現したいので、 𝑥4 の辞書を用いて目的関数とその他辞書から 𝑥2 を消去する 1 1 𝑥4 = 12 − 𝑥1 − 3𝑥2 ⇔ 𝑥2 = 4 − 𝑥1 − 𝑥4 3 3 • また、目的関数zの係数が正の変数から入れ替える非基底変数を選ぶ→基底解の更新を繰り返す 7

単体法の概略：Step4. 目的関数を改善ができなくなるまでStep3を繰り返す max s.t. 1 3 2 3 z = 8 + 𝑥1 − 𝑥4 3 2 1 𝑥1 = 3 − 𝑥1 + 2𝑥4 2 𝑥3 = 2 − 𝑥1 + 𝑥4 , 3 3 1 1 𝑥2 = 4 − 𝑥1 − 𝑥4 , 3 3 5 1 𝑥5 = 6 − 𝑥1 + 𝑥4 , 3 3 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0. 1 2 1 2 max z = 9 − 𝑥3 − 𝑥4 s.t. 𝑥1 = 3 − 𝑥3 + 𝑥4 , 𝑧を改善できない 3 1 2 2 1 1 𝑥2 = 3 + 𝑥3 − 𝑥4 , 2 2 5 1 𝑥5 = 1 + 𝑥3 − 𝑥4 , 2 2 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0. • Step3を繰り返すと𝑧を改善できなくなり、そのときの基底解が最適解となる • 例では、 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 = (3,3,0,0,1)が最適解 8

アジェンダ ◼ 単体法の概略 ◼ 単体法の原理 9

単体法の原理 単体法の解法（主に行列） Step1. 初期の実行可能基底解(𝒙𝑩 , 𝒙𝑵 )を求める Step2. 被約費用ത𝒄𝑵 を求め、 𝑐𝑘ҧ > 0となる非基底変数𝑥𝑘 を選ぶ Step3. 非基底変数𝑥𝑘 の制約上限である𝜃 = max 𝑏ത𝑖 Τ𝑎ത𝑖𝑘 を求める 𝑖 ഥ − 𝜃𝑎ത𝑘 として、𝜃 = 𝑏ത𝑖 Τ𝑎ത𝑖𝑘 を満たす基底変数𝑥𝑖 を非基底変数𝑥𝑘 と入れ替える Step4. 𝑥𝑘 = 𝜃, 𝒙𝑩 = 𝒃 Step5. Step2 に戻り、ത𝒄𝑵 ≤ 𝟎となるまで繰り返す 10

単体法の原理： Step1. 初期の実行可能基底解(𝒙𝑩 , 𝒙𝑵 )を求める max s.t. z = 𝑥1 + 2𝑥2 𝑥1 + 𝑥2 + 𝑥3 = 6, 𝑥1 + 3𝑥2 + 𝑥4 = 12, 2𝑥1 + 𝑥2 + 𝑥5 = 10, 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0. 1 0 0 1 1 この場合は𝑩 = 0 1 0 , 𝑵 = 1 3 0 0 1 2 1 対応 max 𝒄𝑇 𝒙 s.t. 𝑨𝒙 = 𝒃, 𝒙 ≥ 0, 𝑨 ∈ ℝ𝒎×𝒏 , 𝒃 ∈ ℝ𝒎 , 𝒄 ∈ ℝ𝒏 , 𝒙 ∈ ℝ𝒏 • 一般に𝑚 < 𝑛であり、基底変数𝒙𝑩 の次元は𝑚、非基底変数𝒙𝑵 の次元は𝑛 − 𝑚 • 基底変数𝒙𝑩 に対応する𝒄のベクトルを𝒄𝑩 ∈ ℝ𝒎 , 𝑨の部分行列を𝑩 ∈ ℝ𝒎×𝒎 、非基底変数𝒙𝑵 に対応 する𝒄のベクトルを𝒄𝑵 ∈ ℝ𝒏−𝒎 , 𝑨の部分行列を𝑵 ∈ ℝ𝒎×(𝒏−𝒎) とする(𝑩は正則行列) 𝒙𝑩 𝑨𝒙 = 𝑩 𝑵 = 𝑩𝒙𝑩 + 𝑵𝒙𝑵 = 𝒃, 𝒄𝑇 𝒙 = 𝒄𝑩 𝑇 𝒙𝑩 + 𝒄𝑵 𝑇 𝒙𝑵 𝒙𝑵 • 初期の実行可能基底解(𝒙𝑩 , 𝒙𝑵 )は、 𝒙𝑵 = 𝟎より𝒙𝑩 = 𝑩−𝟏 𝒃、目的関数の値は𝒄𝑩 𝑇 𝑩−𝟏 𝒃 11

単体法の原理：Step2. 被約費用ത𝒄𝑵 を求め、 𝑐𝑘ҧ > 0となる非基底変数𝑥𝑘 を選ぶ max z = 𝑥1 + 2𝑥2 s.t. max 𝒄𝑩 𝑇 𝑩−𝟏 𝒃 + 𝒄𝑵 𝑇 − 𝑩−𝟏 𝑵𝒙𝑵 𝒙𝑵 𝑥3 = 6 − 𝑥1 − 𝑥2 , s.t. 𝒙𝑩 = 𝑩−𝟏 𝒃 − 𝑩−𝟏 𝑵𝒙𝑵 , 𝑥4 = 12 − 𝑥1 − 3𝑥2 , 対応 𝒙 ≥ 0, 𝑥5 = 10 − 2𝑥1 − 𝑥2 , 𝑨 ∈ ℝ𝒎×𝒏 , 𝒃 ∈ ℝ𝒎 , 𝒄 ∈ ℝ𝒏 , 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0. 𝒙 ∈ ℝ𝒏 • 次に、目的関数と𝒙𝑩 を𝒙𝑵 で表す • 𝑩𝒙𝑩 + 𝑵𝒙𝑵 = 𝒃を𝒙𝑩 について解くと、 𝒙𝑩 = 𝑩−𝟏 𝒃 − 𝑩−𝟏 𝑵𝒙𝑵 • 𝒙𝑩 を𝒄𝑇 𝒙 = 𝒄𝑩 𝑇 𝒙𝑩 + 𝒄𝑵 𝑇 𝒙𝑵 に代入すると、 𝒄𝑇 𝒙 = 𝒄𝑩 𝑇 𝑩−𝟏 𝒃 − 𝑩−𝟏 𝑵𝒙𝑵 + 𝒄𝑵 𝑇 𝒙𝑵 = 𝒄𝑩 𝑇 𝑩−𝟏 𝒃 + 𝒄𝑵 𝑇 − 𝑩−𝟏 𝑵𝒙𝑵 𝒙𝑵 • ここでത𝒄𝑵 = 𝒄𝑵 𝑇 − 𝑩−𝟏 𝑵𝒙𝑵 を被約費用と呼ぶ • 𝒄ത 𝑵 ≤ 0であれば (𝒙𝑩 , 𝒙𝑵 )は最適解、そうでなければ𝑐𝑘ҧ > 0となる非基底変数𝑥𝑘 を選ぶ 12

単体法の原理：Step3. 非基底変数𝑥𝑘 の制約上限である𝜃 = max 𝑏ത𝑖 Τ𝑎ത𝑖𝑘 を求める 𝑖 ഥ ത Step4. 𝑥𝑘 = 𝜃, 𝒙𝑩 = 𝒃 − 𝜃 𝑎ത𝑘 として、𝜃 = 𝑏𝑖 Τ𝑎ത𝑖𝑘 を満たす基底変数𝑥𝑖 を 非基底変数𝑥𝑘 と入れ替える max z = 𝑥1 + 2𝑥2 s.t. 𝑥3 = 6 − 𝑥1 − 𝑥2 , 𝑥4 = 12 − 𝑥1 − 3𝑥2 , 𝑥5 = 10 − 2𝑥1 − 𝑥2 , 𝑥2 を入れ替えるとすると条件は 𝑥3 = 6 − 𝑥2 ≥ 0, 𝑥4 = 12 − 3𝑥2 ≥ 0, 𝑥5 = 10 − 𝑥2 ≥ 0, 対応 𝑥𝑘 を入れ替えるとすると条件は ഥ − 𝑥𝑘 𝒂 ഥ𝒌 ≥ 0 𝒙𝑩 = 𝒃 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0. • 非基底変数𝑥𝑘 を選ぶと、次に𝑥𝑘 の制約上限𝜃を求める ഥ = 𝑩−𝟏 𝒃、 𝑩−𝟏 𝑵 ∈ ℝ𝒎×(𝒏−𝒎) で非基底変数𝑥𝑘 に対応するベク • 𝒙𝑩 = 𝑩−𝟏 𝒃 − 𝑩−𝟏 𝑵𝒙𝑵 について、 𝒃 トルഥ 𝒂𝒌 とする ഥ − 𝑥𝑘 𝒂 ഥ𝒌) (𝒙𝑩 = 𝑩−𝟏 𝒃 − 𝑩−𝟏 𝑵𝒙𝑵 に𝒙𝑵 = 0 ⋯ 𝑥𝑘 ⋯ 0 𝑇 を代入すると、 𝒙𝑩 = 𝒃 ഥ − 𝑥𝑘 𝒂 ഥ𝒌 ≥ 0を満たす最大の𝑥𝑘 が制約上限𝜃なので𝜃 = max 𝑏ത𝑖 Τ𝑎ത𝑖𝑘 • 𝒙𝑩 = 𝒃 𝑖 ഥ − 𝜃𝑎ത𝑘 として、𝜃 = 𝑏ത𝑖 Τ𝑎ത𝑖𝑘 を満たす基底変数𝑥𝑖 を非基底変数𝑥𝑘 と入れ替える • 𝑥𝑘 = 𝜃, 𝒙𝑩 = 𝒃 ഥ𝒌 ≤ 0ならば𝒙𝑩 ≥ 0を満たしつつ𝑥𝑘 が限りなく大きくできるので最適解は存在しない • ただし、 𝒂 • この後、Step2 に戻り、ത𝒄𝑵 ≤ 𝟎となるまで繰り返す 13