//JOB(ERCC07,STEPHENS,T=200,L=10000) //OPTIONS(QUOTES,OPT) //ALGOL 'COMMENT' *************** * * * ALGG018 * * * *************** ; 'BEGIN''COMMENT' THE TRANSPORTATION PROBLEM; 'PROCEDURE' CPUTIM(T); 'REAL'T; T:=CPUTIME; 'PROCEDURE' S1(K,N,M2,A,U,DEL); 'VALUE' K,N,M2; 'INTEGER' K,N,M2; 'ARRAY' A,U,DEL; 'BEGIN' 'INTEGER' I,J; 'REAL' T; 'FOR'J:=1'STEP'1'UNTIL'N'DO' 'BEGIN' T:=0.0; 'FOR'I:=1'STEP'1'UNTIL'M2'DO' T:=T+U[K,I]*A[I,J]; DEL[J]:=T; 'END'; 'END'; 'PROCEDURE' S2(ICODE,S,N,DEL); 'VALUE' N; 'INTEGER' ICODE,S,N; 'ARRAY' DEL; 'BEGIN' 'INTEGER' I,J; 'REAL' DMIN; DMIN:=1.0&30; ICODE:=1; 'FOR'J:=1'STEP'1'UNTIL'N'DO' 'BEGIN' 'IF'DEL[J]>-1.0&-5'THEN''GOTO' FINISH; ICODE:=2; 'IF'DEL[J]>=DMIN'THEN''GOTO' FINISH; DMIN:=DEL[J]; S:=J; FINISH: 'END'; 'END'; 'PROCEDURE' S3(JCODE,S,R,M,M2,A,U,X,V); 'VALUE' S,M,M2; 'INTEGER' S,R,M,M2,JCODE; 'ARRAY' A,U,X,V; 'BEGIN' 'INTEGER' I,J; 'REAL' T,RMIN; 'FOR'I:=1'STEP'1'UNTIL'M2'DO' 'BEGIN' T:=0.0; 'FOR'J:=1'STEP'1'UNTIL'M2'DO' T:=T+U[I,J]*A[J,S]; V[I]:=T; 'END'; RMIN:=1.0&30; JCODE:=1; 'FOR'I:=1'STEP'1'UNTIL'M'DO' 'BEGIN' 'IF'V[I]<=0.0'THEN''GOTO' FINISH; JCODE:=2; T:=X[I]/V[I]; 'IF'T>=RMIN'THEN''GOTO' FINISH; RMIN:=T; R:=I; FINISH: 'END'; 'END'; 'PROCEDURE' S6(R,M2,U,X,V); 'VALUE' R,M2; 'INTEGER' R,M2; 'ARRAY' U,X,V; 'BEGIN' 'INTEGER' I,J; 'REAL' T; T:=X[R]/V[R]; 'FOR'I:=1'STEP'1'UNTIL'M2'DO' X[I]:=X[I]-V[I]*T; X[R]:=T; 'FOR'J:=1'STEP'1'UNTIL'M2'DO' 'BEGIN' T:=U[R,J]/V[R]; 'FOR'I:=1'STEP'1'UNTIL'M2'DO' U[I,J]:=U[I,J]-V[I]*T; U[R,J]:=T; 'END'; 'END'; 'COMMENT' START OF THE MAIN ROUTINE; 'INTEGER' S,R,M,N,M2,IMANY,IMANY1,IMANY2,I,J,ICODE,JCODE; 'REAL' T,TT; CPUTIM(TT); M := READ; N := READ; IMANY1 := READ; IMANY2 := READ; M2:=M+2; 'BEGIN' 'ARRAY' A[1:M2,1:N],U[1:M2,1:M2],X[1:M2],DEL[1:N], LABEL[1:M], V[1:M2]; 'FOR'I:=1'STEP'1'UNTIL'M'DO' 'FOR'J:=1'STEP'1'UNTIL'N'DO' A[I,J] := READ; 'FOR'J:=1'STEP'1'UNTIL'N'DO' A[M+1,J] := READ; 'FOR'I:=1'STEP'1'UNTIL'M'DO' X[I ] := READ; 'FOR'J:=1'STEP'1'UNTIL'N'DO' A[M+1,J]:=-A[M+1,J]; X[M+1]:=0.0; T:=0.0; 'FOR'I:=1'STEP'1'UNTIL'M'DO' T:=T+X[I]; X[M2]:=-T; 'FOR'J:=1'STEP'1'UNTIL'N'DO' 'BEGIN' T:=0.0; 'FOR'I:=1'STEP'1'UNTIL'M'DO' T:=T+A[I,J]; A[M2,J]:=-T; 'END'; 'FOR'I:=1'STEP'1'UNTIL'M2'DO' 'BEGIN' 'FOR'J:=1'STEP'1'UNTIL'M2'DO' U[I,J]:=0.0; U[I,I]:=1.0; 'END'; 'FOR'I:=1'STEP'1'UNTIL'M'DO' LABEL[I]:=N+I; IMANY:=0; LA: S1(M2,N,M2,A,U,DEL); IMANY:=IMANY+1; 'IF'IMANY>IMANY1'THEN''GOTO' STOP; S2(ICODE,S,N,DEL); 'IF'ICODE=1'THEN''GOTO' L1; S3(JCODE,S,R,M,M2,A,U,X,V); 'IF'JCODE=1'THEN''GOTO' L1; LABEL[R]:=S; S6(R,M2,U,X,V); 'IF'X[M2]<-1.0&-5'THEN''GOTO' LA; WRITETEXT('('PHASE'('S')'I')'); WRITETEXT('('IMANY')'); WRITETEXT('('STEPS')'); IMANY:=0; LB: S1(M+1,N,M2,A,U,DEL); IMANY:=IMANY+1; 'IF'IMANY>IMANY2'THEN''GOTO' STOP; S2(ICODE,S,N,DEL); 'IF'ICODE=1'THEN''GOTO' L3; S3(JCODE,S,R,M,M2,A,U,X,V); 'IF'JCODE=1'THEN''GOTO' L2; LABEL[R]:=S; S6(R,M2,U,X,V); 'GOTO' LB; L1: WRITETEXT('('NO SOLUTION EXISTS')'); 'GOTO' STOP; L2:WRITETEXT('('UNBOUNDED'('S')'OPTIMUM'('S')'EXISTS')'); 'GOTO' STOP; L3:WRITETEXT('('PHASE'('S')'II')'); OUTPUT(IMANY); WRITETEXT('('OBJECTIVE'('S')'FUNCTION'('S')'MAXIMUM')'); OUTPUT(X[M+1]); 'FOR'I:=1'STEP'1'UNTIL'M'DO' 'BEGIN' WRITETEXT('('X(')');PRINT(LABEL[I],6,0); WRITETEXT('(')'('S')'='('S')'')'); OUTPUT(X[I]); 'END'; WRITETEXT('('DUAL'('S')'SOLUTION')'); 'FOR'I:=1'STEP'1'UNTIL'M'DO' OUTPUT(U[M+1,I]); STOP: 'END'; CPUTIM(TT); OUTPUT(TT); 'END' //RUN 9,20,100,100,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1, 1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0, 0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0, 0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0, 0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0, 0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1, -3.0&0,-4.0&0,-5.0&0,-6.0&0,0.0&0, -1.0&9,-5.0&0,-6.0&0,-7.0&0,0.0&0, -1.0&9,-1.0&9,-4.0&0,-5.0&0,0.0&0, -1.0&9,-1.0&9,-1.0&9,-6.0&0,0.0&0, 6.0,6.0,6.0,6.0,4.0,7.0,5.0,7.0,1.0,