Simplex Method Using the TI-89 SM2 Program

The Simplex Method, as presented in the textbook, is a set of steps that can be used to solve linear programming problems. Remember that linear programming does not involve "computer programming". However, it is possible to write a computer or a calculator program to perform the Simplex Method. The calculator program "SM2", has been created to perform the Simplex Method as described in the text. There is a TI-89 specific version of that program that will be made available in class or that can be downloaded here: TI-89 version of SM2.

This page demonstrates the use of the TI-89 program SM2 to perform the Simplex Method. The page steps through the keystrokes and resulting screens for solving two linear programming problems. These problems are taken directly from the textbook.

Before using the SM2 program, it must be loaded onto your calculator. This can be done in class by linking calculators and downloading from one to another. Or, if you have the TI-GraphLink program, you can download the program from this web page to your PC and then load the program from the PC to the TI-89.

Remember that the TI-89 is case-insensitive. Although we may refer to the program as SM2, on the TI-89 this is the same as sm2.

The problem that we will solve on the calculator is taken from page 233 of the text.

Maximize: z = x₁ + x₂
Subject to: x₁ + x₂ <= 125
-4x₁ - 5x₂ <= -500
-2x₁ - x₂ <= -200
assuming: x₁ and x₂ are nonnegative From this we note that there are two variables, and three constraints, and, of course, one objective function.

Figure 1	We request the sm2 program by pressing the keys to generate Figure 1. Note that the name of the program, sm2, must be followed by the set of parentheses. Now press the key to actually start the program.
Figure 2	The program begins by shifting from the HOME screen to the PROGRAM screen and then asking for the number of variables. We respond with . Then the program asks for the number of constraints. Our problem has 3 constraints. Therefore, press . This should leave the screen as in FIgure 2.
Figure 3	We press to accept the number of constraints. Now the program asks for the constraints in matrix form. Figure 3 has our response to this request, entered via the bracket notation for a matrix. Read the material immediately below this table to understand the origin of that matrix.

We need to give the program the constraints in matrix form. We can do this in two different ways. First, we can merely type the matrix using the "[" and "]" characters. This is the method that we used in Figure 3. Second, if we had stored the matrix earlier under a name, then we could just enter the name. We will use that method for the second problem, starting in Figure 22.

Right now, we need to remember how to create the augmented matrix for the constraints. To do this we will re-write the constraints with each variable represented in the inequality. (Note: we are not adding the "slack variables" here; the program will do that for us. We are just making sure that each variable appears in each inequaltiy.]

1x₁ + 1x₂ <= 125
-4x₁ - 5x₂ <= -500
-2x₁ - 1x₂ <= -200 This is a 3x3 matrix of values that we could write as the following table:

1	1	125
-4	-5	-500
-2	-1	-200

And, we would write that, on the TI calculators as [[1,1,125][-4,-5,-500][-2,-1,-200]]. For Figure 3, we entered that matrix via the keys

Figure 4 We complete Figure 3 by pressing the key. The program now asks for the "Objective Function Vector". We should note that on the TI-89 there is no special form for a vector. A vector is treated as a single row matrix, and, we do not need to put the extra set of brackets around that row. For our problem, that objective function vector is made up of the objective function coefficients. Since our objective function is z = 1x₁ + 1x₂ the vector would be [1,1]. We enter this via the keys . This produces the text seen in Figure 4.

Figure 5 Pressing to accept the objective function vector of Figure 4 produces the minimize vs. MAXIMIZE choice. We select the MAXIMIZE option by pressing the key to complete Figure 5.

Figure 6 After Figure 5 we have given the program all of the data that it needs to do the problem. We press the key to start the process. Along the way the calculator will display intermediate results. At times it will pause to let us read those results. The first pause is shown in Figure 6. Here, the calculator has created the TABLEAU and is displaying it for us.

