理学部理学科数学プログラム（数理物質科学専攻　数理科学コース） 田中研究室（最適化理論，オペレーションズ・リサーチ）
最適化数学A / B (251S1517 / 252S1527) (Optimization Mathematics A / B)
使用教科書：田中環著，「もっと知りたくなる　最適化数学の基礎」，培風館，ISBN：978-4-563-01171-0 （発売が少し遅れているかもしれません。それまではプリントを配布します。）
最適化数学A (251S1517) のまとめと筆記試験は 6月4日（水） の予定です。
最適化数学B (252S1527) のまとめと筆記試験は 7月30日（水） の予定です。
[理学部棟 B303]
小テストの解答や課題レポートについては，学務情報システムの 小テスト機能，レポート機能を利用して提出して下さい。
小テストの解答用紙やレポートをPDFで提出する仕方
  1. 表紙は不要。解答は手書き。 小テストの添削を提出するときは用意された解答用紙を使うこと。
  2. レポートの場合はノート（ルーズリーフなど）の一番上に 在籍番号，氏名を記載すること。
  3. スキャンは，プリンタかコピー機でできる。 スマホしかなくてもOfficeLensなどのアプリを使用すれば可能。 ただし，出力形式をPDFに指定すること。 なお，パソコン上で他の形式のファイルをPDFにする方法は色々あるが， 印刷の時にプリンターのところで「Microsoft Print to PDF」を選んべばよい。 なお，その際に用紙のサイズを指定すること。
  4. 出力サイズはB5用紙かA4用紙サイズ。 PDFを表示させた時，ズームで100%表示を選ぶと読み取った元の大きさが分かる。 プロパティからもページサイズを確認することが可能。
  5. 提出するレポートはなるべく１つのファイルに結合したり， ファイル容量を小さくする工夫を行うこと。 仮に，PDFの結合用のソフトが無くても， OfficeLensの場合は追加のボタンで複数のスキャンを１つのPDFとして出力できる。 また，OfficeLensを使わなくても，既に複数の画像ファイル（JPEG,GIF,PNGなど）があった 場合には，それらを複数選択して（Ctrlキーで選択）， 右クリックメニューでポップアップメニューから「印刷」を選択すれば，上記に書いたように プリンターのところで「Microsoft Print to PDF」を選ぶと自動的に１つのPDFが作成できる。
  6. 提出するファイル名は， （半角英数の）学籍番号で始まる名前にすること。
  7. 提出締め切りは「日曜日まで」。 ただし，小テストやその添削については，学務情報システムに記載してある日時が優先される。 もちろん，間に合わなかったときはメールで提出しても構わない。
WordやExcel等のファイルをPDFに変換する仕方
  1. WordやExcelを使ってPDF変換：保存するときに，PDFとして保存すればよい。
  2. Windows10の仮想プリンター [Print to PDF] を使ってPDF変換： WordやExcelで印刷するときに，「Microsoft Print to PDF」を選択すればよい。
