Исследование вопроса сводимости задачи к потоковым моделям

Нас будут интересовать такие задачи W(M), для которых применимы процедуры их сводимости к задаче L – поиска циркуляции минимальной стоимости. Пусть в системе ограничений (1)  и  – целые числа, , .

Определение 1. Будем говорить, что задача W(M) сводится к задаче L, если некоторое подмножество компонент оптимального решения задачи L образует оптимальное решение задачи W(M), и задача W(M) не имеет допустимого решения, если не имеет допустимого решения задача L.

Так как система ограничений (1) задачи W(M) определяется заданием множества M, MÍ2^N(s), будем решать задачу поиска таких множеств M, при которых задача W(M) сводится к задаче L.

В [2] приведены достаточные условия, которые могут быть использованы для исследования сводимости рассматриваемых задач, однако проверка этих условий связана с исследованием свойств матрицы системы ограничений и является достаточно трудоемкой. В данной работе приводятся достаточные условия сводимости задачи  W(M) к задаче L, основанные на исследовании множества M, мощность которого на порядок меньше количества строк системы ограничений задачи W(M).

Введем следующее вспомогательное определение:

Определение 2. Будем говорить, что набор значений индексов  включает в себя набор значений индексов , и обозначать это как , если  и  при . Будем считать, что  для любого .

Теорема 1. Для того чтобы задача W(M) сводилась к задаче L достаточно, чтобы существовало такое разбиение ,  множества M, для которого и .

Доказательство. Приведем конструктивное доказательство, основанное на построении сетевой модели.

Не уменьшая общности, можно предположить, что если Æ и N(s)ÎM, то  и . Если какое-либо из рассматриваемых множеств не включено в M, добавим его, приняв соответствующие величины  за нулевые, а  за бесконечно большие величины. Для удобства обозначений определим .

Будем конструировать сеть, состоящую из:

1. узлов множества , , ;

2. специального замыкающего узла ;

3. дуг, определяемых множеством ,  с нижней пропускной способностью  и верхней пропускной способностью , если , где , , ;

4. дуги, определяемой множеством ,  с нижней пропускной способностью  и верхней пропускной способностью , где ;

5.  дуг, определяемых множеством ,  с нижней пропускной способностью  и верхней пропускной способностью , если , где , , ;

6. дуг, определяемых множеством ,  с нижней пропускной способностью  и верхней пропускной способностью , где ;

7. замыкающих дуг  с нулевой нижней и неограниченной верхней пропускными способностями, если , где , .

Дугам вида  поставим в соответствие стоимости , где v – произвольный узел сети, , а остальным дугам – нулевые стоимости.

Очевидно, что любому допустимому решению задачи W(M) соответствует допустимая циркуляция построенной сети и, наоборот (здесь каждой переменной  задачи W(M) соответствует дуга (v,v_F), FÎE_N(s). При этом стоимость допустимой циркуляции и значение целевой функции (2) на соответствующем допустимом решении совпадают. Кроме того, система ограничений (1) совместна в том и только том случае, если в построенной сети существует допустимая циркуляция. Таким образом, предложенная конструкция сводит задачу W(M) к задаче L. Теорема доказана.

Теорема 2. Матрица, соответствующая системе ограничений (1), для которой выполняются условия теоремы 1, абсолютно унимодулярна.

Доказательство.  Проведем доказательство от противного. Предположим, что для системы ограничений (1) выполняются условия теоремы 1, но матрица, соответствующая этой системе, не абсолютно унимодулярна. Так как условия абсолютной унимодулярности, если  и  – целые числа, ,  являются необходимыми и достаточными для целочисленности всех вершин, соответствующих многограннику ограничений системы (1), то можно построить такую линейную целевую функцию, что задача W(M) будет иметь единственное оптимальное не целочисленное решение. По теореме 1 задача W(M) сводится к задаче L, а для задачи о циркуляции минимальной стоимости согласно теореме о целочисленности потока, всегда существует оптимальное целочисленное решение (если задача имеет решение). Полученное противоречие доказывает теорему. Теорема доказана.

Примеры