Figure 7 The calculator was paused at Figure 6 to allow us to examine the TABLEAU. We did so, and then we press the key to continue the program. The calculator entered the "Preprocessing" phase of the algorithm. In that phase, the calcualtor identified the second row as the work row (not shown), and within that second row, it identified the second column as the work column. That means that the value that was in row 2 column 2, namely -5, becomes a pivot point. Therefore, we use the second elementary row operation to change it to a 1, and the third elementary row operation to convert all remaining elements in the second column to be 0. The calculator has done exactly that, and it has paused at that point to display the resulting matrix, shown in Figure 7. This matrix corresponds to the one in the middle of page 234 in the text. Note that the entire matrix does not fit on the page. The heavy arrow at the right side of the screen indicates that there is more to be displayed.

Figure 8 We have moved from Figure 7 to Figure 8 by pressing the right cursor key, , to move over on the display. Comparing Figure 8 with Figure 7 we can see the values that were cut off in Figure 7.

Figure 9 We leave Figure 8 by pressing the key to continue the program. The calculator continues the preprocessing phase, identifying the third row and first column as the work row and column. It then changes the pivot point to a 1, and converts the remaining work column values to 0. Again, we pause to examine the matrix, shown in Figure 9. This matrix corresponds to the bottom matrix on page 234.

Figure 10 Figure 10 shows more of the matrix from Figure 9. In this case, again, we used the cursor key to move to the right. However, as we examine Figure 10 we note that part of the top row of values has been cut off.

Figure 11 Figure 11 is the result of using the cursor up key, , and the key to move back to the upper left corner of the matrix.

Figure 12 Figure 12 is the result of using the key to move to the next step. Unfortunately, some of the output of the program has scrolled off the screen, and we have no way to return to it. The program has looked at the matrix and determined that we are done with the preprocessing phase. It indicated that fact in the message that is no longer visible, and it displays the same matrix again, as in Figure 12.

Figure 13 The key leaves Figure 12 and moves the calculator into the basic algorithm. Here the calculator determines that the fourth column is the work column, and that the first row is the work row. The calculator makes the element in row 1 column 4 become 1 and the calculator uses that 1 to change the other elements in that column to be 0. Once this is done, the calculator displays the resulting matrix and pauses to allow us to examine it, as shown in Figure 13.

Figure 14 Pressing the key continues the algorithm. The calculator determines that we are done. It gives the message that the final matrix is being displayed and it pauses as in Figure 14.

Figure 15 Now we can get the calculator's best guess at the results by pressing the key. The program responds by indicating that the maximum value for the objective function can be found when x₁ has the value 75. This is exactly the value presented in the second sentence of the paragraph at the bottom of page 234. The other values follow in Figures 16 and 17, with the value of the objective function being given in Figure 18.

Figure 16 We continue by pressing the key, to find, in Figure 16, that the value of x₂ needs to be 50.

Figure 17 Another key shows us Figure 17, whcih gives us s₂, the second slack variable, having the value 50.

Figure 18 Yet another key moves us to Figure 18, which repeats that the objective function value will be 125.

Figure 19 For a convenience, the program continues, after a press of the key, to redisplay the matrix, as shown in Figure 19. The program is paused at that point so that we can scroll over on the matirx if need be. In this case the entire matrix is displayed on screen so we do not need to scroll at all. However, notice the at the lower right of the screen. This indicates that we are still in the sm2 program. In addition, note that all of the menu items at the top of the screen are unavailable in Figure 19.

Figure 20 Pressing of the key allows the program to end, as is shown in Figure 20. However, we are still in the PROGRAM screen. We do have a new option in that the F5 menu item is now available, as noted at the top of the screen.

Figure 21 We return to the HOME screen by pressing the key. Figure 21 shows that HOME screen with The sm2() program marked as done, and with the sm2() item pre-loaded in the command line.

One of the problems with the approach shown above is that there is no asy recovery if you have made an error in the original matrix, or in the objective function vector. The program merely continues, and probably produces the wrong answers. It is much safer for us to store the constraint matrix and the objective vector on the calculator before we use SM2. That way, if an error is found, we can correct it and rerun the program without having to re-enter all of the coefficients and constants. We will demonstrate this in the remaining Figures.

