Текст подпрограммы и версий ( Фортран )
mla1r.zip , mla1d.zip 		Тексты тестовых примеров ( Фортран )
tmla1r.zip , tmla1d.zip
Текст подпрограммы и версий ( Си )
mla1r_c.zip , mla1d_c.zip 		Тексты тестовых примеров ( Си )
tmla1r_c.zip , tmla1d_c.zip
Текст подпрограммы и версий ( Паскаль )
mla1r_p.zip , mla1e_p.zip 		Тексты тестовых примеров ( Паскаль )
tmla1r_p.zip , tmla1e_p.zip

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

Назначение

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

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

Общая задача линейного программирования (или линейной оптимизации) формулируется следующим образом: для 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 задача (1), (3), (4), (5) представляется в виде матрицы коэффициентов A, структура которой приведена на рис.1. В матрице коэффициентов A в первой строке располагаются коэффициенты линейной функции (1), затем в  m1 строках коэффициенты ограничений (3), затем в  m2 строках коэффициенты ограничений (4) и, наконец, в последних  m3 строках коэффициенты ограничений (5). Ограничения (2) в MLA1R учитываются автоматически.

С.А.Ашманов. Линейное программирование. Изд - во "Наука", 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

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

    SUBROUTINE  MLA1R (A, M, N, MA, NA, M1, M2, M3, IFLAG, IZROV,
                                              IPOSV, L1, L2, 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 - решение общей задачи линейного программирования симплекс - методом в режиме удвоенной точности. При этом параметр A должен имет тип DOUBLE PRECISION. 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию:  нет

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

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

             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 для решения данной задачи, может иметь вид: 

       DIMENSION  A(6, 5), IZROV(4), IPOSV(4), L1(6), L2(6), L3(6) 
       M = 4 
       N = 4 
       MA = 6 
       NA = 5 
       M1 = 2 
       M2 = 1 
       M3 = 1 
       A(1, 1) = 0.0 
       A(1, 2) = 1.0 
       A(1, 3) = 1.0 
       A(1, 4) = 3.0 
       A(1, 5) = - 0.5 
       A(2, 1) = 740.0 
       A(2, 2) = - 1.0 
       A(2, 3) = 0.0 
       A(2, 4) = - 2.0 
       A(2, 5) = 0.0 
       A(3, 1) = 0.0 
       A(3, 2) = 0.0 
       A(3, 3) = - 2.0 
       A(3, 4) = 0.0 
       A(3, 5) = 7.0 
       A(4, 1) = 0.5 
       A(4, 2) = 0.0 
       A(4, 3) = - 1.0 
       A(4, 4) = 1.0 
       A(4, 5) = - 2.0 
       A(5, 1) = 9.0 
       A(5, 2) = - 1.0 
       A(5, 3) = - 1.0 
       A(5, 4) = - 1.0 
       A(5, 5) = - 1.0 
       CALL  MLA1R (A, M, N, MA, NA, M1, M2, M3, IFLAG, IZROV, 
      *                          IPOSV, L1, L2, L3) 

Результаты:

       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