Linear Programming Problem -- a walk through

Reading the data file: lp_demo1409f.txt
      Number of variables set to 3
line 1: 24 19 37 le 489 --->   Inequality is:   24 x1  + 19 x2  + 37 x3  ≤  489
line 2: 13 12 32 le 352 --->   Inequality is:   13 x1  + 12 x2  + 32 x3  ≤  352
line 3: 36 -5 22 le 432 --->   Inequality is:   36 x1  + -5 x2  + 22 x3  ≤  432
line 4: 12 27 1 le 297 --->   Inequality is:   12 x1  + 27 x2  + 1 x3  ≤  297
line 5: 11 -20 12 le 132 --->   Inequality is:   11 x1  + -20 x2  + 12 x3  ≤  132
line 6: -1 1 1 le 11 --->   Inequality is:   -1 x1  + 1 x2  + 1 x3  ≤  11
line 7: 33 36 -61 le 396 --->   Inequality is:   33 x1  + 36 x2  + -61 x3  ≤  396
line 8: maximize 22 20 40 --->       set Maximize:   22 x1  + 20 x2  + 40 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   24   19   37   1   0   0   0   0   0   0   0   489 
 s2   13   12   32   0   1   0   0   0   0   0   0   352 
 s3   36   -5   22   0   0   1   0   0   0   0   0   432 
 s4   12   27   1   0   0   0   1   0   0   0   0   297 
 s5   11   -20   12   0   0   0   0   1   0   0   0   132 
 s6   -1   1   1   0   0   0   0   0   1   0   0   11 
 s7   33   36   -61   0   0   0   0   0   0   1   0   396 
   -22   -20   -40   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 -40 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   24   19   37   1   0   0   0   0   0   0   0   489 
 s2   13   12   32   0   1   0   0   0   0   0   0   352 
 s3   36   -5   22   0   0   1   0   0   0   0   0   432 
 s4   12   27   1   0   0   0   1   0   0   0   0   297 
 s5   11   -20   12   0   0   0   0   1   0   0   0   132 
 s6   -1   1   1   0   0   0   0   0   1   0   0   11 
 s7   33   36   -61   0   0   0   0   0   0   1   0   396 
   -22   -20   -40   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 11 and that is in row 2. So make row 2 the work row. That makes the item in row 2 and column 3 the pivot item.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   24   19   37   1   0   0   0   0   0   0   0   489 
 s2   13   12   32   0   1   0   0   0   0   0   0   352 
 s3   36   -5   22   0   0   1   0   0   0   0   0   432 
 s4   12   27   1   0   0   0   1   0   0   0   0   297 
 s5   11   -20   12   0   0   0   0   1   0   0   0   132 
 s6   -1   1   1   0   0   0   0   0   1   0   0   11 
 s7   33   36   -61   0   0   0   0   0   0   1   0   396 
   -22   -20   -40   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 2 by 1 / 32.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   24   19   37   1   0   0   0   0   0   0   0   489 
 s2   13/32   3/8   1   0   1/32   0   0   0   0   0   0   11 
 s3   36   -5   22   0   0   1   0   0   0   0   0   432 
 s4   12   27   1   0   0   0   1   0   0   0   0   297 
 s5   11   -20   12   0   0   0   0   1   0   0   0   132 
 s6   -1   1   1   0   0   0   0   0   1   0   0   11 
 s7   33   36   -61   0   0   0   0   0   0   1   0   396 
   -22   -20   -40   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 2 by -37 and add to row 1.
  2. multiply row 2 by -22 and add to row 3.
  3. multiply row 2 by -1 and add to row 4.
  4. multiply row 2 by -12 and add to row 5.
  5. multiply row 2 by -1 and add to row 6.
  6. multiply row 2 by 61 and add to row 7.
  7. multiply row 2 by 40 and add to row 8.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   287/32   41/8   0   1   -37/32   0   0   0   0   0   0   82 
 s2   13/32   3/8   1   0   1/32   0   0   0   0   0   0   11 
 s3   433/16   -53/4   0   0   -11/16   1   0   0   0   0   0   190 
 s4   371/32   213/8   0   0   -1/32   0   1   0   0   0   0   286 
 s5   49/8   -49/2   0   0   -3/8   0   0   1   0   0   0   0 
 s6   -45/32   5/8   0   0   -1/32   0   0   0   1   0   0   0 
 s7   1849/32   471/8   0   0   61/32   0   0   0   0   1   0   1067 
   -23/4   -5   0   0   5/4   0   0   0   0   0   1   440 
