Решение транспортной задачи

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

Решение транспортной задачи рассмотрим на следующем примере. Некоторая транспортная компания занимается перевозкой зерна специальными зерновозами от трёх элеваторов к четырём мельницам. В таблице 15.2 показаны возможности элеваторов по поставке зерна (предложение) и потребность мельниц в зерне (спрос). Спрос и потребность измеряются в зерновозах. Кроме того, в таблице представлена стоимость c_ij перевозки зерна от элеваторов к мельницам в сотнях долларов.

Таблица 15.2

	x 11	x 12	x 13	x 14
	x 21	x 12	x 23	x 24
	x 31	x 32	x 33	x 34

Последовательность этапов алгоритма решения транспортной задачи повторяет аналогичную последовательность этапов симплекс-метода:

1) определяется начальное базисное допустимое решение;

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

3) с помощью условия допустимости определяют переменную, исключаемую из базиса; затем находят новое базисное решение и возвращаются ко второму этапу.

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

Выполнение метода северо-западного угла начинается с ячейки x ₁₁ (северо-западный угол). Метод включает следующие этапы:

1) переменной x ₁₁ присваивается максимальное значение, допускаемое ограничениями на спрос и предложение;

2) вычёркивается строка или столбец с полностью реализованным предложением или с удовлетворённым спросом; если одновременно удовлетворяется и спрос, и предложение, то вычёркивается либо строка, либо столбец;

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

Рассмотрим применение метода к данным из примера. Максимальное значение x ₁₁, удовлетворяющее ограничениям спроса и предложения, равно 5. Приписываем это значение x ₁₁, вычёркиваем столбец 1 и переходим к ячейке x ₁₂. Учитывая то, что предложение в строке один уже частично удовлетворено на предыдущем шаге, максимальное значение x ₁₂ равно 10. Вычёркиваем первую строку и переходим к ячейке x ₂₂. Продолжая действовать аналогично, получаем результат, приведённый в таблице 15.3.

Таблица 15.3

	5

Базисное решение, полученное по методу северо-западного угла: x ₁₁=5, x ₁₂=10, x ₂₂=5, x ₂₃=15, x ₂₄=5, x ₃₄=10. Суммарная стоимость перевозок при таком решении рана 520.

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

Таблица 15.4

Вновь обратимся к нашему примеру. Минимальную стоимость имеет ячейка x ₁₂. Максимальное значение, удовлетворяющее и спрос, и предложение равно 15. Приписываем переменной x ₁₂ значение 15 и вычёркиваем второй столбец (могли бы вычеркнуть и первую строку). Следующее минимальное значение в невычеркнутой части – 4 (x ₃₁). Переменной x ₃₁ присваиваем значение 5, которое полностью удовлетворяет спрос. Вычёркиваем первый столбец. Следует отметить, что при присвоении переменной в ячейке значения мы должны соответствующим образом скорректировать значение неудовлетворённого спроса или предложения. Поэтому после последнего описанного шага значение предложения третьего элеватора станет равно 5.

Действуя аналогичным образом, получаем результат, приведённый в таблице 15.4. Переменным в невычеркнутом столбце необходимо присвоить значения, которые удовлетворяли бы оставшимся ограничениям. Такие значения также указаны в таблице. Полученное начальное базисное решение имеет вид: x ₁₂=15, x ₁₄=0, x ₂₃=15, x ₂₄=10, x ₃₁=5, x ₃₄=5. Соответствующее значение целевой функции: z = 475.

Метод Фогеля является вариацией метода наименьшей стоимости и в общем случае находит лучшее начальное решение. Метод Фогеля включает следующие шаги.

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

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

3. Если не вычеркнута только одна строка или только один столбец с нулевым спросом или предложением, вычисления заканчиваются. Если не вычеркнута одна строка (столбец) с положительным предложением (спросом), в этой строке (столбце) методом наименьшей стоимости находятся базовые переменные и вычисления заканчиваются. Если всем невычеркнутым строкам и столбцам соответствуют нулевые объёмы предложения и спроса, методом наименьшей стоимости находятся нулевые базисные переменные, и вычисления заканчиваются. Во всех остальных случаях переходят к пункту 1.

Таблица 15.5

						Штраф
Штраф

Используем метод Фогеля для определения начального решения в примере с элеваторами. Из таблицы 15.5 видно, что наибольший штраф имеет строка 3. Наименьшую стоимость в этой строке имеет переменная x ₃₁. Максимальное значение, которое может удовлетворить обоим ограничениям, составляет 5. Вычёркиваем первый столбец, положив значение ограничения для первой строки равным 5.

Таблица 15.6

						Штраф
Штраф

Таблица 15.7

						Штраф
Штраф

Таблица 15.8

						Штраф
Штраф

Продолжая действовать аналогично (табл. 15.6, 15.7, 15.8), получаем начальное базисное решение: x ₁₂ = 15, x ₁₄ = 0, x ₂₃ = 15, x ₂₄ = 10, x ₃₁ = 5, x ₃₄ = 5. Соответствующее значение целевой функции z = 475. В данном случае значение целевой функции такое же, как и при использовании метода наименьшей стоимости. Но обычно метод Фогеля даёт наилучшее начальное решение для транспортной задачи.

После определения начального базисного решения применяется алгоритм, позволяющий найти оптимальное решение транспортной задачи.

1. С помощью симплекс-критерия I определяется вводимая в базис переменная. Если в соответствии с критерием оптимальное решение достигнуто, то алгоритм завершается.

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

