Математическая постановка задачи

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления (склады) в n пунктов назначения (потребители). При этом в качестве критерия оптимальности обычно принимается минимальная суммарная стоимость перевозок всего запаса грузов ко всем потребителям (либо минимальное время его доставки). Рассмотрим первый вид постановки задачи.

Обозначим через c_ij тарифы перевозки единицы груза из i – го пункта отправления в j – й пункт назначения (рис. 9 а), через a_i – запасы груза в i – ом пункте отправления, через b_j - потребность в грузе в j – ом пункте назначения, а через x_ij – количество единиц груза, перевозимого из i – го пункта отправления в j – й пункт назначения (рис. 9b).

Рис.9. К обоснованию математической модели транспортной задачи

Тогда математическая постановка задачи состоит в определении минимального значения функции

или → min (i=1…m; j=1…n) (20)

при условиях ,

,

……………………………

или (j=1…n), (21)

а также ,

,

…………………………..

,

или , (i=1…m), (22)

.

О п р е д е л е н и е 1. Всякое неотрицательное решение систем линейных уравнений (21) и (22), определяемое матрицей (i=1…m; j=1…n), называется планом транспортной задачи.

О п р е д е л е н и е 2. План (i=1…m; j=1…n), при котором функция (20) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записывают в табличной форме (табл.15).

Таблица 15

Форма записи условий транспортной задачи

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

, (23)

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

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

В случае, если запас превышает потребность, т.е.

,

то вводится фиктивный (n+1) –й пункт назначения с потребностью

а соответствующие тарифы считаются равными нулю с_in+1=0 (i=1…m). Аналогично, если запасы меньше потребностей, вводится фиктивный (m+1) –й пункт отправления с запасом груза

и тарифы полагаются равными нулю c_m+1=0 (j=1…n). Так открытая задача сводится к закрытой транспортной задаче.

Как и в производстенной ЗЛП, в транспортной задаче существует множество опорных планов и один из них - оптимальный.

Решение транспортной задачи имеет свои особенности:

- решение задачи начинают с нахождения одного из опорных планов; его

нахождение – самостоятельная проблемная задача (см. ниже);

- план должен быть оценен на предмет подтверждения его оптимальности;

- количество базисных (ненулевых) переменных в опорном плане должно

быть равно (n+m-1). Такой план называется невырожденным. Если их

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

лежит, или его надо преобразовать в невырожденный (см. ниже).

Нахождение опорного плана транспортной задачи

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

Метод северо-западного угла. На примере конкретной задачи продемонстрируем этот метод нахождения опорного плана.

З а д а ч а 12. На три базы А₁, А_2, А₃ поступил однородный груз в количествах, соответственно равных 140, 180, 160 ед. Этот груз требуется перевезти в пять пунктов назначения В₁, В₂, В₃, В₄, В₅ соответственно в количествах 60, 70, 120, 130, 100 ед. Тарифы перевозок единичного количества груза с каждого из складов в соответствующие пункты назначения указаны в табл.16. Найти план перевозок данной транспортной задачи методом северо-западного угла.

Таблица 16

Структурная запись задачи

Р е ш е н и е. Введем понятие маршрута – наименование клетки А_iB_j, где i – порядковый номер поставщика, j – порядковый номер потребителя.

Задача является закрытой, так как количество имеющегося у поставщиков грузов равно объему грузов, запрашиваемых потребителями. Здесь число пунктов отправления m=3, а число пунктов назначения n=5. Следовательно, невырожденный опорный план задачи будет определяться числом заполненных маршрутов (ненулевых переменных) в количестве 5+3-1=7.

По рассматриваемому методу заполнение маршрутов начнем с клетки, стоящей в левом верхнем углу. Потребность в грузе пункта В₁ составляет 60 ед и от поставщика А₁ можно эту потребность полностью удовлетворить. Иначе, по маршруту А₁В₁ будет запланирована поставка в размере 60 ед. Следующий потребитель В₂ нуждается в поставке 70 ед груза, что также можно выполнить, доставив требуемый объем груза от поставщика А₁, у которого после первой поставки осталось 140-60=80 ед. Таким образом, по маршруту А₁В₂ можно запланировать доставку груза в полном объеме. Оставшийся у поставщика А₁ объем груза в 10 ед запланируем доставить потребителю В₃,

