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

42

РЕФЕРАТ

НА ТЕМУ:

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

СОДЕРЖАНИЕ

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. Транспортная задача по критерию времени

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

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

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

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

Потребителям В₁, В₂, ..., В_j, ..., В_n требуется однородный продукт (груз) в количествах соответственно b₁, b₂, ..., b_j ,…, b_n тонн, который производится (или хранится) у поставщиков А₁, А₂, ..., А_i, ....А_m в количествах а₁, а₂, ...,а_i, ..., а_m тонн. Так как все поставщики производят одну и ту же продукцию, каждый из них может удовлетворять запросы любого потребителя. Расстояния между отправителями и получателями груза известны и составляют 1ц километров. Требуется составить такой план перевозок грузов, который обеспечит удовлетворение запросов всех потребителей при минимальной транспортной работе (минимальной сумме тонно-километров). Очевидно, что для решения рассматриваемой задачи необходимо равенство общей потребности получателей наличию груза у отправителей.

Условия задачи удобно записывать в виде табл. 1, называемой матрицей условий.

Таблица 1

Пункт отправления	Пункт назначения	Наличие груза, т
	В1	В2	…	Вj	…	Вn
А1	111	112	…	11j	…	11n	а1
А2	111	122	…	12j	…	12n	а2
…	….	…	…	…	…	…	…
Аi	1j1	1i2	…	1ij	…	1in	аi
…	…	…	…	…	…	…	…
Аm	1m	1m2	…	1mj	…	1mn	аm
Потребность в грузе, т	b1	b2	…	bj	…	bn	bj == аi

Обозначим через х_ij количество тонн груза, предназначенного к отправке из пункта А_i в пункт В_j. Тогда количество груза, планируемое к доставке в пункт В_j из всех пунктов отправления, составит

х_1j + х_2j +…+ x_mj = Х_ij . (1)

Так как потребность пункта назначения В_j составляет b_j, то при планировании перевозок должно соблюдаться равенство

X_ij = b_j .

Сказанное справедливо для любого пункта В_j. Поэтому получаем n уравнений

х ₁₁ + х ₂₁ +…+ х _m1 = b ₁

х ₁₂+ х ₂₂ +…+ х_m2 = b ₂

….……………………… (2)

х _1n + х _2n+…+ х _mn = b _n

С другой стороны, общее количество груза, отправляемого из пункта А_i во все пункты назначения В_j составит

х_i1+х_i2+...+x_in= Х _ij. (3)

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

Х _ij=a_i .

Так как приведённое рассуждение относится к любому пункту отправления, имеем m уравнений

х ₁₁ + х ₂₁ +…+ х _1n = a ₁

х ₂₁+ х ₂₂ +…+ х_2n = a ₂

……………………. (4)

х _m1 + х _m2+…+ х _mn = a _m

Более компактно уравнения (1.1) - (1.4) можно записать следующим образом:

Х _ij= b_j, j = 1, 2, …, n; (5)

Х _ij= a_i, i = 1, 2, …, m; (6)

P = 1₁₁x₁₁ +1₁₂ x₁₂+…+1_ij x_ij +…+1_mn x_mn = l_ij X _ij. (7)

Очевидно, что объем каждой поставки не может быть отрицательным числом, т.е.

x_ij >0, i=1,2, ..., m; j=1,2,..., n. (8)

Таким образом, в математической форме транспортная задача формулируется следующим образом: определить значения переменных x_ij минимизирующих линейную форму

l_ij X _ij, j = 1, 2, …, n, i = 1, 2, …, m (9)

при условиях

X _ij= b_j, j = 1, 2, …, n; (10)

X_ij= a_i, i = 1, 2, …, m; (11)

x_ij>0, i =1, 2, ..., m; j=1, 2,..., n. (12)

Соблюдение равенства (1.10) обеспечивает полное удовлетворение запросов всех потребителей. Уравнения (1.11) гарантируют полный вывоз из пунктов отправления, а уравнения (1.9) - неотрицательность переменных. Для совместности системы уравнений (1.9 - 1.12) необходимо, чтобы

a_i = b_j . (13)

Равенство (1.13) является не только необходимым, но и достаточным условием для совместности системы уравнений (1.9 - 1.12).

