線形計画法(生産計画)

提供: Internet Web School

UNIQ6947b1b9f37b34c-MathJax-2-QINU2 による版
(差分) ←前の版 | 最新版 (差分) | 次の版→ (差分)

メディア: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の図である。

(図1.0)

条件UNIQ27d526106ab224eb-MathJax-99-QINUを充たす点UNIQ27d526106ab224eb-MathJax-100-QINUは 下のような,凸多角形の境界線も含めた内部にある。

(図1.1)

この凸多角形の頂点を 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の値を調べれば良いことが判る.


(図1.2)

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をもつことを表す.制約条件は満たされている.

個人用ツール