Текст подпрограммы и версий ( Фортран )
mlc6r.zip 		Тексты тестовых примеров ( Фортран )
tmlc6r.zip
Текст подпрограммы и версий ( Си )
mlc6r_c.zip 		Тексты тестовых примеров ( Си )
tmlc6r_c.zip
Текст подпрограммы и версий ( Паскаль )
mlc6r_p.zip 		Тексты тестовых примеров ( Паскаль )
tmlc6r_p.zip

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

Назначение

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

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

   Решается задача
                       N
             min    ∑  cj x j ,
                     j =1
          n
         ∑  ai j x j  =  bj ,     i = 1, ..., Q
        j =1
          n
         ∑  ai j x j  ≤  bj ,     i = Q + 1, ..., M ,
        j =1  
         x j  =  0  или  1   ( j = 1,...,N ) ,

 где   c  =  ( c1, ... , cN ) - целый вектор длины N ,
         b  =  ( b1, ... , bM ) - целый вектор длины M ,
         ai j   - элементы целочисленной матрицы размеров M на N

Используется метод вектора спада. Исходная информация задается в компактной форме (см.замечания по использованию)

Сергиенко И.В., Лебедев Т.Т., Рощин В.А. "Приближенные методы решения дискретных задач оптимизации", Киев, "Наука думка", 1980.

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

    SUBROUTINE  MLC6R (A, B, C, IERR, M, MIN, N, P, Q, UP, X) 
   Параметры
A - целый вектор, в котором в упакованном виде хранятся ненулевые элементы матрицы условий, упорядоченные по столбцам; длина вектора A равна количеству ненулевых элементов в матрице условий;
B - целый вектор длины M, в котором содержатся коэффициенты вектора ограничений;
C - целый вектор длины N, в котором компактно заданы коэффициенты линейной формы и информация о количестве ненулевых элементов в столбцах исходной матрицы;
IERR - целая переменная, указывающая причину выхода из подпрограммы
IERR= 0 - найден локальный минимум;
IERR= 5 - истекло заданное время;
IERR=65 - не найдена допустимая точка;
M - число строк в матрице условий, т.е. общее количество ограничений (тип: целый);
MIN - целая переменная, содержащая на выходе наименьшее найденное значение линейной формы (если была найдена допустимая точка);
N - длина вектора X (тип: целый);
P - целый рабочий вектор длины M;
Q - количество ограничений - равенств (тип: целый);
UP - вещественный вектор управляющих параметров длины 2:
UP(1) - время, отведенное центральному процессору на решение задачи, задается пользователем в секундах; на выходе содержит время в секундах, затраченное на решение задачи;
UP(2) - признак печати сообщения о завершении работы подпрограммы:
UP(2)=0. - печати не будет;
UP(2)=1. - будет напечатано сообщение о причине окончания работы подпрограммы;
X - целый вектор длины N; при обращении к подпрограмме содержит заданную начальную точку, на выходе - решение задачи, т.е. ту точку, в которой найдено наименьшее значение линейной формы 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
 

Матрица условий должна быть представлена в компактной форме. Ее ненулевые элементы задаются в виде вектора A, каждый элемент которого содержит очередной (по столбцам) ненулевой элемент  ai j матрицы условий и номер строки  i  в виде условного числа  ai j * 1000 + i.

Количество ненулевых элементов в  j - том столбце матрицы задается вместе с  j - тым коэффициентом линейной формы в виде условного числа в векторе C.

Для упаковки исходной информации можно воспользоваться служебными подпрограммами UTMLCN и UTMLCI. 

      SUBROUTINE  UTMLCN (I, AI)

Упаковывает два целых числа  I, AI, где  I < 1000, в одно условное целое число AI * 1000 + I. На выходе параметр AI содержит требуемое условное число. 

      SUBROUTINE  UTMLCI (A1, NA1, A)

Упаковывает попарно массив целых чисел. На входе: A1 - массив целых чисел вида ..., I, AI, ... , предназначенных для попарной упаковки; NA1 - длина массива A1. На выходе: A - массив, состоящий из условных целых чисел, полученных после упаковки.

Для проверки правильности задания входной информации можно воспользоваться подпрограммой UTMLC1, которая распечатывает упакованную матрицу условий: 

     SUBROUTINE  UTMLC1 (A, NA, C, N)

Входные параметры:
- Целочисленный вектор A длины NA содержит ненулевые элементы матрицы условий в компактной форме.
- Целочисленный вектор C длины N содержит коэффициенты линейной формы, упакованные вместе с информацией о количестве элементов в столбцах матрицы условий.

Если из заданной начальной точки допустимая точка не будет найдена, рекомендуется взять другую начальную точку.
Подпрограмма MLC6R гарантирует локальный минимум в области, не меньшей, чем окрестность радиуса 3 полученной точки минимума.

При работе подпрограммы MLC6R вызываются следующие служебные подпрограммы MLC6R1, MLC6R2, MLC6R3, MLC6R4, MLC6R5, UTMLCJ, UTMLCP.

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

 Найти минимальное значение функции

      (C, X)  =  - x1 - 2x2 - 3x3 - 4x4 

при условиях

        x1 + x2 + x3 + x4  =  2 
        x1 + x2 + x3 + x4  ≤  4  ,

где все    x j  =  0  или  1 ,    j = 1, 2, 3, 4  .

Начальное приближение   X  =  (0, 0, 0, 0)  .
  
       INTEGER  A, A1, B, C, C1, N, M, Q, P, X, NOM, AN 
       REAL  UP 
       DIMENSION  A(8), A1(16), B(2), C(4), C1(8), P(2), UP(2), X(4) 
       DATA  A1 /1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1/ 
       DATA  C1 /2, - 1, 2, - 2, 2, - 3, 2, - 4/ 
       DATA  B, N, M, Q /2, 4, 4, 2, 1/ 
       DATA  X /4*0/ 
       DATA  UP /600., 1./ 
       CALL  UTMLCI (A1, 16, A) 
       CALL  UTMLCI (C1, 8, C) 
 10  CONTINUE 
       CALL  UTMLC1 (A, 8, C, 4) 
       CALL  MLC6R (A, B, C, IERR, M, MIN, N, P, Q, UP, X) 
       END 

Результаты счета: 

Подпрограмма MLC6R, библиотека НИВЦ МГУ

      MIN  =  - 7 
      X  =  0011