Транспортная задача
Лекция 5-6
Постановка транспортной задачи
Имеется 
поставщиков 
, у которых сосредоточены запасы однородного груза в количестве 
единиц соответственно. Этот груз нужно доставить 
потребителям 
, заказавшим 
единиц этого груза. Также известны тарифы на перевозку груза 
(стоимость доставки единицы продукции) от 
-го поставщика к 
-му потребителю. Необходимо составить план перевозок, при котором запасы всех поставщиков реализованы, спрос потребителей удовлетворен, а общая стоимость перевозок минимальна.
Условие транспортной задачи удобно записать в виде таблицы.
Таблица 3.1. Транспортная таблица
| Поставщики | Потребители | Запасы | |||
| 
| 
| 
| ||
| 
| 
|
| 
| 
|
| 
| 
|
| 
| 
|
|
|
|
|
|
|
|
| 
| 
|
| 
| 
|
| Потребности | 
| 
|
| 
|
Неизвестные переменные транспортной задачи – объемы перевозок 
от -го поставщика 
-му потребителю, 
. Эти переменные записываются в виде матрицы перевозок:
.
Математическая постановка транспортной задачи:
 , (3.1)
|  , (3.2)
|
 , (3.3)
|  . (3.4)
|
Опорный план – всякое неотрицательное решение системы (3.2)-(3.4), определяемое матрицей 
.
Оптимальный план – план 
, при котором целевая функция 
принимает свое минимальное значение.
Необходимое и достаточное условие разрешимости транспортной задачи
. (3.5)
Если условие (3.5) выполняется, задача называется сбалансированной, модель – закрытой. Если условие (3.5) не выполняется, то задача – несбалансированная, модель – открытая.
Если задача является открытой, то необходимо свести ее к закрытому типу. Если 
, добавляется фиктивный поставщик 
с запасом груза 
. Если 
, то добавляется фиктивный потребитель 
с потребностью 
. Соответствующие фиктивным объектам тарифы перевозок 
полагаем равными нулю, чтобы суммарная стоимость перевозок не изменялась.
Цель решения транспортной задачи – определение переменных 
, при которых выполняются ограничения (3.2)-(3.4), и целевая функция (3.1) принимает минимальное значение.
Алгоритм решения транспортной задачи:
1. Построение первоначального плана перевозок (метод северо-западного угла, метод минимальной стоимости);
2. Оптимизация плана (метод потенциалов).
Метод северо-западного угла
Составление плана перевозок начинается с распределения запасов товара поставщика 
. Будем за счет его запасов удовлетворять заказы потребителя 
, затем 
и т.д. Таким образом, будем заполнять таблицу, начиная с клетки (1, 1), и двигаться вправо по строке до тех пор, пока остаток запасов поставщика не окажется меньше заказа очередного потребителя. Далее аналогичным образом распределим запасы поставщика 
, затем 
и т.д.
Пример 1. Предположим, что имеются поставщики 
, 
и 
ресурса, потребителями которого являются предприятия 
, , 
и 
.
В условии задачи известны количества ресурсов 
, необходимые предприятиям; возможности поставщиков 
, а также тариф на доставку единицы ресурса от поставщика к потребителю 
. Начальные данные приведены в табл. 3.2.
Таблица 3.2 – Транспортная таблица с исходными данными
| Поставщики | Потребители | Запасы | |||
| 
| 
| 
| ||
| |||||
| |||||
| |||||
| Потребности |
Необходимо построить первоначальный план снабжения методом северо-западного угла.
Решение.
Из табл. 3.2 видно, что транспортная задача сбалансированая.
Шаг № 1. Северо-западный угол табл. 3.2 – клетка (1, 1). У поставщика есть 160, а потребителю нужно 100 единиц товара. Находим минимум из этих двух чисел: min (160, 100) = 100. Клетка (1, 1) перечеркивается по диагонали сплошной чертой (––––), в правом нижнем углу пишется найденный минимум. Это означает, что поставщик должен отправить потребителю 100 единиц товара. Такие клетки в дальнейшем будем называть отмеченными.
Так как потребность потребителя полностью удовлетворена, то данный потребитель исключается из рассмотрения. Поэтому все остальные клетки 1-го столбца закрашиваются. Они называются пустыми и в дальнейшем исключаются из рассмотрения.
Таблица. 3.3 – Транспортная таблица, полученная на шаге № 1
| Поставщики | Потребители | Запасы | |||
|
|
|
|
| ||
|
| |||||
|
| |||||
|
| |||||
| Потребности |
Первый столбец в дальнейшем не рассматривается.
Шаг № 2. Северо-западный угол табл. 3.3 – клетка (1, 2). Поэтому рассмотрим 1-го поставщика и 2-го потребителя. Оставшаяся мощность (объем запаса) поставщика 
равна 60. Спрос потребителя 
– 40. Находим минимум min (60, 40) = 40. Клетка (1, 2) становится отмеченной.
Таблица 3.4 – Транспортная таблица, полученная на шаге № 2
| Поставщики | Потребители | Запасы | |||
|
|
|
|
| ||
|
| |||||
|
| |||||
|
| |||||
| Потребности |
Шаг № 3. Северо-западный угол табл. 3.4 – клетка (1, 3): min (20, 80) = 20.
Таблица 3.5 – Транспортная таблица, полученная на шаге № 3
| Поставщики | Потребители | Запасы | |||
|
|
|
|
| ||
|
| |||||
|
| |||||
|
| |||||
| Потребности |
Шаг № 4. Северо-западный угол табл. 3.5 – клетка (2, 3): min (30, 60) = 30.
Таблица 3.6 – Транспортная таблица, полученная на шаге № 4
| Поставщики | Потребители | Запасы | |||
|
|
|
|
| ||
|
| |||||
|
| |||||
|
| |||||
| Потребности |
Шаг № 5. Северо-западный угол табл. 3.6 – клетка (3, 3): min (90, 30) = 30.
Таблица 3.7 – Транспортная таблица, полученная на шаге № 5
| Поставщики | Потребители | Запасы | |||
|
|
|
|
| ||
|
| |||||
|
| |||||
|
| |||||
| Потребности |
Шаг № 6. В табл. 3.7 осталась незаполненная клетка (3, 4): min (90‑30, 60)=60.
Таблица 3.8 – Транспортная таблица, полученная на шаге № 6
| Поставщики | Потребители | Запасы | |||
|
|
|
|
| ||
|
| |||||
|
| |||||
|
| |||||
| Потребности |
Общая стоимость всех перевозок по полученному опорному плану:
.