プロジェクトの選択

(1)

プロジェクトの選択

岩田憲明

(2)

整数計画法による研究開発プロジェクトの選択

2 7 1

l 本稿の目的

2

研究開発フ。ロジェクト選択問題の例示 3 整数計画法のためのモデルの修正

4

むすび

付録整数計画法のコンピュータ・プログラム(インプリシット・

エヌメレーション〉

1

本稿の目的

本稿の目的は研究開発プロジェクト選択問題に対する整数計四法の適用，

すなわち拙稿「ストカスティック・リニア・プログラミングによる研究開発プロジェクトの選択

1)

Jにおける数値例の計算結果の修正を示すことにあるO

前論文のストカスティック・リニア・プログラミング・モデノレはリニア・

プログラミングのコンビュータ・プログラムを利用して解が求められた。そしてその計算結果は表lのとおりである。

さて研究開発プロジェクトの選択のような問題においては，プロジェクトを「選択する」又は「選択しない」といった形の解が望まれる

O

表 lの計算結果では

ilJ

が「選択する」場合を示し，

iOJ

が「選択しない」場合を示す。しかし表

1

をみると

ilJ iOJ

の他に

i O . 5 J i O . 3 J

といった数値も解にあらわれている口「選択する」でも「選択しない」でもない

i O . 5 J

とか

i O . 3 J

という数値をそのまま利用することは困難である。

さて前論文ではプロジェクト問の相互排反

(mut u a l l y e x c l u s i v e )

関係が考慮された。相互排反の関係とは，あるプロジェクトが沼択されたとき同時に他のプロジェクトを選択することができないという閃係であるO

例えば，プロジェクト

3

については

1

~切においてノレート 1

(X31 1)

又は

j

レート

2 (X32 1)

のいずれか一方のみが選択されるとする

O

これは次の数式で表現された

D

X31 1

十

X32 1 : S : 1

(3)

さて表

l

の計算結果

2

をみると

X31 1

は 1"

0.5J

，

X32 1

も 1"

0.5J

となっているO たしかに数式はみたされているが，しかし相互排反関係にはなっていない口したがってこのような計算結果をそのまま利用することはできなし可

D

問題は解に1"

0.5J

"1

0.3J

といった整数でない数値があらわれる点にあるD このように整数でない解があらわれたのは，リニア・プログラミングの

コンピュータ・プログラムを利用したからである 2) 。さて，~数解のみを求

めることができる数学的方法が整数計画法(I

n t e g e rProgramming)

として開発されているD そこで研究開発プロジェクト選択問題に対して整数計画法を適用することが必要となってくるO

. .，

a )

整数計固法にも程々のみ法があるが，このプロジェクト選択問題においては変数の値が1"

0 J

(選択しない)と1"

1 J

(選択する)しかとらない。変数の値が

O

と

l

に制限される問題については1"インプリシット・エヌメレーション

J

(I

mp

1i

c i t E n u m e r a t i o n )

という方法が開発されており，そのコンピュータ・プログラムを利用することもできる

4)

O したがって前論文の問題に乙のインプリシット・エヌメレーションを適用することにしよう

O

以下本稿においては前論文の数値例でとりあげた研究開発フ。ロジェクトの問題を再度示し，次に整数計画法(インプリシット・エヌメレーション〉のコンピュータ・プログラムを適用するためにモデノレを修正し，最後にむすびとして計算結果を示してその分析を行なうことにする。

2

研究開発プロジェクト選択問題の例示

前論文の数値例でとりあげた問題の概要は図 1のデシジョン・ツリー(プログラム・ツリー)により示されるめO プロジェクト数は

6

であるが，各プロジェクトはデシジョン・ノードにおいて複数のルートにわかれるから，結局表 lで示したごとく

3 0

のプロジェクト(ノレート)間の選択の問題となるO

ここで記号について説明しておこうD

X i j l 1

期において選択されうるプロジェクト

i

のノレート

j

(4)

2 7 3 X i j

色

L

t期に状態

L

が生じたもとで選択されうるプロジェクト

i

のノレ

ート j

例えば

Xll 1

は

1

期において選択されうるプロジェクト

1

のノレート

l

を示し，また，

X61 a l a

は

3

期において状態

1

が生じたもとで選択されうるプロジェクト

6

の

^j

レート

1

を示す。

さてそこで図 1のデシジョン・ツリーをもとにストカスティック・リニア

・プログラミング・モデソレを作成すると表 2のようになる

⁵⁾

。

その計算結果を示したものが前掲の表 1の計算結果 1

i

問

6)

であり，デシジョン・ツリーにその結果を示したものが図

2

であるO さらに計算結果

1

において選択された

X32 1

が選択されなかった

X1L

の選択を必要とするという条件をおいて計算した結果が表

1

の計算結果

2の間であり，これを図で示し

たものが図

3

である。これによると

X1L

は

O

から

0.5

に

X32 1

は

l

から

0.5

に変化しているO

さて整数解を求めるため整数計画法(インプリシット・エヌメレーション)のプログラムを利用するのであるが，その前に記号の単純化をしておこう。表

2

の上の変数

X1L

を

X 1

とし以下右へ順に

X 2

，

X 3

，

X 4

，…

. . . X 30

としようO すると，表 2は次のように示すことができるO

目的関数

MAXIMIZE 5X 1

十

8X 2

十

10X 3 + 4X ₄

十

6X 5

十

5X ₆ + 4 . 5X ₇

十

9X 8

十

OX 9 + 10X 1o

十

2.45X 11

十

2 .45X 1 2 + OX 1 3 + OX 14 + O . 06X 1 5 +

制約条件 (1)

