( ) ? () 1.1 ( 3 ) j x j 10 j 1 10 j = 1,..., 10 x 1 + x x 10 =

第

1

章 線形計画法

—

ベスト・ミックスを探せ

!

この章では，線形計画法 (Linear Programming, LP) の基礎を学びます．LP は， ORの基本的なツールの一つです．ここから派生した様々なツールが存在します． LPには数多くの応用例が存在しますが，まずは「ベスト・ミックス」を見つけ る方法なのだと理解してください．

1.1

クッキー販売の模擬店

1.1.1

営業方針

あなたの所属するサークルでは，毎年大学祭でクッキーをつくって販売しています．経済学部 に所属しているからという根拠の薄い理由で，今年のクッキー屋の責任者はあなたに決まってしま いました．責任者は，商品の選択，原材料の調達，当日のスケジュール調整，売上の管理まで，ほ とんどすべてを引き受けなくてはなりません．仕事はどれもたいへんそうですが，将来経営者にな ることを夢見ているあなたは，これも一つのトレーニングだと，前向きに考えることにしました． さいわい，このサークルでは毎年クッキーの販売をしているおかげで，経験の蓄積があります． 基本的な営業方針はほぼ決まっています． 方針 1. お店はテイクアウト専用 方針 2. 実演販売はしない（というかできない）ので，商品はあらかじめつくっておく 方針 3. お金儲けが目的ではないが，最終的な損益は黒字にしたい 方針 4. 単品で売る 方針 5. 会計が混乱しないように，価格の構成はなるべく単純にしたい． あなたは，まず以下のことを決めなくてはなりません． • メニュー構成 (単品) どの種類のクッキーを作り，いくらで売るか． • メニュー構成 (詰め合わせ) どの組み合わせで売って，値段はいくらにするか． クッキーは事前に作っておかなくてはならないので，どの種類をどれくらい作るかは，営業成 績を左右する大きな要素です．今までいくつかの種類のクッキーをつくって売ってきた経験から， それぞれのクッキーの原料費や人気について，表 1.1 にまとめることができました．これを手がか りに，メニュー構成を考えることにしましょう．

図表 1.1 クッキーの種類と原料費，人気度 商品インデックス クッキーの種類 一枚当たりの原料費 (円) 人気度 1 クルミ 110 高 2 レモン 98 高 3 チョコ 85 高 4 セサミ 90 中 5 紅茶 73 中 6 プレーン 62 中 7 レーズン 92 低 8 パンプキン 88 低 9 キャロット 79 低 10 シナモン 75 低

1.1.2

単品での販売

はじめにもっとも単純な設定で，製造計画を立ててみましょう．方針 4 より，単品で売るクッ キーの値段はすべて同じにします．利益を最大にする商品構成は，どのようになるでしょうか? 人 気度を無視して考えると，とにかく原価が安いものを選べばよいことになります．すなわち，プ レーン・クッキーだけが販売されます．もちろんこんなことでは，模擬店の経営がうまくいくはず がありません．人気のある商品を増やし，品揃えを豊富にすることが必要でしょう． 人気の度合いに応じて，製造量を変えることにします．経験的に，人気の高い・普通・低い商 品の売上の比は，およそ３：２：１であることがわかっています．このことをふまえて，条件を次 のように整理してみましょう． • 全部で 900 枚つくる • 人気が低い種類でも，すくなくとも 40 枚以上つくる • 人気が中の種類は，最低 80 枚以上つくる • 人気が高い種類は，最低 120 枚以上つくる この条件を満たして，利益を最大にする (＝費用を最小にする) ためには，どの種類のクッキー をそれぞれ何枚作ればよいでしょうか．一見，複雑に見えますが，実は簡単に答えを求めることが できます．でもここでは，あえて回り道をして，条件を数式を使って表してみましょう． 表 1.1 の商品インデックスをつかってクッキーを区別します (つまり，第 3 番目のクッキーは チョコ・クッキーを表します)．ここで，第 j 番目のクッキーの製造枚数を xjという変数を使って 表してみましょう．クッキーは全部で 10 種類あるので，j は 1 から 10 までの整数値をとります． これを，j = 1, . . . , 10 とかくことにします．上の条件を式で表現すると x1+ x2+· · · + x10= 900 [総枚数の条件] x1≥ 120, x2≥ 120, x3≥ 120 [人気が高い商品の最低枚数の条件] x4≥ 80, x5≥ 80, x6≥ 80 [人気が中くらいの商品の最低枚数の条件] x7≥ 40, x8≥ 40, x9≥ 40, x10≥ 40 [人気が低い商品の最低枚数の条件]

となります．また，総製造費用は 110x1+ 98x2+ 85x3+ 90x4+ 73x5+ 62x6+ 92x7+ 88x8+ 79x9+ 75x10 です．今は，“与えられた条件のもとで，費用を最小化する” という問題を考えているところです． そこで式をまとめて，次のように書いてみましょう． minimize 110x1+ 98x2+ 85x3+ 90x4+ 73x5+ 62x6+ 92x7+ 88x8+ 79x9+ 75x10 subject to x1+ x2+· · · + x10= 900 xj≥ 120, j = 1, 2, 3 xj≥ 80, j = 4, 5, 6 xj≥ 40, j = 7, 8, 9, 10 (1.1) このように，与えられた条件の中で，目的となる値を最小 (あるいは最大) にするような変数の 値を求める問題を，一般に最適化問題と呼びます．与えられた条件を総称して制約と呼び，制約を 構成する条件式を制約式と呼びます．最小 (最大) 化する式は目的関数です．(1.1) は，最適化問題 の中でも特殊な性質を持つ問題です．これについてはまた後で触れることにします． (1.1)はどのようにして解けばよいのでしょうか？ 幸い，この問題は特別な技法を用いなくて も，少し推論を働かせれば簡単に解くことができます． 演習問題1.1 上の条件を以下のような条件に変えたとき，問題を(1.1)のように書き表しなさい． • 全部で900枚つくる • 人気が低い種類は，合計して160枚以上つくる • 人気が中の種類は，合計して240枚以上つくる • 人気が高い種類は，合計して360枚以上つくる それぞれ何枚つくればよいか．

