実数型 simplex 法の効率的な解き方の提案と検証

実数型 simplex 法の効率的な解き方の提案と検証
卒業研究者古味良，庄野真
指導教員竹内光生
1. はじめに
線形計画法は、与えられた線形の制約条件の下で、ある一つの線形の目的関数を最大あるいは最小にするもの
であり、オペレーションズ・リサーチ、システム工学、経営工学、管理工学などのさまざまな分野において、代
替案の作成手法として広く適用されている。本研究室においても、南海地震に備えた避難施設配置問題の最適配
置手法として、p メディアン探索および線形計画法（混合整数線形計画法）を適用している。
一般に、線形計画問題は、目的関数と制約条件式群のシンプレックス表を、連立方程式解法であるガウス・ジ
ョルダンの消去法により求めることができる。しかし、正順（原点側が実行可能解）以外に、逆順（原点と反対
側が実行可能解）や等式の制約条件式が含まれる場合は、人工変数を追加、また 2 段階単体法 1)と呼ばれる一般
に理解しがたい解法が、線形計画法の基礎とされる。本報告は、実数型シンプレックス法の効率的な解き方の提
案と検証を課題としている。
2. 提案 simplex 法の概要
2.1 simplex 法の一般化
提案する simplex 法は、①正順以外に逆順や等式の制約条件式の混合問題も解ける。②人工変数を追加しなく
ても解ける。
③制約条件式群に矛盾がある場合の判別も可能である。
④有界あるいは非有界の判別も可能である。
⑤制約条件式群は、等式、逆順、正順の順に解く必要があり、従来の単体法とはピボットの選択手順が異なる。
⑥ステップ数（ピボット回数）は、2 段階単体法よりも少ない。⑦操作手順は単純かつ効率的である。
2.2 解析手順
①問題を最小値問題とする。最大値問題のとき Z を－Z として解く。②逆順の制約条件式の両辺に－1 を掛け、
すべての制約条件式を等式あるいは正順型とする。③等式以外の制約条件式にスラック変数を追加し、すべての
制約条件式を等式とする。④スラック変数を追加しなかった等式について、まず、1 つ目の等式のうち x1 の係数
から調べ、0 でない係数をピボットとし、ピボット操作を行う。同様の操作を、スラック変数を追加しなかった
すべての等式について行う。⑤負の常数項 bi(<0)のうち絶対値最大の｜bk｜（k 番目の制約条件式）を選ぶ。K 番
目の制約条件式係数 akj および目的関数の係数 cj が共に負の列のうち絶対値最大の｜cr／akr｜r 列(xr の係数 r 列)
を選ぶ。目的関数の係数 cj に負の係数がない場合は、絶対値最小の｜cr／akr｜(ただし、akj<0)の r 列を選ぶ。つ
ピボット操作を行う。同様の操作を常数項 bi に負が無くなるまで反復する。
まり、k 行 r 列の akr をピボットとし、
bk<0 が存在するにもかかわらず、akj≧0(非負)である場合、問題の制約条件式が矛盾している。⑥負の目的関数
の係数 cj(<0)のうち絶対値最大の｜cr｜(xr の係数 r 列)を選ぶ。cr と同列の各制約条件式の正の係数 air のうち最
小の bk/akr の k 行を選ぶ。つまり、k 行 r 列の akr をピボットとし、ピボット操作を行う。同様の操作を目的関数
の係数 cj に負が無くなるまで反復する。Cr<0 が存在するにもかかわらず、air≦0（非正）である場合、xr→∞、Z
→∞（－∞）となる。
3. 提案 simplex 法の検証
3.1 一般化検証問題 10 問の提案
提案する simplex 法の検証のため、以下の 10 問の simplex 問題を作成した。①全ての制約条件式が逆順の場合
での最小化問題、②全ての制約条件式が逆順の場合での最大化問題（無限大解）
、③全ての制約条件式が正順での
最大化問題、④全ての制約条件式が正順での最小化問題、⑤制約条件式が正順と逆順混合の最大化問題、⑥制約
条件式が正順と逆順混合の最小化問題、⑦制約条件式が正順と逆順混合の最大化問題（複数解、平行）
、⑧制約条
件式が等式（1 つ）と逆順混合の最大化問題、⑨制約条件式が等式（2 つ）と逆順混合の最大化問題、⑩制約条件
式が矛盾する最大化問題である。
3.2 検証事例
表 1. 正順と逆順混合の最大化問題
提案した検証問題 10 問の解を、図解法、2 段階単体法、提案する方法の
max
3 通りで求めた。ここでは、検証として、表 1 に示すように、事例⑤の制
s.t.
約条件式が正順と逆順混合の最大化問題の 2 段階単体法と提案法を示す。
3.2.1 2 段階単体法
表 2 に 7 ステップの 2 段階単体法の解析手順を示す。
設計変数 x1，x2 以外、スラック変数 x3，x4，x5，x6 およ
び人工変数 x7，x8 の合計 8 変数である。
2 段階単体法の第一段階は、人工変数 x7，x8 の和の-1
倍を最大化する実行可能解探索問題である。手順は最小
化手法である。ステップ 1 では、まず、x7 の列、1 つ目
の逆順の制約条件式の係数 1 をピボットしてピボット操
作となる。ステップ 2 では、x8 の列と 2 つ目の逆順の制
約条件式の係数 1 をピボットしてピボット操作となる。
ステップ 3 では、目的関数の負の係数の絶対値最大の-4
x1
-2
x1
0.333333
0.5
1.2
3.5
x2
1
x2
1
1
1
1
b
5
3
6
7
≦
≧
≦
≧
表 2. 2 段階単体法
ｘ1
0
0.333333
0.5
1.2
3.5
x2
0
1
1
1
1
x3
0
1
ｘ1
-0.5
0.333333
0.5
1.2
3.5
ｘ1
-4
0.333333
0.5
1.2
3.5
x2
-1
1
1
1
1
x2
-2
1
1
1
1
x3
0
1
ｘ1
0
0
0
0
1
x2
0
0
1
0
0
（x1 の列）とθi=bi/ >0 の最小値行の係数 a51=3.5 をピボットしてピ
ボット操作となる。ステップ 4 では、目的関数に負係数がないので
第一段階終了である。x7=0，x8=0 であり、実行可能基底解 x1=4/3，
x2=7/3，x3=20/9，x5=31/15 が得られた。
このステップ 3，4 の操作及び判定を、一般に単体法という。
第二段階は、最適解の探索問題である。ステップ 5、つまり第二
段階のステップ 1 の表は、第一段階終了のステップ 4 の表から x7 と
x8 の列を除き、目的関数は表 1 の最大化問題となる。ステップ 5，6，
x4
0
x5
0
x6
0
-1
x7
1
x8
1
1
1
-1
x4
1
x5
0
x6
0
1
1
b
-3
5
3
6
7
b
-10
5
3
6
7
x3
0
1
0
0
0
x4
0
1.055556
-1.16667
0.766667
0.333333
x5
0
0
0
1
0
x6
0
-0.05556
0.166667
0.233333
-0.33333
x7
1
-1.05556
1.166667
-0.76667
-0.33333
x8
1
0.055556
-0.16667
-0.23333
0.333333
b
0
2.222222
2.333333
2.066667
1.333333
ｘ1
2
0
0
0
1
x2
-1
0
1
0
0
x3
0
1
0
0
0
x4
0
1.055556
-1.16667
0.766667
0.333333
x5
0
0
0
1
0
x6
0
-0.05556
0.166667
0.233333
-0.33333
b
0
2.222222
2.333333
2.066667
1.333333
ｘ1
2
0
0
0
1
x2
0
0
1
0
0
x3
0
1
0
0
0
x4
-1.16667
1.055556
-1.16667
0.766667
0.333333
x5
0
0
0
1
0
x6
0.166667
-0.05556
0.166667
0.233333
-0.33333
b
2.333333
2.222222
2.333333
2.066667
1.333333
ｘ1
2
0
0
0
1
x2
0
0
1
0
0
x3
1.105263
0.947368
1.105263
-0.72632
-0.31579
x4
0
1
0
0
0
x5
0
0
0
1
0
x6
0.105263
-0.05263
0.105263
0.273684
-0.31579
b
4.789474
2.105263
4.789474
0.452632
0.631579
-1
x7
0
x8
1
b
5
3
6
7
1
1
x3
0
1
x4
1
x5
0
-1
x6
1
-1
x7
0
1
x8
0
1
1
-1
7 つまり第二段階のステップ 1，2，3 の操作及び判定は単体法である。説明は省略する。得られた結果は、
x1=19/12=0.6316，x2=91/19=4.7895，x3=0，x4=2.1053，x5=0.4526，x6=0，z=67/19=4.7895 である。
3.2.2 提案 simplex 法
表 3 に 3 ステップの提案 simplex 法の解析手順を示す。
設計変数 x1，
x2 以外、スラック変数 x3，x4，x5，x6 の合計 6 変数である。ステップ 1
の表は、表１の目的関数の係数に-1 を掛ける。また、逆順の制約条件
式に-1 を掛けて正順型とし、スラック変数を加えて等式としている。
常数項 bi に負（-3，-7）があるので、絶対値最大の-7 の 5 行目（制約
条件式）を選択する。負の係数 a5j（-3.5，-1）と対応する目的関数の
負の係数-1（x2 の列）があり、5 行 2 列目の a52=-1 をピボットして
ピボット操作となる。ステップ 2 の表では、常数項 bi に負（-2，-1）
表 3.
提案 simplex 法
x1
2
0.33333
-0.5
1.2
-3.5
x2
-1
1
-1
1
-1
x3
0
1
0
0
0
x4
0
0
1
0
0
x5
0
0
0
1
0
x６
0
0
0
0
1
定数
0
5
-3
6
-7
x1
5.5
-3.16667
3
-2.3
3.5
x2
0
0
0
0
1
x3
0
1
0
0
0
x4
0
0
1
0
0
x5
0
0
0
1
0
x６
-1
1
-1
1
-1
定数
7
-2
4
-1
7
x1
0
1
0
0
0
x2
0
0
0
0
1
x3
1.73684
-0.31579
0.94737
-0.72632
1.10526
x4
0
0
1
0
0
x5
0
0
0
1
0
x６
0.73684
-0.31579
-0.05263
0.27368
0.10526
定数
3.52632
0.63158
2.10526
0.45263
4.78947
があるので絶対値最大の-2 の 2 行目を選択する。2 行目の負の係数は a21（-3.16667）のみであり、この 2 行 1 列
の a21=-3.16667 をピボットしてピボット操作となる。ステップ 3 の表では、常数項 bi に負の項が無く、目的関数
の係数にも負の項がないので最適解が得られている。結果は、2 段階単体法と同じである。
4. まとめ
本報告では、実数型シンプレックス法の効率的な解き方を提案した。正順以外に逆順や等式の制約条件式の混合
問題の最適解の探索、制約条件式群に矛盾がある場合の判別、有界あるいは非有界の判別が可能であり、操作手
順は単純かつ効率的である。検証問題 10 問を提案し、図解法及び 2 段階単体法と比較・検証した。
5．参考文献
1)線形計画法，平本巌、長谷彰，培風館

Download Report