第 6 回数理計画シンポジウム報告
小沢正典
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 第 6 回数理計画シンポジウムは， 1985年 11 月 7 日・ 8 日の 2 日間にわたって，学習院大 学百周年記念会館において開催されました. 本シンポジウムは，毎年秋に日本 OR 学会を はじめ 10におよぶ学協会の協賛の下に開催さE
.
L
.
Johnson 博士R
.
J
.
B.
Wets 教授 れています.例年多くの参加者を得ていますが，今回は， 企業・大学を含め一般 138名(海外から 4 名)・学生34名 の参加者がありました.プログラムは，特別講演・数理 計画法一般・応用・特別セッションの 4 つのセッション に分かれ，各セッションにはオーガナイザーを設定して その方々が講演を依頼するかたちで，最新の数理計画の 理論と応用のわかりやすい解説に重点をおく方針でし た.なお，特別講演には，毎年海外から著名な方々の参 加をいただいて講演をお願 L 、していますが，今回は，巡 回セールスマン問題で有名な IBM の E.L
.
Johnson 博 士，数理計画の多くの分野で高名な California 大学の R.J.B.Wets 教授の両氏をお迎えしました. シンポジウムは，伊理委員長の開会の挨拶にひきつづ き，特別講演が行なわれました. (*:オーガナイザー) セッション 1 特別講演1
-
1
rPreprocessing o
f
Mixed 1
n
t
e
g
e
r
Progra-mming Problemsj
E
.
L
.
Johnson(IBM)
混合整数計画における線形計画問題を解くさい，効率 よく解くため変数の上下限をうまく設定し直す方法や， 変数を固定しておく方法などの解説がなされた.
1
-
2
rOn P
a
r
a
l
l
e
l
Processors Design f
o
r
Solving
S
t
o
c
h
a
s
t
i
c
Programsj
R.J.B. Wets(Univ. o
f
C
a
l
i
f.) じ大きさの問題 2 つに分割して解く方法について解説が なされた. セ・7 ション 2 数理計画法一般 本田辺国士(統数研)2
-
1
rTrust Region i
n
Unconstrained
Optimiza-t
i
o
n
j
山下浩(数理システム) 制約条件なしの最適化問題において Newton 法を用 いる場合，ステップ幅が大きくなりすぎると，あらぬと ころに探索点が飛んでしまうが，ステップ隔にうまい上 限を与えて，大域的最適解を求める Trust Region 法 (信頼領域法)の紹介がなされた.2
-
2
r
An Algorithm t
o
Compute a Sparse B
a
s
i
s
o
f
t
h
e
Nul
1
Spacej
金子郁容(一橋大学) 建築構造の解析に現われるような大型の政行列が与え られたときに，その零空間を張る基底行列を疎行列の形 で求める手法の解説がなされた.2
-
3
r
S
o
l
u
t
i
o
n
Methods f
o
r
V
a
r
i
a
t
i
o
n
a
l
1
n
e
q
u
a
l
i
-t
i
e
s
j
福島雅夫(京都大学) 集合 S 内の点 x Iこ対して F(x*) T( x-x*) >0 となる zホを見いだす Variational Inequality 問題が生じて きた背景と理論的な面，その解法の説明がなされた.2
-
4
r
A M
u
l
t
i
p
l
i
c
a
t
i
v
e
Penalty Method f
o
r
Linear
ProgrammingJ
伊理正夫(東京大学)資源に制約のある確率計画問題を解くさい，問題を同 制約領域内で凸関数になり，最適解で最小となる
Pen-alty 関数を作り，それによって LP を解くアルゴリズム
おざわまさのり慶応義塾大学理工学部 の紹介がなされ，また，その数値計算例が示された.
干 223 横浜市港北区日吉 3
-14-1
2
-
5
rOn Cost and Revenue A
l
l
o
c
a
t
i
o
n
Problems
l i l l i l i -l j l l
u
l i-I
M MI
-HI
M-Arising i
n
Mathematical Programming ModelsJ
D. Granot.F. Granot(Univ. o
f
B
r
i
t
i
s
h
Columbia)
各種の数理計画モデルでの費用と利益の配分問題にあ らわれるゲーム問題の解説とその主な定理の紹介がなさ れた セ'"ション 3 応用 *前田英次郎(日本ユニパック)
3
-
1
r原料購貿業務への線形計画法の応用 J 花井宏巳 (JII 崎製鉄) 原料購買情報システムにおいて鉄鉱石・原料炭の購入 計画・配船計画業務に線形計画法を採用して，最適購入 ・最適配船を追及するシステムの構築について紹介され た. 3-2 r最適化手法の衛星通信、ンステムへの応用 j 伊藤泰彦・水池健 (KDD 研究所) 静止衛星を打ち上げるさいに，他の衛星との混信を避 けるために， Penalty 関数法・線形近似法を使用して衛 星の間隔を求めるとともに，その衛星が使用する周波数 について衛星通信での混信を少なくするのに分校限定法 を用いた例が解説された.3
-
3
r 高分子加工プロセスにおける多品種少量生産対応 の生産計画ソフトウエア j 鹿倉尚夫(東レ) 生産計画のエキスパートのノウハウから計画作業の基 準を明確にし，自動計画のアルゴリズム(生産品の機械 の割りつけには LP ，スケジューリングには 1 P) を確 立して，さらに対話型の修正により補完するシステムの 構築について紹介がなされた. セヴション 4 多項式アルゴリズム *加藤直樹(神戸商科大学) 4-1 r 最小費用流問題の解法に関する最近の話題 j 藤重悟(筑波大学) 最小費用流問題の解法として， 1985年に Tardos が発 表した点数と校数の多項式オーダーの手聞の算法の解説 が行なわれ，その解法に双対な解法の提案がなされた.4
-
2
r 組合せ最適化問題に対する SimulatedAnnealing
法 j 中野秀男・中西義郎(大阪大学) 多峰関数の近似最適化手法の SimulatedAnnealing
法が組合せ問題の近似解を求めるにも，強力であること を示し，その手法の紹介がなされた. 4-3 r 幾何学的探索アルゴリズムとその応用 J 浅野孝夫(上智大学) 1986 年 2 月号 計算機幾何学における幾何学的探索問題(点位置決定 問題，領域探索問題，点包囲問題，線分交差探索問題な ど)に，与えられた領域を等間隔のメッシュに分害u して 計算効率を高めるパケット法が紹介された.4-4
r
A Hybrid Method f
o
r
L
i
near ProgrammingJ
刀根薫(埼玉大学) LP の新解法である Karmarkar 法と Simplex 法を 組み合わせ， Karmarkar 法における直交射影のかわり に別の射影を導入して改良を図った多項式オーダーの解 法が紹介された. 4-5 rKarmarkar 法の改良について」 小島政和(東京工業大学) LP の新解法である Karmarkar 法におけるポテンシ ヤル関数を変更し，最適基底変数を決定するためのテス トを設けるなどによって Karmarkar 法の高速化をめ ざす手法の紹介と，その数値結果の解説がなされた. 7 日の 17:30 より懇親会が記念館内で開催され，講演者 をはじめ， 61 名が参加.このさい， Johnson 博士，
