の値を増加させると，基底変数の中で

1.12 (1.23)

で，x

の値を増加させると，基底変数の中で

が最初に

に達する．(1.23) の

本目 の式から

として，他の式に代入することで，

z= 3x₁ +2x₂ x3= 6 −x1 −x2

x₄= 10 −2x₁ −x₂

x5= 3 −x2

を得る．点

に対応する．

1.13 1.

略

min −2y₁+8y₂ s.t. y1+2y2≥3

−y1−4y2≥−1 3y1+y2≥4 4y1−2y2≥5 y₁, y₂≥0 3.

max 3x₁−x₂+4x₃+5x₄ s.t. −x1+x2−3x3−4x4≥2

2x₁−4x₂+x₃−2x₄≤8 x1, x2, x3, x4≥0

1.14 4

月の労働時間に対応した潜在価格がもっとも大きいので，

月の労働時間を追加するのが効 果的と判断できる．

2.1

1.

略

を

( x12 x14 x24 x25 x31 x36 x37 x43 x47 x56 x58 x63 x64 x78 x86 )^⊤

とおく．これに対応した係数行列は















−1 −1 0 0 1 0 0 0 0 0 0 0 0 0 0

1 0 −1 −1 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 −1 −1 −1 1 0 0 0 1 0 0 0

0 1 1 0 0 0 0 −1 −1 0 0 0 1 0 0

0 0 0 1 0 0 0 0 0 −1 −1 0 0 0 0

0 0 0 0 0 1 0 0 0 1 0 −1 −1 0 1

0 0 0 0 0 0 1 0 1 0 0 0 0 −1 0

0 0 0 0 0 0 0 0 0 0 1 0 0 1 −1















2.2

1.

工場と配送センターのインデックスを以下のように定める．

工場

配送センター

利府

仙台北部

名取

仙台南部

古川

石巻

古川

ネットワークは図表

の通り．

図表

工場と配送センターのネットワーク

1 2 3

4 5 6 7

400 300 200 200

200 400 500

[3]

[4]

[5]

[4]

[3] [2] [4] [3]

[3]

[4]

[4] [2]

2.

工場

から配送センター

への輸送量を

とおく．輸送費用の最小化問題は次のように 定式化される．

min 3x₁₄+4x₁₅+5x₁₆+4x₁₇ +3x24+2x25+4x26+3x27

+3x₃₄+4x₃₅+4x₃₆+2x₃₇ s.t. x14+x15+x16+x17=200 x24+x25+x26+x27=400 x34+x35+x36+x37=500 x14+x24+x34=400 x₁₅+x₂₅+x₃₅=300 x16+x26+x36=200 x₁₇+x₂₇+x₃₇=200

xij≥0, i=1, 2, 3; j=4, . . . , 7

参考までに最適解を示す．

x14=200 x15=0 x16=0 x17=0

x24=100 x25=300 x26=0 x27=0

x₃₄=100 x₃₅=0 x₃₆=200 x₃₇=200

2.3

1.

ネットワークは図表

の通り．

図表

ネットワーク

1 2

4 3

2(a)a=b+c

の場合：

min 2x₁₂+5x₁₃+4x₂₁+x₂₃+4x₂₄+2x₃₄+7x₄₃ s.t. −x12−x13+x21= −a

x₁₂−x₂₁−x₂₃−x₂₄=0 x13+x23−x34+x43=b x₂₄+x₃₄−x₄₃=c

x12, x13, x21, x23, x24, x34, x43≥0

2(b)a > b+c

の場合： 変数

を導入する．d

とおく．

min 2x₁₂+5x₁₃+4x₂₁+x₂₃+4x₂₄+2x₃₄+7x₄₃ s.t. −x12−x13+x21−x15= −a

x12−x21−x23−x24=0 x13+x23−x34+x43=b x24+x34−x43=c x₁₅=d

x12, x13, x21, x23, x24, x34, x43, x15≥0

2(c)a > b+c

の場合：変数

，x

を導入する．e

とおく．

min 2x12+5x13+4x21+x23+4x24+2x34+7x43

s.t. −x12−x13+x21= −a x₁₂−x₂₁−x₂₃−x₂₄=0 x13+x23−x34+x43+x63=b x₂₄+x₃₄−x₄₃+x₆₄=c

−x63−x64= −e

x12, x13, x21, x23, x24, x34, x43, x63, x64≥0

2.4

1.

在庫の量は，

，

，

，

で表される．

min 90x₀₁+85x₀₂+92x₀₃+90x₀₄+3x₁₂+3x₂₃+3x₃₄+3x₄₅ s.t. −x01−x02−x03−x04= −550

x01−x12−x16=0 x12+x02−x23−x27=0 x23+x03−x34−x38=0 x₃₄+x₀₄−x₄₅−x₄₉=0

x45=20, x16=140, x27=120, x38=150, x49=120 x₁₂≤100

