数理最適化超入門

更新日

2026年6月28日

はじめに（最適化とは）

今日、大学に来たルートは、どのように選びましたか？

時間が短い？
乗り換えが楽？
景色がいい？

到着しなければならない時刻や・体力・費用などの制約がある中で、自分にとって最も良いルートを選んでいたと思います。

このように、制約のもとで目的を最良にする選択をすることを、最適化といいます。

最適化の3要素

先ほどの話しで登場した「制約」「目的」「選択」は、最適化の3要素です。

概念	数学の言葉	通学の例
変えられない条件	制約条件	始業時刻・体力・費用
何を良くしたいか	目的関数	所要時間を最小化
何を決められるか	決定変数	ルート・出発時刻

ミクロ経済学と最適化

ミクロ経済学では、消費者が予算制約のもとで効用を最大化することを考える、という問題がよく登場します。実はこれは、最適化問題の一種です。

消費者問題（ミクロ）

予算制約のもとで
効用を最大化する
\(x_1\)、\(x_2\)の数量を決める

最適化問題（一般形）

制約条件のもとで
目的関数を最大化する
決定変数を求める

ミクロ経済学は、最適化問題の応用だったというわけです。この問題を復習してみましょう。

例題：お菓子の効用最大化

次のような問題を考えます。

週のおやつ予算は600円。
摂取カロリーは1,200 kcalまで。
チョコレート🍫とクッキー🍪の価格、カロリー、得られる満足度は下の表のように示した通り。

	🍫チョコ（1枚）	🍪クッキー（1袋）
価格	150円	100円
カロリー	150 kcal	300 kcal
満足度	4	3

このとき、満足度の合計を最大にするには、チョコレート🍫とクッキー🍪、どちらをどれだけ買えばよいでしょうか？

数式で書くと

この状況を、数式で表すと、次のようになります。

決定変数	チョコ \(x\) 枚、クッキー \(y\) 袋　\((x,\, y \geq 0)\)
目的関数	\(\max\; 4x + 3y\)　（満足度最大化）
制約条件①	\(150x + 100y \leq 600\)　（予算制約）
制約条件②	\(150x + 300y \leq 1200\)　（カロリー制約）

グラフで書くと

この状況を、グラフにすると、次のようになります。

viewof step = Object.assign(
  Inputs.radio(
    ["予算制約のみ", "カロリー制約を追加", "目的関数を動かす", "最適解を表示"],
    {value: "予算制約のみ", label: "表示"}
  ),
  { id: "step-input", style: "font-size: 1.0rem;" }
)

viewof uSlider = Object.assign(
  step === "最適解を表示"
    ? Inputs.range([1, 22], {value: 17, step: 1, label: "満足度 U = "})
    : step === "目的関数を動かす"
      ? Inputs.range([1, 22], {value: 8, step: 1, label: "満足度 U = "})
      : Inputs.range([1, 22], {value: 8, step: 1, label: "満足度 U = ", disabled: true}),
  { id: "uslider-input", style: "font-size: 1.0rem;" }
)