Определение вводимой в базис переменной производится с использованием метода потенциалов, с помощью которого определяются коэффициенты целевой функции, соответствующие небазисным переменным. В методе потенциалов каждой строке i и столбцу j ставится в соответствие числа (потенциалы) u_i и v_j, удовлетворяющие условию

Рассмотрим решение задачи с элеваторами. В качестве начального возьмём решение, полученное методом северо-западного угла (табл.15.9).

Таблица 15.9

В задаче имеется 7 неизвестных переменных (потенциалов) и 6 уравнений, соответствующих 6 базисным переменным. Для того, чтобы найти значения потенциалов из этой системы уравнений, нужно присвоить одному из них произвольное значение (обычно полагают u ₁ = 0), и затем последовательно вычислять значения остальных потенциалов. Потенциалы определяются в таблице 15.10.

Таблица 15.10

Базисные переменные	Уравнения для потенциалов	Решение
x 11	u 1+ v 1 = 10	v 1 = 10
x 12	u 1+ v 2 = 2	v 2 = 2
x 22	u 2+ v 2 = 7	u 2 = 5
x 23	u 2+ v 3 = 9	v 3 = 4
x 24	u 2+ v 4 = 20	v 4 = 15
x 34	u 3+ v 4 = 18	u 3 = 3

Используя найденные значения потенциалов, для каждой небазисной переменной вычисляются величины u_i + v_j – c_ij. Найденные коэффициенты, совместно с нулевыми коэффициентами для базисных переменных, фактически являются коэффициентами строки целевой функции симплекс-таблицы.

Таблица 15.11

x 11

x 12

x 13

x 14

x 21

x 22

x 23

x 24

x 31

x 32

x 33

x 34

z

-16

-9

-9

Поскольку в транспортной задаче ищется минимум стоимости перевозок, в базис будет вводиться переменная, имеющая наибольший положительный коэффициент в z -строке. В данном случае это будет x ₃₁.

Описанные вычисления обычно выполняются непосредственно в транспортной таблице. В этом случае нет необходимости в явном виде выписывать уравнения для потенциалов. Вычисления в транспортной таблице начинаются с присвоения потенциалу u ₁ нулевого значения. Затем вычисляются v -потенциалы для всех столбцов, имеющих базисные переменные в первой строке. Далее на основании уравнения для потенциалов, соответствующего x ₂₂, определяются величины потенциала u ₂. Зная значения потенциала u ₂, вычисляем потенциалы v ₃ и v ₄, что позволяет найти потенциал u ₃. Поскольку все потенциалы определены, далее вычисляются величины u_i + v_j – c_ij для каждой небазисной переменной x_ij. Эти величины показаны в таблице 15.12 в левом нижнем углу ячеек транспортной таблицы.

Теперь необходимо определить переменную, включаемую в базис. Это делается следующим образом. Обозначим через θ количество груза, перевозимого по маршруту (3, 1), то есть x ₃₁ = θ. Максимально возможное значение θ определяется из следующих условий:

1) должны выполняться ограничения на спрос и предложение;

2) ни по какому маршруту не должны выполняться перевозки с отрицательным объёмом грузов.

Таблица 15.12

	v 1 = 10	v2 = 2	v 3 = 4	v 4 = 15
u 1 = 0			-16
u 2 = 5
u 3 = 3		-9	-9

Построим сначала замкнутый цикл, который начинается и заканчивается в ячейке (3, 1). Цикл состоит из последовательности горизонтальных и вертикальных отрезков (но не диагональных), соединяющих ячейки, соответствующие текущим базисным переменным, и ячейку, соответствующую вводимой переменной. Для любой вводимой переменной можно построить только один замкнутый цикл. Теперь можно найти значение θ. Для того, чтобы удовлетворить ограничениям по спросу и предложению, надо поочерёдно отнимать и прибавлять θ к значениям базисных переменных, расположенных в угловых ячейках цикла.

Таблица 15.13

	v 1 = 10	v2 = 2	v 3 = 4	v 4 = 15
u 1 = 0	5- θ	10+ θ	-16
u 2 = 5		5- θ		5+ θ
u 3 = 3	θ 9	-9	-9	10- θ

Из таблицы 15.13 видно, что наибольшее допустимое значение для θ равно 5, при этом переменные x ₁₁ и x ₂₂ обращаются в 0. Поскольку из базиса исключается только одна переменная, остановим свой выбор на x ₁₁. Теперь следует откорректировать значения базисных переменных, находящихся внутри цикла.

Теперь нужно снова повторить вычисление потенциалов, как показано в таблице 15.14. Новой переменной, вводимой в базис, будет x ₁₄. Цикл, соответствующий этой переменной, также показан в табл. 15.14.

Таблица 15.14

	v 1 = 1	v2 = 2	v 3 = 4	v 4 = 15
u 1 = 0	-9	15 - θ	-16	θ 4
u 2 = 5	-6	0 + θ		10- θ
u 3 = 3		-9	-9

В соответствии с таблицей 15.14, необходимо исключить переменную x ₂₄.

Окончательное решение приведено в таблице 15.15. Все коэффициенты перед переменными в целевой функции теперь отрицательные. Поэтому можно считать, что оптимальное решение найдено.

Таблица 15.15

	v 1 = -3	v2 = 2	v 3 = 4	v 4 = 11
u 1 = 0	-13		-16
u 2 = 5	-10			-4
u 3 = 7		-5	-5

Суммарная стоимость перевозок теперь составляет 435 долларов. Решение интерпретируется так: от элеватора 1 до мельницы 2 нужно отправить 5 зерновозов, от элеватора 1 до мельницы 4 – 10 зерновозов и т.д.