Как решить транспортную задачу?

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

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

Определение:

Транспортная задача - это математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов с минимизацией затрат на перемещение.

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

Ну, начнем! Далее Вводная часть, с которой желательно ознакомиться.

Вводная часть, с которой желательно ознакомиться

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

  • решение транспортной задачи методом потенциалов (рассмотрен в данной статье)
  • решение транспортной задачи с использованием симплекс метода.

Решение задачи методом потенциалов происходит в несколько этапов:

  1. Определение опорного решения.
  2. Применение к найденному опорному решению самого метода потенциалов.
  3. Проверка единственности решения.

Определение опорного плана, в свою очередь, можно выполнить несколькими способами. Мы рассмотрим два из них:

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

(не путать с методами решения самой транспортной задачи!!!)

О чем говорится в определении транспортной задачи?

У нас есть некоторый груз, который находится на складах: склад 1, склад 2, ..., склад  - это пункты отправления.

Этот груз нам необходимо развести по магазинам: магазин 1, магазин 2, ..., магазин k - это пункты назначения.

Нам выгоднее как можно эффективнее выполнить работу, т.е. найти такой вариант перевозки, при котором затраты будут минимальными.

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

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

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

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

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

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

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

пункты отправления

 

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

объем в пунктах назначения

 

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

пункты назначения

 

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

потребности пунктов назначения 

 

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

матрица стоимостей 

 

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

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

 

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

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

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

Trasnportnay 2 

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

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

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

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

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

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

подсчет общих потребностей

Потребности:  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 единиц.

метод минимальных стоимостей

 

 

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

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

опорный план транспортной задачи

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

опорный план

Далее проверим правильность вычисления первоначального плана.

Проверка правильности вычисления первоначального плана

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

Правило: 

Количество заполненных клеток (базисных клеток) в первоначальном плане ВСЕГДА должно быть равно m + n - 1, где m - количество строк, n - количество столбцов

В нашем случае условие выполняется: 2 + 4 - 1 = 5

Что же делать, если количество заполненных ячеек меньше необходимого?

Подробно об этом с разбором примеров в статье Вырожденность опорного плана транспортной задачи. Как избавиться?

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

проверка первоначального плана

100 = 50 + 50

200 = 100 + 75 + 25

По столбцам:

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

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

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

Далее применим метод потенциалов к обоим опорным планам и сравним получившиеся ответы.

 

Метод потенциалов решения транспортной задачи - шаг 1.

 

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

Выпишем матрицу стоимостей, данную в условии задачи.

матрица стоимостей     матрица стоимостей

 

Далее строим рядом две таблицы. Размерность таблиц как и в матрице стоимостей:

количество строк = количеству складов, количество столбцов = количеству магазинов. 

Заполняем первую — левую таблицу в соответствии с полученным опорным планом.

проверка на оптимальность 

Переходим в правую таблицу.

Переносим из матрицы стоимостей значения, которые соответствуют занятым клеткам левой таблицы.

В матрице стоимости эти значения подчеркнуты. 

заполняем промежуточные таблицы 

Припишем каждой строке правой таблице потенциалы u1, u2. Каждому столбцу — потенциалы v1, v2, v3, v4.

потенциалы

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

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

Составим систему уравнений по следующему правилу: 

Каждое из значений в ячейке (правая таблица) равно сумме потенциалов соответствующей строки и соответствующего столбца. 

Например: значение 4 находится в 1-й строке и 1-м столбце. Тогда сумма потенциалов 1-й строки (u1) и 1-ого столбца(v1) равна 4.

правило составления системы 

Первое уравнение системы: u1 + v1 = 4 

Рассмотрим следующее значение таблицы.  

Значение 3 находится в первой строке (потенциал u1), втором столбце (потенциал v2). 

проверка оптимальность

Второе уравнение системы: u1 + v2 = 3

Аналогично для каждого значения таблицы составим уравнение.

Получим систему уравнений:

potenzial 6

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

Для удобства в качестве этого потенциала всегда будем брать v4

один из потенциалов примем равным нулю 

Тогда система уравнений будет выглядеть: 

potenzial 8 

Решим систему уравнений и получим значения потенциалов:

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

Наглядно:

потенциалы 

Так как система очень проста, то значения потенциалов можно получить и устно. 

Покажем подробно:

нахождение потенциалов без системы 