X 1 豆 l

O . 54X 1 6 + 0 . 06X 1 7 + O . 54X 1 S + O . 14X 1 9

十1.

26X 2 0 + 0.14X 21

十

1 .26X 2 2

十

O.135X 23

十1.

215X 24

十

0.135X 25

十

1.

215X 2 6 + O . 315X 27

十

2 .835X 2 8 +0. 315X 2 9 +2. 835X 3 0

( 2 ) X 2 + X 3

三三

l ( 3 ) X 4

十

X 5

十

X 6

三三

1 ( 4 ) X 7

豆 l

( 5 ) X _s 豆l

(5)

( 6 ) X9+X1 0

三三

1

(7)

2X1 +3Xa + 1X4 +2X5 +3X7 + 1Xs + 1X9 +2X1 0

三三

1 0

( 8 ) 3X1 +3X2 +3Xa

^十

1X4+2X5 +2X G +lX7 +3Xs +lX9

+2XIO~三二9 (9)

3X1 +3X2

^十

3Xa+ 1X4

^十

2X5+2X6+1X7

^十

6Xs+ 1Xg +2X1 0

三三9 (

1

m 3Xl+3X2+3Xa+1X4+2X5

十

2X6+3Xs + 1Xg +2X1 0 +2X1 1

三三

9

~

3Xl+3X2+3Xa+1X4+2X5+2X6+6Xs+1Xg

十

2X1 0+2X1 2

三三

9

(

1

) 3X1 2

^十

3X2+lX4 +2X6 +lX7 +3Xs +2X1 5 +4X2 3

三三

8

(

13)

3X1 +3X2 +lX4 +2X6 + lX7 +3Xs +2X1 0 +2X1 6 +4X 24

三三8 (

14)

3X1 +3X2 +lX4 +2X6 +lX7 +6Xs +2X1 7

^十

4X2 5 三

⁸

(

1

日 3X1

^十

3X2+1X4+2X6+1X7

^十

6Xs

^十

2X1 0

^十

2X1 S

^十

4X2 6

三三8 (16)

3X1 +3X2

^十

lX4+2X6 +3Xs +2X1 1

^十

2X1 9+4X2 7

三三

8

~

3Xl+3X2+1X4+2X6+3Xs

十

2X1 0

^十

2X1 1+2X2 0 +4X2 B

三三

8

(18)

3X1

^十

3X2

^十

1X4+2X6 +6Xs +2X1 2

^十

2X21 +4X2 9

三三

8

(

1

) 9 3X1 +3X2 + lX4

^十

2X o

十

6XB

^十

2X1 0 + 2X 1 2 + 2X 2 2 + 4X 3 0 三 : 8

0

日

‑X7+X1 1 +X1 3 =0

帥 ‑X7+X1 2+X 14 =0

ω‑X9

^十

X1 5+X2 a=0

~-X9+X16+X24=0

( 2 4 ) ‑ X9

^十

X1 7+X2 5=0 ( 2 5 ) ‑ X9 +X1 B +X2 6 =0 ( 2 o ) ‑ Xg +X1 9 +X2 7 =0

助 ‑X9+X20+X2S=0

倒 ‑X9+X2 1

^十

X2 9=0 ( 2 9 ) ‑X 9 + X 2 2 + X a 0 = 0

XJ=l ， O j=l ，…… 3 0 .

まず制約条件式印 1 ) " " : 2 9 )

はインプリシット・エヌメレーションのコンピュータプログラムのインプットにするため次の不等式に変えられる

7) 。

間

‑X7+X1 1 + X 1 a : : ; : 0

~1) ‑ X 7 + X 1 2 + X 1 4 三 0

(6)

倒 ‑X9 +X1 5 +X2 3

三玉

0

紛

_‑X9+X 16 +X2 4 豆0 ( 2 4 ) ‑X9 +X1 7 +X2 5

三三

O

(

25)

‑X g +X 18 +X2 6

三三

O

(26)

‑X9+X1 9+X 27

三三

0 0 カ ‑X9+X20+X2S

亘

0 ω

一九十

X2 1+X2 9

三三

0

(29) ‑

X 9 + X 2 2 + X 3 0 豆0

2 7 5

