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

Presentation on theme: "ORの手法(線形計画法2) 社会情報特講Ⅲ 大堀隆文(非常勤講師)."— Presentation transcript:

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

2 先週のベスト感想（講義で分った事） 輸送問題も今までと同じように定式化できることが分かった。
線形計画法は様々な社会問題を解くための基礎的なツールであることが分かった。 2018/11/6

3 ベスト感想（講義・課題で難しかった事） 今回は使われないのにグラフが出てきて混乱した。
課題3が需要を上回るように輸送するのか、上回らないよう(売れ残らない)にするのか分かりにくかった。 課題3で「需要は必ず満たすように制約式で需要≧変数式」にするのか、「需要内であれば必ず売れるから制約式で需要≦変数式」にするのか分からなかった。 変数を削減することが面倒だと感じたので次回の計算は丁寧にしたい。 2018/11/6

4 先週のベスト感想（その他何でも1） 今までの課題があっているか不安です。単位は取れるか？課題の答えが会っていなければ単位は取れないか？
中学のときに解いた数学の問題でも同じようなものがあったと思った。 表4がx1,x2じゃなくてx1(xの1倍),x2(xの2倍)に見えて最初戸惑った。 定式化するのにこんなに難しいのに解も求めるとなると次回が恐ろしい。 2018/11/6

5 先週のベスト感想（その他何でも2） 将棋やってみたいと思った！はさみ将棋しかわからない。
私もよく将棋をやるが棒銀しか戦法をろくに使えないので強い人にあたるとすぐ負けてしまう。 藤井四段はAIなのでは？という疑問がネット上に浮上している。面白い事を考える人もいると思った。 将棋よりマージャンの方が好きだ。 将棋以外のテーブルゲームは何かやりますか？ 2018/11/6

6 先週のベスト感想（その他何でも3） 大谷ヒット！ 久し振りに大谷のヒットが見れて嬉しかった。近藤は今シーズン復帰厳しそうなのが残念だ。
AKB系は毎年話題を作ってくるのが強いなって思った。 加地先生とはどういうきっかけでお知り合いになったのですか？ 2018/11/6

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

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

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

10 例題3.1の定式化2 （解説続き） 資源（牛肉と豚肉）には上限がある。 xとyに負の値はありえない。
牛は1日2x+y（kg）必要で100kgが限度。 豚は1日3x+6y（kg）必要で240kgが限度。 xとyに負の値はありえない。 これら条件を制約条件という。以上をまとめ、 【制約条件】2x+y≦100、3x+6y≦240 　　　　　　　 x≧0、y≧0(非負条件) のもとで、【目的関数】z=2x+3yを最大にするx,yを求めることが目的。

11 例題3.1の定式化3 （定式化まとめ） 【目的関数】 z=2x+3yを最大(max) 【制約条件】 2x+y≦100、3x+6y≦240
【非負条件】 　　　　 x≧0、y≧0

12 例題3.1の解法1 問題は線形計画問題、その解法を線形計画法と呼ぶ。 制約条件を満たし目的関数を最大にする変数を求めることが目的である。
制約条件(3), (4)を特に非負制約という。 目的関数(5)の右辺や制約条件(1), (2)の左辺はすべて「定数×変数」の和で表されるので、線形計画問題という。

13 例題3.1の解法2 2変数線形計画問題をはグラフを描いて解く。 各制約条件の対応領域を考える．
制約条件(1)は変形すると y≦-2x+100 となり，下図(a)の直線と下の領域が対応する． 制約条件(2)は変形すると3x+6y≦(1/2)x+40 となり，下図(b)の直線と下の領域が対応する．

14 例題3.1の解法3 2変数線形計画問題をはグラフを描いて解く。 各制約条件の対応領域を考える．
非負制約x≧0(3)は下図(c)の軸全体と右領域，非負制約y≧0(4)は下図(d)の軸全体と上領域が対応する。

15 例題3.1の解法4 図3.1 各制約条件(1)～(4)のまとめ

16 例題3.1の解法5 解は全制約条件(1)～(4)を満たさないといけない。 4つの領域の共通部分（下図(a)）の中で解を探す。
　　　(下図(b)は(a)の拡大図である)

17 例題3.1の解法6 拡大図(b)で四角形OABCの境界と内部が制約条件(1)-(4)を満たす点の集まりを実行可能領域。
実行可能領域内の点を実行可能解。 目的関数を最大にする実行可 　 能解を探す。 そのために目的関数を y=-(2/3)x+z/3と変形し、 切片値(z/3)を色々変えて、 図(b)の四角形OABCに重ねる。

