2012MP 02 最近の更新履歴 小野 廣隆 (Hirotaka Ono)

担当： 経済 学部門 ^廣隆 [email protected]

1

 9/28 数理計画問題

◦ ^{数理計画問題} 例

◦ ^{代表的 数理計画問題 型}

 _10/10

◦ ^{数理計画問題} (続 )

 ^{代表的 数理計画問題} 型

◦ 線形計画問題1回目

 10/17 線形計画2回目



数理計画問題 _{(続 )}

◦ ^{代表的 数理計画問題} 型



_{線形計画法}

◦ 不等式標準系 等式標準系

3

 問題 数式 使 数学的 表現 定式化)

 定式化さ 問題 ア _適用

答え 求

 こ 授業 _目標：

◦ ^{数理計画問題 型 理解}

◦ 代表的 数理計画問題 知

◦ 代表的 数理計画問題 対 解法 ア

 ^{型 数理計画問題 解くこ 出来}

ア 存在

例 ：

 最大化 2x + 2y + 3 z

 条件 5x + 3 z ҇ 8 2 z ҇ 2

4y + z ҇ 9 x, y, z ҈ 0

例 ：

 最 化 2x + 2y 条件 x y ҈ 1 x, y ҈ 0

線形

等式、不等式

表現さ _い

非線形 式

使わ _い

線形計画問題

非線形計画問題

例 _変種：

 最大化 2x + 2y + 3 z

 条件 5x + 3 z ҇ 8 2 z ҇ 2

4y + z ҇ 9 x, y, z ҈ 0

^{x,y,z 整数}

整数 _{線形 計画問題}

変数 整数制約 付加さ

例 ：

 最大化 2x + 2y + 3 z

 条件 5x + 3 z ҇ 8 2 z ҇ 2

4y + z ҇ 9 x, y, z ҈ 0

目的関数：

最 化

最大化さ _関数

制約式_：問題

中 _条件式

最大化 x + y

条件 x² + y² ҇ 1 x, y ҈ 0

最適解_：

目的関数 最大

最 許

容解関数

最適値_： 際 目的関数値

許容解領域

実行可能領域 ： 許容解

集 許容解 実行可能解 ：

制約式 満

ベク _{(x, y)} ^C

C



 





2 , 1 2 1

 ナッ ック _込

500ｇ 10ｋｇ ｋｇ ｋｇ 10万 15万 5千 1万

 ナッ ック 制限 ｋｇ 越え _い

 総価値 最大 _い

 ナッ ック _込

500ｇ 10ｋｇ ｋｇ ｋｇ 10万 15万 5千 1万

各変数 ^{品物 ナッ ック 入}

