Microsoft Word - Ⅴ表紙

Transcription

1 ISSN No Excel による経済 経営分野の情報処理 Ⅴ 線形計画問題 2007 年 12 月 10 日作成 2010 年 5 月 12 日修正 目 次 1. はじめに 線形計画問題とは 2. 簡単な線形計画問題 3. やや複雑な線形計画問題 4. おわりに参考文献練習問題 Faculty of Economics, Wakayama University

2 ( 表紙裏 )

3 1 Excel による経済 経営分野の情報処理 Ⅴ 線形計画問題 2007 年 12 月 10 日牧野真也 2010 年 5 月 12 日修正 1. はじめに 線形計画問題とは 私たちは何かをしようとするとき, しばしば事前にその計画を立てます とくに, 企業や政府などの大きな組織においては, 実際の業務の実行に先だって, 適切な計画を立てたり, そのためのシステムを設計したりすることがきわめて重要です こうした計画は, 通常難しい問題を含んでいますが, これらの一部は, 最適化問題として定式化し計算によって解を求めることができます たとえば数理計画法では, 数式で与えられた制約の下で, 目的とする関数を最大化 ( あるいは最小化 ) する問題が扱われます これは, 生産や流通の計画などさまざまな場面で使われます 数理計画法が扱う問題やそのための手法にはいくつかありますが, ここでは, それらの中でも簡単な線形計画問題を扱うことにします 線形計画問題とは, 一次の制約式 ( 等式, 不等式 ) の制約のもとで, 一次式の目的関数の値を最適化 ( 最大化, 最小化 ) するような変数の値を求める方法です 一次式の形状は2 次元平面上では直線ですから, 線形 (linear) と名前が付いています 簡単な線形計画問題は, 手計算でも容易に解くことができ, もちろん Excel を使っても簡単に計算できます さらに Excel の ソルバー を使えば, 複雑な問題でも定式化さえうまくできれば, 後は Excel が計算してくれます ソルバーは最適化問題を一般的に解くことができるので, 線形計画問題に限らずさまざまな問題を解くこともできます 以下, 実際のいくつかの例題をもとに Excel を使った線形計画問題の解き方をみていきます

4 2 和歌山大学経済学部,Working Paper Series,No.07-08(2007 年 12 月 ) 2. 簡単な線形計画問題 線形計画問題はある決まった形で記述できます 簡単な例題でみてみましょう これは生産計画と呼ばれている問題です 例題 1( 生産計画 ) あるチョコレート工場では, ビターチョコレートとマイルドチョコレートという 2 種類の板チョコを生産しています ビターチョコレートを 1 ケース生産すると 2 万円の利益があり, マイルドチョコレートを 1 ケース生産すると 3 万円の利益があります また, ビターチョコレート 1 ケースを生産するためには原料としてカカオ豆 4kg と砂糖 1kg が必要であり, マイルドチョコレートを 1 ケース生産するためにはカカオ豆 3kg と砂糖 2kg が必要です 一方,1 日に使える原料には限りがあり, カカオ豆は 120kg で砂糖は 60kg です このとき,1 日あたりの利益を最大にするためにはビターチョコレートとマイルドチョコレートをそれぞれ何ケース生産すればよいでしょう この例題 1 は以下のような線形計画問題として, 定式化できます ( きちんと書くことができます ) 1 日のビターチョコレートの生産量を x ケース, マイルドチョコレートを y ケースとします すると, 利益は 2x 3y 万円となります この式 (x, y の関数 ) の値を最大にすることがこの問題の目的です この関数を 目的関数 と呼びます また,1 日の原材料カカオ豆の使用量は 4x 3y kg となりこの値は 120kg 以下でなければなりません 同様に砂糖の使用量 x 2 y kg も 60kg 以下である必要があります さらに,x, y は生産量ですから負の値になることはありません これらは, 必ず満たさなければならない制約ですから 制約条件 と呼ばれます とくに変数が負でない条件は 非負条件 と呼ばれます これらを, 数式を使って記述すると以下のようになります 目的関数 : 2 x 3y 最大化 制約条件 : 4x 3y 120 x 2 y 60 ( 非負条件 ) x, y 0

