線形計画法の問題：掃き出し法による最大値の判断
- 線形計画法を用いて、与えられた制約条件下での最大値を求める問題において、掃き出し法を用いる場合、求められた係数を利用して最大値を判断することができるか疑問が生じています。
- 与えられた問題では、製品Aと製品Bの生産量を決定する変数をx1とx2とし、それに対応する利益をzとします。また、制約条件によりスラック変数x3とx4も導入されます。
- 掃き出し法を適用して問題を解くと、得られた結果からzが最大値をとる場合についての判断ができない状況になりました。図形的に考えると、おそらくz=18（x1=4、x2=3）になると思われますが、計算上の何か間違いがあるのか、あるいは掃き出し法の結果から最大値を判断することは可能なのかについて、知識を教えていただきたいです。
- ベストアンサー
線形計画法の問題です。
問題は以下のURLの一番下（第2問-問題3）です。 http://www.gsm.kyoto-u.ac.jp/images/education/kakomon/24sugaku.pdf 得られる利益をz、製品Aをx1トン、製品Bをx2トン生産するとし、スラック変数x3、x4を導入すると、 -3x1 - 2x2 + z=0 x1 + x2 = 7 -(1) 2x1 + 3x2 + x3 = 24 3x1 + x2 - x4 =15 x1～x4≧0 ここで(1)式より、x2 = 7 - x1なので、他の式からx2を消去すると、 -x1 + z = 14 -x1 + x3 = 3 2x1 - x4 = 8 これを掃き出し法で解こうとすると、以下の写真のようになったのですが、 この掃き出し法によって分かるのは「z = 18 + x4/2」でx4の係数が正なので、「x4 = 0のときにzが最大値18をとる」とは言えませんよね？ 図形的に考えると、おそらくz=18（x1=4、x2=3）になると思うのですが、私の計算がどこかで間違っているのでしょうか？ それともこの掃き出し法の結果から、zが最大値18をとると言えるのでしょうか？ どなたかご教授ください。どうぞよろしくお願いします。
- yppon
- お礼率16% (16/99)
- 数学・算数
- 回答数5
- ありがとう数1
- みんなの回答 （5）
- 専門家の回答
質問者が選んだベストアンサー
そうか, 「(1)式より、x2 = 7 - x1なので、他の式からx2を消去する」ときに, 制約が 1本増えてたんだ. で, その制約を忘れちゃってるのでうまくいかない, ということか. うぅ～ん, やっぱり自分で手を動かさないといかんなぁ....
その他の回答 (4)
- Tacosan
- ベストアンサー率23% (3656/15482)
それです. いまさらながら思ったんだけど, ふつうは「等式を使って変数を減らす」ことはせず, いきなり (人工変数を導入して) 2段階シンプレックス法に入るような気がする. 少なくとも「教科書的」にはそうじゃなかったかな?
お礼
変数を減らさずに、最初から2段階シンプレックス法で解き直したら、普通に解くことができました！ セオリー通り解くようにしたいと思います。 何度も質問に答えていただき、ありがとうございました！大変助かりました！！
- Tacosan
- ベストアンサー率23% (3656/15482)
1回でダメなら 2段階でやる.
補足
2段階シンプレックス法も試してみたのですが、結局1回のときと同じになってしまいます…。
- Tacosan
- ベストアンサー率23% (3656/15482)
そこは合ってます. が, 掃き出し法に入るところの最初の表が間違っている (はず). 掃き出し法 (シンプレックス法) は大雑把にいうと 可能解を出発して次々に「より良い」可能解を探していく 手続きだから, 最初に可能解を与えないと意味がない. ところが, 最初の表が意味するのは x1 = 0, x3 = 3, x4 = -8 なんだけど, これは可能解じゃない.
補足
ではこの場合、シンプレックス法で解けと言われたらどうすれば良いのでしょうか？
- Tacosan
- ベストアンサー率23% (3656/15482)
一番最初, 「計算」するより前のところで既に間違っているような気がする. x1 を非基底変数として 0 にすると, 可能解にならないよね.
補足
回答ありがとうございます。 ご指摘いただいた「一番最初」というのは -3x1 - 2x2 + z=0 x1 + x2 = 7 2x1 + 3x2 + x3 = 24 3x1 + x2 - x4 =15 x1～x4≧0 のことでしょうか？ 問題文の通りに立式するとこのようになると思うのですが、どこか間違っていますでしょうか？
関連するQ&A
- 線形計画法の問題です
線形計画法の問題です 問題 ・原料PとQから3種類の製品A、B、Cを生産している。 ・製品Aを生産するのに、原料Pを1トン、原料Qを2トン必要 ・製品Bを生産するのに、原料Pを1トン、原料Qを3トン必要 ・製品Cを生産するのに、原料Pを2トン、原料Qを4トン必要 ・原料Pの使用可能量は10トン、原料Qの使用可能量は28トン ・製品A、B、Cの1トン当たりの利益は、30万円、20万円、４０万円 ・市場調査の結果、製品Aの需要量は、製品Bの需要量を2トンより多く上回ることはない 問1．利益を最大化する問題を線形計画問題として定式化せよ 問2．最大利益とその時の各製品の生産量 問3．原料Pの最大使用可能量が1トン減った場合、最大利益がどのように変化するか 問4．原料Qの最大使用可能量が1トン減った場合、最大利益がどのように変化するか 答１．目的関数 30x1+20x2+40x3 → MAX 制約条件 x1+x2+2x3<=10 2x1+3x2+4x3<=28 答2．最大利益 300万円 製品A 10トン 製品B 0トン 製品C 0トン 答3．最大利益は-30万円 答４．最大利益は変化しない となってしまいます。 たぶん、『・市場調査の結果・・・』を制約式に入れていないため、変な答えになっていると思います。 どなたか、模範解答を教えてください。
- ベストアンサー
- 数学・算数
- 問題の意味がよく分かりません。どなたか助けて下さい
問題文は以下のURLの第1問＞問題1＞(2)です。 http://www.gsm.kyoto-u.ac.jp/images/education/kakomon/23sugaku.pdf 一応、以下にも書いておきます。 「(x1, …, xn)∈R^n → y ∈ R を y = √(x1^2 + x2^2 + … + xn^2)で定義する定義する。このとき、f：R^n → R と g：R → R に対して、g(y) = f(x1, …, xn) ⇒ Σ∂^2 f/∂xi^2 = d^2 g/dy^2 + {(n-1)/y} ・ dg/dy が成立することを示せ。」 ここでの「f」は、(x1, …, xn) を y = √(x1^2 + x2^2 + … + xn^2) に変換する関数と捉えればよいのでしょうか？ そう考えると、「g(y) = f(x1, …, xn)」が成り立つとき、g(y) = y ということになりますか？ この解釈の下でやってみると一応証明できたのですが、解釈が合っているかが全く自信がありません。 どうぞよろしくお願いします。
- ベストアンサー
- 数学・算数
- 固有ベクトルは具体的な値を指定して解いてもよい？
以下のURLの第2問の2（連立線形微分方程式の問題）に関してです。 http://www.gsm.kyoto-u.ac.jp/images/education/kakomon/18sugaku.pdf (1)のような問題で、通常固有ベクトルを表すときには、「0以外の任意の実数t1、t2」などを用いるかと思います。 ※ちなみにこの問題では、e1 = t1(1, -1)、e2 = t2(1, 2) となりました。 (2)以降の問題を解くときに、例えばt1=t2=1として、具体的な固有ベクトルを指定して解いていっても良いのでしょうか？ それとも最後まで、t1、t2などの文字を残して計算していかないといけないのでしょうか？ どなたかご教授ください。どうぞよろしくお願いします。
- ベストアンサー
- 数学・算数
- 線形計画法の問題です。
「製品1および製品2の1単位あたりの利益がそれぞれ15、25である。製品1と製品2の製造数をx1、x2とする。製品1を1単位製造するために必要な材料1、材料2の使用料はそれぞれ18単位、20単位であり、製品2の使用料はそれぞれ24単位、9単位である。材料1、2の使用可能量の上限をそれぞれ120単位、80単位とするとき、利益を最大化する製造数とそのときの利益を求めよ。」 自分で解いてみたところ、シンプレックス法で解いても、グラフを書いて解いても「x1=0、x2=5のとき、利益125」という答えになったのですが、これは合っていますでしょうか？ 今まで片方の製造数が0となった問題に出会ったことがないので、不安になり質問させていただきました。 どなたか確認していただけると幸いです。どうぞよろしくお願いします。
- ベストアンサー
- 数学・算数
- 線形計画法
ある工場で二種類の製品A、Bを生産している。A、Bはそれぞれ二種類の原料ｐ、ｑを使い、Aを一トン生産するのにｐ、ｑはそれぞれ２トンと４トン必要です。Bを一トン生産するのにｐ、ｑをそれぞれ６トンと２トン必要です。A、Bそれぞれ一トン当たりの利益は30万円、２０万円です。この工場では、一か月間にｐが２００トン、ｑが１００トンまでしか手に入らないという。このとき、一か月間にA、Bをそれぞれ何トンずつ生産すれば利益は最大になるか。また、その時の利益はいくらか。という問題です Aをｘトン、Bをｙトン生産するとして計算して、答えはAを１０トン、Bを３０トン生産するとき利益は最大となり、その利益は９００万円。 たとえば、この問題がこういう文章題ではなくて、「ｘ、ｙが2x+6y≦200、４ｘ+2y≦１００、x≧０、ｙ≧０を満たすとき、３０ｘ＋２０ｙの最大値を求めよ」というもんだいだったら解けるんですけど、いざ文章題となるとなぜ2x+6y≦200みたいな「トン」という単位についての式を３０ｘ＋２０ｙのような値段についての式を同じ座標という土俵で扱っていいのか？という疑問があります。なかなかぱっといきません
- 締切済み
- 数学・算数
- 線形計画法を2段階シンプレックス法を用いて解く
次の問いを2段階法を用いて解けというものなのですが (1) x0 = 4x1 - 2x2 + x3 → 最大化 2x1 + x2 + x3 ≦ 6 4x1 - 2x2 + x3 ≦ -4 x1, x2, x3 ≧ 0 (2) x0 = 3x1 + 2x2 → 最大化 x1 + 2x2 ≦ 20 7x1 + 6x2 ≧ 84 x1 - x2 ≦ 8 x1, x2 ≧0 (1)に関しては人為変数が不要なのでそもそも2段階法で解けるのでしょうか？ (2)は x1 + 2x2 +x3 = 20 7x1 + 6x2 - x4 = 84 x1 - x2 +x5 = 8 とした後に人為変数x6を用いて x1 + 2x2 +x3 = 20 7x1 + 6x2 - x4 +x6 = 84 x1 - x2 +x5 = 8 として解いていったのですがシンプレックス表で解いている途中で詰まってしまいます。 (1), (2)ともにある程度の途中計算を交えて教えてくださると助かります。 よろしくお願いします。
- 締切済み
- 数学・算数
- 至急お願いします！線形計画問題についてです。
maximize 7x1 + 4x2 + 2x3 subject to 3x1 + 3x2 + x3 ≦ 36 .................. 2x1 + x2 + x3 = 18 .................. x1,x2,x3≦0 この問題を2段階法により解けという問題なのですが、x1,x2,x3と3変数も出てきているのに、制約関数が2式のみって、解くことができないですよね？3変数であれば最低でも3式は必要だと思います。 問題のミスでしょうか？ どなたか教えてください。
- ベストアンサー
- 数学・算数
- 非線形計画法 主-双対問題
次のような制約付き最小化問題を考えています。 目的関数は非線形です。 min x1^2+x2^2 s.t. -x1-x2+4<=0 x1>=0 x2>=0 この問題の場合最適解は(x1,x2)=(2,2)であり、その時の目的関数値は8となります。 次に次式のような双対問題を考えます。 g(x)=-x1-x2+4とおき 双対関数 φ(u)=inf{x1^2+x2^2+u*(-x1-x2+4) : x1>=0 , x2>=0} =inf{x1^2-u*x1 : x1>=0}+inf{x2-2-u*x2 : x2>=0}+4*u 上記においてもしu>=0であれば、x1=x2=(u/2). （なぜなら、x1^2-u*x1をx1で微分するとx1=u/2となる。） u<0であるならばx1=x2-0であることに注目しますと。 φ(u)=-(1/2)*u^2+4*u for u>=0 =4u for u<0 となります． 双対関数がu>0の場合は最大がu=4であることに注目すると、その時の目的関数は8であり、主問題と双対問題の最適な目的関数値は一緒となります。 次に主問題を次のように制約を増やした最小化問題を考えます。 min x1^2+x2^2 s.t. -x1-x2+4<=0 -2*x1-3*x2<=0 x1>=0 x2>=0 これの最適解は上記の問題と同じにならないといけないのですが、 例えば、ラグランジュ関数F(x1,x2,λ1,λ2)を次のようにおき各変数で偏微分して最適解を求めると（λ：ラグランジュ乗数）、 F(x1,x2,λ1,λ2)=x1^2+x2^2+λ1*(-x1-x2+4)+λ2*(-2*x1-3*x2) 最適解はx1=12, x2=-8であり、その時の目的関数は208となり、前問と異なった解が得られました。 この原因は明確であり、ラグランジュ関数の中の各制約式が、偏微分して解を得ることで不等式制約ではなく等式制約とみなされたためです。 偏微分して解を求めなければいいのですが、どうしても偏微分でかいを求めたいために、、前門で示した双対問題を導入しましたが、結果は双対問題のほうでも偏微分するので一緒でした。 しかし、双対問題で得られた解。つまりuは主問題のλに相当し、KKT条件より必ず正である必要があるので、双対問題を解き、uが負になった制約式はの除いてそのあともう一度問題を解きなおす。つまり２番目の問題を前問に置き換える。 っといったことをして問題を解決させようとかんがえていますが、これは理論的に正しいのでしょうか。 これはほんの例題ですが、複数個の不等式制約式を扱い、かつ偏微分可能な最適化問題を解く際に、最適解に対して全てが有効制約になるとは限りませんので、どうかうまくいくアドバイスをください。
- 締切済み
- 数学・算数
- 線形計画法の解について！
線形計画法の解、シャドウ価格の求め方がわからなくて、困っています。 問題は、以下のとおりです。 （線形計画法とシャドウ価格） 次の線形計画法の解、各制約のシャドウ価格を求めなさい。 制約条件 2x＋y≦7, x＋3y≦6, x≧0,y≧0 のもとで、目的関数 Z＝x＋y を最大化せよ。
- ベストアンサー
- 数学・算数
補足
増える制約式とは、「x2 = 7 - x1 ≧ 0」から導き出される「x1 ≦ 7」のことでしょうか？ 確かにこれを制約条件に追加すれば、シンプレックス法でz=21と言えそうです！