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

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

卒業研究者 古味 良，庄野 真 指 導 教 員 竹内 光生

1. はじめに

線形計画法は、与えられた線形の制約条件の下で、ある一つの線形の目的関数を最大あるいは最小にするもの であり、オペレーションズ・リサーチ、システム工学、経営工学、管理工学などのさまざまな分野において、代 替案の作成手法として広く適用されている。本研究室においても、南海地震に備えた避難施設配置問題の最適配 置手法として、p メディアン探索および線形計画法（混合整数線形計画法）を適用している。

一般に、線形計画問題は、目的関数と制約条件式群のシンプレックス表を、連立方程式解法であるガウス・ジ ョルダンの消去法により求めることができる。しかし、正順（原点側が実行可能解）以外に、逆順（原点と反対 側が実行可能解）や等式の制約条件式が含まれる場合は、人工変数を追加、また 2 段階単体法¹⁾と呼ばれる一般 に理解しがたい解法が、線形計画法の基礎とされる。本報告は、実数型シンプレックス法の効率的な解き方の提 案と検証を課題としている。

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 列を選ぶ。つ まり、k 行 r 列の akrをピボットとし、ピボット操作を行う。同様の操作を常数項 biに負が無くなるまで反復する。

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 つ）と逆順混合の最大化問題、⑩制約条件 式が矛盾する最大化問題である。

ｘ1 x2 x3 x4 x5 x6 x7 x8 b

-4 -2 0 1 0 1 0 0 -10

0.333333 1 1 5

0.5 1 -1 1 3

1.2 1 1 6

3.5 1 -1 1 7

ｘ1 x2 x3 x4 x5 x6 x7 x8 b

0 0 0 0 0 0 1 1

0.333333 1 1 5

0.5 1 -1 1 3

1.2 1 1 6

3.5 1 -1 1 7

ｘ1 x2 x3 x4 x5 x6 x7 x8 b

-0.5 -1 0 1 0 0 0 1 -3

0.333333 1 1 5

0.5 1 -1 1 3

1.2 1 1 6

3.5 1 -1 1 7

ｘ1 x2 x3 x4 x5 x6 x7 x8 b

0 0 0 0 0 0 1 1 0

0 0 1 1.055556 0 -0.05556 -1.05556 0.055556 2.222222

0 1 0 -1.16667 0 0.166667 1.166667 -0.16667 2.333333

0 0 0 0.766667 1 0.233333 -0.76667 -0.23333 2.066667

1 0 0 0.333333 0 -0.33333 -0.33333 0.333333 1.333333

ｘ1 x2 x3 x4 x5 x6 b

2 -1 0 0 0 0 0

0 0 1 1.055556 0 -0.05556 2.222222

0 1 0 -1.16667 0 0.166667 2.333333

0 0 0 0.766667 1 0.233333 2.066667

1 0 0 0.333333 0 -0.33333 1.333333

ｘ1 x2 x3 x4 x5 x6 b

2 0 0 -1.16667 0 0.166667 2.333333

0 0 1 1.055556 0 -0.05556 2.222222

0 1 0 -1.16667 0 0.166667 2.333333

0 0 0 0.766667 1 0.233333 2.066667

1 0 0 0.333333 0 -0.33333 1.333333

ｘ1 x2 x3 x4 x5 x6 b

2 0 1.105263 0 0 0.105263 4.789474

0 0 0.947368 1 0 -0.05263 2.105263

0 1 1.105263 0 0 0.105263 4.789474

0 0 -0.72632 0 1 0.273684 0.452632

1 0 -0.31579 0 0 -0.31579 0.631579

x1 x2 x3 x4 x5 x６ 定数

2 -1 0 0 0 0 0

0.33333 1 1 0 0 0 5

-0.5 -1 0 1 0 0 -3

1.2 1 0 0 1 0 6

-3.5 -1 0 0 0 1 -7

x1 x2 x3 x4 x5 x６ 定数

0 0 1.73684 0 0 0.73684 3.52632

1 0 -0.31579 0 0 -0.31579 0.63158

0 0 0.94737 1 0 -0.05263 2.10526

0 0 -0.72632 0 1 0.27368 0.45263

0 1 1.10526 0 0 0.10526 4.78947

x1 x2 x3 x4 x5 x６ 定数

5.5 0 0 0 0 -1 7

-3.16667 0 1 0 0 1 -2

3 0 0 1 0 -1 4

-2.3 0 0 0 1 1 -1

3.5 1 0 0 0 -1 7

3.2 検証事例 表 1. 正順と逆順混合の最大化問題 提案した検証問題 10 問の解を、図解法、2 段階単体法、提案する方法の

3 通りで求めた。ここでは、検証として、表 1 に示すように、事例⑤の制 約条件式が正順と逆順混合の最大化問題の 2 段階単体法と提案法を示す。

3.2.1 2 段階単体法 表 2. 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の列）とθ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，

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. 提案 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）

があるので絶対値最大の-2 の 2 行目を選択する。2 行目の負の係数は a21（-3.16667）のみであり、この 2 行 1 列 の a21=-3.16667 をピボットしてピボット操作となる。ステップ 3 の表では、常数項 biに負の項が無く、目的関数 の係数にも負の項がないので最適解が得られている。結果は、2 段階単体法と同じである。

4. まとめ

本報告では、実数型シンプレックス法の効率的な解き方を提案した。正順以外に逆順や等式の制約条件式の混合 問題の最適解の探索、制約条件式群に矛盾がある場合の判別、有界あるいは非有界の判別が可能であり、操作手 順は単純かつ効率的である。検証問題 10 問を提案し、図解法及び 2 段階単体法と比較・検証した。

5． 参考文献

1)線形計画法，平本巌、長谷彰，培風館

x1 x2

max -2 1

x1 x2 b

s.t. 0.333333 1 ≦ 5

0.5 1 ≧ 3

1.2 1 ≦ 6

3.5 1 ≧ 7