＜最適化の概念＞ 最適化すべき問 題 数学モデル 変数，数式 数理計画法 定められた計算手 順を用いて解くた めの方法論.

Presentation on theme: "＜最適化の概念＞ 最適化すべき問 題 数学モデル 変数，数式 数理計画法 定められた計算手 順を用いて解くた めの方法論."— Presentation transcript:

1 ＜最適化の概念＞ 最適化すべき問 題 数学モデル 変数，数式 数理計画法 定められた計算手 順を用いて解くた めの方法論

2 ＜数理計画＞ 対象とする数理モデルが現 実のどのような問題を定式 化したものであるかにかか わらず、数学的構造がおな じであれば共通の方法が適 用できる。

3 ＜数理計画モデル＞ ・線形計画問題 ・ネットワーク計画問題 ・非線形計画問題 ・組合せ計画問題

4 線形計画モデル < 生産計画問題＞ ４種類の原料Ａ，Ｂ，Ｃ，Ｄを用いて、３種 類の製品 I,II,III を生産している工場が、最大 の利益をあげるにはどのような生産計画をた てればよいか。 変数：各製品 I,II,III の生産量 x 1, x 2, x 3

5 製品を１単位生産するごとに得られる利 益 製品 I,II,III ： 70 万円、 120 万円、 30 万円 各製品を x 1, x 2, x 3 単位づつ生産したと きの総利益 70x 1 ＋ 120x 2 ＋ 30x 3 （万 円） 最大化 目的関数

6 I II III A 5 0 6 B 0 2 8 C 7 0 15 D 3 11 0 生産計画問題のデー タ 原料の利用可能量 A ： 80 単 位 B ： 50 単位 C ： 100 単 位 D ： 70 単 位 5x 1 ＋ 6x 3 ≦ 80 2x 2 ＋ 8x 3 ≦ 50 7x 1 ＋ 15x 3 ≦ 100 3x 1 ＋ 11x 2 ≦ 70 x 1 ≧ 0, x 2 ≧ 0, x 3 ≧ 0 制約条件

7 目的関数： 70x 1 ＋ 120x 2 ＋ 30x 3 最 大 < 線形計画問題＞ 制約条件： 5x 1 ＋ 6x 3 ≦ 80 2x 2 ＋ 8x 3 ≦ 50 7x 1 ＋ 15x 3 ≦ 100 3x 1 ＋ 11x 2 ≦ 70 x 1 ≧ 0, x 2 ≧ 0, x 3 ≧ 0

8 x = x1x1 x2x2 x3x3 A = 5 0 6 0 2 8 7 0 15 3 11 0 b = 80 50 100 70 c = 70 120 30 目的関数： c T x 最大 制約条件： Ax ≦ b, x ≧ 0

9 数理計画法 目的関数： ｆ（ｘ）＝ｆ（ｘ 1, ｘ 2 ・・・ｘ n ） －＞最小化 制約条件： ｇ 1 （ｘ）≦０ ｇ 2 （ｘ）≦０ ・・・・・・ ｇ m （ｘ）≦０ ｆ（ｘ），ｇｉ（ｘ）が線 形（一次式） －＞線形計画問題 ｆ（ｘ）またはｇｉ（ｘ） が非線形 －＞非線形計画問題 変数 ｘ ＝（ｘ 1 ，ｘ 2 ，・ ・・ｘ n ） の値が整数値（離散量） －＞整数計画問題 （離散的最適化問題 組合せ最適化問題）

10 線形計画問題 目的関数： c T x 最小 制約条件： Ax ＝ b, x ≧ 0 ＜標準形＞ いくつかの１次不等式や等式で表 される制約条件のもとで，１次関数 を最大あるいは最小にする問題．

11 目的関数： － 2x 1 ＋ 5x 2 最大 制約条件： 4x 1 － 6x 2 ＝ 30 2x 1 ＋ 8x 2 ≦ 50 7x 1 ＋ 5x 2 ≧ 10 x 1 ≧ 0, x 2 は符号制約なし

12 ＜標準形との相違点＞ （１）目的関数を最大化 （２）変数 x 2 には符号の制約がない （３）２番目と３番目の制約条件が不 等式 （１）目的関数に－１を掛ける （２） x 2 ＝ x’ 2 － x” 2, x’ 2 ≧ 0, x” 2 ≧ 0 （３）新しい非負変数 x 4, x 5 を導入（スラッ ク変数）

13 目的関数： 2x 1 － 5x 2 ＋ 5x 3 最小 制約条件： 4x 1 － 6x 2 ＋ 6x 3 ＝ 30 2x 1 ＋ 8x 2 － 8x 3 ＋ x 4 ＝ 50 7x 1 ＋ 5x 2 － 5x 3 － x 5 ＝ 10 x 1 ≧ 0, x 2 ≧ 0, x 3 ≧ 0, x 4 ≧ 0, x 5 ≧ 0

14 目的関数： － x 1 － x 2 最小 制約条件： 3x 1 ＋ 2x 2 ≦ 12 x 1 ＋ 2x 2 ≦ 8 x 1 ≧ 0, x 2 ≧ 0 基底解と最適解

