Linear Programming for the
TI-83 Plus/TI-84
Content:
This document covers use of the inequality application, row operations, and simplex programs,
on the
TI-83 Plus calculator.
INDEX:
To facilitate lookup, the instructions are divided into
the following categories:
I.
Basic Information - types of row operations,
improving efficiency of row operations, advantages
of inequality application, discussion of whether to use a simplex program,
downloading a simplex
program, entering a simplex program manually,
II. Linear Inequalities - Linear programming without
the inequality App, Linear programming with the
Inequality APP,
III. Simplex Method -Simplex method
by hand
IV. Simplex method using calculator programs
- Simplex method using negative slack variables, Simplex
method using
positive slack variables, addition to the positive slack variable program that
allows that
program to
use negative slack variables,
RELEASE DATE: 9/30/09 DATE LAST REVISED:
10/18/09
© 2003
Frank Kizer
NOTE: See copy restrictions and printing
hints at the end of this document.
I. Basic Information:
1. Updating or not Updating a Matrix with a Row
Operation:
You can choose to only show the result of a row operation or to show the
results and update
the matrix.
If you want to store the result in the matrix, you must tell the calculator to
store
the matrix.
For example, to swap rows 1 and 2 in matrix [A], you would have rowSwap([A],
1,2).
On the other hand,
if you want to store the result in matrix [A], you must have
rowSwap([A], 1,2)-->[A]. The symbol --> is made by pressing STO.
There are four different types of row
operations available on the TI-83 Plus as listed below:
a) Swap two rows with the snytax
rowSwap(matrix name, row number, row number). For example,
if you want
to swap rows 1 and 2 in matrix [A] the display would be as rowSwap([A], 1,2).
You can
either close
the parentheses or not whichever you choose. Do not type an "A" and
enclose it in
brackets for
the matrix type. You must press 2ND, MATRIX, select the matrix, and press
ENTER.
If you want to store the information in matrix [A], you must have rowSwap([A],
1,2)-->[A].
b)
Add two rows with the syntax row+(matrix name, row number, row number).
For example,
if you want
to add row 1 to 2 in matrix [A] the display would be as row+([A], 1,2).
You can
either close
the parentheses or not whichever you choose. Do not type an "A" and
enclose it in
brackets for
the matrix type. You must press 2ND, MATRIX, select the matrix, and press
ENTER.
If you want to store the information in matrix [A], you must have row+([A],
1,2)-->[A].
c)
Multiply a row by a number with the syntax *row(multiplier, matrix name,
row number). For example,
if you want
to multiply row 1 by - 2 in matrix [A] the display would be as *row(-2,[A], 1).
You can
either close
the parentheses or not whichever you choose. Do not type an "A" and
enclose it in
brackets for
the matrix type. You must press 2ND, MATRIX, select the matrix, and press
ENTER.
If you want
to store the information in matrix [A], you must have *row(-2,[A], 1)-->[A].
d)
Multiply a row by a number and add it to another row with the snytax
*row+(multiplier, matrix name,
row
number, row number). For example, if you want to multiply row
1 by - 2 in matrix [A] and add it
to row
2 in matrix [A], the display would be as *row+(-2,[A], 1,2). You can
either close the parentheses
or not
whichever you choose. Do not type an "A" and enclose it in brackets
for the matrix type. You must
press 2ND,
MATRIX, select the matrix, and press ENTER. If you want to store the
information in matrix [A],
you must have
*row+(-2,[A], 1,2)-->[A].
2. Improving Efficiency of Row Operations:
If you have read the
simplex method using row operations that follows farther down the page, you
will notice
I only use the *row+( operation
in that procedure. That can be used because it is possible to use that
operation
to do the addition of two
rows and the multiplication of a row. If that is done, then all one has to
do is press
2ND, ENTRY to display the
previous *row+( operation and edit at most three numbers. I will give two
examples
that will demonstrate
that procedure.
a) Suppose I want to add row 1
to row 2. Instead of using row+([A]1,2), use *row+(1,[A], 1,2).
b) Suppose you want to multiply
row 1 by 1/2. Instead of using *row(1/2, [A],1), use
*row+(-1/2,[A],1,1). Of course, to multiply by 1/3, one would use
*row+(-2/3,[A],1,1).
The obvious
advantage of this method is that instead of going to the matrix list to get
operations, one
need only press
2ND, ENTRY and edit the numbers in the previous row operation.
3. Advantages of Inequality Application:
The inequality application has several
advantages over the method without the application. I have
listed the major ones below.
a) Probably the most important advantage is that X-variables are
available, so that one can graph lines
such as x≤3.
b) All shading except that for the
feasible region can be eliminated. This eliminates the confusion of
determining which
regions are applicable to all constraints.
c) The the corner points can be determined without the
calculator CALC function.
d) The objective function can be evaluated by the
calculator and stored in a special list, rather than
having the student
do the evaluation manually. I am aware, however, that some students may
not have enough
experience with lists to make this worthwhile.
4) Whether to Use a Simplex Program:
Once you get the proper simplex program
installed in your calculator, all you need to do is set up the
proper initial tableau to solve linear
programming problems. There are, however, a few obstacles to
getting the proper program installed.
The major ones are discussed below. I should first add that
everyone who studies linear programming
does not need a simplex program. If you're only going to
do a few row operations, or maybe one or
two simple programs, probably one of the other methods
described here will be entirely sufficient.
a) Choosing the Correct Program:
First one needs to know what format the text, teacher, or other source will
required. Will you be
solving only standard maximum problems or will you be solving those as well as
standard
minimum and mixed constraints? Further, will you require a program that
can handle positive
slack variables, negative slack variables, or both? These are things that
ideally should be settled
before you install a program.
b) Getting the program into your
calculator:
1) Downloading the Program: A simplex program can be
downloaded from the Internet and
installed in a calculator if the file has a .8XP extension. To install a
file with a .8XP file one needs
the TI Connect program installed on a computer and either a USB or "Silver"
cable depending on
which model calculator you have.
2) Entering the Program Manually: The program can be
entered by hand if the program is in text
format. When entering by hand, one needs to know where to find the various
I/O (input/output)
and Control commands. For a person with some knowledge of where to find
these commands,
somewhere around twenty to thirty minutes will be required to enter an average-length simplex
program.
II. Solving Linear Programming Problems Graphically:
1) Graphical Linear Programming without the Inequality Application:
.
Find the maximum of the objective function z=2x +5y,
subject to the following constraints:
3x+2y≤6 (Eq 1a)
-x+2y≤4 (Eq 2a)
x≥0, y≥0
a) First put the two-variable equations in slope-intercept form.
y≤-3/2x+3 (Eq 1b)
y≤1/2x+2 (Eq 2b)
(Remember that you may need to change the direction of the
inequality sign if you have to
multiply or divide by -1 during the rearranging of the equation.)
b) Enter the right side of those equations opposite Y1 and Y2
respectively. Opposite the equal sign
for Y3 enter 0 (zero).
c) Set the WINDOW at Xmin = -1, Ymin=-1, Ymax= the largest value of "b"
plus a few units, say 5 in
this problem.
Xmax is a bit more difficult to anticipate. If there is an equality with a
negative slope, I usually
make Xmax
= 4/3*b/m, round it off to the next largest whole number and add a few units.
You can
enter the arithmetic opposite Xmax. You might want to press GRAPH
and see if all of the
corner points of the bounded region are on the screen.
Now we will enter the inequality signs:
a) Shading of
the graph is
determined by the symbol to the left of the "Y=" entry. Using
the left
arrow, move the cursor all the way to the left of the Y= symbol.
b) Pressing
ENTER in that position will display different symbols. For < or <,
press ENTER
until the upright triangle is displayed. For > or >, press ENTER
until the upside down
triangle is displayed.
c) After you
have the correct symbol displayed, press ENTER to graph the inequality.
Finding the x- and y-values of
the corner points.
You may find it easier to locate the corner points if you change the
inequalities back to equalities
and press GRAPH to graph only the lines. Write down the values of each
corner point. They
will be used to evaluate the objective function
a) Press 2^{nd}, CALC.
b) Press 5 to select intersect.
c) To
get the corner point at the intersection of the two graphs,
move the cursor a little away from
the intersection and press ENTER to mark the first graph line and move the
cursor to the next
graph line.
d) Move the cursor to a little away from the intersection and
press ENTER to mark the second graph
line and set the cursor to guess the intersection.
e) Move the cursor approximately
to the intersection and press
ENTER.
f) The coordinates for
the point of intersection, x=.5 and y=2.25, will appear at the bottom of the
screen.
g) To
obtain the value where the graph line intersects the x-axis, repeat the
procedure
for
the intersection of two lines except that for the second curve you will need to
insure
that the cursor is on the x-axis. If it is not, press the down arrow. The
answer is x=2, y=0.
h) The
corner point where the graph intersects the y-axis is obtained by pressing 2ND,
CALC,
pressing ENTER to select Value, entering 0 (zero) opposite X, and then
pressing ENTER.
Having the calculator evaluate the objective function.
a) First you need to enter the proper expressions. From the home screen, press .5, STO, X,
ALPHA, :
(decimal point key), 2.25, STO, ALPHA, Y, ALPHA, :, 2, X, +, 5, ALPHA, Y.
You should now
have the following on the home screen: .5→X:2.25→Y:2X+5Y
b) Press ENTER and the corner point will be evaluated at 12.25.
c) To evaluate additional points, press 2nd, ENTER and the above
expression will be displayed.
Enter the new corner point and press ENTER. Repeat this as many times as
needed.
2) Graphical Linear Programming with the
Inequalities Application:
Find the maximum of the objective function z=2x +5y,
subject to the following constraints:
3x+2y≤6 (Eq 1a)
-x+2y≤4 (Eq 2a)
x≥0, y≥0
a) First put the two-variable equations in slope-intercept form.
y≤-3/2x+3 (Eq 1b)
y≤1/2x+2 (Eq 2b)
b) Enter the right side of those equations opposite Y1 and Y2 respectively and enter 0
opposite Y3.
c) Set the WINDOW at Xmin = -1, Ymin=-1, Ymax= the largest value of "b"
plus a few units, say 5 in
this problem.
Xmax is a bit more difficult to anticipate. If there is an equality with a
negative slope, I usually
make Xmax
= 4/3*b/m, round it off to the next largest whole number and add a few units.
You can
enter the arithmetic opposite Xmax. You might want to press GRAPH
and see if all of the
corner points of the bounded region are on the screen.
Now we
will enter the inequality signs.
a) Move the cursor to the sign
(either equal or inequality) after Y1. If the inequality symbols do not
appear at the bottom of the screen, you will need to start the Inequality App.
Do that by pressing
APPS, move the cursor
down to Inequal, or Inequalz for the
international version, and press
ENTER, ENTER. The Y= editor screen should be displayed.
b)
Place the cursor on the equal sign opposite Y1 and press ALPHA, F3 (ZOOM).
The equal sign
should have been replaced by the inequality ≤.
c) Do the same for Y2; then opposite Y3, press ALPHA, F5 (GRAPH).
The symbol ≥ should have
replaced the equal sign before the 0.
d) Now, move the cursor up to the "X" in the upper left corner and press
ENTER. With the cursor on the
equal sign opposite X1, press ALPHA, F5 (GRAPH) to enter
≥; then enter a zero after that
symbol.
e) Press GRAPH to draw and shade the graphs.
f) Press ALPHA,
F1, 1 to define the feasible region.
If you only want to graph, you may stop here.
At this time we will find the x- and y-values of the corner points. We
will use a method to have the
calculator determine the corresponding values of the objective function.
If you prefer to determine
those values manually, just record them without pressing STO so that you can
substitute them into
the objective function.
a)
Press ALPHA, F3 (ZOOM) and x=.5, y=2.25 will be displayed. Record
these values if you choose to evaluate the objective
function by hand. Otherwise, press STO, ENTER.
b) Press the left arrow to move to the point x=0, y=2 and press STO, ENTER.
c) Press the right arrow; then then down arrow to read the last point,
x=2, y=0.
Having the calculator evaluate the objective function.
a) Press STAT, ENTER, to bring up the lists with the stored data.
b) First we will name the list after list INEQY. We will name it
OBJ. Move the cursor to the name
block at the top of that list. Press 2ND, ALPHA, O, B, J, ENTER.
Now, we will define the list OBJ.
c) With the curosor on the list name, press ALPHA, " (the + key), 3, x(multiply), 2ND, LIST
and scroll down to
INEQX and press ENTER.
d) Press +, 2, x (multiply), 2ND, LIST, scroll to INEQY and press ENTER.
Press ALPHA, ". You should now have
"3*└INEQX+2*└INEQY" at the bottom left of the screen after "OBJ=". Press
ENTER and the values
of the objective function for each set of coordinates will be displayed in the OBJ list.
III.
Simplex Method:
1. Simplex Using Row Operations with the TI-83Plus or TI-84:
First of all, I suggest that you enter your first tableau in matrix [B], and
then use STO to transfer it to matrix [A].
That way you can work on matrix [A]
and if you make a mistake you won't need to re-enter the original matrix.
You can
Just just transfer the information from [B] to [A] again. Transfer [A] to [B] as follows: Press 2ND, MATRIX,
ENTER, STO, 2ND, MATRIX, 2.
Let's say that you have this set of equations:
Objective Function:
z=24x +36y
Constraints:
x +2y ≤ 14
3x +4y ≤36
x≥ 0, y≥0
So that, when you add slack variables, you
the following as the first tableau:
x y S_{1}
S_{2}
1 2 1
0| 14
3 4 0
1|36
-24 -36 0 0|0
Now, for the pivot
point we first pick the column with the most negative number in the objective
row. That's -36,
so we pick column 2. Now, we want to select the proper
row. Divide 2 into 14and 4 into 36 and select the smaller
result. The quotient for 14/2 is smaller, so 2 is the pivot point.
You want to multiply row 1 by -2 and add it to row 2.
I'll use
"shorthand" such as -2R1 + R2=>R2, to indicate this type of operation.
a) So, enter the matrix in matrix [A] and store it in matrix [B] as
indicated above; then press 2nd, QUIT to go
to the home screen.
b) From the home screen, press 2nd, MATRIX; scroll over to MATH; scroll
down to item F, and press ENTER. You
should now have *row+( on your home
screen.
c) Now you want to enter the multiplier, letter of the matrix, row number
multiplied by, row number to replace in
that order. Do this: Enter
-2, press the comma button, press 2nd, MATRIX, ENTER. You should now
have
*row+(-2, [A] on your screen. DO NOT enter [A] with the brackets and the
letter A but get this from the
matrix list.
d) Now press the comma button, enter 1; press the comma button and
enter 2. You should now have
*row+(-2,[A],1,2 on your screen.
e) Press STO, 2nd, MATRIX, ENTER.
f) You should now have *row+(-2,[A], 1,2)->[A]
on your screen. DO NOT enter [A] with the brackets and the
letter
A. (Note carefully that if you don't add the STO, [A]; then matrix A will
not be changed in your calculator.
Also notice that you can either
close the parentheses after the last row number or leave them open.) Press
ENTER
g) To get a zero in column 1 of the 3rd row, press 2ND, ENTRY (the
ENTER key) to display the first entry again.
Now edit the display so that you have this:
*row+(18,[A],1,3)->[A]. Press ENTER
h) You now have this matrix:
[1 2 1
0| 14
1 0
-2 1|8
-2R_{1}+R_{2}==>R_{2}
-6 0 18
0|252] 18R_{1} +R_{3}==>R3
Now we want to have zeros in the first and third position of column 1.
i) Press 2ND, ENTRY to display the expression and edit it to get this:
*row+(-1,[A], 2,1)->[A].
j) Now, to get a zero in column 1, row 3,
press 2ND, ENTRY and edit the expression to get this:
*row+(6,[A], 2,3)->[A].
You now have this matrix:
[0 2 3
-1| 6 -R_{2}+R_{1}==>R_{1}
1 0 -2
1|8
0 0 6
0|300] 6R_{2}+R_{3}==>R_{3}
k) Finally, we need to get a 1 in row 1, column 2.
We could compose a new statement using the *row( expression,
but let's just save several
steps by pressing 2ND, ENTRY and editing the expression to get this:
*row+(-1/2,[A],1,1)->[A].
The problem is now solved with the following matrix.
[0 1 3/2
-1/2| 3 -1/2R_{1}+R_{1}==>R_{1}
1 0 -2
1|8
0 0 6
0|300]
x=8, y=3, z=300
NOTE: If you want to add two rows; then the syntax is this: row+(matrix
letter, row to be added,
row to be replaced)->[A]
To swap rows, use this syntax: rowSwap(matrix letter, first row,
second row)->[A]
THE REST OF THIS SECTION IS
UNDER CONSTRUCTION BUT CAN BE USED AS A GUIDE TO THE PROGRAMS
THAT I HAVE WRITTEN.
2.
Simplex with the TI-83Plus or TI-84 Using Calculator Programs:
General: Calculator programs for doing
simplex and quite different in the details of their approach, but the
differences in those that I have seen boil down
to whether they will do standard maximization, standard
minimization, mixed, more than of these, or
all of them. There are many program on the Internet that can be
found by a quick search with a good search
engine. I will list my programs and describe what they will do and
where they can be found.
a) Simplex Program Using Negative Slack Variables (tisimplex_neg):
This stand-alone program is for
those who are familiar with the simplex method that uses negative slack
variables when doing problems with mixed constraints or minimization. You must
enter the first tableau in matrix [A] with the proper slack variables and with
the proper signs for the indicator row (objective function.) The program
then manipulates rows to give a first feasible solution and displays the
solution in decimal form. The solution may be displayed in fractional
form, if appropriate, by pressing ENTER. When you are finished with the
answer, press ENTER because the program is STILL RUNNING in PAUSE Mode to permit scrolling the
matrix. This program can be found by clicking on the link in the
title at the beginning
of this discussion.
b) Simplex Program Using Positive Slack Variables
(tisimplex_pos):
This program is for those who are familiar
with the simplex method that uses POSITIVE slack variables when doing problems
with mixed constraints or minimization. You must enter the first tableau
in matrix [A] with the proper slack variables and with the proper signs for the
indicator row (objective function.) The program then manipulates rows to
give a first feasible solution and displays the solution in decimal form.
The solution may be displayed in fractional form, if appropriate, by pressing
ENTER. When you are finished with the answer, press ENTER because the
program is STILL RUNNING in PAUSE Mode to permit scrolling the matrix. I am not
the originator of the ideas in this program. This program can be found by
clicking on the link in the title at the beginning of this discussion.
c) Simplex Program Extension using Negative
Slack Variables (tisimplex_ext):
This is a menu driven front-end
extension to the above program for positive slack variables, that permits use of
negative slack variables with that program. You must have the program
tisimplex_pos entered in your calculator in order for this program to give you
anything other than the initial tableau for minimizations or mixed constraints.
This program sets up the first feasible tableau for mixed inequalities and
standard minimization problems. The program tisimplex_pos and then solves that
tableau for the final optimized tableau. Appropriate negative slack variables
must entered for mixed, or minimization problems. Of course, you can solve
standard maximization problems by entering the first tableau with appropriate
positive slack variables and choosing the appropriate item from the menu. This
program can be found by clicking on the link in the title at the beginning
of this discussion.
==================================
Copy Restrictions:
You
may make single copies of this document for your own personal use and for the
use of other students, but inclusion in another document, publication or any use
for profit requires my permission. Teachers may make multiple copies of this
document for their students if they first get permission from me. Merely send
me an email (Just click on Webmaster in the navigation bar.) with a one-sentence
explanation of what you’re using the document for. I’ll give you permission in
a timely manner.
Making it Better: I
would be grateful if you would report any errors or suggestions for improvements
to me. Just click "E-mail Webmaster," site the item number, and tell me
your suggested change.
Printing Hint:
Most browsers will send both the navigation bar and the text to
the printer, and, as a result, will cut off the right edge of this document if
it the file is printed directly. To prevent this, highlight the
instructions portion only (not the navigation panel) and check "Selection" on
the Print dialog box; then click "Apply." This will eliminate the
navigation panel and get all of the instructions on the printed pages.