1.1.3

比率の調整

前節では，人気の高低に応じて最低枚数を設定しました．結果を見ると，少々偏った計画になっ ています．手作業で，最低枚数を調整しながら何度も計算して，適当な製造枚数を求めることもで きますが，もう少しアプローチを変えて見ましょう． 売上の比は，人気の高い・普通・低い商品の順に，およそ３：２：１ ですから，この比率を直 接制約に組み込むことにします．ただし，厳密に製作枚数をこの比率に一致させるのではなく，あ る程度の幅を持たせることで，価格の差を反映させることができます．具体的には，人気別の商品 ごとに規準となる製作枚数を設定し，実際の製作枚数はそこから上下 20 ％以内に収まるようにし ました． それでは，制約式を定式化してみましょう．新しい変数として， y1：人気が高い商品の規準枚数 y2：人気が中の商品の規準枚数 y3：人気が低い商品の規準枚数

を導入します．それぞれのクッキーが，この規準枚数の上下 20 ％以内に収まる必要があるので， 0.8y1≤ x1≤ 1.2y1 0.8y1≤ x2≤ 1.2y1 0.8y1≤ x3≤ 1.2y1

0.8y2≤ x4≤ 1.2y2 0.8y2≤ x5≤ 1.2y2 0.8y2≤ x6≤ 1.2y2

0.8y3≤ x7≤ 1.2y3 0.8y3≤ x8≤ 1.2y3 0.8y3≤ x9≤ 1.2y3

0.8y3≤ x10≤ 1.2y3 となります．規準枚数の比率の制約は，次のように表すことができます． y1= 3y3 y2= 2y3 以上をまとめると，次の線形計画問題を得ます． minimize 110x1+ 98x2+ 85x3+ 90x4+ 73x5+ 62x6+ 92x7 +88x8+ 79x9+ 75x10 subject to x1+ x2+· · · + x10= 900

0.8y1≤ x1≤ 1.2y1 0.8y1≤ x2≤ 1.2y1 0.8y1≤ x3≤ 1.2y1

0.8y2≤ x4≤ 1.2y2 0.8y2≤ x5≤ 1.2y2 0.8y2≤ x6≤ 1.2y2

0.8y3≤ x7≤ 1.2y3 0.8y3≤ x8≤ 1.2y3 0.8y3≤ x9≤ 1.2y3

0.8y3≤ x10≤ 1.2y3 y1= 3y3 y2= 2y3 (1.2) 残念ながら，(1.2) は (1.1) のように簡単に手計算で解くことはできません．このような制約付 きの最適化問題は，解析的に解ける場合はまれで，数値計算により求めるのが一般的です．そのた めの方法には，多くの種類があり，問題固有の性質を生かして，適切な解法を適用することが重要 です．では，(1.1) や (1.2) の特徴は何なのでしょう？

1.2

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

線形計画問題の特徴 一般の制約付き最適化問題は ¯¯ ¯¯ 最小 (大) 化 xの関数 条件 xはある領域に属する という形をしています．線形計画問題の特徴は， • 目的関数が x の 1 次式であること • 制約領域が，1 次式もしくは 1 次不等式の組合わせで表されていること です．この条件が変わると，一見似ていてもまったく性質の異なる問題になります．

標準型 線形計画問題を表現するにはいくつかの流儀があります．まずは標準型 (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.3)

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

hand side)とよびます．係数を次のようにまとめて表すとこともできます．      a11 a12 · · · a1n a21 a22 a2n .. . . .. ... am1 am2 · · · amn      これは係数行列とよばれています．x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 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= (x1, . . . , xn)⊤ c= (c1, . . . , cn)⊤ b= (b1, . . . , bm)⊤ A=      a11 a12 · · · a1n a21 a22 a2n .. . . .. ... am1 am2 · · · amn     

