最適化の問題に詳しい方

質問

お世話になっております。

Let x0 and x1 be solution of
min tcx+c0
s.t.
Ax≦a,
Bx=b,
x≧0
Show that all points on the line with end points x0 and x1 are solutions.
(A:m×n matrix, a,b,c∈R^n, B:k×n matrix)

訳せば
「x0とx1を
min tcx+c0
s.t.
Ax≦a,
Bx=b,
x≧0
の解とする時、終点をx0とx1とする線上の全ての点が解を示せ」

これはどうやって示せばいいのでしょうか?

tは転置行列の意味だと思います。
x_0とx_1がAx≦a,Bx=b,x≧0を満たしていて、tcx0=tcx1ならば点λx0+(1-λ)x1も
Ax≦a,Bx=b,x≧0を満たしていて、同じ最適値(?)を持つ事をいいのかと思いますが
この手の問題になれてらっしゃる方,お教え下さい。

回答No.2

Tacosan · ベストアンサー

訳が日本語としてなんか変 (この訳なら原文を見た方が多分理解できる) だけど, いわんとすることはわかりました.
その定義なら, 挙げられた方針で OK ですね.

お礼

どうもありがとうございました。

回答No.1

Tacosan

やることは多分それでいいと思う (あ, x0, x1 が最適であることを仮定する必要があるかも) んだけど, この文章において「solution」はどういう意味なんだろ.
広い意味で「solution」というと (制約式を満たすかどうかは関係なく) 変数に対する可能な値の割当を全てさします. そのうち制約式を満たすものを feasible solution (可能解), さらに目的関数が最適なものを optimal solution (最適解) とするものだと思うんだけど....

お礼

有難うございます。

> この文章において「solution」はどういう意味なんだろ.
> 広い意味で「solution」というと (制約式を満たすかどうかは関係なく)

このsolutionの定義は
x0 がof min tcx such that
Ax≦a,
Bx=b,
x≧0
のsolutionならば
(i) x0 fulfills Ax0≦a,Bx0≦b,x0≧0
(ii) tcx0 is the smallest poss. value.

のようです。