Поскольку уравнения (1.10 - 1.12) содержат неизвестные только в первой степени, а показатель L_ij в формуле (1.9) не зависит от x_ij, сформулированная задача является задачей линейного программирования. Формулировка задачи, в которой спрос и предложение равны, получила название закрытой модели.

Модель транспортной задачи имеет следующие особенности:

1. Модель выражается неопределённой системой линейных уравнений и, следовательно, имеет бесчисленное множество возможных решений.

2. Модель совместна, т.е. имеет решение.

3. Элементами матрицы системы являются единицы и нули.

4. Система является линейно-зависимой, так как любое её уравнение можно представить в виде линейной комбинации остальных уравнений.

5. Число линейно независимых уравнений всегда на одно меньше общего количества уравнений в системе, так как без любого одного уравнения каждое оставшееся уравнение нельзя представить как линейную комбинацию из других уравнений. Следовательно, базис системы равен количеству уравнений минус единица.

6. Целевая функция выражается линейной формой. Матрица целевой функции -- это матрица-строка, элементами которой могут быть расстояния, время или стоимость перевозки.

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

Разновидности распределительного метода отличаются в основном способом выявления оптимального решения.

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

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

Распределение груза по потребителям производится начиная с грузоотправителя А₁ и грузополучателя В₁ т.е. с клетки А₁В₁. Потребность в грузе потребителя В₁ удовлетворяется полностью грузоотправителем А₁ . В клетку А₁В₁ записывается объем потребления грузополучателя В₁ - 200 т. Оставшийся в точке А₁, груз в количестве 200 т будет вывозиться потребителю В₂. Но потребителю В₂ нужно завезти не 200, а 400 т груза. Недостающие 200 т груза можно ввозить от грузоотправителя А₂. Оставшиеся у грузоотправителя А₂ 400 т груза можно вывезти в точку В₃ и т.д. Рассуждая таким образом, распределим весь груз по потребителям.

Таблица 2

Грузообразующие точки	Грузопоглощающие точки	Итого по вывозу, т	Потенциалы
	B1	В2	B3	В4
А1	16 200	6 200	10	4	400	-16
А2	8	2 200	12 400	14	600	-12
А3	2	18	8 400	6 600	1000	- 8
Итого по ввозу, т	200	400	800	600	2000	Vj
Потенциалы	0	10	0	2	Ui	--

В табл. 2 распределение груза по потребителям (закрепление потребителей за грузоотправителями) выразится в заполнении клеток А₁В₁, A₁B₂, А₂В₃, А₂В₂, А₃В₃, А₃В₄.

Условимся в дальнейшем называть клетки таблицы, в которых отмечено количество груза, перевозимого от грузоотправителя к данному грузополучателю, загруженными. Количество загруженных клеток всегда должно равняться величине базиса, который будет равен n + m - 1 (n- число строк таблицы; m - число столбцов). В данном примере это условие соблюдено: 3 + 4-1=6.

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

200-16 + 200-6 + 200-2 + 400-12 + 400-8 + 600-6 = 16 400 т*км.

Однако нельзя сказать, является ли полученный вариант решения оптимальным или нет. Чтобы ответить на этот вопрос, необходимо выполнить следующие действия:

1. Во всех загруженных клетках получить нулевой потенциал. Для этого по строчкам и столбцам табл. 1.2 к расстояниям, проставленным в верхних правых углах клеток, прибавляют такие числа (потенциалы), которые в сумме с расстояниями загруженных клеток дают нуль (нулевой потенциал). Например, чтобы получить в загруженной клетке А₁В₁, нулевой потенциал, нужно ко всем расстояниям строки А₁ прибавить потенциал - 16(16-16 - 0). В загруженной клетке А₁В₂ нулевой потенциал получится в том случае, если к ее расстоянию 6 и ранее прибавленному по строке А₁ потенциалу - 16 прибавить по столбцу В₂ потенциал + 10 (6 -16+ 10= 0) и т.д.

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

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

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

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

В первом варианте решения нашей задачи отрицательные потенциалы имеются в клетках А₁В₄, А₂В₁, А₁В₃, А₃В₁ (табл. 1.3). Наиболее потенциальной клеткой (клетка, имеющая наибольшее отрицательное значение потенциала) будет клетка А₁В₄, потенциал которой равен -10. Во втором шаге решения наиболее потенциальная клетка получает загрузку. Это вызывает перераспределение загрузки клеток таблицы, которое осуществляется следующим образом:

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

