第八回シンプレックス表の経済的解釈 2003.5.15 山梨大学 1 内容と目標内容：１．双対問題と双対問題の例２．シンプレックス表の経済的解釈３．シャドウ・プライスの意味を学ぶ目標：１．双対問題を復習する２．自分で双対問題を作る３．シンプレックス表の経済的意味を理解する 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の条件式の係数は、問題Ｉの条件式の係数を縦に用い、問題IIの条件式の定数は、問題Ｉの目的関数の係数である。また、問題IIの目的関数の係数は、問題Ｉの条件式の定数である。これらの関係は、次のように書いて示す。 2003.5.15 山梨大学 5 原問題ー＞双対問題 y1 y2 . . . ym x1 x2 ... xn a11 a12 ... a1n    a21 a22 ... a2 n    . .  . . . .    . .  .   a a ... a m2 mn   m1 [c1 2003.5.15 c2 … 山梨大学 b1  b   2 .    .  .    bm  cn] 6 原問題と双対問題の関係１）問題IIは問題Ｉの双対問題とよばれ、双対問題に対して元の問題Ｉを原問題という。２）原問題と双対問題の関係は逆も成り立つ。問題IIを原問題と考えれば、問題Ｉは、その双対問題になる。 2003.5.15 山梨大学 7 双対問題の例例：原料A1 , A2, A3を用いて、２種類の製品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の各１単位分の申し出価格をy1 , y2, y3とすると、買取会社としては、全体の買取価格をなるべく安くしたいと考えるであろう。 2003.5.15 山梨大学 11 双対問題の解釈製品B1の１単位分に相当する買取価格は 4y1+3y2+7y3になるが、これがB1の１単位分の利益を下回っては、工場側は売る気にならないであろう。したがって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 シンプレックス表の経済的解釈原問題として、ステップ２で最適解が得られている。このステップ２から、次のことがわかる。 1) 基底変数はλ1、x1 、λ3で、非基底変数はｘ2、 λ２である。最適基底解における各変数の値は x1 =6, x2 =0, λ1 =15, λ2 =0, λ3=14 2) f行によれば、非基底変数のx2 が１単位増加すれば、ｆの値は1/3だけ減少し、同じくλ2 が１単位増加すれば、ｆの値は2/3だけ減少する。 2003.5.15 山梨大学 14 原料A1、A2 、A3の使い残りをλ1、λ2 、λ3で表したが、(1)によりλ2=0,λ1 >0,λ3>0であるから、A2 は使い切ってしまい、A1、A3は残りがあることになる。ここでλ2 を０から１にするということは、使い切ることになっていたA2 を１単位使い残すことで、これはA2 の制限量を18から17に減らした状態と同じことであるが、(2)によると、このとき利益が2/3だけ減少したことになる。 2003.5.15 山梨大学 15 これに反して、使い残りのあるA1、A3は制限量を減らしても利益に影響はない。言い換えると、この時点ではA2 の１単位は 2/3の価値があり、A1、A3の価値は０であると考えることができる。この意味の価値をシャドウ・プライスまたは帰属価格と呼んでいる。 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 これはＢ1１単位から得られる利益の２に等しい。すなわち、２の価値を持つ原料を使用して、２の利益を得る製品を作ることになり、損失を考えるなら０である。実は表の太ワクa内の０がこのことを示している。同様に、B2 を1単位作るとすれば、原料のシャドウ・プライスは、 3v1+2v2+2v3 = 3×0+2×2/3+2×0 = 4/3 であるから、B1１単位から得られる利益は１で、差し引き1/3の損失と考えることができ、そのことを太ワクa内の1/3が示している。 2003.5.15 山梨大学 18 以上述べた、原料のシャドウ・プライスと製品の利益の大小関係を式にすれば 4v1+3v2+7v3 = 2 3v1+2v2+2v3 > 1 である。また、v1, v2, v3 は最終ステップのｆ行の数であるから非負である。したがって、v1, v2, v3は双対問題の条件式(8)の解である。 2003.5.15 山梨大学 19 目的関数の(7)にこの解を代入すれば Min. z= 39v1+18v2+56v3 であるが、これは最初に与えられた原料全体の価値をシャドウ・プライスで測ったものといえよう。いまの場合、その価値は z = 39×0+18×2/3+56×0 = 12 で、これは原問題のｆの最大値に一致する。 2003.5.15 山梨大学 20 課題 4種類の食品F1, F2, F3, F4がある。それぞれの１単位中に含まれるビタミン A, Bの量および各食品１単位の価格が、以下の表のとおりである。 F1 F2 F3 F4 必要量 A 2 3 1 1 20 B 1 0 1 2 18 価格 5 4 6 7 ある主婦が、この４種類の食品を用いて、ビタミンＡが少なくとも２０単位、ビタミンＢが少なくとも１８単位含まれている料理を、なるべく安い価格で作りたいと考えた。各食品の使用量を決定せよ。この問題について、元の線形計画問題とその双対問題を作れ。原問題と双対問題をそれぞれシンプレックス法で解け。原問題の変数・スラック変数と双対問題の変数・スラック変数を比較する。例に参考して、シャドウ・プライスを説明せよ。 2003.5.15 山梨大学 21