( ) () () ( ) () () () ()

第

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 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 時間を越えることはできない．

数式を導入する最初のステップとして，変数を定義します．製造枚数を決めたいので，これを 変数としましょう． x1：チョコチップクッキーの枚数 x2：ブラウニーの枚数 x3：ショートブレッドの枚数 x4：ジンジャークッキーの枚数 材料費の合計をz とすると，材料費と製造枚数の関係は， z = 25.1x1+ 25.4x2+ 20.4x3+ 17.9x4 となります．枚数の条件は次のように表せるでしょう． x1+ x2+ x3+ x4= 1000 作業時間は，次のように考えます．例えば，チョコチップクッキーは，１セットの材料から24 枚 つくれるので，これを作業時間の単位とします．つまり，もし24 枚チョコチップクッキーを作る のであれば，準備時間は10 分，調理時間は 10 分かかることを意味します．もし 48 枚であれば， それぞれ20 分，20 分かかります．したがって，準備時間の条件は， 10 ∗x₂₄1+ 5 ∗x₁₂2+ 15 ∗ x₁₄3+ 120 ∗x₁₈4 ≤ 40 ∗ 60 とかけます．あるいは，分数を小数に直して， 0.417x1+ 0.417x2+ 1.071x3+ 6.667x4≤ 2400 です．調理時間の条件は， 0.417x1+ 2.083x2+ 2.50x3+ 1.111x4≤ 1200 となります． 以上より，製造枚数，作業時間の条件を満たしつつ，原材料費を最小化する問題は， min. z = 25.1x1+ 25.4x2+ 20.4x3+ 17.9x4 s.t. x1+ x2+ x3+ x4= 1000 0.417x1+ 0.417x2+ 1.071x3+ 6.667x4≤ 2400 0.417x1+ 2.083x2+ 2.50x3+ 1.111x4≤ 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= 432.0 x2= 0.0 x3= 280.0 x4= 288.0 z = 21705.0 これよりジンジャークッキーを多く作ることが必ずしも適切ではないことがわかりました．よくみ ると，ブラウニーの製造枚数は0 となっているので，これは作らないということです．方針として 4 種類全てを作ることになっているので，モデルを少し見直してみましょう．モデルのパラメータ の変更によって，計算結果が変わる場合があります．例えば，ブラウニーの材料１セットから作る 枚数を12 枚から増やして 15 枚とすると，1 枚のサイズは小さくなるものの生産効率が上がるため ブラウニーを作る方が有利になると期待できます．1 セットから 15 枚とすると，(1.1) の 2 番目の 制約式および3 番目の制約式の x2の係数が，それぞれ0.417 → 0.333，2.083 → 1.667 となり，再 度計算して x1= 229.6 x2= 447.1 x3= 0.0 x4= 323.3 z = 20647.6 を得ます．x3が0 となり，ショートブレッドを作らないことになってしまいました．何度もパラ メータの調整を繰り返して4 種類全てのクッキーをつくるような解を導くことも不可能ではないで しょうが，別のアプローチをしてみます．必ず4 種類作るということは，最低でも作る枚数をあた えてしまってもよいということです．ここでは最低枚数を100 枚としましょう．この条件は， x1≥ 100, x2≥ 100, x3≥ 100, x4≥ 100 と表現できます．非負条件を修正した問題 min. z = 25.1x1+ 25.4x2+ 20.4x3+ 17.9x4 s.t. x1+ x2+ x3+ x4= 1000 0.417x1+ 0.417x2+ 1.071x3+ 6.667x4≤ 2400 0.417x1+ 2.083x2+ 2.50x3+ 1.111x4≤ 1200 xj≥ 100, j = 1, . . . , 4 (1.2) を解くと， x1= 406.2 x2= 100.0 x3= 197.1 x4= 296.7 z = 22067.3 となりました． 演習問題1.1 クッキーの製造枚数を求める問題で，次の条件はどのように表されるか．  どの種類のクッキーも300枚より多く作らない．  準備と調理の作業時間の合計が50時間をこえない． 演習問題1.2 準備時間，調理時間の制約は変わらないものとして，費用が2万円以下という条件を加える．総 枚数を最大にするための，クッキーの製造枚数を求める線形計画問題を作れ．ただし，少なくと もすべてのクッキーを100枚以上作るものとする．

1.2

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

1.2.1 最適化問題と線形計画問題

一般の制約付き最適化問題は   最小_条件(大) 化 f(x)_{x ∈ X} (1.3)

という形をしています．f(x) は目的関数で，X は制約領域，x は決定変数です．問題 (1.3) の意味 は，制約領域X に属する x の中で目的関数 f(x) を最小に (もしくは最大に) する x を求めよ，とい うことです． 線形計画問題の特徴は，  目的関数が x の 1 次式であること  制約領域が，1 次式もしくは 1 次不等式の組合わせで表されていること です．この条件が変わると，一見似ていてもまったく性質の異なる問題になります．

1.2.2 線形計画問題の書き換え

線形計画問題を表現するにはいくつかの流儀があります．そのため同じ意味を持つ問題が異なっ て表現されたりすることがあります．その際，どの流儀が優れているかを考えることにあまり意味 はありません．大事なのは，問題の意味を損なわずに適切に書き換えることができることです． ここでは，まずは標準型(standard form) を紹介します．標準型では，制約式がすべて等式で す．またすべての変数に非負条件がつきます． maximize c1x1+ c2x2+ · · · + cnxn subject to a11x1+ a12x2+ · · · + a1nxn = b1 a21x1+ a22x2+ · · · + a2nxn = b2 ... am1x1+ am2x2+ · · · + amnxn= bm x1≥ 0, x2≥ 0, . . . , xn≥ 0 (1.4)

b1, . . . , bmを右辺(right hand side) とよびます．aij (i = 1, . . . , m; j = 1, . . . , n) は係数です．

係数を次のようにまとめて表すとこともできます．      a11 a12 · · · a1n a21 a22 a2n ... ... ... am1 am2 · · · amn      これは係数行列とよばれています．x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0 は非負制約 (nonnegativity con-straint) です．非負制約や上下限制約を持たない変数は自由変数と呼ばれます． (x1, . . . , xn) が制約条件をすべて満たしているならば，それは実行可能解 (feasible solution) で す．実行可能解の中で，目的関数を最小化するものを最適解(optimal solution) とよび，そのとき の目的関数の値を最適値とよびます． 問題(1.4)) をシグマ記号 \∑" を使って，以下のように書き表すこともあります． maximize ∑n j=1 cjxj subject to ∑n j=1 aijxj= bi, i = 1, . . . , m xj≥ 0, j = 1, . . . , n (1.5)

