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

Назначение

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

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

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

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

Вектоp  C длины  n содержит запись коэффициентов линейной формы, т.е. в  C (J) помещается коэффициент  C_j. Вектор 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.

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

    int mnr3r_c (real *x, real *xs, real *a, shortint *na, real *b,
             real *c__, shortint *nc, integer *m, integer *n, real *y, real *z__, 
            real *zs, integer *s, integer *ny, integer *nx, real *dif, real *eps)

   Параметры 

   Версии:  нет 

   Вызываемые подпрограммы 

   Замечания по использованию  

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

   Найти
                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)

int main(void)
{
    /* Initialized data */
    static float b[8] = { 2.f,2.f,2.f,2.f,-1.f,-1.f,-1.f,-1.f };
    static float c__[6] = { 1.f,1.f,1.f,1.f,1.f,1.f };
    static shortint nc[6] = { 4,4,4,4,4,4 };
    static float a[24] = { 1.f,1.f,-1.f,-1.f,1.f,1.f,-1.f,-1.f,1.f,1.f,-1.f,
                 -1.f,1.f,1.f,-1.f,-1.f,1.f,1.f,-1.f,-1.f,1.f,1.f,-1.f,-1.f };
    static shortint na[24] = { 1,2,5,6,1,3,5,7,2,3,6,7,1,4,5,8,2,4,6,8,3,4,7,
                               8 };
    static int xs[1] = { 0 };

    /* System generated locals */
    int i__1;

    /* Local variables */
    extern int mnr3r_c(int *, int *, float *, shortint *, float *, float *,
                       shortint *, int *, int *, float *, float *, float *,
                       int *, int *, int *, float *, float *);
    static int i__, k, m, n, s, x[1];
    static float y[8], z__;
    extern int utmn13_c(int *, int *, int *);
    static int ip, nx[6], ny[8];
    static float zs, dif[8], eps;

    m = 8;
    n = 6;
    s = 0;
    eps = 1e-4f;
    mnr3r_c(x, xs, a, na, b, c__, nc, &m, &n, y, &z__, &zs, &s, ny, nx, dif,
            &eps);

    k = 0;
    i__1 = n;
    for (i__ = 1; i__ <= i__1; ++i__) {
        utmn13_c(&i__, x, &ip);
        if (ip == 0) {
            goto l2;
        }
        ++k;
        nx[k - 1] = i__;
l2:
        ;
    }
    printf("\n %7.0f \n", z__);
    printf("\n %5i %5i \n",nx[0], nx[1]);
    return 0;
} /* main */


Результаты:

      x  =  (1, 0, 0, 0, 0, 1)
      z  =  2