Linear Programming Problem -- a walk through

Reading the data file: lp_demo_08.txt
      Number of variables set to 3
line 1: 14 2 13 le 153 --->   Inequality is:   14 x1  + 2 x2  + 13 x3  ≤  153
line 2: -2 1 1 le 1 --->   Inequality is:   -2 x1  + 1 x2  + 1 x3  ≤  1
line 3: 1 -23 10 le 10 --->   Inequality is:   1 x1  + -23 x2  + 10 x3  ≤  10
line 4: 34 3 -26 le 340 --->   Inequality is:   34 x1  + 3 x2  + -26 x3  ≤  340
line 5: -39 4 24 le 24 --->   Inequality is:   -39 x1  + 4 x2  + 24 x3  ≤  24
line 6: -23 37 29 le 222 --->   Inequality is:   -23 x1  + 37 x2  + 29 x3  ≤  222
line 7: -7 2 15 le 12 --->   Inequality is:   -7 x1  + 2 x2  + 15 x3  ≤  12
line 8: maximize -4 7 11 --->       set Maximize:   -4 x1  + 7 x2  + 11 x3
Create the Initial Tableau After reconfiguring the objective function and converting any '≥' constraints to a '≤' form, we can produce the following tableau:
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   14   2   13   1   0   0   0   0   0   0   0   153 
 s2   -2   1   1   0   1   0   0   0   0   0   0   1 
 s3   1   -23   10   0   0   1   0   0   0   0   0   10 
 s4   34   3   -26   0   0   0   1   0   0   0   0   340 
 s5   -39   4   24   0   0   0   0   1   0   0   0   24 
 s6   -23   37   29   0   0   0   0   0   1   0   0   222 
 s7   -7   2   15   0   0   0   0   0   0   1   0   12 
   4   -7   -11   0   0   0   0   0   0   0   1   0 
Processing
There is at least one negative value in the last row (excluding the final column). Therefore we need to start the regular simplex processing algorithm.

The lowest negative value in the last row is -11 and that is in column 3. So make column 3 the work column.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   14   2   13   1   0   0   0   0   0   0   0   153 
 s2   -2   1   1   0   1   0   0   0   0   0   0   1 
 s3   1   -23   10   0   0   1   0   0   0   0   0   10 
 s4   34   3   -26   0   0   0   1   0   0   0   0   340 
 s5   -39   4   24   0   0   0   0   1   0   0   0   24 
 s6   -23   37   29   0   0   0   0   0   1   0   0   222 
 s7   -7   2   15   0   0   0   0   0   0   1   0   12 
   4   -7   -11   0   0   0   0   0   0   0   1   0 
The lowest ratio between positive values in column 3 and corresponding values in the the final column is 0.8 and that is in row 7. So make row 7 the work row. That makes the item in row 7 and column 3 the pivot item.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   14   2   13   1   0   0   0   0   0   0   0   153 
 s2   -2   1   1   0   1   0   0   0   0   0   0   1 
 s3   1   -23   10   0   0   1   0   0   0   0   0   10 
 s4   34   3   -26   0   0   0   1   0   0   0   0   340 
 s5   -39   4   24   0   0   0   0   1   0   0   0   24 
 s6   -23   37   29   0   0   0   0   0   1   0   0   222 
 s7   -7   2   15   0   0   0   0   0   0   1   0   12 
   4   -7   -11   0   0   0   0   0   0   0   1   0 
Use the elementary row operation *row to change the pivot item to be 1. That is, multiply row 7 by 1 / 15.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   14   2   13   1   0   0   0   0   0   0   0   153 
 s2   -2   1   1   0   1   0   0   0   0   0   0   1 
 s3   1   -23   10   0   0   1   0   0   0   0   0   10 
 s4   34   3   -26   0   0   0   1   0   0   0   0   340 
 s5   -39   4   24   0   0   0   0   1   0   0   0   24 
 s6   -23   37   29   0   0   0   0   0   1   0   0   222 
 s7   -7/15   2/15   1   0   0   0   0   0   0   1/15   0   4/5 
   4   -7   -11   0   0   0   0   0   0   0   1   0 