ベクトル表示を用いることもあります． maximize c>_x subject to Ax = b x ≥ 0 (1.6) ただし， x =    x1 ... xn    c =    c1 ... cn    b =    b1 ... bm    A =      a11 a12 · · · a1n a21 a22 a2n ... ... ... am1 am2 · · · amn      であり，> は転置を表す．2 すべての線形計画問題は，標準型に帰着できます．以下のように，制約に不等式が含まれてい ても， maximize c1x1+ c2x2+ · · · + cnxn subject to a11x1+ a12x2+ · · · + a1nxn ≤ b1 a21x1+ a22x2+ · · · + a2nxn ≤ b2 ... am1x1+ am2x2+ · · · + amnxn≤ bm x1≥ 0, x2≥ 0, . . . , xn≥ 0 (1.7) スラック変数xn+1, xn+2, . . . , xn+mを導入することで， maximize c1x1+ c2x2+ · · · + cnxn subject to a11x1+ a12x2+ · · · + a1nxn+ xn+1= b1 a21x1+ a22x2+ · · · + a2nxn+ xn+2= b2 ... am1x1+ am2x2+ · · · + amnxn+ xn+m= bm x1≥ 0, . . . , xn≥ 0, xn+1≥ 0, . . . , xn+m≥ 0 (1.8) とすることができます． 自由変数を含む場合を考えてみましょう．問題(1.9) の変数 x1には，非負制約も上下限制約も 与えられていないので，自由変数となります． maximize c1x1+ c2x2+ · · · + cnxn subject to a11x1+ a12x2+ · · · + a1nxn = b1 a21x1+ a22x2+ · · · + a2nxn = b2 ... am1x1+ am2x2+ · · · + amnxn = bm x2≥ 0, . . . , xn≥ 0 (1.9) この場合は，自由変数を二つの非負変数の差で表します． x1= x+1 − x−1 (ただし，x+1 ≥ 0, x−1 ≥ 0) 2_c>_{= (c1, . . . , cn) である．}

