Текст подпрограммы и версий
mla1r_c.zip , mla1d_c.zip 		Тексты тестовых примеров
tmla1r_c.zip , tmla1d_c.zip

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

Назначение

Решение общей задачи линейного программирования симплекс - методом

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

Общая задача линейного программирования (или линейной оптимизации) формулируется следующим образом: для N независимых переменных  x1, x2, ...,xN максимизировать линейную функцию (или линейную форму) 

(1)                  z = a0 1 x1 + a0 2 x2 + ... + a0 N xN

при одновременном соблюдении N главных ограничений 

(2)                  x1 ≥ 0,  x2 ≥ 0, ...,  xN ≥ 0

и M = m1 + m2 + m3 дополнительных ограничений, из которых  m1 ограничений имеют вид 

(3)     ai 1 x1 + ai 2 x2 + ... + ai N xN ≤ bi   ( bi ≥ 0 ) ,   i = 1, ..., m1

m2 ограничений имеют вид 

(4)     aj 1 x1 + aj 2 x2 + ... + aj N xN ≥ bj ≥ 0 ,    j = m1 + 1, ..., m1 + m2

и m3 ограничений имеют вид 

(5)     ak 1 x1 + ak 2 x2 + ... + ak N xN = bk ≥ 0 ,

             k = m1 + m2 + 1, ..., m1 + m2 + m3

В подпрограмме mla1r_c задача (1), (3), (4), (5) представляется в виде матрицы коэффициентов A, структура которой приведена на рис.1. В матрице коэффициентов A в первой строке располагаются коэффициенты линейной функции (1), затем в  m1 строках коэффициенты ограничений (3), затем в  m2 строках коэффициенты ограничений (4) и, наконец, в последних  m3 строках коэффициенты ограничений (5). Ограничения (2) в mla1r_c учитываются автоматически.

С.А.Ашманов. Линейное программирование. Изд - во "Наука", 1981.

Д.Данциг. Линейное программирование, его обобщения и применение. - М.: Прогресс, 1966. 

              |        0                      a01                    a02              . . . .      a0N
              |        b1                   -a11                   -a12             . . . .     -a1N
(6)         |    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
              |       bm1                 -am1 1                -am1 2          . . .       -am1 N
              |      bm1+1             -am1+1,1            -am1+1,2         . . .     -am1+1,N
     A  =  |    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
              |    bm1+m2           -am1+m2,1          -am1+m2,2       . . .    -am1+m2,N
              |   bm1+m2+1       -am1+m2+1,1       -am1+m2+1,2    . . .   -am1+m2+1,N
              |    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
              |  bm1+m2+m3    -am1+m2+m3,1    -am1+m2+m3,2    ...   -am1+m2+m3,N
          
                                                     рис.1

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

    int mla1r_c (real *a, integer *m, integer *n, integer *ma,
            integer *na, integer *m1, integer *m2, integer *m3, integer *iflag, 
            integer *izrov, integer *iposv, integer *l1, integer *l2, integer *l3)

   Параметры
a - вещественный двумерный массив размеров ma на na (ma ≥ m + 2,  na ≥ n + 1), в первых m + 1 строках и n + 1 столбцах которого задается матрица коэффициентов (6) исходной задачи; (m + 2) - я строка массива a используется в качестве рабочей; на выходе массив a содержит решение задачи (см.параметры izrov и iposv); полученное максимальное значение функции (1) содержится в элементе a (1, 1);
m - заданное количество дополнительных ограничений (3), (4), (5) исходной задачи, m = m1 + m2 + m3 ≥ n (тип: целый);
n - заданное количество независимых переменных  x1, x2, ...,xn,  n ≤ m (тип: целый);
ma, na - заданное число строк и столбцов массива a, ma ≥ m + 2,  na ≥ n + 1 (тип: целый);
m1 - заданное количество ограничений вида (3) (тип: целый);
m2 - заданное количество ограничений вида (4) (тип: целый);
m3 - заданное количество ограничений вида (5) (тип: целый);
iflag - целая переменная, служащая для сообщения об ошибках, обнаруженных в ходе работы подпрограммы; при этом:
iflag= 0 - когда решение задачи получено;
iflag=65 - когда заданное значение m не равно m1 + m2 + m3;
iflag=66 - когда хотя бы одно значение  bi,  i = 1, ...,m1 + m2 + m3, заданное в матрице коэффициентов (6) отрицательно;
iflag=67 - когда заданная функция (1) неограничена;
iflag=68 - когда исходная задача не имеет решений, удовлетворяющих заданным ограничениям
izrov - целый вектор длины n, в j - ом элементе которого (j = 1, 2, ..., n) содержится номер  i  независимой переменной  xi, равной нулю в полученном решении; если значение  i > n, то значение j - го элемента вектора izrov игнорируется;
iposv - целый вектор длины m, в j - ом элементе которого (j = 1, 2, ..., m) содержится номер  i  независимой переменной  xi, значение которой в полученном решении содержится в элементе a (j + 1, 1) результирующего массива a; если значение  i > n, то значение j - го элемента вектора iposv игнорируется;
l1, l2 -
l3   		целые векторы длины ma, используемые в подпрограмме в качестве рабочих 
   Версии