{
  const W = width, H = width * 0.75; // キャンパスサイズ
  const mx = 30, my = 30, mr = 30, mb = 30; // マージン
  const pw = W - mx - mr, ph = H - my - mb; // プロット領域のサイズ

  const xmax = 9, ymax = 7.5;
  const sx = x => mx + (x / xmax) * pw;
  const sy = y => my + ph - (y / ymax) * ph;

  function utilityClipped(U) {
    // 4x+3y=U → y=(U-4x)/3、傾き -4/3
    const pts = [];
    const y_at_x0 = U / 3;
    const x_at_y0 = U / 4;
    if (y_at_x0 <= ymax) pts.push([0, y_at_x0]);
    else pts.push([(U - 3*ymax)/4, ymax]);
    if (x_at_y0 <= xmax) pts.push([x_at_y0, 0]);
    else pts.push([xmax, (U - 4*xmax)/3]);
    return pts;
  }

  const feasible = [[0,0],[4,0],[2,3],[0,4],[0,0]];
  const showCal = step !== "予算制約のみ";
  const showU   = step === "目的関数を動かす" || step === "最適解を表示";
  const showOpt = step === "最適解を表示";
  const U = uSlider;

  const svg = d3.create("svg").attr("width", W).attr("height", H)
    .style("font-family", "sans-serif").style("font-size", "16px");

  const regionPts = showCal ? feasible : [[0,0],[4,0],[0,6],[0,0]];
  svg.append("polygon")
    .attr("points", regionPts.map(([x,y]) => `${sx(x)},${sy(y)}`).join(" "))
    .attr("fill", "#cce5ff").attr("opacity", 0.55);

    for(let i=1;i<=8;i++){
    // 縦線：y=0からymaxまで
    svg.append("line").attr("x1",sx(i)).attr("y1",sy(0)).attr("x2",sx(i)).attr("y2",sy(ymax))
        .attr("stroke","#ddd").attr("stroke-width",1);
    // 横線：x=0からxmaxまで
    svg.append("line").attr("x1",sx(0)).attr("y1",sy(i)).attr("x2",sx(xmax)).attr("y2",sy(i))
        .attr("stroke","#ddd").attr("stroke-width",1);
    }

  svg.append("line").attr("x1",sx(0)).attr("y1",sy(0)).attr("x2",sx(xmax)).attr("y2",sy(0))
    .attr("stroke","#333").attr("stroke-width",2.5);
  svg.append("line").attr("x1",sx(0)).attr("y1",sy(0)).attr("x2",sx(0)).attr("y2",sy(ymax))
    .attr("stroke","#333").attr("stroke-width",2.5);

  for(let i=1;i<=8;i++){
    svg.append("text").attr("x",sx(i)).attr("y",sy(0)+22).attr("text-anchor","middle")
      .attr("font-size","16px").text(i);
    svg.append("line").attr("x1",sx(i)).attr("y1",sy(0)).attr("x2",sx(i)).attr("y2",sy(0)+6)
      .attr("stroke","#333").attr("stroke-width",1.5);
  }
  for(let i=1;i<=7;i++){
    svg.append("text").attr("x",sx(0)-12).attr("y",sy(i)+5).attr("text-anchor","end")
      .attr("font-size","16px").text(i);
    svg.append("line").attr("x1",sx(0)).attr("y1",sy(i)).attr("x2",sx(0)-6).attr("y2",sy(i))
      .attr("stroke","#333").attr("stroke-width",1.5);
  }
  svg.append("text").attr("x",sx(xmax)-80).attr("y",sy(0)-10)
    .attr("font-size","18px").attr("font-weight","bold").text("x（チョコ）");
  svg.append("text").attr("x",sx(0)+10).attr("y",sy(ymax)+15)
    .attr("font-size","18px").attr("font-weight","bold").text("y（クッキー）");

  // 予算制約: 150x+100y=600 → (0,6)〜(4,0)
  svg.append("line")
    .attr("x1",sx(0)).attr("y1",sy(6)).attr("x2",sx(4)).attr("y2",sy(0))
    .attr("stroke","#1a6fc4").attr("stroke-width",3);
  svg.append("text").attr("x",sx(1)-8).attr("y",sy(5)-14)
    .attr("fill","#1a6fc4").attr("font-size","18px").attr("font-weight","bold")
    .text("予算制約");

  // カロリー制約: 150x+300y=1200 → (0,4)〜(8,0)
  if(showCal){
    svg.append("line")
      .attr("x1",sx(0)).attr("y1",sy(4)).attr("x2",sx(8)).attr("y2",sy(0))
      .attr("stroke","#e07b00").attr("stroke-width",3);
    svg.append("text").attr("x",sx(5)).attr("y",sy(1.5)-14)
      .attr("fill","#e07b00").attr("font-size","18px").attr("font-weight","bold")
      .text("カロリー制約");
  }

  if(showU){
    const [[x1,y1],[x2,y2]] = utilityClipped(U);
    svg.append("line")
      .attr("x1",sx(x1)).attr("y1",sy(y1)).attr("x2",sx(x2)).attr("y2",sy(y2))
      .attr("stroke","#22a862").attr("stroke-width",3).attr("stroke-dasharray","8,5");
    svg.append("text").attr("x",sx((x1+x2)/2)+10).attr("y",sy((y1+y2)/2)-20)
      .attr("fill","#22a862").attr("font-size","16px").attr("font-weight","bold")
      .text(`4x + 3y = ${U}`);
  }

  // 頂点：制約追加時はA,C（グレー）
  const pts = showCal
    ? [
        {x:4, y:0, label:"A(4, 0)", opt:false},
        {x:0, y:4, label:"C(0, 4)", opt:false},
        ...(showOpt ? [{x:2, y:3, label:"B(2, 3)", opt:true}] : [])
      ]
    : [
        {x:4, y:0, label:"A(4, 0)", opt:false},
        {x:0, y:6, label:"C(0, 6)", opt:false}
      ];

  pts.forEach(({x,y,label,opt})=>{
    svg.append("circle").attr("cx",sx(x)).attr("cy",sy(y)).attr("r", opt?11:7)
      .attr("fill", opt?"#e63946":"#555").attr("stroke","white").attr("stroke-width",2);
    svg.append("text").attr("x",sx(x)+15).attr("y",sy(y)+5)
      .attr("fill", opt?"#e63946":"#333").attr("font-size","15px")
      .attr("font-weight", opt?"bold":"normal").text(label);
  });

  return svg.node();
}

