Алгоритм решения транспортной задачи методом потенциалов

Теоретический материал по транспортной задаче

Транспортная задача (задача Монжа – Канторовича) – математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.

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

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

где: Z – затраты на перевозку грузов;
X – объем груза;
C – стоимость (тариф) перевозки единицы груза;
A – запас поставщика;
B – запрос потребителя;
m – число поставщиков;
n – число потребителей.

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

Общая постановка транспортной задачи заключается в определении оптимального плана перевозок некоторого однородного груза из пунктов отправления A1, A2,…, Am в пункты назначения B1, B2,…, Bn. Критерий оптимальности берется минимальная стоимость перевозки или минимальное время доставки груза.

Рассмотрим транспортную задачу, где в качестве критерия оптимальности взята минимальная стоимость перевозок всего груза. Обозначим через Сij тарифы перевозки единицы груза из пункта отправления i в пункт назначения j. Обозначим через Ai запасы груза i-м пункте отправления, а через Bj потребности груза j-м пункте назначения, а через Xj количество единиц груза переводимого из пункта отправления i в пункт назначения j.

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

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

Определение 1. Любое неотрицательное решение Xij=∥xij∥ (i=1,..,mj=1,…,n) систем (1.2) и (1.3) называется допустимым планом транспортной задачи.

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

Если сумма груза у поставщиков равно общей сумме потребностей в пунктах назначения:

(1.5)

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

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

Соответствующие тарифы считаются равными нулю: ci n+1=0 (i=1,…,m). После этих преобразований получим закрытую модель транспортной задачи.

Аналогично, вводится фиктивный (m+1) пункт отправления с грузом, а тарифы полагаются равными нулю: cm+1j=0 (j=1,…,n). После этих преобразований получим закрытую модель транспортной задачи.

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

Число переменных Xij равно mn, где m число пунктов отправнения , а n число пунктов назначения. Число уравнений в (1.2) и (1.3) равно m+n. Так как мы рассматриваем закрытую модель транспортной задачи (выполняется равенство (1.5)), то число линейно независимых уравнений равно m+n−1. Следовательно опорный план транспортной задачи может иметь не более m+n−1 отличных от нуля неизвестных.

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

Для решения транспортной задачи сначала определяется начальный опорный план, а затем определяется оптимальный план путем улучшения текущего опорного плана.

Для определения начального опорного плана существует несколько методов. Мы рассмоьтрим три метода. Метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля.

Незамкнутые задачи

Задача замкнута, если сумма производств равна сумме потребления.

Обычно в постановке сумма производства больше суммы потребления. Для решения незамкнутых задач, а также для простоты получения начального базисного плана используется метод искусственного базиса [4]. Для этого исходный граф расширяется, вводится «свалка» — дополнительный пункт, на который свозится все лишнее производство за нулевую цену.

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

Дуги на свалку от пунктов производства соответствуют дополнительным переменным в симплекс-методе, а дуги со свалки к пунктам потребления соответствуют искусственным переменным.

Пример №3. Решение транспортной задачи линейного программирования. Метод наименьшей стоимости (фиктивный потребитель)

Данное решение является образцом работы программы, представленной на сайте.
Пример №1. Транспортная задача. Метод наименьшей стоимости (сбалансированная задача)
Пример №2. Транспортная задача. Метод наименьшей стоимости (фиктивный поставщик)
Пример №4. Транспортная задача. Метод северо-западного угла (сбалансированная задача)
Пример №5. Транспортная задача. Метод северо-западного угла (фиктивный поставщик)
Пример №6. Транспортная задача. Метод северо-западного угла (фиктивный потребитель)

Задача:
Стоимость доставки единицы продукции от поставщика к потребителю располагается в правом нижнем углу ячейки.
Поставщик Потребитель Запас
B 1 B 2 B 3
A 1
3
5
4
20
A 2
6
3
1
40
A 3
3
2
7
30
Потребность 30 35 20
Требуется составить план перевозок, при котором общая стоимость доставки продукции будет наименьшей.
Решение:
Для решения задачи необходимо выполнение следующего условия:
cуммарные запасы продукции у поставщиков должны равняться суммарной потребности потребителей.

Проверим.
Запасы поставщиков: 20 + 40 + 30 = 90 единиц продукции.
Потребность потребителей: 30 + 35 + 20 = 85 единиц продукции.
Разница в 5 единиц продукции.
Введем в рассмотрение фиктивного потребителя B4, с потребностью 5 единиц продукции.
Стоимость доставки единицы продукции от всех поставщиков к потребителю B4 примем равной нулю (см. таблицу ниже).
Теперь суммарные запасы продукции у поставщиков равны суммарной потребности потребителей.
Для решения задачи необходимо выполнение следующего условия:
количество задействованных маршрутов = количество поставщиков + количество потребителей – 1.

