Die Simplexmethode in Basic und Turbo Pascal/Free Pascal
Von: Delastelle
Datum: Mi. 21. Februar 2018 09:37:37
Thema: Software


Im folgenden Artikel ist die Simplexmethode der lineren Optimierung in Commodore Basic und Turbo Pascal/Free Pascal implementiert.
Der Ursprung des Basic-Programms stammt aus dem Buch "Planen+Entscheiden mit dem Sharp PC-1500" von X.T.Bui und Herbert Klein.
Ich habe dieses Programm in Commodore Basic und Turbo Pascal/Free Pascal umgewandelt.
4 Beispiele werden mit den Programmen gelöst.

Beispiele 1 bis 3 stammen aus meinem älteren Artikel zum Simplexverfahren und
deren Lösung mittels Scilab und Octave ( http://matheplanet.com/matheplanet/nuke/html/article.php?sid=1266 ).
Dabei ist Beispiel 1 lösbar, Beispiel 2 nicht lösbar wegen widersprüchlicher Nebenbedingungen
und Beispiel 3 nicht lösbar wegen Unbeschränktheit des zulässigen Bereichs.
Das 4.Beispiel - Klee-Minty mit 3 Variablen zeigt die schlechte Performance des Simplex-Verfahrens - 8 Iterationen werden benötigt.

Beispiel 1 und Lösung des Beispiels in Turbo Pascal/Free Pascal  

Die

Max. F(x,y) = 4x+3y

x+3y  <= 9
-x+2y >= 2
x, y  >= 0



***
(Scilab-Lösung)
--> f  =
   - 16.2
  lagr  =
     2.2
     1.8
  x  =
     2.4
     2.2

Lösung mit Pascal:
SIMPLEX-METHODE

LINEARE PROGRAMMIERUNG

MAXIMIERUNG ODER MINIMIERUNG
(MAX/MIN/ENDE) MINIMIERUNG DER ZIELFUNKTION
ANZAHL DER ENTSCH.VARIAB.ANZAHL DER ENTSCH.VARIAB. 2

ANZAHL DER NEBENBEDINGUNGEN
(AUSGEN.NICHTNEGATIVE NEBENBEDINGUNGEN):
 <= KLEINER ODER GLEICH <= ? 2
 >= GROESSER ALS ODER GLEICH >= ? 0
GLEICH = GLEICH = ? 0

DEFINITION DER INDIZ. VARIABLE :

ENTSCHEIDUNGSVARIABLE 1
= X(  1)
ENTSCHEIDUNGSVARIABLE 2
= X(  2)

SCHLUPFVARIABLE(N) DER
KLEINER ODER GLEICH
NEBENBEDINGUNG :
NEBENBEDINGUNG 1 = X(  3)
NEBENBEDINGUNG 2 = X(  4)


KOEFFIZIENTEN DER ZIELFUNKTION :
---------------
KOEFF.DER ENTSCH.VAR.
X(1)=
KOEFF.DER ENTSCH.VAR. 1 =   4.00000
KOEFF.DER ENTSCH.VAR.
X(2)=
KOEFF.DER ENTSCH.VAR. 2 =   3.00000

WERT DER RECHTEN SEITE
---------------
==DER NEBENBEDINGUNG
X(1)=
==DER NEBENBEDINGUNG 1 =    9.00000
==DER NEBENBEDINGUNG
X(2)=
==DER NEBENBEDINGUNG 2 =   -2.00000

NEBENBED.KOEFFIZIENTEN :
---------------
KOEFFIZ.DER NEBENBED.NR. 1
ENTSCH.VARIABLE1,1=--ENTSCH.VARIABLE 1 =   1.00000
ENTSCH.VARIABLE1,2=--ENTSCH.VARIABLE 2 =   3.00000
KOEFFIZ.DER NEBENBED.NR. 2
ENTSCH.VARIABLE2,1=--ENTSCH.VARIABLE 1 =   1.00000
ENTSCH.VARIABLE2,2=--ENTSCH.VARIABLE 2 =  -2.00000



ITERATION NR.0
---------------
BASIS VARIABLEN          WERT
     X(  3)             9.00000
     X(  4)            -2.00000

VARIABLEN DES SIMPLEX-TABLEAUS
X(  3);
X(  4);
X(  1);
X(  2);


KOEFIZ.MATRIX A(I,J) :
---------------
   1.00000    0.00000    1.00000    3.00000
   0.00000    1.00000    1.00000   -2.00000
MARG.DECK.BEITRAGSKOEFF. Z(J)-C(J) :
   0.00000    0.00000    4.00000    3.00000

ZIEFFUNKTION Z =         0.00000

WEITER ? J/N


ITERATION NR.1
---------------
BASIS VARIABLEN          WERT
     X(  3)            11.00000
     X(  1)            -2.00000

VARIABLEN DES SIMPLEX-TABLEAUS
X(  3);
X(  4);
X(  1);
X(  2);


KOEFIZ.MATRIX A(I,J) :
---------------
   1.00000   -1.00000    0.00000    5.00000
   0.00000    1.00000    1.00000   -2.00000
MARG.DECK.BEITRAGSKOEFF. Z(J)-C(J) :
   0.00000   -4.00000    0.00000   11.00000

ZIEFFUNKTION Z =         8.00000

WEITER ? J/N


ITERATION NR.2
---------------
BASIS VARIABLEN          WERT
     X(  2)             2.20000
     X(  1)             2.40000

VARIABLEN DES SIMPLEX-TABLEAUS
X(  3);
X(  4);
X(  1);
X(  2);


KOEFIZ.MATRIX A(I,J) :
---------------
   0.20000   -0.20000    0.00000    1.00000
   0.40000    0.60000    1.00000    0.00000
MARG.DECK.BEITRAGSKOEFF. Z(J)-C(J) :
  -2.20000   -1.80000    0.00000    0.00000

ZIEFFUNKTION Z =       -16.20000

WEITER ? J/N


*** OPTIMALE LOESUNG GEFUNDEN ***
*** NACH 3 ITERATIONEN ***

---------------
ENTSCH.VARIABLEN     WERT
---------------
     X(  2)          =   2.20000
     X(  1)          =   2.40000
! BEACHTE !
ALLE VARIABLEN, DIE IN DIESER TABELLE
NICHT GEZEIGT WERDEN,
HABEN DER WERT 0.
---------------
MAXIMUM Z =        16.20000
---------------
Hinweis: Das Pascal-Programm gibt am Ende den Betrag der Zielfunktion an.

Beispiel 2 und Lösung des Beispiels in Turbo Pascal/Free Pascal  

Max. F(x,y) = x-y
2x-y <= 0
x+2y <= 1
2x+y >= 2
x,y >= 0

***
(Scilab-Lösung)
--> !--error 127
 no feasible solution

Lösung mit Pascal:
SIMPLEX-METHODE

LINEARE PROGRAMMIERUNG
...
ITERATION NR.0
---------------
BASIS VARIABLEN          WERT
     X(  3)             0.00000
     X(  4)             1.00000
     X(  5)            -2.00000

VARIABLEN DES SIMPLEX-TABLEAUS
X(  3);
X(  4);
X(  5);
X(  1);
X(  2);


KOEFIZ.MATRIX A(I,J) :
---------------
   1.00000    0.00000    0.00000    2.00000   -1.00000
   0.00000    1.00000    0.00000    1.00000    2.00000
   0.00000    0.00000    1.00000   -2.00000   -1.00000
MARG.DECK.BEITRAGSKOEFF. Z(J)-C(J) :
   0.00000    0.00000    0.00000    1.00000   -1.00000

ZIEFFUNKTION Z =         0.00000

WEITER ? J/N


ITERATION NR.1
---------------
BASIS VARIABLEN          WERT
     X(  1)             0.00000
     X(  4)             1.00000
     X(  5)            -2.00000

VARIABLEN DES SIMPLEX-TABLEAUS
X(  3);
X(  4);
X(  5);
X(  1);
X(  2);


KOEFIZ.MATRIX A(I,J) :
---------------
   0.50000    0.00000    0.00000    1.00000   -0.50000
  -0.50000    1.00000    0.00000    0.00000    2.50000
   1.00000    0.00000    1.00000    0.00000   -2.00000
MARG.DECK.BEITRAGSKOEFF. Z(J)-C(J) :
  -0.50000    0.00000    0.00000    0.00000   -0.50000

ZIEFFUNKTION Z =         0.00000

WEITER ? J/N


*** OPTIMALE LOESUNG GEFUNDEN ***
*** NACH 2 ITERATIONEN ***

*** DEGENERIERTE LOESUNG ***

---------------
ENTSCH.VARIABLEN     WERT
---------------
     X(  1)          =   0.00000
     X(  4)          =   1.00000
     X(  5)          =  -2.00000
! BEACHTE !
ALLE VARIABLEN, DIE IN DIESER TABELLE
NICHT GEZEIGT WERDEN,
HABEN DER WERT 0.
---------------
MAXIMUM Z =         0.00000
---------------

Beispiel 3 und Lösung des Beispiels in Turbo Pascal/Free Pascal  

Max. F(x,y) = 2x+y
-x+y <= 1
x+3y >= 6
x,y >= 0

***
(Scilab-Lösung)
--> !--error 123
  fonction not bounded from below

Lösung mit Pascal:
SIMPLEX-METHODE

LINEARE PROGRAMMIERUNG
...
ITERATION NR.0
---------------
BASIS VARIABLEN          WERT
     X(  3)             1.00000
     X(  4)            -6.00000

VARIABLEN DES SIMPLEX-TABLEAUS
X(  3);
X(  4);
X(  1);
X(  2);


KOEFIZ.MATRIX A(I,J) :
---------------
   1.00000    0.00000   -1.00000    1.00000
   0.00000    1.00000   -1.00000   -3.00000
MARG.DECK.BEITRAGSKOEFF. Z(J)-C(J) :
   0.00000    0.00000    2.00000    1.00000

ZIEFFUNKTION Z =         0.00000

WEITER ? J/N *** LOESUNG UNMOEGLICH ***

Beispiel 4 und Lösung des Beispiels in Commodore Basic  

Beispiel Klee-Minty 3x3
( en.wikipedia.org/wiki/Klee-Minty_cube )


max 4 x + 2 y + z
x             <=   5
4 x + y       <=  25
8 x + 4 y + z <= 125
x, y, z       >=   0



Hinweis: Victor Klee und George Minty fanden dieses Beispiel 1973.
Mit der klassischen Simplexmethode werden sehr viele Ecken besucht - der Algorithmus zeigt eine schlechte Performance.
Für das angegebene 3er Beispiel werden 8 Iterationen des Simplexalogrithmus benötigt.

(Lösung in Octave)
Octave
c = [4,2,1]';
a = [1,0,0;4,1,0;8,4,1];
b = [5, 25, 125]';
lb = [0,0,0]';
ub = [];
ctype = "UUU"; % U: Ax <= b
vartype = "CCC"; % i integer (ILP)
s = -1; % Maximierung
param.msglev = 1;
param.itlim = 100;
[xmin,fmin,status,extra] = glpk(c,a,b,lb,ub,ctype,vartype,s,param);
xmin =
0
0
125
fmin = 125

Lösung des Beispiels in Commodore Basic:









Hinweis: Das Basic-Programm gibt am Ende den Betrag der Zielfunktion an.




Listing Simplexmethode in Commodore Basic

Handhabung von "SIMPLEX.P00"
(1) Download von "SIMPLEX.P00" aus meinem Notizbuch
( fav.php?uname=Delastelle )
(2) VICE PLUS 4 starten (xplus4.exe)
(3) Options -> Double size // doppelte Bildschirmgröße
(4) File -> Autostart disk -> "SIMPLEX.P00"
(5) DLOAD"SIMPLEX" // laden von Festplatte
(6) RUN // starten
(7) Eingaben für Beispiel 1:
0,MAX,2,2,0,0
4,3
9,-2
1,3,1,-2
(8) (Berechnung)

BASIC
10 PRINT"SIMPLEX-METHODE"
20 PRINT
30 PRINT"LINEARE PROGRAMMIERUNG"
40 PRINT
50 INPUT"BEISPIEL 0 bis 5 ";BE
51 IF BE=1 THEN RESTORE 10000
52 IF BE=2 THEN RESTORE 11000
53 IF BE=3 THEN RESTORE 12000
54 IF BE=4 THEN RESTORE 13000
55 IF BE=5 THEN RESTORE 14000
59 IF BE>0 THEN READ C$: GOTO 80
60 PRINT"MAXIMIERUNG ODER MINIMIERUNG": INPUT"(MAX/MIN/ENDE) ";C$
65 IF C$="ENDE" THEN STOP
70 IF LEFT$(C$,2)<>"MA" AND LEFT$(C$,2)<>"MI" THEN 60
80 IF LEFT$(C$,2)="MI" THEN PT=-1: PRINT"MINIMIERUNG DER ZIELFUNKTION": GOTO 110
90 PRINT"MAXIMIERUNG DER ZIELFUNKTION"
100 PT=1
110 IF BE>0 THEN READ MN: GOTO 120
115 INPUT"ANZAHL DER ENTSCH.VARIAB.";MN
120 PRINT"ANZAHL DER ENTSCH.VARIAB. ";MN
130 PRINT
140 PRINT"ANZAHL DER NEBENBEDINGUNGEN":PRINT"(AUSGEN.NICHTNEGATIVE NEBENBEDINGUNGEN):"
145 IF BE>0 THEN READ NS: GOTO 160
150 INPUT" <= ";NS
160 PRINT"KLEINER ODER GLEICH <= ? ";NS
165 IF BE>0 THEN READ NB: GOTO 180
170 INPUT" >= ";NB
180 PRINT"GROESSER ALS ODER GLEICH >= ? ";NB
185 IF BE>0 THEN READ NE: INPUT"WEITER ";C$: GOTO 200
190 INPUT"GLEICH = ";NE
200 PRINT"GLEICH = ? ";NE
210 M=NS+NB+NE
220 N=M+MN+NB
230 DIM B(M),CI(N),CJ(N),Z(N),ZC(N),XI(N),XJ(N),A(M,N)
240 PRINT
250 PRINT"DEFINITION DER INDIZ. VARIABLE :": PRINT
260 K=1: FOR J=M+1 TO M+MN
270 PRINT"ENTSCHEIDUNGSVARIABLE ";K
280 XJ(K)=K
290 PRINT"= X(";XJ(J);")"
300 K=K+1: NEXT J: PRINT
310 IF NS<=0 THEN 400
320 PRINT"SCHLUPFVARIABLE(N) DER"
330 PRINT"KLEINER ODER GLEICH": PRINT"NEBENBEDINGUNG :"
340 K=MN+1: FOR J=1 TO NS
350 PRINT"NEBENBEDINGUNG ";J;
360 XJ(J)=K
370 PRINT" = X(";XJ(J);")"
380 K=K+1: NEXT J: PRINT
390 FOR I=1 TO N: CJ(I)=0: NEXT I
400 IF NB=0 THEN 490
410 PRINT"SCHLUPFVARIABLE(N) DER"
420 PRINT"GROESSER ODER GLEICH": PRINT"NEBENBEDINGUNG"
430 PRINT"( RESTVARIABLE(N) ):"
440 K=M+MN+1: FOR J=M+MN+1 TO N
450 PRINT"NEBENBEDINGUNG ";J+NS-M-MN;
460 XJ(J)=K
470 PRINT" = X(";XJ(J);")"
480 K=K+1: NEXT J: PRINT
490 IF NB=0 AND NE=0 THEN 580
500 PRINT"KUENSTLICHE VARIABLE(N) FURE DIE"
510 PRINT" >= UND = NEBENBEDINGUNG :"
520 K=MN+NS+1: FOR J=NS+1 TO M
530 PRINT"NEBENBEDINGUNG ";J;
540 XJ(J)=K
550 PRINT" = X(";XJ(J);")"
560 CJ(J)=10000
570 K=K+1: NEXT J: PRINT
580 FOR I=1 TO M: XI(I)=XJ(I): NEXT I
590 PRINT: PRINT"KOEFFIZIENTEN DER ZIELFUNKTION :"
600 PRINT"---------------"
610 FOR I=M+1 TO M+MN
615 IF BE>0 THEN READ CJ(I): GOTO 640
620 PRINT"KOEFF.DER ENTSCH.VAR.":PRINT"X(";I-M;")= ";
630 INPUT CJ(I)
640 PRINT"KOEFF.DER ENTSCH.VAR. ";I-M;" =";CJ(I)
650 CJ(I)=CJ(I)*PT*(-1)
660 NEXT I: PRINT
665 IF BE>0 THEN INPUT"WEITER ";C$
670 PRINT"WERT DER RECHTEN SEITE"
680 PRINT"---------------"
690 FOR I=1 TO M
695 IF BE>0 THEN READ B(I): GOTO 720
700 PRINT"==DER NEBENBEDINGUNG "
710 PRINT"X(";I;")=": INPUT B(I)
720 PRINT"==DER NEBENBEDINGUNG ";I;" = ";B(I): NEXT I
725 IF BE>0 THEN INPUT"WEITER ";C$
730 FOR I=1 TO M: FOR J=1 TO N
740 IF I<>J THEN 770
750 A(I,J)=1
760 GOTO 780
770 A(I,J)=0
780 NEXT J: NEXT I
790 PRINT
800 PRINT"NEBENBED.KOEFFIZIENTEN :"
810 PRINT"---------------"
820 FOR I=1 TO M
830 PRINT"KOEFFIZ.DER NEBENBED.NR. ";I
840 FOR J=M+1 TO M+MN
845 IF BE>0 THEN READ A(I,J): GOTO 860
850 PRINT"ENTSCH.VARIABLE";I;",";J-M;"=": INPUT A(I,J)
860 PRINT"--ENTSCH.VARIABLE ";J-M;" =";A(I,J)
870 NEXT J:NEXT I
875 IF BE>0 THEN INPUT"WEITER ";C$
880 IF NB=0 THEN 920
890 FOR I=1 TO NB
900 A(NS+I,M+MN+I)=-1
910 NEXT I
920 FOR I=1 TO M: FOR J=1 TO N
930 IF XI(I)<>XJ(J) THEN 950
940 CI(I)=CJ(J)
950 NEXT J: NEXT I
960 IT=0
970 FOR J=1 TO N
980 Z(J)=0
990 FOR I=1 TO M
1000 Z(J)=Z(J)+CI(I)*A(I,J)
1010 NEXT I
1020 ZC(J)=Z(J)-CJ(J)
1030 NEXT J
1040 OB=0
1050 FOR I=1 TO M
1060 OB=OB+CI(I)*B(I)
1070 NEXT I
1080 PRINT: PRINT: PRINT
1090 PRINT"ITERATION NR.";IT
1100 PRINT"---------------"
1110 PRINT"BASIS VARIABLEN          WERT"
1120 FOR I=1 TO M
1130 PRINT"     X(";XI(I);")          ";INT(100*B(I)+.5)/100: NEXT I
1140 PRINT: N1=1: N2=8
1150 IF N2<=N THEN 1170
1160 N2=N
1170 PRINT"VARIABLEN DES SIMPLEX-TABLEAUS"
1180 FOR I=N1 TO N2
1190 PRINT "X(";XJ(I);");";
1200 NEXT I
1210 PRINT: PRINT
1220 REM
1230 PRINT"KOEFIZ.MATRIX A(I,J) :"
1240 PRINT"---------------"
1250 K=-10
1260 FOR I=1 TO M
1270 K=K-25: F=32
1280 FOR J=N1 TO N2
1290 F=F-32
1300 REM CURSOR
1310 PRINT INT(100*A(I,J)+.5)/100;" ";
1320 NEXT J: PRINT: NEXT I
1330 REM
1340 PRINT"MARG.DECK.BEITRAGSKOEFF. Z(J)-C(J) :"
1350 FOR I=N1 TO N2
1360 PRINT INT(100*ZC(I)+.5)/100;" ";
1370 NEXT I: PRINT
1380 IF N2>=N THEN 1410
1390 N1=N1+8: N2=N2+8
1400 GOTO 1150
1410 PRINT: PRINT"ZIEFFUNKTION Z = ";INT(100*OB+.5)/100: PRINT
1420 INPUT"WEITER ? J/N ";C$
1425 IF C$="N" THEN STOP
1430 IT=IT+1; CM=ZC(1): JM=1
1440 FOR J=2 TO N
1450 IF ZC(J)<=CM THEN 1470
1460 CM=ZC(J): JM=J
1470 NEXT J
1480 IF CM>0 THEN 1880
1490 M3=M+MN: M0=M+1
1500 IF M=NS THEN 1560
1510 FOR I=1 TO M
1520 M4=NS+1
1530 FOR J=M4 TO M
1540 IF XI(I)=XJ(J) THEN 1860
1550 NEXT J: NEXT I
1560 FOR K=M0 TO M3
1570 FOR I=1 TO M
1580 IF XJ(K)=XI(I) GOTO 1610
1590 NEXT I
1600 IF ZC(K)=0 THEN 1630
1610 NEXT K
1620 GOTO 1640
1630 PRINT"* MEHRERE OPT.LOESUNGEN MOEGLICH *"
1640 PRINT: PRINT: PRINT
1650 PRINT"*** OPTIMALE LOESUNG GEFUNDEN ***"
1660 PRINT"*** NACH ";IT;" ITERATIONEN ***"
1670 FOR I=1 TO M
1680 IF B(I)<>0 THEN 1710
1690 PRINT: PRINT"*** DEGENERIERTE LOESUNG ***"
1700 GOTO 1720
1710 NEXT I
1720 PRINT
1730 PRINT"---------------"
1740 PRINT"ENTSCH.VARIABLEN     WERT"
1750 PRINT"---------------"
1760 FOR I=1 TO M
1770 PRINT"     X(";XI(I);")          =";INT(1000*B(I)+.5)/1000
1780 NEXT I
1790 PRINT"! BEACHTE !": PRINT"ALLE VARIABLEN, DIE IN DIESER TABELLE"
1800 PRINT"NICHT GEZEIGT WERDEN,": PRINT"HABEN DER WERT 0."
1810 PRINT"---------------"
1820 IF PT=1 THEN PRINT"MAXIMUM Z = ";ABS(OB)
1830 IF PT=-1 THEN PRINT"MINIMUM Z = ";ABS(OB)
1840 PRINT"---------------"
1845 STOP
1850 PRINT: PRINT: PRINT: PRINT: PRINT: STOP
1860 PRINT: PRINT"*** UNBESCHRAENKTE LOESUNG ***"
1870 STOP
1880 XM=1.0E25: IM=0
1890 FOR I=1 TO M
1900 IF A(I,JM)<=0 THEN 1940
1910 XX=B(I)/A(I,JM)
1920 IF XX>=XM THEN 1940
1930 XM=XX: IM=I
1940 NEXT I
1950 IF IM>0 THEN 1980
1960 PRINT"*** LOESUNG UNMOEGLICH ***"
1970 STOP
1980 XX=A(IM,JM)
1990 B(IM)=B(IM)/XX
2000 FOR J=1 TO N
2010 A(IM,J)=A(IM,J)/XX
2020 NEXT J
2030 FOR I=1 TO M
2040 IF I=IM THEN 2100
2050 XX=A(I,JM)
2060 B(I)=B(I)-XX*B(IM)
2070 FOR J=1 TO N
2080 A(I,J)=A(I,J)-XX*A(IM,J)
2090 NEXT J
2100 NEXT I
2110 CI(IM)=CJ(JM)
2120 XI(IM)=XJ(JM)
2130 GOTO 970
2140 PRINT: PRINT: PRINT: PRINT: PRINT: END
10000 REM BEISPIEL 1
10010 DATA MAX,2,2,0,0
10020 DATA 4,3
10030 DATA 9,-2
10040 DATA 1,3,1,-2
11000 REM BEISPIEL 2
11010 DATA MAX,2,3,0,0
11020 DATA 1,-1
11030 DATA 0,1,-2
11040 DATA 2,-1,1,2,-2,-1
12000 DATA BEISPIEL 3
12010 DATA MAX 2,2,0,0
12020 DATA 2,1
12030 DATA 1,-6
12040 DATA -1,1,-1,-3
13000 REM BEISPIEL 4 KLEE-MINTY 3X3
13010 DATA MAX,3,3,0,0
13020 DATA 4,2,1
13030 DATA 5,25,125
13040 DATA 1,0,0,4,1,0,8,4,1
14000 REM BEISPIEL 5 KLEE-MINTY 4X4
14010 DATA MAX,4,4,0,0
14020 DATA 8,4,2,1
14030 DATA 8,25,125,625
14040 DATA 1,0,0,0,4,1,0,0,0,8,4,1,0,16,8,4,1

Listing Simplexmethode in Turbo Pascal/Free Pascal

Pascal
program simplex;
{$N+}
label
   60, 110, 400, 490, 580, 770, 780, 920, 950, 970;
label
 1150,1170,1410,1470,1560,1610,1630,1640,1710,1720;
label
 1860,1880,1940,1980,2100;
 
const
  MOG = 30;
  NOG = 30;
  OG1 = 3;
  OG2 = 5;
  OG3 = 10;
  OG4 = 15;
 
var
   B:array[1..MOG] of Double;
   CI:array[1..NOG] of Double;
   CJ:array[1..NOG] of Double;
   Z:array[1..NOG] of Double;
   ZC:array[1..NOG] of Double;
   XI:array[1..NOG] of integer;
   XJ:array[1..NOG] of integer;
   A:array[1..MOG,1..NOG] of Double;
   F,I,IM,IT,J,JM,K,M,M0,M3,M4,MN,N,N1,N2,NB,NE,NS,PT : integer;
   CM,OB,XM,XX : Double;
   c:string;
 
begin
writeln('SIMPLEX-METHODE');
writeln;
writeln('LINEARE PROGRAMMIERUNG');
writeln;
{REM}
60: writeln('MAXIMIERUNG ODER MINIMIERUNG'); write('(MAX/MIN/ENDE) ');readln(C);
IF C='ENDE' THEN halt;
IF (C<>'MAX') AND (C<>'MIN') THEN GOTO 60;
IF C='MIN' THEN PT:=-1; writeln('MINIMIERUNG DER ZIELFUNKTION'); GOTO 110;
writeln('MAXIMIERUNG DER ZIELFUNKTION');
110: PT:=1;
{rem}
write('ANZAHL DER ENTSCH.VARIAB.'); readln(MN);
writeln('ANZAHL DER ENTSCH.VARIAB. ',MN);
writeln;
writeln('ANZAHL DER NEBENBEDINGUNGEN'); writeln('(AUSGEN.NICHTNEGATIVE NEBENBEDINGUNGEN):');
write(' <= '); readln(NS);
writeln('KLEINER ODER GLEICH <= ? ',NS);
write(' >= '); readln(NB);
writeln('GROESSER ALS ODER GLEICH >= ? ',NB);
write('GLEICH = '); readln(NE);
writeln('GLEICH = ? ',NE);
M:=NS+NB+NE;
N:=M+MN+NB;
{DIM B(M),CI(N),CJ(N),Z(N),ZC(N),XI(N),XJ(N),A(M,N)}
writeln;
writeln('DEFINITION DER INDIZ. VARIABLE :'); writeln;
K:=1; FOR J:=M+1 TO M+MN DO
begin
 writeln('ENTSCHEIDUNGSVARIABLE ',K);
 XJ[J]:=K;
 writeln('= X(',XJ[J]:OG1,')');
 K:=K+1;
end;
{NEXT J:}
writeln;
IF NS<=0 THEN GOTO 400;
writeln('SCHLUPFVARIABLE(N) DER');
writeln('KLEINER ODER GLEICH'); writeln('NEBENBEDINGUNG :');
K:=MN+1; FOR J:=1 TO NS DO
begin
 write('NEBENBEDINGUNG ',J);
 XJ[J]:=K;
 writeln(' = X(',XJ[J]:OG1,')');
 K:=K+1;
end;
{ NEXT J:}
writeln;
FOR I:=1 TO N DO
begin
 CJ[I]:=0;
end;
{ NEXT I }
400: IF NB=0 THEN GOTO 490;
writeln('SCHLUPFVARIABLE(N) DER');
writeln('GROESSER ODER GLEICH'); writeln('NEBENBEDINGUNG');
writeln('( RESTVARIABLE(N) ):');
K:=M+MN+1; FOR J:=M+MN+1 TO N DO
begin
 write('NEBENBEDINGUNG ',J+NS-M-MN);
 XJ[J]:=K;
 writeln(' = X(',XJ[J]:OG1,')');
 K:=K+1;
end;
{NEXT J:}
writeln;
490: IF (NB=0) AND (NE=0) THEN GOTO 580;
writeln('KUENSTLICHE VARIABLE(N) FURE DIE');
writeln(' >= UND = NEBENBEDINGUNG :');
K:=MN+NS+1; FOR J:=NS+1 TO M DO
begin
 write('NEBENBEDINGUNG ',J);
 XJ[J]:=K;
 writeln(' = X(',XJ[J]:OG1,')');
 CJ[J]:=10000;
 K:=K+1;
end;
{ NEXT J:}
writeln;
580: FOR I:=1 TO M DO
begin
 XI[I]:=XJ[I];
end;
{ NEXT I }
writeln; writeln('KOEFFIZIENTEN DER ZIELFUNKTION :');
writeln('---------------');
FOR I:=M+1 TO M+MN DO
begin
 writeln('KOEFF.DER ENTSCH.VAR.'); writeln('X(',I-M,')= ');
 readln(CJ[I]);
 writeln('KOEFF.DER ENTSCH.VAR. ',I-M,' =',CJ[I]:OG3:OG2);
 CJ[I]:=CJ[I]*PT*(-1);
end;
{ NEXT I:}
writeln;
writeln('WERT DER RECHTEN SEITE');
writeln('---------------');
FOR I:=1 TO M DO
begin
 writeln('==DER NEBENBEDINGUNG ');
 writeln('X(',I,')='); readln(B[I]);
 writeln('==DER NEBENBEDINGUNG ',I,' = ',B[I]:OG3:OG2);
end;
{ NEXT I }
FOR I:=1 TO M DO
begin
 FOR J:=1 TO N DO
 begin
  IF I<>J THEN GOTO 770;
  A[I][J]:=1;
  GOTO 780;
  770: A[I][J]:=0;
  780: { }
 end;
end;
{ NEXT J: NEXT I }
writeln;
writeln('NEBENBED.KOEFFIZIENTEN :');
writeln('---------------');
FOR I:=1 TO M DO
begin
 writeln('KOEFFIZ.DER NEBENBED.NR. ',I);
 FOR J:=M+1 TO M+MN DO
 begin
  write('ENTSCH.VARIABLE',I,',',J-M,'='); readln(A[I][J]);
  writeln('--ENTSCH.VARIABLE ',J-M,' =',A[I][J]:OG3:OG2);
 end;
end;
{ NEXT J:NEXT I }
IF NB=0 THEN GOTO 920;
FOR I:=1 TO NB DO
begin
 A[NS+I][M+MN+I]:=-1;
end;
{ NEXT I }
920: FOR I:=1 TO M DO
begin
 FOR J:=1 TO N DO
 begin
  IF XI[I]<>XJ[J] THEN GOTO 950;
  CI[I]:=CJ[J];
  950: { }
 end;
end;
{ NEXT J: NEXT I }
IT:=0;
970: FOR J:=1 TO N DO
begin
 Z[J]:=0;
 FOR I:=1 TO M DO
 begin
  Z[J]:=Z[J]+CI[I]*A[I][J];
 end;
{ NEXT I }
 ZC[J]:=Z[J]-CJ[J];
end;
{ NEXT J }
OB:=0;
FOR I:=1 TO M DO
begin
 OB:=OB+CI[I]*B[I];
end;
{ NEXT I }
writeln; writeln; writeln;
writeln('ITERATION NR.',IT);
writeln('---------------');
writeln('BASIS VARIABLEN          WERT');
FOR I:=1 TO M DO
begin
 writeln('     X(',XI[I]:OG1,')          ',round(100*B[I])/100:OG3:OG2);
end;
{ NEXT I }
writeln;
N1:=1; N2:=8;
1150: IF N2<=N THEN GOTO 1170;
N2:=N;
1170: writeln('VARIABLEN DES SIMPLEX-TABLEAUS');
FOR I:=N1 TO N2 DO
begin
 writeln( 'X(',XJ[I]:OG1,');');
end;
{ NEXT I }
writeln; writeln;
{ REM }
writeln('KOEFIZ.MATRIX A(I,J) :');
writeln('---------------');
K:=-10;
FOR I:=1 TO M DO
begin
 K:=K-25; F:=32;
 FOR J:=N1 TO N2 DO
 begin
  F:=F-32;
  { REM CURSOR }
  write( round(100*A[I][J])/100:OG3:OG2,' ');
 end;
 { NEXT J: }
 writeln;
end;
{ NEXT I }
{ REM }
writeln('MARG.DECK.BEITRAGSKOEFF. Z(J)-C(J) :');
FOR I:=N1 TO N2 DO
begin
 write( round(100*ZC[I])/100:OG3:OG2,' ');
end;
{ NEXT I: }
writeln;
IF N2>=N THEN GOTO 1410;
N1:=N1+8; N2:=N2+8;
GOTO 1150;
1410: writeln; writeln('ZIEFFUNKTION Z = ',round(100*OB)/100:OG4:OG2); writeln;
write('WEITER ? J/N '); readln(C);
IF C='N' THEN HALT;
IT:=IT+1; CM:=ZC[1]; JM:=1;
FOR J:=2 TO N DO
begin
 IF ZC[J]<=CM THEN GOTO 1470;
 CM:=ZC[J]; JM:=J;
 1470: { }
end;
{ NEXT J }
IF CM>0 THEN GOTO 1880;
M3:=M+MN; M0:=M+1;
IF M=NS THEN GOTO 1560;
FOR I:=1 TO M DO
begin
 M4:=NS+1;
 FOR J:=M4 TO M DO
 begin
  IF XI[I]=XJ[J] THEN GOTO 1860;
 end;
end;
{ NEXT J: NEXT I }
1560: FOR K:=M0 TO M3 DO
begin
 FOR I:=1 TO M DO
 begin
  IF XJ[K]=XI[I] THEN GOTO 1610;
 end;
{ NEXT I }
 IF ZC[K]=0 THEN GOTO 1630;
 1610: { }
end;
{ NEXT K }
GOTO 1640;
1630: writeln('* MEHRERE OPT.LOESUNGEN MOEGLICH *');
1640: writeln; writeln; writeln;
writeln('*** OPTIMALE LOESUNG GEFUNDEN ***');
writeln('*** NACH ',IT,' ITERATIONEN ***');
FOR I:=1 TO M DO
begin
 IF B[I]<>0 THEN GOTO 1710;
 writeln; writeln('*** DEGENERIERTE LOESUNG ***');
 GOTO 1720;
 1710: { }
end;
{ NEXT I }
1720: writeln;
writeln('---------------');
writeln('ENTSCH.VARIABLEN     WERT');
writeln('---------------');
FOR I:=1 TO M DO
begin
 writeln('     X(',XI[I]:OG1,')          =',round(1000*B[I])/1000:OG3:OG2);
end;
{ NEXT I }
writeln('! BEACHTE !'); writeln('ALLE VARIABLEN, DIE IN DIESER TABELLE');
writeln('NICHT GEZEIGT WERDEN,'); writeln('HABEN DER WERT 0.');
writeln('---------------');
IF PT=1 THEN writeln('MAXIMUM Z = ',ABS(OB):OG4:OG2);
IF PT=-1 THEN writeln('MINIMUM Z = ',ABS(OB):OG4:OG2);
writeln('---------------');
readln(c);
HALT;
writeln; writeln; writeln; writeln; writeln; HALT;
1860: writeln; writeln('*** UNBESCHRAENKTE LOESUNG ***');
HALT;
1880: XM:=1.0E25; IM:=0;
FOR I:=1 TO M DO
begin
 IF A[I][JM]<=0 THEN GOTO 1940;
 XX:=B[I]/A[I][JM];
 IF XX>=XM THEN GOTO 1940;
 XM:=XX; IM:=I;
 1940: { }
end;
{ NEXT I }
IF IM>0 THEN GOTO 1980;
writeln('*** LOESUNG UNMOEGLICH ***');
HALT;
1980: XX:=A[IM][JM];
B[IM]:=B[IM]/XX;
FOR J:=1 TO N DO
begin
 A[IM][J]:=A[IM][J]/XX;
end;
{ NEXT J }
FOR I:=1 TO M DO
begin
 IF I=IM THEN GOTO 2100;
 XX:=A[I][JM];
 B[I]:=B[I]-XX*B[IM];
 FOR J:=1 TO N DO
 begin
  A[I][J]:=A[I][J]-XX*A[IM][J];
 end;
{ NEXT J }
 2100: { }
end;
{ NEXT I }
CI[IM]:=CJ[JM];
XI[IM]:=XJ[JM];
GOTO 970;
writeln; writeln; writeln; writeln; writeln;
end.

Abschluß

Die Lösungen der 4 Beispiele sehen richtig aus. Ich kann aber keine Garantie für
die Fehlerfreiheit der beiden Programme geben.

Die beiden Programme habe ich auch in meinem Notizbuch zum Download.
fav.php?uname=Delastelle

Viele Grüße
Ronald


Dieser Artikel kommt von Matroids Matheplanet
http://matheplanet.com

Die Url für diesen Artikel ist:
http://matheplanet.com/default3.html?article=1828