Математические методы исследования операций в экономике (стр. 23 из 37)

Задачу минимизации функции (3.13) при ограничениях (3.11)-(3.12) обычно называют линейной сетевой задачей. Очевидно, что она является задачей линейного программирования. Если дополнительно для каждой дуги сетиd∊D определить величины r_d ≥ 0, называемые пропускными способностями, то, добавив ограничения

мы получаем задачу о потоке в сети с ограниченными пропускными способностями.

Приведенные формулировки задач специально даны в столь абстрактном виде, что позволяет подчеркнуть их универсальность. К очевидной сфере их приложения относится организация грузоперевозок в транспортной сети. В таких моделях вершины i трактуются как пункты, соединенные сетью дорог, и характеризуются потребностями в некотором продукте (b_i<0) или его запасами (b_i>0). Задачи определения плана, минимизирующего затраты на перевозки, которые с математической точки зрения полностью идентичны (3.11)-(3.13), (3.14), также называют транспортными задачами в сетевой постановке.

3.2.2. Метод потенциалов для транспортной задачи в сетевой постановке. Рассмотрим задачу определения оптимального потока Х в некоторой сети (I, D, G), для которого

при ограничениях

где r_d ≥ 0. Предполагается также, что сеть является сбалансированной, т. е.

Для задачи (3.15)-(3.17) справедлив критерий оптимальности:

-Для того, чтобы допустимый поток Х={х_d}_d∊D (т. е. удовлетворяющий условиям (3.16)-(3.17)) был оптимальным, необходимо и достаточно существование для каждой вершины i ∊ I такого числа v_i, называемого потенциалом, что для всех дуг d = (i, j)

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

Для решения транспортной задачи в сетевой постановке (3.15)-(3.17) также может быть применен метод потенциалов, который является обобщением описанного выше метода потенциалов для транспортной задачи в матричной постановке.

Поскольку задача (3.15)-(3.17) является частным случаем задачи линейного программирования, ее можно привести к канонической форме. При этом достаточно просто устанавливается, что ранг матрицы задачи равен m-1, где m — количество вершин в сети. Введем дополнительно еще некоторые понятия, используемые при описании свойств сетевых задач.

Остовом сети (I, D, G) называется любое ее частичное дерево (частичный граф, являющийся деревом). Справедливо утверждение:

-Произвольному остову сети (I, D, G) соответствует базис задачи (3.15)-(3.17) и наоборот.

Пусть имеется некоторый поток Х={х_d}_d∊D. Рассмотрим множество дуг D(X)= {d∊D| 0 < x_d < r_d}. Опорой потока Х называется частичный граф (I, D(X), G). Говорят, что поток Х невырожден, если его опора (7, D(X), G) является остовом сети (I, D, G). Иными словами, используя терминологию транспортной задачи, в невырожденном потоке, которому отвечает допустимый базисный план задачи, дороги, по которым осуществляются перевозки груза, не достигающие по объему ограничения на пропускную способность, образуют остов (связанную подсеть без циклов) рассматриваемой транспортной сети.

Теперь дадим краткое описание схемы метода потенциалов для транспортной задачи в сетевой постановке.

1°. Предполагается, что в начале очередной итерации q имеется некоторый допустимый невырожденный потокХ={х_d^(q)}_d∊D(о методах его генерации на начальном этапе будет сказано в дальнейшем).

По имеющемуся потоку Х^(q) строится система потенциалов пунктов сети. Для этого выбирается произвольный пунктi₀, потенциал которого полагаетсяv_i0 =0. Множество вершин, смежных с i₀, обозначим через I(i₀). Тогда для любой вершины j ∊ I(i₀) потенциалы рассчитываются по правилу

если (i₀,j)∊D(X^(q)) (дуга направлена от i₀),и

если (j,i₀)∊G(D(X^(q))) (j,i₀)∊D(X^(q)) (дуга направлена кi₀).

Получив очередную группу вершин с известными потенциалами, мы имеем возможность на основе (3.22)-(3.23) вычислить потенциалы для следующей группы смежных вершин и т. д., пока не будут определены все потенциалы. Возможность сделать это единственным образом вытекает из свойства отсутствия циклов у остова сети.

Имея полную систему потенциалов, для всех дуг следует проверить условия критерия оптимальности (3.19)-(3.21). Если они выполняются, то текущий поток Х^(q) — оптимальный и, следовательно, алгоритм завершен; в противном случае — переходим к построению следующего «улучшенного» потока.

2°. По аналогии с другими методами последовательного улучшения плана очередной поток получается за счет «ввода» в него одной дуги и «вывода» другой. Если условия критерия оптимальности нарушаются сразу для нескольких дуг, то для ввода имеет смысл выбрать ту, на которой достигается максимальное отклонение цены от разности потенциалов соединяемых вершин. Пусть для ввода выбрана некоторая дугаd_l = (s,t), направленная из вершины s в вершину t. Из правил построения потенциалов следует, что в остове существуют две цепи, одна из которых соединяет базовую вершину i₀, потенциал которой был принят равным нулю, с s, а другая — i₀ с t. Если дополнить остов дугойd_l, образуется единственный цикл. Построенныйцикл является аналогом цепочки преобразования плана в методе потенциалов для транспортной задачи в матричной постановке. Обозначим черезD⁺_(s,t) множество дуг данного цикла, ориентация которых совпадает с ориентацией дугиd_l = (s, t), а через D^-_(s,t)— множество дуг, имеющих противоположную ориентацию. Определим величину возможной корректировки объемов грузоперевозок, «перемещаемых» по циклу

Идея формулы (3.24) достаточно прозрачна: при циклическом преобразовании текущего потока увеличиваются объемы грузоперевозок на тех дугах, которые сонаправлены вводимой дуге, и уменьшаются на дугах, имеющих обратную ориентацию. Соответственно, при добавлении мы должны следить за тем, чтобы не превысить ограничения на пропускные способности (θ ≤ r_d–х_d^(q)), а при вычитании — за неотрицательностью х_d^(q). После определения θ происходит пересчет компонент текущего потока по формуле

В результате мы получаем новый допустимый поток х_d^(q+1)), полагаем номер текущей итерацииq+1 и переходим к п. 1°.

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

Отдельно следует остановиться на методах генерации исходного допустимого потока. Наиболее простой из них (хотя, возможно, и наименее рациональный) основан на идеях, сходных с идеями метода минимизации невязок, используемого для построения допустимого базисного плана ЗЛП. Данный метод предполагает решение соответствующей вспомогательной задачи, которая получается из основной в результате следующих преобразований:

1. К множеству вершин сети добавляется фиктивная нулевая вершина с нулевой интенсивностью (b₀= 0).

2. Все вершины, имеющие отрицательную интенсивность (спрос) b_i < 0, соединяются с добавленной вершиной 0 входящими дугами (0, i), а вершины, обладающие положительной интенсивностью (запасом) b_i >0, — исходящими дугами (i,0). Ограничения на пропускные способности для добавляемых дуг отсутствуют.

3. Стоимости перемещения единицы продукта для вновь добавленных дуг полагаются равными 1, а для дуг, соответствующих транспортной сети основной задачи, — 0.

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