|
Текст подпрограммы и версий mlc4r_p.zip |
Тексты тестовых примеров tmlc4r_p.zip |
Решение задачи целочисленного линейного программирования модифицированным методом Юнга.
Постановка задачи: найти максимум (a, x) при условиях:
Ax ≤ b
n
∑ x j ≤ L ,
j =1
где x ≥ 0 - целый вектор длины n,
a - заданный целый вектор длины n,
A - заданная целая матрица размеров m*n,
b ≥ 0 - заданный целый вектор длины m,
L > 0 - заданное целое число.
Для решения задачи используется оригинальная модификация метода Юнга. Эта модификация удобна, когда матрица A слабо заполнена. Ненулевые элементы матрицы хранятся компактно в одномерном массиве в виде ai j*1000 + j. В отдельном целочисленном массиве длины m хранятся количества ненулевых элементов в строках матрицы A. В процессе вычислений преобразуется только небазисная матрица размеров n * n .
Т.Ху. Целочисленное программирование и потоки в сетях. Изд - во "Мир", М., 1974.
procedure MLC4R(var NA :Array of Integer; var NS :Array of Integer;
var NAI :Array of Integer; var NAJ :Array of Integer;
L :Integer; var NB :Array of Integer;
var NR :Array of Integer; M :Integer;
N :Integer; N1 :Integer; MN :Integer;
var IT :Integer; TMAX :Real; var IERR :Integer);
Параметры
| NA - | заданный целый массив длины MN, в котором упакованы ненулевые элементы матрицы A (по строкам) по формуле ai j * 1000 + j; |
| NS - | заданный целый вектор длины m, содержащий количество ненулевых элементов в строках матрицы A; |
| NAI - | заданный вектор правых частей длины m (тип: целый); |
| NAJ - | заданный вектор коэффициентов линейной формы длины n (тип: целый); |
| L - | заданная целая переменная (верхняя граница на сумму компонент вектора x); |
| NB - | целый рабочий массив размеров (n + 1) * (n + 1); |
| NR - | целый рабочий вектор длины 4 * (m + n + 2), на выходе в первых (m + n + 2) элементах вектора NR находится решение; |
| M - | M = m, целая переменная, число строк в матрице A; |
| N - | N = n, целая переменная, число столбцов в матрице A; |
| N1 - | N1 = n + 1, размер рабочей матрицы; |
| MN - | число ненулевых элементов в матрице A, тип целый; |
| IT - | заданное максимальное число итераций, на выходе - выполненное число итераций, тип целый; |
| TMAX - | заданное максимальное время работы программы (в секундах), тип вещественный; |
| IERR - | целая переменная, указывающая причину окончания счета; |
| IERR= 1 - | найдено оптимальное решение; |
| IERR= 2 - | выполнено заданное число итераций; |
| IERR= 3 - | истекло время; |
| IERR=65 - |
выполнилось ограничение
n
∑ x j = L
j =1
|
Версии: нет
Вызываемые подпрограммы: UTMN05
Замечания по использованию
|
Для упаковки ненулевых элементов матрицы A удобно воспользоваться
вспомогательной подпрограммой IW(( I - 1)/2 + 1) = IV( I ) + IV( I + 1)*1000. Таким образом, если в векторе IV перечислить номера столбцов и значения ненулевых элементов матрицы A (по строкам) в виде: номер столбца, значение элемента матрицы, номер столбца, значение ... и т.д., то обратившись к подпрограмме UTMLC мы получим требуемое представление исходной информации. Вектор - решение хранится в первых m + n + 1 элементах вектора NR, причем NR (1) - значение линейной формы, NR (2) ÷ NR (m + 1) - невязки в ограничениях, равные b - Ax, NR (m + 2) ÷ NR (m + n + 1) - компоненты вектора x. Счет можно закончить по заданному числу итераций или по времени. При этом вектор x может не быть оптимальным, но обязательно будет допустимым. Если ограничения в задаче имеют вид Ax ≥ b, b ≥ 0, x ≥ 0, целые, то иногда может помочь замена переменных yj = K - xj, где K ≥ xj для всех j = 1, ..., n. Подставим xj = K - yj в функционал и систему ограничений: найти max (- a, y) при условиях - Ay + AK ≥ b или Ay ≤ AK - b, где K - вектор - столбец, все элементы которого равны K. n n
∑ yj = nK - ∑ x j
j =1 j =1
n
∑ yj ≤ nK
j =1
Если вектор AK - b ≥ 0, то задача имеет требуемый вид. Если задача поставлена на минимум, переходим к поиску максимума, изменив знаки у вектора коэффициентов линейной формы. Количество итераций не всегда связано с размерами задачи и оценке не поддается. При IERR = 1 и IERR = 2 допустимое решение может оказаться оптимальным. Используются служебные подпрограммы: MLC4B, MLC4C, MLC4E, MLC4O, MLC4Z, MLC4W, UTMN05, UTMN06. |
Найти максимум x0 = x1 + x2 + x3 при условиях:
- 4x1 + 5x2 + 2x3 ≤ 4
- 2x1 + 5x2 ≤ 5
3x1 - 2x2 + 2x3 ≤ 6
2x1 - 5x2 ≤ 1
x1 + x2 + x3 ≤ 10
x1, x2, x3 ≥ 0, целые
Решение: x0 = 5 , x1 = 3 , x2 = 2 , x3 = 0
Unit TMLC4R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, UTMLC_p, MLC4R_p;
function TMLC4R: String;
implementation
function TMLC4R: String;
var
M1,I,IERR :Integer;
NA :Array [0..9] of Integer;
NB :Array [0..15] of Integer;
NR :Array [0..35] of Integer;
const
IV :Array [0..19] of Integer = ( 1,-4,2,5,3,2,1,-2,2,5,1,3,2,-2,3,2,1,2,2,-5 );
NS :Array [0..3] of Integer = ( 3,2,3,2 );
NAI :Array [0..3] of Integer = ( 4,5,6,1 );
NAJ :Array [0..2] of Integer = ( 1,1,1 );
M :Integer = 4;
N :Integer = 3;
N1 :Integer = 4;
MN :Integer = 10;
L :Integer = 10;
IT :Integer = 20;
ТМАХ :Real = 60.0;
begin
Result := ''; { результат функции }
UTMLC(IV,20,NA);
MLC4R(NA,NS,NAI,NAJ,L,NB,NR,
M,N,N1,MN,IT,TMAX,IERR);
M1 := M+N+2;
Result := Result + Format('%s',[' IERR']);
Result := Result + Format('%7d ',[IERR]);
Result := Result + Format('%s',[' Решение']);
Result := Result + #$0D#$0A;
for I:=1 to M1 do
begin
Result := Result + Format('%8d ',[NR[I-1]]) + #$0D#$0A;
end;
Result := Result + #$0D#$0A;
UtRes('TMLC4R',Result); { вывод результатов в файл TMLC4R.res }
exit;
end;
end.
Unit UTMLC_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc;
procedure UTMLC(var IV :Array of Integer; N :Integer;
var IW :Array of Integer);
implementation
procedure UTMLC(var IV :Array of Integer; N :Integer;
var IW :Array of Integer);
var
I,I1 :Integer;
label
_10;
begin
{ УПАКОВКА }
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.
Результаты решения:
IERR = 1
NR(1) ÷ NR(8) : 5 6 1 1 5 3 2 0
Таким образом, (a, x) = 5, невязки
по строкам матрицы условий равны, соответственно,
(6, 1, 1, 5),
вектор - решение x = (3, 2, 0).