標準型への書換え すべての線形計画問題は，標準型に帰着できます．以下のように，制約に不等式が含まれてい ても， 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.6) スラック変数 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.7) とすることができます． 自由変数を含む場合を考えてみましょう．問題 (1.8) の変数 x1には，非負制約も上下限制約も 与えられていないので，自由変数となります． maximize c1x1+ c2x2+· · · + cnxn subject to a11x1+ a12x2+· · · + a1nxn = b1 a21x1+ a22x2+· · · + a2nxn = b2 .. . am1x1+ am2x2+· · · + amnxn= bm x2≥ 0, . . . , xn≥ 0 (1.8) この場合は，自由変数を二つの非負変数の差で表します． x1= x+1 − x − 1 (ただし，x + 1 ≥ 0, x − 1 ≥ 0) そうすると，(1.8) は， maximize c1x+1 − c1x1−+ c2x2+· · · + cnxn subject to a11x+1 − a11x−1 + a12x2+· · · + a1nxn = b1 a21x+1 − a21x−1 + a22x2+· · · + a2nxn = b2 .. . am1x+₁ − am1x−₁ + am2x2· · · + amnxn = bm x+₁ ≥ 0, x−₁ ≥ 0, . . . , xn≥ 0 (1.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

食餌問題

サラダづくり 食餌問題 (diet problem) は，線形計画法の古典的な応用例です．たいていの線形計画法の教科 書には載っています．何らかの制約をみたした上で，配分・配合を決める問題の基本型といってい いでしょう．同じ形式の実務上の問題も数多く存在します． この問題を一言で言うと，「必要な栄養の基準を満たし，かつもっともコストの低い食餌は何か?」 です．単純な問題を例にとって説明しましょう． 図表 1.2 可食部 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.3 野菜の値段 (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.21_{にある野菜を使って，野菜サラダをつくります．いくつかの栄養素の中から，たんぱく} 質，ビタミン B1，ビタミン C に着目しました．これらの栄養素を一定の量以上取ることができて， 1_{食品データベースシステム (http://food.tokyo.jst.go.jp/) を利用しました．}

かつできるだけ安くするためには，どの野菜をどれだけ買えばよいのでしょうか．栄養素の必要量 は，それぞれ 10g，0.5mg，50mg としました2_{．価格は表 1.3 にある通りです．} 変数として，インデックス 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 です．栄養成分の要求量をみたし，かつ価格を最小にするには，以下の問題を解けばよいことにな ります． 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.10) 問題 (1.10) を解くと，最適解として， x1= 2.679 x2= 0.0 x3= 0.0 x4= 0.0 x5= 0.0 x6= 7.143 x7= 0.0 が得られます．残念ながら，かぼちゃともやしだけではあまり食欲はそそりません．しかも値段は なんと 722.8 円です．現実に活かすためにはもっと定式化に工夫が必要でしょう． 参考：食餌問題の系譜 はじめて食餌問題を論じたのは，Stigler[8] です．この時点では，まだ線形計画問題の効率的な 解法は知られていませんでした．Stigler は，当時の代表的と思われる食品 77 品目を対象に，カロ リー，たんぱく質，カルシウム，鉄分，ビタミン A，ビタミン B1，ビタミン B2，ナイアシン，ビ タミン C の必要量を考慮した問題を解いています．結果はやはり万人向けとは言いがたいメニュー です (表 1.4)．彼自身，論文でこう述べています．

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

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

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

500種以上の食品を対象に食餌問題を解くことにしました ([2])．最初に解いた問題から得られたメ

2_{「第６次改定日本人の栄養所要量」によると，18∼29 才の男性 (女性) が 1 日に必要な量は，たんぱく質 70(55)g，ビ}

図表 1.4 Stigler の結果：一日の摂取量 品名 小麦粉 キャベツ ほうれん草 パンケーキ粉 牛レバー 量 535 lb. 107 lb. 13 lb. 134 lb. 25 lb. ニューでは，酢を 500 ガロン (約 1890L3 _{)飲むべしとなったそうです．これは，酢のデータの作} り方に問題があったせいでした．酢を食品リストからはずして再度解いてみたところ．今度のメ ニューでは，一日に 200 個の固形ブイヨンを食べよ，となりました．それでもへこたれずに，制約 を見直して4_{再挑戦したら，ふすま (bran) を 2 ポンド (約 900g) 食べるはめになりました．さらに，} ふすまの量に上限を課し，4 度目に解いたところ，糖蜜 (blackstrap molasses) が 2 ポンド (約 900g) とでてきました．ここにいたって，奥さんが減量メニューは自分で作ると宣言したので，Dantzig もあきらめたようです． 問題の設定は単純なのですが，現実的な解を導くのは簡単ではないようです．しかし，多くの 工夫を用いることで，線形計画法によって，栄養の条件を満たし，適度に美味しく，かつバラエ ティにとんだメニューをつくることは可能です．実際に病院，療養所，介護施設，学校，刑務所な どで，この手法が用いられて成果を上げています．一定期間にわたるメニューの構成を考える問題 は，メニュー・スケジューリング問題と呼ばれていて，線形計画問題よりやや解くのが難しい問題 として定式化する必要があります．

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

いて，次の点を工夫しています． • 目的関数を費用ではなく，主観的な受け入れやすさとした • 食品の候補に個人の選好を反映させた • 制約に自由度を持たせた 病院で特定の患者に対して食餌を処方する場合を考えます．患者は栄養士といっしょに現在の 食餌の情報を入力し，これが出発点になります．ついで，患者に必要な栄養成分を入力すると，新 しいメニューが出力されます．これは，栄養の必要量を満たしているメニューのなかで，現在の食 餌にもっとも “近い” ものが提示されます．通常は，ここで提案されるメニューは患者の好みとは 一致しない場合が多いので，モデルを改良するプロセスに入ります． 1. 上下限を導入する 2. 比率の制約を導入する 3. 必要栄養成分を調整する 4. 食品の追加，削除，入れかえを行う 定式化の詳細も興味深い内容を含んでいますが，LP を習い始めたばかりでは手に余るかもし れません．今回は触れないでおきます．論文に載っていた，慢性腎不全の患者のためのメニューだ けを紹介しましょう．表 1.5 がその結果です．回数をおうごとに，制約が見直され，そのためにだ んだんと食品の構成が現実的になっていくことが見て取れます．

1.3.2

配合を決める問題

食餌問題それ自体も重要な応用問題ですが，ほかにもおなじ形式をもつ重要な問題があります． 3_{1升瓶千本以上です．} 4_{Dantzigは，ブイヨンの個数を変えてつくったスープを飲んで，一日 3 個までなら大丈夫であることを確認しています．}

図表 1.5 病院食メニューの推移 食品名 食品の量 (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.6 で与えられています． 図表 1.6 製品 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とする．

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 x1, x2, x3, x4, x5, y1, y2, y3≥ 0

農家の問題 [11]を参照しました． 農家が，夏にんじん，春大根，春キャベツ，春白菜5_{の作付を計画しています．栽培可能な面積} は 100a です．これらの野菜が旬をむかえる４，５，６月は，収穫のためたいへん忙しくなるため， 労働時間を考慮して計画を立てる必要があります．必要なデータは，表 1.7，1.8 に示した通りで す．予想収益を最大にするには，どの野菜をどれくらい栽培するのがよいでしょうか？ 図表 1.7 単位作付面積当たりの必要労働時間と予想収益 夏にんじん 春大根 春キャベツ 春白菜 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.8 月別の投入可能労働時間 投入可能な労働時間 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 果物の分配 ３人で，みかん 20 個とりんご 20 個と梨 5 個をわけることにしました．A さんは，みかん 1 つ を交換するのに，りんごなら 1.2 個，梨なら 1.5 個を要求しています．みかん 1 つに対して，B さ んはりんご 0.8 個，梨 1.1 個，C さんはりんご 1.4 個，梨 0.8 個の比率です．今，みかん一個から 得られる満足度が３人とも等しいとするなら，全員の満足度の合計を最大にするにはどのようなわ け方をすべきでしょうか．線形計画問題として定式化しなさい．ただし，どの果物も必要なら切っ てわけても構いません． また，分配された果物の数を等しくする (この場合は一人 15 個) という条件がついた場合はど うなるでしょうか？ [定式化] 5_{ここで，夏にんじんは前年 12 月下旬に播種して初夏に収穫，春大根は 1 月中旬播種／春収穫，春キャベツは前年 11} 月上旬播種／春収穫，春白菜は前年 12 月播種／春収穫，としています．

Aさんが得るみかん，りんご，梨の個数を x1，x2，x3 で表します．同様に B さんの得るみか ん，りんご，梨の個数を y1，y2，y3，C さんは z1，z2，z3 とします．満足度を表す変数も導入 しましょう．A さん，B さん，C さんの満足度をそれぞれ，uA, uB, uCとします．満足度をみかん の個数で換算して表す6_{とすると，交換比率から，} uA= x1+ 1 1.2x2+ 1 1.5x3 uB= y1+ 1 0.8y2+ 1 1.1y3 uC= z1+ 1 1.4z2+ 1 0.8z3 となるはずです．りんご，みかん，梨の個数が与えられているので，以下のように定式化すること ができます． 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.11) この問題は，わざわざ LP に定式化しなくても解けます．梨とりんごは，それをもっとも欲し がる人に全部あげれば満足度の合計は高くなります．みかんは，皆が同じ満足度なので，どのよう にわけても満足度の合計は変化しません．したがって，A さんに梨をすべて与え，C さんにりんご をすべて与えればよいのです (みかんは自由にわけてよい)． 分配後の個数に制約がある場合は，次の制約を (1.11) に付け加えてください． x1+ x2+ x3= 15 y1+ y2+ y3= 15 z1+ z2+ z3= 15 この場合，果物の配分は図表 1.9 のようになります． 図表 1.9 果物の分配 名前 満足度 みかん りんご 梨 Aさん 12.5 5.0 5.0 5.0 Bさん 15.0 15.0 0 0 Cさん 10.7 0 15.0 0 6_{みかんが numeraire というわけです．}

演習問題1.4 ビタミン剤 製薬会社K4コーポレーションがビタミン剤をつくっている．これには，ビタミンAが重量比 で8%，ビタミンBが重量比で4%，ビタミンCが重量比で2%以上含まれていなければならな い．一方，各ビタミン成分をつくるのに，4種類の原材料を用いることができる．原材料1gか ら精製される各ビタミン成分の量は，表1.10の通りである．例をあげると，1gの原材料1を精 製することで，ビタミンA，B，Cがそれぞれ0.03g，0.02g，0.01gを入手できる． 図表 1.10 原材料から精製されるビタミンのの量 原材料費 (円/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単位の量を価格pc1，p c 2で納入しなければならない．それ以上生産 した分は，市場価格はpm1，市場価格はp m 2 で販売することができる． 製品Pi (i = 1; 2)を１単位作るために必要な原材料A，B，C，Dの量は，それぞれaAi，aBi， aC i，aDi 単位である．原材料A，B，C，Dの１単位当たりの価格をそれぞれqA，qB，qC，qD とし，予算が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.11の情報に基づいて，売り上げを最大にする原料の購入 量，商品の製造量を求めよ． 図表 1.11 原料と価格の情報 オレンジ 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 時点だけを考慮して配分を決めていました．今度は，一定の期間にわたる配分 を決める問題を考えましょう．このタイプの問題は，状態が時間に応じて変化する場合に多く見ら れます．配分の基本は同じですが，時点間の関係をうまく表現する必要があります． クッキーの作成スケジュール 大学祭で販売するクッキーは手作りです．材料を買ってきて，クッキーを焼き，袋づめをする まで，すべて自分達でこなさなければなりません．昨年は，責任者がいい加減な計画しか作らな かったせいで，サークルのメンバー全員が直前になってたいへん忙しい思いをしました．今年の責 任者であるあなたは，まともな計画を立てるよう圧力をかけられています． 模擬店で販売するクッキーは，おおよそ以下の手順で作ります． 1. 材料を買ってきて，レシピに従いクッキーを焼く 2. 一日おいて冷ましてから，10 個づつ袋づめにする．

実際の作成にあたっては，いろいろな条件を考慮しなければなりません． • 全部で 200 パック作る • 大学祭直前の 5 日間を作成期間にあてる • オーブンを持っている部員にクッキーを焼いてもらい，袋づめは部室で行う． • 1時間で 100 個のクッキーを焼くことができる • 1時間で 150 パックをつくれる あなたが，サークルのメンバーの予定を聞いてみたところ，準備期間に投入可能な労働時間に ついて表 1.12 を得ました．また，多少無理をすれば，追加的に労働時間を増やすこともできそう です． 図表 1.12 投入可能な労働時間 準備期間 1日目 2日目 3日目 4日目 5日目 確実に投入可能な労働時間 5 4 4 3 2 追加可能な労働時間 12 12 12 5 5 ここで一つ重要なことがあることをあなたは思い出しました．毎年そうなのですが，袋づめの ために部室においてあるクッキーを，味見と称して部員がつまみ食いしてしまうのです．あまりき びしく注意すると作業に協力してもらえなくなるので，手間賃だと割りきることにしました．ど うやらつまみ食いは時間と量に比例するようです．一日あたり，詰めてないままのクッキーのおよ そ 10 ％とパックの 5 ％がなくなってしまいます．つまみ食いの総量を減らすには，なるべくクッ キーを長い間部室においておかないようにするほかありません． あなたの目標は，予定の製品数を達成し，かつなるべく追加的な労働時間を減らすことです．準 備期間中のクッキーを焼く枚数と袋づめする枚数はどうすればよいでしょうか． [記法] wt t日目に作るクッキーの枚数 (t = 1, . . . , 5) xt t日目に作るパック数 (t = 2, . . . , 5) yt t日目までに作った累計パック数 (t = 2, . . . , 5) zt t日目に詰め終えてないクッキーの枚数 (t = 1, . . . , 5) ut t日の総労働時間 (t = 1, . . . , 5) vt t日の追加的な労働時間 (t = 1, . . . , 5)

[定式化] min v1+ v2+ v3+ v4+ v5 s.t. ₁₀₀1 w1− u1≤ 0 1 100wt+ 1 150xt− ut≤ 0, t = 2, . . . , 5 u1− v1≤ 5, v1≤ 12 u2− v2≤ 4, v2≤ 12 u3− v3≤ 4, v3≤ 12 u4− v4≤ 3, v4≤ 5 u5− v5≤ 2, v5≤ 5 w1− z1= 0 wt+ 0.9zt−1− 10xt− zt= 0, t= 2, . . . , 5 10xt− 0.9zt−1≤ 0, t = 2, . . . , 5 w5= 0, z5= 0 x2− y2= 0 xt+ yt−1− yt= 0, t= 3, . . . , 5 y5≥ 200 wt≥ 0, t = 1, . . . , 4 xt≥ 0, t = 2, . . . , 5 yt≥ 0, t = 2, . . . , 5 zt≥ 0, t = 1, . . . , 5 ut≥ 0, t = 1, . . . , 5 vt≥ 0, t = 1, . . . , 5 (1.12) 図表 1.13 クッキーの作成スケジュール 準備期間 1日目 2日目 3日目 4日目 5日目 総労働時間 (ut) 5.00 4.00 7.55 8.00 1.61 追加労働時間 (vt) 0.00 0.00 3.55 5.00 0.00 焼いたクッキーの枚数 (wt) 500.00 370.00 732.90 800.00 0.00 詰めた袋の数 (xt) — 45.00 33.30 0.00 131.36 袋の数の累計 (yt) — 45.00 76.05 72.25 200.00 詰めていないクッキーの枚数 (zt) 500.00 370.00 732.90 1459.61 0.00 (1.12)を解いた結果は表 1.13 となりました．クッキーや袋の個数が小数になってしまってます が，実際には適当に数値を丸めてきりのよい数字にする必要があるでしょう． クッキーの作成スケジュールの問題は，在庫問題と見なせます．ここで，つまみ食いされてし まうクッキーの量は，一般的には保管費用と位置づけることができます． キャッシュフローマッチング問題 [問題] 現在から T 期までの各期間において Lt(t = 1, . . . , T )の資金需要が発生することがあらかじめ わかっています．この資金需要を債券に投資することで賄うことにしました．投資対象の債券は， すべて残存期間が T 期以下であるとし，第 t 期 (t = 1, . . . , T ) に債券 Bj(j = 1, . . . , n)から得られ る収入 (クーポン，もしくは元本) を cjtとします．債券 Bjの 1 単位あたりの価格が pj，t 期の利 率が itであるとき，必要な初期投資額が最小になるような債券の購入計画を作りなさい． [定式化]

債券 Bjの購入単位数を xjとし，t 期に生じる余剰金を vtとする． min ∑n_j=1pjxj s.t. ∑n_j=1cjtxj+ (1 + it)vt−1− vt= Lt, t= 1, . . . , T v0= 0 xj≥ 0, j = 1, . . . , n vt≥ 0, t = 1, . . . , T 図表 1.14 キャッシュフローの模式図

Σ

c x_{jt j} (1+i )v_{t t-1 v} t Lt 演習問題1.8 販促活動 あるビールのメーカーが，新しい製品の販売促進のためにキャンペーンを行おうとしている．キャ ンペーンを一定期間行うと，その期の売上が上昇する．売上の上昇率はキャンペーンに投入した 費用に比例しており，経験的に次の関係にあることがわかっている． [当期の売上の上昇率] = 0:8× [当期の費用] + 0:2× [前期の費用] - 0:05× [前前期の費用] キャンペーンの期間は連続する4期間を予定しており，総費用は15億円を予定している．ただ し，それぞれの期間に投入できる費用の上限はあらかじめ決められており，それは表1.15の通 りである．4期間の売上の上昇率の合計を最大にするには，各期にどれだけの費用をかければよ いか． 図表 1.15 予算の上限 期 第 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.13)

制約式に着目してください．x1+ 2x2が −3 以下でなければならいとあります．一方，非負条件か

ら x1+ 2x2は常に 0 以上です．したがって，問題 (1.13) の制約条件を満たす (x1, x2)は存在しませ

ん．このように，制約条件を満たす変数の組が存在しない場合，その問題は実行不可能 (infeasible) と呼びます．逆に，制約条件を満たす変数の組がただ一つでも存在すれば，その問題は実行可能

(feasible)です．制約条件を満たす変数の組は，実行可能解 (feasible solution) と呼ばれます．

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

1.4.2

LP

の図解

制約領域 次の線形計画問題を図示によって解くことにします．目的関数の係数は，具体的な数値を入れ ずに，(c1, c2)としてあります． max c1x1+ c2x2 s. t. x1+ x2 ≤ 6 2x1+ x2 ≤ 10 x2 ≤ 3 x1, x2 ≥ 0 (1.16) 問題 (1.16) の制約領域 (制約を満たす x1，x2の集合) を S とおきます．S は x1–x2平面上に， 1.16のように図示することができます． 図表 1.16 制約領域 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.17 制約領域 S と目的関数の等高線 (1) x 1 x 2 0 (C1,C2) 図表 1.18 制約領域 S と目的関数の等高線 (2) x 1 x 2 0 (C1,C2)

無限解を生成する場合の例 (問題 (1.17)) を図 1.19 に示しました． max c1x1+ c2x2 s. t. x1+ x2 ≥ 6 2x1+ x2 ≥ 10 x2 ≥ 3 x1, x2 ≥ 0 (1.17) 図表 1.19 無限解の例 x 1 x 2 0 (C1,C2) 演習問題1.9 パラメータ¸を用いて，線形計画問題が次のように定義されている． max x1- x2 s. t. 2x1- 3x2≤ -3 ¸x1- x2≤ 3¸ - 3 x1; x2≥ 0 この問題が最適解を持つための¸の条件を調べ，最適解を求めよ． [ヒント] x1-x2平面上で，¸x1- x2= 3¸ - 3で表される直線は，¸の値によらず，座標(3; 3) を必ず通る．

1.4.3

方程式系の変形

問題 (1.16) の目的関数の係数を (c1, c2) = (3, 2)とし，さらにスラック変数を導入して標準形 (1.18)へ変形します． max 3x1+ 2x2 s. t. x1+ x2+ x3 = 6 2x1+ x2+ x4 = 10 x2+ x5 = 3 x1, x2, x3, x4, x5 ≥ 0 (1.18) まず，非負制約を除いた 3 本の制約式だけに着目します． x1+ x2 +x3 = 6 2x1+ x2 +x4 = 10 x2 +x5 = 3 (1.19) (1.19)は変数が 5 つで，方程式が 3 本の連立方程式です．ふたつの変数 x2，x4を選んで，他の 変数を表してみましょう．(1.19) の 1 本目の式から，x1= −x2− x3+ 6を得るので，これを 2 本 目の式に代入します． x1 +x2 +x3 = 6 −x2 −2x3 +x4 = −2 x2 +x5 = 3 (1.20) (1.20)の 2 本目の式から，x3= −0.5x2+ 0.5x4+ 1として，1 本目の式に代入すると， x1 +0.5x2 +0.5x4 = 5 −x2 −2x3 +x4 = −2 x2 +x5 = 3 (1.21) が得られます．目的関数に目を向けましょう．問題 (1.18) の目的関数を z= 3x1+ 2x2 とおきます． (1.21) の 1 本目の式を用いて，x1を消去すると， z= 3∗ (5 − 0.5x2− 0.5x4) + 2x2= 15 + 0.5x2− 1.5x4 (1.22) となり，こちらも x2，x4のみで表すことができました．(1.21) と (1.22) まとめ，x2, x4を左辺に 移項すると， z= 15 +0.5x2 −1.5x4 x1= 5 −0.5x2 −0.5x4 x3= 1 −0.5x2 +0.5x4 x5= 3 −x2 (1.23) となります．この変形が何を意味しているか，具体的に検討してみましょう．

等価な方程式系 もとの問題 (1.18) から，非負条件を除き，目的関数を z とおいて，方程式系として示すと， z= 3x1+ 2x2 x1+ x2+ x3= 6 2x1+ x2+ x4= 10 (1.24) x2+ x5= 3 となります．(1.23) は，(1.24) から代入操作だけで得らるので，両者は等価な方程式系ということ ができます．等価というのは，一方の方程式系をみたす解は，かならず他方の方程式系を満たすと いうことです． 演習問題1.10 (1.24)を満たす(x1; x2; : : : ; x5)の値を計算で求め，それが(1.23)を満たしていることを確認せ よ．逆に，(1.23)を満たす(x1; x2; : : : ; x5)の値を計算で求め，それが(1.24)を満たしているこ とを確認せよ．

1.4.4

基底形式表現

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

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

基底形式表現の特徴は，非基底変数を 0 とおくことで，ただちに基底変数の値と目的関数値が得 られることです．(1.23) で，x2= x4= 0とおくと，x1= 5, x3= 1, x5= 3, z = 15が得られます． 同じ結果を，(1.24) で得ようとすると，やや面倒な計算が必要です．(1.24) において，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.23)から得られる基底解は，x1= 5, x2= 0, x3= 1, x4= 0, x5= 3です (これは実行可能

基底解です)．スラック変数の導入前の変数は，x1と x2だけでした．(x1, x2) = (5, 0)という座標

は，図表 1.16 における点 D に相当します．

もう一つ，例を出します．x3，x4を非基底変数とする基底形式表現を求めると， z= 16 −x3 −x4 x1= 4 +x3 −x4 x2= 2 −2x3 +x4 x5= 1 +2x3 −x4 (1.25) が得られます．この場合の基底解は， x1= 4, x2= 2, x3= 0, x4= 0, x5= 1 なので，もとの x1-x2平面上では，(x1, x2) = (4, 2)の座標を表し，点 C に相当します． このことからわかるように，実行可能基底解は制約領域の端点を表しているのです．そして，線 形計画問題の最適解が端点で達成されることを考えれば，実行可能基底解が重要な意味を持つこと が理解できるはずです． 演習問題1.11 x1; : : : ; x5の中から適当な変数の２つ選び，それを非基底変数とした基底形式表現を求めよ．そ こから基底解を求め，それが図表1.16において，どの点に相当するか確認せよ． [注意]変数の選び方によっては必ずしも実行可能基底解とはならない．実行可能でない場合，対 応する点は領域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.23) 点 C に対応        z= 16 −x3 −x4 x1= 4 +x3 −x4 x2= 2 −2x3 +x4 x5= 1 +2x3 −x4 (1.25) (1.23)における (実行可能) 基底解は，非基底変数 x2, x4を 0 とおくことで得られます．(1.23) の目的関数の式を見ると， 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.26)

