一99一
線型 計 画 問 題 の新 しい 解 き方(1)
一 フ リッシュの 対 数 ポ テ ン シャル 法 一
古 瀬 大 六
RagnarFriseh:PrineiplesofLinear .Programming,wi七h particularreferenceto七hedoublegradientforエnof七he
logari七hmiepoten七ialme七hod.(MemorandumfraUniversite七es
Socia1φkonomiskeIns七iもutt,Oslo,180c七 〇ber1954)PP.219.
本 稿 は 、 上 の 論 文 の 出 来 る だ け 忠 実 な 紹 介 を 試 み た も の で 、 筆 者 の 意 見 を 全 く 含 ま な い 。 内 容 に つ い て の 批 判 は 、 実 際 に 幾 つ か の 計 算 を 試 み た 上 で な く て は 、 下 し 難 い の で 、 別 の 機 会 に 譲 る こ と と す る 。
目 次
1序
2線 型 計画 問題 の数学 的定式 化 3全 変数 を基底変数 で表 わす こと 4若 干 の 基底変 数の入れ替 え 5余 分 な拘 束の除去
も 許 容域 内の一 点 の決定(線 型不等 式の解法) 7価 格 概念
(以 下次号)
8最 適 解 の一般 的構造
9与 え られ た点 が最適 点で あ る ことの証 明法、双対法 10拘 束 の切 除
11自 由度 の切除 12複 勾配 法 の一般 原理
13複 勾 配法 を実 施ず る際 の計算規 則 14単 体法
15高 階線 型聯立方程式 の解 法 についての一般 的な話 16消 去 法 に よる高階 線型聯立 方程式 の解 き方
17ガ ウスの計算法
18繰 返 し法 によ る高階 線型聯立 方程式 の解 き方 19最 大 雇傭 問題 を複勾 配配法 に よつ て解 いた例 20最 小入 超 問題 を複勾 配法 で解 いた例
一100一 商 学 討 究 才6巻 才2号
1序
オ ス ロ 大 学 経 済 学 研 究 所 に お け る 線 型 計 画 研 究 の 結 果 の 第 一 報 は 、1954年6‑
7月 に イ タ リ ・一 の コ モ で 開 か れ た 「投 入 産 出 分 析 に 関 す る ヴ ァレ ナ 会 議 」に 提 出 さ れ 、"MethodsofSolvingLinearProgrammingProblems,firstdraf七",
]M【imeographedMemQrandumofJune1954,theOsloIns七i七ute,PI).90(Z>
表 題 を 附 し て 発 表 さ れ た 。
吾 々 の 目 的 は 、 巨 視 的 経 済 計 画 の 問 題 を 、 古 典 的 な 単 体 法(simplex
method)の よ う に 大 規 模 な 電 子 管 式 デ ィ ジ タ ル 型 計 算 装 置 を 使 う こ と な し に 、
ロ
簡 単 な手廻 し計算 機 だ けで能 率的 に解 く方 法 を探 す ことで あつ た。
巨視 的経 済 計画 を立 て るに当 つて は 、 今 迄 の よ うな 単純 な投 入 産 出分 析 で は 不 充 分で あ る。則 ち 、(1贋 源 ・固 定設 備 の 限界 を示 す 不等式 関係 が無視 されて お り、{2踵 々 の資源 ・生 産 手 段 の 問 の代 替 関係 、新 しい技 術 導入 の 可能性 が考 慮 され て お らず 、(31製品 組合 せ の割合 も固 定 されて お り、(4社 会 的 ・人 道 的又
は 政治 的 な諸 目的 につ い ての極 大化 が 考 え られて い ない 。
これ らの点 を計算 に入 れ るには 、種 々 の線 型 不 等式 拘 束 を追加 し、 極 大 化計 算 を取 入 れ る ことに よつて 、 投 入産 出分 析 の線 型聯 立 方程 式 を線 型 計 画法 の形
に改 め な けれ ば な らない。
2線 型 計画 問 題 の数 学 的定 式 化
巨視 的 経 済 現 象 の 内容 を 構 成 す る と ころ の 純 国 民 生 産 物 、 国 民 消 費 、 純 国 民 投 資 、 種 々 の 財 の 消 費 と投 資 並 に そ の 各 部 門 間 の 授 受 量 、 種 々 の 商 品 の輸 出 入 量 、 種 々 の 租 税 及 び 政 府 支 出 等 々 、 を表 わ す 変 数x、 、Xa、 ・・・… κN塗 ・ 構 造 変 数 と 呼 ぷ 。 これ らの 構 造 変 数 の 間 に は 、 種 々 の 定 義 的 関 係 又 は 経 済 主 体 の 行 動 様 式 を表 わ すM個 の 構 造 方 程 式 が 与 え られ て い る 。
(2.1)ai。 十ai、xノ 十 ・・十aiNXN=0(i=1,…,M)
投 入 産 出 分 析 の 場 合 と は 異 り、 変 数 の数1>と 式 の 数Mと は 一 致 せ ず ・ 一 般 に 変 数 の 数Nの 方 が 式 の 数Mよ り も多 い 。 そ の 差(N‑M)を 構 造 的 自 由 度 と 呼 ぷ 。
線 型 計 画 問 題 の 新 し い 解 き方(古 瀬)一 一一101‑一 資 源 ・ 生 産 設 備 の 有 限 性 、 輸 入 量 の 制 限 、 政 治 的 考 慮 に 基 く 制 限(最 低 雇 傭 量 等)な ど は 、 右 の 構 造 変 数 に つ い て のN*個 の 線 型 不 等 式 で 表 わ さ れ る 。
(2.2)ai。 十aitxノ 十 … 十aiNXn≧0(i・=2V十1ジ ・・,!V十2V*)
こ れ を(2・1)の 等 式 と 同 等 に 扱 え る よ うに す る た め に 、NX個 の 非 負 な る ス ラ ッ ク変 数 加+、,…,κ π研*を 導 入 し て 、
(2・4)aj。 十aj/xノ →一… 十ajlvXiπ 一Xj=0(ブ=N十1,…,N十N*)
と 、 書 き改 め る。 これ を(2・1)と 一 括 して 考 え れ ば 、(N十N*)個 の 変 数 に つ い て の(M十Nり 個 の線 型 聯 立 方 程 式 が 得 られ る 。
そ の 外 に ま た 、 個 々 の 構 造 変 数 が 、 そ の 変 域 の 上 限 又 は 下 限 を 持 つ こ とが 多 い 。 下 限 がaで あ れ ば 、xの 代 りに(x‑a)と お け ば 、x≧0な る 単 純 な非 負 条 件 で これ を表 わ す こ とが で き る 。 下 限 な らば 、(う 一め で お き か え る こ と
・に よつ て、 同 様 に 、 κ の 非 負 条 件 に転 化 させ る こ とが で き る。 両 方 に 限 界 の あ る場 合 に は 、 下 限 の 方 は 非 負 条 件 で 、 上 限 の 方 は ス ラ ッ ク変 数 で 処 理 す る こ と に よ り、 必 らず 等 式 化 す る こ とが 可 能 で あ る。
以 上 の よ うな 等 式 化 を施 し た結 果 、(〃 十 初 り個 の 変 数 に つ い て の π 個 の式 よ りな る線 型 聯 立 方 程 式 と 、@+m‑N)乃 至(n+m)個 の 変 数 に つ い て の 非
■
負 条 件 と が 得 ら れ 、 そ れ ら に よ つ て 自 由 度 π(則 ち π 次 元 の)な る 許 容 域(
admissibleregion)、 則 ちxの 存 在 可 能 領 域 が 規 定 さ れ る 。 計 画 法 と は 、 こ の 領 域 内 で 、 或 る 選 好 函 数(preferenccfunGtion)
∫=π 。+π 、κ、+… 十 砺 欄 κπ。脇
を 最 大 な ら し め る と こ ろ の 変 数 κ の 値 を 求 め る 問 題 に 外 な ら な い 。
3全 変数 を基 底 変数 で 表わ す こ と
前 述 の 如 く 、 線 型 計 画 問 題 は 、
ai。 十ai、xノ 十 … 十ai,m+nXm+n=0(il=1,…,m) x≧0
な る 条 件 の 下 で
∫=π 。+π 、κ、+…+π 鵬柳 毎 柳
を 最 大 に す る と こ ろ の 解 を 求 め る こ と で あ る 。 そ れ は 〃 の 自 由 度 を 持 つ か ら 、
一102‑‑M商 学 討 究 才6巻 才2号
初 十"個 の変 数 の うち の 任 意 の π 個 を常 数 と 見 て 、 残 りの 吻 個 の 変 数 に つ い て 解 けば 、 これ らの 初 変 数 を%変 数 の函 数 と して 求 め る こ とが で きる 。 こ の 選 ば れ たn個 の 変 数 を基 底 変 数(basisvariablos)、 そ れ らに よ つ て表 現 され
るm個 の 変 数 を 従 属 変 数 こdependen七variables)と 呼 ぷ 。 こ の 基 底 変 数 を・
(Xu,κ 。,…,κw)、 従 属 変i数を(Xp,Xq,・ …Xr)と す れ ば 、 右 の 聯 立 方 程 式 は (3・1)X」=∂,・ 十b5uXu十bd。x。 十 … 十b5,。xω(ブ=ρ,q,… グ〉
と な る 。 これ に 娩=腕(ゴ=循 の,…,ω)な る π 個 の 恒 等 式 を 添 加 す れ ぼ 、 右 の 式 は ブ=1,・ ・,m+nに つ い て の(m+n)個 の 聯 立 方 程 式 と見 る こ と が で
き る。
或 る一 組 の 変 数(蜘,κ 。,…,κ,")が 底 基 変 数 と して 使 え る た め に は 、 残 りの m変 数 の 係 数 よ り構 成 さ れ るm×m行 列 がnon‑singular(則 ち 、 そ の 行 列 式 の 値 が0で は な い)で な け れ ば な らな い 。 然 し、 実 際 の 計 算 に 際 し て は 、 一 々 そ の 行 列 式 の 値 を 計 算 して い て は 手 数 が か か る の で、 簡 単 な 基 底 方 程 式 の 求 め方 が 必 要 と な る。
(1}三 角 行 列 法 … ・・(2.1),(2.4り 式 に お け る従 属 変 数 の 係 数 を要 素 と す る mXm行 列 の行 ・列 を適 当 に 入 れ 替 え る こ と に よ つ て 、 そ れ を三 角 行 列(対 角 要 素 は 悉 く非 零 、 其 他 の 要 素 は 零 で も差 支 な い)に 改 め る こ と が で き るな ら ば 、 順 次 に 代 入 す る こ と に よ つ て 、 手 廻 し計 算 機 だ け で(3.1)式 の 各 係 数 を 求 め る こ と が で きる 。
② 三 角 行 列 法 と聯 立 方 程 式 解 法 と の 髭 用 … … 大 部 分 の 従 属 変 数 が 三 角 行 列 条 件 を充 た す な らば ・ 三 角 行 列 法 で 出 来 るだ けや つ てさ 出 来 な くな つ た と きに は 通 常 の 消 去 法 其 他 の 聯 立 線 型 方 程 式 解 法 で 解 き、 更 に 三 角 行 列 法 を 続 け る、
と い う具 合 に 、 交 互 に二 つ の方 法 を繰 返 え す 。
(3)入 為 変 数(artificialvariabヱes)法 一 ・m×m行 列 に属 す る従 属 変 数 の うち 、 若 干(ン 個)の 変 数 を除 い て 、 こ れ を 主 変 数 の申 に加 え る こ と に よ つ て 、(m一 の ×(m‑v)行 列 が 三 角 化 され る な らば 、 これ に よ つ て 過 剰 と な つ た 珂 固の方 程 式 を右 のv個 の 変 数 に つ い て 解 き、 そ の 解 を 残 りの(m‑v)個 の 聯 立 方 程 式 に 代 入 す る こ と に よ つ て 、 問 題 を 、 主 変 数n個 、 従 属 変 数(〃2一 の 個 の 三 角 行 列 法 に 転 化 させ る こ とが で き る 。
線型計 画問題 の新 しい解 き方(古 瀬)一 一一103・一一 四 主 変 数 の 選 び方 ・… ・以 上 の 何 れ の 便 法 も使 え な い よ うな場 合 に は 、 吻 変 数 に つ い て の 聯 立 方 程 式 を ま と もに 解 か な け れ ば な らな い の で 、 ど の 変 数 を基 底 に とつ て も大 し た違 は な い 。 然 し、 以 降 の 計 算 を 簡 単 に す るた め に は 、 問 題 に つ い て の 具 体 的 知 識 、 又 は、 目 の子 算 に よ る近 似 解 、 が 与 え られ て い る な ら
ば 、 これ に基 い て ど の 不 等 式 が 最 適 解 に お い て 作 用 す るか 或 は し な い か の 見 当 を つ け て 、 な るべ く零 と な る こ とが 確 実 な変 数 を 基 底 変 数 に と る こ と が 望 ま し
い 。
斯 く し て 全 変 数 ・全 方 程 式 が 基 底 型(basisfOrm)に 改 め ら れ た な ら ば 、 変 数 の 番 号 附 け を 改 め て 、 主 変 数(basisvariables)の 番 号 をx、,一 ・,Xn、 従 属 変 数 の 番 号 を 晦+,,…,勉 孤 と す る の が 便 利 で あ る 。 則 ち 、
れ
(3.6)Xd=∂ ゴ。 十 Σ ∂錦 為(ブ=1,…,%十m)
ノ
(但 し 左 辺 のX,か らXnま で はXj=Xj)
これ らの 方 程 式 を 作 り上 げ る に 当 つ て は 、 一 部 の 変 数 に つ い て は そ の 変 域 を 非 負 変 域 に 限 定 して きた が 、 残 りの 変 数 に つ い て は何 等 そ の よ うな 条 件 は つ け ず に 進 ん で き た 。 然 し、 若 し或 る一 変 数 が そ の 変 域 の 限 定 を うけ な い とす るな らば 、 そ の 値 を無 限 大 又 は 無 限 小 な ら しめ る こと に よつ て 選 好 函 数 の 値 を無 限 大 に す る こ とが で き るの で 、 計 画 法 と して の 実 質 的 意 味 が な くな つ て し ま う。
ま た 、 若 し そ の 非 限 定 変 数 の 選 好 函 数 に お け る係 数 が 零 で あ る な らば 、 そ れ を 含 む総 て の 方 程 式 は 。。=。。 と な つ て 、 方 程 式 と して の 意 義 を 失 つ て しま うの で 、 これ らの 変 数 及 び方 程 式 は 、 悉 く これ を 問 題 か ら除 い て 考 え な け れ ば な ら な い 。 そ の よ うな 操 作 を行 つ た 結 果 と して 得 られ た もの が 右 の(3.6)式 で あ
る と す る な らば 、(3.6)式 の 総 て の 変 数 は 一 つ 残 らず 非 負 変 数 で あ る 、と規 定 し な け れ ば な らな い 。 則 ち、
(3.8)Xj≧0(i=二1,…,n十m)
とい う制 約 が 加 え られ る こ とに な る 。
4若 干 の基 底変 数 の入 れ 替 え
シ ン プ レ 。クス 法 で は 、 底 基 変 数 の 入 れ 替 え は 、 必 らず 一 回 一・変 数 に 限 られ
一一104憎 商 学 討 究 才6巻 才2号
る た め 、 そ の 計 算 は 比 較 的 簡 単 で す ん だ 。 然 し 、筆 者 の 方 法 に よ る と きは 、 多 数 の 変 数 を 同 時 に 入 れ 替 えな け れ ば な らな い の で 、 そ の 計 算 を 簡 単 に す る方 法
を 考 え る こ と の 意 義 が 非 常 に 大 き くな っ て く る。
基 底 変 数Xu,Xv,…,Xwの 申 か ら除 きた い と思 う変 数 をXA,XB,…,Xc、 従 属 変 数 物,物,…,紛 の 中 か ら、 晦,物,…,物 と入 れ 替 え に 、 新 た に 基 底 変 数 の うち に加 え た い と思 う変 数 を 、 勘,κ β,…,鈎 とす る 。
元 の 基 底 方 程 式 が 非 常 に 簡 単 な もの で あれ ば 、 単 純 な消 去 法 に よつ て 、 変 数 入 替 え を 行 うこ とが で き る。 則 ち 、 基 底 方 程 式 の うち 、 新 た に採 用 す べ き変 数 晦,掬,…,鈎 を左 辺 に 持 つ 方 程 式 だ け を 取 出 し て 聯 立 させ 、 そ れ を 、 除 去 す べ き変 数XA,κB,…,Xclcつ い て 解 い て 、得 られ た 答 を元 の 基 底 方 程 式 に 代 入 ・整 頓 す れ ば よ い 。
右 の 計 算 が 非 常 な 手 数 を要 す る と きは 、次 に 述 べ る遷 移 行 列(shif七ma七rix) と逆 遷 移 行 列(inverseshiftma七rix)と を 使 つ て 解 く方 が 簡 単 に な るで あ ろ う♂
先 ず 、 基 底 方 程 式 の うち、 左 辺 が 晦,κ β,…,κγの 式 だ け を 抜 出 し、 更 に そ の 右 辺 のXA,κB,…Xcに つ い て の 係 数 だ け を 取 出 し た 行 列 〔b」.)(i=α,β,・ ・, γ;le=A,B,d‑一,C)を 作 り、 こ れ を遷 移 行 列 と名 附 け る。
「砺轟 β… 伽 麗 制 ∂β伽 …bβc
〔偏 砺̲伽
この 行 列 がnon‑singular(i∂ 祠 ≠0)で あ る と仮 定 す るな らば 、 そ の 逆 行 列
〔∂誘 〕 もま た 計 算 可 能 で あ る・ 具 体 的 計 算 手 続 と し て は ・15〜18章 の うち の適 当 な もの を 利 用 す れ ば よ い 。
こ の 逆 遷 移 行 列 を 使 つ て 、 元 の 基 底 方 程 式 中 、 左 辺 に κω,κβ,…,絢 を 持 つ 式
ノ
だ け を 聯 立 さ せ て.XA,XB,…,Xcacつ い て 解 い た 値 を 求 め れ ば 、
Xk=Σ ∂㍊(Xj‑bj・ 一 ΣbjhXh)
jeat,β,'一 一一,γ ・hsu・v・u‑『)A)B・'一'一 ・c(一 一一tW
(k=A,B,…,C)
==一 Σ ∂だ 砺 一 Σ(Σ δ》 ∂」の 筋
5=αt,β ザ …,γ ん 呂 簡"一 一一一(」,・β ・ 一一一・σ)一 一一・" 」=偽 β,…,γ
り
線型計 画問題 の新 しい解 き方(古 瀬)一 一105‑
+Σ 碍 勾 .
'昌 偽 βジ ー一・,γ
こ こ で 、
b'k・=儒
,。認 …,,嬬 妬(le=4・B・‑t● ・c)
b…h‑一 扇 ∵ 諏(le=A,B,…,Ch
=π,v,… ン1,B,…,C(… ω)
殉 一6だ(々=A,B,…,cブ=α
,β,…,γ) とお けば 、 右 の 式 は 、
(4.8)x、 、=b・ 、、。+Σb・i、h.・ 。+Σb・ 、両
h=ti,Vv‑…)A,B‑一 一・,σ(一 一一wj=ct,β,一 一一一,γ
(k==A,B,…,C) の 如 く 見 易 く な る 。
こ の 銑 を 、 元 の 基 底 方 程 式 の う ち の 、 左 辺 に 筋,仰,…,絢 以 外 の 変 数 を 有 す る 方 程 式 に 代 入 す れ ば 、
凝 ・=δξ。+Σ ∂錦 ごκん ・
h=tt,Vl‑一 一一)A,Bv‑一,C(…w
+Σ ゐ轟(biic。+Σb!iCI、Xh+Σ ∂勾 κ」)
iCmA,B,・ 一一一,ah=ti,Vt‑一 一・)A,B,… 一,a(… ・w,j・=αt,β,・ 一一一,Y
ゼと な る 。 こ こ で ま た 、 ・
∂ノe。="bg・+Σbg .icbliC・{9=P,q,…)α,β,…,γ(…,r}
滝 犀A,B,一 一・,σ
∂'緬=∂ 緬+ΣbEkbliCh=哉 ん一 Σb!g」b」h
le』AB,一 一一,o'一 α},β,一 一一一,γ
'髭:￡
:91111諺:91誇誕1需
∂㌔=Σb・,lebノ 炉 Σ ∂覇6㍊
髭=A,β,一 一一一,σ 滝 鵠A,B,一 一一一,σ
擁1締'β'."γ('."「}
o
と お け ば ・ 更 に 簡 靴 紳 て ・ (4・13)Xg:bノ σ・ ㌔
̲.,藷L,。 、…,ω ∂'・漁 ㌔c、;i;ltll."一.,,殉η
{9==P,q,…)α,β,…,γ(・‑7r}
と な る 。
一一106一 商 学 討 究 才6巻 才2号
則 ち 、 計 算 手 続 き と し て は 、 先 ず15〜18章 の 方 法 で 逆 遷 移 行 列 を 求 め 、 次 に そ れ を 使 つ て 新 し い 係 数b/k。,b/leh,∂ ㌔;b!,o,bi、.h)臥 」 を 求 め て 、 こ れ ら を(4・8),(4.13)式 に 代 入 す れ ば 、 新 ら し い 基 底 変 数Xu,κ 。,…,Xdi,xβ 、・一一・
κγ,…,紛 に つ い て の 基 底 方 程 式 が 得 ら れ る 。
最 後 に 、 こ の よ うな 変 数 の 遷 移 に 伴 つ て 生 ず る 、 選 好 函 数 の 変 化 を 求 め て お か な け れ ば な ら な い 。 最 初 の 基 庖 変 数 に 対 応 す る 選 好 函 数 を
f・=P。 十PaXu十Pvx.十 … 十Pt。Xw と す る 。 こ れ に(4.8)を 代 入 す れ ば 、
ノ=ρ 。+Σ ρん筋+Σ ρ繍 ん
ん 漏 脇"ザ …)為 β,… 一,oc‑一 ωiC=璃 β ジ ー一,o
=ρ 。+Σ ρ 砂 ん
h・=ti,",…)A,B,一,o(・ 一一一"
'+Σ 毎(∂ 鰯+Σ δ'
肋 筋
kuA,・8,…,Oh=u,v,・ …)A,Bゾ …,0(一 ・ω
+Σblk」XJり
」 一 α,β,一 一一㍉ γ
の 如 く、 新 しい 基 底 変 数 に つ い て の 選 好 函 数 が 得 られ る 。 こ こで 、 グ 。=ρ 。+Σ'光 〜4β 毎 δノ肋
,一 一一,c
〆,=Σ ρ融 ㌔=Σ ρ孟 だ(ノ=α,β ・…,γ)
iC禰A,B,…,σiC=A,B,一 一一,c
グ ん=毎+Σ 毎 ∂'肋=毎 一 Σ グ,∂ μ
iC=A,B,一 一・一,cj..αt・ β,一 一一Y
=カ ド Σ 毎 ・Σ 勾 ∂'ん
k=A,」B,一 一一・,σ 」=at・ β ・ 一旧「rソ
と お け ば 、
f.pi。+ΣP1hXh+ΣP/jX」
re=UIVe)AB‑一 一 σ(・ …,7jaαt,β ド ・,γ
が求 める 選 好函 数 で あ る。
5余 分 な 拘 束 の 除 去
N+個 の 不 等 式 拘 束 条 件 の うち に は 、 そ れ らの うち の幾 つ か が 成 立 つ な らば 、 そ れ に伴 つ て 必 然 的 に成 立 つ よ うな 不 等 式 が 含 ま れ て い る場 合 が 考 え られ る。
後 者 の 不 等 式 を 、 余 分 な拘 束(redundan七bounds)と 名 附 け る。 この よ うな redundantboundsは 、 あつ て もな くて も、 計 画 法 の 答 え に は 何 の 影 響 を も与
線 型 計 画 問 題 の 新 し い 解 き方(古 瀬)一 一107‑一 えず 、 単 に 計 算 手 続 を複 雑 に す るだ け で あ るか ら、 予 め これ を 除 い て お く こ と が 望 ま し い 。 最 初 か ら完 成 に 除 さ去 る こ とは む つ か しい け れ ど も、 簡 単 な 手 続 だ け で そ の うち の か な りの 部 分 を 予 め 除 去 す る こ とが で き る。
(第 一 命 題)問 題 を基 底 型(basisform)に 直 し た 結 果 、・或 る従 属 変 数 ∬̀を 左 辺 に 持 つ式 の 右 辺 の 総 て の 係 数(砺,砺,砺,…,∂ δの が 非 負 で あ れ ば 、 右 辺 の 主 変 数 は(3.8)に よ り同 じ く非 負 で あ るの で 、Xiは 必 然 的 に 非 負 と な
る 。従 つ て 、元 の 不 等 式
れ セ
bt。 十 ΣbiicXiC≧0
陀 躍 ノ
は 、 余 分 な 拘 束 で あ り 、 最 初 か ら 除 去 す る こ と が で き る 。
(第 二 命 題)二 つ の 従 属 変 数Xi、X」 を 左 辺 に も つ 式 の 右 辺 の 各 係 数(bi・, 砺,…,bin),(b5。,∂ 」、,・・,b」n)を 比 較 を 比 較 し た 結 果 、 娠 ≧ ∂祇 ん=1,…,n)・
則 ち 、Xiを 左 辺 に も つ 式 の 係 数 の 方 が 鈎 の そ れ よ り も悉 く 大 き い(uniform dominant)な ら ば 、Xiに つ い て の 方 程 式 を 除 去 し て 、Xjに つ い て の 方 程 式 だ
け を 残 し て お け ば よ い 。
(第 三 命 題)娩 が 直 接 に は 第 二 命 題 を 満 足 し な い 場 合 で も 、 基 底 型(basis form)か ら の 論 理 的 に 必 然 的 な 変 換 に よ つ て 得 ら れ た と こ ろ の 或 る式X」=f (x、,…,xn)と 比 較 し てuniformdominan七 で あ る な ら ば 、 そ のJviを 除 く こ
と が で き る 。
6許 容域 内の一 点 の決定(線 型 不 等 式 の解 法)
6a序
対 数 ポ テ ン シ ャル 法(10gari七hmicpotentiallne七hod、 そ の 詳 細 に つ い て ぱ 第12・13章 を 参 照 の こ と)を 利 用 す る際 に は 、 予 め 、 総 て の不 等 式 拘 条 件 を 満 足 す る と こ ろ の,t'の 一 つ の 値(則 ち 、ini七ialfeasiblesolu七ion)が わ か っ て い な け れ ば な らな い 。 単 に 、 与 え ら れ た 式 の 形 を な が め る だ け で 、 こ の ini七ialfoasiblesolutionを 求 め る こ と の で き る場 合 も少 くな い 。 然 し な が ら、 与 え られ た式 が 複 雑 で あ る と 、 も つ と 組 織 的 な 求 め方 が 必 要 と な つ て く る。
こ の 許 容 域 内 の 一 点 を 見 出 す 組 織 的 方 法(則 ち 、 線 型 聯 立 不 等 式 を 解 く方
一一108‑一
.商 学 討 究 才6巻 才2号
法)と して 、 種 々様 々 な 逐 次 計 算 法(itera七iveme七hodり が 考 え 出 き れ て い る。 オ ス ロ ー の 経 済 研 究 所 で は 、 これ らの 方 法 を使 っ て 実 際 に 計 算 し て み た 結 果 、 次 の(6e‑6g)の 方 法 が 最 も有 敷 で あ る こ とが わ か つ た 。
許 容 域 内 の 一 点 が 求 め られ れ ば 、 爾 後 の 線 型 計 画 問 題 を 解 くに 必 要 な 手 続 き は 、 次 の 二 つ に 分 け て 考 え る こ と が で き る。 そ の 一 つ は 、 許 容 域 内 の 出 発 点 か
らの 運 動 方 向 を決 定 す る こ とが あ り、 他 の 一 つ は 、 そ の 方 向 に 沿 つ て の 運 動 の 長 さを 決 め る こ と で あ る。 則 ち 、出 発 点(ini七ialfeasiblesolntion)のn+m
ヴ=ク トル をx、 運 動 の 方 向 ヴェク トル をd、 運 動 の長 さ を λ とす れ ば 、 そ の 運 動 の 終 点 κノ の 値 は 、
(6a.4)xlニx十 λd
で 表 わ き れ る。 この 二 つ の点 κ、 κノ は 何 れ も 許 容 域 内 に な け れ ば な らな い か ら、 何 れ もbasisfoxm(3.6♪ を 満 足 す る筈 で あ る。
則 ち、
一 に二1激㌶1::1:淵
1
れ
∴x!」‑X」=Zd」=Σb」 ノκ(x!iC‑XiC)=Σ ノδ」κ(λd,、
(6a.5)∴d」=Σbj,d,(ノ=1,…,n十m)1
が 成 立 た な け れ ば な らな い 。 但 し(6a・5)は ・(ブ=1・ … ・n)の 場 合 に はd」=
d」 な る恒 等 式 に す ぎな い 。 この(d、,…,dn)を 、 変 数 の 場 合 と 同様 に 、基 底 方 向(basisdirec七iOll)と 名 附 け る な らば 、 この'n個 の方 向 要 素 の 決 ま りさ え す れ ば 、 残 りのm個 の方 向 要 素(d。 。i,…,dn.m)は(6a.5)式 を 通 じ て 一 義 的 ・従 属 的 に決 定 され る。
こ のdの 値 は 、 そ れ が 出 発 点 の 近 傍 に於 て 許 容 域 内 に あ る限 り、無 限 に 多 く の 値 を と る こ とが で き るが 、 そ れ に 伴 う選 好 函 数 の 増 加 を最 大 に す る と こ ろ の 方 向 が 必 らず 存 在 す る筈 で あ る。.この よ うなdの 値 、 則 ちdの 最 適 値 を求 め よ うとす れ ば 、 そ れ に は 、 与 え られ た線 型 計 画 問 題 を 完 全 に 解 か ね ば な らぬ こ と と な り、 逐 次 計 算 法 とレ て の意 味 が 全 く失 わ れ て し ま う。 そ れ故 ・ 最 適 値 で
線型計 画 問題 の新 しい解 き方(古 瀬)‑109一
な くて もよ い か ら、 そ れ に 近 い 値 を 、 簡 単 な 計 算 手 続 で 、 求 め られ る よ うに工 夫 し な け れ ぼ な らな い 。 以 下(6b‑‑6e)に お い て 、 この よ うな 簡 易 決 定 法 に つ
い て 考 え て み よ う。
6b聯 立 方 程 式 を解 か ず にdを 決 め る妥 協 的 方 法
以 下 、証 明 の便 宜 上 、測 定 単 位 の影 響 を 除 くた め に 、全 変 数 を 予 めnormalize して お ぐ。 則 ち
(6b・ ・)ξ ・ 一 青(ブ ー ・ ・… ・n+m)
但し
(6b・2)B'一 ♂ わ'ヲ+…+わ ・ぽ ・R・・:%)
と 変 数 変 換 を 施 し た 上 で 、(3.6)のbasisformを
(6b.3)ξ,=β5。+:liβ 」iCξte(ブ=1,…,n+m)
ノ
の よ う に 書 き 換 え て お く 。hormalizeさ れ て い る か ら 、 β,ヲ+…+β51i・=1で あ
'
る こ と 勿 論 で あ る 。
先 ず 、 絶 対 座 標 の 値 が(x,,…,κn)で あ る 一 点xか ら 、Xjこ0な る 平 面 へ 下 し た 垂 線 の 脚 の 一 点(則 ちxのX」=0平 面 へ のprojec七ion)の 座 標 を (κ り,… ・κηの と す れ ば 、
16b・6)簸 ・ 一 ゐ
,ヲ鷹 ゐ,露(le‑・ ・… ・n)
と な る 。 こ れ をnormalizeし て 、 ξ を 使 つ て 表 す な ら ば 、 簡 単 に 、
(6b・7)e・ ・1‑ele‑e」sjk(餐 芦 伽)
と な る で あ ろ う 。 θ
こ の 出 発 点 ξ(ξ パ ・二,ξn)か ら 、(一 β」、,…,一 β5沿 の 方 向 に(則 ち ξ」=0平 面 に 向 つ て 垂 直 に りL5の 長 さ だ け 進 ん だ 先 の 点 を ξノ≡(ξ ノ、,…,ξ ノn)と す れ ば 、
(6b・8)e・ …9・+L・ βパ(1:1:iii:憂+m)
と な る こ と 、 云 うま で もな い 。 この ξ!点 が 丁 度 ξ」=0平 面 上 に 達 す る(則 ち 、 ξノ」=0と な る)た め の必 要 十 分 条 件 は 、
一一110‑ ,商 学 討 究 才6巻 才2号
(6b.9)Lj==一 ξj
で あ る こ と 、(6b.7)式 を 一 目 見 れ ば 明 か で あ ろ う 。 こ こ で 、 ξj=0平 面 に 垂 直 に 進 ん で 丁 度 ξ,=0平 面 に 達 し た 瞬 間 の 、 ヴ ェク トル 要 素 の 増 分 に 注 目 し 、
こ れ を 砺=ξ ㌔ 一 銚@=1,…,n)で 表 わ せ ば 、
じ
∠icj・=(ξ,+L」 βjiC)一ξ酌=・Ljβ 」iC=・一一ξjβ」k (6b.10)"■.∠tk」==一 一ξ,βjiC(ん=1,…,n)
の 如 く 簡 単 に 表 わ さ れ る で あ ろ う 。
以 上 は 、ξ,=0と い う唯 一 つ の 平 面 に 向 つ て 垂 直 に 進 む 場 合 の 座 標 の 動 き を 考 え て き た の で あ る が 、 更 に 、 幾 つ か の 平 面 に 対 し て 同 時 に 近 似 的 に 垂 直 に な る よ う に 進 も う と 試 み る 場 合 に つ い て 考 え て み よ う 。 こ の よ う な 妥 協 的 方 法 に は 種 々 の や り 方 が 考 え ら れ る 。 各 平 面 に つ い て 計 算 さ れ た 鞠 の 合 計 値 を 以 て 決 定 す る の も 一 つ の 方 法 で あ ろ う 。 則 ち 、 こ の 場 合 の 妥 協 的 基 底 方 向 (compromisebasiedirec七ion)を(∠ パ ・・,dn)と す れ ば 、 そ れ は 、
(6b・11)4F需
,∠炉 認(一 ξ・防 の(le=1・'t'・n)
で 表 わ され る。 総 和 記 号 に 添 え られ たsel.ブ な る符 号 は 、 そ の 方 向 へ 進 も うと 計 画 して い る平 面 に つ い て の み 合 計 す る こ とを 意 味 す る。 これ に伴 う従 属 変 数
の 変 化(lin+.,…,dn+m>は 、(6b・3)式 よ り 、
(6b.12)4=Σ β」,d,(ブ=π 十1,…,n十m)
1
と な り 、 こ の 右 辺 に(6b.11)を 代 入 す れ ば 、d.,…,ム の 場 合 と 同 様 にselξ 」 の 線 型 函 数 と な る 。 以 上 二 つ の 場 合 を 一 括 す れ ば 、 向 うべ き平 面 が 決 ま り さ え す れ ば 、 全 変 数 に つ い て の 方 向A、,…,dn+mが 決 ま り 、 従 つ て 、 こ の 方 向 に λ
の 長 さ だ け 進 ん だ 先 の 座 標 ξ!の 値 は 、
(6b.13)ξ ノ」=ξ 」十 λ ∠t∫(ブ=1プ ・・,n十m) と な る で あ ろ う 。
こ こ で 、 εθ1ξ」 の 選 び 方 に つ い て 一 言 し て お か な け れ ば な ら な い 。 ξ,は 何 れ も 非 負 で な け れ ば な ら な い か ら 、 缶 発 点 に お い て 負 で あ る と こ ろ の 総 て の 変 数 を 、selξdに 選 ぶ の が 極 め て 自 然 で あ る 。 丁 度0に 等 し い 変 数 は 、selξ 」の 中 に 加 え て も 加 え な く て もd」 の 値 に は 変 り は な い(6b・11)。 そ れ 故 ・ .
線 型 計 画 問 題 の 新 し い 解 き方(古 瀬)‑ll1‑一 (6b,14)diC=Σ 」(一 ξjβ3ガ)〔ξ」>0〕(々 ・=1,…,n)
に よ つ てcompromisebasisdiroctionを 求 め 、 そ れ を(6b.12)に 代 入 し て 残 り の 方 向dn+、 ・…,4η 編 を 決 定 す れ ば よ い 。
以 上 は 、normalizeき れ た ξ 座 標 ・β 係 数 に つ い て 論 じ て き た が 、 ξゴ=・x」/
B」,殊=娠/B」 に よ つ て 元 のx座 標 ・b係 数 に 戻 せ ば 、(6b・14)式 は
寄=Σ ・C一 箭 × 象)〔XjK・ ・0〕(た=・,… ・η) と改 め られ る。更 に見易 くす るた めに
(6b・ ・7)Xl一 毒(ノ ー ・・…,n+m)
と お い て 、
(6b.18、d,==B,Σ 」(‑Xjbj,)〔Xj<0〕(le=1パ ・,n) と 書 き 直 し て お く と 、 計 算 に 便 利 で あ る 。
則 ち 、 出 発 点 の κ 座 標 と 、 基 底 方 程 式 と が 与 え ら れ る な ら ば 、 先 ず Bj2=b,ヲ 十 … 十bjli(ブ=1,…,n十m)
を 計 算 し て お き 、 そ れ を 使 つ てX,==X」/Bi(ブ=1,…7n十m)を 求 め 、 そ れ を 前 記 の(6b.18)式 に 代 入 す る こ と に よ つ て 、CQMpromisebasis
direc七ion(d',…,dn)を 簡 単 に 算 出 す る こ と が で き る 。 そ れ を 更 にd」=Σ
ノ
伽 ゐ(ブ=〃+1,…,n+m)(6a.5)に 代 入 す れ ば 、 残 り の 総 て の 方 向 ヴ ェク トル が 決 ま る 。 そ の 上 で 、6ノ 〜69の 方 程 式 で 進 行 の 長 さ λ を 決 定 す れ ば 、
Xノ」=Xj十Adj(ブ=1,…,n十m)
に よ つ て 、 新 し い 位 置c2ilx座 標 、 則 ち 〆 の 値 が 計 算 さ れ る で あ ろ う。
6c回 帰 法 に よ る方 向 の 決 定
何 等 か の 方 法 で 決 め られ た 方 向Dに 向 つ て 進 み た い の だ が 、 そ の 行 きつ い た 先X1」=X」+λD」 が 元 の 基 底 方 程 式Xj=b」 。十 Σ 娠 簸(ノ=ゐ ・・,n+m)
ノ
を 満 足 す る とい う保 証 が な い 場 合 に は 、 ど うし た ら よ いで あ ろ うか?
Dと は 別 に 、 基 底 方 程 式 を 満 足 す る未 知 の 方 向dを 考 え る。 このaを 、 出 来 るだ けDに 近 い よ うに 決 め る な らば 、Dへ 進 み た い と い う要 求 と、 基 底 方 程 式 を満 足 させ た い とい う要 求 と を 、妥 協 きせ る こと が で き るで あ ろ う。
一112‑一 商 学 討 究 才6巻 矛2号
則 ち 、 問 題 は 、Dが 与 え ら れ た と き 、 あキれ
Σ(dj‑Dj)2
■
を 最 小 に す る よ う な 方 向dを 求 め る こ と で あ る 。 右 の 自 乗 和 は 、46σ=1,…, n)を 主 変 数 、dj==Σ 伽4κ(ブ=n+1,…7n十m)を 従 属 変 数 と す る 連 続 函
ノ
数 で あ るか ら、 これ を主 変 数 ゐ に つ い て 偏 微 分 し た もの を零 と お け ば 、
キ
2(d,‑Di)十2Σ(d」 一一D」)b」i=0(∫=1,…,の
n十1
と い う 聯 立 方 程 式 が 得 ら れ る 。(d̀一 一一D,)=Σ(d」 一一Dj)bi,(∵i=」 →bJt
ノ
=1,件 ブ→bji=0)で あ るか ら、右 の 聯 立 方 程 式 は 更 に 、
れキ
Σ(dj‑Dj)bji=0(ゴ=1,…en)
■
の よ う な 見 易 い 形 に 改 め ら れ る 。 こ の 式 の 中 に 含 ま れ て い るm個 の 従 属 変 数 (dn+i・ …,dn+m)を 、d」=12bjんXiCに よ つ て 悉 くn個 の 主 変 数 で 表 わ せ ば 、
■
れ キ れ
Σ(12bj,d.‑Dj)b」,=0σ;1プ ・・,n)
」・・1■
ナ ら れ キ
∴ 一 ΣD,妬 十 Σ(Σ ろ,ib」,)d為=0σ=1,…,n)
■iC=11
こ こ で 、 ・
のナ
Mド ー ΣDjb5,σ=1,…,n)
ノ
晦 ㌢ 鯨(i=1,…,nle
==1,…,n) と お け ば 、
(6c.2)砥 十 ΣMi,d,=0(i=1,…,n)
ノ
と な り、 これ を 解 け ば 、b・asiGdirectionを 一 義 的 に 決 定 す る こ とが で き る。係 数MiiCは 対 称n×n行 列 の 要 素 で あ るか ら、n2個 全 部 に つ い て 計 算 す る必 要 は な く、 約 半 数 のn(n+1)/2個 だ け 計 算 す れ ば よ い こ と に な る。
6d回 帰 法 の 特 殊 型
前 記 の 回 帰 法 で は 、 希 望 方 向Dが 、 基 底 関 係 を満 足 す るか ど うか 不 明 で あ つ
線型計 画問題 の新 しい解 き方(古 瀬)一 一113‑一一 た の で 、 そ れ を満 足 す るよ う な方 向dを 別 に 選 び 出 さ な け れ ば な らな か つ た 。 然 し、Dの 選 び方 を適 当 に す れ ば 、 別 にdを 考 え な くて も、Dの ま ま で 基 底 関 係 を 満 足 させ る こ とが で き る。
そ れ に は先 ず 、 出 発 点 に お い て 負 で あ る よ うな 座 標 に つ い て はDの 値 を 正 に 、 零 で あ る と ころ の 座 標 に つ い て はDの 値 を零 又 は正 に と る。 出 発 点 の 座 標 値 が 正 の と きは 、 そ れ に対 応 す るDの 要 素 の 符 号 は任 意 に 選 ん で 差 支 な い 。
次 に 、 λ の 値 と して は 、 (6d.2)Max‑Xj/1),〔.rj<0〕
'
よ り も 大 き く 、 同 時 に 、 (6d.2)MinXj/‑Dj〔Xj>0,Dj<0〕
」
よ り も小 さい 任 意 の値 を決 め る 。Max‑Xj/D,〔X」<0〕 は 必 らず 正 で あ る か ら、 そ れ よ り も大 き な λ の 値 もま た 、 必 らず 正 で あ る。 そ の よ うな λ の変 域 が 存 在 し な い 場 合 に も、Dの 各 要 素 の 値 を 、 右 の 符 号 条 件 を 守 りな が ら、適 当 に 修 正 す る こ と に よ つ て 、 存 在 す るよ うに す る こ とが で き る場 合 も あ る で あ
ろ う。
そ の よ うな 運 動 の終 点 の位 置 〆 の 値 は 、 Xノ」=x∫ 十1D5(ブ=1,…,n十m)
で 与 え られ 、 負 な る物 を 為 とす れ ば
ぬ …+λD・=吻 弓'〔 ・c'<・ 〕}D・+XiC
≧ κ・+一 誰D・‑o
.'.xliC>0
と な り、 また 、 出発 点 が正 で運 動方 向 が負 で あ る変数 を 鋭 とす れ ば、
tll‑Ut+zDl‑Xl+{吻%毒 〔x'>o・D・<o〕}De
≦ ・Xl+一 毒D・ 一 ・
.'.xie>0
と な る 。Xj≧0,D」 ≧0の 場 合 に はx/jは 勿 論 正 で あ る 。 以 上 に よ り 、 終 点
・一一・114・一 商 学 討 究 才6巻 才2号
κ'の 各 要 素 は 何 れ も非 負 条 件 を 満 足 し 、従 つ て 、一 気 に許 容 域 内 に 突 入 す る こ とが で き る。
Dを 任 意 に選 べ る な らば 、
(6d.3)Dj=一 一一x」(ノ=1,…,n十m)
とす る こ と に よ つ て 、(6d.2)の 最 大 値 と最 小 値 と は何 れ も1に な り、 そ の 運 動 の 結 果 、xノ,は 悉 く0と な る。 然 し なが ら、 これ は 基 底 関 係 を 無 視 して い る
の で 、 一 般 に は 使 用 さ れ な い方 法 で あ る。 け れ ど も、 そ れ を前 記 の 回 帰 法 のD と し て 使 い 、 そ れ に よ つ て 妥 協 的 方 向dを 決 め る こ と は 可 能 で あ る。
(奉 節 に記 され た特 殊 回帰 法 は・何 れ も基底 関係 を無 視 してい るの で・ 出 発 点x及 び方 向Dが 何 れ も基 底 方程 式 を満 足 して い るので な けれ ば 、実 際 の役 に は立 た ない と思 わ れ る。 紹介 者 註記 。)
6e若 干 の負 変数 を零 とお い て方 向 を決 め る方 法
先 ず 、 π 個 の主 変数 κ、,…,物 を任 意 に選 ぶ 〔実 例 では全 部正 値 を与 えて い
る)。 これ を 基 底 方 程 式X」=∂,。+Σ 娠 篇 に 代 入 し て 、m個 の 従 属 変 数
ノ
蜘+、,…,蜘 搬 を決 め る。 そ の うち に は 、 そ の点 が 既 に 許 容 域 内 に あ る と い う 偶 然 の場 合 を 除 い て 、 幾 つ か の 負 値 を と る変 数 が 必 らず 存 在 す る で あ ろ う。 若
し も、 これ ら の負 変 数 の うち 互 に 線 型 従 属 の もの が あ れ ば 、 そ の うち任 意 の 一 つ を残 して 残 りを以 下 の 計 算 の対 象 か ら除 い て お く。
これ ら の負 変 数 の 数 が π よ り も多 い と き は 、 そ の絶 対 値 「κ到 の 大 きい もの か ら順 に 〃 個 を と る。 η 個 未 満 な らば全 部 を対 象 とす る こ と が で き。 る これ らの 選 ば れ た 負 の 従 属 変 数X」 を左 辺 に もつ 基 底 方 程 式b」,・+Σ 娠 簸=0を 聯 立 させ 、 式 の 数 よ り も変 数 の数 η の 方 が 多 い と きは 、 そ れ らの うち の 任 意 の も の を0と お い て 、 式 の数 と変 数 の 数 と を一 致 させ た 上 で 、 こ れ を解 く。 そ の 解
をxノ 、,…,〆 物(予 め0と お い た 変 数 は 、 そ の ま ま0と 見 倣 す)と す れ ば 、 方 向dは 、
(6e.1)d,=xlic‑XiC(le・1,…,n)
に よ つ て 決 定 され る。 従 属 方 向 は 、 この主 方 向 をd」=Σb」 ・d・(ノ=η+1,
ノ
…,π+粥)に 代 入す る こ と に よ つ で 決 定 きれ る こ と、 言 うま で も な い 。(こ の よ うな 手 続 を と る こ と に よ り 〆 点 は κ 点 よ り も許 容 域 に 近 附 くで あ ろ う。)
評 〆
線型計 画 問題 の新 しい解 き方(古 瀬)一 一一115一 方 向dが 決 ま れ ば 、 そ の 方 向 に 方 つ て69節 のS(λ)が 最 小 に な る よ うに ス を決 め る。 必 要 が あれ ば 、 更 に この 点 を 出 発 点 と して 、 同様 の 計 算 を繰 返 す 。
出 発 点 に お け るn,個 の主 変 数 の 値 を悉 く0と お く こ と も可 能 で あ る。
6f運 動 の長 さ に つ い て の一 般 的 立 言
以 上6b‑6eに 亙 っ て 、 方 向dを 決 め る四 つ の方 法 に つ い て 述 べ た 。 以 下 に お い て は 、 λ の 長 さ を決 め る方 法 を 論 じ な け れ ば な らな い 。
方 向dと 出 発 点xと が 基 底 関 係 を 満 足 して い る とす る と 、吾 々 の 狙 い は 、 λの 値 を適 当 に 決 め る こ と に よつ て 、総 て の 変 数 を 非 負 な ら し め る こ とに あ る。
従 つ て 、・これ ら の変 数 の うち で 負 値 を と る各 変 数 の 絶 対 値 の 和S(2,)を 最 小 に す るよ うな λ の 値 を求 め な け れ ば な らな い 。 方 向dが 決 ま れ ば 、S(λ)は λの 一 価 函 数 と な る 。 そ の 導 函 数Sノ ・λ)は 、 λ の 増 加 に つ れ て 、 ヴェク トルdが 、 各Xj=:o単 面 を 正 か ら負 へ 、 又 は 負 か ら正 へ 通 過 す る際 に 、 有 限 値 か ら0へ
又 は0か ら有 限 値 へ と、 不 連 続 的 に 変 化 す る。
も
右 のSCλ)の 代 りに 、 負 値 を と る各 変 数 の絶 対 値 のvarianceを 利 用 す る こ と もで き る 。 こ れ もま た 、 λ の函 数 で あ る。 然 し、6eの 方 法 でdを 決 め る際 に は 、 経 験 上 、S(わ を最 小 に す る λ 決 定 法 が 極 め て 便 利 で あ る 。
6gS(わ を最 小 に す る よ うに λ を決 め る方 法
S(λ)の 値 が 、λの 増 加 に つ れ て ど う変 るか 、 を 考 えて み よ う。 以 下 の 説 明 は 非 常 に 複 雑 だ が ・ 実 際 や つ て み る と 、 計 算 は 極 め て 簡 単 で 、 容 易 に 機 極 化 す る こ と が で き 、 机 上 型 計 算 機 の 操 作 に 慣 れ た 人 な ら 誰 で も 行 う こ と が で き る 。 先 ず 、 若 干 の 存 在 定 理 か ら 始 め る 。
(69.1)若 し 一 ・Σ「dj〔Xj=0,dゴ>0〕 ≦Edj〔Xj<0,dj歪 …0〕
≦ 一 Σ4,〔Xj=O,d5<0〕
な ら ば 、S(わ<S(0)な ら し め る よ う な λ の 値 は 存 在 し な い 。 則 ち 、 出 発 点x か ら 方 向d又 は 一dに 向 っ て 動 い て も 、S(λ)の 値 は 減 少 し な い 。 何 と な れ ば 、 λ>0の 場 合 に は 、 前 提 に よ り 、
S(λ)=一 一Z,Sd」 〔X」<0〕 一 λΣdf〔Xj=0,dj<0〕 ≧0 ま た λ<0の 場 合 に は 、
一一116‑一一 商 学 討 究 才6巻 才2号
S(1)=ZSdj〔Xj=0,d」>0〕 ・+λ∫4,⊂ κ」<0〕 ≧0
と な るか らS(ハ の 値 は λ が0か ら正 又 は負 方 向 に増 して も、決 して 減 少 す る こ とは な い 。
(69.2)若 し 一∫45〔Xj=0,d5<0〕<Sdj〔Xj<0,d5≡ ≡0〕
な らば 、S(わ の 値 を 最 小 にす る と ころ の1の 正 な 一 義 的 値 が 存 在 し 、 そ の S(λ)の 値 はS(0)よ り も小 で あ る。(証 明 後 述)。
(69.3)若 しXd」 〔X」<0,ds菱O〕<‑Xdj〔X」==0,dj>0〕
な らば 、S(わ の 値 を最 小 に す る と こ ろ のZの 負 な 一 義 的 値 が 存 在 し、 そ の 1S(λ)はS(O)よ り も小 で あ る(証 明 後 述)。
若 し、 右 の(69.2)と(69.3)と が 同 時 に 満 足 され る な らぼ 、Aの 最 適 値 は 、 正 負 そ れ ぞ れ 二 つ づ つ 存 在 す る 。 そ の うち 何 れ の方 を 取 るべ きか を決 め る に は 、 以 下 に 述 べ る計 算 法 に 従 つ て 、 そ れ ぞ れ の場 合 のS(λ)の 値 を求 め た 上 で 、 そ の うち の小 さ い 方 を採 用 す べ きで あ る。 但 し、出 発 点 の κ,の 値 が 一 つ も
ノ
零 を 含 ま ず 、 且 つ 、 Σd」〔X」<0,偽 ≧0〕 ≠0で あ るな らぼ 、 そ の よ うな面 倒 臭 い二 重 計 算 をす る必 要 は な い 。 何 と な れ ば 、Σ45〔Xj<0,4,蓬0〕 の 値 が 正 の と きは λ の 最 適 値 は(69.2)に よ り正 、 上 記 の値 が 負 の と きは λの 最 適 値 は(6g・3)に よ り負 、と 、 何 れ か 一 方 に 予 め 決 ま つ て し ま うか ら、 正 負 何 れ か 一 方 だ け に つ い て 計 算 す れ ぼ 十 分 で あ る 。
以 下 、 λ の 最 適 値 の計 算 法 を 述 べ る 。先 ず 、dが(69.2)の 条 件 を 充 た す もの とす る。 最 初 に 次 の γ。 を 計 算 す る。
(6g.4)‑Vo… ≡≡Σ4,〔Xj<0,dゴ ≧≡0〕 十XdJ〔Xj=0,dj<0〕
この 右 辺 は 前 提(69.2)に よ り必 らず 正 、 従 つ てV。 は 必 らず 負 、 で あ る 。 次 に 、 鈎 と め とが 異 符 号 の もの に つ い て
(69・5)λ 計 驚1(螂 ・)
を 計 算 す る 。 λ」は 勿 論 悉 く 正 で あ る か ら 、 そ れ を 小 さ い も の か ら 順 に 並 べ て 、 0<λ(、)<λ(。)<… … と 番 号 を つ け て お く 。 場 合 に よ つ て は 、 同 じ1,i)に 属 す る ブ が 二 つ 以 上 存 在 す る こ と も 考 え ら れ る 。 そ こ で 、 同 じ λ(。)に 属 す る 総 て の d」(そ れ をd.,dβ,… … で 示 す)の 絶 対 値 の 和V(r)を 求 め る 。
線 型 計 画 問 題 の 新 し い 解 き方c古 瀬)‑117‑
(6g.7)V(r)=ld.'十}dβ 十 ・… ・(r=1,2プ … ・・)
こ れ ら のV。,y(、),7(。),… 〜・ の 値 か ら 、 累 積 的 に 、 次 のV〔 。〕,V〔 、〕,V〔 ・〕,……
を 計 算 す る 。
v〔 。〕叢y。
V[ノ 〕≡V。 十7(、)
ー ー
)896( アv〔r〕 ≡ …Σv̀1♪ 十v。
■
ゆ
yヒω〕≡ Σy④ 十y・
ノ 、
こ のV〔 の,V〔t〕デ・・,V〔 。〕の 数 列 は 、V〔 ・〕 が 負 、7ω,…,V(ω)が 悉 く正 、 で あ る か ら 、 初 め の う ち は 負 変 域 に お い て 単 調 増 加 を 続 け 、 或 る 段 階V[,)に 達 す る と 負 か ら 正 又 は 零 に 転 ず る で あ ろ う 。 若 し 、 こ のV(。]が 正 で あ る な ら ぼ 、 そ れ は 全 数 列 中 の 正 の 最 小 値 で あ り 、 そ れ に 相 当 す る λ(,)=Ixr/d,1が1の 正 の 最 適 値 に 外 な ら な い 。 則 ち 、 こ の λω に お い て 、S(λ)は λ の 非 負 変 域 に お け る 最 小 値 を と る 。 そ の λ(r)をS㈹ に 代 入 し た 値S(λ(の)が 零 で あ る な ら ぼ 、 吾 々 は 既 に 許 容 域 内 に あ り 、 正 で あ れ ぼ 、 然 ら ぎ る こ と を 示 す 。
ま たV〔r)=Oと な る な ら ぼ 、S(λ)の 値 は λω とZ(r+,)と の 区 間 内 に お い て 一 定 の 値 を 保 つ 。
而 て 、 こ のS(λ ω)=S(λ(.切)=0は 、 前 の 場 合 と 同 様 に 、1の 非 負 変 域 に お け る 最 低 値 に 外 な ら な い 。
〔69.2の 証 明 〕 出 発 点 κ5が 負 な ら ぼ 、d」 の 符 号 の 如 何 に 拘 ら ず 、 λ の 値 に 十 分 小 き な 正 値 を 与 え る こ と に よ り 、 絢+λ め の 値 を 負 な ら し め る こ と が で き る 。 ま た 、X」 が0でdjが 負 の 場 合 に は 、 λ の 任 意 の 正 値 に 対 し て 、 X」+λd」 は 必 ら ず 負 と な る 。 従 つ て 、
(6g.11)rs(λ)≡.X(x5十 λdj)〔Xj<0,4,i義0〕
十2(x5十Adj)〔Xj=0,d5<0〕
の 値 は 、 λ に 十 分 小 さ な 正 値 を 与 え る な ら ぼ 、 負 と な る で あ ろ う。 こ の 右 辺 を 整 頓 し て 、 λXdj〔Xj<0,4,≧iO〕 十 λXdj〔Xj=0,dj<0〕 と 、
一一一118‑一 商 学 討 究 才6巻 才2号
・ΣXj〔Xj<0,4'≧iO〕+XX」 〔κ」=0,d」<0〕 と に 分 け れ ぼ 、 前 者 は(6g.
4)に よ り 一 λγ。 に 等 し く 、 後 者 は 一S(Oう1i1ii‑Xix」i〔C」<0〕 に 等 し い 。 そ れ 故 、
‑S(λ)=‑S(0)一 λV。
(6g.12)∴S(λ)=S(0)十 λV。
こ の 関 係 は 、 少 く と も一 つ の 変 数 が 、 λ の 増 加 に つ れ て 、 始 め て 負 か ら 正 へ 、 又 は 正 か ら負 へ 変 化 す る 瞬 間 ま で 、 持 続 さ れ る 。 そ の 瞬 間 に お け る λ の 値 は 、 lj=1x」/4囲 〔Xjd」<0〕 で 定 義 さ れ る み の う ち 最 小 の も の に 等 し く 、 従 つ て 、 λ(、)に 一 致 す る 。 ・
そ の λ(、)に 該 当 す る 勾 が 編 で あ り 、 且 つ 、 そ れ が λω に お い て 負 か ら 正 に 移 る も の と す れ ぼ 、S(λ)の1に つ い て の 微 係 数 、 則 ちV。 の 値 は 、Aが 0<λ<λ(、)の 区 間 に あ る 間 は 一一 定 に 保 た れ る が 、 λω を 超 え る 瞬 間 か ら 一d.が 脱 落 し 、V。 の 値 は 従 つ てd.(>0)だ け 大 き く な る 。 反 対 に 、Xdiが 正 か ら 負 に 移 る 場 合 に は 、V。 の 中 に 新 た に 一d.(d.<0)が 加 わ つ て き て 、V・ の 値 は 一d.だ け 大 き く な る 。 則 ち 、 何 れ の 場 合 に お い て も 、V。 の 値 は 、V。 か ら
γ。+ld.)に 増 加 す る 。minλ 」 に 該 当 す る 変 数 が 二 つ 以 上(Xdi,xβ,…,κy) あ る 場 合 に は 、14訓 の 代 り にid.)+14副+…+]dγiを と れ ぼ よ い 。 然 し 、 何 れ で あ ろ う と そ れ はV(、)に 外 な ら な い か ら 、 総 て の 場 合 を 通 じ て 、dS(わ /dλ の 値 はV。=V(。 〕か らV。+V(、)=Vi〔 、〕 に 増 加 す る 。 二 番 目 の 極 小 ろ 、
則 ち λ(。)、に つ い て も 同 様 の こ と が 言 え る 。 故 に 、 一 般 的 に dS(λ)
=V〔r〕 〔λ(r)<1<λ(r+ノ)〕dλ
が 成 立 つ 。
他 方 、(6g.8)式 の 説 明 の 際 に 述 べ た よ う に 、 数 列V(。 〕,Vi〔、〕・瑳 。〕,…… は 、 初 項 は 負 で あ る が 、 負 変 域 内 に お い て 次 第 に 増 加 し 、 或 る 番 号 か ら 先 は 、 正 域 罷 お い て 単 調 増 加 を 続 け る 。 ま た 、 同 時 に 、S(。)≡ 捌 κヨ 〔Xj<0〕>0で あ る か ら 、
S(λ)=S(0)十 λV〔r〕
で 表 わ き れ るS(わ の 値 は 、A=Oに お い て は 正 で あ り 、 λ の 増 加 に つ れ て 次
舗
