アルゴリズムの発展的問題・線形計画問題

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

線形計画問題とは

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

• カロリーの合計を600kcal以下

• 値段の合計を1000円以下

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

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

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