Подпрограмма:  MNR3R (модуль MNR3R_p)

Назначение

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

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

Для решения задачи  min < c, x >,  Ax ≤ b,  x_i = 0 или 1 ( i = 1, ..., n), где  c и  x - векторы длины  n,  A - матрица  m * n,  b - вектоp длины  m, используется метод Балаша с модификацией Джеофриона. Исходная информация задается в компактной форме.

Ненулевые элементы матрицы задаются в виде одномерного массива, каждый элемент которого содержит очередной (по столбцам) ненулевой элемент  a_i j матрицы  A. Номера строк ненулевых элементов матрицы условий задаются в целочисленном массиве NA в том же порядке, в котором перечислены сами ненулевые элементы, т.е. если  a_i j ≠ 0 и  A (I) = a_i j, то NA (I) = i.

Вектоp  C длины  n содержит запись коэффициентов линейной формы, т.е. в  C (J) помещается коэффициент  C_j. Вектор NC длины  N содержит количества ненулевых элементов в столбцах матрицы  A, т.е.  NC (k) = α означает, что в  k - ом столбце матрицы содержится  α ненулевых элементов.

Информация о ненулевых компонентах решения хранится в виде шкалы в массиве  X, причем разряды шкалы упорядочены справа налево и от первого элемента шкалы к последнему.

Geoffrion A.M., Integer Programming by Implicit Enumeration and Balas'Method. SIAM Review Vol.9, No.2, April, 1967.

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

procedure MNR3R(var X :Array of Integer; var XS :Array of Integer;
                var A :Array of Real; var NA :Array of Integer;
                var B :Array of Real; var C :Array of Real;
                var NC :Array of Integer; M :Integer;
                N :Integer; var Y :Array of Real; var Z :Real;
                var ZS :Real; S :Integer;
                var NY :Array of Integer; var NX :Array of Integer;
                var DIF :Array of Real; EPS :Real);

   Параметры 

   Версии:  нет 

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

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

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

   Найти
                G
        min  ∑  xi
               i =1
   при условиях:
  
       x1  +  x2         +  x4                    ≤   2
       x1            +  x3         +  x5          ≤   2
                 x2  +  x3                  +  x6 ≤   2
                                 x4  +  x5  +  x6 ≤   2
     - x1  -  x2           -  x4                   ≤ - 1
     - x1            -  x3          -  x5          ≤ - 1
              - x2   -  x3                   -  x6 ≤ - 1
                              -  x4   -  x5  -  x6 ≤ - 1

       xi  =  0 или 1   ( i = 1, ..., 6)

Unit TMNR3R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, MNR3R_p, UTMN13_p;

function TMNR3R: String;

implementation

function TMNR3R: String;
var
М,N,S,K,I,IP :Integer;
Z,ZS,EPS :Real;
DIF :Array [0..7] of Real;
Y :Array [0..7] of Real;
NY :Array [0..7] of Integer;
NX :Array [0..5] of Integer;
Х :АRray [0..0] of Integer;
const
B :Array [0..7] of Real = ( 2.0,2.0,2.0,2.0,-1.0,-1.0,-1.0,-1.0 );
C :Array [0..5] of Real = ( 1.0,1.0,1.0,1.0,1.0,1.0 );
NC :Array [0..5] of Integer = ( 4,4,4,4,4,4 );
A :Array [0..23] of Real = ( 1.0,1.0,-1.0,-1.0,1.0,1.0,-1.0,-1.0,1.0,1.0,
-1.0,-1.0,1.0,1.0,-1.0,-1.0,1.0,1.0,-1.0,-1.0,1.0,
1.0,-1.0,-1.0 );
NA :Array [0..23] of Integer = ( 1,2,5,6,1,3,5,7,2,3,6,7,1,4,5,8,2,4,6,8,3,4,7,8 );
XS :Array [0..0] of Integer = ( 0 );
label
_2;
begin
Result := '';  { результат функции }
M := 8;
N := 6;
S := 0;
EPS := 0.1E-03;
MNR3R(X,XS,A,NA,B,C,NC,M,N,Y,Z,ZS,S,NY,NX,DIF,EPS);
K := 0;
for I:=1 to N do
 NX[I-1] := 0;

for I:=1 to N do
 begin
  UTMN13(I,X,IP);
  NX[I-1] := IP;
_2:
 end;
Result := Result + Format('%s',['   Z=']);
Result := Result + Format('%20.16f ',[Z]);
Result := Result + Format('%s',['  NX=']);
Result := Result + #$0D#$0A;
for I:=1 to N do
 begin
  Result := Result + Format('%3d ',[NX[I-1]]) + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;

UtRes('TMNR3R',Result);  { вывод результатов в файл TMNR3R.res }
exit;
end;

end.

Результаты:

      X  =  (1, 0, 0, 0, 0, 1)
      Z  =  2