ORの手法(組合せ最適化) 社会情報特講Ⅲ 大堀隆文(非常勤講師).

Slides:



Advertisements
Similar presentations
受付番号 平成 23 年度 東北復興に向けた地域ヘルスケア構築推進事業 (被災地域における医療・介護周辺サービスの提供拠点整備の推進及び医療情報 等の共有システムの推進のための調査事業) 提案書 事業区分 イ-2:被災地における医療情報等の共有等を可能にするシステム の推進の調査事業 (被災地での地域医療提供体制の再構築のための情報通信技術の活用の在り方、
Advertisements

計量的手法入門 人材開発コース・ワークショップ (IV) 2000 年 6 月 29 日、 7 月 6 ・ 13 日 奥西 好夫
統計学 第3回 西山. 第2回のまとめ 確率分布=決まっている分布の 形 期待値とは平均計算 平均=合計 ÷ 個数から卒業! 平均=割合 × 値の合計 同じ平均値でも 同じ分散や標準偏差でも.
Excel ソルバー練習 *ツール → アドイン → ソルバーアド インにチェックを入れて、ソルバー を使えるようにしてから、作業を行 うこと。
受付番号 平成 23 年度 東北復興に向けた地域ヘルスケア構築推進事業 (被災地域における医療・介護周辺サービスの提供拠点整備の推進及び医療情報 等の共有システムの推進のための調査事業) 提案書 事業区分 イ-1:被災地における医療情報等の共有等を可能にするシステム の推進の調査事業 (平成22年度医療情報化促進事業の検討内容を踏まえ、被災地において被災.
第6回 線形計画法の解法(4) 混合最小値問題 山梨大学.
エクセル(1)の目次 起動法、ブック、シート、セル ブックの開き方 エクセル画面 マウスポインターの種類 シート数の調節 データの入力法
エクセル(7)の目次 関数の書式 関数ウィザードの使い方 四捨五入/切り上げ/切り捨て IF関数 問題(1) 問題(2) 問題(3)
線形計画 追加問題 ジュースを売って儲けよう!
第八回  シンプレックス表の経済的解釈 山梨大学.
電子情報工学科5年(前期) 7回目(21/5/2015) 担当:古山彰一
情報処理入門A・B 坂口 利裕 横浜市立大学・商学部
Copyright © Kazuhito HAMANO 2007 all Rights Reserved.
エクセルで時間割作成 コンピュータリテラシー入門.
第三回 線形計画法の解法(1) 標準最大値問題 山梨大学.
エクセル(1)の目次 起動法、ブック、シート、セル ブックの開き方 エクセル画面 マウスポインターの種類 シート数の調節 データの入力法
整数計画法を用いた スリザーリンクの解法 杉村 由花 (東京大学)
エクセル(2)の目次 セル範囲の指定方法 データの消去法 アクティブセルの移動 セル内容の複写と移動 セル幅の変更方法
最適化ソルバーのための Python言語入門
アルゴリズムイントロダクション第5章( ) 確率論的解析
第二回 連立1次方程式の解法 内容 目標 連立1次方程式の掃出し法 初期基底を求める 連立1次方程式を掃出し法を用いてExcelで解析する
リンクパワーオフによる光ネットワークの省電力化
情報処理A 第?回 Excelの使い方2.
第 七 回 双対問題とその解法 山梨大学.
情報理論2 第6回 小林 学 湘南工科大学 2011年11月15日 〒 神奈川県藤沢市辻堂西海岸1-1-25
1章前半.
第九回 問題の定式化練習と 自主研究課題 山梨大学.
問題 1 キーボードから入力した数の合計を計算するプログラムを 作成せよ。最初に、何個の数を入力するかその数を入力 するようにする。
メディア学部 2011年9月29日(木) 担当教員:亀田弘之
寺尾 敦 青山学院大学社会情報学部 エクセルでの正規分布の グラフの描き方 寺尾 敦 青山学院大学社会情報学部
需要の価格弾力性 価格の変化率と需要の変化率の比.
ORの手法(線形計画法3) 社会情報特講Ⅲ 大堀隆文(非常勤講師).
寺尾 敦 青山学院大学社会情報学部 エクセルでの正規分布の グラフの描き方 寺尾 敦 青山学院大学社会情報学部
プロジェクトの選択基準 と CBAの役割と限界
<研究開発分野> 次世代人工知能技術分野 <研究開発項目⑦> 次世代人工知能技術の社会実装に関するグローバル研究開発
表計算 Excel 演習 6. ルックアップ,データの入力規則.
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.3 節 Lagrange緩和 pp
情報工学総合演習 D-I 近似アルゴリズム 埼玉大学 理工学研究科 山田 敏規、 橋口 博樹、 堀山 貴史
「ユーザー設定リスト」の作成と削除 ◎ 新しい「リスト」の作成法
プログラミング応用 printfと変数.
エクセル(6)の目次 「ユーザー設定リスト」の作成と削除 「入力規則」での「リスト」 ユーザー定義による表示形式
寺尾 敦 青山学院大学社会情報学部 エクセルでの正規分布の グラフの描き方 寺尾 敦 青山学院大学社会情報学部
関数の書式 ● SUM関数、AVARAGE関数など代表的ないくつかの関数の書式(数式の構文)は、下記のようなものである。 =関数名(引数1,引数2,引数3,・・・・・) ●引数(入力データ)は、数値で入力しても、セル名で指定してもよい。 例: =SUM(A1:A10,B21:B30,C31:C40)
ゲームプログラミング講習  第3章 ゲーム作成 ブロック崩しを作ります ゲームプログラミング講習 第3章 ゲーム作成.
ORの手法(組合せ最適化) 社会情報特講Ⅲ 大堀隆文(非常勤講師).
人為変数や二段階を不要とする 実数型simplex法の解き方の 提案と検証
「次世代人工知能・ロボット中核技術開発」 (次世代人工知能技術の日米共同研究開発) ●●●●●●●●の研究開発
ボルツマンマシンの定義 ボルツマンマシン(Boltzmann machine)は、スピン・システムをヒントに作られたモデルである。
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
ファジィ制約充足問題への 連続領域の導入 Introducing continuous domains to
情報理論2 第3回 小林 学 湘南工科大学 2011年10月25日 〒 神奈川県藤沢市辻堂西海岸1-1-25
エクセル(2)の目次 セル範囲の指定方法 データの消去法 アクティブセルの移動 セル内容の複写と移動 セル幅の変更方法
ex-8. 平均と標準偏差 (Excel 実習シリーズ)
コンパイラ 2011年10月20日
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
計測工学 計測工学8 最小二乗法3 計測工学の8回目です。 最小二乗法を簡単な一時関数以外の関数に適用する方法を学びます。
  第3章 論理回路  コンピュータでは,データを2進数の0と1で表現している.この2つの値,すなわち,2値で扱われるデータを論理データという.論理データの計算・判断・記憶は論理回路により実現される.  コンピュータのハードウェアは,基本的に論理回路で作られている。              論理積回路.
最長片道きっぷの厳密解を求める 東京大学大学院 宮代隆平,葛西隆也.
表計算 Excel 演習 1.Excel を使ってみる.
データ解析 静岡大学工学部 安藤和敏
サポートベクターマシン Support Vector Machine SVM
ORの手法ゲームの理論3 (Excelによるゲーム理論実習)
メディア学部 2010年9月30日(木) 担当教員:亀田弘之
2.関数の組み合わせ によるプログラム.
ex-8. 平均と標準偏差 (Excel を演習で学ぶシリーズ)
or-10. 線形計画法を Excel で行う (オペレーションズリサーチを Excel で実習するシリーズ)
Cプログラミング演習 ニュートン法による方程式の求解.
3 一次関数 1章 一次関数とグラフ §4 方程式とグラフ         (3時間).
募集ページ作成マニュアル 準備 募集画面作成 コンタクトフォームの作成(コンタクトフォームとは何か説明) 応募フォームの作成 リンク付け
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
Presentation transcript:

ORの手法(組合せ最適化) 社会情報特講Ⅲ 大堀隆文(非常勤講師)

例題10.5(プロジェクト選択問題) ある会社で下表のプロジェクトが採用候補である。 予算1,300万円以内で,予想利益(純利益)が最大になるようプロジェクトを採用したい。 本問題を定式化しモデル化せよ(単位:万円) プロジェクト A B C D E 予想利益 160 170 100 150 70 予算 600 550 400 250 200

プロジェクト選択問題の変数 定式化ではx1, x2, …, x5 の5変数を用意。 x1はプロジェクトA,x2 はBに対応。 同様に5変数が1か0でプロジェクト採否。 組合せ最適化の内、変数が整数に限る問題を整数計画という。 特に変数が0か1に限る問題を0-1整数計画といい、プロジェクト選択問題もこれに属する。   

プロジェクト選択問題の定式化 目的関数160x1+170x2+100x3+150x4+70x5→最大 目的関数はプロジェクト採用の場合,対応変数が1となりプロジェクト予想利益を加算する。 1番目の制約条件は予算限度1300万円以内に収める条件で,2番目は変数が0か1に制限する.

10.5 プロジェクト選択問題を エクセルで解く1 上記シートのセルには次の値や関数を入力する。 B2:F2:各プロジェクトの予想利益の入力 10.5 プロジェクト選択問題を エクセルで解く1 上記シートのセルには次の値や関数を入力する。 B2:F2:各プロジェクトの予想利益の入力 B3:F3:各プロジェクトにかかる予算の入力 B4:F4:各プロジェクトに対する変数xiのセル(解が保持される)

10.5 プロジェクト選択問題を エクセルで解く2 G2:目的関数値とし下記の式を入力する。「=SUMPRODUCT(B2:F2,B$4:F$4)」 G3:1番目の制約条件の左辺を入力する。「=SUMPRODUCT(B3:F3,B$4:F$4)」 H3:1番目の制約条件の右辺の値を入力する。

10.5 プロジェクト選択問題を エクセルで解く3 ソルバー起動し「ソルバーの パラメータ」ダイアログで以下の 設定をする(右図参照). 10.5 プロジェクト選択問題を エクセルで解く3 ソルバー起動し「ソルバーの パラメータ」ダイアログで以下の 設定をする(右図参照). 「目的セルの設定」:$G$2   「目標値」:最大値 「変数セルの変更」:$B$4:$F$4 「解決方法の選択」:シンプレックスLP 「制約条件の対象」:$G$3 <= $H$3を追加

10.5 プロジェクト選択問題を エクセルで解く4 変数0-1条件を追加するために 「制約条件の追加」:$B$4:$F$4に対し「<=」の選択リストで「bin」を選び条件に加えると変数がバイナリ(0-1)制約となる。 「int」選択で整数制約。 「解決方法の選択」で シンプレックスLPと選択 すると整数計画では分 枝限定法が用いられる。

10.5 プロジェクト選択問題を エクセルで解く5 結果は下図に示し、プロジェクトC,D,Eを採用し,予想利益が420万円となる.

10.5 プロジェクト選択問題を エクセルで解く6 ソルバーパラメータ画面をExcel結果Sheetに貼り付ける。 ソルバーパラメータ画面はSnippingツールかPrintScreen等の画面複写により複写し、ExcelSheetに貼り付ける。

課題2(レポート収集問題) 社会情報実験を履修する二宮君は優れたレポートを書こうと過去レポートを集める。 先輩により過去レポートを保管していなかったり、レポートを返却しない年があったりで、保存レポートにばらつきがある。 下表は各先輩から借りるコストと保存レポートの種類を示す。 最小コストで全レポートを集めるにはどの先輩達に頼むのが良いか。例題と下記の定式化を参考にExcelソルバーで解をSheet2に求めなさい。 プロジェクト A B C D E 予想利益 160 170 100 150 70 予算 600 550 400 250 200

レポート収集問題の定式化 先輩iに依頼を1、非依頼を0とする変数をxi(i=1~8)とする。 目的関数:2000x1+4300x2+5700x3+2500x4    +3800x5+2800x6+5200x7+2300x8 ⇒ min 制約式:x1+x2+x3≧1 x3+x4+x7≧1 x3+x6+x8≧1 x1+x5+x6≧1 x2+x4+x5+x7≧1 x1+x5+x6+x7≧1 xi=0 or 1(i=1~8)

レポート収集問題を Excelソルバーで解く1 B2:I2:各先輩のコスト(費用)を入力。 B3:I4:各先輩のレポート採用可否変数xiのセル(解が保持される)

レポート収集問題を Excelソルバーで解く2 J2:目的関数とし下記の式を入力する。「=SUMPRODUCT(B2:I2,B3:I3)」 J4:1番目の制約条件の左辺を入力する。「=SUMPRODUCT(B4:I4,B$3:I$3)」 J4をJ5~J9に複写。 K4~K9:制約条件の右辺(1)を入力。

レポート収集問題を Excelソルバーで解く3 「ソルバーパラメータ」ダイアロ グで以下の設定をする。 「目的セルの設定」:$J$2   「目標値」:最小値 「変数セル変更」:$B$3:$I$3 「解決方法の選択」:シンプレックスLP

レポート収集問題を Excelソルバーで解く4 「制約条件対象」 制約条件$J$4 >=1 ~ $J$9>=1を追加するために、「<=」の選択リストで   「>=」を選ぶ。 0-1条件を追加するため に$B$3:$I$3に対し「<=」 の選択リストで「bin」を選 ぶと変数がバイナリ (0-1)制約となる。

レポート収集問題を Excelソルバーで解く5 「解決」ボタンを押すと、   右上図が出るので「OK」ボタンを押す。 結果は右下図で、最適解では先輩1,4,8のレポートを採用。 最適費用は、2000+2500+2300 =6800円となった。

レポート収集問題を Excelソルバーで解く6 ソルバーパラメータ画面をExcel結果Sheetに貼り付ける。 ソルバーパラメータ画面はSnippingツールかPrintScreen等の画面複写により複写し、ExcelSheetに貼り付ける。

課題3(コンサート警備問題) 嵐のコンサートが札幌ドームで開催される。 人気グループなので大勢のファンが殺到するので事故防止のために厳重な警備が必要である。 そこで札幌ドームではどこに警備員を配置するかを検討する。 会場担当者は会場全体を小さなブロックi=1~7に分け、警備員を候補地点j=1~7に配置することにした。

課題3(コンサート警備問題) 各候補地の担当ブロックを下表に示す。 会場全体を最小人数の警備員で警備するときの警備員配置を求める、組合せ最適化問題を定式化しなさい。 表 各候補地の担当ブロック 表2 各候補地の担当ブロック

コンサート警備問題の定式化 変数定義:候補地iの選定を1、非選定を0とする変数をxi(i=1~8)とする。 目的関数:x1+x2+x3+x4+x5+x6+x7+x8 ⇒ min 制約式:x1+x3≧1, x1+x2+x7≧1 x2+x3≧1, x4+x7≧1, x4+x5≧1. x6≧1, x5+x6+x7≧1 xi=0 or 1(i=1~8) 表2 各候補地の担当ブロック

課題1(派生ユニット編成問題) 東北震災復興支援のために乃木坂46のメンバーから派生ユニットを編成したい。 メンバーの人気度と出演料を右表に示す。 予算が500を超えない範囲で、人気度の和が最大になるメンバーを選定し派生ユニットを編成する、組合せ最適化問題を定式化しなさい。 表 人気度と出演料

派生ユニット編成問題の定式化 変数定義:x1(秋元)x2(生田)x3(生駒)x4(斎藤) x5(桜井)x6(白石)x7(高山)x8(西野)x9(松村)x10 (若月)は、選抜で1、非選抜で0 目的関数:50x1+60x2+40x3 +80x4+45x5+70x6+35x7 +100x8+40x9+45x10⇒max 制約式:140x1+120x2+50x3 +40x4+70x5+150x6+90x7 +170x8+90x9+70x10≦500 xi=0 or 1(i=1~10) 表3 人気度と出演料

ソルバーで解けない問題 Excelソルバーでは、変数の数,制約式の数が制限され実用的問題は解けない。 最近性能の良い最適化ソルバーも開発されている。 問題のタイプ,問題の大きさなどで解けない問題も存在する. TSPなどは定式化は可能であるが制約式が指数的に増大するので、ソルバーで直接解くのは難しい。