線形計画法の解き方が判らなくて困っています。
判らないこと
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を求めます。
No.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 となります。
No.1
- 回答日時:
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が見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Visual Basic(VBA) Excel のユーザー定義関数でソルバーが動作しない 1 2022/09/05 19:51
- 高校 対数方程式につきまして 4 2022/05/05 07:55
- 統計学 主成分分析について 1 2022/06/14 14:53
- Visual Basic(VBA) ExcelのVBAを使い、複数シートの同一箇所を、同一条件にて一括でソルバーを回す方法について 1 2022/04/23 11:49
- 数学 8 件の住宅について, 駅からの徒歩時間 (分) と賃料 (万円) を調べたところ, (徒歩時間, 1 2022/12/18 18:09
- 数学 8 件の住宅について, 駅からの徒歩時間 (分) と賃料 (万円) を調べたところ, (徒歩時間, 2 2022/12/18 20:26
- 数学 大学数学の定期テストの直しを行っているのですがこの線形代数の問題が分かりません。 次の連立一次方程式 1 2022/08/22 13:48
- その他(Microsoft Office) ある表(10桝程度)の中に数字が入っています。ダブっている数字を除く数字の合計数の計算方法 5 2023/02/15 11:33
- 物理学 量子力学 球面調和関数 導出 方位角成分 微分方程式の解 2 2022/07/02 13:40
- 高校 方程式の証明 5 2022/05/12 09:29
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
PowerPoint 罫線で直線を引く...
-
メール文章で直線の描き方について
-
実数x,yはx^2+y^2=4を満たすと...
-
直線補完?
-
2点を通り、半径 r の円の中心...
-
円を直線で分割すると・・・?
-
グランドにきれいな長方形を描...
-
仰角?
-
wordでルーズリーフに縦線を引...
-
数学Ⅱ 直線の方程式を求めよと...
-
wordの図形の描き方について
-
2つの楕円の領域のy=xに対...
-
パワポで点線を引きたいです・・・
-
直線を含む平面
-
直線の正確な定義を教えてくだ...
-
Excel 1変数データを数直線で...
-
三次元空間での直線の式
-
バケツの水を0.7リットル入るジ...
-
相関係数と回帰直線ってなんで...
-
平行条件には2直線が一致する...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
メール文章で直線の描き方について
-
PowerPoint 罫線で直線を引く...
-
電気ハンドホールの設置間隔の...
-
円x²+y²=1と直線y=x+mが接する...
-
円を直線で分割すると・・・?
-
直線を含む平面
-
組み合わせの問題
-
座標計算でのTan(θ)-1/Cos(θ)に...
-
不等号をはじめて習うのは?
-
エクセル・パワーポイントなど...
-
グランドにきれいな長方形を描...
-
実数x,yはx^2+y^2=4を満たすと...
-
下の画像の問題(7)なのですが、...
-
直線の傾き「m」の語源
-
120分の番組を1.5倍速で見ると8...
-
なまし鉄線(番線)をまっすぐ...
-
このSを正射影した面積がScosθ...
-
general formとstandard formの...
-
作図の問題です
-
wordの図形の描き方について
おすすめ情報