第四回
線形計画法(2)
混合最大値問題
2003.4.24
山梨大学
1
内容と目標
内容:
1.シンプレックス表に起こる諸問題
2.LP問題と人為変数:罰金法
3.LP問題と人為変数:2段階法
目標:
1.シンプレックス表を十分に理解する
2.混合型LP問題を理解する
3.人為変数の概念を理解する
2003.4.24
山梨大学
2
スラック変数の導入
a11x1 + a12x2 + … + a1nxn+λ1
a12x1 + a22x2 + … + a2nxn
+λ2
= b1
= b2
(1)
…………………………………
am1x1 +am2x2 + … + amnxn
f ー c1x1 ー c2 x2… ー cnxn
2003.4.24
山梨大学
+λm= bm
=0
(2)
3
シンプレックス表(ステップ1)
基底
x1
λ1
λ2
a11
a21
. .
. .
. .
am1
-c1
。
。
。
λm
f
2003.4.24
x2
…
a12 …
a22 …
. . .
. . .
.. .
am2 …
-c1 …
xn
λ1 λ2 … λm
a1n 1
a2n 0
.. .
. . .
. . .
amn 1
-cn 0
山梨大学
定数
0 … 0
1 … 0
b1
b2
.
.
0… 0
0… 0
.
bm
0
4
シンプレックス表における
計算手順
(1) f行の最小負数の列に縦ワクをつける。
(2) 定数列の数を縦ワク列の数で割ってθ列
を作り、θ列の最小値の行に横ワクをつけ
る。
(3) 横ワク行の数をピボットで割り、ピ
ボットの値を1にする。
2003.4.24
山梨大学
5
(4) 横ワク行に適当な数を掛けて他の行から
引き、ピボット以外の縦ワク列の数を0にす
る。これで新しいステップの表が完成する。
(5)
上記(1)〜(4)を繰り返し、f行の数がすべ
て非負になれば最適解が得られている。
2003.4.24
山梨大学
6
混合型LP問題の例
例:
Max.
f = 2x1 + 3x2
(3)
制約条件:
2x1+5x2 ≦ 20
3x1+ 2x2 ≧ 14
(4)
x1 + 2x2= 6
x1 , x2,≧0
2003.4.24
山梨大学
7
スラック変数の導入
スラック変数を導入すると、
2x1+5x2+λ1
= 20
3x1+2x2
= 14
ーλ2
x1+2x2
(5)
=6
でも、これは標準形ではない!
2003.4.24
山梨大学
8
人為変数の導入
非負の(人為)変数μ2、μ3を導入すると
2x1+5x2+λ1
= 20
3x1+2x2 ―λ2 +μ2
x1+2x2
= 14
(6)
+μ3 = 6
「非常に大きな正数」Mを導入すると、
f = 2x1+3x2-Mμ2-Mμ3
(7)
Mはその性質から罰金とよばれる。
2003.4.24
山梨大学
9
罰金法ー>二段階法

罰金法:
– 理解しやすい
– 計算機による計算のときは不便