なぜ角かどが最適解になるのか？

目的関数（満足度）は直線
制約条件も直線 → 実行可能領域は凸多角形

満足度が大きくなる方向に直線をスライドさせると…

実行可能領域に目的関数が最後に触れるのは、必ず頂点になる

このタイプの問題を線形計画問題と呼びます。

現実への応用

このような最適化問題は、表に示すように多くの分野で実際の意思決定の場面に応用されています。

分野	最適化の問題
企業経営	生産計画／資源配分／メディアミックス
政策	予算配分・社会厚生の最大化
金融	ポートフォリオ最適化（リスク vs リターン）
サプライチェーン	コスト最小の輸送計画
AI・機械学習	損失関数の最小化（モデルの学習）

ただし、線形計画法「だけでは」解けない問題もあります。

変数が整数でなければならない → 整数計画問題
目的関数が非線形 → 非線形計画問題
不確実性がある → 確率的最適化
変数が数百万個 → 大規模最適化

このように、次々に手法が開発され、多くの問題が解けるようになっています

組み合わせ最適化

線形計画から整数計画へ

お菓子の最適化問題の例で、設定によっては、最適解がクッキー \(x = 3.7\) 袋…などということになることもありそうです。ただし、そのような解が得られたとしても、そのようにクッキーを買うことはできません（実行不可能）。では、どうすればよいでしょうか。

最適化問題に、変数が整数でなければならない制約を加えるとどうなるか、考えてみましょう。