x23≤100 x34≤100 x45≤100

xij≥0, ij

はすべての枝 最適解は，

x01=140 x02=220 x03=50 x04=140

x12=0 x16=140 x23=100 x27=120

x34=0 x38=150 x45=20 x49=120

2.

新しく端点

を導入し，各期の需要の未充足分

を枝

0^′9

を通る量で表す．枝

，

，

，

を通る量は販売量を表す．ネットワークで表すと，

図表

のようになる．販売価格はマイナスをつけて表した．

問題は

総売り上げ

−

総仕入れ価格

−

在庫費用

─

ペナルティの合計

の最大化だが，本 文との連続性を考慮し，最小化問題として定式化してある．

min −99x16−93.5x27−101.2x38−99x49

+90x01+85x02+92x03+90x04

+108x₀′6+102x₀′7+110.4x₀′8+108x₀′9

+3x12+3x23+3x34+3x45

s.t. −x₀₁−x₀₂−x₀₃−x₀₄−x₀₀′ = −550 x01−x12−x16=0

x12+x02−x23−x27=0 x23+x03−x34−x38=0 x34+x04−x45−x49=0 x₄₅=20

x16+x0^′6=140 x₂₇+x₀′7=120 x38+x0^′8=150 x49+x0^′9=120

x00^′−x0^′6−x0^′7−x0^′8−x0^′9=0

x12≤100, x23≤100, x34≤100, x45≤100 x_ij≥0, ij

はすべての枝

図表

需要不足のペナルティを考慮したガソリン販売

0

1 2 3 4 5

6 140 7 8 9 120

-550

20 [90] [85] [92] [90]

[3] [3] [3] [3]

0’

120 150

[-99]

[-99] [-93.5] [-101.2]

[108] [102] [110.4] [108]

参考までに最適解を示す．

x₀₁=140 x₀₂=220 x₀₃=50 x₀₄=140 x₁₂=07 x₁₆=140 x₂₃=100 x₂₇=120

x34=0 x38=150 x45=20 x49=120

x0^′6=0 x0^′7=0 x0^′8=0 x0^′9=0

2.5

min 500x₁₃+500x₄₆+500x₇₉+500x_10,12+650x₂₃+650x₅₆+650x₈₉+650x_11,12 +100x36+100x69+100x9,12

s.t. −x₁₃−x_1,13= −80, −x₂₃−x_2,13= −20

−x46−x4,13= −80, −x56−x5,13= −20

−x79−x7,13= −80, −x89−x8,13= −20

−x10,12−x10,13= −80, −x11,12−x11,13= −20 x1,3+x2,3−x3,6=85

x_3,6+x_4,6+x_5,6−x_6,9=60 x6,9+x7,9+x8,9−x9,12=90 x_9,12+x_10,12+x_11,12=105 x1,13+x2,13+· · ·+x12,13=60 xij≥0, ij

はすべての枝

参考までに最適解のうち非負の値を持つもののみ示す．

x13=80 x23=5 x2,13=15 x46=75 x4,13=5 x5,13=20 x69=15 x79=80 x8,13=20 x9,12=5 x10,12=80 x11,12=20

2.6

図表

参照．

枝

が店頭に残るレンタカーを表す．

枝

は，

日でメンテナンスを終えるレンタカーを表す．

枝

は，

日でメンテナンスを終えるレンタカーを表す．

枝

は，姉妹店から借りてくるレンタカーを表す．

図表

レンタカーショップの運用モデル

[q] [q] [q] [q] [q]

[p] [p] [p] [p] [q]

d6

d1 d2 d3 d4 d5

−Σ^dj

-d2

-d1 -d3 -d4 -d5 -d6

Σ

30+ dj

1

1’

2 3 4 5 6 7

2’ 3’ 4’ 5’ 6’

0 9 8

2.7

省略

2.8

最大移動距離の最小化は次のようになる．c

は，i から

までの距離を表す．

min y

s.t. y−c1Ax1A−c1Bx1B−c1Cx1C≥0 y−c2Ax2A−c2Bx2B−c2Cx2C≥0 ...

y−c12Ax12A−c12Bx12B−c12Cx12C≥0 x_iA+x_iB+x_iC=1, i=1, . . . , 12 x1A+x2A+· · ·+x12A=6

x1B+x2B+· · ·+x12B=3 x_1C+x_2C+· · ·+x_12C=3

xij

は

または

をとる

この問題は，ネットワークの構造に新しい制約が付け加わっているため整数性を持たない．

そのため，整数条件が必要である．詳しくは

章で説明する．

2.9

従業員

を仕事

にわりあてたとき，x

は

とする．

min 5xA1+4xA2+8xA3+7xA4+3xA5+4xB2+9xB3+11xB4+5xB5

6x_C1+5x_C2+8x_C3+5x_C4+4x_C5+7x_D1+9x_D2+11x_D3+6x_E1+8x_E2+10x_E3 s.t. xA1+xC1+xD1+xE1=1

