+----------------------------------+ | | | MATRIX PROGRAM TUTORIAL FILE | | | +----------------------------------+ The purpose of this file is to provide a tutorial lesson on all the basic features of the program called MATRIX. While it is possible to learn how to use the program by reading all the built-in help screens, if you are a first-time user, we suggest you read this tutorial while first running the program, and then later you can digest all the information contained in the help functions within the program. You can import this file, MATRIX.TXT, into any word processor and then print it so you can read the hard copy output while you run the program. To begin the tutorial you must have the compiled binary on-line help file called MATRIX.HLP, and you must have the program file MATRIX.EXE. We assume these two files are in the current directory on the currently selected disk drive. PRELIMINARY CONVENTIONS ======================= USING A MOUSE ------------- The MATRIX program has been designed to be used with a mouse. It provides a standard windows interface. If you are already familiar with either Microsoft Windows or with a Macintosh interface, then we assume you know how to work pull-down menus, and how to differentiate selecting things with a mouse versus dragging things with a mouse. We assume you know how to work radio buttons, list boxes, and push buttons, and how to manipulate the objects commonly found in dialog boxes. MATRIX operates in a text mode on IBM-compatible computers. Radio button items are delineated by parentheses, and when such an item is checked a small round dot will appear between the parentheses. Since not all printers or displays print this exact symbol, in this tutorial file we will use the asterisk character * to denote the dot. On your screen however, you will see a dot, not an asterisk. For example, in the three items below, only the middle one is checked. ( ) this item is not checked (*) this item is checked ( ) this item is not checked When using a mouse, you can click anywhere on the text labeling such an item to cause that item to be selected. USING THE PROGRAM WITHOUT A MOUSE --------------------------------- If you do not have a mouse, you can still access all the features of the program. A mouse is recommended because its use makes things faster, but for those times when you do not have a mouse you can accomplish everything with a keyboard, at the cost of making a few more keystrokes. As part of this tutorial we need to give directions on which keys to press on your keyboard. We will enclose in angle brackets single keystrokes that you should type. For example, if we ask you to type the first three letters of the alphabet we will show . If we ask you to press the control key, the alternate key, the backspace key, the space bar, the tab key, or the enter (or return) key, we will show , , , , , or . Each enclosure in angle brackets should refer to exactly one keystroke or one character. Some characters like <+> or <*> can be entered in two different ways on some keyboards, one way uses the key, the other way does not. In general, we would only show the single character in angle brackets and we leave it up to you to decide whether or not the is needed to enter the character. Function keys will be denoted by where n is the corresponding number. In most situations pressing brings up the context sensitive help system. These keyboard conventions should make clear exactly how many and which keys you press. If it is necessary to press two keys simultaneously we will show a connecting plus sign between the keystrokes. This is done primarily with the Control key , and the Alternate key . For example, when we show + it means you should press both the Alternate key and key X at the same time. + is used to exit the program. At other times we may need to refer to a keystroke without intending that you actually press the keys. If we mention the ALT+X command, but it is not enclosed with angle brackets, then you should not press the keys. You only press the keys when the angle brackets surround the command. DISPLAY STRINGS =============== We also need to indicate the contents of text strings you might see on the display screen. Such text parts will always be displayed in double quotes in this tutorial file. You will not see the double quotes on the screen, and the screen may contain other text parts that we do not show in this file. The double quotes are simply a convenient way to indicate parts of what you may see on the display. ADVICE FOR NOVICES AND EXPERTS ============================== This tutorial file assumes you have the mathematical background required to understand the features that will be demonstrated. You may find some sections more applicable to novices than experts, or vice versa, depending on your background and experience. If you encounter an example that is beyond your understanding, you can either skip that example, or you can press the keys and view the results, even though you may not fully comprehend the output. This tutorial does not discuss techniques on how to best use or apply the available features. It only serves to demonstrate the basic features and capabilities which you can learn to apply to solve problems that are of interest to you. GETTING STARTED =============== To begin running the MATRIX program type the command: When the matrix program first starts it loads a 3x3 matrix in a window, in which each element is a 0. The entire screen can be considered to be divided into three distinct sections. The very top line on the screen is what is called the Menu Bar. The very last line is called the Status Line. The area of the screen between the Menu Bar and the Status Line is called the Desktop, and it is within the Desktop that your matrices will be displayed. Each matrix is displayed in a separate window that is surrounded by a border or what will be called the window frame. Intitially there is only one large window whose frame is a thick double line. THE MAIN MENU BAR AND SELECTING SUBMENU ITEMS ============================================= Commands are always selected from items on the Menu Bar. If you have a mouse then you exercise each pull-down menu by clicking or selecting the text of the menu titles. If you do not have mouse you can use the key together with the highlighted letter of each menu item. For example, pressing Alt+F will cause the File menu item to display its list of contents. Pressing Alt+M will show the items under the Modify menu. To further select an item under any menu (what is called a submenu item), use the down arrow or up arrow keys to move the highlighting to the item you wish to select and then press the key to execute the corresponding command. A sometimes faster alternative to using the arrow keys is to press the highlighted letter of the menu item you wish to select. Each menu item has one of its letters highlighted. For example, under the Modify menu the Redimension command is associated with the letter R. So pressing Alt+M and then R would select the Redimension command. INDICATORS FOR MENU COMMANDS ============================ Most of the commands of the MATRIX program are derived from menu items. To indicate the selection of a command in this tutorial file that is associated with one or more menu commands we will show the menu titles in all upper case letters. Submenu commands will be preceded by their parent menu titles, with a vertical line | separating the items. For example, MODIFY | REDIMENSION refers to the main menu command MODIFY and then the further submenu command under MODIFY that is titled REDIMENSION. Most commands use two levels of depth within the menus; a few special commands go down 3 or 4 menu levels. In any case, each capitalized title represents a menu command that you should select. We will not show the keystrokes ALT+M and R that would select the Modify and Redimension menu items if you have only a keyboard. In this tutorial file we prefer to show the command names which are meaningful for both mouse and keyboard users. After a little use you will recognize the menu names and the submenu items and you will feel more comfortable with the command organization and the logical grouping of the menus and commands. THE STATUS LINE =============== The Status Line at the bottom of the screen is used to give you hints or messages about the actions you are performing. The hints are context sensitive. Usually the left side of the Status Line shows the two commands ALT+X EXIT and F1 Help. If you have a mouse, you can click the mouse over the text of these commands without using the keyboard. THE ACTIVE WINDOW ================= When you have two or more matrix windows on the Desktop, then only one will show the double-line frame. This window is called the active window. The other windows will be drawn with frame borders that show single thin lines. The active window border is also highlighted; the other window borders will appear more plain. SOLVING A 3x3 LINEAR SYSTEM =========================== The first example we give will show how to use the program to solve a system of 3 equations and 3 unknowns. The system to be solved is: 4X + 6Y - 8Z = 8 2X + 5Y + 4Z = 16 5X - 3Y + 10Z = -22 The matrix we need to enter is as shown below. +- -+ | 4 6 -8 | 8 | | | | | 2 5 4 | 16 | | | | | 5 -3 10 | -22 | +- -+ This system requires a 3x4 matrix, and the default matrix you should be looking at is only 3x3. So the first thing we need to do is redimension the active matrix. Select the command MODIFY | REDIMENSION and a dialog box will appear into which you are to type the number of rows and the number of columns you wish the matrix to have. DIALOG BOXES AND THEIR CONTROLS =============================== Most dialog boxes have two special buttons marked OK and CANCEL. If you have only a keyboard then you should know that the ENTER key normally selects the OK pushbutton and the ESC key selects the CANCEL pushbutton. If a dialog box also has a Help pushbutton then you can press function key F1 to execute that pushbutton. You should also note that when a dialog box contains several controls, you can use the Tab key to move the focus from one control to the next. Most controls are labeled with a text title that contains a highlighted letter. Pressing the Alt key simultaneously with that letter will move the focus directly to that control. If the control is a pushbutton you can further press the space bar to execute the button. The focus should already be in the Rows edit line so press <3> <4> After pressing ENTER (this pushes the OK button) the dialog box will disappear and you should see the current matrix has changed to the new 3x4 size, but it is still filled with all 0's. Note the center of the top window title frame shows "3x4". Also, the entry in the (1,1) position has a blinking cursor under it. The lower left corner of the window frame should show "1:1" which gives the Row:Column position of the edit cursor. Press to cause another dialog box to appear, one which is used to edit the element that was under the cursor. When the Edit Element dialog box appears, select the Help pushbutton. With a mouse you can simply click on the Help button, but without a mouse you can press either + or A Help window will appear on the screen which gives information about using the dialog box to edit an element. Read all of the information about editing an element. When you get to the bottom of the help window you can use the down arrow key to scroll the window contents. Or, with a mouse you can employ the scroll bar down arrow to scroll the window. The scrolling stops when there is no more information below the bottom window edge. Read all the information. Read the information in the status line at the very bottom of the screen. The status line hint tells how to quit help. With a mouse you can click the close box in the upper left window title frame, or with a keyboard press to quit Help and return to the edit dialog box. Press <4> to enter the coefficient on X in the first equation. After pressing Enter the dialog box goes away and the edit cursor position will automatically shift to the second element in the first matrix row. The indicator in the lower left window frame corner should show "1:2". An asterisk character also appears to the left of the row indicator and is used to remind you that you have manually edited the matrix, and that you have not saved this matrix in a disk file. The asterisk appears after editing any entry and disappears when you save the matrix in a disk file. Again, press to bring up the edit dialog box, then press <6> to change the coefficient on Y in the first equation. Note how the edit position cursor automatically switches to the next matrix element to be edited. Continue entering the numbers in the first row by typing <-> <8> and <8> The first row should now be completely entered, and the edit position cursor should be down in the second row, but in the first matrix column. "2:1" Enter the second row of numbers by typing <2> <5> <4> <1> <6> Finally enter the last row by typing <5> <-> <3> <1> <0> <-> <2> <2> In this tutorial file we will show matrices within brackets and, where appropriate, we will show broken line partitions within the matrix. But the matrices you see on the screen should appear as a plain array of numbers without brackets or partition lines. The MATRIX program can hold a matrix up to 20x20 in size. All of our sample problems will deal with much smaller matrices and they will all fit on one screen display. The program automatically formats each matrix for the screen display. For those unusual cases in which the matrix is too large to fit in the window, the program will automatically attach scroll bars to the window and then you can scroll any other non-visible parts of the matrix into view. Before solving this system we are going to duplicate the matrix in a new window. Select the command MODIFY | DUPLICATE MATRIX A new window will appear on the desktop which holds a copy of the original 3x4 matrix. The new window is usually relatively small. WINDOW MANAGEMENT ================= We would next like to demonstrate how to move and resize this new window. Note the shape and color of the window frame. Then select the command WINDOW | MOVE/RESIZE WINDOW (With a keyboard +) The window frame should change and if you now use the four arrow keys on the keyboard you should be able to move the window anywhere, up or down or left or right on the desktop. The Status Line indicates the use of the arrow and shift keys. Now move the window so it is nearly in the center of the entire desktop and then start holding down and continue to hold a key while you press the arrow keys. You should now see the window size is being changed. The right arrow key makes the window wider, the down arrow key makes it taller. The left and up arrow keys have the opposite effects and make the window smaller. If you let up on the SHIFT key and continue to press the arrow keys the window position changes. To quit the moving and resizing you would normally press ENTER, but don't do this yet. Size the window so that you can see all of the matrix entries and make the window width relatively wide (2/3 of the desktop width) so that there is extra space in the left and right window margins. Make the window height relatively short, so that only the three rows and a top and/or a bottom blank line appear in the window. Move the window down on the desktop so that it is sitting just above the Status Line. This should leave a lot of blank space near the top of the desktop, just under the Menu Bar. Then press to fix the size and shape of the window. The window frame should now be a highlighted double line. If you have a mouse, you can move the window position by grabbing and dragging the the top of the title frame. You can reshape the window by grabbing and then dragging the lower right window frame corner. In any case, leave some room at the top of the screen just under the Menu Bar. CONTROLLING THE SPEAKER ======================= The program normally beeps after it finishes any calculation. If this beeping of the speaker bothers you, you can turn the speaker permanently off by selecting the command OPTIONS | SPEAKER... which brings up a dialog box. This dialog box allows you to control the use of the speaker. Press to close the Speaker Control Dialog Box. SOLVING THE SYSTEM ================== Before solving the system we need to set an operational mode of the program so that it displays row operations. This mode is called the Instructional Mode and it is selected by giving the command OPTIONS | AUTO/INSTRUCTIONAL MODE A new dialog box should appear which contains two radio buttons. The top button selects what is called the Automatic Mode. The bottom button controls the Instructional Mode. You can select the bottom item by either pressing + or by pressing a down arrow key. With a mouse you can simply click anywhere on any of the text that is in the second line. "( ) Automatic Mode (Does not show row operations) (*) Instructional Mode (Pauses for each row operation)" Then to return to the desktop, press which is the same as selecting the OK pushbutton. To begin solving the system select the command ALGORITHMS | ROW REDUCE The program should then change and show a dialog box at the top of the screen. The message displayed in the dialog box shows "Think ?" to prompt you to think of the row operation you would perform next if you were solving the system. Press to see the first row operation the computer has selected. The dialog box at the top of the screen should show "(1/4)*(Row 1)" With a mouse click the Ok button, or with a keyboard press and the matrix below should change and appear as: +- -+ | 1 3/2 -2 | 2 | | | | | 2 5 4 | 16 | | | | | 5 -3 10 | -22 | +- -+ Note the 1 in the M(1,1) position. In this tutorial file, as in the program, individual matrix elements will be referred to by writing the capital letter M immediately followed by the ordered pair which gives the element's position in (row,column) format. This first row operation has changed the entire first row in the matrix. Again, a "Think ?" message appears. Press to see the second row operation. "(-2)*(Row 1) + (Row 2)" Press to see the subsequent matrix after the 2nd row operation has been performed. The middle row has changed. +- -+ | 1 3/2 -2 | 2 | | | | | 0 2 8 | 12 | | | | | 5 -3 10 | -22 | +- -+ Press to see the next row operation. "(-5)*(Row 1) + (Row 3)" Press to see the subsequent matrix. The 3rd row has changed. +- -+ | 1 3/2 -2 | 2 | | | | | 0 2 8 | 12 | | | | | 0 -21/2 20 | -32 | +- -+ The upper left 1 has been used again to eliminate the two numbers below it. The program has completed all the work in the first column. Now think of the next row operation you would perform and then press to see the first row operation the program has selected for the 2nd column. "(1/2)*(Row 2)" and continue to press to see the resulting matrix. +- -+ | 1 3/2 -2 | 2 | | | | | 0 1 4 | 6 | | | | | 0 -21/2 20 | -32 | +- -+ We now have a 1 in the second column in the second row. Press The next row operation is "(-3/2)*(Row 2) + (Row 1)" Press The subsequent matrix is +- -+ | 1 0 -8 | -7 | | | | | 0 1 4 | 6 | | | | | 0 -21/2 20 | -32 | +- -+ The 1 in the 2nd column is being used to eliminate the numbers above and below it in the same column. Press The next row operation is "(21/2)*(Row 2) + (Row 3)" Press and you should see the matrix +- -+ | 1 0 -8 | -7 | | | | | 0 1 4 | 6 | | | | | 0 0 62 | 31 | +- -+ Press The next row operation is "(1/62)*(Row 3)" Press and the subsequent matrix should appear as +- -+ | 1 0 -8 | -7 | | | | | 0 1 4 | 6 | | | | | 0 0 1 | 1/2 | +- -+ Note how this last operation has placed a 1 in the 3rd column. This 1 will now be used to eliminate the -8 and 4 above it. Press The next row operation is "(8)*(Row 3) + (Row 1)" Press and the next matrix should be +- -+ | 1 0 0 | -3 | | | | | 0 1 4 | 6 | | | | | 0 0 1 | 1/2 | +- -+ Press The final row operation is "(-4)*(Row 3) + (Row 2)" Press and the final matrix is +- -+ | 1 0 0 | -3 | | | | | 0 1 0 | 4 | | | | | 0 0 1 | 1/2 | +- -+ Note the distinct pattern of 0's and 1's. When you press the program sounds a short beep to indicate it is finished performing row operations. The dialog box at the top of the screen will disappear. We would interpret the solution from the final matrix as X = -3 Y = 4 Z = 1/2 COMPUTING A DETERMINANT ======================= We will now select the previous matrix window. With a mouse you can simply click the background window. With a keyboard press The active window always has a number in the upper right hand corner of the title frame. This number will always be between 1 and 9, since the program allows a maximum of 9 matrix windows. At any time you can press Alt+n to select the window numbered n and make it the active window. The current window should be numbered 1 in the upper right corner and you should see the matrix +- -+ | 4 6 -8 | 8 | | | | | 2 5 4 | 16 | | | | | 5 -3 10 | -22 | +- -+ Since determinants are defined for square matrices only, we will first delete the rightmost column. Select the command MODIFY | DELETE COLUMNS A new dialog box appears in which you specify the range of columns to be deleted. In this case it is only the 4th column that needs to be deleted and the default parameters should specify only the last column. So press (that's the equivalent of pressing the OK pushbutton) and note the new matrix is only 3x3 and it appears as +- -+ | 4 6 -8 | | | | 2 5 4 | | | | 5 -3 10 | +- -+ We still have the Instructional Mode turned on, but for the next demonstration we want to select the Automatic Mode. So give the command OPTIONS | AUTO/INSTRUCTIONAL MODE and when the dialog box appears change to the Automatic Mode. With a keyboard you can press + or with a mouse you can click anywhere in the line of text for the Automatic Mode. Press the OK button by typing Finally, select the command ALGORITHMS | DETERMINANT and an information box will appear in which the determinant has a value of 496. Computing determinants using this command is painless! Press to make the information box disappear. Note that the original matrix was left unchanged by the determinant calculation. FINDING A MATRIX INVERSE ======================== Next we will demonstrate how to find the inverse of a square matrix. First select the command MODIFY | DUPLICATE MATRIX to make a copy of the current matrix. Then select the command ALGORITHMS | INVERSE and you should see a new matrix window created that holds the inverse of the matrix that was in the active window at the time you executed the inverse command. The inverse should be +- -+ | 1/8 -9/124 4/31 | | | | 0 5/31 -2/31 | | | | -1/16 21/248 1/62 | +- -+ The inverse should be in a window numbered 4 in its upper right frame corner. FINDING AN INVERSE THE OLD FASHIONED WAY ======================================== Now make window number 1 the active window by pressing key Then give the command MODIFY | DUPLICATE MATRIX The new copy is in a small window. With a mouse click the zoom button in the upper right window frame corner, or with a keyboard press so that the window is maximized and fills the entire desktop. The other matrices will be hidden from view, but any one of them may be re-activated at any time. The MATRIX program has a couple of features that aid in finding and verifying the inverse of a matrix. We assume you are already familiar with the matrix theory of inverses. To use MATRIX to demonstrate the algorithm, select the command MODIFY | APPEND IDENTITY Note the window title frame shows the size of the new matrix is "3x6". +- -+ | 4 6 -8 | 1 0 0 | | | | | 2 5 4 | 0 1 0 | | | | | 5 -3 10 | 0 0 1 | +- -+ Now we can automatically perform the row operations that will yield the inverse. Select the command ALGORITHMS | ROW REDUCE The program will beep and display the following matrix +- -+ | 1 0 0 | 1/8 -9/124 4/31 | | | | | 0 1 0 | 0 5/31 -2/31 | | | | | 0 0 1 | -1/16 21/248 1/62 | +- -+ The 3x3 matrix on the right is the inverse of the original 3x3 coefficient matrix. Now give the command MODIFY | SWAP HALVES and you should see +- -+ | 1/8 -9/124 4/31 | 1 0 0 | | | | | 0 5/31 -2/31 | 0 1 0 | | | | | -1/16 21/248 1/62 | 0 0 1 | +- -+ which shows the left and right halves have been exchanged so that the identity matrix is now on the right, and the inverse is now on the left. SOME DISPLAY OPTIONS ==================== The default operating mode of the program uses fractions, but sometimes you may wish to see results in decimal form. While looking at the matrix select the command OPTIONS | DISPLAY DECIMALS and the matrix display should switch to show the entries as decimals. The default number of decimal places displayed is 5. +- -+ | 0.125 -0.07258 0.12903 | 1. 0. 0. | | | | | 0. 0.16129 -0.06452 | 0. 1. 0. | | | | | -0.0625 0.08468 0.01613 | 0. 0. 1. | +- -+ After viewing the decimals, select the command OPTIONS | DISPLAY FRACTIONS and the matrix entries will be redrawn as fractions. So converting between decimals and fractions is quick and easy. Next, select the MODIFY | DELETE COLUMNS command and when the dialog box appears type <4> <6> to leave the inverse as a "3x3" matrix. MORE WINDOW MANAGEMENT ====================== At this point we have 5 matrices on the desktop, but you can't see the ones that are hidden behind the maximized window. So give the command WINDOW | TILE ALL WINDOWS and you should see the 5 matrices in windows that cover the entire desktop like tiles cover a floor. To verify the matrix in window number 5 is the inverse of the matrix in window 1, we will next multiply the two matrices. Select the command ALGORITHMS | INTER-MATRIX OPERATION A new dialog box will appear. This dialog box has several controls, the first of which is a series of radio buttons which are used to select the desired operation. Select the 4th item which is to multiply two matrices. +<4> Then you need to enter the window numbers of the two matrices that will be multiplied. Press + <1> <5> When you are ready to execute the operation press the push button labeled as "Perform Operation". Since this is the default button, pressing will do the trick. Yet another new window gets created which holds the product of the two selected matrices. The new window is numbered 6 and it should contain the 3x3 identity matrix. Sometimes when you have several matrices on the desktop you wish to see all the window title frames without tiling all the windows. Select the command WINDOW | CASCADE ALL WINDOWS and you should see the 6 matrix windows stacked one on top of the other, but in a cascaded form. You could now press key F6 several times to select each window in turn. Now select the command WINDOW | TILE ALL WINDOWS and this time all 6 windows are tiled on the desktop. Before beginning the next problem we are going to clear the desktop by closing all the windows. With a mouse you can click on each close box in each upper left window frame, or with a keyboard you can repeatedly press + As each window disappears its window contents are lost. If you wanted to save a matrix in a file, you could give the FILE | SAVE AS command. The desktop should now be entirely blank. SOLVING A STANDARD LP PROBLEM ============================= One of the more significant features of the MATRIX program is its ability to solve both standard and non-standard linear programming problems via the Simplex Algorithm. We assume you are familiar with linear programming problems as well as the Simplex Algorithm so no fundamental explanation of these concepts will be given. There are several apparently different ways of representing linear programming problems. Assuming you are already familiar with the Simplex Algorithm you should be able to follow what the MATRIX program does. Of significance is that the signs of the objective function coefficients are stored with opposite signs from the coefficients you enter. These will appear in the bottom row of the matrix. Before you can use the program to solve a linear programming problem you must determine the objective function and the system of constraints. We define a problem to be in standard form when the objective function is to be maximized and when all the variables are nonnegative and all the constraints are written as being less than or equal to nonnegative constants. A problem will be considered nonstandard if it involves an equation or a greater than or equal to inequality, or if the objective function is to be minimized. The MATRIX program will automatically handle any combination of the three possible types of constraints (i.e., less than, or equals, or greater than) that occur in linear programming problems. The program is therefore capable of solving nonstandard problems that go beyond the standard problems one normally finds in textbooks. You can enter any mixture of constraints in any order. The program always assumes the objective function is to be maximized, but this is in no way a limitation on minimum problems. If you have a minimum problem then enter your objective function coefficients as usual but check the radio button which indicates this is a minimum type of problem. Internally, the program will assume you entered -f for the objective function because minimizing f is exactly the same problem as maximizing -f. In the case of a minimum type of problem the program will automatically change the signs of f's coefficients for you. The program always provides complete slack variable information in the matrix so the values of dual problem solutions are readily available. There is no need to construct a transpose for a dual problem. The MATRIX program really handles both maximizing and minimizing problems. The MATRIX program also attempts to warn you when you give it a problem that is unsolvable. The two cases detected are either an empty region of feasible solutions or an unbounded objective function. If the constraints you enter are inherently inconsistent then the region of feasible solutions will be empty and the program will inform you when that is the case. The other extreme is that at least one variable is unbounded by the given constraints. This doesn't always mean there is no solution to your problem, although that is usually the case. If your objective function grows without bound the MATRIX program will warn you. It is possible to contrive examples where the region of feasible solutions is unbounded and yet the objective function remains finite and in fact constant. In these cases the program will give you one correct solution but no warning about the nature of the region of feasible solutions, or the fact that the given solution is not unique. Of course it is also possible that the region of feasible solutions is finite (bounded) and yet there are still an infinite number of solutions which all lie on one edge of the region. In these cases the program will supply only one solution but it won't warn you that the solution may not be unique. So if your problem doesn't have a solution the program will tell you that is the case and it will explain why that is the case. If your problem has at least one solution the program will find one, but it won't tell you when more than one solution is available. Actually, there is one kind of problem that MATRIX doesn't handle. It is theoretically possible for the Simplex Method to stall in an infinite repeating cycle in which the objective function remains constant. Such problems are exceedingly rare in real applications and are almost as rare in theory. In fact, it is possible to construct a theoretical problem that should cycle, but due to round off error in floating point calculations on digital computers the cycling phenomena is by-passed. This is one case where a little round off error is helpful. To appreciate how rare cycling is you should try searching the available literature to find a problem that cycles. The author of MATRIX used the Simplex Method on a casual basis for 10 years before he encountered a text with an actual example! Many texts mention the possibility of degenerate problems that cycle, but very few give a simple concrete example to demonstrate the phenomenon. It is historically interesting that George Dantzig developed the Simplex Algorithm in 1947 but the first constructed example of cycling wasn't published until six years later in 1953 by A. J. Hoffman. One problem at the end of the LP examples in this tutorial is a cycling problem published by E. Beale in 1955. It is not an easy matter to construct an example that cycles. As an example of a simple standard linear programming problem, consider the following. A cat breeder supplies cat food in the form of chicken, tuna, and liver. The breeder makes a profit of 20 cents on each can of chicken, 22 cents on each can of tuna, and 18 cents on each can of liver. The breeder's stockroom will only hold 2,700 cans total. To satisfy the peculiar dietary habits of the clientele the breeder must limit the total amount of sugar and salt content in the three kinds of cat food. Assume each can of chicken, tuna and liver contains 4mg, 6mg, and 5mg respectively of salt and 8mg, 9mg, 2mg respectively of sugar. The total limitation on salt is 14 grams while that on sugar is 18 grams. How many cans of each kind of cat food should the breeder stock to maximize the total profit and satisfy all of the above constraints ? We must transform the information in the above problem into a list of linear inequalities and we must form the objective function. Let X = the number of cans of chicken Y = the number of cans of tuna Z = the number of cans of liver Then X + Y + Z <= 2700 (space restriction) 4X + 6Y + 5Z <= 14000 (salt restriction) 8X + 9Y + 2Z <= 18000 (sugar restriction) and the profit (objective) function is given by P = 20X + 22Y + 18Z Note that we have 3 variables and 3 constraints. Give the command ALGORITHMS | START A NEW LP PROBLEM and you will see a dialog box into which you are to enter the number of variables and the number of constraints. Type <3> <3> Next the program will prompt you for the constants (coefficients) in the system of inequalities. Note that instead of using the letters X, Y, and Z for variables, the program numbers the variables as X1, X2, X3, etc.. The program also numbers each constraint but the order is immaterial and the numbering is given only to help you keep track of which constraint you are currently entering. The dialog box which is used to edit the constraint information contains several controls. There is a large list box on the left which contains the current values of the coefficients of all the variables. To the right is a series of 3 radio buttons which are used to select the type of constraint (i.e. <=, =, or >= ). An edit line near the bottom right corner holds the constraint constant bound. In the lower left corner is the identification number of the constraint. The operation of the list box is unusual in that you can only temporarily select any coefficient it holds. The reason is that as soon as a coefficient is selected for editing, that coefficient gets copied into the edit line that appears in the upper right dialog box corner. The text line above this edit box describes the contents of the edit box. Below the edit box is a push button with the label "Update Edited Coeff.". The idea is that you perform all editing of a coefficient within the edit box, and when finished editing, press the Update button and your edited number will appear in the list box on the left. But as soon as the list box receives an edited item, it automatically selects the next item in its list, and it sends that item to the edit box which receives it. The edit box title always tells you which item the edit box contains. The item highlighted within the list box is the one that gets updated when you press the Update Edited Coefficient push button. Thus the list box, the edit box, the edit box title, and the update push button all work in concert to make what could be called a multi-line edit box. But in fact, there is only one edit line, and all editing is done within the edit box. We are now editing the first constraint. The coefficient on X1 has already been selected for editing. So type <1> then press the push button "Update Edited Coeff.", with a keyboard, + The number 1 should now appear as the first item in the list box, and the coefficient on X2 should automatically be selected for editing. Again type <1> and press the Update button. + The coefficient on X3 is now selected for editing. Type <1> and press the Update button. + Now all three variable coefficients have been entered. You should see three 1's in the list box on the left. Select the first radio button on the right which corresponds to selecting a less than or equals constraint type. + Then select the edit box to enter the constraint bound constant. + Then enter the constant <2> <7> <0> <0> Note that when entering large integers you DO NOT use commas to separate digit groups. When everything for the first constraint is entered as it should be press which removes the dialog box for the first constraint. You will then be prompted to enter all the information for the second constraint. Note the constraint number in the lower left corner. For the second constraint variable coefficients press <4> + <6> + <5> + Press + Then select the constant bound + and enter the constant. <1> <4> <0> <0> <0> Press to make the changes permanent. Then enter the third constraint information. Press <8> + <9> + <2> + + + <1> <8> <0> <0> <0> and press to make the changes permanent. After all the constraint information has been entered you will be asked to enter the objective function coefficients. The list box and edit controls in this dialog box operate similar to those in the constraint dialog boxes. The radio button which indicates the problem is a maximum type of problem should already be checked, so you don't need to change the radio button for this example problem. Note the dialog box title line shows "Edit Objective Function" Type <2> <0> + <2> <2> + <1> <8> + After the last objective function coefficient has been entered press and the new matrix will show the initial simplex matrix. Of course the partition lines won't appear on the screen display. We will always show three partition lines within each LP matrix. The leftmost of the two vertical lines separates the original variable coefficients from the slack and artificial variable coefficients. The rightmost vertical line separates the constraint bounds from the slack and artificial variable coefficients. The objective function coefficients are below the single horizontal partition line. +- -+ | 1 1 1 | 1 0 0 | 2700 | | | | | | 4 6 5 | 0 1 0 | 14000 | | | | | | 8 9 2 | 0 0 1 | 18000 | |----------------+-----------------+---------| | -20 -22 -18 | 0 0 0 | 0 | +- -+ The program has automatically changed the signs of the objective function coefficients. The remainder of the last row has been filled with 0's. The constraint bound constants form the upper part of the right-most column and a 3x3 identity matrix has been inserted in the middle to represent slack variable coefficients. The lower-right corner shows the current value of the objective function which is initially 0. Before performing the Simplex Algorithm we need to turn on the Instructional Mode. So select the command OPTIONS | AUTO/INSTRUCTIONAL MODE and once the dialog box appears turn on the Instructional Mode radio button. + Press to terminate the dialog box. We should also move and resize the window so that we leave room at the top of the screen for displaying information. Make the window height relatively small. (Ctrl+F5 selects the WINDOW | MOVE/RESIZE command. ENTER quits the mode as indicated by the Status line hint.) Now to perform the Simplex Algorithm select the command ALGORITHMS | PERFORM SIMPLEX ALGORITHM The program will select the pivots and the row operations one step at a time. You should try to locate the next pivot position. Then when you press ENTER to continue you can compare your selection with that of the program. You should see the message "Think ?" Think of where the first pivot should be and then press to continue. The next screen should show the matrix together with the first pivot information. "The next pivot is at M(3,2) Objective Function Value = 0" Note the position of the first pivot and then press and you should see the program's choice for the first row operation. "(1/9)*(Row 3)" This operation should make the current pivot element turn into a 1. After pressing you should see the next matrix and you should think of the next row operation to be performed. As you continue, the program should use the 1 as the pivot and it should perform a series of row operations to make 0's in the pivot column above and below the 1. When finished with the current pivot column the program should stop to display the new value of the objective function and it should indicate the position of the next pivot. Keep pressing to continue the solution. For the current problem the second pivot information should appear as "The next pivot is at M(2,3) Objective Function Value = 44000" The initial value of the objective function is always 0 and as you reach each new pivot if the value changes at all it will increase. Keep pressing and follow the solution step by step. The 3rd pivot information should appear as "The next pivot is at M(1,1) Objective Function Value = 1688000/33" When the 3rd pivot is finished the program will sound a beep and then display the final solution in a dialog box as shown below. "X1 = 700 X2 = 1200 X3 = 800 Any slack variables not shown above are 0. Objective Function Value = 54800" Slack variable values are not shown unless they occur as basic variables. (There are none in the above problem). We would interpret the above solution for the given problem as indicating that the breeder should plan on using 700 cans of chicken, 1200 cans of tuna, and 800 cans of liver. The profit in pennies will be 54,800 or in dollars, $548.00. In the unlikely event that you should give it a problem that it determines it cannot solve it should sound a beep and then display an explanatory message. As previously discussed, the program will detect and report a failure when the region of feasible solutions is empty because the system of constraints is inconsistent. When both the region of feasible solutions and the objective function are unbounded the program will report the first variable that it finds that is unbounded. Of course variables other than the one the program reports may also be unbounded, so you should not assume there is a problem with only the reported variable when the program stops because the objective function is unbounded. As a last comment about unusual problems, we give the following problem which cycles. (See E. Beale, Naval Research Logistics Quarterly 2:269-275, 1955) Maximize 0.75X - 20Y + 0.5Z - 6W subject to 0.25X - 8Y - Z + 9W <= 0 0.5X - 12Y - 0.5Z + 3W <= 0 Z <= 1 This famous problem demonstrates the phenomena called cycling. You should only try to work this in the Instructional Mode. Keep track of the first matrix and compare it with the 7th matrix. To quit press the ESC key instead of the ENTER key. If you are not in Instructional Mode the program will cycle forever, but you can press the keys CONTROL+BREAK to abort any long time-consuming operation. MANUAL ROW OPERATIONS ===================== You may wish to select your own row operations. To do this you can select the command ALGORITHMS | SINGLE ROW OPERATION You can perform one of three kinds of row operations. Type 1. Interchange any two rows Type 2. Multiply a single row by a non-zero constant Type 3. Add a multiple of one row to another No matter which type you select, the program will further prompt you for the parameters associated with each row operation and all you need do is follow the instructions on the screen. A NOTE FOR TEACHERS =================== The MATRIX program can be used by teachers to create problems that will have known simple solutions. This is especially important if you use the program to make test problems. If you select test questions from books you can use the MATRIX program to check that the problems have "nice numbers". Otherwise you may face the wrath of your students. If you have not already thought of the following applications you should know that the MATRIX program can be used to work backwards from known solutions to create original problems. In creating systems of linear equations one trick is to start with a known simple row reduced echelon form and then perform manual row operations (type III) that appear to scramble the final solution. If you start with a simple enough form and perform row operations with whole numbers to fill in the 0's you should be able to create some nice problems. In fact you can set up inconsistent systems or create other resourceful solutions. Finding matrices with "nice" inverses is a natural for the MATRIX program. Simply start with the identity matrix which is known to have a determinant equal to 1 and perform type III row operations that involve integers only. The scrambled matrix is then guaranteed to have an inverse with integer entries only. Of course when the student attempts to find the inverse they may run into fractions but the final inverse solution will contain integer entries only. The justification of this technique depends on the inverse formula that uses the adjoint and the reciprocal of the determinant, and the fact that type III row operations don't alter the determinant. It is also possible to create linear programming problems with simple solutions by choosing an optimal solution to begin with. Assign the variables their final values. Then form a series of inequalities choosing arbitrary coefficients. Choose the constraint bounds so that the solution exactly satisfies each constraint. Choose the objective function coefficients last. Of course there may be other solutions that are more optimal but by increasing or decreasing the objective function coefficients you can force the solution to head in the direction needed to arrive at your chosen solution. The MATRIX program is a valuable tool for the creation of problems with "nice numbers". You are limited only by your creativity and imagination. DISK FILE FORMATS ================= When you save a matrix to a disk file, the matrix is saved in an ordinary ASCII text file which can be edited with your favorite word processor. You can learn the disk file format by using the program's Save As function and studying the resulting file. The format is fairly free form. Spaces in the file are ignored when the file is read. The first line should contain the size of the matrix. The second line contains display mode information which differs for decimals & fractions. The lines following the header information list the matrix elements, one per line. Your file can have empty lines to space the elements, usually by rows. However, each element line has its position explicitly specified, so elements can appear in the file in any order. Elements not directly specified will be assumed to be 0. Thus, only nonzero elements are necessary to be in the file, but this program will also write 0's when it saves a file. Once you understand the file format, you can create demonstration matrix files using just about any word processor, independent of this program. If you save a matrix that is a Linear Programming (LP) problem, the matrix file format is similar to that for a regular matrix, but the file contains state information as well as information about slack and artificial variables and the objective function coefficients. The state information and the information about the slack and artificial variables is critical for the program to be able to properly interpret the disk file. You can save LP problem matrices and then study the file format. CONCLUSION ========== This concludes the MATRIX program tutorial. If you haven't done so already, you can now read the help information. Many of the basic features have been covered here, but you will gain more insight by reading all the help information available to you. If after all this you still have questions, you can contact the author at the address given below. To quit the MATRIX program press + The MATRIX program is periodically updated to make improvements, add new features, (and sometimes to correct bugs!). You may also wish to contact the author to check if you have the latest version of the program. The author also invites your comments about how you liked the program and will consider any suggestions you may wish to offer for making the program even more useful. OTHER PROGRAMS ============== If you enjoy using the MATRIX program you may be interested to know there is a whole suite of mathematical programs made by the author of MATRIX. These programs are intended to help motivate an interest in mathematics and computer science. Some of the titles of these programs and a brief description of each is given below. 1. MATRIX - a program that teaches row operations with matrices. Features include fractions and decimal modes, determinants, inverses, Gram-Schmidt orthogonalization, eigenvectors and eigenvalues and both standard and non-standard linear programming problems. 2. YFUNX - a program for graphing and analyzing functions in rectangular form, Y=F(X). Includes coordinate trace and tangent/normal line modes, zooming in and out, scalable axes, numerical integration including the standard approximations together with Gaussian Quadrature and Romberg approximations. Animation features include plane areas, plane arc length, 3D volumes and 3D surface areas, Newton's Method and the Method of Successive Bisections for solving F(X)=0, and automatic search for max/min extrema. 3. POLAR - a program for graphing and analyzing functions in polar form, R=F(@) or R^2=F(@). Similar to YFUNX, includes coordinate trace and tangent/normal line modes, zooming in and out, scalable axes, numerical integration for polar areas and arc length, automatic search for max/min extrema over any section of a curve. 4. PARAM - a program for graphing and analyzing functions in parametric form, X=F(T) and Y=G(T). Similar to YFUNX, includes coordinate trace and tangent/normal line modes, zooming in and out, scalable axes, numerical integration for areas and arc length, automatic search for max/min extrema over any section of a curve. 5. POLPM - a program for graphing and analyzing functions in polar coordinates, but that have been parametrized, say R=F(T) and @=G(T). Similar to the POLAR and PARAM programs, this program includes coordinate trace and tangent/normal line modes, zooming in and out, scalable axes, numerical integration for areas and arc length, automatic search for max/min extrema over any section of a curve. 6. DIFEQ - a program related to 1st order differential equations. Includes graphing the direction field and solves initial value problems using Euler methods and a 4th order Runge-Kutta method. Includes coordinate trace mode, zooming in and out, and scalable axes. 7. CURVE3D - a program for making 3D graphs of curves given in the parametric form X=f(t), Y=g(t), and Z=h(t). The resulting curve may be viewed from any position, and the drawing is a true-perspective 3D picture. 8. SURF3D - a program to graph 3-dimensional surfaces of the form Z=F(X,Y). The resulting surface may be viewed from any position, and the drawing is a true-perspective 3D picture. The surface may be displayed using lines of constant x, or constant y, or a fishnet. Included is a hidden line algorithm for more realistic pictures. 9. CFIT - a program which performs curve fits to data. Includes linear regression for linear, exponential, logarithmic, and power functions. Graphs scatter diagrams and the fitted function curves and performs a statistical analysis, including an automatic best fit selection. Data may be saved to or read from disk files. 10. GALTON - simulates coin tossing experiments related to probabilities and demonstrates graphically a binomial distribution and its relation to the standard normal Gaussian bell-shaped curve. Also compares results with the numbers generated by Pascal's Triangle. Either coins or ping-pong balls may be used in simulated experiments. 11. PROPC - a symbolic logic program that calculates truth tables, analyzes tautologies, parses infix formulas and displays their Polish notation form, and generates Karnaugh maps from either tables or formulas. 12. RPNDEMO - a program which simulates how a calculator with RPN logic works. This program includes its own language and is similar in power to the HP-41 calculator. Programs may be animated to show the internal workings of the machine. Can also be used to teach assembly language concepts. 13. CALC - a reverse Polish logic calculator that operates on 5 data types. Included are real and complex numbers, fractions, binary integers and polynomials. Special features include factoring integers and polynomials, analyzing repeating decimals and working with continued fractions. 14. LOAN - a finance program that handles the two standard cases of compound interest. Uses the 5 standard financial variables n i PV PMT FV found on most financial calculators. Can determine payment schedules for loans and annuities and can print amortization schedules for loans. 15. FCARD - simple flash card type of program that can be used to memorize any simple series of facts, with one item per line of text. Items can be presented in a random order with timing if desired. 16. THANOI - an example of a recursive process that is in the form of a game known as the Towers of Hanoi game. 17. TRIANGLE - a simple program which solves triangle problems in which one is given 3 facts about a triangle and must solve for all the remaining parts. Handles all 19 cases of triangle inputs and includes the Law of Cosines and the ambiguous case of the Law of Sines. Can automatically determine and display a 2nd valid triangle solution. 18. EXPMCON - a utility type of program that works with the above MATRIX program and the commercial scientific word processor called EXP. This program converts MATRIX files from an ASCII format to the EXP format. 19. BMPLOT - a utility type of program that makes high resolution monochrome bitmap function plots, identical to the kinds of graphs made by the programs YFUNX, POLAR, PARAM, and POLPM. The bitmaps may be read into other programs such as paint or drawing or desktop publishing programs which can be used to add labels and titles. The monochrome bitmaps may be of any size or resolution. The file formats supported include PCX, TIFF, and BMP. Even the HP-GL/2 plotter language can be used to make a graph on any PCL 5 LaserJet printer. 20. XPRES - a simple program which computes large integers. Numbers may contain up to 20,000 digits. The program computes exact values of factorials, permutations, combinations, and powers of integers. You can use this program to compute 1000! exactly or to compute the exact value of 999 raised to the 1000th power. Numbers may be saved to or read from disk files. For more information about any of these programs contact the author at the address below. John Kennedy Mathematics Department Santa Monica College 1900 Pico Blvd. Santa Monica, CA 90405 Phone (310) 450-5150 Ext. 9721 A message may be left at any time of day or night. You may also send a self-addressed stamped envelope with a single 1.44MB high density 3 1/2 floppy disk that is pre-formatted with nothing on it and as many useful programs as will fit on the disk will be returned to you.