Now use the elementary row operation *row+ to change the other items in column 3 to 0.
  1. multiply row 7 by -13 and add to row 1.
  2. multiply row 7 by -1 and add to row 2.
  3. multiply row 7 by -10 and add to row 3.
  4. multiply row 7 by 26 and add to row 4.
  5. multiply row 7 by -24 and add to row 5.
  6. multiply row 7 by -29 and add to row 6.
  7. multiply row 7 by 11 and add to row 8.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   301/15   4/15   0   1   0   0   0   0   0   -13/15   0   713/5 
 s2   -23/15   13/15   0   0   1   0   0   0   0   -1/15   0   1/5 
 s3   17/3   -73/3   0   0   0   1   0   0   0   -2/3   0   2 
 s4   328/15   97/15   0   0   0   0   1   0   0   26/15   0   1804/5 
 s5   -139/5   4/5   0   0   0   0   0   1   0   -8/5   0   24/5 
 s6   -142/15   497/15   0   0   0   0   0   0   1   -29/15   0   994/5 
 s7   -7/15   2/15   1   0   0   0   0   0   0   1/15   0   4/5 
   -17/15   -83/15   0   0   0   0   0   0   0   11/15   1   44/5 
Now we need to copy the heading for the work column (column 3) to the heading for the work row (row 7).
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   301/15   4/15   0   1   0   0   0   0   0   -13/15   0   713/5 
 s2   -23/15   13/15   0   0   1   0   0   0   0   -1/15   0   1/5 
 s3   17/3   -73/3   0   0   0   1   0   0   0   -2/3   0   2 
 s4   328/15   97/15   0   0   0   0   1   0   0   26/15   0   1804/5 
 s5   -139/5   4/5   0   0   0   0   0   1   0   -8/5   0   24/5 
 s6   -142/15   497/15   0   0   0   0   0   0   1   -29/15   0   994/5 
 x3   -7/15   2/15   1   0   0   0   0   0   0   1/15   0   4/5 
   -17/15   -83/15   0   0   0   0   0   0   0   11/15   1   44/5 
Having finished the steps of the processing routine, we need to see if there are any remaining negative values in the final column. If so, then we restart the processing steps.

The lowest negative value in the last row is -83 / 15  = -5.53333333333333 and that is in column 2. So make column 2 the work column.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   301/15   4/15   0   1   0   0   0   0   0   -13/15   0   713/5 
 s2   -23/15   13/15   0   0   1   0   0   0   0   -1/15   0   1/5 
 s3   17/3   -73/3   0   0   0   1   0   0   0   -2/3   0   2 
 s4   328/15   97/15   0   0   0   0   1   0   0   26/15   0   1804/5 
 s5   -139/5   4/5   0   0   0   0   0   1   0   -8/5   0   24/5 
 s6   -142/15   497/15   0   0   0   0   0   0   1   -29/15   0   994/5 
 x3   -7/15   2/15   1   0   0   0   0   0   0   1/15   0   4/5 
   -17/15   -83/15   0   0   0   0   0   0   0   11/15   1   44/5 
The lowest ratio between positive values in column 2 and corresponding values in the the final column is 0.230769230769231 and that is in row 2. So make row 2 the work row. That makes the item in row 2 and column 2 the pivot item.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   301/15   4/15   0   1   0   0   0   0   0   -13/15   0   713/5 
 s2   -23/15   13/15   0   0   1   0   0   0   0   -1/15   0   1/5 
 s3   17/3   -73/3   0   0   0   1   0   0   0   -2/3   0   2 
 s4   328/15   97/15   0   0   0   0   1   0   0   26/15   0   1804/5 
 s5   -139/5   4/5   0   0   0   0   0   1   0   -8/5   0   24/5 
 s6   -142/15   497/15   0   0   0   0   0   0   1   -29/15   0   994/5 
 x3   -7/15   2/15   1   0   0   0   0   0   0   1/15   0   4/5 
   -17/15   -83/15   0   0   0   0   0   0   0   11/15   1   44/5 
Use the elementary row operation *row to change the pivot item to be 1. That is, multiply row 2 by 15 / 13.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   301/15   4/15   0   1   0   0   0   0   0   -13/15   0   713/5 
 s2   -23/13   1   0   0   15/13   0   0   0   0   -1/13   0   3/13 
 s3   17/3   -73/3   0   0   0   1   0   0   0   -2/3   0   2 
 s4   328/15   97/15   0   0   0   0   1   0   0   26/15   0   1804/5 
 s5   -139/5   4/5   0   0   0   0   0   1   0   -8/5   0   24/5 
 s6   -142/15   497/15   0   0   0   0   0   0   1   -29/15   0   994/5 
 x3   -7/15   2/15   1   0   0   0   0   0   0   1/15   0   4/5 
   -17/15   -83/15   0   0   0   0   0   0   0   11/15   1   44/5 
