ORの手法(線形計画法1)
社会情報特講Ⅲ
先週のベスト感想（講義で分った事）
• エクセルを使うと自分で計算するよりも断然楽であ ることが分かった。 • スニッピングツールが使いやすい。 • アドイン等不慣れな言葉がでたがソルバー自体は 分かりいいもので数値を入力するのが楽しかった。 • 制約式とか操作の仕組みを覚えるのが大変だった が一度できると簡単！ • 丁寧にやり方を教えてもらったのですぐできました。 • 手計算ではなかなか難しい組み合せ問題もエクセ ルを用いれば簡単だとわかった。ベスト感想（講義・課題で難しかった事）
• 解がおかしいときに自分がどこを間違えて入力した のか探すのが大変だった。 • アドインからソルバーを適用するのに方法が分から ず時間がかかった。 • 課題によりソルバーで選ぶセルが違ったのでその 選別に苦労した。 • コンサート課題の目的関数が見つからなかった。 • ソルバーを初めて使ったので使い方が難しかった。 • 制約式の設定を自分でやるとなるとなかなかできな いと思った。先週のベスト感想（その他何でも
1）
• エクセルが便利で毎回実習が楽しいです。 • エクセル最高！ • 手計算より確実で早く解けるので積極的に使って いきたい。 • ソルバーを他のことにも活用できたら良い。 • 簡単に計算できるが故に本当にこれが最適なの か疑ってしまった。 • Excelのバージョンが違うと操作手順が大分違う ので少し困った。先週のベスト感想（その他何でも
2）
• スライドアップのURL(http://oohorisemi･･･)をmanaba からリンクを踏んで移動できるようにして下さい。 • 解説を増やしてほしい。 • 交流戦お疲れさまでした。 • NMB48須藤さん結婚しますね！ • 乃木坂46のことをほとんど知らなかったのですが、 この講義のお陰でメンバーの名前だけ覚えました。 • 今日は雨で電車が止まってしまい大変でした。 • コーヒーブレイクを楽しみにしていました。線形計画法とは
• 特定分野の特殊問題を解く方法ではない。
• 様々な分野の使い道の広い最適化問題を解
く手法である。
• 例えば資源に限りがある中で利益を最大に
する生産計画を立てる問題がある。
• また幾つかの供給地から幾つかの需要地に
物品を、需要地の需要量を満たし総輸送費を
最小にする輸送計画を立てる問題がある。
2変数の線形計画問題
• ここで説明する製造販売計画と輸送問題は、
変数が
2個（または2個に削減）問題である。
• 2個では線形計画法は鉛筆定規で実行できる。
• 3変数以上では線形計画法は「単体(シンプ
レックス
)法」かコンピュータソフトで解く。
• 単体法は万能だが数学的に難解である。
• ソフト解法は付録でExcelソルバーによる解法
3.1 製造・販売計画
• 経営資源（ヒト,モノ,カネ）に限りある中で利益が最 大の製品の製造販売量を求める問題。 • 簿記検定では「最適セールスミックス決定」。 【例題3.1】「角大食品」はハンバーグとミートボールを 製造する。2製品の1ロット当り牛豚の使用料と利益 （万円）、1日の牛豚使用可能量を下表に示す。 製品 ハンバーグ ミートボール 使用可能量 牛肉（kg/ロット） 2 1 100 豚肉（kg/ロット） 3 6 240 利益（万円/ロット） 2 3例題
3.1の解き方
• 製品は毎日売れるとすると利益を最大にする
にはハンバーグとミートボールを毎日何ロット
製造すれば良いか？
（解説）
• ハンバーグをx(ロット)とミートボールy (ロット)
を製造すると、総利益
z(万)はz=2x+3yである。
• この最大化（コストでは最小化）関数を
目的関
数という。
例題
3.1の解き方1
（解説続き）
• 資源（牛肉と豚肉）には上限がある。
• 牛は1日2x+y（kg）必要で100kgが
限度。
• 豚は1日3x+6y（kg）必要で240kgが
限度。
• xとyに負の値はありえない。
• 以上の条件を
制約条件という。
例題
3.1の解き方2
【制約条件】
2x+ y≦100 (3.1)
3x+6y≦240 (3.2)
【非負条件】
x≧0、y≧0 (3.3),(3.4)
のもとで、
【目的関数】
z=2x+3y (3.5)
を最大にする
x,yを求めることが目的である。
• この問題は線形計画問題といい、その解法
を線形計画法と呼ぶ。
• 定式化で目的関数や制約条件の左辺はす
べて「定数×変数」の合計で表される。
• 変数の1次式なので線形計画問題といい、そ
の解法を線形計画法という。
例題
3.1の解き方3
例題
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の解き方6
• 問題の解はすべての制約条件(3.1)～(3.4)を満た さないといけないので4つの領域の共通部分（図 3.2(a)）の中で解を探す。
例題
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.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ロット製造し利益例題
3.1の解き方11
• 最大化（または最小化）問題において目的関 数を最大（または最小）にする実行可能解を最 適解という。 • 例題3.1では(x,y)=(40,20)が最適解である。 • 得られる解は理論解であり実用解であるか常 に検討すべきである。 • 例題3.1の最適解は整数値が得られ「12ロット ずつ」などの出荷単位の指定もないので実用 解である。好きなゲーム
1(将棋)
将棋との出会い
• 始めたのは4才頃で、父が電気工 事会社の親分で、多くの若い電工 さんが我が家に出入りしていた。 • 電工さん達で将棋が流行り、私も 仲間に入れてもらった。 • 20代の若者に勝てるはずがなく、 連戦連敗だったが、負けず嫌いで 何度も挑戦するが負け続け、やが て相手にされなくなる。 昭和の将棋盤好きなゲーム
1(将棋)
その後の将棋人生
• 中学の頃までは主に親戚のおじさ んと遊びで将棋をやり、勝敗も5分 だった。 • アマ初段くらいか？ • 高校の頃から囲碁の方に興味が 移り、年に2回主に親父相手に囲 碁を遊ぶ。 • アマ3級くらいか？ • 最近は両方ほとんどプレイしない。 昭和の囲碁盤好きな将棋棋士
1
升田九段
• 14歳にして家出した時母の物差し に書き残したのが「名人に香車を引 いて勝てば大阪へ行く」の一文。 • 香車を引く=自分の香車を落とすハ ンデをつけて対局。 • 五期王将戦で再度大山名人を香落 ちで3連勝。 • 「新手一生」を掲げ、升田式石田流、 駅馬車定跡、角換わり腰掛け銀の 升田定跡など多くの新手を発明。 升田幸三九段好きな将棋棋士
2
藤井四段
• 2002年7月愛知県瀬戸市生まれの現在 中学3年。昨年10月史上5人目の中学生 プロ棋士。 • 史上最年少棋士でデビュー以来無敗で 6月26日竜王戦1回戦で増田四段に勝 利し歴代1位の29連勝を達成。 • 劣勢に陥ることもあるが対戦相手は「ス キのない将棋」と口を揃える指し手。 • 14才の快進撃はメディアに大きく取り上 げられ社会現象となる。 藤井聡太四段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小売店の需要を満たす中で総輸送費を最小に する各ルートの輸送量を求めよ。 輸送費 （万円/t） Cデパー トへ D百貨店 へ Eスーパー へ A工場から 1 2 5 B工場から 4 3 2 表3.2 各ルートごとの1t当りの輸送費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を満たす。
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)
⇒最小化
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)
• (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を得る。
3.2 輸送問題の変数削減2
• (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)
3.2 輸送問題の変数削減3
• 以上をまとめると，例題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を求める問題に変形できる。
3.2 輸送問題の変数削減4
3.3 レジャー選択問題
• 夏休み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)、各食品100ｇに含まれる栄養素、各 食品100ｇの値段が表1に与えられている。 表1 各食品に含む栄養素と値段 • 各栄養素を摂取し最小食 費にする食パンと牛乳の 量を求める線形計画問題 を定式化せよ。今日の課題
1：
栄養問題
(回答)
表1 各食品に含む栄養素と値段
変数定義
目的関数
今日の課題
2：
余暇問題
• 麻雀とテニスの好きな人がいる。週末に麻雀とテ ニス１回当たりの時間、費用、満足度を表2に示す。 • 余暇時間は16時間、 費用は2万円とすると き、満足度を最大にす る麻雀とテニスの回 数を求める線形計画 問題を定式化せよ。 表2 各余暇の時間と費用今日の課題
2：
余暇問題
(回答)
変数定義
目的関数
制約式(非負条件含) 表2 各余暇の時間と費用
