- ベストアンサー
線形計画問題
最近線形計画法について独学で勉強を始めたのですが いくつかの書籍を調べてもどうしても分からない点が あったのでこの場を利用させて頂きます。 頭を悩めていますのは制約条件が特殊なためです。 問題を簡略すると以下のようになっています。 min : x(1)/2 + 5x(2)/2 suject to: 1/x(1)+1/4x(2) ≦ 8 x(1) ≧ 0, x(2) ≧ 0 御覧頂けますように制約条件において決定変数が 分母にきているのです。目的関数で分母に変数を 持つものは分数計画問題といるのを拝見した事が あるのですが上記のような例は探し方が悪いのか 見つける事ができていません。 実行可能領域は非有界ですが最小化問題のため 上記の例であると2変数なのでグラフにプロットする 事でおよそですが解は見つかりました。 しかし実際の問題は10変数以上の問題となっています ので解が求められません。 その後も実行可能領域を多面体で近似すれば良いのか 等の考察を繰り返しましたが問題が複雑になりお手上げ の状態です。 ちゃんとした解法があるのならお教え頂けるか書籍の 案内をして頂きたいです。宜しくお願いします。
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
#1さんもおっしゃるとおり、制約条件のある非線形最適化問題と思ったほうがよいですね。ラグランジュの未定乗数法みたいなものでは対応できなさそうでしょうか？ 演習書といっても、最適化という分野は、（一部のシンプレックス法を除いて）紙と鉛筆を使うというよりは、プログラミングでしょうからね。基本コンセプトが反復計算ですから。 そういう意味では、URLの本もお勧めかと思いますが、amazonでも在庫切れなんですね・・・大学の図書館にはあったりしません？
その他の回答 (1)
- pori_boy
- ベストアンサー率60% (18/30)
こんばんは まず、質問のタイトルに線形計画問題とありますが 今回の質問の問題はその範疇に入るのでしょうか？ 私の理解ではもっと難しい問題と感じました。 次に、質問文中にある分数計画問題に関して うまく対処する方法をご存知でしたら、 与えられた問題を変形すれば良いと思います。 (1/x(1) を 新しくy(1) という変数に置く。 境界条件などの考慮が必要になります） 線形計画問題はもちろん、一般の数理計画問題 （非線形計画問題）に対してもさまざまな研究・ 書籍がありますが、非線形の場合は、すっきり 解くというのは厳しいかもしれませんね。 最後に書籍の紹介ですが、古典から最新のもの、 和書や洋書（その翻訳）と非常に多いので、 絶対にこれという薦め方は私ではできません。 参考までに、私の手元にあるのは次のあたりです。 数理計画入門 福島 雅夫 最適化法 田村 明久 非線形最適化の基礎 福島 雅夫 大きな書店や大学の書籍部などで手にとって もらえると自分好みのものが選べて良いと思います。
お礼
pori_boy様、早速のお返事ありがとうございます。 線形計画法に関して理解が不十分なためタイトルと 質問の中身が一致していない点があったかも知れま せん。ご指摘ありがとうございます。 分数計画問題については一冊書籍がありますので 今回の問題に適用できるか検討してみたいと思います。 また、いくつかの書籍のご紹介を頂きありがとう ございます。上二つについては私の手元にもあります ので是非学習の一助として使いたいと思います。 昨日は図書館にこもっておりましたので数理計画問題 に関して様々な書籍を見つけましたが演習書のような ものが他分野の数学と比較して不足しているように 感じられました。
お礼
kony0さん、お返事ありがとうございます。 ラグランジュの未定乗数法を使う事で次元を 増やしても解く事ができました。 またタイトルに誤りがあって申し訳ありませんでした。 URLの本については図書館にあったので早速借りました。 各々の最適化について理論についても触れられていて 内容が充実していますね。今後学習を進めていく上で プログラミングは避けられないと思うので是非利用 していきたいと思います。 あとFORTRANについても復習する必要がありますね。