Geek Answers Handbook

Copy Linear Programming Exercise Manually

I deal with the problems of linear programming in my class, creating their graphics, but I would like to know how to write a program for a specific problem in order to solve it for me. If there are too many variables or constraints, I can never do this with a graph.

Example problem, maximize 5x + 3y with limitations:

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

I drew this and got a visible area with three angles. x = 5 y = 2 is the optimal point.

How to turn this into code? I know about the simplex method. And what is very important, will all LP problems be encoded in one structure? Will brute force work?

+6
source share
2 answers

There are many Simplex solutions you will find when searching.

In addition to the one mentioned in the commentary (Numerical recipes in C) you can also find:

To address two other issues:

  • Will all LP encodings be the same? Yes, a common LP solver can be written to download and resolve any LP. (There are industry standard formats for reading LPs such as mps and .lp

  • Does brute force work? Keep in mind that many companies and large organizations spend a lot of time fine-tuning solvers. There are LPs that have interesting properties that many solvers will try to use. In addition, some calculations can be solved in parallel. The algorithm is exponential, therefore, with some large number of variables / constraints, brute force will not work.

Hope this helps.

+5
source

I wrote that it was Matlab yesterday, which could be easily rewritten in C ++ if you use the Eigen library or write your own matrix class using std :: vector 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
0
source

More articles:


All Articles