5 Excel による経済 経営分野の情報処理 Ⅴ 線形計画問題 3 グラフによる解法線形計画問題の解き方はいろいろあります この問題は変数が 2 つしかない簡単な問題なので, 中学校までの数学の知識で十分に解くことができます まず, 制約条件を満たす領域を x y 平面に図示してみましょう 2 つの制約条件の直線 : 4x 3y 120 と x 2 y 60 の交点は (12,24) ですから ( 計算して確認してください ), 以下の図 1 の四角形 ABCO( 網掛けの部分 ) が制約条件を満たす領域となります y A (12, 24) B C x 図 1 例題 1 の制約条件を満たす領域と目的関数 この領域内で目的関数 2x 3y が最大になる (x, y) を求めます 2x 3y k とおくと, 2 k 2 y x であるので, この領域を通る傾き の直線で,y 切片が最 大になるものを求めることができれば, その領域と直線の交わっているところ 2 が解となります この直線の傾き は, 領域をつくる 2 つの直線の傾き, それ ぞれ と の間になるので, 図 1 のように点 (12,24) を通る場合に目的関数 3 2 が最大となり, 最大値はこれを目的関数に代入し, となります つまり,1 日あたりビターチョコレート 12 ケースとマイルドチョコレート 24 ケースを生産すれば, 最大の利益 96 万円を得ることができるわけです この解法に基づいて Excel で計算してみましょう 以下の図 2 のワークシートでは,4 行目までで目的関数の係数や制約条件の係数 定数を対応関係がわかるように与えています そして,6 行目以降では, 図 1 の点 A,B,C つまり制約条件の直線と y 軸との交点,x 軸との交点, 制約

6 4 和歌山大学経済学部,Working Paper Series,No.07-08(2007 年 12 月 ) 条件の直線同士の交点を計算しています 線形計画問題では, 制約条件を満たす領域は直線で囲まれていて, その領域との関係をみる目的関数も直線です そのため, それらの傾きを比較しなくても, 最適解は必ず A,B,C の 3 点のいずれかとなります したがって,ABC 各点の x,y 値に基づいて目的関数の値を計算し最大になるところを求めればよいわけです 点 A と点 C は簡単に計算できますね たとえば, 点 A(y 軸との交点 ) は y 軸と直線 x 2 y 60 の交点ですから,x=0 であり,y=60 2 で計算できます したがって, セル C7 に入る式は =D4/C4 となります 点 B( 制約式交点 ) は 2 つの直線の 2 元 1 次の連立方程式を解くことで求め られます 連立方程式 ax by e cx dy f の解は, ad bc 0 のとき存在し, de bf af ce x, y ですから, そのままセルの式にすればよいだけです ad bc ad bc セルに入れる式はみなさんで考えてみてください この場合, 解をもたなくてもエラーになるだけですから ad bc 0は無視してもよいかもしれません なお, Excel には逆行列を計算する関数もありますが, この場合は簡単ですから使わなくてもよいと思います A B C D 1 ビター マイルド 制約条件 2 利益 カカオ豆 砂糖 x y 目的関数の値 7 y 軸との交点 x 軸との交点 制約式交点 目的関数の最大値 96 図 2 生産計画の Excel による解 正しく式を入れて計算すれば, 図 2 のような結果が得られると思います 手計算と同じ結果になることを確認してください