Now we need to copy the heading for the work column (column 3) to the heading for the work row (row 2).
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   287/32   41/8   0   1   -37/32   0   0   0   0   0   0   82 
 x3   13/32   3/8   1   0   1/32   0   0   0   0   0   0   11 
 s3   433/16   -53/4   0   0   -11/16   1   0   0   0   0   0   190 
 s4   371/32   213/8   0   0   -1/32   0   1   0   0   0   0   286 
 s5   49/8   -49/2   0   0   -3/8   0   0   1   0   0   0   0 
 s6   -45/32   5/8   0   0   -1/32   0   0   0   1   0   0   0 
 s7   1849/32   471/8   0   0   61/32   0   0   0   0   1   0   1067 
   -23/4   -5   0   0   5/4   0   0   0   0   0   1   440 
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 -23 / 4  = -5.75 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   287/32   41/8   0   1   -37/32   0   0   0   0   0   0   82 
 x3   13/32   3/8   1   0   1/32   0   0   0   0   0   0   11 
 s3   433/16   -53/4   0   0   -11/16   1   0   0   0   0   0   190 
 s4   371/32   213/8   0   0   -1/32   0   1   0   0   0   0   286 
 s5   49/8   -49/2   0   0   -3/8   0   0   1   0   0   0   0 
 s6   -45/32   5/8   0   0   -1/32   0   0   0   1   0   0   0 
 s7   1849/32   471/8   0   0   61/32   0   0   0   0   1   0   1067 
   -23/4   -5   0   0   5/4   0   0   0   0   0   1   440 
The lowest ratio between positive values in column 1 and corresponding values in the the final column is 0 and that is in row 5. So make row 5 the work row. That makes the item in row 5 and column 1 the pivot item.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   287/32   41/8   0   1   -37/32   0   0   0   0   0   0   82 
 x3   13/32   3/8   1   0   1/32   0   0   0   0   0   0   11 
 s3   433/16   -53/4   0   0   -11/16   1   0   0   0   0   0   190 
 s4   371/32   213/8   0   0   -1/32   0   1   0   0   0   0   286 
 s5   49/8   -49/2   0   0   -3/8   0   0   1   0   0   0   0 
 s6   -45/32   5/8   0   0   -1/32   0   0   0   1   0   0   0 
 s7   1849/32   471/8   0   0   61/32   0   0   0   0   1   0   1067 
   -23/4   -5   0   0   5/4   0   0   0   0   0   1   440 
Use the elementary row operation *row to change the pivot item to be 1. That is, multiply row 5 by 8 / 49.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   287/32   41/8   0   1   -37/32   0   0   0   0   0   0   82 
 x3   13/32   3/8   1   0   1/32   0   0   0   0   0   0   11 
 s3   433/16   -53/4   0   0   -11/16   1   0   0   0   0   0   190 
 s4   371/32   213/8   0   0   -1/32   0   1   0   0   0   0   286 
 s5   1   -4   0   0   -3/49   0   0   8/49   0   0   0   0 
 s6   -45/32   5/8   0   0   -1/32   0   0   0   1   0   0   0 
 s7   1849/32   471/8   0   0   61/32   0   0   0   0   1   0   1067 
   -23/4   -5   0   0   5/4   0   0   0   0   0   1   440 
Now use the elementary row operation *row+ to change the other items in column 1 to 0.
  1. multiply row 5 by -287 / 32 and add to row 1.
  2. multiply row 5 by -13 / 32 and add to row 2.
  3. multiply row 5 by -433 / 16 and add to row 3.
  4. multiply row 5 by -371 / 32 and add to row 4.
  5. multiply row 5 by 45 / 32 and add to row 6.
  6. multiply row 5 by -1849 / 32 and add to row 7.
  7. multiply row 5 by 23 / 4 and add to row 8.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   0   41   0   1   -17/28   0   0   -41/28   0   0   0   82 
 x3   0   2   1   0   11/196   0   0   -13/196   0   0   0   11 
 s3   0   95   0   0   95/98   1   0   -433/98   0   0   0   190 
 s4   0   73   0   0   19/28   0   1   -53/28   0   0   0   286 
 s5   1   -4   0   0   -3/49   0   0   8/49   0   0   0   0 
 s6   0   -5   0   0   -23/196   0   0   45/196   1   0   0   0 
 s7   0   290   0   0   1067/196   0   0   -1849/196   0   1   0   1067 
   0   -28   0   0   44/49   0   0   46/49   0   0   1   440 
