Ｅｘｃｅｌソルバーによる整数計画法の解法

整数計画法とは

整数計画法とは、線形計画法の派生手法の一つで、「変数の全部あるいは一部が整数値である」という制約条件を加えたものです。

これまでの線形計画法の定式化と図式解法などでは、製品ｘとｙは「トン」のような連続量だとしていました。しかし、製品が機械のようなものだと、最適解が１６.５個などではなく、１６個、１７個のような整数でないと不適切な場合があります。

通常の線形計画法での最適解が整数値だと説明がしにくいので、モデルを若干修正しました、

整数制約がないときのの場合は下左図のようになり、制約条件は青色の範囲で、最適解はＰ点になります。製品ｙは６個ですが、製品ｘは１６.５個になってしまいました。
　Ｐ点付近を拡大したのが下右図です。ｘとｙが整数になる候補として、赤点が考えられます。目的関数（赤線）との関係から、直感的にＱ点（ｘ＝１６個、ｙ＝６個）が最適であるとわかります。

単純なモデルならば、このようにいつかの候補に絞り込み、目的関数を計算して最大のものを求めることもできますが、変数や制約式が多い場合は不可能です。整数計画法の解法は幾つかありますが、すべて私たちには理解が困難な高度な数学を用います。
　解法を理解するのではなく、単に解を得たいだけなら、Excelのソルバー機能が利用できます。

整数計画法の応用と限界

生産計画で、設備有無を０と１で表すことにより、設備の有無も含めた最適解を得ることができます。
　それを発展させれば、いわゆる組合せ問題を整数計画法として定式化できます。
　組合せ問題はＯＲの分野で適用したい問題が多いのに、計算量が極度に大きくなるので、何らかの妥協をしてアプローチしている現状です。

効率的な整数計画法の解法が期待されるのですが、未だ画期的なものがありません。専用のアプリでもそうなのですから、実務的な問題をソルバーで解くのは無理だといえます。

整数制約のない場合の求解操作

ソルバーによる(（通常の）線形計画法の解法は、「Ｅｘｃｅｌソルバーによる整数計画法の解法」で説明しました。
　その復習から始めます。

Ｅｘｃｅｌを起動して，次の入力画面のように入力します。

入力を終えたExcelファイル（reidai.xlsx）をダンロードできます。

入力画面

Ｅｘｃｅｌ画面で，［データ］→［ソルバー］をクリックすると，ソルバーが起動して，「ソルバーのパラメータ」が表示されるので、次のように設定します。

設定画面１

［解決］をクリックすると、最適解が得られると、次の画面が表示されます。

設定画面２

［ＯＫ］をクリックすると、入力画面が次のように変化します（緑と青の個所）。

整数制約がないときの解

すなわち，「ｘ＝１６.５，ｙ＝６のとき，目的関数は最大値６１.５になり，制約条件はａとｂは余裕がないが，ｃは４８－３４.５＝４.５の余裕がある」ことがわかります。

整数制約がある場合

ソルバーでは、「ｘとｙは整数値である」ことを、「制約条件の追加」で設定します。設定画面１で「追加」をクリックし、設定画面３で「int」を指定します。これだけでよいのだから簡単ですね。

設定画面３

［ＯＫ］をクリックすると、設定画面２に整数条件を追加した設定画面４が表示されます。

設定画面４

後は、制約がない場合とほぼ同じです。［解決］をクリックすると、最適解が得られたとき、次の画面が表示されます。

設定画面５

［ＯＫ］をクリックすると、入力画面が次のように変化します（緑と青の個所）。

整数条件を加えたときの解

これより、最適解はｘ＝１６個、ｙ＝６個で、目的関数の値が６０であることがわかります、