Текст подпрограммы и версий ( Фортран )
mlc2r.zip 		Тексты тестовых примеров ( Фортран )
tmlc2r.zip
Текст подпрограммы и версий ( Си )
mlc2r_c.zip 		Тексты тестовых примеров ( Си )
tmlc2r_c.zip
Текст подпрограммы и версий ( Паскаль )
mlc2r_p.zip 		Тексты тестовых примеров ( Паскаль )
tmlc2r_p.zip

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

Назначение

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

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

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

                        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.

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

    SUBROUTINE  MLC2R (A, M, N, MR, MAX, EPS, IERR) 
   Параметры
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  |

       INTEGER  A(8, 4), M, N, MR(24), MAX, IERR
       REAL  EPS
       DATA  A /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/
       DATA  M /8/,  N /4/,  MAX /10/,  EPS /0.001/
       CALL  MLC2R (A, M, N, MR, MAX, EPS, IERR)

Результаты:

      max  z   =  A(1, 1)  =  19

             x1  =  A(2, 1)  =  2
             x2  =  A(3, 1)  =  2
             x3  =  A(4, 1)  =  1