— ベスト・ミックスを探せ ! 第 1 章線形計画法

２００７年度前期

オペレーションズ・リサーチ 講義資料

東北大学大学院経済学研究科 鈴木賢一

3

第

1

—

!

この章では，線形計画法(Linear Programming, LP)の基礎を学びます．LPは，

ORの基本的なツールの一つです．ここから派生した様々なツールが存在します．

LPには数多くの応用例が存在しますが，まずは「ベスト・ミックス」を見つけ る方法なのだと理解してください．

1.1

1.1.1

あなたの所属するサークルでは，毎年大学祭でクッキーをつくって販売しています．経済学部 に所属しているからという根拠の薄い理由で，今年のクッキー屋の責任者はあなたに決まってしま いました．責任者は，商品の選択，原材料の調達，当日のスケジュール調整，売上の管理まで，ほ とんどすべてを引き受けなくてはなりません．仕事はどれもたいへんそうですが，将来経営者にな ることを夢見ているあなたは，これも一つのトレーニングだと，前向きに考えることにしました．

さいわい，このサークルでは毎年クッキーの販売をしているおかげで，経験の蓄積があります．

基本的な営業方針はほぼ決まっています．

方針1. お店はテイクアウト専用

方針2. 実演販売はしない（というかできない）ので，商品はあらかじめつくっておく 方針3. お金儲けが目的ではないが，最終的な損益は黒字にしたい

方針4. 作るクッキーの種類は，チョコチップクッキー，ブラウニー，ショートブレッド，ジン ジャークッキーの4種類．

方針5. 合わせて1000枚つくる．

まず決めることは，4種類のクッキーをそれぞれどれくらい作るか，です．最初に費用に着目 してみました．原材料は，表1.1の通りです．ただし，バニラエッセンスや，ベイキングパウダー，

塩などは省いてあります．単純に材料費だけに着目すると，ジンジャークッキーがもっとも安いこ とから，それを多く作るのがよいようにみえます．本当にそうすべきでしょうか?

クッキーは事前に作っておく必要があり，そのためには当然作業の時間がかかります．原材料 費も大事ですが，むしろ学生にとっては作業時間の方が考慮すべき要因であるようです．作業時間 は，大まかに見積もって表1.2のようになります．¹

1材料，作業時間は，http://allrecipes.com/を参照しました．

図表1.1クッキーの種類と原料

チョコチップ ブラウニー ショート ジンジャー 材料単価 クッキー ブレッド クッキー (円) バター(カップ) 1 0.5 1 0.75 200

砂糖(カップ) 1.5 1 0.5 1 50

卵(個) 2 2 1 30

小麦粉(カップ) 2.25 0.5 2 2.25 30

チョコチップ (カップ) 2 100

ココアパウダー(カップ) 0.33 240

生姜(カップ) 0.5 50

材料１セットあたりの枚数 24 12 14 18

1枚あたり単価 25.1 25.4 20.4 17.9

図表1.2クッキーの種類と１セットあたりの作業時間

チョコチップ ブラウニー ショート ジンジャー クッキー ブレッド クッキー

準備時間（分） 10 5 15 120

調理時間（分） 10 25 35 20

ジンジャークッキーの準備時間が長いのは，生地を冷蔵庫で冷やさねばならないからです．材 料費は安いものの，時間が取られることを考えると，ジンジャークッキーばかり作るのは得策とは いえません．

作業する人の予定によって全体の作業時間を見積もることができます．生地作りや成形などの 準備作業は分担してできるのに対して，オーブンの数が限られているため調理時間は多く取ること ができません．前者は40時間，後者は20時間確保できると見積もることにします．

上記の作業時間内でクッキーを作るものとして，材料費の合計をもっとも安くするにはどのクッ キーを何枚作ればよいか，という問題を考えてみます．

1.1.2

クッキーの製造枚数を考えるにあたって，考慮すべき要素(ここでは，製造枚数や作業時間，材 料費)を数式で表すことによって製造枚数と要素の関係を明確にすることができます．満たすべき 条件をまとめてみましょう．

1. 材料費の合計を小さくしたい．

2. 作る枚数は全部で1000枚とする．

3. 準備時間は40時間を越えることはできない．

4. 調理時間は20時間を越えることはできない．

1.1. クッキー販売の模擬店 5 数式を導入する最初のステップとして，変数を定義します．製造枚数を決めたいので，これを 変数としましょう．

x₁：チョコチップクッキーの枚数 x₂：ブラウニーの枚数

x₃：ショートブレッドの枚数 x₄：ジンジャークッキーの枚数 材料費の合計をzとすると，材料費と製造枚数の関係は，

z=25.1x1+25.4x2+20.4x3+17.9x4

となります．枚数の条件は次のように表せるでしょう．

x1+x2+x3+x4=1000

作業時間は，次のように考えます．例えば，チョコチップクッキーは，１セットの材料から24枚 つくれるので，これを作業時間の単位とします．つまり，もし24枚チョコチップクッキーを作る のであれば，準備時間は10分，調理時間は10分かかることを意味します．もし48枚であれば，