Now we need to copy the heading for the work column (column 1) to the heading for the work row (row 5).
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   0   41   0   1   -17/28   0   0   -41/28   0   0   0   82 
 x3   0   2   1   0   11/196   0   0   -13/196   0   0   0   11 
 s3   0   95   0   0   95/98   1   0   -433/98   0   0   0   190 
 s4   0   73   0   0   19/28   0   1   -53/28   0   0   0   286 
 x1   1   -4   0   0   -3/49   0   0   8/49   0   0   0   0 
 s6   0   -5   0   0   -23/196   0   0   45/196   1   0   0   0 
 s7   0   290   0   0   1067/196   0   0   -1849/196   0   1   0   1067 
   0   -28   0   0   44/49   0   0   46/49   0   0   1   440 
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 -28 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   0   41   0   1   -17/28   0   0   -41/28   0   0   0   82 
 x3   0   2   1   0   11/196   0   0   -13/196   0   0   0   11 
 s3   0   95   0   0   95/98   1   0   -433/98   0   0   0   190 
 s4   0   73   0   0   19/28   0   1   -53/28   0   0   0   286 
 x1   1   -4   0   0   -3/49   0   0   8/49   0   0   0   0 
 s6   0   -5   0   0   -23/196   0   0   45/196   1   0   0   0 
 s7   0   290   0   0   1067/196   0   0   -1849/196   0   1   0   1067 
   0   -28   0   0   44/49   0   0   46/49   0   0   1   440 
The lowest ratio between positive values in column 2 and corresponding values in the the final column is 2 and that is in row 1. So make row 1 the work row. That makes the item in row 1 and column 2 the pivot item.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   0   41   0   1   -17/28   0   0   -41/28   0   0   0   82 
 x3   0   2   1   0   11/196   0   0   -13/196   0   0   0   11 
 s3   0   95   0   0   95/98   1   0   -433/98   0   0   0   190 
 s4   0   73   0   0   19/28   0   1   -53/28   0   0   0   286 
 x1   1   -4   0   0   -3/49   0   0   8/49   0   0   0   0 
 s6   0   -5   0   0   -23/196   0   0   45/196   1   0   0   0 
 s7   0   290   0   0   1067/196   0   0   -1849/196   0   1   0   1067 
   0   -28   0   0   44/49   0   0   46/49   0   0   1   440 
Use the elementary row operation *row to change the pivot item to be 1. That is, multiply row 1 by 1 / 41.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   0   1   0   1/41   -17/1148   0   0   -1/28   0   0   0   2 
 x3   0   2   1   0   11/196   0   0   -13/196   0   0   0   11 
 s3   0   95   0   0   95/98   1   0   -433/98   0   0   0   190 
 s4   0   73   0   0   19/28   0   1   -53/28   0   0   0   286 
 x1   1   -4   0   0   -3/49   0   0   8/49   0   0   0   0 
 s6   0   -5   0   0   -23/196   0   0   45/196   1   0   0   0 
 s7   0   290   0   0   1067/196   0   0   -1849/196   0   1   0   1067 
   0   -28   0   0   44/49   0   0   46/49   0   0   1   440 
Now use the elementary row operation *row+ to change the other items in column 2 to 0.
  1. multiply row 1 by -2 and add to row 2.
  2. multiply row 1 by -95 and add to row 3.
  3. multiply row 1 by -73 and add to row 4.
  4. multiply row 1 by 4 and add to row 5.
  5. multiply row 1 by 5 and add to row 6.
  6. multiply row 1 by -290 and add to row 7.
  7. multiply row 1 by 28 and add to row 8.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 s1   0   1   0   1/41   -17/1148   0   0   -1/28   0   0   0   2 
 x3   0   0   1   -2/41   689/8036   0   0   1/196   0   0   0   7 
 s3   0   0   0   -95/41   19095/8036   1   0   -201/196   0   0   0   0 
 s4   0   0   0   -73/41   505/287   0   1   5/7   0   0   0   140 
 x1   1   0   0   4/41   -242/2009   0   0   1/49   0   0   0   8 
 s6   0   0   0   5/41   -769/4018   0   0   5/98   1   0   0   10 
 s7   0   0   0   -290/41   78257/8036   0   0   181/196   0   1   0   487 
   0   0   0   28/41   971/2009   0   0   -3/49   0   0   1   496 
Now we need to copy the heading for the work column (column 2) to the heading for the work row (row 1).
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 x2   0   1   0   1/41   -17/1148   0   0   -1/28   0   0   0   2 
 x3   0   0   1   -2/41   689/8036   0   0   1/196   0   0   0   7 
 s3   0   0   0   -95/41   19095/8036   1   0   -201/196   0   0   0   0 
 s4   0   0   0   -73/41   505/287   0   1   5/7   0   0   0   140 
 x1   1   0   0   4/41   -242/2009   0   0   1/49   0   0   0   8 
 s6   0   0   0   5/41   -769/4018   0   0   5/98   1   0   0   10 
 s7   0   0   0   -290/41   78257/8036   0   0   181/196   0   1   0   487 
   0   0   0   28/41   971/2009   0   0   -3/49   0   0   1   496 
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 -3 / 49  = -0.0612244897959184 and that is in column 8. So make column 8 the work column.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 x2   0   1   0   1/41   -17/1148   0   0   -1/28   0   0   0   2 
 x3   0   0   1   -2/41   689/8036   0   0   1/196   0   0   0   7 
 s3   0   0   0   -95/41   19095/8036   1   0   -201/196   0   0   0   0 
 s4   0   0   0   -73/41   505/287   0   1   5/7   0   0   0   140 
 x1   1   0   0   4/41   -242/2009   0   0   1/49   0   0   0   8 
 s6   0   0   0   5/41   -769/4018   0   0   5/98   1   0   0   10 
 s7   0   0   0   -290/41   78257/8036   0   0   181/196   0   1   0   487 
   0   0   0   28/41   971/2009   0   0   -3/49   0   0   1   496 