2. Для наиболее потенциальной клетки А₁В₄ строится контур. Контуром называется замкнутая ломаная линия, образованная прямыми отрезками, углы соединений между которыми равны 90°. Строится контур так, чтобы все углы, кроме одного, располагались в загруженных клетках, а один угол находился в свободной, наиболее потенциальной клетке. При соблюдении этих двух правил для каждой свободной клетки можно построить только один контур.

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

Таблица 3

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

4. Выявляют наименее загруженную клетку, занятую отрицательным углом контура. Количество груза, указанное в этой клетке, отнимается из всех клеток, занятых отрицательными углами контура, и прибавляется во все клетки, занятые положительными углами.

В результате такого действия одна или несколько из ранее загруженных клеток становятся свободными, а наиболее потенциальная клетка становится загруженной. Ранее загруженные клетки, которые не оказались расположенными в углах контура, переносят в таблицу (табл. 4) нового варианта закрепления потребителей груза за грузоотправителями без изменений.

В табл. 3 из всех клеток, занятых отрицательными углами контура, наименьшую загрузку имеет клетка А₁В₂ - 200 т. Эти 200 т вычитаются из клеток, занятых отрицательными углами контура, и прибавляются в клетки, занятые положительными углами. В результате клетка А₁В₂ становится свободной, а наиболее потенциальная клетка А₁B₄ получает загрузку в 200 т. Загрузка клетки А₁В₁, в которой нет угла контура, в новом варианте решения остаётся без изменения (см. табл. 4).

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

200 * 16 + 200 * 2 + 200 * 12 + 600 * 8 + 400 * 6 = 14400 т*км.

Это на 2000 т*км меньше, чем получено в первом варианте решения. Величину сокращения грузооборота можно определить и как произведение количества груза, которое получила наиболее потенциальная клетка, на её потенциал.

Таблица 4

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

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

Задача решается до тех пор, пока не будет найден оптимальный вариант. Количество промежуточных решений зависит от сложности задачи. В нашем примере второй вариант, как и первый, является неоптимальным (табл. 5), оптимальный же вариант получен в результате третьего шага решения (табл. 6).

Таблица 5

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

Таблица 6

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

Объем грузовой работы при оптимальном решении

400*4 +400*2+ 200*12 + 200*2 + 600*8 + 200*6 =11200 т*км.

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

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

На основании исходных данных задачи так же, как и при первом способе решения, составляется таблица и указывается по диагонали первое распределение груза (табл. 7). Определение оптимального решения начинается с построения контуров для всех свободных клеток. Расстояниям, указанным в клетках положительных углов контура, придается знак плюс, а расстояниям отрицательных углов - знак минус. Алгебраическая сумма расстояний, стоящих в клетках всех углов контура, будет потенциалом свободной клетки. Так, у контура свободной клетки А₂В₁; отрицательные углы будут расположены в клетках А₁B₁, А₂В₂, положительные - в клетках А₂В₁, A₁B₂. Ее потенциал будет -16-2+8+6 = -4.

У контура клетки А₃В₁, отрицательные углы будут находиться в клетках A₁B₁, A₂B₂, A₃B₃, положительные - в клетках А₃В₁, А₂В₃, А₁В₂. Потенциалом этой клетки будет сумма: -16-2-8+2+12+6 = -6 и т.д.

Найденные таким путем потенциалы записывают в левых верхних углах свободных клеток. При решении задачи на минимум оптимальный вариант будет в том случае, когда потенциалы всех свободных клеток станут положительными величинами. Если же есть отрицательные значения потенциалов, то выявляется наиболее потенциальная клетка (в нашем примере такой клеткой будет клетка А₁В₄) и по ее контуру (см. табл. 7), соблюдая указанные ранее правила, делают перераспределение груза.

Таблица 7

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

С новым вариантом решения (табл. 8) производят те же действия, что и с предыдущим, и так далее до получения оптимального решения (табл. 9).

Таблица 8

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

Таблица 9

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

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

Условие задачи записано в табл. 10. Первое распределение груза производится по диагональному методу. Для оценки оптимальности решения подбираются потенциалы следующим образом.

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

