離散最適化の理論と応用

開講元

経営工学コース

担当教員

塩浦 昭義

授業形態

講義 (対面型)

メディア利用科目

-

曜日・時限
(講義室)

火3-4 (W9-425) / 金3-4 (W9-425)

クラス

-

科目コード

IEE.B433

単位数

200

開講時期

2024年度

開講クォーター

3Q

シラバス更新日

2025年3月14日

使用言語

英語

シラバス

授業の目的（ねらい）、概要

この講義では，複数の不可分財（離散財）を扱うオークションについて議論する．そのようなオークションにおいて，財の最適な配分および均衡価格は繰り返しオークションと呼ばれるアルゴリズム（プロトコル）によって求められることが知られている．本講義では，これまでに提案されている幾つかの繰り返しオークションを紹介し，離散最適化の観点から理解する．とくに，このオークションにおいて重要な役割を果たす，効用関数の粗代替性について説明し，離散凹性との関係を示す．

本講義では、離散最適化の理論に関する数学的な研究成果を用いることで，経済学におけるオークションへ新しい視点を与えられる，という面白さを味わってもらうことを目指す．

到達目標

講義の終わりまでに，以下のことができるようになる．
（１）不可分財に関するオークションモデルを説明できるようになる．
（２）粗代替性の概念とその性質を理解できる．
（３）繰り返しオークションがどのようにして均衡価格を求めるのか，説明できるようになる．
（４）繰り返しオークションと最適化アルゴリズムの関係を理解できる．

キーワード

オークション，離散最適化，均衡解，アルゴリズム

学生が身につける力

• 専門力
• 教養力
• コミュニケーション力
• 展開力 (探究力又は設定力)
• 展開力 (実践力又は解決力)

授業の進め方

毎回の授業では主に講義を行い，講義の最後ではその講義内容に関連した演習問題を提示する．

授業計画・課題

準備学修(事前学修・復習)等についての指示

学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ概ね100分を目安に行うこと。

教科書

とくになし

参考書、講義資料等

参考図書：
室田一雄: 離散凸解析, 共立出版, 2001
室田一雄: 離散凸解析の考えかた---最適化における離散と連続の数理, 共立出版, 2007
K. Murota: Discrete Convex Analysis, SIAM, 2003
室田一雄, 塩浦昭義: 離散凸解析と最適化アルゴリズム, 朝倉書店, 2013
田村明久: 離散凸解析とゲーム理論, 朝倉書店, 2009

成績評価の方法及び基準

レポートと試験により評価

関連する科目

• IEE.A206 ： オペレーションズ・リサーチ 基礎
• IEE.A330 ： オペレーションズ・リサーチ応用

履修の条件・注意事項

組合せ最適化の理論に関する知識を持っていること（初回授業においてテストの形で確認する可能性あり）
具体的には，最短路問題，最大（重み）マッチング問題，ネットワークフロー問題の定義，
最適性条件，およびアルゴリズムを知っていること．

オフィスアワー

いつでも可．ただし，メールで事前連絡の上，訪問すること．