|
Текст подпрограммы и версий mlc6r_p.zip |
Тексты тестовых примеров tmlc6r_p.zip |
Решение задачи целочисленного линейного программирования с булевыми переменными методом вектора спада.
Решается задача
N
min ∑ cj x j ,
j =1
n
∑ ai j x j = bj , i = 1, ..., Q
j =1
n
∑ ai j x j ≤ bj , i = Q + 1, ..., M ,
j =1
x j = 0 или 1 ( j = 1,...,N ) ,
где c = ( c1, ... , cN ) - целый вектор длины N ,
b = ( b1, ... , bM ) - целый вектор длины M ,
ai j - элементы целочисленной матрицы размеров M на N
Используется метод вектора спада. Исходная информация задается в компактной форме (см.замечания по использованию).
Сергиенко И.В., Лебедев Т.Т., Рощин В.А. "Приближенные методы решения дискретных задач оптимизации", Киев, "Наука думка", 1980.
procedure MLC6R(var A :Array of Integer; var B :Array of Integer;
var C :Array of Integer; var IERR :Integer;
M :Integer; var MIN :Integer; N :Integer;
var P :Array of Integer; Q :Integer;
var UP :Array of Real; var X :Array of Integer);
Параметры
| A - | целый вектор, в котором в упакованном виде хранятся ненулевые элементы матрицы условий, упорядоченные по столбцам; длина вектора A равна количеству ненулевых элементов в матрице условий; |
| B - | целый вектор длины M, в котором содержатся коэффициенты вектора ограничений; |
| C - | целый вектор длины N, в котором компактно заданы коэффициенты линейной формы и информация о количестве ненулевых элементов в столбцах исходной матрицы; |
| IERR - | целая переменная, указывающая причину выхода из подпрограммы |
| IERR= 0 - | найден локальный минимум; |
| IERR= 5 - | истекло заданное время; |
| IERR=65 - | не найдена допустимая точка; |
| M - | число строк в матрице условий, т.е. общее количество ограничений (тип: целый); |
| MIN - | целая переменная, содержащая на выходе наименьшее найденное значение линейной формы (если была найдена допустимая точка); |
| N - | длина вектора X (тип: целый); |
| P - | целый рабочий вектор длины M; |
| Q - | количество ограничений - равенств (тип: целый); |
| UP - | вещественный вектор управляющих параметров длины 2: |
| UP(1) - | время, отведенное центральному процессору на решение задачи, задается пользователем в секундах; на выходе содержит время в секундах, затраченное на решение задачи; |
| UP(2) - | признак печати сообщения о завершении работы подпрограммы: |
| UP(2)=0. - | печати не будет; |
| UP(2)=1. - | будет напечатано сообщение о причине окончания работы подпрограммы; |
| X - | целый вектор длины N; при обращении к подпрограмме содержит заданную начальную точку, на выходе - решение задачи, т.е. ту точку, в которой найдено наименьшее значение линейной формы. |
Версии: нет
Вызываемые подпрограммы: нет
Замечания по использованию
|
Матрица условий должна быть представлена в компактной форме. Ее ненулевые элементы задаются в виде вектора A, каждый элемент которого содержит очередной (по столбцам) ненулевой элемент ai j матрицы условий и номер строки i в виде условного числа ai j * 1000 + i. Количество ненулевых элементов в j - том столбце матрицы задается вместе с j - тым коэффициентом линейной формы в виде условного числа в векторе C. Для упаковки исходной информации можно воспользоваться служебной подпрограммой UTMLCI.
procedure UTMLCI(var A1 :Array of Integer; NA1 :Integer;
var A :Array of Integer);
Упаковывает попарно массив целых чисел. На входе: A1 - массив целых чисел вида ..., I, AI, ... , предназначенных для попарной упаковки; NA1 - длина массива A1. На выходе: A - массив, состоящий из условных целых чисел, полученных после упаковки. Если из заданной начальной точки допустимая точка не будет найдена, рекомендуется взять другую начальную точку. Подпрограмма MLC6R гарантирует локальный минимум в области, не меньшей, чем окрестность радиуса 3 полученной точки минимума. При работе подпрограммы MLC6R вызываются следующие служебные подпрограммы MLC6R1, MLC6R2, MLC6R3, MLC6R4, MLC6R5, UTMLCJ, UTMLCP. |
Найти минимальное значение функции
(C, X) = - x1 - 2x2 - 3x3 - 4x4
при условиях
x1 + x2 + x3 + x4 = 2
x1 + x2 + x3 + x4 ≤ 4 ,
где все x j = 0 или 1 , j = 1, 2, 3, 4 .
Начальное приближение X = (0, 0, 0, 0) .
Unit TMLC6R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, UTMLCI_p, MLC6R_p;
function TMLC6R: String;
implementation
function TMLC6R: String;
var
NOM,AN,_i,IERR,MIN :Integer;
A :Array [0..7] of Integer;
C :Array [0..3] of Integer;
P :Array [0..1] of Integer;
const
A1 :Array [0..15] of Integer = ( 1,1,2,1,1,1,2,1,1,1,2,1,1,1,2,1 );
C1 :Array [0..7] of Integer = ( 2,-1,2,-2,2,-3,2,-4 );
B :Array [0..1] of Integer = ( 2,4 );
N :Integer = 4;
M :Integer = 2;
Q :Integer = 1;
X :Array [0..3] of Integer = ( 0,0,0,0 );
UP :Array [0..1] of Real = ( 600.0,1.0 );
label
_10;
begin
Result := ''; { результат функции }
UTMLCI(A1,16,A);
UTMLCI(C1,8,C);
_10:
MLC6R(A,B,C,IERR,M,MIN,N,P,Q,UP,X);
Result := Result + Format('%s',[' MIN=']);
Result := Result + Format('%6d ',[MIN]);
Result := Result + Format('%s',[' X=']);
Result := Result + #$0D#$0A;
for _i:=0 to 3 do
begin
Result := Result + Format('%4d ',[X[_i]]);
if ( ((_i+1) mod 4)=0 )
then Result := Result + #$0D#$0A;
end;
Result := Result + #$0D#$0A;
Result := Result + Format('%s',[' ВРЕМЯ CЧETA=']);
Result := Result + Format('%20.16f ',[UP[0]]) + #$0D#$0A;
UtRes('TMLC6R',Result); { вывод результатов в файл TMLC6R.res }
exit;
end;
end.
Unit UTMLCI_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc;
procedure UTMLCI(var IV :Array of Integer; N :Integer;
var IW :Array of Integer);
implementation
procedure UTMLCI(var IV :Array of Integer; N :Integer;
var IW :Array of Integer);
var
I,I1 :Integer;
label
_10;
begin
{ YПAKOBKA BXOДHOГO MACCИBA IV B MACCИB IW }
I := 1;
while ( I<=N ) do
begin
I1 := (I - 1) div 2 + 1;
IW[I1-1] := IV[I-1] + IV[I+0]*1000;
_10:
inc(I,2);
end;
end;
end.
Результаты счета:
MIN = - 7
X = 0011