Now use the elementary row operation *row+ to change the other items in column 2 to 0.
  1. multiply row 2 by -4 / 15 and add to row 1.
  2. multiply row 2 by 73 / 3 and add to row 3.
  3. multiply row 2 by -97 / 15 and add to row 4.
  4. multiply row 2 by -4 / 5 and add to row 5.
  5. multiply row 2 by -497 / 15 and add to row 6.
  6. multiply row 2 by -2 / 15 and add to row 7.
  7. multiply row 2 by 83 / 15 and add to row 8.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   267/13   0   0   1   -4/13   0   0   0   0   -11/13   0   1853/13 
 s2   -23/13   1   0   0   15/13   0   0   0   0   -1/13   0   3/13 
 s3   -486/13   0   0   0   365/13   1   0   0   0   -33/13   0   99/13 
 s4   433/13   0   0   0   -97/13   0   1   0   0   29/13   0   4671/13 
 s5   -343/13   0   0   0   -12/13   0   0   1   0   -20/13   0   60/13 
 s6   639/13   0   0   0   -497/13   0   0   0   1   8/13   0   2485/13 
 x3   -3/13   0   1   0   -2/13   0   0   0   0   1/13   0   10/13 
   -142/13   0   0   0   83/13   0   0   0   0   4/13   1   131/13 
Now we need to copy the heading for the work column (column 2) to the heading for the work row (row 2).
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   267/13   0   0   1   -4/13   0   0   0   0   -11/13   0   1853/13 
 x2   -23/13   1   0   0   15/13   0   0   0   0   -1/13   0   3/13 
 s3   -486/13   0   0   0   365/13   1   0   0   0   -33/13   0   99/13 
 s4   433/13   0   0   0   -97/13   0   1   0   0   29/13   0   4671/13 
 s5   -343/13   0   0   0   -12/13   0   0   1   0   -20/13   0   60/13 
 s6   639/13   0   0   0   -497/13   0   0   0   1   8/13   0   2485/13 
 x3   -3/13   0   1   0   -2/13   0   0   0   0   1/13   0   10/13 
   -142/13   0   0   0   83/13   0   0   0   0   4/13   1   131/13 
Having finished the steps of the processing routine, we need to see if there are any remaining negative values in the final column. If so, then we restart the processing steps.

The lowest negative value in the last row is -142 / 13  = -10.9230769230769 and that is in column 1. So make column 1 the work column.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   267/13   0   0   1   -4/13   0   0   0   0   -11/13   0   1853/13 
 x2   -23/13   1   0   0   15/13   0   0   0   0   -1/13   0   3/13 
 s3   -486/13   0   0   0   365/13   1   0   0   0   -33/13   0   99/13 
 s4   433/13   0   0   0   -97/13   0   1   0   0   29/13   0   4671/13 
 s5   -343/13   0   0   0   -12/13   0   0   1   0   -20/13   0   60/13 
 s6   639/13   0   0   0   -497/13   0   0   0   1   8/13   0   2485/13 
 x3   -3/13   0   1   0   -2/13   0   0   0   0   1/13   0   10/13 
   -142/13   0   0   0   83/13   0   0   0   0   4/13   1   131/13 
The lowest ratio between positive values in column 1 and corresponding values in the the final column is 3.88888888888889 and that is in row 6. So make row 6 the work row. That makes the item in row 6 and column 1 the pivot item.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   267/13   0   0   1   -4/13   0   0   0   0   -11/13   0   1853/13 
 x2   -23/13   1   0   0   15/13   0   0   0   0   -1/13   0   3/13 
 s3   -486/13   0   0   0   365/13   1   0   0   0   -33/13   0   99/13 
 s4   433/13   0   0   0   -97/13   0   1   0   0   29/13   0   4671/13 
 s5   -343/13   0   0   0   -12/13   0   0   1   0   -20/13   0   60/13 
 s6   639/13   0   0   0   -497/13   0   0   0   1   8/13   0   2485/13 
 x3   -3/13   0   1   0   -2/13   0   0   0   0   1/13   0   10/13 
   -142/13   0   0   0   83/13   0   0   0   0   4/13   1   131/13 
