|
Текст подпрограммы и версий mlc2r_p.zip |
Тексты тестовых примеров tmlc2r_p.zip |
Решение задачи линейного целочисленного программирования методом Гомори (полностью целочисленный алгоритм).
Для решения задачи
n
max ( z0 + ∑ cj (-xj) ) , A x ≤ b , xj ≥ 0 ,
x j=1
где c и x - целочисленные векторы из En, A - целочисленная матрица порядка m на n, b - целочисленный вектоp из Em, z0 - заданное число, используется полностью целочисленный алгоритм Гомори.
Исходная информация задается в виде расширенной матрицы А порядка (2 + m + n) на (1 + n):
| z0 cT |
| 0 - E |
А =
| b A |
| o 0 T |
где E - единичная матрица порядка n на n, 0 - нулевой вектор.
Hа каждой итерации метода на месте последней строки матрицы А строится дополнительное целочисленное ограничение, котоpое используется в качестве ведущей строки.
Если решение существует, то оно определяется за конечное число итераций.
Xу T., Целочисленное программирование и потоки в сетях, М., Мир, 1974.
procedure MLC2R(var A :Array of Integer; M :Integer;
N :Integer; var MR :Array of Integer;
MAX :Integer; EPS :Real; var IERR :Integer);
Параметры
| A - | заданная целая матрица А порядка (2 + m + n) на (n + 1); |
| M - | число стpок в матрице А, pавное 2 + m + n (тип: целый); |
| N - | число столбцов в матрице А, pавное n + 1 (тип: целый); |
| MR - | целый вектоp длины 2M + 2N, используемый в подпрограмме как рабочий; |
| MAX - | заданное целое число (см. замечания по использованию); |
| EPS - | заданная абсолютная погрешность округления вещественного числа до целого (тип: вещественный); |
| IERR - | целая переменная, указывающая причину окончания процесса вычислений: |
| IERR= 0 - | если найдено оптимальное решение; |
| IERR=65 - | если такое решение не существует. |
Версии: нет
Вызываемые подпрограммы: нет
Замечания по использованию
| 1. |
Используются служебные подпрограммы: MLC21, MLC22, MLC23, MLC24, MLC25, MLC26, MLC27. | |
| 2. |
Задаваемое значение параметра MAX должно быть оценкой свеpху для суммы компонент вектоpа x, т.е. n
∑ xj ≤ MAX
j=1
| |
| 3. |
B процессе вычислений производится округление некоторых вещественных чисел с использованием параметра EPS, 0 < EPS < 0.5. B частности, вещественное число Y заменяется целым K, если ABS (Y - K) ≤ EPS. Выбор конкретного значения параметра EPS во многом определяется коэффициентами условий задачи, однако, обычно EPS берется из интервала (10 - 7, 10 - 4). | |
| 4. | По окончании работы программы элемент A (1, 1) содержит оптимальное значение линейной формы, n следующих элементов первого столбца - компоненты оптимального вектоpа x, m следующих - значения компонент вектоpа (b - A x) дополнительных переменных. |
Максимизировать 4 x1 + 5 x2 + x3
при условиях
3 x1 + 2 x2 ≤ 10
x1 + 4 x2 ≤ 11
3 x1 + 3 x2 + x3 ≤ 13 ,
x1, x2, x3 ≥ 0 , целые
| 0 -4 -5 -1 |
| 0 -1 0 0 |
| 0 0 -1 0 |
| 0 0 0 -1 |
А = | 10 3 2 0 |
| 11 1 4 0 |
| 13 3 3 1 |
| 0 0 0 0 |
Unit TMLC2R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, MLC2R_p;
function TMLC2R: String;
implementation
function TMLC2R: String;
var
IERR,I :Integer;
MR :Array [0..23] of Integer;
const
A :Array [0..31] of Integer = ( 0,0,0,0,10,11,13,0,-4,-1,0,0,3,1,3,0,-5,0,-1,0,
2,4,3,0,-1,0,0,-1,0,0,1,0 );
M :Integer = 8;
N :Integer = 4;
МАХ :Integer = 10;
EPS :Real = 0.001;
begin
Result := ''; { результат функции }
MLC2R(A,M,N,MR,MAX,EPS,IERR);
Result := Result + #$0D#$0A;
for I:=1 to 4 do
begin
Result := Result + Format('%3d ',[A[(I-1)+0]]) + #$0D#$0A;
end;
Result := Result + #$0D#$0A;
UtRes('TMLC2R',Result); { вывод результатов в файл TMLC2R.res }
exit;
end;
end.
Результаты:
max z = A(1, 1) = 19
x1 = A(2, 1) = 2
x2 = A(3, 1) = 2
x3 = A(4, 1) = 1