Die Mathe-Redaktion - 24.04.2018 16:38 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 755 Gäste und 21 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Mathematik: Die Simplexmethode in Basic und Turbo Pascal/Free Pascal
Freigegeben von matroid am Mi. 21. Februar 2018 09:37:37
Verfasst von Delastelle -   199 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
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 ( 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
\(\endgroup\)

Link auf diesen Artikel Link auf diesen Artikel  Druckbare Version Druckerfreundliche Version  Einen Freund auf diesen Artikel aufmerksam machen Weitersagen Kommentare zeigen Kommentare  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist nicht im Verzeichnis der Arbeitsgruppe Alexandria eingetragen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
Verwandte Links
 
Besucherzähler 199


[Seitenanfang]

" Mathematik: Die Simplexmethode in Basic und Turbo Pascal/Free Pascal" | 0 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]