線形計画法（コピー）

提供: Internet Web School

メディア:Example.ogg線形計画法は 線形計画法 （Wikipedia）に説明がある.

解法には

シンプレックス法（Wikipedia）や内点法（Wikipedia）がある. シンプレクス法は[菅沼]の解説が判りやすい．

ここでは2つの例を用いて説明する.　Microsoft　Excel　のソルバーを用いた解法例も説明する.

生産計画

例題1

ある製造会社があって, UNIQ4a7804d74ba148f4-MathJax-76-QINU と UNIQ4a7804d74ba148f4-MathJax-77-QINU という２種類の製品の製造販売をしている. これらを製造するには, 原材料UNIQ4a7804d74ba148f4-MathJax-78-QINU，UNIQ4a7804d74ba148f4-MathJax-79-QINU，UNIQ4a7804d74ba148f4-MathJax-80-QINUが必要で, UNIQ4a7804d74ba148f4-MathJax-81-QINU, UNIQ4a7804d74ba148f4-MathJax-82-QINUをそれぞれ1単位当 たり造るのに必要な量と, 使用できる在庫量が下の表のように決まっている．

原材料＼製品	x	y	在庫量
A	10	20	400
B	20	10	600
C	15	40	1300

UNIQ4a7804d74ba148f4-MathJax-83-QINU, UNIQ4a7804d74ba148f4-MathJax-84-QINUを販売するとそれぞれ1単位当たり２万円, 1万円の利益が得られる. 問題は, 表の在庫量の範囲で, UNIQ4a7804d74ba148f4-MathJax-85-QINUとUNIQ4a7804d74ba148f4-MathJax-86-QINUをそれぞれ何単位ずつ造れば利益が最大に なるかである。

線形計画法(1)

これを数式化すると, UNIQ4a7804d74ba148f4-MathJax-87-QINU, UNIQ4a7804d74ba148f4-MathJax-88-QINUの製造量をUNIQ4a7804d74ba148f4-MathJax-89-QINU, UNIQ4a7804d74ba148f4-MathJax-90-QINUで表すとして：

原材料UNIQ4a7804d74ba148f4-MathJax-91-QINU, UNIQ4a7804d74ba148f4-MathJax-92-QINU, UNIQ4a7804d74ba148f4-MathJax-93-QINUについての制約から

UNIQ4a7804d74ba148f4-MathJax-94-QINU

負の生産量はないのであるから

UNIQ4a7804d74ba148f4-MathJax-95-QINU

利益は

UNIQ4a7804d74ba148f4-MathJax-96-QINU

で結局, (6)をUNIQ4a7804d74ba148f4-MathJax-97-QINUの条件のもとで最大にすることになる。

下の図は関数UNIQ4a7804d74ba148f4-MathJax-98-QINUの図である。

(図1.0)

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

(図1.1)

この凸多角形の頂点を UNIQ4a7804d74ba148f4-MathJax-101-QINU とすると,

内部の点UNIQ4a7804d74ba148f4-MathJax-102-QINUはこれらの頂点UNIQ4a7804d74ba148f4-MathJax-103-QINUによって

UNIQ4a7804d74ba148f4-MathJax-104-QINU

で表される。これをUNIQ4a7804d74ba148f4-MathJax-105-QINUの凸結合という．

UNIQ4a7804d74ba148f4-MathJax-106-QINU

には「線形性」が成り立っている.

これは UNIQ4a7804d74ba148f4-MathJax-107-QINU

とUNIQ4a7804d74ba148f4-MathJax-108-QINUについて,

UNIQ4a7804d74ba148f4-MathJax-109-QINU

という性質である。この線形性を使うと,以下の議論ができる。

まず各頂点での関数UNIQ4a7804d74ba148f4-MathJax-110-QINUの値

UNIQ4a7804d74ba148f4-MathJax-111-QINU

のうち最大値をUNIQ4a7804d74ba148f4-MathJax-112-QINUとする.

凸多角形の内の任意の点UNIQ4a7804d74ba148f4-MathJax-113-QINUに対するUNIQ4a7804d74ba148f4-MathJax-114-QINUは

UNIQ4a7804d74ba148f4-MathJax-115-QINUがUNIQ4a7804d74ba148f4-MathJax-116-QINU の凸結合で表されることから

UNIQ4a7804d74ba148f4-MathJax-117-QINU

さらにUNIQ4a7804d74ba148f4-MathJax-118-QINUの線形性から

UNIQ4a7804d74ba148f4-MathJax-119-QINU

UNIQ4a7804d74ba148f4-MathJax-120-QINUが最大で,(3)のように各UNIQ4a7804d74ba148f4-MathJax-121-QINUは正の数(UNIQ4a7804d74ba148f4-MathJax-122-QINU)であるから,

UNIQ4a7804d74ba148f4-MathJax-123-QINU

さらに,(2)から

UNIQ4a7804d74ba148f4-MathJax-124-QINU

で

UNIQ4a7804d74ba148f4-MathJax-125-QINU