(

3

日 _2X7+8X9 _‑X1 ₁ _‑X1 ₂ _‑X1 ₃ _‑X1 ₄ _‑X1 ₅ _‑X1 ₆ _‑X1 ₇ _‑X1 _S _‑X1 ₉ _‑X2 ₀

‑X2 1 ‑X2 2 ‑X2 3 ‑X2 4 ‑X2 5 ‑X2 6 ‑X2 S ‑X2 9 ‑X3 0

三三

0

さて次に使用するコンビュータ・プログラムにおいては，目的関数が最小化

(MINIMIZE)

される。そこで

X=l‑X'

とおくと目的関数は，

MAX. 5 ( 1 ‑X 1 ' ) + 8 (1‑X 2 ' ) +……

… +0. 3 1 5 ( l ‑X2 ^Q ^' ⁾ +2. 8 3 5 ( l ‑X3 0 ' )

= 7 9 . 4 ‑(5X 1

'十

8X2'+

^…^・

・・・・・

+0.315X29 ' +2.835X3 0 ' )

となる。したがって次の最小化問題に変えられるD

MINIMIZE 5X1 ' +8X2' + l O X3' +4X4' + 6X s'

十

5X6 ' + 4 . 5X 7 ' + 9X S ' +OX9' + 10X1 0 ' +2. 45X1 1' + 2 . 45X1 2'

^十

OX1 3 ' + OX 1 4 ' +

o . 06X 1 5 ' + O . 54X 1 6 ' + O . 06X 1 7 ' + O . 54X 1 S ' + O . 14X 1 9 ' + 1 . 26X2 0 '

十

o .14X2 ^l' + 1 . 26X2 2 '

十

o .135X2 3 ' + 1 . 215X2 4 + 0.135X 25' +1. 215X2 6' +0.315X 27' +2.835X2 S' +0.315X2 9' +2.835X3 0'

~ìlj約条件についても同校にして次のように変えられる。(例えば (1) の X1 豆l

は

1‑X1 ' 豆1 X1

';三

0 )

( 1 ) X

t'ミ

0 ( 2 ) X2 +X3'

^三^三

1 ( 3 ) X4' +X5'

^十

XB ^F

^J

三 2

(4) X/~三O

(7)

( 5 ) X s

';三

O ( 6 ) X9'+X1 0'

ミl

(7)

2X/ +3X3'

十

1X4'+2X5 ' +3X7' +lXs' +lX9' +2X1 0 '

ミ

5

(8)

3X1 ' +3Xz' +3X3' + 1X4' +2X5' +2X6' + 1X7' +3X s' + 1X9' + zX1 0 '

二三

1 2

( 9 ) 3X1 ' +3Xz'

十

3X3'+ 1X4' +2X5 ' +2X6'

十

1X7 ' + 6X s ' + 1X 9 ' + 2X 1 0 '

~15

(

10)

3X1 '

十

3Xz'

十

3X3'+ 1X4' + 2X5 ' + 2X6'

十

3X s'十 1X9'+ 2X 1 0 ' + 2X1 1'

詮

1 3

(11)

3X1 ' + 3Xz' + 3X3'

十

1X4'+ 2X5 ' + 2X6' + 6X s' + 1X9'

十

2X1 0'+

2X1 Z' ; ' : ;

三

1 6

( 1 2 ) 3X1 ' +3Xz' + 1X4' +2X6 ' + 1X7' +3Xs' +2X1 5' +4Xz 3 '

二三

1 1

(13)

3X1 '

十

3 X z '+ 1X4 ' +2X6' + 1X7 ' + 3Xs'

十

2X1 0 ' + 2X 1 6 ' + 4X z 4 ' 三三 1 3 ( 1 4 ) 3X/ +3Xz' + 1X4' +2Xe ' + 1X7' .

十

6Xs'+2X1 7' +4X2 5 '

二三

1 4

(

1

日

3X1 '+3X2' + 1X4' +2X6' +lX7' +6Xs'

十

2X1 0 ' + 2X 1 S ' + 4X 2 6 ' ミ 1 6 (

1

6)

3X1 ' +3X2' + 1X4' +2X6' +3Xs' +2X1 1' +2X1 9' +4X2 7

';三

1 2 ( 1 7 ) 3X1 ' +3X2 ' + 1X4' +2X6 ' +3Xs' +2X1 0 '

十

2X1 1 ' + 2X 2 0

'十

4X2 s ' 三三 1 4

(

1

8 ) 3X1 ' +3X2' + 1X4' +2X6' +6Xs' +2X1 2' +2X2 1 +4Xz 9 ' と 1 5

(

1

9 ) 3X1 ' +3X2' + 1X4' +2X6' +6Xs' +2X1 0 ' +2X1 2'

^十

2X2 2'+4X3 0'

二三

1 7

(

抑

‑X7'+Xll'+X13'

主

l

帥 ‑X7'

十

X1 2

^'十

X1 4' ^三 ^三 l

ω ‑X9'+X15'+X23' 三三 1

ω ‑X9'

十

X1 6'+X2 4' ^三 ^三 1

( 2 4 ) ‑X9' +X1 7' +X2 5 ' 三 1

(25)

‑X9'

十

X 18 '+XZ 6'

ミ1

(2G) -X9'+X19'+X27'~三1 争力

‑X9'+X20'+X2S'

迄

l

倒 ‑

X9 ' + X2 l ' + X2 9 ' ;

三

l

(29) ‑

X9' + Xz 2 '

十

X30 '

二三

1

(8)

277 (

3

日

2X 7 ' + 8X 9 ' ‑ X 1 1 ' ‑ X 1 2 ' ‑ X 1 3 ' ‑X 1 4 ' ‑ X 1 5 ' ‑ X 1 6 ' ‑ X 1 7 ' ‑ X 1 8 '

‑X 19' ‑ X 2 0' ‑ X 2 l' ‑ X 2 2' ‑ X 2 3 ' ‑X 2 4' ‑ X 2 5' ‑ X 2 6' ‑ X 2 7'

‑ X 2 9' ‑ X 3 0' と ‑10 X j '=O

，l j

=1

・・・，

30

前論文においては

X 5

の選択は

X 1

の選択を必要とするという条件を追加した場合についても計算したがこれは最小化問題にすると次のようになるD

前論文では

X 5

三二

X 1

であるから，X

5 =1‑X 5'

，

X 1 =1‑X

t'とおくと (l

‑X 5')

三二(l

‑X

t')

(l

‑X

t')一(l

‑X 5')

二三

O

‑X

t'

+X 5'

二三

O

かくして例題はコンピュータのインプットの形式に修正されたのであるO

次節においてアウトプットである計算結果について論じよう

o

5

む

すび

リニア・プログラミングおよび整数計画法(インプリシット・エヌメレーション)による計算結果をまとめたものが表

3

である。

計算結果

1

の欄をみると，リニアプログラミング(以下LP)では

X41 2 2 2

X42 2 2 2

が

10.5J

という矛盾した結果があらわれた。すなわち

2

期において

状態

2

が生じた場合プロジェクト

4について相互排反民係にあるノレー 1と

ノレート 2が同時に(部分的ながら)選択された。しかし整数計画法(以下

IP)

ではX41

2 2 2

が

11J X42 2 2 2

は

10J

，すなわち

2

~切において状態 2 が生じた場合にはプロジェクト

4

については

j

レート

1

のみを選択せよという明確な結果があらわれた。

また

IP

においてはX62

1

が

X61 1

にかわり選択されている

O

そのために

X62313 X623 23 … X623 83

は選択されなくなった。目的関数の値も

36.2

から

35.4

へと低くなっている。

さて計算結果

2は計算結果 1

のモデルに

X32 1

三二

Xll 1

という条件すなわち計算結果

1 X32 1

XILの選

択を必要とするという条件を追加した場合の計算結果である

o LPでは

(9)

Xll 1

が

r O . 5

.Jで(部分的に)選択されたが，

I P

では

XIL

は選択されないし，さらに

X32 1

も選択されなくなった。

最後に計算結果

3

であるが，乙れも計算結果

2

と同様に

X41 ₁

三二

Xll ₁

_という条件すなわち計算結果

1 X41 1

XIL

の選択を必要とするという条件を追加した場合の計算結果である。

LP

の結果をみると

X4L

とともに

Xll 1

も選択されるようになった。

I P

では

X4L

とともに

Xll 1

も選択されるようになったのは同じであるが，興味深いのは

X61s 1 s

以下の変数の位が変化している点である。

I P

の結果によると「プロジェクト

6

について

3

}切に状態

1

，状態

2

，状態

3

，状態

4

が生じた場合には

j

レート

l

を選択せよ，しかし状態

5

，状態

6

，状態

7

および状態 8が生じた場合にはノレート 2を選択せよ」すなわち「プロジェクト 4において

2 ~切に確率 0.3 の方が生じた場合には，プロジェクト 6 は 3 期にノレート l

を，又確率

0.7

が生じた場合にはノレート

2

を選択せよ」ということになる

o

LP

ではいかなる状態が生じた場合でもプロジェクト

6

についてはノレート

2

を選択せよという計算結果であり

LP

と

I P

で計算結果が変化している点は注目すべきである

O

本稿においては整数計画法のコンビュータ・プログラムを利用して，前論文の計算結果を修正した。部分選択がすなわちリニアプログラミングを利用した前論文の計算結果においては部分選択(

r O . 3 J

とか

r O . 5 J

)という解があらわれたし，また相互排反の関係にあるプロジェクトが同時に(ただし部分的に)選択されるなど解釈の困難な点があったが，これらの欠点は整数計四法の適用することにより克服することができたのである口

コンピュータを利用することにより我々は整数解を容易に得ることができるD そこで付録として使用したコンピュータ・プログラムを示すことにする口注1) 長崎大学経済学研究会

r f f

主目と経済

J 5 5

巻

l

号，

P P . 5 5 ‑ 7 8

，昭和

5 0

年。

2 )

コンピュータは名古屋大学大型計算機センターの

FA C OM230‑60

，リニア・

プログラミングのプログラムは富士通捉供の

L1 P S60C

を利用した。

3 )

整数計画法については

前田活郎，大野豊，藤井純監修，

r

コンピュータマネジメント・サイエンスハン

(10)

2 7 9

ドブック

J

，

pp 1 1 6 ‑ 1 5 4

，オーム社，昭和

4 6

年。

4 )

