[03_06]九州大学大型計算機センター広報 : 3(6)
15
0
0
全文
(2) FACOM230‑60LIPSV‑1に. つ い て. 線 型 計 画 法 の ア プ リケ ー シ ョ ン ・プ ロ グ ラ ム ※)襲. 香. 1.は. 田. 徹. ※. 小. 野. 漢. 子. じめ に. 一 般 的 な 線 型 計 画 法 を 解 くア プ リケーショ 近 くユ ー ザ にリリー 使 用 法 、 第4節. ン プロ グ ラ ム と し てFACOM230‑60LIPSV‑1が. ス さ れ る予 定 で あ る 。 そ こ で 第2節. で 線 型 計 画 法 に つ い て 、 第3節. で 使 用 例 に つ い て 述 べ る 。 実 際 の 使 い 方 を知 り た い 方 は 、 第3節. で 、V‑1の. 、 第4節. だ け読 ん で. 下 さ い。. 2.線. 型 計画 法 の概 要. 線 型 計 画 法 に つ い て は 、 す で に 数 多 くの 文 酬1)一 一(4)があ る の で 、 詳 し くは 、 こ れ ら を参 照 さ れ た い 。 こ こ で は 、 第3節. で 述 べ るLIPSV‑1の. 使 用 法 と の 関 連 か ら 、 シ ン プ レ ック ス法 、 改 訂 シ ン プ レ ッ. ク ス 法 に 関 連 す る術 語 の 説 明 を 中 心 に し て 行 な う。(術 語 は 、 参 考 文 献(ユ)にほ ぼ 従 う 。). 2.1シ. ンプ レ ック ス法. 線 型 計 画 法 とは 、い. くつ か の 線 型 の 制 約 式 の も と で 線 型 の 目 的 関数 を最 小 ま た は 最 大 に す る 非 負 の. 最 適 解 を 求 め る 問 題 で あ る 。 こ こ で 制 約 式 と は 、 次 の3つ 第 一 の 型(ま. た はL型)Σà∫xノ. 第 二 の 型(ま. た はG型)Σa♂. '」1. の 型 の 任 意 の 組 合 せ で あ る。. ≦bi(bi≧o,i=1,…,Ml)(1) ノ≦bi(bi≧0,i=Ml+1,・. …,Ml+M2)(2>. 71 第 三 の 型(ま. た はN型)ΣaガXj=bi(bi≧0,i=M1+M2十1,・. …,Ml十M2十M3・. ・m)〈3). J=1. ま た 、 目 的 関 数 は 次 の よ う に 表 わ せ る。 ノ ー ￡ ・、・ ・、(4) ノニ. こ こ で 、aδ を 制 約 係 数,biを. 制 約 量,c∫. を コ スト 係 数xメ. を真 変 数 と よぶ ・. ま た 、問 題 に よ っ て は 、真 変 数 が 、 負 の 値 を と り う る場 合 が あ る。 こ の 時 は 、xノ を 次 の よ う に分 解 し て x、‑x、. ㌔x三x∫+≧o,x∫‑ko〈5). (1)〜(4>に代 入 す る。 以 上 の事 よ り、真 変 数X」 を非 負 の 条件 の 下 で解 い て も一 般 性 を失 わな い。 まず シ ンプ レ ック ス法 の 原 理 を考 え る。 簡 単 の た め 、2変 数 の場 合 に つ い て行 な う。 縦九州 大 学工 学 研 究科 通信 工 学専 攻 繁 巌九州 大 学 大 型 計 算 機 セ ン タ ー研 究 開 発 部.
(3) 目 的 関 数f(x、)=3x、+2x2. 図:制 約 領 域 と 目的 関 数 の 変 化. 斜 線 を 施 し た 制 約 領 域 を 可 能 解 領 域 と よ ぶ 。 図 か ら 明 ら か な よ う に 、目 的 関 数 を 最 適 に す る の は 、少 な く と も可 能 解 領 域 の ○ 印 の つ い た 点 で あ る 。 こ れ を端 点 と よ ぶ 。(最 適 解 が 一 義 的 に 定 ま ら な い 場 合 は 、(た と え ばf(x)=x、‑x2)端 端 点(こ. 点 と端 点 を 結 ぶ 直 線 が 最 適 に な る 。)ゆ え に 最 適 解 を 求 め る に は 、. れ を 可 能 基 底 解 と よ ぶ)を. 知 る 必 要 が あ る 。 こ の 端 点 は 、 基 底 解 を 求 め る こ と に よ り知 る. こ と が で き る。 こ の 基 底 解 は 次 の よ うに して求 め る。 (1>〜(3>に 新 た な 変 数(こ. た だ し 、Mは. れ を ス ラ ッ ク 変 数 と よ ぶ)Si(i=1,…,m、+M2),Si'(i=M、+M2+1,. 最 小 値 問 題 に 対 し て は 正 な る 大 き な 値 、 最 大 値 問 題 に 対 し て は 負 な る 大 き な 値 とす る 。. こ のMはsピ(i・Mi+m2+1,…,繍. が 少 し で も正 の 値 を と れ ば 目 的 関 数 の 値 を最 小 値 問 題 に 対 し て は 非. 常 に 大 き な 値 に し 、 最 大 値 問 題 に 対 し て は 非 常 に 小 さ な 値 とす る 。 こ れ に よ っ てSi'(i=Mx+M2+1, …. ,m)の. 値 は0に. な る(罰 金 法)。 わ か りや す くす る た め に ⑥ 〜(9)を 次 の よ う に 書 き か え る ・.
(4) (16)にお い て 、N個 の 変 数 の う ち 、m個 を 残 し て 、n個 を0と 個 と な り 、m個 のm次. お く と変 数 の 数 、制 約 条 件 の 数 、 と も にm. 元 連 立 一 次 方 程 式 に な る。 こ の 方 程 式 の 解 を 基 底 解 と よ ぶ(こ. ま ら な い と き が あ る が1)、 こ こ で は 触 れ な い)。 基 底 解 の 数 は 、 た か だ か,q個 底 解 の う ち 、 各 変 数 の 値 が す べ て 非 負 に な っ て い る 時 、 こ れ を 可 能 基 底 解(端 ッ ク ス 法 は こ れ ら 端 点 の う ち 、 あ る 端 点(こ. の解が一義 的に定. 存 在 す る。 これ らの 基 点)と. の 最 初 の 端 点 を 初 期 端 点 と よ ぶ)か. よぶ 。 シ ンプ レ. ら 出 発 して 、 目 的 関. 数 を 改 善 す る よ う な 端 点 を順 次 探 索 して 最 適 解 を 得 る 方 法 で あ る。 し た が っ て 、 最 初 に 初 期 端 点 を 探 し 出 す 必 要 が あ る 。 こ れ を 第1段 ぶ 。 初 め に 第H段 i)第H段. 階 とよ. 階. 階 につ い て 述 べ る。 あ る 一 つ の 端 点 をy1=〔y、,y2,…,yN〕Tと. が あ る が 、 こ のn個. の 零 を う し ろ に 寄 せ て 、 残 り のm個. カ. z1=〔z、,z,,…,zm,Q,・. こ の 順 序. 階 と よ ぶ 。 次 に 順 次 よ り よ い 端 点 を 見 つ け 出 す 操 作 を 第H段. を 入 れ 替. え る こ. 係 数V、,V2,…,VNがW、,W2,…,礪Nに. …. と に. よ っ. す る 。y、,…,yNの. う ち 、 少 な く と もn個. を 前 に つ め 、 こ れ を新 た にZ1と. 零. す る。. 〕T(20). て 、 制 約 係. 変. わ る. 数 ベ. と す. ク. ト ルa、,a2,…,aNがd、,d2,…,dNに. 、. コ ス. ト. る 。. こ こ でlh毒 の 上 の 添 字 は 、 基 底 行 列D、 の 下 の 添 字 に 対 応 し て い る が 、 混 乱 の な い 限 り 、lh毒 をlhkと 書 く.
(5) 任 意 の 非 基 底 ベ ク トル をdkと. と な る 。 こ のz2が. す る と 、(21)一(24)×&よ. 、 端 点z1に. 相 隣 り合 う端 点 に な る た め に は 、. か つ 、 以 下 に 示 す 正 な る 硫 を 定 め る と 、ZXが. す な わ ち 、z2は. り. 新 た な端 点 とな る。. 、1番 目 の 要 素 が 零 と な り 、k番 目 の 要 素 が 正 と な る 。. (㈱ に お い て 、hk,i<o(i・1,…,m)の. 時 は 、z2は. 端 点 とは な らず 、 しい て 言 え ば 無 限 遠 点 に 端 点 が 存. 在 す る 。 こ の 場 合 、 目 的 関 数 を ど れ だ け で も 改 善 す る こ とが で き 、 最 大 値 、 最 小 値 問 題 に 対 し て 、 そ れ ぞ れ 、 最 大 値 、 最 小 値 が 有 限 な 値 と し て は 存 在 し な い 。) 次 に2つ. の 端 点zl,z2に. f'(z2)=w1(̀'zコ. 対 し て 、 各 々 の 目 的 関 数 の 値 を比 較 し ょ う。. ー θk,lh,,k)十w2(z1一. =(W、v'Z1+W、Z、+…. ==f'(z1)一. θk,ih2,k)十. …+WmZ. m)一. 新 し い 基 底 ベ ク トル(こ. vectordkを. …Wmhm,k‑‑Wk>. ヘ ア ま た 最 大 値 問 題 に 対 し て 、9k‑Wk〈0な. れ をchosenvectorと. よ ぶ)に. て 、 新 し い 非 基 底 ベ ク ト ル(こ れ をremovedvectorと 改 善 す る た め に 、iUk‑Wkiの. ・ 一θk,ihm,k)十wkθk,1. … … … 十wmhm,kニwhk(31). ゆ え に 、 最 小 値 問 題 に 対 し て 、 寝ズーWk>0、 トルdkを. 十wm(z,n‑・. θk,1(W、h、,k+W、h、,h+…. θk,s(Uk‑Wk)(3①. こ こ で 、uk=wlh1,k十w2h2,k十. … …. 大 き なdhを. る非 基 底 ベ ク. 選 び 、 基 底 ベ ク トルdlを. よ ぶ 〉に す る 。 こ こ で よ9能. 率 よ く 目的 関 数 を. 選 ぶ 。(話 の 都 合 上 、 順 序 は 逆 に な っ た が 、 は じ め にchosen. 選 び ㈱ の θkを計 算 す る こ と に よ り 、removedvectordiが. 決 ま る 〉こ れ ら の こ と を 繰 り. 返 し行 な い 、 改 善 し よ うが な く な っ た ら 、(す な わ ち最 小 値 問 題 に 対 し て は 、Ux‑Wk>0を 基 底 ベ ク トルdkが. 追 い出 し. な い と き 、 最 大 値 問 題 に 対 し て は 、Uk‑Wk〈Oを. が 最 適 解 に な る 。 こ の 第ll段 階 は 、 実 際 に は 、 シ ン プ レ ッ ク ス 表(制 の 要 素 を 枢 軸 要 素(PlvorrALELEMENT)に. 満 た すdkが 約 係 数 行 列Aに. 満たす非. な い 時)そ. の端点. お い て 、9行k列. 目. し て 、掃 出 し を行 な う)を 用 い て 行 な うが 、 こ こ で は. 述 べ な い。 ii)第1段. 階. 初 期 端 点 は 、 制 約 式 が 第1、 ハ. y1=[o,・. ハやま. ハヤあコ. ・ 。 ・ ・ ㌧o,b.・ ・ ・ …b搬 もb痛÷瓜撞 …. 第3の. 型 の み で あ る な ら、 だ. ヂ・ ・ …,b,]〈M2=0)〈32). と す れ ば 、 こ れ が 端 点 と な る 。 し か し 、 制 約 式 が 第2の. 型 を含 む と きは 、 簡 単 に は求 ま らず 、次 の よ. うに す る。 ⑥ 〜 ⑨ に 導 入 し た ス ラ ッ ク 変 数 の 他 に 、 さ ら に 新 た な 変 数 μ̀(こ れ を 技 巧 変 数 と よ ぶ)を. 導 入 す る。.
(6) ΣaiJ'xノ. ーsi+μ. 一M1=bi(bi≧0,si≧0,μr切,≧0,i="m1+1,…,㎞1+m・)(33). 」=1. (6),(8),(33)の. 条 件 下 で. 9='μ1十. μ2十 … … 十 μ 飢、(34). を 最 小 に す る 新 た な 問 題 を 考 え る 。 こ の 問 題 の 初 期 端 点 はyN+1=μ ↓9丑 ∪ と 、Y1=[0,0,…,O,b1,…,b.,,0,・ を 選 び 、g=0と. な る 最 適 解 を 第H段. 1,…,M2)が. 】,yN+2=μ2,…,yN+m、=μ. 。,と す る. ・ 也m・+・+f「 ・ln+inl+m・ ・+inl+ml+1↓NJIN+,・ ・・…,0,b.,+ml+1,・ ・・…,bN,bm,十1,…,b,,+m,](35) 階 の 操 作 を 行 な う こ と に よ っ て 得 る 。(g=0と. な い 場 合 は 、 原 問 題 は 可 能 解 を 持 た な い 。)こ. の で 、 こ れ を も と に し て 、 第H段. な る 解 μ 、=o(i=. の最 適 解 は原 問題 の 初 期 端 点 に なって い る. 階 の 操 作 を行 な えば よ い。. ま た 次 の よ う に し て も よ い 。 原 問 題 の 目 的 関 数(9)の ロを g'=f「+M'ΣPt,(た. だ し 、M'の. 代 り に ㈲ のg'を. 値 は(9)と. 目的 関数 を と り、. 同 じ よ う に き め る 。)(36). 1ニ1. 初 期 端 点 と し て は 、(35)のy1を 2.2改. と り第n段. 訂 シ ン プ レ ッ ク ス法. 階 を用 い る。. 初 期 端 点 の 求 め 方 は2.1節. し て 行 な う。(22),(24),(31)よ. 階 は 次 の よ うに. り. へ りユ z=D】d(37). と 同 じで あ る 。 第H段. ユ. h毒=D,dk(38). へ. Uk=wlhk=(wDli)dk(39). Uk‑Wk=wD三1dk‑Wk(40) と な る 。 非 基 底 ベ ク ト ルdkに 基 底 ベ ク ト ルdiを. つ い て 、(4①のUk‑Wkを. 計 算 し て 、新 し い 基 底 ベ. 追 い 出 し て 新 し い 非 基 底 ベ ク ト ル と す る 。 こ れ ら の ベ ク ト ル の 選 び 方 は2・1節. じ よ う に し て 行 な う 。 そ れ に と も な い 、 基 底 行 列D、 がD、 dm],h毒. ク ト ル を 探 し 、そ し て 、. に 変 わ る 。 こ こ でD、=[d・,d・,…,dl,…,. 、=hk,. D,=[d、,d2,…. … 噸dk,…. …,dm]で. 、 こ れ らの 関 係 は 次 の 通 り、. れ 100 010 B、=00hlli(m次. の 正 方 行 列)(41). ::0 001 と す る と 、D、B、=D、(42). りユ. へユ. ゆ え に ・D・‑BIID・(44) さ ら に 基 底 ベ ク トル の 入 れ 替 え を 行 な う と 、. と同.
(7) ゆ. ㈱. D3驚B三1D計. ゆヌや ユ. p回 基底 ベ クトル の 入 れ 替 え を行 な って最 適 解(そ の端 点zが. 最 適 解 か ど うか の 判 断 は 、シ ンプyッ ク リおや ま. ス 法 と 同 様 に ㈱ のUk‑Wkの. 符 号 を す べ てkに つ い て 調 べ る。)を 得 た とす る と、そ の 最 適 解zは. 、. とな る。 以 上 の こ と か ら 、Dブ,Bが. を 知 る と 、シ ン プ レ ッ ク ス 法 と 同 じ よ う に 、こ れ ち の 操 作(逆 行 列 の 掛 算 〉. を繰 り返 し行 な う と 最 適 解 が 得 ら れ る こ と が わ か る 。 こ の 方 法 を 改 訂 シ ン プ レ ッ ク ス 法 と よ ぶ 。 3.'FACOMLIPSV‑1(s>について 3.1V‑一. 一1の 機 能 ・特 長. (1)制 約 係 数 ・制 約 量 ・ コ ス ト係 数 の 非 零 要 素 の み を 係 数 入 力 とす れ ば よ い 。 ② 制 約 式 に お い て 、 ス ラ ッ ク 変 数 ・技 巧 変 数 を 入 力 と し て い れ る 必 要 は な く 、 制 約 条 件 式 の 型 を 指 定 し さ え す れ ば よ い. (3)解 法 は 計 算 機 に 適 し た 改 訂 シ ン プ レ ッ ク ス 法 で あ る 。 い. ゆ. ユ. 〈4)基 底 行 列Dの 逆 行 列Dの 保 存 は プasダ ク トフォー ム で あ る。 2‑2節 よ り新 しい 基 底行 列 は 、前 の基 底 行 列 と、行 列Bを 知 れ ば よい。p回 基 底 ベ ク トル の 入 れ 替 え を へ. ユ. 行 な え ば 、(新 し い 基 底 行 列 の 逆 行 列Dp+1は. ゆ ヘ. ユ. ユ. 、>Dp+i・Bp恥. ユ. ゆ. ユ. と な る の で あ る が 、前 の 基 底 行 列Dbを. 計 算せ ず に 、 ‑1. ̲1̲1‑1‑1. D,.、.i・BpB,..三. … … 取D,よ. り 、Bユ,Bm…. こ れ を プ ロ ダ ク トフ ォー ム とよぶ 。 す る と、. …,Bpを. も と に し て 計 算 を行 な え ば よ い こ とが わ か る。.
(8) よ り、hikl,h論,…. … …,hPkpだ. け を 記 憶 し て お け ば よ い こ と に な る。 こ のh㌦iを. η ベ クFル. と よぶ。 (5)マル チ プ ラ イ シ ン グ の 機 能 が あ る。(新. た に 基 底 に 入 れ る 非 基 底 ベ ク トル の い くつ か を イ ン コ ア. に バ ッ フ ァ リ ン グ し て サ ブ セ ッ ト を 作 る。 そ の サ ブ セ ッ ト を も と に し て 、 最 適 解 を 求 め る 。 そ の 最 適 解 が 、 全 体 の 変 数 で 最 適 に な っ て い るか ど う か を調 べ る 。 な って い な か っ た ら新 し い サ ブ セ ッ トの も と で 同 じ こ と を 繰 り返 す 。 こ の よ う に す る と 、 計 算 が イ ン 灘 ア で 行 な え 、 計 算 時 間 を短 縮 で き る。) (6)リ イ ン バ ー シ ョ ン の 機 能 が あ る。 ノ. プ ロ ダ ク ト法 に お い て 、 基 底 の 入 れ 替 え 数Pが. 大 き くな る と. ま. Dpを. 逐 次B,,恥,…. …,Bpを. 初 期 基 底 行 列Dpを. も と に して 計 算 す る の は時間 が か か る の で 穂 圃 か 基 底 を 入 れ 替 え る と. 作 り 直 す 。 す る と η ベ ク トル の 数 を減 ら す こ と が で き る。. (7)ク ラ ッシ ン グ の 機 能 が あ る 。. 技 巧 変 数 を な る べ く早 く基 底 変 数 か ら追 い 出 し て 第1段. 階 での. 操 作 を 簡 単 に す る。 (8)Dualな. 解 が 求 め ら れ る。. ⑨ マ ル チRHS(制 (10)制約 量,コ. 約 量 〉 、 マ ル チ コ ス トが で き る 。(制 ス トの レ ン ジ ン グ が で き る。(最. 約 量,コ. ス トを 変 え た と き の 解 が 求 ま る}. 適 基 底 の 内 容 が 変 わ る こ と な く 、RHS;コ. ス トの. 値 が 変 化 で き る範 囲 を 求 め 、 そ れ ら の 値 を 越 え た と き、 基 底 か ら出 て 行 く変 数 名 を求 め る こ とが で き る。) 以 上 の よ う な 特 長 が あ る が 、 し か し 次 の よ う な制 約 が あ る 。 (1)入 力 デ ー タ 形 式 が カ ー ドの み で あ る。 (2)カ ー ドフ ォ ー マ ッ トに は 、 か な り の 制 約 が あ る。 (3)出力 と し て は 、 ラ イ ン プ リ ン タ ー の み で あ る。 (4)パ ラ メ い1ッ 以 上4つ に 脇. クLPな. どの 感 度 分 析 は行 な え な い。. が 大 き な 欠 点 で あ る が 、 近 い将 来 、(1)を 解 決 す る機 能 を 持 っ たV‑2の. シス テ ム がユ ー ザ. 一 ス され る予 定 で あ る。. 3.2V‑1の. 使用方 法. ユ ー ザ が 用 意 す べ きデ ー タ を大 別 す れ ば 次 の 三 通 り で あ る 。 (1)コ ン トロ ー ル カ ー ド ② コ ン トロ ー ル デ ー タ (3)イ ン プ ッ トデ ー タ. 3.21コ. ン トロ ー ル カ ー ド. コ ン トu一. ル カ ー ドはLIPSシ. タ ー に 指 示 を 与 え る カ ー ドで あ る 。 col.1か. らcol.72の. 間 に 次 の 要 領 で 書 く。. ス テ ム を動 作 させ る た め に 、モ ニ.
(9) ¥NO ¥QJOB ¥LIPS (コ ン トロ ー ル デ ー タ) ¥IDATA (イ ン プ ッ ト̀デー タ) ¥JEND. 3.2.2コ. ン ト ロ ー ル デ ー タcol,1か. (1)コ メ ン トカ ー一ドcel.1に"ズ. らcol.72ま. で の 間 に 次 の 要 領 で 書 く。. の あ る カ ー ドで ユ ー ザ が 注 釈 文 と し て 用 い る。 コ ン トu一 ル. デ ータ の 中 に で も 、 イ ン プ ッ トデ ー タ の 中 に で も 入 れ て 用 い る こ と が で き る。 ② コ ン トロ ー ル カ ー ド. コ ン トロ ー ル デ ー タ の は じ ま り を 次 の よ う に 書 く、piに ま た は"MAX"を. は"MIN". 入 れ 、 そ れ ぞ れ 最・ 』 ・ 値 問 題 、 最 大 値 問 題 を示 し 、p2. CONTROL〈Pl,p2) は イ ン プ ッ トデ ー タ ー を リ ス トす る か 否 か を そ れ ぞ れ 、"LIST","N OLIST"で. 指 示 す る 。p1,p2の. (3)プ ロ セ デ ュ ア カ ー ド. パ ラ メー タ は省 略 で き、 そ の と きは 、 そ れ ぞれ 前 者 の 方 を とる。. こ れ ら の カ ー ド を 省 く と標 準 の プ ロ セ デ ュ ア で 行 な う。. (。)クラ ッシ ン グカー ド. ク ラ ッシ ン グ を孝 テな う か. ド. 鷹. (b>制 約 量 レ ン ジ ン グ カ ー ド. 制 約 量 に 関 す る 感 動 分 析 を行 な う カ ー ドRANGERHS. (c)ロ ス ト レ ン ジ ン グ カ ー ド. コ ス トに. (4)代 入 文 カ ー ド. 〃COSTRHS. 代 入 文 カ ー ドは 、LIPS60シ. 代 入 数 値 の 書 き 方 は 、FORTRANの. ス テ ム に 問 題 を 解 く計 算 上 の 指 示 を与 え る 。. 記 法 に 従 う。. 代 入数値 の型. XEPS. ReaI. 誤差 判 定 基 準(こ の値 以 下 は零 とみ な す 〉. 2.OE‑12. XCRITE. Real. 収 束 判定 基準(目 的 関数 の相 対係数 がこの値 以下 は零). 2.oE‑1o. XNOINV. Integer. イ ンバ ー トを行 な う掃 出 し回数. XNOUT. IRteger. 何 回掃 出 し を行 な え ば 中 間 結 果 を出 す か を示 す数. XPRICF. Integer. (5>デ ー タ 転 送 カ ー ド 端 を 囲 ん だ8文. 字 以 内(ブ. 内. 容. X一 変 数 名. り ベ ク トル を コア 内 に読 み 込 む 本 数. 省略 した と き.の値. 50. a. 1 10. 与 え る 問 題 の 、 問 題 名 、 目 的 関 数 名 、 制 約 量 名 を,"▼ … … ▼"の ラ ン ク も含 む)の. 文 字 列 で 与 え る。. よ うに 両.
(10) (註)"▼"はEL型,H型. (6)タ イ トル カ ー ド "(. … …)"の. 問 題 に 対 す る標 題(ラ. で は"@"を. 用 い る、. イ ン プ リ ン タ ー に 出 力 さ れ る と き 、初 め に 打 出 す 。)を. よ う に 両 端 を 囲 ん だ64字 以 内 の 文 字 列 で あ ら わ す 。 こ の カ ー ドを 省 略 し た と き。 ,. (7)コ ン ・ トロー ル エ ン ドカー. 以 上7種. コ ン トロ ー ル デ ー タ の 最 後 を示 す 。. ド. 類 の カ ー ド が あ り 、(2>と(7)は. 3.2.3イ. ン プ ッ トデ ー タ. (1)見 出 し カ ー ド. 必 ず 用 意 しな け れ ば な ら な い。 ほ か は 省 略 可 能 で あ る。. 制 約 行 列 の 行 ・列 名 、 制 約 量 ・ 目 的 関 数 名 、 そ れ ら の値 を 与 え る。. こ の カ ー ド は 、 そ の 後 に 続 く デ ー タ カ ー ドの 種 類 を示 し、coLlか. ら 書 く。. こ の カ ー ド の 後 、 制 約 式 ・目 的 関 数 名 を 与 え る。 〃 …. 〃. 、 変 数 名,非. 零 の 鋤. ベ ク トル ・ コ ス ト係 数 を 与 え る 。. 、制 約 量 を与 え る。. イ ン プ ッ トデ ー タ の 終 わ り を示 す 。 (2)デ ー一タ カ ー. ド. a.NAMEカ coL15か. らcol.22の. ー ド. 例 に 示 す よ う にcol.1か. らcol.4の. 間 に 、 す で に コ ン ト ロ ー ル カ ー ドXPROBで. 聞 に"NAME"と 与 え た8文. 書 き、 字 以 内 と同 じ内容 を. 書 く。. b.ROWSデ. ー タ カ ー ド. 左 に 示 し て い る よ う に 、col.5か 1,第2,第3の. 制 約 式 名 を 書 き 、col.2か. れ そ れ に対 応. し て"N","L","G","E"を. 数 名 は 、 す で に コ ンロー 同 じ内 容 を 書 L,DGな. らcol.12の. ル カ ー ドXOBJで. く。 ほ か に 、N,L,G,Eに. ど と 書 く こ と が で き る が15)こ. 間 に 目 的 関 数 名 、第 らcol.4の 書. 問 に 、 そ.. く。 た だ し 、 目 的 関. 与 え た8文. 字 以 内 と. 対 応 す る 所 にDN,D こ で は 省 略 す る。.
(11) c.COLUMNSデ. ー タ カ ー ドai」. ベ ク トル の 列 名(す. な わ ち変 数 名)を. 定 義 し、 こ の 列 名. に よ り、 制 約 係 数 行 列 要 素 の 値 、 コ ス ト係 数 値 の う ち 非 零 要 素 を与 え る だ け で よ い 。 ま た ス ケ ー ル す る こ とが で き る が 、 こ こ で は 省 略 す る 。 数 値 の 型 は 、 整 数 、 実 数 型 の ど ち ち で も よ く 、FORTRAN の 記 法 に 従 う。. こ の デ ー タ カ ー ドの 順 序 は 次 の よ う な 規 則 が あ る 。 あ る 列(変. 数)の. 名 前 を定 義 し 、 す で にROWSデ. み に つ い て 、 行 名x数. 値 を そ れ ぞ れ 、 フ ィー ル ド3・4、次 に ま た 同 様 に 、 フ ィ ー ル ド5・6に 書 く。. (但 し 、 フ ィ ー ル ド5・6は 再 び フ ィ ー ル ド2で. ー タ カー ドで 定 義 し た 行 名 の う ち 、 非 零 要 素 の. オ プ シ ョ ン フ ィ ー ル ド、 そ の 列 に 関 し て 、2つ. そ の 列 名 を 書 き 、 残Dの. 以 上 の 非 零要 素 が あ れ ば. 非 零 要 素 を 同 じ よ う な フ ォ ー マ ッ ト で 書 く。 こ の よ う に. し て 非 零 要 素 の 制 約 係 数 を 書 い た あ と 、 そ の 変 数 に 対 す る 欝 的 函 数 が 非 零 で あ れ ば 、 フ ィ ー ル ド3・ 4ま 第4章. た は フ ィ ー ル ド5・6に. 書 く。 こ の こ と を そ れ ぞ れ の 変 数 に 対 応 し て カ ー ド を作 る 。 詳 し く は 、. の 実 例 を参 照 の こ と。. イ ン プ ッ ト ・デ ー タ の 順 序 が 上 の よ う な 規 則 と違 う と 、エ ラ ー メ ッセ ー ジ を打 ち 出 さ ず に 、 読 み 飛 ば す 場 合 が あ る か ら 十 分 注 意、を 払 う必 要 が あ る 。. 4.V‑‑1の. 使 用例.
(12) VOL3No.6広. 報. ,;16L,,、. 。C.,丁R。 ・[. IFACO・‑230‑60LP .L. ∴. 、)、,、 ヒ,,AT,1,,、T'、,、T^ll,RR。RLIS'iLIDA・. .V・ ・1L一 ユ.、. 一 一一 一一.一 一. …. 「tt冒. 料. ・2・・'..,・G‑「. 'l. →TITLETypeoutl. 且ON‑I. 一一・.一一一.・.一.一..一. ‑"…t'一. 一. 。........LINEARPROGRA胆INGPROBLEM.45‑08‑21PAGE1. 1‑CONTROしRFSULT(ONりi下 l..一. 資. 一.一. 一一一一. ・…. 一一 ・一一一一.一. 一一一一一. 一.一一. 一. 一. 一一 一. ・一. ・ 一一 一・一一. 一一 一. ・. 一一 一. ・. 一・".』. 『. 一 一一t,‑J‑』'一. …‑1t.一. 凶一.L一. 一'一. 一.. 『̀『幽 PRdBじEMTYPE+t∴. ∴. PROBL.EMNAIE・. 一̀'tlAx『;i:ISTH't「. '「'「. 一. 『'』. 一'一. 』. …. 『.一'"t‑"‑T…. 「F. 。.・PROB鴫002. .. OBJヒ 幽 一'『. ⊂T.FUN(NA画E:・..DUAしSUMV. 『 R日. ..一...戸. ≦NAriE'‑』. ∴.'."DU.へLAHSN'…'『. 「馳1.1.''"』. 『‑‑一. 貞・e・LEMTITしEL….s'.t..一.L艮NEAR.PROGRAY「AINGPR。Bt. ・. 督 脅曇OplIONALF,ROCEr)UkE菅. 督管. 冒騨. ・EMI脇. プ ロ セ デ ニ ア カ ー ドLを省 い 」た の でSTANDARDζ. 幽'‑‑"圃. 補. 』'「.』. τ憂襯 1脇. 一. 『. 一'『. 。7省. な るb. STANDARD. 骨 静督VAしUEoF⊂ONSTANT骨. v. 槻曇. 省 略 し'た と き のf直 と な る;. VA山EOrFPSIRON̲.0.200。. ELA卜. 。0。Of‑11VAしUヒOF⊂RTTERION・. …0・2000。0。OE"。9. NUM、3EROFINVERT̲,50NUMBEROFPRICF・. ….1。. NUMBrROFOUTpUT̲,1NUr・BEROFSAVE・. …10000. ・SFTIME....00HOO卜111S10rALT1・. ・tF・. .1LJr}. …. 。Oti。OMl1S'瀦. は]ア. 楠. 時 間 ・そ 賭1螺. 計 コ ア,'IEeema. .'2[)ヱ5{dl監11[/1、. 骨 「INPUTDATAL置ST軸 '一 冒"ザ. し 21 骨L22 iNAMヒPROH‑002."1』.'『. 『LU『.2』3'. ...、.ROwS..し24一. コ ン トロー ル デ 『 タ('7え た の と「 酉】じ 内 容 に す る ・ND 一一コ ン トロ・一ル デ ー タ で 与 え た 目 的 関 数 名 と 同 じ内 容. UAしSÙ"V...nt‑L25・ GDUALRelO.. .に. す る。LD. UAしRW1..』. 一.. しDUAしRW2 GDUAしRW3.一'."「.'"『‑..」'. 「 「』. .LDUALRft4 'C OLUMNS̀し211.".國 DUALVlDUAしRw。1・00000L212 .VlDUALSUMV1・0.. .tDUAt ̀...'』... DUALV2DUAしR.NO‑1・0000. .ODUALR"11・00000L213D. UALV2DUALSUF・IV1巳O噛'一. 『r. DUAしV3DUAしRwO‑1・OOÒ)ODUALRw21.00000L214 DUAしV3DUP.LSLIN・. 》1.or.. '.. DUAしV4DUAしRWOo1.OGOOODUAしt〜w21・00GOOし215 DUメLしV4DUAしR'N11̀〔 DUALV4〔. 〕OOOOL216' 嬰LSItMV1・O. DUAしVsDUAし. 一RWO1.OOOOO「DUALRL・.31・OOOOOL217... DUALV5DUAi̲SUMV1●LY DUALV6δ. ]li言. σALRwb1.00000DUAI.R・31.00000L218. 識IRy2tlli. i,1,‑i:80000L2・. DUALV7DUAしRLilO. ・. 、 二歪灘. 劉1轍. の後に変ta. .1.OOOOODUALRw3.1・00000し220DUAしV7DUALRW2 駒1.OOOOOし221. DUALV7DUALSUMV1.O DUAしV8DUAt̲RWO.1.00000.DUALPW31.00(IOO』.し222‑1. DUALV8DUALRw2‑1・00000DUALPWlo1・00000し223 DUALv8DuAしSuMV.1・Q『.. DUALV9DUALRWO. .‑1・00000DUALRW4享. ・00000L224D. UAしVgDUALSUMV1.0'‑̀.' ..DUAしVIODUALRwO,1・00000DUALRW41・00000L225 DUAしV】ODUALRW11.OOOOO....'L226. DUALV10DUAしSUr‑v1..O DUAしVllDUALRwO..'01・OOOOODUAt.RW4'1・00000し227.. 1.・. .BU:tU}}言. 訟L塞ご1、 ε1:80000….一. ・…L22e・. .‑DUALV12「)UAt日WO‑1.00000DUALRW41,00000L229D UAしV12DUAt‑Rvl2i.00000DUALRW11・00000し230 DUAしV12DUALStJttV,1。 〇. 一'‑i. ‑43一.
(13) 解. 説. 九 州 大 学 大 型 計 算 機 セ ン ター197o‑12. =}韓IJsLts̲一..::・:燃. ∫・:t±'. ゆUハ しV13貸UAしRWO‑1.QOOOonVAV・w奪1・000し231 {〉隻凄 織.V13{)雛AしRW3輪Lo0{}oo、 DUAしV13￡. し2.3?. 》UAしSUMV1・o. DUAしV1らDUALRwO脚1.0⊂,OOODUAしRw41・. ・00000L233. DUAしV14DUALR…3,‑1.。0。. 。。DUAしftw1・1・. {>9轟 しヤ149》lj《LSfjt噂}三 bUム 塵. しV15C}UAtpwO1轍1.ob〔}OOoU《. し「(W4}艇. 1)Uム 星 、Vユ5ひUAしRW3勲1。o(}ooOひV」. 一.一1》. V《tv主5鴨. 』DUAしV16DUAしRWO. 、しR?'2..,1.・O(>9三)o、. し2.̲甲. UAしV罰16bu《. しRWゴ. ヒUl念. 箆{}̲̲、. 一. 1イ『i 聯1.OOOOODUAしRW4. ・‑9甑. し234. ○o0oOし235. δ群ム 〔Sし地 〜バ'1;o.…. 甲"『 』b. ….一. 。。。0。. 〇む'.. 【「【…. 一 品 ユボ00060邸. .,卵,.̲..1..OOOOO、........、.髭. 、2̲、.31、,、....〒̲.̲̲̲一. 「、.pt.、. 「DVALR歯2i。OOOOOし238. 認 資と§漏.一.}:8㈱(し. ・…. 一 一一一 ・ ・ 一一. …・ ・ 一一 一一.一 ・ ・ 一一一 … 一・一. 一't皇. 要. 一. 轟. ・.曲. 一.、̲唱. 〒'Tt"'「. … 『…. 、̲.̲.、̲....一. 一. ・. 一. 噛.‑t‑r…. ・. ・幽. 「‑. K8$. .;・. 一一・ 』. 「 ・98倉 ヒ霞q量嵩91iftt霞. し. 躍. 鰍. 嵩9…. 蹴. 圭:89898…. 購. 噛 『.一 ・ 『 一・ 一・一・闇『.・ ・・ ・ ….…. 一…}:灘. 1【)VALRHSNOUALRW4ユ ltt1讐. 一. 一.・. …. ・… 一一.一一. 。PQOOo..、...一.、..、..̲..一. にN『. 髄・P・・』. …. 一. セ 妻「・ 言茎 ・ 髄 ・噛 』閲:・・一. 一 ・…ヒ1‑.衰. 麦 鷲. 、.t、.̲..しL2、. ・ ・.一 一 一・'一. 繋嘉1劉. ・'.酌 ¶』. ゆ一ルデ…鰍. 禽5..・. ・一. たの と一. 「..・H‑.'. 》A了A. ド. ・ 劉藤. ="ヤ 『""". 働a。. りALVI23・. ・67891・1日2・3・. ・516。UAしR"SN、.、,一. 、:. " vuALRw。,.1一. 垂. 。峯. 。萎,,1・. 鱒. レouALRWtll‑1一. .よ. 纏,式. ㌧ 、̲.一. 一・‑1・1‑・‑1‑1≦. 韮.蒙. 。U、 、RW21・. 、、 一 、 鵬. 、. ・.1. 蓄. 蓼{≦. 事..・. …. 一レ11191≦}一. しRW,・. ・ ・ 一. …. 麻い. い1"1≧{一..・. OVALRW4重1嘉1璽}婁. 喜. ・.一. 一・P‑一.. ≦. 量.・.・. 一. ≦ 繕的関畿oljALSVMVill.li、li韮1華1葦1…{l. NUMtjFROFε. しFM日 いFξlrNNON'CONSTRAtNttUROW(S》. .・1ゆ. 帆 i、̀、. 鰍v;. ̲,.・.・6‑一. 丁7需 噌一tr▼. 國」畠. 隔■覇、. ヒ. 16卓 NUMBF.隣OFぎ. 勧 ・煽. ゆ. しEMENTSIN(OXS'rRAIN'EPRQ…S・. 《oVNTKols・. の鰐. マルチ「以潜. せ そ;塑. じ. の コ ド. ロ. 謝i約 係 数名 と栃. てガ. 鰍. 聯. マドコじ. 糠. 娠. コ. ぐoり〜.IT殺C皆(OUN↑}(ov'(OUNIRow.COtiNlROW(OUNTROw. 『(二. 飛W38DUAしRft轟. 〇UNTNAMECOVt・iTN〈MECOUN丁NANECOUNTNAMECOUN↑NA図E. 1oUAtv12DUALV22'蓄)り 3￡ 》UALV74DUAしV82麟UAしV930U《 3蓬 〉り堀.V:3#'蓬)ijALVik"4ゴ{》VALV…,う. {)EN31丁¥oFPR6iLξr耀w、PERCf't達 THTSPROItEMv"$9SF̀tE』. ・EFヒ・・・・・ …L・. 鞭. 轍}. 》UAしR訴OBDUAしR碧1SDUAtRVi28DUAし い 轍 拭 賊 鳳 盆糠 こつい てほ.繍 の麟 綬 騒 しf珂εMSEヤ ぐ0LUN簿oRt>ご 険鴨・ ・.変 数の か らみ た,隙i約係数ヴ》 葬零の .ハ冒み 」 、F圃 幽「層,数1. (oUNINA糾. ・. ・の軸6"緋. 、ー. の. '. 徽. 、冗 ▼㌔L、. レ ド ヒじドア. NUMBERO旺. ・ …肖的 関鋲多 とその コxト 係数 の#零 饗素数. ・1"は 舳. 《しV33otiALVぺ2DijALV53oり 「. 丁6c.oOo一. う. しVIO...3DUAしV11.7一 芝 》ljAL》16L→. 変ts雛gAL¥ms3つ 非零係 数 がある。. 《しVも 砲.ε 》UALV12 の綱約」ミにつ いて に. 瀞納 縣数の遜奪要素 私 塵 瀞〜若溺合{充i最率}が 容〜}%そあ'菰....、.. じ ・1鮒丁$・16VEC了ORANり. 一"VA・ ・AtSLFNA・"[.一. 「. ・!一. うRov;$・. ・ 敵. ・. 灘. 謄. 一 この間懸 はJt・ 儲. 名に番伽. り 勅{4麟. る し あ臣}1磯数で5SUの 紺 拭 をもつ・、. (一 「6賢写・×1{x}=嚇 鵬 蹴"し 亀 ては・副. 《卜・ENUMB日 まA。St¥A■[NUMBEttA重SNA替ENUMB韮 …殺A・SNAMENりMBEgA,S緯 rし→ζ)馨A1.Vlの変数1二は'tジ'の 爵写'をつける"へ 3oり 森しV12竈}継A瓢V23DV轟 しV3鐸{》VAtVも5{)UALV5 6DUAし.V67,DUAしV731)UAしV89DUALV910DUAしVlO ユ】DuハLV1112DUAしV1213DUAしV1314DUAしV1ら15Duへ 1Ct)VAL》!も17へ ・S捧{猟 ξ 、衰ぎOl8SoVAtRW119S{)UAしRXv2、20.轟 21sDUPL.RV:4L・ ・岡A臓w⇔ 蝋 猷 聯 ザ の騨 を・琳 、こ蠣 献 ガG摩 であるの歌 勿 渡 靴 麟. 変数 塵 際. 数曜. の・. NVMg,[R燕.S踵. .!一.puALRw4の εLAY$f三T「. を附 雛. る. 鷺蔓管層o0鱈Ooト133S. 一残」ヴ変 数』 を八れたグ》で第 計愛隣 をやる,藤̀要 があ るA第 罧奨階1尉始. NbO多NOoFN(1〈}F(=tlitKF.Nl'CURREN了(}番oSfN鷺EFtovF.f)黛 亘IER覧NrしASE1へSVA【Uε(w)VAしUE【Z)VE(二 li1￠"3oi1oQeo(}(}Eも152《 2. し>15 ・SOUALR,V3' 蝋. 嗣 約式紅継 ・Zi"の番号をr){r、この凝 釣式は ・裏 ♂ 饗であ るの で.ス ラ,ノク変数Stitを欝繍すれば よい,,. 面し 鱒勢皆"00HOOM21STO丁ALτ!t》1邑. 誉̀PttAS .(1BEG奮Klee鱒. ・HgS τORVF(τQPEしEMENTEL戦f・1ENT(RI↑ 》 《o.1登(}《}導9窮[{)1Q重1《}o〈. き. tto.̲..2..̲..q̀0、Oひ1ooofきo05Vlユ. :B・ll2≧. 《懸… 三. 譜「3,・1.41・'1:̀5t・k6冠7聖. 茎7《o毒0..o。10oo(}ooEo1囎o・}OooCO{}Eoi 蝦tWFf《s韮fiL9. ・1,89・;ligti}1翼o鯛. .嚢oL#T:〈}纏. 一in‑44‑一. 一聯. .P韮V(1;A藍(疑. 窪段E'NT 〔 …RlON. 》ooe薪c1轍o専2oo{)ocoεel.
(14) 註1.イ. タ レー シ ョ ン数(基. 底 ベ ク トル の 入 れ 替 え 回数). 註2.基. 底 に 入 っ て い る 技 巧 変 数 の 数 。 こ の 数 が"0"と. 註3.η. ベ ク トルの 数 。 こ の 数 は そ れ ま で に リ イ ンバ ー シ ョ ン を行 な わ な い 限 「)"NOOFINTER"の. 註4.第1段. 階 での 仮 の 目的 関 数 の値(第2節(34)のgに. 註5.本. 来 の 目的 関 数 値(第2節(9)のfFに. 註'6.基. 底 に と り入 れ られ た変 数 番 号. 註7.基. 底 か ら追 い 出 され た変 数 番 号(第1段. な る まで ベ ク トル の 入 れ 替 え を必 要 とす る。 数 と一 致 す る。. 相 当 す る 。). 相 当 す る。). 階 で は"A"の. て は い け な い。) 註8.ピ. ボ ッ ト行 のRHSの. 値. 註9.ピ. ボ ッ ト要 素 の 値. 註10.基. 底 に と り入 れ ら れ た 変 数 の シ ン プ レッ ク ス基 準. つ い た 変 数 番 号(技. 巧 変 数)が. すべ て 追 い 出 さ れ な く.
(15) 5.参 )関. 考文献 根. 〈2)森口. 泰 a次 著. 数 理 計 画 法 王(岩. 繁一 、宮下藤太郎 著. 波 講座 基 礎 工 学 〉. 線 型 計 画 法(岩. 波 講 座 現 代 応 用 数 学). (3)森. 口. 繁一 著. 線 型 計 画 法 入 門(日. (4)刀. 根. 薫監 訳. 電 子 計 算 機 の た め の 数 理 計 画 法(H.P。. ー 共 著)(H科 〈5)富. 科 技 連 ラ イ ブ ラ リー) ュ ンダ. ユ ー ザ ー へ のリリー. 説書. ス の 時 期 に つ き ま し て は 、 お っ て セ ン タ ーニュース. せ します 。 な お 、LIPSV‑一. ャ ッ ノ＼C.A.チ. 技 連). 士 通FACOM236‑60LP(V‑1)解. LIPSV‑iの. キ ュ ン チ 、H.G.チ. ・‑1は特 殊 ジ ョ ブ 扱 い と な!lま す 。. で お 知 ちせ.
(16)
関連したドキュメント
九州大学学術情報リポジトリ Kyushu University Institutional Repository.. 九州大学大型計算機センター
Kyushu University Institutional Repository.
九州大学学術情報リポジトリ Kyushu University Institutional Repository.. 論理IF文の判定 大矢,
九州大学学術情報リポジトリ Kyushu University Institutional Repository.. 九州大学大型計算機センター
九州大学学術情報リポジトリ Kyushu University Institutional Repository.. 九州大学大型計算機センター
九州大学学術情報リポジトリ Kyushu University Institutional Repository.. 九州大学大型計算機センター
FOPEN FDNAME, FCB, BUF, FORG, MACRF, FLTYP, ILL FCLOSE... くだ さい。 ENCODEc,n,Vlist
九州大学学術情報リポジトリ Kyushu University Institutional Repository.. 九州大学大型計算機セン ター
