←講義のツボメニューへ
←【アプリケーション総論】シラバスへ 線形計画法１
【2001.05.24 ２限 第６回】１．線形計画法
発表者：高橋
○線形計画法の手順
- 問題の状況を整理し、必要なデータを集める。
- 問題の状況を数式を用いて定式化する
- 制約条件式をグラフにあらわして、実行可能領域を明らかにする
- 実行可能領域の上に、適当に利益を表すグラフを書く
- 利益を表すグラフを右上の方向に平行移動していって、実行可能領域内で出来るだけ利益が大きくなる点を求める。それはふつう、実行可能領域を表す多角形の頂点になる
- 利益を最大にする点の座標を求めるために、その点で交わっている制約条件式（あるいは場合によっては横軸ないし縦軸）からなる連立方程式を解く
- 最適な計画のもとでの利益の値を求める。
例）
とある家具店では、卒業シーズンに備えて、社会人向けの陳列コーナーを設けようとしている。仕入れようとしている商品は、ベッドと洋服ダンスの２種類である。これら２つの商品を100m^2の陳列スペースに陳列しようとしている。また、仕入れに使うことの出来る資金は240万円が限度である。
ベッドの仕入れ価格は１台３万円、１台あたりの利益は２万円。１台あたり２m^2のスペースを必要とする。
洋服ダンスの仕入れ価格は１台６万円、１台あたりの利益は３万円。１台あたり1m^2のスペースを必要とする。
さて、出来るだけ利益を大きくするような仕入れ計画はどうなるだろうか考えてみよう。
とりあえず、問題を整理してみよう。整理すると以下のような表になる。
ベッド 洋服ダンス 制約 陳列スペース 2m^2 1m^2 100m^2 仕入れ価格 ３万円 ６万円 ２４０万円 利益 ２万円 ３万円
ベッドの仕入れ台数をx、洋服ダンスの仕入れ台数をyとして考えてみよう。
ベッドの利益は２万、洋服ダンスの利益は３万なので、利益合計は利益合計z=2x+3yとなる。出来るだけ利益を大きくしようという目的を持っているので、この式は目的関数と呼ばれる。
次に、陳列スペースと仕入れ予算の制約を式に表すことを考えてみよう。
ベッドの陳列スペースは2m^2、洋服ダンスは1m^2、上限は100m^2なので2x+y<=100となる。このような式の事を制約条件式という。
同様に、仕入れ予算の制約条件式は3x+6y<=240となる。
なお、仕入れ代数はマイナス（負）の値を取ることはない。すなわち、プラス（正）か０である。このような変数のことを非負変数と呼ぶ。
これらをまとめると、以下のようになる。
非負変数x,y(x>=0,y>=0)において、
2x+ y<=100
3x+6y<=240
の制約条件式の元で、
z=2x+3y
で表される目的関数の値をできるだけ大きく（最大に）するような、xおよびyの値を求めること。
このような形にまとめられた問題を線形計画問題という。
これらの問題を解くために、グラフを用いる方法がある。
制約条件式をグラフに表し、それらの条件が当てはまる実行可能領域の中から、目的関数の値が最大になるものを探しだす。
多分、実行可能領域を表す多角形の頂点になるはずだ。
そこで、この頂点の座標を計算してみよう。
制約条件式を等式に置き換え、連立方程式として解いてみると、2x+ y=100となる。そのときの利益を求めるために、xとyの値を目的関数に代入すると
3x+6y=240
これらを解くと
x=40,y=20
z=2*40+3*20=140となり、ベッドを40台、洋服ダンスを20台仕入れるのが最適であり、そのときの利益の大きさは140万円となる。
２．シンプレックス法
条件が増え、グラフに表す事が出来なくなった場合、シンプレックス法を用いて解くことが出来る。
シンプレックス法での考え方
- 利益の大きい商品から仕入れてみる
前述の例だと、１台の利益が大きい洋服ダンスを出来るだけ仕入れてみることになる。
陳列スペースの制約と、予算の制約があるので、y<=100,6y<=240の２つの条件式を見たさなければならない。この場合、yの取りうる値は最大で40なので、40台仕入れることにする。そのときの利益はz=2*0+3*40=120となる。また、この時の陳列スペースは60、予算は0余ることとなる。
- もう片方の仕入れは有利か
もう片方のベッドを仕入れて見ることを考えてみよう。
予算はもう余っていないので、洋服ダンスの台数を減らしてベッドを仕入れることになる。
ベッドの仕入値は３万円、洋服ダンスの仕入値は６万円なので、洋服ダンスの仕入れ台数を1/2にすれば、ベッド１台分の３万円を捻出できる。
（ベッド１台あたりの仕入値／洋服ダンス１台あたりの仕入値）＝3/6=1/2さて、洋服ダンスの仕入れ台数を1/2台に減らし、それによって余る3万円でベッドを仕入れたら利益はどうなるだろうか？
ベッドを１台仕入れる事による利益の増加 ２万つまり、利益は1/2万だけ増えることになる。
洋服ダンスの仕入れ台数を1/2減らす
−）ことによる利益の減少 1/2*3万
−−−−−−−−−−−−−−−−−−−−−−−−−−
差し引き利益の変化 1/2万
したがって、ベッドの仕入れが有利だということが考えられる。
- ベッドを最大、何台まで仕入れることができるか
ベッドを仕入れるためには、１台あたり洋服ダンスの1/2台ずつ減らさなければならない。
洋服ダンスは、初めの40台が0台になるまでしか減らせないので1/2x<=40 すなわち x<=80の条件を満たさなければならない。
もう１つ、陳列スペースの制約条件を考えてみよう。
洋服ダンスの仕入れ台数を減らしてベッド１台を仕入れようとするとベッド１台あたりの陳列スペース-洋服ダンス１台あたりの陳列スペース*洋服ダンスの仕入れの減少=となり、3/2だけ多くのスペースを必要とする。
2m^2 - 1m^2 * 1/2 = 3/2m^2
ところで、陳列スペースは60m^2だけ余っているので、洋服ダンスの仕入れ台数を減らしてベッドを仕入れると、3/2x<=60 すなわち x<=40の式を満たさなければならない。
さて、洋服ダンスの台数を減らし、ベッドを仕入れると、ベッドが40台まで増やしたところでスペースが一杯になってしまう。
このようにして、新しい仕入れ案はx=40,y=20この時の陳列スペース及び予算はとなり、いずれも限度いっぱい使っていることになる。
- 陳列スペース：2*40+1*20=100(m^2)
- 仕入れ代金：3*40+6+20=240(万円)
- これ以上の仕入れ案はないか
さて現在、陳列スペースと仕入れ予算をすべて使いきって、ベッド40台、洋服ダンス20台を仕入れる案となっており、そのときの利益は140万である。それでは、これ以上利益を大きくする案はないだろうか？
まず、今の仕入れ案は、以下の連立方程式を解くことによって求められる。2x+ 3=100さて、新しい案は、陳列スペースと予算を使いきる上記以外の案なので、必ずあまりスペースが出る。
3x+6y=240
陳列スペースの余りをu、予算の余りをvとしたとき、新しい案は2x+ y=100-uこれらを解いてx,yを求めると
3x+6y=240-vx=40-2/3u+1/9vとなる。この値を目的関数に代入すると
y=20+1/3u-2/9vz=2x+3yが得られる。
=2*{40-2/3u+1/9v}+3*{20+1/3u-2/9v}
=140-1/3u-4/9v
この式により、uとvの値が増えると利益も減っていくので、不利になる事がわかる。
従って、現在の仕入れ案が利益が最も大きくなる最適な案であることがわかる。
演習課題
発表者：飯田
（１）次の問題を線形計画問題に表し、最適解を求めよ。
（２）上記（１）をグラフに示し、解説せよ。
1-1
下の表は、市販されている家畜の飼料A,B ２種類の１kgあたりの熱量、蛋白質、単価をまとめて示したものである。いま、A,Bを混合して熱量を12000カロリー以上、蛋白質を1300g以上取らせるようにしたい。A,Bをそれぞれ何kgずつ購入すれば費用が最も安くてすむか。
飼料A（1kgあたり） 飼料B（1kgあたり） 熱量 3000カロリー 1500カロリー 蛋白質 130g 260g 単価 250円 200円
1-2
ある工場で、２種類の製品A,Bを製造している。 製造量は、プレス機械と塗装機械の使用時間によって制限されている。 すなわち、製品Aを１個製造するためにはプレス機械40時間と塗装機械50時間を使用し、製品Bを１個製造するためにはプレス機械40時間と塗装機械25時間を使用する。 製品１個あたりの利益はAが60万円、Bが40万円である。 ただし、プレス機械の使用時間は１カ月480時間を、また塗装機械の使用時間は１カ月400時間を、それぞれ越えることができないものとする。 この場合製品A,Bをそれぞれ１カ月何個製造するのが最も有利か。
＜ヒント＞
1-1
２つの制約条件式を表すと3000x+1500y>=12000となる。
130 x+ 260y>=1300
1-2
以下のような表にまとめるとわかりやすい
製品Ａ 製品Ｂ 制約 プレス機械 40h 40h 480h 塗装機械 50h 25h 400h 利益 60万 40万
←講義のツボメニューへ
←【アプリケーション総論】シラバスへ
←鈴木研究室ホームへ