Discussion :

[oundou]

bonjour à tous,

j'ai un probleme avec le simplex, les résultats sont erronés, et je n'arrive pas à détecter l'erreur, est ce q qlq peut m'aider, svp, c urgent !

merci

[ram-0000]

Bien sûr, montre nous ton code et explique nous ton problème

[oundou]

merci ram,

bon, j'utilise le delphi, et le programme du simplex est dans un module séparé, les procedures du programme sont :



Procedure Data; // remplissage du tableau initial
Var R1,R2: real;

I,J: Integer;
Begin

XERR := 0;
nv := nbVar;
nc := nbCtr+nbVar;
setlength(ts,nc+2,nv+2);
setlength(tabvar,nbvar);

for i := 0 to nc+1 do
for j := 0 to nv+1 do
ts[i,j] := 0;

//writeln(' INPUT COEFFICIENTS OF ECONOMIC FUNCTION:');
FOR J := 1 TO NV DO
begin
R2 := obj[j];
TS[1, J + 1] := R2 * R1 ;
end;
//write(' Right hand side ? '); readln(R2);
R2 := 0;
TS[1, 1] := R2 * R1;
FOR I := 1 TO NC-nv DO
begin

// writeln(' CONSTRAINT X', I);
FOR J := 1 TO NV DO
begin
R2 := A[i-1,j-1];
TS[I + 1, J + 1] := -R2 ;
end;
//write(' Right hand side ? '); readln(TS[I + 1, 1])
TS[I + 1, 1] := B[0];
end;

for i := nc-nv+2 to nc+1 do
begin
ts[i,i-nc+nv] := -1;
ts[i,1] := dom5;
end;

FOR J := 1 TO NV DO TS[0, J + 1] := J;
FOR I := NV + 1 TO NV + NC DO TS[I - NV + 1, 0] := I;

End;

Procedure Pivot; Forward;
Procedure Formula; Forward;
Procedure Optimize; Forward;
Procedure ecriture; Forward;

{procedure principale du simplexe *****************************************************************}
Procedure SIMPLEX1;
Label 10;
Begin
10: PIVOT;
FORMULA;
OPTIMIZE;
IF NOPTIMAL = 1 THEN GOTO 10
End;

{pivot ********************************************************************************************}
Procedure PIVOT;

Var RAP,V,XMAX: real;
I,J: Integer;
Begin
XMAX := 0.0;
FOR J := 2 TO NV + 1 DO
begin
IF (TS[1, J] > 0) AND (TS[1, J] > XMAX) THEN
begin
XMAX := TS[1, J];
P2 := J
end
end;
RAP := 999999.0;
FOR I := 2 TO NC + 1 DO
begin
IF TS[I, P2] < 0 THEN
begin
V := ABS(TS[I, 1] / TS[I, P2]);
IF V < RAP THEN
begin
RAP := V;
P1 := I
end;
end;
end;
V := TS[0, P2]; TS[0, P2] := TS[P1, 0]; TS[P1, 0] := V
End;


Procedure FORMULA;{******************************************************************************}
Var I,J: Integer;
Begin
FOR I := 1 TO NC + 1 DO
begin
IF I <> P1 THEN // ligne non pivot
FOR J := 1 TO NV + 1 DO
begin
IF J <> P2 THEN // colonne non pivot
TS[I, J] := TS[I, J] - TS[P1, J] * TS[I, P2] / TS[P1, P2];
end;
end;
TS[P1, P2] := 1.0 / TS[P1, P2];
FOR J := 1 TO NV + 1 DO
begin
IF J <> P2 THEN
TS[P1, J] := TS[P1, J] * ABS(TS[P1, P2]);
end;
FOR I := 1 TO NC + 1 DO
begin
IF I <> P1 THEN
TS[I, P2] := TS[I, P2] * TS[P1, P2];
end
End;

Procedure OPTIMIZE;{*******************************************************************************}
Label 10;
Var I,J: Integer;
Begin
FOR I := 2 TO NC + 1 DO
IF TS[I, 1] < 0 THEN XERR := 1;
NOPTIMAL := 0;
IF XERR = 0 THEN
FOR J := 2 TO NV + 1 DO
IF TS[1, J] > 0 THEN NOPTIMAL := 1;
End;

Procedure RESULTS;{********************************************************************************}
Label 30,70,100;
Var I,J: Integer;
Begin
IF XERR = 0 THEN GOTO 30;
// writeln(' NO SOLUTION.');
GOTO 100;
30:
if xerr = 0 then
begin
for i := 0 to nbvar-1 do
tabvar[i] := 0;

FOR I := 1 TO NV DO
FOR J := 2 TO NC + 1 DO
begin
IF TS[J, 0] = I THEN
begin
form5.Memo3.Lines.Add('X'+inttostr(I)+' = '+floattostr(TS[J, 1])+', ');
// writeln;
// writeln(' VARIABLE X', I,': ', TS[J, 1]:8:2);
tabvar[i-1] := TS[J, 1];
end;
70: end;
// writeln;
form5.Memo3.Lines.Add('Z = '+floattostr(TS[1, 1]));
// writeln(' ECONOMIC FUNCTION: ', TS[1, 1]:8:2);
100://writeln; writeln
end;
End;

mon pb est q ce programme marche bien avec qlq instances, mais il donne des résultats erronés avec d'autres,

[oundou]

