ORの手法(線形計画法1) 社会情報特講Ⅲ 大堀隆文(非常勤講師).

Slides:



Advertisements
Similar presentations
中学校段階での 相関関係の指導 宮崎大学教育文化学部 藤井良宜. 概要 現在の学習指導要領における統計の扱い これまでの相関関係の指導 相関関係の指導のポイント 相関関係.
Advertisements

模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
初年次セミナー 第13回 2次元グラフィックス(1).
情報・知能工学系 山本一公 プログラミング演習Ⅱ 第3回 配列(1) 情報・知能工学系 山本一公
線形計画 追加問題 ジュースを売って儲けよう!
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.5 節 主・双対法 pp
第八回  シンプレックス表の経済的解釈 山梨大学.
電子情報工学科5年(前期) 7回目(21/5/2015) 担当:古山彰一
Ⅰ.電卓キーの基本的機能 00 0 1 2 3 6 ⑤ 4 9 8 7 M- MR MC + × % M+ - = ÷ C √ +/- GT
ゲーム理論・ゲーム理論Ⅰ (第8回) 第5章 不完全競争市場の応用
「基礎OR」/「OR演習」 第3回 宿題3.2 Red Brand Canners解説
© Yukiko Abe 2014 All rights reserved
Copyright © Kazuhito HAMANO 2007 all Rights Reserved.
初級ミクロ経済学 -生産者行動理論- 2014年10月20日 古川徹也 2014年10月20日 初級ミクロ経済学.
第三回 線形計画法の解法(1) 標準最大値問題 山梨大学.
本時の目標 連立方程式の加減法のしかたを理解し、加減法を用いて連立方程式を解くことができる。
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
第四回 線形計画法(2) 混合最大値問題 山梨大学.
3 一次関数 1章 一次関数とグラフ §3 一次関数の式を求めること          (3時間).
数楽(微分方程式を使おう!) ~第5章 ラプラス変換と総仕上げ~
モード付き並列機械における オンラインスケジューリング
土木計画学 第11回(12月21日) 土木計画と説明責任 計画における代替案の作成1 担当:榊原 弘之.
3次関数・4次関数の極値に 関する高専1年生の発見
経済・経営情報コース コース紹介.
ランダムウォークに関するいくつかの話題 ・ランダムウォークの破産問題 ・ランダムウォークの鏡像原理 1 小暮研究会Ⅰ 11月12日
第二回 連立1次方程式の解法 内容 目標 連立1次方程式の掃出し法 初期基底を求める 連立1次方程式を掃出し法を用いてExcelで解析する
第6章 2重ループ&配列 2重ループと配列をやります.
消費の理論: スルーツキー方程式 需要曲線の導出 序数と基数
データ構造と アルゴリズム 知能情報学部 新田直也.
第 七 回 双対問題とその解法 山梨大学.
1章前半.
第九回 問題の定式化練習と 自主研究課題 山梨大学.
問題 1 キーボードから入力した数の合計を計算するプログラムを 作成せよ。最初に、何個の数を入力するかその数を入力 するようにする。
第4回 カルノー図による組合せ回路の簡単化 瀬戸 目標 ・AND-OR二段回路の実現コスト(面積、遅延)が出せる
電気回路Ⅱ 演習 特別編(数学) 三角関数 オイラーの公式 微分積分 微分方程式 付録 三角関数関連の公式
ORの手法(線形計画法3) 社会情報特講Ⅲ 大堀隆文(非常勤講師).
ORの手法(線形計画法2) 社会情報特講Ⅲ 大堀隆文(非常勤講師).
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.3 節 Lagrange緩和 pp
4. 組み合わせ回路の構成法 五島 正裕.
© Yukiko Abe 2014 All rights reserved
経営システム工学入門実験 ロジスティクス 第3回
経営システム工学入門実験 ロジスティクス 第3回
第6章 連立方程式モデル ー 計量経済学 ー.
表計算 Excel 演習 4.検索,条件付き書式設定,並べ替え.
ORの手法(組合せ最適化) 社会情報特講Ⅲ 大堀隆文(非常勤講師).
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
生産計画を立てる • 簡単なバージョン:輸送問題 定式化、最小費用流、バリエーション • 部品組立て計画 定式化、バリエーション
ミクロ経済学第9回 企業と費用2:費用最小化.
第Ⅱ部 協力ゲームの理論 第10章 コア 2008/07/01(火) ゲーム理論合宿.
担当者: 河田 正樹 年度 管理工学講義内容 担当者: 河田 正樹
25. Randomized Algorithms
変換されても変換されない頑固ベクトル どうしたら頑固になれるか 頑固なベクトルは何に使える?
or-11. 一次式 (オペレーションズリサーチを Excel で実習するシリーズ)
© Yukiko Abe 2015 All rights reserved
ex-8. 平均と標準偏差 (Excel 実習シリーズ)
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
計測工学 計測工学8 最小二乗法3 計測工学の8回目です。 最小二乗法を簡単な一時関数以外の関数に適用する方法を学びます。
5.集計,ピボットテーブル(クロス集計表)
第10章 機械設計の高度化 ★本講義の内容だけでは機械設計はできない? ★教科書や参考書の設計手順で設計ができるのか?
第16章 動的計画法 アルゴリズムイントロダクション.
ORの手法ゲームの理論3 (Excelによるゲーム理論実習)
プログラミングⅡ 第2回.
プログラミング入門 電卓を作ろう・パートI!!.
担当者: 河田 正樹 年度 管理工学講義内容 担当者: 河田 正樹
ex-8. 平均と標準偏差 (Excel を演習で学ぶシリーズ)
アルゴリズム入門 (Ver /10/07) ・フローチャートとプログラムの基本構造 ・リスト ・合計の計算
or-10. 線形計画法を Excel で行う (オペレーションズリサーチを Excel で実習するシリーズ)
割り当て問題(assignment problem)
情報数理Ⅱ 第10章 オートマトン 平成28年12月21日.
3 一次関数 1章 一次関数とグラフ §4 方程式とグラフ         (3時間).
Presentation transcript:

