R-Tek Scratchpad Version 1.00 TSPadDatad TPictured TCommentTextd TLogFontd Times New Roman densed BT Linear Programming nnnnnnnnnnnnnnnnnn] TCommentTextd Sometimes there are multiple solutions to a linear programming problem.G nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TCommentsd TCommentTextd objective function nnnnnnnnnnnnnnnnnn] TCommentTextd maximize: nnnnnnnnn] TExpressiond z:2*x[1]+x[2]-2*x[3]-2*x[4] TCommentTextd constraints nnnnnnnnnnn] TCommentTextd subject to: nnnnnnnnnnn] TExpressiond 2*x[1]+x[2]-2*x[4] TExpressiond x[2]+2*x[3]+4*x[4] TExpressiond x[1]-2*x[2]+x[4] TCommentTextd non-negativity constraints (often not explicitly stated)8 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TExpressiond TExpressiond TExpressiond TExpressiond TEndCommentsd TCommentTextd The scratchpad requires that you translate the above problem into a form it understands.X nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TExpressiond c:M000100072@1@-2@-2@0@0@0@ TCommentTextd coefficients of the objective function, last three are for slacks (optional)L nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TExpressiond A:M000300042@1@0@-2@0@1@2@4@1@-2@0@1@% TCommentTextd coefficients of the constraints nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TExpressiond r:M000300011@1@-1@ TCommentTextd relations of the inequality constraints. 1 for less than or equal 0 for equal -1 for greater than or equalj nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnn] TCommentTextd You should note that each r element is the same as the initial slack variable coefficient (for positive b)k nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnn] TExpressiond b:M0003000150@50@20@ TCommentTextd constants of the constraints nnnnnnnnnnnnnnnnnnnnnnnnnnnn] TCommentTextd This completes the translation of the problem into the necessary form. Next, set up the variables that will contain the solution. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TExpressiond x:zmat(1,1) TCommentTextd it is only important that tableau and x are matrices, since their size will be adjusted as necessarye nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TExpressiond tableau:x THardPageBreakd TExpressiond lpmax(c,A,r,b,x,tableau) TCommentTextd objective function maximum nnnnnnnnnnnnnnnnnnnnnnnnnn] TCommentTextd lpmax solves the linear programming maximization problem. You can see that the first four parameters define the problem and the last two return information about the solution z. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TExpressiond TExpressiond tableau TCommentTextd Examine the final row of the tableau, which is the simplex criteria row. The fact that there are no negatives indicates we are at an optimal solution for a maximization problem. x1, x2, and the second slack variable (x6) are in the solution so we expect to see zeros in these columns. column 3 indicates that if we increase the coefficient of x3 in the objective function by more than 2, we would force x3 into the solution vector. Of more interest are the zeros in columns 4 and 7, not currently in the solution. These indicates that any tiny increase, no matter how small, in the coefficient of x4 or x7 in the objective function will force x4 or x7 into the solution vector. This tells us that there are other solution vectors for this problem, indeed infinitely many solution vectors that are linear combinations of the one we know about and the ones we now know must exist. Let's show this by first finding the other solution vectors. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnzznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnzz] TExpressiond x_new:zmat(1,1) TCommentTextd the new solution will be returned in this vector0 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TExpressiond tableau_new:x_new TExpressiond c_new:c TExpressiond c_new[4]:c[4]+1/1000000 TCommentTextd or any other small increment nnnnnnnnnnnnnnnnnnnnnnnnnnnn] TExpressiond z:lpmax(c_new,A,r,b,x_new,tableau_new)& TExpressiond x_new TExpressiond tableau_new THardPageBreakd TCommentTextd See how x4 was forced into the solution vector, while the objective function and its optimimun value were hardly effected.z nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TCommentTextd This problem has a couple more solution vectors (see if you can find them using the perturbation technique, ie add or subtract a small amount from the coefficents with zeros in the simplex criteria row of tableau and keep track of new solutions) nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TCommentTextd The general solution then can be any linear combination of the solution vectors, as in:W nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnn] TExpressiond f1:1/4 TExpressiond f2:1/4 TExpressiond f3:1/4 TExpressiond f4:1/4 TCommentTextd You can make these fractions whatever you want so long as they total one.I nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TExpressiond solution1:M0004000124@2@0@0@ TExpressiond solution2:M0004000175/2@0@0@25/2@! TExpressiond solution3:M0004000130@10@0@10@ TExpressiond solution4:M0004000125@0@0@0@ TExpressiond x_linear_combination:f1*solution1+f2*solution2+f3*solution3+f4*solution4H TExpressiond c:submat(c,1,1,1,4) TCommentTextd chop off slack coefficients if used (only nonzero for perturbation technique anyway)U nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TExpressiond z_linear_combination:c*x_linear_combination+ TCommentTextd As an alternate method of calculating the other optimum solution vectors, let's begin by using the final tableau and our knowledge of the simplex method to introduce x4 into the simplex tableau. We examine each row and calculate the ratio of the final columm element to the 4th column element. We then choose the row with the minimum such positive ratio and perform a Gauss-Jordan elimination based on that rows 4th column element. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TCommentTextd Let's recall the tableau corresponding to solution1 for easy reference:G nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TCommentTextd ignore row 1 since 4th element is negative* nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TCommentTextd start with nnnnnnnnnn] TExpressiond 48/((24/5)) TExpressiond tableau TExpressiond solution1 TCommentTextd ignore row 3 since 4th element is negative* nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] THardPageBreakd TCommentTextd We see that the second row has the minimum positive ratio, so we now pivot on the 2, 4 th element of the tableau to introduce x4 into the solution (eliminating the second slack variable from the solution in the process.) nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TExpressiond 10/((1/3)) TCommentTextd new solution nnnnnnnnnnnn] TCommentTextd ignore row 2 since 7th element is negative, nnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnn] TExpressiond solution3 TExpressiond pivot(tableau,2,4) TCommentTextd ignore row 3 since 7th element is negative, nnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnn] TCommentTextd We see that the first row has the minimum positive ratio, so we now pivot on the 1, 7 th element of the tableau to introduce x7 into the solution (eliminating x2 from the solution in the process.) nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnn] TCommentTextd new solution nnnnnnnnnnnn] TExpressiond solution4 TExpressiond tableau:pivot(tableau,1,7) TCommentTextd solution2 is not reachable in a single pivot from the tableau corresponding to solution1, but is reachable with one additional pivot from the tableau immediately above. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] TCommentTextd new solution nnnnnnnnnnnn] TExpressiond pivot(tableau,2,4) TExpressiond solution2 TCommentTextd Inspection of this tableau shows us that we have now obtained the same solution vectors by pivoting that we calculated above by the perturbation method. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnznnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn]][ TPrinterDimensionsd TSPadInitDatad TLogFontd Times New Roman densed BT TLogFontd Arial TLogFontd Arial TLogFontd Symbol TLogFontd Symbol TNumberFormatDatad TGraphSetupDatad TPageSetupDatad R-Tek Scratchpad Example File LP_MULTI