j'ai copié ce code pascal de l'internet, et je l'ai modifié.
j'ai l'impression que ce programme ne marche qu'avec les systèmes linéaires tels que les les constantes (partie droite des contraintes) des contraintes sont positifs.

[oundou]

le code pascal original est le suivant :


PROGRAM SIMPLEX;
Uses Crt;

Const
CMAX = 10; {max. number of variables in economic function}
VMAX = 10; {max. number of constraints}

Var
NC, NV, NOPTIMAL,P1,P2,XERR: Integer;
TS: Array[0..CMAX,0..VMAX] of real;

{introduction des données****************************************************************}

Procedure Data;
Var R1,R2: real;

I,J: Integer;
Begin
writeln;
writeln(' LINEAR PROGRAMMING');
writeln;


write(' NUMBER OF VARIABLES OF ECONOMIC FUNCTION ? '); readln(NV);
writeln;
write(' NUMBER OF CONSTRAINTS ? '); readln(NC);
writeln;

R1 := 1;

writeln(' INPUT COEFFICIENTS OF ECONOMIC FUNCTION:');
FOR J := 1 TO NV DO
begin
write(' X',J,' ? '); readln(R2);
TS[1, J + 1] := R2 * R1
end;
write(' Right hand side ? '); readln(R2);
TS[1, 1] := R2 * R1;
FOR I := 1 TO NC DO
begin
writeln;
writeln(' CONSTRAINT X', I);
FOR J := 1 TO NV DO
begin
write(' X',J,' ? '); readln(R2);
TS[I + 1, J + 1] := -R2
end;
write(' Right hand side ? '); readln(TS[I + 1, 1])
end;
writeln;
writeln(' RESULTS:');
writeln;
FOR J := 1 TO NV DO TS[0, J + 1] := J;
FOR I := NV + 1 TO NV + NC DO TS[I - NV + 1, 0] := I;

End;

Procedure Pivot; Forward;
Procedure Formula; Forward;
Procedure Optimize; Forward;
Procedure ecriture; Forward;

{procedure principale du simplexe *****************************************************************}
Procedure SIMPLEX1;
Label 10;
Begin
10: PIVOT;
FORMULA;
OPTIMIZE;
IF NOPTIMAL = 1 THEN GOTO 10
End;

{pivot ********************************************************************************************}
Procedure PIVOT;
Label 100;
Var RAP,V,XMAX: real;
I,J: Integer;
Begin
XMAX := 0.0;
FOR J := 2 TO NV + 1 DO
begin
IF (TS[1, J] > 0) AND (TS[1, J] > XMAX) THEN
begin
XMAX := TS[1, J];
P2 := J
end
end;
RAP := 999999.0;
FOR I := 2 TO NC + 1 DO
begin
IF TS[I, P2] >= 0 THEN GOTO 100;
V := ABS(TS[I, 1] / TS[I, P2]);
IF V < RAP THEN
begin
RAP := V;
P1 := I
end;
100: end;
V := TS[0, P2]; TS[0, P2] := TS[P1, 0]; TS[P1, 0] := V
End;


Procedure FORMULA;{******************************************************************************}
Label 60,70,100,110;
Var I,J: Integer;
Begin
FOR I := 1 TO NC + 1 DO
begin
IF I = P1 THEN GOTO 70;
FOR J := 1 TO NV + 1 DO
begin
IF J = P2 THEN GOTO 60;
TS[I, J] := TS[I, J] - TS[P1, J] * TS[I, P2] / TS[P1, P2];
60: end;
70: end;
TS[P1, P2] := 1.0 / TS[P1, P2];
FOR J := 1 TO NV + 1 DO
begin
IF J = P2 THEN GOTO 100;
TS[P1, J] := TS[P1, J] * ABS(TS[P1, P2]);
100: end;
FOR I := 1 TO NC + 1 DO
begin
IF I = P1 THEN GOTO 110;
TS[I, P2] := TS[I, P2] * TS[P1, P2];
110: end
End;

Procedure OPTIMIZE;{*******************************************************************************}
Label 10;
Var I,J: Integer;
Begin
FOR I := 2 TO NC + 1 DO
IF TS[I, 1] < 0 THEN XERR := 1;
NOPTIMAL := 0;
IF XERR = 1 THEN GOTO 10;
FOR J := 2 TO NV + 1 DO
IF TS[1, J] > 0 THEN NOPTIMAL := 1;
10: End;

Procedure RESULTS;{********************************************************************************}
Label 30,70,100;
Var I,J: Integer;
Begin
IF XERR = 0 THEN GOTO 30;
writeln(' NO SOLUTION.'); GOTO 100;
30: FOR I := 1 TO NV DO
FOR J := 2 TO NC + 1 DO
begin
IF TS[J, 0] <> I THEN GOTO 70;

writeln;
writeln(' VARIABLE X', I,': ', TS[J, 1]:8:2);

70: end;
writeln;
writeln(' ECONOMIC FUNCTION: ', TS[1, 1]:8:2);
100:writeln; writeln
End;

procedure ecriture;{Affichage d'une matrice de N lignes et P colonnes *****************************}
var I, J : integer ;
begin
writeln('tab ');
for I := 1 to Nv+1 do
begin
for J := 1 to nc+1 do

write (' ',TS[I, J]:8:2,' ' );
writeln { passage à la ligne}

end
end ;








{main program}

BEGIN

Data;
ecriture;
Simplex1;
ecriture;
Results;
ReadKey;

END.

{end of file simplex.pas}



je veux savoir est ce que ce programme est correct ?