ORの手法(線形計画法1) 社会情報特講Ⅲ 大堀隆文(非常勤講師)

先週のベスト感想(講義で分った事) エクセルを使うと自分で計算するよりも断然楽であることが分かった。 スニッピングツールが使いやすい。 アドイン等不慣れな言葉がでたがソルバー自体は分かりいいもので数値を入力するのが楽しかった。 制約式とか操作の仕組みを覚えるのが大変だったが一度できると簡単! 丁寧にやり方を教えてもらったのですぐできました。 手計算ではなかなか難しい組み合せ問題もエクセルを用いれば簡単だとわかった。 2018/10/13

ベスト感想(講義・課題で難しかった事) 解がおかしいときに自分がどこを間違えて入力したのか探すのが大変だった。 アドインからソルバーを適用するのに方法が分からず時間がかかった。 課題によりソルバーで選ぶセルが違ったのでその選別に苦労した。 コンサート課題の目的関数が見つからなかった。 ソルバーを初めて使ったので使い方が難しかった。 制約式の設定を自分でやるとなるとなかなかできないと思った。 2018/10/13

先週のベスト感想(その他何でも1) エクセルが便利で毎回実習が楽しいです。 エクセル最高! 手計算より確実で早く解けるので積極的に使っていきたい。 ソルバーを他のことにも活用できたら良い。 簡単に計算できるが故に本当にこれが最適なのか疑ってしまった。 Excelのバージョンが違うと操作手順が大分違うので少し困った。 2018/10/13