tを大きくすれば，目的関数値 z = 15 + 0.5t も増加します．しかし無限に t を増加させることはで きません．なぜならば，t を増加させると，基底変数である x1, x3, x5の値が減少していき，つい には負の値になってしまうからです．そうなっては，実行可能でなくなってしまいます．実行可能 性を保ちつつ t を大きくすると，t = 2 が最大となります．このとき，x3= 0です． ここで，以下の点を確認してください． • (1.23)において，3 本目の式 x3= 1 − 0.5x2+ 0.5x4を，他の式に代入して整理すると，(1.25) が得られる． • (1.23)の非基底変数 x2が (1.25) では基底変数に入り，(1.23) の基底変数 x3が (1.25) では非 基底変数に出ていっている． • (1.25)における基底解での目的関数値は 16 であり，これは，15 + 0.5∗ 2 と等しい． 上記のように，非基底変数と基底変数を交代することで，目的関数値を改善することを，基底 の更新といいます．この操作は，幾何学的には，隣りの端点へ動くことに対応しています． 演習問題1.12 (1.23)で，x4の値を増加させて(この場合，目的関数の値は減少する)，最初に0になった基底 変数と入れ替えをおこなうと，どのような基底形式表現が得られるか? また，それは図表1.16 のどの点に対応するか? 最適解 (1.23)の基底を更新することで，(1.25) が得られました．(1.25) の解をさらに改善することは できるでしょうか．目的関数の式を見ると， z= 16 − x3− x4 となっているので，非基底変数である x3と x4の値を 0 から増加させても，目的関数の値は増加 しません．実際，(1.25) は，最適解を与えています． (1.25)によって最適解が得られていることは，次のようにして確かめることができます．基 底形式表現はすべて等価な方程式系であることを思い出してください．したがって，実行可能解 (^x1, . . . ,^x5)に対しては，いかなる基底形式表現もその目的関数は同じ値をとります．もとの問題 (1.18)の目的関数と (1.25) の目的関数の値を実行可能解で評価すると， z= 3^x1+ 2^x2= 16 − ^x3− ^x4 と成り立ちます9_{．実行可能解であるならば，^x} 3≥ 0, ^x4≥ 0 なので， z= 3^x1+ 2^x2≤ 16 という不等式が成り立ちます．したがって，任意の実行可能解で評価した目的関数値はかならず 16 を下回ることから，16 が最適値であることが言えます． 9_{実行可能解である (5; 0; 1; 0; 3)，(0; 0; 6; 10; 3)，(3; 3; 0; 1; 0) などを代入して確認してください．}

