オペレーションズリサーチ　中間試験解答例

オペレーションズリサーチ 中間試験解答例

２００７年１１月２７日

bababababababababababababababababababab

問題１

次の線形計画問題を２段階シンプレックス法により解け。解答にあたり、各反復で基底に入る または出る変数の選択理由を明記するように。

最大化

z = 2x 1 − 3x 2 + 3x 3 − 2x 4

制約条件

x 1 + 3x 2 + 2x 3 − x 4 = 12, 3x ₁ − x ₂ + x ₃ = 21,

x ₁ ≥ 0, x ₂ ≥ 0, x ₃ ≥ 0, x ₄ ≥ 0.

人工変数

x 5 , x 6

を導入した人工問題を考え、その人工変数を基底とした辞書をつくる。

最大化

w(= − x 5 − x 6 ) = − 33 + 4x 1 + 2x 2 + 3x 3 − x 4

制約条件

x ₅ = 12 − x ₁ − 3x ₂ − 2x ₃ + x ₄ , x ₆ = 21 − 3x ₁ + x ₂ − x ₃ , x _i ≥ 0 (i = 1, 2, 3, 4, 5, 6).

目的関数の中で非基底変数

x ₁

にかかる係数は

4

で正なので、これを基底変数にする。

x ₁

を増やして いったとき、最初に

0

となる基底変数は

x ₆

なので、これを非基底変数とする。すると次の辞書を得る。

最大化

w = − 5 + 10 3 x ₂ + 5

3 x ₃ − x ₄ − 4 3 x ₆

制約条件

x ₁ = 7 + 1

3 x ₂ − 1 3 x ₃ − 1

3 x ₆ , x 5 = 5 − 10

3 x 2 − 5

3 x 3 + x 4 + 1 3 x 6 , x _i ≥ 0 (i = 1, 2, 3, 4, 5, 6).

目的関数の中で非基底変数

x 2

にかかる係数は

¹⁰ ₃

で正なので、これを基底変数にする。

x 2

を増やして いったとき、最初に

0

となる基底変数は

x 5

なので、

x 5

を非基底変数とする。すると次の辞書を得る。

最大化

w = − x 5 − x 6

制約条件

x 1 = 15 2 − 1

2 x 3 + 1

10 x 4 − 1

10 x 5 , − 3 10 x 6

x 2 = 3 2 − 1

2 x 3 + 3

10 x 4 − 3

10 x 5 + 1 10 x 6 , x i ≥ 0 (i = 1, 2, 3, 4, 5, 6).

最適値が

0

となり、基底変数に人工変数が含まれない辞書が得られた。このとき、

x 1 , x 2

を基底変数と

1

した元の問題の辞書をつくることができる。

最大化

z = 21 2 + 7

2 x ₃ − 27 10 x ₄

制約条件

x ₁ = 15

2 − 1 2 x ₃ + 1

10 x ₄ , x ₂ = 3

2 − 1 2 x ₃ + 3

10 x ₄ , x _i ≥ 0 (i = 1, 2, 3, 4).

目的関数の中で非基底変数

x 3

にかかる係数は

⁷ ₂

で正なので、これを基底変数にする。

x 3

を増やして いったとき、最初に

0

となる基底変数は

x 2

なので、

x 2

を非基底変数とする。すると次の辞書を得る。

最大化

z = 21 − 7x 2 − 3 5 x 4

制約条件

x 1 = 6 + x 2 − 1 5 x 4 , x ₃ = 3 − 2x ₂ + 3

5 x ₄ , x i ≥ 0 (i = 1, 2, 3, 4).

この辞書の目的関数において、係数が正である非基底変数は存在しない。よって、問題の最適解は

(x 1 , x 2 , x 3 , x 4 ) = (6, 0, 3, 0)

であり、そのときの最適値は

21

となる。

bababababababababababababababababababab

問題２

次のような線形計画問題の主問題と双対問題について考える。

主問題：

最大化

− 4x ₁ + 8x ₂ + 14x ₃ − 4x ₄ + 2x ₅

制約条件

x ₁ + 2x ₂ + 3x ₃ + 2x ₄ + x ₅ = 8, 2x ₁ + x ₂ + x ₃ + x ₄ + 3x ₅ = 9, x ₁ + x ₂ + 2x ₃ + 2x ₅ = 7, x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0.

双対問題：

最小化

8y ₁ + 9y ₂ + 7y ₃

制約条件

y ₁ + 2y ₂ + y ₃ ≥ − 4,

2y ₁ + y ₂ + y ₃ ≥ 8, 3y ₁ + y ₂ + 2y ₃ ≥ 14, 2y 1 + y 2 ≥ − 4, y 1 + 3y 2 + 2y 3 ≥ 2.

今、主問題の最適解の候補が

4

つ、双対問題の最適解の候補が

3

つある。これらの中に最適解が あれば全て選び、その理由を分かりやすく説明せよ。



 

 

 x 1

x 2

x 3

x 4

x 5



 

 



=



 

 

 0 1 1 0 3



 

 

 ,



 

 

 3 0 1.5

0 0.5



 

 

 ,



 

 

 0 3 0 0 2



 

 

 ,



 

 

 2 0 3 0 1



 

 

 .



 y 1

y 2

y 3



 =



 3

− 5 7



 ,



 3

− 8 12



 ,



 4

− 2 2



 .

まず、実行可能性について調べる。

³

0 1 1 0 3

´ T

と

³

2 0 3 0 1

´ T

は主問題の制約条件

