第
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 −c1x−1 +c2x2+· · ·+cnxn
subject to a11x+1 −a11x−1 +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.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，ビ タミンB1 1.1(0.8)mg，ビタミンC 100(100)mgだそうです．
図表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 配合を決める問題
食餌問題それ自体も重要な応用問題ですが，ほかにもおなじ形式をもつ重要な問題があります．
31升瓶千本以上です．
4Dantzigは，ブイヨンの個数を変えてつくったスープを飲んで，一日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というわけです．