Сумма отмеченных потенциалов равна 7, следовательно, потенциал u2 = 7

нахождение потенциалов далее

Значение 4 базисной ячейки находится во 2-й строке, 3-м столбце, тогда рассмотрим сумму соответствующих потенциалов.

v3 + 7 = 4 откуда v3 = -3

Далее все аналогично:

нахождение потенциалов

Значение 2 равно сумме потенциалов 2-й строки и 2-го столбца:

2 = v2 + 7 откуда v2 = -5

определение потенциалов транспортной задачи

u1 - 5 = 3, откуда u1 = 8

нахождение потенциалов 

v1 + 8 = 4, откуда v1 = -4 

В итоге получили:

потенциалы транспортной задачи 

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

Свободные ячейки подчиняются тому же правилу суммирования потенциалов.

заполняем свободные ячейки

Вычислим оценочную матрицу, по которой узнаем, оптимален ли рассматриваемый план.

Из каждого элемента матрицы стоимостей вычтем соответствующий элемент правой таблицы: 

potenzial 01  —  определение оценочной матрицы транспортной задачи  =  оценочная матрица

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

Критерий оптимальности:

если в оценочной матрице нет отрицательных элементов, то решение оптимально, в противном случае решение не оптимально. 

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

не оптимальность решения опорного плана

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

сводная таблица

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

Для перехода к следующему опорному решению выполним следующее (построим цикл пересчета):

- найдем среди отрицательных значений оценочной матрицы максимальный по модулю (или по другому, минимальный среди отрицательных) 

- в соответствующей ячейке левой таблицы ставим знак " + "

 

В нашем примере наименьшее отрицательное значение -2.

Знак " + " ставим в ячейке 1-й строки, 4-го столбца левой таблицы - ячейка соответствующая значению (-2).

создаем цикл пересчета

Необходимо расставить чередующиеся значения "+ " и " — " в левой таблице так, чтобы получился замкнутый цикл и выполнялись правила:

- остальные знаки цикла (все кроме уже поставленного первого " + ") ставим только в заполненных (базисных) ячейках таблицы,

- если в строке есть "плюс" ("минус"), то в этой строке должен быть и "минус" ("плюс"),

- если в столбце есть " плюс" ("минус"), то в этом столбце должен быть и "минус" ("плюс").

 

Применим к нашей таблице:

В столбце В4 есть "плюс", следовательно в этом столбце должен быть и "минус". 

расстановка знаков в цикле пересчета 

Аналогично, в строке А2 есть "минус", следовательно должен быть и "плюс". 

Если мы поставим этот "плюс" в столбце В3, то цепочка порвется, так как в этом же столбце невозможно поставить "минус" — нет заполненной ячейки. 

Ставим " + " в столбце В2 и продолжаем чередовать знаки. 

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

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

 

Далее обратимся к ячейкам, содержащим "минусы". Среди значений этих ячеек найдем минимальное:  Δ = мин {50;75} = 50 

К  "плюсам" прибавим найденное Δ = 50, в ячейках с "минусами" — вычтем Δ = 50.

Ячейка, в которой находилось значение  Δ = 50 останется пустой. В ячейке в которой мы поставили первый плюс появится значение, равное Δ = 50.

Общее количество заполненных (базисных) ячеек при пересчете не должно изменится! 

Получили следующий опорный план: 

опорный план 

Вычислим стоимость перевозки на первом шаге.

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

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

S1 = 50 · 4 + 100 · 2 + 75 · 4 + 25 · 7 + 50 · 6 = 1275 

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

опорный план 

Общая стоимость перевозки S1 = 1275

Метод потенциалов — шаг 2

Алгоритм проверки плана на оптимальность и построение цикла пересчета очень подробно расписан в шаге 1. 

Далее решение задачи будем излагать менее детально.

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

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

Вычисляем потенциалы строк и столбцов:

нахождение потенциалов опорного плана

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

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

Вычисляем оценочные значения в свободных ячейках.

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

проверка на оптимальность опорного плана

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

Получили оптимальный план. Итоговая стоимость перевозки S1 = 1275

 

 

Примеры решения транспортных задач:

Закрытая транспортная задача размерностью 2х2

Закрытая транспортная задача размерностью 3х4

Закрытая транспортная задача размерностью 2х3

Закрытая транспортная задача размерностью 4х5