Приведение открытой транспортной задачи к закрытой

В открытой или несбалансированной задаче имеет место неравенство

.

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

Рассмотрим формальные приемы. Пусть в исходной задаче предложение превышает спрос:

Тогда условия задачи имеют вид

(5.22)

(5.23)

В каждое неравенство (5.22) введем дополнительную переменную x_i,n+1. В сумме эти переменные должны равняться величине дебаланса:

Добавляя это равенство к условиям (5.23), получаем закрытую задачу:

Потребность b_n+1 называют фиктивной.Таким образом, чтобы сбалансировать задачу, достаточно ввести фиктивного потребителя с потребностью, равной дебалансу. Практически это означает, что к исходной таблице добавляется один столбец с потребностью b_n+1 и затратами C_i,n+1 =0. Ненулевые дополнительные переменные в оптимальном решении будут показывать количество груза, остающееся в соответствующих ПО.

Второй случай несбалансированности задачи имеет место, когда спрос превышает предложение:

.

При этом исходные условия записываются в виде:

Поступаем аналогично первому случаю. Введем в каждое неравенство дополнительную переменную x_{m+ 1, j}. Очевидно, что сумма этих переменных равна величине дебаланса:

С учетом этого равенства сбалансированная модель принимает вид:

Такое преобразование соответствует введению фиктивного поставщика (дополнительной строки) с возможностью a_{m+ 1} и нулевыми затратами C_{m+ 1, j}. Дополнительная переменная x_{m+ 1, j} имеет смысл количества груза, недопоставленного j- му ПН.

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

1. ЛПР корректирует потребности, обеспечивая баланс.

2. Выявляется и учитывается влияние недопоставок для каждого потребителя. Если зависимость потерь от величины недопоставки линейная, то задача остается в классе линейных. В этом случае задача балансируется как при формальном подходе, но в дополнительной строке в качестве затрат берутся удельные потери от недопоставки.

Если ожидается, что спрос будет длительное время превышать существующие возможности на величину a_{m+ 1}, то встает вопрос о расширении производства. Он может решаться в рамках транспортной модели следующим образом. Проектируются варианты увеличения производства, каждый на величину a_{m+ 1}. В исходную таблицу добавляется столько строк, сколько предлагается вариантов. При k вариантах это приведет к противоположному дебалансу, равному (k –1)· a_{m+ 1}. Поэтому для сбалансированности модели добавляется фиктивный потребитель с такой потребностью. А в качестве затрат во всех клетках таблицы принимаются суммарные затраты на перевозку и производство С^’_ij=C_ij+C_i, где C_i – себестоимость в i -м ПО. Исключение составляет фиктивный столбец: в первых m клетках затраты равны M, а в остальных – нулю. Те варианты, которые в оптимальном решении закрепятся за фиктивным потребителем, должны быть отброшены.

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

27. Транспортные задачи в сетевой постановке
(транспортные сети)

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

Исходный граф транспортной задачи легко сводится к сети с одним стоком и одним истоком путем введения фиктивных пунктов t (исток) и s (сток). Фиктивным дугам приписываются значения параметров: d_ti=a_i, d_js=b_j, C_ti=C_js =0. Пример сети транспортной задачи без промежуточных пунктов приведен на рис. 5.6.

Модель Т_d-задачи в сетевой постановке имеет вид:

åå C_ijx_ij ®min; (5.29)

k ¹ t, k ¹ s; (5.30)

(5.31)

В сбалансированной транспортной задаче

Z =å a _i=å b_j; (5.32) 0£ x_ij £ d_ij. (5.33)

Равенства (5.30) отражают условия баланса для всех пунктов кроме источника и стока. Баланс для последних представлен уравнением (5.31). В модели использованы обозначения: – множество дуг, входящих в вершину k и выходящих из нее, Z – новая величина, называемая потоком сети.

Наибольший интерес представляет постановка задачи, в которой критерием является поток сети:

Z ® max; (5.34)

k ¹ t, k ¹ s; (5.35) (5.36)

0£ x_ij £ d_ij. (5.37)

Задача (5.34) – (5.37) называется задачей о максимальном потоке. Она имеет большое практическое значение. Для нее разработаны алгоритмы, которые эффективнее методов решения транспортных задач. Они работают непосредственно с сетью как разновидностью графов.

В связи с этим напомним понятие разреза графа (сети), которое используется в основополагающей теореме Форда-Фалкерсона.

Пусть дан ориентированный граф G= (V,U), где V и U -множества вершин и дуг соответственно. Разрезом сети на подмножестве вершин A Ì V, A ¹Æ, A ¹ V, tÎ A, sÎ V\A называется множество дуг ij Î U таких, что i Î A & j Î V\A. Обозначим его P(A). Сумма пропускных способностей дуг разреза называется величиной (пропускной способностью) разреза:

Пример 5.5. Построим один из разрезов сети, приведенной на рис.5.7.

Если A ={t,1,2,3}, то разрезом будет множество дуг P(A)={1,4; 1,6; 2,5; 3,6}, а его величина определяется как d (A)= d₁₄+d₁₆+d₂₅+d₃₆. Дуги, составляющие этот разрез, выделены жирными линиями.▲

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

Можно показать, что задачи максимизации потока и минимизации величины разреза являются двойственной парой. Из этого факта следует
Теорема Форда и Фалкерсона:

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

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

Аналогом цикла пересчета является увеличивающая цепь. Это цепь, соединяющая исток и сток, все дуги которой допустимые. Дуга является допустимой увеличивающей, если ее направление совпадает с направлением потока и поток на ней меньше пропускной способности, то есть x_ij<d_ij. Дуга считается допустимой уменьшающей, если направление дуги противоположно потоку и x_ij > 0.

На увеличивающей дуге поток может возрасти на величину q_ij=d_ij-x_ij, а на уменьшающей дуге возможно снижение потока, равное q_ij = x_ij. Следовательно, максимальное допустимое изменение величины потока по увеличивающей цепи определяется как минимальное из возможных:

q₀ = (5.38)

Таким образом, максимальный поток сети может быть определен по следующему алгоритму.

1. Задать начальную величину потока, обеспечиваемую потоками дуг при выполнении условий (5.35)-(5.37).

Примечание. Очевидно, что в качестве начального всегда можно взять нулевой поток.

2. Построить увеличивающую цепь. Если построить невозможно, то решение завершено.

3. По формуле (5.38) вычислить q₀.

4. Переместить вдоль цепи q₀, прибавляя к потокам на увеличивающих дугах и вычитая из потоков уменьшающих дуг. В результате поток сети увеличивается на q₀. Перейти на шаг 2.