7 Excel による経済 経営分野の情報処理 Ⅴ 線形計画問題 5 Excel のソルバーによる解法 Excel のソルバーを使ってこの線形計画問題を解くことができます ソルバーを使えば, 線形計画問題に限らず, いくつかの最適化問題を解くことができます 以下みていきましょう ソルバーは, あるセルの値が最適 ( 最大, 最小, 特定の値 ) になるように, 複数のセルの値を変化させてくれるツールです その際に満たすべき制約条件を指定することもできます [ データ ] タブ [ 分析 ] グループの [ ソルバー ] を選ぶと以下のようなダイアログボックスがあらわれます 1 図 3 ソルバーのダイアログボックス ここで,[ 目的セル ] には値を最適化するセルを指定します [ 目標値 ] のラジオボタンで, それを最大化するのか, 最小化するのか, 特定の値に近づけるのかを指定します [ 変化させるセル ] に, そのセルの値を変化させることによって [ 目的セル ] を最適化するセルを入れます [ 制約条件 ] にはその際の制約条件を入れます これら [ 目的セル ] [ 変化させるセル ] [ 制約条件 ] が, 線形計画問題の目的関数の値 変数 制約条件に対応します まず, きわめて簡単な例でソルバーを説明しましょう いま, y x ( x 2) の y を最大化する x を求めてみます 当然ながら答えは x 1のとき y 1になりますね この場合, セル A1 に =-B1*(B1-2) と式を入 1 [ データ ] タブ [ 分析 ] グループに [ ソルバー ] がない場合は,[Office ボタン ] の [Excel のオプション ] [ アドイン ] の [ 管理 ] 欄で Excel アドイン を選択し [ 設定 ] ボタンをクリック,[ アドイン ] ダイアログから [ ソルバーアドイン ] を選択します それもない場合は,Excel の CD-ROM などからインストールしてください

8 6 和歌山大学経済学部,Working Paper Series,No.07-08(2007 年 12 月 ) れておき, ソルバーでセル A1 を目的セルに, 目標値を最大値に, セル B1 を変化させるセルに指定します つまり, セル A1 を y にセル B1 を x にしているわけです その上で, ソルバーに以下のように式を入れて ( もちろんマウスクリックやドラッグで入力できます ) 実行すれば, セル A1 の値は 1 にセル B1 は 1 になります A B 1 =-B1*(B1-2) 図 4 簡単な例のワークシート 図 5 簡単な例のソルバー では, 例題 1 の生産計画の問題をソルバーで解いてみましょう やり方は何通りもありますから, ここで示すのは 1 つの例にすぎません たとえば, 以下のようなワークシートをつくります A B C D E F 1 ビター マイルド 利益 2 目的関数 変数 4 制約 制約式の値 上限 5 カカオ豆 <= 砂糖 <= 60 図 6 ソルバーで生産計画を解くためのワークシート

9 Excel による経済 経営分野の情報処理 Ⅴ 線形計画問題 7 セル B3 と C3( 黄色のセル ) にビターチョコレートとマイルドチョコレートのケース数つまり変数を入れることにします もちろん, この値はソルバーが計算してくれるので何も入れる必要はありません セル D2( 水色のセル ) には, 利益つまり目的関数の値を入れます これは 2x 3y ですから, =B2*B3+C2*C3 と式を入れることになります 次に, 制約式ですが, これはいろいろな入れ方があります 基本的な方針として, なるべくワークシート上で計算するようにして, ソルバーの入力は最小限にするようにします そうすることで作業が簡単になります ここでは, 制約条件の左辺の値を予め計算しておき, それをセル D5,D6 に入れておきます たとえば,D5 の式は, 4x 3y ですから =B5*B3+C5*C3 となります D6 も同様に式を入れます ( みなさんで考えてください ) 最後にソルバーを起動して, 目的セル ( 最大化 ) に D2 を, 変化させるセルに B3:C3 をそれぞれマウスクリックやドラッグで指定します そして, 制約条件を追加します 制約条件の [ 追加 ] ボタンをクリックします 以下の図 7 のようなダイアログボックスがあらわれるので,[ セル参照 ] のところに制約式の値を [ 制約条件 ] のところに上限を以下の図 7 のように入れます ( もちろんマウスドラッグで入れられます ) ここでは セル範囲 <= セル範囲 のような式 ( 不等式や等式 ) をつかって制約条件をまとめて入れることができます 2 なお, 関係子 <= の部分はプルダウンになっていて,= や >= などに変更できます 図 7 制約条件の入力 制約条件の入力を終えて [OK] あるいは [ 追加 ] をクリックすると, その制約条件が追加されます 3 最終的には, ソルバーのダイアログボックスは以下の図 8 のようになります ( 非負条件も同様の方法で入力しています ) そして,[ 実行 ] をクリックすると 2 もちろん, それぞれの制約条件を 1 つずつ入れてもかまいません 3 制約条件の追加 ダイアログボックスの セル参照 ( 左側 ) には数値は入れられません また, 制約条件 ( 右側 ) に数値を入れると, 入力された参照が正しくない という警告が出る場合がありますが, 制約条件は正しく入力されます 予めその数値を入力したセルを準備しておけば, この警告を回避できます

