実数型 Simplex 法の解き方の単純化（効率化）に関する研究

土木学会第69回年次学術講演会(平成26年9月)
Ⅳ-133
実数型 Simplex 法の解き方の単純化（効率化）に関する研究
高知高専
正会員
○竹内光生
四国旅客鉄道（株）
非会員
古味
良
（株）大林組
非会員
庄野
真
１．はじめに
線形計画法は、線形計画問題や非線形計画問題、整数線形計画問題などの基礎として、オペレーションズ・
リサーチ、システム工学、経営工学、管理工学などのさまざまな分野において広く適用されている。
しかし、正順（原点側が実行可能解）以外に、逆順（原点と反対側が実行可能解）や等式の制約条件式が含
まれる場合は、人工変数（技巧変数）を追加、また 2 段階単体法と呼ばれる理解しがたい解法が線形計画法の
基礎とされる。本報告は、simplex 法の単純化（効率化）の提案と検証を課題としている。
２． 最小化手法を前提とする Simplex 法の解法の単純化の概要
２．１
正順の制約条件式について
正順のみの制約条件式の線形計画問題の場合は、原点側が制約条件式を満足する側である。したがって、正
のスラック（余裕）変数を追加して、原点が初期の実行可能解である等式とし、一般に単体法と呼ばれる解法
の手順となる。変更はない。つまり、目的関数の係数 cj 行に着目して、負の係数がなければ最適解であり、
負の係数があれば、負の係数の絶対値最大|cr|の r 列を選択する。その選択した r 列の正の係数 air と定数項
bi（正）の比θi（＝定数項 bi／正の係数 air）の最小値θk の k 行を選択する。その k 行 r 列の係数 akr をピボ
ットとするピボット操作によって改良解が得られる。以下、最適解が得られるまで反復する。なお、目的関数
の係数に負の係数 cr があるにも関わらず、その r 列の係数 air がすべて非正である場合は無限大解となる。本
研究も目的関数の負の係数を選択する最小化手法を想定している。
２．２
等式の制約条件式について
等式の制約条件式は、その等式上に解があり、その等式の 0 以外の係数を順次選択してピボット操作すれば、
その等式を満足する改良解が得られるとした。従って、等式の制約条件式に人工変数を追加しない。また、等
式の制約条件式は、正順と逆順の 2 つの制約条件式に置き換えるべきでないとした。つまり、等式の制約条件
式は、スラック変数や人工変数を追加しないで、目的関数の係数の非負（目的関数の増加）とは無関係に、逆
順や正順の制約条件式よりも優先的に、正順の場合のように、列、行の順にピボットを選択するのではなく、
行、列の順にピボットを選択し、すべての等式の制約条件式のピボット操作をする必要があるとした。
２．３
逆順の制約条件式について
逆順の制約条件式は、原点と反対側が満足領域である。従って、目的関数の係数の非負（目的関数の増加）
とは無関係に考慮（ピボット選択）しなければならない。しかし、有効な逆順の制約条件式のみ考慮すればよ
い。その選択手順は、正順の制約条件式については、列、行の順であったが、逆順の制約条件式は、等式の制
約条件式と同様に、行、列の順でピボットを選択することになる。正順の制約条件式の場合、最初の列の選択
において、目的関数の負の係数の絶対値最大|cr|の r 列を選択した。逆順の制約条件式の場合、行、列の順で
選択するとして、最初の行の選択において、aij xj≧bi（aij≒1 と仮定）の最大値 bk の k 行目の制約条件式を
選択すれば、他の逆順の制約条件を、順次、満足すると仮定した。続く列の選択においては、目的関数の負の
係数 cj があれば、先に選択した k 行目の制約条件式の係数 akj との比の絶対値最大|cr／akr|の r 列を選択する。
目的関数の係数 cj に負の係数がない場合は、絶対値最小の｜cr／akr｜の r 列を選ぶとした。
２．４
スラック変数の追加および等式、逆順、正順のピボット選択手順について
まず、①逆順の制約条件式に-1 を掛けて、正順の制約条件式型とする。このとき、逆順の制約条件式の定
数項のみ負の値となっていると想定している。②次に、等式の制約条件式以外の制約条件式にスラック変数を
キーワード
実数型 simplex 法、正順・逆順・等式混合問題、単純化、効率化
連絡先
〒783-8508
高知県南国市物部 200-1
環境都市デザイン（旧建設）工学科
-265-
竹内光生
ＴＥＬ088-864-5587
土木学会第69回年次学術講演会(平成26年9月)
Ⅳ-133
追加して、すべての制約条件式を等式型とする。③まず、等式の制約条件式があれば、2.2 で示したように、
すべての等式の制約条件式を選択しピボット操作をする。④次に、定数項 bi が負の値となっている制約条件
式（逆順の制約条件式）があれば、2.3 で示したように、行、列の順でピボットを選択し、ピボット操作をす
る。なお、行の選択において、逆順の制約条件式の定数項を負としているので、絶対値最大値|bk|の k 行目の
制約条件式を選択する。また、列の選択において、2.3 における係数 akj は負の係数のみ有効である。もし、
定数項が負の制約条件式があるにも関わらず、その制約条件式の係数 akj がすべて非負であれば、xj≦bk／akj
（負）を示し、制約条件式が矛盾していることになる。定数項が負の値の制約条件式が無くなるまで反復する。
⑤最後に、2.1 で示したように、目的関数に負の係数があれば、一般に単体法と呼ばれる解法の手順となる。
３． 検証事例
３．１
表 1.
全ての制約条件式が逆順の最小化問題
min
表 1 に、全ての制約条件式が逆順の最小化問題を示している。表 2 に、本
s.t.
報告が提案する単純化した simplex 法を、三段階で示している。各段階の 1
行目に目的関数、2,3,4 行目に表 1 の 3 つの制約条件式を順に示している。
一段階目においては、まず、2.4 の①と②によって、
すべての制約条件式を等式とする。ピボット選択として、
③は省略し、④によって、定数項の min{-2,-5,-1}=-5
より 2 つ目（3 行目）の制約条件式および max{1/-2,1/-1}
=1/-2 より設計変数 x1 の係数-2 を選択する。ピボット操
作結果が二段階目である。二段階目において、min{-0.75}
より 1 つ目（2 行目）の制約条件式および max{0.5/-0.75,
0.5/-0.25}=0.5/-0.75 より設計変数 x1 の係数-0.75 を選
択する。ピボット操作結果が三段階目である。三段階目
においては、負の定数項はなく、2.4 の⑤に移り、目的
表 2.
x1
1
-0.5
-2
-1
x1
0
0
1
0
x1
0
0
1
0
逆順・最小化問題
x1
1
x1
0.5
2
1
x2
1
x2
1
1
≧
≧
≧
2
5
1
表 1 の問題の単純化 simplex 法
x2
1
-1
-1
0
x2
0.5
-0.75
0.5
0.5
x2
0
1
0
0
x3
0
1
0
0
x3
0
1
0
0
x3
0.6667
-1.3333
0.6667
0.6667
x4
0
0
1
0
x4
0.5
-0.25
-0.5
-0.5
x4
0.3333
0.3333
-0.6667
-0.6667
x5
0
0
0
1
x5
0
0
0
1
x5
0
0
0
1
定数
0
-2
-5
-1
定数
-2.5
-0.75
2.5
1.5
定数
-3
1
2
1
関数の係数に負がないので、x1=2,x2=1,x3=0,x4=0,x5=1,z=3 の最適解が得られている。
３．２
制約条件式が矛盾する正順・逆順混合最小化問題
表 3.
正順・逆順混合矛盾問題
表 3 に、2.4 の④の全ての制約条件式を満足する実行可能領域の存在しない
min
事例として、正順・逆順混合最小化問題を示している。表 4 に、本報告が提
案する単純化した simplex 法を、三段階で示している。一段階目においては、
2.4 の①と②によって、すべての制約条件式を等式とする。ピボット選択とし
て、③は省略し、④によって、定数項の min{-1,-5}=-5
より 3 つ目（4 行目）の制約条件式および max{-1/-1}よ
り設計変数 x2 の係数-1 を選択する。ピボット操作結果
が二段階目である。二段階目においては、min{-3}より 2
つ目の制約条件式および max{4.5/-2.1}より設計変数 x1
の係数-2.1 を選択する。ピボット操作結果が三段階目で
ある。三段階目においては、負の定数項{-0.2857}がある
にも関わらず、その行の係数が全て非負であるので、実
行可能領域は存在しないこととなる。
４． まとめ
表 4.
x1
2
0.5
0.4
-2.5
x1
4.5
3
-2.1
2.5
x1
0
0
1
0
s.t.
x1
2
x1
-0.5
0.4
2.5
x2
-1
x2
1
1
1
≧
≦
≧
1
2
5
表 3 の問題の単純化 simplex 法
x2
-1
-1
1
-1
x2
0
0
0
1
x2
0
0
0
1
x3
0
1
0
0
x3
0
1
0
0
x3
0
1
0
0
x4
0
0
1
0
x4
0
0
1
0
x4
2.1429
1.4286
-0.4762
1.1905
x5
0
0
0
1
x5
-1
-1
1
-1
x5
1.1429
0.4286
-0.4762
0.1905
定数
0
-1
2
-5
定数
5
4
-3
5
定数
-1.4286
-0.2857
1.4286
1.4286
実数型 Simplex 法の解法の単純化を提案し、その概要と検証事例を示した。人工変数（技巧変数）を追加せ
ずに、等式、逆順、正順の順に、制約条件式をピボット選択・操作すればよいとした。従来の実数型 Simplex
法の解法のピボット選択手順とは異なる。単純、効率的である。制約条件式が矛盾する場合の判別も可能であ
る。今後、さらに他の検証問題を用いて、本研究で提案するアルゴリズムの事例検証を重ねる。
-266-