3-1線形代数と行列
土曜の朝8時、こむぎ堂の扉の外まで行列が伸びていました。焼き上がったばかりのクロワッサンを目当てに来たお客さんが、歩道に12人並んでいます。レジは1台だけで、店長が袋に詰め、会計をし、また袋詰めに戻ります。列の後ろのほうで、2人のお客さんが時計を見て帰っていきました。閉店後、店長はレジの横の空いた場所を手で測りながら言います。「もう1台レジを置くべきかな。でも、平日はがらがらなんだよね」。勘で決めるには、レジは高い買い物です。ミナトは相棒に打ち込みました。「行列の長さって、計算で出せるのかな」
相棒の返事は、計算の式ではありませんでした。「出せるよ。でも、その前に数字を集めて並べよう。お客さんが来た時刻、会計にかかった時間、売れたパンの数」。ミナトは次の土曜にストップウォッチを持ってレジの横に立つことにして、まず手元にある先週末の売れ数をノートに書き出しました。土曜は食パン20本、バゲット10本、メロンパン30個。日曜は食パン15本、バゲット12本、メロンパン25個です。
土曜の売れ数のように、いくつかの数を決まった順に並べた組をベクトルといいます。（食パン, バゲット, メロンパン）の順と決めておけば、土曜は (20, 10, 30)、日曜は (15, 12, 25) と書けます。数学では、ベクトルを大きさと向きをもつ量として矢印で描くこともあります。2つの数の組 (3, 4) なら、右へ3、上へ4進む矢印で、その長さは5です。成分が3つ、4つと増えると矢印は描けなくなりますが、数の組として計算するやり方はそのまま使えます。
ここから基本情報！大きさだけをもつ量
ベクトルと対になるのが、値段の340円や気温の22℃のように、1つの数で表され、大きさだけをもち向きをもたない量です。これをスカラ（スカラー）といいます。ベクトルにスカラを掛けると、すべての成分が同じ倍率で変わります。土曜の売れ数 (20, 10, 30) を2倍すると (40, 20, 60) です。「連休の土曜は2倍売れるとしたら」という見積もりは、スカラ倍の計算にあたります。
基本情報の範囲ここまで
土曜と日曜のベクトルを上下に重ねると、数が縦と横の長方形に並びます。このように数を長方形に並べたものを行列といいます。横の並びを行、縦の並びを列と呼ぶので、売れ数の表は2行3列の行列です。
| 食パン（340円） | バゲット（300円） | メロンパン（180円） | |
|---|---|---|---|
| 1行目：土曜 | 20 | 10 | 30 |
| 2行目：日曜 | 15 | 12 | 25 |
行列にすると、2日分の売上を1回の計算で出せます。値段の (340, 300, 180) を縦に並べたベクトルにして、売れ数の行列に掛けます。行列とベクトルの掛け算は、行ごとに、同じ位置にある数どうしを掛けて足す決まりです。1行目は 20×340＋10×300＋30×180 で15,200円、2行目は 15×340＋12×300＋25×180 で13,200円になります。土曜のほうが2,000円多く売れていました。
ベクトルや行列、そして後で出てくる連立一次方程式のように、数の組を「掛けて足す」計算を扱う数学の分野を線形代数といいます。表計算ソフトで何百行もの売上を集めるのも、写真を回転させたり拡大したりするのも、AIが学習のあいだに膨大な掛け算と足し算を繰り返すのも、中身は行列の計算です。行列で書いておけば、パンの種類が30に増えても、計算の手順は変わりません。
ここから基本情報！行列の性質と連立方程式
数の掛け算には、掛けても相手を変えない1があります。行列でそれにあたるのが、左上から右下への対角線に1が並び、ほかがすべて0の正方行列（行と列の数が等しい行列）で、単位行列といい、E と書きます。2行2列の単位行列は、1行目が (1, 0)、2行目が (0, 1) です。どの行列に掛けても、相手は元のままです。
数の 2 に 1/2 を掛けると 1 になるように、正方行列 A に掛けると単位行列になる行列を、A の逆行列といい、A−1 と書きます。AA−1＝A−1A＝E が成り立ちます。0 に逆数がないのと同じで、逆行列をもたない正方行列もあります。
逆行列を使うと、連立一次方程式が解けます。レシートの合計だけが残っていて、「食パン2本とバゲット1本で980円」「食パン1本とバゲット1本で640円」だったとします。値段を x、y とすると 2x＋y＝980、x＋y＝640 です。係数を並べた行列 A は1行目が (2, 1)、2行目が (1, 1) で、その逆行列は1行目が (1, −1)、2行目が (−1, 2) になります（A に掛けて単位行列になることを確かめられます）。逆行列を右辺の (980, 640) に掛けると、x＝980−640＝340、y＝−980＋2×640＝300。食パンは340円、バゲットは300円と分かります。
行列 A の i 行 j 列にある要素を、j 行 i 列に移した行列を転置行列といい、AT と書きます。売れ数の2行3列の行列を転置すると、パンの種類が行、曜日が列の3行2列になります。表の縦と横を入れ替える操作です。
行列をベクトルに掛けると、ふつうは向きも長さも変わります。ところが、行列によっては、特定の向きのベクトルだけは向きを変えず、長さだけが何倍かになります。Ax＝λx を満たす0でないベクトル x を固有ベクトル、その倍率のスカラ λ を固有値といいます。1行目が (2, 1)、2行目が (1, 2) の行列に (1, 1) を掛けると (3, 3) で、これは (1, 1) の3倍なので、固有値3、固有ベクトル (1, 1) です。(1, −1) を掛けると (1, −1) のままなので、こちらは固有値1です。固有値は、データの散らばりがいちばん大きい向きを探す主成分分析などに使われます。
基本情報の範囲ここまで
3-2数列と関数
月曜の朝、店長は継ぎ足している天然酵母の元種の瓶を見せてくれました。暖かい日は、数時間で倍の高さまでふくらむそうです。ミナトのほうは、春に始めた通販の注文数を週ごとに並べていました。20件、25件、30件、35件。「どっちも増えているけど、来月にはまるで違う数になりそうだね」と店長が言いました。
増え方には型があります。毎週同じ数だけ増えるのか、毎回同じ倍率で増えるのか。型が分かれば、まだ来ていない週の数を、並びの規則から計算で出せます。逆に、どの型かを取り違えると、見積もりは週を追うごとに大きく外れていきます。
ここから基本情報！数列の3つの型
通販の注文のように、各項に一定の数（公差）を足すと次の項になる数列を等差数列といいます。20, 25, 30, 35 は公差5の等差数列で、n 週目の注文数は 20＋5×(n−1) と書けます。10週目は 20＋5×9 で65件です。
元種のように、各項に一定の数（公比）を掛けると次の項になる数列は等比数列です。100g の元種が 200g、400g、800g とふくらめば、公比2の等比数列です。10回倍になると、100g は 210 倍の 102,400g（約102kg）になります。等差数列は直線のように増え、等比数列はあるところから急に増えます。
1, 1, 2, 3, 5, 8, 13 のように、直前の2つの項を足すと次の項になる数列をフィボナッチ数列といいます。等差でも等比でもありませんが、隣どうしの比は 1.618… という一定の値に近づいていきます。プログラムの練習問題で、同じ計算を何度も繰り返さない工夫を学ぶ題材としてもよく使われます。
基本情報の範囲ここまで
店では、作業台を正方形のものに入れ替えることになりました。天板の面積は2平方メートルにしたい。では、一辺は何メートルにすればよいでしょうか。2乗すると2になる数を求めればよく、これを2の平方根といい、√2 と書きます。√2 は 1.41421356… と小数が規則なく続くので、一辺はおよそ1.41メートルです。2乗して2になる数は −√2 もありますが、長さは負にならないので正の方を使います。表計算ソフトではSQRT関数で求められ、データの散らばりを表す標準偏差を出すときにも平方根を使います。
ここから基本情報！対数と三角関数
等比数列を逆向きにたどると、新しい問いが出ます。元種は何回倍になれば1,000倍を超えるのか。ax＝N のとき、x を「a を底とする N の対数」といい、logaN と書きます。210＝1,024 なので log21,024＝10 で、10回倍になれば1,000倍を超えます。対数を使うと、とても大きな数も小さな数で扱えます。並べ替え済みのデータを半分ずつに絞って探すやり方では、データが2倍に増えても調べる回数は1回増えるだけで、回数はデータ件数の対数にほぼ比例します。
店の入口の段差に、高さ10cm、斜面の長さ120cmのスロープを付けることになったとします。斜面の傾きの角度を θ とすると、高さ÷斜面の長さ を sin θ、底辺÷斜面の長さ を cos θ、高さ÷底辺 を tan θ と呼びます。このように角度と辺の比の関係を表す sin、cos、tan などの関数をまとめて三角関数といいます。このスロープでは sin θ＝10÷120 で約0.083です。三角関数は、音や電波のような波の形を表すのにも使われます。
基本情報の範囲ここまで
3-3数値解析と誤差
2回目の土曜、ミナトはレジの横でお客さん一人ひとりの会計の時間を測りました。ところが、ストップウォッチを押すのがどうしても一拍遅れます。同じ朝、店長は生地を量りながら「このはかり、1kgの重りを載せると1,002gと出るんだよ」とこぼしました。
測った値や計算で得た値と、本当の値（真の値）とのずれを誤差といいます。ストップウォッチの押し遅れも、はかりの2gのずれも誤差です。ずれのない測定はありません。だから、測った数字を使うときは、どれくらいずれていそうかを見積もり、比べる条件をそろえておきます。押し遅れが毎回ほぼ同じなら、平日と土曜の会計時間を同じストップウォッチ、同じ人で測ることで、比べたときのずれは打ち消し合います。毎回ばらばらにずれる誤差なら、何人分も測って平均をとると小さくなります。
ここから基本情報！誤差の大きさと生まれ方
誤差の大きさを表す方法は2つあります。真の値と測った値の差の絶対値が絶対誤差です。1,000g の生地が 1,002g と出れば、絶対誤差は2gです。絶対誤差を真の値で割ったものが相対誤差で、ずれが真の値の何割にあたるかを示します。生地なら 2÷1,000 で0.2%です。同じはかりで10g の塩を量って12g と出たら、絶対誤差は同じ2g でも、相対誤差は20%になります。生地では気にならないずれが、塩では味を変えます。
コンピュータの計算そのものからも誤差は生まれます。コンピュータは数を決まった桁数でしか持てないので、1÷3＝0.333… のように終わらない数は、どこかの桁で丸めて持つことになります。このとき生じる誤差が丸め誤差です。10進数の0.1が2進数では割り切れず、0.1を10回足しても1ちょうどにならないのも、丸め誤差のためです。
これとは別に、本来は無限に続く計算を、有限の回数で打ち切ることで生じる誤差を打切り誤差といいます。円周率を求める式のように、項を無限に足していけば正しい値になる計算でも、コンピュータは途中でやめなければなりません。やめたところから先の項の分が、打切り誤差になります。
基本情報の範囲ここまで
ここから基本情報！近い値を繰り返し求める方法
方程式によっては、式を変形して答えを直接求められないものがあります。そこで、答えに近い値から出発し、計算を繰り返して少しずつ真の値に近づける方法がとられます。代表的なのがニュートン法です。曲線上の今の点で接線を引き、その接線が x 軸と交わる点を次の近い値にします。
作業台の一辺だった √2 を、ニュートン法で求めてみます。√2 は x2−2＝0 の解なので、次の値を (今の値＋2÷今の値)÷2 で求める式になります。1 から出発すると、1回目は (1＋2)÷2＝1.5、2回目は (1.5＋1.333…)÷2＝1.41666…、3回目は 1.414215… です。真の値は 1.414213… なので、3回で小数第5位まで一致しました。何回で計算をやめるかを決めるのは人の側で、やめた時点で残るずれは打切り誤差です。
答えをはさむ範囲を決め、その範囲を半分ずつ狭めていく二分法もあります。ニュートン法より遅いかわりに、範囲の中に答えがあれば確実に近づきます。また、測った点と点の間の値を推定する方法を補間法といいます。9時に20℃、11時に24℃だった厨房の温度から、10時はその間をまっすぐ結んで22℃と見積もるのは、補間法の一つです。
基本情報の範囲ここまで
3-4数式処理
火曜の朝、店長はオーブンの予熱を始めてから、窓の温度表示をじっと見ていました。最初の数分はぐんぐん上がるのに、200℃に近づくと上がり方がゆっくりになります。「いま、1分あたり何度ずつ上がっているんだろう。それに、これまでに使った電気はどれくらいなんだろう」
店長の2つの疑問は、向きが逆の計算です。一つめは「いまの変わる速さ」を、二つめは「これまでの分を足し合わせた量」を知りたがっています。
関数がある瞬間にどれだけの速さで変わっているか（変化率）を求めるのが微分、細かく区切った分を足し合わせ、グラフと横軸ではさまれた面積のような量を求めるのが積分です。2つを合わせて微分と積分と呼びます。車にたとえると、速度計の針が示す「いまの速さ」は距離を微分したもので、走った距離は速さを積分したものです。こむぎ堂なら、1時間あたりに売れるパンの数の移り変わりを積分すると、1日に売れた数になります。
コンピュータは、こうした計算を数値だけでなく、文字を含む式のまま扱うこともできます。√2 を 1.41421… と小数で出すのが数値計算なら、√2 を記号のまま残し、式を変形したり微分したりするのが数式処理です。数式処理のソフトウェアは、手で解くと間違えやすい長い式の変形を、記号のまま正確に進めます。
ここから基本情報！式の変形と微分・積分の計算
多項式を、いくつかの式（因数）の積の形に書き直すことを因数分解といいます。x2＋5x＋6 は (x＋2)(x＋3) と因数分解できます。積の形から元に戻す展開の、逆の操作です。積の形にしておくと、式が0になるのは x＝−2 か x＝−3 のときだと、すぐ読み取れます。
微分は、関数の瞬間の変化率を求める計算で、グラフでいえばその点で引いた接線の傾きにあたります。y＝x2 を微分すると 2x になり、x＝3 の点では接線の傾きが6です。予熱のグラフの傾きが、店長の知りたかった「いま1分あたり何度上がっているか」です。
積分は、関数をある区間にわたって細かく足し合わせる計算で、微分の逆の演算にあたります。y＝2x を x＝0 から x＝3 まで積分すると、グラフの下の三角形の面積で 3×6÷2＝9 になります。これは、2x を微分する前の x2 に3を入れた値と一致します。
基本情報の範囲ここまで
3-5データの集計と表計算
2回目の土曜の記録を、ミナトは表計算ソフトに打ち込みました。8時から9時までのお客さん60人分の、来た時刻、会計にかかった秒数、買ったパン。店長が後ろからのぞき込みます。「で、何が分かったの」。60行の数字は、並べただけでは何も答えてくれませんでした。
まずは、たくさんのデータから合計や平均を求めてまとめるデータの集計です。会計の秒数を全員分足すと3,240秒、60人で割ると平均は54秒でした。1時間に来た60人を、平均54秒ずつで会計していたことになります。
表計算ソフトのセルに入れる式には種類があります。=B2*C2 のように、計算した結果が数値になる式を算術式といいます。結果が文字列になる式は文字式です。商品名のセルと「（予約）」の文字をつなげて「食パン（予約）」と表示させる、といった使い方をします。ほかに、結果が真か偽になる論理式もあります。=C2>=300 のように値を比べる式は、文字列どうしを比べるときも論理式です。
| 行 | A：時刻 | B：パン | C：金額 | D：税込（式） |
|---|---|---|---|---|
| 2 | 8:01 | 食パン | 340 | =C2*(1+$F$1) |
| 3 | 8:02 | クロワッサン | 220 | =C3*(1+$F$1) |
| 4 | 8:02 | バゲット | 300 | =C4*(1+$F$1) |
表の D 列の式を見てください。D2 に入れた式を下の行へ複写すると、C2 の部分は C3、C4 と、複写した先の行に合わせて変わります。複写元と複写先の位置関係に応じて参照するセルが自動的にずれる方式を相対参照といいます。一方、税率を入れたセル F1 は、どの行でも同じセルを見なければなりません。$F$1 のように行と列の前に $ を付けて、複写してもずれないようにする方式が絶対参照です。D2 に =C2*(1+F1) と書いて複写すると、下の行では F2、F3 と空のセルを見てしまい、税込の金額が正しく出ません。
次に、売れた順を知りたくなります。データを大小などの基準に従って順番に並べ直す操作がデータの並べ替え（ソート）で、金額の多い順や時刻の早い順に並べ替えられます。並べた結果に1位、2位と順位を付けたものがランキングです。パンの種類ごとに売れ数を集計して多い順に並べると、土曜の朝はクロワッサンが1位でした。
「会計に60秒以上かかった人は何人か」のように、条件を満たすセルの件数だけを数える関数を、試験の表計算では条件付個数と呼びます。Excel などでは COUNTIF 関数にあたります。数えると18人で、その多くは、パンを選びながら会計をしていた人でした。
値段の表を別に作っておき、商品の名前から値段を探して取り出すこともできます。値段の表が縦に並んでいるときに、左端の列を上から下へ探し、見つかった行から値を取り出すのが垂直照合で、Excel などの VLOOKUP 関数にあたります。表が横に並んでいて、上端の行を左から右へ探すときは水平照合で、HLOOKUP 関数にあたります。どちらも、探す向きが縦か横かの違いです。
最後に、規則性をもたない、でたらめな数を乱数といい、RAND 関数などで作れます。ミナトは乱数でお客さんの来る時刻を何通りも作り、レジが1台のときと2台のときで行列がどうなるかを表の上で試してみることにしました。実際の店を使わずに、起こりうる朝を何度でも試せます。
3-6グラフ理論
日曜の昼、ミナトは近所の4か所に予約のパンを届けることになりました。花屋、喫茶店、保育園、図書館。店長がくれた手描きの地図には、道が何本も書き込まれていて、どの順に回ればいいのかすぐには分かりません。ミナトは地図を見ながら、店と4か所を丸で、道を線で書き直しました。
ミナトが描いた丸と線の図は、数学でいうグラフです。棒グラフや折れ線グラフとは別のもので、点と、点どうしを結ぶ線だけで、ものとものの「つながり」を表します。こうしたグラフの性質や、グラフの上での問題の解き方を調べる数学の分野をグラフ理論といいます。
グラフの点を頂点（ノード）、2つの頂点を結ぶ線を辺（エッジ）といいます。配達の地図では、店と4か所が頂点、道が辺です。辺に距離や時間、費用などの数（重み）を付けると、どの道を通ると近いかを計算できるようになります。地図の形そのものは描き直しても、どの頂点がどの頂点とつながっているかが同じなら、グラフとしては同じものです。
地図の道は、どちら向きにも通れます。このように辺に向きの区別がないグラフを無向グラフといいます。SNS で、互いに承認しあってつながる「友達」の関係も無向グラフです。
これに対して、辺に向きがあり、矢印の向きにしか進めないグラフが有向グラフです。パンを作る作業の順序は、こねる→一次発酵→成形→二次発酵→焼く、と矢印でつながり、焼いてからこねることはできません。片方だけが相手をフォローできる SNS のフォローの関係も、有向グラフで表せます。作業の順序を有向グラフにしておくと、どの作業が終わるまで次に進めないかが図から読み取れます。
3-7待ち行列
表計算ソフトでまとめた2回目の土曜の数字は、ミナトにとって意外なものでした。8時からの1時間に来たのは60人で、平均すると1分に1人。会計は平均54秒です。「1分に1人来て、54秒で終わるなら、レジは間に合っているはずだよね」と店長。それなのに、その朝も行列は歩道まで伸びていました。
お客さんが窓口に来て、空いていなければ並んで待ち、サービスを受けて帰っていく。この流れを数で表し、列の長さや待つ時間を、お客さんの来る頻度と1人にかかる時間から確率を使って見積もる考え方を待ち行列（待ち行列理論）といいます。お店のレジだけでなく、コンピュータのサーバに届く処理の要求や、プリンタに送られた印刷の順番も、同じ考え方で見積もれます。
店長の「間に合っているはず」は、平均だけを見た答えです。お客さんは1分おきにきちんとは来ません。3人続けて来る時間もあれば、5分だれも来ない時間もあります。だれも来ない間、レジは空いていますが、その空いた時間を後でまとめて来た人のために取っておくことはできません。来る時刻と会計の長さのばらつきが、平均では間に合うはずの窓口に行列を作ります。
待ち行列の型は、基本の形では3つの記号を斜線で並べて表します。1つめは客の来方、2つめは1人にかかる時間の分布、3つめは窓口の数です。M/M/1（M/M/1モデル）は、客がばらばらに（ポアソン分布に従って）来て、1人にかかる時間も指数分布に従ってばらつき、窓口が1つの型です。M は、過去に左右されないでたらめさ（マルコフ性）を表す記号です。この書き方をケンドール記法といいます。レジ1台で、お客さんが思い思いの時刻に来るこむぎ堂の土曜の朝は、M/M/1 に近い形です。
ここから基本情報！M/M/1 の待ち時間を計算する
M/M/1 の計算に使う量を順に並べます。ある客が来てから次の客が来るまでの時間が到着間隔で、土曜の朝の平均は1分でした。単位時間あたりに来る客の数の平均が平均到着率で、記号 λ（ラムダ）で表します。平均到着間隔の逆数なので、λ＝1人/分です。
窓口が1人の客の処理にかかる時間をサービス時間といい、平均を Ts と書きます。こむぎ堂では Ts＝0.9分（54秒）です。1つの窓口が単位時間あたりに処理できる客の数の平均は平均サービス率で、記号 μ（ミュー）で表し、平均サービス時間の逆数になります。μ＝1÷0.9 で、約1.11人/分です。
λ を μ で割った ρ（ロー）を利用率といい、窓口がふさがっている時間の割合を表します。土曜の朝は ρ＝1÷1.11＝0.9 で、レジは9割の時間ふさがっていました。
客が並んでから会計が始まるまでの待ち時間の平均 Wq は、M/M/1 では Wq＝ρ÷(1−ρ)×Ts で求められます。土曜の朝は 0.9÷0.1×0.9 で8.1分です。会計を終えて帰るまでなら、これに Ts を足して9分になります。
| 利用率 ρ | ρ÷(1−ρ) | 平均待ち時間 Wq |
|---|---|---|
| 0.5 | 1 | 0.9分 |
| 0.8 | 4 | 3.6分 |
| 0.9 | 9 | 8.1分 |
| 0.95 | 19 | 17.1分 |
表のとおり、ρ が1に近づくと待ち時間は急に伸びます。0.8から0.9へ1割増えただけで、待ち時間は倍以上になりました。レジを2台にして、客がどちらかのレジに半分ずつ並ぶとすると、1台あたりの到着間隔は2分、ρ＝0.45 になり、Wq＝0.45÷0.55×0.9 で約0.74分、およそ44秒です。
基本情報の範囲ここまで
待ち行列の考え方から分かるのは、窓口がふさがっている割合が1に近づくほど、待つ時間が急に長くなることです。ふだんは空いている窓口でも、混む時間帯に客が少し増えるだけで、行列は一気に伸びます。平日のこむぎ堂がすいていて、土曜の朝だけ行列が歩道に出るのは、この性質のためでした。Webサイトのサーバが、アクセスの集中する時刻にだけ急に遅くなるのも、同じ理由です。
3-8最適化問題
レジの台数の答えが見えてきたところで、店長は次の悩みを口にしました。「土曜は何をどれだけ焼けばいいんだろう。小麦粉にも、オーブンの段数にも限りがあるし」。ミナトの手元には、日曜の配達の地図も残っています。どの順に回れば、いちばん早く帰ってこられるのか。
守らなければならない条件（制約条件）のもとで、目的にする量（目的関数）を最も大きく、または最も小さくする答えを探す問題を、まとめて最適化問題といいます。粉とオーブンの限りの中で利益を最も大きくする、配達の道のりを最も短くする、待ち時間とレジの費用のつり合いがいちばんよい台数を決める。どれも、目的と条件の組み合わせで書ける最適化問題です。答えの候補を全部試せない大きな問題ほど、効率よく最適な答えにたどり着く解き方が要ります。
ここから基本情報！一次式で書ける最適化
制約条件も目的関数も一次式で書ける最適化問題を解く方法を線形計画法といいます。食パン1本の利益が200円、バゲット1本が150円だとします。食パンは小麦粉を400g、バゲットは200g使い、使える粉は8kgです。オーブンはどちらも1本につき1枠を使い、土曜の朝に使えるのは30枠です。食パンを x 本、バゲットを y 本焼くとすると、条件は 400x＋200y≦8,000（整理すると 2x＋y≦40）と x＋y≦30、目的は 200x＋150y を最も大きくすることです。
条件を満たす (x, y) の範囲をグラフに描くと、角のある図形になります。目的関数が一次式なら、最も大きくなる点はこの図形の角のどれかにあるので、角を調べれば足ります。
| 角 | 食パン x | バゲット y | 利益 200x＋150y |
|---|---|---|---|
| 粉だけで決まる角 | 20 | 0 | 4,000円 |
| オーブンだけで決まる角 | 0 | 30 | 4,500円 |
| 2つの条件が交わる角 | 10 | 20 | 5,000円 |
食パン10本、バゲット20本のとき、粉もオーブンも使い切って利益は5,000円になり、これが最も大きくなります。
基本情報の範囲ここまで
ここから基本情報！最短の道順と、計算の使い回し
グラフの頂点の間を結ぶ道順のうち、通る辺の重みの合計が最も小さいものを求める問題を最短経路問題といいます。3-6 の配達のグラフで、店から図書館までを考えます。道の長さ（百メートル単位）は、店−花屋4、店−喫茶店2、喫茶店−花屋1、花屋−保育園5、喫茶店−保育園8、保育園−図書館3、喫茶店−図書館10 です。
店から近い頂点から順に、そこまでの最短距離を確定させていきます。喫茶店は2で確定します。花屋は、直接行くと4、喫茶店を通ると2＋1＝3なので3です。保育園は、花屋を通ると3＋5＝8、喫茶店から直接だと2＋8＝10なので8。図書館は、喫茶店から直接だと2＋10＝12、保育園を通ると8＋3＝11なので11です。店→喫茶店→花屋→保育園→図書館の道は、回り道に見えて、いちばん短い道でした。この手順はダイクストラ法と呼ばれます。
この解き方では、花屋までの最短距離3を、保育園や図書館までの計算でそのまま使い回しました。大きな問題を小さな部分問題に分け、部分問題の最適な答えを表に記録しておき、同じ計算を繰り返さずに全体の最適な答えを組み立てる方法を動的計画法（DP）といいます。直前の2項の和で次の項が決まるフィボナッチ数列の第30項も、毎回最初から足し直すと計算の回数が爆発的に増えますが、求めた項を表に残していけば28回の足し算で済みます。
作業の順序と所要時間を有向グラフに表し、全体の完了までに最短で何日かかるか、どの作業が遅れると全体が遅れるかを求めるPERTも、最適化問題の考え方を使う手法の一つです。
基本情報の範囲ここまで
3回目の土曜、こむぎ堂のレジは8時から10時の間だけ2台になりました。ふだん予約の受け取りに使っている台を、その2時間だけ会計にも使うことにしたのです。ミナトが測ると、会計を待つ時間は平均で1分を切り、歩道に行列は出ませんでした。10時を過ぎると、2台目はまた予約の受け取りに戻ります。
店長が最初に考えた「もう1台レジを置くべきか」は、置くか置かないかの二択でした。数字を集めてみると、答えはそのどちらでもありませんでした。行列ができていたのは、1時間に来る人数が多すぎたからではありません。レジが9割の時間ふさがり、来る時刻のばらつきを吸収する余裕がなかったからです。余裕が要るのは土曜の朝の2時間だけだったので、その2時間だけ窓口を増やせば足りました。
片付けを終えた店長が、カレンダーをめくりながらつぶやきます。「じゃあ、クリスマスの朝は何台あればいいのかな」。予約の数は、去年の倍になりそうです。ミナトは表計算ソフトを開き、到着間隔の列に新しい数を入れはじめました。