シンプレックス表の解釈

Report
第八回
シンプレックス表の経済的解釈
2003.5.15
山梨大学
1
内容と目標
内容:
1.双対問題と双対問題の例
2.シンプレックス表の経済的解釈
3.シャドウ・プライスの意味を学ぶ
目標:
1.双対問題を復習する
2.自分で双対問題を作る
3.シンプレックス表の経済的意味を理解する
2003.5.15
山梨大学
2
双対問題ー原問題Ⅰ

目的関数
Max. f = c1x1+c2x2+…+cnxn

(1)
制約条件
a11x1+ a12x2+…+a1nxn ≦ b1
a21x1+a22x2+…+a2nxn ≦ b2
(2)
…………………………….
am1x1+am2x2+…+amnxn≦bm
x1, x2, …, xn≧0
2003.5.15
山梨大学
3
双対問題Ⅱ

目標関数
Min. z = b1y1+b2y2+…+bmym

(3)
制約条件
a11y1+a21y2+…+am1ym ≧ c1
a12y1+a22y2+…+am2ym ≧ c2
(4)
…………………………….
a1ny1+a2ny2+…+amnym≧ cn
y1, y2, …, ym≧0
2003.5.15
山梨大学
4
原問題Ⅰー>双対問題Ⅱ
問題IIの条件式の係数は、問題Iの
条件式の係数を縦に用い、問題IIの条
件式の定数は、問題Iの目的関数の係
数である。また、問題IIの目的関数の
係数は、問題Iの条件式の定数である。
これらの関係は、次のように書いて示
す。
2003.5.15
山梨大学
5
原問題ー>双対問題
y1
y2
.
.
.
ym
x1
x2 ... xn
a11 a12 ... a1n  b1 

 b2 
a21 a22 ... a2n   

 . 
.
.  
.
. 

.
.
.   
.


.
.   
.
bm 
a

 m1 am2 ... am n
[c1
2003.5.15
c2 …
山梨大学
cn]
6
原問題と双対問題の関係
1)問題IIは問題Iの双対問題とよばれ、
双対問題に対して元の問題Iを原問題と
いう。
2)原問題と双対問題の関係は逆も成り
立つ。問題IIを原問題と考えれば、問題
Iは、その双対問題になる。
2003.5.15
山梨大学
7
双対問題の例
例:原料A1 , A2, A3を用いて、2種類
の製品B1 , B2を作る工場があり、原料の
使用量、制限および製品から得られる利
益は、以下の表に示したとおりである。
利益を最大にする生産計画を立てよ。
2003.5.15
山梨大学
8
A1
A2
A3
利
益
B1
B2
4
3
7
3
2
2
2
1
制
限
39
18
56
この問題を数式の形にすれば、B1 , B2の生
産量をx1 , x2としたとき、以下のような線形
計画問題になる。
2003.5.15
山梨大学
9
例の原問題

目的関数
Max.

f = 2x1+x2
(5)
制約条件
4x1+3x2 ≦ 39
3x1+2x2 ≦ 18
(6)
7x1+2x2 ≦ 56
x1, x2≧0
2003.5.15
山梨大学
10
例の双対問題
ある会社が、原料A1 , A2, A3をすべて買い
取りたい。このとき、買取会社が工場に対し
て申し出る価格を、どのように考えて決めれ
ばよいであろうか。A1 , A2, A3の各1単位分
の申し出価格をy1 , y2, y3とすると、買取会社
としては、全体の買取価格をなるべく安くし
たいと考えるであろう。
2003.5.15
山梨大学
11
双対問題の解釈
製品B1の1単位分に相当する買取価格は
4y1+3y2+7y3になるが、これがB1の1単位分の
利益を下回っては、工場側は売る気にならない
であろう。したがって4y1+3y2+7y3は2以上の値
にならないと、商談は成立しない。B2について
も同様である。結局、y1 , y2, y3に対しては, つ
ぎのような線形計画問題になる。
2003.5.15
山梨大学
12

目的関数
Min. z = 39y1+18y2+56y3

