数理計画法 第1回
１．数理計画問題 ２．線形計画
担当： 塩浦昭義
(情報科学研究科 助教授) [email protected]
｢数理計画法｣の授業の目的
z 数理計画問題、およびその解法について学ぶ 使用する教科書
☆田村明久、村松正和著
「最適化法｣、工系数学講座１７巻 共立出版、2002年
☆適宜資料を配布
成績評価の方法および基準
z 中間試験(50点)
z 期末試験(50点）
z 演習レポートの提出状況(20点) により評価
z 60点以上で合格
z 出席点は全く考慮しない
z レポートを一回以上提出した者のみ試験を受ける ことが可能
授業に関する情報のページ
http://www.dais.is.tohoku.ac.jp/~shioura /teaching/mp04/index.html
数理計画問題とは？
z 数理計画問題（≒最適化問題）
与えられた評価尺度に関して 最も良い解を求める問題
例1：飲料会社のジュース生産計画
z 限られた資源を使って最大の収益を得たい
z 資源 − オレンジ、にんじん、トマト
z 生産するジュース
− オレンジ１００、トマト100、ミックス
９ ２
８
最大供給量
３ １
２ ３
ミックス
２ ４
トマト
２ ５
オレンジ
収益 トマト
にんじん オレンジ
種類
例2：長方形の問題
z 面積が１以上の長方形を描く
z 外周の長さを最小にするには？
数理計画問題の解き方
z 問題を数式を使って数学的に表現
（定式化)
z 定式化された問題にアルゴリズムを適用、
答えを求める この授業の内容
数理計画問題を解く様々なアルゴリズムの説明
例1の定式化
z 限られた資源を使って最大の収益を得たい
９ ２
８ 最大供給量
３ １
２ ３
ミックス
２ ４
トマト
２ ５
オレンジ
収益 トマト
にんじん オレンジ
種類
•各ジュースの生産量を変数で表現 ｘ：オレンジ100の生産量 ｙ：トマト100の生産量 ｚ：ミックスの生産量
例1の定式化(続き）
９ ２
８ 最大供給量
３ １
２ ３
ミックス
２ ４
トマト
２ ５
オレンジ
収益 トマト
にんじん オレンジ
種類
最大化 2x + 2y + 3 z 条件 5x + 3 z ≦ 8
2 z ≦ 2 4y + z ≦ 9 x, y, z ≧ 0
収益を最大に 使用できるオレン
ジの量は8以下
各ジュースの 生産量は非負
例2の定式化
z 面積が１以上の長方形を描く
z 外周の長さを最小にするには？
ｘ：縦の長さ
ｙ：横の長さ
最小化 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
例１：
例2：
すべて線形の 等式、不等式で 表現されている
線形計画問題
最小化 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 条件 x2 + y2 ≦1
x, y ≧0
1 1
許容解：制約式 をすべて満たす ベクトル(x, y)
許容解領域：
許容解すべての 集まり
(√2, √2)
最適解：目的 関数を最大 または最小に
する許容解 最適値：
最適解の 目的関数値 資料の「最小化」は
「最大化」の誤り
整数計画の例１：ナップサック問題
z ナップサックにものを詰め込む
z ナップサックの重量制限（１０ｋｇ）を 越えてはならない
z 総価値を最大にしたい
500ｇ 10ｋｇ １ｋｇ ５ｋｇ
10万 15万 5千 1万
整数計画の例１：ナップサック問題
定式化ー各アイテムに変数を割り当て
w x y z
最大化 10w + 15x + 0.5y + z 条件0.5w + 10 x + y + 5 ≦10
w, x, y, z は0 または 1 宝石を選んだらw = 1, 選ばなかったらw = 0
選んだアイテ ムの総価値 選んだア
イテムの 総重量
整数計画の例２：研究室配属
•各研究室に学生一人を 割り当てる
•学生の満足度の合計を 最大にしたい
10 3 7
9 5 6
4 8 1 満足度
A
B
C
S
T
U
整数計画の例２：研究室配属
定式化
学生と先生のペアに変数を 割り当て
xAS, xAT, xAU, xBS, ...
A をS に割当てたらxAS= 1 割り当てなければxAS= 0
10 3 7
9 5 6
4 8 1 満足度
A
B
C
S
T
U 最大化 10xAS+ 7xAT+ 3xAU+ ...
条件xAS+ xAT+ xAU= 1 ...
xAS+ xBS+ xCS= 1 ...
各変数は0 または1
非線形計画の例１：構造設計
2本の鉄パイプ（トラス）で荷重 ２Wを支える
荷重 ２W
幅 2 s
高さx3 パイプ断面
直径x1
厚さx2
•鉄パイプの総重量 (ρは密度）
2 3 2 2
2π ρx1x s +x
→ 最小にしたい
•トラスの高さの制限：x3≤b1
•パイプの厚さの制限： 2
2
1 b
x x ≤
非線形計画の例１：構造設計
•トラスが重みにより変形したまま元に戻らない、
ということにならないための条件：
3 2 1 3 2 3
2 x b xx x
s
W + ≤
•パイプが折れ曲がらないための条件：
( ) ( 22)
2 1 3 1 4 2 3 2 3
2 x b xx x x
s
W + ≤ +
•非負条件： x1≥0, x2 ≥0, x3 ≥0
非線形計画の例２：
ポートフォリオ選択問題
ポートフォリオ：株式などの金融資産を組み合わせたもの 投資家が最も満足する投資方法を求めたい
ある投資家の資産
3種類の株式に投資
m 円
Yahoo NTT東日本
東芝
それぞれ 現在の価格pi 来月の価格Qi
（確率変数）
x3円 x2円 x1円
1ヵ月後の資産：
3 3 3 2
2 2 1
1 1
p x Q p
x Q p
x
M=Q + + （確率変数）
非線形計画の例２：
ポートフォリオ選択問題
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
−
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
⎟−
⎟⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
=
3 2 1
3 23 13
23 2 12
13 12 1
3 2 1
2
3 2 1
3 2 1
3 2 1
3 2 1
)]
( [
x x x
x x x
x x x
r r r
x x x
r r r M U E
T
T T
σ σ σ
σ σ σ
σ σ σ β
β
来月の資産Mに対する満足度：U(M) = M − βM2 U(M)の期待値を最大にしたい
条件： x1+x2+x3=m, x1,x2,x3 ≥0
riはQi/pi の平均 σij は
(Qi/pi– ri)(Qj/pj– rj) の共分散
２．線形計画
２．１ 線形計画問題とその標準形
最大化 2x + 2y + 3 z 条件 5x + 3 z ≦8
2 z ＝2 4y + z ≧9 x, y ≧0
線形計画問題（ＬＰ）の定義
•目的関数が線形関数，制約式も線形式の最適化問題 目的は「最大化」「最小化」
どちらでもよい
制約式は「≧」「＝」「≦」
どれでもよい 制約式は
「不等号つき」「不等号なし」
どちらでもよい
ＬＰの不等式標準形
任意の形のＬＰを扱う のは面倒
⇒ 不等式標準形
目的は最小化
制約式は「左辺≧右辺｣の形
各変数は非負 最小化 c1x1+c2x2+・・・+cnxn
条件 a11x1+a12x2+・・・+a1nxn≧b1 a21x1+a22x2+・・・+a2nxn≧b2
・・・
am1x1+am2x2+・・・+amnxn≧bm x1≧0, x2≧0, …, xn≧0
次回の予定
z 線形計画
☆線形計画問題とその標準形
☆双対問題
z 教科書を生協で購入しておいてください