それぞれ20分，20分かかります．したがって，準備時間の条件は，

10∗ x1

24+5∗ x2

12+15∗ x3

14+120∗ x4

18 ≤40∗60 とかけます．あるいは，分数を小数に直して，

0.417x₁+0.417x₂+1.071x₃+6.667x₄≤2400

です．調理時間の条件は，

0.625x1+2.083x2+2.50x3+1.111x4≤1200 となります．

以上より，製造枚数，作業時間の条件を満たしつつ，原材料費を最小化する問題は，

min. z=25.1x1+25.4x2+20.4x3+17.9x4

s.t. x₁+x₂+x₃+x₄=1000

0.417x1+0.417x2+1.071x3+6.667x4≤2400 0.625x₁+2.083x₂+2.50x₃+1.111x₄≤1200 xj≥0, j=1, . . . , 4

(1.1)

と表すことができます．なお，最後の行の“ xj≥0, j=1, . . . , 4”は，

x1≥0, x2≥0, x3≥0, x4≥0 を略して書いたもので，製造枚数が非負であることを表しています．

このように，与えられた条件の中で，目的となる値を最小(あるいは最大)にするような変数の 値を求める問題を，一般に最適化問題と呼びます．与えられた条件を総称して制約と呼び，制約を 構成する条件式を制約式と呼びます．最小(最大)化する式は目的関数です．最適化問題(1.1)は，

目的関数と制約式がいずれも1次式・1次不等式で表されるという特徴があることから，線形計画

問題(linear programming problem)と呼ばれます．線形計画問題の性質や解法の体系をまとめて，

線形計画法(linear programming)といいます．

計算機を用いて(1.1)を解くと，次の解が得られます．

x1=476.2, x2=0.0, x3=230.7, x4=293.2

これよりジンジャークッキーを多く作ることが必ずしも適切ではないことがわかりました．よくみ ると，ブラウニーの製造枚数は0となっているので，これは作らないということです．方針として 4種類全てを作ることになっているので，モデルを少し見直してみましょう．例えば，材料１セッ トから作る枚数を12枚から増やして15枚として，再度計算してみます．すると，

x1=275.9, x2=401.4, x3=0.0, x4=322.7

となり，ショートブレッドを作らないことになってしまいました．何度も製造枚数の調整を繰り返 して4種類全てのクッキーをつくるような解を導くことも不可能ではないでしょうが，別のアプ ローチをしてみます．必ず4種類作るということは，最低でも作る枚数をあたえてしまってもよい ということです．ここでは最低枚数を100枚としましょう．この条件は，

x1≥100, x2≥100, x3≥100, x4≥100 と表現できます．あらためて，問題

min. z=25.1x1+25.4x2+20.4x3+17.9x4

s.t. x₁+x₂+x₃+x₄=1000

0.417x1+0.417x2+1.071x3+6.667x4≤2400 0.625x₁+2.083x₂+2.50x₃+1.111x₄≤1200 xj≥100, j=1, . . . , 4

(1.2)

を解くと，

x₁=447.7, x₂=100.0, x₃=150.7, x₄=301.5 となりました．

演習問題1.1

クッキーの製造枚数を求める問題で，次の条件はどのように表されるか．

• ^{どの種類のクッキーも}300枚より多く作らない．

• 準備と調理の作業時間の合計が50時間をこえない．

1.2

線形計画問題の特徴

一般の制約付き最適化問題は

¯¯¯¯ 最小(大)化 xの関数

条件 xはある領域に属する という形をしています．線形計画問題の特徴は，

• 目的関数がxの1次式であること

• 制約領域が，1次式もしくは1次不等式の組合わせで表されていること です．この条件が変わると，一見似ていてもまったく性質の異なる問題になります．

1.2. 線形計画問題のフォーマット 7

標準型

線形計画問題を表現するにはいくつかの流儀があります．まずは標準型(standard form)を覚 えてください．

maximize c1x1+c2x2+· · ·+cnxn

subject to a₁₁x₁+a₁₂x₂+· · ·+a_1nx_n=b₁ a21x1+a22x2+· · ·+a2nxn=b2

...

am1x1+am2x2+· · ·+amnxn=bm

x1≥0, x2≥0, . . . , xn≥0

(1.3)

x1, x2, . . . , xnを(決定)変数(decision variable)とよび，ベクトル(b1, . . . , bm)^⊤を右辺(right

hand side)とよびます．係数を次のようにまとめて表すとこともできます．







a11 a12 · · · a1n

a21 a22 a2n

... . .. ... a_m1 a_m2 · · · a_mn







これは係数行列とよばれています．x₁ ≥ 0, x₂ ≥0, . . . , x_n ≥0 は非負制約(nonnegativity con-

straint)です．非負制約や上下限制約を持たない変数は自由変数と呼ばれます．