(7)
制約条件
4y1+3y2 +7y3 ≧ 2
(8)
3y1+2y2+2y3 ≧ 1
y1, y2, y3 ≧0
条件(8)のもとで(7)を最小にするというのが、
買取会社の問題で、これは(5)、(6)の問題の双対
問題になっている。
2003.5.15
山梨大学
13
シンプレックス表の経済的解釈
原問題として、ステップ2で最適解が得られ
ている。このステップ2から、次のことがわかる。
1) 基底変数はλ1、x1 、λ3で、非基底変数はx2、
λ2である。最適基底解における各変数の値は
x1 =6, x2 =0, λ1 =15, λ2 =0, λ3=14
2) f行によれば、非基底変数のx2 が1単位増加すれ
ば、fの値は1/3だけ減少し、同じくλ2 が1単位
増加すれば、fの値は2/3だけ減少する。
2003.5.15
山梨大学
14
原料A1、A2 、A3の使い残りをλ1、λ2 、λ3で表した
が、(1)によりλ2=0,λ1 >0,λ3>0であるから、A2 は
使い切ってしまい、A1、A3は残りがあることにな
る。ここでλ2 を0から1にするということは、使
い切ることになっていたA2 を1単位使い残すこと
で、これはA2 の制限量を18から17に減らした状
態と同じことであるが、(2)によると、このとき利
益が2/3だけ減少したことになる。
2003.5.15
山梨大学
15
これに反して、使い残りのあるA1、A3は
制限量を減らしても利益に影響はない。言
い換えると、この時点ではA2 の1単位は
2/3の価値があり、A1、A3の価値は0である
と考えることができる。この意味の価値を
シャドウ・プライスまたは帰属価格と呼ん
でいる。
2003.5.15
山梨大学
16
表の太ワクbの部分がそのシャドウ・プライス
で、これをv1、v2 、v3で示すことにすれば
v1=0, v2 =2/3, v3=0
である。もし、この時点で原料の制限を緩和して、
B1を1単位作ることを考えると、それに要する原
料はA1, A2, A3がそれぞれ4, 3, 7単位で、その原
料の価値をシャドウ・プライスで測ると
4v1+3v2+7v3 = 4×0+3×2/3+7×0 = 2
2003.5.15
山梨大学
17
これはB11単位から得られる利益の2に等しい。
すなわち、2の価値を持つ原料を使用して、2の
利益を得る製品を作ることになり、損失を考える
なら0である。実は表の太ワクa内の0がこのこ
とを示している。同様に、B2 を1単位作るとすれ
ば、原料のシャドウ・プライスは、
3v1+2v2+2v3 = 3×0+2×2/3+2×0 = 4/3
であるから、B11単位から得られる利益は1で、
差し引き1/3の損失と考えることができ、そのこと
を太ワクa内の1/3が示している。
2003.5.15
山梨大学
18
以上述べた、原料のシャドウ・プライスと製
品の利益の大小関係を式にすれば
4v1+3v2+7v3 = 2
3v1+2v2+2v3 > 1
である。また、v1, v2, v3 は最終ステップのf行
の数であるから非負である。したがって、v1, v2,
v3は双対問題の条件式(8)の解である。
2003.5.15
山梨大学
19
目的関数の(7)にこの解を代入すれば
Min. z= 39v1+18v2+56v3
であるが、これは最初に与えられた原料全体の
価値をシャドウ・プライスで測ったものといえ
よう。いまの場合、その価値は
z = 39×0+18×2/3+56×0 = 12
で、これは原問題のfの最大値に一致する。
2003.5.15
山梨大学
20
課 題
4種類の食品F1, F2, F3, F4がある。それぞれの1単位中に含まれるビタミン
A, Bの量および各食品1単位の価格が、以下の表のとおりである。
F1
F2
F3
F4
必要量
A
2
3
1
1
20
B
1
0
1
2
18
価格 5
4
6
7
ある主婦が、この4種類の食品を用いて、ビタミンAが少なくとも20単
位、ビタミンBが少なくとも18単位含まれている料理を、なるべく安い価
格で作りたいと考えた。各食品の使用量を決定せよ。
この問題について、元の線形計画問題とその双対問題を作れ。原問題と双
対問題をそれぞれシンプレックス法で解け。原問題の変数・スラック変数と
双対問題の変数・スラック変数を比較する。例に参考して、シャドウ・プラ
イスを説明せよ。
2003.5.15
山梨大学
21

similar documents