【しっかり学ぶ数理最適化】2.2.5~2.2.6

2025年度後期輪読会 #3（2025/10/23） しっかり学ぶ数理最適化 2.2.5-2.2.6 退化・巡回・二段階単体法 京都大学 情報学研究科 福岡 M1 亮典 0

アジェンダ n 退化・巡回とは n 二段単体法とは 1

アジェンダ n 退化・巡回とは n 二段単体法とは 2

退化とは基底解の中で１つ以上の基底変数が0となること 以下の線形計画問題を考える 出典:しっかり学ぶ数理最適化 モデルからアルゴリズムまで 梅⾕俊治（ＫＳ情報科学専⾨書） 3

退化とは基底解の中で１つ以上の基底変数が0となること 以下の線形計画問題を考える 出典:しっかり学ぶ数理最適化 モデルからアルゴリズムまで 梅⾕俊治（ＫＳ情報科学専⾨書） 4

退化とは基底解の中で１つ以上の基底変数が0となること 以下の線形計画問題を考える 出典:しっかり学ぶ数理最適化 この問題の実行可能領域 モデルからアルゴリズムまで 梅⾕俊治（ＫＳ情報科学専⾨書） 5

退化とは基底解の中で１つ以上の基底変数が0となること 実行可能領域 頂点 (b) で３本の直線②, ③, ④が交差している そのため，頂点 (b) に以下の３つの実行可能基底解が存在 これらの実行可能基底解では値が０となる基底変数が存在する 出典:しっかり学ぶ数理最適化 モデルからアルゴリズムまで 梅⾕俊治（ＫＳ情報科学専⾨書） 6

退化とは基底解の中で１つ以上の基底変数が0となること 値が０となる基底変数が存在すると、 単体法のピボット選択次第では、 基底変数(x3)と⾮基底変数(x4)を⼊れ替え →基底変数(x4)と⾮基底変数(x3)を⼊れ替え →基底変数(x3)と⾮基底変数(x4)を⼊れ替え・・・ といったループから抜け出せなくなる→「巡回」 「巡回」の結果、⽬的変数の最適化が、終了条件に到達不可になる 出典:しっかり学ぶ数理最適化 モデルからアルゴリズムまで 梅⾕俊治（ＫＳ情報科学専⾨書） 7

退化とは基底解の中で１つ以上の基底変数が0となること 値が０となる基底変数が存在すると、 単体法のピボット選択次第では、 基底変数(x3)と⾮基底変数(x4)を⼊れ替え ここで⼊れ替えが⽌まれば →基底変数(x4)と⾮基底変数(x3)を⼊れ替え 「巡回」は発⽣しない →基底変数(x3)と⾮基底変数(x4)を⼊れ替え・・・ といったループから抜け出せなくなる→「巡回」 「巡回」の結果、⽬的変数の最適化が、終了条件に到達不可になる ⼊れ替え(ピボット)する基底変数を添え字が⼩さいものに限定する規則 →「最⼩添え字規則」 出典:しっかり学ぶ数理最適化 モデルからアルゴリズムまで 梅⾕俊治（ＫＳ情報科学専⾨書） 8

アジェンダ n 退化・巡回とは n 二段単体法とは 9

「二段階単体法」は初期実行可能基底を自動的に見つける手法 以下の線形計画問題を考える この問題の実⾏可能領域は↓ 出典:しっかり学ぶ数理最適化 モデルからアルゴリズムまで 梅⾕俊治（ＫＳ情報科学専⾨書） 10

「二段階単体法」は初期実行可能基底を自動的に見つける手法 以下の線形計画問題を考える 右辺が負となる制約条件が存在するため、 スラック変数 x3, x4, x5 と変数 z (⽬的関数 の値を表す)を導⼊して以下の辞書を作成 しかし、これを満たす実⾏可能解は存在しない 出典:しっかり学ぶ数理最適化 モデルからアルゴリズムまで 梅⾕俊治（ＫＳ情報科学専⾨書） 11

「二段階単体法」は初期実行可能基底を自動的に見つける手法 この問題を解く前に「⼈⼯変数 x0 」を新たに導⼊し、 実⾏可能基底解を１つ求める補助問題を作成する 補助問題の最適値が０ (x0＝0) であれば元の問題に 実行可能解が存在し，最適値が正 (x0＞0) であれば 元の問題に実行可能解が存在しないことが分かる． 出典:しっかり学ぶ数理最適化 モデルからアルゴリズムまで 梅⾕俊治（ＫＳ情報科学専⾨書） 12

「二段階単体法」は初期実行可能基底を自動的に見つける手法 以下の線形計画法の初期実行可能基底を「二段階単体法」を用いて求めよ 出典:しっかり学ぶ数理最適化 モデルからアルゴリズムまで 梅⾕俊治（ＫＳ情報科学専⾨書） 13

14