線形計画法の解法について！

質問

線形計画法の解き方が判らなくて困っています。

判らないこと

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

info222_ · ベストアンサー

>判らないこと
>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）と得られます。この時のｋの最大値=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

stomachman

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*を出発点にして繰り返し。こうすれば全ての頂点を調べる必要はないから、総当たりより速くなります。詳細は「シンプレックス法」をお調べになれば分かるでしょ。