т.е. по маршруту А₁В₃. Так как ресурсы поставщика А₁ полностью израсходованы, потребителю В₂ оставшиеся 110 ед груза запланируем доставить по маршруту А₂В₃ , т.е. от поставщика А₂. Пользуясь подобным алгоритмом, по маршруту А₂В₄ запланируем доставку 70 ед, по маршруту А₃В₄ доставку 60 ед и по маршруту А₃В₅ оставшиеся 100 ед груза (табл.17).

Таблица 17

Результирующая таблица опорного плана задачи 12

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

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

.

План имеет 7 заполненных маршрутов. Следовательно, полученный опорный план невырожденный, может быть проанализирован на оптимальность и при необходимости улучшен (см. ниже).

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

З а д а ч а 13. Повторим процедуру нахождения первичного опорного плана для сформулированной выше задачи, реализуя этот метод.

В общем наборе тарифов есть два маршрута со ставкой «1» и три маршрута со ставкой «2», два маршрута со ставкой «3», четыре маршрута со ставкой «4», два маршрута со ставкой «7», по одному маршруту со ставками «8» и «9». В такой же последовательности будем перераспределять груз. При равенстве тарифов маршрут выбирают произвольно.

Начнем с маршрута А₂В₅. Назначим объем перевозок по нему 100 ед, а по маршруту А₂В₃ оставшиеся у поставщика А₂ 80 ед груза. Естественно, маршруты А₁В₅ и А₃В₅, а также А₂В₁, А₂В₂, А₂В₄ должны быть выключены из списка свободных (знак Х). Теперь заполним маршрут А₁В₁ , назначив по нему перевозку груза в объеме 60 ед (таков запрос потребителя В₁) и выведем из состава свободных маршрут А₃В₁. Следующим заполняем маршрут А₁В₄ количеством груза в объеме 80 ед (оставшиеся у поставщика А₁ после заполнения маршрута А₁В₁). Соответственно исключаем маршруты А₁В₂, А₁В₃. Оставшиеся маршруты закрываем безвариантно (табл.18).

Таблица 18

Заполнение таблицы при методе минимального элемента

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

,

для которого функция цели принимает значение

.

Полученный план имеет 7 заполненных маршрутов, поэтому план невырожденный и может быть в дальнейшем улучшен (если при первом шаге начать составление плана с маршрута А₂В₃, то получим план со значением функции цели F=1480).

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

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

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

Таблица 19

Нахождение опорного плана по Фогелю

В таблице соблюдался следующий порядок заполнения маршрутов: А₁В₁, А₂В₃, А₃В₅, А₁В₄, А₂В₂, А₃В₂, А₃В₄. Максимальные разности по столбцам и строкам выделены жирным шрифтом.

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

,

т.е. опорный план имеет 7 заполненных маршрутов, а, следовательно, он невырожденный. Функция цели принимает значение:

.

Очевидно, наилучший опорный план получен по методу Фогеля, но и он может быть в дальнейшем улучшен (см. ниже).

Оценка опорного плана транспортной задачи на оптимальность

и нахождение очередного плана

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

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

Т е о р е м а. Если для некоторого опорного плана , (i=1…m; j=1…n) транспортной задачи для каждого базисного маршрута существуют такие числа α₁, α₂, …, α_m; β₁, β₂, …, β_n, при которых

при х_ij >0

и при

для всех i=1…m и j=1…n, тогда - оптимальный план задачи.

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

Сформулированная теорема позволяет построить алгоритм нахождения решения транспортной задачи. Он состоит в следующем.

Пусть одним из ранее рассмотренных методов найден опорный план. Следует предположение, что полученный план оптимален. Тогда для каждого из закрытых маршрутов можно определить потенциалы α_i и β_j (i=1…m, j=1…n). Эти числа находят, решая систему уравнений (полагаем, что х_ij >0):

, (24)

где с_ij – тариф соответствующего маршрута.

Так как количество определенных (базисных) маршрутов (n+m-1), а число неизвестных α,β равно (n+m), т.е. на единицу больше, то одно из неизвестных (обычно α₁ или β₁ ) приравнивают нулю, тогда легко считаются остальные по заполненным маршрутам опорного плана. После нахождения α_i и β_j для всех свободных маршрутов определяют числа

. (25)

Если среди этих чисел нет положительных (хотя бы одного), то такой план считается оптимальным. В противном случае предположение относительно оптимальности анализируемого плана недействительно и его можно улучшить. Маршруты-претенденты на включение в базис будут иметь ∆_ij >0. Но перевести в базис можно только один маршрут, для которого ∆_ij>0 и max.