15 2 4 6 2 46 x 1 + 2 x 2 = 8 0 x1x1 x2x2 最適解 810 3x 1 + 2 x 2 = 12 実行可能領域 目的関数の等高線 － x 1 － x 2 = － ｚ

16 ＜２変数の線形計画問題＞ 実行可能領域：平面上の凸多角形 目的関数の等高線：平行な直 線 最適解：凸多角形の境界上に存在 ＜一般の線形計画問題＞ 実行可能領域：空間 R n 上の凸多面体 最適解：凸多面体の頂点のなかに存 在 シンプレックス法（単体法）： G.B.Dantzig (1947)

17 目的関数： － x 1 － x 2 最小 制約条件： 3x 1 ＋ 2x 2 ＋ x 3 ＝ 12 x 1 ＋ 2x 2 ＋ x 4 ＝ 8 x 1 ≧ 0, x 2 ≧ 0, x 3 ≧ 0, x 4 ≧ 0 ＜標準形＞

18 ２つの変数を適当に選んでそれらを０と おけば、残りの２つの変数は一意的に定 まる。 基底解 基底解のうち x ≧ 0 を満たすもの 実行可能基底解 基底解を定める際に 0 とおいた変 数 非基底変数 x N それ以外の変数 基底変数 x B

19 (a) x = (2,3,0,0) T ：基底変数 x B = (x 1,x 2 ) T ， 非基底変数 x N = (x 3,x 4 ) T (b) x = (8,0,-12,0) T ： x B = (x 1,x 3 ) T ， x N = (x 2,x 4 ) T (c) x = (4,0,0,4) T ： x B = (x 1,x 4 ) T ， x N = (x 2,x 3 ) T (d) x = (0,4,4,0) T ： x B = (x 2,x 3 ) T ， x N = (x 1,x 4 ) T (e) x = (0,6,0,-4) T ： x B = (x 2,x 4 ) T ， x N = (x 1,x 3 ) T (f) x = (0,0,12,8) T ： x B = (x 3,x 4 ) T ， x N = (x 1,x 2 ) T

20 2 4 6 2 46 0 x1x1 x2x2 810 (a) (c)(b) (e) (d) (f) x 3 =0 x 4 =0 x 2 =0 x 1 =0 基底解と実行可能基底 解

21 ＜一般の標準形問題の制約条件＞ Ax ＝ b, x ≧ 0 A ： m×n 行列 m ＜ n かつ rank A = m とする 変数 n 個，基底変数 m 個，非基底変数 n － m 個 x B ： m 次元基底変数ベクト ル x N ： (n － m) 次元非基底変数ベクト ル

22 行列 A の n 本の列を，基底変数に対応す る m 本の列と非基底変数に対応する n － m 本の列に分割する． 基底変数に対応する m×n 行列 Ｂ： 基底行列 非基底変数に対応する m×(n － m) 行列 N ： 非基底行列 A ＝ (B, N)

23 A ＝ (B, N) とする。 Ax ＝bAx ＝b Bx B + Nx N ＝ b B が正則ならば ，非基底変数の値を０と おくことにより ，基底解が得られる． x B ＝ B －１ b ， x N ＝ 0 B －１ b ≧ 0 のとき，実行可能基底解

24 実行可能 基底解 実行可能領域 （凸多面体）の頂 点 対応 １組の基底変数と非 基底変数の入れ替え １つの頂点から隣 り合う別の頂点に 移動 ピボット操 作

25 ＜最適性の判定＞ A ＝ (B, N) Ax ＝bAx ＝b Bx B + Nx N ＝ b x B ＝ B －１ ( b － Nx N ) Bx B ＝ b － Nx N x B ＝ B －１ b － B －１ Nx N

26 目的関数に代入 c T x ＝ c T B x B + c T N x N x B ＝ B －１ b － B －１ Nx N ＝ c T B ( B －１ b － B －１ Nx N ) + c T N x N ＝ c T B B －１ b + ( c T N － c T B B －１ N ) x N π ＝ (B T ) －１ c B とする（ π ：シンプレックス乗 数） c T N － π T N ＝ c T N － c T B B －１ N ≧ 0 が成り立つならば最適解

27 c T N － π T N ＝ c T N － c T B B －１ N ≧ 0 最適性の判定条件 すべての実行可能解 x N ≧ 0 の中で目的関数 は x N ＝ 0 のとき最小値をとる． c T x ＝ c T B B －１ b ( ＝ π T b ) 実行可能解 （ x B ， x N ）＝（ B －１ b ， 0 ） は最適解

28 例 (a) の実行可能基底解 c B ＝ （ -1 ， -1 ） T ， c N ＝ （ 0 ， 0 ） T π ＝ （ -1/4 ， -1/4 ） T c T N － π T N ＝ （ 0 ， 0 ） T － （ -1/4 ， - 1/4 ） T N ＝ （ 1/4 ， 1/4 ） 最適解 c N － N T π の各要素： x N の相対コスト係 数

