Mathematik: Die Simplexmethode in Basic und Turbo Pascal/Free Pascal
Released by matroid on Mi. 21. Februar 2018 09:37:37 [Statistics]
Written by Delastelle - 561 x read [Outline] Printable version Printer-friendly version -  Choose language   
Software

\(\begingroup\) 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 (LinkLösen von linearen Optimierungsproblemen mittels Scilab und Octave). 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) \sourceon 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); \sourceoff 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) \sourceon 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 \sourceoff

Listing Simplexmethode in Turbo Pascal/Free Pascal

\sourceon 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. \sourceoff

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
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Optimierung :: Software :: Lineare Optimierung :
Die Simplexmethode in Basic und Turbo Pascal/Free Pascal [von Delastelle]  
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
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 561
 
Aufrufstatistik des Artikels
Insgesamt 59 externe Seitenaufrufe zwischen 2018.05 und 2022.11 [Anzeigen]
DomainAnzahlProz
https://google.com3254.2%54.2 %
https://google.de2033.9%33.9 %
https://yandex.ru23.4%3.4 %
http://google.de11.7%1.7 %
https://www.bing.com11.7%1.7 %
https://www.startpage.com11.7%1.7 %
http://google.com11.7%1.7 %
https://www.ecosia.org11.7%1.7 %

Häufige Aufrufer in früheren Monaten
Insgesamt 51 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2022 (31x)https://google.com/
2020-2022 (20x)https://google.de/

[Top of page]

"Mathematik: Die Simplexmethode in Basic und Turbo Pascal/Free Pascal" | 0 Comments
The authors of the comments are responsible for the content.

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]