mla1d_c - решение общей задачи линейного программирования симплекс - методом в режиме удвоенной точности. При этом параметр a должен имет тип double. 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию:  нет

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

Пусть требуется максимизировать линейную функцию 

             z  =  x1 + x2 + 3x3 - 0.5x4

при одновременном соблюдении n = 4 главных ограничений 

          x1 ≥ 0,   x2 ≥ 0,   x3 ≥ 0,   x4 ≥ 0

и m = 4 дополнительных ограничений (m1 = 2, m2 = 1, m3 = 1): 

              x1             + 2x3             ≤  740 
                       2x2            -  7x4   ≤  0 
                        x2    -  x3  +  2x4  ≥  0.5 
               x1  +  x2   +  x3  +   x4   =  9

Головная программа, вызывающая подпрограмму mla1r_c для решения данной задачи, может иметь вид: 

int main(void)
{
    /* Local variables */
    extern int mla1r_c(float *, int *, int *, int *, int *, int *, int *,
                       int *, int *, int *, int *, int *, int *, int *);
    static float a[30] /* was [6][5] */;
    static int i__, m, n, iflag, l1[6], l2[6], l3[6], iposv[4], m1, m2,
            m3, izrov[4], ma, na;

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

    m = 4;
    n = 4;
    ma = 6;
    na = 5;
    m1 = 2;
    m2 = 1;
    m3 = 1;
    a_ref(1, 1) = 0.f;
    a_ref(1, 2) = 1.f;
    a_ref(1, 3) = 1.f;
    a_ref(1, 4) = 3.f;
    a_ref(1, 5) = -.5f;
    a_ref(2, 1) = 740.f;
    a_ref(2, 2) = -1.f;
    a_ref(2, 3) = 0.f;
    a_ref(2, 4) = -2.f;
    a_ref(2, 5) = 0.f;
    a_ref(3, 1) = 0.f;
    a_ref(3, 2) = 0.f;
    a_ref(3, 3) = -2.f;
    a_ref(3, 4) = 0.f;
    a_ref(3, 5) = 7.f;
    a_ref(4, 1) = .5f;
    a_ref(4, 2) = 0.f;
    a_ref(4, 3) = -1.f;
    a_ref(4, 4) = 1.f;
    a_ref(4, 5) = -2.f;
    a_ref(5, 1) = 9.f;
    a_ref(5, 2) = -1.f;
    a_ref(5, 3) = -1.f;
    a_ref(5, 4) = -1.f;
    a_ref(5, 5) = -1.f;
    mla1r_c(a, &m, &n, &ma, &na, &m1, &m2, &m3, &iflag, izrov, iposv, l1, l2,
            l3);

    for (i__ = 1; i__ <= 5; ++i__) {
         printf("\n %15.4e %15.4e %15.4e \n",
                a_ref(i__, 1), a_ref(i__, 2), a_ref(i__, 3));
         printf("\n %15.4e %15.4e %15.4e \n",
                a_ref(i__, 4), a_ref(i__, 5), a_ref(i__, 6));
    }
    printf("\n %5i \n", iflag);
    printf("\n %5i %5i %5i %5i \n",
           izrov[0], izrov[1], izrov[2], izrov[3]);
    printf("\n %5i %5i %5i %5i \n",
           iposv[0], iposv[1], iposv[2], iposv[3]);
    return 0;
} /* main */


Результаты:

       a(1, 1) = 17.02 ;    a(2, 1) = 730.5 ; 
       a(3, 1) = 3.325 ;    a(4, 1) = 0.95 ;
       a(5, 1) = 4.725 

       iflag = 0 ; 
       izrov = (1, 6, 8, 7) ;
       iposv = (5, 2, 4, 3) 

Таким образом,

         max  z   =   17.02 

         x1 = 0 ;   x2 = 3.325 ;   x3 = 4.725 ;   x4 = 0.95