となる。結局,関数UNIQ4a7804d74ba148f4-MathJax-126-QINUの制約条件を表す凸多角形の内部(境界を含む)の点全てを調べる必要がなく、

頂点での関数UNIQ4a7804d74ba148f4-MathJax-127-QINUの値を調べれば良いことが判る．

(図1.2)

UNIQ4a7804d74ba148f4-MathJax-128-QINU式のように変数に関する制約条件式が1次式で与えられ, UNIQ4a7804d74ba148f4-MathJax-129-QINU式のように評価関数も1次式で与えられる問題は線形計画法と呼ばれる.

線形化計画法の代表的な解法であるシンプレクス法は,制約条件を表す凸多角形の頂点での 関数UNIQ4a7804d74ba148f4-MathJax-130-QINUの値を効率的に調べる方法である。 適当な,頂点から始め,関数UNIQ4a7804d74ba148f4-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をそれぞれUNIQ4a7804d74ba148f4-MathJax-132-QINU 単位生産するときUNIQ4a7804d74ba148f4-MathJax-133-QINUは以下の不等式を満たす.

UNIQ4a7804d74ba148f4-MathJax-134-QINU

さらに各製品生産量は負ではないから

UNIQ4a7804d74ba148f4-MathJax-135-QINU

この制約条件のもとに

UNIQ4a7804d74ba148f4-MathJax-136-QINU

を最大にするUNIQ4a7804d74ba148f4-MathJax-137-QINUを求めよ.

この問題の解法にはシンプレックス法や内点法がある. シンプレクス法は[菅沼]の解説が判りやすい．

この問題を解くのにはMicrosoft Excelのソルバーや フリーソフトのOpen Office で提供されるソルバーと同等の機能をもつソフトを用いることができる. この問題のMicrosoft Excelのソルバーによる解法例を示す。

Microsoft Excelのソルバー　を用いる.

• ソルバーの導入
• Excel　の　メニュー「データ」に「分析」「ソルバー」がある場合は以下の手続きは不要である．　

そのままソルバーによる解法の例を実行する．　

• Excelのメニュー「データ」に「分析」「ソルバー」がない場合
  • ファイル　>　オプション　>　アドイン　の順に選択
  • アドインの表示窓　アクティブでないアプリケーションにExcelソルバー　があることを確認
  • 画面下の管理(A)と表示される小さい窓のドロップダウンリスト▼でExcelアドインを選択後，設定(G)をクリック
  • 有効なアドインが小窓で表示される.　その中のソルバーアドインを選択しチェックを入れ[OK]をクリックする.

• ソルバーによる解法の例　
  • Excelに下記の作成例のように表１のデータを作成する.

この作成例では セル　B2,C2,D2　が　製品A,B,Cのそれぞれの生産量 UNIQ4a7804d74ba148f4-MathJax-138-QINUを表す.

• • 線形の一次式

UNIQ4a7804d74ba148f4-MathJax-139-QINU

をE3, E4, E5, E6に入力している.

ここで,sumproduct(B4:D4,BUNIQ4a7804d74ba148f4-MathJax-140-QINU2)はベクトル(B4,C4,D4) と(B2,C2,D2)の内積　B4*B2+C4*C2+D4*D2　 でありUNIQ4a7804d74ba148f4-MathJax-141-QINU　を表す．

• • F3,F4, F5, F6には,原材料Ⅰ,Ⅱ,Ⅲ,Ⅳの使用できる量の上限を入力している.

• • E7には

UNIQ4a7804d74ba148f4-MathJax-142-QINU

を表す式を入力している．

• • 表のデータを入力後,
    • メニュー　「データ」，「分析」，「ソルバー」の順にクリックしてソルバーのパラメータ入力用の窓を開く．

• • • 目的の設定という欄にセルE7を指定する　
    • 目標値には「最大値」を選択し，チェックを入れる．
    • 変数セルの変更欄にはx_1,x_2,x_3を表すセルB2からD2をドラックして指定する．

• • • 制約条件の対象の欄には

この例題の制約条件式

UNIQ4a7804d74ba148f4-MathJax-143-QINU

を表す式を入力する．　 　このためには,入力窓の「追加」をクリックし制約条件の追加入力用の窓を表示させ, 例えば

UNIQ4a7804d74ba148f4-MathJax-144-QINU

を表す式を入力するのであればセルの参照欄にUNIQ4a7804d74ba148f4-MathJax-145-QINUを表すセルE3を指定 ≦,=,≧などのドロップダウンリストで≦を選択し,制約条件の欄には上限値の90を入力する．入力後さらに「追加」をクリックし他の３つの制約条件式も同様に入力する．

• • • さらに, 制約条件式　

UNIQ4a7804d74ba148f4-MathJax-146-QINU を入力するため

「制約のない変数を非負数にする」　にチェックを入れる．

• • 最後に「解決」をクリックすると以下の結果が出力される.

UNIQ4a7804d74ba148f4-MathJax-147-QINU のときに

UNIQ4a7804d74ba148f4-MathJax-148-QINU　

が最大値1485をもつことを表す.制約条件は満たされている.