Тема 1.4 транспортная задача.

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления  в п пунктов назначения  . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через  тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через  – запасы груза в i-м пункте отправления, через  –потребности в грузе в j–м пункте назначения, а через  – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

(56)

при условиях

(57)

(58)

(59)

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

Определение 1.15 Всякое неотрицательное решение систем линейных уравнений (57) и (58), определяемое матрицей  , называется планом транспортной задачи.

Определение 1.16 План  , при котором функция (56) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записывают в виде таблицы 21.

Таблица 21

Очевидно, общее наличие груза у поставщиков равно  , а общая потребность в грузе в пунктах назначения равна  единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е.

(60)

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

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

В случае превышения запаса над потребностью, т. е.  вводится фиктивный (n+1)–й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю:  Полученная задача является транспортной задачей, для которой выполняется равенство (60).

Аналогично, при  вводится фиктивный (m+1)–й пункт отправления с запасом груза  и тарифы полагаются равными нулю:  Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. В дальнейшем будем рассматривать закрытую модель транспортной задачи. Если же модель конкретной задачи является открытой, то, исходя из сказанного выше, перепишем таблицу условий задачи так, чтобы выполнялось равенство (60).

Число переменных  в транспортной задаче с т пунктами отправления и п пунктами назначения равно пт, а число уравнений в системах (57) и (58) равно п+т. Так как мы предполагаем, что выполняется условие (60), то число линейно независимых уравнений равно п+т–1. Следовательно, опорный план транспортной задачи может иметь не более п+т–1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности п+т–1, то план является невырожденным, а если меньше – то вырожденным.

Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.

Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы.

Пример.

Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Решение. Обозначим через  количество единиц сырья, перевозимого из i–го пункта его получения на j–е предприятие. Тогда условия доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств:

(61)

При данном плане  перевозок общая стоимость перевозок составит

(62)

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

Определение опорного плана транспортной задачи.

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

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

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

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

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

Метод аппроксимации Фогеля. При определении опорного плана транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают максимальную. В строке или столбце, которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.

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

Определение оптимального плана транспортной задачи. Для определения оптимального плана транспортной задачи разработано несколько методов. Наиболее часто используются метод потенциалов и метод дифференциальных рент.

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

Теорема 1.14. Если для некоторого опорного плана транспортной задачи существуют такие числа α₁, α₂,…, α_m и β₁, β₂,…, β_n, что

и , то - оптимальный план транспортной задачи.

Определение 1.17. Числа α_i и β_j называются потенциалами соответственно пунктов назначения и пунктов потребления.

Алгоритм нахождения решения транспортной задачи состоит в следующем. Пусть одним из методов найден опорный план транспортной задачи. Для каждого из пунктов назначения и отправления определяют потенциалы α_i и β_j. Эти числа находят из системы уравнений , где - тарифы, стоящие в заполненных клетках таблицы условий транспортной задачи.

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

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

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

Если ломаная линия, образующая цикл, пересекается то точки самопересечения не являются вершинами.

Примеры циклов.

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

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

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

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

Пример.

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

Пункты отправления	Пункты назначения				Запасы
	В1	В2	В3	В4
А1	1	2	4	1	50
А2	2	3	1	5	30
А3	3	2	4	4	10
Потребности	30	30	10	20

Найдем опорный план всеми рассмотренными способами.

Метод северо-западного угла.

Пункты отправления	Пункты назначения				Запасы
	В1	В2	В3	В4
А1	1 30	2 20	4	1	50
А2	2	3 10	1 10	5 10	30
А3	3	2	4	4 10	10
Потребности	30	30	10	20

S=1*30+2*20+3*10+1*10+5*10+4*10=200

Метод минимальной стоимости.

Пункты отправления	Пункты назначения				Запасы
	В1	В2	В3	В4
А1	1 30	2 10	4	1 10	50
А2	2	3 20	1	5 10	30
А3	3	2	4 10	4	10
Потребности	30	30	10	20

S=1*30+2*10+1*10+3*20+5*10+4*10=210

Метод аппроксимации Фогеля

Пункты отправления	Пункты назначения				Запасы
	В1	В2	В3	В4
А1	1 30	2	4 10	1 10	50	1		1		1		-
А2	2	3 20	1	5 10	30	1		1		1		2
А3	3	2 10	4	4	10	1		1		1		2
Потребности	30	30	10	20
	1	1	3	3
	1	1	-	3
	1	1	-	-
	-	1	-	-

S=1*30+4*10+1*10+3*20+5*10+2*10=210

Основываясь на опорном плане, найденного методом северо-западного угла, проверим его на оптимальность.

Составим систему уравнений

Полагая α₁=0, получим β₁= 1, β₂=2, β₃=0, β₄=4, α₃=0, α₂=-1. Для каждой свободной клетки вычисляем . Имеем . План не явлется оптимальным.

Пункты отправления	Пункты назначения				Запасы
	В1	В2	В3	В4
А1	1 30	2 - 20	4 -4	1 + 3	50
А2	2 0	3 + 10	1 10	5 - 10	30
А3	3 -2	2 0	4 -4	4 10	10
Потребности	30	30	10	20

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

Следующие этапы проводим аналогично.