Текст подпрограммы и версий
mlc3r_p.zip 		Тексты тестовых примеров
tmlc3r_p.zip

Подпрограмма:  MLC3R (модуль MLC3R_p)

Назначение

Решение задачи линейного целочисленного программирования модифицированным методом Гомори (полностью целочисленный алгоритм с компактным хранением исходной информации).

Математическое описание

Для решения задачи 

                        n
   max  ( z0  +  ∑  cj (-xj) ) ,     A x ≤ b ,   xj ≥ 0 ,
                       j=1

где  c и  x - целочисленные векторы из En, A - целочисленная матрица порядка  m на n,  b - целочисленный вектоp из Em,  z0 - заданное число, используется полностью целочисленный алгоритм Гомори. Исходная информация задается в компактной форме.

Ненулевые элементы матрицы условий A задаются в виде одномерного массива IA, каждый элемент которого содержит очередной (по стpокам) ненулевой элемент  ai j матрицы A и номер столбца  j в виде условного числа  ai j * 103 + j.

Количество ненулевых элементов в  i - ой стpоке матрицы задается в  i - ой компоненте вектоpа KV длины  m.

Руднева Т.Л., Яранов М.Г. Программная реализация полностью целочисленного алгоритма Гомори. В сб. "Математические вопросы задач оптимизации и управления", M., МГУ, 1981.

Использование 

procedure MLC3R(LIA :Integer; M :Integer; N :Integer;
                var IA :Array of Integer; var KV :Array of Integer;
                var X :Array of Integer; var C :Array of Integer;
                var Z :Integer; MAX :Integer;
                var B :Array of Integer; var MR :Array of Integer;
                EPS :Real; var IERR :Integer);


   Параметры
LIA - число ненулевых элементов в матрице A (тип: целый);
M - число стpок в матрице A (тип: целый);
N - число столбцов в матрице A (тип: целый);
IA - заданный целый вектоp длины LIA, содержащий ненулевые элементы исходной матрицы A по стpокам в виде условных чисел;
KV - заданный целый вектоp длины M, содержащий количество ненулевых элементов матрицы A по стpокам;
X - целый вектоp длины N + M (см. замечания по использованию);
C - заданный целый вектоp длины N, содержащий коэффициенты линейной формы;
Z - целая переменная; на входе содержит заданное значение  z0, на выходе - оптимальное значение целевой функции;
MAX - заданная оценка свеpху на сумму компонент вектоpа  x (тип: целый);
B - целая матрица N на N, используемая в подпрограмме как рабочая;
MR - целый вектоp длины 4 + 5N + 2 max (N, M), используемый в подпрограмме как рабочий;
EPS - заданная абсолютная точность округления вещественного числа до целого (тип: вещественный);
IERR - целая переменная, указывающая причину окончания процесса вычислений:
IERR= 0 - если найдено оптимальное решение;
IERR=65 - если решения не существует. 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
  1. 

Используются служебные подпрограммы: MLC32, MLC33, MLC34, MLC35, MLC36, MLC37, MLC38, MLC39, MLC3A, MLC3B, MLC3L, MLC3M, MLC3V.

  2. 

Задаваемое значение параметра MAX должно быть оценкой свеpху для суммы компонент вектоpа  x, т.е. 

                  n
                 ∑  xj ≤ MAX
                 j=1
  3. 

Hа входе первые N компонент вектоpа X полагаются равными нулю, а следующие M компонент должны содержать коэффициенты вектоpа ограничений  b. Hа выходе первые N компонент вектоpа X содержат оптимальное решение задачи, а M последующих - значения дополнительных переменных, т. е. X (N + I) = [b - Ax] I, I = 1,..., M.

  4.  B процессе вычислений производится округление некоторых вещественных чисел с использованием параметра EPS, 0 < EPS < 0.5. B частности, вещественное число Y заменяется целым K, если ABS (Y - K) ≤ EPS. Выбор конкретного значения параметра EPS во многом определяется коэффициентами условий задачи, однако, обычно EPS берется из интервала (10 - 7, 10 - 4).

Пример использования 

   Максимизировать        4 x1 + 5 x2 + x3

при условиях 
                3 x1  +  2 x2           ≤ 10
                  x1   +  4 x2           ≤ 11
                3 x1  +  3 x2  +  x3  ≤ 13 ,

                x1,  x2,  x3 ≥ 0 ,  целые


Unit TMLC3R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, MLC3R_p;

function TMLC3R: String;

implementation

function TMLC3R: String;
var
_i,IERR :Integer;
B :Array [0..8] of Integer;
MR :Array [0..24] of Integer;
const
IA :Array [0..6] of Integer = ( 3001,2002,1001,4002,3001,3002,1003 );
KV :Array [0..2] of Integer = ( 2,2,3 );
X :Array [0..5] of Integer = ( 0,0,0,10,11,13 );
Z :Integer = 0;
EPS :Real = 0.0001;
C :Array [0..2] of Integer = ( -4,-5,-1 );
LIA :Integer = 7;
M :Integer = 3;
N :Integer = 3;
МАХ :Integer = 19;
begin
Result := '';  { результат функции }
MLC3R(LIA,M,N,IA,KV,X,C,Z,MAX,B,MR,EPS,IERR);
Result := Result + Format('%s',[' IERR=']);
Result := Result + Format('%3d ',[IERR]);
Result := Result + Format('%s',[' Z=']);
Result := Result + Format('%3d ',[Z]);
Result := Result + Format('%s',[' X=']);
Result := Result + #$0D#$0A;
for _i:=0 to 5 do
 begin
  Result := Result + Format('%3d ',[X[_i]]);
  if ( ((_i+1) mod 4)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
UtRes('TMLC3R',Result);  { вывод результатов в файл TMLC3R.res }
exit;
end;

end.

Результаты:

       IERR  =  0
       Z  =  19
       X  =  (2, 2, 1)