Поэтому если возникнет ситуация, в которой будет необходимо исключить столбец и строку одновременно, мы исключим что-то одно.
В первую очередь, будем задействовать маршруты с наименьшей стоимостью доставки.
Маршруты доставки продукции от поставщиков к фиктивному потребителю B4 будем рассматривать в последнюю очередь.
Возможно, это позволит получить меньшую стоимость доставки продукции для начального решения.
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4
A 1
3
5
4
0
20
A 2
6
3
?
1
0
40
A 3
3
2
7
0
30
Потребность 30 35 20 5
20 = min { 20, 40 }
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4
A 1
3
5
4
0
20
A 2
6
3
20
1
0
40 20
A 3
3
?
2
7
0
30
Потребность 30 35 20
нет
5
30 = min { 35, 30 }
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4
A 1
?
3
5
4
0
20
A 2
6
3
20
1
0
40 20
A 3
3
30
2
7
0
30 нет
Потребность 30 35
5
20
нет
5
20 = min { 30, 20 }
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4
A 1
20
3
5
4
0
20 нет
A 2
6
?
3
20
1
0
40 20
A 3
3
30
2
7
0
30 нет
Потребность 30
10
35
5
20
нет
5
5 = min { 5, 20 }
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4
A 1
20
3
5
4
0
20 нет
A 2
?
6
5
3
20
1
0
40 20 15
A 3
3
30
2
7
0
30 нет
Потребность 30
10
35
5
нет
20
нет
5
10 = min { 10, 15 }
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4
A 1
20
3
5
4
0
20 нет
A 2
10
6
5
3
20
1
?
0
40 20 15 5
A 3
3
30
2
7
0
30 нет
Потребность 30
10
нет
35
5
нет
20
нет
5
5 = min { 5, 5 }
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4
A 1
20
3
5
4
0
20 нет
A 2
10
6
5
3
20
1
5
0
40 20 15 5 нет
A 3
3
30
2
7
0
30 нет
Потребность 30
10
нет
35
5
нет
20
нет
5
нет
Стоимость доставки продукции, для начального решения, не сложно посчитать.

Определение опорного плана. Предварительные сведения

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

В первом случае временно исключаем из рассмотрения столбец j и изменяем запас груза пункта отправления i. Во втором случае временно исключаем из рассматрения строку i и изменяем потребность груза пункта назначения j. Далее повторяем процедуру с таблицей условий с исключенной строкой или столбцом.

В m+n−1-ом шаге получаем задачу с одним пунктом отправления и одним пунктом назначения. Остается свободной одна клетка. Запасы оставшегося пункта отправления будут равны потребностям пункта назначения. Заполнив эту клетку заканчиваем m+n−1-ый шаг и получаем опорный план.

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

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

При нахождении опорного плана транспортной задачи методом северно-западного угла, заполнене клеток таблицы условий начинают с верхней левой клетки K11 поэтому метод и называется “метод северно западного угла”).

Рассмотрим метод на конкретном примере.

Пример 1. На три базы A1, A2, A3 поступил очередной груз в количествах равных 140, 160, 120 ед. Этот груз требуется перевезти в четыре пунктов назначения B1, B2, B3, B4 в количествах 150, 90, 100, 80. Тарифы перевозок представлена матрицей

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

Решение. Запишем все данные в таблицу условий:

Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+4−1=6 заполненых клетках таблицы.

Наличие груза у поставщиков равно: ∑Ai=140+160+120=420.

Общая потребность в грузе в пунктах назначения равна: ∑Bj=150+90+100+80=420.

Ai=∑Bj. Модель транспортной задачи является закрытой. Следовательно она разрешима.

Найдем опорный план задачи методом северно-западного угла.

A1B1. Следовательно в клетку (A1, B1 ) помещаем число min(A1, B1)=140. Запасы пункта A1 полностью исчерпаны. Поэтому исключаем из рассмотрения строку A1 и будем считать потребности пункта B1 равными 150−140=10.

A2>B1. Следовательно в клетку (A2, B1) помещаем число min(A2, B1)=10. Потребности пункта B1 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B1 и будем считать запасы пункта A2 равными 160−10=150.

При этом плане стоимость перевозок вычисляется так:

F=2·140+8·10+4·90+ 1·60+3·40+6·80=1380.

Метод минимального элемента

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

Рассмотрим метод минимального элемента на примере.

Пример 2. Найти опорный план транспортной задачи представленной в таблице условий ниже методом минимального элемента.

Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+4−1=6 заполненых клетках таблицы. Тарифы перевозок единицы груза из кажного пункта отправления во все пункты назначения задаются матрицей.

