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

Транспортные задачи. Математические методы решения транспортных задач.

Постановка и основные определения.

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

Рассмотрим математическую модель транспортной задачи.

,

(1)

Здесь a_i — запасы продукции на складах поставщиков, b_j — потребность в продукции потребителей. x_ij — неизвестный план поставки продукции от i-го поставщика к j-му потребителю, c_ij — стоимость доставки единицы продукции от от i-го поставщика к j-му потребителю.

Произвольный набор чисел называется планом задачи (1), если он удовлетворяет всем ее ограничениям. Требуется найти такой план перевозок X от поставщика к потребителю, который бы обладал минимальными затратами на его реализацию. Обычно требования задачи сводятся в таблицу следующего вида:

Потр Пост	b1	b2	…	bn
a1	c11	c12	…	c1n
x11	x12	…	x1n
a2	c21	c22	…	c2n
x21	x22	…	x2n
…	…	…	…	…
…	…	…	…
am	сm1	сm2	…	сmn
xm1	xm2	…	xmn

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

Очевидно, что задача (1) имеет решение тогда и только тогда, когда выполняется условие баланса

(2)

Задача, в которой выполняется равенство (2), называется транспортной задачей закрытого типа, в отличие от задач открытого типа, в которых условие баланса (2) не выполняется. На практике соотношение (2) выполняется крайне редко. Тем не менее задачи решаются независимо от того, открытые это задачи или закрытые.

Если транспортная задача является открытой, то она обычно сводится к закрытой посредством введения фиктивного (m+1)-го поставщика, если спрос превышает предложение, или фиктивного (n+1)-го потребителя в противном случае.

Если объем поставщика > объема потребителя, то в модель вводится фиктивный пункт потребления (добавляется новая строка).

Если потребности > объема поставок, то добавляется фиктивный поставщик (новый столбец).

Фиктивному поставщику в качестве объема его поставки приписывается разница между суммарным спросом и суммарным предложением. Затраты на доставку продукции принимаются нулевыми:

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

В таблице фиктивный поставщик отображается с помощью дополнительной строки, фиктивный потребитель — с помощью дополнительного столбца.

В дальнейшем будем предполагать, что задача (1) — задача закрытого типа.

Пример математической модели для транспортной задачи со следующим условием:

У трех поставщиков находится груз в количестве a_i единиц. Данный груз необходимо доставить трем потребителям, спрос которых в этом грузе составляет b_j. Стоимость перевозки единицы груза из i-го пункта отправления в j-й пункт назначения равна c_ij . Необходимо составить план перевозок с минимальными транспортными издержками, который полностью удовлетворяет спрос потребителей в грузе. (В задаче использовать фиктивного поставщика или фиктивного потребителя).

	Спрос потребителей
Запасы поставщиков	Потребители   Поставщики

Математическая модель:

Сравним общий спрос потребителей с общими запасами поставщиков:

20 + 30 + 60 t 30 + 25 + 40

Так как общий спрос превышает общие запасы, в задачу следует добавить четвертого фиктивного поставщика с запасом 15 ( = 20 + 30 + 60 – (30 + 25 + 40)).

Введем обозначения для искомых 12-ти величин. Пусть

x₁₁ – количество груза, перевозимого от 1-го поставщика 1-му потребителю

x₁₂ – количество груза, перевозимого от 1-го поставщика 2-му потребителю

…..

x₄₃ – количество груза, перевозимого от 4-го поставщика 1-му потребителю

Ограничения на спрос потребителей:

x₁₁ + x₂₁ + x₃₁ + x₄₁ = 20

x₁₂ + x₂₂ + x₃₂ + x₄₂ = 30

x₁₃ + x₂₃ + x₃₃ + x₄₃ = 60

Ограничения на запасы поставщиков:

x₁₁ + x₁₂ + x₁₃ = 30

x₂₁ + x₂₂ + x₂₃ = 25

x₃₁ + x₃₂ + x₃₃ = 40

x₄₁ + x₄₂ + x₄₃ = 15

Граничные условия:

все x_ijt 0, где i = 1…4 (количество поставщиков), j = 1…3 (количество потребителей)

Целевая функция (затраты на перевозку):

ЦФ = 7x₁₁ + 10x₁₂ + 2x₁₃ + x₂₁ + 8x₂₂ + 5x₂₃ + 3x₃₁ + 2x₃₂ + 9x₃₃ à min

