Microsoft Solver Foundationを利用して、単純な線形計画問題をシンプレックス法で解きます。

問題

下記の条件のとき、売上を最大にするためには「ぺんぎんクッキー」と「らくだサブレ」をいくつ作るのが良いでしょうか？

製品情報

商品	小麦粉	砂糖	販売価格
ぺんぎんクッキー	4	3	14,500
らくだサブレ	6	2	9,800

在庫情報

原料	在庫
小麦粉	25
砂糖	10

答えを求める

先に検証用の結果を出します。

とします。
在庫の条件は 販売価格は となります。
条件は
です。
在庫の条件式を変形します。
この2つの式をグラフに描画します。


両方を満たす領域(黄色に塗られた多角形)と が交差する範囲で最もrが大きくなる値を探すと、黄色の多角形の右上の頂点部分(ピンクと水色の線が交差する頂点)であることがわかります。このx,yの値が求める答えとなります。図から、x=1.0 y=3.5 程度に見えます。

プログラム

Windows フォームアプリケーションを作成します。

事前準備

Microsoft Solver Foundation をインストールします。インストール手順はこちらの記事を参照してください。

UI

下図のUIを作成します。ボタンと複数行のテキストボックスを配置します。

コード

下記のコードを記述します。

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using Microsoft.SolverFoundation;
using Microsoft.SolverFoundation.Solvers;

namespace SimpleSimplex
{
  public partial class FormMain : Form
  {
    public FormMain()
    {
      InitializeComponent();
    }

    private void button1_Click(object sender, EventArgs e)
    {
      SimplexSolver simplex = new SimplexSolver();

      int p1, p2;
      simplex.AddVariable("ぺんぎんクッキー", out p1);
      simplex.AddVariable("らくだサブレ", out p2);
      simplex.SetBounds(p1, 0, 10000);
      simplex.SetBounds(p2, 0, 10000);

      int flour;
      int sugar;
      simplex.AddRow("小麦粉", out flour);
      simplex.AddRow("砂糖", out sugar);

      simplex.SetBounds(flour, 0, 25);
      simplex.SetBounds(sugar, 0, 10);

      simplex.SetCoefficient(flour, p1, 4);
      simplex.SetCoefficient(sugar, p1, 3);

      simplex.SetCoefficient(flour, p2, 6);
      simplex.SetCoefficient(sugar, p2, 2);

      int price;
      simplex.AddRow("販売価格", out price);
      simplex.SetCoefficient(price, p1, 14500);
      simplex.SetCoefficient(price, p2, 9800);
      simplex.AddGoal(price, 1, false);

      simplex.Solve(new SimplexSolverParams());

      textBox1.Text += string.Format("ぺんぎんクッキー:{0:f} , らくだサブレ:{1:f}\r\n",simplex.GetValue(p1).ToDouble(), simplex.GetValue(p2).ToDouble());
      textBox1.Text += string.Format("販売価格合計:{0:f}\r\n", simplex.GetValue(price).ToDouble(), simplex.GetValue(p2).ToDouble());
      textBox1.Text += string.Format("小麦粉使用量:{0:f} , 砂糖使用量:{1:f}\r\n", simplex.GetValue(flour).ToDouble(), simplex.GetValue(sugar).ToDouble());

    }
  }
}

解説

初めにシンプレックス法のソルバー SimplexSolver のオブジェクトを作成します。

  SimplexSolver simplex = new SimplexSolver();

変数を追加します。今回の例では、「ぺんぎんクッキー」「らくだサブレ」それぞれの商品の生産数が変数になります。ここで用いられるp1,p2は計算結果の値が入る変数ではなく、変数を識別するためのIDが設定されます。AddVariableメソッドで変数を追加すると、その変数の識別IDがout変数で戻ります。

  int p1, p2;
  simplex.AddVariable("ぺんぎんクッキー", out p1);
  simplex.AddVariable("らくだサブレ", out p2);

変数の取りうる範囲を設定します。今回の問題では範囲が示されていないため、設定しないでも問題ありません。とりあえず、0～10000の範囲としておきます。

  simplex.SetBounds(p1, 0, 10000);
  simplex.SetBounds(p2, 0, 10000);

材料に関する情報を設定します。商品を作るために必要な材料を追加します。今回は「小麦粉」と「砂糖」の2つになります。こちらも先ほどの変数の追加と同様に、追加された列を識別するためのIDがout変数で戻されます。

      int flour;
      int sugar;
      simplex.AddRow("小麦粉", out flour);
      simplex.AddRow("砂糖", out sugar);

材料の取りうる範囲を指定します。今回は在庫の量が指定されているため、在庫以上には使用できない条件とします。小麦粉は25以下、砂糖は10以下となります。

      simplex.SetBounds(flour, 0, 25);
      simplex.SetBounds(sugar, 0, 10);

係数(Coefficient)を設定します。それぞれの商品の生産に必要な材料の量を設定します。

  //ぺんぎんクッキーの生産に必要な材料
  simplex.SetCoefficient(flour, p1, 4);
  simplex.SetCoefficient(sugar, p1, 3);

  //らくだサブレの生産に必要な材料
  simplex.SetCoefficient(flour, p2, 6);
  simplex.SetCoefficient(sugar, p2, 2);

販売価格の設定をします。

  int price;
  simplex.AddRow("販売価格", out price);
  simplex.SetCoefficient(price, p1, 14500);
  simplex.SetCoefficient(price, p2, 9800);

計算結果のゴールの設定をします。price の値が最大となる設定とします。

  simplex.AddGoal(price, 1, false);

Solveメソッドを呼び出し、計算を実行します。計算結果をテキストボックスに表示します。
計算結果はGetValueメソッドを呼び出して取得します。取得したい値のIDをGetValueメソッドの引数に与えます。

  simplex.Solve(new SimplexSolverParams());

  textBox1.Text += string.Format("ぺんぎんクッキー:{0:f} , らくだサブレ:{1:f}\r\n",simplex.GetValue(p1).ToDouble(), simplex.GetValue(p2).ToDouble());
  textBox1.Text += string.Format("販売価格合計:{0:f}\r\n", simplex.GetValue(price).ToDouble(), simplex.GetValue(p2).ToDouble());
  textBox1.Text += string.Format("小麦粉使用量:{0:f} , 砂糖使用量:{1:f}\r\n", simplex.GetValue(flour).ToDouble(), simplex.GetValue(sugar).ToDouble());

実行結果

プロジェクトを実行します。下図のウィンドウが表示されます。


[button1]をクリックします。計算が実行され結果が表示されます。