ProfitPress Mega CDROM2 Shareware Freeware (MSDOS)(1992)(Eng)

home *** CD-ROM | disk | FTP | other *** search

/ ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng) / ProfitPress-MegaCDROM2.B6I / MISC / EDUCATIO / TSLIN33.ZIP / LINSOLVE.LIS < prev next >

Wrap

File List | 1990-12-16 | 27.6 KB | 614 lines

- 1 - 16th December, 1990 (Ver 3.3) CONTENTS: page 1. About TSLIN in General 1 2. Introduction 2 3. Linear Programming 2 4. Sensitivity Analysis 3 5. Floating Point Significance 4 6. Linear Goal Programming 4 7. Specialist's Corner 5 8. Other Computers and Programs 6 9. Release Notes for linsolve 6 10. Selected References on Linear and Linear Goal Programming 12 1. About TSLIN in General ========================= Apply a question mark ? with the program call for the description of the program, i.e. use LINSOLVE ? for the short instructions. The public domain version of the TSLIN package may be used and distributed freely for NON-COMMERCIAL, NON-INSTITUTIONAL, PRIVATE usage, provided it is not changed in any way (with the potential exception of changing the packing method). For ANY other usage, such as use in a business enterprise or at a university for your lectures or similar purposes (and/or the larger version), please contact the author for registration. No unauthorized charge for distributing this program is allowed. No part of the package may be distributed separately. Uploading to bulletin boards is encouraged. An individually registered version is strictly for the use of the registrant. An identical program may NOT be running on more than one computer at a time. Likewise a site licensed copy must not be run on any machine outside the registered site. A registration gives the right to use the program as it is delivered. It does not cover tutoring or any other similar user support. The LINSOLVE program is under development. Comments and contacts are welcome. Feedback is solicited! Internet address: ts@chyde.uwasa.fi (preferred) Funet address: GADO::SALMI Bitnet address: SALMI@FINFUN FidoNet address: 2:515/1 (Micro Maniacs Opus; To: Timo Salmi). The author shall not be liable to the user for any direct, indirect or consequential loss arising from the use of, or inability to use, LINSOLVE or this package, or any other program or file howsoever caused. No warranty is given that the system will work under all circumstances. Timo Salmi Professor of Accounting and Business Finance School of Business Studies, University of Vaasa P.O.BOX 297, SF-65101 Vaasa, Finland .page - 2 - 2. INTRODUCTION LINSOLVE solves linear programming ('LP') problems interactively. LINSOLVE can also be used to solve linear GOAL programming problems. For more details, see the later pages. The current maximum capacity of a registered program is 120 decision variables, 80 constraints, and 10 objectives. Notice, however, that the public domain (PD) version will not handle more than 25 decision variables. You give your problem in an 'as is' facsimile format from a file or keyboard. The program will ask your choices for the options available. You have the choice of maximizing or minimizing, and even printing out the Simplex-tableaux should you so wish. 3. LINEAR PROGRAMMING Consider the following LP-problem (Name for row:) maximize z = 2X1 + 3X2 (Z) subject to X1 + 2X2 + X3 ≤ 13 (COND1) X3 = 5 (COND2) -X1 + X2 + 2X3 ≥ 8 (COND3) 3 ≤ X3 ≤ 6 (LO/UP) X1,X2,X3 ≥ 0 Write LINSOLVE to call the program. LINSOLVE first prompts for the method of input (keyboard or file), then for the constraints, and next for the objective(s). The problem is given to LINSOLVE in facsimile format from the console or an ordinary text file: COND1: X1 + 2X2 + X3 < 13 COND2: X3 = 5 !exclamation marks (!) can be COND3: -X1 + X2 + 2X3 > 8 !used to include comments LO: X3 > 3 !after and/or between rows UP: X3 < 6 END Z: 2X1 + 3X2 END !END can be replaced by LOPPU Each variable, constraint and objective must be named using a unique name. The name of a constraint, objective or variable can be up to 10 characters long. Each constraint (and objective) name must be followed by colon (:) to separate it from the rest of the row. .page - 3 - Spaces are ignored by the program. You can, of course, utilize spaces to clarify the structure of the problem. Lower and upper cases are not differentiated. (Thus e.g. "b" and "B" are treated the same.) The alphabet consist of A-Z, Å, Ä, and Ö. A row can be continued using an ampersand (&) or a star (*). E.g. the third constraint could have been given as COND1: X1 + 2X2 & + X3 < 13 LINSOLVE checks and reports syntax errors before proceeding to solve the problem. If the input is taken from a file, the program is aborted when the first error is encountered. If the task is entered from the keyboard, and the error is not fatal, LINSOLVE prompts for the relevant constraint (or objective) again. The program also prompts for the choice of output device (screen or file), whether the objective is to minimize (if not, then maximize), and whether the Simplex-tableaux are printed. Using systematic extension such as .SOL in the output file name is commendable if output is directed to a file. Output can be directed to the screen by giving CON, or no name at all, to the output file. 4. SENSITIVITY ANALYSIS LINSOLVE optionally performs a sensitivity analysis on the coefficients of the objective function, and the right-hand sides of the constraints. The sensitivity analysis for the objective function solves the range of objective function coefficients which retain the optimum solution. (The definition of retaining an optimum solution is that the variables in the basis remain the same. In the case of objective function sensitivity analysis, also the values of the optimum values of the variables remain unchanged.) The sensitivity analysis for the right-hand sides give their corresponding ranges retaining the optimum basis. (In this case, the values of the variables in the optimum basis would be changed.) The sensitivity analysis is only performed if certain conditions are met. First, it is limited to linear programming problems with one objective. Sensitivity analysis is thus not performed in the case of linear goal programming problems. Second, the analysis is performed only if the problem has a feasible, non-infinite solution. Third, although LINSOLVE can, and will, solve problems which have negative right-hand sides, no sensitivity analysis is performed for such tasks. .page - 4 - 5. FLOATING POINT SIGNIFICANCE When formulating the original LP problem do not use very large or small coefficients in the constraints or the objective(s). Although seldom recognized, this requirement is endemic in most linear programming codes. This results from the fact that the accuracy of real numbers is always more or less limited in computing, even if mathematically linear programming poses no problems. Thus, instead of e.g 400000X1 + 800000X2 < 2000000 or 0.004X1 + 0.008X2 < 0.02 use 4X1 + 8X2 < 20 In particular, do not to mix large and small coefficients in the same problem. In business applications, a change of unit of the variables is often a useful trick for avoiding problems caused by computers' limited accuracy. Also avoid the mistake of giving the same constraint twice, since such linear dependency can make the Simplex-algorithm fail. (Travelling salesman problems are particularly prone to these careless formulations.) If the program terminates in an error message: Runtime error 205 at xxxx:xxxx. which indicates a floating point overflow, it is not a failure of the program code, but a result of a bad scaling of your LP task. 6. LINEAR GOAL PROGRAMMING As with linear programming, it is assumed that the user is fully familiar with the concept of linear goal programming. If not, the text-books by Sang M. Lee (Goal Programming for Decision Analysis) and James P. Ignizio (Goal Programming) are recommended. See the references at the end of these instructions. Consider the following linear goal programming problem where P1 denotes the highest priority level. Note that the standard of goal programming is minimization. Minimize Z = P1(d2+) + 2P2(d1-) + 3P2(d2-) subject to X1 + 2X2 > 2 (ROW1) 4X1 + 2X2 + d1- = 4 (ROW2) 3X1 + 5X2 + d2- - d2+ = 3 (ROW3) X2 < 5 (ROW4) X1,X2,d1-,d2-,d2+ > 0 .page - 5 - The corresponding input to LINSOLVE should be ROW1: X1 + 2X2 > 2 ROW2: 4X1 + 2X2 + D1N = 4 ROW3: 3X1 + 5X2 + D2N - D2P = 3 ROW4: X2 < 5 END P1: D2N !Highest priority first P2: 2D1N + 3D2N END 7. SPECIALIST'S CORNER The Algorithm LINSOLVE applies the two-stage Simplex-method. (In linear goal programming a corresponding multiple-stage Simplex- method.) In both cases, artificial variables and objective (called "Extra" in LINSOLVE_EXE) are added to the problem. In the first stage the algorithm tries to get rid of the artificial variables. (If it can't, the solution of the original problem is not feasible. If this is the case, LINSOLVE duly reports the fact.) In the subsequent stage(s) LINSOLVE finds the solution to the problem given by the user. If the user requests LINSOLVE to print the Simplex-tableaux, the Extra objective and Extra variables are included. Similarly, the Extra objective appears on the listing of the optimum solution. (Its value will become zero, if the original problem has a feasible solution.) Altering the zero criterion The accuracy of the floating point arithmetic is eleven significant digits in the Turbo Pascal 5.0 (internal) arithmetic. Round-off errors tend accumulate in the Simplex-algorithm. To counter this fact, all elements less than a zero-limit (5E-6) are set to exact zero at each iteration. An experienced user may want to alter this limit. This can be done by giving the new value as the parameter of the program call. For example: LINSOLVE 0.0001 The optional statistics include the number of round-offs performed by the program. The smaller the figure, the less likely the problems due to the floating point arithmetic. .page - 6 - 8. OTHER COMPUTERS AND PROGRAMS The LINSOLVE program is also available for the Sinclair QL computer. It is part of a Public Domain library for QUANTA members. LINSOLVE has also been programmed for the VAX 11/750 computer at the Vaasa University, by the author, but the input and output commands of the VAX "TAVOPT" are in Finnish, and the program is not public domain. The origins of LINSOLVE date back to 1971 and IBM 1130 and my licentiate thesis in management science. The package for drawing LP programs and other figures in two dimensions, TSDRAW, is available separately for the PC. 9. RELEASE NOTES In version 1.1 a bug preventing the input of more than (only) eleven constraints was corrected. In version 1.2 the sensitivity analysis was added to the program. Also some minor improvements were made in the defaults, and the information about the solution, when the solution is directed to a file. The algorithm has been tested with more problems with known solutions. The rare special situations where the Simplex-algorithm is known to fail, have not yet been tested. (See notes on ver 2.1.) In version 1.3 some minor stylistic changes were made. In version 1.4 the possibility of entering a header on each page of output was added. If the very first line of the task starts with !! as in !!A tiny task E1: X1 + 2X2 < 2 END MAX: 3X1 + 5X2 END then the text "A tiny task" is used as a header for each page of output, if the output is directed to a file. !! indicates a header, a single ! an ordinary comment. In version 1.5 more error checks have been added to safeguard the user against giving input that could not be parsed into a proper LP format. E.g. it is now checked that a continuation row really follows after the use the the continuation marker (& or *) on the previous row. Version 1.6 introduces a built-in help to linsolve. Help can be invoked by entering ? when the program asks for input. From version 1.6 it is possible to use the Scandinavian characters (Å, Ä, Ö) in the variable, constraint and objective names. .page - 7 - Version 1.7 uses an improved directory utility. If the input file is not found, the user is given the option of listing directories on the screen without having to exit LINSOLVE. The directory mask (file definition) is now much more relaxed, and almost the same as for the MS-DOS dir command. More information on this feature can be found within the TSUTIL package. (See the TSPROG.INF file.) Version 1.8 introduces mostly internal changes not visible to the user. In version 1.9 an attempt to rewrite a read-only output file no longer crashes the program. Version 2.0 improves the speed of reading the problem from a file. Version 2.1: A linear programming problem can generally be stated as max cx s.t. Ax ≤ b x ≥ 0 Version 2.1 introduces an index of the accuracy of the solution. In linear programming computer implementations the round-off errors may cause problems, and even deviations from optimality. To assess the effect of these problems on the current task the final tableau the is recalculated from the inverse matrix of the base. Then the original solution tableau is compared with the recalculated tableau by defining four different (in)accuracy measures. These are the sum of absolute deviations in the left-hand side matrix A, the sum of absolute deviations in the solution vector b, and sum of absolute deviations in the simplex coefficients. The simplex-algorithm version used in this program seeks the optimum by trying to get all the simplex coefficients to be non-positive. The fourth (in)accuracy measure is the sum of the free recalculated positive simplex coefficients. The four inaccuracy measures are called respectively a-inaccuracy, b-inaccuracy, z-inaccuracy, and non-optimality. The overall inaccuracy reported together with the solution is simply the sum of these four inaccuracies. Another novel feature in version 2.1 is checking the special cases caused by linear dependencies and point-like solutions. In both these cases (see the linear programming literature) artificial (Extra) variable(s) may remain in the optimal basis but as zero(s). If the solution of a linear programming or a linear goal programming problem is non-feasible then the value of the artificial variable(s) staying in basis will be non-zero. These zero/non-zero conditions are now detected by LINSOLVE. .page - 8 - Parsing the problem (i.e. reading and interpreting it) has been made faster, as has been computing the iterations. The range of the zero described in an earlier section "Altering the Zero Criterion" has been made wider, and it is now possible not to alter the small elements at all. This is achieved by calling the program by LINSOLVE 0. This is not advisable, though, since it usually leads to suboptimal solutions. Version 2.2 introduces the choice between starting each new page of output (when directed to a file) either with a formfeed or two blank lines (earlier it was always a formfeed). If output is directed to the printer, that is to the file PRN, the user now has a choice of the left margin between 0 and 20. Version 2.3: The default output gives the values of the variables, slacks, objectives, and the shadow prices, i.e. the simplex coefficients of the variables in the first basis. The simplex coefficients of the the original variables have been added to the default output in version 2.3. They are given under the title REDUCED COST. (For interpreting the shadow prices and reduced costs see the appropriate literature.) If the output is directed to a printer (that is to file PRN), the online/offline status of the printer is now tested immediately, and the user is notified. (In the program code, this is achieved by using the interrupts for the testing, instead of IOResult checking.) Version 2.4: The program has been recompiled with Turbo Pascal 5.0. The bug preventing reading a read-only file has been fixed. (This bug was actually due to Turbo Pascal 4.0 documentation.) Furthermore, the program now augments pathnames to filenames when appropriate. Version 2.5: Most importantly, new files have been added to the TSLIN package. See the separate documentation in MPS2EQU.INF and in chapter 9. As to linsolve, if an input file is not found, the user has been given the option of listing directories from within linsolve. This directory routine has been rewritten for a more relaxed syntax and tighter code. A bug in the heap control has been fixed. This caused problems in rare cases during the out of memory condition. The maximum number of objectives in linear goal programming was one too small because of a bug. This has been fixed. .page - 9 - Version 2.6: Modern technology (sometimes not so modern :-) makes it possible to project a computer screen using an overhead projector onto a wall screen e.g. for classroom usage. In trying this out, I noticed, that it would be useful to have the option of changing the linsolve colors. The consequent new usage of the LINSOLVE call is LINSOLVE [/fx (foreground color)] [/bx (background color)] [/zxx.x (zero criterion)] [/h (help)] The simplest way of changing the colors is using just LINSOLVE /f, which will give you a white text on black background. The /f and /b parameters can include a color number ranging from 0-15 for the foreground, and 0-7 for the background. For the color map, either experiment, or see a Turbo Pascal manual for TextColor constants. I have made a couple of minor internal changes to speed up the program at certain phases. Also, the help screen can now be directed to a file, or to the printer. For this, use LINSOLVE /h > PRN. Version 2.7: This revision includes two major enhancements. The capacity of the program has been increased from 55x80 constraints and variables to 80x120. The second enhancement is the possibility of input recall with line-editing. A well-known bottle-neck of MsDos is the fact that the Intel 808x processors limit array sizes to 64K. To use larger arrays special techniques are needed. LINSOLVE version 2.7 employs the so-called huge-arrays method. This means enhanced capacity, but also slightly slower code. LINSOLVE still runs in the memory, and remains fast, contrary to many other LP programs using sloo..oow disk access in iterating. The possibility of input recall with line-editing is introduced. This means that in giving input from the keyboard, you have the following extra input keys available: Home, End, CursorLeft, CursorRight, CursorUp, Delete, and Esc. CursorUp is the recall key. The others are self-explanatory. This option is particularly useful in giving the linear programming task from the keyboard in classroom usage. That is the primary reason why I added this feature into linsolve. Version 2.8: The public domain task size limits have been increased to 55x25 from 55x15. Line-editing has been made more context sensitive, and the Insert key has been made functional. Version 2.9: If output is directed to a file, the file ready message now also contains the file size in bytes. The acceptable file names now also include the ( ) and _ characters. .page - 10 - Version 3.0: The program can now be interrupted in an orderly manner by pressing CTLC-C or the break key. The cursor will now resume its normal size after such a break. The input recall has been enhanced to remember the continuation lines. If you are giving the input from the keyboard and you enter e.g. E1 : 20X1 + & 30X2 & 10 which has an error (the last line should be = 10), you can recall each of these lines by applying consequtive PgUps until you are back at the third line. (Then you can apply line-editing to insert the missing = ). Version 3.1: First see the discussion on inaccuracy indexes for version 2.1. The idea is that in large and/or ill-behaved LP-problems round-off errors can cause serious inaccuracies and deviations from the mathematical, true optimum. Linsolve guards against such errors both in the algorithm, and by displaying inaccuraccy indexes. The number of these indexes has been reduced from four to two, and their calculation has been altered somewhat. First there is a non-optimality index which now gives the norm (square root of the sum of the squared) positive simplex-coefficients in the optimal tableau. Mathematically, it should have none, and thus the closer to zero, the better. Second there is an inaccuracy index giving the norm of the deviation of a recalculated optimal simplex-tableu from the optimal simplex-tableau. The recalculation is based on the inverse of the basis matrix. (See the relevant literature for details.) The norm is used since it gives the length of the deviation when it is considered a vector. Version 3.2: Input and output file names can now be optionally given as parameters in the program call, e.g. LINSOLVE /ic:\ordat\lptask.dat /of:\tmp The name of the input file and output file will still be asked by the program, but if you press the CursorUp key at the question, the given file names will pop up. I added this option when I noticed that this is more convenient for solving problems where frequent changes in the input data are needed. When a file is not found, the user has the option to look at the directory. The directory option has been improved and a minor bug has been corrected. .page - 11 - Version 3.3: Version 2.6 introduced the possibility of selecting the foreground and background colors of linsolve by applying /f# and /b# switches in the program call where # means a color number (0-15 for foreground, 0-7 for background). I have made several improvements. The forground and the background color can no longer be made equal to each other. Giving an out of range value is now trapped by the program. Most importantly the color codes can now be optionally given as color names (Black, Blue, Green, Cyan, Red, Magenta, Brown, LightGray, DarkGray, LightBlue, LightGreen, LightCyan, LightRed, LightMagenta, Yellow, and White). After having not used linsolve for a spell myself, and needing to change the colors for an overhead projector session in a classroom situation (I got squarely stuck for a minute), I decided to make these improvements. The normal maximum width of a simplex tableau is 79 characters which means presenting six columns of figures per row. I have added a switch /c# to the program call where # can range from 1 to 15 columns. This means a choice of a wider (or a narrower) output than the standard screen. This switch is operative in registered versions only. When output is directed to the printer, the program checks that the printer is online. The method I used earlier fails on some printers, so I adapted another method which is hopefully more robust. Updated the list of references (Chapter 10 of the instructions). .page - 12 - 10. SELECTED REFERENCES ON LINEAR AND LINEAR GOAL PROGRAMMING Gass, Saul I. Linear Programming: Methods and Applications. Second edition. McGraw-Hill Book Company, 1964. Hadley, G. Linear Programming. Addison-Wesley Publishing Company, 1962. (This is one of the classics on the mathematics of linear programming.) Ignizio, James P. Goal Programming and Extensions. Lexington Books, 1976. Ignizio, James p. "A Review of Goal Programming: A Tool for Multiobjective Analysis", Journal of the Operational Research Society, Vol. 29, No. 11 (November 1978), ss. 1109-1119. Jennergren, Peter L. "Linear programming on a micro - The case of the Apple II", European Journal of Operational Research, Vol. 19, No. 2 (February 1985), pp. 212-216. Jääskeläinen, Veikko. Lineaarinen optimointi ja budjetointi. Ekonomia-sarja 18. Tapiola: Weilin+Göös, 1972. Jääskeläinen, Veikko. Linear Programming and Budgeting. Malmö, Sweden: Student-litteratur, 1975. (One of the very few good applications oriented text-books on the utilization of linear programming. Covers also linear goal programming.) Kallio, Markku. A Corporate Planning Model. Research Paper D-17. Helsinki School of Economics, January 1977. Lee, Sang M. Goal Programming for Decision Analysis. Philadelphia: Auerbach Publishers Inc., 1972. (out of print?) Llewellyn, John & Ramesh Sharda. "Linear Programming Software for Personal Computers: 1990 Survey", OR/MS Today, (October 1990), pp. 35-47.. Perälä, Tarja. Tavoiteoptimointi ja investointipäätökset. Tutkielma kvantitatiivisen yritysanalyysin koulutusohjelmassa. Vaasan korkeakoulu 1982. (Sisältää kattavan lähdeluettelon.) Salmi, Timo. Lineaarinen optimointi ja sen soveltaminen. Täydennetty painos. Vaasan korkeakoulu, 1981. (Yksinkertaistettu johdatus aiheeseen.) .page - 13 - Schniederjans, Mark J. Linear Goal Programming. Princeton, New Jersey: Petrocelli Books, 1984. (Contains a lot of further references.) Stadler, Hartmut & Maren Groenenveld & Heidrun Hermanssen. "A Comparison of LP Software on Personal Computers for Industrial Applications", European Journal of Operational Research. Vol. 35, No. 2 (May 1988), pp. 146-159.