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

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

Назначение

Решение задачи линейного целочисленного программирования модифицированным методом Гомори (полностью целочисленный алгоритм с компактным хранением исходной информации).

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

Для решения задачи 

                        n
   max  ( z0  +  ∑  cj (-xj) ) ,     A x ≤ b ,   xj ≥ 0 ,
                       j=1

где  c и  x - целочисленные векторы из En, A - целочисленная матрица порядка  m на n,  b - целочисленный вектоp из Em,  z0 - заданное число, используется полностью целочисленный алгоритм Гомори. Исходная информация задается в компактной форме.

Ненулевые элементы матрицы условий A задаются в виде одномерного массива IA, каждый элемент которого содержит очередной (по стpокам) ненулевой элемент  ai j матрицы A и номер столбца  j в виде условного числа  ai j * 103 + j.

Количество ненулевых элементов в  i - ой стpоке матрицы задается в  i - ой компоненте вектоpа KV длины  m.

Руднева Т.Л., Яранов М.Г. Программная реализация полностью целочисленного алгоритма Гомори. В сб. "Математические вопросы задач оптимизации и управления", M., МГУ, 1981.

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

    int mlc3r_c (integer *lia, integer *m, integer *n, integer *ia,
             integer *kv, integer *x, integer *c, integer *z, integer *max, 
            integer *b, integer *mr, real *eps, integer *ierr)

   Параметры
lia - число ненулевых элементов в матрице A (тип: целый);
m - число стpок в матрице A (тип: целый);
n - число столбцов в матрице A (тип: целый);
ia - заданный целый вектоp длины lia, содержащий ненулевые элементы исходной матрицы A по стpокам в виде условных чисел;
kv - заданный целый вектоp длины m, содержащий количество ненулевых элементов матрицы A по стpокам;
x - целый вектоp длины n + m (см. замечания по использованию);
c - заданный целый вектоp длины n, содержащий коэффициенты линейной формы;
z - целая переменная; на входе содержит заданное значение  z0, на выходе - оптимальное значение целевой функции;
max - заданная оценка свеpху на сумму компонент вектоpа  x (тип: целый);
b - целая матрица n на n, используемая в подпрограмме как рабочая;
mr - целый вектоp длины 4 + 5n + 2 max (n, m), используемый в подпрограмме как рабочий;
eps - заданная абсолютная точность округления вещественного числа до целого (тип: вещественный);
ierr - целая переменная, указывающая причину окончания процесса вычислений:
ierr= 0 - если найдено оптимальное решение;
ierr=65 - если решения не существует. 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
  1. 

Используются служебные подпрограммы: mlc32_c, mlc33_c, mlc34_c, mlc35_c, mlc36_c, mlc37_c, mlc38_c, mlc39_c, mlc3a_c, mlc3b_c, mlc3l_c, mlc3m_c, mlc3v_c.

  2. 

Задаваемое значение параметра max должно быть оценкой свеpху для суммы компонент вектоpа  x, т.е. 

                  n
                 ∑  xj ≤ max
                 j=1
  3. 

Hа входе первые n компонент вектоpа x полагаются равными нулю, а следующие m компонент должны содержать коэффициенты вектоpа ограничений  b. Hа выходе первые n компонент вектоpа x содержат оптимальное решение задачи, а m последующих - значения дополнительных переменных, т. е. x (n + i) = [b - ax] i, i = 1,..., m.

  4.  B процессе вычислений производится округление некоторых вещественных чисел с использованием параметра eps, 0 < eps < 0.5. b частности, вещественное число y заменяется целым k, если abs (y - k) ≤ eps. Выбор конкретного значения параметра eps во многом определяется коэффициентами условий задачи, однако, обычно eps берется из интервала (10 - 7, 10 - 4).

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

   Максимизировать        4 x1 + 5 x2 + x3

при условиях 
                3 x1  +  2 x2           ≤ 10
                  x1   +  4 x2           ≤ 11
                3 x1  +  3 x2  +  x3  ≤ 13 ,

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


int main(void)
{
    /* Initialized data */
    static int ia[7] = { 3001,2002,1001,4002,3001,3002,1003 };
    static int max__ = 19;
    static int kv[3] = { 2,2,3 };
    static int x[6] = { 0,0,0,10,11,13 };
    static int z__ = 0;
    static float eps = 1e-4f;
    static int c__[3] = { -4,-5,-1 };
    static int lia = 7;
    static int m = 3;
    static int n = 3;

    /* Local variables */
    static int ierr;
    extern int mlc3r_c(int *, int *, int *, int *, int *, int *, int *,
                       int *, int *, int *, int *, float *, int *);
    static int b[9] /* was [3][3] */, mr[25];

    mlc3r_c(&lia, &m, &n, ia, kv, x, c__, &z__, &max__, b, mr, &eps, &ierr);

    printf("\n %5i \n", ierr);
    printf("\n %5i \n", z__);
    printf("\n %5i %5i %5i %5i %5i %5i \n",
           x[0], x[1], x[2], x[3], x[4], x[5]);
    return 0;
} /* main */


Результаты:

       ierr  =  0
       z__  =  19
       x  =  (2, 2, 1)