xA2+xB2+xC2+xD2+xE2=1 xA3+xB3+xC3+xD3+xE3=1 xA4+xB4+xC4=1

x_A5+x_B5+x_C5=1

xA1+xA2+xA3+xA4+xA5=1 x_B2+x_B3+x_B4+x_B5=1 xC1+xC2+xC3+xC4+xC5=1 xD1+xD2+xD3=1

xE1+xE2+xE3=1

xij ≥0, i=A, B, . . . , E; j=1, . . . , 5

参考までに，最適な割り当てを示す．

A−5 B−4 C−1 D−2 E−3

2.10

1.

この問題をネットワークとして表現すると図表

のようになる．枝の費用

学生の満足 度) は省略してある．端点

の供給量

は，ゼミの総定員

と学生数

の差を表す．

図表

演習問題

の解答例

1 2 3 4 5 6 7 8 9 10 0

A B C

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2

4 4 4

2.

図表

参照．

図表

で，上は

部グラフでない場合の解答例，下は

部グラフで表した場合の解答例で ある．

いずれの場合もゼミの定員

名を，最低人数の分

名と，その他の

名にわけて表してある．

端点

，

，

が最低埋めるべき定員に対応しており，端点

，

，

が必ずしも充足しな くて良い人数に対応している．A

，B

，C

にのみ，2 名

の供給を 持つ端点

から枝が張られる．

2

部グラフで表現した場合，同じクラスへの所属を表す枝の費用は同じである．すなわち，

u_1A=u_1A′

．

図表

演習問題

の解答例；下の図は

部グラフの場合

1 2 3 4 5 6 7 8 9 10 0

A B C

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2

2 2 2

A’ B’ C’

2 2 2

1 2 3 4 5 6 7 8 9 10 0

A B C

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2

2 2 2

A’ B’ C’

2 2 2

図表

演習問題

の解答例

<6>

<5>

<4>

<3>

<4>

[-1]

<3>

<3>

<3>

<3>

<3>

<3>

<3>

1

2

3

4

5

6

7

8

9

10

11

12

13

14

2.11

図表

参照．

枝

・

・

・

・

・

・

の上限は

種のチョコレートの作成数

個

を表す．

枝

・10,14・11,14・

の上限は

つの箱に詰められるチョコレートの数を表す．

破線で表されている枝の上限は

である．

参考までに結果を記せば，最大流は

となり，

つの箱にすべて異なる種類のチョコレート を詰めることは可能である．

2.13

時間分析の結果は以下の表の通り．工程名，先行アクティビティは省略した．

工程 作業時 間

最早開 始時刻

最遅完 了時刻

全余裕 時間

自由余 裕時間

安全余 裕時間

s. 0 0 0 0 0 0

a. 2 0 2 0 0 0

b. 4 2 6 0 0 0

c. 10 6 16 0 0 0

d. 7 16 27 4 2 4

e. 4 16 22 2 0 2

f. 5 20 27 2 0 0

g. 6 16 22 0 0 0

h. 7 22 29 0 0 0

i. 8 25 35 2 0 0

j. 15 29 44 0 0 0

k. 4 33 40 3 1 1

l. 5 33 40 2 0 0

m. 2 44 46 0 0 0

n. 6 38 46 2 2 0

t. 0 46 46 0 0 0

2.14

プロジェクトネットワーク図の例は

と

はそれぞれスタートとフィニッシュを

表すアクティビティ．クリティカルパスは，

→

→

→

→

で，プロジェクト全体の所

要時間は

図表

プロジェクト・ネットワーク図

S

A D

E

F G

H

B C

I

T 0 [0,0]

5 [0,21]

13 [0,13]

10 [0,13]

1 [5,27]

3 [5,24]

6 [13,19]

6 [10,19] 8 [19,27]

3 [13,27]

0[27,27]

端点の上の数値は，作業時間 [最早開始時刻，最遅完了時刻] を表す

2.15

プロジェクトネットワーク図は

を用いる．

図表

プロジェクト・ネットワーク図

s

a

b

c

d

e

t

アクティビティの集合を

とおく．

である．アクティビティ

の 所用時間を

とし，その開始時刻を

とおく．

目標終了時刻を

としたときに，費用を最小化する問題は以下のようになる．

min −0.5x_a−0.3x_b−0.8x_c−0.2x_d−0.5x_e s.t. ys−ya=0

ys−yb=0 ya+xa−yc≤0 ya+xa−yd≤0 y_b+x_b−y_e≤0 yc+xc−ye≤0 y_d+x_d−y_t≤0 ye+xe−yt≤0 yt≤T

3≤xa≤8 4≤xb≤7 3≤x_c≤9 2≤xd≤6 5≤x_e≤5

yj≥0, j∈{s, a, b, c, d, e, t}