Trailing-Edge
-
PDP-10 Archives
-
decuslib20-05
-
decus/20-0137/rvslpr/rvslpr.rno
There are 2 other files named rvslpr.rno in the archive. Click here to see a list.
.LEFT MARGIN 5
.RIGHT MARGIN 70
.SPACING 1
.TITLE#####LIN. PROG.(REVISED SIMPLEX METHOD)_#2.2.5
.CENTER 68
^^WESTERN MICHIGAN UNIVERSITY\\
.CENTER 68
^^COMPUTER CENTER\\
.SKIP 3
.NF
^^LIBRARY PROGRAM:_#2.2.5\\
^CALLING ^NAME:##^^RVSLPR\\
^PREPARED BY:#############**
^ADAPTED BY:###^BILL ^GRANET*
^APPROVED BY:##^JACK ^R. ^MEAGHER
^DATE:#########^JUNE 1977
.FOOTNOTE 6
.NF
---------------------------
.F
*^THIS IS A COMBINATION OF A PROGRAM WRITTEN BY ^CHARLOTTE ^M. ^DAVISSON
(REF.1) WITH SUBSTANTIAL ADDITIONAL AND REVISIONAL PROGRAMMING BY ^BILL
^GRANET,^BOBBY ^HUNG, AND ^DR.#^A.#^WRIGHT. ^DEBUGGING HELP FROM ^MARK ^O'^BRYAN
AND ^RUSSELL ^R. ^BARR ^^III\\ IS ACKNOWLEDGED.
.NF
**^HELP FROM ^DR. ^WRIGHT IS ACKNOWLEDGED.
!
.SKIP 3
.CENTER 68
^^LINEAR PROGRAMMING\\
.CENTER 68
(^REVISED ^SIMPLEX ^METHOD)
.SKIP 3
^^TABLE OF CONTENTS\\
-----------------
.S
1.0 ^SPECIAL ^SYMBOLS
2.0 ^PURPOSE
3.0 ^LIMITATIONS
4.0 ^SAMPLE ^PROBLEM
5.0 ^^INPUT?\\ AND ^^OUTPUT?\\
6.0 ^OPTIONS
7.0 ^SAMPLE ^TERMINAL ^RUN
8.0 ^BATCH ^SET ^UP
9.0 ^REFERENCES
10.0 ^TOLERANCES
.SKIP 2
1.0 ^SPECIAL ^SYMBOLS
-------------------
(A)<^^CR\\> MEANS ENTER ^^RETURN\\.
(B)<= MEANS LESS THAN OR EQUAL.
(C)>= MEANS GREATER THAN OR EQUAL.
(D)^^^^CTRL Z\\ MEANS ENTER ^^CTRL\\ AND ^Z BUTTONS SIMULTANEOUSLY.
2.0 ^PURPOSE
-----------
.F
^THIS PROGRAM DETERMINES THE VALUES OF X(J) THAT SOLVE THE STANDARD
LINEAR PROGRAMMING PROBLEM:
.NF
A(I,1)+...+A(I,N) (<=,=,>=) B(I) (I=1,...,M)
X(J) >= 0 (J=1,...,N)
AND F(X(1),...,X(N)) = C(1)X(1)+...+C(N)X(N) IS OPTIMAL.
.PAGE
3.0 ^LIMITATIONS
---------------
.S
^^13*NR+8*NCFIN+NR*NR+2*NCFIN*NR\\ <= 15,000
WHERE ^^NCFIN=NC+2*NR-IPHASE-IEQUAL\\
^^IPHASE\\ = NUMBER <= CONSTRAINTS
^^IEQUAL\\ = NUMBER OF EQUALITY CONSTRAINTS
^^NC\\ = NUMBER OF REAL VARIABLES
^^NR\\ = NUMBER OF CONSTRAINTS.
4.0 ^SAMPLE ^PROBLEM
------------------
.S
.NF
^MAXIMIZE F((X1),X(2)) = 11*X(1)+4*X(2)
SUBJECT TO THE CONSTRAINTS
7*X(1)+6*X(2) <= 84
4*X(1)+2*X(2) <= 32
X(1) >= 2
X(2) >= 3
.S
.F
^FOR THIS PROBLEM THERE ARE FOUR INEQUALITIES AS DEFINED BY THIS PROGRAM. ^IF X(1) >= 2 AND X(2) >= 3 WERE TO BE REPLACED BY X(1) >= 0
AND X(2) >= 0,THEN BY THE DEFINITION OF THIS PROGRAM THERE ARE ONLY
TWO INEQUALITIES. ^THAT IS,THIS PROGRAM ASSUMES ALL X(I) >= 0
UNLESS THE USER SPECIFIES OTHERWISE.
.S
.NF
5.0 ^^OUTPUT?\\ AND ^^INPUT?\\
----------------------
.S
.NF
^THE FIRST TWO PROMPTINGS BY THIS PROGRAM ARE ^^OUTPUT?\\ AND ^^INPUT\\?.
.S
^^OUTPUT?\\
-------
.F
^THE RESPONSE TO THIS QUESTION SPECIFIES THE DEVICE TO BE USED FOR
THE RESULTS. ^IT USUALLY CONSISTS OF A DEVICE AND POSSIBLY A FILENAME
WITH OR WITHOUT AN EXTENSION. ^DEVICES MAY BE SPECIFIED BY LOGICAL OR
PHYSICAL NAMES. ^THE POSSIBLE DEVICES ARE:
.S
.TAB STOPS 18
.NF
^DEVICE ^DESCRIPTION
------ -----------
.S
.LEFT MARGIN 18
.F
.INDENT -13
^^TTY:\\ ^TERMINAL
.INDENT -13
^^DSK\\: ^DISK (^FILENAME AND EXTENSION MAY BE USED.)
.INDENT -13
^^LPT:\\ ^LINEPRINTER
.INDENT -13
^^DTA_#:\\ ^DECTAPE UNIT(^USER'S DECTAPE SHOULD ALREADY BE
MOUNTED. ^FILENAME AND EXTENSION MAY BE USED.)
.INDENT -13
^^MTA_#:\\ ^MAGTAPE UNIT(^USER'S MAGTAPE SHOULD ALREADY BE MOUNTED
AND POSITIONED.)
.S
.LEFT MARGIN 5
.F
^THE DEVICE COLUMN HAS PHYSICAL NAMES.
^IF THE DEVICE ^^LPT:\\ WAS USED,MULTIPLE COPIES OF THE OUTPUT
MAY BE OBTAINED BY FOLLOWING ^^LPT:\\ WITH A ^^/COPIES:\\ AND THE
NUMBER OF PRINTED COPIES DESIRED. ^IF NO RESPONSE IS GIVEN, THAT
IS, JUST A CARRIAGE RETURN (^^<CR\\>) IS ENTERED, THE DEFAULT DEVICE
IS THE TERMINAL. ^IF NO DEVICE IS SPECIFIED BUT A FILENAME IS GIVEN
,THE DEFAULT DEVICE IS THE DISK; AND IF A DEVICE WHICH REQUIRES A
FILENAME AND EXTENSION IS SPECIFIED , BUT NO FILENAME IS GIVEN, THE
DEFAULT NAME WILL BE ^^OUTPUT.DAT\\.
.S
.NF
^EXAMPLES
--------
^^OUTPUT? LPT:/COPIES:3
OUTPUT? RPT.DAT
OUTPUT? DTA0:OUT.DAT\\
.S
.NF
^^INPUT?\\
------
.S
.F
^THE RESPONSE TO THIS QUESTION SPECIFIES THE INPUT DEVICE. ^IT
USUALLY CONSISTS OF A DEVICE, POSSIBLY A FILENAME WITH OR
WITHOUT AN EXTENSION, AND POSSIBLY A PROJECT-PROGRAMMMER NUMBER
ENCLOSED IN SQUARE BRACKETS. ^DEVICES MAY BE SPECIFIED BY LOGICAL
OR PHYSICAL NAMES. ^THE POSSIBLE DEVICES ARE:
.S
.TAB STOPS 18
.NF
^DEVICE ^DESCRIPTION
------ -----------
.F
.S
.LEFT MARGIN 18
.INDENT -13
^^TTY:\\ ^TERMINAL
.INDENT -13
^^DSK:\\ ^DISK(^FILENAME AND EXTENSION, PROJECT-PROGRAMMER
NUMBER MAY BE USED.)
.INDENT -13
^^DTA_#:\\ ^DECTAPE UNIT(^USER'S DECTAPE SHOULD ALREADY BE
MOUNTED.^FILENAME AND EXTENSION MAY BE USED.)
.INDENT -13
^^MTA_#:\\ ^MAGTAPE UNIT(^USER'S MAGTAPE SHOULD ALREADY BE
MOUNTED AND POSITIONED.)
.INDENT -13
^^CDR:\\ ^CARD READER(USED IN BATCH ONLY)
.S
.F
.LEFT MARGIN 5
^THE DEVICE COLUMN HAS PHYSICAL NAMES. ^IF NO RESPONSE IS GIVEN
, I.E. A CARRIAGE RETURN(<^^CR\\>) IS ENTERED , THE DEFAULT DEVICE
IS ^^TTY:\\(TERMINAL). ^IF NO DEVICE IS SPECIFIED BUT
A FILENAME IS GIVEN , THE DEFAULT DEVICE IS ^^DSK:\\
(DISK). ^IF A DEVICE WHICH REQUIRES A FILENAME AND EXTENSION IS
SPECIFIED BUT NO FILENAME IS GIVEN , THE DEFAULT NAME WILL BE
^^INPUT.DAT\\. ^IF ^^DSK:\\ IS SPECIFIED AS THE INPUT DEVICE AND
NO PROJECT-PROGRAMMER NUMBER IS GIVEN, THE USER'S PROJECT-PROGRAMMER
NUMBER WILL BE ASSUMED.
.S
.NF
^EXAMPLES
--------
.S
^^INPUT? DATA.DAT
INPUT? MTA0
INPUT? DTA1:FILE1.DAT\\
.S
.F
^SEVERAL RESPONSES ARE VALID ON THE SECOND AND SUBSEQUENT ^^INPUT?\\.
.S
.NF
.TAB STOPS 25
^RESPONSE ^DESCRIPTION
-------- -----------
.S
.LEFT MARGIN 25
.F
.INDENT -20
^^SAME\\ ^IF THE DATE FILE TO BE USED IS THE SAME AS THE
PRECEDING ONE.
.INDENT -20
^^FINI,FINISH,_^^Z ^A ^^FINI,FINISH,\\ OR ^^CTRL Z\\ MUST
BE USED TO EXIT FROM THE PROGRAM. ^THIS ENSURES THE OUTPUT
ASSIGNED TO ^^LPT:\\ WILL BE PRINTED. ^FAILURE TO DO SO
MAY RESULT IN LOSING THE ENTIRE OUTPUT FILE.
.INDENT -20
^^CONTINUE\\ ^FOR MAGTAPES THIS MEANS DO NOT REREAD THE SAME PART
OF TAPE AS BEFORE, RATHER READ THE NEXT PART OF TAPE.
^FOR DISK OR DECTAPE THE RESULT OF USING ^^CONTINUE\\ IS
THE SAME AS USING THE ^^SAME\\ OPTION.
.INDENT -20
/^^OUTPUT\\ ^THIS COMMAND WILL PROMPT AN ^^OUTPUT?\\
ALLOWING THE USER TO CHANGE THE OUTPUT DEVICE. ^ANY
LINEPRINTER OUTPUT WILL BE QUEUED AND THE PROGRAM WILL
AGAIN ASK FOR ^^INPUT?\\.
.S
.F
.LEFT MARGIN 5
^^NOTE: (FOR HELP TYPE HELP)\\ WILL ALSO BE PRINTED THE FIRST
TIME ^^OUTPUT?\\ AND ^^INPUT?\\ ARE PRINTED. ^AFTER THAT
THIS MESSAGE WILL NOT BE PRINTED.
.NF
.S
^EXAMPLES
--------
.S
^^INPUT? SAME
INPUT? FINISH
INPUT? /OUTPUT\\
.S
.NF
6.0 ^THE ^THIRD ^AND ^FOURTH ^PROMPTINGS
-----------------------------------
.S
.F
^IT IS UNDERSTOOD IN THE FOLLOWING THAT (A) ONE ENTERS A ^^RETURN\\
AT THE END OF EACH LINE OF INPUT AND (B) ALL INPUT DATA AND
UNDERLINED ITEMS ARE SUBMITTED BY USERS.
.S
.NF
^THE THIRD PROMPTING IS: ^^ENTER DIMENSIONS\\
.S
^EXAMPLE
-------
.S
^^ENTER DIMENSIONS\\
4,2
.S
.F
4 IS THE NUMBER OF INEQUALITIES AND 2 IS THE NUMBER OF VARIABLES
NOT INCLUDING SLACK OR ARTIFICIAL VARIABLES.
.S
.NF
^THE FOURTH PROMPTING IS: ^^ENTER INEQUALITIES\\
.S
^EXAMPLES
--------
1
7,6
^^LE\\,84
2
4,2
^^LE\\,32
3
1
^^GE\\,2
4
0,1
^^GE\\,3
0
.S
^^NOTES:\\
------
.S
.F
1) ^A ^^CTRL Z\\ MAY BE USED INSTEAD OF 0 WHEN YOU ARE ENTERING INEQUALITIES FROM TERMINAL. ^IF INPUT IS COMING FROM DISK, USE 0 INSTEAD OF
^^CTRL Z\\.
.S
2) ^^LE,GE,\\ AND ^^EQ\\ MEAN LESS THAN OR EQUAL,GREATER THAN OR EQUAL,
AND EQUAL RESPECTIVELY.
.S
^THE ABOVE EXAMPLE USES THE SAMPLE PROBLEM GIVEN IN SECTION 3.0.
^EACH INEQUALITY IS PRECEDED BY ITS SEQUENTIAL IDENTIFICATION NUMBER.
^THE 0 FOLLOWING GE,3 SIGNIFIES THAT THE USER HAS NO MORE
INEQUALITIES TO ENTER. ^THE COEFFICIENTS OF THE INEQUALITIES
ARE ENTERED AT THE RATE OF 5 PER LINE.
.S
.NF
6.1 ^PRE-SOLUTION ^OPTIONS
------------------------
.S
.F
^THE FIFTH PROMPTING IS ^^ENTER OPTIONS\\. ^THIS IS FOLLOWED ON
THE NEXT LINE BY AN *. ^THE AVAILABLE PRE-SOLUTION
RESPONSES TO * ARE
^^OBJ, NAMES, MAX, MIN, START, TITLE, INOUT, TABLO, HELP, TOL1, TOL2, TOL3,
TOL4, TOL5, TOL6, TOL7, TOL8, TOL9, TOL10, TOL11. TOL1, TOL2, ..., TOL11 \\
WILL BE DISCUSSED IN THE LAST
SECTION (SECTION 9.0).
^THE PROPER RESPONSE TO AN * WILL LEAD TO ANOTHER *.
.S
^^OBJ\\ STANDS FOR OBJECTIVE FUNCTION. ^ON THE LINE FOLLOWING ^^OBJ\\
ENTER THE CEFFICIENTS OF THE OBJECTIVE FUNCTION AT THE RATE OF 5 PER
LINE.
.S
.NF
^EXAMPLE
-------
*^^OBJ\\
11,4
*
.S
.F
^ON THE LINE FOLLOWING ^^NAMES\\ ENTER NAMES FOR THE VARIABLES USED
IN THE OBJECTIVE FUNCTION AND THE INEQUALITIES AT THE RATE OF ONE PER
LINE. ^UP TO 10 CHARACTERS MAY BE USED IN A NAME.
.S
.NF
^EXAMPLE
-------
*^^NAMES\\
X1
X2
*
.S
.F
^IF NEITHER ^^MAX\\ NOR ^^MIN\\ ARE ENTERED, THEN THIS PROGRAM
ATTEMPTS TO MAXIMIZE THE OBJECTIVE FUNCTION.
.S
^^START\\ CAUSES THE PROGRAM TO BEGIN CALCULATIONS. ^^OBJ\\ AND ^^NAMES\\
MUST BE ENTERED BEFORE ^^START\\ IS ENTERED.
^OTHERWISE A MESSAGE ^^ENTER NAMES AND OBJ BEFORE START \\ WILL PRINT.
^THE USER THEN HAS ANOTHER CHANCE TO ENTER THE APPROPRIATE OPTIONS.
.S
^ON THE LINE FOLLOWING ^^TITLE\\ THE USER MAY ENTER UP TO 20
CHARACTERS WHICH WILL APPEAR AT THE BEGINNING OF THE OUTPUT.
.S
^^INOUT\\ CAUSES THE PRINTOUT OF THE OBJECTIVE
FUNCTION , VARIABLE LEAVING THE BASIS, AND THE VARIABLE ENTERING
THE BASIS FOR EACH PIVOT OF THE REVISED SIMPLEX PROCEDURE.
.S
^^TABLO\\ OR ^^TABLE\\ CAUSES THE PRINTOUT OF THE INITIAL TABLEAU.
.S
^IN ORDER TO UNDERSTAND THE GENERATION OF SLACK VARIABLES,
ARTIFICIAL VARIABLES, AND THE INITIAL BASIS VARIABLES AS SHOWN IN THE PRINTOUT OF THE TABLEAU,
ONE MUST BE GIVEN THE FOLLOWING PROCEDURE FOLLOWED BY THIS
PROGRAM.
.S
^IF B(I) (CONSTRAINT CONSTANTS) < 0 , THIS PROGRAM CHANGES THE
SIGN OF B(I), REVERSES THE INEQUALITY AND CHANGES THE SIGN OF
COEFFICIENTS IN THE ITH INEQUALITY.
.S
^THIS PROGRAM GOES THROUGH THE CONSTRAINTS ONE BY ONE ACCORDING
TO THE FOLLOWING PROCEDURE: ^IF THE ITH CONSTRAINT IS AN ^^
EQ\\, A COLUMN CORRESPONDING TO AN ARTIFICIAL VARIABLE
IS ADDED TO THE TABLEAU. THIS COLUMN WILL HAVE +1 IN THE
ITH ROW AND ZEROS IN THE OTHER ROWS.
.S
^IF THE ITH CONSTRAINT IS A ^^LE\\ , A COLUMN CORRESPONDING TO A SLACK
VARIABLE IS ADDED TO THE TABLEAU. ^THIS COLUMN WILL HAVE A
+1 IN THE ITH ROW AND ZEROS IN THE OTHER ROWS.
.S
^IF THE ITH CONSTRAINT IS A ^^GE\\, TWO COLUMNS WILL BE ADDED TO THE
TABLEAU. ^THE FIRST COLUMN ADDED CORRESPONDS TO A SLACK VARIABLE AND
IT WILL HAVE A -1 IN THE ITH ROW AND ZEROS IN THE OTHER ROWS.
^THE SECOND COLUMN ADDED CORRESPONDS TO AN ARTIFICIAL VARIABLE AND
IT WILL HAVE A +1 IN THE ITH ROW AND ZEROS IN THE OTHER ROWS.
.S
^THE TOTAL NUMBER OF REAL , SLACK , AND ARTIFICIAL VARIABLES IS DETERMINED
BY THE FORMULA
.S
.NF
^^NCFIN=NC+2*NR-IPHASE-IEQUAL\\
WHERE ^^IPHASE\\=NUMBER OF ^^LE\\ CONSTRAINTS
^^IEQUAL\\=NUMBER OF EQUALITY CONSTRAINTS
^^NC\\=NUMBER OF REAL VARIABLES
^^NR\\=NUMBER OF ROWS.
.F
.S
^THE INITIAL BASIS VARIABLES ARE SLACK AND ARTIFICIAL VARIABLES. ^THE
SLACK VARIABLES ARE ASSOCIATED WITH THOSE
CONSTRAINTS THAT ARE ^^LE\\ INEQUALITIES. ^ALL ARTIFICIAL VARIABLES
ARE IN THE INITIAL BASIS.
.S
.NF
.PAGE
6.2 ^POST ^SOLUTION ^OPTIONS
-------------------------
.S
.F
^AFTER THE ENTERING OF ^^START\\ AND THE CONSEQUENT
PRINTING OF THE ANSWERS, ^^ENTER THE POST SOLUTION OPTION(S)\\
AND AN * WILL PRINT. ^THE AVAILABLE RESPONSES TO * ARE:
^^RELCO, INVER, BASEN, NBSEN, BVSEN, HELP, TABLO, INEQ, OBJ, BVALU,
START , END.
.S
.NF
^^RELCO\\ STANDS FOR RELATIVE COST COEFFICIENTS.
.S
^^INVER\\ WILL CAUSE THE PRINTING OF THE INVERSE OF THE BASIS MATRIX.
.S
^^HELP\\ WILL GIVE POST SOLUTION OPTIONS WITH BRIEF DESCRIPTIONS.
.S
^^BASEN\\ PRODUCES A SENSITIVITY ANALYSIS TABLE FOR THE BASIS VARIABLES.
^FOR EACH FINAL BASIS VARIABLE THE FOLLOWING INFORMATION IS SUPPLIED.
.LEFT MARGIN 10
.INDENT -5
.F
1.###VARIABLE NAME
.INDENT -5
2.###THE UPPER AND LOWER LIMITS OF THE COST COEFFICIENT FOR THIS
VARIABLE THAT DEFINE THE RANGE FOR WHICH THE CURRENT SOLUTION
IS OPTIMAL
.INDENT -5
3.###THE NAME OF THE NON BASIS VARIABLES WHICH LIMIT THE RANGE
OF THE COST COEFFICIENT AND WHICH WOULD ENTER THE
SOLUTION IF THE RANGE WERE EXCEEDED
.INDENT -5
4.###^IN THE ^^LOW LIMIT\\ AND ^^TOP LIMIT\\ COLUMNS .17000000E+39
AND -.17000000E+39
SIGNIFY THAT THERE IS NO LIMIT.
.S
.LEFT MARGIN 5
.F
^^NBSEN\\ PRODUCES A SENSITIVITY ANALYSIS TABLE FOR THE NON BASIS
VARIABLES. ^FOR EACH NON BASIS VARIABLE THE FOLLOWING
INFORMATION IS SUPPLIED.
.LEFT MARGIN 10
.INDENT -5
1.###VARIABLE NAME
.INDENT -5
2.###THE UPPER AND LOWER LIMITS OF USAGE OF THE VARIABLE FOR
WHICH THE CORRESPONDING RELATIVE COST COEFFICIENTS(MARGINAL UNIT
COST) APPLIES
.INDENT -5
3.###THE NAME OF THE BASIS VARIABLES WHICH LIMIT THE RANGE OF
APPLICABILITY OF THE RELATIVE COST COEFFICIENT (^THE UPPER
LIMITING BASIS VARIABLE IS THE ONE WHICH WOULD LEAVE THE
BASIS SOLUTION IF THE ASSOCIATED NON BASIS VARIABLE WERE FORCED
INTO THE SOLUTION AT THE TOP LIMIT VALUE. ^SIMILARLY
THE LOWER LIMITING BASIS VARIABLE IS THE ONE WHICH WOULD
LEAVE THE BASIS SOLUTION IF THE ASSOCIATED NON BASIS VARIABLE
WERE FORCED INTO THE SOLUTION AT THE LOW LIMIT VALUE.)
.S
.LEFT MARGIN 5
^^BVSEN\\ PRODUCES A SENSITIVITY ANALYSIS TABLE FOR THE CONSTRAINT
CONSTANTS. ^FOR EACH CONSTRAINT CONSTANT THE FOLLOWING INFORMATION IS
SUPPLIED. (^THE FIRST CONSTRAINT CONSTANT LISTED IS ASSOCIATED WITH
THE FIRST INEQUALITY, THE SECOND ONE IS ASSOCIATED WITH THE
SECOND INEQUALITY,ETC.)
.F
.LEFT MARGIN 10
.INDENT -5
1.###THE LOWER AND UPPER LIMITS OF USAGE OF THE CONSTRAINT CONSTANT
THAT DEFINE THE RANGE FOR WHICH THE CURRENT BASIS IS OPTIMAL
.INDENT -5
2.###THE NAME OF THE BASIS VARIABLES WHICH LIMIT THE RANGE OF
USAGE OF THE CONSTRAINT CONSTANT AND WHICH WOULD LEAVE THE BASIS IF THE
RANGE WERE EXCEEDED
.LEFT MARGIN 5
.F
^^END\\ SIGNIFIES THAT NO MORE POST SOLUTION OPTIONS WILL BE ENTERED
AND CAUSES THE PRINTING OF ^^INPUT?\\ WHICH IS EXPLAINED IN
SECTION 4.0.
.S
^^INEQ, OBJ, BVALU, \\ AND ^^START\\ ALLOW A USER TO
MAKE CHANGES IN THE ORIGINAL INPUT DATA FOR PROCESSING WITHOUT
HAVING TO REENTER THE ENTIRE ORIGINAL INPUT DATA.
.S
^IF IN THE SAMPLE PROBLEM IN SECTION 3.0 WE WISH TO CHANGE 3 TO 5,
6 TO 8, 7 TO 9, AND 11 TO 3 AND SOLVE THE NEW PROBLEM, WE COULD DO IT
THE FOLLING WAY:
.S
.NF
*^^INEQ\\
1,1,9
1,2,8
0
*^^OBJ\\
1.3
0
*^^BVALU\\
4,5
0
*^^START\\
[OUTPUT]
*
.S
.F
^^TABLO\\ PRINTS THE CURRENT TABLEAU TAKING INTO ACCOUNT ANY CHANGES
PREVIOUSLY MADE USING THE ^^INEQ , OBJ , \\ AND ^^BVALU\\ OPTIONS.
.S
.NF
^^NOTES:\\
.S
.LEFT MARGIN 10
.F
.INDENT -5
1)###^WITH ^^INEQ\\ WE SUBMIT THREE VALUES SEPARATED BY TWO COMMAS.
^THE FIRST TWO VALUES ARE INTEGERS WHICH REPRESENT THE
SEQUENTIAL IDENTIFICATION I OF THE INEQUALITY AND THE
SEQUENTIAL IDENTIFICATION J OF THE UNKNOWN (X(J) OF SECTION
1.0) RESPECTIVELY. ^THE THIRD VALUE IS THE NEW COEFFICIENT
A(I,J).
.INDENT -5
2)###^^CTRL Z\\ OR 0 CAUSES ANOTHER * TO PRINT. ^IF INPUT IS
COMING FROM DISK, USE 0 INSTEAD OF ^^CTRL Z\\.
.INDENT -5
3)###^WITH ^^OBJ\\ WE SUBMIT TWO VALUES SEPARATED BY A COMMA.
^THE FIRST VALUE IS AN INTEGER WHICH REPRESENTS THE SEQUENTIAL
IDENTIFICATION J OF THE COST COEFFICIENT (C(J) OF SECTION 1.0).
^THE SECOND VALUE IS THE NEW COST COEFFICIENT.
.INDENT -5
4)###^WITH ^^BVALU\\ WE SUBMIT TWO VALUES SEPARATED BY A COMMA.
^THE FIRST VALUE IS AN INTEGER WHICH REPRESENTS THE
SEQUENTIAL IDENTIFICATION I OF THE INEQUALITY. ^THE SECOND
VALUE IS THE NEW CONSTRAINT CONSTANT B(I) FOR THE INEQUALITY.
.INDENT -5
5)###^^START\\ CAUSES THE NEW PROBLEM TO BE SOLVED.
.S
.NF
.LEFT MARGIN 5
.PAGE
7.0 ^SAMPLE ^TERMINAL ^RUN
-----------------------
.S
.F
^IF THE RESPONSE TO ^^INPUT?\\ IS ^^TTY:\\ OR <^^CR\\>, THEN ALL OF
THE USER'S INPUT IS ENTERED THROUGH THE TERMINAL. ^IF THE RESPONSE
TO ^^INPUT\\? IS NEITHER ^^TTY:\\ NOR <^^CR\\>>), THEN ALL THE
USER'S INPUT EXCEPT THE USER'S RESPONSE TO ^^OUTPUT?\\ AND
^^INPUT?\\, COMES FROM DISK OR A DEVICE OTHER THAN TERMINAL.
.S
.NF
.LITERAL
.R RVSLPR
WMU LINEAR PROGRAMMING(REVISED SIMPLEX)
OUTPUT? (for help type HELP)
INPUT? (for help type HELP)
ENTER DIMENSIONS.
4,2
ENTER INEQUALITIES.
1
7,6
LE,84
2
4,2
LE,32
3
1,0
GE,2
4
0,1
GE,3
0
ENTER OPTIONS
*NAMES
X1
X2
*OBJ
11,4
*TITLE
TEST PROBLEM
*START
TEST PROBLEM
THE MAXIMUM VALUE OF OBJECTIVE FUNCTION IS
83.500000
THE VARIABLES AND NUMBER OF UNITS THAT SHOULD BE USED TO MAXIMIZE
THE OBJECTIVE FUNCTION ARE AS FOLLOWS:
SL VAR# 1 20.500000
SL VAR# 3 4.5000000
X1 6.5000000
X2 3.0000000
ZERO UNITS OF OTHER VARIABLES ARE TO BE USED.
ENTER POST SOLUTION OPTION(S).
*BASEN
SENSITIVITY ANAL. TABLE FOR BASIS (SOLUTION) VARIABLES
--------------------------------------------------------------
I I I I
VAR. NAM. IL.L. VAR. I LOW LIMIT ITOP L. VARITOP LIMIT
I I I I
--------------------------------------------------------------
I I I I
SL VAR# 1ISL VAR# 4I-.60000000 ISL VAR# 2I 1.5714286
SL VAR# 3ISL VAR# 4I-3.0000000 INONE I .17000000E+39
X1 ISL VAR# 4I 8.0000000 INONE I .17000000E+39
X2 INONE I-.17000000E+39ISL VAR# 4I 5.5000000
*NBSEN
SENSITIVITY ANAL. TABLE FOR NONBASIS VARIABLES
--------------------------------------------------------------
I I I I
VAR. NAM. IL.L. VAR. I LOW LIMIT ITOP L. VARITOP LIMIT
I I I I
--------------------------------------------------------------
I I I I
SL VAR# 2ISL VAR# 1I-11.714286 ISL VAR# 3I 18.000000
SL VAR# 4IX2 I-3.0000000 ISL VAR# 1I 8.2000000
*RELCO
RELATIVE COST COEFFS
X1 X2 SL VAR# 1 SL VAR# 2 SL VAR# 3
0.000E+00 0.000E+00 0.000E+00 0.275E+01 0.000E+00
SL VAR# 4 ART VAR# 1 ART VAR# 2
0.150E+01 0.000E+00 -0.150E+01
*END
INPUT? FINISH
.END LITERAL
.PAGE
8.0 ^BATCH ^SET ^UP
----------------
.S
.F
^IN THE FOLLOWING BATCH SET UP ,EACH LINE REPRESENTS ONE
CARD, EACH CARD STARTING IN COLUMN 1. ^DO NOT INCLUDE THE COMMENTS
ON THE RIGHT. ^SEE COMPUTER CENTER ^^USER'S GUIDE _#7\\ OR THE
^^DECSYSTEM-10 USER'S HANDBOOK\\ FOR OTHER BATCH SYSTEM COMMANDS.
-------------------------------------------------------------
.F
.TAB STOPS 25
.LEFT MARGIN 25
.INDENT -20
$^^JOB\\ [_#,_#] ;_#,_# REPRESENTS THE USER'S PROJECT
-PROGRAMMER NUMBER.
.INDENT -20
$^^PASSWORD\\ _# ;_# REPRESENTS THE USER'S PASSWORD.
.INDENT -20
_.^^R RVSLPR\\ ;^RUN ^^RVSLPR\\.
.NF
.S
.LEFT MARGIN 5
[RESPONSES TO PROMPTINGS AS
EXPLAINED IN SECTIONS 4 AND 5]
.S
(EOF) ;END OF FILE CARD
9.0 ^REFERENCES
--------------
.S
.F
1) ^CHARLOTTE ^M. ^DAVISSON, "^LPSUB-^A ^FORTRAN ^SUBROUTINE ^FOR
^SOLVING ^ANY ^STANDARD ^LINEAR ^PROGRAMMING ^PROBLEM ^OF ^A ^SIZE
^COMPATIBLE ^WITH ^THE ^COMPUTER ^BEING ^USED.",^NAVAL ^RESEARCH
^LABORATORY,^WASHINGTON ^D.^C.,JAN. 1972
.S
2) ^WALTER ^W. ^GARVIN,"^INTRODUCTION ^TO ^LINEAR ^PROGRAMMING",
^MC-^GRAW ^HILL ^BOOK ^CO.,1960
.S
3) ^^G.B. D\\ANTZIG, "^LINEAR ^PROGRAMMING ^AND ^EXTENSIONS",
^PRINCETON ^UNIVERSITY ^PRESS,1963.
.S
.NF
10.0 ^TOLERANCES
---------------
.S
.F
^^TOL1 , TOL2, ..., TOL11\\ REPRESENT THE 11 NUMBERS THAT ARE USED
BY THIS PROGRAM FOR SCALING OR TO TEST FOR ZERO RESULTS. ^IF
THE USER DOES NOT SPECIFY TOLERANCE NUMBERS ,THE FOLLOWING
NUMBERS ARE ACTUALLY USED BY THE PROGRAM TO REPRESENT ^^TOL1,
TOL2, ..., TOL11:
1.0E-5, 1.0E-6, 1.0E-7, 1.0E+7, 1.0E-7, 1.0E-7, 1.0E-7, 1.0E-7, 1.0E-7,
1.0E-7, 1.0E-5\\
.S
.NF
^^TOL1
----
.F
\\^ANY VARIABLE WHOSE PHASE 1 RELATIVE COST COEFFICIENT IS > ^^TOL1\\
AT THE END OF PHASE 1 IS CONSIDERED TO BE AN ARTIFICIAL VARIABLE.
^THEREFORE , IN PHASE 2 WE WILL NOT CONSIDER THOSE VARIABLES
FOR ENTRY INTO THE BASIS.
.S
.NF
^^TOL2
----\\
.F
^AFTER ALL PHASE 1 RELATIVE COST COEFFICIENTS ARE > = 0
,THE VALUE OF THE INFEASIBILITY FORM IS COMPARED WITH ^^TOL2\\.
^IF INFEASIBILITY FORM (PHASE 1 OBJECTIVE FUNCTION)<= ^^TOL2\\
, THIS PROGRAM PROCEEDS TO PHASE 2; OTHERWISE , THE MESSAGE ^^
PROBLEM HAS NO FEASIBLE SOLUTION\\ PRINTS. ^THEN ^^INPUT?\\
PRINTS.
.S
.NF
^^TOL3\\
----
.F
^AN ELEMENT IN THE PIVOTAL COLUMN FOR DETERMINING NEW INVERSE
MATRIX IS COMPARED WITH ^^TOL3\\. ^IF ITS ABSOLUTE VALUE IS < TOL3 , THEN THE ELEMENT IS
SET TO ZERO AND WE GO TO THE NEXT STEP.
.S
.NF
^^TOL4\\ AND ^^TOL5\\
-------------
.F
^RATIO OF TRANSFORMED B VALUES TO PIVOTAL COLUMN ELEMENTS ARE
ROUNDED TO NEAREST 7TH DECIMAL PLACE WHEN ^^TOL5\\ HAS A DEFAULT
VALUE OF 1.0E-7. ^THIS IS USED IN DETERMINING WHEN TWO RATIOS
ARE TIED FOR THE SMALLEST RATIO. ^IN THIS CASE A DEGENERACY
PROCEDURE IS USED.
.S
.NF
^^TOL6\\
----
.F
^AFTER CALCULATION OF TRANSFORMED B VALUES (NEW VALUES OF
BASIS VARIABLES), THE NEW VALUES ARE COMPARED WITH ^^TOL6\\.
^IF ITS ABSOLUTE VALUE IS < ^^TOL6\\, THEN NEW VALUE IS SET TO ZERO.
.S
.NF
^^TOL7\\
----
.F
^AFTER THE CALCULATION OF THE ELEMENTS OF THE NEW INVERSE MATRIX
,THE NEW ELEMENTS ARE COMPARED WITH ^^TOL7\\. ^IF ITS ABSOLUTE VALUE
IS < ^^TOL7\\ NEW ELEMENT IS SET TO ZERO.
.S
.NF
^^TOL8\\
----
.F
^AFTER THE CALCULATION OF NEW SIMPLEX MULTIPLIERS FOR THE
OBJECTIVE FUNCTION, IN BOTH PHASE 1 AND PHASE 2 , THE NEW VALUES
ARE COMPARED WITH ^^TOL8\\. ^IF ITS ABSOLUTE VALUE
IS < ^^TOL8\\, THE NEW VALUE IS SET TO ZERO.
.S
.NF
^^TOL9\\
----
.F
^AFTER CALCULATION OF NEW SIMPLEX MULTIPLIERS FOR INFEASIBILITY FORM,
THE NEW VALUES ARE COMPARED WITH ^^TOL9\\. ^IF ITS ABSOLUTE VALUE IS
< ^^TOL9\\, THE NEW VALUE IS SET TO ZERO.
.S
.NF
^^TOL10\\
-----
.F
^AFTER CALCULATION OF NEW VALUES FOR THE INFEASIBILITY FORM, THE NEW
VALUES ARE COMPARED WITH ^^TOL\\10. ^IF ITS ABSOLUTE VALUE IS < ^^TOL10\\,
THE NEW VALUE IS SET TO ZERO.
.S
.NF
^^TOL11\\
-----
.F
^AFTER CALCULATION OF NEW RELATIVE COST COEFFICIENTS, THE NEW VALUES
ARE COMPARED WITH ^^TOL11\\. ^IF ITS ABSOLUTE VALUE IS < ^^TOL11\\, THE NEW
VALUE IS SET TO ZERO.