1
「基礎OR」/「OR演習」
第2回
10/06/2009
森戸 晋
鉄鉱石配合問題の定式化
• 変数: Ti=配合1トン当たりの鉱山jの鉱
石の重量 (≧0)
• 目的関数:最小化 トン当たりの費用
• 制約条件:各元素(A-C)の品質基準満足
配合の合計は1トン
• Min z=800T1+400T2+600T3+500T4 (費用)
• s.t. 10T1+ 3T2 + 8T3+ 2T4≧ 5 (元素A)
90T1+150T2+75T3+175T4≧100 (元素B)
45T1+ 25T2+20T3+ 37T4≧ 30 (元素C)
T1+
T2+ T3+
T4= 1 (合計1)
T1,
T2, T3,
T4 ≧ 0(非負条件)
2
Mic rosoft Exc e l 8 .0 d 感度レポート
ワークシート名: [Book1 0 ]鉄鉱石配合問題
レポート作成日: 0 1 / 1 0 / 0 8 1 7 :2 3 :1 1
変化させるセル
セル
$B$6
$C$6
$D$6
$E$6
名前
変数 鉱石1
変数 鉱石2
変数 鉱石3
変数 鉱石4
計算
限界
値
コスト
0.259259259
0
0.703703704
0
0.037037037
0
0 91.11111111
目的セル
係数
800
400
600
500
許容範囲内 許容範囲内
増加
減少
223.6363636
120
66.84782609
300
85.71428571 118.2692308
1E+30 91.11111111
制約条件
セル
$F$9
$F$10
$F$11
$F$12
名前
元素A 含有量
元素B 含有量
元素C 含有量
合計 含有量
計算
値
5
131.6666667
30
1
潜在
制約条件 許容範囲内 許容範囲内
価格
右辺
増加
減少
44.44444444
5
2.375
0.25
0
100 31.66666667
1E+30
4.444444444
30 0.714285714
7
1 5 5 .5 5 5 5 5 6
1
0.25 0.043478261
3
4
被約費用(reduced cost)
(EXCELでは)限界コスト
• 変数(列)に対応
• 二つの解釈が可能
①xj=0である変数を無理に正にしようとし
たときの、xj単位当たりの目的関数値の増
加の度合い
②xj=0である変数を正にする可能性が生
じる(つまり、最適解が最適でなくなる)目
的関数の係数cjの変化量
5
潜在価格(shadow price)
双対価格(dual price)
• 制約条件式(行)に対応(別名: 単体乗数
(simplex multiplier), 双対変数(dual
variable))
• 当該制約条件の右辺定数以外のすべて
の係数を元の問題のままにした上で、当
該制約条件の右辺定数を微小量増加させ
たときの、増加単位量当たりの最適目的
関数値の改善/改悪の度合い
6
農場経営問題のLP定式化
• ①変数(variables)
②目的関数(objective function)
③制約条件(constraints)
• (決定)変数:wheat、alfalfa、beefの生産量
alfalfaの販売・購入量
• 目的関数:「収益ー費用」最大
• 制約条件:土地の許容上限
用水の許容上限
alfalfaのバランス
7
農場経営問題 変数・目的関数
• 変数(variables):(単位の設定は一例)
W=wheat raised and sold (acres)
A=alfalfa raised (tons)
B=beef raised and sold (tons)
Ab=alfalfa bought (tons)
As=alfalfa sold (tons)
• 目的関数(objective function):
最大化 72Wー30/3A+560Bー36Ab+34As
8
農場経営問題 制約条件
制約条件
• 土地 (単位acres)
W+(1/3)A+0.05B≦1,200
• 灌漑用水 (単位acre feet)
1.5W+(2.5/3)A+0.1B≦2,000
• alfalfa (単位tons)
Aー4B+AbーAs=0
• 非負条件
W, A, B, Ab, As ≧ 0
9
生産計画問題の定式化
線形計画問題
• (決定)変数(決めること)
– 製品1の生産量
– 製品2の生産量
x1
x2
• 最大化 z =2 x1 + 3 x 2 (目的関数:利益)
• 制約(条件) x1 + 2 x 2 ≦ 14 (鉄鋼)
x1 + x 2 ≦ 8 (電力)
3 x1 + x 2 ≦ 18 (労働力)
x1、x2≧0
10
生産計画問題の幾何的表現
x2
z=一定
0
x1
生産計画問題: スラック変数の導入
• 最大化 z =2 x1 + 3 x 2 (利益)
• 制約
x1 + 2 x 2 ≦ 14 (鉄鋼)
x1 + x 2 ≦ 8 (電力)
3 x1 + x 2 ≦ 18 (労働力)
x1、x2≧0
• 最大化 z =2 x1 + 3 x 2 (利益)
• 制約
x1 + 2 x 2+x3
= 14 (鉄)
x1 + x 2 +x4 = 8 (電)
3 x1 + x 2
+x5 =18 (労)
x1、x2、x3、x4、x5≧0
11
生産計画: 連立方程式の非負解
z ー2 x1 ー 3 x 2
=0 (利益)
x1 + 2 x 2 +x3
= 14 (鉄)
x1 + x 2
+x4 = 8 (電)
3 x1 + x 2
+x5 =18 (労)
x1、x2、x3、x4、x5≧0
上の連立方程式からすぐに読み取れる解
x=(x1,x2,x3,x4,x5)=(0,0,14,8,18),z=0
• 実行可能解: 非負条件を満たす解
• 実行可能基底解: 「一切の計算なしに連立
方程式から読み取れる実行可能解」
12
生産計画: 最適性の判定
z ー2 x1 ー 3 x 2
=0 (利益)
x1 + 2 x 2 +x3
= 14 (鉄)
x1 + x 2
+x4 = 8 (電)
3 x1 + x 2
+x5 =18 (労)
• x1=x2=0とすると、x=(0,0,14,8,18),
z=0; この解は最適か?
• これ以外の解はx1,x2の少なくとも一方が正
• 一方を0に固定して他方を正にしよう; x1,x2
のどっち?; そのとき解は改善するか?
• (選択された変数を)どこまで増やせるか?
13
生産計画: 連立方程式の等価変換1
z ー2 x1 ー 3 x 2
=0 (利益)
x1 + 2 x 2 +x3
= 14 (鉄)
x1 + x 2
+x4 = 8 (電)
3 x1 + x 2
+x5 =18 (労)
z ー 2 x1 ー 3 x 2
=0 (利益)
(1/2)x1 + x 2+(1/2)x3
= 7 (鉄)
x1 + x 2
+x4 = 8 (電)
3 x1 + x 2
+x5 =18 (労)
14
生産計画: 連立方程式の等価変換2
z ー2 x1 ー 3 x 2
=0 (利益)
(1/2)x1 + x 2+(1/2)x3
= 7 (鉄)
x1 + x 2
+x4 = 8 (電)
3 x1 + x 2
+x5 =18 (労)
x 2=7-(1/2)x1ー(1/2)x3
z ー 2 x1 ー 3 x 2
=0 (利益)
(1/2)x1 + x 2+(1/2)x3
= 7 (鉄)
(1/2)x1
ー(1/2)x3 +x4 = 1 (電)
3 x1 + x 2
+x5 =18 (労)
15
生産計画: 連立方程式の等価変換3
z ー2 x1 ー 3 x 2
=0 (利益)
(1/2)x1 + x 2+(1/2)x3
= 7 (鉄)
(1/2)x1
ー(1/2)x3 +x4 = 1 (電)
3 x1 + x 2
+x5 =18 (労)
x 2=7-(1/2)x1ー(1/2)x3
z ー2 x1 ー 3 x 2
=0 (利益)
(1/2)x1 + x 2+(1/2)x3
= 7 (鉄)
(1/2)x1
ー(1/2)x3 +x4 = 1 (電)
(5/2) x1
ー(1/2)x3 +x5=11 (労)
16
生産計画: 連立方程式の等価変換4
z ー 2 x1 ー 3 x 2
=0 (利益)
(1/2)x1 + x 2+(1/2)x3
= 7 (鉄)
(1/2)x1
ー(1/2)x3 +x4 = 1 (電)
(5/2) x1
ー(1/2)x3 +x5=11 (労)
x 2=7-(1/2)x1ー(1/2)x3
z ー (1/2)x1
+(3/2)x3
=21 (利益)
(1/2)x1 + x 2+(1/2)x3
= 7 (鉄)
(1/2)x1
ー(1/2)x3 +x4 = 1 (電)
(5/2) x1
ー(1/2)x3 +x5=11 (労)
x=(x1,x2,x3,x4,x5)=(0,7,0,1,11),z=21
17
18
生産計画問題の幾何学的表現
労働力
x2
z=一定
鉄鋼
電力
0
x1
生産計画: 解の改善
z ー (1/2)x1
+(3/2)x3
=21 (利益)
(1/2)x1 + x 2+(1/2)x3
= 7 (鉄)
(1/2)x1
ー(1/2)x3 +x4 = 1 (電)
(5/2) x1
ー(1/2)x3 +x5=11 (労)
x=(x1,x2,x3,x4,x5)=(0,7,0,1,11),z=21
•
•
•
•
•
この実行可能基底解は最適か?
x1=x3=0だと、この解しかない
この解以外では、少なくともx1,x3の一方が正
x1,x3のどちらを0から増やす?
どこまで増やせるか?
19
生産計画: 解の改善
20
z ー (1/2)x1
+(3/2)x3
=21 (利益)
(1/2)x1 + x 2+(1/2)x3
= 7 (鉄) 14
(1/2)x1
ー(1/2)x3 +x4 = 1 (電) 2
(5/2) x1
ー(1/2)x3 +x5=11 (労) 22/5
• (x3を0に固定して)x1をどこまで増やせるか?
z ー (1/2)x1
+(3/2)x3
=21 (利益)
(1/2)x1 + x 2+(1/2)x3
= 7 (鉄)
x1
ー
x3 +2x4 = 2 (電)
(5/2) x1
ー(1/2)x3 +x5=11 (労)
x1 = 2 + x3 ー2x4
21
生産計画問題の幾何学的表現
労働力
x2
z=一定
鉄鋼
電力
0
x1
生産計画: 最適解
22
z ー (1/2)x1
+(3/2)x3
=21 (利益)
(1/2)x1 + x 2+(1/2)x3
= 7 (鉄) 14
x1
ー
x3 +2x4 = 2 (電) 2
(5/2) x1
ー(1/2)x3 +x5=11 (労) 22/5
z
x1
x2
+x3+ x4
=22 (利益)
+x3 ー x4
= 6 (鉄)
― x3 +2x4
= 2 (電)
2x3 ー5 x4 +x5=11 (労)
23
単体表 No.0
z ー2 x1 ー 3 x 2
=0 (利益)
x1 + 2 x 2 +x3
= 14 (鉄)
x1 + x 2
+x4 = 8 (電)
3 x1 + x 2
+x5 =18 (労)
軸の列
z x1 x2 x3
-3 0
軸 1 -2 0
の 0
1 12 1
行
0
1 01 0
3 01 0
0
x4
0
0
1
0
軸
x5 定数項
0 0
0 14
0 8
1 18
基底変数
比
z
x3
x4
x5
No.0
14/7
8/1
18/1
等価変換=軸演算(掃き出し演算)
目標: 軸の列を、軸の要素を1とする単位
ベクトルにする
新(軸の行) ← 旧(軸の行)÷軸の要素
新(軸以外の行) ←
旧(軸以外の行)+定数*軸の行
25
単体表 No.1
z ー (1/2)x1
+(3/2)x3
=21 (利益)
(1/2)x1 + x 2+(1/2)x3
= 7 (鉄)
(1/2)x1
ー(1/2)x3 +x4 = 1 (電)
(5/2) x1
ー(1/2)x3 +x5=11 (労)
z
1
0
0
0
x1
-1/2
1/2
1/2
5/2
x2
0
1
0
0
x3
3/2
1/2
-1/2
-1/2
x4
0
0
1
0
x5 定数項
0 0
0 7
0 1
1 11
基底変数
比
z
x2
x4
x5
No.1
14
2
22/5
単体表 No.2
z
1
0
0
0
z
1
0
0
0
x1
-1/2
1/2
1/2
5/2
x2
0
1
0
0
x3
3/2
1/2
-1/2
-1/2
26
x4
0
0
1
0
x5 定数項
0 21
0 7
0 1
1 11
基底変数
比
z
x2
x4
x5
No.1
14
2
22/5
x1 x2 x3 x4
0 0 1 1
0 1 1 -1
1 0 -1 2
0 0 2 -5
x5 定数項
0 22
0 6
0 2
1 6
基底変数
比
z
x2
x1
x5
No.2
最適解
基底解(Basic Solution)
27
• 基底解 = m(3)本の制約条件(非負条件を除
く)、n (5)個の変数(スラック変数を含む)からな
る連立方程式の解で、適当なn-m (2)個の変数
を0に固定し、残りのm (3)個の変数で連立方程
式を解いて得られた解 (緑は生産計画問題の場合)
• 問題の制約条件がすべて不等式制約の場合、
不等式制約や非負制約を定める直線・平面等
の交点として定まる点 (「生産計画問題」の場合全部で
10個)が、幾何学的には基底解に対応
• 基底解の中には、値が負となる変数が出て、制
約条件を満足しない実行不可能基底解も存在
可能基底解と可能基底形式
29
(basic feasible solution; b.f.s.)
• 可能基底解=非負条件を満足する基底解、すな
わち、実行可能な基底解; 実行可能領域の端点
(または頂点)に対応
• 可能基底形式=一切の計算をせずに可能基底解
が読み取れる形で表示された連立方程式
• 可能基底形式(単体表)は、以下の条件を満たす:
1)基底変数に対応する列は単位ベクトル
2)基底変数の目的関数の係数は0
3)右辺定数は非負
30
単体法の基本手順
• ステップ0 初期可能基底解を見つけ、ステップ1
へ。
• ステップ1 可能基底解は最適か?(最適性の判
定)最適でなければ、ステップ2へ。(新たに基底
変数となる変数の決定;軸の列の決定)
• ステップ2 基底から追い出される変数の決定(=
軸の行の決定)と無限解(unbounded solution)の
存在判定を行い、無限解でなければステップ3へ。
• ステップ3 可能基底解を更新(軸演算、掃き出し
演算)し、ステップ1へ。
軸演算(掃き出し演算):計算
31
• 「軸の列」に関しては、軸の要素を1とする単位
ベクトルになるような等価変換を行いたい
• 等価変換で許される演算は、以下の2種類:
(a)軸の行に関しては、行を軸要素の値で割る
(b)軸の行以外の行に関しては、当該行から軸
の行の定数倍を引いたり、当該行に軸の行の
定数倍を加える
(a)[新(軸の行)]←[旧(軸の行)]/軸要素
(b)[新(当該行)]←[旧(当該行)]-定数*[旧(軸の行)]
(ただし、当該行≠軸の行)
32
単体法計算のチェックリスト
• 右辺定数(目的関数値を除く)が非負か?
(右辺定数が負はおかしい)
• 単位行列が隠れている
• 目的関数値が改善されている
– 基底変数の値が0の行が軸の行に選ばれな
ければ,すなわち,基底解が「退化」(後で解
説予定)していなければ,目的関数値は単調
に改善していくはず)
単体法の幾何的解釈
33
x2
z=
一定
• 実行可能領域 =
凸多面体(Convex Polytope) 0
• 実行可能領域の端点(または頂点)
→ 実行可能基底解(bfs)に対応
• 実行可能領域の端点のいずれかに
線形計画問題の最適解が存在
• 単体法(Simplex Algorithm) =
実行可能領域の隣接する端点を
改善方向に動いていく
x1
35
初期単体表が作れないとき
どうすればよいか?
Key Words:
二段階単体法、PhaseⅠ、人工変数
初期可能基底解が自明な場合
最大化 z=-3x1 +x3
制約 x1+x2+x3+x4≦4
ー2x1+x2-x3
≦1
3x2+x3+x4≦9
xj ≧0(j=1,2,3,4)
1)各制約式に非負スラック変数を入れて等
式化 たとえば、xj ≧0(j=5,6,7)
2)スラック変数を初期基底変数として初期単
体表(=初期可能基底解)を作成
36
37
初期可能基底解が自明でない
問題の解き方
最大化 z=-3x1 +x3
制約 x1+x2+x3+x4=4
ー2x1+x2-x3
=1
3x2+x3+x4=9
xj ≧0(j=1,2,3,4)
38
非負人工変数
(Artificial Variables)の導入
最小化 z1=x5 +x6 +x7(人工変数の総和)
制約 x1+x2+x3+x4 +x5
=4
ー2x1+x2-x3
+x6 =1
3x2+x3+x4
+x7=9
xj ≧0(j=1,2,3,4),x5 ,x6,x7 ≧0
39
第1段階(Phase I)
線形計画問題の実行可能性の判定
z1
ーx5ーx6ーx7 =0(人工変数総和)
x1+x2+x3+x4 +x5
=4
ー2x1+x2-x3
+x 6
=1
3x2+x3+x4
+x7 =9
xj ≧0(j=1,2,3,4),x5 ,x6,x7 ≧0
40
第1段階(Phase I)
「単体表」への等価変換
基底変数
z1
ーx1+5x2+x3+2x4
=14
x1+x2+x3+x4 +x5
=4
ー2x1+x2-x3
+x6 =1
3x2+x3+x4
+x7=9
xj ≧0(j=1,2,3,4),x5 ,x6,x7 ≧0
z1
x5
x6
x7
42
PhaseⅠ成功(z1の最適値が0)
→ 元のLPが実行可能
• 第1段階の線形計画問題の最適目的関数
値(z1の最適値)が0ならば、元のLP問題
は実行可能
• 元の問題の実行可能基底解が(原則とし
て)求まる(どうやって?)
• 第1段階の線形計画問題の最適目的関数
値(z1の最適値)が正ならば、元のLP問題
は実行不可能
43
所与のLPの実行可
能性は、そのLPの
Phase Ⅰ問題(これも
またLP)を解けば判定
できる!
44
非負人工変数
(Artificial Variables)の導入
最小化 z1=x5 +x6 +x7(人工変数の総和)
最大化
z =-3x1 +x3 (元の目的関数)
制約 x1+x2+x3+x4 +x5
=4
ー2x1+x2-x3
+x6 =1
3x2+x3+x4
+x7=9
xj ≧0(j=1,2,3,4),x5 ,x6,x7 ≧0
第1段階(Phase I)
線形計画問題の実行可能性の判定
z1
ーx5ーx6ーx7 =0(人工変数総和)
z +3x1
ーx3
=0(元の目的関数)
x1+x2+x3+x4 +x5
=4
ー2x1+x2-x3
+x6 =1
3x2+x3+x4
+x7=9
xj ≧0(j=1,2,3,4),x5 ,x6,x7 ≧0
z1
ーx5ーx6ーx7 =0(人工変数総和)
z +3x1
ーx3
=0(元の目的関数)
x1+x2+x3+x4 +x5
=4
ー2x1+x2-x3
+x6 =1
3x2+x3+x4
+x7=9
xj ≧0(
,x7 ≧0
5 ,x6x7
z1 z x1
x2 j=1,2,3,4),
x3 x4 x5 xx6
定数 基底 比
1
0
0
1
0
0
0
0
0
0
0
3
1
0
0
-2
1
3
0
1
0
-1
1
0
0
-1 -1 -1
0 0 0
0
0
z1 No.0
z
-
1
1
0
0
4
x5
-1
0
1
0
0
1
0
0
1
1
9
x6
x7
1
基底変数
z1
ーx1+5x2+x3+2x4
=14 z1
z +3x1
ーx3
=0 z
x1+x2+x3+x4 +x5
=4 x5
ー2x1+x2-x3
+x6 =1 x6
3x2+x3+x4
+x7=9 x7
=1,2,3,4),
,x7定数
≧0 基底 比
z1 z x1xj ≧0(
x2 jx3
x4 x5 xx65 ,x6x7
1
0
0
1
-1
3
5
0
1
-1
2
0
0
0
0
0
0
0
14
0
z1 No.0
z
-
0
0
1
1
1
1
1
0
0
4
x5
4
0
0
0
0
-2
0
1
3
-1
1
0
1
0
0
1
0
0
1
1
9
x6
x7
1
3
↓
基底変数
z1 + 9x1+ 6x3+2x4 ー 5x6
=9 z1
z + 3x1
ー x3
=0 z
3x1+ 2x3+ x4 +x5 ーx6 =3 x5
ー2x1+x2-x3
+x6
=1 x2
6x1+ 4x3+ x4 ー 3x6 +x7=6 x7
z1 z xx1
x2j=1,2,3,4),
x3 x4 x5x5x6
定数 基底 比
,x6,xx77 ≧0
j ≧0(
1
0
0
1
9
3
0
0
6
-1
2
0
0
0
-5
0
0
0
9
0
z1 No.1
z
-
0
0
3
0
2
1
1
-1
0
3
x5
0
0
0
0
-2
6
1
0
-1
4
0
1
0
0
1
-3
0
1
1
6
1
x2 ∞
まだ続く
x7
1
49
所与のLPの実行可
能性は、そのLPの
Phase Ⅰ問題(これも
またLP)を解けば判定
できる!
ダウンロード

(1/2)x 1 ー