インフ。リシット・エヌメレーションおよびそのコンピュータ・プログラムについては，

Donald R. Plane and Claude McM i 1 1 an

，

] r .

，

D i s c r e t e Optimization:

Integer Programming and Network Analysis f o r Management D e c i s i o n s

，

P r e n t i c e ‑ H a l l

，

1 9 7 1 .

5 )

ボックス内の数字は資源必要呈を示す。乙のモデルではモデノレ単純化のために考 j設される資源制約ほ

1

種類の資源に限られている。

6 )

乙れはギ、ア=ロケットの計算結果を修正したものである。

A. E . Gear and A. G. Lockett

，

A Dynamic Model o f Some Multistage Aspects o f Research and Development P o r t f o l i o s "

，

IEEE Transactions on Engineering Management

，

V o l . EM‑20

，

No.

，1

P P . 2 7 ‑ 2 8

，

February 1 9 7 3 .

7 )

等式は一般に次の方法lとより不等式に変えることができる。

n

~ al{xj=bl f o r i = 1

，

2

， ...

m n

~ afj~bf f o r = 1

，

2

， "'，

m

η

~αjXjζ 日 j=l

立 1

ただし α ‑

~

a1j

立 1

s = ‑ ~bl

j

=1

(等式)

(不等式〉

Harvey M. Wagner

，

P r i n c i p l e s o f Operations Research with a p p l i c a ‑ t i o n s t o managerial D e c i s i o n s

，

P . 7 9

，

P r e n t i c e ‑ H a l l

，

1 9 6 9 .

参考文献

1.

Anthony E . Gear and A. Geaff Lockett

，

. " A Dynamic Model o f Some

Multistage Aspects o f Research and Development P o r t f o l i o "

，

IEEE

(11)

Transactions on Engineering management

，

V o l . EM‑20

，

N o . 1

，

p p . 2 2 ‑ 2 9

，

February 1 9 7 3 .

2 .

平田正敏著，財務管理と数理計画法，森山香庖，昭和

4 4

年。

3 . E.L. Lawler and M. D. B e l l

，

A. Method f o r Solving D i s c r e t e Optimization Problems"

，

Operations Research

，

p p . 1 0 9 8 ‑ 1 1 1 2

，

November‑

December

，

1 9 6 6 .

4 .

前田活郎，大野豊，藤井純監修，コンビュータマネジメント・サイエンスハンドブック，オーム社，昭和46年。

5 . C l i f f o r d C . P e t e r s e n

，

Computational Experience With Variants Of The Balas Algorithm Applied To The S e l e c t i o n Of R&D P r o j e c t s "

，

Management S c i e n c e

，

Vo 1 . 1 3

，

No. 9

，

P P . 7 3 6 ‑ 7 5 0

，

May

，

1 9 6 7 .

6 . Donald R. Plane and Claude McMillan J r .

，

D i s c r e t e Optimization:

I n t e g e r Programming and Network Analysis f o r Management D e c i s i o n s

，

P r e n t i c e ‑ H a l l

，

1 9 7

1.

7 . Harvey M. wagner

，

P r i n c i p l e Of Opesrations Research with a p p l i c a t i o n s t o managerial d e c i s i o n s

，

P r e n t i c e ‑ H a l l

，

1 9 6 9 .

8 .

拙稿「ストカスティック・リニア・プログラミングによる研究開発プロジェクトの選択

J

， (長崎大学)

r

経営と経済

J

，

5 5

巻 l号

P P . 5 5 ‑ 7 8

，昭和

5 0

年。

付録整数計画法のコンピュータ・プログラム(インプリシット・エヌメレーション)

このプログラムはプレーン=マクミランの閃発したフ。ログラムについてアウトプット形式に若干の修正を加えたものである。プレーン=マクミランのプログラムでは変数が

1 0

以内でなければならない。本稿でとりあげた論文では変数が

3 0

である。そのためにより多くの変数

( 3 5

以内)より多くの制約式

( 3 5

以内)の場合に適用できるように修正したものである。

(12)

C ZERO‑ONE INTEGER PROGRAMMING IMPLICIT ENUMERATION

終‑国昨臨叫

r DIMENSION A(40

，

40)

，

C(40)

，

B(40)

，

CS(40)

，

W(40

，

40)

，

IX(40)

，

IS(40) 2 DIMENSION IV(40)

，

IT(40)

，

NOTT(40)

，

SUMS(40) 3 DIMENSION IPRIN

1(

40)

，

IPRIN2(40)

，

IPRIN3(40) 門 DIMENSION ISAVE(40

，

40)

，

1STEP(40)

，

1NUM(40)

チ

γ 4

ひ

4 5 EPS = 0.000001

三出詔目、」日担

6 IPRIN4=0 7 DO 11 1=

1，

40 8 11 INUM

(I

)=1

ロ

9 1 CONT1NUE

¥己，

1TPCK=O

い

10 ¥迂 11 1FEAS=O ー r 12 1COUNT=O

苅耐δ

13 READ(5

，

500)M

，

N

，

KA1 14 500 FORMAT(314) 15 1F(M‑36) 4

，

9000

，

9000 16 4 DO 2 II

=1，

40 17 B

(I

1)=O.

。

18 C

(I

I)=O.

。

19 1S(II) =0 20 IV(II)=O 21 IT

(I1)

=0 22 1X

(I

I)=9 23 NOTT

(I

1)=O

トCト~コ

24 SUMS

(I1)

=0.0

(13)

25 DO 2

]J =1，

35 26 A(II

，]J)