The next example is taken from page 238 of the text. In this case there are three variables and two constraints. The problem is stated as:

Minimize: z = 20x₁ - 10x₂ + 30x₃
Subject to: 5x₁ + 10x₂ + 15x₃ >= 150
-2x₁ - 2x₂ + 6x₃ >= 12
assuming: x₁, x₂, and x₃ are nonnegative The textbook points out that we need to rewrite the problem as Maximize: Z = -20x₁ + 10x₂ - 30x₃
Subject to: -5x₁ - 10x₂ - 15x₃ <= -150
2x₁ + 2x₂ - 6x₃ <= -12
assuming: x₁, x₂, and x₃ are nonnegative to make it conform to the requirements of the simplex method. For this we have a constraint matrix that we can represent in the table:

-5	-10	-15	-150
2	2	-6	-12

We will store this matrix and the objective vector on the calculator before we start the SM2 program.

Figure 22 The first step is to create the constraint matrix. The key strokes produce the command line shown in Figure 22. We stop here only to demonstrate that as we add more to the input line, in Figure 23, part of the command line scrolls off the left end as new characters are added to the right.

Figure 23 We complete the matrix via the keys to complete the entry of the matrix. To save it under a name we use the key followed by the desired name. In the example shown in Figure 23, that name is aa, and was created via the key sequence.

Figure 24 Pressing the key to accept the command causes the display to change to that shown in Figure 24.

Figure 25 In Figure 25 we will enter the objective vector and save it under the name bb. Again, remember that on the TI-89 a vector is just a single row matrix. A small warning: this is not the right set of values, but we will enter them here, use them, discover our error, correct them, and rerun the program with the correct values. The keys produce the vector. Note the single left and right square bracket. Then we store the vector in bb via the keys and . We finish Figure 25 by typing the name of the program including the parentheses, using the key sequence: .

Figure 26 The program starts as before, asking for the number of variables, we respond with , and the number of constraints, to which we respond with .

Figure 27 We leave Figure 26 via the key. The program responds with a request for the matrix of constraint coefficients and constants. In this case, we have already entered that matrix and we have saved it under the name aa. Therefore, we type the name of the matrix via the keys. We press to accept that answer. The program asks for the Function Vector. We respond with the name of the single row matrix that we saved earlier: . This completes Figure 27.

Figure 28 Having pressed to accept the name of the Function Vector, the program asks if we want to minimize or MAXIMIZE that function. In this case we want ot "minimize" the result so we press the key.

Figure 29 Again we press the keys to accept the 0 in Figure 28. The program goes on to show the initial Tableau, as shown in Figure 29. We can compare this to the matrix on page 239. It is almost the same. However, we note that the signs on the values in the bottom row are reversed. What happened?
If we go back we will find that we created the objective function vector using the equation
Z = -20x₁ + 10x₂ - 30x₃ We created Z = -z as was done in the book. However, the program, SM2, does this for us when we select the "minimize" option. Therefore, SM2 has undone our conversion, and the values in the final row of the TABLEAU have the wrong sign. We need to stop the program, change the vector and then run the program again with the new vector.

Figure 30 We stop the program by pressing the key. The calculator responds with Figure 30. We know what we need to do, and that does not involve changing the program. Therefore, we want to select the CANCEL menu item. To do this we press the key.

Figure 31 Figure 31 shows the Program IO screen, with the sm2 program ended. There is no at the lower right corner and the only available option at the top is the option. We need to return to the HOME screen. Therefore, we press the key to select that option. Because we are on the PROGRAM screen, the F5 option takes us back to the HOME screen.

Figure 32 Figure 32 has us back at the HOME screen. We can see that the former run of the sm2 program ended in the "Error: Break" condition.

Figure 33 We need to reverse the values stored in bb. We do not need to re-enter those values. Instead, we can simply multiply bb by -1 and store the results in bb. The keys needed to do this are . The calculator multiplies each element of the vector by -1 and stores the resulting vector in bb, and displays the new bb.

