Текст подпрограммы и версий
mlc6r_c.zip 		Тексты тестовых примеров
tmlc6r_c.zip

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

Назначение

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

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

   Решается задача
                       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.

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

    int mlc6r_c (integer *a, integer *b, integer *c,
            integer *ierr, integer *m, integer *min, integer *n, integer *p,
            integer *q, real *up, integer *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_c и utmlci_c. 

     int utmlcn_c(integer *i, integer *ai)

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

      int utmlci_c(int *a1, int *na1, int *a)

Упаковывает попарно массив целых чисел. На входе: a1 - массив целых чисел вида ..., i, ai, ... , предназначенных для попарной упаковки; na1 - длина массива a1. На выходе: a - массив, состоящий из условных целых чисел, полученных после упаковки.

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

int utmlc1_c(int *a, int *na, int *c, int *n)

Входные параметры:
- Целочисленный вектор a длины na содержит ненулевые элементы матрицы условий в компактной форме.
- Целочисленный вектор c длины n содержит коэффициенты линейной формы, упакованные вместе с информацией о количестве элементов в столбцах матрицы условий.

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

При работе подпрограммы mlc6r_c вызываются следующие служебные подпрограммы mlc6r1_c, mlc6r2_c, mlc6r3_c, mlc6r4_c, mlc6r5_c, utmlcj_c, utmlcp_c.

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

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

      (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)  .
  

int main(void)
{
    /* Initialized data */
    static int a1[16] = { 1,1,2,1,1,1,2,1,1,1,2,1,1,1,2,1 };
    static int c1[8] = { 2,-1,2,-2,2,-3,2,-4 };
    static int b[2] = { 2,4 };
    static int n = 4;
    static int m = 2;
    static int q = 1;
    static int x[4] = { 0,0,0,0 };
    static float up[2] = { 600.f,1.f };

    /* Local variables */
    static int ierr;
    extern int mlc6r_c(int *, int *, int *, int *, int *, int *, int *,
                       int *, int *, float *, int *);
    static int a[8], c__[4], p[2];
    extern int utmlci_c(int *, int *, int *);
    static int min__;

    utmlci_c(a1, &c__16, a);
    utmlci_c(c1, &c__8, c__);
/* l10: */
    mlc6r_c(a, b, c__, &ierr, &m, &min__, &n, p, &q, up, x);

    printf("\n %5i \n", min__);
    printf("\n %5i %5i %5i %5i \n", x[0], x[1], x[2], x[3]);
    printf("\n %10.3e %10.3e \n", up[0], up[1]);
    return 0;
} /* main */


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

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

      min__  =  - 7 
      x  =  0011