線形計画法の解法について
- 線形計画法の解き方が判らなくて困っています。
- 制約条件の式と計算値、目的関数の式と目的値が判りません。
- 線形計画法は変数と制約条件と目的関数が与えられます。制約条件を満足し、目的関数が最大(最小)となる変数を求めます。具体的な例として、変数xとyに対する制約条件(A)〜(E)を満足し、目的関数(M)が最大となる変数xとyを求める手法です。
- ベストアンサー
線形計画法の解法について!
線形計画法の解き方が判らなくて困っています。 判らないこと 1.制約条件の式と計算値 2.目的関数の式と目的値 線形計画法は変数と制約条件と目的関数が与えられます。 制約条件を満足し、目的関数が最大(最小)となる変数を求めます。 線形計画法の例 変数 x y 制約条件 (A) 10x + 4y ≦ 360 (B) 4x + 5y ≦ 200 (C) 2x + 10y ≦ 300 (D) x ≧ 0 (E) y ≧ 0 目的関数 M = 7x+12y A,B,C,D,Eの条件を満足し目的関数(M)が最大となる変数x,yを求めます。
- taka_632
- お礼率57% (88/153)
- 数学・算数
- 回答数2
- ありがとう数3
- みんなの回答 (2)
- 専門家の回答
質問者が選んだベストアンサー
>判らないこと >1.制約条件の式と計算値 線形計画法の例で言うと (A)~(E)の制約条件を満たす領域Rの図をxy座標面上に描く。 >2.目的関数の式と目的値 線形計画法の例で言うと 1で描いた領域Rを 目的関数=kとおいた直線(曲線)が通過するようなkの最大値(または最小値)と その時のx,yを求めれば良い。 具体的には、線形計画法の例で言うと > 変数 x y > 制約条件 > (A) 10x + 4y ≦ 360 > (B) 4x + 5y ≦ 200 > (C) 2x + 10y ≦ 300 > (D) x ≧ 0 > (E) y ≧ 0 (A)~(E)を満たす点(x,y)の領域Rを図示すると添付図の水色領域のようになります。 > 目的関数 > M = 7x+12y >A,B,C,D,Eの条件を満足し目的関数(M)が最大となる変数x,yを求めます。 このため 7x+12y=k と置き、この目的関数の直線y=(k/12)-(7/12)xが 上で描いた水色領域Rを通過するようなkの範囲を求めます。 領域Rを通過する目的関数の直線は添付図の黒実線の直線のようになります。 この直線の傾きは-(7/12)で一定ですからkが変わると並行移動します。 k(直線のy切片はk/12)が最大となる時のkは、直線が領域Rの点Pを通る赤線の直線の時の kとなります。 点Pは (B)の境界線:4x+5y=200 と(C)の境界線:2x+10y=300との交点ですから、連立方程式を解いてP(50/3, 80/3)と得られます。この時のkの最大値=7x+12y=7(50/3)+12(80/3)=1310/3 変数が実数であれば、kの最大値1310/3 が目的関数Mの最大値1310/3となります。そしてP点の座標(x,y)=(50/3, 80/3)が目的関数Mが最大値をとる時のx,yとなります。 もし、変数 x,y が整数値しか取らないのであれば、領域R内にあって点Pの近隣の格子点(x,y)について、k=7x+12yを計算しkの値が最も大きい格子点を選び、目的関数の直線が通るようにすれば、その時の整数の組(x,y)に対するk=7x+12y の値が目的関数Mの最大値になります。 今の場合、点Pの近隣の領域R内の格子点でkがより大きくなる候補は P1(17,26)とP2(15,27)ですが P1に対するkを求めるとk=431 P2に対するkを求めるとk=429 なので目的関数Mを最大にする(正の)整数の組x,yは x=17,y=26でありMの最大値はM=431 となります。
その他の回答 (1)
- stomachman
- ベストアンサー率57% (1014/1775)
n変数の線形計画法では、制約条件を満たす領域Aはひとつのn次元凸多面体になり、その多面体の頂点のうちのどれかは解です。だから総当たりで、頂点それぞれについて目的関数を計算すれば良い。 ご質問の場合は2変数だからさらに簡単。制約条件を満たす領域(凸多角形)のグラフを描いて、さらにM=c (cは勝手な定数)の直線L(c)を1本描いてみれば、「L(c)を平行移動したとき(つまりcを変えたとき)、多角形の頂点のどれを通るようにすればcが最大(最小)になるか」は即座に分かるでしょ。 しかし、nが大きく頂点の個数が莫大であるという場合には、目的関数がより良くなる頂点を、凸多面体の辺をたどって順次探すという方法を使います。すなわち、まずひとつの頂点Xを出発点に決める。そして、頂点Xと辺で繋がっている頂点Yの集合の中から頂点Yにおける目的関数の値M(Y)が一番良い頂点Y*を探す。M(Y*)=M(X)ならXが解。さもなくば、Y*を出発点にして繰り返し。こうすれば全ての頂点を調べる必要はないから、総当たりより速くなります。詳細は「シンプレックス法」をお調べになれば分かるでしょ。
関連するQ&A
- 線形計画法の解について!
線形計画法の解、シャドウ価格の求め方がわからなくて、困っています。 問題は、以下のとおりです。 (線形計画法とシャドウ価格) 次の線形計画法の解、各制約のシャドウ価格を求めなさい。 制約条件 2x+y≦7, x+3y≦6, x≧0,y≧0 のもとで、目的関数 Z=x+y を最大化せよ。
- ベストアンサー
- 数学・算数
- 非線形計画法について
非線形計画法を現在勉強しています。 1. どういうときに線形でどういうときに非線形となるのか良く分かりません。 例えば、ある従属変数yを線形関数f=Σcx で表したいときにパラメータcの絶対値の和が定数bより小さくなるという制約のもとで、yとfの二乗誤差を最小化するパラメータcを求める問題を考えます。 この場合、制約条件はcについて線形ですが、最小化したいのは、yとfの二乗誤差なのでこの場合は非線形ということになるのでしょうか?それとも関数fはcに関して線形関数なので、線形計画法で解くことになるのでしょうか? 2. 以下のサイトで勉強しているのですが、このサイトにある楕円型の等高線はおそらく、従属変数yと目的関数fの誤差を表しているのだと思うのですが、なぜ「楕円」になるのですか?二乗誤差を考えるのならば、「円」になるのではと疑問で仕方ありません。 http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/nonlinear/nonlinear.htm#2.2 疑問が晴れずにもやもやしています。 回答もしくはアドバイス、よろしくお願いします。
- 締切済み
- 数学・算数
- 線形計画法の目的関数の最大値の出し方
【制約条件式】 4x+2y≦160 3x+4y≦170 x≧0,y≧0 【目的関数】 Z=20x+15y この目的関数の最大値は900なのですが、 その出し方がわかりません。 途中式を省かず、 上記以外の数字が出た場合は、それがどこから出たのか、なんであるのかという解説までお願いします。
- ベストアンサー
- 数学・算数
- 経営科学の線形計画法、教えてください
線形計画法のシンプレックス法で、問題を解くために不等式であらわされた制約条件式を、わざわざ余裕変数を用いて等式条件にするのはどうしてですか?
- 締切済み
- その他(学問・教育)
- 線形計画法の問題で、悩んでます。
線形計画法の問題ですが。 たとえの問題です。 2種類の餌料「X」と「Y」を牛に与える1日に必要な、 ビタミン量を確保したままで、できるだけ価格を安くしたい。 X=50円/kg Y=100円/Kg ビタミン量X Y ------------ A 4 1 B 2 1 C 7 10 D 1 3 ------------ 餌(kg) ビタミン(mg) ビタミン必要量 ------------ A 12 B 10 C 70 D 15 ------------ ヒントは:目的は安くすること、制約条件は必要量。 どうとくのか、式だけでも教えていただけないでしょうか? どう、手をつけたらいいのかわかりません。
- 締切済み
- 物理学
- 線形計画法の説き方 初級シスアド 平成16年度 午前問73改変
線形計画法の説き方についてです。 ある工場で製品A,Bを生産している。製品Aを1t製造するのに、原料P,Qをそれぞれ4t、9t必要とし、製品Bについてもそれぞれ8t、6t必要とする。また、製品A,Bは1tあたりそれぞれ2万円、3万円の利益を生む。しかし、原料Pは40t、Qは54tしかない。利益を最大にするにはどうしたらよいか。 制約条件 4x+8y≦40→y≦-1/2x+5 9x+6y≦54→y≦-3/2x+9 x≧0,y≧0 目的関数 2x+3y 答えxが3 yが4 ここまでは分かります。その下にグラフがあり、頂点のいずれかで利益が最大になります。となっていて、4つの頂点で目的関数に値を入れて答えを出しているのですが、このグラフはどうやって書くのですか。また、その答えが4つの頂点の中の、x、y軸に接していない頂点のxもしくはyの値の出し方も分かりません。 更に、制約条件の式を普通に解いても答えと同じx、yが出たのですが、これはたまたまでしょうか。 ちなみに数学が苦手なほうです。よろしくお願いします。
- 締切済み
- 情報処理技術者
- 線形計画法で最大利益を求める
情報基本処理の問題で質問ですが、線形計画法で最大利益を求める問題があります。 教科書で検索しても、ネットで検索してもいまいち線形計画法がよくわからないのですが、どういう方法をいうのでしょうか? またこの線形計画法を使っての式ですが、 例) Aの式 2 x + y = 100 Bの式 x + 2 y = 80 とあります。最初のAの式でYを求めると y= 100 - 2 xとなるとあります。 続いてxを求める時に、そのAの式で求めたy= 100 - 2 xをBの式に当てはめて、xを求めるとあります。なぜ、その式をBの式に入れるのでしょうか?Aの式ではだめなのでしょうか? おそらく数学の根本的な基礎を忘れてしまっているかもしれませんが、どなたかアドバイスをお願いします。
- ベストアンサー
- 情報処理技術者
- 線形計画問題
最近線形計画法について独学で勉強を始めたのですが いくつかの書籍を調べてもどうしても分からない点が あったのでこの場を利用させて頂きます。 頭を悩めていますのは制約条件が特殊なためです。 問題を簡略すると以下のようになっています。 min : x(1)/2 + 5x(2)/2 suject to: 1/x(1)+1/4x(2) ≦ 8 x(1) ≧ 0, x(2) ≧ 0 御覧頂けますように制約条件において決定変数が 分母にきているのです。目的関数で分母に変数を 持つものは分数計画問題といるのを拝見した事が あるのですが上記のような例は探し方が悪いのか 見つける事ができていません。 実行可能領域は非有界ですが最小化問題のため 上記の例であると2変数なのでグラフにプロットする 事でおよそですが解は見つかりました。 しかし実際の問題は10変数以上の問題となっています ので解が求められません。 その後も実行可能領域を多面体で近似すれば良いのか 等の考察を繰り返しましたが問題が複雑になりお手上げ の状態です。 ちゃんとした解法があるのならお教え頂けるか書籍の 案内をして頂きたいです。宜しくお願いします。
- ベストアンサー
- 数学・算数
お礼
詳しい解説、有難うございました。