{
  const W = 460, H = 460;
  const mx = 30, my = 30, mr = 30, mb = 30;
  const pw = W - mx - mr, ph = H - my - mb;
  const xmax = 5, ymax = 5;
  const sx = x => mx + (x / xmax) * pw;
  const sy = y => my + ph - (y / ymax) * ph;

  const svg = d3.create("svg").attr("width", W).attr("height", H)
    .style("font-family", "sans-serif");

  // 実行可能領域: (0,0),(4,0),(2,3),(0,4)
  const region = [[0,0],[4,0],[2,3],[0,4]];
  svg.append("polygon")
    .attr("points", region.map(([x,y]) => `${sx(x)},${sy(y)}`).join(" "))
    .attr("fill","#cce5ff").attr("opacity",0.4);

  // 予算制約: 150x+100y=600 → (0,6)〜(4,0)
  svg.append("line")
    .attr("x1",sx(0)).attr("y1",sy(6)).attr("x2",sx(4)).attr("y2",sy(0))
    .attr("stroke","#1a6fc4").attr("stroke-width",1.5).attr("stroke-dasharray","4,3").attr("opacity",0.7);
  svg.append("text").attr("x",sx(1.4)).attr("y",sy(4))
    .attr("fill","#1a6fc4").attr("font-size","16px").text("予算制約");

  // カロリー制約: 150x+300y=1200 → (0,4)〜(8,0)
  svg.append("line")
    .attr("x1",sx(0)).attr("y1",sy(4)).attr("x2",sx(8)).attr("y2",sy(0))
    .attr("stroke","#e07b00").attr("stroke-width",1.5).attr("stroke-dasharray","4,3").attr("opacity",0.7);
  svg.append("text").attr("x",sx(3.5)).attr("y",sy(1.4))
    .attr("fill","#e07b00").attr("font-size","16px").text("カロリー制約");

  // 格子点（x=0〜8, y=0〜4）
  for(let i=0;i<=8;i++)
    for(let j=0;j<=4;j++){
      const inLP = 150*i+100*j<=600 && 150*i+300*j<=1200 && i>=0 && j>=0;
      svg.append("circle").attr("cx",sx(i)).attr("cy",sy(j)).attr("r",inLP?6:3)
        .attr("fill",inLP?"#1a6fc4":"#ccc").attr("opacity",inLP?0.8:0.4);
    }

  // 軸
  svg.append("line").attr("x1",sx(0)).attr("y1",sy(0)).attr("x2",sx(xmax)).attr("y2",sy(0))
    .attr("stroke","#333").attr("stroke-width",2);
  svg.append("line").attr("x1",sx(0)).attr("y1",sy(0)).attr("x2",sx(0)).attr("y2",sy(ymax))
    .attr("stroke","#333").attr("stroke-width",2);
  for(let i=0;i<=8;i++){
    svg.append("text").attr("x",sx(i)).attr("y",sy(0)+20).attr("text-anchor","middle")
      .attr("font-size","14px").text(i);
  }
  for(let j=0;j<=4;j++){
    svg.append("text").attr("x",sx(0)-10).attr("y",sy(j)+5).attr("text-anchor","end")
      .attr("font-size","14px").text(j);
  }

  // LP最適解 (2,3)
  svg.append("circle").attr("cx",sx(2)).attr("cy",sy(3)).attr("r",12)
    .attr("fill","none").attr("stroke","#e63946").attr("stroke-width",3);
  svg.append("text").attr("x",sx(2)+16).attr("y",sy(3)-10)
    .attr("fill","#e63946").attr("font-size","15px").attr("font-weight","bold")
    .text("LP最適解 (2,3) ✓ 整数！");

  // 軸ラベル
  svg.append("text").attr("x",sx(xmax)-50).attr("y",sy(0)-8)
    .attr("font-size","15px").attr("font-weight","bold").text("x（チョコ）");
  svg.append("text").attr("x",sx(0)+8).attr("y",sy(ymax)+14)
    .attr("font-size","15px").attr("font-weight","bold").text("y（クッキー）");

  // 凡例
  svg.append("circle").attr("cx",sx(3)).attr("cy",sy(4.5)).attr("r",6)
    .attr("fill","#1a6fc4").attr("opacity",0.8);
  svg.append("text").attr("x",sx(3)+12).attr("y",sy(4.5)+5)
    .attr("font-size","16px").text("整数の実行可能解");

  return svg.node();
}

先ほどのクッキーとチョコレートの例では、たまたま最適解が整数になりましたが、一般には線形計画問題の解が整数になるとは限りません。

線形計画問題（LP）と整数計画問題（IP）の違い

