Текст подпрограммы и версий ( Фортран )
mlc4r.zip 		Тексты тестовых примеров ( Фортран )
tmlc4r.zip
Текст подпрограммы и версий ( Си )
mlc4r_c.zip 		Тексты тестовых примеров ( Си )
tmlc4r_c.zip
Текст подпрограммы и версий ( Паскаль )
mlc4r_p.zip 		Тексты тестовых примеров ( Паскаль )
tmlc4r_p.zip

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

Назначение

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

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

Постановка задачи: найти максимум (a, x) при условиях: 

                         Ax  ≤  b
                       n
                      ∑  x j  ≤  L  ,
                     j =1
 где   x ≥ 0    - целый вектор длины  n,
         a          - заданный целый вектор длины  n,
         A         - заданная целая матрица размеров  m*n,
         b ≥ 0    - заданный целый вектор длины  m,
         L > 0   - заданное целое число.

Для решения задачи используется оригинальная модификация метода Юнга. Эта модификация удобна, когда матрица A слабо заполнена. Ненулевые элементы матрицы хранятся компактно в одномерном массиве в виде ai j*1000 + j. В отдельном целочисленном массиве длины  m хранятся количества ненулевых элементов в строках матрицы A. В процессе вычислений преобразуется только небазисная матрица размеров n * n .

Т.Ху. Целочисленное программирование и потоки в сетях. Изд - во "Мир", М., 1974.

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

    SUBROUTINE  MLC4R (NA, NS, NAI, NAJ, L, NB, NR, M, N, N1, MN,
                                              IT, TMAX, IERR) 
   Параметры
NA - заданный целый массив длины MN, в котором упакованы ненулевые элементы матрицы A (по строкам) по формуле ai j * 1000 + j;
NS - заданный целый вектор длины  m, содержащий количество ненулевых элементов в строках матрицы A;
NAI - заданный вектор правых частей длины  m (тип: целый);
NAJ - заданный вектор коэффициентов линейной формы длины  n (тип: целый);
L - заданная целая переменная (верхняя граница на сумму компонент вектора  x);
NB - целый рабочий массив размеров (n + 1) * (n + 1);
NR - целый рабочий вектор длины 4 * (m + n + 2), на выходе в первых (m + n + 2) элементах вектора NR находится решение;
M - M = m, целая переменная, число строк в матрице A;
N - N = n, целая переменная, число столбцов в матрице A;
N1 - N1 = n + 1, размер рабочей матрицы;
MN - число ненулевых элементов в матрице A, тип целый;
IT - заданное максимальное число итераций, на выходе - выполненное число итераций, тип целый;
TMAX - заданное максимальное время работы программы (в секундах), тип вещественный;
IERR - целая переменная, указывающая причину окончания счета;
IERR= 1 - найдено оптимальное решение;
IERR= 2 - выполнено заданное число итераций;
IERR= 3 - истекло время;
IERR=65 - выполнилось ограничение 
       n
       ∑   x j  =  L 
      j =1 
   Версии:  нет 
   Вызываемые подпрограммы:  UTMN05 
   Замечания по использованию
 

Для упаковки ненулевых элементов матрицы A удобно воспользоваться вспомогательной подпрограммой SUBROUTINE  UTMLC ( IV, N, IW), которая из целого вектора IV длины N строит целый вектор длины N/2, упаковывая каждую пару компонент вектора IV в одну компоненту вектора IW по формуле: 

          IW(( I - 1)/2 + 1)  =  IV( I ) + IV( I + 1)*1000.

Таким образом, если в векторе IV перечислить номера столбцов и значения ненулевых элементов матрицы A (по строкам) в виде: номер столбца, значение элемента матрицы, номер столбца, значение ... и т.д., то обратившись к подпрограмме UTMLC мы получим требуемое представление исходной информации.

Вектор - решение хранится в первых m + n + 1 элементах вектора NR, причем NR (1) - значение линейной формы, NR (2) ÷ NR (m + 1) - невязки в ограничениях, равные  b - Ax,  NR (m + 2) ÷ NR (m + n + 1) - компоненты вектора  x.

Счет можно закончить по заданному числу итераций или по времени. При этом вектор  x может не быть оптимальным, но обязательно будет допустимым.

Если ограничения в задаче имеют вид Ax ≥ b,  b ≥ 0,  x ≥ 0, целые, то иногда может помочь замена переменных  yj = K - xj, где K ≥ xj для всех  j = 1, ..., n. Подставим  xj = K - yj в функционал и систему ограничений:

найти  max (- a, y) при условиях - Ay + AK ≥ b или Ay ≤ AK - b, где K - вектор - столбец, все элементы которого равны K. 

                    n                         n
                   ∑   yj  =  nK  -   ∑   x j
                  j =1                     j =1
                            n
                           ∑  yj  ≤  nK
                          j =1

Если вектор AK - b ≥ 0, то задача имеет требуемый вид.

Если задача поставлена на минимум, переходим к поиску максимума, изменив знаки у вектора коэффициентов линейной формы.

Количество итераций не всегда связано с размерами задачи и оценке не поддается.

При IERR = 1 и IERR = 2 допустимое решение может оказаться оптимальным.

Используются служебные подпрограммы: MLC4B, MLC4C, MLC4D, MLC4O, MLC4P, MLC4W, UTMN05, UTMN06.

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

Найти максимум   x0  =  x1 + x2 + x3 при условиях: 

              - 4x1 + 5x2 + 2x3  ≤ 4
              - 2x1 + 5x2            ≤ 5
                 3x1 -  2x2 + 2x3 ≤ 6
                 2x1 -  5x2           ≤ 1
                   x1 +   x2  +   x3 ≤ 10 

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

Решение:  x0 = 5 ,  x1 = 3 ,  x2 = 2 ,  x3 = 0

       INTEGER  NA(10), NS(4), NAI(4), NAJ(3), L, NB(4,4), 
      *                 NR(36), M, N, N1, IT, IV(20), IERR
       REAL  TMAX 
       DATA  IV /1, - 4, 2, 5, 3, 2, 1, - 2, 2, 5, 1, 3, 2, - 2, 3, 2, 1, 2, 2, - 5/ 
       DATA  NS /3, 2, 3, 2/ 
       DATA  NAI /4, 5, 6, 1/,  NAJ /1, 1, 1/ 
       DATA  M, N, N1, L, IT, TMAX /4, 3, 4, 10, 20, 60./ 
       CALL  UTMLC (IV, 20, NA) 
       CALL  MLC4R (NA, NS, NAI, NAJ, L, NB, NR, M, N, N1, MN,
      *                          IT, TMAX, IERR)

Результаты решения: 

   IERR = 1 
   NR(1) ÷ NR(8) :  5   6   1   1   5   3   2   0

Таким образом,  (a, x)  =  5, невязки по строкам матрицы условий равны, соответственно, (6, 1, 1, 5),  вектор - решение  x = (3, 2, 0).