L_ij = N_i + M_j ,

где N_i - потенциал строки; М_j- потенциал столбца.

Так, если для первой строки таблицы взят потенциал, равный нулю, то потенциал столбца В₁ будет равен 16, так как разность между расстоянием загруженной клетки А₁В₁ и потенциалом первой строки равна 16 (16 - 0 = 16). Потенциал второго столбца В₂ будет равен 6 (6 - 0 = 6), так как расстояние загруженной клетки А₁В₂ равно 6. Тогда потенциал строки А₂ будет определен по расстоянию загруженной клетки А₂В₂ и найденному потенциалу столбца В₂ (2 - 6 = -4). Потенциал столбца В₃ определяется через расстояние загруженной клетки А₂В₃ и найденный потенциал второй строки А₂: 12 - (-4) =16. Таким же образом находятся потенциалы строки А₃ и столбца В₄.

Таблица 10

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

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

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

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

Клеткой, обладающей наибольшим потенциалом при решении задачи на минимум, является клетка, у которой имеется наибольшая разность между суммой потенциалов и расстоянием, проставленным в клетке. В нашем примере такой клеткой является клетка А₁В₄ (см. табл. 10). Ее потенциал равен 10 (14 - 4 = 10). Перераспределение загрузок по ее контуру дает новый вариант решения задачи (табл. 11), который не является еще оптимальным. В этом варианте наиболее потенциальной будет клетка А₃В₁. Ее потенциал равен 16(18-2= 16). Перераспределение загрузки по контуру клетки А₃В₁ позволяет найти оптимальное решение задачи (табл. 12).

Таблица 11

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

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

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

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

Таблица 12

Грузообразую-щие точки	Потенциалы	Грузопоглощающие точки	Итого по вывозу, т
		B1	B2	B3	B4
		0	-4	6	4
A1	0	16	6	10	4 400	400
A2	6	8	2 400	12 200	14	600
A3	2	2 200	18	8 600	6 200	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.

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

Построение допустимого плана этим способом начинается с верхней левой клетки и заканчивается в нижней правой клетке матрицы. В клетки заносят максимально возможную поставку, учитывая соотношение ресурсов поставщика и спрос потребителя. Груз первого поставщика распределяется так, что вначале удовлетворяются потребности первого потребителя, затем второго и так до полного распределения всего объема грузов данного поставщика. Затем переходят к распределению грузов второго поставщика и так до полного распределения объема грузов всех поставщиков. Если спрос какого-либо потребителя превышает количество груза у поставщика, то недостающий спрос удовлетворяется за счет следующего поставщика, т.е. расчет в этом случае ведется по столбцу. Допустимый план перевозки кирпича на строительные площадки, составленный способом северо-западного угла, приведен в табл. 14. В плане полностью соблюдается условие по ввозу и вывозу кирпича, количество заполненных клеток соответствует m + n - 1. Суммарная транспортная работа по плану распределения, составленному способом северо-западного угла, будет

L( x ) = 15 * 25 +12 * 75 +22 * 75 +22 * 100+14 * 125+ 6 * 50 + 10 * 25+ 18* 125 = 9675т* км.

Таблица 14

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

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

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

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

Функционал полученного решения

L(x) = 6 * 25 + 12 * 75 +5 * 75+16 * 25+ 18 * 75 + 14 * 50 + 12 * 150 +22 * 25 = 7625 т*км.

Обычно способ наименьшего элемента в матрице дает допустимое решение, более близкое к оптимальному, чем способ северо-западного угла. В условии нашего примера суммарный объем транспортной работы меньше на 2050 т*км (96*75 - 7625 = 2050). Способ наименьшего элемента в матрице целесообразно использовать при решении небольших матриц, поскольку с увеличением размера матрицы его применение затрудняется. В данном случае хорошие результаты позволяет получить способ двойного предпочтения.

Таблица 15

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

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

Этот способ заключается в нахождении минимального элемента в столбце и его проверке на минимальность по строке таблицы. Если этот элемент окажется наименьшим и по столбцу, и по строке, то в данную клетку записывают максимально возможную поставку, и все элементы данной строки или столбца из дальнейшего рассмотрения исключают. Если минимальный элемент в столбце не является минимальным в строке, то временно этот столбец из рассмотрения опускают и переходят к следующему. После рассмотрения всех столбцов возвращаются к пропущенным и операции повторяют. Так поступают до тех пор, пока не будет получено базисное распределение. Базисное распределение, полученное способом двойного предпочтения, приведено в табл. 16.

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

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

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