18 例題3.1の解法7 下図の直線①はz/3=10（∴z=30）に対する目的関数直線である。
実行可能領域内にある直線①上の点は「全制約条件を満たしかつ利益が30万円」の点。 直線②はz/3=20（∴z=60）に対する目的関数直線である。 実行可能領域内の 直線②上の点は「す べての制約条件を 満たしかつ利益が 60万円」の点。

19 例題3.1の解法8 切片が大きい程目的関数は大きくなるが，直線は実行可能領域に含まれる必要である。
右図の点Bを通る直線③が切片値が最大の限界直線となり目的関数を最大にする実行可能解である。 点Bは右図より2直線2x+y=100,3x+6y=240の交点で，この連立一次方程式を解けばx=40,y=20となり目的関数z=2x+3yに代入しz=140を得る。 ハンバーグ40, ミートボ ール 20ロット製造し利益は140万 円で最大になる。

20 Coffee break 2017/7/5

21 朝ドラ「ひよっこ」あらすじ1 好きなドラマ(その1) 1964年東京オリンピック前後茨城県の奥茨城村に育つヒロイン谷田部みね子の物語。
東京出稼ぎの父を探し集団就職で上京し下町の工場で働きながら父を探す。 オリンピック後の不況で工場倒産で行く宛てなく父常連の洋食屋「すずふり亭」に勤める。 家出しているすずふり亭の1人娘由香に祖母と父親の仕送りを届ける。 2017/7/5

22 朝ドラ「ひよっこ」あらすじ2 好きなドラマ(その1) 由香の感じの悪さに怒るが母の死で家庭内不和に至る由香の思いに同情する。
すずふり亭を訪れた綿引から新情報で実が引ったくり犯に殴れら失踪したことを聞く。 ビートルズファンの叔父宗男のためコンサートチケットを入手しようと奮闘する。 ヒロインは『あまちゃん』でヒロイン母の少女時代を演じた有村架純を起用。 2017/7/5

23 朝ドラ「ひよっこ」キャスト1 好きなドラマ(その1) 主人公谷田部 みね子 演有村架純 みね子の母 演木村佳乃 みね子の父 演沢村一樹
2017/7/5

24 朝ドラ「ひよっこ」キャスト2 好きなドラマ(その1) みね子友人時子 演佐久間由衣 みね子友人三男演泉澤祐希 みね子叔父宗男演峯田和伸
2017/7/5

25 朝ドラ「ひよっこ」キャスト3 好きなドラマ(その1) すずふり亭店主 鈴子演宮本信子 鈴子の息子省吾演佐々木蔵之介 省吾の娘由香演島崎遥香
2017/7/5

26 今日の課題1：栄養問題 成人が1日に必要な熱量(kcal)、蛋白質(g)、カルシウム(mg)、各食品100ｇに含まれる栄養素、各食品100ｇの値段が表1に与えられている。 表1 各食品に含む栄養素と値段 各栄養素を摂取し最小食費にする食パンと牛乳の量を図的解法で求めなさい。

27 今日の課題1：栄養問題(回答) 表1 各食品に含む栄養素と値段 図的解法 定式化：食パンx, 牛乳y(×100g)とする。
目的関数：z=40x+25y → min 制約式： 270x+ 60y≧2500 8x+ 3y≧70 11x+100y≧600、x, y≧0 最適解

28 今日の課題2：余暇問題1 麻雀とテニスの好きな人がいる。週末に麻雀とテニス１回当たりの時間、費用、満足度を表2に示す。
余暇時間は16時間、費用は2万円とするとき、満足度を最大にする麻雀とテニスの回数を図的解法で求めなさい。 表2 各余暇の時間と費用

29 今日の課題2：余暇問題1(回答) 図的解法 表2 各余暇の時間と費用 定式化：麻雀x, テニスy(回)とする。
目的関数：z=5x+6y → max 制約式： 　4x+2y≦16 　2x+4y≦20 　x, y≧0 最適解

30 今日の課題3：余暇問題2 課題2の余暇問題において、麻雀とテニスの満足度がそれぞれ2と6に変わったときの最適解を図的解法で求めなさい。
表3 各余暇の時間と費用

31 今日の課題3：余暇問題2(回答) 表3 各余暇の時間と費用 図的解法 定式化：麻雀x, テニスy(回)とする。
目的関数：z=2x+6y → max 制約式： 　4x+2y≦16 　2x+4y≦20 　x, y≧0 最適解

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