Пример решения транспортной задачи: оптимальный план перевозок
Транспортная задача является важным инструментом оптимизации логистики и позволяет минимизировать затраты на перевозки при условии удовлетворения спроса. Давайте разберем на конкретных примерах основные методы нахождения оптимального плана перевозок.
1. Постановка транспортной задачи
Транспортная задача формулируется следующим образом: имеется несколько пунктов отправления (например, складов) и несколько пунктов назначения (например, магазинов), между которыми осуществляются перевозки некоторого однородного груза. Известны:
- объем груза в каждом пункте отправления;
- потребность в грузе каждого пункта назначения;
- стоимость перевозки единицы груза по каждому маршруту.
Необходимо составить такой план перевозок, чтобы общие транспортные затраты были минимальными.
Рассмотрим пример транспортной задачи.
| Пункт отправления | Пункт назначения 1 | Пункт назначения 2 |
| Склад 1 | 4 | 2 |
| Склад 2 | 5 | 3 |
Здесь стоимость перевозки 1 единицы груза со Склада 1 в Пункт назначения 1 составляет 4 условные единицы.
Объем груза на складах:
- Склад 1: 50 единиц
- Склад 2: 60 единиц
Потребность пунктов назначения:
- Пункт назначения 1: 40 единиц
- Пункт назначения 2: 70 единиц
Математическая модель этой задачи имеет следующий вид:
где xij - объем перевозок с i-го склада в j-й пункт назначения.
2. Нахождение опорного плана
Для нахождения оптимального решения транспортной задачи используют пошаговые итерационные методы. На первом этапе находят некоторое начальное допустимое решение, которое называется опорным планом . В качестве опорного плана может быть взят план с минимальной стоимостью перевозок или план, удовлетворяющий критерию северо-западного угла.
Метод северо-западного угла
Суть этого метода заключается в следующем:
- Заполняются ячейки транспортной таблицы, расположенные в левом верхнем углу.
- Если спрос пункта назначения удовлетворен, переходят к следующему пункту.
- Если возможности пункта отправления исчерпаны, переходят к следующему.
Рассмотрим на примере транспортной задачи как применяется этот метод.
Сначала заполняется ячейка в левом верхнем углу (Склад 1 - Пункт 1). Отправляем сюда 40 единиц груза (по спросу пункта). Затем переходим к Пункту 2 и отправляем туда оставшиеся 10 единиц со Склада 1.
Далее переходим к Складу 2. Весь его объем 60 единиц отправляем в Пункт 2, заполняя его спрос.
В результате получаем опорный план:
| Пункт 1 | Пункт 2 | |
| Склад 1 | 40 | 10 |
| Склад 2 | 0 | 60 |
Метод минимальной стоимости
Этот метод заключается в следующем: сначала заполняются ячейки с минимальными транспортными затратами, затем переходят к следующим по возрастанию затрат.
Для той же транспортной задачи опорный план по этому методу будет таким:
| Пункт 1 | Пункт 2 | |
| Склад 1 | 0 | 50 |
| Склад 2 | 40 | 30 |
Здесь сначала мы заполнили ячейку со стоимостью 2 (Склад 2 - Пункт 2), затем стоимостью 3 (Склад 2 - Пункт 1) и т.д.
Таким образом, в зависимости от выбранного метода опорный план может существенно отличаться.
3. Метод потенциалов решения транспортной задачи пример
Наиболее распространенным методом поиска оптимального плана перевозок является метод потенциалов . Рассмотрим его подробный алгоритм на конкретном примере.
Допустим, у нас есть опорный план, найденный методом северо-западного угла:
- Построить вспомогательную таблицу потенциалов.
- Определить значения потенциалов для каждого пункта отправления и назначения.
- Проверить оптимальность текущего плана.
- Найти цикл улучшения плана.
- Пересчитать план с учетом найденного цикла.
Рассмотрим все эти шаги подробно на примере нашей транспортной задачи...
4. Продолжение метода потенциалов
Итак, мы остановились на этапе построения вспомогательной таблицы потенциалов. Для этого рядом с таблицей опорного плана строится таблица такого же размера. В ячейки, соответствующие заполненным в опорном плане, подставляются значения из матрицы транспортных затрат.
На следующем шаге необходимо найти значения потенциалов. Потенциал - это оценка выгодности использования данного пункта отправления или назначения. Потенциалы строк соответствуют пунктам отправления, потенциалы столбцов - пунктам назначения.
Потенциалы находят из условия: значение в любой заполненной ячейке равно сумме потенциалов соответствующей строки и столбца. Эта система уравнений решается для нахождения всех неизвестных потенциалов.
Далее проверяем оптимальность текущего плана перевозок. Для этого заполняем пустые ячейки вспомогательной таблицы, используя найденные потенциалы. Если все значения неотрицательны - план оптимален.
5. Поиск цикла улучшения
Если среди заполненных пустых ячеек вспомогательной таблицы есть хотя бы одно отрицательное значение, значит найден не оптимальный план перевозок. В этом случае необходим поиск цикла улучшения плана.
Для этого в таблице опорного плана отмечаются знаками "+" и "-" ячейки, соответствующие отрицательному элементу вспомогательной таблицы так, чтобы получился замкнутый контур.
На следующем шаге происходит пересчет опорного плана с учетом найденного цикла. После чего вся процедура - проверка оптимальности, поиск цикла улучшения и пересчет плана - повторяется.
6. Критерий оптимальности
Итак, рассмотренный метод потенциалов позволяет постепенно улучшать опорный план перевозок за счет нахождения циклов улучшения. Возникает вопрос - когда же нужно остановиться?
Ответ прост - когда достигнут оптимальный план. Оптимальность плана определяется по критерию оптимальности:
- Все ячейки таблицы потенциалов неотрицательны
- Суммы по строкам и столбцам таблицы плана равны заданным ограничениям
Как только оба эти условия выполняются - перевозки спланированы оптимальным образом, дальнейшее улучшение плана невозможно.
7. Сравнение методов решения
Кроме метода потенциалов, существуют и другие эффективные методы решения задачи оптимизации перевозок:
- Распределительный метод
- Метод минимального элемента
- Вогельское приближение
Каждый из подходов имеет свои преимущества и ограничения. Например, распределительный метод хорошо масштабируется, а метод потенциаловдилатион удобен для небольших транспортных сетей...