Kodowanie ręcznego programowania liniowego ręcznie

Question

Robiłem problemy programowania liniowego w mojej klasie przez ich graficzne, ale chciałbym wiedzieć, jak napisać program dla konkretnego problemu, aby rozwiązać go dla mnie. Jeśli istnieje zbyt wiele zmiennych lub ograniczeń, nigdy nie mógłbym tego zrobić za pomocą wykresów.

Przykład problem maksymalnego 5x + 3y z ograniczeniami:

• 5x - 2y> = 0
• x + y < = 7
• x < = 5
• x> = 0
• y> = 0

Wykreśliłem to i otrzymałem widoczny r egion z 3 rogami. x = 5 y = 2 to optymalny punkt.

Jak zmienić to w kod? Znam metodę simplex. I bardzo ważne, czy wszystkie problemy z LP będą kodowane w tej samej strukturze? Czy brutalna siła zadziała?

Answer 1

Istnieje wiele implementacji Simplex, które można znaleźć, jeśli przeszukujesz.

Oprócz jednego wymienionego w komentarzu (Numerical Recipes in C), można również znaleźć:

1. Google's own Simplex-Solver
2. Potem jest COIN-OR
3. GNU posiada własną GLPK
4. Jeśli chcesz implementację C++, ta w Google Code jest rzeczywiście dostępna.
5. Istnieje wiele wdrożeń w R, w tym boot package. (W R można zobaczyć realizację funkcji wpisując go bez nawiasów.)

Aby rozwiązać swoje dwa inne pytania:

1. Czy wszystkie LP być zakodowane w ten sam sposób? Tak, generalny solver LP można zapisać, aby załadować i rozwiązać dowolny LP. (Istnieją formaty standardowe przemysłowe do czytania LP jak mps i .lp

2. Czy brute pracę siły? Należy pamiętać, że wiele firm i dużych organizacji spędzają długi czas na dostrojeniu się rozwiązują. Istnieje LP, które mają ciekawy właściwości, które rozwiązują wiele będzie próbował wykorzystać. również niektóre obliczenia mogą być rozwiązywane równolegle. algorytm jest wykładniczy, więc w pewnym dużej liczby zmiennych/ograniczeń, brute force nie będzie działać.

nadzieja, że pomaga.

Answer 2

pisałem to wczoraj Matlab, które mogą być łatwo przepisywane do C++, jeśli używasz biblioteki EIGEN lub wyraź swoją klasę matrycy za pomocą std :: wektor 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