2. Базис транспортной таблицы. Символом U обозначим множество клеток транспортной задачи:

Пусть - произвольное подмножество клеток транспортной таблицы. Попытаемся соединить между собой клетки из U₁ вертикальными и горизонтальными звеньями замкнутой ломаной линии. При этом в клетках из U₁ ломаная обязательно должна менять направление. Если это удалось, то будем говорить, что клетки множества U₁ образуют цикл.

Множество клеток будем называть базисом транспортной таблицы, если оно удовлетворяет следующим условиям:

1) никакие клетки из U_б не образуют между собой циклов;

2) любая клетка из (не базисная клетка) образует с базисными клетками цикл.

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

Приведенное выше определение базиса транспортной таблицы является аналогом понятия базиса в линейном программировании и учитывает специфику транспортных задач.

Доказано, что любой базис транспортной таблицы содержит ровно n+m-1 клетку, т.е. . Это условие является необходимым условием «базисности» любого множества клеток транспортной таблицы. Если клеток больше или меньше, то они не образуют базиса.

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

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

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

а) метод северо-западного угла. Алгоритм метода северо-западного угла рассмотрим на конкретном примере. Допустим, что решается следующая транспортная задача:

Потр Пост
					(1)
					(2)
					(3)
	(1)	(2)	(3)	(4)

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

Итерация 1. Выберем в таблице северо-западную клетку (в соответствии с географической терминологией – это клетка в левом верхнем углу таблицы, что объясняет название метода). В начале работы алгоритма – это всегда клетка (1,1). Первый поставщик предлагает 30 единиц продукции, первому потребителю требуется 40 единиц. Поэтому объем поставки от первого поставщика первому потребителю примем равным 30 единицам: x₁₁=min{30,40}=30. Запасы первого поставщика a₁=30 и потребности первого потребителя b₁=40 уменьшим на величину только что рассчитанной поставки x₁₁=30. Поскольку при этом откорректированный объем поставки , то первую строку вычеркнем из таблицы:

	Потр Пост	40
0	30

Итерация 2. В оставшейся части таблицы опять выберем северо-западную клетку. Теперь это будет клетка (2,1). Объем поставки для этой клетки составит x₂₁=min{60,10}=10единиц. После корректировки a₂ и b₁ и вычеркивания второго столбца таблица примет вид:

		10
	Потр Пост	40
0	30
	60

Итерация 3. Снова в оставшейся части таблицы выбираем северо-западную клетку – (2,2). Для нее объем поставки составит x₂₂=min{50,50}=50.После корректировки запасов и потребностей получим: , . Это означает, что из таблицы одновременно вычеркиваются и строка, и столбец:

			10
		Потр Пост	40	50
		30
0	50	60

Аналогичным образом выполняются итерации 4 и 5,после чего таблица примет вид:

			10
		Потр Пост	40	50	30	20
		30
0	50	60
0	20	50

Таким образом, в результате работы алгоритма построен план перевозок:

Потр Пост
30

Поскольку на каждой итерации алгоритма после заполнения клетки вычеркивались строка или столбец (или и строка и столбец вместе), то заполненные клетки не образуют между собой циклов. Поэтому необходимое условие «базисности» автоматически становится и достаточным: для того, чтобы заполненные клетки образовывали базис транспортной таблицы их должно быть n+m-1(в нашем случае - 6).Следовательно, построенный план не является базисным, т.к. количество заполненных клеток составляет 5.

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

В нашем примере годится любая из клеток (3,2), (2,3). Для определенности выберем клетку (2,3). В результате получим начальный базисный план перевозок:

Потр Пост

B) метод минимального элемента. Метод минимального элемента отличается от метода северо-западного угла тем, что в качестве клетки для заполнения выбирается не северо-западная клетка, а клетка с минимальными транспортными издержками. Если таких клеток несколько – выбирается любая из них.

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

				20	20
			Потр Пост	40	50	30	20
			30		1 (1)
	20	20	60	5 (5)	1 (2)		6 (6)
		20	50	4 (4)		1 (3)

В результате получили следующий план перевозок:

Потр Пост

Как видим, этот план является базисным (количество заполненных клеток равно 6). Однако и методе минимального элемента возможны ситуации, когда построенный план не будет базисным из-за недостаточного количества заполненных клеток. Фиктивные базисные клетки в таком случае находятся методом подбора.