Figure 34 Now we need to start the program again. We could re-type the sm2() command, but we will take this opportunity to demonstrate moving back into the history to retrieve an earlier command. We use the key 4 times to move the highlight up to the sm2() command on the screen, as is shown in Figure 34.

Figure 35 Having highlighted the command that we wnat to recall, we press the key to actually paste that command into the command line, shown in Figure 35. At this point, we could edit tht line if we desired. Howver, in this case, we simply want to repeat the command to start the program again. Therefore, we press to leave Figure 35 and start running the program in Figure 36.

Figure 36 Again we answer the initial questions of the program.

Figure 37 In Figure 37 we supply the name of the Constraint matrix, aa, and the name of the Function Vector, bb.

Figure 38 We again choose to minimize the function.

Figure 39 In Figure 39 we have a new version of the initial TABLEAU. This time it corresponds exactly with the example on page 239 in the text.

Figure 40 We press the key to move further through the program, comparing the program output with the values given in the text at each step.

Figure 41 We press the key to move further through the program, comparing the program output with the values given in the text at each step.

Figure 42 We press the key to move further through the program, comparing the program output with the values given in the text at each step.

Figure 43 The program announces, in Figure 43, that we are done, and it redisplays the matrix.

Figure 44 The program now steps through what it believes to be the solution. In Figure 44 we have the statement that x₂ is 8.

Figure 45 Figure 45 has x₃ being 4 2/3, or 14/3

Figure 46 And, Figure 46 shows the objective value to be 60.

Figure 47 A final display of the matrix shows up in Figure 47. The program is still running. It is just PAUSED. Therefore we can use the cursor key to move around in the matrix.

Figure 48 In fact, we use the key to move to the right side of the matrix in Figure 48.

Figure 49 We press to allow the program to end, in Figure 49. This leaves us in the PROGRAM IO screen.

Figure 50 We return to the HOME screen in Figure 50 by pressing the key. Note that the line above the command line indicates that the just finished run of the sm2 program terminated with the "Done" condition.

