線形計画法(生産計画)
提供: Internet Web School
メディア:Example.ogg線形計画法は 線形計画法 (Wikipedia)に説明がある.
解法には
シンプレックス法(Wikipedia)や内点法(Wikipedia)がある. シンプレクス法は[菅沼]の解説が判りやすい.
ここでは2つの例を用いて説明する. Microsoft Excel のソルバーを用いた解法例も説明する.
生産計画
例題1
ある製造会社があって, UNIQ27d526106ab224eb-MathJax-76-QINU と UNIQ27d526106ab224eb-MathJax-77-QINU という2種類の製品の製造販売をしている. これらを製造するには, 原材料UNIQ27d526106ab224eb-MathJax-78-QINU,UNIQ27d526106ab224eb-MathJax-79-QINU,UNIQ27d526106ab224eb-MathJax-80-QINUが必要で, UNIQ27d526106ab224eb-MathJax-81-QINU, UNIQ27d526106ab224eb-MathJax-82-QINUをそれぞれ1単位当 たり造るのに必要な量と, 使用できる在庫量が下の表のように決まっている.
原材料\製品 | x | y | 在庫量 |
A | 10 | 20 | 400 |
B | 20 | 10 | 600 |
C | 15 | 40 | 1300 |
UNIQ27d526106ab224eb-MathJax-83-QINU, UNIQ27d526106ab224eb-MathJax-84-QINUを販売するとそれぞれ1単位当たり2万円, 1万円の利益が得られる. 問題は, 表の在庫量の範囲で, UNIQ27d526106ab224eb-MathJax-85-QINUとUNIQ27d526106ab224eb-MathJax-86-QINUをそれぞれ何単位ずつ造れば利益が最大に なるかである。
線形計画法(1)
これを数式化すると, UNIQ27d526106ab224eb-MathJax-87-QINU, UNIQ27d526106ab224eb-MathJax-88-QINUの製造量をUNIQ27d526106ab224eb-MathJax-89-QINU, UNIQ27d526106ab224eb-MathJax-90-QINUで表すとして:
原材料UNIQ27d526106ab224eb-MathJax-91-QINU, UNIQ27d526106ab224eb-MathJax-92-QINU, UNIQ27d526106ab224eb-MathJax-93-QINUについての制約から
UNIQ27d526106ab224eb-MathJax-94-QINU
負の生産量はないのであるから
UNIQ27d526106ab224eb-MathJax-95-QINU
利益は
UNIQ27d526106ab224eb-MathJax-96-QINU
で結局, (6)をUNIQ27d526106ab224eb-MathJax-97-QINUの条件のもとで最大にすることになる。
下の図は関数UNIQ27d526106ab224eb-MathJax-98-QINUの図である。
条件UNIQ27d526106ab224eb-MathJax-99-QINUを充たす点UNIQ27d526106ab224eb-MathJax-100-QINUは 下のような,凸多角形の境界線も含めた内部にある。
この凸多角形の頂点を UNIQ27d526106ab224eb-MathJax-101-QINU とすると,
内部の点UNIQ27d526106ab224eb-MathJax-102-QINUはこれらの頂点UNIQ27d526106ab224eb-MathJax-103-QINUによって
UNIQ27d526106ab224eb-MathJax-104-QINU
で表される。これをUNIQ27d526106ab224eb-MathJax-105-QINUの凸結合という.
UNIQ27d526106ab224eb-MathJax-106-QINU
には「線形性」が成り立っている.
これは UNIQ27d526106ab224eb-MathJax-107-QINU
とUNIQ27d526106ab224eb-MathJax-108-QINUについて,
UNIQ27d526106ab224eb-MathJax-109-QINU
という性質である。この線形性を使うと,以下の議論ができる。
まず各頂点での関数UNIQ27d526106ab224eb-MathJax-110-QINUの値
UNIQ27d526106ab224eb-MathJax-111-QINU
のうち最大値をUNIQ27d526106ab224eb-MathJax-112-QINUとする.
凸多角形の内の任意の点UNIQ27d526106ab224eb-MathJax-113-QINUに対するUNIQ27d526106ab224eb-MathJax-114-QINUは
UNIQ27d526106ab224eb-MathJax-115-QINUがUNIQ27d526106ab224eb-MathJax-116-QINU の凸結合で表されることから
UNIQ27d526106ab224eb-MathJax-117-QINU
さらにUNIQ27d526106ab224eb-MathJax-118-QINUの線形性から
UNIQ27d526106ab224eb-MathJax-119-QINU
UNIQ27d526106ab224eb-MathJax-120-QINUが最大で,(3)のように各UNIQ27d526106ab224eb-MathJax-121-QINUは正の数(UNIQ27d526106ab224eb-MathJax-122-QINU)であるから,
UNIQ27d526106ab224eb-MathJax-123-QINU
さらに,(2)から
UNIQ27d526106ab224eb-MathJax-124-QINU
で
UNIQ27d526106ab224eb-MathJax-125-QINU
となる。結局,関数UNIQ27d526106ab224eb-MathJax-126-QINUの制約条件を表す凸多角形の内部(境界を含む)の点全てを調べる必要がなく、
頂点での関数UNIQ27d526106ab224eb-MathJax-127-QINUの値を調べれば良いことが判る.
UNIQ27d526106ab224eb-MathJax-128-QINU式のように変数に関する制約条件式が1次式で与えられ, UNIQ27d526106ab224eb-MathJax-129-QINU式のように評価関数も1次式で与えられる問題は線形計画法と呼ばれる.
線形化計画法の代表的な解法であるシンプレクス法は,制約条件を表す凸多角形の頂点での 関数UNIQ27d526106ab224eb-MathJax-130-QINUの値を効率的に調べる方法である。 適当な,頂点から始め,関数UNIQ27d526106ab224eb-MathJax-131-QINUの値が増大する頂点へ次々移動して,最大解を探す.
この他に,凸多角形の内部の点から,最大解を与える頂点を探索する内点法もある。
線形計画法(2)
例題2
ある企業では製品A,B,Cを原料Ⅰ,Ⅱ,Ⅲ,Ⅳ用いて生産している. 製品A,B,C の1単位当たり利益をそれぞれ80,110,95とする. また, 製品A,B,Cを1単位生産するのに必要な原料Ⅰ,Ⅱ,Ⅲ,Ⅳのそれぞれ量と使用可能な上限が次の表で与えられる. これらの条件のもとに,利益を最大にするには製品A,B,Cをそれぞれ,どれだけ生産すれば良いか?.
原材\製品名 | A | B | C | 使用できる上限 |
Ⅰ | 4 | 0 | 7 | 90 |
Ⅱ | 1 | 3 | 9 | 60 |
Ⅲ | 6 | 0 | 14 | 110 |
Ⅳ | 4 | 10 | 1 | 75 |
この問題も例題1と同じように以下のように数学的に定式化される.
製品A,B,CをそれぞれUNIQ27d526106ab224eb-MathJax-132-QINU 単位生産するときUNIQ27d526106ab224eb-MathJax-133-QINUは以下の不等式を満たす.
UNIQ27d526106ab224eb-MathJax-134-QINU
さらに各製品生産量は負ではないから
UNIQ27d526106ab224eb-MathJax-135-QINU
この制約条件のもとに
UNIQ27d526106ab224eb-MathJax-136-QINU
を最大にするUNIQ27d526106ab224eb-MathJax-137-QINUを求めよ.
この問題の解法にはシンプレックス法や内点法がある.
シンプレクス法は[菅沼]の解説が判りやすい.
この問題を解くのにはMicrosoft Excelのソルバーや
フリーソフトのOpen Office で提供されるソルバーと同等の機能をもつソフトを用いることができる.
この問題のMicrosoft Excelのソルバーによる解法例を示す。
Microsoft Excelのソルバー を用いる.
- ソルバーの導入
- Excel の メニュー「データ」に「分析」「ソルバー」がある場合は以下の手続きは不要である.
そのままソルバーによる解法の例を実行する.
- Excelのメニュー「データ」に「分析」「ソルバー」がない場合
- ファイル > オプション > アドイン の順に選択
- アドインの表示窓 アクティブでないアプリケーションにExcelソルバー があることを確認
- 画面下の管理(A)と表示される小さい窓のドロップダウンリスト▼でExcelアドインを選択後,設定(G)をクリック
- 有効なアドインが小窓で表示される. その中のソルバーアドインを選択しチェックを入れ[OK]をクリックする.
- ソルバーによる解法の例
- Excelに下記の作成例のように表1のデータを作成する.
この作成例では
セル B2,C2,D2 が 製品A,B,Cのそれぞれの生産量
UNIQ27d526106ab224eb-MathJax-138-QINUを表す.
- 線形の一次式
UNIQ27d526106ab224eb-MathJax-139-QINU
をE3, E4, E5, E6に入力している.
ここで,sumproduct(B4:D4,BUNIQ27d526106ab224eb-MathJax-140-QINU2)はベクトル(B4,C4,D4) と(B2,C2,D2)の内積 B4*B2+C4*C2+D4*D2 でありUNIQ27d526106ab224eb-MathJax-141-QINU を表す.
- F3,F4, F5, F6には,原材料Ⅰ,Ⅱ,Ⅲ,Ⅳの使用できる量の上限を入力している.
- E7には
UNIQ27d526106ab224eb-MathJax-142-QINU
を表す式を入力している.
- 表のデータを入力後,
- メニュー 「データ」,「分析」,「ソルバー」の順にクリックしてソルバーのパラメータ入力用の窓を開く.
- 表のデータを入力後,
- 目的の設定という欄にセルE7を指定する
- 目標値には「最大値」を選択し,チェックを入れる.
- 変数セルの変更欄にはx_1,x_2,x_3を表すセルB2からD2をドラックして指定する.
- 制約条件の対象の欄には
この例題の制約条件式
UNIQ27d526106ab224eb-MathJax-143-QINU
を表す式を入力する. このためには,入力窓の「追加」をクリックし制約条件の追加入力用の窓を表示させ, 例えば
UNIQ27d526106ab224eb-MathJax-144-QINU
を表す式を入力するのであればセルの参照欄にUNIQ27d526106ab224eb-MathJax-145-QINUを表すセルE3を指定 ≦,=,≧などのドロップダウンリストで≦を選択し,制約条件の欄には上限値の90を入力する.入力後さらに「追加」をクリックし他の3つの制約条件式も同様に入力する.
- さらに, 制約条件式
UNIQ27d526106ab224eb-MathJax-146-QINU を入力するため
「制約のない変数を非負数にする」 にチェックを入れる.
- 最後に「解決」をクリックすると以下の結果が出力される.
UNIQ27d526106ab224eb-MathJax-147-QINU
のときに
UNIQ27d526106ab224eb-MathJax-148-QINU
が最大値1485をもつことを表す.制約条件は満たされている.