2

を満たしておらず、実行可能解ではない。よって最適解とは成り得ない。残りの

³

3 0 1.5 0 0.5

´ ^T

と

³

0 3 0 0 2

´ ^T

は主問題の実行可能解となっている。また、

³

3 − 5 7

´ ^T

と

³

3 − 8 12

´ ^T

と

³

4 − 2 2

´ ^T

は、全て双対問題の実行可能解である。

次に、各実行可能解の目的関数値を計算する。すると、主問題の実行可能解

³

0 3 0 0 2

´ ^T

の目 的関数値と、双対問題の実行可能解

³

3 − 5 7

´ ^T , ³

4 − 2 2

´ ^T

の目的関数値は共に

28

となり等し いことが分かる。すると双対定理より、これらは主問題と双対問題の最適解であるといえる。

bababababababababababababababababababab

問題３

次の数理計画問題に関して以下の問いに答えよ。

最小化

2x ² − 2xy + 3y ² + x − 3y

制約条件

x + 2y ≥ 4,

− 3x + 2y ≤ − 6, x ≥ 0.

1.

この問題を２次計画問題の形に変換せよ。目的関数の凸性は証明しなくてよい。

2. 1.

の双対問題を述べよ。

1. •

目的関数を最大化にする。

•

１番目の不等式制約の両辺に

− 1

をかける。

•

^自由変数

y

を、二つの非負変数の差

y = y ₁ − y ₂

で表す。

最大化

¡

− 1 3 − 3 ¢ 

 x y ₁ y 2



 − 1 2

¡ x y ₁ y ₂ ¢ 



4 − 2 2

− 2 6 − 6 2 − 6 6







 x y ₁ y 2





制約条件

µ − 1 − 2 2

− 3 2 − 2

¶ 

 x y 1

y 2



 ≤ µ − 4

− 6

¶ ,



 x y 1

y 2



 ≥



 0 0 0



 .

2.

双対問題は次のようになる。

最小化

¡

− 4 − 6 ¢ µ z w

¶ + 1

2

¡ x y ₁ y ₂ ¢ 



4 − 2 2

− 2 6 − 6 2 − 6 6







 x y ₁ y ₂





制約条件



 − 1 − 3

− 2 2 2 − 2



 µ z w

¶

≥



 − 1 3

− 3



 −





4 − 2 2

− 2 6 − 6 2 − 6 6







 x y ₁ y ₂



 , µ z

w

¶

≥ µ 0

0

¶ .

3

bababababababababababababababababababab

問題４

関数

f (x, y, z) = x + y ² + z ⁴ + e ^(x

²

^+y

²

^+z

²

⁾

の最小化を行いたい。変数に関して次のような条件 があるとき、局所的最小解であるための一次の必要条件（

KKT

条件）を求めよ。

1.

変数について特に条件が無い、つまり変数

x, y, z

が任意の実数をとれる場合。

2.

変数

x, y, z

が、

x ² + y ² + z ² ≤ 200

を満たさなければならない場合。

3.

変数

x, y, z

が、

x ² + y ² + z ² ≤ 200

で、さらに

z = x + y

を満たさなければならない 場合。

1.

多変数関数の（制約無し）最小化なので、一次の必要条件は勾配ベクトルがゼロベクトルになるこ

とである。



 

 

 



 

 

 



∂f

∂x = 1 + 2xe ^(x

²

^+y

²

^+z

²

⁾ = 0,

∂f

∂y = 2y + 2ye ^(x

²

^+y

²

^+z

²

⁾ = 0,

∂f

∂z = 4z ³ + 2ze ^(x

²

^+y

²

^+z

²

⁾ = 0,

2.

ラグランジュ関数は

L(x, y, z, u) = x + y ² + z ⁴ + e ^(x

²

^+y

²

^+z

²

⁾ + u(x ² + y ² + z ² − 200)

である。

よって、

KKT

条件は以下のように表せる。

 

 

 

 

 

 

 



∇ ^x L(x, y, z, u) = 1 + 2xe ^(x

²

^+y

²

^+z

²

⁾ + 2ux = 0,

∇ ^y L(x, y, z, u) = 2y + 2ye ^(x

²

^+y

²

^+z

²

⁾ + 2uy = 0,

∇ ^z L(x, y, z, u) = 4z ³ + 2ze ^(x

²

^+y

²

^+z

²

⁾ + 2uz = 0, x ² + y ² + z ² − 200 ≤ 0,

u ≥ 0,

u(x ² + y ² + z ² − 200) = 0.

3.

ラグランジュ関数は

L(x, y, z, u, v) = x+y ² +z ⁴ +e ^(x

²

^+y

²

^+z

²

⁾ +u(x ² +y ² +z ² − 200)+v(x+y − z)

で ある。よって、

KKT

条件は以下のように表せる。

 

 

 

 

 

 

 

 

 



∇ ^x L(x, y, z, u, v) = 1 + 2xe ^(x

²

^+y

²

^+z

²

⁾ + 2ux + v = 0,

∇ ^y L(x, y, z, u, v) = 2y + 2ye ^(x

²

^+y

²

^+z

²

⁾ + 2uy + v = 0,

∇ ^z L(x, y, z, u, v) = 4z ³ + 2ze ^(x

²

^+y

²

^+z

²

⁾ + 2uz − v = 0, x ² + y ² + z ² − 200 ≤ 0,

u ≥ 0,

u(x ² + y ² + z ² − 200) = 0, x + y − z = 0.

4