The lowest ratio between positive values in column 8 and corresponding values in the the final column is 196 and that is in row 4. So make row 4 the work row. That makes the item in row 4 and column 8 the pivot item.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 x2   0   1   0   1/41   -17/1148   0   0   -1/28   0   0   0   2 
 x3   0   0   1   -2/41   689/8036   0   0   1/196   0   0   0   7 
 s3   0   0   0   -95/41   19095/8036   1   0   -201/196   0   0   0   0 
 s4   0   0   0   -73/41   505/287   0   1   5/7   0   0   0   140 
 x1   1   0   0   4/41   -242/2009   0   0   1/49   0   0   0   8 
 s6   0   0   0   5/41   -769/4018   0   0   5/98   1   0   0   10 
 s7   0   0   0   -290/41   78257/8036   0   0   181/196   0   1   0   487 
   0   0   0   28/41   971/2009   0   0   -3/49   0   0   1   496 
Use the elementary row operation *row to change the pivot item to be 1. That is, multiply row 4 by 7 / 5.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 x2   0   1   0   1/41   -17/1148   0   0   -1/28   0   0   0   2 
 x3   0   0   1   -2/41   689/8036   0   0   1/196   0   0   0   7 
 s3   0   0   0   -95/41   19095/8036   1   0   -201/196   0   0   0   0 
 s4   0   0   0   -511/205   101/41   0   7/5   1   0   0   0   196 
 x1   1   0   0   4/41   -242/2009   0   0   1/49   0   0   0   8 
 s6   0   0   0   5/41   -769/4018   0   0   5/98   1   0   0   10 
 s7   0   0   0   -290/41   78257/8036   0   0   181/196   0   1   0   487 
   0   0   0   28/41   971/2009   0   0   -3/49   0   0   1   496 
Now use the elementary row operation *row+ to change the other items in column 8 to 0.
  1. multiply row 4 by 1 / 28 and add to row 1.
  2. multiply row 4 by -1 / 196 and add to row 2.
  3. multiply row 4 by 201 / 196 and add to row 3.
  4. multiply row 4 by -1 / 49 and add to row 5.
  5. multiply row 4 by -5 / 98 and add to row 6.
  6. multiply row 4 by -181 / 196 and add to row 7.
  7. multiply row 4 by 3 / 49 and add to row 8.
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 x2   0   1   0   -53/820   3/41   0   1/20   0   0   0   0   9 
 x3   0   0   1   -207/5740   3/41   0   -1/140   0   0   0   0   6 
 s3   0   0   0   -27973/5740   201/41   1   201/140   0   0   0   0   201 
 s4   0   0   0   -511/205   101/41   0   7/5   1   0   0   0   196 
 x1   1   0   0   213/1435   -7/41   0   -1/35   0   0   0   0   4 
 s6   0   0   0   143/574   -13/41   0   -1/14   0   1   0   0   0 
 s7   0   0   0   -27387/5740   306/41   0   -181/140   0   0   1   0   306 
   0   0   0   761/1435   26/41   0   3/35   0   0   0   1   508 
Now we need to copy the heading for the work column (column 8) to the heading for the work row (row 4).
   x1   x2   x3   s1   s2   s3   s4   s5   s6   s7   z   
 x2   0   1   0   -53/820   3/41   0   1/20   0   0   0   0   9 
 x3   0   0   1   -207/5740   3/41   0   -1/140   0   0   0   0   6 
 s3   0   0   0   -27973/5740   201/41   1   201/140   0   0   0   0   201 
 s5   0   0   0   -511/205   101/41   0   7/5   1   0   0   0   196 
 x1   1   0   0   213/1435   -7/41   0   -1/35   0   0   0   0   4 
 s6   0   0   0   143/574   -13/41   0   -1/14   0   1   0   0   0 
 s7   0   0   0   -27387/5740   306/41   0   -181/140   0   0   1   0   306 
   0   0   0   761/1435   26/41   0   3/35   0   0   0   1   508 
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 = 508

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