Таблица 16

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

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

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

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

Если в задаче спрос потребителей меньше предложения поставщиков, то задача решается следующим образом. Составляется таблица по форме табл. 17, в которую вводится фиктивный (несуществующий) потребитель. Его спрос равен разности между суммами фактических величин предложения и спроса (2000 -1400 = 600), т.е. 600 т. Для фиктивного потребителя отводится дополнительный, четвертый столбец в таблице, куда и проставляют потребность в 600 т груза. Поскольку груз никуда не вывозится, то в углах клеток столбца В_ф ставят нули (можно и любые другие цифры, но одинаковые величины). Дальше задача решается обычным путем по алгоритму метода потенциалов (распределительного метода), рассматривая столбец В_ф как четвертый потребитель груза. В данном случае задача решена с помощью модифицированного распределительного метола. Полученное решение, кроме оптимального закрепления потребителей за грузоотправителями, доказывает, что наиболее рационально, с точки зрения транспортных затрат, иметь 400 т резервного запаса груза у поставщика А₁ и 200 т - у поставщика А₂.

Аналогично решаются и задачи, в которых потребности в грузе у грузопоглощающих точек выше, чем его имеется у грузоотправителей (спрос превышает предложение). Только в этом случае для недостающего объема груза вводится фиктивная строка, клетки которой будут иметь нулевые элементы, а ограничение по предложению равняться разности между суммами фактического спроса и предложения.

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

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

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

Таблица 17

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

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

Директивная корреспонденция означает обязательность поставки из точки А_i; в точку В_j части или всего объема груза, имеющегося в точке А_i, В этом случае величина обязательной поставки вычитается из суммы спроса В_j и суммы ограничения А_i и при решении задачи не учитывается.

Например, из точки А₂ нужно обязательно поставить 400 т груза в В₃ (см. табл. 17). Следовательно, при решении задачи ограничения столбца В₃ и строки А₂ должны быть уменьшены на 400 т, т.е. будут равны для В₃ - 400 т (800 - 400 = 400) и для А₂ - 200 т (600 - 400 = 200).

При подсчете окончательного грузооборота обязательный объем (400*8 = 3200 т*км) прибавляют к полученному оптимальному объему грузооборота.

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

Открытая модель распределительного метода возникает в тех случаях, когда отсутствует какая-либо из групп ограничений -- спрос b_j или предложение a_i. Это означает, что любой потребитель может взять всю сумму имеющихся у поставщиков материалов или, наоборот, любой из поставщиков может удовлетворить спрос всех потребителей данного материала.

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

Рассмотрим пример. Чтобы удовлетворить потребности в строительном песке пяти потребителей В₁, В₂, В₃, В₄, В₅, его можно добывать в неограниченном количестве в любой из трёх точек А₁, А₂, А₃. Потребность в сутки: В₁ - 300 т, В₂ - 200 т, В₃ - 400 т, В₄ - 250 т, В₅ - 400 т.

Расстояния (элементы целевой матрицы) между потребителями и возможными местами добычи песка указаны в правых верхних углах клеток табл. 18 .Сколько в каждой точке нужно добывать песка и как спланировать грузопотоки, чтобы транспортная работа была оптимальной?

Таблица 18

Возможные поставщики песка	Потребители песка	Запасы, т
	B1	B2	B3	B4	B5
A1	2	4	6	3	4	--
A2	5	3	8	5	4	--
A3	3	1	4	5	3	--
Потребность, т	300	200	400	250	400	1550

Переносим ограничения спроса по столбцам в клетки с минимальными расстояниями А₁В₁, А₃В₂, А₃В₃, А₁В₄, А₃В₅. Таким образом, эти клетки получают загрузку в 300 т, 200 т, 400 т, 250 т и 400 т (табл. 19).

Таблица 19

Возможные поставщики песка	Потребители песка	Запасы, т
	B1	B2	B3	B4	B5
