私はクラスで線形計画問題をグラフ化してやっていますが、特定の問題を解決するためのプログラムを作成する方法を知りたいです。変数や制約が多すぎると、グラフ化してこれを行うことはできません。
問題の例、制約付きで5x+3yを最大化します。
これをグラフ化すると、3つのコーナーがある可視領域が得られました。x = 5 y=2が最適な点です。
これをコードに変換するにはどうすればよいですか？私はシンプレックス法を知っています。そして非常に重要なのは、すべてのLP問題が同じ構造でコーディングされるのでしょうか。ブルートフォースは機能しますか？
検索すると、かなりの数のシンプレックス実装が見つかります。
コメント（Cの数値レシピ）で言及されているものに加えて、次のものも見つけることができます：
他の2つの質問に対処するには：
すべてのLPは同じ方法でコーディングされますか？はい、一般的なLPソルバーは、任意のLPをロードして解決するように作成できます。（LPのようなものを読むための業界標準のフォーマットがありmpsます.lp
ブルートフォースは機能しますか？多くの企業や大規模な組織は、ソルバーの微調整に長い時間を費やしていることに注意してください。多くのソルバーが利用しようとする興味深い特性を持つLPがあります。また、特定の計算を並行して解決することもできます。アルゴリズムは指数関数的であるため、いくつかの変数/制約では、ブルートフォースは機能しません。
お役に立てば幸いです。
私は昨日これをmatlabと書きました。これは、Eigenライブラリを使用するか、std::vectorのstd::vectorを使用して独自の行列クラスを作成すると、C++に簡単に変換できます。
function [x, fval] = mySimplex(fun, A, B, lb, up)
%Examples paramters to show that the function actually works
% sample set 1 (works for this data set)
% fun = [8 10 7];
% A = [1 3 2; 1 5 1];
% B = [10; 8];
% lb = [0; 0; 0];
% ub = [inf; inf; inf];
% sample set 2 (works for this data set)
fun = [7 8 10];
A = [2 3 2; 1 1 2];
B = [1000; 800];
lb = [0; 0; 0];
ub = [inf; inf; inf];
% generate a new slack variable for every row of A
numSlackVars = size(A,1); % need a new slack variables for every row of A
% Set up tableau to store algorithm data
tableau = [A; -fun];
tableau = [tableau, eye(numSlackVars + 1)];
lastCol = [B;0];
tableau = [tableau, lastCol];
% for convienience sake, assign the following:
numRows = size(tableau,1);
numCols = size(tableau,2);
% do simplex algorithm
% step 0: find num of negative entries in bottom row of tableau
numNeg = 0; % the number of negative entries in bottom row
for i=1:numCols
if(tableau(numRows,i) < 0)
numNeg = numNeg + 1;
end
end
% Remark: the number of negatives is exactly the number of iterations needed in the
% simplex algorithm
for iterations = 1:numNeg
% step 1: find minimum value in last row
minVal = 10000; % some big number
minCol = 1; % start by assuming min value is the first element
for i=1:numCols
if(tableau(numRows, i) < minVal)
minVal = tableau(size(tableau,1), i);
minCol = i; % update the index corresponding to the min element
end
end
% step 2: Find corresponding ratio vector in pivot column
vectorRatio = zeros(numRows -1, 1);
for i=1:(numRows-1) % the size of ratio vector is numCols - 1
vectorRatio(i, 1) = tableau(i, numCols) ./ tableau(i, minCol);
end
% step 3: Determine pivot element by finding minimum element in vector
% ratio
minVal = 10000; % some big number
minRatio = 1; % holds the element with the minimum ratio
for i=1:numRows-1
if(vectorRatio(i,1) < minVal)
minVal = vectorRatio(i,1);
minRatio = i;
end
end
% step 4: assign pivot element
pivotElement = tableau(minRatio, minCol);
% step 5: perform pivot operation on tableau around the pivot element
tableau(minRatio, :) = tableau(minRatio, :) * (1/pivotElement);
% step 6: perform pivot operation on rows (not including last row)
for i=1:size(vectorRatio,1)+1 % do last row last
if(i ~= minRatio) % we skip over the minRatio'th element of the tableau here
tableau(i, :) = -tableau(i,minCol)*tableau(minRatio, :) + tableau(i,:);
end
end
end
% Now we can interpret the algo tableau
numVars = size(A,2); % the number of cols of A is the number of variables
x = zeros(size(size(tableau,1), 1)); % for efficiency
% Check for basicity
for col=1:numVars
count_zero = 0;
count_one = 0;
for row = 1:size(tableau,1)
if(tableau(row,col) < 1e-2)
count_zero = count_zero + 1;
elseif(tableau(row,col) - 1 < 1e-2)
count_one = count_one + 1;
stored_row = row; % we store this (like in memory) column for later use
end
end
if(count_zero == (size(tableau,1) -1) && count_one == 1) % this is the case where it is basic
x(col,1) = tableau(stored_row, numCols);
else
x(col,1) = 0; % this is the base where it is not basic
end
end
% find function optimal value at optimal solution
fval = x(1,1) * fun(1,1); % just needed for logic to work here
for i=2:numVars
fval = fval + x(i,1) * fun(1,i);
end
end