=O.O 27 W(II

，]J

)=O.O 28 2 CONT1NUE 29 DO 3 1=

1，

35 30 IPRIN1

(I)

=0 31 1PRIN2

(I)

=0 32 1PR1N3

(I)

=0 33 3 CONTINUE 34 READ(5

，

510)(C

(J) ，] =1，

N) 35 510 FORMAT

(l

OF8.4) 36 DO 10 I=

1，

M 37 10 READ(5

，

510)B

(I)，

(A

(I，J)，]=1，

N) 38 READ(5

，

510)ZBAR 39 FZBAR = ZBAR 40 DO 20 ]

=1，

N 41 CS

(J

)=O.O 42 DO 20 I=

1，

M 43 20 CS

(J

)=CS

(J

)+A

(I，])

44 WRITE(6

，

12) 45 12 FORMAT

(l

H1

，

19X

，

18HOB]ECTIVE FUNCTION

，!)

46 WR1TE(6

，

76)

(I

NUM

(J)，]=1，

N) 47 76 FORMAT

(l

2X

，

10(9X

，

lHX

，

I2)) 48 WRITE(6

，

77)(C(K)

，

K=

1，

N) 49 77 FORMAT

(l

HO

，

12X

，

10F12.4

，!，(l

3X

，

10F12.4)) 50 WRITE(6

，

8

l)

51 81 FORMAT

(l

HO

，

j20X

，

llHCONSTRAINTS

，

jj

，

6X

，

8HCONSTANT

，j)

(14)

52 DO 84 I=

l，

M

目緊一国時叫出←

53 WRITE(6

，

83)I

，

B

(I)，

(A

(I，J)，

j =1

，

N) 54 83 FORMAT

(l

HO

，

1X

，

1HG

，

I2

，

2X

，

F6.1

，

10F12

.4，j， (l

3X

，

10F12.4)) 55 84 CONTjNUE 56 DO 17 I=

l，

M ii ?γ 57 IF(B

(I

))19

，

17

，

17

心

4 58 17 CONTINUE

羽目四

日

謀

、

4奇L

59 ZBAR=O.O 60 WRITE(6

，

86) 61 86 FORMA T

(l

HO

，j / ，

16X

，

26HALL CONST ANTS ARE POSITIVE

， j) ロ

62 GO TO 1750

ぺ:

19 NUMB=O