10 8 和歌山大学経済学部,Working Paper Series,No.07-08(2007 年 12 月 ) 解が計算されます 解が見つかると図 9 のようなダイアログボックスがあらわれるので, 解を記入します 図 8 ソルバーの設定 図 9 最適解が見つかった場合のダイアログボックス A B C D E F 1 ビター マイルド 利益 2 目的関数 変数 制約 制約式の値 上限 5 カカオ豆 <= 砂糖 <= 60 図 10 ソルバーの実行結果 その結果のワークシートは図 10 のようになります グラフによる解法と結果が同じになることを確認してください

11 Excel による経済 経営分野の情報処理 Ⅴ 線形計画問題 9 目的関数を最小化する問題ここまでみた生産計画の問題は, 利益を最大にするという問題であり, 目的関数を最大化する問題でした 一方, 目的関数を最小化する問題ももちろんあります たとえば, 目的関数がコストである場合などがそうです 以下, 栄養問題と呼ばれる線形計画問題をみてみましょう 例題 2( 栄養問題 ) サプリメント X の 1 粒にはビタミンαが 4mg, ビタミンβが 1mg 含まれています 一方, サプリメント Y の 1 粒にはビタミンαが 3mg, βが 2mg 含まれます 1 日に必要な量はビタミンαが 120mg 以上,β が 60mg 以上です サプリメント X の価格が 1 粒 2 円, サプリメント Y が 3 円であるとき, 最小の支出で 1 日の必要量を満たすには, それぞれ何粒ずつ摂取すればよいでしょう この問題は, サプリメント X を x 粒,Y を y 粒とすれば, 以下のように定式化できます 目的関数 : 2 x 3y 最小化 制約条件 : 4x 3y 120 x 2 y 60 ( 非負条件 ) x, y 0 これは, 例題 1 と同様に, グラフでもソルバーでも解くことができます ソルバーで解く場合は,[ 目的セル ] の [ 目標値 ] が最小化,[ 制約条件 ] の不等号が反対になります みなさんで試してみてください また, この問題は例題 1 と同じ答えになります 定式化した数式の形をみても, 例題 1 の最大化を最小化に変えて, 制約条件の不等号を変えれば全く同じ問題なります

12 10 和歌山大学経済学部,Working Paper Series,No.07-08(2007 年 12 月 ) 3. やや複雑な線形計画問題 前節の線形計画問題は変数が 2 つしかない簡単な問題ですから, 平面にグラフを書いて考えることができました 変数の数がもっと多い場合の一般的な解法もシンプレックス法などいくつか提案されています シンプレックス法は, 制約条件がつくる n 次の多面体 (2 次の場合は多角形でした ) の頂点に必ず解があることを利用して, 解を効率よく探索します ここでは, シンプレックス法は取り上げず,Excel のソルバーを使ってもう少し複雑な線形計画問題を解いてみます 例題 3( 輸送計画 ) ある会社は,3 つの工場と 5 つの直売店をもっています 各工場で作られた製品は各直売店に輸送されて販売されます 各工場 ( 工場 1, 工場 2, 工場 3) は 1 日あたり以下の量の製品を出荷できます 工場の出荷可能量工場 1 工場 2 工場 また, 各直売店の 1 日あたりの製品の発注量は以下のようになっています 直売店の発注量直売店 1 直売店 2 直売店 3 直売店 4 直売店 製品の輸送にかかるコストは, 工場と直売店の組み合わせによって決まります 各工場から各直売店への製品の輸送単価 ( 製品 1 単位あたりの輸送に要するコスト ) は以下のようになっています 輸送コスト 直売店 1 直売店 2 直売店 3 直売店 4 直売店 5 工場 工場 工場

13 Excel による経済 経営分野の情報処理 Ⅴ 線形計画問題 11 最小の輸送費用で, 直売店の発注を満たすためには, どの工場からどの直売店へどれだけの製品を送ればよいですか 4 この問題は輸送計画と呼ばれ, 複数の供給地から複数の需要地への輸送に際して需要地と供給地間の輸送単価が与えられている場合にコストを最小化する問題です 輸送計画は一般に以下のように記述することができます 供給地を i ( i 1,2,, k) とし, 需要地を j ( j 1,2,, l) とします 供給地 i の供給量を si, 需要地 j の需要量を dj とします また, 供給地 i から需要地 j への輸送量を xij とし, 同じく i から j への輸送コストを cij とすると, この問題は,xij を変数として輸送コストの総額を最小化する問題であり, 以下のように定式化できます 目的関数 : 制約条件 : k l i 1 j 1 l j 1 k i 1 c ij x ij 最小化 xij s, i 1,2,, k i xij d, j 1,2,, l j ( 供給量から ) ( 需要量から ) x ij 0, i 1,2,, k, j 1,2,, l ( 非負条件 ) 制約条件の 1 番目の式は, 各供給地の供給量が可能な範囲に収まっていることを示しています 2 番目の式は, 各需要地の需要量を満たしているということです では例題 3を, ソルバーを使って解いてみましょう もちろん, 解き方はいろいろあります ここで示すのは 1 つの例です 以下の図 11 のようなワークシートをつくります 上の表の B3:F5( 黄色の部分 ) はそれぞれの工場から直売店への出荷量であり, この問題の変数です (Excel が値を決めます ) B6~F6 はそれぞれ直売店別の出荷量の合計です G3~G5 は工場別の出荷量の合計です ( それぞれのセルに入れる式は自明ですね ) たとえば, 工場別の出荷量の合計は, それぞれの出荷可能量を超えないことが制約条件の 1 つですから, その制約条件をソルバーに入れ 4 この問題の数値は, 高井 真鍋 (2000)66-67 ページを参考に一部変更したものです

14 12 和歌山大学経済学部,Working Paper Series,No.07-08(2007 年 12 月 ) る準備として予め合計を求めておきます 目的関数は, 変数と輸送単価の各要素の積の合計です 同形のセル範囲同士のそれぞれの対応する要素の積和を求める関数 SUMPRODUCT を使います ( セル B9) たとえば,SUMPRODUCT(A1:B2, C1:D2) は,A1*C1+A2*C2+B1*D1+B2*D2 を計算します A B C D E F G H 1 変数 2 直売店 1 直売店 2 直売店 3 直売店 4 直売店 5 工場別計出荷可能 3 工場 工場 工場 店別計 発注量 輸送コスト =SUMPRODUCT(B3:F5,B11:F13) 10 直売店 1 直売店 2 直売店 3 直売店 4 直売店 5 11 工場 工場 工場 図 11 輸送計画のワークシート ソルバーを起動して, 目的セル, 変化させるセル, 制約条件を入れます 以下の図 12 のようになることがわかりますか

