手動編寫線性編程練習

Question

我一直在繪製線性編程問題，但我想知道如何編寫一個特定問題的程序來爲我解決這個問題。如果有太多的變量或限制，我永遠無法通過繪圖來做到這一點。

實施例的問題，最大化5X + 3Y與約束：

• 5倍 - 2Y> = 0
• X + Y < = 7
• X < = 5
• X> = 0
• y> = 0

我繪製了這個圖，得到了一個可見的r帶3個角落的天體。 x = 5 y = 2是最佳點。

我該如何將它變成代碼？我知道單純的方法。而且非常重要的是，所有LP問題都將在相同的結構中編碼？暴力行爲會起作用嗎？

Answer 1

如果您搜索，您會發現很多Simplex實現。

除了在註釋（數字食譜在C）中提到的一個， 你還可以找到：

1. Google's own Simplex-Solver
2. 然後是COIN-OR
3. GNU都有自己GLPK
4. 如果你想要一個C++實現，這個在Google Code實際上是可以訪問的。
5. R中有許多實現，包括boot package。 （在R，您可以通過不括號鍵入它看到一個函數的實現。）

爲了解決您的另外兩個問題：

1. 將所有有限合夥人可以以同樣的方式編碼？是的，可以編寫一個通用的LP解算器來加載和解決任何LP。 （有行業標準格式讀取LP的喜歡mps和.lp

2. 會蠻力工作？請記住，許多公司和大機構花了很長時間在微調的求解器。有LP的有有趣性質，許多求解器將嘗試利用。此外，某些計算可以並行求解。該算法是指數的，因此在一些大量的變量/約束，蠻力將無法正常工作。

。希望幫助。

Answer 2

這個是我寫的matlab昨天，這可以很容易地轉錄成C++，如果您使用本徵庫或使用STD的一個std ::矢量:: vector的

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