Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

оценка Cj каждого небазисного столбца а7определяется выраже­ нием Cj = Cj — яа;. Если все Cj ^ 0, то текущий базис является оптимальным. Если некоторый cj > 0, то соответствующий этому cj столбец aj должен быть введен в базис. Оказывается, что задача нахождения Cj несложна. Будем интерпретировать я г как длину дуги г. Тогда величина яа7будет равна длине той цепи, которой соответствует столбец aj. Заметим, что Cj — + 1 для всех столбцов. При вычислениях с помощью симплекс-метода вектор я появляет­ ся в нулевой строке под слабыми переменными х). Оказывается, что нам не нужно запоминать все столбцы матрицы А, соответ­ ствующие всевозможным цепям каждого продукта. На каждой стадии вычислений можно просто использовать модифицированный

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

ше, то это значит, что текущий базис является оптимальным 2)* . Заметим, что перед введением в таблицу каждый столбец должен быть скорректирован, как это делается в § 7.2.

Перейдем теперь к многопродуктовой задаче о допустимости. Для каждого продукта задана величина потока, и требуется опре­ делить, могут ли быть эти величины одновременно реализованы в заданной сети. Например, пусть задана сеть с ограничениями

в N 2, три единицы 2-го продукта — из N 2 в А 4 и т. д.). Требуется

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

Рассмотрим так называемые допустимые сети, которые удовле­ творяют заданным требованиям к потоку. Каждая такая сеть получается следующим образом. Для каждого продукта находят некоторую цепь из его источника в сток, затем каждой дуге этой

2) Если длина некоторой кратчайшей цепи окажется меньше 1, то стол­ бец, соответствующий этой цепи, должен быть введен в базис.— Прим,

перев.

(1 )

si^ z 0.

Если оптимальное значение 0 ^ 1 , это значит, что в исходной сети все требования к многопродуктовому потоку выполняются.

Если оптимальное значение 0 = 1, то исходная сеть является допустимой. При такой формулировке матрица [а,ц] может содер­ жать миллионы столбцов, но, к счастью, нет необходимости все их выписывать.

Если у нас имеется т столбцов, являющихся начальным бази­ сом задачи (2 ), то с помощью симплекс-метода можно найти вектор

цен я. С помощью этого вектора я можно, как это делалось в моди­ фицированном симплекс-методе, найти столбец, который увели­ чивает значение целевой функции. Так как относительная оценка cj столбца aj определяется выражением Cj = Cj — яа;-, а с} = 1

для всех столбцов, то нам надо искать минимальную из величин

X (т + 1 ) и интерпретируем величину я г как стоимость дуги i

единичной пропускной способности. Когда в симплексной таблице получаются все я г ^ 0 , мы пытаемся ввести в базис столбец,

который представляет самую дешевую допустимую сеть 1). Если получается 0 ^ 1 , значит, все требования к многопродуктовому

потоку выполняются. Если получается, что 0 < 1, а яа7- ^ 1 для всех у, то исходная сеть не содержит линейной выпуклой ком­ бинации допустимых сетей 2*).

Рассмотрим пример, иллюстрирующий решение многопродук­ товой задачи о допустимости. Пусть в сети на рис. 11.8 числа около дуг указывают их пропускные способности, а требования к четырехпродуктовому потоку в этой сети представлены на на рис. 11.9. Требуется определить, можно ли этот четырехпро­ дуктовый поток пропустить в заданной сети.

В симплексной таблице 11.1 представлены дуговые пропускные

менно заданные требования к потоку. Действительно, нетрудно показать, что если в некоторой сети одновременно реализованы заданные требования к потоку, то эта сеть представима в виде линейной выпуклой комбинации допустимых сетей.— Прим, перев.