(x1, . . . , xn)が制約条件をすべて満たしているならば，それは実行可能解です．実行可能解の中

で，目的関数を最小化するものを最適解とよび，そのときの目的関数の値を最適値とよびます．

問題(1.3))をシグマ記号“∑

”を使って，以下のように書き表すこともあります．

maximize ∑n j=1cjxj

subject to ∑n

j=1aijxj=bi, i=1, . . . , m xj≥0, j=1, . . . , n

(1.4)

ベクトル表示を用いることもあります．

maximize c^⊤x subject to Ax=b

x≥0

(1.5)

ただし，

x= (x₁, . . . , x_n)^⊤ c= (c₁, . . . , c_n)^⊤ b= (b1, . . . , bm)^⊤

A=







a11 a12 · · · a1n

a21 a22 a2n

... . .. ... am1 am2 · · · amn







標準型への書換え

すべての線形計画問題は，標準型に帰着できます．以下のように，制約に不等式が含まれてい ても，

maximize c1x1+c2x2+· · ·+cnxn

subject to a₁₁x₁+a₁₂x₂+· · ·+a_1nx_n ≤b₁ a21x1+a22x2+· · ·+a2nxn ≤b2

...

am1x1+am2x2+· · ·+amnxn≤bm

x1≥0, x2≥0, . . . , xn≥0

(1.6)

スラック変数xn+1, xn+2, . . . , xn+mを導入することで，

maximize c1x1+c2x2+· · ·+cnxn

subject to a₁₁x₁+a₁₂x₂+· · ·+a_1nx_n+x_n+1=b₁ a21x1+a22x2+· · ·+a2nxn+xn+2=b2

...

am1x1+am2x2+· · ·+amnxn+xn+m=bm

x1≥0, . . . , xn≥0, xn+1≥0, . . . , xn+m≥0

(1.7)

とすることができます．

自由変数を含む場合を考えてみましょう．問題(1.8)の変数x₁には，非負制約も上下限制約も 与えられていないので，自由変数となります．

maximize c1x1+c2x2+· · ·+cnxn

subject to a₁₁x₁+a₁₂x₂+· · ·+a_1nx_n =b₁ a21x1+a22x2+· · ·+a2nxn =b2

...

am1x1+am2x2+· · ·+amnxn=bm

x2≥0, . . . , xn≥0

(1.8)

この場合は，自由変数を二つの非負変数の差で表します．

x₁=x⁺₁ −x⁻₁ (ただし，x⁺₁ ≥0, x⁻₁ ≥0) そうすると，(1.8)は，

maximize c₁x⁺₁ −c₁x⁻₁ +c₂x₂+· · ·+c_nx_n

subject to a11x⁺₁ −a11x⁻₁ +a12x2+· · ·+a1nxn =b1

a₂₁x⁺₁ −a₂₁x⁻₁ +a₂₂x₂+· · ·+a_2nx_n =b₂ ...

am1x⁺₁ −am1x⁻₁ +am2x2· · ·+amnxn =bm

x⁺₁ ≥0, x⁻₁ ≥0, . . . , x_n≥0

(1.9)

となります．あるいは，代入によって消去するする方法もあります．

1.3. 典型的な問題 9

演習問題1.2

以下の問題を標準型の最大化問題に直せ

max 3x1+2x2-4x3

s.t. -x1+x3≥2 x1+2x2+x3≤5

x1≥0;-4≤x2≤5; x3≥0

演習問題1.3

以下の標準型の最大化問題の制約式をすべて不等式で表した等価な問題をつくれ

max x1+x2+x3

s.t. 2x1-x2+3x3+x4=6 -x1-4x2+2x3+x5=5 x1; x2; x3; x4; x5≥0

1.3

1.3.1

サラダづくり

この節は，Lancaster(1992)を参照しました．

食餌問題(diet problem)は，線形計画法の古典的な応用例です．何らかの制約をみたした上で，

配分・配合を決める問題の基本型といっていいでしょう．同じ形式の実務上の問題も数多く存在し ます．

この問題を一言で言うと，「必要な栄養の基準を満たし，かつもっともコストの低い食餌は何か?」

です．単純な問題を例にとって説明しましょう．

図表1.3可食部100g当たりの栄養素 食品名 エネル

ギー

水分 たんぱ く質

脂質 炭水化 物

灰分 食塩相 当量

ビタミ ンB1

ビタミ ンC

コレス テロー ル

(kcal) (g) (g) (g) (g) (g) (g) (mg) (mg) (mg)

かぼちゃ 60 84 1.9 0.1 13.3 0.7 0 0.08 16 0 だいこん 18 94.6 0.4 0.1 4.1 0.6 0 0.02 11 0 たまねぎ 26 93 0.6 0.1 6.1 0.2 0 0.03 5 0 トマト 19 94 0.7 0.1 4.7 0.5 0 0.05 15 0 にんじん 37 89.6 0.6 0.1 9 0.7 0.1 0.04 4 0 もやし 34 93 2.9 1.6 2.2 0.3 0 0.04 1 0 レタス 12 95.9 0.6 0.1 2.8 0.5 0 0.05 5 0