Use the elementary row operation *row to change the pivot item to be 1. That is, multiply row 6 by 13 / 639.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   267/13   0   0   1   -4/13   0   0   0   0   -11/13   0   1853/13 
 x2   -23/13   1   0   0   15/13   0   0   0   0   -1/13   0   3/13 
 s3   -486/13   0   0   0   365/13   1   0   0   0   -33/13   0   99/13 
 s4   433/13   0   0   0   -97/13   0   1   0   0   29/13   0   4671/13 
 s5   -343/13   0   0   0   -12/13   0   0   1   0   -20/13   0   60/13 
 s6   1   0   0   0   -7/9   0   0   0   13/639   8/639   0   35/9 
 x3   -3/13   0   1   0   -2/13   0   0   0   0   1/13   0   10/13 
   -142/13   0   0   0   83/13   0   0   0   0   4/13   1   131/13 
Now use the elementary row operation *row+ to change the other items in column 1 to 0.
  1. multiply row 6 by -267 / 13 and add to row 1.
  2. multiply row 6 by 23 / 13 and add to row 2.
  3. multiply row 6 by 486 / 13 and add to row 3.
  4. multiply row 6 by -433 / 13 and add to row 4.
  5. multiply row 6 by 343 / 13 and add to row 5.
  6. multiply row 6 by 3 / 13 and add to row 7.
  7. multiply row 6 by 142 / 13 and add to row 8.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   0   0   0   1   47/3   0   0   0   -89/213   -235/213   0   188/3 
 x2   0   1   0   0   -2/9   0   0   0   23/639   -35/639   0   64/9 
 s3   0   0   0   0   -1   1   0   0   54/71   -147/71   0   153 
 s4   0   0   0   0   166/9   0   1   0   -433/639   1159/639   0   2068/9 
 s5   0   0   0   0   -193/9   0   0   1   343/639   -772/639   0   965/9 
 s6   1   0   0   0   -7/9   0   0   0   13/639   8/639   0   35/9 
 x3   0   0   1   0   -1/3   0   0   0   1/213   17/213   0   5/3 
   0   0   0   0   -19/9   0   0   0   2/9   4/9   1   473/9 
Now we need to copy the heading for the work column (column 1) to the heading for the work row (row 6).
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   0   0   0   1   47/3   0   0   0   -89/213   -235/213   0   188/3 
 x2   0   1   0   0   -2/9   0   0   0   23/639   -35/639   0   64/9 
 s3   0   0   0   0   -1   1   0   0   54/71   -147/71   0   153 
 s4   0   0   0   0   166/9   0   1   0   -433/639   1159/639   0   2068/9 
 s5   0   0   0   0   -193/9   0   0   1   343/639   -772/639   0   965/9 
 x1   1   0   0   0   -7/9   0   0   0   13/639   8/639   0   35/9 
 x3   0   0   1   0   -1/3   0   0   0   1/213   17/213   0   5/3 
   0   0   0   0   -19/9   0   0   0   2/9   4/9   1   473/9 
Having finished the steps of the processing routine, we need to see if there are any remaining negative values in the final column. If so, then we restart the processing steps.

The lowest negative value in the last row is -19 / 9  = -2.11111111111111 and that is in column 5. So make column 5 the work column.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   0   0   0   1   47/3   0   0   0   -89/213   -235/213   0   188/3 
 x2   0   1   0   0   -2/9   0   0   0   23/639   -35/639   0   64/9 
 s3   0   0   0   0   -1   1   0   0   54/71   -147/71   0   153 
 s4   0   0   0   0   166/9   0   1   0   -433/639   1159/639   0   2068/9 
 s5   0   0   0   0   -193/9   0   0   1   343/639   -772/639   0   965/9 
 x1   1   0   0   0   -7/9   0   0   0   13/639   8/639   0   35/9 
 x3   0   0   1   0   -1/3   0   0   0   1/213   17/213   0   5/3 
   0   0   0   0   -19/9   0   0   0   2/9   4/9   1   473/9 
