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

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

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

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

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

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

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

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

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

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

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

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

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

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

13 例題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とその下の領域(次頁図中桃色)が対応する。

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

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

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

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

18 例題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 目的関数最大化する実行可能解探索

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

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

21 Coffee break 2015/7/3

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

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

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

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

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

27 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で一致）。

28 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

29 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

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

31 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= …(3.14) 2015/6/12

32 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

33 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

34 3.2 輸送問題の変数削減4 以上をまとめると，例題2は制約条件 x+y≧ 3 …(3.19) x+y≦ 10 …(3.20)
3.2 輸送問題の変数削減4　 以上をまとめると，例題2は制約条件 　 x+y≧ …(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

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

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

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

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

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

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

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

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

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

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

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

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

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