い

63 ¥斗 64 NS=O

‑‑r

65 45 IF(NUMB)645

，

645

，

639

出悩

8 66 639 DO 1001 1 =1

，

NS 67 IPRIN1

(I)

= IS

(I)

68 1001 CONTINUE 69 645 FP=O.O 70 NW=O

71

IF(NS)5

1，

5

1，

52 72 52 DO 50 j=

l，

NS 73 IF(IS(J))50

，

50

，

55 74 55 NW=NW 十 1 75 JJ =IS

(J)

76 DO 60 I=

l，

M hbGJ

コ

J

77

60 W

(I ，

NW) =A

(I ，

JJ)

(15)

78 FP=FP+CCJJ) 79 50 CONTINUE 80 51 NW=NW+1 81 DO 65 I=

l，

M 82 65 W

(I，

NW)=B

(I)

83 MV=O 84 DO 70 I=

l，

M 85 SUMS

(I

)=O.

。

86 DO 80 J=

l，

NW 87 80 SUMS

(I

)=SUMS

(I

)+W

(I，J)

88 IF(SUMS

(I)

+ EPS )85

，

70

，

70 89 85 MV=MV+1 90 IV(MV)=I 91 70 CONTINUE 92 IF(MV)200

，

200

，

90 93 90 DO 1200 I=

l，

MV 94 IPRIN2

(I)

= IV

(I)

95 1200 CONTINUE 96 CLIM=ZBAR‑FP 97 NW=O 98 NT=O 99 IT

(l

)=O 100 DO 100 J

=l，

N 101 100 NOTT

(J)

=0 102 IF(NS )104

，

104

，

101 103 101 DO 105 J

=l，

NS

(16)

1TEMP = 15(]) 1F

(I

TEMP)102

，

105

，

105 1TEMP= ー 1TEMP NOTT

(l

TEMP) =1 DO 110 J=

l，

N 1F(NOTT(J) )115

，

115

，

110 1F(CL1M‑C(]))110

，

110

，

120 DO 125 1=

l，

MV 1TEMP=1V

(I)

1F(A

(I

TEMP

，

J))125

，

125

，

130 125 CONTINUE GO TO 110 130 NT=NT+1 1T(NT)=J NW=NW+1 DO 135 1=

l，

M 135 W

(I，

NW)=A

(I，J)

110 CONT1NUE 108 DO 1300 1=

l，

NT 1PR1N3( 1) = IT( 1) CONT1NUE 1F(NT)1400

，

1400

，

138 1TPCK=l JMAX=O GO TO 1000 DO 140 1=

l，

MV

眼球却国時一円1げが車同呂開け判︒ロ勺h

戸︑ 78

山山川出

102 105 104 115 120

104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 1300 125 126

ω

∞

ω

1400 138

127 128 129

(17)

130 ITEMP=IV

(I)

131 DO 145 J

=l，

NW 132 IF(W

(I

TEMP

，

J))145

，

145

，

150 133 150 S UMS(ITEMP) = S UMS

(I

TEMP) + W

(I

TEMP

，

J) 134 145 CONTINUE 135 IF(SUMS

(I

TEMP) + EPS)152

，

140

，

140 136 152 IPRIN4=ITEMP 137 ITPCK=l 138 JMAX=O 139 GO TO 1000 140 140 CONTINUE 141 JMAX=IT

(l)

142 CSMAX=CS

(J

MAX) 143 IF(NT ‑2)156

，

146

，

146 144 146 DO 155 J =2

，

NT 145 JTEMP=IT

(J)

146 IF(CS

(J

TEMP)‑CSMAX)155

，

160

，

170 147 160 IF(C

(J

TEMP) ー C

(J

MAX) )170

，

155

，

155 148 170 JMAX = JTEMP 149 CSMAX=CS

(J

TEMP) 150 155 CONTINUE 151 156 CONTINUE 152 GO TO 1000 153 157 CONTINUE 154 NS=NS+1 155 IS(NS) = JMAX

(18)

156 NUMB=NUMB 十 1

トU野

￥ o 157 GO TO 45 158 200 DO 210 ]

=1，

N

際型国

159 210 1X

(J

)=O 160 ZBAR=O

('¥ Pγ DO 215 ]

=1，

NS 161 e}I 162 ]TEMP =1S

(J) E員

163 1F

(J

TEMP )215

，

215

，

217 PE E 164 217 1X

(J

TEMP)=1

淑、i，

165 ZBAR = ZBAR + C(]TEMP)

ロ

166 215 CONT1NUE

九〈;，

ド 167 1FEAS=l ¥ミ

‑r

168 ]MAX=O 169 CLIM=O

悩

8 170 1000 ]CK=(NUMBjKA1)*KA] ‑NUMB

出

171 1F

(I

CK)1550

，

1010

，

1550 172 1010 WR1TE(6

，

11

l)

NUMB 173 WRITE(6

，

112)

(I

PR1N1

(I) ，

1=

l，

NS) 174 WR1TE(6

，

113)

(I

PR1N2

(I) ，

1=

1，

MV) 175 WR1TE( 6

，

114)CLIM 176 WRITE(6

，

119)

(I

PR1N3

(I) ，

1=1

，

NT) 177 WR1TE( 6

，

116)1PR1N4 178 WRITE( 6

，

117) ]MAX 179 WRITE(6

，

118) ZBAR 180 111 FORMAT

(l

H

，

4HSTEP

，

14)

トコ。コh斗

112 FORMAT

(l

H

，

llX

，

1HS

，

9X

，

3513) 181

(19)

182 113 FORMAT

(l

H

，

llX

，

1HV

，

9X

，

3513) 183 114 FORMAT