図表1.4野菜の値段(100gあたり)：2003年3月15日の取引価格

インデックス 1 2 3 4 5 6 7

品名 かぼちゃ だいこん たまねぎ トマト にんじん もやし レタス

値段(円) 136.5 157.5 273.0 136.5 157.5 50.0 147.0

表1.3²にある野菜を使って，野菜サラダをつくります．いくつかの栄養素の中から，たんぱく 質，ビタミンB1，ビタミンCに着目しました．これらの栄養素を一定の量以上取ることができて，

かつできるだけ安くするためには，どの野菜をどれだけ買えばよいのでしょうか．栄養素の必要量 は，それぞれ 10g，0.5mg，50mgとしました³．価格は表1.4にある通りです．

変数として，インデックスj(j=1, . . . , 7)の野菜の量をxj(100g)とします．すると，野菜をそ れぞれx₁, . . . , x₇用いると，各々の野菜から摂取できるたんぱく質の合計は，

1.9x1+0.4x2+0.6x3+0.7x4+0.6x5+2.9x6+0.6x7

となります．同様に，ビタミンB1は，

0.08x₁+0.02x₂+0.03x₃+0.05x₄+0.04x₅+0.04x₆+0.05x₇

と表され，ビタミンCは，

16.0x1+11.0x2+5.0x3+15.0x4+4.0x5+1.0x6+5.0x7

となります．また価格の合計は，

136.5x1+157.5x2+273.0x3+136.5x4+157.5x5+50.0x6+147.0x7

です．栄養成分の要求量をみたし，かつ価格を最小にするには，以下の問題を解けばよいことにな ります．

min 136.5x₁+157.5x₂+273.0x₃+136.5x₄+157.5x₅+50.0x₆+147.0x₇ subject to 1.9x1+0.4x2+0.6x3+0.7x4+0.6x5+2.9x6+0.6x7≥10

0.08x1+0.02x2+0.03x3+0.05x4+0.04x5+0.04x6+0.05x7≥0.5 16.0x1+11.0x2+5.0x3+15.0x4+4.0x5+1.0x6+5.0x7≥50 xj≥0, j=1, . . . , 7

(1.10)

問題(1.10)を解くと，最適解として，

x₁=2.679 x₂=0.0 x₃=0.0 x₄=0.0 x₅=0.0 x₆=7.143 x₇=0.0

が得られます．残念ながら，かぼちゃともやしだけではあまり食欲はそそりません．しかも値段は

なんと722.8円です．現実に活かすためにはもっと定式化に工夫が必要でしょう．

参考：食餌問題の系譜

はじめて食餌問題を論じたのは，Stigler[5]です．この時点では，まだ線形計画問題の効率的な 解法は知られていませんでした．Stiglerは，当時の代表的と思われる食品77品目を対象に，カロ リー，たんぱく質，カルシウム，鉄分，ビタミンA，ビタミンB1，ビタミンB2，ナイアシン，ビ タミンCの必要量を考慮した問題を解いています．結果はやはり万人向けとは言いがたいメニュー です(表1.5)．彼自身，論文でこう述べています．

No one recommends these diets for anyone, let alone everyone.

