j:=0;
while (a[j,i]=a[j,i1]) and (j if (j end; functionFind_nu(a:MyArray;m,n:integer; i,i1:integer):longint; {i - индекс лексикографическиминимального столбца} varj:integer; begin Find_nu:=1; j:=0; while (a[j,i]=a[j,i1]) and (j if (j end; procedureFull_Integer_Simplex(var x:MyArray_X; a:MyArray; m,n:integer); {Полностьюцелочисленный алгоритм задачи линейного целочисленного программирования, см. Ху Т. 'Целочисленноепрограммирование и потоки в сетях', стр. 300-309, a - матрица размером m+n+2*n+1, по аналогии: Требуется найти максимум z= - 10x1 - 14x2 - 21x3 2x1 + 2x2 + 7x3 >= 14 8x1 + 11x2 + 9x3 >= 12 9x1 + 6x2 + 3x3 >=10, тогда матрица абудет выглядеть: 1 10 14 21 0 -1 0 0 0 0 -1 0 0 0 0 -1 -14 -2 -2 -7 -12 -8 -11 -9 -10 -9 -6 -3 0 0 0 0, процедура возвращает вектор X, первые mкомпонент которого - искомое решение, если последняякомпонента вектора = 1, то решения не существует или оно = бесконечности} vari,i1:integer; j,j1:integer; alfa:real; begin repeat i:=1; while (i if i j:=1; while (j if j for i1:=1 ton-1 do if (a[i,i1] минимальный столбец} {выбор альфа} if j {Writeln(i,' ',j);readln;} alfa:=0; for i1:=1 to n-1 do if a[i,i1] begin j1:=Find_nu(a,m,n,j,i1); if (j1>0) and (-a[i,i1]/j1>alfa) thenalfa:=-a[i,i1]/j1; end; {writeln(alfa,' ',i,' ',j);readln;} {получение отсечения Гомори} for i1:=0to n-1 do if a[i,i1]>0 then a[m-1,i1]:=round(Int(a[i,i1]/alfa)) else begin a[m-1,i1]:=round(Int(a[i,i1]/alfa)); if Frac(a[i,i1]/alfa)0 then a[m-1,i1]:=a[m-1,i1]-1; end; Step_Dual_simplex(a,m,n,m-1,j); end; end; until (i>=m-1) or (j>=n); for i:=0 to m-1 do x[i]:=round(a[i,0]); if j>=n then x[m-1]:=1 else x[m-1]:=0; end; procedure Step_One_Simplex(vara:MyArray; m,n,i:integer); var i1,i2:integer; {Один шагпрямого целочисленного метода (производящая строка - последняя i - производящий столбец)} begin for i1:=0 to m-2 doa[i1,i]:=a[i1,i]/(-a[m-1,i]); for i2:=0 to n-1 do for i1:=0 to m-2 do if i2ithen a[i1,i2]:=a[i1,i2]+a[i1,i]*a[m-1,i2]; end; procedureDirect_Integer_Simplex(var x:MyArray_X; a:MyArray; m,n:integer); {Прямойцелочисленный алгоритм задачи целочисленного линейного программирования, см. Ху Т. 'Целочисленное программированиеи потоки в сетях', стр. 344-370, a - матрица размером m+n+3*n+1 по аналогии: требуется максимизировать z = x1 + x2 + x3 -4x1 + 5x2 + 2x3 -2x1 + 5x2 3x1 - 2x2 + 2x3 2x1 - 5x2 тогда матрица абудет выглядеть: 0 -1 -1 -1 4 -4 5 2 5 -2 5 0 6 3 -2 2 1 2 -5 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 10 1 1 1 - вэтой строке первое число - грубая max суммы небазисныхпеременных 0 0 0 0 -строка для отсечения Гомори, алгоритм работает только при a[i,0]>=0 возвращает вектор X - на месте единичнойматрицы искомое решение, если в последнейкомпоненте единица - ошибка при расчетах} vari,j,i1,j1:integer; bool:boolean; b,b1,b2:array of byte; r:real; begin SetLength(b,m);SetLength(b1,m); for i:=0 to m-1 do b1[i]:=0; {проверка условия оптимальности} bool:=false; for j:=1 to n-1 do if a[0,j] while bool do begin {поиск производящего столбца} bool:=false;j1:=0; for j:=1 to n-1 do begin if a[m-2,j]>0 then begin for i:=0 to m-3 do a[i,j]:=a[i,j]/a[m-2,j]; if not bool then begin j1:=j;bool:=true;end else ifLexikogr_few(a,m,n,j,j1) then j1:=j; end; end; {поиск производящей строки} for j:=1to n-1 do if a[m-2,j]>0 then for i:=0 to m-3 do a[i,j]:=a[i,j]*a[m-2,j]; for i:=0 to m-1 do b[i]:=0;