% this is the matlab diary from class on February 27, 2002. % start the diary: >> diary 2_27_02 % Consider the linear programming problem % % maximize - x1 + 7 x2 + x3 + 2 x4 % subject to % % x1 + x2 + x3 + x4 <= 1 % 1/2 x1 - 11/2 x2 - 5/2 x3 + 9 x4 <= 0 % 1/2 x1 - 3/2 x2 - 1/2 x3 + x4 <= 0 % % x1, x2, x3, x3 >= 0 % % I enter the matrix that I want to put into the simplex method: >> A = [1,1,1,1,1,0,0,1; .5,-11/2,-5/2,9,0,1,0,0;.5,-3/2,-1/2,1,0,0,1,0;1,-7,-1,-2,0,0,0,0] A = 1.0000 1.0000 1.0000 1.0000 1.0000 0 0 1.0000 0.5000 -5.5000 -2.5000 9.0000 0 1.0000 0 0 0.5000 -1.5000 -0.5000 1.0000 0 0 1.0000 0 1.0000 -7.0000 -1.0000 -2.0000 0 0 0 0 % I now use LP_setup to define my basic variables... >>[A,bv] = LP_setup(A); what is your basic variable? x5 what is your basic variable? x6 what is your basic variable? x7 x1 x2 x3 x4 x5 x6 x7 x5 1 1 1 1 1 0 0 1 x6 0.5 -5.5 -2.5 9 0 1 0 0 x7 0.5 -1.5 -0.5 1 0 0 1 0 obj 1 -7 -1 -2 0 0 0 0 % I now take one step of the simplex algorithm >> [A,bv] = pivot(A,bv); what is the incoming variable? x4 what is the outgoing variable? x7 x1 x2 x3 x4 x5 x6 x7 x5 0.5 2.5 1.5 0 1 0 -1 1 x6 -4 8 2 0 0 1 -9 0 x4 0.5 -1.5 -0.5 1 0 0 1 0 obj 2 -10 -2 0 0 0 2 0 % I now take one step of the simplex algorithm >> [A,bv] = pivot(A,bv); what is the incoming variable? x3 what is the outgoing variable? x6 x1 x2 x3 x4 x5 x6 x7 x5 3.5 -3.5 0 0 1 -0.75 5.75 1 x3 -2 4 1 0 0 0.5 -4.5 0 x4 -0.5 0.5 0 1 0 0.25 -1.25 0 obj -2 -2 0 0 0 1 -7 0 % I now take one step of the simplex algorithm >> [A,bv] = pivot(A,bv); what is the incoming variable? x2 what is the outgoing variable? x4 x1 x2 x3 x4 x5 x6 x7 x5 0 0 0 7 1 1 -3 1 x3 2 0 1 -8 0 -1.5 5.5 0 x2 -1 1 0 2 0 0.5 -2.5 0 obj -4 0 0 4 0 2 -12 0 % I now take one step of the simplex algorithm >> [A,bv] = pivot(A,bv); what is the incoming variable? x1 what is the outgoing variable? x3 x1 x2 x3 x4 x5 x6 x7 x5 0 0 0 7 1 1 -3 1 x1 1 0 0.5 -4 0 -0.75 2.75 0 x2 0 1 0.5 -2 0 -0.25 0.25 0 obj 0 0 2 -12 0 -1 -1 0 % I now take one step of the simplex algorithm >> [A,bv] = pivot(A,bv); what is the incoming variable? x7 what is the outgoing variable? x2 x1 x2 x3 x4 x5 x6 x7 x5 0 12 6 -17 1 -2 0 1 x1 1 -11 -5 18 0 2 0 0 x7 0 4 2 -8 0 -1 1 0 obj 0 4 4 -20 0 -2 0 0 % I now take one step of the simplex algorithm >> [A,bv] = pivot(A,bv); what is the incoming variable? x6 what is the outgoing variable? x1 x1 x2 x3 x4 x5 x6 x7 x5 1 1 1 1 1 0 0 1 x6 0.5 -5.5 -2.5 9 0 1 0 0 x7 0.5 -1.5 -0.5 1 0 0 1 0 obj 1 -7 -1 -2 0 0 0 0 % And you see that I've gone in a full circle. This would have been % avoided, had I used Bland's rule to choose the incoming and outgoing % variables whenever all choices of entering variables led to no increase % of the objective function. % % Let's try again... % % if x2 enters then x5 departs and the objective function increases by 7 % if x3 enters then x5 departs and the objective function increases by 1 % if x4 enters then either x6 or x7 departs and the objective function increases by 0 % % So, since there's a choice of entering variable that leads to an increase of the % objective function, I don't even need to use Bland's rule. I'll choose the entering % variable that leads to the largest increase: x2. >> [A,bv] = pivot(A,bv); what is the incoming variable? x2 what is the outgoing variable? x5 x1 x2 x3 x4 x5 x6 x7 x2 1 1 1 1 1 0 0 1 x6 6 0 3 14.5 5.5 1 0 5.5 x7 2 0 1 2.5 1.5 0 1 1.5 obj 8 0 6 5 7 0 0 7 % and it terminated! -------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------- % Now consider the new problem, involving artifical variables. % % maximize z = x1 + 2 x2 + 3 x3 + x4 % subject to % x1 + 3 x2 - x3 + x4 <= 5 % x1 + 7 x2 + x3 >= 4 % 4 x1 + 2 x2 + x4 <= 3 % % x1, x2, x3, x4 >= 0 % % adding slack variables, this becomes % % maximize z = x1 + 2 x2 + 3 x3 + x4 % subject to % x1 + 3 x2 - x3 + x4 + x5 = 5 % x1 + 7 x2 + x3 - x6 = 4 % 4 x1 + 2 x2 + x4 + x7 = 3 % % x1, x2, x3, x4, x5, x6, x7 >= 0 % % To start phase 1, we add an artificial variable, call it x8. This is added to the % second equation: % x1 + 7 x2 + x3 - x6 + x8 = 4 % % In phase 1, we then want to maximize z = -x8. However, the basic % variables are x5, x7, and x8 and we don't want the objective function % to involve the basic variables. From eqn 2, x1+7 x2+x3-x6-4 = -x8 and % so we're trying to maximize z = x1 + 7 x2 + x3 - x6 - 4. This makes % the objective row -x1 - 7 x2 - x3 + x6 + z = -4 % % In short, in phase 1, we're trying to solve: % % maximize z = x1 + 7 x2 + x3 - x6 - 4 % subject to % x1 + 3 x2 - x3 + x4 + x5 = 5 % x1 + 7 x2 + x3 - x6 + x8 = 4 % 4 x1 + 2 x2 + x4 + x7 = 3 % % x1, x2, x3, x4, x5, x6, x7, x8 >= 0 % % % I first define the matrix A: >> A = [1,3,-1,1,1,0,0,0,5; 1,7,1,0,0,-1,0,1,4; 4,2,0,1,0,0,1,0,3;-1,-7,-1,0,0,1,0,0,-4] A = 1 3 -1 1 1 0 0 0 5 1 7 1 0 0 -1 0 1 4 4 2 0 1 0 0 1 0 3 -1 -7 -1 0 0 1 0 0 -4 % I set up the linear programming problem: >> [A,bv] = LP_setup(A); what is your basic variable? x5 what is your basic variable? x8 what is your basic variable? x7 x1 x2 x3 x4 x5 x6 x7 x8 x5 1 3 -1 1 1 0 0 0 5 x8 1 7 1 0 0 -1 0 1 4 x7 4 2 0 1 0 0 1 0 3 obj -1 -7 -1 0 0 1 0 0 -4 % At this point, there are three possible choices of entering variables: % % if x1 enters then x7 will depart and the objective will increase by 3/4 % if x2 enters then x8 will depart and the objective will increase by 4 % if x3 enters then x8 will depart and the objective will increase by 4 % % both x2 and x3 will lead to the largest increases, so I'll choose one of them. If I choose % x2 to enter then I'll get into some nasty fractions involving 7 in the denominator, so I'll % choose to have x3 enter for this reason: >> [A,bv] = pivot(A,bv); what is the incoming variable? x3 what is the outgoing variable? x8 x1 x2 x3 x4 x5 x6 x7 x8 x5 2 10 0 1 1 -1 0 1 9 x3 1 7 1 0 0 -1 0 1 4 x7 4 2 0 1 0 0 1 0 3 obj 0 0 0 0 0 0 0 1 0 % It's terminated! % % Now we start phase 2. We want to maximize z = x1 + 2 x2 + 3 x3 + x4. We are maximizing it over % the same feasible set of solutions as before: A*x = b where A is the 3x8 matrix (the matrix % that includes the artificial variable x8. Notice that our initial basic feasible solution is % x1 = 0, x2 = 0, x3 = 4, x4 = 0, x5 = 9, x6 = 0, x7 = 3, x8 = 0. This particular solution also % satisfies the problem where the artificial variables have been taken out: Ax=b where A is 3x7. % (The two problems are identical as long as we keep x8 = 0 at every step of the simplex % method.) So we keep our set of constraints A x = b with A being 3x8 and all we want to % do is change the function that we're optimizing. % % The new objective function is z = x1 + 2 x2 + 3 x3 + x4. We need to express % it in terms of nonbasic variables. x1, x2, and x4 are nonbasic. x3 is basic. % so we use equation 2, to write x3 in terms of nonbasic variables: % % x3 = - x1 - 7 x2 + x6 - x8 + 4 % % Making the objective function % % z = - 2 x1 - 19 x2 + x4 + 3 x6 - 3 x8 + 12 % % So we change the row corresponding to the objective function: >> A(4,:) = [2,19,0,-1,0,-3,0,3,12]; % Let's look at the tableau... >> LP_disp x1 x2 x3 x4 x5 x6 x7 x8 x5 2 10 0 1 1 -1 0 1 9 x3 1 7 1 0 0 -1 0 1 4 x7 4 2 0 1 0 0 1 0 3 obj 2 19 0 -1 0 -3 0 3 12 % now we're ready to do the simplex algorithm. % % if x4 enters then x7 will depart and the objective function will increase by 3 % if x6 enters then there are no departing variables. We can take x6 as large as % we want and stay in the regime of feasible solutions. As x6 increases, the objective % function increases and so we conclude: % % there is no optimal solution because the objective function can be arbitrarily large % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Now we consider a problem where we know phase 1 will fail. % % maximize z = x1 + x2 % subject to % x1 + x2 >= 0 % - x2 >= 1 % x1 <= 2 % % x1,x2 >=0 % % This problem has no feasible solutions. % % First, we add slack variables x3, x4, and x5: % % maximize z = x1 + x2 % subject to % x1 + x2 - x3 = 0 % - x2 - x4 = 1 % x1 + x5 = 2 % % x1,x2,x3,x4,x5 >=0 % % Now we add artificial variables x6 and x7: and write the problem for % phase 1: % maximize z = - x6 - x7 % subject to % x1 + x2 - x3 + x6 = 0 % - x2 - x4 + x7 = 1 % x1 + x5 = 2 % % x1,x2,x3,x4,x5,x6,x7 >=0 % % the objective function z = - x6 - x7 should be in terms of nonbasic % variables only. We use eq 1 to write % % - x6 = x1 + x2 - x3 % - x7 = - x2 - x4 - 1 % % hence z = x1 - x3 - x4 - 1 % and the objective row equation becomes % -x1 + x3 + x4 + z = -1 >> A = [1 1 -1 0 0 1 0 0; 0 -1 0 -1 0 0 1 1; 1 0 0 0 1 0 0 2; -1 0 1 1 0 0 0 -1] A = 1 1 -1 0 0 1 0 0 0 -1 0 -1 0 0 1 1 1 0 0 0 1 0 0 2 -1 0 1 1 0 0 0 -1 % set up the linear programming problem: >> [A,bv] = LP_setup(A); what is your basic variable? x6 what is your basic variable? x7 what is your basic variable? x5 x1 x2 x3 x4 x5 x6 x7 x6 1 1 -1 0 0 1 0 0 x7 0 -1 0 -1 0 0 1 1 x5 1 0 0 0 1 0 0 2 obj -1 0 1 1 0 0 0 -1 % if x1 enters then x6 would depart and the objective function would increase by 0. % Since my only choice of entering variable leads to no increase of the objective % function, I must use Bland's rule. Which tells me to take x1 entering and x6 % departing. (Note: since there were not other choices of entering and departing % variables possible, Bland's rule was irrelevant in this particular instance.) >> [A,bv] = pivot(A,bv); what is the incoming variable? x1 what is the outgoing variable? x6 x1 x2 x3 x4 x5 x6 x7 x1 1 1 -1 0 0 1 0 0 x7 0 -1 0 -1 0 0 1 1 x5 0 -1 1 0 1 -1 0 2 obj 0 1 0 1 0 1 0 -1 % Phase 1 has terminated but x6 and x7 are not zero, as desired. This is because % there are no feasible solutions of % % maximize z = x1 + x2 % subject to % x1 + x2 >= 0 % - x2 >= 1 % x1 <= 2 % % x1,x2 >=0 % % hence there are no optimal solutions. % end the diary: >> diary off