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

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

Назначение

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

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

Решается задача линейного пpoгpaммирования 

      min  (c,x)  ( или  max  (c,x) )
      A x  =  b ,
      0 ≤ x ≤ α ≤ +∞ ,

где A - матрица размерности  m * n,   x,  c,  α - векторы длины  n,  b - вектоp длины  m.

Используется модифицированный симплекс - метод с мультипликативным представлением обратной матрицы и с пересчетами мультипликаторов. Процедура пересчета элементарных матриц - мультипликаторов предназначена для эффективного использования оперативной памяти ЭВМ и осуществляется при выполнении заданного числа итераций, либо при заполнении участка оперативной памяти, отведенной для хранения мультипликаторов.

Информация о задаче задается в следующем виде:

Матрица условий  A задается в трех массивах:

- в одномерном массиве  A последовательно помещаются ненулевые элементы матрицы по столбцам;
- в одномерном массиве NSA записываются номера строк соответствующих ненулевых элементов;
- в массиве NTAB указывается количество ненулевых элементов в каждом столбце матрицы.

Вектор  C содержит коэффициенты линейной формы.
Вектор ограничений  b задается в массиве  B.

Выходными параметрами подпрограммы являются:
вещественная переменная  F - оптимальное значение линейной формы;
вещественный вектор RM после окончания счета, содержащий в первых  N ячейках компоненты решения;
и целая переменная IERR, указывающая причину окончания счета.

Вводится в рассмотрение расширенный вектор ограничений  b длины  M = m + 2, у которого  b = bi  для  i = 1, ..., m,   bM - 1 = 0,   bM = - (b1 + ... + bm).

Точность вычислений характеризуется величиной невязки 

                            n
        r  =  bM  -   ∑  Sj x j ,    где    Sj = - ( ai j + ... + am j ) .
                           j =1

С.Гасс, Линейное программирование, Физматгиз, M., 1961.

Г.Зойтендейк, Методы возможных направлений. Изд - во ИЛ, M., 1963.

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

    int mlogr_c (integer *m, integer *n, integer *prp, real *a,
        shortint *nsa, shortint *ntab, real *alfa, shortint *nalfa,
            integer *kv, real *b, real *c, integer *lb, real *eps,
            integer *mnmx, real *f, shortint *im, real *rm, integer *ierr)

   Параметры
m - число строк расширенной матрицы (тип: целый);
n - число столбцов в матрице условий (тип: целый);
prp - целая переменная, задающая число итераций метода, через которое делается пересчет мультипликаторов (см. замечания по использованию);
a - вещественный вектор, задающий ненулевые элементы матрицы по столбцам;
nsa - массив индексов строк для соответствующих ненулевых элементов (тип: integer * 2);
ntab - вектор длины  n - таблица ненулевых элементов матрицы по столбцам (тип: integer * 2);
alfa - вещественный вектоp длины kv, содержащий отличные от + ∞, компоненты вектора верхних ограничений  α;
nalfa - массив номеров отличных от + ∞, компонент вектора верхних ограничений  α (тип: integer * 2);
kv - количество отличных от + ∞ верхних ограничений на переменные (тип: целый);
b - вещественный вектор длины  m содержащий ограничения;
c - вещественный вектоp длины  n, содержащий коэффициенты линейной формы;
lb - целая переменная, задающая объем свободной оперативной памяти (см. замечания по использованию);
eps - вещественная переменная, задающая точность вычисления оптимального плана;
mnmx - целая переменная, задающая признак оптимизации:
mnmx=0, если задача поставлена на минимум;
mnmx=1, если - на максимум,
f - вещественная переменная, содержащая оптимальное значение линейной формы;
im - рабочий массив длины (1 + 6m + 2n + lb) (тип: integer * 2);
rm - вещественный рабочий массив длины (1 + 4m + n + lb), после окончания счета в первых  n ячейках стоит решение;
ierr - целая переменная служащая для сообщения о причине окончания счета:
ierr= 0 - получено оптимальное решение;
ierr=65 - задача несовместна;
ierr=66 - линейная форма неограничена. 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
 

Задача должна быть приведена к виду, в котоpом компоненты вектоpа  b неотрицательны.

Вектор верхних ограничений на переменные   α не должен содержать нулевых компонент и хотя бы одна его компонента должна быть отлична от + ∞.

Процедура пересчета элементарных матриц предназначена для эффективного использования оперативной памяти. Обычно для хранения элементарных матриц используется вся свободная память (lb). Число prp рекомендуется выбрать равным 3m/2, где  m - число ограничений задачи. Выбор момента пересчета элементарных матриц осуществляется программой. Пересчет производится при выполнении хотя бы одного из условий:
- выполнено prp итераций метода,
- объем оперативной памяти, занимаемой элементарными матрицами превосходит lb.

При определении lb следует иметь ввиду, что программа использует (2 + 8 * m + 4,5 * n + 1,5 * z) ячеек памяти без учета массива элементарных матриц, где  z - количество ненулевых элементов в матрице условий.

Длина входных векторов  a и nsa должна быть не меньше  z.

После работы подпрограммы изменяются:
вектор правых частей, вектор коэффициентов линейной формы и eps.

Используются служебные подпрограммы: mlmpm, mlmvk1_c, mlmpk_c, mlmrn_c, mlmlp_c, mlmxi_c, mlml11_c, mlml21_c, mlmx1_c, mlmd_c, mlmup2_c, mlmu_c, mlmxk2_c, mlmg11_c, mlmvx1_c, mlmbr_c.

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

    max  [(c, x)  =  x1  +  2x2  +  3x3 - x4 ] , 
      x1  +  2x2  +  3x3            =  15 , 
    2x1  +    x2  +  5x3            =  20 , 
      x1  +  2x2  +    x3  +  x4  =  10 , 
             0 ≤ x1 ≤ 2 , 
             0 ≤ x2 , 
             0 ≤ x3 ≤ 3 , 
             0 ≤ x4 .


int main(void)
{
    /* Initialized data */
    static float a[10] = { 1.f,2.f,1.f,2.f,1.f,2.f,3.f,5.f,1.f,1.f };
    static int prp = 6;
    static int kv = 2;
    static int mnmx = 1;
    static int lb = 30;
    static float eps = .01f;
    static float alfa[2] = { 2.f,3.f };
    static float b[5] = { 15.f,20.f,10.f,0.f,0.f };
    static float c__[4] = { 1.f,2.f,3.f,-1.f };
    static shortint nalfa[2] = { 1,3 };
    static shortint nsa[10] = { 1,2,3,1,2,3,1,2,3,3 };
    static shortint ntab[4] = { 3,3,3,1 };
    static int m = 5;
    static int n = 4;

    /* Local variables */
    static int ierr;
    static float f;
    extern int mlogr_c(int *, int *, int *, float *, shortint *, shortint *,
                       float *, shortint *, int *, float *, float *, int *,
                       float *, int *, float *, shortint *, float *, int *);
    static shortint im[69];
    static float rm[55];

    mlogr_c(&m, &n, &prp, a, nsa, ntab, alfa, nalfa, &kv, b, c__, &lb, &eps,
            &mnmx, &f, im, rm, &ierr);

/* l300: */
    printf("\n %10.5f %10.5f %10.5f %10.5f \n", rm[0], rm[1], rm[2], rm[3]);
    return 0;
} /* main */


Результаты:

       ierr = 0

       Значение линейной формы   f = 14.571

       Решение

       2.0000     2.42857     2.71428     0.42857