変数が整数でなければならないという制約を加えた問題を、整数計画問題といいます。線形計画問題と整数計画問題の違いを簡単に整理してみます。

	線形計画（LP）	整数計画（IP）
実行可能領域	凸多角形（凸多面体）	格子点
最適解	実行可能領域の頂点	LPの最適解とずれる
求解	比較的早く解ける	はるかに難しい

整数計画問題の例：チーム編成問題

次のような問題を考えましょう。

8人の学生を2つのグループに分けたい
過去のグループワークですでに同じグループだったペアをできるだけ少なくしたい

これを数理最適化の問題としてとらえるために、決定変数・制約条件・目的関数を数式で表してみましょう。

決定変数

決定変数を0/1（ゼロ・イチ）変数にします。 0/1変数とは、0または1のどちらかの値を取る変数です。

\(x_{ig} \in \{0, 1\}\quad i=\{1,2,\ldots , 8\}\quad g=\{1, 2\}\)

\[x_{ig} = \begin{cases} 1 & \text{学生} i \text{ がグループ} g \text{ に入る} \\ 0 & \text{それ以外} \end{cases}\]

変数は、8人 × 2グループ = 16個の0/1変数です。

\(g\backslash i\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)
\(1\)	\(x_{11}\)	\(x_{21}\)	\(x_{31}\)	\(x_{41}\)	\(x_{51}\)	\(x_{61}\)	\(x_{71}\)	\(x_{81}\)
\(2\)	\(x_{12}\)	\(x_{22}\)	\(x_{32}\)	\(x_{42}\)	\(x_{52}\)	\(x_{62}\)	\(x_{72}\)	\(x_{82}\)

それぞれの\(x_{ig}\)が0または1の値をとります。

例えば、グループ \(1=\{1, 2, 3, 4\}\)、グループ \(2=\{5, 6, 7, 8\}\)のとき、そのようなグループ分けの状態は次のような変数の組み合わせとして表すことができます。

\(g\backslash i\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)
\(1\)	\(1\)	\(1\)	\(1\)	\(1\)	\(0\)	\(0\)	\(0\)	\(0\)
\(2\)	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)

また、グループ \(1=\{1, 3, 5, 7\}\)、グループ \(2=\{2, 4, 6, 8\}\)のときには、\(x_{ig}\)は下の表のようになります。

\(g\backslash i\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)
\(1\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)	\(0\)
\(2\)	\(0\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)

制約条件

上の2つの\(x_{ig}\)例を見て、何か決まりがあることに気づいたのではないでしょうか。それがそのまま制約条件になります。

制約①：各学生は必ずどちらか1つだけのグループに所属

これは先ほどの\(x_{ig}\)の表でいうと、表の列和（縦方向の合計）が必ず1になることを意味します。ある個人\(i\)についてみたときに、その人がどちらのグループにも属していない（\(x_{i1}=0\)かつ\(x_{i2}=0\)）とか、両方のグループに所属している（\(x_{i1}=1\)かつ\(x_{i2}=1\)）状態を許さない、という制約です。これを数式で表現すると次のようになります。

\[x_{i1} + x_{i2} = \sum_gx_{ig} = 1 \quad (\forall i\in\{1,2,\ldots,8\})\]

制約②：グループサイズの上限は4人

これは先ほどの\(x_{ig}\)の表でいうと、表の行和（横方向の合計）が必ず4以下になることを意味します。これを数式で表現すると次のようになります。

\[x_{1g} + x_{2g} + \cdots x_{8g} = \sum_ix_{ig} \leq 4 \quad (\forall g\in\{1,2\})\]

目的関数

目的関数は、過去のグループワークですでに同じグループだったペアをできるだけ少なくすることです。これを数式で表現するために、補助変数 \(y_{ij} \in \{0,1\}\) を導入します。

\[y_{ij} = \begin{cases} 1 & \text{学生}i\text{と}j\text{が今回同じグループに入る} \\ 0 & \text{それ以外} \end{cases}\]