The lowest ratio between positive values in column 5 and corresponding values in the the final column is 4 and that is in row 1. So make row 1 the work row. That makes the item in row 1 and column 5 the pivot item.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   0   0   0   1   47/3   0   0   0   -89/213   -235/213   0   188/3 
 x2   0   1   0   0   -2/9   0   0   0   23/639   -35/639   0   64/9 
 s3   0   0   0   0   -1   1   0   0   54/71   -147/71   0   153 
 s4   0   0   0   0   166/9   0   1   0   -433/639   1159/639   0   2068/9 
 s5   0   0   0   0   -193/9   0   0   1   343/639   -772/639   0   965/9 
 x1   1   0   0   0   -7/9   0   0   0   13/639   8/639   0   35/9 
 x3   0   0   1   0   -1/3   0   0   0   1/213   17/213   0   5/3 
   0   0   0   0   -19/9   0   0   0   2/9   4/9   1   473/9 
Use the elementary row operation *row to change the pivot item to be 1. That is, multiply row 1 by 3 / 47.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   0   0   0   3/47   1   0   0   0   -89/3337   -5/71   0   4 
 x2   0   1   0   0   -2/9   0   0   0   23/639   -35/639   0   64/9 
 s3   0   0   0   0   -1   1   0   0   54/71   -147/71   0   153 
 s4   0   0   0   0   166/9   0   1   0   -433/639   1159/639   0   2068/9 
 s5   0   0   0   0   -193/9   0   0   1   343/639   -772/639   0   965/9 
 x1   1   0   0   0   -7/9   0   0   0   13/639   8/639   0   35/9 
 x3   0   0   1   0   -1/3   0   0   0   1/213   17/213   0   5/3 
   0   0   0   0   -19/9   0   0   0   2/9   4/9   1   473/9 
Now use the elementary row operation *row+ to change the other items in column 5 to 0.
  1. multiply row 1 by 2 / 9 and add to row 2.
  2. multiply row 1 by 1 and add to row 3.
  3. multiply row 1 by -166 / 9 and add to row 4.
  4. multiply row 1 by 193 / 9 and add to row 5.
  5. multiply row 1 by 7 / 9 and add to row 6.
  6. multiply row 1 by 1 / 3 and add to row 7.
  7. multiply row 1 by 19 / 9 and add to row 8.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   0   0   0   3/47   1   0   0   0   -89/3337   -5/71   0   4 
 x2   0   1   0   2/141   0   0   0   0   301/10011   -5/71   0   8 
 s3   0   0   0   3/47   0   1   0   0   2449/3337   -152/71   0   157 
 s4   0   0   0   -166/141   0   0   1   0   -1859/10011   221/71   0   156 
 s5   0   0   0   193/141   0   0   0   1   -352/10011   -193/71   0   193 
 x1   1   0   0   7/141   0   0   0   0   -4/10011   -3/71   0   7 
 x3   0   0   1   1/47   0   0   0   0   -14/3337   4/71   0   3 
   0   0   0   19/141   0   0   0   0   1661/10011   21/71   1   61 
Now we need to copy the heading for the work column (column 5) to the heading for the work row (row 1).
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s2   0   0   0   3/47   1   0   0   0   -89/3337   -5/71   0   4 
 x2   0   1   0   2/141   0   0   0   0   301/10011   -5/71   0   8 
 s3   0   0   0   3/47   0   1   0   0   2449/3337   -152/71   0   157 
 s4   0   0   0   -166/141   0   0   1   0   -1859/10011   221/71   0   156 
 s5   0   0   0   193/141   0   0   0   1   -352/10011   -193/71   0   193 
 x1   1   0   0   7/141   0   0   0   0   -4/10011   -3/71   0   7 
 x3   0   0   1   1/47   0   0   0   0   -14/3337   4/71   0   3 
   0   0   0   19/141   0   0   0   0   1661/10011   21/71   1   61 
Having finished the steps of the processing routine, we need to see if there are any remaining negative values in the final column. If so, then we restart the processing steps.
There are no more negative values is the final column. Therefore, regular processing is done...

Display the answers. Note that if a variable does not appear in the following list then it should be given the value 0. The list is generated from the final tableau by reading down the labels on the left and assigning to each the value in the rightmost column. Any slack variables in the labels on the left will be included in the list, but they can be ignored.
When

the objective function has a Maximum = 61

©Roger M. Palay     Saline, MI 48176     October, 2010