単体法 線形計画法の解法の一つである単体法 (simplex method) は，初期実行基底解から出発して，次々 に基底を更新することで最適解を求める手法です．その概略は上で示したとおりですが，他にも考 慮しなければならないことがたくさんあります． • 問題が実行不可能であることをどのように判定するか． • 実行不可能でなかったとして，初期実行可能基底解をどのようにみつけるか． • 問題が有界でなかった場合，どのようにしてそれを判断するか． • 必ず基底は更新できるのか． • 単体法は，有限回の手続きで終了するのか． これらは講義では取り扱いません．詳しくは専門書を参照してください．

1.4.6

感度分析１

最適解を表現する基底形式表現がわかると，それを用いて感度分析を行うことができます．例 として，家具工場の製造計画問題を考えてみることにしましょう． この家具工場では，原材料として木材・金属・ガラスを用い，製品としてテーブル・シェルフ を製造しています．それぞれ製品 1 単位の生産に必要な資源の量，製品価格，投入可能な資源の量 は図表 1.20 の通りです 図表 1.20 家具製造における資源量，価格，保有量 テーブル シェルフ 保有量 木材 1 1 6 金属 2 1 10 ガラス 0 1 3 製品価格 3 2 製品がすべて売れるとの仮定のもとで，売上を最大にする製造量を求める問題は，次のように 定式化されます． max 3x1+ 2x2 s. t. x1+ x2 ≤ 6 2x1+ x2 ≤ 10 x2 ≤ 3 x1, x2 ≥ 0 (1.27) これは，(1.16) と同じ問題であることに注意してください．最適解を与える基底形式表現は，すで にわかっている通り， z= 16 −x3 −x4 x1= 4 +x3 −x4 x2= 2 −2x3 +x4 x5= 1 +2x3 −x4 (1.25) です．