(l

H

，

llX

，

4HCLIM

，

6X

，

F8.4) 184 119 FORMAT

(l

H

，

llX

，

1HT

，

9X

，

3513) 185 116 FORMAT

(l

H

，

llX

，

7HNOT SAT

，

3X

，

13) 186 117 FORMAT

(l

H

，

llX

，

8HADD TO S

，

2X

，

13) 187 118 FORMAT

(l

H

，

llX

，

4HZBAR

，

6X

，

F8

，

4

1)

188 1550 DO 1600 1=

1，

35 189 1PR1N1

(I)

=0 190 1PR1N2

(I)

=0 191 1PRIN3

(I)

=0 192 1600 CONT1NUE 193 1PR1N4=0 194 1F(1FEAS‑1)1605

，

300

，

300 195 1605 1F

(I

TPCK‑

l)

157

，

300

，

300 196 300 NEWS=NS 197 DO 220 ]

=1，

NS 198 JJ=NS‑]+1 199 1F(1S(]]))225

，

225

，

230 200 225 NEWS=NEWS‑1 201 220 CONT1NUE 202 GO TO 400 203 230 1S

(JJ)

=‑1S

(J])

204 NS=NEWS 205 1F

(I

FEAS‑

l)

1512

，

1508

，

1508 206 1508 1F

(I

TPCK‑1)1511

，

1512

，

1512 207 1511 1F(50‑1COUNT)1512

，

1512

，

1509

(20)

関鮮半国︐好一円1げが車同盟淑刈︒ロ山︑

_u

ド山可

78

儲芦 ω∞ω

208 1509 1COUNT=1COUNT+1 209 1STEP

(I

COUNT)=NUMB 210 DO 1510 1=

l，

N 211 1SA VE

(I

COUNT

， I)

= 1X

(I)

212 1510 CONT1NUE 213 1512 1FEAS=O 214 1TPCK=O 215 NUMB=NUMB 十 1 216 GO TO 45 217 400 WR1TE(6

，

1610) 218 1610 FORMAT

(l

HO) 219 1F

(I

X(

l)

‑9)1630

，

1615

，

1615 220 1615 WR1TE(6

，

1620)FZBAR 221 1620 FORMAT

(l

H

，

4X

，

80HTHERE 1S NO FEASIBLE SOLUTION W1TH A VALUE FOR TH 2E OB]ECTVE FUNCTION LOWER THAN

，

F7.4

，

24H

，

THE 1N1T1AL ZBAR VALUE) 222 GO TO 1 223 1630 DO 1700 1=

1，

1COUNT 224 WR1TE(6

，

1650)1STEP

(I)， (I

SAVE

(I ，j) ，] =l，

N) 225 1650 FORMAT

(l

HO

，

15HFEAS1BLE S STEP

，

14

，

2X

，

3513) 226 1700 CONTINUE 227 1750 WR1TE(6

，

1751) 228 1751 FORMAT

(l

HO

，

130

(l

H

骨))

229 WRITE(6

，

1800)

(I

X

(I)，

1=

l，

N) 230 1800 FORMAT(Hro

，

16HOPTIMAL SOLUT10N

，

5X

，

3513) 231 WRITE( 6

，

1900 )ZBAR 232 1900 FORMAT

(l

HO

，

28X

，

38HOPTIMAL VALUE OF OB]ECTIVE FUNCT10N =

，

F10.4)

(21)

計算結果

