Линейное программирование. Метод Джордана-Гаусса.
Методы линейного программирования - численные методы решения оптимизационных задач, cводящихся к формальным моделям линейного программирования.
Как известно, любая задача линейного программирования может быть приведена к канонической модели минимизации линейной целевой функции с линейными ограничениями типа равенств. Поскольку число переменных в задаче линейного программирования больше числа ограничений (n > m), то можно получить решение, приравняв нулю (n - m) переменных, называемых свободными. Оставшиеся m переменных, называемых базисными, можно легко определить из системы ограничений-равенств обычными методами линейной алгебры. Если решение существует, то оно называется базисным. Если базисное решение допустимо, то оно называется базисным допустимым. Геометрически, базисные допустимые решения соответствуют вершинам (крайним точкам) выпуклого многогранника, который ограничивает множество допустимых решений. Если задача линейного программирования имеет оптимальные решения, то по крайней мере одно из них является базисным.
Метод Жордана-Гаусса (Jordan) почти ничем не отличается от классического метода Гаусса, только матрица системы приводится не к треугольному, а к диагональному единичному виду. Если отвлечься от перестановки строк и столбцов для выбора наивыгоднейшего ведущего элемента, то процесс выглядит так. Пусть нам дана система n линейных уравнений с таким же количеством неизвестных. Представим коэффициенты этой системы и свободные члены в виде расширенной матрицы A размером n*(n+1). Элементы матрицы будем обозначать a[i,j]. Выполним операции: для каждого i от 1 до n: . | для каждого k от n+1 до 1 с шагом (-1): . | | a[i,k] <- a[i,k]/a[i,i] . | для каждого j от 1 до n, не равного i: . | | для каждого k от n+1 до i с шагом (-1): . | | | a[j,k] <- a[j,k] - a[j,i]*a[i,k] .
После этого последний столбец матрицы A даст решение задачи. По сравнению с классическим методом Гаусса здесь отсутствует обратный ход, но общее число операций больше (хотя порядок по n одинаковый - n3). Особенно удобен метод Жордана-Гаусса для обращения матрицы. Если матрицу системы расширить не столбцом свободных членов, а единичной матрицей того же порядка, то после описанной процедуры на ее месте получится матрица, обратная заданной.
Листинг программы
function Divide(var V: Vector; D: real): boolean;
var
I: Integer;
begin
Result := true;
for I := Low(V) to High(V) do
if (V[I]=0) and (D=0) then V[I] := 0 else
if D<>0 then
V[I] := V[I] / D
else Result := false;
end;
procedure Multiply(var V: Vector; K: real);
var
I: Integer;
begin
for I := Low(V) to High(V) do
V[I] := V[I] * K;
end;
procedure Subtract(var V1, V2: Vector);
var
I: Integer;
begin
for I := Low(V1) to High(V1) do
V1[I] := V1[I] - V2[I];
end;
procedure TForm1.Button2Click(Sender: TObject);
var
M: Matrix;
i, j: integer;
k: real;
Report: TStringList;
begin
SetLength(M,StringGrid1.RowCount-1);
for I := Low(M) to High(M) do
SetLength(M[I],StringGrid1.ColCount-1);
for I := Low(M) to High(M) do
for J := Low(M[I]) to High(M[I]) do
M[I,J] := StrToInt(StringGrid1.Cells[J+1,I+1]);
Report := TStringList.Create;
Report.Add('<style> .matrix {text-align: right; padding-right: 0.5em; padding-left: 1em; margin: -4;} </style>');
Report.Add('<ol><p>Данная СЛАУ:');
MatrixToHTML(Report, M);
for I := Low(M) to High(M) do begin
Report.Add('<li><p>Избавляемся от коэффициентов перед <i>x<sub>' + IntToStr(I+1) + '</sub></i>:');
if M[i,i]<>1 then
if not Divide(M[I], M[I,I]) then begin // Приведение текущей строки
MessageBox(Handle, 'Деление на ноль: ...', 'Внимание', MB_OK + MB_ICONWARNING);
Report.Free;
Exit;
end;
for j := Low(M) to High(M) do begin
if I=j then Continue;
k := 1;
if M[I,I]<>M[J,I] then begin
k := M[J,I];
if not Divide(M[J], k) then begin
MessageBox(Handle, 'Деление на ноль: ...', 'Внимание', MB_OK + MB_ICONWARNING);
Report.Free;
Exit;
end;
end;
Subtract(M[j],M[I]);
if (k<>1) and (I>j) then Multiply(M[j], k);
end;
MatrixToHTML(Report, M);
end;
Report.SaveToFile(ExtractFilePath(Application.ExeName) + 'result.html');
Report.Free;
MessageBox(Handle, PChar('Создан файл отчета: ' + ExtractFilePath(Application.ExeName) + 'result.html'),
'Решение получено', MB_OK + MB_ICONINFORMATION);
WebBrowser1.Navigate(ExtractFilePath(Application.ExeName) + 'result.html');
end;
procedure TForm1.Button1Click(Sender: TObject);
var
N: Integer;
begin
N := StrToInt(LabeledEdit1.Text);
StringGrid1.RowCount := N+1;
StringGrid1.ColCount := N + 2;
end;
end.