home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 2: PC / frozenfish_august_1995.bin / bbs / d01xx / d0199.lha / ASimplex / ASimplex.doc < prev    next >
Text File  |  1989-03-31  |  8KB  |  283 lines
  1.  
  2.                           ASimplex Version 1.2
  3.                           ====================
  4.  
  5.                         THE AMIGA-Simplex-Program
  6.  
  7.                       (c) 18.03.1989 Stefan Foerster
  8.  
  9.  
  10.  
  11. "ASimplex" is placed in the Public Domain. Nevertheless no part of this
  12. program may be sold or used in any commercial program. Private use is free.
  13.  
  14. If there are any bugs (I hope not!) or if you like the program so much that
  15. you have the desire to send me (poor student) a small donation, write to:
  16.  
  17.           Stefan Foerster
  18.           Weinbergstr. 29
  19.           8877 Burtenbach
  20.           West-Germany
  21.  
  22.  
  23. ASimplex is an implementation of the famous simplex-algorithm for solving
  24. linear programs. It was developed as a project in the course "Optimierung I"
  25. held at the university of Augsburg by Prof. Dr. Groetschel. It is written
  26. in C using the Manx Aztec C Compiler V3.6a.
  27.  
  28.  
  29. In general, linear programs are of the form
  30.  
  31.   max dx (or min dx), Ax = a, Bx <= b, Cx >= c, l <= x <= u,
  32.  
  33. where A, B and C are matrices and a,b,c,d,x,l and u are vectors.
  34. dx is called the objective (or cost) function that is to be maximized (or
  35. minimized) subject to the constraints Ax = a, Bx <=b, Cx >=c and l <= x <= u.
  36.  
  37. For example:
  38.  
  39.   min           x1 +   x2 -   x3
  40.  
  41.   subject to    x1 - 4*x2 + 3*x3 <= 6
  42.                 x1 + 2*x2 -   x3 <= 1
  43.                 x1 + 2*x2 +   x3 <= 8
  44.  
  45.                          0 <= x1 <= 1
  46.                          0 <= x2 <= 1
  47.                          0 <= x3 <= 3
  48.  
  49. with
  50.  
  51.       / 1  -4   3 \      / 6 \      / 1 \      / 0 \      / 1 \      / x1 \
  52.   B = | 1   2  -1 |, b = | 1 |, d = | 1 |, u = | 0 |, l = | 1 |, x = | x2 |
  53.       \ 1   2   1 /      \ 8 /      \-1 /      \ 0 /      \ 3 /      \ x3 /
  54.  
  55.  
  56.  
  57. Starting ASimplex:
  58. ------------------
  59.  
  60. i)  CLI:       Type "ASimplex" (Do not "run" ASimplex. This will cause an
  61.                EOF-error)
  62. ii) Workbench: Use the icon and a CON:-window will open. 
  63.  
  64.  
  65.  
  66.  
  67.  
  68. Commands of ASimplex:
  69. ---------------------
  70.  
  71. HELP
  72.  
  73. HELP lets you see all possible commands.
  74.  
  75.  
  76. VERBOSE
  77.  
  78. VERBOSE is a flag that can be ON or OFF. If it is ON, you get further
  79. information what ASimplex is currently doing. Default is OFF.
  80.  
  81.  
  82. PRIORITY [N]
  83.  
  84. PRIORITY N sets the task-priority of ASimplex to N (0<=N<=20).
  85. PRIORITY gives the current task-priority. Default is 0.
  86.  
  87.  
  88. QUIT
  89.  
  90. Leave ASimplex.
  91.  
  92.  
  93. LOAD <file> [-cGOAL] [-bRHS] [-rRANGE] [-uBOUND] [-m] [-fFILE]
  94.  
  95. With LOAD ASimplex reads the data of a linear program. The data must be
  96. in the standardized MPSX-format (MPSX is a trademark of IBM). A brief
  97. description of this format follows later; now you should only know, that
  98. the data is subdivided into sections and it is possible for some sections
  99. to contain data for different linear programs (e.g. different objective
  100. functions: Data belonging to a certain objective function has a unique
  101. identifier).
  102.  
  103. <file>   The file-name of the file you want to load.
  104.  
  105. -cGOAL   GOAL is the identifier of the objective function you want to use.
  106.          if -cGOAL is not specified then ASimplex uses the objective
  107.          function it finds (if there is only one) or it asks you to choose
  108.          one.
  109.  
  110. -bRHS    RHS is the identifier of the right hand side you want to use.
  111.          (b in the above example).
  112.  
  113. -rRANGE  RANGE is the identifier of the range you want to use.
  114.  
  115. -uBOUND  BOUND is the identifier of the bounds (l and u in the above
  116.          example).
  117.  
  118. -m       If -m is specified, ASimplex tries to minimize the objective
  119.          functions; otherwise it tries to maximize it.
  120.  
  121. -fFILE   If -fFILE is specified, ASimplex writes the result (also) to the
  122.          file "FILE" (FILE could also be PRT: to get the results to
  123.          printer).
  124.  
  125.  
  126.  
  127. The MPSX-format
  128. ---------------
  129.  
  130. The data of a linear program is subdivided into sections. This sections are
  131.  
  132.   NAME
  133.   ROWS
  134.   COLUMNS
  135.   RHS
  136.   RANGES
  137.   BOUNDS
  138.   ENDATA
  139.  
  140. where RANGES and BOUNDS are optional.
  141.  
  142.  
  143. i)    NAME-section:
  144.       The NAME-section determines the name of the linear program. In the
  145.       above example you could write
  146.  
  147.       NAME example
  148.  
  149.  
  150. ii)   ROWS-section:
  151.       You have to give every constraint of the linear program a name. This
  152.       name and the type of the constraint is determined in the ROWS-section.
  153.       The possible types are:
  154.       N   no constraint, objective function
  155.       E   "="   equality
  156.       L   "<="  less than or equal
  157.       G   ">="  greater than or equal
  158.       In the above example you could write:
  159.  
  160.       ROWS
  161.         N goal
  162.         L constr1
  163.         L constr2
  164.         L constr3
  165.  
  166.  
  167. iii)  COLUMNS-section:
  168.       The COLUMNS-section determines the variables and the coefficients
  169.       for every variable (in the constraints and in the objective function).
  170.       If a coefficient is not specified, it is assumed to be 0.
  171.       In the above example you could write:
  172.  
  173.       COLUMNS
  174.         x1  goal      1
  175.         x1  constr1   1
  176.         x1  constr2   1
  177.         x1  constr3   1
  178.         x2  goal      1
  179.         x2  constr1   -4
  180.         x2  constr2   2
  181.         x2  constr3   2
  182.         x3  goal      -1
  183.         x3  constr1   3
  184.         x3  constr2   -1
  185.         x3  constr3   1
  186.  
  187.       It is possible to use two fields in one line, e.g.
  188.  
  189.         x1  goal      1     constr1     1
  190.  
  191.  
  192. iv)   RHS-section:
  193.       In this section every value of the right hand side is determined.
  194.       If a value is missing it is assumed to be 0. Our example:
  195.  
  196.       RHS
  197.         b   constr1   6     constr2     1
  198.         b   constr3   8
  199.  
  200.       b is the name of this right hand side. If you want to define a second
  201.       right hand side, you could write
  202.  
  203.         b2  constr1   -2    constr2     9
  204.         b2  constr3   3.5
  205.  
  206.       It is possible to use two fields in one line.
  207.  
  208.  
  209. v)    RANGES-section:
  210.       Say you have the two constraints      2*x1 + x2  <= 10  and
  211.                                             2*x1 + x2  >= 8   .
  212.       You could write them in the form 8 <= 2*x1 + x2  <= 10  .
  213.       Then it is possible to define only one constraint in the ROWS-section
  214.       and define a range (a left hand side) in the RANGES-section, e.g.:
  215.  
  216.       ROWS
  217.         l constr
  218.         ...
  219.       RHS
  220.         b constr  10
  221.         ...
  222.       RANGES
  223.         r constr  2   ( IMPORTANT: not 8, but 2 = 10-8 !!! )
  224.  
  225.       r is the name of the range. It is possible to have several different
  226.       ranges in one RANGES-section and to specify two fields in one line.
  227.       The RANGES-section is optional.
  228.  
  229.  
  230. vi)   BOUNDS-section:
  231.       The BOUNDS-section defines the lower and upper bound (l and u) of the
  232.       linear program. Missing values in l are assumed to be 0 and missing
  233.       values in u are assumed to be "infinite". The BOUNDS-section is
  234.       optional. Every line begins with a "UP" (for upper bound) or "LO"
  235.       (for lower bound), followed by the name of the bounds. It is possible
  236.       to specify more than one bounds-name. Our exaple:
  237.  
  238.       BOUNDS
  239.         UP  bound   x1    1
  240.         UP  bound   x2    1
  241.         UP  bound   x3    3
  242.  
  243. vii)  ENDATA-section:
  244.       ENDATA simply is the end of the data.
  245.  
  246.  
  247.  
  248.  
  249.  
  250. Further notes on MPSX:
  251. ----------------------
  252.  
  253. - Identifiers are restricted to 8 characters. They can consist of every
  254.   printable character (except of space- and tab-characters). Lowercase
  255.   letters are converted to uppercase letters.
  256.  
  257. - Fields don't have to start in special columns (as in the original MPSX-
  258.   format coming from hollerith-cards). The only restriction is, that
  259.   section names have to start in column 1 the other lines mustn't start in
  260.   column 1.
  261.  
  262. - Lines can have a maximum length of 255 charcters. Every line must have a
  263.   new-line-character ('\n') at the end.
  264.  
  265.  
  266.  
  267. Technical notes:
  268. ----------------
  269.  
  270. - ASimplex uses double precision IEEE-arithmetic. "infinite" is represented
  271.   as NAN (Not A Number).
  272.  
  273. - The linear programs can have any size that fits into memory. The only
  274.   "restriction" is that you can't have more than 32767 rows or columns.
  275.   But that's not really restricting, because if you'd have a LP with e.g.
  276.   10000 rows and 20000 columns you'd need 2.2GBytes!
  277.  
  278.  
  279.  
  280.  
  281. ------------
  282. EOF
  283.