Figure 4	We complete Figure 3 by pressing the key. The program now asks for the "Objective Function Vector". We should note that on the TI-89 there is no special form for a vector. A vector is treated as a single row matrix, and, we do not need to put the extra set of brackets around that row. For our problem, that objective function vector is made up of the objective function coefficients. Since our objective function is z = 1x₁ + 1x₂ the vector would be [1,1]. We enter this via the keys . This produces the text seen in Figure 4.
Figure 5	Pressing to accept the objective function vector of Figure 4 produces the minimize vs. MAXIMIZE choice. We select the MAXIMIZE option by pressing the key to complete Figure 5.
Figure 6	After Figure 5 we have given the program all of the data that it needs to do the problem. We press the key to start the process. Along the way the calculator will display intermediate results. At times it will pause to let us read those results. The first pause is shown in Figure 6. Here, the calculator has created the TABLEAU and is displaying it for us.
Figure 7	The calculator was paused at Figure 6 to allow us to examine the TABLEAU. We did so, and then we press the key to continue the program. The calculator entered the "Preprocessing" phase of the algorithm. In that phase, the calcualtor identified the second row as the work row (not shown), and within that second row, it identified the second column as the work column. That means that the value that was in row 2 column 2, namely -5, becomes a pivot point. Therefore, we use the second elementary row operation to change it to a 1, and the third elementary row operation to convert all remaining elements in the second column to be 0. The calculator has done exactly that, and it has paused at that point to display the resulting matrix, shown in Figure 7. This matrix corresponds to the one in the middle of page 234 in the text. Note that the entire matrix does not fit on the page. The heavy arrow at the right side of the screen indicates that there is more to be displayed.
Figure 8	We have moved from Figure 7 to Figure 8 by pressing the right cursor key, , to move over on the display. Comparing Figure 8 with Figure 7 we can see the values that were cut off in Figure 7.
Figure 9	We leave Figure 8 by pressing the key to continue the program. The calculator continues the preprocessing phase, identifying the third row and first column as the work row and column. It then changes the pivot point to a 1, and converts the remaining work column values to 0. Again, we pause to examine the matrix, shown in Figure 9. This matrix corresponds to the bottom matrix on page 234.
Figure 10	Figure 10 shows more of the matrix from Figure 9. In this case, again, we used the cursor key to move to the right. However, as we examine Figure 10 we note that part of the top row of values has been cut off.
Figure 11	Figure 11 is the result of using the cursor up key, , and the key to move back to the upper left corner of the matrix.
Figure 12	Figure 12 is the result of using the key to move to the next step. Unfortunately, some of the output of the program has scrolled off the screen, and we have no way to return to it. The program has looked at the matrix and determined that we are done with the preprocessing phase. It indicated that fact in the message that is no longer visible, and it displays the same matrix again, as in Figure 12.
Figure 13	The key leaves Figure 12 and moves the calculator into the basic algorithm. Here the calculator determines that the fourth column is the work column, and that the first row is the work row. The calculator makes the element in row 1 column 4 become 1 and the calculator uses that 1 to change the other elements in that column to be 0. Once this is done, the calculator displays the resulting matrix and pauses to allow us to examine it, as shown in Figure 13.
Figure 14	Pressing the key continues the algorithm. The calculator determines that we are done. It gives the message that the final matrix is being displayed and it pauses as in Figure 14.
Figure 15	Now we can get the calculator's best guess at the results by pressing the key. The program responds by indicating that the maximum value for the objective function can be found when x₁ has the value 75. This is exactly the value presented in the second sentence of the paragraph at the bottom of page 234. The other values follow in Figures 16 and 17, with the value of the objective function being given in Figure 18.
Figure 16	We continue by pressing the key, to find, in Figure 16, that the value of x₂ needs to be 50.
Figure 17	Another key shows us Figure 17, whcih gives us s₂, the second slack variable, having the value 50.
Figure 18	Yet another key moves us to Figure 18, which repeats that the objective function value will be 125.
Figure 19	For a convenience, the program continues, after a press of the key, to redisplay the matrix, as shown in Figure 19. The program is paused at that point so that we can scroll over on the matirx if need be. In this case the entire matrix is displayed on screen so we do not need to scroll at all. However, notice the at the lower right of the screen. This indicates that we are still in the sm2 program. In addition, note that all of the menu items at the top of the screen are unavailable in Figure 19.
Figure 20	Pressing of the key allows the program to end, as is shown in Figure 20. However, we are still in the PROGRAM screen. We do have a new option in that the F5 menu item is now available, as noted at the top of the screen.
Figure 21	We return to the HOME screen by pressing the key. Figure 21 shows that HOME screen with The sm2() program marked as done, and with the sm2() item pre-loaded in the command line.