そして、学生\(i\)と学生\(j\)過去に同じグループだった回数を\(w_{ij}\)とすると、目的関数は以下のように表すことができます。

\[\min \sum_{i,j} w_{ij} \cdot y_{ij}\]

同じグループに入った全てのペアについての\(w_{ij}\)合計を最小化する、という意味です。

そして、\(y_{ij}\)と\(x_{ig}\)の関係を規定する制約式を追加します（これは少しテクニカルな話なので、理解しなくても構いません）。

\[y_{ij} \geq x_{ig} + x_{jg} - 1 \quad \forall i,j,g\]

手作業でやってみよう

【練習1】8人・履歴1回・2グループ（4+4）

過去のチーム分けが以下の通りであったとします。

グループ \(X = \{1,2,3,4\}\)、グループ \(Y = \{5,6,7,8\}\)

このとき、できるだけ過去のブループが一緒だったペアが少なくなるように、2グループに分けてください。

グループ 1	グループ 2
?	?

そのグループ分けにおいて、過去に同じグループで一緒だったペアは、合計で何ペアありますか？

【練習2】8人・履歴2回・2チーム（4+4）**

過去のチーム分けが以下の通りであったとします。 - 1回目：チーム \(X = \{1,2,3,4\}\)、チーム \(Y = \{5,6,7,8\}\) - 2回目：チーム \(X' = \{1,3,5,7\}\)、チーム \(Y' = \{2,4,6,8\}\)

このとき、できるだけ過去ペアが少なくなるよう2チームに分けてください。

グループ 1	グループ 2
?	?

そのグループ分けにおいて、過去に同じグループで一緒だったペアは、合計で何ペアありますか？そして、「これが本当に最小か」自信を持って言えますか？

コンピュータで解くと…

グループ分けの履歴が1回増えると、最適解を見つけるのがより難しくなるのが分かったと思います。コンピュータを使って全ての場合を列挙してこの問題を解くと、最適解でのスコアは8であることがわかりあます。すなわち、これが証明された最小値だということです。

しかし、同じスコア8を達成する並べ方は9通りあります。「正解はこれ」だけではなく「最適値が8であること（それよりも良い解がないこと）が証明された」ことも大事です。

スコア8を達成するすべての組み合わせ
	グループ 1	グループ 2
(1)	1, 2, 5, 6	3, 4, 7, 8
(2)	1, 2, 5, 7	3, 4, 6, 8
(3)	1, 2, 6, 8	3, 4, 5, 7
(4)	1, 2, 7, 8	3, 4, 5, 6
(5)	1, 3, 5, 6	2, 4, 7, 8
(6)	1, 3, 5, 7	2, 4, 6, 8
(7)	1, 3, 6, 8	2, 4, 5, 7
(8)	1, 3, 7, 8	2, 4, 5, 6
(9)	1, 4, 6, 7	2, 3, 5, 8

また、生徒の人数やグループの数が増えると、より困難になることが容易に想像できます。

実践：来週からのグループ分け

24人の学生を6人ずつ4つのグループに分けることを考えるとき、何通りの分け方があるでしょうか？その答えは、以下のように計算できます。

\[ \frac{{}_{24}C_{6}\times {}_{18}C_{6}\times {}_{12}C_{6}}{4!} = \text{9,663,972,130} \]

全ての分け方について過去ペア数の合計を計算するには、96.6億通りの計算が必要になります。これは、コンピュータを使っても数分〜数時間かかる計算量です。したがって、先ほどの8人のグループ分けでやったように、全ての組み合わせを計算し、最適解を全て列挙することは困難です。

しかし、整数計画問題として定式化し、その求解ツールを使えば、短時間で最適解（の1つ）を求めることができます。

ヒント

R + OMPR + HiGHS 使ってこの問題を解くRコードを公開します。興味があるかたは、試してみてください。