A1	2 300	4	6	3 250	4	550
A2	5	3	8	5	4	--
A3	3	1 200	4 400	5	3 400	1000
Потребность, т	300	200	400	250	400	1550

Поскольку загружались клетки с оптимальным значением элемента целевой матрицы, то полученное решение с точки зрения транспортной работы будет оптимальным. При этом добыча песка в точках А₁ и А₂ должна быть соответственно 550 и 1000 т. В точке А₂ добычу вести нерационально.

Открытая модель распределительного метода встречается при решении задач определения оптимального размещения и мощности АТП, закрепления маршрутов за АТП, размещения и ёмкости складов и т.д.

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

Для задачи, условия которой записаны в табл. 18, пользуясь методом МОДИ, найдем оптимальное решение (табл. 19). Объем грузовой работы при оптимальном решении равен 11 200 т*км.

Однако в этой задаче имеется другое базисное оптимальное решение с точно таким же объёмом грузовой работы, но другим вариантом грузопотоков. Оно получится, если загрузить клетку А₁В₃, перераспределив загрузку в клетках А₁В₄ , А₃В₃ и А₃В₄, учитывая ограничения по спросу и предложению (табл. 20). Следовательно, имеются два базисных оптимальных решения (табл. 19 и 20).

Переместив 400 т груза из клетки А₃В₃ в ранее свободную клетку А₁В₃ и из клетки А₁В₄ - в клетку А₃В₄, получим другой вариант оптимального решения (другой базис). При этом от первого перемещения было получено сокращение грузооборота на 400*2 = 800 т*км, от второго - увеличение на 800 т*км, т.е. грузооборот остался прежним, а грузопотоки изменились. Потенциалы и их суммы для всех клеток матрицы одинаковы.

Сохранить неизменными в табл. 21 потенциалы позволило то обстоятельство, что в свободной клетке А₁В₃ табл. 20 сумма потенциалов равна элементу целевой функции. Это же мы замечаем и для клетки А₁В₄ в табл. 20.

Таблица 20

Возможные поставщики	Потенциалы	Грузопоглощающие точки	Итого по вывозу, т
		B1	B2	B3	B4
		2	-2	8	6
A1	-2	16	6	6	4 400	400
A2	4	8	2 400	12 200	14	600
A3	3	2 200	18	8 600	6 200	1000
Потребность, т	200	400	800	600	1550

Таблица 21

Возможные поставщики	Потенциалы	Грузопоглощающие точки	Итого по вывозу, т
		B1	B2	B3	B4
		2	-2	8	6
A1	-2	16	6	6 400	4	400
A2	4	8	2 400	12 200	14	600
A3	0	2 200	18	8 600	6 200	1000
Потребность, т	200	400	800	600	1550

Следовательно, при решении задач модифицированным распределительным методом наличие одного или нескольких альтернативных оптимальных базисных решений можно обнаружить по равенству суммы потенциалов с элементами целевой матрицы в одной или нескольких свободных клетках. Но если имеется хотя бы одно альтернативное базисное решение, то существует множество оптимальных решений. В этом нетрудно убедиться, если в клеткахА₁В₃, А₁В₄, А₃В₃ и А₃В₄ изменить загрузку в различных вариантах, не нарушая ограничений по спросу и предложению.

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

Распределительный метод достаточно прост, он позволяет решать широкий круг различных задач. Существенным недостатком этого метода является то, что им можно пользоваться только тогда, когда имеем дело с однородными величинами (однородный груз, однородный подвижной состав и т.п.).

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

Во многих случаях перевозке подлежат разные, но взаимозаменяемые продукты (например, уголь, нефть, мазут или цемент разных марок). Рассмотрим постановку и метод решения такой задачи.

В пунктах а₁, А₂, ..., А_i, ..., А_m хранится соответственно а₁, а₂, …, а_i, …, а_m тонн топлива разных сортов, причем в каждом из них имеется топливо только одного сорта. Таким образом, число пунктов отправления и число сортов топлива в этой задаче совпадают. Под топливом разного сорта подразумевается не только горючее разных видов (например, уголь, нефть, мазут), но и топливо одного вида, но разного качества (например, уголь разных сортов). Предприятиям, расположенным в пунктах В₁, В₂, ..., В_j, ..., В_n, требуется соответственно b₁, b₂, ..., b_j, …,b_n тонн условного топлива. Каждый из потребителей может использовать любой из имеющихся видов топлива. Коэффициенты приведения топлива разных сортов к условному топливу известны и составляют k₁, k₂, …, k_i, …,k_m. Известны также расстояния l_ij между пунктами А_i и В_j. Требуется составить план перевозок (закрепления потребителей топлива за поставщиками) так, чтобы полностью удовлетворить запросы всех потребителей при минимальном объеме транспортной работы.

