% We want to study the simplex tableau for the example given in the book % where the basic variables are x11, x14, x22, x24, x32, and x33. % (See page 299, tableau 5.2) % I first create a matrix that has the information held in the equations % (5) on page 298 > A = zeros(7,12); > for j=1:4, A(1,j) = 1; end > for j=1:4, A(2,4+j) = 1; end > for j=1:4, A(3,8+j) = 1; end > for j=1:3, A(4,1+(j-1)*4) = 1; end > for j=1:3, A(5,2+(j-1)*4) = 1; end > for j=1:3, A(6,3+(j-1)*4) = 1; end > for j=1:3, A(7,4+(j-1)*4) = 1; end % I saved a copy of A (in case I mess up). Also I made sure that A looks right % by typing the command w/o a semicolon at the end... this allows matlab % to display > B = A % I now put the objective row into A: > A(7,:) = [5,7,9,6,6,7,10,5,7,6,8,1]; > A(7,:) = -A(7,:); % I looked at A by typing "A" > A % I see that it's not in the simplex % tableau form. That is columns that look right when the correspond % to the basic variables. % I figured out what would have to happen to A to make the first column % look right. I then did that to A: % make x11 a basic variable > A(4,:) = A(4,:)-A(1,:); > A(7,:) = A(7,:)+5*A(1,:); % I now inspected A by typing "A". > A %It still doesn't look right. % I figured out what would have to happen to A to make the sixth column % look right. I then did that to A: % make x22 a basic variable > A(5,:) = A(5,:)-A(2,:); > A(7,:) = A(7,:)+7*A(2,:); % I now inspected A by typing "A". > A % It still doesn't look right. % I figured out what would have to happen to A to make the tenth column % look right. I then did that to A: % make x32 a basic variable > A(5,:) = A(5,:)-A(3,:); > A(7,:) = A(7,:)+6*A(3,:); % I now inspected A by typing "A". > A % It still doesn't look right. % I figured out what would have to happen to A to make the fourth column % look right. I then did that to A: % make x14 a basic variable > A(1,:) = A(1,:) + A(4,:); > A(7,:) = A(7,:) - A(4,:); > A(4,:) = -A(4,:); % I now inspect A by typing "A". > A % It still doesn't look right. % I figured out what would have to happen to A to make the eleventh column % look right. I then did that to A: % make x33 a basic variable > A(3,:) = A(3,:) + A(5,:); > A(6,:) = A(6,:) + A(5,:); > A(7,:) = A(7,:) - 2*A(5,:); > A(5,:) = -A(5,:); % I now inspect A by typing "A". > A % It still doesn't look right. % I figured out what would have to happen to A to make the eighth column % look right. I then did that to A: % make x24 a basic variable > A(2,:) = A(2,:) + A(6,:); > A(3,:) = A(3,:) - A(6,:); > A(5,:) = A(5,:) + A(6,:); > A(7,:) = A(7,:) + 4*A(6,:); > A(6,:) = -A(6,:); % I now inspect A by typing "A". > A % It now looks right except that I have to give the values of the basic variables. % the value of x11 > A(1,13) = 100; % the value of x22 > A(2,13) = 40; % the value of x32 > A(3,13) = 20; % the value of x14 > A(4,13) = 20; % the value of x33 > A(5,13) = 80; % the value of x24 > A(6,13) = 100; % I also have to put the current cost into the bottom right corner: % % the current cost: > c = [5,7,9,6,6,7,10,5,7,6,8,1]; > x = [100,0,0,20,0,40,0,100,0,20,80,0]; > A(7,13) = x*c'; % the objective row is now consistent with the information given on % pages 302 and 303 about the various loops that are possible and their % costs. > A A = 1 0 0 0 1 0 0 0 1 0 0 0 100 0 1 1 0 0 1 1 0 -1 0 0 -1 40 0 0 -1 0 0 0 -1 0 1 1 0 1 20 0 1 1 1 -1 0 0 0 -1 0 0 0 20 0 0 1 0 0 0 1 0 0 0 1 0 80 0 -1 -1 0 1 0 0 1 1 0 0 1 100 0 1 1 0 -2 0 -1 0 -4 0 0 3 2160 % I am ready to start the simplex method. I use the routine "LP_setup_transport" % which requires that I declare the basic variables. It also needs the input % of the number of suppliers and warehouses > [A,bv]=LP_setup_transport(A,3,4); what is your basic variable? x11 what is your basic variable? x22 what is your basic variable? x32 what is your basic variable? x14 what is your basic variable? x33 what is your basic variable? x24 bv x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34 x11 1 0 0 0 1 0 0 0 1 0 0 0 100 x22 0 1 1 0 0 1 1 0 -1 0 0 -1 40 x32 0 0 -1 0 0 0 -1 0 1 1 0 1 20 x14 0 1 1 1 -1 0 0 0 -1 0 0 0 20 x33 0 0 1 0 0 0 1 0 0 0 1 0 80 x24 0 -1 -1 0 1 0 0 1 1 0 0 1 100 obj 0 1 1 0 -2 0 -1 0 -4 0 0 3 2160 % I'm now ready to pivot. Possible incoming variables are x12, x13, and x34 since % these all have loops that will save money. I choose x34 as incoming. I then % have to choose an outgoing variable. x32 has the smallest theta-ratio > [A,bv] = pivot_transport(A,bv,3,4); what is the incoming variable? x34 what is the outgoing variable? x32 bv x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34 x11 1 0 0 0 1 0 0 0 1 0 0 0 100 x22 0 1 0 0 0 1 0 0 0 1 0 0 60 x34 0 0 -1 0 0 0 -1 0 1 1 0 1 20 x14 0 1 1 1 -1 0 0 0 -1 0 0 0 20 x33 0 0 1 0 0 0 1 0 0 0 1 0 80 x24 0 -1 0 0 1 0 1 1 0 -1 0 0 80 obj 0 1 4 0 -2 0 2 0 -7 -3 0 0 2100 % Note that the cost has decreased by 3*20, as expected! % I'm now ready to pivot again. Possible incoming variables are x12, x13, and x23 since % these all have loops that will save money. I choose x23 as incoming. I then % have to choose an outgoing variable. x24 has the smallest theta-ratio. (I can % choose any incoming variable as long as it will save me $$ --- this will lead me % to a lower-cost basic feasible solution and eventually the simplex method will % terminate. It might terminate faster if I choose x13 as incoming though... > [A,bv] = pivot_transport(A,bv,3,4); what is the incoming variable? x23 what is the outgoing variable? x24 bv x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34 x11 1 0 0 0 1 0 0 0 1 0 0 0 100 x22 0 1 0 0 0 1 0 0 0 1 0 0 60 x34 0 -1 -1 0 1 0 0 1 1 0 0 1 100 x14 0 1 1 1 -1 0 0 0 -1 0 0 0 20 x33 0 1 1 0 -1 0 0 -1 0 1 1 0 0 x23 0 -1 0 0 1 0 1 1 0 -1 0 0 80 obj 0 3 4 0 -4 0 0 -2 -7 -1 0 0 1940 % I'm now ready to pivot again. Possible incoming variables are x12 and x13 since % these both have loops that will save money. I choose x13 as incoming. I then % have to choose an outgoing variable. x33 has the smallest theta-ratio. (I can % choose any incoming variable as long as it will save me $$ --- this will lead me % to a lower-cost basic feasible solution and eventually the simplex method will % terminate. It might terminate faster if I choose x13 as incoming though... > [A,bv] = pivot_transport(A,bv,3,4); what is the incoming variable? x13 what is the outgoing variable? x33 bv x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34 x11 1 0 0 0 1 0 0 0 1 0 0 0 100 x22 0 1 0 0 0 1 0 0 0 1 0 0 60 x34 0 0 0 0 0 0 0 0 1 1 1 1 100 x14 0 0 0 1 0 0 0 1 -1 -1 -1 0 20 x13 0 1 1 0 -1 0 0 -1 0 1 1 0 0 x23 0 -1 0 0 1 0 1 1 0 -1 0 0 80 obj 0 -1 0 0 0 0 0 2 -7 -5 -4 0 1940 % I'm now ready to pivot again. The only possible incoming variables is x24 since % it has a loop that will save money. I then % have to choose an outgoing variable. x14 has the smallest theta-ratio. (I can % choose any incoming variable as long as it will save me $$ --- this will lead me % to a lower-cost basic feasible solution and eventually the simplex method will % terminate. It might terminate faster if I choose x13 as incoming though... > [A,bv] = pivot_transport(A,bv,3,4); what is the incoming variable? x24 what is the outgoing variable? x14 bv x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34 x11 1 0 0 0 1 0 0 0 1 0 0 0 100 x22 0 1 0 0 0 1 0 0 0 1 0 0 60 x34 0 0 0 0 0 0 0 0 1 1 1 1 100 x24 0 0 0 1 0 0 0 1 -1 -1 -1 0 20 x13 0 1 1 1 -1 0 0 0 -1 0 0 0 20 x23 0 -1 0 -1 1 0 1 0 1 0 1 0 60 obj 0 -1 0 -2 0 0 0 0 -5 -3 -2 0 1900 % The objective row has no positive entries --- I've found an optimal solution!