否 表 (w=1 ^{指輪 ナッ ック 入}

w ^{x y z}

最大化 10w + 15x + 0.5y + z

条件 0.5w + 10x + y + 5z ҇ 10 w, x, y, z ^{0 1}

選 アイ

総価値

選 アイ

総

 各研究室 学生一人 割 当

 学生 満足度 _合計

最大 _い

満足度

10 7 3 9

6 5

4 ³ 1

S

T

U A

C B

 ポ _：

株式 金融資産 組 合わ

 投資家 最 満足 投資方法 求 _い

 あ 投資家 _資産

 _1ヶ月後 資産 _期待値：

m円

○○株式会社

株式会社△ △

××商 x₁円

x₂円 x₃円

現在 _価格pi 来月 _価格Qi

確率変数



 x_iQ_i p_i

M /

 来月 _{資産M 対} 満足度：U(M) = M _βM²

 _U(M) 期待値 最大 _い

Ax x

x r x

r M

U

E ^T

i

i i i

i

i ^{ }



_

_

)] (

[ 

m x

i

i ^



制約

 0 xi

 実験 _{(xi, yi) (i} = 1, 2, …, n) 得

 直線y = ax + b 近似 い

)2

( _i

n

i

i ^{b y}

ax  



|

| ax_i  b  y_i

点 直線 _誤差

点 直線 誤差 乗和

最 い

最 化

 いく 代表的 数理計画問題 _紹介

◦ 線形計画問題

◦ 非線形計画問題

 ^{次計画問題 ポ 問題、最} 乗問題

◦ ^組合 最適化問題

 ^{整数計画問題 ナッ} ック問題

 未紹介 _問題

◦ ^{線形計画問題} 特殊例

 輸送問題

 ネッ ワ ク計画 最短路問題、最大流、最少費用流問題

15

 教科書第1章 演習問題(1.6節

◦ 問題1.1, 1.2, 1.3

16

 線形計画問題 _標準形

 _{基底解 最適解}

 シン _{ック 法}

 シン ック

 _双対性

 _感度解析



17

 線形計画問題 Linear Programming,^ＬＰ 定義

 目的関数 線形関数 制約式 線形式 _{最適化問題}

 最大化 2x + 2y + 3 z

 条件 5x + 3 z ҇ 8 2 z ҇ 2 4y + z ⁹ x, y, z ҈ 0

18

制約式

҈ _҇

い 目的 _最大化

最 _化 い

 目的： 最大化、最 化 ^い

 _{制約： ҈ ҇} い _い

 _あ い 、焦点 絞 _くい

 や さ 、典型的 型

標準形 定 進

◦ 不等式標準形

◦ 等式標準形

 保証 _等価性

19

 _{う LP} 等価 不等式標準形 変換可能

 _{不等式標準形}

◦ ^{目的 最 化}

◦ ^{制約式 辺҈右辺｣} 形

◦ ^各変数 非負

 最 _{化 c1 x1 +c2 x2 + +cn xn}

 _{条件 a11 x1 +a12 x2 + +a1n xn҈b1}

a21 ^x1 ^+a22 ^x2 ^{+ +a}2n ^xn^҈b2

am1 ^x1 ^+am2 ^x2 ^{+ +a}mn ^xn^҈bm

x1^{҈0, x}2^{҈0, …, x}n^҈0

20

 命題：任意 ＬＰ 等価 不等式標準形 変換

 次 _{変換法 利用}

式 同値変形 等式 _{不等式 表現}

目的関数 倍 最大化 最 _化

最大化 最 化

21



j

j

j^{x b}

a

_

_

j

j j n

j

j

j^{x b a x b}

a ,



j

j j^x

c ^

_

n

j

j j^x

c

 制約 倍 不等式 _{҇ ҈}

 差 _表現

非負制約 い変数 _{非負変数 表現}

xj ^非負制約

x_j = x_{j1 –xj2} , x_j1҈0, x_j2҈0

22



j

j

j^{x b}

a 

_

j

j

j^{x b}

a

23

最大化 _{3x + 2y} 条件 x + y = 1 x ҈0

最大化 _{3x + 2(y1 y2)} 条件 x + (y₁ y₂) = 1 x ҈0

y₁ ҈0, y₂ ҈0

最 化 _{- 3x - 2(y1 - y2)} 条件 x + (y₁ - y₂) = 1 x ҈0 y1 ^{҈0, y}2 ^҈0

最 化 _{3x 2(y1 y2)} 条件 _{- x - (y1 - y2) ҈ - 1} x + (y₁ - y₂) ҈ 1

y₁ ҈0, y₂ ҈0

 差 _表現

x_j 非負制約 x_j = x_{j1 –xj2} , x_j1҈0, x_j2҈0 変換前 問題：P1 ^変換後 問題：P2

 _{P1 P2} 本質的 等価

 _{(s1 , ..., sj, ..., sn )：P1 許容解}

(s₁ , ..., s_{j1 –sj2} , ..., s_n )：

P2 許容解 目的関数値同 ,

sj1 ^{= s}j ^{, s}j2 ^{= 0 s}j ^҈0

sj1 ^{= 0, s}j2 ^{= s}j ^sj ^{< 0}

24

 _{(t1 , ..., tj1 , tj2 , ..., tn )：P2 許容解}

(t₁ , ..., t_{j1 –tj2} , ..., t_n )：P1 許容解 目的関数値同

25

 _{LP 等式標準形}

◦ ^{目的 最} 化

◦ ^制約 等式

◦ ^各変数 非負

 最 _{化 c1 x1 +c2 x2 + +cn xn}

 _{条件 a11 x1 +a12 x2 + +a1n xn b1}

a21 ^x1 ^+a22 ^x2 ^{+ +a}2n ^xn ^b2

am1 ^x1 ^+am2 ^x2 ^{+ +a}mn ^xn ^bm

x1^{҈0, x}2^{҈0, …, x}n^҈0



26



命題：任意 ＬＰ 等式標準形 変換

 任意 ＬＰ 不等式標準形 変換 命題 ₁

 不等式 辺҈右辺 等式

 _{新 い非負変数 yi 入(} ック変数₎

27



j

i j

ij^{x b}

a a_ijx_{j -} y_{i =} b_i

j

å

4x_{1 –3x2} + x_{3 –y1} = -1

x₁҈0, x₂҈0, x₃҈0, y₁҈0 4x_{1 –3x2} + x₃ ҈-1

x₁҈0, x₂҈0, x_3҈0

 教科書第1章 演習問題(2.10節

◦ 問題2.1

28