価格の変化 今，製品価格は，テーブルが３，シェルフが２です．ここで，シェルフの価格を変化させたと き，最適解や最適値がどのように変化するか，検討してみましょう．もっとも単純な方法は，新し い価格体系のもとで，再度線形計画問題を解くことです．しかし，すでに最適解をあたえる基底形 式表現がわかっている場合，問題を解くことなく最適解の変化を知ることができます． まず，シェルフの価格が 2 から 2.5 に変化した場合を考えてみましょう．(1.25) では，目的関数 は，z = 16 − x3− x4と表されています．これは，もともとの目的関数 z = 3x1+ 2x2を， z= 3x1+ 2x2 = 3(4 + x3− x4) + 2(2 − 2x3+ x4) としたものです．シェルフの価格が 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.28) となります．目的関数の x4の係数が正となったので，x4を 0 から増やし，新しい基底変数を x1, x2, x4 とすると， z= 21 −3x3 −x5 x1= 3 −x3 +x5 x2= 3 −x5 x4= 1 +2x3 −x5f (1.29) となります．これは，最適解です． この例では，シェルフの価格が 3 以下であれば，最適な家具の生産量は変化しません．シェル フの価格が 3 を越えたところで，最適な家具の生産量が変化します．

1.5

双対理論

1.5.1