Обозначим через x_ij количество топлива 1-го сорта (т. е. из i-го пункта), поставляемое j-му потребителю. Тогда рассматриваемая задача формально записывается следующим образом: минимизировать транспортную работу

x_ij l_ij (14)

при условиях

k_i x_ij = b_j , j = 1, 2, …, n (15)

x_ij < a_i , i = 1, 2, …, m (16)

x_ij > 0, I = 1, 2, …, m; j = 1, 2, …, n (17)

Ограничения (15) означают, что объем доставляемого в каждый пункт потребления топлива должен в условных единицах равняться спросу этого пункта. Условия (16) означают, что общий объем топлива, направляемый во все пункты потребления из i-го пункта, не должен превышать запасов топлива i-го сорта (имеющегося в i-м пункте).

Задача (14) -- (17) отличается от классической транспортной наличием в условиях (15) коэффициента k_i. Поэтому актуальной является проблема сведения подобной задачи к классической транспортной. Анализ показывает, что в данном случае это возможно.

Обозначим запасы топлива на складах в тоннах условного топлива (условных тоннах) через а`<sub>1</sub>, а`₂, ..., а`<sub>i</sub>, ..., а`_m. При этом а`<sub>i</sub> = а<sub>i</sub> k<sub>i</sub>. Поскольку произведение условных тонн и условного расстояния перевозки не дают теперь величины реальной транспортной работы (тонно-километров), заменим l<sub>ij</sub> на l`_ij = l_ij /k _i.

Нетрудно заметить, что произведение условных тонн и условного расстояния дает реальные тонно-километры, т. е.

l`<sub>ij</sub> x`_ij = l_ij x _ij ,

где х` -- количество условного топлива, поставляемого из пункта А_i в пункт В _j).

В новых обозначениях задача принимает следующий вид: минимизировать линейную форму

l`<sub>ij</sub> x`_ij (18)

при условиях

x`<sub>ij</sub> = b`_j , j = 1, 2, …, n; (19)

x`<sub>ij</sub> < a`_i, i = 1, 2, …, m; (20)

x`_ij >0, i = 1, 2, …, m , j = 1, 2, …, n. (21)

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

1. Пересчитать матрицу расстояний || l_ij || на || l`_ij || = l_ij /k_i.

2. Выразить запасы топлива в пунктах А₁, А₂, ..., А_i, ..., А_m в тоннах условного топлива.

3. Составить матрицу условий, используя величины а`<sub>i</sub>, b<sub>j</sub> и l`_ij.

4. Решить поставленную задачу (найти оптимальный план перевозок топлива, выраженного в условных единицах) методом потенциалов.

5. Заменить величины а`<sub>i</sub>, х`_ij и l`_ij матрицы оптимального плана числами а_i, х_ij и l_ij, рассчитанными по формула

a _i = а`<sub>i</sub> / k<sub>i</sub> , x<sub>ij</sub> = x`_ij/ k_i , l _ij = l`_ij / k_i .

Оптимальный план перевозок топлива найден. Решение закончено.

Поясним процедуру вычислений на конкретном примере. Пусть в пунктах А₁ и А₄ имеется соответственно 30 и 20 т угля марки А, в пункте А₂ --50 т угля марки Бив пункте А₃-- 40 т угля марки В. Коэффициенты перевода угля в тонны условного топлива для марок А, Б и В соответственно 1,00; 1,20 и 1,25. Потребителям В₁, В₂, В₃ и В₄ требуется соответственно 40, 70, 40 и 10 т условного топлива, причем удовлетворять эту потребность можно углем любой марки. Расстояния между пунктами приведены в табл. 22. Требуется закрепить потребителей угля за поставщиками так, чтобы при полном удовлетворении спроса суммарный объем транспортной работы при перевозке угля был минимальным.