15 Excel による経済 経営分野の情報処理 Ⅴ 線形計画問題 13 図 12 輸送計画のソルバーの設定 ソルバーを実行すると, 変数 ( 輸送量 ) は以下の表のようになり, 輸送コストの総額は 2460 になるはずです みなさんの結果が正しいことを確認してください ( 解はいくつかあるかもしれません ) 直売店 1 直売店 2 直売店 3 直売店 4 直売店 5 工場 工場 工場 図 13 輸送計画の結果 最後に, 輸送計画とよく似た問題である割当計画をみてみましょう 例題 4( 割当計画 ) あるプロジェクトチームには 3 人のメンバーがいます それぞれのメンバーはそれぞれが得意とするタスク ( 仕事 ) があり, 受けもつタスクによってそのパフォーマンス ( 能力発揮の程度 ) が違います たとえば, 語学が得意な人もいれば, 計算が得意な人もいるでしょう それを, 以下の図 14 のようにまとめられたとします タスク 1 タスク 2 タスク 3 メンバー メンバー メンバー 図 14 メンバーが受けもつタスクによるパフォーマンス

16 14 和歌山大学経済学部,Working Paper Series,No.07-08(2007 年 12 月 ) プロジェクトチーム全体のパフォーマンスを最大化するためには, どのメンバーにどのタスクを担当させればよいでしょうか ただし, メンバー 1 人が 1 つのタスクをその人だけで受けもつものとします 5 この問題は割当計画と呼ばれ, 複数のタスクを複数の担当者に割り当てるときに最適な割り当て方を求める問題です 割当計画は一般に以下のように記述できます 簡単のために 1 人の担当者が 1 つのタスクを排他的に受けもつものとします 担当者を i ( i 1,2,, k) とし, タスクを j ( j 1,2,, l) とします 担当者 i がタスク j を担当するかどうかを xij で表わし, 担当する場合 xij =1, しない場合 xij =0 とします また, 担当者 i がタスク j を担当した場合の利益を bij とします すると, この問題は,xij を変数として利益の総額を最大化する問題であり, 以下のように定式化できます 目的関数 : 制約条件 : k l i 1 j 1 l j 1 k i 1 x x b ij x ij 最大化 ij 1,, i 1,2, k ij 1,, j 1,2, l ( 各担当者に 1 つのタスク ) ( 各タスクに 1 人の担当者 ) x ij 0, i 1,2,, k, j 1,2,, l ( 非負条件 ) また, 変数 xij は,0 または 1 の値しかとりません これも重要な制約の1つでしょう x {0,1} (xij は,0 か 1 のいずれか ) ij このように解が整数値に限定される線形計画問題は, しばしば整数計画問題と呼ばれます これまで解いてきた問題も, 厳密に考えれば解は整数に限定されるのかもしれません ( 生産量や輸送量に 35.6 個のような小数は認められないこともあるでしょう ) 整数計画問題もソルバーを使って適切に解くことができます では, 例題 4を, ソルバーを使って解いてみましょう 輸送計画とほぼ同様に解くことができます 5 この問題は中央情報教育研究所 (1994)59-60 ページを参考に作成しました

17 Excel による経済 経営分野の情報処理 Ⅴ 線形計画問題 15 たとえば, 以下の図 15 のようなワークシートをつくります 輸送計画と同様に B3:D5( 黄色の部分 ) がこの問題の変数です メンバー別 タスク別に合計をとっています 目的関数も同様に変数とパフォーマンスの積和を SUMPRODUCT で計算します ソルバーを起動して, 目的セル, 変化させるセル, 制約条件を入れます 以下の図 16 のように目的セルは最大化されます 制約条件にはメンバー別, タスク別の合計が 1 になることをいれています なお, 変数の値が 0 か 1 という制約は, 以下の図 17 のように制約条件のダイアログボックスで [ データ区間 ] を選択すれば, 設定できます A B C D E 1 変数 2 タスク 1 タスク 2 タスク 3 計 3 メンバー メンバー メンバー 計 パフォーマンス 0 9 タスク 1 タスク 2 タスク 3 10 メンバー メンバー メンバー 図 15 割当計画のワークシート