［１］配布資料と学習内容
  1. 講義案内と授業予定
  2. 4/9 は，高等学校で習う，内積の定義を見直し， スライド[1]に基づいて， 連立方程式(不等式)の解の集合を手際よく図示できるように考えるコツを学習します。 また，超平面と半空間の概念を学習します。
    なお，教科書がまだ入荷されていないかもしれませんので， 参考資料として，参考資料[1] も利用して下さい。
  3. 4/16 は，前回の復習を簡単に行って， すぐに 小テスト[A1](4/16) を行いました。 その後， 参考資料[2]（教科書37--48頁の内容）に基づいて， 数理計画問題の紹介とその内，制約関数に制限をつけて線形計画問題を説明します。 あらかじめ，該当するところをよく読んで理解してきてください。 それと，スラック変数を入れて不等式を等式に変形する事も学びます。 次回は，基底解，実行可能解，実行可能基底解などの概念とその線形代数的な意味付けを学びます。 また，連立一次方程式や連立一次不等式の表す領域（実行可能領域）についての 基本的な考え方とその上での線形関数の最大・最小を学習します。
  4. 4/23 は， 参考資料[2]の残りを説明し線形計画問題の」標準形について学習しました。 教科書の写し（pp.41--48）を使用して， 線形計画問題の実行可能領域が有限個の頂点を持つ凸多面体（polytope）である時は，最適解はその頂点の いずれかとなり，最大値あるいは最小値は必ず存在することを説明しましたが， 証明は次回となりました。教科書の写しをよく読んでみてください。 また， 実行可能領域が凸多面体でない場合，つまり，有界な集合でなく，無限遠まで領域が 広がっている場合は，目的関数の法線ベクトル（勾配ベクトル）の向きによって， 最大値や最小値が存在しないこともあることについても次回となります。
    その後，具体例として 小テスト[A2]で 線形計画問題の実行可能領域が有限個の頂点を持つ凸多面体である時には，端点で最小値，最大値をとる ことを確認しました。
    その他，スラック変数を挿入して標準形に直す方法を確認します。 その他の用語（基底行列，基底変数，非基底行列，非基底変数など）については 各自で復習しておいて下さい。
    次回は，4月30日（水）です。 それまでに， シンプレックス法の手続きとその具体例について， 教科書の写し（pp.49--54） を参考にして理解して下さい。
  5. 4/30 は，最初に，教科書の定理2.1を学習してから， なぜ，実行可能集合の頂点（端点）で最適値を取るのかを理解しました。これにより， 小テスト[A2](4/23) の振り返りをしました。また， 2022年のオンライン授業動画を用いて，シンプレックス法の考え方を学びます。 その後に， 線形計画問題の標準形に直す方法を復習してから， 小テスト[A3] を実施しました。 そして， 課題[A2]の振り返りをしました。 これは，これまでの学習の復習とシンプレックス法の理解のための準備運動です。
  6. 5/14 は， 教科書の写し（pp.49--54）に基づいて， 線形計画問題の標準形に対する シンプレックス法を学びます。 シンプレックス法の基本操作は「行列の行基本変形」です。 ただし，ガウス行列を作るやり方とは異なり，あるルールに従って基底行列を構成します。
    具体的には， 基底行列の選び方に複数の可能性があること，判定項の位置， 停止できない時に次に選ぶピボットの場所の選び方， 停止した時にスラック変数を捨て去って最適解を書くこと， 表（タブロー）の中の最適値の現れる場所等について学習します。
    配布資料の内容が理解できない場合は，過去の授業の内容を参考にしてください。 この時の判定項（停止条件）や更新手続きがどのようにして導かれるのか， についても学習しました。 教科書の写し（pp.55--60） をスライドで説明しました。もう一度，よく読んでください。
  7. 5/21は，最初に小テスト[A4](4)と課題[A3][Report-A3]の解答例の説明を行ってから 教科書の写し（pp.66--71）に基づいて， 線形計画問題の初期実行可能基底解の見つけ方とその計算方法を学習しました。 　
    【２段階法の考え方】
    最初から，等式制約だけの問題の場合は，スラック変数を使うことができず， 基底行列をどのように選べばよいかが問題となります。 連立方程式が2本の式だけなら，２次元の図が書けるので容易に見つけることが可能ですが， 3本以上の問題では，一次独立の列ベクトルの組を探すだけでも一苦労です。
    そんな時， 元の問題の制約条件に人為変数を挿入して， その挿入した人為変数の和を目的関数とする（別の）線形計画問題（人工問題）を 解くことによって，元の問題に実行可能解が存在するかどうかを判定でき， 『最適値が零になった時に元の問題に実行可能解が存在する』ことが分かります （実は，その逆も成り立ちます）。 同時にその人工問題の変形後の最後の係数行列の部分を再利用することができ， 人為変数を捨て去った連立方程式の部分を制約式として目的関数を元の問題にして シンプレックス法を続けるという２段階法を学習しました。
    ２段階目を解く際に，目的関数の基底変数に関する係数を零にする際に， 係数行列の成分に分数があるところをうまく処理する方法も説明しました。 つまり，ケアレスミスを失くす方法を具体的に説明しました。 ポイントは分数の部分をくくりだすということです。 実際には通分にあたるのですが，括弧の中が整数だけなので，簡単な計算になり， 計算ミスを防げるという点が有用です。 最後に，小テスト[A5]を実施して理解を深めました。 各自で その解答をみて添削して下さい。 その２ページ目に類題をつけて解いたものを学務情報システムから提出してください。
  8. 5/28は，最初に授業評価アンケートに回答してもらいます。 既に入力できるようになっているので，今から入力してもらっても構いません。
    次に， 小テスト[A5]の解説を行ってから，
    練習問題（5/28）の説明をします。 すでにダウンロードできるようにしてあります。試験問題対策として利用してください。 解答例は， 過去のオンライン授業動画（第７回）に解説されています。後でアクセスできるようにします。
  9. 6月4日（水）まとめと筆記試験