2食品データベースシステム(http://food.tokyo.jst.go.jp/)を利用しました．

3「第６次改定日本人の栄養所要量」によると，18〜29才の男性(女性)が1日に必要な量は，たんぱく質70(55)g，ビ タミンB1 1.1(0.8)mg，ビタミンC 100(100)mgだそうです．

1.3. 典型的な問題 11

図表1.5 Stiglerの結果：一日の摂取量

品名 小麦粉 キャベツ ほうれん草 パンケーキ粉 牛レバー 量 535 lb. 107 lb. 13 lb. 134 lb. 25 lb.

Dantzigが線形計画法を解くためのアルゴリズムである単体法(simplex method) を開発した

のは1947年です．1950年代初頭，医者から減量を指示されたDantzigは，自ら開発した手法で，

500種以上の食品を対象に食餌問題を解くことにしました([2])．最初に解いた問題から得られたメ ニューでは，酢を500ガロン(約1890L⁴ )飲むべしとなったそうです．これは，酢のデータの作 り方に問題があったせいでした．酢を食品リストからはずして再度解いてみたところ．今度のメ ニューでは，一日に200個の固形ブイヨンを食べよ，となりました．それでもへこたれずに，制約 を見直して⁵再挑戦したら，ふすま(bran)を2ポンド(約900g)食べるはめになりました．さらに，

ふすまの量に上限を課し，4度目に解いたところ，糖蜜(blackstrap molasses)が2ポンド(約900g) とでてきました．ここにいたって，奥さんが減量メニューは自分で作ると宣言したので，Dantzig もあきらめたようです．

問題の設定は単純なのですが，現実的な解を導くのは簡単ではないようです．しかし，多くの 工夫を用いることで，線形計画法によって，栄養の条件を満たし，適度に美味しく，かつバラエ ティにとんだメニューをつくることは可能です．実際に病院，療養所，介護施設，学校，刑務所な どで，この手法が用いられて成果を上げています．一定期間にわたるメニューの構成を考える問題 は，メニュー・スケジューリング問題と呼ばれていて，線形計画問題よりやや解くのが難しい問題 として定式化する必要があります．

Fletcher, Soden, Zinober[4]の用いた方法をみてみることにしましょう．彼らは，モデル化にお いて，次の点を工夫しています．

• 目的関数を費用ではなく，主観的な受け入れやすさとした

• 食品の候補に個人の選好を反映させた

• 制約に自由度を持たせた

病院で特定の患者に対して食餌を処方する場合を考えます．患者は栄養士といっしょに現在の 食餌の情報を入力し，これが出発点になります．ついで，患者に必要な栄養成分を入力すると，新 しいメニューが出力されます．これは，栄養の必要量を満たしているメニューのなかで，現在の食 餌にもっとも“近い”ものが提示されます．通常は，ここで提案されるメニューは患者の好みとは 一致しない場合が多いので，モデルを改良するプロセスに入ります．

1. 上下限を導入する 2. 比率の制約を導入する 3. 必要栄養成分を調整する

4. 食品の追加，削除，入れかえを行う

定式化の詳細も興味深い内容を含んでいますが，LPを習い始めたばかりでは手に余るかもし れません．今回は触れないでおきます．論文に載っていた，慢性腎不全の患者のためのメニューだ けを紹介しましょう．表1.6がその結果です．回数をおうごとに，制約が見直され，そのためにだ んだんと食品の構成が現実的になっていくことが見て取れます．

41升瓶千本以上です．

5Dantzigは，ブイヨンの個数を変えてつくったスープを飲んで，一日3個までなら大丈夫であることを確認しています．

図表1.6病院食メニューの推移

食品名 食品の量(g)

1(現状) 2 3 4 5

フルーツ入りミューズリー 50 50 112 50 50 ヨーグルト 125 0 63 63 63 紅茶 200 0 100 200 200 コーヒー 200 0 100 200 100

全麦パン 70 70 0 70 70

カッテージ・チーズ 75 75 265 75 75

胡椒 1 1 99 1 1

梨 100 100 0 100 100 ローストチキン 150 95 0 82 82 にんにく 10 10 10 10 10 有塩バター 10 10 54 10 10 マッシュポテト 75 0 38 38 38 トマトソース・スパゲッティ 75 259 75 75 75 りんご 20 254 667 57 57 ミルクチョコレート 50 223 53 50 98 牛乳 200 0 100 100 100 レモン・メレンゲ・パイ (200) — — 297 220

1.3.2

食餌問題とおなじ形式をもつ問題をいくつか見てみましょう．

家具製造工場の問題

ある家具製造工場では，３種類の原木を用いて５種類の家具を作ることができます．それぞれ の家具１つあたり用いる原木の量，原木の価格，および，家具の価格は表1.7で与えられています．

図表1.7製品1単位に必要な原木の量

机1 机2 椅子1 椅子2 戸棚 価格(千円/単位) 原木A 4.5 2.0 1.5 1.2 8.0 2

原木B 1.0 3.0 0.5 1.0 2.0 4 原木C 0 1.0 0.5 0 4.0 8 価格(千円) 45 60 15 20 150

この工場の原木の購入予算が150万円であるとき，売上が最大になるような製品の組合せは求 めるにはどうすればよいでしょうか．ただし，つくった家具が売れ残ることはないと仮定します．

[定式化]

製造する家具の量を，机1についてはx1，机2についてはx2，椅子1についてはx3，椅子2 についてはx4，戸棚についてはx5とする．また，原木A，B，Cの購入量をy1，y2，y3とする．

1.3. 典型的な問題 13

max 45x1+60x2+15x3+20x4+150x5

s.t. 4.5x1+2.0x2+1.5x3+1.2x4+8.0x5−y1≤0 1.0x1+3.0x2+0.5x3+1.0x4+2.0x5−y2≤0 1.0x2+0.5x3+4.0x5−y3≤0

2y₁+4y₂+8y₃≤1500 x1, x2, x3, x4, x5, y1, y2, y3≥0

農家の問題

[6]を参照しました．

農家が，夏にんじん，春大根，春キャベツ，春白菜⁶の作付を計画しています．栽培可能な面積 は100aです．これらの野菜が旬をむかえる４，５，６月は，収穫のためたいへん忙しくなるため，

労働時間を考慮して計画を立てる必要があります．必要なデータは，表1.8，1.9に示した通りで す．予想収益を最大にするには，どの野菜をどれくらい栽培するのがよいでしょうか？

図表1.8単位作付面積当たりの必要労働時間と予想収益

夏にんじん 春大根 春キャベツ 春白菜

4月 6.9 71.0 2.0 33.0

5月 2.6 0.0 28.0 0.0

6月 70.0 0.0 0.0 0.0

予想収益 29.8 10.4 13.8 19.8

図表1.9月別の投入可能労働時間

投入可能な労働時間

4月 260

5月 280

6月 290

[定式化]夏にんじんの栽培面積をx1(a)，春大根の栽培面積をx2(a)，春キャベツの栽培面積をx3(a)，

春白菜の栽培面積をx4(a)とします．

max 29.8x1+10.4x2+13.8x3+19.8x4

s.t. x1+x2+x3+x4=100

6.9x₁+71.0x₂+2.0x₃+33.0x₄≤260 2.6x1+28.0x3≤280

70.0x₁≤290

xj≥0, j=1, . . . , 4

6ここで，夏にんじんは前年12月下旬に播種して初夏に収穫，春大根は1月中旬播種／春収穫，春キャベツは前年11 月上旬播種／春収穫，春白菜は前年12月播種／春収穫，としています．

債券のポートフォリオ

債券を特徴づける指標には，次のようなものがあります．

• 価格：取引価格

• 満期利回り：利回りをあらわす指標

• 残存年数：満期までの期間

• クーポン・レート：利付き債のクーポンの額面に対する比率

• デュレーション：利子率の変化に対する利付き債価格の感応度をあらわす指標

詳しくはファイナンスなどの授業で勉強してください．今，7つの債券に対してこれらの指標の値 を求めると，表1.10のようになりました．

図表1.10投資可能な債券

名前 債券1 債券2 債券3 債券4 債券5 債券6 債券7

価格 106.08 111.39 104.81 92.53 97.09 105.63 142.20

満期日(年) 2 2.5 3.5 4 6 7.5 9 クーポン・レート(%) 5 6 4 2 3 4 7 デュレーション 1.86 2.24 3.12 3.71 5.08 5.76 5.81 満期利回り(%) 2.19 2.41 2.71 2.83 3.08 3.31 3.51

この7つの債券に投資を行い，債券ポートフォリオを構成しようと思います．投資の条件や債 券ポートフォリオが満たすべき性質を次のように定めました．

• 投資総額は，1千万円．

• ポートフォリオの平均クーポンレートは，5%以上．

• ポートフォリオのデュレーションは，4以下．

• 一つの債券への投資額は，最大で予算の40%．

• ポートフォリオの満期利回りを最大化する．

• 取引手数料や税金は無視する．債券は無限に分割可能とする．

ここで重要なのは，ポートフォリオの満期利回り，デュレーション，平均クーポンレートは，すべ てポートフォリオを構成する債券の重みつき平均として計算されるということです．例をあげる と，債券1と債券2に50％づつ投資を行うと，その結果得られるポートフォリオの満期利回りは，

0.5∗2.19+0.5∗2.41=2.30(％)

となります．では，債券ポートフォリオを求める問題を定式化してみましょう．債券jの購入枚数 (1万枚)をxj(j=1, . . . , 7)とおきます．

予算制約は，

106.08x1+111.39x2+104.81x3+92.53x4+97.09x5+105.63x6+142.20x7≤1000 となります．

1.3. 典型的な問題 15 ポートフォリオのクーポン・レートとデュレーションはをあらわすには，その重み（投資比 率）が必要です．債券１を例にとると，x1単位購入すると，その価格は106.08x1なので，重みは

106.08x1/1000です．ポートフォリオのクーポン・レートとデュレーションに関する制約は，それ

ぞれ，

5∗106.08x1+6∗111.39x2+4∗104.81x3+2∗92.53x4+3∗97.09x5

+4∗105.63x6+7∗142.20x7≥5∗1000 1.86∗106.80x1+2.24∗111.39x2+3.12∗104.81x3+3.71∗92.53x4

+5.08∗97.09x5+5.76∗105.63x6+5.81∗142.20x7≤4∗1000 と表される．

目的関数となるポートフォリオの満期利回りも同様に考えて (2.19∗106.08x1+2.41∗111.39x2+2.71∗104.81x3+2.83∗92.53x4

+3.08∗97.09x5+3.31∗105.63x6+3.51∗142.20x7)/1000 となります．

投資比率の上限制約は，以下のとおりです．

106.08x1≤0.4∗1000 111.39x2≤0.4∗1000 104.81x3≤0.4∗1000 92.53x4≤0.4∗1000 97.09x5≤0.4∗1000 105.63x6≤0.4∗1000 142.20x7≤0.4∗1000

以上をまとめると，債券ポートフォリオの最適化問題は，

¯¯¯¯

¯¯¯¯

¯¯¯¯

¯¯¯¯

¯¯

maximize0.232x1+0.269x2+0.284x3+0.262x4+0.299x5+0.349x6+0.499x7

subject to106.08x1+111.39x2+104.81x3+92.53x4+97.09x5+105.63x6+142.20x7≤1000 0.530x1+0.668x2+0.419x3+0.185x4+0.291x5+0.423x6+0.995x7≥5

0.197x1+0.249x2+0.327+x3+0.344x4+0.493x5+0.608x6+0.826x7≤4 106.08x₁≤400, 111.39x₂≤400, 104.81x₃≤400, 92.53x₄≤400, 97.09x₅≤400, 105.63x₆≤400, 142.20x₇≤400

x_j≥0 j=1, . . . , 7

(1.11) と定式化できます．

これを解くと，最適な投資額は，

(x^∗₁, x^∗₂, x^∗₃, x^∗₄, x^∗₅, x^∗₆, x^∗₇) = (0, 1.84, 3.82, 0, 0, 0, 2.78)

となりました(単位は1万枚)．

果物の分配

３人で，みかん20個とりんご20個と梨5個をわけることにしました．Aさんは，みかん1つ を交換するのに，りんごなら1.2個，梨なら1.5個を要求しています．みかん1つに対して，Bさ んはりんご0.8個，梨1.1個，Cさんはりんご1.4個，梨0.8個の比率です．今，みかん一個から 得られる満足度が３人とも等しいとするなら，全員の満足度の合計を最大にするにはどのようなわ

け方をすべきでしょうか．線形計画問題として定式化しなさい．ただし，どの果物も必要なら切っ てわけても構いません．

また，分配された果物の数を等しくする(この場合は一人15個)という条件がついた場合はど うなるでしょうか？

[定式化]

Aさんが得るみかん，りんご，梨の個数をx1，x2，x3 で表します．同様にBさんの得るみか ん，りんご，梨の個数をy₁，y₂，y₃，Cさんは z₁，z₂，z₃ とします．満足度を表す変数も導入 しましょう．Aさん，Bさん，Cさんの満足度をそれぞれ，uA, uB, uCとします．満足度をみかん の個数で換算して表す⁷とすると，交換比率から，

uA=x1+ 1

1.2x2+ 1 1.5x3

u_B=y₁+ 1

0.8y₂+ 1 1.1y₃ uC=z1+ 1

1.4z2+ 1 0.8z3

となるはずです．りんご，みかん，梨の個数が与えられているので，以下のように定式化すること ができます．

max uA+uB+uC

s.t. u_A−x₁−_1.2¹ x₂− _1.5¹ x₃=0 uB−y1− _0.8¹ y2−_1.1¹ y3=0 u_C−z₁− _1.4¹ z₂−_0.8¹ z₃=0 x1+y1+z1=20

x2+y2+z2=20 x3+y3+z3=5 xj≥0, j=1, 2, 3 y_j≥0, j=1, 2, 3 zj≥0, j=1, 2, 3

(1.12)

この問題は，わざわざLPに定式化しなくても解けます．梨とりんごは，それをもっとも欲し がる人に全部あげれば満足度の合計は高くなります．みかんは，皆が同じ満足度なので，どのよう にわけても満足度の合計は変化しません．したがって，Aさんに梨をすべて与え，Cさんにりんご をすべて与えればよいのです(みかんは自由にわけてよい)．

分配後の個数に制約がある場合は，次の制約を(1.12)に付け加えてください．

x1+x2+x3=15 y1+y2+y3=15 z1+z2+z3=15

この場合，果物の配分は図表1.11のようになります．

演習問題1.4 ビタミン剤

製薬会社K4コーポレーションがビタミン剤をつくっている．これには，ビタミンAが重量比 で8%，ビタミンBが重量比で4%，ビタミンCが重量比で2%以上含まれていなければならな

7みかんがnumeraireというわけです．

1.3. 典型的な問題 17

図表1.11果物の分配

名前 満足度 みかん りんご 梨

Aさん 12.5 5.0 5.0 5.0

Bさん 15.0 15.0 0 0

Cさん 10.7 0 15.0 0

い．一方，各ビタミン成分をつくるのに，4種類の原材料を用いることができる．原材料1gか ら精製される各ビタミン成分の量は，表1.12の通りである．例をあげると，1gの原材料1を精 製することで，ビタミンA，B，Cがそれぞれ0.03g，0.02g，0.01gを入手できる．

図表1.12原材料から精製されるビタミンのの量

原材料費(円/g) ビタミンA ビタミンB ビタミンC 原材料1 8 0.03 0.02 0.01 原材料2 10 0.06 0.04 0.01 原材料3 11 0.10 0.03 0.04 原材料4 14 0.12 0.09 0.04

ビタミン剤20kgの生産に対して，最も原材料の費用を低くするには原材料をそれぞれいくらず つ購入するのがよいか．

演習問題1.5

ある工場では，原材料A，B，C，Dから２種類の製品を製造している．親会社との契約で，製 品P1をd1単位，P2をd2単位の量を価格p^c₁，p^c₂で納入しなければならない．それ以上生産 した分は，市場価格はp^m1，市場価格はp^m2 で販売することができる．

製品Pi (i=1; 2)を１単位作るために必要な原材料A，B，C，Dの量は，それぞれa^A_i，a^B_i， a^C_i，a^D_i 単位である．原材料A，B，C，Dの１単位当たりの価格をそれぞれq^A，q^B，q^C，q^D とし，予算がbであるとき，この工場の最適な生産計画を表す問題を作れ．ただし，売れ残り は考えないことにする．

演習問題1.6 キャンディーづくり

1. 今，あなたの手元には，80kgの砂糖と20kgのナッツ，30kgのチョコレートがある．あ なたは，これを使って2種類のキャンディーをつくり，一儲けしようとしている．チョコ キャンディーには，重量比で20%のチョコレートが含まれていなくてはならない．また，

ミックスキャンディーには，重量比で10%のチョコレートと10%のナッツが含まれていな くてはならない(残りの成分は砂糖である)．チョコキャンディー1kgは5千円で，ミック スキャンディーは6千円で売ることができる．売り上げを最大にするには，それぞれのキャ ンディーをいくらつくればよいか．

2. キャンディーの製造計画を考えていたあなたは，何も手持ちの原材料だけにこだわること はないことに気が付いた．原料を買ってきて，もっと多くのキャンディーを作ることもで きるはずだ．砂糖，ナッツ，チョコレートの1kgあたりの費用は，それぞれ1200円，2000 円，1600円であった．残念ながらあなたの時間には限りがあるので，つくることができる 量は，両方のキャンディーをあわせて120kgまでである．収益(＝売り上げ─追加した材 料の購入額)を最大にするには，それぞれのキャンディーをいくらつくればよいか．

3. 時間が足りないなら，友だちに応援を頼むのはどうだろうか．友だちが1時間手伝ってく れれば，両方のキャンディーをあわせて10kg多くつくることができそうだ(つまり，2時 間手伝ってもらえれば，あわせて140kgつくれる)．友だちに払う時給を1500円として，

新たな製造計画をつくれ．ただし，友だちが手伝ってくれる時間は4時間までである．

演習問題1.7 ジュース

1. 食品メーカーK1社は，農家からオレンジを購入して，袋づめにして売っている．また，オ レンジを加工してジュースをつくり，販売している．また，すでに加工済のグレープフルー ツジュースを購入して，オレンジジュースと混ぜてミックスジュースをつくっている．予 算が500万円あったとして，表1.13の情報に基づいて，売り上げを最大にする原料の購入 量，商品の製造量を求めよ．

図表1.13原料と価格の情報

オレンジ1kgの購入価格: 300円 オレンジ1kgの販売価格: 500円 オレンジジュース1kgの販売価格: 600円 オレンジジュース1kgに必要なオレンジの重量: 0.8kg

グレープフルーツジュース1kgの購入価格: 250円 ミックスジュース1kgに必要なオレンジジュースの量: 0.5kg ミックスジュース1kgに必要なグレープフルーツジュースの量: 0.3kg ミックスジュース1kgの販売価格: 800円

2. 前の問題で与えられた情報に加えて，需要の予測が手に入った．

オレンジジュースとミックスジュースの需要が，それぞれ3000kgと1500kgであるとし て，需要を必ず満たしたうえで，売り上げを最大にする原料の購入量，商品の製造量を求 めよ．なお，この需要は最低満たすべき需要であり，超過分もすべて売れるものとする．

3. 前の問題では，需要は必ず満たす必要があった．

今度は，必ずしも需要を満たさなくても良いが，不足分にはペナルティがかかることにす る．オレンジジュースの不足に対しては，1kgあたり200円，ミックスジュースの方は1kg あたり300円のペナルティーがかかる．売り上げから(もしあれば)ペナルティーを引いた 額が最大になるように製造計画を立てよ．需要を超過した分もすべて売れるものとする．

4. 前の問題の設定では，需要の超過分はすべて売れるものとした．新たに，需要の超過分は 安い価格でしか処分することができないものとする．超過分については，オレンジジュー ス，ミックスジュースがそれぞれ1kgあたり，100円，120円ですべて売り切ることがで きるとしたとき，最適な製造計画を立てよ．

1.3.3

前節の問題は1時点だけを考慮して配分を決めていました．今度は，一定の期間にわたる配分 を決める問題を考えましょう．このタイプの問題は，状態が時間に応じて変化する場合に多く見ら れます．配分の基本は同じですが，時点間の関係をうまく表現する必要があります．

クッキーの作成スケジュール

大学祭で販売するクッキーは手作りです．材料を買ってきて，クッキーを焼き，袋づめをする まで，すべて自分達でこなさなければなりません．昨年は，責任者がいい加減な計画しか作らな かったせいで，サークルのメンバー全員が直前になってたいへん忙しい思いをしました．今年の責 任者であるあなたは，まともな計画を立てるよう圧力をかけられています．

模擬店で販売するクッキーは，おおよそ以下の手順で作ります．