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

Текст подпрограммы и версий
mla1r_p.zip , mla1e_p.zip

Тексты тестовых примеров
tmla1r_p.zip , tmla1e_p.zip

Подпрограмма: MLA1R (модуль MLA1R_p)

Назначение

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

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

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

(1)                  z = a_{0 1} x₁ + a_{0 2} x₂ + ... + a_{0 N} x_N

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

(2)                  x₁ ≥ 0,  x₂ ≥ 0, ...,  x_N ≥ 0

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

(3)     a_{i 1} x₁ + a_{i 2} x₂ + ... + a_{i N} x_N ≤ b_i   ( b_i ≥ 0 ) ,   i = 1, ..., m1

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

(4)     a_{j 1} x₁ + a_{j 2} x₂ + ... + a_{j N} x_N ≥ b_j ≥ 0 ,    j = m1 + 1, ..., m1 + m2

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

(5)     a_{k 1} x₁ + a_{k 2} x₂ + ... + a_{k N} x_N = b_k ≥ 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                      a₀₁                    a₀₂              . . . .      a_0N
              |        b₁                   -a₁₁                   -a₁₂             . . . .     -a_1N
(6)         |    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
              |       b_m1                 -a_{m1 1}                -a_{m1 2}          . . .       -a_{m1 N}
              |      b_m1+1             -a_m1+1,1            -a_m1+1,2         . . .     -a_m1+1,N
     A  =  |    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
              |    b_m1+m2           -a_m1+m2,1          -a_m1+m2,2       . . .    -a_m1+m2,N
              |   b_m1+m2+1       -a_m1+m2+1,1       -a_m1+m2+1,2    . . .   -a_m1+m2+1,N
              |    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
              |  b_m1+m2+m3    -a_m1+m2+m3,1    -a_m1+m2+m3,2    ...   -a_m1+m2+m3,N
          
                                                     рис.1

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

procedure MLA1R(var A :Array of Real; M :Integer; N :Integer;
                MA :Integer; NA :Integer; M1 :Integer;
                var M2 :Integer; M3 :Integer; var IFLAG :Integer;
                var IZROV :Array of Integer;
                var IPOSV :Array of Integer; var L1 :Array of Integer;
                var L2 :Array of Integer; var L3 :Array of Integer);

   Параметры

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 -	заданное количество независимых переменных x₁, x₂, ...,x_N, 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 -	когда хотя бы одно значение b_i, i = 1, ...,M1 + M2 + M3, заданное в матрице коэффициентов (6) отрицательно;
IFLAG=67 -	когда заданная функция (1) неограничена;
IFLAG=68 -	когда исходная задача не имеет решений, удовлетворяющих заданным ограничениям.

IZROV -	целый вектор длины N, в J - ом элементе которого (J = 1, 2, ..., N) содержится номер i независимой переменной x_i, равной нулю в полученном решении; если значение i > N, то значение J - го элемента вектора IZROV игнорируется;
IPOSV -	целый вектор длины M, в J - ом элементе которого (J = 1, 2, ..., M) содержится номер i независимой переменной x_i, значение которой в полученном решении содержится в элементе A (J + 1, 1) результирующего массива A; если значение i > N, то значение J - го элемента вектора IPOSV игнорируется;
L1, L2 - L3	целые векторы длины MA, используемые в подпрограмме в качестве рабочих.

   Версии

MLA1E -

решение общей задачи линейного программирования симплекс - методом в режиме расширенной (Extended) точности. При этом параметр A должен имет тип Extended.

   Вызываемые подпрограммы:  нет

   Замечания по использованию:  нет

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

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

             z  =  x₁ + x₂ + 3x₃ - 0.5x₄

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

          x₁ ≥ 0,   x₂ ≥ 0,   x₃ ≥ 0,   x₄ ≥ 0

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

              x₁             + 2x₃             ≤  740 
                       2x₂            -  7x₄   ≤  0 
                        x₂    -  x₃  +  2x₄  ≥  0.5 
               x₁  +  x₂   +  x₃  +   x₄   =  9

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

Unit TMLA1R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, MLA1R_p;

function TMLA1R: String;

implementation

function TMLA1R: String;
var
M,N,MA,NA,M1,M2,M3,I,_i,IFLAG :Integer;
A :Array [0..29] of Real;
IZROV :Array [0..3] of Integer;
IPOSV :Array [0..3] of Integer;
L1 :Array [0..5] of Integer;
L2 :Array [0..5] of Integer;
L3 :Array [0..5] of Integer;
begin
Result := '';  { результат функции }
M := 4;
N := 4;
МА := 6;
NA := 5;
M1 := 2;
M2 := 1;
M3 := 1;
A[0] := 0.0;
A[6] := 1.0;
A[12] := 1.0;
A[18] := 3.0;
A[24] := -0.5;
A[1] := 740.0;
A[7] := -1.0;
A[13] := 0.0;
A[19] := -2.0;
A[25] := 0.0;
A[2] := 0.0;
A[8] := 0.0;
A[14] := -2.0;
A[20] := 0.0;
A[26] := 7.0;
A[3] := 0.5;
A[9] := 0.0;
A[15] := -1.0;
A[21] := 1.0;
A[27] := -2.0;
A[4] := 9.0;
A[10] := -1.0;
A[16] := -1.0;
A[22] := -1.0;
A[28] := -1.0;
MLA1R(A,M,N,MA,NA,M1,M2,M3,IFLAG,IZROV,IPOSV,L1,L2,L3);
Result := Result + #$0D#$0A;
for I:=1 to M+1 do
 begin
  Result := Result + Format('%20.16f ',[A[(I-1)+0]]) + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
Result := Result + Format('%5d ',[IFLAG]) + #$0D#$0A;
Result := Result + #$0D#$0A;
for _i:=0 to 3 do
 begin
  Result := Result + Format('%5d ',[IZROV[_i]]);
  if ( ((_i+1) mod 4)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
Result := Result + #$0D#$0A;
for _i:=0 to 3 do
 begin
  Result := Result + Format('%5d ',[IPOSV[_i]]);
  if ( ((_i+1) mod 4)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
UtRes('TMLA1R',Result);  { вывод результатов в файл TMLA1R.res }
exit;
end;

end.

Результаты:

       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 

         x₁ = 0 ;   x₂ = 3.325 ;   x₃ = 4.725 ;   x₄ = 0.95