Общая потребность в грузе в пунктах назначения равна: .

 Модель транспортной задачи является закрытой. Следовательно она разрешима.

Минимальный тариф равный 1 находится в клетке (A1, B3). Поэтому заполняем эту клетку.

A1>B3. Следовательно в клетку (A1, B3) помещаем число 70. Потребности пункта B3 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B3 и будем считать запасы пункта A1 равными 150−70=80.

Минимальный тариф равный 1 находится в клетке (A2, B4). Поэтому заполняем эту клетку.

A2>B4. Следовательно в клетку (A2, B4) помещаем число 40. Потребности пункта B4 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B4 и будем считать запасы пункта A2 равными 100−40=60.

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

1. Выберем какую-либо вершину i.

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

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

Несколько замечаний об эффективности алгоритма[править | править код]

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

Для уменьшения времени на проверку оптимальности применяется несколько приемов.

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

2. Циклический просмотр — перебор начинается с того места, на котором остановились в предыдущем просмотре.

3. Выбор «претендентов» — при просмотре выбирается не одна дуга, а несколько. На следующем шаге проверяются только отобранные дуги.

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

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

Транспортная задача задается следующей таблицей:

Что означают числа в условии транспортной задачи?

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

Это наши “склады” – пункты отправления: два склада с товаром: А1 и А2

Это объем товара – количество груза, соответственно на складах А1 и А2:

Далее имеем дело с пунктами назначения – с “магазинами”. В нашем случае их 4 штуки: В1, В2, В3 и В4.

И соответственно потребности каждого из магазинов – потребности пунктов назначения:

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

Например, для перевозки 1 единицы груза из пункта отправления (“склада”) А2 в пункт назначения (“магазин”) В3 надо заплатить 4 условные единицы стоимости, например 4 руб.

Аналогично, мы заплатим 6 рублей за перевозку 1 единицы груза из “склада” А1 в “магазин” В4.

Или та же самая задача может быть задана сразу в более понятном виде:

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

Рассмотрим самый распространенный метод получения опорного плана – метод северо-западного угла.

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

Перед тем, как распределять ресурсы по “магазинам”, проверим, равны ли общие потребности имеющимся ресурсам?

Потребности: 50 + 100 + 75 + 75 = 300

Ресурсы: 100 + 200 = 300

Потребности = Ресурсам

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

Начнем нахождение опорного решения:

Заполним клетку (1;1).

В магазин В1 требуется 50 единиц товара. Со склада А1 отправим в этот магазин 50 единиц.

Потребности магазина В1 выполнены, следовательно, нет необходимости везти туда груз со склада А2.

На складе А1 еще осталось 50 единиц груза. Эти остатки можем направить в магазин В2. Ресурсы склада А1 исчерпаны.

Переходим к складу А2.

Так как потребности магазина В1 выполнены полностью, рассмотрим магазин В2, которому требуется 100-50=50 единиц товара. Направим их туда.

Заметим, на складе А2 осталось еще 200-50=150 единиц груза, которые мы распределим по магазинам В3 и В4, полностью удовлетворяя и их потребности.

Склады пусты!

Потребности магазинов в товаре полностью выполнены!

Получен опорный (первоначальный) план транспортной задачи.

Рассмотрели северо-западный метод построения первоначального плана (опорного решения).

Метод минимальных стоимостей получения опорного плана

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

Направляем 100 единиц груза из склада А2 в магазин В2.

Остатки на складе А2 — 100 единиц. Потребности магазина В2 выполнены.

Груз со склада А2 отправим в магазин, у которого стоимость перевозки ниже — магазин В3, так как мин(4;7)=4

Размер поставки равен потребности магазина — 75. Остатки со склада 200-100-75=25 перенесем в магазин В4.

Остается только раскидать груз со склада А1 по магазинам: В1 — 50 единиц, В4 — 75-25=50 единиц.

Получили два опорных плана: методом северо-западного угла и методом минимальных стоимостей.

Первый опорный план (по методу северо-западного угла):

Второй опорный план (по методу минимальных стоимостей):

Источники


  • http://galyautdinov.ru/post/transportnaya-zadacha
  • https://matworld.ru/linear-programming/transportnaya-zadacha.php
  • https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BF%D0%BE%D1%82%D0%B5%D0%BD%D1%86%D0%B8%D0%B0%D0%BB%D0%BE%D0%B2
  • http://reshmat.ru/example_transport_3.html
  • http://matecos.ru/mat/matematika/kak-reshit-transportnuyu-zadachu-2.html

Рейтинг
( Пока оценок нет )
Понравилась статья? Поделиться с друзьями:
Все об Экселе: формулы, полезные советы и решения