2 / 10
Выпуклые матрицы и многомерная задача о ранце общей лестничной структуры
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2016. № 6
33
Аналогично определяют матрицы, выпуклые по столбцам. Матрицы, выпуклые по
строкам или по столбцам, будем называть просто
выпуклыми.
Некоторые матрицы
ограничений могут быть приведены к таким матрицам перестановкой строк и
столбцов.
Теорема 1.
Выпуклые матрицы абсолютно унимодулярны.
◀ Рассмотрим, для определенности, матрицу, выпуклую по строкам. Необ-
ходимо доказать в соответствии с определением абсолютной унимодулярности,
что любой минор рассматриваемой матрицы равен нулю, +1 или –1. Матрица
любого минора будет выпуклой. Вычислим этот минор. Выделим в его матрице
строки, в которых единицы начинаются в первом столбце. Если таких строк нет,
минор равен нулю. Из выделенных строк возьмем строку, в которой наимень-
шее число единиц. Прибавим эту строку, взятую с обратным знаком, ко всем
выделенным строкам. Эта операция не нарушит выпуклости матрицы минора,
сведя его определение к вычислению минора, порядок которого на единицу
меньше порядка исходного минора. ▶
Следовательно, линейная целочисленная оптимизационная задача с выпук-
лой матрицей ограничений может решаться с помощь симплекс-метода [1]. Од-
нако этим не ограничивается полезность понятия выпуклой матрицы. Различ-
ные применения выпуклых матриц описаны в работах [2–17]. Для многомерной
задачи о ранце с матрицей ограничений специального лестничного вида в рабо-
те [18] предложен полиномиальный декомпозиционный метод решения, позво-
ляющий значительно увеличить размерность решаемых задач.
Ограничения классической транспортной задачи не являются выпуклыми,
однако любая пара ограничений (взятых по одному из каждой группы) является
выпуклой подматрицей матрицы ограничений. Этого достаточно для возмож-
ности создания декомпозиционного метода решения транспортной задачи и ее
вариаций [19–21]. В настоящей работе рассмотрена многомерная задача о ранце
с выпуклой матрицей ограничений общей лестничной структуры.
Постановка задачи.
Пусть имеется многомерная задача о ранце с выпуклой
матрицей ограничений следующей структуры:
– первое ограничение
1
1
1
...
;
J
x
x a
(1)
– второе ограничение
2
2
2
1
2
...
,
j
j
J
x x
x a
1 2
2 1
1,
;
J j
J J
(2)
– третье ограничение
3
3
3
1
3
...
,
j
j
J
x x
x a
1 3 2 3 2
,
;
J j
j
J J
(3)
–
k
-е ограничение
1
...
,
k
k
k
j
j
J
k
x x
x a
1
1 3 2
,
;
k
k k
J
j
j
J J
(4)
j
x
принимают значения 0 или 1,
1
,
k
j J
0,
i
a
целые,
1
.
i k