LP（線形計画問題）に関する問題です。答えを教えてください。

問

変数がx,y（2変数）であるLPにおいて、最適解は存在するが端点最適解は存在しない例を1つ挙げよ。

質問者からの補足コメント

• LPの最適解が境界値、つまり端点最適解となるならば、私の考えている問いに答えはないという解釈で大丈夫でしょうか。何か間違いがあれば教えていただけると嬉しいです。

  No.2の回答に寄せられた補足コメントです。 補足日時：2020/04/28 17:50

No.3 ベストアンサー 回答者： ありものがたり 回答日時： 2020/04/28 18:56

ああ、「最適解は存在するが端点最適解は存在しない例」って書いてある。

読み違えてました。 Sorry.
既に書いたように、LPでは、最適解が存在する問題であれば
その最適値は実行可能集合の頂点上にあります。
それが、シンプレックス法の根拠でもあります。
あとは、「端点最適解」という言葉の定義にもよるのですが、
例外的な場合としては、最適値が1個の頂点ではなく
実行可能集合の辺上や面上に現れる場合もあります。
それだと「端点最適解」だとは少し言いにくいのかもしれないけれど、
それでも「端点最適解は存在しない」という言い方にはならない気がします。

この回答へのお礼

何度も回答していただき、ありがとうございました。おそらく理解できたと思います。

お礼日時：2020/04/28 20:34

No.2 回答者： ありものがたり 回答日時： 2020/04/28 13:19

2変数であることは関係がありません。

一般に最適化問題について、最適化する関数が滑らかならば
最適値は極値か境界値かのどちらかです。
LPの場合、勾配が定数なため極値は存在しないので、
最適値は境界値となります。それを端点最適解と呼んでいる
のだと思います。

この回答へのお礼

LPの最適解が境界値、つまり端点最適解となるならば、私の考えている問いに答えはないという解釈で大丈夫でしょうか。何か間違いがあれば教えていただけると嬉しいです。

お礼日時：2020/04/28 18:27

No.1 回答者： ありものがたり 回答日時： 2020/04/22 16:41

そのとき、最適解が端点ではなくどこにあるのかを

教科書で調べなさい。 丸投げはいけません。

この回答へのお礼

「LPで最適解が存在するならば、端点最適解が存在する」という性質があることは分かっていて、それだと問題がおかしいのではと思い、色々と調べたり自分で考えたりしたのですがそれ以上分からず質問していた次第です。答でなくても何か取っ掛かりだけでも教えていただけたら幸いです。

お礼日時：2020/04/28 11:53