先週のベスト感想(その他何でも2) スライドアップのURL(http://oohorisemi・・・)をmanaba からリンクを踏んで移動できるようにして下さい。 解説を増やしてほしい。 交流戦お疲れさまでした。 NMB48須藤さん結婚しますね! 乃木坂46のことをほとんど知らなかったのですが、この講義のお陰でメンバーの名前だけ覚えました。 今日は雨で電車が止まってしまい大変でした。 コーヒーブレイクを楽しみにしていました。 2018/10/13

線形計画法とは 特定分野の特殊問題を解く方法ではない。 様々な分野の使い道の広い最適化問題を解く手法である。 例えば資源に限りがある中で利益を最大にする生産計画を立てる問題がある。 また幾つかの供給地から幾つかの需要地に物品を、需要地の需要量を満たし総輸送費を最小にする輸送計画を立てる問題がある。

2変数の線形計画問題 ここで説明する製造販売計画と輸送問題は、変数が2個(または2個に削減)問題である。 2個では線形計画法は鉛筆定規で実行できる。 3変数以上では線形計画法は「単体(シンプレックス)法」かコンピュータソフトで解く。 単体法は万能だが数学的に難解である。 ソフト解法は付録でExcelソルバーによる解法を紹介する。

3.1 製造・販売計画 経営資源(ヒト,モノ,カネ)に限りある中で利益が最大の製品の製造販売量を求める問題。 簿記検定では「最適セールスミックス決定」。 【例題3.1】「角大食品」はハンバーグとミートボールを製造する。2製品の1ロット当り牛豚の使用料と利益(万円)、1日の牛豚使用可能量を下表に示す。 製品 ハンバーグ ミートボール 使用可能量 牛肉(kg/ロット) 2 1 100 豚肉(kg/ロット) 3 6 240 利益(万円/ロット)

例題3.1の解き方 製品は毎日売れるとすると利益を最大にするにはハンバーグとミートボールを毎日何ロット製造すれば良いか? (解説) ハンバーグをx(ロット)とミートボールy (ロット)を製造すると、総利益z(万)はz=2x+3yである。 この最大化(コストでは最小化)関数を目的関数という。

例題3.1の解き方1 (解説続き) 資源(牛肉と豚肉)には上限がある。 牛は1日2x+y(kg)必要で100kgが 限度。 以上の条件を制約条件という。

例題3.1の解き方2 【制約条件】 2x+ y≦100 (3.1) 3x+6y≦240 (3.2) 【非負条件】 のもとで、 【目的関数】 z=2x+3y (3.5) を最大にするx,yを求めることが目的である。

例題3.1の解き方3 この問題は線形計画問題といい、その解法を線形計画法と呼ぶ。 定式化で目的関数や制約条件の左辺はすべて「定数×変数」の合計で表される。 変数の1次式なので線形計画問題といい、その解法を線形計画法という。

例題3.1の解き方4 2変数線形計画問題はグラフを描き解く。 各制約条件の対応領域を考える。 制約条件(3.1)を変形すると、 y≦-2x+100 となり,図3.1(a)のように直線y=-2x+100とその下の領域(次頁図中桃色)が対応する。 制約条件(3.2)を変形すると、 y≦-(1/2)x+40 となり,図3.1(b)のように直線y=-(1/2)x+40とその下の領域(次頁図中桃色)が対応する。

例題3.1の解き方5 非負制約(3.3)は図3.1(c)のように軸全体とその右側領域,非負制約(3.4)は図3.1(d)のように軸全体とその上の領域が対応する. 図3.1 各制約条件(3.1)~(3.4)に対応する領域

例題3.1の解き方6 問題の解はすべての制約条件(3.1)~(3.4)を満たさないといけないので4つの領域の共通部分(図3.2(a))の中で解を探す。 図3.2 例題3.1の実行可能領域

例題3.1の解き方7 図3.2(a)を拡大した図3.2(b)において四角形OABCの境界と内部が制約条件(3.1)~(3.4)を満たす点の集まりで実行可能領域という。 実行可能領域内の点を実行可能解という. 目的関数を最大にする実行可能解を探す。

例題3.1の解き方8 図3.2(a)を拡大した図3.2(b)において四角形OABCの境界と内部が制約条件(3.1)~(3.4)を満たす点の集まりで実行可能領域という. 実行可能領域内の点を実行可能解という. 目的関数を最大にする実行可能解を探す。

例題3.1の解き方9 目的関数をy=-(2/3)x+(z/3)と変形し切片を変え図3.2(b)の四角形OABCに重ね書きする。 図3.3の直線①はz/3=10(∴z=30)に対する目的関数である。実行可能領域内の直線①上の点は「全制約条件を満たし利益30万円の点」となる。 直線②はz/3=20(∴z=60)に対する目的関数である。実行可能領域内の直   線②上の点は「全制約条 件を満たし利益60万円の 点」となる。 図3.3 目的関数最大化する実行可能解探索

例題3.1の解き方10 切片が大きい程目的関数は大きいがその直線は実行可能領域と共有する必要がある。 図3.3点Bを通る直線③が切片値をこれ以上大きくできない限界の直線となる。 点Bが目的関数を最大にする実行可能解である。 点Bは図3.2(b)より2直線2x+y=100, 3x+6y=240の交点だから連立一次方程式として解けばx=40, y=20を得る。 目的関数(3.5)に代入しz=2×40+3×20=140を得るハンバーグ40,ミートボール20ロット製造し利益は140万円で最大になる。

例題3.1の解き方11 最大化(または最小化)問題において目的関数を最大(または最小)にする実行可能解を最適解という。 例題3.1では(x,y)=(40,20)が最適解である。 得られる解は理論解であり実用解であるか常に検討すべきである。 例題3.1の最適解は整数値が得られ「12ロットずつ」などの出荷単位の指定もないので実用解である。

Coffee break 2015/7/3

好きなゲーム1(将棋) 将棋との出会い 始めたのは4才頃で、父が電気工事会社の親分で、多くの若い電工さんが我が家に出入りしていた。 電工さん達で将棋が流行り、私も仲間に入れてもらった。 20代の若者に勝てるはずがなく、連戦連敗だったが、負けず嫌いで何度も挑戦するが負け続け、やがて相手にされなくなる。 昭和の将棋盤 2015/11/2

好きなゲーム1(将棋) その後の将棋人生 中学の頃までは主に親戚のおじさんと遊びで将棋をやり、勝敗も5分だった。 アマ初段くらいか? 高校の頃から囲碁の方に興味が移り、年に2回主に親父相手に囲碁を遊ぶ。 アマ3級くらいか? 最近は両方ほとんどプレイしない。(麻雀は時々やる) 昭和の囲碁盤 2015/11/2

好きな将棋棋士1 升田九段 14歳にして家出した時母の物差しに書き残したのが「名人に香車を引いて勝てば大阪へ行く」の一文。 香車を引く=自分の香車を落とすハンデをつけて対局。 五期王将戦で再度大山名人を香落ちで3連勝。 「新手一生」を掲げ、升田式石田流、駅馬車定跡、角換わり腰掛け銀の升田定跡など多くの新手を発明。 升田幸三九段 2015/11/2

好きな将棋棋士2 藤井四段 2002年7月愛知県瀬戸市生まれの現在中学3年。昨年10月史上5人目の中学生プロ棋士。 史上最年少棋士でデビュー以来無敗で6月26日竜王戦1回戦で増田四段に勝利し歴代1位の29連勝を達成。 劣勢に陥ることもあるが対戦相手は「スキのない将棋」と口を揃える指し手。 14才の快進撃はメディアに大きく取り上げられ社会現象となる。 藤井聡太四段 2015/11/2

3.2 輸送問題 ある物を複数供給地から複数需要地に送る。 ルートにより輸送費が異なると総輸送費を最小にする各ルート輸送量を決めない。 輸送問題は線形計画問題で定式化できる。 単体法やExcelソルバーで解けるし次の例題3.2のグラフ解法で解ける場合もある。 「飛び石法」という独特法もある。

3.2 輸送問題(続き) 【例題3.2】食肉加工会社で商品「ボンフルハム」を工場A, Bから小売店C, D, Eに卸す。輸送ルートは図3.4のように6通りある。 図3.4 輸送ルート 1日の納入可能量はAから15t, Bから10t。1日当りの需要量は,Cで10t, Dで8t, Eで7t(需給計25tで一致)。

3.2 輸送問題(続き) 1日で納入可能量はAから15t, Bから10tである。 1日当りの需要量はCで10t, Dで8t, Eで7tである。(需給は計25tで一致)。 各ルート毎の1t当り輸送費は下表である。 3小売店の需要を満たす中で総輸送費を最小にする各ルートの輸送量を求めよ。 表3.2 各ルートごとの1t当りの輸送費 輸送費(万円/t) Cデパートへ D百貨店へ Eスーパーへ A工場から 1 2 5 B工場から 4 3

3.2 輸送問題の定式化1 1日当りの総輸送費をp(万)とおくとpはAからCへの輸送費1・u(万),AからDは2v(万), BからEは2z(万)の合計である。 p=u+2v+5w+4x+3y+2z(万)で最小化する。 A工場から小売店C, D, Eに対しu,v,w(t)を供給し合計15(t)、u+v+w=15を満たす。B工場はx+y+z=10を満たす。 CデパートはAとB工場からu+x=10、D百貨店はv+y=8、Eスーパーはw+z=7を満たす。 u,v,w,x,y,zは0以上の値をとる。 2015/6/12

3.2 輸送問題の定式化2 (制約式) u+v+w=15 …(3.6) x+y+z=10 …(3.7) u+x=10 …(3.8) v+y= 8 …(3.9) w+z= 7 …(3.10) (非負条件) u,v,w,x,y,z≧0 …(3.11) (目的関数) p=u+2v+5w+4x+3y+2z…(3.12)         ⇒最小化 2015/6/12

3.2 輸送問題の変数削減1 (解答)・例題3.2には6変数が登場しグラフ解法が使えない。 この問題に限り2変数の線形計画問題に変形できる。 非負制約を除く制約式を減らす。(3.6),(3.7)の両辺を加えると   u+v+w+x+y+z=25 …(3.13) (3.8),(3.9)式の両辺を加えると   u+x+v+y=18 …(3.14) 2015/6/12

3.2 輸送問題の変数削減2 (13)式の両辺から(14)式の両辺を引くと(10)式w+z=7を得る。 3.2 輸送問題の変数削減2  (13)式の両辺から(14)式の両辺を引くと(10)式w+z=7を得る。 これは(3.6)~(3.9)を満たす変数は自動的に(3.10)式も満たす。 (3.10)式は制約式として不要なので無視する。((3.6)~(3.10)のどの式を削除してよい). 2つの変数だけを残しそれ以外の変数を消去する。(3.7)より z=10-x-y …(3.15) z≧0も考慮しx+y≦10を得る。 2015/6/12

3.2 輸送問題の変数削減3 (3.8)より u=10-x …(3.16) が得られu≧0とx≧0を考慮し0≦x≦10を得る。 3.2 輸送問題の変数削減3  (3.8)より u=10-x …(3.16) が得られu≧0とx≧0を考慮し0≦x≦10を得る。 (3.9)より   v=8-y …(3.17) が得られv≧0とy≧0を考慮し0≦y≦8を得る。 (3.10),(3.15)式から   w=7-z=7-(10-x-y)=x+y-3 …(3.18) が得られw≧0を考慮しx+y≧3を得る。 (3.12)に(3.15)~(3.18)式を代入し p=(10-x)+2(8-y)+5(x+y-3)+4x+3y+2(10-x-y) =6x+4y+31 2015/6/12

3.2 輸送問題の変数削減4 以上をまとめると,例題2は制約条件 x+y≧ 3 …(3.19) x+y≦ 10 …(3.20) 3.2 輸送問題の変数削減4  以上をまとめると,例題2は制約条件   x+y≧ 3 …(3.19)   x+y≦ 10 …(3.20)   0≦x≦10 …(3.21)   0≦y≦ 8 …(3.22) の下で目的関数 p=6x+4y+31…(3.23) を最小にする変数x,yを求める問題に変形できる。 2015/6/12

3.3 レジャー選択問題 夏休み1週間を海水浴とレストランで過ごす。 海水浴とレストラン1回当たりの日数、費用、満足度を下表に示す。 表に日数と費用の上限を与えるとき、満足度を最大にする海水浴とレストランの回数を求めよ。

3.3 レジャー選択問題(定式化1) 【変数選択】 海水浴とレストランの回数をそれぞれ変数x,yと置く。 【目的関数】 海水浴とレストランの1回当りの満足度がそれぞれ3,2なので、トータルの満足度(目的関数)は、 z=3x+2y となる。

3.3 レジャー選択問題(定式化2) 【制約式(非負条件含)】 海水浴とレストランの1回当りの日数がそれぞれ2,1で、上限の7(夏休み期間)を超えてはならないので、  2x+y≦7 海水浴とレストランの1回当りの費用がそれぞれ1,2で、上限の5(万円)を超えてはならないので、 x+2y≦5 各回数は非負でなけれ ばならないので、 x≧0, y≧0

3.4 調理問題 レストランで手持ち材料でハンバーグとオムレツを幾つか作り利益を最大にしたい。 ひき肉とタマネギの在庫量と両メニューに必要な量、ハンバーグとオムレツの単価を表に示す。 利益を最大にする には、ハンバーグ とオムレツをいくつ 作るといいか?

3.4 調理問題(定式化1) 【変数選択】 ハンバーグとオムレツの数をそれぞれ変数x,yと置く。 【目的関数】 ハンバーグとオムレツの単価がそれぞれ400, 300なので、トータル利益は、 z=400x+300y となる。

3.3 調理問題(定式化2) 【制約式(非負条件含)】 ハンバーグとオムレツに必要なひき肉の量はそれぞれ60,40で、上限の3800を超えてはならないので、  60x+40y≦3800 ハンバーグとオムレツに必要なたまねぎの量はそれぞれ20,30で、上限の2100を超えてはならないので、 20x+30y≦2100 ハンバーグとオムレツ の数は非負でなければ   ならないので、 x≧0, y≧0

今日の課題1:栄養問題 成人が1日に必要な熱量(kcal)、蛋白質(g)、カルシウム(mg)、各食品100gに含まれる栄養素、各食品100gの値段が表1に与えられている。 表1 各食品に含む栄養素と値段 各栄養素を摂取し最小食費にする食パンと牛乳の量を求める線形計画問題を定式化せよ。

今日の課題1:栄養問題(回答) 表1 各食品に含む栄養素と値段 目的関数 制約式(非負条件含) 変数定義

今日の課題2:余暇問題 麻雀とテニスの好きな人がいる。週末に麻雀とテニス1回当たりの時間、費用、満足度を表2に示す。 余暇時間は16時間、費用は2万円とするとき、満足度を最大にする麻雀とテニスの回数を求める線形計画問題を定式化せよ。 表2 各余暇の時間と費用

今日の課題2:余暇問題(回答) 目的関数 表2 各余暇の時間と費用 制約式(非負条件含) 変数定義

今日の課題3:果物の輸送問題 仁木、壮瞥、余市の果樹園経営者が室蘭と小樽にりんごを輸送販売する。 出荷能力、需要、出荷地消費地間輸送コストを表3に示す。 変数は出荷地消費地間の輸送量とし表4で定義する。 全輸送コストを最小にする輸送量を求める線形計画問題を定式化した後、変数を2個に削減しなさい。 表3 出荷能力と需要及び出荷需要地輸送コスト 表4 変数の定義

今日の課題3:果物の輸送問題(回答) 制約式(非負条件含) 表3 果樹園出荷能力と消費地需要及び出荷需要地輸送コスト 変数2個に削減 目的関数

今日の課題4:講義・課題の感想 学生番号と氏名(1枚目、2枚目とも) 今日の講義・課題の感想 講義で分ったこと 講義で難しかったこと 課題で難しかったこと その他(何でも) 社会情報特講Ⅲ