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

Документ взят из кэша поисковой машины. Адрес оригинального документа : http://num-anal.srcc.msu.ru/lib_na/cat/ml_htm_p/mlogr_p.htm
Дата изменения: Thu Nov 5 15:12:14 2015
Дата индексирования: Sun Apr 10 04:07:43 2016
Кодировка: Windows-1251

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

Тексты тестовых примеров
tmlogr_p.zip

Подпрограмма: MLOGR (модуль MLOGR_p)

Назначение

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

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

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

      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.

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

procedure MLOGR(M :Integer; N :Integer; PRP :Integer;
                var A :Array of Real; var NSA :Array of Integer;
                var NTAB :Array of Integer; var ALFA :Array of Real;
                var NALFA :Array of Integer; var KV :Integer;
                var B :Array of Real; var C :Array of Real;
                LB :Integer; var EPS :Real; MNMX :Integer;
                var F :Real; var IM :Array of Integer;
                var RM :Array of Real; var IERR :Integer);

   Параметры

M -	число строк расширенной матрицы (тип: целый);
N -	число столбцов в матрице условий (тип: целый);
PRP -	целая переменная, задающая число итераций метода, через которое делается пересчет мультипликаторов (см. замечания по использованию);
A -	вещественный вектор, задающий ненулевые элементы матрицы по столбцам;
NSA -	массив индексов строк для соответствующих ненулевых элементов;
NTAB -	вектор длины N - таблица ненулевых элементов матрицы по столбцам;
ALFA -	вещественный вектоp длины KV, содержащий отличные от + ∞, компоненты вектора верхних ограничений α;
NALFA -	массив номеров отличных от + ∞, компонент вектора верхних ограничений α;
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, MLMPK, MLMRN, MLMLZ, MLMXI, MLML11, MLML21, MLMX1, MLMD, MLMUZ2, MLMU, MLMXK2, MLMG11, MLMVX1, MLMBR.

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

    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₄ .

Unit TMLOGR_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, MLOGR_p;

function TMLOGR: String;

implementation

function TMLOGR: String;
var
I,IERR :Integer;
F :Real;
RM :Array [0..54] of Real;
IM :Array [0..68] of Integer;
const
A :Array [0..9] of Real = ( 1.0,2.0,1.0,2.0,1.0,2.0,3.0,5.0,1.0,1.0 );
ALFA :Array [0..1] of Real = ( 2.0,3.0 );
B :Array [0..4] of Real = ( 15.0,20.0,10.0,0.0,0.0 );
C :Array [0..3] of Real = ( 1.0,2.0,3.0,-1.0 );
NALFA :Array [0..1] of Integer = ( 1,3 );
NSA :Array [0..9] of Integer = ( 1,2,3,1,2,3,1,2,3,3 );
NТАВ :Array [0..3] of Integer = ( 3,3,3,1 );
M :Integer = 5;
N :Integer = 4;
PRP :Integer = 6;
KV :Integer = 2;
MNМХ :Integer = 1;
LB :Integer = 30;
EPS :Real = 0.01;
begin
Result := '';  { результат функции }
MLOGR(M,N,PRP,A,NSA,NTAB,ALFA,NALFA,KV,B,C,LB,EPS,MNMX,
     F,IM,RM,IERR);
Result := Result + #$0D#$0A;
for I:=1 to N do
 begin
  Result := Result + Format('%20.16f ',[RM[I-1]]) + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
UtRes('TMLOGR',Result);  { вывод результатов в файл TMLOGR.res }
exit;
end;

end.

Результаты:

       IERR = 0

       Значение линейной формы   F = 14.571

       Решение

       2.0000     2.42857     2.71428     0.42857