18 16 和歌山大学経済学部,Working Paper Series,No.07-08(2007 年 12 月 ) 図 16 割当計画のソルバーの設定 図 17 制約条件のバイナリでの設定 ソルバーを実行すると, 変数は以下の図 18 のようになり, パフォーマンスは 16 になるはずです みなさんの結果が正しいことを確認してください 6 タスク 1 タスク 2 タスク 3 メンバー メンバー メンバー 図 18 割当計画の結果 なお, 変数の値が整数であるという制約は, 以下の図 19 のように制約条件のダイアログボックスで [ 区間 ] を選択すれば, 設定できます 6 ソルバーは近似的に最適解を求めているので, わずかな誤差が出ることがあります たとえば 0 になるべきところが,1.23E-15(= ) のようにきわめて微少な値になることがあります 気になるのであれば, 表示形式を変えるなどして対処してください

19 Excel による経済 経営分野の情報処理 Ⅴ 線形計画問題 17 図 19 制約条件のバイナリでの設定

20 18 和歌山大学経済学部,Working Paper Series,No.07-08(2007 年 12 月 ) 4. おわりに 以上,Excel による線形計画問題の解き方についてみてきました ソルバーを使えば線形計画問題に限らず, 整数計画問題などさまざまな最適化問題を解くことができます もちろん, ここでの説明は最小限にとどめています もしソルバーを使う機会があればいろいろと試してみてください 参考文献中央情報教育研究所 (1994) 第二種共通テキスト9 産業社会と情報化 伊賀隆 (1979) 経営のための数学入門 同文館 森哲夫 (1994) 数理計画法 共立出版 高井英造 真鍋龍太郎編著 (2000) 問題解決のためのオペレーションズ リサーチ入門 日本評論社

21 Excel による経済 経営分野の情報処理 Ⅴ 線形計画問題 19 練習問題 問題 1 本文中の各例題を, ソルバーを使って解きなさい (1) 例題 1( 生産計画 ) (2) 例題 2( 栄養問題 ) (3) 例題 3( 輸送計画 ) (4) 例題 4( 割当計画 ) 問題 2( 購買計画 ) ある工場では, それぞれ別の鉱山から採掘される鉱石 A, 鉱石 B を購入しています 鉱石 A の 1kg 中には, 金 10g, 銀 40g が含まれます 同様に鉱石 B には金 5g, 銀 30g 含まれます 鉱石 A は 1kg あたり 10 万円,B は 6 万円です その工場では,1 日に金 1.0kg, 銀 4.5kg が必要です 購入費を最も少なくするためには, 鉱石 A,B をそれぞれ何 kg 購入すればよいでしょうか (1) この問題を線形計画問題として定式化しなさい (2) この問題を Excel で解きなさい 問題 3 あるサークルが, 同じ電車の5つの駅 A,B,C,D,E のそれぞれに隣接する会場でイベントを開催しています しかし, 当日, 来客数の予想が外れ, スタッフが足りない会場と余っている会場ができてしまいました いま, 会場 A は 12 名,E は 16 名スタッフが余っています 一方,B は 10 名,C は 14 名,D は 4 名足りません そのため, スタッフを適切に電車で移動させこの問題を解消したいと考えています 電車の運賃が以下の運賃表のようであるとき, どの会場からどの会場へ何人移動させると最も運賃が安くなるでしょうか Excel のソルバーを使って解きなさい 解が複数ある場合は, どれか1つを示しなさい 運賃表 ( 単位 : 円 ) E D 150 C B A

22 ISSN 非売品 Faculty of Economics, Wakayama University