定式化をΣ記号でまとめると

チーム編成問題の定式化をまとめておきます。なんだか難しそうに見えますが、これまでの説明を思い出せば、1つ1つの式の意味はわかると思います。

\[\min \sum_{i < j} w_{ij} \cdot y_{ij}\]

\[\text{s.t.} \quad \sum_{g} x_{ig} = 1 \quad \forall i\]

\[\sum_{i} x_{ig} \leq 6 \quad \forall g\]

\[y_{ij} \geq x_{ig} + x_{jg} - 1 \quad \forall i,j,g\]

\[x_{ig},\, y_{ij} \in \{0, 1\}\]

空間最適化へ

チーム編成問題は、最適なグループ分けを見つける問題でした。言うなれば、人をグループに割り当てる問題です。

空間的な問題に対しても、最適化の考え方が適用できることがわかります。例えば、以下のような問題があります。

施設配置問題：人を施設に割り当てる
- どこに施設を置けば住民の移動距離が最小になるか
輸送問題：施設と施設を割り当てる
- 工場から倉庫への輸送コストを最小化
巡回セールスマン問題（TSP）：人を経路に割り当てる
- 全都市を最短経路で回るルートを探す

これらはすべて、すべて「制約のもとで目的を最小化／最大化する」整数計画問題です。

施設配置問題

福岡市内に宅配ピザ店を3店舗新設することを考えてみましょう。このとき、商圏人口を最大化するには、どこに出店すればよいでしょうか？

この問題にも0/1整数計画問題が適用できることがわかります。すなわち：

決定変数：各候補地に置くか否か（0/1）
目的関数：カバーされる人口の最大化
制約条件：出店数 = 3

1店舗だけ出店する場合とは、考え方がちょっと変わりますよね。

巡回セールスマン問題（TSP）

これは例えば\(n\)個の支社をすべて1回ずつ訪問して本社に戻る最短ルート（訪問順）を求める問題です。

{
  const W = 450, H = 450;
  const svg = d3.create("svg").attr("width", W).attr("height", H)
    .style("font-family","sans-serif");

  const cities = [
    {name:"東京", x:380, y:200},
    {name:"大阪", x:225, y:250},
    {name:"名古屋", x:300, y:270},
    {name:"福岡", x:100, y:270},
    {name:"札幌", x:390, y:40},
    {name:"仙台", x:400, y:110},
    {name:"広島", x:150, y:250},
    {name:"那覇", x:50, y:400},
  ];

  const route = [0,5,4,1,6,3,7,2];

  for(let k=0;k<route.length;k++){
    const a = cities[route[k]], b = cities[route[(k+1)%route.length]];
    svg.append("line")
      .attr("x1",a.x).attr("y1",a.y).attr("x2",b.x).attr("y2",b.y)
      .attr("stroke","#1a6fc4").attr("stroke-width",2).attr("opacity",0.6);
  }

  cities.forEach(c=>{
    svg.append("circle").attr("cx",c.x).attr("cy",c.y).attr("r",10)
      .attr("fill","#e63946").attr("stroke","white").attr("stroke-width",2);
    svg.append("text").attr("x",c.x+13).attr("y",c.y+5)
      .attr("font-size","15px").attr("font-weight","bold").text(c.name);
  });

  return svg.node();
}

上の図に示すように、訪問すべき地点が7であれえば、全ての経路数 = 7! / 2 = 2,520通り程度です。しかし、地点数が増えると経路数は爆発的に増加します。そうなると、コンピュータを使っても、大きなスケールの問題を解くのは難しくなります。

まとめ

線形計画：連続変数、グラフで解ける
整数計画：0/1変数、組み合わせ爆発、でも定式化は同じ発想
グループ分けも施設配置もTSPも同じ枠組み
GISと組み合わせると空間的な最適化へ

ヒント

次回：空間最適化の考え方を使って、自転車観光ルートを考えてみたいと思います。