Technical Applications for T/S Computers

Author(s): Dennis Parry
Pub Details: Time Designs Magazine v2 n2 (Volume 2, Issue 2)
Date: January/February 1986
Pages: 15-16

LINEAR PROGRAMMING

Linear Programming, is the minimazation or maximazation of a linear form, subject to linear constraints, containing non-negative variables. The program I have written, uses the “simplex” method to do this.

The linear constraints are used to model certain physical situations, and the linear form that is optimized, tells how the situation that has been modeled, reacts to changes in the variables.

The program that I have written finds the mimimum of the linear function and the value of the variables used. The array S contains the column numbers of the variables having been solved-for, starting with the first equation and going on down to the last constraint equation. For example:

      minimize  Z= -x3  subject to
      x1    +5x3      =1
         x2 + x3      =6
             -x3  + x4=5
  x1≥0, x2≥0, x3≥0, x4≥0

                   x1= 1-5x3
  S=(1,2,4)  since x2= 6- x3
                   x4= 5+ x3

  consider the example:
           minimize Z=-x1
           x1 + x2    =5
          2x1     +x3=1

  x1≥0, x2≥0, x3≥0

In the computer program the constant in the function Z (i.e.; D) is zero.

The array C= (-1,0,0) since the coefficients
 of x3 and x2 must be zero in the algorithm.
The array S= (2,3)
The array A= (1 1 0)
             (2 0 1)
The array E= (5,1)
The array B= (1 0 0)
             (0 1 0)
             (0 0 1)   initially

The array F is used to transform the array B in each cycle of the algorithm. Note: The coefficients of the basic variables in Z must be made zero.

Here is a problem that is sovable by Linear Programming: A company makes wooden dowels. They make three sizes; 1/4″, 1/2″, and 3/4″ in diameter, with a fixed length of three feet. They sell for one, two and three dollars per dozen respectively. Fifty of 1/4 and 3/4 inch dowels, together can be be made from one piece of wood ( if the wood is good). Seventy-five of the 1/4 and 1/2-inch dowels can be made if the wood is good.

To conserve wood, two 1/4-inch dowels are made after each 3/4-inch dowel is made. How many of each size dowel, should be made to maximize profit, from each piece of wood?

maximize
Z= $1.00 x1 + $2.00 x2 + $3.00 x3  subject to
     2 x1 +                 + 1 x3≤ 50
     1 x1 +     1  x2             ≤ 75
x1≥0, x2≥0, x3≥0, X4≥0, X5≥0

To minimize Z, we take the negative of -Z, i.e.; -(-Z). The answer: x3=50, x2=75, z= $300.00, x1=x4=x5=0

where x1= the number of 1/4" dowels made
      x2= the number of 1/2" dowels made
      x3= the number of 3/4" dowels made

To put the problem in a form the computer can use, we need to add slack variables x4, and x5 where both x4≥0 and x5≥0. then the problem is:

maximize
Z= $1.00 x1 + $2.00 x2 + $3.00 x3
     2 x1         + x3 + x4 + 0 x5 =50
       x1 + x2         +0x4 +   x5 =75
    xi≥0   (i= 1,2,3,4,5)

and we find (- minimum (-Z)).

A good reference [for further information]: “LINEAR OPTIMIZATION” by Spivey, W. Allen, and Thrall, Robert M., Copyright 1970 by Holt, Rinehart and Winston, Inc.

This program will run on the Timex/Sinclair 2068

 100 REM PROGRAM SIMPLEX
