汎用数理計画ソフトクエア
反町洋一，小田稔周，熊野長次郎
11川11川11川11川11川11川11川1111川11川11川11川11川11川11川11川11川11川11川11川11川11川11川11川11川l川11川11川11川111川11川l川11川11川11川11川11川11川11川11川l川11川11川111川11川11山11川11川11川11川11川11川11川11川11川11川11川11111川11川11川11川11川11川1111川11川11川11川11川11川11川111川111川11川l川l川11川11川11川11川11川11川11川11川11川11川11川11川11川11川11川11川11川11川1111川11川11川11川11川11川11川11川11川111川11川11川11川11川11川11川11川11川11川11川l川111川l日111川11川111川11川11川11川11川l川11川11川11川111川11川11川11川11川11川11川11川11川111川111川11川11川11川11川111川111111川11川11川11川11川11川11川11111川11川11川11川l川11川1111川11川11川11川I川l川1111川11川11川11川11川11川1111川11川11川11川11川11川111川111川l川11川11川11川11川111111l1
.
はじめに
線形計画法で代表される数理計画法の応用が，これま で，産業界でいちじるしく進展できたのは，計算機，特 に大型汎用計算機の技術革新に応じて，新しい汎用数理 計画ソフトウェアがメーカ一等により開発され，産業界 へたえず供給され続けたことであろう.メーカ一等で開 発された数理計画ソフトウェアの共通した特徴は，いず れも 1960年代に IBM社により開発されたMP S;360を 源流としていることであろう.このために，これらのソ そりまち ょういち紛三菱総合研究所* おだ としかね国際電信電話紛研究所村 くまの ちょうじろう 側三菱総合研究所判事*
干 100 千代田区大手町 2-3-6*
*
干 356 埼玉県上福岡市大原 2 ー 1 ー 15 紳* 干 530 大阪市北区堂島 2-2-2 表 1L
P 共通問題含有成分 I
Cu
I
S
i
I
Fe
I
Zn
I
Mn
I
Mg
|下限い .8 1 瓜 8
1
0
.
8
1
1
.
6 1 0 1
0
.
3
4
1 上限 \2.2
¥
11
.
2¥ 0
.
9
¥1.8 10.3 1
0
.
3
5
材料|単価|
含
有
率(%)
X 1
1
275円[1. 4 1 日 1
0
.
7
[
1
.
5
1
0
.
2
[
0
.
8
x 2 [
2
7
5
1υ[
8
.
0
1
0
.
8
1
4
.
5
1
0
.
2
[
0
.
3
X 3
[
2
8
5
[
2
.
5
[
7
.
7
[
0
.
9
[0.9 也三到土竺
X41285¥2.519.5¥0.9[0.9[0.18[0.09
X5[185 [
2
.
5
[
9
.
3
[0.95[ 0
.
9
3
[
0
.
1
8
[
0
.
0
9
X6¥235 ¥
2
.
3
¥8.
4
¥
0
.
8
[
3
.
0
1
0
.
2
1
¥1.4
X7[235 [
2
.
5
[
9
.
0
10.9 [
X8[ ぉo
[
0
.
2
[
0
.
2
1
0
.
5
[
[
0
.
5
[
X 9 [
2
9
0
[
9
8
.
0
[
x 叫刈
[97
[
0
.
5
[
~55
14.
0
[0・ 5
[
0
.
5
J
O.1 [0.5 [0.5
1993 年 3 月号 フトウュアは，基本的な外部仕様および，利用者にとっ て最もニーズの高い入力データについて互換性が保たれ ている.このことから，本稿では汎用数理計画ソフトウ ェアの例として IBM社の MP X;370を，編集者より与 えられた例題を中心に第 2 章で説明をする. 最近の計算機のダウンサイジングの影響は，この分野 でのソフトウェアの利用も，PC
, EWS 等が中心とな っているが，本格的応用をめざした大規模線形計画問題 については，現状では，汎用数理計画ソフトウェアの利 用が必要となろう.第 3 章ではこのような大規模問題の 汎用数理計画ソフトウェアでの取扱いについて述べるこ とにする.2
.
例題による数理計画ソフトウェアの
紹介
例題生産計画問題 LP 共通問題 (r特集にあたって J 参照)に示すように 表 2 数理計画法のソフトウェア 分類 ソフト名 ライブラリーOSLib
,
NAG
,
1MSL
パッケージ MPSX，AMPS.
,FMPS
, NLP・ GRG，WISE
,
FortLP
会話型 L1NDO ，GINO
モデル記述LlNGO ，
XPRESS.MP
,
ASNOP
表計算 EXCEL ，
Wha
t's
B
e
s
t
中間言語 SAS;IML ，
S
,Speakeasy
,APL
,LAMAX-S
その他 SAS;OR ，
Mathematica
(5)
1
1
3
11 個の使用材料を用いてある製品を作る場合，銅をはじ め 6 種類の成分が表の上下限に入るように使用材料の混 合比率を決めたい.
X
1 は使用材料の混合比率を示す， その場合， X 1 のさらに 1.4%だけの銅を含んでいる.た だし， X :3は 35%にして欲しいとのことである.結果は 実行可能解がない.どの制約をゆるめればよし、か? この例題は，以下のように定式化される. 添字: m... 材料の添字 e …成分の添字 定数:C
m …材料の単価(円) Rm，e…材料m に含まれる成分 e の含有率 (%lLe
…製品に含まれる成分 e の含有率の下線 (%l Ue
…製品に含まれる成分eの含有率の上限 (%l 変数: Xm …製品を構成する材料m の混合比率d…製品に含まれる成分 e の含有率 (%l
ただし，一∞く Y!<+ ∞
Ye …製品に含まれる成分 e の含有率 (%l ただし ， Le;五百e;:;;;Ue ÔYe+ …製品に含まれる成分 e の含有率の上限逸脱 率 (%l ただし ， Ô百e+;;;O ÔYe- …製品に含まれる成分 e の含有率の下限逸脱 率 (%l ただし ，ﾔ
Y
e
-
;
;
;
O
定式化: 線形計画問題の定式化では，特に大規模問題において は，実行不可能にならないように留意すべきであろう. 大規模問題において実行不可能な場合，数理計画法のソ フトウェアは，実行不可能な状態の解を出力するが，こ の理由を解析し対策を講ずるために，分析者は多くの時 間と労力を費すことになる. この例題では ，Ye=
L
:
Rm
,e
Xm の制約を設定した場 m 合， 実行不可能となる場合があり ， Xm が負値と出力さ れる恐れがある.こうなっては対策に窮することになる. このような理由から，ここではあらかじめ，補助変数Y!， δYe+' ôYe- を導入し，実行不可能を防止する
すなわち ， y!=-ôYe-+Ye+ÔYe+' 百!=L: Rmμm
m とし，目的関数に，図 1 に示す罰金関数f(
Y
!
l
=Mc
OYe-+Mc O
Y
e
+
を含めることとする. この凸計画問題は，以下のように線形計画問題に定式1
1
4
(6)y
全yc- Lc Y"図 1 罰金関数 f(Y!l
y,# mz
mc
z m
+
+ e M g q O CM
ヤム】 e+
e N Y CM
Z
e
① る れ .m え』 m レ U ， 4 ・罰金関数 L: f(Y! l+製品単価
e を最小化する . Mc=10000 とする.8.t.
(L:
xm=l ロ1 …混合比率の総和はである.(
Y!-
L:
Rmμm=O
for Vem
…成分 e の含有率 Y! の定義式
④ Y!+δYe--Ye-ÔYe+=O
for VeY! の内訳を示す式
⑤ Le;三百e~玉 Ue forve …成分 e の含有率百e の上下限制約 (xs=0.35
…材料 m= :3の混合比率を 0.35 とする要求 表 1 は，この問題を生成し，汎用線形計画ソフトウェ ア MPS
X/370[1][2] を用いて， 1 BM社の大型計算機 上で解くためのジョブ・ストリームである. 表中の step 1 の問題生成は，筆者らが開発したマトリ グス・ジェネレータ MCC. MG[3] を使用している .M G の文法の詳細がわからずとも，上記の定式化と素直に 対応していることは一目瞭然である. MG はMPS 形式のデータを出力し，次の step 2 では このデータを受けて，MP
S
X/370が最適化を行ない， 解を出力する.MP
S
X/370は，計算機資源を最大限に利用し，有効 な最適化戦略が構築できるように，プロシージャと呼ば れる機能単位を制御言語から呼び出す形式を採用してい る.表 1 で使用しているプロシージャの機能を概説する. CONVERT ・ ..MPS 形式データの入力処理を行な う. SETUP …計算効率を最大化するように計算機資源 オベレーションズ・リ+ーチ © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.表 1
L
P 共通問題を解くための入力データノノ
(
JOB CARD )ノノ'STEP1 EXEC SMG
ノパ1G.SYSIN 00 蝿
5 PPP 5 PPP DATA. MODEL
,
PPP,
DATA'‘
誕圃園田 L1NEAR PROGRAM門1NG --'
-誕
提
提
EX. PRODUCTION PLANNING MATERIAL LIST
,
MSUFIX,
2,
11A3101 02 03 04 05 06
07 随 09 10 豆l ー材料Dl~間併しめシボレリ 1 ト
ENDELE門ENTrr足Fg従信 i
…威令の 3抑制予〉船レリスト
END
MATERIAL
CONST.∞訂.1 市剖FIX ，OPTCD=:1c! 11A5
，，'~ 1t科草líiÍ C汎: COST時
∞釘 |275. 275. 285. 285. 185. 235. 235. 260. 290. 340. 2日 .1END
CO門 POUND CO自主T点E位互旦z色É.Sj!f.:Çさ，_11!?.!!日差迫PTCD=1 ， 6A6 ，刊陪K=CR_MS
CU S1 FE ZN MN MG 1.4 3.3 0.7 1.5 0.2 0.8 2.5 8.0 0.8 4.5 0.2 0.3 2.5 7.7 0.9 0.9 0.18 0.19 2.5 9.5 0.9 0.9 0.18 0.09 RAT10 X01 X02 X03
x
o
<
t
X05 X06 X07 X08 XOヲ X10 X11 2.5 9.3 0.95 0.93 0.18 0.091 A • ~ 2.3 8.4 0.8 3.0 0.211.4 卜ー告者雫 RIIl.e:
CRATIOe.m
.
2.5 9.0 0.9 0.2 0.2 0.5 0..5 98. 。 97.0 0.5 4.0 0.5 0.5 0.1 0.5 0.5E
t
!
D
LO BOUND CONST
,
LOELM,
l,
ESUFIX,
OPTCD:=l,
6A6OF ELM.
1 1. 8二ご盟主 0・ 88 1 ・ 6
0 ・1)
0三百一舎者約機 le:
l
O
E
l
M e El'!DUP BOUND CONST
,
UPELM,
1,
ESUFIX,
OPTCD=1,
6A6OF
EL門. l~.2 11 ・ 2
0.91 ・ 8
0 ・?
0.351--- 令有竿の t恨 Ue:
U
P
E
L
t-'1eEND ENDMODEL
1NST悶JCT. 門OOEL ， PPP ， INSTRUCT10N
門ATR1X
MIN... -1-COST FUNCTION
安叡忠一.;("，.
X
"
"
I
1
:
:
y
#
"
I
1e:γ色
ðY~: Ð'(刊 e ， ð1~:
ﾐYP
e
N ，・ COST ・，・ 10000.0 ・揖叩 DY門・ ESUFIX+・10000.0 ・英 'DYP'ESUF 工X
+
COST 軒 'X'rlSUFlXS.T. -2-TOTAL COMPOUND RAT10 EQ. 1
E ，・ TOTALttR ・，
+
'1. 0 ・誕 'X'MSUF1X,
+
'1.0 ・誕 'RHS'-3- DEFINE SUM OF ELEMENT E
,
・ DEFS帯・ ESUFIX,
一目的関紘①
(罰金聞をE 十製品単価)
ー制約@
(;昆合応挙の総和=f.)
+・1. 0 ・誕 'Yft:・ ESUFIX ーー制約@“
ー CRATI立主3 ・ MSUFIX. 【 ESUFIX) ICR_MS (段、今e の令右孝 d
c
c
c
c
c
c
ー九D?TL;7t332;?F ・ YE'ESUF1X
の主義司、
)
c
+・ 1.0 ・!E 'YjI:'ESUFIX+・ 1.0 ・揖・ DYM'ESUFIX
ーー制約<Ð
c
・1. 0 ・揖 'Y ・ ESUFIX -'1 ・ 0・提唱YP・ E剖FZX
(1fn 内託色示す去1')
C END 1993 年 3 月号 © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.(7)
1
1
5
表 1 (つづき) BOUNO
-5- UPPER LOWER BOUND OF VARIABLE X
LO ，・ Y'ESUF工X
,
LOELM--
-WJ 絢@
/持 UP ，・ Y'ESUF.IX,
UPELf
1
由美- REQUIRE門 ENT LO,
'X03 ・，・ 0.35 ・ UP,
'X03 ・， '0.35 ・ END ENorl00ELt 戒令乙の令宥牢の主τ鰻)
一制約@
(材料 3 の 3掛比季=依り
ノノSTEP2 EXEC MPSXVS ， REGION. 門PSXE=1000K/1刊PSXC.SYSIN DD 提
PROGRA門 INIT工ALZ
刊OVE 【 XDATA ，・ ppp ・】 1
NOVE (XP8N
Ar
'lE,
I ppp I>j
tデル活 向指足
CONVERT ( 'CHECK I
,
'SU問問ARY ・}門OVf(XBOUNO ，・ BNO') -/\"ヤシド
SETUP
NOVE (XOBJ
,
I COST ' )MOVE(XRHS
,
'RHS ・ 3 CRASH PR工門AL SOLUTl
ON EXIT-
.
.
MPSX/370 の制御言語
PEND,___
M 隠れ到のず"-'1~ド‘
ノ鍵,.
ノノl1PS泌E.SYSIN
00OSN時 .STEPl.MG.FT07FOOl ， OISP=OLO
入る中岡 11'" レ
ノノ (主記憶，ファイル)の割付けを行なう. CRASH …実行可能解を素早く求めるための処理を 行なう. (複数アルゴリズムをもっ) PRIMAL …主単体法により最適化を行なう. SÖLUTIÖN'" 計算された基底に対する解を出力 する. 表 1 の入力データの実行により得られた最適解を表 2 に示す. 表 2 LP 共通問題の解(暫定版) SECTION 1 - ROWSNUMBER • ..ROll.. AT ..• ACTIVITY ... SLACK ACTIVlTY LL 10000.00口 00
問目的領D-l
COST22 DYPFE LL 10000.00000
BS 635.68402 635.68402- H~ I 23 DYPI1G LL 1000口 .0000日
TOTAL帯R E町 1.00000 24 DYPMN LL 10000.00日目。
EQ 25 DYPSI Lι 1000日 .00000
DEFS!!S工 E司 26 DYPZN LL 10000.00000
DEFS脅 FE E日 27 X01 BS .17717 275. 口0000 目EFS骨ZN E町 28 X02 BS .14473 275. 日01100 DEFSf./1N EQ 29 X03 EQ .35000 285.00000 DEFS官"白 E由 30 X04 LL 285.00000 COMPY，αJ E日 Z叫 31 X05 BS .24233 185.0000日 CO!.IPYSI E骨 32 X06 BS .04752 235.00口口口 COMPYFE E司 33 X07 LL 235.00000 CO/'lPYZN EQ 34 X08 LL 260.00000 COMPYMN EQ 35 X09 LL 290.0000口 COMPYMG EQ 36 X10 BS .03824 340.00000 37 Xll LL 255.00000 BS 2.20000
SECTION 2 -COLU~lNS
2姐LYym#F1宮
E BS .8'1216BS .3<
,
000YI!IlN BS .18098
NU門BER .COLUMNS AT ...ACTIVITY... ..INPUT COST.. YIISI BS 10.80000
Y!lZN 白雪 1.600目。
LL
.03784
I
10000.000口口 UL 2.20000
16lYI1FE BS 10000.00000 YFE LL .88000
! l '
.
J
17 目YMMG LL 10000.00000F
a
YYYYNSZ11N Z 5 N LL .34000 18 DYr1l'1N LL 10000.000口口 BS .18098 19 口Y!'lS工 LL 10000.00000 LL 10.80000 20 DYI1ZN LL 10000.00000 LL 1.600001
1
6
(8) © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず. オベレーションズ・リサーチ2/6 判35 川4.-9/~~/
0.0 /4.6/ 0.0 /4.0 / 0.0 この結果から ， õye+, õyeーで正の値をとるものを探 せば ， Ys- (F E 成分の合有率の下限逸脱率)のみが， 0.03784 (%)をもつことがわかる.したがって，答は， FE の含有率の下限を 0.04(%) (小数以下 2 桁)ゆるめ ればよい .FE の含有率の下限 Ls を 0.88から 0.84に変更 し，再度表 1 の入力データを実行すれば表 3 に示す解が 得られる. この時の製品単価は， 253.5 円となる. なお， 1 BM社の MPS X/370 と同様に，大型計算機 上で稼動する線形計画ソフトウェアとして，富士通社の AMPS, UNISYS 社の FMPS が挙げられる. これらのソフトウェアは，大規模問題でも効率よく解 くことができる反面，大型計算機上で稼動するため，ユ ーザ・インターフェースが立ち遅れている. 近年， E W S (エンジニアリング・ワークステーショ ン)の性能が飛躍的に向上しており，今後は，図 2 で示 す形態で利用されることが主流となると予想される. ここでは，マトリクス・ジェネレータによるモデルの 構築，制約式の展開りストによるモデルのチェック，最 適化の実行，解のチェックといった基本作業を同期して 進行させることができる. 例題 2:
2 次計画問題 次の 2 次計画問題の最適解を求めよ. / 3.0 1. 0 ー 0.5\ min (x
tI
1.0 2.0 ー 0.4I
x
\-0.5 ー 0.4 1.0 / 、lil--/ -A9h ・ 0 Z Z Z I f l i l -1 t L 一一z
s.t.② -1.3xl ー 1. 2x2 ー1.08X3+ 1.12~日 ③ Xl+X2+X3 ー1. 0=0 ④ Xl 話 0.75， X2 豆 0.75 ， X3 豆 0.75 この問題は，非線形計画法のソフトウェアを用いて解 くことができる.表 4 に，三菱総合研究所で開発したNL
P-GRG[4]を用いて解くための入力データを掲げ る. 表 5 を実行することにより得られた最適解を表 5 に示 す. 一般に，非線形計画法のソフトウェアは，変数の数， iIlIJ約式の数ともに 100 程度以下の小規模問題を対象とし たものが多い. 以下では，大規模 2 次計画問題を線形計画問題にもち 込んで解く方法について述べる. 一般的に 2 次計画問題は以下のように定式化され る. minxtQx
5
.
t
.
Ax=b
l ;;;;， x 主三 u)
噌 i ( 方法 + -0.80000E+00(X06 + 0.10000E+0 1< Y持 FE NUMBER OF ELENENTS : ) + -0.90000E+00(X07 11 q p ｭ 内dm n 帥円I nH 何wd•
•
•
u n v n ' ロ s n t 内d a w n H i l L 来 wmvm EQU向TION : 10 + -0.80000E+00CXOl + -0. 14000E+OICX06 NUMBER OF ELEMENTS : DEFS静MG ) + -0. 30000E +00 (X02 ) + -0.50000E+00(Xl1 8 EQU向TION : 11 + -0.20000E+00(XOl + -0. 21000E+00(X06 NU阿 BER OF ELEMENTS : DEFS持 MN ) + -0.20000E+00(X02 ) + -0.50000E+00(X08 9 EQU日TION : 12 + -0.33000E+Ol(XOl + -0. 84000E+01<X06 + 0.10000E+0 1< Y押 SI NUMBER OF ELEMENTS : DEFS持SI ) + -0.80000E+01<X02 ) + -0. 90000E +01 (X07 ) 11 EQU円 TION : 13 + -0. 15000E+Ol(XOl + -0.30000E+Ol(X06 NUMBER OF ELEMENTS : DEFS持ZN ) + -0.45000E+Ol(X02 ) + -0.10000E+00(Xll 8 12 13 00..66335566067787EE++0033 O O..OOOOOOOOOOOOEE++OOOO 0 0..663355666088EE++0033 O O.. 1h 15 DnYYMMCFUE LBLS 図 2 EWS 上での線形計画法の利用形態 10000.00000 1 日 nn日ー日日目白日 1993 年 3 月号 MODEL.PPP.DAT向e
x
.
Production Planning nHV4 ・= -nυqJvqJvqd ZJP しの oqV14nunuda 守ムハ b 『 vγlβu ・・・・・・ 1&AHH うム p'M 門 nU ハ U ハUnunu--4Ba ・内 Hv nU4 ム nu' 44' ・ VA06000041 -AEJTi 内〈《 4 唱 A4 よ 'A 勺 4 《wv--《MVF ド hM 町内・司・・・・ 《HV 内Hue-AHHUWMmHnHVA 川υA 川》《 HU 《HV 内HV 《 hv 《、 の。 γt 《 UM 円 ハ U ロ B. ，内 d n v R b y H R J V F D Q J V Q J v q d n U 7ra'nxvγ ム MN ・・・・・・ ハ Uukn つ -Fr7 』 1 ・ 4 ， nunU 内 Und 今‘ iv'h ム HHV 向 63GFOS 噌 a 命 nHV 《 UHM 問HHHV ・「 F 』戸、 JV -iβbcJVF2' マ rQυGIVQ リ GJvouqu に J 'FD'uNMm リ内 XU 内 4 「己・--- qノ』ハ HV 内ノ ιMmu' 《JιPF ト 'nHV 《川 υ 内川 V 《HυnHV ハ HvnHV 内川 υ ''T ム nU VAAHEV 八 M 川 'nuγ よ γ ムハ UT ムウ LT1 ・ ?l FIE-eiuRJV 《門令叫ハ U7aphJV つ dAHjnu つ ι Hυ 勺 JHυF 」 nυ7epunT ム--- qunυCJV 「卜 PLV 内4punb 『 VQU7fqJVQuoυQ ゾ nu MmF 仁'' 'ヘノ'』 p 〒 f ムヤ BFAHV ヤ 43 ア lnUTl ハb ハ、 v ・ハ、、 u ponυP3nυMNFhJvnυMN バ汁 RdEJRdR ， v つ JVFb ウム T ム T ム MNT4HUMNnU76MNnUHU-. . . 'lt 』 nUPF トヒ』 lL 作r ‘し UF 己《 P1し lU》内つノ 4ιF 」 F し P し 1 よ今 4 内J 〈ι 勺 ι ぺ?/ζ 』ぺフ /ζ 』ぺつノ ζιnU u 痢辺黒川川 u nu.i 《?/ζ 句=今 ο4.Pb ハb づ〆/，。 υ M川川 .n 村 ν 《Hυ ハ Uv ハHv ハ Hυ 》 w 《 Hv ハHv ハH HHν ハ H 》 νA ハ υx ハ Vλ ハ vλ 川 υY ハ VA 川 VR ハ υY ハ ハ Uγ ム 内ド・ TI M円八円 ハ U 門代 P し 4 日付 AMU ハ unU 4 ・ 4f p ト』 Pト』 ハNUV 《HV ハU ハ U ハ HV ハ HU づ/ハ U 『 re 《ノ ι••
ハ U ハ U-v-6 ・ 4E ) ) 0.5 0.00000 n.03784 (9)
1
1
7
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.表 4
// ( JOB CARD l
//白 RG EXEC FORTXCLG ， REGION.Gロ=512K ， TIME.GO=1
//FORT.SYSIN DD 提
C 園田UADRATIC PR口GRAMMING--ｭ
REAL FUNCTION OBJ誕SI X
,
N )X<N>,X1,X2.X3,Y1,Y2,Y3 REAL'
‘
sc
c
明 =(323Y
OB1= xt~ …目的朋鉱
X1 = XI1l X2 = X<Z> X3 = XI3> Y1 3.0終X1 + 1.0終日2 -0.5様X3 Y2 1. 日発X1 + 2. 自発X2 - 0.41fX3 Y3 =-D.5IfX1 -0.4焚X2 <ト 1.01fX3c
ロßJ X1機Y1 + X2lfY2 + X3祷Y3
c
c
RETURN END SUBROUTINE CONST ( G ， X ，阿川} G( 門】， X(NJ,X1,X2,X3 REAL焚8c
c
制約百@"，$の時
制約虫; ~(叫 =p ，∞ 1
\~Sω".)J X1 X<1l X2 XI2l X3 XI3l Gfl) -1.3~X1 -1.21fX2 ・ 1.08鰍草+1.1Z ~2) X1 + X2 + X3 - 1.0 百 (3) X1 - 0.75 GI4l X2 - 0.75 GI5l X3 - 0.75c
RETURN END /誕/ /LKED. ADDLtl00 OD DISP=SHR
,
DSN=NLPGRG. LOAD/ /LKED. SYS:t:N0目録
It!CLUDE A目 DLMODIGRGOI
ENTRY MAIN
c
..t 数の紋 3 '制約;t;骨抜 5一洞期解11'吹行不可能1):~婚令:可能負手 E 卒、め~~J'fを
仔う rュめ岬 Iマラ F ・7 指定一 等苛制約 tEo.) ，不等号制絢(1..町の椅乞 . .，，('制孟 0 ， 11<':幻 =0 ， 13(~) ー・ ~s(:d.) 豆? LE) <EQ) (/.1,) /梼 //GO.SYSIN 00 誕 &PARM XN XM XFEAS &END 訴CONST S EqEEE L P E -L -L -L 3,
5,
1,
可-a 内'』 '3A 抽YE3 0.0 0.0 0.0 司-a 句ι's 製 INIT ..;lI: :::ID 主祁潮時 1・守 1 /鍵 // 表 5•
' a MM 刊 ー 内u o ‘ 『h a,
U 円 I T i n r 内 υ * a ' N -A n u N N n U H U T-内U Tsch ・ 晶見 M 河川 qu nn ・ 5n n U H H F r N H I A n n 削内 Fu n u n u TARn ' a n r H U ' i u n r AU‘
L "、“細川 V•
-F.
.
.
-0.15510 5 0.02 (SEC)1
....-最畠餅ヨE のイ芭
-0.49976 4 -景，1、目的関数値L 0.3百可百百 -0. 5951~ NUMBER Of 1TERAT10NS 15 2FI~AL OBJECTIVE VALUE5 15 ~ヨ
f Ul~且五三日 F V AR T¥I¥I.ES ARF
1_1___0 • 1 54 8 6 0 • 25 JI24
I 河口 ICIES OF BD 日 f~G CO~5THAI~TS ARE
FI~AL VALUES OF CO~STR\I'TS ARE
-2.~0983E"02 1.90"26E-08
Ff可 JL VAL~ES Of GRAOfE¥T ARE
0.83175 n.B3~75
~L 可日 ER Of OBJECTIVE FU~CTIO~ CALL5 [5
0.8:) .175
1
11
オベレーションズ・ H サーチ
対称行列 Q を変形コレスキー (root
f
r
e
e
cholesky)
分解し ， Q=UtDU を得る.ただし ， U は上半三角行列， D は対角行列である.ペパ)
y=Ux とすれば，問題(1)は以下のように書き換えるこ とができる.min
y
t
Dy=
'L.dj
Yi
S.t.y-Ux=o
Ax=b
(
2
)
ptQP=A
A= /
3
.
7
6
4
3
0¥
1.3
9
2
4
¥o
0
.
8
4
3
2
8
/
P =
/
0.82513 ー 0.553080
.
5
1
8
5
2
0
.
8
2
2
3
6
¥
-0. 2
2
4
2
8
-0.13354
0.11519\ と求まる.0
.
2
3
4
2
3
I
0
.
9
6
5
3
3
/
目的関数が Qx= 'L.À.jYi. j 4 3 2 1;五 S 主~U X=PYYi2を図 3 のように折 Vdi~ 0 の時は，凸計画問題となり ， Yi を図 3 のよう れ線近似を行なかすなわち， に折れ線近似し，線形計画法で解くことにより最小解が 約 =Y/-Yj- ， Yj+ 主主 0 ， 得られる. 方法 2 対称行列 Q の閤有値んと固有ベクトル Pj を求める.A=
(À., 0\ P=(P， …Pn) とすれば，¥
o
.ﾀn/ P は直交行列であり ，pt
QP=A が成立する.x=Py とすれば ，
xt
Qx=yt pt QPy=yt
Ay= ん官，2+え2Y22+...+ ん Yn2 が得られる. m À.，~À.ú~ … ~À.m~ À. m+'~"'~ À. n~O とし， 'L.À.j~tr
Q
j=' m の場合， xtQx 竺'L.ﾀ.j Yi と近似できる .Yj=Pi
x よ j=lり ，
y'=(y
,...ym)t
, P'=(P， … Pm) とすれば .y'=P'tx
となり，問題(1)は以下のように近似することができる.
ηz
min
y'tA'y'=
'L.ﾀ.jYi
1='
s
.
t
.
y'_P't
x= θAx=b
(
3
)
1;五 s 孟 u Q が相関行列の場合，ん…ん ， P，...， Pmは主成分分析 を行なうことにより得られる. Qが大規模の場合， m は n と比較してきわめて少なく てすむ. この他，目的関数が分散を与え，サンプル数が変量の 数よりいちじるしく少ない場合は，投資分析における今 野氏の方法日]のように省計算時開化された巧妙な方法 がある. 以下では，例題 2 を方法 2 で解くことを試みる. Q をヤコピ (Jacob i)の方法で，固有値分解する. 1993 年 3 月号Yj- 孟 o
(
4
)
図 3 f(y)=がの折れ
げ =psf O 副sf 豆 iì.j線近似
s=l ， … ， S ー 1 0:三 Yãi'" (5)Yj-=
'L.y
.
j
-
0;五百.j- 三三 iì.j s=l ， … ， S ー l 0:三百;j- (6) Yl 竺 Zj= 'L. C.jys/ 十'L.C
.
j
Y
S
j
-
(
7
)
ただし C.j = {(Y~-l+i.j
)2_Y:-=tl/δ.j=2y~_ ，+isj
Ys旬 =Y:- ， 十九j(Y♂ =0)
fors= 1
, ...,
S
であり，折れ線区間の傾きを表わす.
C.j<C
s
+
1
j
以上の準備の後，例題2は表 B に示すように，線形計 画問題として定式化される. この解は， {1JJ題 2 の近似解であり，解の精度は分割 s の取り方に依存する.表 B の問題は，伊j題 1 と同様にMP
S
X/370を用いて解くことができるが，分割 s を改訂 しながら近似の精度を高める必要があるため，より簡便 に EWS 上で利用可能な線形計画ソフトウェア WIS E
[
3
J
[6J を用いて解いた.W I
SE はブロック構造をもっ 大規模問題を解くために， KDD 研究所と三菱総合研究 所で共同開発した内点法のソフトウェアである.表 7 に その実行ログと計算結果を示す. この時 ，y=(O.I
,0.0
, 0.67546)t となる. 解の精度 を高めるため，この付近の分割を細かくし，再計算を行 なった結果を表 8 に掲げる. この結果，y=(0.12
,0.04
, 0.65430)t となる. さら にこの付近を細分化した結果を表 9 に掲げる. この結果，目的関数の変化が十分小さくなったので， (11)1
1
9
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.1
2
0
(12
)
表 8 例題 2 の LP モデル生成のための入力データ DATA. MODEL ， ωADßA， DATA 牟---QuadraticProgra阻ing-- -min. x'Vx V: non-negative definite, ど: transJlOsed x / c4 s.t. Ax=b 1<
x
<
u
章一 Approximateby Convex Separableprograming 一! 傘 L: eigen values (non-negative diagonal matrix) I P: eigen vectors(ortro脚1almatrix) • x = Py, xVx = (py)' V (Py) = y'・ {P'VP)y = y' Ly Approxi圃ateas follol's./
+
/
/
/
/
c31
f
/
/
/
/
• Z = y'y ー> y = y+ -y-(y+>
0, y->日) I/
傘•
傘 y+= y+(1)+ •.• + y+ (S)‘
y-= Y-{
I
)
+." + y-(s)c
2
1
/
z = clザ+(1)+ ••• + cs+y+(s) Icl / + cl事y-(1} +…キ CS*y-(s) I /* then, ( cl<
•..
<
cs ) キ/ー+ーー←一一→一>y+ y+(1), . . . y+ (s-1), y+ (s) キ min. e' Lz ( e = (1,..., 1)' ) s. t. z -cl+y+(1) - -cs.y争 (s) -cl+y-(1) -... -cs*y-(s} = 0 * y+ -y+ (1)ー..， -y+{s)=日 y--y-(1)ー... -y-(s) = 0 y-ytty-=O x -Py=日 Ax= b 。く y.(s) く us(s) 日<y-(s)<
us(s) 1<
x く u ---VARIABLE'
^
SECTION -- -VAR.X .!JSLJ<.SUFIX. 1, 3A2 SUFFIX.1
1
2 3 1 END RESTR I CT1.'∞NSTL REST1.1. XSUFIX. OPTCD=I.3A9 COEFF. 11.3 1.2 1.081 END VAL X UPC側幻'. XUP. 1. X剖 FI X. 0門CD= 1.3A9 10.75 0.75 日 75 1 END --VARIABLE Y SECTION -- -VAR.Y .LlST,
V.
SUFIX,1.
3A2 SUFFIX.1
1
2 3 1ーを叡%の 5桑手 4 の~，.本〉ν ・リスト
一抑制①の H:拡;RESTI .
.
-
-
tf交じの主fl.ii! ;XUP.;一者数守 (l 来字 i IT} 手ア木iぃリスト
EIGEN ∞NST. EG#VAL.1.YSUFI丸旦凹CD=1.3A9川ES I品;64313ma 叩副
ー仔列 Q の財 il 勺 :E射VAl・J
EIGEN ..!;ONST.EωVEC. 2. YSUFllt XSUFJX. OPTCD=
1
.
3A9 VECTO郎作 Y2 Y3--1 lx1x2l卜0.5即日幻m
0m且剛 乱捌附
2幻236祁6 O.口2幻3位
U川山山凶間111悶即51 x3 1-0.2幻24位28 一4日.1口3354 0.9鋪65閃33 END --VARIABLE Y (S)SEロ ION---一困布川トル Þ'i
:
E合唱1J"Ec，j t
SUBDIVIDE LIST. SUBDIV.1.16A2剖FIX
I百 3 4 百-rs'ù !L.~工旦]一削線1r.!~氏の 4潮岬 ~~~oð の
日E澗!日
日ポ，レ・リス卜
VAL.. Y(S)CON~YS~P，_L~切盟主j]旺I丸町:CD=1.16M. 側聞飢路一一一 UP I Y 1 I O. 1 O. 1 O. 1 O. 1 O. 1 O. 1 O. 1 O. 1 O. 1 O. 1 O. 2 O. Z O. 2 O. 2 O. Z I I~ 川 1O. 1 O. 1 O. 1 O. 1 O. 1 O. 1 O. 1 O. 1 O. 1 O. 2 O. 2 O. 2 O. 2 O.2 トーい州幅 f..ì
げ 31 O. 1 O. 1 O. 1 01 O. 1 O. 1 O. 1 01 O. 1 O. 1 O. 2 O. 2 O. 2 O. 2 O.2 I VI END 一一一一 '(SUPAiAPPROX. CONST, C明JADRA，2, SUBDIV. YSUFIX, OPTCD=3 COEFF. CQUADﾟA = QUADﾟA(SUBDIV. YSUP)
ENﾐ
EN鵬侃L
-
-
~~IE 向の i~互主 Cllj:
CQUA
f
>
RAsi
(ユイ:"1網拡〉
オベレーションズ・リザーチ
表 B {つづき) 1 NSTRUCT.MODEL，切ADRA，1 NSTRUCTI ON MATRIX MIN... ート COST FUNCTION N , 'COST'，印刷い 'Z' YSUFlX 一日間鳩敬 Zλ ‘ l ， S.T, -2・ QUAD陥TICPART APPROXlMATiN' --.._, -
i
,., ~~ E, 'ωIADZ' YSUF IX, & + '1.0・·'Z'YSUFIXιZ-
C切ADRA ド YP'
SUBDIV, YSUFIX ---l~ IJ 定義が
:
-CQUADRA 傘 'YM'SUBDIV, YSUfIXυ
I
r
,=
1
3
C. ・￥十 1
、 -3司 DEFINE'YP' YSUFIX {"
4
-"
"
.
.
.
.
.
;tAj ¥E. 'DE
f
Y
P
'
YSUF IX,
\ tZ
:
CAj '1;' ノ a+・1.O'• • YP'YSUFIX __ _
., .•
"・1. 0・ドYP' SUBDI川SUFIX 一苦手じ '/.i 岬周係式 a -4司 DEFINE'YM'YSUFIX
E
-
:
-
'ï;ËmTysÜFÎ
X",
(
'
I
i
=
~ ~ザ)
+ '1.0・ド YM'y，別F1X ~ ..-.-・1. 0・ド YぽSUBDIV，
YSUFIX ---'
t
d !:~ザの胡f忠商 a
t-E円lLト551;j(1f= 手 :f.'f)
+ '1.0'• 'Y'YSUfIX ー- 品、ピ 1;.~;-岬府保I -・1. 0・· 'YP'YSUFIX + '1. 0・中 'm-YSUFIX +T
-6-_DEF，I~~_'X' l<SUFIX .", 'uv'.n (~i
=
'
I
i
-
~i)E, 'DEFX' XSUFIX, + '1.0・· 'X'XSUFIX -EG#VEC• 'Y' YSUFIX -7-RESTRICTJON 1 G, 'RESTR!' + REST1 ｷ 'X' XSUF IX, + '1. 12・牟， RIlS・ -8-RESTRICTION 2 E , 'RESTR2', + '1.0・傘 'X'XSUFIX, + '1.0'• 'RIIS' 悶JNO
十 UPPER
BOUNO OFSUBDIVIOED 附IJABLES
十uU
144
>UP, 'YP'SUBDIY, YSUFIX I Y印刷， YSUP ___ 0 ~ Y.
l
' 壬ゐ UP, 'YM'SUBDIV. YSUFIX I YSUP.MS,YSUP叩-UPPER 剛HDOFUMBLE XO 付Aj á 匂
LO, 'Y' YSUFIX "一 100 ・ UP， γYSUFIXJlot- 一- -fvf 重 l，・言門(刈的丈) UP, 'X' XSUFIX,XUP EN助的 DEL 表 7 例題 2 を解くための WIS
E の実行ログと計 算結果 ‘， .e ・ i・・・・‘. eea--e ・ e ・ -e *,
‘
H r a H + a t ｭ ' k i ' eahι 守 傘 )as-H 国間四回帥 H" は chhMH ' r e -m 限切削 H 日 m --wAija ・ 4'Sr ・ ' " t e l ｭ -l n r l ｭ eiod' 争 ' e o f A i ｭ -' d n F { -r e e o I l ｭ -c r e ，ぃ O グ MYO ' g i b b ' e n r I . e l e n -H 聞川日 dH 'aIfr 牟 -raa ・ 4 ' g d -e -H m m M t H e F H U D ｭ -E2 ・'
r
ｭ
-a
--E ・,
n-a'1 ・'
L
ｭ
••
.•
••
・・・ A'ee -a ' e -Enter too naae of da1a : or2 白 In凹t 即del>
>
{:{血，t凹 tsolution>
>
{:{ AlgoriU.. > > tti)gl block structure>
>
公Con trol 阿 r...， ter >>
1，~:(~1:t. lt. 側・緋， 。r2 J..干の碕金桶事支えi.j兎用 solulÏ叩 ーム 2D_search by Iri, Jlll瀛 & Yalllashita Sparse (aini1l¥.11Iegree) PINF 0.1日目E+11 XTOLV 0.100E-03 XTOLV2 0.1 日目E-14 XTOLPV O. 100E-09 XTOLRL 0.1日日E-07 XG紬刷 0.990E+00 XBZ ・ 0.100E・02 SAVE RESTOR 陪V1SE 日 Are you.11right1?(y/n) : y NO胃 DATA lN阿TPROCESS .
NO・ DATA S1附C官JREDESIGNIN¥i .. .
NOIi九闘t• A(t)_".tPR∞ESS .. . NOIiINITIAL SOLUTlON CALCPR∞ESS ..' 1993 年 3 月号 - ::lL
=
P
'
i
I
a
a
一ー制約@ & & ---剥拘@a
a
X. さ D‘ 75"' 表 7 (つづき) .m臥Tl ONSTART• mmmmmmm 川 mmmmm 叩 mmmmmmmm l・ -'ee ， +4l'++ 一 -44'i'l ， ++ATI'l' A E E E E E E E E E E E E E E E E E E E E E E T 7 2 9 8 0 0 6 4 5 2 8 0 5 4 5 0 1 0 2 2 0 8 E43128E450929qO43 日 508 日日 B 4 5 3 9 5 3 9 7 3 8 0 5 7 6 9 9 8 9 3 2 8 7 6752425192265573747E56 a 且 ttao 且 ooaaa 日札止 oto 且 oanu 8121220121112222222222222 1 。 11000008000000 日 00000 日日日 O A--一 ++'AT++ 』守 A' ・ e+a ， a-+94 』守 a'AT&T++ HEEEEEEEEEEEEEEEEEEEEEEEEE F9B36B15902218795222777753 LBE09523379540549507444443 A35191 日 793216808n34100000 日日 1225116212752121111111111 a 日 BE 日 000000oto 日 otoEOE00 凪日 一一一一 T10422222111000 日日日日日日日日日日目 S1100 日日日日日日日日日日日日日日日日日日日目目 。 ++64+4a'a ，‘ ++4+++ 令 ++6++aTAT-' nuELELEIHEb 智 luEhFMFUFUELRtFbELELELE し ELF 」 phFhFUFUFhFhF 』 ym 叩幻 nn 即日お ωmm 幻 η 邸側初何回日目的刊伺伺印 T56486 日 557348851q978999999 L755958940452734E133333333 A0558394009431181222222222 N1145554385381334444444444 1BB ・ FFe ， a ROOO 日 00000 日 0000000 日目 000000 一一一-一一一-一一一一 10 日日日日日日日目 000000 日日日日 OOBOO L0000 日日日日日日 ODOOOBOB 日 OOOBOO lea マ +++++t 今 ++++++4+++ee+4++ EEEEEEEEEEEEEEEEEEEEEEEEEE 1900 日日円 000000000000 日日日日日日 D S29 日日日日日 00 日 00000000000OBOO A5E 日日日日日日日 0000 日日日日日日日日日目 DO E75 日日日日日日日日目 00000000 日 00000 F05 日日日日日 00000 日日日日日日日 OOOBOO N--00 日日日日日日日日日日日日日日日日日日 BOO l -e -日日日日日日日 000 日 000000 日日日日日日日 0 444222221110 日日日日日日日日 008 日日 )日日日日日日日日 000000 日日日 000 日日日目。 L+ ‘ +eeφ++++ ・ ++AT+ 令 ++AT'+ ，‘ ATe in 官」 FhFhFUELFhFιELFhFhFUF 」 FLELELZLULCLELELFMFhVMFhFh U5597942029688235801E2835 日 2SEElo7En35022590805E5B999 (34323E1209697647465344444 T5B486 日 557348851n3978999299 52059589404527346133333333 02558394009431181222222222 C4445554385381334444444444 ---E'・・・・ e 日日日日日日日 080 日 000000H0000 日目。 -F ←一←一-一 FF-一 叩山 0123456789012345578901234 T 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 1 (13)1
2
1
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.分割精度を向上させた時の近似解 郎 H r
u
s
y
u ns
m
・ 111 5 0 0 0 A -. 8 0 0 0 1121212 =白 UnunununU 的 U D -ｭ F b o u n u n u n u n u n u T I F121212 nunυaununununU X000000 I F111211 U000000s
Y00000O VI--21i zl 白 UnununununU D -ｭ B00000 日 目 U S111111 'OO 日 000 9& ・・ E ・ 00 日日日日 p a U211121 30000oo -ｭ T h o u n u n u n u n u n U 5 2 1 1 1 1 N008068D A U -M H C08000 日 E ) 6 1 2 3 v a V E V A V -E L O -A U U V 表 8 .. DEFINED AS... (つづき) ITERATl ON 聞JMBER= 25 . ACTlVITY... 一- EXACT 表 7 (OPTI臥L) 0.15 MINS. ...臥姫... 50山口 ON TlME = ω訂 問自 0.423950 FUNCTl O刷AL REST臥 INTS AT ... ACTIVITY.. . SLACK ACTlVITY •• L側'ERLIMIT.一 INPUT C凶T.. ..L(川ER LI削 T NONE -0.41747 0.41747 AT ... ACTIVITY... BS N川BER ...R侃. 1 COST 机明日ER • COLUMN • L何回1IMIT. 0.00000 0.00000 O. 日0000 -100.00000 100.000日日 → 100. 日0000 SECTION 2 -ωLU剛S
肌珊BER • CO山剛 AT ... ACTIVITY... ..IN問T C凶T..
0.00日日0 0.000日日 日即日日0 0.0000日 0.0000日 ð.O日日目。 郎防 mmmmm 123123 V A V A U A V E V I V E 201234 nμuhhu -b ・ 8
t
q
0.00000 O. 日0000 0.0000日 -100.00000 -100.0000日 ー 100.00000 0.00000 0.00000 0.00000 0.00000 0.0000日 日日日日日。百=問|
郎防郎防郎防 19 X1 20 X2 21 X3 22y1 23 Y2 24 Y3 細分化の反復を停止した.この解は，表 5 の NLPGR G の解とよく一致している. 以上の例題を通して，紹介したソフトウェア(これら は筆者らの必需品である.)の一覧を表 10 に示す. さらに分割精度を向上させた時の近似解 表 9 即m m v -HU-A ・ I ・ s o o o Y B O O -ｭ " E n u o w n u A121212 M 日 000 日日 ' n u n w n u n u n u n U 6 ・ . . . . , a m o w n v n u n u n u n U 6 6 ・ 111111 1 日日日目。。 二日日日日 oo h u -ｭ coo 日 00 日 T A nrT4 宅 PATA--'l'1 00 日 0000 .。日 OODD I--目 10 日 0000 F U212111 500 日目。。 Y000 日目。 -ｭ u v n u n u n u n u n u n U RHun ， z. ， PA 内'h ・‘ふの P “・・ z B 日日日日目。 U 日日 OOBO S -EnununU の unun 馴 2 ' 1 l i p-日 1050 U 日日 OUGO OD---ｭ V A O U n u n u o u n u n vT
I
l
-5 0 2 0 0 N10006 日 D O -N FLvnHU 内 HUnHU 凸 HunHunHUFFU ) S 1 2 3 ( u y u y v a v -1 F An 引 U U V NUMBER ... ROW. • AT¥..ACTIVITY... SLACK ACTIVITY .. LOWER LIMIT. 0.00000 0.00日日日 0.00000 10日.0日日日日 •100.00000 -100.000日日 労力が大幅に軽減され，汎用数理計画ソフトウェアによ る最適化計算の実行に入ることができる. 汎用数理計画ソフトウェアには大規模線形計調問題を NONE 川開閉
削
肌同州川市川
仰心
r
大規模線形計画問題の一般的な定義は存在しないが経 験的にみて，線形計画モデルのデータ作成，および運用 管理，さらには最適化計算の難易度などからみれば，制 約式数が，数千以上のモデルを大規模線形問題とするこ とは応用上実際的であろう.このようなモデルで、は，応 用を進める上で，モデルの大規模化に起因する上述した 多くの問題が発生する. 大規模線形計画問題においてこれらの問題を解決し， 与えられた課題に対して解を得るためには，まずデータ 作成時に 2 章の例題 1 ，表 l で説明したように「マト リクス・ジェネレータ J を使用することが必要な用件と なろう.これによりデータ作成に費やす分析者の時間と大規模線形計画問題の取扱い
3
.
-0.41737 0.00000 0.000日日 日.日0000 0.00000 0.00日00 0.0000日 0.41737 BS 郎防郎 Mmmmm 阿川BER • COLUMN 1 COST 19Xl 20 X2 21 X3 22y1 23 Y2 24 Y3 紹介ソフトウェアの一覧表 表 10竺一 能
|機一竺|
備
ι_I~司令ザ
ソフトウエア名|
1
B 乱4 数千制約式モデル向き 大型機 線形計画最適化MP
S
X/370
富士通"
"
"
AMPS
UNISYS
"
"
"
FMPS
三菱総研"
マトリクス・ジェネレータMCC. MG
三菱総研 KDD 研 /三菱総研 制約式 100 以下のモデル向き"
非線形計画最適化NLP-GRG
内点法 ブロック構造向き.E W S
線形計画最適化WI
S
E
MCC.
MG の改良版"
マトリクス・ジェネレータMG
三菱総研 オベレーションズ・リサーチ"
線形計画モデル・チェッグEQULST
1
2
2
(14) © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.効果的に解くための多くの機能が用意されている. 以下に主要な機能について述べよう. 1) 問題の縮小化 線形計画問題に含まれている，冗長な制j約式，変数お よび不必要な有界変数条件を取り除いて，問題のサイズ を縮小できなし、かを調べ，原問題と等価な縮小した線形 計画問題を，自動的に生成する機能である. この機能により問題の縮小化がされた場合には，最適 化計算に要する総計算量を減少させるとともに，問題を 縮小化する過程で，問題の実行不可能，あるいは無限解 等の定式化に含まれている誤りをこの段階で発見するこ とができると L 、う効果もある. 2) 多重プライシング 大規模線形計画問題の膨大なデータ・ファイル(マト リクス・ファイル)を最適化計算での反復の各プライシ ング毎に処理することをせず，多重プライシングでは i 回のプライシングで複数の基底候補を選ぶ.以下の反復 では，選ばれた基底候補群のみを対象として，最適化計 算の反復を行ない，基底候補になりうる変数がなくなる まで繰り返し，再びプライシングに入る.これによりデ ータ・ファイルは，各プライシング毎に一度読み込めば よく，各プライシング毎に 1 回以上の反復が実行される ことになる. 3) 基底逆行列の再逆転 再逆転は，現在の基底の逆行列を新しく計算する.こ れにより逆行列の積形式の大きさを，できる限り減少さ せ，その結果，以降の最適化計算を，精度よく，速く実 行することができることになる.再逆転の算法としては LU 三角化法が用いられている. 大規模線形計画問題の，最適化計算実行の次のような 状況で，再逆転が必要となろう. (1) 一部または全基底を，初期解として与えて最適化 計算を実行する場合.
(
2
)
計算の進行にともなって蓄積される丸めの誤差が 増大した場合. (3) 基底逆行列の，イータ・ベクトノレの増加により， l 反復あたりの計算時聞が増大した場合.4
.
おわりに f日j題を中心とした説明のため，図，表が多くなり，与え られた枚数を大幅に超過しましたことをお詫びします. 当初は Karmarkar らによる，内点法にもとづくソフト ウェアの大規模線形計画問題に対する取扱い等にも言及 する予定でしたが，次号以降に報告させていただきます. 参考文献[
1
J IBM corporation: IBM Mathematical
Pr-ogramming System Extended/370 (MPSX/
3
7
0
)
Programming Reference Manual
,
Publicaｭ
t
i
o
n
SHI9-1095-1
[2 J IBM corporation: IBM Mathematical
Pr-ogramming System Extended/370 (MPSX/370
Control Language
,
Publication SHI9-1094-2
[3 J
反町洋一編:線形計画法の実際.産業図書，1
9
9
2
[4J
三菱総合研究所: NLP-GRG 利用者マニュアル[ラ J
