БЧА НИВЦ МГУ. MLOGR_C. Общая задача линейного программирования

Документ взят из кэша поисковой машины. Адрес оригинального документа : http://num-anal.srcc.msu.ru/lib_na/cat/ml_htm_c/mlogr_c.htm
Дата изменения: Fri Apr 24 07:36:21 2015
Дата индексирования: Sun Apr 10 03:10:35 2016
Кодировка: Windows-1251

Текст подпрограммы и версий
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 = b_i для i = 1, ..., m, b_M - 1 = 0, b_M = - (b₁ + ... + b_m).

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

                            _n
        r  =  b_M  -   ∑  S_j x_j ,    где    S_j = - ( a_{i j} + ... + a_{m 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)  =  x₁  +  2x₂  +  3x₃ - x₄ ] , 
      x₁  +  2x₂  +  3x₃            =  15 , 
    2x₁  +    x₂  +  5x₃            =  20 , 
      x₁  +  2x₂  +    x₃  +  x₄  =  10 , 
             0 ≤ x₁ ≤ 2 , 
             0 ≤ x₂ , 
             0 ≤ x₃ ≤ 3 , 
             0 ≤ x₄ .

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