今回も第19回・20回に引き続き、アルゴリズムで解ける発展的な問題を紹介します。今回のテーマは「線形計画問題」です。やや難しい内容になりますが、アルゴリズムを使えば“こんな問題も解けるのか”ということを体感していただけると幸いです。

線形計画問題とは

線形計画問題は以下のような問題です。 目の前にラーメンとサラダが置かれており、1gあたりのカロリーはラーメンが3kcal、サラダが1kcalです。また、1gあたりの値段はラーメンが2円、サラダが4円です。あなたは以下の条件の下で、できるだけたくさんのものを食べたいと考えています。最大で何g食べることができるでしょうか。

  • • カロリーの合計を600kcal以下
  • • 値段の合計を1000円以下

    例えばラーメンを200g、サラダを100g食べる場合、合計カロリーが700kcalとなってしまい、カロリー制限を超過してしまいます。また、ラーメンを100g、サラダを250g食べる場合、カロリー制限は超過しないものの、合計価格が1200円となってしまい、価格制限を超過してしまいます。

    しかし、ラーメンを140g、サラダを180g食べる場合、カロリー制限も価格制限も超過せずに合計320gを達成できます。そして、これ以上食べる方法は存在しないため、320gがこの問題の答えとなります。

    なお、厳密には線形計画問題は「一次式で表される条件がたくさん与えられるとき、一次式で表されるスコアを最大にする問題」なのですが、今回はこのような細かいことを詳しく説明せず、先に進もうと思います。

    線形計画問題の解き方

    それでは、先ほどの320gという答えはどう導き出せばよいのでしょうか。まず、横軸xを食べるラーメンの量、縦軸yを食べるサラダの量としたグラフに、条件を書き込みます。カロリーの条件は3x+y≤600という式で表されるので、直線3x+y=600をグラフに書き込みます。また、価格の条件は2x+4y≤1000という式で表されるので、直線2x+4y=1000をグラフに書き込みます。

    すると、最適な答えは2つの直線の交点に絞られます（直線はx軸およびy軸を含む）。この理由は少し難しいですが、下図のように食べる合計の量x+yを少しずつ上げていったとき、最後は2つの直線の交点で「条件を満たす部分」と離れるから、と理解しましょう。

    したがって、2つの直線の交点を全探索すれば、線形計画問題を解くことができます。具体的には以下のようになります。

    ステップ1: 交点を列挙

    下図に示すように、交点は(x,y)=(0,0)、(0,250)、(0,600)、(140,180)、(200,0)、(500,0)の6つである。

    ステップ2: 各交点について調べる

    これらのうち、価格とカロリーの条件を両方満たすのは (0,0)、(0,250)、(140,180)、(200,0) のみであり、食べる量の合計はそれぞれ0g、250g、320g、200gであるため、答えは320gとなる。

    解法の問題点

    しかし、前章で紹介した解法には問題点があります。それは計算に時間がかかることです。もちろん、先ほどの例のように条件がカロリーと価格の2つしかない場合、6通りの交点を全探索するだけで済むので、大した問題ではありません。しかし、カロリーと価格だけでなく、タンパク質、脂質、ビタミンなどのさまざまな条件を付け加えると、交点の数が一気に増えてしまいます。例えば条件が100個の場合、なんと5151通りを全探索する必要が出てきます。

    効率的なアルゴリズム：単体法

    そこでより効率的なアルゴリズムとして、「単体法」が知られています。単体法は、最初は(0,0)から出発し、「ある直線に沿って、スコアが改善する方向にギリギリまで移動する」ということを繰り返すアルゴリズムです。少し複雑なので、冒頭の具体例で考えてみましょう。

    ステップ1

    まず、スタート地点である(x,y)=(0,0)は「x軸」と「y軸」の交点ですが、どちらに沿って動いてもスコア※が上昇します。そのため、適当にx軸に沿って、条件を満たすギリギリのところまで動きます。すると下図のようになり、(x,y)=(200,0) に到達します。

    ※ここでは食べる量の合計x+y

    ステップ2

    次に、現在位置(x,y)=(200,0)は「x軸」と「カロリー上限」の交点ですが、x軸に沿って動くとスコアが低下する一方、カロリー上限に沿って動くとスコアが上昇します。そのため、カロリー上限に沿って、条件を満たすギリギリのところまで動きます。すると下図のようになり、(x,y)=(140,180) に到達します。

    ステップ3

    最後に、現在位置(x,y)=(140,180)は「カロリー上限」と「価格上限」の交点ですが、どちらに沿って動いてもスコアは低下してしまいます。そのため、単体法では(x,y)=(140,180)を答えとして出力します。なお、証明は難しいので省略しますが、単体法が最後に出力する解は最適解であることが保証されています。

    なお、単体法を使うと、「ラーメンの量xとサラダの量y」のように変数が2つのケースであれば、条件が数十万個あっても、現実的な時間で解けることが多いです。また、難易度が高いので本稿では説明しませんが、単体法は変数が3つ以上の場合にも応用することができます。詳しくは、筆者が以前作成した「数理最適化ことはじめ」というスライドをご覧ください。