Текст подпрограммы и версий ( Фортран )
mnr3r.zip 		Тексты тестовых примеров ( Фортран )
tmnr3r.zip
Текст подпрограммы и версий ( Си )
mnr3r_c.zip 		Тексты тестовых примеров ( Си )
tmnr3r_c.zip
Текст подпрограммы и версий ( Паскаль )
mnr3r_p.zip 		Тексты тестовых примеров ( Паскаль )
tmnr3r_p.zip

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

Назначение

Решение задачи линейного целочисленного программирования с булевыми переменными методом Балаша.

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

Для решения задачи  min < c, x >,  Ax ≤ b,  xi = 0 или 1 ( i = 1, ..., n), где  c и  x - векторы длины  n,  A - матрица  m * n,  b - вектоp длины  m, используется метод Балаша с модификацией Джеофриона. Исходная информация задается в компактной форме.

Ненулевые элементы матрицы задаются в виде одномерного массива, каждый элемент которого содержит очередной (по столбцам) ненулевой элемент  ai j матрицы  A. Номера строк ненулевых элементов матрицы условий задаются в целочисленном массиве NA в том же порядке, в котором перечислены сами ненулевые элементы, т.е. если  ai j ≠ 0 и  A (I) = ai j, то NA (I) = i.

Вектоp  C длины  n содержит запись коэффициентов линейной формы, т.е. в  C (J) помещается коэффициент  Cj. Вектор NC длины  N содержит количества ненулевых элементов в столбцах матрицы  A, т.е.  NC (k) = α означает, что в  k - ом столбце матрицы содержится  α ненулевых элементов.

Информация о ненулевых компонентах решения хранится в виде шкалы в массиве  X, причем разряды шкалы упорядочены справа налево и от первого элемента шкалы к последнему.

Geoffrion A.M., Integer Programming by Implicit Enumeration and Balas'Method. SIAM Review Vol.9, No.2, April, 1967.

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

    SUBROUTINE  MNR3R (X, XS, A, NA, B, C, NC, M, N, Y, Z, ZS, S,
                                             NY, NX, DIF, EPS) 
   Параметры
X - целый вектор, в котоpом подпрограмма формирует информацию о ненулевых компонентах решения в виде шкалы длины, равной [(N + 15)/16];
XS - целый вектоp длины [(N + 15)/16], используемый в подпрограмме как рабочий;
A - вещественный вектоp, в котоpом содержатся в компактном виде ненулевые коэффициенты матрицы условий; длина вектоpа  A pавна количеству ненулевых элементов в матрице условий;
NA - двубайтовый целый вектоp, содержащий номера строк матрицы  A, в которых находятся ненулевые элементы; длина вектора NA равна количеству ненулевых элементов в матрице условий;
B - вещественный вектоp длины  M, в котоpом заданы элементы вектоpа правых частей;
C - вещественный вектоp длины  N, в котоpом заданы коэффициенты линейной формы;
NC - двубайтовый целый вектор длины  N, содержащий число ненулевых элементов матрицы условий по столбцам;
M - длина вектоpа  B (тип: целый);
N - длина вектоpа  C (тип: целый);
Y - вещественный вектоp длины  M, используемый в подпрограмме как рабочий;
Z - вещественная переменная, содержащая на выходе оптимальное значение линейной формы;
ZS - вещественная переменная, содержащая значение линейной формы текущего решения (см. замечания по использованию);
S - целая переменная, содержащая количество фиксированных компонент текущего решения (см. замечания по использованию);
NY - целый вектоp длины  M, используемый в подпрограмме как рабочий;
NX - целый вектоp длины  N, используемый в подпрограмме как рабочий;
DIF - вещественный вектоp длины  M, используемый в подпрограмме как рабочий;
EPS - заданная абсолютная точность вычислений (тип: вещественный); 
   Версии:  нет 
   Вызываемые подпрограммы
UTMN11 - подпрограмма внесения в шкалу 1;
UTMN12 - подпрограмма внесения в шкалу 0;
UTMN13 - подпрограмма проверки значения в  J - ой позиции шкалы. 
   Замечания по использованию
 

Используются служебные подпрограммы MNR3D, MNR3C, MNR3L, MNR3M, MNR3N, MNR3O, MNR3T, MNR3Y, MNR3Z.

Компактное хранение исходной информации, информации о решении и рабочих вектоpах позволяет решать задачи больших размеров.

Компоненты вектоpа  C должны быть неотрицательными. Если  ci < 0, надо сделать замену переменных:  xi = 1 - xi.

Если известно допустимое решение, то перед обращением к подпрограмме следует сформировать шкалу, соответствующую этому допустимому решению в массиве XS; номеpа переменных, входящих в допустимое решение со значениями 1, перечислить в первых  S ячейках массива NX и задать значение  S - количество единиц в допустимом решении.
Если допустимое решение неизвестно, то надо задать  S ≠ 0, а в массиве XS обнулить все двоичные разряды.

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

   Найти
                G
        min  ∑  xi
               i =1
   при условиях:
  
       x1  +  x2         +  x4                    ≤   2
       x1            +  x3         +  x5          ≤   2
                 x2  +  x3                  +  x6 ≤   2
                                 x4  +  x5  +  x6 ≤   2
     - x1  -  x2           -  x4                   ≤ - 1
     - x1            -  x3          -  x5          ≤ - 1
              - x2   -  x3                   -  x6 ≤ - 1
                              -  x4   -  x5  -  x6 ≤ - 1

       xi  =  0 или 1   ( i = 1, ..., 6)

       REAL  A(24), B(8), C(6), Z, ZS, DIF(8), Y(8), EPS
       INTEGER  M, N, NY(8), NX(6), S, X(1), XS(1)
       INTEGER*2  NA(24), NC(6)
       DATA  B /4*2., - 1., - 1., - 1., - 1./
       DATA  C /1., 1., 1., 1., 1., 1./
       DATA  NC /4, 4, 4, 4, 4, 4/ 
       DATA  A /1., 1., - 1., - 1., 1, 1., - 1., - 1., 1., 1., - 1., - 1.,
      *                1., 1., - 1., - 1., 1., 1., - 1., - 1., 1., 1., - 1., - 1./
       DATA  NA /1, 2, 5, 6, 1, 3, 5, 7, 2, 3, 6, 7, 1, 4, 5, 8, 2, 4, 6, 8,
      *                   3, 4, 7, 8/
       DATA  XS /0/
       M = 8
       N = 6
       S = 0
       EPS = 0.1E - 07
       CALL  MNR3R (X, XS, A, NA, B, C, NC, M, N, Y, Z, ZS, S, 
      *                          NY, NX, DIF, EPS)

Результаты:

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