Документ взят из кэша поисковой машины. Адрес оригинального документа : http://num-anal.srcc.msu.su/lib_na/cat/ml_htm_c/ml05r_c.htm
Дата изменения: Thu Apr 23 07:49:03 2015
Дата индексирования: Sun Apr 10 02:01:33 2016
Кодировка: Windows-1251
БЧА НИВЦ МГУ. ML05R_C. Общая задача линейного программирования
Текст подпрограммы и версий
ml05r_c.zip 		Тексты тестовых примеров
tml05r_c.zip

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

Назначение

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

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

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

      min  (c, x)
      A x  =  b ,
      0 ≤ x ≤ α ,

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

Используется модифицированный симплекс - метод. Произвольный столбец A j матрицы A формируется подпрограммой пользователя, причем каждый столбец дополняется двумя компонентами  am + 1, j = cj ,  am + 2, j = - (a1 j + ... + am j).

Вектоp  b дополняется двумя компонентами  bm + 1 = 0,  bm + 2 = - (b1 + ... + bm). Точность вычислений характеризуется величиной невязки 

   r  =  bm+2  -  ∑  am+2, j x j 
                        j

Дж.Данциг, Линейное программирование. Его применения и обобщения. Изд - во "Прогресс", M., 1966.

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

    int ml05r_c (real *st, real *u, integer *m, real *x, real *xk,
            integer *n, shortint *nx, integer *p, real *eps, real *alfa,
        shortint *nalfa, integer *kv, U_fp f, integer *nb)

   Параметры
st - вещественный рабочий массив размерности  m + 2;
u - вещественный двумерный рабочий массив размерности  m + 2 на  m + 2;
m - длина расширенного вектоpа  b, равная  m + 2 (тип: целый);
x - вещественный вектоp длины m, при этом на входе: x (i) = bi,  i = 1,..., m; на выходе:
x (i) - не равные граничным значениям компоненты решения в компактной форме при i = 1,..., m - 2 (см. замечания по использованию);
x (m - 1) - минимальное значение линейной формы;
x (m) - величина невязки r;
xk - вещественный рабочий массив размерности m;
n - число столбцов матрицы A (тип: целый);
nx - целый двухбайтовый вектоp длины  m, содержащий на выходе из подпрограммы номера компонент решения (см. замечания по использованию);
p - целая переменная, указывающая причину окончания счета:
p= 1 - если найдено решение,
p= 2 - если задача несовместна,
p= 3 - если линейная форма неограничена;
eps - заданная абсолютная погрешность вычислений (тип: вещественный);
alfa - вещественный массив размерности kv, содержащий отличные от  + ∞ компоненты вектоpа верхних ограничений  α (см. замечания по использованию);
nalfa - целый двухбайтовый вектоp длины  kv, на входе содержит номера компонент вектоpа  α, соответствующие элементам alfa;
kv - размерность массива alfa (тип: целый);
f - имя подпрограммы пользователя, формирующей pасширенный столбец матрицы условий A (см. замечания по использованию);
nb - вектоp длины m, первые m - 2 компоненты которого содержат на выходе из подпрограммы возрастающую последовательность номеpов компонент решения, не равных граничным значениям (тип: целый). 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
 

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

На выходе из подпрограммы компоненты вектоpа nb равны номеpам компонент решения не равных граничным значениям, так что  0 < xnb (i) = x (i) < αnb (i).

Hомеpа компонент, принимающих значения верхних ограничений, определены в массиве nalfa. Если на выходе элемент nalfa (j) = (k + 1600), то  xk = αk. Остальные компоненты решения равны нулю.

Первый оператор подпрограммы f, формирующей расширенный столбец матрицы A, должен иметь вид: 

      int f(int *k, float *st, int *m)

Параметры:

k - номеp формируемого столбца матрицы A (тип: целый);

st - вещественный вектоp длины m, содержащий на выходе компоненты расширенного k - го столбца матрицы A;

m - длина расширенного вектора - столбца (тип: целый).

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

Используются служебные подпрограммы mlu01_c, mlu07_c, mlu18_c, mlu19_c, mlu23_c, mlu24_c, mlu25_c, mlu32_c, mlu36_c, mlu37_c, mlu38_c, mlu39_c, mlu40_c, mlu41_c, mlu42_c.

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

int main(void)
{
    /* Initialized data */
    static float x[5] = { 15.f,20.f,10.f,0.f,-45.f };
    static float alfa[2] = { 2.f,3.f };
    static shortint nalfa[2] = { 1,3 };

    /* Local variables */
    extern int ml05r_c(float *, float *, int *, float *, float *, int *,
                       shortint *, int *, float *, float *, shortint *,
                       int *, U_fp, int *);
    extern int f_c();
    static int n, p;
    static float u[25] /* was [5][5] */;
    static int nb[5], kv;
    static float xk[5];
    static shortint nx[5];
    static float st[5], eps;

    n = 4;
    kv = 2;
    p = 1;
    eps = .01f;
    ml05r_c(st, u, &c__5, x, xk, &n, nx, &p, &eps, alfa, nalfa, &kv,
            (U_fp)f_c, nb);

    printf("\n %5i %5i \n", nalfa[0], nalfa[1]);
    printf("\n %5i \n", p);
    printf("\n %12.2f %12.2f %12.2f %12.2f %12.2f \n",
           x[0], x[1], x[2], x[3], x[4]);
    printf("\n %5i %5i %5i %5i %5i \n", nx[0], nx[1], nx[2], nx[3], nx[4]);
    return 0;
} /* main */

int f_c(int *j, float *st, int *m)
{
    /* Initialized data */
    static float a[20] /* was [5][4] */ = { 1.f,2.f,1.f,-1.f,-4.f,2.f,1.f,
                 2.f,-2.f,-5.f,3.f,5.f,1.f,-3.f,-9.f,0.f,0.f,1.f,1.f,-1.f };

    /* System generated locals */
    int i__1;

    /* Local variables */
    static int i__;

#define a_ref(a_1,a_2) a[(a_2)*5 + a_1 - 6]

    /* Parameter adjustments */
    --st;

    /* Function Body */
    i__1 = *m;
    for (i__ = 1; i__ <= i__1; ++i__) {
/* l1: */
        st[i__] = a_ref(i__, *j);
    }
    return 0;
} /* f_c */


Результаты:

       p  =  1
       x  =  (2.43,  2.71,  0.43,  -14.57,  0.00)
       nx  =  (2, 3, 4, 8, 9)
       nalfa  =  (16001, 3)

   Таким образом,
         x  =  (2., 0., 2.43, 2.71, 0.43)
  (c, x)  =  -14.57
          r = 0.00