Figure 22	The first step is to create the constraint matrix. The key strokes produce the command line shown in Figure 22. We stop here only to demonstrate that as we add more to the input line, in Figure 23, part of the command line scrolls off the left end as new characters are added to the right.
Figure 23	We complete the matrix via the keys to complete the entry of the matrix. To save it under a name we use the key followed by the desired name. In the example shown in Figure 23, that name is aa, and was created via the key sequence.
Figure 24	Pressing the key to accept the command causes the display to change to that shown in Figure 24.
Figure 25	In Figure 25 we will enter the objective vector and save it under the name bb. Again, remember that on the TI-89 a vector is just a single row matrix. *A small warning: this is not the right set of values, but we will enter them here, use them, discover our error, correct them, and rerun the program with the correct values.* The keys produce the vector. Note the single left and right square bracket. Then we store the vector in bb via the keys and . We finish Figure 25 by typing the name of the program including the parentheses, using the key sequence: .
Figure 26	The program starts as before, asking for the number of variables, we respond with , and the number of constraints, to which we respond with .
Figure 27	We leave Figure 26 via the key. The program responds with a request for the matrix of constraint coefficients and constants. In this case, we have already entered that matrix and we have saved it under the name aa. Therefore, we type the name of the matrix via the keys. We press to accept that answer. The program asks for the Function Vector. We respond with the name of the single row matrix that we saved earlier: . This completes Figure 27.
Figure 28	Having pressed to accept the name of the Function Vector, the program asks if we want to minimize or MAXIMIZE that function. In this case we want ot "minimize" the result so we press the key.
Figure 29	Again we press the keys to accept the 0 in Figure 28. The program goes on to show the initial Tableau, as shown in Figure 29. We can compare this to the matrix on page 239. It is almost the same. However, we note that the signs on the values in the bottom row are reversed. What happened? If we go back we will find that we created the objective function vector using the equation Z = -20x₁ + 10x₂ - 30x₃ We created Z = -z as was done in the book. However, the program, SM2, does this for us when we select the "minimize" option. Therefore, SM2 has undone our conversion, and the values in the final row of the TABLEAU have the wrong sign. We need to stop the program, change the vector and then run the program again with the new vector.
Figure 30	We stop the program by pressing the key. The calculator responds with Figure 30. We know what we need to do, and that does not involve changing the program. Therefore, we want to select the CANCEL menu item. To do this we press the key.
Figure 31	Figure 31 shows the Program IO screen, with the sm2 program ended. There is no at the lower right corner and the only available option at the top is the option. We need to return to the HOME screen. Therefore, we press the key to select that option. Because we are on the PROGRAM screen, the F5 option takes us back to the HOME screen.
Figure 32	Figure 32 has us back at the HOME screen. We can see that the former run of the sm2 program ended in the "Error: Break" condition.
Figure 33	We need to reverse the values stored in bb. We do not need to re-enter those values. Instead, we can simply multiply bb by -1 and store the results in bb. The keys needed to do this are . The calculator multiplies each element of the vector by -1 and stores the resulting vector in bb, and displays the new bb.
Figure 34	Now we need to start the program again. We could re-type the sm2() command, but we will take this opportunity to demonstrate moving back into the history to retrieve an earlier command. We use the key 4 times to move the highlight up to the sm2() command on the screen, as is shown in Figure 34.
Figure 35	Having highlighted the command that we wnat to recall, we press the key to actually paste that command into the command line, shown in Figure 35. At this point, we could edit tht line if we desired. Howver, in this case, we simply want to repeat the command to start the program again. Therefore, we press to leave Figure 35 and start running the program in Figure 36.
Figure 36	Again we answer the initial questions of the program.
Figure 37	In Figure 37 we supply the name of the Constraint matrix, aa, and the name of the Function Vector, bb.
Figure 38	We again choose to minimize the function.
Figure 39	In Figure 39 we have a new version of the initial TABLEAU. This time it corresponds exactly with the example on page 239 in the text.
Figure 40	We press the key to move further through the program, comparing the program output with the values given in the text at each step.
Figure 41	We press the key to move further through the program, comparing the program output with the values given in the text at each step.
Figure 42	We press the key to move further through the program, comparing the program output with the values given in the text at each step.
Figure 43	The program announces, in Figure 43, that we are done, and it redisplays the matrix.
Figure 44	The program now steps through what it believes to be the solution. In Figure 44 we have the statement that x₂ is 8.
Figure 45	Figure 45 has x₃ being 4 2/3, or 14/3
Figure 46	And, Figure 46 shows the objective value to be 60.
Figure 47	A final display of the matrix shows up in Figure 47. The program is still running. It is just PAUSED. Therefore we can use the cursor key to move around in the matrix.
Figure 48	In fact, we use the key to move to the right side of the matrix in Figure 48.
Figure 49	We press to allow the program to end, in Figure 49. This leaves us in the PROGRAM IO screen.
Figure 50	We return to the HOME screen in Figure 50 by pressing the key. Note that the line above the command line indicates that the just finished run of the sm2 program terminated with the "Done" condition.