二段階法
– 第1段階:人為変数がすべて0になるよ
うな基底解を求める
– 第2段階:人為変数を条件式から除き、
目的関数の最大化を行う
2003.4.24
山梨大学
10
二段階法の例
まず人為変数が、すべて0になるような基底解を
求めることを考える。そのために
f’ = ーμ2 –μ3
(8)
という式を考え、これを目的関数として条件(6)のも
とで最大化する。これが第1段階である。
μ2, μ3は非負であるからf’=0になればμ2=μ3=0で、
第1段階は終わりである。ここで、μ2、μ3 を条件式
から除き、目的関数をfにして最大化を行う。これが
第2段階である。
2003.4.24
山梨大学
11
二段階法での計算例
最初はf’行に注目して計算し、基底に人為
変数がなくなったときf’行とμ2列、μ3列を除
き、その後はf行に注目して計算を行なえばよ
い。
下の表は(3), (6), (8)から作られたシンプレッ
クス表で、2段階法の計算例である。
2003.4.24
山梨大学
12
二段階法のシンプレックス表
2
ステップ
2003.4.24
3
0
0
μ2
-1
基底
x1
x2
λ1
1
0
-1
-1
1
2
μ3
f
f’
2
3
1
-2
-4
5
2
2
-3
-4
1
0
0
0
0
0
-1
0
0
1
2
0
2
-1
λ1
x1
3
f
f’
0
1
0
0
0
11/3
2/3
4/3
-5/3
-4/3
1
0
0
0
0
2/3
–1/3
1/3
-2/3
-1/3
3
0
2
3
λ1
x1
x2
f
f’
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
-1/4
-1/2
1/4
-1/4
0
7
4
1
11
0
4
0
2
0
λ1
x1
x2
f
0
1
0
0
1
2
4
1
1
0
0
0
0
0
1
0
8
6
4
12
山梨大学
λ2
-1
0
1
0
0
0
μ3
定数
0
0
1
0
0
20
14
6
0
-20
0
0
1
0
0
32/3
14/3
4/3
28/3
-4/3
13
fとf’行の計算
c行、c列にはfの係数とf’の係数を一緒に書いたの
で、ステップ1のf行、f’行を作るときに注意しなけ
ればならない。fの式(3)ではμ2、μ3の係数は0であ
るから、f行を作るときはμ2、μ3に対するcの値は
0と考えて作らねばならないし、f’の式(8)ではμ2、μ3
以外の変数の係数は0であるから、f’行を作るときは
μ2、μ3以外のcの値はすべて0と考えて作らねばな
らない。以下の表を参考して、例えば、
2003.4.24
山梨大学
14
f’行計算例
cj
C
定数
基底
c1
c2
c3
f’
a1
a2
a3
c’j
c’j = c1 a1 + c2 a2 + c3 a3 - cj
山梨大学
c
2003.4.24
15
例3-1の説明
(1)f行のx1列なら
0✕2 + 0✕3 + 0✕1 – 2 = -2
f’行のx1列なら
0✕2 +(-1)✕3 + (-1)✕1 - 0 = -4
(2) θの最小値が、どの行になるかは容易
に見当がつくので、θ列は省略しても
構いません。
2003.4.24
山梨大学
16
(3)ステップ1のf’行には最小負数の-4
が2つある。ここではx1列に縦ワクを
つけたが、x2列につけてもよい。
(4)ステップ2でμ2が基底から追い出さ
れたので、ここからはμ2は不要にな
り、μ2列の計算はやめることにした。
2003.4.24
山梨大学
17
(5) ステップ3ではμ3が基底から追い出された
ので、μ3列の計算もやめることにした。ここ
で、基底からすべての人為変数が追い出され、
当然f’=0になり、第一段階の終わりである。
この表では念のためにf’行が書いてあるが、
基底に人為変数がなくなると同時にf’行も必
要がなくなるから、本来ならここでf’行を表
から省いてよい。
2003.4.24
山梨大学
18
(6) ステップ3の表す条件式と目的関数の式
は以下のとおりである。これ以降は条件
(12)のもとで(13)のfを最大にする計算で、
それが第2段階である。したがって、縦ワ
クはf行の最小負数につけてある。
1
4
1
- 2  4
2
1
 2  1
4
1
-  2  11
4
1 -  2  7
x1
x2
f
2003.4.24
(12)
(13)
山梨大学
19
(7) ステップ3以降は人為変数の列がすべて空
白になり、定数列だけがはなれすぎるので、
定数列を左に移動して、μ2列の下におくこ
とを考えてもよい。
(8) この表はステップ4で最適解が得られ
λ1=8, x1=6, λ2=4, x2=μ2=μ3=0, f=12
である。すなわち
x1= 6, x2 = 0, f = 12
は最初の問題の最適解である。
2003.4.24
山梨大学
20
課
題
目的関数
制約条件
Max. f = 3x1+4x2
x1+ x2 ≦15
2x1 - x2 ≧7
- x1 +3x2≧9
x1, x2≧0
解答:
2003.4.24
x1=22/3, x2=23/3, f=158/3
山梨大学
21
ダウンロード

線形計画問題の解法