そうすると，(1.9) は， maximize c1x+1 − c1x−1 + c2x2+ · · · + cnxn subject to a11x+₁ − a11x₁−+ a12x2+ · · · + a1nxn= b1 a21x+1 − a21x−1 + a22x2+ · · · + a2nxn= b2 ... am1x+1 − am1x−1 + am2x2· · · + amnxn = bm x+ 1 ≥ 0, x−1 ≥ 0, . . . , xn≥ 0 (1.10) となります． 自由変数を非負変数の差によって表すのではなく，代入によって消去するする方法もあります． 一般の線形計画問題を，標準型に帰着させる方法をまとめておきます．  制約に不等式が含まれているならば，不等号の向きを ≤ にそろえる．スラック変数を導入し て，等式にする．  自由変数が含まれているならば， – その変数を代入によって消去するか， – 二つの非負変数の差によって表す． 演習問題1.3 以下の問題を標準型の最大化問題に直せ max 3x1+ 2x2− 4x3 s.t. −x1+ x3≥ 2 x1+ 2x2+ x3≤ 5 x1≥ 0, −4 ≤ x2≤ 5, x3≥ 0 演習問題1.4 以下の標準型の最大化問題の制約式をすべて不等式で表した等価な問題をつくれ 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.33にある野菜を使って，野菜サラダをつくります．いくつかの栄養素の中から，たんぱく 質，ビタミンB1，ビタミン C に着目しました．これらの栄養素を一定の量以上取ることができて， かつできるだけ安くするためには，どの野菜をどれだけ買えばよいのでしょうか．栄養素の必要量 は，それぞれ 10g，0.5mg，50mg としました4．価格は表1.4 にある通りです． 変数として，インデックスj (j = 1, . . . , 7) の野菜の量を xj(100g) とします．すると，野菜をそ れぞれx1, . . . , x7用いると，各々の野菜から摂取できるたんぱく質の合計は， 1.9x1+ 0.4x2+ 0.6x3+ 0.7x4+ 0.6x5+ 2.9x6+ 0.6x7 となります．同様に，ビタミンB1 は， 0.08x1+ 0.02x2+ 0.03x3+ 0.05x4+ 0.04x5+ 0.04x6+ 0.05x7 と表され，ビタミン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 です．栄養成分の要求量をみたし，かつ価格を最小にするには，以下の問題を解けばよいことにな 3_{食品データベースシステム(http://food.tokyo.jst.go.jp/) を利用しました．} 4_{「第６次改定日本人の栄養所要量」によると，18∼29 才の男性 (女性) が 1 日に必要な量は，たんぱく質 70(55)g，ビ} タミンB1 1.1(0.8)mg，ビタミン C 100(100)mg だそうです．

ります． min 136.5x1+ 157.5x2+ 273.0x3+ 136.5x4+ 157.5x5+ 50.0x6+ 147.0x7 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.11) 問題(1.11) を解くと，最適解として， x1= 2.679 x2= 0.0 x3= 0.0 x4= 0.0 x5= 0.0 x6= 7.143 x7= 0.0 が得られます．残念ながら，かぼちゃともやしだけではあまり食欲はそそりません．しかも値段は なんと722.8 円です．現実に活かすためにはもっと定式化に工夫が必要でしょう． 参考：食餌問題の系譜 はじめて食餌問題を論じたのは，Stigler[7] です．この時点では，まだ線形計画問題の効率的な 解法は知られていませんでした．Stigler は，当時の代表的と思われる食品 77 品目を対象に，カロ リー，たんぱく質，カルシウム，鉄分，ビタミンA，ビタミン B1，ビタミン B2，ナイアシン，ビ タミンC の必要量を考慮した問題を解いています．結果はやはり万人向けとは言いがたいメニュー です(表 1.5)．彼自身，論文でこう述べています．

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

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

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

Dantzig が線形計画法を解くためのアルゴリズムである単体法 (simplex method) を開発した のは1947 年です．1950 年代初頭，医者から減量を指示された Dantzig は，自ら開発した手法で， 500 種以上の食品を対象に食餌問題を解くことにしました ([2])．最初に解いた問題から得られたメ ニューでは，酢を500 ガロン (約 1890L5 ) 飲むべしとなったそうです．これは，酢のデータの作 り方に問題があったせいでした．酢を食品リストからはずして再度解いてみたところ．今度のメ ニューでは，一日に200 個の固形ブイヨンを食べよ，となりました．それでもへこたれずに，制約 を見直して6再挑戦したら，ふすま(bran) を 2 ポンド (約 900g) 食べるはめになりました．さらに， ふすまの量に上限を課し，4 度目に解いたところ，糖蜜 (blackstrap molasses) が 2 ポンド (約 900g) とでてきました．ここにいたって，奥さんが減量メニューは自分で作ると宣言したので，Dantzig もあきらめたようです． 問題の設定は単純なのですが，現実的な解を導くのは簡単ではないようです．しかし，多くの 工夫を用いることで，線形計画法によって，栄養の条件を満たし，適度に美味しく，かつバラエ ティにとんだメニューをつくることは可能です．実際に病院，療養所，介護施設，学校，刑務所な どで，この手法が用いられて成果を上げています．一定期間にわたるメニューの構成を考える問題 は，メニュー・スケジューリング問題と呼ばれていて，線形計画問題よりやや解くのが難しい問題 として定式化する必要があります． 5_{1 升瓶千本以上です．} 6_{Dantzig は，ブイヨンの個数を変えてつくったスープを飲んで，一日 3 個までなら大丈夫であることを確認しています．}

Fletcher, Soden, Zinober[5] の用いた方法をみてみることにしましょう．彼らは，モデル化にお いて，次の点を工夫しています．  目的関数を費用ではなく，主観的な受け入れやすさとした  食品の候補に個人の選好を反映させた  制約に自由度を持たせた 病院で特定の患者に対して食餌を処方する場合を考えます．患者は栄養士といっしょに現在の 食餌の情報を入力し，これが出発点になります．ついで，患者に必要な栄養成分を入力すると，新 しいメニューが出力されます．これは，栄養の必要量を満たしているメニューのなかで，現在の食 餌にもっとも\近い" ものが提示されます．通常は，ここで提案されるメニューは患者の好みとは 一致しない場合が多いので，モデルを改良するプロセスに入ります． 1. 上下限を導入する 2. 比率の制約を導入する 3. 必要栄養成分を調整する 4. 食品の追加，削除，入れかえを行う 定式化の詳細も興味深い内容を含んでいますが，LP を習い始めたばかりでは手に余るかもし れません．今回は触れないでおきます．論文に載っていた，慢性腎不全の患者のためのメニューだ けを紹介しましょう．表1.6 がその結果です．回数をおうごとに，制約が見直され，そのためにだ んだんと食品の構成が現実的になっていくことが見て取れます． 図表 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 原木の購入できる量には上限があり，原木A，B，C それぞれについて，150，100，200 単位で す．原木の購入予算が150 万円であるとき，売上が最大になるような製品の組合せは求めるにはど うすればよいでしょうか．ただし，つくった家具が売れ残ることはないと仮定します． [定式化] 製造する家具の量を，机1 については x1，机2 については x2，椅子1 については x3，椅子2

についてはx4，戸棚についてはx5とします．また，原木A，B，C の購入量を y1，y2，y3とし

ます． 製作数×単価で売上なので，それをすべての製品について加えた総売上が目的関数です．1∼3 本目の制約は原木の使用量が購入量を上回らないための条件です．4 本目は予算制約，5 本目は購 入量の上限制約です． 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 2y1+ 4y2+ 8y3≤ 1500 y1≤ 150, y2≤ 100, y3≤ 200 x1, x2, x3, x4, x5, y1, y2, y3≥ 0 (1.12) [計算結果] (1.12) を解くと， x1= 18.8 x2= 20 x4= 21.2 x3= x5= 0 y1= 150 y2= 100 y3= 100 となりました．

農家の問題 [8] を参照しました． 農家が，夏にんじん，春大根，春キャベツ，春白菜7の作付を計画しています．栽培可能な面積 は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.9x1+ 71.0x2+ 2.0x3+ 33.0x4≤ 260 2.6x1+ 28.0x3≤ 280 70.0x1≤ 290 xj≥ 0, j = 1, . . . , 4 [計算結果] 計算の結果，最適な栽培計画は x1= 4.14 x2= 0 x3= 9.62 x4= 6.43 となりました． 債券のポートフォリオ 債券を特徴づける指標には，次のようなものがあります． 7_{ここで，夏にんじんは前年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 となります． ポートフォリオのクーポン・レートとデュレーションはをあらわすには，その重み（投資比 率）が必要です．債券１を例にとると，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 以上をまとめると，債券ポートフォリオの最適化問題は，          maximize 0.232x1+ 0.269x2+ 0.284x3+ 0.262x4+ 0.299x5+ 0.349x6+ 0.499x7 subject to 106.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.08x1≤ 400, 111.39x2≤ 400, 104.81x3≤ 400, 92.53x4≤ 400, 97.09x5≤ 400, 105.63x6≤ 400, 142.20x7≤ 400 xj≥ 0 j = 1, . . . , 7 (1.13) と定式化できます． これを解くと，最適な投資額は， (x∗ 1, x∗2, x∗3, x∗4, x∗5, x∗6, x∗7) = (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 さんの得るみか ん，りんご，梨の個数をy1，y2，y3，C さんは z1，z2，z3とします．満足度を表す変数も導入 しましょう．A さん，B さん，C さんの満足度をそれぞれ，uA, uB, uCとします．満足度をみかん の個数で換算して表す8とすると，交換比率から， uA= x1+_1.21 x2+_1.51 x3 uB= y1+_0.81 y2+_1.11 y3 uC= z1+_1.41 z2+_0.81 z3 となるはずです．りんご，みかん，梨の個数が与えられているので，以下のように定式化すること ができます． max uA+ uB+ uC s.t. uA− x1− _1.21 x2−_1.51 x3= 0 uB− y1−_0.81 y2−_1.11 y3= 0 uC− z1−_1.41 z2−_0.81 z3= 0 x1+ y1+ z1= 20 x2+ y2+ z2= 20 x3+ y3+ z3= 5 xj≥ 0, j = 1, 2, 3 yj≥ 0, j = 1, 2, 3 zj≥ 0, j = 1, 2, 3 (1.14) この問題は，わざわざLP に定式化しなくても解けます．梨とりんごは，それをもっとも欲し がる人に全部あげれば満足度の合計は高くなります．みかんは，皆が同じ満足度なので，どのよう にわけても満足度の合計は変化しません．したがって，C さんに梨をすべて与え，B さんにりんご をすべて与えればよいのです(みかんは自由にわけてよい)． 分配後の個数に制約がある場合は，次の制約を(1.14) に付け加えてください． x1+ x2+ x3= 15 y1+ y2+ y3= 15 z1+ z2+ z3= 15 この場合，果物の配分は図表1.11 のようになります． 演習問題1.5 1. 上記の果物の分配の問題では，配分する果物の個数を等しくして，3人の効用の合計を最 大化した． ここで条件を変えて，果物の個数は等しくなくてもよいかわりに，全員の効用を等しくし て，かつその効用を最大化するものする．この問題を定式化せよ． 8_{みかんが基準財(numeraire) というわけです．}

図表 1.11 果物の分配 名前 満足度 みかん りんご 梨 A さん 14.2 10 5 0 B さん 18.8 0 15 0 C さん 16.3 10 0 5 2. 次に，果物の配分個数を等しく15個としたうえで，効用がもっとも低い人の値をなるべく 大きくするものとする．すなわち，目的関数を， min{uA, uB, uC} →最大化 とする．ただし，x, y, zの中から最小のものを選ぶ関数min{x, y, z}は，x, y, zに関する線 形な関数でないので，このままの形では線形計画問題にならない．定式化を工夫すること で，線形計画問題としてモデル化せよ． 演習問題1.6 ビタミン剤 製薬会社K2コーポレーションがビタミン剤をつくっている．これには，ビタミンAが重量比 で8%，ビタミンBが重量比で4%，ビタミンCが重量比で2%以上含まれていなければならな い．一方，各ビタミン成分をつくるのに，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.7 ある工場では，原材料A，B，C，Dから２種類の製品を製造している．親会社との契約で，製 品P1をd1単位，P2をd2単位の量を価格pc₁，pc₂で納入しなければならない．それ以上生産 した分は，市場価格はpm₁，市場価格はpm₂ で販売することができる． 製品Pi (i = 1, 2)を１単位作るために必要な原材料A，B，C，Dの量は，それぞれaAi ，aBi， aC i，aDi 単位である．原材料A，B，C，Dの１単位当たりの価格をそれぞれqA，qB，qC，qD とし，予算がbであるとき，この工場の最適な生産計画を表す問題を作れ．ただし，売れ残り は考えないことにする． 演習問題1.8 キャンディーづくり 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.9 ジュース 1. 食品メーカーK1社は，農家からオレンジを購入して，袋づめにして売っている．また，オ レンジを加工してジュースをつくり，販売している．また，すでに加工済のグレープフルー ツジュースを購入して，オレンジジュースと混ぜてミックスジュースをつくっている．予 算が500万円あったとして，表1.13の情報に基づいて，売り上げを最大にする原料の購入 量，商品の製造量を求めよ． 図表1.13 原料と価格の情報 オレンジ1kg の購入価格: 300 円 オレンジ1kg の販売価格: 500 円 オレンジジュース1kg の販売価格: 600 円 オレンジジュース1kg に必要なオレンジの重量: 0.8kg グレープフルーツジュース1kg の購入価格: 250 円 ミックスジュース1kg に必要なオレンジジュースの量: 0.5 kg ミックスジュース1kg に必要なグレープフルーツジュースの量: 0.3 kg ミックスジュース1kg の販売価格: 800 円 2. 前の問題で与えられた情報に加えて，需要の予測が手に入った． オレンジジュースとミックスジュースの需要が，それぞれ 3000kgと1500kgであるとし て，需要を必ず満たしたうえで，売り上げを最大にする原料の購入量，商品の製造量を求 めよ．なお，この需要は最低満たすべき需要であり，超過分もすべて売れるものとする． 3. 前の問題では，需要は必ず満たす必要があった． 今度は，必ずしも需要を満たさなくても良いが，不足分にはペナルティがかかることにす る．オレンジジュースの不足に対しては，1kgあたり200円，ミックスジュースの方は1kg あたり300円のペナルティーがかかる．売り上げから(もしあれば)ペナルティーを引いた 額が最大になるように製造計画を立てよ．需要を超過した分もすべて売れるものとする． 4. 前の問題の設定では，需要の超過分はすべて売れるものとした．新たに，需要の超過分は 安い価格でしか処分することができないものとする．超過分については，オレンジジュー ス，ミックスジュースがそれぞれ1kgあたり，100円，120円ですべて売り切ることがで きるとしたとき，最適な製造計画を立てよ．

1.3.3 時間軸を含む問題

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

クッキーの作成スケジュール 大学祭で販売するクッキーは手作りです．材料を買ってきて，クッキーを焼き，袋づめをする まで，すべて自分達でこなさなければなりません．昨年は，責任者がいい加減な計画しか作らな かったせいで，サークルのメンバー全員が直前になってたいへん忙しい思いをしました．今年の責 任者であるあなたは，まともな計画を立てるよう圧力をかけられています． 計画では4 種類のクッキーをつくることになっています．しかし，スケジュールを計画するた めに単純化して，1 種類だけ作ることにしましょう．このクッキーは一度に 20 枚焼けるものとし， その時間は18 分であるとします9．1000 枚をつくるには，のべ 50 回クッキーを焼く工程が必要で す．単純計算で，50 × 18=900 分かかることになります． 材料をまぜて生地を作る工程は手分けして効率的に進めることができるので，調理（オーブン で焼く工程）時間の配分のみに着目して作業スケジュールを考えてみましょう．オーブンを持って いる部員に，大学祭直前の5 日間に作業にさける時間を聞いたところ，表 1.14 のような回答をえ ました．作業可能な時間は優先度によって高・中・低の三つに分かれています．優先度高として計 上されている時間は，クッキー作成のために優先的に使える時間です．優先度中は，クッキー作成 のため使ってもいいが，他のこともしたいと考えている時間で，優先度低は，できればクッキー作 成以外のことに使いたいと考えている時間です． 優先度の大小を数値で表現するために，次の質問をしてみました． 優先度高の時間にクッキーをつくるときに時給500 円がもらえるとして，優先度中の 時間にクッキーをつくるときに時給はいくらほしいか．また，優先度低の時間ではい くらか． それにたいして，優先度中のときは600 円，優先度低のときは 750 円という回答がえられました． これにもとづき，時間の重みとして， 優先度高: 優先度中 : 優先度低 = 500 : 600 : 750 = 1 : 1.2 : 1.5 を採用することにします． 図表 1.14 大学祭までの 5 日間に使える労働時間 準備期間 1 日目 2 日目 3 日目 4 日目 5 日目 優先度高（時間） 4 5 1 3 1 優先度中（時間） 2 2 2 2 2 優先度低（時間） 4 4 2 2 2 ここで重要なことをあなたは思い出しました．毎年そうなのですが，出来上がって部室におい てあるクッキーを，味見と称して部員がつまみ食いしてしまうのです．あまりきびしく注意すると 作業に協力してもらえなくなるので，手間賃だと割りきることにしました．どうやらつまみ食いに よってなくなる量は一定の比率にしたがい，一日あたりおいてあるクッキーの10 ％と見積もるこ とができるようです． つまみ食いの総量を減らすには，なるべくクッキーを長時間部室においておかないことです．だ から大学祭直前に集中的に作ってしまうのがよいのですが，一方で投入できる作業時間には限りが あります．あなたの目標は，予定の製品数を達成し，かつなるべく優先度の低い労働時間を減らす ことです．準備期間中の作業時間をどのように配分してクッキーを作成すべきでしょうか． 9_{1.1.2 節での最適な作成枚数を重みとして 4 種のクッキーの調理時間の平均を取ると約 18.3 分となります．}

問題を定式化するにあたって，次のような記法を用います． xt：t 日目に作るクッキーの枚数 (t = 1, . . . , 5) yt：t 日目までに作った累計クッキー数 (t = 1, . . . , 5) ut：t 日の優先度高の作業時間 (t = 1, . . . , 5) vt：t 日の優先度中の作業時間 (t = 1, . . . , 5) wt：t 日の優先度低の作業時間 (t = 1, . . . , 5) 一日の作成枚数とその日までの累計枚数の関係は，次のようになります．例として，3 日目を 考えましょう．2 日目までに作ったクッキーの累計枚数は y2です．そのうちの10 ％が消費されて しまうので，3 日目には 0.9y2が残っています．3 日目に作成する量は x3なので，3 日目の累計枚 数y3は y3= x3+ 0.9y2 (1.15) となります． 作成枚数と作業時間の関係を，やはり3 日目の例で見てみます．3 日目の作成枚数は x3枚です． 18 分で一度に 20 枚焼けるとしているので，必要な作業時間は18 60∗ x203 = 0.015x3(時間) と見積も ります．作業にあてられる時間の制約は， 0.15x3≤ u3+ v3+ w3, u3≤ 1, v3≤ 2, w3≤ 2 (1.16) と表されます． 目的関数は，優先度に応じた重みをつけて評価した作業時間とします． u1+ u2+ u3+ u4+ u5+ 1.2v1+ 1.2v2+ 1.2v3+ 1.2v4+ 1.2v5 +1.5w1+ 1.5w2+ 1.5w3+ 1.5w4+ 1.5w5 (1.17) (1.15)(1.16)(1.17) をまとめると次のような問題になります． min ∑5 t=1 ut+ 5 ∑ t=1 1.2vt+ 5 ∑ t=1 1.5wt s.t. y1= x1 y2= x2+ 0.9y1 y3= x3+ 0.9y2 y4= x4+ 0.9y3 y5= x5+ 0.9y4 y5≥ 1000 0.015x1≤ u1+ v1+ w1, 0.015x2≤ u2+ v2+ w2, 0.015x3≤ u3+ v3+ w3, 0.015x4≤ u4+ v3+ w4, 0.015x5≤ u5+ v3+ w5, u1≤ 4, u2≤ 5, u3≤ 1, u4≤ 3, u5≤ 1 v1≤ 2, v2≤ 2, v3≤ 2, v4≤ 2, v5≤ 2 w1≤ 4, w2≤ 4, w3≤ 2, w4≤ 2, w5≤ 2 xt≥ 0, yt≥ 0, ut≥ 0, vt≥ 0, wt≥ 0, t = 1, . . . , 5 (1.18)

図表 1.15 クッキーの作成スケジュール 準備期間 1 日目 2 日目 3 日目 4 日目 5 日目 優先度高(ut) 0 5 1 3 1 優先度中(vt) 0 0 2 2 2 優先度低(w_t) 0 0 0 0 1.4 作成枚数(xt) 0 333.3 200.0 333.3 295 累計枚数(yt) 0 333.3 500.0 783.3 1000 (1.18) を解いた結果は表 1.15 となりました．ポイントとなるのは，5 日間のうち実際の作業は 4 日間で済むこと，また5 日目のみ優先度の低い時間を使うことなどです．あとは，この計算結果を 出発点として，作業に携わる人と相談しながら実際の作業スケジュールを作ることになるでしょう． 念のために，つまみ食いの比率をかえて計算してみました．なぜならこの数値が一番大雑把な 見積もりだからです．比率を0.02 と 0.2 の場合の結果を表 1.16 に示しました．つまみ食いの比率 が倍になっても，それほど大きな変化はないようですが，つまみ食いの比率を0.02 とすると，1 日 目から作業が始まるようになります．そのかわり，優先度が低い時間は使いません．もしどうして も優先度の低い時間を使いたくないなら，部員に厳しく注意してつまみ食いの比率を減らす努力を してもよいかもしれません． 図表 1.16 つまみ食いの比率を変えた場合のスケジュール 比率 準備期間 1 日目 2 日目 3 日目 4 日目 5 日目 0.02 優先度高(ut) 4 5 1 3 1 優先度中(vt) 0 0 0 0 1.7 優先度低(wt) 0 0 0 0 0 作成枚数(xt) 266.7 333.3 66.7 200 180.28 累計枚数(y_t) 266.7 594.7 649.4 836.5 1000 0.2 優先度高(u_t) 0 4.8 1 3 1 優先度中(vt) 0 0 2 2 2 優先度低(wt) 0 0 0 2 2 作成枚数(xt) 0 322.9 200.0 466.7 333.3 累計枚数(yt) 0 322.9 485.3 833.3 1000 クッキーの作成スケジュールの問題は，在庫問題と見なせます．つまみ食いされてしまうクッ キーの量は，一般的には保管費用と位置づけることができるでしょう． 土地の開墾 農家が荒地を開墾して5 年間かけて 100 ヘクタールの畑地を作るつもりでいます．開墾した土 地は翌年から作物を植えて，収入を得ることができます．1 単位の投資額により 5 ヘクタールの土 地の開墾が可能です．作られた畑地1 ヘクタールからは 0.25 単位の収入が得られます． 一方で，5 年間の間には，借金の返済や機材の購入などで以下のような資金需要が発生します． 2 年目：10 単位 4 年目：40 単位 5 年目：20 単位 この資金需要に対応し，かつ100 ヘクタールの畑地を作るためには，最低で何単位の初期投資額が 必要で，各年度に何ヘクタールの土地を開墾するべきでしょうか．

変数を以下のようにおきます． x0：初期投資額 xt：t 年の投資額 (t = 1, . . . , 5) yt：t 年末の畑地面積 (t = 1, . . . , 5) zt：t 年末の保有額 (t = 1, . . . , 5) 2 年目を例にとり，お金の動きと畑地の関係を見てましょう．2 年目に x2単位の投資をすると， その年の終わりは5x2ヘクタールの畑地が新たに得られます．したがって， y2= y1+ 5x2 という関係が得られます．2 年目の支出として，10 単位の支払いがあり，x2単位を開墾に使いま す．収入は，前年度の繰越金z1とその年の収穫から得られる0.25y1です（2 年目に畑地として使 えるのはy2ヘクタールではなくy1ヘクタールであることに注意してください）．よって， z2= z1− 10 − x2+ 0.25y1 となります．開墾のための投資は年度の始めに行うので，前年度末の保有額以上の投資はできない ものとします．すると，投資額に上限が存在して，x2≤ z1と表されます．以上をまとめると，次 のような問題が得られます． min x0 s.t. z1= x0− x1 z2= z1− 10 − x2+ 0.25y1 z3= z2− x3+ 0.25y2 z4= z3− 40 − x4+ 0.25y3 z5= z4− 20 − x5+ 0.25y4 y1= 5x1 y2= y1+ 5x2 y3= y2+ 5x3 y4= y3+ 5x4 y5= y4+ 5x5 y5≥ 100 x1≤ x0, x2≤ z1, x3≤ z2, x4≤ z3, x5≤ z4 xt≥ 0, yt≥ 0, zt≥ 0, t = 1, . . . , 5 (1.19) (1.19) を解くと， x1= 13.1 x2= 0 x3= 6.3 x4= 0 x5= 0.6 y1= 65.3 y2= 65.3 y3= 97 y4= 97 y5= 100 z1= 0 z2= 6.3 z3= 16.3 z4= 0.6 z5= 4.3 となり，初期投資額x0= 13.1 です． 演習問題1.10 元金均等返済とは，借入金を返済する方式の一つである．たとえば，借入金が100万円で，1回 あたりの金利1%，10回払いの元金均等返済の場合，毎回10万円(=100/10)とその時点の残高 の金利分を支払う．3回目の支払額は 10 + (100 − 20) ∗ 0.01 = 10.8万円

である． 上記の開墾の問題では，5年間の資金需要が与えられていた．ここでは，初期投資額を全額借入 金でまかない，発生する資金需要が借入金の返済のみであるとする．借入金の返済を5年間の元 金均等返済方式とし，金利は年利5%とする．初期投資額を最小にする問題を定式化せよ． 演習問題1.11 販促活動 あるビールのメーカーが，新しい製品の販売促進のためにキャンペーンを行おうとしている．キャ ンペーンを一定期間行うと，その期の売上が上昇する．売上の上昇率はキャンペーンに投入した 費用に比例しており，経験的に次の関係にあることがわかっている． [当期の売上の上昇率] = 0.8 × [当期の費用] + 0.2 × [前期の費用] − 0.05 × [前前期の費用] キャンペーンの期間は連続する4期間を予定しており，総費用は15億円を予定している．ただ し，それぞれの期間に投入できる費用の上限はあらかじめ決められており，それは表1.17の通 りである．4期間の売上の上昇率の合計を最大にするには，各期にどれだけの費用をかければよ いか． 図表 1.17 予算の上限 期 第1 期 第 2 期 第 3 期 第 4 期 総額 費用の上限 7 3 7 5 15

1.4

線形計画問題の性質

1.4.1 実行可能，非有界

単純な問題をもちいて，線形計画問題の性質を示していきます． まず次の問題を考えましょう． max x1+ x2 s.t. x1+ 2x2≤ −3 x1≥ 0, x2≥ 0 (1.20) 制約式に着目してください．x1+ 2x2が−3 以下でなければならいとあります．一方，非負条件か らx1+ 2x2は常に0 以上です．したがって，問題 (1.20) の制約条件を満たす (x1, x2) は存在しませ ん．このように，制約条件を満たす変数の組が存在しない場合，その問題は実行不可能(infeasible) と呼びます．逆に，制約条件を満たす変数の組がただ一つでも存在すれば，その問題は実行可能 (feasible) です．制約条件を満たす変数の組は，実行可能解 (feasible solution) と呼ばれます．

問題(1.20) の制約式を少し変えました． max x1+ x2 s.t. −x1+ 2x2≤ 3 x1≥ 0, x2≥ 0 (1.21) 問題(1.21) は制約条件を満たす実行可能解，たとえば (x1, x2) = (1, 1) が存在します．(x1, x2) = (1, 1) で目的関数の値を評価すると，1 + 1 = 2 です．第 1 成分に正数 t を加えて，(1 + t, 1) とし ても， −(1 + t) + 2 ∗ 1 = 1 − t ≤ 3

なので，実行可能性は保たれます．目的関数値は，(1 + t) + 1 = 2 + t で t の分だけ増加していま す．実行可能性を保ったまま，t はいくらでも大きくできるので，目的関数値も無限に大きくする ことが可能です．このような場合，その問題は有界でない10(unbounded) といいます． より正確に述べれば，線形計画問題が有界でないのは，  実行可能解 ^x にたいして，ある方向ベクトル d が存在し，任意の正数 t にたいして ^x + td が 実行可能解であること，  ^x で評価した場合に比べて，^x + td で評価した場合の方が，目的関数値が改善していること， が同時に成り立っていることです．片方だけでは不十分です． このことを明らかにするために，問題(1.21) の目的関数の係数を変えてみましょう． max −x1+ x2 s.t. −x1+ 2x2≤ 3 x1≥ 0, x2≥ 0 (1.22) 問題(1.22) の制約条件は，問題 (1.21) と同じなので，d = (1, 0) の方向に無限に進めることは共通 です．しかし，問題(1.22) では，その方向に進んでも解は改善しません．この問題には最適解が存 在し，それは(0, 1.5) です． 以上をまとめておきます．  線形計画問題において，すべての制約式を満たすことができない場合がある．この場合，そ の問題は実行不可能(infeasible) であるという．  実行不可能でないならば，その問題は実行可能 (feasible) である．  制約を満たす解は，実行可能解 (feasible solution) と呼ばれる．  最大 (小) 化の問題が実行可能であり，かつ目的関数値を無限に増加 (減少) させることがで きる場合，その問題は有界ではない．最適解は存在しない．  問題が実行可能かつ，無限解を生成しないならば，最適解が存在する．

1.4.2 LP の図解

制約領域 次の線形計画問題を図示によって解くことにします．目的関数の係数は，具体的な数値を入れ ずに，(c1, c2) としてあります． max c1x1+ c2x2 s. t. x1+ x2 ≤ 6 2x1+ x2 ≤ 10 x2 ≤ 3 x1, x2 ≥ 0 (1.23) 問題(1.23) の制約領域 (制約を満たす x₁，x₂の集合) を S とおきます．S は x₁{x₂平面上に， 1.18 のように図示することができます． 10_{非有界とも言います．}

図表 1.18 制約領域 S

x

1

x

2

0

(5,0)

(6,0)

(4,2)

(3,3)

(3.5,3)

(0,3)

A

B

C

D

E

F

O

S

目的関数の等高線 目的関数は傾き(c1, c2) を用いて，図示することができるます．制約領域に目的関数の等高線 を書くことで，最適解を図から求めることもできます．等高線とは，目的関数値が同じ値となる点 を線で結んで表したもので，関数が線形なら\直線" となります． 傾きがかわると，最適解もかわることに注意してください． 図から明らかなように最適解は，(存在するならば) かならず端点で達成されます．参考までに， 無限解を生成する場合の例(問題 (1.24)) を図 1.21 に示しました． max c1x1+ c2x2 s. t. x1+ x2 ≥ 6 2x1+ x2 ≥ 10 x2 ≥ 3 x1, x2 ≥ 0 (1.24) 演習問題1.12 パラメータαを用いて，線形計画問題が次のように定義されている． max x1− x2 s. t. 2x1− 3x2≤ −3 αx1− x2≤ 3α − 3 x1, x2≥ 0 この問題が最適解を持つためのαの条件を調べ，最適解を求めよ． [ヒント] x1-x2平面上で，αx1− x2= 3α − 3で表される直線は，αの値によらず，座標(3, 3) を必ず通る．

図表1.19 制約領域 S と目的関数の等高線 (1) x 1 x 2 0 (C1,C2) 図表1.20 制約領域 S と目的関数の等高線 (2) x 1 x 2 0 (C1,C2)

図表 1.21 無限解の例 x 1 x 2 0 (C1,C2)

1.4.3 方程式系の変形

問題(1.23) の目的関数の係数を (c1, c2) = (3, 2) とし，さらにスラック変数を導入して標準形 (1.25) へ変形します． max 3x1+ 2x2 s. t. x1+ x2+ x3 = 6 2x1+ x2+ x4 = 10 x2+ x5 = 3 x1, x2, x3, x4, x5 ≥ 0 (1.25) まず，非負制約を除いた3 本の制約式だけに着目します． x1+ x2 +x3 = 6 2x1+ x2 +x4 = 10 x2 +x5 = 3 (1.26) (1.26) は変数が 5 つで，方程式が 3 本の連立方程式です．ふたつの変数 x2，x4を選んで，他の 変数を表してみましょう．(1.26) の 1 本目の式から，x1= −x2− x3+ 6 を得るので，これを 2 本 目の式に代入します． x1 +x2 +x3 = 6 −x2 −2x3 +x4 = −2 x2 +x5 = 3 (1.27)

(1.27) の 2 本目の式から，x3= −0.5x2+ 0.5x4+ 1 として，1 本目の式に代入すると， x1 +0.5x2 +0.5x4 = 5 −x2 −2x3 +x4 = −2 x2 +x5 = 3 (1.28) が得られます．目的関数に目を向けましょう．問題(1.25) の目的関数を z = 3x1+ 2x2 とおきます．(1.28) の 1 本目の式を用いて，x1を消去すると， z = 3 ∗ (5 − 0.5x2− 0.5x4) + 2x2= 15 + 0.5x2− 1.5x4 (1.29) となり，こちらもx2，x4のみで表すことができました．(1.28) と (1.29) まとめ，x2, x4を左辺に 移項すると， z = 15 +0.5x2 −1.5x4 x1= 5 −0.5x2 −0.5x4 x3= 1 −0.5x2 +0.5x4 x5= 3 −x2 (1.30) となります．この変形が何を意味しているか，具体的に検討してみましょう． 等価な方程式系 もとの問題(1.25) から，非負条件を除き，目的関数を z とおいて，方程式系として示すと， z = 3x1+ 2x2 x1+ x2+ x3= 6 2x1+ x2+ x4= 10 (1.31) x2+ x5= 3 となります．(1.30) は，(1.31) から代入操作だけで得らるので，両者は等価な方程式系ということ ができます．等価というのは，一方の方程式系をみたす解は，かならず他方の方程式系を満たすと いうことです． 演習問題1.13 (1.31)を満たす(x1, x2, . . . , x5)の値を計算で求め，それが(1.30)を満たしていることを確認せ よ．逆に，(1.30)を満たす(x1, x2, . . . , x5)の値を計算で求め，それが(1.31)を満たしているこ とを確認せよ．

1.4.4 基底形式表現

(1.30) は，左辺の z, x1, x3, x5を右辺のx2とx4で表している構造になっています．言葉を変え ると，x2とx4の値を適当に決めると，自動的にz, x1, x3, x5が決まるということです． 方程式系のこのような表し方を基底形式表現といいます11．ここで，左辺に現れているx1, x3, x5

を基底変数(basic variable)，右辺の x2, x4を非基底変数(nonbasic variable) と呼びます．

基底形式表現の特徴は，非基底変数を0 とおくことで，ただちに基底変数の値と目的関数値が得 られることです．(1.30) で，x2= x4= 0 とおくと，x1= 5, x3= 1, x5= 3, z = 15 が得られます． 同じ結果を，(1.31) で得ようとすると，やや面倒な計算が必要です．(1.31) において，x2= x4= 0 とすると， x1+ x3= 6 2x1+ x4= 10 x5= 3 が得られ，これを連立方程式として解いてx1 = 5, x3 = 1, x5 = 3 を得ます．そして，これを z = 3x1+ 2x2に代入して，ようやくz = 15 が得られるのです． 基底解と端点 基底形式表現において，非基底変数を0 とおいたときの解を基底解 (basic solution) と呼びま す．基底解がすべて非負であったなら，それを実行可能基底解(feasible basic solution) と呼びま す．基底解にはどのような意味があるのでしょうか． (1.30) から得られる基底解は，x1= 5, x2= 0, x3= 1, x4= 0, x5= 3 です (これは実行可能 基底解です)．スラック変数の導入前の変数は，x1とx2だけでした．(x1, x2) = (5, 0) という座標 は，図表1.18 における点 D に相当します． もう一つ，例を出します．x3，x4を非基底変数とする基底形式表現を求めると， z = 16 −x3 −x4 x1= 4 +x3 −x4 x2= 2 −2x3 +x4 x5= 1 +2x3 −x4 (1.32) が得られます．この場合の基底解は， x1= 4, x2= 2, x3= 0, x4= 0, x5= 1 なので，もとのx1-x2平面上では，(x1, x2) = (4, 2) の座標を表し，点 C に相当します． このことからわかるように，実行可能基底解は制約領域の端点を表しているのです．そして，線 形計画問題の最適解が端点で達成されることを考えれば，実行可能基底解が重要な意味を持つこと が理解できるはずです． 演習問題1.14 x1, . . . , x5の中から適当な変数の２つ選び，それを非基底変数とした基底形式表現を求めよ．そ こから基底解を求め，それが図表1.18において，どの点に相当するか確認せよ． [注意]変数の選び方によっては必ずしも実行可能基底解とはならない．実行可能でない場合，対 応する点は領域Sの外側に位置する．

1.4.5 基底の更新

上述の２つの基底形式表現を，再度，示しておきます． 点D に対応        z = 15 +0.5x2 −1.5x4 x1= 5 −0.5x2 −0.5x4 x3= 1 −0.5x2 +0.5x4 x5= 3 −x2 (1.30) 点C に対応        z = 16 −x3 −x4 x1= 4 +x3 −x4 x2= 2 −2x3 +x4 x5= 1 +2x3 −x4 (1.32) (1.30) における (実行可能) 基底解は，非基底変数 x2, x4を0 とおくことで得られます．(1.30) の目的関数の式を見ると， z = 15 + 0.5x2− 1.5x4 となっています．x2の係数は，0.5 と正数なので，x2を0 から増加させることで目的関数の値を 改善することが可能です．x4を0 に固定したまま，x2を0 から t まで増やしてみると，その他の 値は，次のように変わります． z = 15 +0.5t x1= 5 −0.5t x3= 1 −0.5t x5= 3 −t (1.33) t を大きくすれば，目的関数値 z = 15 + 0.5t も増加します．しかし無限に t を増加させることはで きません．なぜならば，t を増加させると，基底変数である x1, x3, x5の値が減少していき，つい には負の値になってしまうからです．そうなっては，実行可能でなくなってしまいます．実行可能 性を保ちつつt を大きくすると，t = 2 が最大となります．このとき，x3= 0 です． ここで，以下の点を確認してください．  (1.30) において，3 本目の式 x3= 1 − 0.5x2+ 0.5x4を，他の式に代入して整理すると，(1.32) が得られる．  (1.30) の非基底変数 x2が(1.32) では基底変数に入り，(1.30) の基底変数 x3が(1.32) では非 基底変数に出ていっている．  (1.32) における基底解での目的関数値は 16 であり，これは，15 + 0.5 ∗ 2 と等しい． 上記のように，非基底変数と基底変数を交代することで，目的関数値を改善することを，基底 の更新といいます．この操作は，幾何学的には，隣りの端点へ動くことに対応しています． 演習問題1.15 (1.30)で，x4の値を増加させて(この場合，目的関数の値は減少する)，最初に0になった基底 変数と入れ替えをおこなうと，どのような基底形式表現が得られるか? また，それは図表1.18 のどの点に対応するか?

最適解 (1.30) の基底を更新することで，(1.32) が得られました．(1.32) の解をさらに改善することは できるでしょうか．目的関数の式を見ると， z = 16 − x3− x4 となっているので，非基底変数であるx3とx4の値を0 から増加させても，目的関数の値は増加 しません．実際，(1.32) は，最適解を与えています． (1.32) によって最適解が得られていることは，次のようにして確かめることができます．基 底形式表現はすべて等価な方程式系であることを思い出してください．したがって，実行可能解 (^x1, . . . , ^x5) に対しては，いかなる基底形式表現もその目的関数は同じ値をとります．もとの問題 (1.25) の目的関数と (1.32) の目的関数の値を実行可能解で評価すると， z = 3^x1+ 2^x2= 16 − ^x3− ^x4 と成り立ちます12．実行可能解であるならば，^x3≥ 0, ^x4≥ 0 なので， z = 3^x1+ 2^x2≤ 16 という不等式が成り立ちます．したがって，任意の実行可能解で評価した目的関数値はかならず16 を下回ることから，16 が最適値であることが言えます． 最適な基底であることの条件は，次の通りです． 最大（小）化問題では，基底形式表現において， 目的関数の係数がすべて0 以下（以上）であること 単体法 線形計画法の解法の一つである単体法(simplex method) は，初期実行基底解から出発して，次々 に基底を更新することで最適解を求める手法です．その概略は上で示したとおりですが，他にも考 慮しなければならないことがたくさんあります．  問題が実行不可能であることをどのように判定するか．  実行不可能でなかったとして，初期実行可能基底解をどのようにみつけるか．  問題が有界でなかった場合，どのようにしてそれを判断するか．  必ず基底は更新できるのか．  単体法は，有限回の手続きで終了するのか． これらは講義では取り扱いません．詳しくは専門書を参照してください．

図表1.22 家具製造における資源量，価格，保有量 テーブル シェルフ 保有量 木材 1 1 6 金属 2 1 10 ガラス 0 1 3 製品価格 3 2

1.4.6 感度分析１

最適解を表現する基底形式表現がわかると，それを用いて感度分析を行うことができます．例 として，家具工場の製造計画問題を考えてみることにしましょう． この家具工場では，原材料として木材・金属・ガラスを用い，製品としてテーブル・シェルフ を製造しています．それぞれ製品1 単位の生産に必要な資源の量，製品価格，投入可能な資源の量 は図表1.22 の通りです 製品がすべて売れるとの仮定のもとで，売上を最大にする製造量を求める問題は，次のように 定式化されます． max 3x1+ 2x2 s. t. x1+ x2 ≤ 6 2x1+ x2 ≤ 10 x2 ≤ 3 x1, x2 ≥ 0 (1.34) これは，(1.23) と同じ問題であることに注意してください．最適解を与える基底形式表現は，すで にわかっている通り， z = 16 −x3 −x4 x1= 4 +x3 −x4 x2= 2 −2x3 +x4 x5= 1 +2x3 −x4 (1.32) です． 価格の変化 今，製品価格は，テーブルが３，シェルフが２です．ここで，シェルフの価格を変化させたと き，最適解や最適値がどのように変化するか，検討してみましょう．もっとも単純な方法は，新し い価格体系のもとで，再度線形計画問題を解くことです．しかし，すでに最適解をあたえる基底形 式表現がわかっている場合，問題を解くことなく最適解の変化を知ることができます． まず，シェルフの価格が2 から 2.5 に変化した場合を考えてみましょう．(1.32) では，目的関数 は，z = 16 − x3− x4と表されています．これは，もともとの目的関数z = 3x1+ 2x2を， z = 3x1+ 2x2 = 3(4 + x3− x4) + 2(2 − 2x3+ x4) 12_{実行可能解である(5, 0, 1, 0, 3)，(0, 0, 6, 10, 3)，(3, 3, 0, 1, 0) などを代入して確認してください．}

としたものです．シェルフの価格が2 から 2.5 に変化すると， z = 3x1+ 2.5x2 = 3(4 + x3− x4) + 2.5(2 − 2x3+ x4) = 17 − 2x3− 0.5x4 となります．目的関数値は16 から 17 になりました．しかし，係数は負のままなので，この基底 形式表現が最適解を与えることに変わりはありません．目的関数の値と係数以外は変化がないの で，最適解も変わりません．つまり，シェルフの価格を少し変化させても，最適値が若干変化した 以外，生産量は同じです． では，シェルフの価格を2 から 4 まで変化させるとどうなるでしょうか? この場合，基底形式 表現は， z = 20 −5x3 +x4 x1= 4 +x3 −x4 x2= 2 −2x3 +x4 x5= 1 +2x3 −x4 (1.35) となります．目的関数のx4の係数が正となったので，x4を0 から増やし，新しい基底変数を x1, x2, x4 とすると， z = 21 −3x3 −x5 x1= 3 −x3 +x5 x2= 3 −x5 x4= 1 +2x3 −x5 (1.36) となります．これは，最適解です． シェルフの価格が2.5 であれば最適解は変わらず，4 とすると最適解が変化しました．2.5 と 4 の 間に最適解が変化する価格が存在することがわかります．具体的にそれを求めてみましょう．シェ ルフの価格の変化量をδ とおくと，新しい価格は 2 + δ と表されます．最適解が変化しない，すな わち基底解の構成が変化しないためには，その基底が最適基底であることの条件をみたしていなく てはなりません．新しい価格2 + δ で目的関数を表現すると， z = 3x1+ (2 + δ)x2 = 3(4 + x3− x4) + (2 + δ)(2 − 2x3+ x4) = 16 + 2δ + (−1 − 2δ)x3+ (−1 + δ)x4 となります．その基底が最適であるための条件(34 ページ) より，目的関数の係数が 0 以下でなく てはなりません．よって，δ は −1 − 2δ ≤ 0 −1 + δ ≤ 0 を満たしている必要があります．すなわち，−0.5 ≤ δ ≤ 1 となるので，シェルフの価格が 1.5 から 3 の範囲にあるときは，最適な生産量は変化しません． 演習問題1.16 上記の問題において，シェルフではなくテーブルの価格を変えてみよう．最適な生産量が変化し ないためのテーブルの価格の範囲を求めよ．