担当: 経済工学部門 小 廣隆 hirotaka@en.kyushu-u.ac.jp
プ ェクタ利用
数理計画問題 主 線形計画法 、
びそ 解法 い 学ぶ
使用 教科書
◦ 福島 夫:数理計画入門
◦ 朝倉書店 (1996/09)
◦ 定価 3360
◦ 旧版(定価3600 税) OK
◦ 生協 購入
数理
線形計画法
問題 解法
最適化問題
計算
フ
演習 兼小 0〜40点く い
◦ 得点調整 利用
◦ 小 行う場合, 11月後半 12月前半く い
定期試験 60〜100点く い
◦ 出席点 考慮 い
◦ 配分 あく 目安
昨年度 評価 方 変え
連絡先
◦ : hirotaka@en.kyushu-u.ac.jp
◦ 居室:経済学部4 号室
質問
◦ 事務的 容
◦ 授業 容 関 基本的 来室 質問
来室 質問
◦ 前日 連絡 無駄 さ
◦ 飛び込 、対応 い 多々あ
9/28 数理計画問題 今回
◦ 数理計画問題 例
◦ 代表的 数理計画問題 型
10/3 ( せ 、い 休講
10/10 線形計画1回目
10/17 線形計画2回目
休講予定:
◦ 12月半 回 2回?
あ 種 数理計画問題 解 う
数理計画問題 例:
問題: 範囲 次 関数 最小値 そ え 値 求
◦ 問題 中学生 小学生? 解
200
100 x
x
1
2
)
( x x
f
問題: 範囲
次 関数 最大値 そ え 値 求
問題 高校生 中学生? 解
4
2
,
4
2
,
0
,
0 x y x y x y
y
x,
y
x
y
x
f ( , ) 2 3
問題:
範囲 次 関数 最大値 そ え 値 求
問題 , 解 方 可能
x
nx
x
, 0 , , 0
0
1 2
,
,
2 2 1
1
1 1
2 12 1
11
m n
mn m
m
n n
b
x
a
x
a
x
a
b
x
a
x
a
x
a
n n
n
c x c x c x
x
x
f (
1,..., )
1 1
2 2
x
nx ,...,
1 先 あ う 問題 限 解 い
= ック 解 い
ック 解く 問題 数学的構 ,数学
的特性 理解 必要 あ
う 問題 解く
解く 場合 く解く
以 取 組 学問分
数理計画
Mathematical Programming
◦ 数理 数学 使 計画 立 問題
◦ え 評価尺度 関 最 良い解 求 問題 最適化問題
限 資源 使 最大 収益 得 い
資源 ン 、 、
生産 ュ
ン % 100% ック
ン 収益
ン 100% 5 2
100% 4 2
ック 3 2 1 3
供給 8 2 9
限 資源 使 最大 収益 得 い
各 ュ 生産 変数 表現
◦ x: ン 100 生産
◦ y: 100 生産
◦ z: ック 生産
ン 収益
ン 5 2
4 2
ック 3 2 1 3
供給 8 2 9
最大化 2x + 2y + 3z
条件 5x + 3z ҇ 8 2z ҇ 2 4y + z ҇ 9 x, y, z ҈ 0
ン 収益
ン 5 2
4 2
ック 3 2 1 3
供給 8 2 9
収益 最大化
各作物 使用 供給 以 各 ュ 生産
非負
面積 以 長方形 描く
外周 長さ 最小 ?
面積 以 長方形 描く
外周 長さ 最小 ?
最小化 2x + 2y 条件 xy ҈ 1 x, y ҈ 0
外周 長さ 最小
面積 以
縦横 長さ 非負
x:縦 長さ
y:横 長さ
問題 数式 使 数学的 表現 定式化)
定式化さ 問題 適用
答え 求
授業 目標:
◦ 数理計画問題 型 理解
◦ 代表的 数理計画問題 知
◦ 代表的 数理計画問題 対 解法
型 数理計画問題 解く 出来 ?
= 存在 ?
例 :
最大化 2x + 2y + 3 z
条件 5x + 3 z ≦ 2 z 2
4y + z ≧ x, y, z 0
例 :
最小化 2x + 2y 条件 x y 1 x, y 0
べ 線形
等式、 等式 表現さ い
非線形 式 使わ い
線形計画問題
非線形計画問題
例 変種:
最大化 2x + 2y + 3 z
条件 5x + 3 z ≦ 2 z 2
4y + z ≧ x, y, z 0 x,y,z 整数
整数 線形 計画問題
変数 整数制約 付加さ
例 :
最大化 2x + 2y + 3 z
条件 5x + 3 z ≦ 2 z 2
4y + z ≧ x, y, z 0
目的関数:
最小化
最大化さ 関数
制約式:問題 中 条件式
最大化 x + y
条件 x2 + y2 1 x, y 0
最適解:
目的関数 最大
最小 許
容解関数
最適値: そ 際 目的関数値
許容解領域
実行可能領域 : 許容解 べ
許容解 実行可能解 :
制約式 べ 満
ベク (x, y) C
C
2 , 1 2 1