|
Текст подпрограммы и версий ml01r_p.zip |
Тексты тестовых примеров tml01r_p.zip |
Решение задачи линейного программирования модифицированным симплекс - методом.
Решается задача линейного программирования:
min (c, x) ( или max (c, x) ) ,
A x = b ,
x ≥ 0 ,
где A - матрица размерности m на n, x и c - векторы длины n, b - вектоp длины m.
Используется модифицированный симплекс - метод. Исходная информация задается в виде расширенной матрицы | a11 a12 . . . a1n
| . . . . . . . . . . . . . . . . . . . . . .
A1 = | am1 am2 . . . amn
| c1 c2 . . . cn
| am+2,1 am+2,2 . . . am+2,N
где ai j ( i = 1, ... , m ; j = 1, ... , n ) - элементы матрицы A ,
am+2, j = - ( a1 j + a2 j + ... + am j ) для j = 1, ... , n .
Вектоp b дополняется двумя компонентами bm + 1 = 0, bm + 2 = - (b1 + ... + bm).
Точность вычислений характеризуется величиной невязки
r = bm+2 - ∑ am+2, j x j .
j
С.Гасс, Линейное программирование, Физматгиз, 1961.
procedure ML01R(var A :Array of Real; M :Integer;
var U :Array of Real; N :Integer;
var X :Array of Real; var NB :Array of Integer;
var P :Integer; EPS :Real; var XK :Array of Real);
Параметры
| A - | вещественный двумерный массив размерности m + 2 на n, содержащий элементы расширенной матрицы A1; |
| M - | число стpок матрицы A1 (тип: целый); |
| U - | рабочий массив размерности M на M (тип: вещественный); |
| N - | число столбцов матрицы A1 (тип: целый); |
| X - |
вещественный вектоp длины M, при этом на входе
X (I) = bI,
I = 1, ..., M, на выходе для
I = 1, ... , M - 2 ; X (I) - ненулевые компоненты решения, X (M - 1) - минимальное (или максимальное) значение линейной формы, X (M) - величина невязки r; |
| NB - | вектоp длины M, содержащий номеpа ненулевых компонент решения т.е. xNB (I) = X (I) для I = 1, ... , M - 2 (тип: целый); |
| P - | целая переменная, при обращении к подпрограмме задается равной 1, если требуется найти максимум линейной формы, и не равной 1, в противном случае; на выходе: |
| P = 1 - | если найдено решение, |
| P = 2 - | если задача несовместна, |
| P = 3 - | если значение линейной формы неограничено; |
| EPS - | заданная абсолютная погрешность вычислений (тип: вещественный); |
| XK - | вещественный рабочий вектоp длины M. |
Версии: нет
Вызываемые подпрограммы: нет
Замечания по использованию
|
Задача должна быть приведена к виду, в котоpом компоненты вектоpа b неотрицательны. Подпрограмма рекомендуется для использования, если матрица A содержит много ненулевых элементов. Подпрограмма ML01R использует служебные подпрограммы MLU01, MLU02, MLU03, MLU04, MLU05, MLU06, MLU07, MLU08, MLU09, MLU10. |
Unit TML01R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, ML01R_p;
function TML01R: String;
implementation
function TML01R: String;
var
_i :Integer;
ХК :Array [0..4] of Real;
U :Array [0..24] of Real;
const
A :Array [0..19] of Real = ( 1.0,2.0,1.0,1.0,-4.0,2.0,1.0,2.0,2.0,-5.0,3.0,
5.0,1.0,3.0,-9.0,0.0,0.0,1.0,-1.0,-1.0 );
X :Array [0..4] of Real = ( 15.0,20.0,10.0,0.0,-45.0 );
NB :Array [0..4] of Integer = ( 0,0,0,0,0 );
P :Integer = 1;
M :Integer = 5;
N :Integer = 4;
EPS :Real = 0.01;
begin
Result := ''; { результат функции }
ML01R(A,M,U,N,X,NB,P,EPS,XK);
Result := Result + Format('%s',[' P=']);
Result := Result + Format('%3d ',[P]);
Result := Result + Format('%s',[#$0D#$0A + ' X=']);
Result := Result + #$0D#$0A;
for _i:=0 to 4 do
begin
Result := Result + Format('%20.16f ',[X[_i]]);
if ( ((_i+1) mod 4)=0 )
then Result := Result + #$0D#$0A;
end;
Result := Result + #$0D#$0A;
Result := Result + Format('%s',[#$0D#$0A + ' NB=']);
Result := Result + #$0D#$0A;
for _i:=0 to 4 do
begin
Result := Result + Format('%6d ',[NB[_i]]);
if ( ((_i+1) mod 4)=0 )
then Result := Result + #$0D#$0A;
end;
Result := Result + #$0D#$0A;
UtRes('TML01R',Result); { вывод результатов в файл TML01R.res }
exit;
end;
end.
Результаты:
X = ( 2.5, 2.5, 2.5, 15., -0.00 )
NB = ( 2, 3, 1 )
P = 1
то есть решение x = ( 2.5, 2.5, 2.5, 0. )
(c, x) = 15.0
невязка r = 0.00