線形計画法

第5章仕入計画
p.69-98
追加：Ｅｘｃｅｌソルバーによる
線形計画法の解法
1
Operations Research
線形計画法
P74-78
2
1.線形計画法の意味
• 利益の最大を求めたり、在庫費用の最小を
求めるために、条件を連立一次方程式や連
立一次不等式の形で表すことを線形計画法
という。
• 線形計画法（Linear Programming : LP）
Linear・・・直線の線形一次
Programming・・・計画計画法
⇒すべての式が一次式で表される計画問題
3
2-1.線形計画法の問題 ①
例題5-1
新店舗3階には家具売り場を設置する予定である。
この売り場で、3月の卒業シーズンに備えて、新社
会人向けの陳列コーナーを設けようとしているもの
とする。仕入れる商品は、ベッドと洋服ダンスの2種
類とし、これらの商品を100㎡のスペースに陳列す
る計画である。なお、今回の仕入れに使える資金は、
240万円を限度とする。
限られた陳列スペース（100㎡）と仕入れ予算
（240万円）とを有効に活用し、できるだけ大きな利
益を上げるためにはそれぞれ何台ずつ仕入れると
良いだろうか。
4
2-1.線形計画法の問題 ②
• 例題5-1の条件をまとめると次のようになる
ベッド
(x)
洋服ダンス
(y)
陳列スペースおよび
仕入予算の制約
陳列スペース（１台あたり）
2㎡
1㎡
100㎡
仕入価格（1台あたり）
3万円
6万円
240万円
利
2万円
3万円
益(1台あたり）
x
ベッドの仕入台数・・・
洋服ダンスの仕入台数・・・
x
y
5
3-1 問題の定量化目的関数
• 利益を求める式
ベッドの1台あたりの利益は2万円→2ｘ
洋服ダンスの1台あたりの利益は3万円→3ｙ
利益の合計を z とすると、利益を求める式は
次のようになる。
y
2x 3y  z
利益の合計を大きくすることが目的なので、
この式は目的関数と呼ばれる。
6
3-2 問題の定量化制約条件式
• 陳列スペースの式
ベッドの1台あたりの陳列スペースは2㎡→2ｘ
洋服ダンスの1台あたりの陳列スペースは1㎡→ｙ
陳列スペースの合計は100㎡以内でなければならな
いので、陳列スペースの式は次のようになる。
2x  y  100
制約や条件がついた式を、制約条件式と呼ぶ。
7
3-3 問題の定量化制約条件式
• 仕入予算の式
ベッドの1台あたりの仕入価格は3万円→3ｘ
洋服ダンスの1台あたりの仕入価格は6万円→6ｙ
仕入代金の合計は240万円以内でなければならな
いので、仕入予算の式は次のようになる。
3x  6 y  240
ベッドと洋服ダンスの仕入台数ｘ，ｙは負の値をとる
ことはないので、非負変数と呼ばれる。
8
4-1 問題のグラフ化
• 家具売り場の仕入問題は次のようにまとめることができる。
非負変数　x, y（ x  0, y  0）について
2x  y  100  ①
3x  6 y  240　 ②
の制約条件式のもとで
2x  3 y  z　 ③
で表される目的関数zの値を、できるだけ大きくする
（最大にする）ような、 x, yの値を求める。
9
4-2 グラフの設定
グラフの設定
変数がｘ（ベッドの仕入台
数）とｙ（洋服ダンスの仕
入台数）の2つなので、横
軸をｘ、縦軸をｙとしてグラ
フを作る。
10
4-3 陳列スペースの式のグラフ化
• 陳列スペースの式のグラフ化
2x  y  100
この式は1次式なのでグラフが横軸
と縦軸に交わる点を結ぶ直線となる。
Ｘ軸との交点は、y=0として、
2x+0=100
x=50
次に、ｙ軸との交点は、x=0として、
0+y=100
y=100
この二つの点、(50,0)と(0,100)の直線
で結ぶとグラフのようになる。
不等式の範囲を示すと網掛けの部分になる。
11
4-4 仕入予算の式のグラフ化
• 仕入予算の式のグラフ化
3x  6 y  240
Ｘ軸との交点は、y=0として、
3x=240
x=80
次に、ｙ軸との交点は、x=0として、
0+6y=240
y=40
この二つの点、(80,0)と(0,40)の直線
で結ぶとグラフのようになる。
不等式の範囲を示すと網掛けの部分になる。
12
4-5 実行可能領域の指定
陳列スペースのグラフと仕入予算のグラフを
合わせるとグラフのようになる。
この二つのグラフの両方の制
約条件を満たす範囲は、OABC
で囲まれた範囲（線上も含む）
となる。この範囲のことを実行
可能領域という。利益を最大に
する仕入計画を考えるためには
グラフ上でこの実行可能領域を
調べばよい。
13
線形計画法
（P79～84）
Ｈ１０３０６１
常盤真由子
14
グラフによる最適解の求め方
例題5－1より
制約条件式
・陳列スペースの式
・・・2x + y ≦ 100
・仕入予算の式
・・・3x + 6y ≦ 240
（OABC＝実行可能領域）
グラフ上で利益が最大になる仕入計画を考える
15
利益を求める式のグラフ化
・利益を求める式（目的関数）・・・ 2x + 3y = z
・利益が80万円の式（2x + 3y = 80）
・利益が100万円の式（2x + 3y = 100）
・利益が140万円の式（2x + 3y = 140）
・利益が160万円の式（2x + 3y = 160）
点Ｂを境にしてそれ以上に利益を
大きくすると実行可能領域から出てしまう。
点Ｂのときの仕入計画が利益を
最大にする案である
16
利益を最大にする仕入計画
点Ｂは陳列スペースの式と仕入れ予算の式の
交点であるため、連立一次方程式で解くことが
できる。
・2x + y = 100
・3x + 6y =240
x=40 y=20
↓代入
・2x + 3y = z
z=140
利益を最大にする仕入計画
ベッド40台・洋服ダンス20台
最大利益140万円
17
グラフ解法
•
グラフによる線形計画法の問題を実際に解くには、通
常、実行可能領域を現す多角形の頂点（端点）が、そ
の解（端点解）となるため、表を作成して答を求めること
が多い。
端点
座標（x , y）
z
O
(0 , 0)
0
(0 , 40)
120
(40 , 20)
140
(50 , 0)
100
A
C
B
z = 2x + 3y （目的関数）
18
コンピュータを使ったグラフの作成
例題５－２
表計算ソフトを使って例題５－１のグラフを作成しなさい
〔処理条件〕
・入力するデータは文字列データとベッドの仕入れ台数の
数値データのみとし、それ以外は表計算ソフトで計算さ
せる。
・ベッドの仕入れ台数は、仕入れ予算の制約条件式
（3x+6y≦240）から最大でも80台なので「0～80」の数
値を入力する。
19
表の作成
A
1
2
3
B
C
D
＜制限条件式のグラフ＞
ベッドの
仕入台数
IF関数・・・条件を判断する
洋服ダンスの仕入れ台数
スペースの制約
100
予算の制約
4
0
5
10
6
20
7
30
8
40
9
50
15
10
60
10
11
70
5
12
80
13
14
80
40
60
35
40
30
20
25
0
20
↑
「y = 100 － 2x」の式の値
@ IF（条件式 , 条件が真のときの処理 ,
条件が偽のときの処理)
セル(B4)
=IF((100-2＊A4) >= 0 ,
100-2＊A4 , ””)
セル(C4)
=IF((240-3＊A4)/6 >= 0 ,
(240-3＊A4)/6 , ””)
0
↑
「y = (240 - 3x) / 6」の式の値
20
データのグラフ化
A
1
2
B
C
＜制限条件式のグラフ＞
洋服ダンスの仕入れ台数
3
ベッドの
仕入台数
4
0
100
40
5
10
80
35
6
20
60
30
7
30
40
25
8
40
20
20
9
50
0
15
10
60
10
11
70
5
12
80
0
スペースの制
約
予算の制
約
21
シンプレックス法
P85~P９５
H103058 月岡健一
H103062 中川末吉
22
シンプレックス法
○利益の最大化や在庫費用の最小化を求めた
りする場合、いくつもの変数から求めなけれ
ばならない場合がある。
→変数が二つの場合、グラフによる解法ができ
る。
→変数がいくつもあるときにシンプレックス法を
用いる。
23
シンプレックス法による解法
• 例題5‐1 新店舗3階には家具売り場を設置する予
定である。この売り場で、3月の卒業シーズンに備え
て、新社会人向けの陳列コーナーを設けようとして
いるものとする。仕入れる商品は、ベッドと洋服ダン
スの2種類とし、これらの商品を100㎡のスペースに
陳列する計画である。なお、今回の仕入れに使える
資金は、240万円を限度とする。
限られた陳列スペース（100㎡）と仕入れ予算
（240万円）を有効に活用し、できるだけ大きな利益
を上げるにはそれぞれ何台ずつ仕入れるべきか。
24
シンプレックス法による解法
（解説）
・ベッドの数をx、洋服ダンスの数をy、利益の
合計金額をz、使われていない陳列スペース
をu、仕入れ予算の使い残しをｖとする。
等式化
２ｘ＋ｙ＜＝１００ ⇒ ２ｘ＋ｙ＋u＝１００
３ｘ＋６ｙ＜＝２４０ ⇒ ３ｘ＋６ｙ＋ｖ＝２４０
２ｘ＋３ｙ＝ｚ
⇒ ２ｘ＋３ｙ＋０u＋０ｖ＝ｚ
25
シンプレックス法による解法
制約条件式の係数と
定数項を入力する。⇒
b
100
x
2
y
1
u
1
v
0
240
3
6
0
1
2
3
0
0
b
x
y
u
v
100
2
1
1
0
240
3
6
0
1
↓
目的関数の式の係数を
変数の上に入力する。⇒
26
シンプレックス法による解法
ｂ列の左側に
基底変数の列を
つくり、u,ｖを入力 ⇒
2
3
0
0
基底変数
b
x
y
u
v
u
v
100
240
2
3
1
6
1
0
0
1
2
3
0
0
↓
基底変数の
左側にｃ列を
つくり、「0,0」
を入力 ⇒
c
基底変数
b
x
y
u
v
0
0
u
v
100
240
2
3
1
6
1
0
0
1
27
シンプレックス法による解法
2
3
0
0
c
基底変数
b
x
y
u
v
0
u
100
2
1
1
0
0
v
240
3
6
0
1
z
0
-2
-3
0
0
z行を作成し、シンプレックス基準値を入力↑
シンプレックス基準の計算方法
例：ｘ列
｛（0×2）＋（0×3）－2｝＝－2
28
シンプレックス法による解法
θ列を作成し、100,40を入力 ↓
ｖとｙを入れ替える→
[Ａ表]
2
3
0
0
c
基底変数
b
x
Y↑
u
v
θ
0
u
100
2
1
1
0
100
0
←v
240
3
6
0
1
40*
z
0
-2
-3
0
0
29
オペレーションズリサーチ
経営情報入門p91～p95
H103058 月岡健一
H103062 中川末吉
30
軸要素とはき出し計算
最初に軸要素を「１」にする計算をする。
軸要素とは新たに基底変数に入れる変数の列と基底から外す変数の行とが交
差する蘭の数値のことをいう。
軸要素を「１」にするために[A表]の（２）を６で割る。
すると表[B表]の（４）のようになる。
[A表]
[B表]
2
3
0
0
c
基底変数
ｂ
ｘ
ｙ↑
u
ｖ
θ
0
u
100
2
1
1
0
100
(1)
0
←ｖ
240
3
⑥
0
1
40*
(2)
z
0
-2
-3
0
0
0
u
60
3/2
0
1
-1/6
(3)
3
ｙ
40
1/2
1
0
1/6
(4)=(2)÷6
31
軸要素とはき出し計算
この計算で y （洋服ダンスの台数）の値を最大にしたことが示される。
この結果 y を「４０」にしたところで v が「０」となって y と v が入れ替わる。
次に y 列の他の要素を「０」にすることを考える。
つまり y 列 u 行の値を「０」にする。
（１）から（４）を引いて（３）の列に書くと表のようになる。
[A表]
[B表]
2
3
0
0
c
基底変数
ｂ
ｘ
ｙ↑
u
ｖ
θ
0
u
100
2
1
1
0
100
(1)
0
←ｖ
240
3
⑥
0
1
40*
(2)
z
0
-2
-3
0
0
0
u
60
3/2
0
1
-1/6
(3)=(1)-(4)×1
3
ｙ
40
1/2
1
0
1/6
(4)=(2)÷6
32
軸要素のはき出し計算
これらの計算によって x =0, y =40, u =60, v =0 が求められた。
ベッドは仕入れず、洋服ダンスを40台仕入れ、陳列スペースは
60㎡使い残し、仕入予算は完全に使い切るという計画が立てられた。
このような基底変数を入れ替えるための計算をはき出し計算という。
[A表]
[B表]
2
3
0
0
c
基底変数
ｂ
ｘ
ｙ↑
u
ｖ
θ
0
u
100
2
1
1
0
100
(1)
0
←ｖ
240
3
⑥
0
1
40*
(2)
z
0
-2
-3
0
0
0
u
60
3/2
0
1
-1/6
(3)=(1)-(4)×1
3
ｙ
40
1/2
1
0
1/6
(4)=(2)÷6
33
新しい解の評価
新しい解が求められたので利益計算をする。
C 列と b 列をかけ合わせて合計することで求められる。
利益の値は120となって b 列 z 行に記入される。
次に各変数についてシンプレックス基準を計算する。
すると[表B]の z 行のようになる。
[A表]
[B表]
2
3
0
0
c
基底変数
ｂ
ｘ
ｙ↑
u
ｖ
θ
0
u
100
2
1
1
0
100
(1)
0
←ｖ
240
3
⑥
0
1
40*
(2)
z
0
-2
-3
0
0
0
u
60
3/2
0
1
-1/6
(3)=(1)-(4)×1
3
ｙ
40
1/2
1
0
1/6
(4)=(2)÷6
z
120
-1/2
0
0
1/2
34
新しい解の評価
次に x を基底変数にするので現在の基底変数 u、 y の中から
x と入れ替える変数を決める。
b 列の各要素を x 列の各要素で割る計算をする。
計算の結果 u 行の値「４０」が最小値となるので x と u で基底
変数の入れ替えを行う。
[A表]
[B表]
2
3
0
0
c
基底変数
ｂ
ｘ
ｙ↑
u
ｖ
θ
0
u
100
2
1
1
0
100
(1)
0
←ｖ
240
3
⑥
0
1
40*
(2)
z
0
-2
-3
0
0
0
u
60
3/2
0
1
-1/6
40*
(3)=(1)-(4)×1
3
ｙ
40
1/2
1
0
1/6
80
(4)=(2)÷6
z
120
-1/2
0
0
1/2
35
新しい解の評価
新しい解を求めるために x 列と u 行が交わる3/2を軸要素として
はき出し計算を行う。
計算すると図の[C表]のようになる。
[C表]の示す新しい解は、ベッドを40台仕入れ、洋服ダンスを20台仕入れ、
そして陳列スペースも予算も使い切るという仕入案を示している。
[A表]
[B表]
[C表]
2
3
0
0
c
基底変数
ｂ
ｘ
ｙ↑
u
ｖ
θ
0
u
100
2
1
1
0
100
(1)
0
←ｖ
240
3
⑥
0
1
40*
(2)
z
0
-2
-3
0
0
0
←u
60
3/2
0
1
-1/6
40*
(3)=(1)-(4)×1
3
ｙ
40
1/2
1
0
1/6
80
(4)=(2)÷6
z
120
-1/2
0
0
1/2
2
x
40
1
0
2/3
-1/9
(5)=(3)÷3/2
3
y
20
0
1
-1/3
2/9
(6)=(4)-(5)×1/2
36
シンプレックス表の完成
新しい解にもとずいて再び評価をし、利益が140万円と計算される。
続いてシンプレックス基準を計算する。
[C表]の z 行のようになる。
[A表]
[B表]
[C表]
2
3
0
0
c
基底変数
ｂ
ｘ↑
ｙ↑
u
ｖ
θ
0
u
100
2
1
1
0
100
(1)
0
←ｖ
240
3
⑥
0
1
40*
(2)
z
0
-2
-3
0
0
0
←u
60
3/2
0
1
-1/6
40*
(3)=(1)-(4)×1
3
ｙ
40
1/2
1
0
1/6
80
(4)=(2)÷6
z
120
-1/2
0
0
1/2
2
x
40
1
0
2/3
-1/9
(5)=(3)÷3/2
3
y
20
0
1
-1/3
2/9
(6)=(4)-(5)×1/2
z
140
0
0
1/3
4/9
37
シンプレックス表の完成
z 行のシンプレックス基準をみるとすべての値が「０」かプラスの値になったので
これ以上基底変数の入れ替えによって利益を大きくすることができないことを示す。
したがって x =40 y =20 の仕入案が最大の利益をもたらす最適が計画であるとい
うことになる。
[A表]
[B表]
[C表]
2
3
0
0
c
基底変数
ｂ
ｘ↑
ｙ↑
u
ｖ
θ
0
u
100
2
1
1
0
100
(1)
0
←ｖ
240
3
⑥
0
1
40*
(2)
z
0
-2
-3
0
0
0
←u
60
3/2
0
1
-1/6
40*
(3)=(1)-(4)×1
3
ｙ
40
1/2
1
0
1/6
80
(4)=(2)÷6
z
120
-1/2
0
0
1/2
2
x
40
1
0
2/3
-1/9
(5)=(3)÷3/2
3
y
20
0
1
-1/3
2/9
(6)=(4)-(5)×1/2
z
140
0
0
1/3
4/9
38
Ｅｘｃｅｌソルバーによる
線形計画法の解法
参考
http://www.kogures.com/hitoshi/webtext/lp-solver/
39
ソルバーアドインのインストール
Excelの「ツール」に「ソルバー」があ
ればすぐに使用できます。なければ
次の手順でインストールする。
１．ツール→アドインを選択し有効な
アドインを表示する。
２．有効なアドインボックスからソル
バーアドインをマークする。
３．その後はシステムの指示に従い、
操作する。
40
モデルの作成
• Ｅｘｃｅｌで線形計画法の問題を入力する。
• ここでは教科書ｐ７６ページ例題５－１からの家具の
陳列に対する線形計画法の数値を使用する。
目的関数
z = 2x + 3y → 最大
制約条件
2x + y <= 100 ・・・ ①
3x + 6y <= 240 ・・・ ②
41
Ｅｘｃｅｌでの入力
• Ｅｘｃｅｌを起動して、次のように入力する。
目的関数
z = 2x + 3y → 最大
制約条件
2x + y
3x + 6y
<= 100 ・・・ ①
<= 240 ・・・ ②
• 各係数、在庫量はそのまま入力する
• 求めるべき最適発注量をソルバーでは「変化させるセル」という。
• 目的関数の式、制約条件の式を入力する
42
目的関数の式
制約条件の式
43
ソルバーでの条件設定
ツールからソルバーを起動し
– 目的セルにD3を選択する。
– 変化させるセルにB3とC3を選択。
– 制約条件を指定するために、「追加」のボタンをクリックしてセル参
照にD5、制約条件にE5を選択する。D6、E6についても追加してお
く。
44
計算の実行とその結果
設定が終了し「実行」ボタンをクリックすると計算が実行され、探索結果が
表示される。
これにより、最適解での変数の値、最適解での目的関数の値、変数が最
適値であるときの制約式の値が示される。
•変化させるセルに，最適解での変数の値が表示されています。
•目的セルに最適解での目的関数の値（最大値）が表示されています。
•制約条件の式に，変数が最適値であるときの制約式の値が表示されています。
45

Download Report