最適化理論１

Optimization Theory 1

9914615

14MAAPM306

小笠原　英穂

Hideho Ogasawara

2024年度前期

2024 1st Semester

月曜2限

Monday 2nd Period

理学部第一部　応用数学科

Department of Applied Mathematics, Faculty of Science Division Ⅰ

2.0単位

講義

Lecture

-

① [対面]対面授業/ [On-site] On-site class

自然科学・工学・社会科学などのいろいろな分野で発生する最適化問題（数理計画問題）の理論や数値解法について勉強する．

最適化問題の基本である線形計画法を学ぶ．本学科のディプロマ・ポリシーに定める『グローバル化する社会情勢の中で、解決困難な様々な課題に対し、状況を的確に把握・分析して、自らの数学的・論理的思考力によって柔軟に対応し積極的に問題解決を図る能力』を養成するための科目である．

1. 最適化問題とはどのような問題を指し、実社会のどんな場面で利用されているのかを説明できる．
2. 線形計画法の定式化を学び、代表的アルゴリズムである単体法の理論と実際を知って、その特徴が説明できる．また具体的な問題が解けるようになる．

リンク先の [評価項目と科目の対応一覧]から確認できます（学部対象）。
履修登録の際に参照ください。
​You can check this from “Correspondence table between grading items and subjects” by following the link(for departments).
https://www.tus.ac.jp/fd/ict_tusrubric/​​​

この授業は基本的に反転授業なので、LETUSに掲示された動画を予め視聴している必要がある．そのことを前提として、授業ではその内容に関する演習及び解説を行う．
１年次の微積分学と線形代数の知識が、ここに至って頻繁に活用されることを痛感させられるであろう．何事も基礎が大切である所以である．したがって曖昧なまま放置してきた事項に関しては、この際各自で十分な理解と定着を図らなければならない．
最適化のアルゴリズムは、数値計算によって実現されるので、数値計算上の種々の取扱いや基礎知識は不可欠である．よって２年次の「数値解析基礎1, 2及び演習」を履修済であることが望ましい．また「オペレーションズ・リサーチ」あるいは「数理計画法」を履修済みかまたは現在履修中だと相互に理解が深まる．演習にも用いるので教科書(誤植修正のある最新刷りのもの)は必ず購入すること．MathematicaやExcelを課題で利用する場合があるので、いつでも使えるようにしておくこと．

反転授業　Flipped classroom

-

履修上の注意に書いたように、予習としてLETUSに掲示された動画を事前に視聴し、ノートも取ってまとめておくこと．
線形計画法では1年生で習得した線形代数学、特に線形独立・従属、階数の概念や掃出し法の計算法が重要なのでよく復習しておくこと．教科書・ノートを見返して前回の内容を復習し、教科書の章末問題を解いてみて理解度を確認する．次回の内容を教科書・Web資料等で予習しておく．疑問や理解しにくいところがあれば、その要点をまとめておき、授業時に解決できるような姿勢で聴講する(予・復習合わせて4時間程度)．

出席が良好である前提(15回x80%=12回以上出席)で、平常時の課題やレポート・試験等により総合的に評価する．7〜9回目頃に中間試験を行う．なお、病欠等特別な理由なく出席が良好でない場合(上記の基準未満)や中間試験が著しく悪い場合は評価対象外とする．

・S：到達目標を十分に達成し、極めて優秀な成果を収めている
・A：到達目標を十分に達成している
・B：到達目標を達成している
・C：到達目標を最低限達成している
・D：到達目標を達成していない
・-：学修成果の評価を判断する要件を欠格している

・S：Achieved outcomes, excellent result
・A：Achieved outcomes, good result
・B：Achieved outcomes
・C：Minimally achieved outcomes
・D：Did not achieve outcomes
・-：Failed to meet even the minimal requirements for evaluation

Y

工学基礎 最適化とその応用／矢部 博 著／数理工学社／2006年発行／ISBN 978-4901683340

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
​https://mirai.kinokuniya.co.jp/tokyorika/​​​

It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
​​https://mirai.kinokuniya.co.jp/tokyorika/

◎線形と非線形計画法を両方扱っている本：
[1] 田村 明久・村松 正和「最適化法」（共立出版・工系数学講座 17）
[2] 寒野 善博・土谷 隆「最適化と変分法」（丸善出版・東京大学工学教程 基礎系 数学）
[3] 山下 信雄・福島 雅夫「数理計画法」（コロナ社・電子情報通信レクチャーシリーズC-4）
[4] 久野誉人・繁野麻衣子・後藤順哉「数理最適化」（オーム社）
[5] 金谷 健一「これなら分かる最適化数学」（共立出版）
◎非線形計画法のみを扱っている本：
[6] 山下 信雄「非線形計画法」（朝倉書店・応用最適化シリーズ6）
[7] 矢部 博・八巻 直一「非線形計画法」（朝倉書店）
[8] 今野 浩・山下 浩「非線形計画法」（日科技連）
[9] 講座・数理計画法・全11巻（産業図書）

1．最適化問題とは
最適化問題の定式化を理解し、ベクトル値関数による簡潔な表現がわかる．問題の様々な分類法が理解できる．
制約の有無（制約付、無制約）、関数の性質（線形、非線形、２次、分数）、　関数の特殊性（凸、最小２乗）、変数の性質（連続、離散）、整数計画（離散、組合せ最適化）
2．最適化問題の例（１）
生産計画と栄養問題を例に、問題の定式化の実際例を学び、その特徴が理解できる．
3．最適化問題の例（２）
輸送問題とナップサック問題などを例に、問題の定式化の実際例を学び、その特徴が理解できる．
4．線形計画法の歴史・標準形
線形計画法の簡単な歴史と位置付けを把握する．標準形への変換方法が説明できる．
5．基本用語と基本定理
線形計画法の基本用語や定義等が理解できる．単体法の理論的正当性を与える基本定理について、幾何学的意味とともに理解できる．
6．単体法の原理と基本事項（１）
単体法の原理を幾何学的解釈から理解できる．実際の計算は代数的操作によるので、必要な基礎的用語や概念が説明できる．（正準形、最適性条件）
7．単体法の原理と基本事項（２）
引き続き単体法の理論的根拠を学ぶ．（非有界、退化・非退化の場合、実行可能基底解の改良）
8．単体法のアルゴリズムと例
単体法の基本的アルゴリズムが理解できる（単体表）．問題が一意解の場合、そうでない場合、退化の場合、非有界の場合などを例で考察し、単体法の諸相と典型的特徴を幾何学的に理解できる．
9．２段階法（１）
単体法の中核をなす２段階法を学ぶ．第１段階で導入される人為問題と実行可能性との関係，第２段階との関係が理解できる．
10．２段階法（２）
２段階法の例を学び、単体法の有限回収束性について理解できる．
11．双対性と双対定理・相補性定理
双対問題の導入とその意味が理解できる．線形計画法の数学的構造の最も美しい部分である双対定理が理解できる．相補性定理から新しい視点や一般化が得られることを説明できる．
12．双対単体法（１）
主単体法の考えを双対問題に適用した双対単体法が理解できる．
13．双対単体法（２）
双対単体法を用いて問題が解ける．
14．感度解析と再最適化
再最適化を効率的に行う手法を説明できる．特に双対単体法を実際の場面に応用できるようになる．
15．前期の確認
到達度評価によって、前期に学んだ内容の習熟度を確認する．最後に簡単な解説を行う．

-

Mathematica

Excel, Scilab

-

-