線形計画問題の標準形

現在大学で線形計画法を学んでいるのですが，実際に数字を用いて問題を解く事にはなれてきたのですが，証明問題などになるとどの様に回答を行えば良いか回答に繋がるプロセス分かりません．

どの様なプロセスで回答をすれば良いかなにかアドバイスがございましたらよろしくお願いします．以下が現在回答に困っている問題ですのでよろしくお願いします．

線形計画法の標準形

目的関数：c^T x →最小
制約条件：Ax =b
x≧0

m<nとなる自然数．x ∈ R^n, c ∈ R^n, b ∈ R^mであり，Aはm*n実行列で，rankA = m とし b ≠ 0 とする．

問題１．線形計画問題の制約条件を満たすxのなす集合を実行可能領域Fで表し，Fが空集合でないときFが凸集合であることを示しなさい． Fが凸集合とは
x,x' ∈ F ⇒tx + (1 - t)x' ∈ F (∀t ∈ [0,1])
が成立するときをいう．

問題２．Au = b を満たすベクトル u ≠ 0 が存在する事を示せ．

問題３．Ax = 0 を満たすxのなす R^n の線形部分空間はAの核と呼ばれkerAと表す．Ax = bを満たすxのなす R^n の部分集合を J で表すとき
J = { x ∈ R^n | x = u + v, v ∈ kerA}
となる事を示せ．ただしuは問題２で存在を示したベクトルである．

No.1 回答者： Tacosan 回答日時： 2008/07/17 21:57

単なる線形代数の問題ですね.

1. 「凸集合」の定義に従うことを示す.
2. rank A = m だから A からうまく m本の列ベクトルを選んで正則行列 B が作れることを示す.
3. x ∈ J なら Ax = b は自明, 逆も x-u を考えればほぼ明らか.

この回答への補足

やっぱりちょっと解法がわからないです．

具体的にこうすると解けるなどのアドバイスがありましたらよろしくお願いします．

補足日時：2008/07/17 23:45

この回答へのお礼

早速のお返事ありがとうございます．

アドバイスを参考に頑張ってみたいと思います．

お礼日時：2008/07/17 22:13

No.2 回答者： Tacosan 回答日時： 2008/07/18 12:26

どこまでができていて, どこからがわからないんでしょうか?

少なくとも 1 については定義をおえば証明できてしまうはずなんですが....
つまり
Ax = b, Ax' = b であるような x, x' に対し A[tx + (1-t)x'] を計算するだけなんだし.

この回答へのお礼

早速のお返事ありがとうございます．

問題1.と問題2．はこんな感じなのでしょうか？
自信がないので何とも言えませんが・・・．

問題１．
x, y ∈ F を取る．このとき
t x + (1-t) x' ≧ 0
A (t x + (1-t) x') = t A x + (1-t) A x' = t b + (1-t) b = b
よって t x + (1-t) x' ∈ F となって F は凸集合

問題２．
A u = b が解を持つことと，正則行列 S, T に対して
(S A T) u' = (S b) が解を持つことは同値なので，
一般性を失うことなく，A をランク標準形としてよい．
（ランク標準形：正則行列 S, T を用いて (S A T) = 階段行列）

このとき，方程式の形は（簡単のため m = 3, n = 5 で書くと）
|1 0 0 0 0||u1| = |b1|
|0 1 0 0 0||u2| 　|b2|
|0 0 1 0 0||u3| 　|b3|
　 　　　　  |u4|
　　 　　　  |u5|
のようになっているので，これを満たす u は
　u = (b1, b2, b3, 0, 0) + (0, 0, 0, s, t)
の形で書ける（s, t は任意の実数）．
よって問題２が従う．

問題３は ker A = { (0, 0, 0, s, t) | s, t ∈ R }
となることは分かるのですが，それ以降の証明でどのように導けばいいのかが分かりません．

お礼日時：2008/07/18 17:09

No.3 回答者： Tacosan 回答日時： 2008/07/18 17:53

1 と 2 はそんな感じ.

3 は
{ x ∈ R^n | x = u + v, v ∈ kerA } = u + ker A と書かせてもらうことにして
J = u + ker A
を示せばいいんだけど, これは
J ⊆ u + ker A かつ J ⊇ u + ker A
と等価です. でこっちを証明するんだけど後者は
x ∈ u + ker A とすると x = u + v, v ∈ ker A とおけて, このときに Ax = b が導ければいいということになります.
前者は x ∈ J に対し x - u ∈ ker A, つまり A(x-u) = 0 が言えれば OK です.