Транспортная задача и методы ЕЁ решения

ТРАНСПОРТНАЯ ЗАДАЧА И МЕТОДЫ ЕЁ РЕШЕНИЯ

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

2. Первый способ (метод Хичкока)

3. Второй способ (метод Креко)

4. Третий способ (модифицированный распределительный метод - МОДИ, или метод потенциалов)

5. Вырождение в задачах линейного программирования

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

6.1 Способ северо-западного угла

6.2 Способ наименьшего элемента в матрице

6.3 Способ двойного предпочтения

6.4 Способ аппроксимации Фогеля

7. Решение транспортных задач, имеющих некоторые дополнительные условия

7.1 Задача с распределением резерва (спрос не равен предложению)

7.2 Запрещение корреспонденции

7.3 Обязательная (директивная) корреспонденция

7.4 Открытая модель распределительного метода

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

8. Закрепление потребителей за поставщиками неоднородного взаимозаменяемого продукта

9. Усложнённая задача перевозки разнородной продукции

10. Транспортная задача по критерию времени

Использованная литература

Вырождение в задачах линейного программирования

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

Таблица 12

Грузообразующие точки	Потенциалы	Грузопоглощающие точки						Итого по вывозу, т
		B1		B2		B3	B4
		0		-4		6	4
A1	0	16		6		10	4400	400
A2	6	8		2 400		12200	14	600
A3	2	2 200		18		8600	6200	1000
Итого по ввозу, т	200	400		800		600	2000

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

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

Таблица 13

Cуточное производство и потребность в кирпиче, т

Расстояние от перевозки, км

Завод

Объём производства

Строительные площадки

Потребность в кирпиче

Завод

B1

B2

B3

B4

B5

A1 A2 A3 A4

100 300 75 125

B1 B2 B3 B4 B5

25 150 100 175 150

A1 A2 A3 A4

15 15 10 6

12 22 5 13

16 22 17 18

21 14 6 22

18 12 10 18

Первоначальное распределение перевозок может быть получено несколькими способами. Рассмотрим на конкретном примере сущность и эффективность некоторых из них. От четырех кирпичных заводов кирпич автомобильным транспортом доставляется на пять строительных площадок. Необходимо определить план перевозок кирпича, при котором объем транспортной работы будет минимальной. Исходные данные задачи приведены в табл. 13.

Способ аппроксимации Фогеля

При этом способе первое допустимое распределение является близким к оптимальному и по сути является приближенным решением задачи.

Таблица 16

Завод	Строительная площадка							Объём производства, т
	B1		B2		B3	B4	B5
A1	15		12 75		1625	21	18	100
A2	15		22		22	14150	12150	300
A3	10		5 75		17	6	10	75
A4	6		13		1875	2225	18	125
Потребность в кирпиче, т	25		150		100	175	150	600

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

Дополнительные условия

Запрещение корреспонденции

В практике организации и планирования работы транспорта могут возникнуть ситуации, когда в силу каких-либо причин невозможно удовлетворить спрос потребителя В_j поставками из А_i, т.е. на корреспонденцию из А_i в B_j налагается запрет.

Например, наложим запрет на перевозки груза от поставщика А₂ потребителю В₂ (см. табл. 17). Чтобы решить задачу, достаточно вместо реального элемента целевой матрицы, стоящего в клетке А₂В₂, равного 2, поставить букву М, под которой подразумевается очень большое число, больше любого наперед заданного числа, или поставить какое-либо число, например 100, которое больше любого элемента целевой матрицы, имеющегося в данной задаче. В этом случае экономически невыгодно осуществлять поставку в эту клетку. Такой приём называется «блокированием клетки».

Таблица 17

Грузообразующие точки	Грузопоглощающие точки						Итого по вывозу, т
	B1		B2		B3	BФ
A1	16		6		6	0400	400
A2	8		2 400		12	0200	600
A3	2 200		18		8800	0	1000
Итого по ввозу, т	200		400		800	600	2000

ТРАНСПОРТНАЯ ЗАДАЧА И МЕТОДЫ ЕЁ РЕШЕНИЯ

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

2. Первый способ (метод Хичкока)

3. Второй способ (метод Креко)

4. Третий способ (модифицированный распределительный метод - МОДИ, или метод потенциалов)

5. Вырождение в задачах линейного программирования

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

6.1 Способ северо-западного угла

6.2 Способ наименьшего элемента в матрице

6.3 Способ двойного предпочтения

6.4 Способ аппроксимации Фогеля

7. Решение транспортных задач, имеющих некоторые дополнительные условия

7.1 Задача с распределением резерва (спрос не равен предложению)

7.2 Запрещение корреспонденции

7.3 Обязательная (директивная) корреспонденция

7.4 Открытая модель распределительного метода

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

8. Закрепление потребителей за поставщиками неоднородного взаимозаменяемого продукта

9. Усложнённая задача перевозки разнородной продукции

10. Транспортная задача по критерию времени

Использованная литература