1.
数理計画法：Mathematical Programming(最適化問題：Optimization)
目的関数
Objective function:
制約条件式
Constraints function(s):
Z(x1,x2,…,xn)
b1(x1,x2,…,xn)=0
…..
bm1(x1,x2,…,xn)=0
bm1+1(x1,x2,…,xn)≦0
…..
bm1+m2 (x1,x2,…,xn)≦0
独立変数：Dependent variable:
従属変数：Independent variable:
Z(x1,x2,…,xn)
x1,x2,…,xn
数理計画法
Discrete Variable < Continuous Variable
(differentiable)
Constrained
< Unconstrained
Linear Function > Non Linear Function
> Probabilistic
Deterministic
･･････････
･････････
1. Linear Programming
* Linear Programming
* Integer Linear Programming
3. Combinational Optimization
* Dynamic Programming
* Relaxation Method
* Branch and Bound Method
2. Non Linear Programming
* Unconstrained Optimization
* Constrained Optimization
4. Probabilistic Methods
* Queuing Theory
* Game Theory
* Markov Chains
2.1 線形計画法：Linear Programming
Min. Z(xi) = Σ ai・ xi
x2
s.t. Σb1i ・ xi ≦ b01
……
Σbmi ・ xi ≦ b0m
x1
輸送問題：Transport Problem
輸送問題： Transport Problem
輸送問題： Transport Problem
目的関数 Min. Σ Σ Cij・ xij
制約条件
xij [ton]
Cij [B/ton]
Si [ton]
Cj [ton]
s.t.
Σ xij ≦ Si [ton]
Σ xij ＞＝ Cj [ton]
： i倉庫 からj 百貨店への輸送荷物量
: i倉庫 から j 百貨店への単位重量あたり輸送コスト
: i倉庫における在庫量
: j 百貨店における消費量
線形計画問題の条件
1.
2.
3.
目的関数とすべての制約が線形関数
制約条件はすべて ≦, ≧, or =
変数は連続変数
c.f.整数計画法
線形計画法の解法
1. 図形解法
2. 代数解法
3. シンプレックス法
[例]
Max. Z=60x1+80x2
s.t.
x1 ＋ x2≦10
4x1＋6x2≦48
0≦x1, 0≦x2
2.1.1図形解法 (1)
x2
x1 ＋x2≦10
10
x1 ＋x2=10
8
4x1＋6x2=48
4x1＋6x2≦48
x1 = 0
0≦ x1
0≦ x2
x2 = 0
Feasible Region
0
0
10
12
x1
図形解法(2)
x2
Z  (
Z Z
, )
x y
Z=60x1+80x2
10
x2=-3/4x1+Z/80
8
x1 ＋x2=10
4x1＋6x2=48
=(3,4)
Feasible Region
0
0
x2=-3/4x1+Z4/80
x2=-3/4x1+Z3/80
x2=-3/4x1+Z2/80
x2=-3/4x1+Z1/80
x1 =6
x2 =4
Z =680
端点：Corner Point(1)
x2
実行可能領域
Feasible Region
制約条件を全て満たす点の集合
10
8
(6,4)
Feasible Region
0
0
Corner Point
10
12
x1
端点(2)
x1 1-t
x1
x2
x3=tx1+(1-t)x2  S : Convex Set
For all t  [0,1] and all x1,x2 S : Convex Set*
t x2
端点(3)
端点定理
線形計画問題の最適解は，端点で得られる
もし，端点以外で，最適解が得られるとすると，
x0 =αx1＋βx2
α＋β = １ α≧０，β≧０
Ｚ = f(x0)
= ｃx0
= ｃαx1＋ｃβx2
= αf(x1)＋βf(x2)
= α（f(x1)−f(x2)）＋f(x2)
= β（f(x2)−(x1)）＋f(x1)
If f(x1)≦f(x2) then f(x1)≦f(x0)≦f(x2)
If f(x2)≦f(x1) then f(x2)≦f(x0)≦f(x1)
In either case, f(x0) is not a optimal solution.
端点(4)
a11x1+a21x2=0
a12x1+a22x2=0
a11x1+a21x2 + a31x3=0
a12x1+a22x2 + a32x3 =0
a13x1+a23x2 + a33x3 =0
凸領域
x1
x1
x2
x2
x3=tx1+(1-t)x2  S
For all t  [0,1] and all x1,x2 S
x3= tx1+ (1-  t)x2  S
For all x1,x2  S
2.2.2 代数解法
スラック変数
Slack Variable : x3, x4
Z=60x1+80x2
s.t.
x1 ＋ x2≦10
4x1＋6x2≦48
0≦x1, 0≦x2
Z=60x1+80x2
s.t.
x1 ＋ x2 ＋x3
4x1＋6x2
= 10
＋x4 =48
0≦x1, 0≦x2 , 0≦x3 , 0≦x4
(x1 , x2 , x3 , x4 )
x2
x1 ＋x2=10
(0,10,0,-12)
4x1＋6x2=48
10
8
x1 = 0
(0,8,2,0)
x2 = 0
(6, 4, 0, 0)
(12, 0,-2, 0)
0
0
12
10
(0, 0,10,48)
(10, 0, 0,8)
x1 ＋ x2 ＋x3
4x1＋6x2
= 10
＋x4 =48
x1
標準系
ａ11x1 + ａ12x2 + ‥‥
+ ａ1nxn＋xn+1
ａ21x1 + ａ22x2 + ‥‥
+ ａ2nxn
‥‥
‥‥
ａm1x1 + ａm2x2 + ‥‥
xi＝ 0
xj ＝ 0
‥
xk＝0
+ ａmnxn
n
非基底解 ：Non-Basic Solutions
非基底変数：Non-Basic Variables
＝ ｂ1
＋xn+2
＝ ｂ2
＋xn+m ＝ ｂm
xi’＝ c1
xj’＝ c2
‥
xk’＝cm
m
基底解 ： Basic Solutions
基底変数 ： Basic Variables
①
②
③
④
⑤
⑥
Ｘ1 Ｘ2 Ｘ3 Ｘ4
0 0 10 48
0 10
0 -12
0 8
2
0
10 0
0
8
12 0 -2
0
6 4
0
0
x2
②
Ｚ
0
800
x1 ＋ x2 ＋x3
640
600
4x1＋6x2
680
10
8
(0,8,2,0) ③
①
(6, 4, 0, 0)
⑥
0
0
(0, 0,10,48)
＋x4 =48
720
(0,10,0,-12)
④10
(10, 0, 0,8)
非基底変数
xi =0
基底変数
xi =c=0
(12, 0,-2, 0)
⑤
12
x1
= 10
2.2.3 シンプレックス法
Simplex Method
シンプレックス法の概念
Z(x15,x25,x35)
Z
Z(x12,x22,x32)
Z(x11,x21,x31)
隣接端点(1)
a11x1+a12x2+a13x3-b1=0
(1)
(2)
a21x1+a22x2+a23x3-b2=0
(3)
a31x1+a32x2+a33x3-b3=0
(4)
a41x1+a42x2+a43x3-b1 =0
a21x1+a22x2+a23x3-b2=0
a31x1+a32x2+a33x3-b3=0
a41x1+a42x2+a43x3-b1 =0
a11x1+a12x2+a13x3-b1=0
a21x1+a22x2+a23x3-b2=0
a31x1+a32x2+a33x3-b3=0
隣接端点(2)
(1) a21x1+a22x2+a23x3+x4
=b2
(2) a21x1+a22x2+a23x3 + x5
=b2
(3) a31x1+a32x2+a33x3
+x6
=b3
(4) a41x1+a42x2+a43x3
+x7 =b4
a21x1+a22x2+a23x3-b2=0
Basic
Non-Basic
Variables Variables
x1=a1
x2=a2
x3=a3
x4=a4
Basic
Non-Basic
Variables Variables
x1=c1
x2=c2
x3=c3
x5=0
x6=0
x7=0
x4=0
x5=0
x6=0
x7= c7
(1)
(2)
(3)
(4)
隣接端点(3)
n dimensions
* the number of non-basic variables at the corner points is n.
* n-1 non-basic variables are common
between the adjacent corner point
x2
x1 ＋ x2 ＋x3
4x1＋6x2
= 10
10
8
⑥
＋x4 =48
Non-Basic Variables
xi =0
Basic Variables
xi =c=0
(6, 4, 0, 0)
①
0
0
(0, 0,10,48)
④10
(10, 0, 0,8)
12
x1
隣接端点(4)
a11x1 + a12x2 + ‥‥ + a1nxn ＋xn+1
a21x1 + a22x2 + ‥‥ + a2nxn
‥‥
‥‥
am1x1 + am2x2 + ‥‥ + amnxn
Non-Basic Variables
＝ b1 (1)
＝ b2 (2)
＋xn+2
＋xn+m ＝ bm (m)
Basic Variables
xn+2 → Non-Basic Variables, x1 → Basic Variables
x1 + a12’x2 + ‥‥ + a1n’xn + xn+1 + a1n’xn+2
= b1 ’ (1) ’
a22’x2 + ‥‥+ a2n’xn
+ a1n’xn+2
= b2 ’ (2) ’
‥‥
‥‥
am2’x2 + ‥‥+amn’xn
+a1n’xn+2 +xn+m= bm ’ (m) ’
隣接端点(5)
a11x1 + a12x2 + ‥‥ + a1nxn＋xn+1
＝ b1
a21x1 + a22x2 + ‥‥ + a2nxn
＋xn+2
＝ b2
‥‥
‥‥
am1x1 + am2x2 + ‥‥ + amnxn
＋xn+m ＝ bm
(1)
(2)
(m)
(2)/a21
x1 + a12/a21x2 + ‥‥ + a1n /a21xn＋1 /a21xn+1
(1)－a11×(2)’
＝ b1 /a21
(2)’
0+(a22-a11a12/a21)x2 + ‥ + (a2n-a11a1n /a21)xn－a11 /a21xn+1 ＋xn+2 ＝ b2－a11b1 /a21 (1)’
(m)－am1×(1)’
0+(am2-am1a12/a21)x2 + ‥ + (amn-am1a1n /a21)xn－am1 /a21xn+1 ＋xn+m ＝ bm－am1b1 /a21 (m)’
a12’x2 + ‥‥ + a1n’xn + xn+1 + a1n’xn+2
x1 + a22’x2 + ‥‥+ a2n’xn
‥‥
am2’x2 + ‥‥+amn’xn
= b1 ’
(1) ’
+ a1n’xn+2
= b2 ’
(2) ’
+a1n’xn+2 +xn+m
= bm ’ (m) ’
‥‥
隣接端点(6)
a12’x2 + ‥‥ + a1n’xn + xn+1 + a1n’xn+2
x1 + a22’x2 + ‥‥+ a2n’xn
‥‥
am2’x2 + ‥‥+amn’xn
= b1 ’
(1) ’
+ a1n’xn+2
= b2 ’
(2) ’
+a1n’xn+2 +xn+m
= bm ’ (m) ’
‥‥
Z=c1 x1+ c2 x2+
+ cn xn
= c1(b2 ’- a22’x2 - ‥‥- a2n’xn - a1n’xn+2 ) + c2 x2+
= c1 b2 ’+(c2 - a22’ ) x2 ‥ +(c2 - a22’ ) xn - a1n’xn+2
+ cn xn
例
Z=60x1+80x2
s.t.
x1 ＋ x2≦10
4x1＋6x2≦48
0≦x1, 0≦x2
Z=60x1+80x2
s.t.
x1 ＋ x2 ＋x3
= 10 (1)
4x1＋6x2
＋x4 =48
(2)
0≦x1, 0≦x2 , 0≦x3 , 0≦x4
Non-Basic Variables
8
③
(0,8,2,0)
① 00
(0, 0,10,48)
Basic Variables
① x1 ,x2
x3 , x4
③ x1 , x4
x2 , x3
(2’)=(2)/a22
2/3x1＋x2
＋1/6x4 =8 (2’)
(1’)=(1) - (2’)
1/3x1 ＋ x3 ｰ1/6x4
=2 (1’)
1/3x1
＋ x3 ｰ 1/6x4 = 2 (1’)
2/3x1 ＋x2
＋1/6x4 = 8 (2’)
Z=60x+80x2=60x1+80 (8-2/3x1-1/6x4)
Z = 20/3 x1 – 40/3x4 + 640
Simplex Method Phase I
n 次元
* ひとつの端点には，
個の隣接端点がある．
どの端点を選ぶか？
（どの変数が次の基底解になるか？）
Z Z
Z
Z
Z ( x )  ( ,
, , ,  )
x1 x 2
xi
xn
Max(
Z Z
Z
Z
,
,, , )
x1 x 2
xi
xn
Z
Z
Simplex Method Phase I (cont.)
Z=60x1+80x2
Z Z
, )  (60,80)
x1 x 2
Max(60,80)  80
Z ( x )  (
x2 is selected as a new basic variable
Z Z
Z  ( , )
x1 x 2
x2
③ 8
(0,8,2,0)
①00
④10
(0, 0,10,48) (10, 0, 0,8)
Simplex Method Phase II
ｍ個の制約条件式
* m 個の基底変数. *
m 個の基底変数の内，どの基底変数が非基底変数になるか？
x1 ＋ x2 ＋x3
= 10
4x1＋6x2
＋x4 =48
x3, x4
48
10
0
x3
x1 =
x2 ＋x3 0 = 10
6x2
＋x4 =48
x4
8
② (0,10,0,-12)
x2
③ 8
(0,8,2,0)
10 x2
-12
0
①
0
x4 is selected as a new non-basic variable
(0, 0,10,48)
③ is selected as a corner point
10
シンプレックス法の解法手順
Step.1
初期実行可能解を求める.
Step.2 目的関数を改善する隣接端点を調べる
無い場合：その点が最適解
ある場合：Step 3へ
Step.3 目的関数を最も改善する方向を決定する．
（どの変数が次の基底解になるかを決める）
Step.4 制約条件を満たす中で，目的関数を最も改善する端点を決定する．
（どの変数が次の非基底解になるかを決める） Step 2へ
解なし［実行可能領域無し］
x1 ＋ x2≧10
2x1＋x2≦8
0≦x1
0≦x2
x2
10
8
4
10
x1
How to solve LP with Excel?
Spread Sheet
Example
A company produces two products P1 and P2 with three materials
M1, M2, and M3. 1kg of M1, 2kg of M2, and 3 kg of M3 are used
to produce 1 kg of P1. Similarly, 7kg of M1, 4kg of M2, and 2 kg
of M3 are used to produce 1 kg of P2. However, they have only
140kg of M1, 100kg of M2, and 120 kg of M3. Obtain the best
combination of product P1 and P2, when the benefits of 1kg of P1
and that of P2 are 3US$ and 5US$ respectively?
Z=3x1+5x2
s.t.
x1 ＋ 7x2≦140
Z=3x1+5x2
s.t.
x1 ＋ 7x2 ＋x3 =140
2x1 ＋4x2≦100
2x1 ＋4x2
3x1 ＋2x2≦120
3x1 ＋2x2
0≦x1, 0≦x2
＋x4 =100
＋x5 =120
0≦x1, 0≦x2 ,0≦x3, 0≦x4 , 0≦x5
Simplex Table(1)
Z=3x1+5x2
x1 ＋ 7x2 ＋x3 =140
s.t.
2x1 ＋4x2
＋x4 =100
3x1 ＋2x2
＋x5 =120
0≦x1, 0≦x2 ,0≦x3, 0≦x4 , 0≦x5
Z - 3x1 - 5x2 =0
Variable
(1)
I
(2)
(3)
(4)
B.V.
Z
Z 0 1
x3 140 0
x4 100 0
x5 120 0
x1 x2 x3
Marginal
x4
x5
-3
-5
0
0
0
1
7
1
0
0
140/7 = 20
2
4
0
1
0
100/4 = 25
3
2
0
0
1
120/2=60
Simplex Table(2)
Basic
(1)
I
(2)
(3)
(4)
(5)
II
(6)
(7)
(8)
Variable
Variable
Z
x1 x2 x3
Z
x3
x4
x5
Z
x2
x4
x5
0
1
-3
-5
140
0
1
100
0
120
Marginal
x4
x5
0
0
0
7
1
0
0
140/7 = 20
2
4
0
1
0
100/4 = 25
0
3
2
0
0
1
120/2=60
100
1
-16/7
0
5/7
0
0
20
0
1/7
1
1/7
0
0
20/ (1/7) = 140
(2)÷7
20
0
10/7
0
-4/7
1
0
20/ (10/7) =14
(3)-(6)×4
80
0
19/7
0
-2/7
0
1
80/ (19/7)≒ 30
(4)-(6)×2
(1) - (6)×(-5)
Simplex Table(3)
Basic
(5)
II
(6)
(7)
(8)
(9)
III (10)
(11)
(12)
(13)
IV (14)
(15)
(16)
Variable
x1 x2 x3
Marginal
x4
x5
5/7
0
0
1
1/7
0
0
20/ (1/7) = 140
(2)÷7
10/7
0
-4/7
1
0
20/ (10/7) =14
(3)-(6)×4
0
19/7
0
-2/7
0
1
80/ (19/7)≒ 30
(4)-(6)×2
132
1
0
0
-1/5
8/5
0
18
0
0
1
1/5 -1/10
0
14
0
1
0
-2/5 7/10
0
42
0
0
0
4/5 -19/10 1
142.5 1
0
0
0
9/8
1/4
(9)-(16)×(-1/5)
Variable
Z
Z
x2
x4
x5
Z
x2
x13
x5
Z
x2
x1
x3
100
1
-16/7
0
20
0
1/7
20
0
80
(1) - (6)×(-5)
(5) - (11)×(-16/7)
18/ (1/5) =90
(6) - (11)×1/7
(7) ÷10/7
42/ (4/5) = 52.5
(8)-(11)×19/7
7.5
0
0
1
0
3/8
-1/4
(10)-(16)×1/5
35
0
1
0
0
-1/4
1/2
(11) - (16)×(-2/5)
52.5
0
0
0
1
-19/8 5/4
(12)÷ 4/5
Shadow Price
(Marginal Value)
Z=3x1+5x2
s.t.
x1 ＋ 7x2 ＋x3 =140
2x1 ＋4x2
＋x4 =100
3x1 ＋2x2
＋x5 =120
0≦x1, 0≦x2 ,0≦x3, 0≦x4 , 0≦x5
(x*, x2*, x3 *, x4 *, x5 *)=(35,7.5, 52.5, 0, 0)
Transport Problem
Transport Problem
Transport Problem (3 depots(i=1..3) & 4 customers(j=1..4))
Transportation Cost Cij
j
1
2
3
1
2
1
1
xij [ton]
Cij [B/ton]
Si [ton]
Cj [ton]
2
1
1
2
3
1
2
3
4
3
3
1
(S1 , S2 , S3 )=(100,200,150)
(C1 , C2 , C3 , C4 )=(100,60,50,80)
： Amount of Transported Cargo
from i warehouse to j department
: Transport Cost per ton
from i warehouse to j department
: Amount of Stock at i warehouse
: Amount of Consumption at j department
Transport Problem (3 depots(i=1..3) & 4 customers(j=1..4))
Total Cost ΣCij xij= 2x11 +x12 +x13 +3x14
+x21 +x22 +2x23 +3x24
+x31 +2x32 +3x33 +x34
x11 +x12 +x13 +x14≦S1 =100
x11 +x21 +x31 ≧C1 = 100
x12 +x22 +x32 ≧ C2 = 60
x13 +x23 +x33 ≧ C3 = 50
x14 +x24 +x34 ≧ C4 = 80
x21 +x22 +x23 +x24 ≦S2 = 200
x31 +x32 +x33 +x34≦S3 = 150
xij
0
30
70
50
10
0
50
0
0
0
0
80
Transport Problem
Min. Σ Σ Cij・ xij
s.t. Σ xij ≦ Si [ton]
Σ xij ≦ Cj [ton]
xij [ton]
Cij [B/ton]
Si [ton]
Cj [ton]
： Amount of Transported Cargo
from i warehouse to j department
: Transport Cost per ton
from i warehouse to j department
: Amount of Stock at i warehouse
: Amount of Consumption at j department
Dynamic Programming(1)
DP is a mathematical technique used for the optimization of
multistage decision process. In this technique, the decisions that
affect the process are optimized in stage rather than simultaneously.
This is done by dividing the original decision problem into small
sub-problems that can be handled much more efficiently from a
computational standpoint. DP is a systematic procedure for
determining the combination of decisions that maximizes overall
effectiveness or minimizes overall disutility. It is based on the
principle of optimality enunciated by Bellman(1957).
Bellman's Principle of Optimality:
An optimal policy has the property that whatever the
initial state and the initial decisions are, the remaining decisions
must constitute an optimal policy with regard to the state
resulting from the first decision.
Dynamic Programming(2)
Example: Shortest Path
O
D
○D.P. can be applied to problems that are
･ are non-linear.
･ have non-convex feasible region.
･ have discontinuous variables.
×D.P. is limited to dealing with problems with relatively few constraints
DP complements LP
Queuing Theory(1)
Demand
Arrival
Average Arrival Rate
Probability of k arrivals
in t hours
vs.
Supply
Service
λ Average Arrival Rate
μ
Probability of k services ( t) k e  t
(t) k e  λt
k!
in t hours
k!
Pn: Probability that there are n customers in the system
Pn= (1- λ/μ)(λ/μ) n
Lq: Average number of customers in the queue
Lq= λ 2/(μ(μ- λ))
Wq: Average time a customer spends in the queue
Wq= λ/(μ(μ- λ))
Pw: Probability that an arriving customer must for services
Pw= λ /μ
Queuing Theory(2)
Demand
Arrival
Average Arrival Rate
Probability of k arrivals
in t hours
vs.
Supply
Service
λ Average Arrival Rate
μ
Probability of k services ( t) k e  t
(t) k e  λt
k!
in t hours
k!
Pn: Probability that there are n customers in the system
Pn= (1- λ/μ)(λ/μ) n
Lq: Average number of customers in the queue
Lq= λ 2/(μ(μ- λ))
Wq: Average time a customer spends in the queue
Wq= λ/(μ(μ- λ))
Pw: Probability that an arriving customer must for services
Pw= λ /μ
Queuing Theory(3)
Lq
Lq
10
50
9
8
40
7
6
30
5
4
20
3
2
10
1
0
00.0 0.1 0.2 0.3 0.4
0.0 0.1 0.2 0.3 0.4
0.5 0.6 0.7 0.8 0.9 1.0
0.5 0.6 0.7 0.8 0.9 1.0
λ /μ
λ /μ
Convex Function
(Strictly Convex Function)
a. One variable
1. Z[x 1  (1 -  )x 2 ]  Z[x1 ]  (1 -  )Z[x 2 ]
2. Z(x1 ) 
dZ(x1 )
(x 3 - x 1 )  z(x 3 )
dx
d 2 Z(x)
3.
0
dx
b. Multi variables
1. Z[x1  (1 -  )x 2 ]  Z[ x1 ]  (1 -  )Z[ x 2 ]
dZ( x1 )
2. Z( x1 ) 
(x3 - x1 )  z( x3 )
dx
3. t xx  0
 2Z

2

x
 21
  Z
2
   Z (x)   x x
 2 1
 
Hessian Matrix   2 Z
 xM x1
2Z
x1x2
2Z
2
x2

2Z
x M x2




2Z 
x1xM 

2
 Z 
x1xM 

 
2Z 
2
xM 
Report
1. Make a transportation problem on the condition that
each number of shippers and customers is more than 3.
2. Solve it with Excel.
3. Make “what-if ” analysis.
By the dead line, 25th July.
Assignment

ETS Rexroth STD PARTS STOCKING LIST (2).