第八回　 シンプレックス表の経済的解釈 2003.5.15 山梨大学

内容と目標 内容： １．双対問題と双対問題の例 ２．シンプレックス表の経済的解釈 ３．シャドウ・プライスの意味を学ぶ 目標：   目標： １．双対問題を復習する ２．自分で双対問題を作る ３．シンプレックス表の経済的意味を理解する 2003.5.15 山梨大学

双対問題ー原問題Ⅰ 目的関数 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 山梨大学

双対問題Ⅱ 目標関数 Min. z = b1y1+b2y2+…+bmym (3) 制約条件 a11y1+a21y2+…+am1ym ≧ c1 ……………………………. 　　 a1ny1+a2ny2+…+amnym≧ cn y1, y2, …, ym≧0 2003.5.15 山梨大学

原問題Ⅰー＞双対問題Ⅱ 　　問題IIの条件式の係数は、問題Ｉの条件式の係数を縦に用い、問題IIの条件式の定数は、問題Ｉの目的関数の係数である。また、問題IIの目的関数の係数は、問題Ｉの条件式の定数である。　これらの関係は、次のように書いて示す。 2003.5.15 山梨大学

原問題ー＞双対問題 [c1 c2 … cn] 2003.5.15 山梨大学

原問題と双対問題の関係 ２）原問題と双対問題の関係は逆も成り立つ。問題IIを原問題と考えれば、問題Ｉは、その双対問題になる。 2003.5.15 山梨大学

双対問題の例 　　例：原料A1 , A2, A3を用いて、２種類の製品B1 , B2を作る工場があり、原料の使用量、制限および製品から得られる利益は、以下の表に示したとおりである。利益を最大にする生産計画を立てよ。 2003.5.15 山梨大学

この問題を数式の形にすれば、B1 , B2の生産量をx1 , x2としたとき、以下のような線形計画問題になる。   B1 　　 B2 制　　限 　A1 　A2 　A3 4 　 3 3 　 2 7 　 2 39 18 56 利　　益 2 　 1 　　この問題を数式の形にすれば、B1 , B2の生産量をx1 , x2としたとき、以下のような線形計画問題になる。 2003.5.15 山梨大学

例の原問題 目的関数 Max. f = 2x1+x2 (5) 制約条件 4x1+3x2 ≦ 39 3x1+2x2 ≦ 18 (6) 2003.5.15 山梨大学

例の双対問題 　　ある会社が、原料A1 , A2, A3をすべて買い取りたい。このとき、買取会社が工場に対して申し出る価格を、どのように考えて決めればよいであろうか。A1 , A2, A3の各１単位分の申し出価格をy1 , y2, y3とすると、買取会社としては、全体の買取価格をなるべく安くしたいと考えるであろう。 2003.5.15 山梨大学

双対問題の解釈 　　製品B1の１単位分に相当する買取価格は4y1+3y2+7y3になるが、これがB1の１単位分の利益を下回っては、工場側は売る気にならないであろう。したがって4y1+3y2+7y3は2以上の値にならないと、商談は成立しない。B2についても同様である。結局、y1 , y2, y3に対しては, つぎのような線形計画問題になる。 2003.5.15 山梨大学

条件(8)のもとで(7)を最小にするというのが、買取会社の問題で、これは(5)、(6)の問題の双対問題になっている。 目的関数 　　 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 山梨大学

シンプレックス表の経済的解釈 原問題として、ステップ２で最適解が得られ ている。このステップ２から、次のことがわかる。 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 山梨大学

　　原料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 山梨大学

これに反して、使い残りのあるA1、A3は制限量を減らしても利益に影響はない。言い換えると、この時点ではA2 の１単位は2/3の価値があり、A1、A3の価値は０であると考えることができる。この意味の価値をシャドウ・プライスまたは帰属価格と呼んでいる。 2003.5.15 山梨大学

表の太ワクbの部分がそのシャドウ・プライスで、これをv1、v2 、v3で示すことにすれば である。もし、この時点で原料の制限を緩和して、B1を1単位作ることを考えると、それに要する原料はA1, A2, A3がそれぞれ4, 3, 7単位で、その原料の価値をシャドウ・プライスで測ると 　　 4v1+3v2+7v3 = 4×0+3×2/3+7×0 = 2 2003.5.15 山梨大学

であるから、B1１単位から得られる利益は１で、差し引き1/3の損失と考えることができ、そのことを太ワクa内の1/3が示している。 　　これはＢ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 山梨大学

以上述べた、原料のシャドウ・プライスと製品の利益の大小関係を式にすれば 　　以上述べた、原料のシャドウ・プライスと製品の利益の大小関係を式にすれば 　　　 4v1+3v2+7v3 = 2 　　　 3v1+2v2+2v3 > 1 　である。また、v1, v2, v3 は最終ステップのｆ行の数であるから非負である。したがって、v1, v2, v3は双対問題の条件式(8)の解である。 2003.5.15 山梨大学

であるが、これは最初に与えられた原料全体の価値をシャドウ・プライスで測ったものといえよう。いまの場合、その価値は 　 目的関数の(7)にこの解を代入すれば 　　　 Min. z= 39v1+18v2+56v3 であるが、これは最初に与えられた原料全体の価値をシャドウ・プライスで測ったものといえよう。いまの場合、その価値は 　　　 z = 39×0+18×2/3+56×0 = 12 で、これは原問題のｆの最大値に一致する。 2003.5.15 山梨大学

課　題 　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 山梨大学