Текст подпрограммы и версий ( Фортран )
mlc3r.zip 		Тексты тестовых примеров ( Фортран )
tmlc3r.zip
Текст подпрограммы и версий ( Си )
mlc3r_c.zip 		Тексты тестовых примеров ( Си )
tmlc3r_c.zip
Текст подпрограммы и версий ( Паскаль )
mlc3r_p.zip 		Тексты тестовых примеров ( Паскаль )
tmlc3r_p.zip

Подпрограмма:  MLC3R

Назначение

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

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

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

                        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.

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

    SUBROUTINE  MLC3R (LIA, M, N, IA, KV, X, C, Z, MAX, B, MR, EPS,
                                             IERR) 
   Параметры
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 ,  целые

       INTEGER  IA(7), KV(3), X(6), C(3), B(3, 3), MR(25), Z
       REAL  EPS
       DATA  IA /3001, 2002, 1001, 4002, 3001, 3002, 1003/
       DATA  KV /2, 2, 3/,  X /0, 0, 0, 10, 11, 13/,  Z /0/,  EPS /0.0001/, 
      *           C /-4, -5, -1/,  LIA /7/,  M /3/,  N /3/, MAX /19/
       CALL  MLC3R (LIA, M, N, IA, KV, X, C, Z, MAX, B, MR, EPS, IERR)

Результаты:

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