29 シンプレックス 法 c T N － π T N ＝ c T N － c T B B －１ N ≧ 0 最適性の条件 が成立していない場合、負の要素が少 なくとも一つ存在する。 x k x B ＝ B －１ b － B －１ a k x k x B ＝ B －１ b － B －１ Nx N x k を増加させれば目的関数の値を減少でき る

30 b ＝ B －１ b ， y ＝ B －１ a k Δ ＝ min {b i ／ y i ｜ y i >0 (i=1,…,m)} 非基底変数 x k を最大 Δ まで増大させても 非負条件 x ≧ 0 は満たされる。 x k の値を Δ まで増やしたとき Δ ＝ b i ／ y i を満たす i に対応する基底変数の値は ０

31 ＜シンプレックス法＞ (0) 初期実行可能基底解（ x B ， x N ）＝（ B －１ b ， 0 ） を選ぶ。 b ＝ B －１ b とおく。 (1) シンプレックス乗数 π ＝ (B T ) －１ c B を計 算 (2) 非基底変数の相対コスト係数 c j － π T a j がすべて０以上なら、最適基底解。計算終 了。 そうでなければ、 c k － π T a k < 0 である非基 底変数 x k を１つ選ぶ。

32 (3) ベクトル y ＝ B －１ a k を計算 (4) ベクトル y に正の要素がなければ、問 題 は有界でない。計算終了。 そうでなければ、 Δ ＝ min {b i ／ y i ｜ y i >0 (i=1,…,m)} (5) 非基底変数の値を Δ 、それ以外の非基 底変数の値を 0 とおく。 x B ＝ b － Δy 非基底変数 x k を基底変数とし、ステップ (4) で求めた i に対応する基底変数を非基底 変数とする。ステップ (1) に戻る。

33 シンプレックス・タ ブロー -1 -1 0 0 0 3 2 1 0 12 1 2 0 1 8 相対コスト係数 c T N － π T N= c T N － c T B B －１ N B －１ A B －１ b － ( 目的関数値 ) x3x3 x4x4 ＝－ c T B B －１ b

34 0 -1/3 1/3 0 4 1 2/3 1/3 0 4 0 4/3 -1/3 1 4 x1x1 x4x4 0 0 1/4 1/4 5 1 0 1/2 -1/2 2 0 1 -1/4 3/4 3 x1x1 x2x2

35 双対性 目的関数： c T x 最 小 制約条件： Ax ＝ b, x ≧ 0 目的関数： b T w 最 大 制約条件： A T w ≦ c ＜主問題＞ ＜双対問題＞

36 目的関数： c T x 最 小 制約条件： Ax ≧ b, x ≧ 0 目的関数： b T w 最 大 制約条件： A T w ≦ c, w ≧ 0 ＜主問題＞ ＜双対問題＞

37 主問題 (primal problem) ： (P) 双対問題 (dual problem) ： (D) (P) と (D) それぞれの任意の実行可能 解 x ， w に対して，常に不等式 c T x ≧ b T w が成り立つ． ＜弱双対定理＞ c T x ≧ ( A T w) T x ＝ w T b Ax ＝ b, x ≧ 0 および A T w ≦ c よ り [ 証明 ]

38 (P) または (D) の一方が最適解をもてば 他方も最適解をもち， (P) の最小値と (D) の最大値は等しい ． ＜双対定理＞ c T x ≧ (D) の最大値 （ x ： (P) の実行可能 解 ) b T w ≦ (P) の最小値 （ x ： (D) の実行可能 解 ) c T x ＝ b T w ならば x ， w は最適 解

39 材料 ビタミン C ビタミン D 値段 R 1 a 11 mg ／ g a 21 mg ／ g c 1 円／ g R 2 a 12 mg ／ g a 22 mg ／ g c 2 円／ g R 3 a 13 mg ／ g a 23 mg ／ g c 3 円／ g ビタミン C ， D を b 1 mg ， b 2 mg 以上含む料 理

40 目的関数： c 1 x 1 ＋ c 2 x 2 ＋ c 3 x 3 最 小 制約条件： a 11 x 1 ＋ a 12 x 2 ＋ a 13 x 3 ≧ b 1 x 1 ≧ 0, x 2 ≧ 0, x 3 ≧ 0 a 21 x 1 ＋ a 22 x 2 ＋ a 23 x 3 ≧ b 2 x j ：材料 R j の量

41 ビタミン C ， D の１ mg あたりの価格： w 1 円,w 2 円 目的関数： b 1 w 1 ＋ b 2 w 2 最大 制約条件： a 11 w 1 ＋ a 21 w 2 ≦ c 1 w 1 ≧ 0, w 2 ≧ 0 a 12 w 1 ＋ a 22 w 2 ≦ c 2 a 13 w 1 ＋ a 23 w 2 ≦ c 3 双対問題の最適解 w * ：主問題の潜在価格 （シャドウ・プラ イス）

42 多項式時間アルゴリズ ム シンプレックス法の反復回 数： 制約条件の数の 1.5 倍から 3 倍程 度 多項式時間アルゴリズムではない ＜内点法＞ 多項式時間アルゴリズム 大規模な問題ではシンプレックス法より効 率的