［２］確認問題(小テスト)とレポート問題や練習問題
  1. レポート課題[A1](4/9)
    スライド[1]の課題をレポートとしています。 線形計画問題の不等式を満足する領域を内積の考え方を使って図示し（各不等式の法線ベクトルを記載する）， 目的関数の等高線を表示して（法線ベクトルを記載する），最大値を与える解とその時の値を求めよう。
  2. 小テスト[A1](4/16)と その解答
    内積を利用して不等式領域（半空間）を図示する問題。 法線ベクトル（勾配ベクトルともいう）と半空間の関係が理解できているかを見る問題。 半空間の境界（平面の時は直線）を超平面というが，それと法線ベクトルは直交している。
  3. 小テスト[A2](4/23)
    線形計画問題の実行可能領域が有限個の頂点を持つ凸多面体である時の最大・最小に関する問題。
  4. レポート課題[A2]（授業中に途中まで作業します） 解答例
    簡単な線形計画問題に対してスラック変数を用いて標準形へ変形したり，実行可能基底解をすべて求めたり， グラフから最適解を直感的に求めたりする問題。 また，シンプレックス法で解いて最適解と最適値が他の方法で求めたものと同じくなることを確かめてみよう。
  5. 小テスト[A3](4/30)と その解答例
    不等号の向きが反対だったり，非負条件のない一般の線形計画問題を 標準形（最小化問題，等式制約，すべての変数に非負条件あり）に直す問題。
  6. 小テスト[A4]と その解答例
    初期の実行可能基底解を適当に見つけ，シンプレックス法で最適解とその時の最適値を求める問題。 実行可能基底解は３通りあるので，どれから出発しても良いので，一通りだけの解答でよい。
  7. 課題[A3][Report-A3]と その解答例
    線形計画問題をシンプレックス法で解いて最適解と最適値を求める問題。
  8. 小テスト[A5]と その解答

    人為変数を挿入して２段階法のシンプレックス法で解く線形計画問題。 最初に，２段階法で省エネ型として，既に与えられている。 ２本の連立方程式なので，どの２つの列を組合せて基底行列になるように選べばよいかを考えればよい。
    第１段階の人工問題の最適値が０となる問題となっているのだが，ちゃんと０となることを シンプレックス法で確かめて，その後，その最後の表の元の変数に当たる部分の係数行列と右辺を 取り出し，目的関数を元の関数の係数に取り換えて，あらためて第２段階をシンプレックス法で 解くことになる。
  9. 練習問題と その最適解・最適値のみ
  10. 小テスト[B1]と その解答および その解説
    与えられた線形計画問題からその双対問題を作る問題。(2)についてはいくつも方法があるが， 式を整理すると同じものになる。昨年の授業の動画に詳しい解説があります。
  11. 小テスト[B2]と その解答
    与えられた線形計画問題を標準形に直し，その双対問題を作る問題。 また，双対問題が２変数の線形計画問題になるので，容易に最適解と最適値を求めることができる。 もちろん，シンプレックス法で解いても答えは同じになる。 授業では与えられた問題(LP)を標準形にして双対問題を求めたが， 一般形の不等号の場合に対する最大化の双対問題にしてもよい。この場合は， 見かけは異なって見えるが，同値な問題である。
  12. 課題[B2]
    具体的な行列$A$とベクトルを与えて， ファルカスの補題とゴルダンの定理について， 二者択一の定理の一方が成立して他方が成立しない例をそれぞれ図を書いて説明せよ。
  13. 小テスト[B3]と その解答例
    複数の２変数実数値関数からなる制約条件の下で，２変数実数値関数の最適性条件を確認する問題。

［３］2022年のオンライン授業動画（履修登録者のみ視聴可能） YouTubeの32名までの制限により，学務情報システムの学生のアカウントを各回ごと２つのリンク先のどちらかに登録してあります。 両方には登録できないので，一方がだめなら他方を試してみてください。
  1. [A]第１回（令和4年4月13日）のYouTube動画
  2. [A]第１回（令和4年4月13日）のYouTube動画
  3. [A]第２回（令和4年4月20日）のYouTube動画
  4. [A]第２回（令和4年4月20日）のYouTube動画
  5. [A]第３回（令和4年4月27日）のYouTube動画
  6. [A]第３回（令和4年4月27日）のYouTube動画
  7. [A]第４回（令和4年5月11日）のYouTube動画
  8. [A]第４回（令和4年5月11日）のYouTube動画
  9. [A]第５回（令和4年5月18日）のYouTube動画
  10. [A]第５回（令和4年5月18日）のYouTube動画
  11. [A]第６回（令和4年5月25日）のYouTube動画
  12. [A]第６回（令和4年5月25日）のYouTube動画
  13. [A]第７回（令和4年6月1日）のYouTube動画
  14. [B]第２回（令和4年6月22日）のYouTube動画
  15. [B]第３回（令和4年6月29日）のYouTube動画
  16. [B]第４回（令和4年7月6日）のYouTube動画
  17. [B]第５回（令和4年7月13日）のYouTube動画
  18. [B]第６回（令和4年7月20日）のYouTube動画
  19. [B]第７回（令和4年7月27日）のYouTube動画

［４］関連リンク
  1. 数理計画法パッケージ　Nuorium Optimizer
    株式会社「NTT DATA 数理システム」で開発・販売されている数理計画ソフトウェアで， 「数式ベースの自然で簡潔な記述ができるモデリング言語」や「様々な実用的な求解アルゴリズム」 などを含んだ汎用数理最適化パッケージです。
  2. 数式処理・数式モデル設計環境 Maple (メイプル)
    Maplesoft社の数式処理ソフトMapleの概要と事例を見ることができます。
  3. (社)日本オペレーションズ・リサーチ学会
    日本OR学会のホームページでは， 日本でのオペレーションズ・リサーチ（OR）関係の活動情報が見れます。 2022年度の秋季研究発表会は新潟でハイブリッド開催されました。
  4. 第28回RAMPシンポジウム
    日本OR学会の数理計画研究部会 (RAMP: Research Association of Mathematical Programming) が 開催する，最適化や数理計画に関するシンポジウムです。2016年度は新潟大学で開催されました。

トップへ
トップへ


新潟大学 理学部数学プログラム／大学院自然科学研究科数理物質科学専攻　数理科学コース
E-mail: prtana@m.sc.niigata-u.ac.jp