- ベストアンサー
線形計画問題について教えてください。
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
こんにちは この問題に関しては条件を1としても2としても まったく同じ最適解がでてきそうですね。 まず、条件1と条件2を比べると、条件2で実行可能となる解は 全て条件1でも実行可能となるので、 1)の最適値 ≧ 2)の最適値 となりますよね。 次に、条件1のもとで線形計画問題を解くと X1=X2=X4=X6=1, X3=X5=0 という最適解が得られます。 （線形計画問題の一般的な解法を使っても良いですし、 この問題は、ナップサック問題とよばれる問題形式 となっていることから、専用の解法を使っても良いです） ここで得られた解を見ると、条件1を満たすのは当然ですが 幸運にも条件2を満たしているので、この解が条件2での 最適解ということがわかると思います。
その他の回答 (2)
- Willyt
- ベストアンサー率25% (2858/11131)
１では一般的な線形計画法を適用して解を得ることができますが、１の場合は取れる独立変数の値が連続ではないので、通常の線形計画法を適用できなくなります。無理矢理に適用するには例えば解が０または１にできるだけ近くなるような懲罰函数を目的関数に加えることで近似的に達成することができます。しかしこれは線形ではなくなりますよね。
お礼
詳しく教えてくださってありがとうございます。 参考になりました(^^♪
- rabbit_cat
- ベストアンサー率40% (829/2062)
１）と２）では、難しさが段違いに違います。２）のほうが圧倒的に面倒です。まあ、線形なんでできますけど。 最適解は、多分、１）２）で違うでしょうけど実際に計算してないのでわかりません。 ただ、必ず 1)の最適値 ≧ 2)の最適値 は成り立ちます。
お礼
教えてくださってありがとうございました。 参考になりました。(^^♪
関連するQ&A
- 線形計画法の解について！
線形計画法の解、シャドウ価格の求め方がわからなくて、困っています。 問題は、以下のとおりです。 （線形計画法とシャドウ価格） 次の線形計画法の解、各制約のシャドウ価格を求めなさい。 制約条件 2x＋y≦7, x＋3y≦6, x≧0,y≧0 のもとで、目的関数 Z＝x＋y を最大化せよ。
- ベストアンサー
- 数学・算数
- 非線形計画問題
min f(x1,x2)=(x1-1)^2+x2^2 subject to x1+x2>=5 2x1+x2>=7 (計画変数x1,x2は非負) (1)KKT条件を示し、最適解x1*,x2*を求め、目的関数の最小値を示せ。 (2)最適解x1*,x2*が存在する鞍点において、制約条件式(x1+x2>=5)の右辺の値がσだけ増加したときの 目的関数の変化量を求めよ。また、このような変化量に対して、λ1*,λ2*がどのような意味をもつか簡潔に述べよ。 という問題です」。 (1)はノーマルな解法で解いたら, x1*=2,x2*=3,目的関数の最小値は10でした。 (2)については変化量を求めたら、5σ^2-10σでした。 ですが、「このような変化量に対して、λ1*,λ2*がどのような意味をもつか簡潔に述べよ。」 ところはわかりませんでした。 そこがわかる方がいらっしゃいましたら、ぜひご教授お願いします！
- ベストアンサー
- 数学・算数
- 【至急】線形計画問題について、ヒントをください！
maximize 7x1 + 4x2 + 2x3 subject to 3x1 + 3x2 + x3 ≦ 36 .................. 2x1 + x2 + x3 = 18 .................. x1,x2,x3≦0 . この問題の最適解と最適値を求めたいのですが、、まず標準形の線形計画問題に変形する段階で、 2x1 + x2 + x3 = 18 と、 = がでできてしまい、 subject to 3x1 + 3x2 + x3 + x4 = 36 ................... 2x1 + x2 + x3 + x5 = 18 ................... x1,x2,x3,x4,x5≦0 としていいのか、 subject to 3x1 + 3x2 + x3 + x4 = 36 ................... 2x1 + x2 + x3 = 18 ................... x1,x2,x3,x4≦0 としていいのかが分かりません。 ≦ や ≧ ではなく、= が制約関数に含まれていると、標準形ではどの様に変形すれば宜しいのでしょうか？ どなたか教えてください。また、理由もお聞かせ頂けると幸いです。
- 締切済み
- 数学・算数
- 線形計画問題
最近線形計画法について独学で勉強を始めたのですが いくつかの書籍を調べてもどうしても分からない点が あったのでこの場を利用させて頂きます。 頭を悩めていますのは制約条件が特殊なためです。 問題を簡略すると以下のようになっています。 min : x(1)/2 + 5x(2)/2 suject to: 1/x(1)+1/4x(2) ≦ 8 x(1) ≧ 0, x(2) ≧ 0 御覧頂けますように制約条件において決定変数が 分母にきているのです。目的関数で分母に変数を 持つものは分数計画問題といるのを拝見した事が あるのですが上記のような例は探し方が悪いのか 見つける事ができていません。 実行可能領域は非有界ですが最小化問題のため 上記の例であると2変数なのでグラフにプロットする 事でおよそですが解は見つかりました。 しかし実際の問題は10変数以上の問題となっています ので解が求められません。 その後も実行可能領域を多面体で近似すれば良いのか 等の考察を繰り返しましたが問題が複雑になりお手上げ の状態です。 ちゃんとした解法があるのならお教え頂けるか書籍の 案内をして頂きたいです。宜しくお願いします。
- ベストアンサー
- 数学・算数
- 非線形計画問題に関する質問
非線形計画問題に関する質問 minimize f(x1,x2)=(x1-1)^2+x2^2 subject to x1+x2≧5 (1) 2x1+x2≧7 x1≧0 x2≧0 (1)の右辺の値がδだけ増加した時の目的関数の変化量と、この変化量に 対して乗数λ1,λ2はどのような意味を持つか述べよ という問題です。 最適値は(x1,x2)=(3,2)で乗数は(λ1,λ2)=(4,0) というところまで求めました。 変化量はδ^2/2かなとは思いますが、乗数の意味がわかりません。
- 締切済み
- 数学・算数
- 線形代数の固有値の問題がわかりません。
線形代数についての以下の問題がわからないので、過程も含めて解答を教えて下さい。 実2次形式Q(x)= Σn i=1 Σn j=1 (hij xi xj)、hij = hji (∀i,j = 1,2,...n)とする。Σn i=1 xi^2 = 1 の条件のもとで、Q(x)の最大値は係数行列H=(hij)の固有値の最大値と一致することを証明せよ。
- ベストアンサー
- 数学・算数
- 線形計画法の問題です
Ｐ：最大化ｃ＾Ｔｘ（ｃ＾Ｔはｃの転置） 条件Ａｘ＜＝ｂ ｘ＞＝０ ただし、Ａはｍ＊ｎ行列、ｂはｍ次元ベクトル、ｃはｎ次元ベクトル、ｘはｎ次元 変数ベクトルである。ベクトルはすべて列ベクトルとし、ｃ＾Ｔはｃの転置を表す。 問題Ｐは最適解を持つと仮定し、目的関数の最大値をｆと表す。また、問題Ｐ に関連して、ｍ次元ベクトルｕをパラメータとする次の線形計画問題を考える。 Ｐ（ｕ）：最大化ｃ＾Ｔｘ－ｕ＾Ｔ（Ａｘ－ｂ） 条件ｘ＞＝０ 問題Ｐ（ｕ）の目的関数の最大値ｇ（ｕ）と表す。ただし、問題Ｐ（ｕ）が有界でない 場合はｇ（ｕ）＝無限大と定義する。以下の問いに答えなさい。 １）問題Ｐの双対問題を書きなさい ２）任意のｕ＞＝０に対して、ｇ（ｕ）＞＝ｆが成り立つことを示しなさい ３）ｍｉｎ｛ｇ（ｕ）｜ｕ＞＝０｝＝ｆが成り立つことを示しなさい。ただし、線形計画問題 に対する強双対定理を用いて良い。 以上の問題をお願いします。
- 締切済み
- 数学・算数
お礼
かなり詳しく教えてくださってありがとうございます。 わかりやすかったです。 最適解まで解いてもらっちゃって・・・(^_^;) すごく助かりました！！