Заполнение такого маршрута неизбежно повлечет за собой изменение объемов поставок по другим маршрутам (естественно, так как любой опорный план всегда сбалансирован). Эта процедура выполняется на базе графического алгоритма, называемого циклом.

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

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

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

1. Считая первым тот маршрут, который вносится в базис, присвоить ему знак «+» и далее, перемещаясь по циклу, следующему маршруту присваивается знак «-», далее опять знак «+» и так далее, т.е. всем нечетным маршрутам присваивается знак «+», а нечетным – знак «-» (только по концам линий цикла).

2. Среди маршрутов со знаком «-» выбирают маршрут с минимальным объемом перевозки.

3. По маршрутам со знаком «+» прибавляют вышеуказанный минимум грузоперевозки, а по маршрутам со знаком «-» это число отнимают. В результате получают очередной (также сбалансированный) опорный план.

4. Проверяют новый опорный план на оптимальность.

На рис.10 представлены некоторые варианты схем циклов при формировании очередного опорного плана транспортной задачи.

Рис. 10. Варианты схем циклов

З а д а ч а 15. В качестве примера проанализируем опорный план выше рассмотренной задачи, полученный методом северо-западного угла. Для этого составим таблицу 20, где взамен обозначений поставщика А_i и потребителя B_j вписаны обозначения потенциалов α_i и β_j.

Таблица 20

Расчет потенциалов

	β1 = 2	β2 = 3	β3 = 4	β4 = 7	β5 = 2
α1 = 0
α2 = 3
α3 = 0

Первоначально рассчитаем потенциалы, воспользовавшись заполненными маршрутами. Составим систему из семи уравнений типа (24):

; ; ;

; ; .

;

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

; ; ; ; ;

; ; .

Полученные значения потенциалов внесем в табл.20. Теперь для каждого свободного маршрута рассчитаем значения ∆_ij, согласно уравнения (25) и впишем их в таблицу (в квадратных скобках). Видим, что ∆_ij>0 по двум маршрутам: А₁В₄ (∆_ij=+5) и А₃В₃ (∆_ij=+1). По всем остальным маршрутам этот параметр отрицательный. Очевидно, что маршрут А₁В₄ должен быть переведен из свободных в базисные.

Строим цикл. Он пройдет через следующие узловые маршруты:

А₁В₄→А₂В₄→А₂В₃→А₁В₃→А₁В₄.

Это единственный вариант построения ломаной, у которой в вершинах находятся заполненные (базисные) маршруты. Соответственно маршруты приобретают знаки:

А₁В₄→(+); А₂В₄→(-); А₂В₃→(+); А₁В₃→(-).

В цикле надо перемещать минимальное число, соответствующее транспортируемому грузу по маршруту со знаком «минус». Таковым будет число 10 по маршруту А₁В₃. Получим новый опорный план, представленный в табл.21.

Таблица 21

Первый улучшенный план

	β1 = 2	β2 = 3	β3 = -1	β4 = 2	β5 = -3
α1 = 0
α2 = -2
α3 = -5

Повторим относительно и этого плана описанные выше процедуры, получим значения потенциалов по всем маршрутам и видим, что и этот план неоптимален, так как имеет три маршрута с положительными потенциалами, равными (+1). С целью его улучшения введем в базис маршрут А₃В₃ (у него минимальная тарифная ставка) и строим цикл:

А₃В₃→А₃В₄→А₂В₄→А₂В₃→А₃В₃.

С учетом знаков по маршрутам объем перемещаемого по узловым точкам цикла груза в объеме 60 ед получаем очередной опорный план (табл.22).

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

Таблица 22

Второй улучшенный план

	β1 = 2	β2 = 3	β3 = -1	β4 = 2	β5 = -2
α1 = 0
α2 = -2
α3 = -4

за план, перемещаемый в базис, и построив от него цикл

А₂В₂→А₂В₄→А₁В₄→А₁В₂→А₂В₂

с объемом перемещаемого груза в 70 ед, получим третий улучшенный опорный план, который представлен в табл.23.

Таблица 23

Третий улучшенный план

	β1 = 2	β2 = 2	β3 = -1	β4 = 2	β5 = -2
α1 = 0
α2 = -2
α3 = -4

Этот план по всем незаполненным маршрутам имеет только отрицательные потенциалы. Следовательно, он оптимальный:

.

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

; ; ; ,

т.е. по сравнению с первоначальным вариантом оптимальный план улучшен примерно на 15%. Для этого выполнены четыре итерационных цикла оптимизации.