NetNews Usenet Archive 1992 #26

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

/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / sys / hp48 / 5731 < prev next >

Wrap

Text File | 1992-11-14 | 21.6 KB | 429 lines

Newsgroups: comp.sys.hp48 Path: sparky!uunet!think.com!ames!stanford.edu!leland.Stanford.EDU!rmarimon From: rmarimon@leland.Stanford.EDU (Ricardo Jose Marimon) Subject: Solving Linear Programs with SIMPLEX Message-ID: <1992Nov13.223017.26457@leland.Stanford.EDU> Sender: news@leland.Stanford.EDU (Mr News) Organization: DSG, Stanford University, CA 94305, USA Date: Fri, 13 Nov 92 22:30:17 GMT Lines: 418 Here is a program that I hope you would all enjoy... The program is used to solve the simplex. I find it very fast, it can solve a 8 variables by 5 constraints problem in less than 15 seconds performing 5 iterations on the tableau. The problem this program is intended to solve is of the form, min c.x st A.x = b (* b must be greater than zero *) x >= 0 The way the problem is entered is as a matrix of the following form, [ c | 0 | 0 ] [---+---+---] [ A | I | b ] Where I is the matrix formed by adding the slack and excess variables. And is NOT necessarily the identity matrix. For examples to solve the following problem max x1 + 2 x2 + x3 st x1 + x2 <= 3 x1 - x2 + x3 <= 3 x2 + x3 <= 3 x1 + x2 + x3 >= 3 x2 <= 2 x1, x2, x3 >=0 We convert it to the standard form min - x1 - 2 x2 - x3 st x1 + x2 + x4 = 3 x1 - x2 + x3 + x5 = 3 x2 + x3 + x6 = 3 x1 + x2 + x3 - x7 = 3 x2 + x8 = 2 x1, x2, x3 >= 0 And write it as a matrix to enter it in the program. [[ -1 -2 -1 0 0 0 0 0 0 ] [ 1 1 0 1 0 0 0 0 3 ] [ 1 -1 1 0 1 0 0 0 3 ] [ 0 1 1 0 0 1 0 0 3 ] [ 1 1 1 0 0 0 -1 0 3 ] [ 0 1 0 0 0 0 0 1 2 ]] This is matrix is provided as an examples and it is stored in the directory containing the program under the name "P" (weird name hu?). To solve the problem right away, just enter the matrix, press the [INIT] key which initializes some of the variables used by the program and then press the [SOLVE] key which iterates and gives the solution in three parts as follows, 3: :X: [ 2 .999999999998 2 0 0 0 2 1 ] 2: :\Gl: [ -1 0 -1 0 0 ] 1: :Z: -6 Where x is the actual point that minimizes the problem, the \Gl (lambda) is the solution to the dual problem or shadow prices of each of the constraints, and Z is the objective function value at the point found to be the minimum. This is the end of the quick start procedure to solve linear programs (LP) with my program. Now lets go to some details... The solution of an LP can be classified into, unfeasible, when there is no point satisfying the set of constraints unbounded, when the set of constraints can not restrict the decrease of the objective function (c.x) feasible & bounded, when there is a solution to the set of constraints which minimizes the objective function value. The problem can handle all three cases, giving the solution when it is feasible and bounded, providing a ray (which is a vector through which you can infinitely decrease the objective function while remaining in the feasible region) when the solution is unbounded, or flagging that there is no feasible solution. To achieve the different solutions, the program goes through the two phase simplex method automatically (you don't have to include artificial variables). Phase 1 is used to derive a starting basic feasible solution by introducing a set of artificial variables whith the objective of minimizing its sum; when this is achieved, the set of artificial variables is removed and Phase 2 starts with the original objective function. (refer to any LP book for more details into the 2 phase simplex method) One important thing to notice, is that the columns corresponding to the artificial variables, although not taken into account on phase 2, are not removed from the problem because it is sometimes usefull to have these columns at the end of the problem in order to perform sensitivity analysis. The basic algorithm that I used to solve the problem is a pseudo revised simplex method, where all that is maintained is the inverse of the base, the set of basic and non basic variables, and the rest of the data provided at the initialization process. I think this is the most effective procedure in terms of time because it requires less computations... Now it will give a brief explanation of what the programs in the directory do. This first set of programs are the ones intended to be used directly to solve the problem, [INIT] Initializes the set of variables that are needed by the program. [TABL] Provided the current tableau. [SOLU] Extracts the solution from the current tableau. [SRAY] Extracts a ray from an unbounded LP. [TRACE] Performs one iteration at a time, it is equivalent to solve, but you can take a look at the partial tableaus that are generated by the procedure. [SOLVE] Gives the answer to the LP if it exists. This second set of programs should not be used directly unless you REALLY know what you're doing. There are some system-RPL programs that can crash your system... [ITER] Given which variables enter and which variable goes out, this program performs the necessary iterations. Becarefull because the number that this programs expects are the indices into the BVAR and NVAR variables corresponding to the basic and non-basic variables. [INVAR] Calculates which variable enters tha base. It returns 0 if it is an optimum. [OUTVAR] Given which variable enters the base, it gives which variable must exit the base. It returns 0 if the solution is unbounded. [PH1] Performs all the calculations necesary to start phase 1. [PH2] Same but for phase 2. [MCHOP] Given a matrix and the contents of the 'ZERO' variable if an element of the matrix is less than 'ZERO' in absolute value it changes it to 0. [MVIN] Calculates the min element such that it is strictly less than zero. It returns the index into the array corresponding to the element. It returns 0 if no negative elements are found. [MVOUT] It performs the ratio test among two vectors. 2: v2 1: v1 Returns i s.t. min over all i [ v1[i]/v2[i] for v2[i]>0 ] Returns 0 if all v2[i] are less or equal to 0. [MJOC] Given two matrices it joins them in the standard form 2: [ A ] 1: [ B ] It returns [ A | B ] [MSBC] It takes the columns of a column as specified by a list with the numbers of the columns. 2: [ A ] 1: { 3 2 2 1} It returns [ A3 A2 A2 A1 ] where Ai represents the ith column of A. [MELM] This program is used to calculate the matrix that when multiplied by the inverse of the base, it gives the new inverse. 2: [1 2 4] 1: 1 It returns [[ 1 0 0] [-2 1 0] [-4 0 1] Multyplying by this matrix is equivalent to performing row reduction in row 1 (as specified by element in level 1) given that the column involved is specified by the element in level 2. [MBASE] It quickly calculates wether there is a base in the system and if there is, which one it is. It returns a list such that its elements correspond to the elements of the original matrix that corresponds to the the columns of the identity. [MSPL] It just separates the original problem form, [ c | 0 | 0 ] [---+---+---] [ A | I | b ] Into the matrices [ A | I ], [ b ], and [ c ]. [CLR14] Clears the top 14 rows of the display. Here are the variables used by the above procedures. Do not play with these variables during a run of the problem because you might get incorrect answers. [ZERO] Threshold after which numbers are considered to be zero. This in important because due to numeric problems, results tend to show some rounding errors. [BINV] This is the inverse of the base. [ACST] Actual cost function being used, it changes from phase 1 to phase 2. [NVAR] Non basic variables. [BVAR] Basic variables, in the order in which they are in the inverse of the base. [COST] The original objective function coefficients of the problem. The matrix [ c ] [DATA] The matrix [ A | I ] [RSRC] The matrix [ b ] [ARTI] Number of artificial variables included. [COLS] Number of variables in the problem, excluding artificials. [ROWS] Number of constraints in the problem. The custom menu provides a quick access to all of these variables. I hope that most of the question will be answered by the above brief description, but you can always contact me, and if I have time I will get back yo you fairly soon. Ricardo Marimon 28-D Escondido Village Stanford CA 94305 Email: rmarimon@leland.stanford.edu Most of the bugs have already been worked out, but as Murphy says, there is always one more bug... Please send any bug reports to my email address... Of course, I am not responsible for any damages that this program might cause to your calculator, your job, yout studies, or your life... :-) But again, I haven't had any troubles for months. And here is the program. Store it is in ASC format, and it is a directory. ----- Cut Here ----- %%HP: T(3)A(R)F(.); "69A20FF7CAB20000001005108E92097300339202000060000900000000000000 0000190000000000000029000000000000001900000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000010000000000000001000000000000000000000000000 0000100000000000000000000000000000000000000000000000000000000000 0000000000000000000030000000000000001000000000000000190000000000 0000100000000000000000000000000000001000000000000000000000000000 0000000000000000000000000000000000003000000000000000000000000000 0000100000000000000010000000000000000000000000000000000000000000 0000100000000000000000000000000000000000000000000000300000000000 0000100000000000000010000000000000001000000000000000000000000000 0000000000000000000000000000000000001900000000000000000000000000 0000300000000000000000000000000000001000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 000010000000000000002048300303435453047A2084E20402667162784E2040 2696E66784E2040E667162784E20404616471684E20402737273684E20401636 374784E204036F63747B2130D70004027F677374033920000000000000005012 0004036F6C637403392000000000000000801200040162747964033920000000 0000000000120004046164716408E9209E200339202000050000900000000000 0000000100000000000000010000000000000000000000000000000100000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000010000000000000001900000000000000100000000 0000000000000000000000010000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000100000000 0000000100000000000000000000000000000000000000000000000100000000 0000000000000000000000000000000000000000000000000000000100000000 0000000100000000000000010000000000000000000000000000000000000000 0000000000000000000000019000000000000000000000000000000100000000 0000000000000000000000010000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000100000000 000000000AF2004027372736408E920960003392020000500001000000000000 0000003000000000000000300000000000000030000000000000003000000000 00000020A70004036F63747408E9209900033920200001000080000000000000 0000019000000000000002900000000000000190000000000000000000000000 0000000000000000000000000000000000000000000000000000000AA0004026 6716274047A209C2A23F2A2743A2ED2A2C53A2B2130F20004016363747408E92 0990003392020000100008000000000000000000190000000000000029000000 0000000019000000000000000000000000000000000000000000000000000000 00000000000000000000000000AA00040E66716274047A20803A2D13A2233A2B 213052000402696E667408E9209A100339202000050000500009997666666666 6609994333333333330999333333333333978900000000000590000000000000 0009993333333333339999433333333333099976666666666607890000000000 0590000000000000000999766666666666099943333333333309997666666666 6600000000000000019000000000000000099933333333333309994333333333 3399993333333333330789000000000005000000000000000009993333333333 3399994333333333330999333333333333978900000000000590000000000000 010AB1005034C425134350D9D20FEF30B7040FD621B21307200040A55425F440 3392019900000000000501200040D43505C440D9D202BA81D9F811192040000D 9D20881308A7532FA30CB916D9D201192010500A3836B2130CA1307A22632230 7A22657B30CB916D9D201192010500A3836B213003D43D0040073E5954500D47 0E04166B316EC370122708B5533223043370649266B316E0E30CA1302CE30FED 30CAF069B1364B2A2244302C230EC37059230EF11609736F665343370B9F06E0 4167E3166B3162CE30FED306B316F6E307F370122708B553322306B3165A3704 42307E316E0E309FF30CA1302CE30FED30CAF069B1364B2A2244302C230EC370 59230EF11609736F665343370B9F06E04167E3166B3162CE306B316FED307F37 0122706B31680836122707F370122708B55332230433706B3165A370442307E3 16E0E306B316E0E30CA1302CE30FED30CAF069B1364B2A2244302C230EC37059 230EF11609736F665343370B9F0679470B2130B21301920050D42414355450D9 D202BA812BF811192040000D9D20881308A753A2170D9D201192010500A3836B 213003D4330040073E5954500D4704B2A27E316073E595450322306B316BD370 FEF30CAF0612270322307E316BD3702C2306B316CBD3033F068B55388130FC7A 28DA16D9D209C2A21C8A28DA16D9D20BBF066AC308DA1612270D9D20FEF30F00 46B2130E9016B2130D9D20BBF0653526E9016F0046B2130B21304423043370B9 F06592304D2268DA16D9D205923012270FBD81CAF0600CD132230B2130442304 33704423079470B2130B21308A10040D454C4D440D9D20D8A81D9F8111920140 00D9D20AEC813223088130265309BC269B1364B2A2244309FF3032230EF116BD 3702C230C1216CBD30FED3033F069C2A232230F665343370B9F0659230C1216C AF06A32168B553E9016A3216BD370122708B553100262C23028216CBD3033F06 BBF069A21612270E4D308DA16D9D20E5216EF9A2029A2B2130FAAA232230F665 3592304337032230AF01627F06B2130B21307410040D435243440D9D20D8A81D 9F811192054000D9D20FA45084E36D9D201192030200A3836B2130D7ED588130 D2E3052330881308A753A2170D9D201192010500A3836B2130BBF065B0369B13 64B2A2244302C230BD3701227032230B601696126A2170D9D201192020200A38 36B2130AEC81662262C2302821638D3057B30CB916D9D201192030200A3836B2 130B601628216BD3702C23028216CBD3033F068B5534C016100262C23028216C BD3033F062001632230F665310026433704CB2662726433704C016E7F06B2130 B2130C910040D4A4F43440D9D20D8A81D9F811192044000D9D20881308A7532F A30CB916D9D201192010500A3836B2130C12168A7532FA30CB916D9D20119201 0500A3836B21309FF309FF3003D43B2040073E5954500D47083416C6416E4D30 CB916D9D201192010500A3836B213032230C6416BD3706B316E0416C27368813 0CAF060E5167F370122708B553CAF0643370322307E316C5416C273688130CAF 060F5167F370122708B553CAF0643370322304337085230C6416C5416E0416CB D30CA1302CE30FED30CAF069B1364B2A2244302C2309FF307F37059230EF1160 9736F665343370B9F0679470B2130B21308D10050D465F4554550D9D20D8A81D 9F811192044000D9D2032230274A2FEF30100268813026530EF11626530BE026 A2170D9D201192010500A3836B2130BD370122708B55388130997A28DA16D9D2 059230122708B55359230EF9A288130E5216178A28DA16D9D204C01610026852 3012270CAF06B21304423032230B2130442304337085230B9F06FBD81B2130B2 130C110040D46594E440D9D202BA81D9F811192040000D9D208813026530274A 2119200000010026BD370122708B553881304B2A2178A28DA16D9D2088130A32 16178A28DA16D9D2010026852301227059230B213044230B2130442304337062 726FBD81B2130B2130AC00050D43484F40550D9D202BA81D9F811192040000D9 D2044B7384E2040A55425F4322308813026530FED309FF307F370122708B5530 09A2EF116178A2CB916D9D204B2A212270F6653B213043370B9F06B2130B2130 9A0003005842330D9D20E163284E2040E6671627B7FC147A20B21309C2A2E0CF 1301323CE2292CF184E204036F6C637D5CE1AFE22D9D20DBBF18DBF1B21305BF 2276BA15DF22C42323CE2278BF18B9C184E2040E66716278B9C1DBBF190DA184 E204016274796279E1AFE22D9D204563284E2040E667162797632DCC024B2A24 563284E20401627479697632DCC0284E204036F637474563284E204016363747 97632DCC02B21305BF228DBF15DF2293632B2130361003005841330D9D20E163 24B2A24563284E20401627479697632DCC0247A20B213084E204026671627330 3278BF14B2A24BAC178BF1D5032D9D20E0CF192CF176BA1E0CF1E0CF184E2040 36F6C6374563284E204016274796976324F80276BA1704D1B2130496328DBF13 CE2284E204016274796AFE22D9D204563284E20402667162797632DCC0284E20 4027F67737CD2D1DBBF184E2040D435243484E204046164716DBBF184E2040D4 A4F4344563284E20404616471697632DCC029C2A284E204036F6C63784E20401 627479676BA1ED2A2387C14B2A2681D184E204036F6C6379C2A276BA184E2040 36F6C63784E20401627479676BA10A132D6E201096D6E2010969C2A2704D1C42 32B21305BF22D9D208DBF18DBF184E204036F63747B21305DF224563284E2040 1636374797632DCC0293632B2130F620060F4554565142560D9D20E163284E20 40E6671627DBBF16C7D19C2A2387C184E204046164716DBBF184E2040D435243 484E20402696E667DBBF1EEDA184E2050D43484F40584E20402696E66784E204 027372736EEDA184E2050D43484F40584E2050D465F4554593632B21309D0005 094E465142550D9D20E163284E20401636374784E20402667162784E2040D435 243484E20402696E667EEDA184E20404616471684E2040E667162784E2040D43 52434EEDA184E20401636374784E2040E667162784E2040D435243490DA1599A 184E2050D43484F40584E2040D46594E493632B2130CE000409445542540D9D2 0E16321C432D6E202096E6D6E2030F65747E163284E20402696E66784E204046 1647164563284E2040E667162797632D6E202096E66C7D19C2A2387C184E2040 D4352434EEDA1D6E2030F6574784E2040D454C4D44563284E20402696E667976 32357024563284E2040E667162797632D6E202096E66C7D14563284E20402667 162797632D6E2030F657476C7D14563284E2040E667162797632D6E202096E6E 0CF1704D14563284E20402667162797632D6E2030F65747E0CF1704D1EF53293 632B2130891005035F4C4655450D9D20E1632916C11C432D6E205066C6167637 E16323392010000000000000105D2C13C03284E205034C4251343C2A20B10009 4475627164796F6E6A3029C2A2485A184E205094E46514253CE2278BF14B2A2D 9AE1AFE22D9D2078BF184E2060F455456514253CE2278BF14B2A2D9AE1AFE22D 9D201C432D6E202096E6D6E2030F65747E1632C2A20B100094475627164796F6 E6A3024563284E2040E667162797632D6E202096E66C7D1B0BC176BA1C2A20B0 00002D80276BA14563284E20402667162797632D6E2030F657476C7D1B0BC176 BA19C2A2485A1D6E202096E6D6E2030F6574784E204094455425EF532B21305B F22D9D208DBF18DBF1C2A205200055E626F657E6460235F6C6574796F6E69C2A 2485A19C2A24A5A1339201000000000000010472C1B21305DF22B21305BF22D9 D208DBF13CE2284E204016274796AFE22D9D20C2A20B200094E696479616C696 A7564602058616375602239C2A2485A184E20300584233CE2284E20401627479 6AFE22D9D20C2A20F20000527F626C656D60296370255E6665616379626C6569 C2A2485A1B21305DF22B21305BF22D9D20C2A201200035F6C6574796F6E60264 F657E6469C2A2485A184E204035F4C4559C2A24A5A1339201000000000000010 472C1B21305DF22B21305DF22DE032339201000000000000010313C19B632D6E 205066C6167637F76C1EF53293632B21305140050452514345450D9D20E16328 4E205034C4251343C2A20B100094475627164796F6E6A3029C2A2485A184E205 094E46514253CE2278BF14B2A2D9AE1AFE22D9D2078BF184E2060F4554565142 53CE2278BF14B2A2D9AE1AFE22D9D201C432D6E202096E6D6E2030F65747E163 2C2A20B100094475627164796F6E6A3024563284E2040E667162797632D6E202 096E66C7D1B0BC176BA1C2A20B000002D80276BA14563284E204026671627976 32D6E2030F657476C7D1B0BC176BA19C2A2485A1D6E202096E6D6E2030F65747 84E204094455425EF532B21305BF22D9D208DBF18DBF1C2A205200055E626F65 7E6460235F6C6574796F6E69C2A2485A184E204035251495B21305DF22B21305 BF22D9D208DBF13CE2284E204016274796AFE22D9D2084E20300584233CE2284 E204016274796AFE22D9D20C2A20F20000527F626C656D60296370255E666561 6379626C6569C2A2485A1B21305BF22D9D20C2A20B200094E696479616C696A7 564602058616375602239C2A2485A1B21305DF22B21305BF22D9D20C2A201200 035F6C6574796F6E60264F657E6469C2A2485A184E204035F4C455B21305DF22 B21305DF229C2A24A5A193632B213077300403525149540D9D20E163284E2040 2696E66784E204046164716EEDA184E2040E667162784E205094E46514256C7D 19C2A2387C184E2040D4352434599A184E204036F6C63784E20401627479676B A19C2A2387C14B2A2681D19C2A284E2040266716278B9C10A132D6E20109692C F1D6E2010966C7D14563284E20402667162797632D6E2010966C7D1DBBF1704D 1C4232DBBF18DBF193632B2130731004035F4C45540D9D20E163284E20402696 E66784E204027372736EEDA184E204036F6C63784E20401627479676BA19C2A2 387C14B2A2681D19C2A284E2040266716278B9C10A132D6E20109692CF1D6E20 10966C7D14563284E20402667162797632D6E2010966C7D1DBBF1704D1C4232C 2A207000085EB522DBBF184E20401636374784E20402667162784E2040D43524 3478BF184E20402696E667EEDA147A2084E204027F67737B2130FD0D1C2A2070 00069EB522DBBF1E0CF1EEDA1B7FC18DBF1C2A2070000A5EB52293632B2130F9 10040451424C440D9D20E163284E2040461647168B9C1B7FC18DBF11C432D6E2 01027D6E201036E163247A209C2A2D6E201036B21304B2A2681D184E20401636 374784E20402667162784E2040D435243484E20402696E667EEDA19C2A2D6E20 10360A132D6E20109678BF184E204046164716D6E2010969C2A2387C184E2040 D4352434EEDA1B7FC18DBF13CE22D6E20109684E204036F6C63784E204016274 79676BA1CFCE1AFE22D9D2084E204016363747D6E2010966C7D1B21305BF224B 2A25DF2290DA1E0CF1D6E201096E0CF1704D1DBBF1C423284E204027372736EE DA1599A184E2040D4A4F434599A1293D184E20402696E66784E204046164716E EDA184E20402696E66784E204027372736EEDA184E2040D4A4F434293D184E20 40D4A4F434293D184E2050D43484F405EF53293632B2130C62004094E4944540 D9D20E163278BF18B9C1B7FC18DBF11C432D6E201046D6E2010D6D6E2010E6E1 63284E205034C4251343C2A20310003596D607C656879C2A2485A1D6E2010D69 C2A290DA14563284E204027F6773797632DCC02D6E2010E69C2A290DA1456328 4E204036F6C63797632DCC02D6E20104684E2040D43505C44563284E20404616 471697632DCC024563284E20402737273697632DCC024563284E204036F63747 97632DCC0284E20404616471684E2050D4241435544563284E20402667162797 632DCC0284E20300584133CE2284E204016274796AFE22C2A20B200094E69647 9616C696A7564602058616375602135BF22C2A20D100064F657E646021602241 637565DF229C2A2485A147A20B21309C2A284E204036F6C6370A132D6E201096 3CE2284E204026671627D6E2010964BAC1F88E1AFE22D9D20D6E20109676BA1B 21305DF22C42324563284E2040E667162797632DCC0284E20404616471684E20 402667162784E2040D43524344563284E20402696E66797632DCC029C2A24A5A 1EF53293632B213023FE" ----- Down To Here ------