ORの手法(線形計画法2)
社会情報特講Ⅲ
先週のベスト感想(講義で分った事)
• 輸送問題も今までと同じように定式化できる ことが分かった。
• 線形計画法は様々な社会問題を解くための 基礎的なツールであることが分かった。
ベスト感想(講義・課題で難しかった事)
• 今回は使われないのにグラフが出てきて混乱した。 • 課題3が需要を上回るように輸送するのか、上回 らないよう(売れ残らない)にするのか分かりにく かった。 • 課題3で「需要は必ず満たすように制約式で需要 ≧変数式」にするのか、「需要内であれば必ず売 れるから制約式で需要≦変数式」にするのか分か らなかった。 • 変数を削減することが面倒だと感じたので次回の先週のベスト感想(その他何でも
1)
• 今までの課題があっているか不安です。単位は 取れるか?課題の答えが会っていなければ単位 は取れないか? • 中学のときに解いた数学の問題でも同じようなも のがあったと思った。 • 表4がx1,x2じゃなくてx1(xの1倍),x2(xの2倍)に見 えて最初戸惑った。 • 定式化するのにこんなに難しいのに解も求めると なると次回が恐ろしい。先週のベスト感想(その他何でも
2)
• 将棋やってみたいと思った!はさみ将棋しかわから ない。 • 私もよく将棋をやるが棒銀しか戦法をろくに使えな いので強い人にあたるとすぐ負けてしまう。 • 藤井四段はAIなのでは?という疑問がネット上に浮 上している。面白い事を考える人もいると思った。 • 将棋よりマージャンの方が好きだ。 • 将棋以外のテーブルゲームは何かやりますか?先週のベスト感想(その他何でも
3)
• 大谷ヒット! • 久し振りに大谷のヒットが見れて嬉しかった。近 藤は今シーズン復帰厳しそうなのが残念だ。 • AKB系は毎年話題を作ってくるのが強いなって 思った。 • 加地先生とはどういうきっかけでお知り合いに なったのですか?2変数の線形計画問題
• ここで説明する製造販売計画問題は、変数が
2個の問題である。
• 2個では線形計画法は鉛筆定規で実行できる。
• 3変数以上では線形計画法は「単体(シンプ
レックス
)法」かコンピュータソフトで解く。
• 単体法は万能だが数学的に難解である。
• ソフト解法は来週Excelソルバーによる解法を
3.1 製造・販売計画
• 経営資源(ヒト,モノ,カネ)に限りある中で利益が最 大の製品の製造販売量を求める問題。 • 簿記検定では「最適セールスミックス決定」。 【例題3.1】「角大食品」はハンバーグとミートボールを 製造する。2製品の1ロット当り牛豚の使用料と利益 (万円)、1日の牛豚使用可能量を下表に示す。 製品 ハンバーグ ミートボール 使用可能量 牛肉(kg/ロット) 2 1 100 豚肉(kg/ロット) 3 6 240 利益(万円/ロット) 2 3例題
3.1の定式化1
• 製品は毎日売れるとすると利益を最大にする
にはハンバーグとミートボールを毎日何ロット
製造すれば良いか?
(解説)
• ハンバーグをx(ロット)とミートボールy (ロット)
を製造すると、総利益
z(万)はz=2x+3yである。
• この最大化(コストでは最小化)関数を
目的関
数
という。
例題
3.1の定式化2
(解説続き)
• 資源(牛肉と豚肉)には上限がある。
• 牛は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
を求めることが目的。
例題
3.1の定式化3
(定式化まとめ)
【目的関数】
z=2x+3yを最大(max)
【制約条件】
2x+y≦100、3x+6y≦240
【非負条件】
x≧0、y≧0
• 問題は線形計画問題、その解法を線形計
画法と呼ぶ。
• 制約条件を満たし目的関数を最大にする
変数を求めることが目的である。
• 制約条件(3), (4)を特に非負制約という。
• 目的関数(5)の右辺や制約条件(1), (2)の
左辺はすべて「定数×変数」の和で表され
るので、線形計画問題という。
例題
3.1の解法1
例題
3.1の解法2
• 2変数線形計画問題をはグラフを描いて解く。
• 各制約条件の対応領域を考える.
• 制約条件(1)は変形すると y≦-2x+100 となり,
下図
(a)の直線と下の領域が対応する.
• 制約条件(2)は変形すると3x+6y≦(1/2)x+40
• となり,下図(b)の直線と下の領域が対応する.
例題
3.1の解法3
• 2変数線形計画問題をはグラフを描いて解く。
• 各制約条件の対応領域を考える.
• 非負制約x≧0(3)は下図(c)の軸全体と右領域,
非負制約
y≧0(4)は下図(d)の軸全体と上領域
が対応する。
例題
3.1の解法4
• 解は全制約条件(1)~(4)を満たさないといけない。 • 4つの領域の共通部分(下図(a))の中で解を探す。 (下図(b)は(a)の拡大図である)
例題
3.1の解法6
• 拡大図(b)で四角形OABCの境界と内部が制約条 件(1)-(4)を満たす点の集まりを実行可能領域。 • 実行可能領域内の点を実行可能解。 • 目的関数を最大にする実行可 能解を探す。 • そのために目的関数を y=-(2/3)x+z/3と変形し、例題
3.1の解法7
• 下図の直線①はz/3=10(∴z=30)に対する目的 関数直線である。 • 実行可能領域内にある直線①上の点は「全制約 条件を満たしかつ利益が30万円」の点。 • 直線②はz/3=20(∴z=60)に対する目的関数直 線である。 • 実行可能領域内の 直線②上の点は「す べての制約条件を 満たしかつ利益が例題
3.1の解法8
• 切片が大きい程目的関数は大きくなるが,直線は実 行可能領域に含まれる必要である。 • 右図の点Bを通る直線③が切片値が最大の限界直 線となり目的関数を最大にする実行可能解である。 • 点Bは右図より2直線2x+y=100,3x+6y=240の交点 で,この連立一次方程式を解けばx=40,y=20となり 目的関数z=2x+3yに代入しz=140を得る。 • ハンバーグ40, ミートボ ール好きなドラマ
(その1)
朝ドラ「ひよっこ」あらすじ
1
• 1964年東京オリンピック前後茨城県の奥茨
城村に育つヒロイン谷田部みね子の物語。
• 東京出稼ぎの父を探し集団就職で上京し下
町の工場で働きながら父を探す。
• オリンピック後の不況で工場倒産で行く宛て
なく父常連の洋食屋「すずふり亭」に勤める。
• 家出しているすずふり亭の1人娘由香に祖母
好きなドラマ
(その1)
朝ドラ「ひよっこ」あらすじ
2
• 由香の感じの悪さに怒るが母の死で家庭内
不和に至る由香の思いに同情する。
• すずふり亭を訪れた綿引から新情報で実が
引ったくり犯に殴れら失踪したことを聞く。
• ビートルズファンの叔父宗男のためコン
サートチケットを入手しようと奮闘する。
• ヒロインは『あまちゃん』でヒロイン母の少女
時代を演じた有村架純を起用。
好きなドラマ
(その1)
朝ドラ「ひよっこ」キャスト
1
好きなドラマ
(その1)
朝ドラ「ひよっこ」キャスト
2
みね子友人時子 演佐久間由衣 みね子友人三男 演泉澤祐希 みね子叔父宗男 演峯田和伸好きなドラマ
(その1)
朝ドラ「ひよっこ」キャスト
3
今日の課題
1:
栄養問題
• 成人が1日に必要な熱量(kcal)、蛋白質(g)、カル シウム(mg)、各食品100gに含まれる栄養素、各 食品100gの値段が表1に与えられている。 表1 各食品に含む栄養素と値段 • 各栄養素を摂取し最小食 費にする食パンと牛乳の 量を図的解法で求めなさ い。今日の課題
1:
栄養問題
(回答)
表1 各食品に含む栄養素と値段 図的解法 定式化:食パンx, 牛乳y(×100g) とする。 目的関数:z=40x+25y → min 制約式:今日の課題
2:
余暇問題
1
• 麻雀とテニスの好きな人がいる。週末に麻雀とテ ニス1回当たりの時間、費用、満足度を表2に示す。 • 余暇時間は16時間、 費用は2万円とすると き、満足度を最大にす る麻雀とテニスの回 数を図的解法で求め なさい。 表2 各余暇の時間と費用今日の課題
2:
余暇問題
1(回答)
定式化:麻雀x, テニスy(回)とす る。 目的関数:z=5x+6y → max 制約式: 4x+2y≦16 図的解法 最適解 表2 各余暇の時間と費用今日の課題
3:
余暇問題
2
• 課題2の余暇問題において、麻雀とテニスの満足 度がそれぞれ2と6に変わったときの最適解を図 的解法で求めなさい。