110 REM THE PROGRAM SOLVES A
120 REM LINEAR PROGRAMMING
130 REM PROBLEM IN CANONICAL
135 REM FORM
137 REM
140 GO SUB 7000
155 GO SUB 1090
160 IF K=Z THEN GO SUB 1725
165 GO SUB 1170
170 GO SUB 1320
180 GO SUB 1430
190 GO SUB 1510
200 GO SUB 1680
210 GO TO 155
220 REM
1090 REM COMPUTE NEW C AND FIND
MINIMUM C(I)
1095 LET K=Z
1100 FOR I=O TO N
1110 LET X=Z: LET Y=Z
1120 FOR J=T TO S
1130 LET X=X+B(O,J)*A(J-O,I)
1140 NEXT J
1145 LET X=C(I)+X
1150 IF X>=Y THEN GO TO 1160
1155 LET Y=X: LET K=I: LET F(O)=X
1160 NEXT I
1164 REM IF K=0, THEN STOP ;
OPTIMAL SEQUENCE
1165 RETURN
1167 REM
1170 REM FIND min b(i)/a(i,K),
a(i,K)>0
1190 LET L=Z
1200 FOR I=T TO S
1210 LET X=Z
1220 FOR J=T TO S
1230 LET X=X+B(I,J)*
A(J-O,K)
1240 NEXT J
1260 LET F(I)=X
1265 IF X>Z THEN LET L=O
1270 NEXT I
1280 REM
1300 REM IF L<>O THEN LET COST BO
UNDED
1305 IF L<>O THEN PRINT AT T+O,O;H$ : STOP
1315 RETURN
1320 LET Y=1000
1325 REM
1330 FOR I=T TO S
1340 IF F(I)<=Z THEN GO TO
1390
1350 LET X=E(I-O)/F(I)
1360 IF X>=Y THEN GO TO 1390
1365 LET J=I
1370 LET H=J-O: LET Y=X
1390 NEXT I
1400 REM
1410 LET S(H)=K: RETURN
1430 REM FORM INVERSE MULTIPLIER
1435 LET Q=F(H+O)
1440 LET F(O)=-F(O)/Q
1450 REM
1460 FOR I=T TO S
1470 LET F(I)=-F(I)/Q
1480 NEXT I
1490 REM
1500 LET F(H+O)=O/Q: RETURN
1510 REM MULTIPLY ARRAY B BY
ARRAY F
1520 REM
1530 FOR I=O TO S
1532 IF I=H+O THEN GO TO 1570
1540 FOR J=T TO S
1550 LET B(I,J)=B(I,J)+F(I)*B(H+O,J)
1560 NEXT J
1565 REM
1570 NEXT I
1580 REM
1590 LET I=T: LET B(H+O,I)=B(H+O,I)*(O/Q): LET I=I+O
1620 IF I>S THEN RETURN
1630 LET B(H+O,I)=B(H+O,I)*(O/Q)
1640 LET I=I+O: GO TO 1620
1670 REM
1680 REM MULTIPLY E(*), BY F(*)
1685 LET X=F(H+O)*E(H)
1687 REM
1690 FOR I=T TO S
1695 IF H=I-O THEN GO TO 1710
1700 LET E(I-O)=E(I-O)+F(I)*E(H)
1710 NEXT I
1712 REM
1715 LET E(H)=X: RETURN
1725 REM
1730 REM PRINT OPTIMAL VALUE AND
OPTIMAL PROGRAM
1765 CLS
1775 PRINT "THE OPTIMAL PROGRAM IS"
1780 REM PRINT OPTIMAL PROGRAM
1790 FOR I=O TO P
1795 LET D=D-C(S(I))*E(I)
1800 PRINT "X";S(I);"=";E(I)
1810 NEXT I
1815 PRINT "WHERE Z= ";-D
1820 REM
1830 PRINT V$: STOP
1900 REM
7000 LET Z=PI-PI
7005 LET X=Z
7010 LET O=PI/PI
7020 LET T=O+O
7030 LET A$=" INPUT THE NUMBER OF VARIABLES IN THE PROBLEM"
7031 LET W$="THE OPTIMAL PROGRAM IS:"
7032 LET V$="WHERE THE OTHER VARIABLES EQUAL ZERO."
7040 LET B$=" INPUT THE NUMBER OF CONSTRAINTS"
7045 LET C$="THE COEFFICIENT OF XI IN EQUATION J IS?"
7050 LET D$="THE CONSTANT IN THE OBJECTIVE FUNCTION IS?"
7060 LET E$=" INPUT THE BASIC SEQUENCE"
7070 LET F$=" INPUT THE CONSTRAINT CONSTANTS."
7080 LET G$=" INPUT THE COEFFICIENTS IN THE OBJECTIVE FUNCTION"
7090 REM ARRAY C CONTAINS COST
COEFFICIENTS
7095 LET H$="THE OBJECTIVE FUNCTION IS UNBOUNDED"
7110 REM ARRAY A CONTAINS
INITIAL TABLEAU
7120 REM ARRAY B CONTAINS
INVERSE OF BASIS
7140 REM Z-D IS THE VALUE OF THE
OBJECTIVE FUNCTION
7150 REM ARRAY E CONTAINS
CONSTRAINT CONSTANTS
7160 REM ROW H IS THE PIVOT ROW
7170 REM COLUMN K IS PIVOT
COLUMN
7180 REM ARRAY T CONTAINS COLUMN
K OF A
7185 LET Y$="THE C(S(I)), MUST BE ZERO."
7190 REM ARRAY F IS PIVOT MATRIX
7210 REM ARRAY A HAS P ROWS AND
N COLUMNS
7220 REM
7230 PRINT A$
7240 INPUT N : CLS
7250 PRINT B$ : INPUT P : LET S=
P+O : CLS
7260 DIM S(P) : DIM B(S,S)
7270 DIM C(N) : DIM E(P): DIM F(S) : DIM A(P,N)
7280 PRINT C$
7285 REM
7290 FOR I=O TO N
7300 FOR J=O TO P
7310 PRINT AT Z,20;I;AT
O,12;J
7320 INPUT A(J,I)
7330 NEXT J
7340 NEXT I
7350 REM
7355 CLS
7356 REM
7360 FOR I=O TO S
7370 LET B(I,I)=O
7380 NEXT I
7390 REM
7400 PRINT E$: PRINT
7405 REM
7410 FOR I=O TO P
7420 INPUT S(I)
7440 PRINT "S(";I;")= ";S(I)
7450 NEXT I
7460 REM
7463 PRINT "PRESS ANY KEY TO CONTINUE."
7465 PAUSE Z
7470 CLS
7480 PRINT F$: PRINT
7485 REM
7490 FOR I=O TO P
7500 INPUT E(I)
7510 PRINT "E(";I;")=";E(I)
7520 NEXT I
7525 PRINT "PRESS ANY KEY TO CONTINUE."
7530 REM
7535 PAUSE Z
7540 CLS
7550 PRINT G$: PRINT
7555 REM
7560 FOR I=O TO N
7570 INPUT C(I)
7580 PRINT "C(";I;")=";C(I)
7590 NEXT I
7595 FOR I=1 TO P
7596 IF C(S(I))<>Z THEN PRINT Y$: STOP
7597 NEXT I
7600 REM
7601 PRINT "PRESS ANY KEY TO CONTINUE."
7605 PAUSE Z
7610 CLS
7620 PRINT D$: PRINT
7630 INPUT D: PRINT TAB 15,"D=";D: PRINT "PRESS ANY KEY TO CONTINUE.": PAUSE Z: LET D=-D : CLS : RETURN

Note: Type-in program listings on this website use ZMAKEBAS notation for graphics characters.