Транспортная задача замкнутого типа: постановка, существование решения, метод потенциалов

Формулировка транспортной задачи (ТЗ): имеется m поставщиков (пунктов отправления) А₁, …, A_m, у которых имеется однородный груз в кол-вах а₁, …, а_m. В этом товаре нуждается n потребителей В₁, …, В_n, каждый в кол-ве b₁, …, b_n. Т.ж. известны так называемые коэф-ты затрат с_ij = стоимости перевозки груза от постав А_i к потреб В_j. Данные удобно записывать в распределительной матрице:

потр пост	В1	…	Вn
b1	…	bn
А1	а1	с11 х11	…	с1n х1n
…	…	…	…	…
Am	аm	сm1 хm1	…	сmn хmn

Постановка ТЗ: необходимо найти такой план перевозок, чтобы:

1) мощности всех поставщиков были реализованы

2) спрос всех потребителей был удовлетворителен

3) суммарные затраты на перевозки были мин-ми

Составим эк-ко-мат-ую модель ТЗ, т.е. запишем на мат-ом языке зад-ые усл-ия. Обоз-им ч/з х_ij – кол-во ед-ц груза, к-ый необх. доставить от поставщика а_i к потребителю b_j. Матрица, сост-щая из х_ij наз-ся матрицей перевозок, а из с_ij – матрицей тарифов.

Мощности всех поставщиков д.б. реализованы

(1)

Спрос всех потреб-лей д.б. удовл-н

(2) По смыслу поставка не м.б. отр-ной

(3) Суммарные затраты на перевозку
ТЗ закл-ся в нах-ии х_ij, удовл-щие (1), (2), при к-ых (3) принимает наим-ее значение.

План перевозок х наз-ся допустимым, если он удовл-ет (1) и (2). Распред-ие поставок наз-ся оптимальным, если оно доставляет мин-м (3).

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

Т. о ранге матрицы: Ранг матрицы коэф-тов системы (1) = m+n-1. (Если спросят написать):

Решение закрытой ТЗ:

1. нах-ся любое допустимое распред-ие поставок
2. это распред-ие перестр-ся, чтобы мин-ть затраты

1. н-р, эту з-чу м. решить с пом. мет. наим. затрат. Согласно этому мет. В нач. дается макс-но возм-ная поставка в клетку с наим-им коэф-том затрат. Эту клетку сч-т заполненной, для удобства перечерк-т сплошной линией. Выпавшие из дальнейшего рассм-ия клетки наз-т свободными и перечер-т пунктирными линиями. Затем процедура повт-ся в непрочер-ых никакими линиями клетках. После этого дел-ся проверка: кол-во заполн-х клеток д. = m+n-1. Если их меньше, то вводим фиктивные нулевые поставки до треб-го кол-ва. Вводят их т.о., чтобы не образ-ся квадрат или прямоугольник из заполн-ых клеток (иначе невозм-но будет найти потенциал).

2. м-д потенциалов.

Он основан на Т. о потенциалах: Если х^* есть оптимальный план поставок, то ему соотв-т система чисел (u_i^*,v_j^*), i=1,m,j=1,n, наз-ых потенциалами строк и столбцов (поставщиков и потребителей), удовл-щих усл-ию:

Исп-уя эту теорему, мы м. найти эти числа. Для этого u₁ полагают =0 (м. = любому числу), остальные потенциалы нах-ся по заполненным клеткам по след-щей ф-ле: .

После того, как были найдены все потенциалы нах-т Эл-ты матрицы оценок по ф-ле: .

Для заполн-ых клеток эл-ты этой матрицы =0. Если для незапол-ых клеток все >=0, то по теореме мы нах-м оптимальное распред-ие. Если же среди оценок есть отриц-ые, то распред-ие точно не оптимальное и перераспред-т поставки, а именно строят цикл пересчета. Для этого берут любую свободную клетку с отриц-ой оценкой наз-т вершиной цикла, далее двиг-ся по некот-ым заполн-ым клеткам так, чтобы вернуться назад, двиг-ся под прямыми углами. В одной строчке или столбце м.б. лишь одно звено.

Вершине цикла усл-но ставим «+», затем знаки черед-ся(в цикле всегда четное кол-во клеток). Затем из тех клеток, где «-» выбираем наим-ую поставку и ее вычитаем из всех клеток, где «-», и прибавляем, где «+». Измененные значения цикла вставляем в исходную таблицу и снова нах-м потенциалы и матрицы оценок.

Альтернативное решение.

Если оценка получается в оптимальном решении =0 в свободной клетке. Выбираем вершину, создаем цикл, получаем новое решение и составляем выпуклую линейную комбинацию вида: