数理ファイナンス入門
付録Ａ 線形計画法 第１版 2001年5月7日
■まとめ
(A.1)...主問題
minimize cTＸ
Ａ・Ｘ≧ｂ
Ｘ≧０
(A.2)...双対問題
maximize ＹTｂ
ＡT・Ｙ≦ｃ
Ｙ≧０
主問題の解の存在と、双対問題の解の存在は同値であり、解が存在すれば目的関数の値も等しい。
■Ｑ＆Ａ
1).線形計画法って何ですか？
一次不等式で表された制限条件の中で、目的の達成度を最大にする最適の方法を求める数学的技法で、
1947年に米国の数学者ダンツィグ(G.B. Dantzig)によって開発されました。
Dantzigのシンプレックス法の開発によって、その後急速に注目されるようになりました。
経営計画(経営資源の最適配分etc)・輸送計画などに多く利用され、リニアプログラミング(略してLP)とも呼ばれます。
2).線形計画法の良い教科書を教えてください。
この「数理ファイナンス入門」を理解するためだけに、線形計画法を別に勉強するのは
やめた方がいいと思います。この付録を大体理解できればそれで良しとしないと、時間がいくらあっても足りません。
＜それでも...という方に＞
線形計画法というタイトルの書籍は最近ちっとも店頭で見かけません。昔は多かったんですが...
（線形代数の書籍は多いですね？？数理計画法というタイトルの方が多いのかな？）
さて、大型書店に行ってみたら、
「線形計画法」今野浩 ／日科技連出版社 1987/03出版
だけがありました。教科書のような感じです。ちなみに、この本で問題回答のヒントを得ました。
あと絶版ですが、
「線形計画法」上・下
バシェク・フバ−タル/阪田省二郎 ／啓学出版 1988/09出版
が良いテキストのようです。良く大学院レベルの講義で利用されているようです。
それと、線形計画法を含む数理計画概論のオンラインテキストを見つけましたので、紹介します。
東京大学 総合文化研究科・広域科学専攻・広域システム科学系の 大勝研究室
（ここの、数理計画の中の第３章「線形計画法」を参照のこと。良くできています）
3).双対はなんて読むのですか？
「そうつい」です。上述の今野浩先生の本にもそう書いてあります。
今野先生はDantzig先生の弟子筋に当たり、この分野の権威ですから間違いないでしょう。
■問題回答
問Ａ．１
1).主問題の双対をとる
(A.1)
minimize cTＸ
Ａ・Ｘ≧ｂ
Ｘ≧０
これの双対をとると、
(A.2)
maximize ＹTｂ
ＡT・Ｙ≦ｃ
Ｙ≧０
(*).経済分野の数学では、転置行列をＡTでなく、Ａ’と表記することが多いようです。理工系ではまずみかけません。
2).(A.2)を主問題の形式に変形する
ｂ*≡−ｂ
Ａ*≡−ＡT
ｃ*≡−ｂ
と定義すると、(A.2)は
maximize −ＹTｂ*
−Ａ*・Ｙ≦−ｃ*
Ｙ≧０
となり、整理して
(A.3)
minimize ＹTｂ*
Ａ*・Ｙ≧ｃ*
Ｙ≧０
となって、主問題の形式になる。
3).(A.3)の双対問題
(A.3)の双対問題は、
(A.4)
maxmize ＺT・ｃ*
Ａ*T・Ｚ≦ｂ*
Ｚ≧０
であり、ｂ、Ａ，ｃで表記すると
maxmize −ＺT・ｃ
−Ａ・Ｚ≦−ｂ
Ｚ≧０
となり、
(A.5)
minmize ＺT・ｃ＝ｃT・ＺT
Ａ・Ｚ≧ｂ
Ｚ≧０
より、(A.1)と同値になった。
以上より、(A.1)の双対の双対は(A.1)である。
以下の変形は線形計画法の常套手段らしいです。これを知らないと、以下の問題はちょっと解けません。
・等号の条件を不等式の条件に変形する手段
Ａ・ｘ＝ｂで、Ａ*≡［Ａ, −Ａ］として、
Ａ*・ｘ≧ｂに変形する
・不等号の条件を等号の条件に変形する手段
Ａ・ｘ≦ｂ、ｘ≧０で、変数ｓを導入して
(Ａ・ｘ)＋ｓ＝ｂ、ｘ≧０、ｓ≧０に変形する
・ベクトルｘが無制約であることを制約条件に変形する手段
ｘ≡ｘA−ｘBとして、ｘA≧０、ｘB≧０とする。
(*).こうすると、ｘA≧０、ｘB≧０でも、ｘは正負なんでもとれます。
問Ａ．２
主問題は
minimize cTＸ
Ａ・Ｘ≧ｂ
で、この双対問題が
maximize ＹTｂ
ＡT・Ｙ＝ｃ
Ｙ≧０
であることを証明する。
1).主問題を変形する。
Ｘ≡ｘA−ｘBとすると、主問題は
minimize cT・（ｘA−ｘB）
Ａ・（ｘA−ｘB）≧ｂ
ｘA≧０、ｘB≧０
となり、ここで
Ａ*としてＡ, −Ａを横に並べたマトリクス、つまりＡ*≡［Ａ, −Ａ］
Ｘ*としてｘA, ｘBを縦に並べた列ベクトル
ｃ*をｃ, −ｃを縦に並べた列ベクトル
と定義すると
minimize c* T・Ｘ*
Ａ*・Ｘ*≧ｂ
Ｘ*≧０
という標準的な主問題になる。
2).双対形式をとる
これの双対は
maximize ＹTｂ
Ａ* T・Ｙ≦ｃ* ... (2-A)
Ｙ≧０
となり、Ａ*＝［Ａ, −Ａ］より、(2-A)式は
ＡT・Ｙ≦ｃ
−ＡT・Ｙ≦−ｃ
となり、整理して
ＡT・Ｙ≦ｃ
ＡT・Ｙ≧ｃ
であるから、
ＡT・Ｙ＝ｃ
である。
従って、双対形式は
maximize ＹTｂ
ＡT・Ｙ＝ｃ
Ｙ≧０
となり、証明できた。
問Ａ．３
主問題は
minimize cTＸ
Ａ・Ｘ＝ｂ
Ｘ≧０
で、この双対問題が
maximize ＹTｂ
ＡT・Ｙ≦ｃ
であることを証明する。
1).主問題を変形する。
Ａ・ｘ＝ｂは
Ａ・ｘ≧ｂ、かつ−Ａ・ｘ≧−ｂ
と同値なので、
| Ａ*≡ |
┌
│
│
└
|
Ａ
−Ａ
|
┐
│
│
┘
|
、 ｂ*≡ |
┌
│
│
└
|
ｂ
−ｂ
|
┐
│
│
┘
|
と定義すると、
|
主問題は、
minimize cTＸ
Ａ*・Ｘ≧ｂ*
Ｘ≧０
となる。
2).双対形式をとる
これの双対は、
maximize ＹTｂ*
Ａ* T・Ｙ≦ｃ*
Ｙ≧０
となり、Ｙ≡［ＹA, ＹB］として整理すると
maximize （ＹA−ＹB）Tｂ
ＡT・（ＹA−ＹB）≦ｃ
ＹA≧０、ＹB≧０
となり、新しくＹ≡（ＹA−ＹB）と定義すると、
maximize ＹTｂ
ＡT・Ｙ≦ｃ
Ｙは無制約
となり、証明できた。
問Ａ．４
主問題は
Ｘ1≧Ｘ2＋1
Ｘ1≦Ｘ2−2
と変形できるので、常にＸ2＋1＞Ｘ2−2なので、解を持たない。
双対問題は
maximize −Ｙ1＋2Ｙ2
Ｙ1−Ｙ2≦1
−Ｙ1＋Ｙ2≦-2
簡単すぎる問題だな〜。
問Ａ．５
1).(A.2)⇒Ｄｖ≦０、ｄｖ＞０が解を持つ
(A.2)が解を持つとすると、
| ｄ＝ |
┌
│
│
└
|
Ｙ
-1
|
┐
│
│
┘
|
とすれば、 |
Ｄ・ｖ＝ |
┌
│
│
└
|
ＡT−ｃ
−Ｙ
|
┐
│
│
┘
|
≦０となり、
|
ｄ・ｖ＝1＞0も成り立つので、Ｄ・ｖ≦０、ｄ・ｖ＞０は解ｖを持つ。
2).Ｄｖ≦０、ｄｖ＞０が解を持つ⇒(A.2)（実はこれは間違い）
Ｄｖ≦０、ｄｖ＞０が解を持つとすると、
| ｄ≡α・ |
┌
│
│
└
|
Ｙ
-1
|
┐
│
│
┘
|
とすれば、 |
α・｛ＡT・Ｙ−ｃ｝≦０
−α・Ｙ≦０
ｄ・ｖ＝α
が成り立ち、ｄ・ｖ＞０よりα＞０だから、
ＡT・Ｙ≦ｃ
Ｙ≧０
が解を持つことが分かる。
しかし、だからといって、max ＹT・ｂが存在するとは限りません。
解があるからといって、max ＹT・ｂが存在するとは限りません。
反例を示します。
（いや〜、証明しようとして苦労しました。）
反例
Ａ＝−Ｉのマトリックスとすれば、
Ｙ≧−ｃかつＹ≧０が解であり、いくらでも大きいＹが可能で、maxはとれない。
ということで、(A.2)⇒Ｄｖ≦０、ｄｖ＞０が解を持つということは成立しますが、逆は成立しません。
本文中では、(A.2)が解を持たない⇒Ｄｖ≦０、ｄｖ＞０が解を持たない⇒ｗＤ＝ｄ、ｗ≧０が解を持つ⇒矛盾発生と、
証明が進んでいきますが、証明方法が間違いということですね。もちろん、結論は正しいのですが、
問Ａ．６
これは問題としては難しすぎると思いますが...
1).列ベクトルＶA、ＶBが、ＶA≧ＶBの時
列ベクトルＹ、Ｙ≧０に対して、ＹT・ＶA≧ＹT・ＶBとなる。
証明
Ｐ≡ＶA−ＶBとすれば、Ｐ≧０なので、Ｙ≧０より、ＹT・Ｐ≧0
従って、ＹT・(ＶA−ＶB)≧0より、ＹT・ＶA≧ＹT・ＶB
2).弱双対定理（と呼びます）
主問題と双対問題に解Ｘ、Ｙが存在すれば、常にＹT・ｂ≦cTＸが成立する
つまり、双対問題の目的関数値≦主問題の目的関数値となる。
証明
Ｙ≧０かつＡ・Ｘ≧ｂより、ＹT・Ａ・Ｘ≧ＹT・ｂ
Ｘ≧０かつＡT・Ｙ≦ｃより、ＹT・Ａ・Ｘ＝（ＡT・Ｙ）T・Ｘ≦ｃT・Ｘとなり、
ＹT・ｂ≦ｃT・Ｘとなる。
3).Farkasの補題の系
Ａ・Ｘ≧ｂ、Ｘ≧０が解を持つ⇔ＹTＡ≦０となる任意のＹ≧０でＹT・ｂ≦０
証明
Ａ・Ｘ≧ｂ、Ｘ≧０⇔Ａ・Ｘ-s・Ｉ＝ｂ、Ｘ≧０，s≧0⇔Ａ*・Ｘ＝ｂ、Ｘ*≧０
ただし、
| Ａ*≡ |
┌
│
└
|
Ａ
|
-1
|
┐
│
┘
|
Ｘ*≡ |
┌
│
│
└
|
Ｘ
s
|
┐
│
│
┘
|
問１．１０より、Ａ*・Ｘ＝ｂ、Ｘ*≧０が解を持つ ⇔ ＹTＡ*≦０、ＹT・ｂ＞０が解を持たない
⇔ ＹTＡ≦０、ＹT・ｂ＞０、Ｙ≧０が解を持たない ⇔ ＹTＡ≦０、Ｙ≧0となるすべてのＹで、ＹT・ｂ≦0
4).強双対定理（と呼ぶらしい)
主問題、双対問題がいずれも解を持つ時、その目的関数の値は等しい
証明
主問題、双対問題がいずれも解をもつとすると、以下条件を満たしている。
Ａ・Ｘ≧ｂ、ＡT・Ｙ≦ｃ、Ｘ≧０、Ｙ≧０ ...(1)
この時に、ＹT・ｂ−ｃT・Ｘ≧0 ...(2)
であることを示せば、上述の弱双対定理のＹT・ｂ≦ｃT・Ｘとあわせて
ＹT・ｂ＝ｃT・Ｘであることを示すことができる。
4-1).
上述の条件(1)、(2)をマトリックス形式で整理して、
| |
┌
│
│
│
└
|
Ａ
０
−ｃT
|
０
−ＡT
ｂT
|
┐
│
│
│
┘
|
┌
│
│
└
|
Ｘ
Ｙ
|
┐
│
│
┘
|
≧ |
┌
│
│
└
|
ｂ
−ｃ
0
|
┐
│
│
┘
|
、 |
┌
│
│
└
|
Ｘ
Ｙ
|
┐
│
│
┘
|
≧０が解を持つことを示せば良い。 |
これは、上述の3).Farkasの補題の系から
| |
┌
│
│
└
|
ＡT
０
|
０
−Ａ
|
−ｃ
ｂ
|
┐
│
│
┘
|
┌
│
│
└
|
ｐ
ｑ
α
|
┐
│
│
┘
|
≦０を満足するすべての |
┌
│
│
└
|
ｐ
ｑ
α
|
┐
│
│
┘
|
≧０で、 ...(3) |
| |
┌
│
└
|
ｂT |
−ｃT |
0 |
┐
│
┘
|
┌
│
│
└
|
ｐ
ｑ
α
|
┐
│
│
┘
|
＝ ｐT・ｂ−cT・ｑ≦0 ...(4) |
となることと同値である。
これをα＞0と α＝0の２通りに分けて証明する。
4-2).α＞0の時
Ｘ*≡ｑ／α、Ｙ*≡ｐ／αと定義すれば、
(3)式に代入すれば、Ａ・Ｘ*≧ｂ、Ａ*T・Ｙ≦ｃ、Ｘ*≧０、Ｙ*≧０となるから、
上述2).の弱双対定理より、Ｙ*T・ｂ−ｃT・Ｘ* ≦ 0となる。
(4)式を変形すれば、ｂT・ｐ−ｃT・ｑ＝α・(ｂT・Ｙ*T−ｃT・Ｘ*）≦0となるので
常に(4)式を満たすことができる。
4-3).α＝0の時
条件(3)から、Ａ・ｑ≧０、ｑ≧０
また、条件(1)からＡT・Ｙ≦ｃ、Ｙ≧０であるので、
弱双対定理より、（弱双対定理のＸをｑ、ｂを０とみてください）
ＹT・０≦cTｑから、cT・ｑ≧0 ... (5)
同様に、条件(3)から、ＡT・ｐ≦０，ｐ≧０
また、条件(1)からＡ・Ｘ≧ｂ、Ｘ≧０であるので、
弱双対定理より、（弱双対定理のＹをｐ、ｃを０とみてください）
ｐT・ｂ≦０T・ｑから、ｐT・ｂ≦0 ... (6)
(5)と(6)から、ｐT・ｂ−cT・ｑ≦0となり、
常に(4)式を満たすことができる。
4-4).
以上より、条件(1)の時に、条件(2)は常に満足される。
これと弱双対定理と合わせて、証明できた。
戻る