工場の買収

投資家が前節の家具工場のもつ資源の買い取りを提案してきたとします．この投資家は家具工 場のオーナーに対して，工場の保有する資源ごとに買い取り価格を提示しています．投資家が提案

する資源の買い取り価格を y1，y2，y3としましょう．そうすると，総買収額は 6y1+ 10y2+ 3y3 で表されます．さて，ここでオーナーの立場になってみましょう．オーナーは今工場を保有してい るので，安い値段で資源を売ってしまうくらいなら，家具をつくって売った方が有利です．つまり， 製品価格で売るよりも資源を個別に売った方が有利である場合にのみ，オーナーは交渉の席につく のです．シェルフ 1 単位を作るには，1 単位の労働時間，1 単位の金属，1 単位のガラスを用いま した．シェルフ 1 単位分の資源をそのまま投資家に提示された価格で売ると，y1+ y2+ y3をえ ます．製品に仕立てて売れば，2 単位のお金に相当するのですから，オーナーは， y1+ y2+ y3≥ 2 でなければ承知しないでしょう．テーブルについても y1+ 2y2≥ 3 でなければならないはずです．投資家の側からみれば、買収金額を小さくしたいので、両者が折り 合うためには、次の問題を解く必要があるでしょう． min 6y1+ 10y2+ 3y3 s. t. y1+ 2y2 ≥ 3 y1+ y2+ y3 ≥ 2 y1, y2, y3 ≥ 0 (1.30) この問題の最適解は y∗1= 1、y∗2= 1、y∗3= 0で、目的関数値 (買収金額) は 16 です．この値は最適 生産計画の売上げ額と等しいことに着目してください．問題 (1.30) の最適解は、潜在価格 (shadow price)と呼ばれるものです．資源をもっとも有効に利用しているときの、資源の内在的な価格です． この潜在価格は (1.30) を解くことによって得ることができます．問題 (1.27) と問題 (1.30) の関 係は次節で論ずることにしましょう．また潜在価格の解釈については，1.5.3 節で述べます．

1.5.2

双対問題

以下のような線形計画問題 (1.31) が与えられたとします． maximize c1x1+ c2x2+· · · + cnxn subject to a11x1+ a12x2+· · · + a1nxn ≤ b1 a21x1+ a22x2+· · · + a2nxn ≤ b2 .. . am1x1+ am2x2+· · · + amnxn≤ bm xj≥ 0, j = 1, . . . , n (1.31) このとき，問題 (1.32) を，問題 (1.31) の双対問題 (dual problem) といいます． minimize b1y1+ b2y2+· · · + bmym subject to a11y1+ a21y2+ . . . + am1ym ≥ c1 a12y1+ a22y2+ . . . + am2ym ≥ c2 .. . a1ny1+ a2ny2+ . . . + amnym ≥ cn yi≥ 0, i = 1, . . . , m (1.32)