1 (X32 ₁

_三_二

Xll ₁₎

計算結果

2 Xll ₁ 0 . 5

X21 ₁

X22 1

1.

0

1.

0 X31 ₁ 0 . 5

X32 ₁

1.

0 0 . 5

X33 ₁

X41 ₁

1.

0

1.

0 X51 ₁ 0 . 3

X61 ₁

1.

0

1.

0 X62 ₁

ー・ー・ーーーーーーー・・増・ー‑ ‑ ‑ ‑ ‑ ・ ‑ ‑ ‑ ‑ ‑ ‑ ‑ ‑ ‑ ‑ . ー・・・・・・園町・ー・ ‑ ‑ ・・ー・・・・ ‑ ‑ ‑ ‑ ‑ ‑ ‑ ‑ ‑ ‑ ・・・』町 ‑ ‑ ‑ ーー ‑ ーー ‑ ‑ ‑ ‑ ・・・・・，場岨， ‑ ‑ ‑ ‑ ー ‑ ‑ ‑ ‑ ‑ ‑ ‑ ‑ ‑ ‑ ‑ ‑ ‑ ‑ ・・・・・・・・・ーーー ‑ ‑ ー・ーー ‑ ー ‑ ‑ ー ‑ ‑

X41 ₂ 1 ₂

1.

0

1.

0 X41 ₂ 2 ₂ 0 . 5

1.

0 X42 ₂ 1 ₂

X42 ₂ 2 ₂ 0 . 5 X613 13

X613 2 3 X613 33 X613 4 3 X613 5 3 X613 63 X613 73 X613 83

X623 13

¹^.

0

1.

0 X623 2 3

1.

0

1.

0 X62333

¹^.

0

1.

0 X623 4 3

1.

0

1.

0 X623 5 3

1.

0

1.

0 X623 63

¹^.

0

1.

0 X623 73

¹^.

0

1.

0 X623 83

¹^.

0

1.

0

目的関数の値

3 6 . 2 3 5 . 9

表l ストカスティック・リニア・プログラミングの計算結果

(22)

整数計画?去による研究開発フ。ロジェクトの選択

2 9 1

口円 ; 臼回二日トー

⁵

フ。ロジェク卜 2

白川

田、日;

;白子→

8

下 X科目 ' . 日 ; ~~[日トー 10

3

卜刊日

^日

:~4

xq~.日日正J十一 6

何回回目十

⁵

X4~ 河合目 ;

叫~r-l~

^O ^. ^!

日 : 四日 ← ‑

5

巴勺凶刃向日こ日トー

l X 叫 : 日 : :目立当二

日エクト

6 .

Ix~:日'.聞に;

: :

国国国

図 1

数値例のデシジョン・ツリー

(23)

M

ロ

M お M お M お ~ ~ ~写~ ~~ ~ ・

4

Hg ・喝 HHg

網網

KNg

例:.<

制~: ~ 同"・・ M

刊

g ・"・ K的~:・・ M

守

g ・・・・ M 岡~: ~田~:旬 ><伺開 H

回

g 嶋・・ K g H

崎..

MNg

縄何

Hng

一一

~守~" ~的~: A= ~

ト"

H ∞ ~:

点始におけ単る採

条周件ル1 ト

プロジェクト 1 1 壬二 1 " 2 三 1 I " 3 1 1 l 三二 l

"

4 l 三二 l " 5 1 三三 l " 6 1 1 三二 1 1 期 2 期状態 1 三二 9 "

"

21 3 三二 9 " " 31 3 。三二 9 資 "

11

41 3 6 2 2 。 s: 9 源 3 期状態 1 。 2 4 さ二 8 併

l11 11

21 3 2 2 4 三二 8 見守 " " 31 3 。 2 4 三二 8 条 "

11

41 3 2 2 4 三二 8 件

11

" 51 3 3 。 2 4 三二 8

11 11

61 3 3 。 2 4 三二 8

11 11

71 3 6 。 2

。

2 4 三二 B "

11

81 3 6 2 2 。 2 4 三二 8 プロジェタト 4

状態

1 ‑1 l 1

"

" 2 ‑1 1 1 前プロジェクト

E状態

l ‑1 1 1 後

11 "

2 ‑1 1 l

~

0 関 "

11

3

~1

1 1 連

" "

4 ‑1 l 1 条

"

" 5 ‑1 l 1 件 "

11

6 ‑1 1 l

"

" 7 ‑1 1 1 " " E ‑1 l 1

I~

0

的目関政

10 5 4.5 10 2.45 2.45 0 0.06 0.54 0.06 0.54 0.14 1. 26 0.14 1. 26 0.135 1. 215 0.135 1. 215 0.315 2.835 0.315 2.835 表 2 数官官例のストカスティック・リニア・プログラミング・モデル

(24)

2 9 3

JE:: 日日子→ ⁵

1qE~，:[QE}- s

九クト

2 . c

^x²²^;^t

E ~~~ー10

q j

仁日;

_~~[己: _{ご I~ゴ← 4}

巨コー

‑;nqJEL j巴 ←Eコ←一

¹ ⁵

角

~I

³kてr;=‑I!コ

^λ ^. ^. ^. ^. ^. ^. ^. ^. ^. ^j

^巴コ雨宮⁷

何 ;

: O L 7 也事 : : : : : : j E ? o

~:日討に出....__....j出ご9

九ト

6 f : 日日 i : :

￨何;日1‑'‑‑‑‑

. . . 可制 : :

回目白

1

期

2

周

3

期

完全採用・・・暗部分採用

図 2 計算結果 1 の図示

(25)

計非結果 l

L P

I

1 P

) 2 一P

44

一

泊呆一

I

/﹀古了 1i1

草川一

ね宇一

p

xi 一

(計一

L

(X4h

三X1h) 計算結果

3 L P

I

1 P X 1

→

Xll

₁

X 2

→

X21 ₁ X 3

→

X22 ₁ X 4

→

X31 ₁ X 5

→

X32 ₁ X 6

→

X33 ₁

X 7

→

X41 ₁

1.

0 X 8

→

X51

₁

0 . 3

X 9

→

X61 ₁

1.

0

I 1.

0

1.

0

I

1 X

lO→

X62 ₁ 1

I

Xll

→

X41 ₂ 1

2

1.

0 I 1 I

1.

0 I 1 I 0 . 4

X12

→

X41 ₂ 2 ₂ 0 . 5 I 1 I

1.

0 I 1 I 0 . 4

X13

→

X42 ₂ 1 ₂ 0 . 4

X14

→

X42 ₂ 2 ₂ 0 . 5 I 0

.4

X15

→

X613 13 X16

→

X613 23 X17

→

X613 33 X18

→

X613 43 X19

→

X613 53 X20

→

X613 63 X21

→

X613 73 X22

→

X613 83 X23

→

X623 13 X24

→

X623 23 X25

，ー

X62333 X26

→

X623 43 X27

→

X623 53 X28

→

X623 63 X29

→

X623 73 X30

→

X623 83

0 . 5 0 . 9

1.

0 1

1.

0 0 . 5 0 . 5

1.

0

1 1 0 . 9

1.

0

1.

0

1.0 1.0 1.0 1.

0

1.

0

1.

0

1.。

1.

0

1.

0

1.0 1.

0

1.

0

1.

0

1.

0

1.0

1.

0

1.

0

1.0 1.0 1.

0

1.

0

1.

0

1.0

寸げ止の数閲

h

叶J

R 口 R

U

バ斗

4

n J

3

1.

0

表 3 計算結果の要約

q A

円 ︒

門ベ

JV

3 5 . 4 I 3 5 . 9 I

⁴

^A

^う^つ

^d

1 1 1

1

ーム司

i

占

﹃ fム司よ

τ

ょ 1 ょ

可よ司 lム司

l

白守

1A