П.2.4. Решение транспортной задачи

Порядок решения транспортных задач с помощью QSB рассмотрим на следующем примере.

Пример. Требуется составить такой план прикрепления трёх потребителей к трём поставщикам, при котором общая стоимость перевозок будет минимальной. Тарифы перевозки единицы продукции от поставщиков к потребителям, объёмы предложения поставщиков и спроса потребителей заданы в таблице.

Обозначим через x_{i j} – количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю.

Тогда ЭММ:

Здесь предполагается, что суммарное предложение равно суммарному спросу. Такая задача называется закрытой или замкнутой. Если это условие не выполнятся, то задача называется открытой. Для сведения открытой задачи к закрытой вводится или фиктивный поставщик или фиктивный потребитель.

Подготовьте ЭММ задачи для решения на ЭВМ, причём объёмы предложения поставщиков и спроса потребителей должны быть целыми числами, а тарифы перевозок могут быть вещественными. Итак, в нашей задаче: ЦФ на минимум, 3 поставщика, 3 потребителя. Предложение поставщиков: 120, 100 и 80. Спрос потребителей: 90, 90 и 120.

Выберите опцию 3 – Транспортная задача в главном меню системы. На экране появится функциональное меню, идентичное рассмотренному ранее.

В функциональном меню выберите опцию 2- Ввод новой задачи, введите название задачи (например, prim3 ), ответьте на вопросы о задаче. Варианты ответов: ЦФ на минимум, 3 поставщика, 3 потребителя, будем использовать заданные обозначения поставщиков (S₁, S₂,...S_n) и потребителей (D₁, D₂,...,D_n). По окончании нажмите клавишу Spacebar .На экране появится шаблон для ввода объёмов предложения поставщиков и спроса потребителей.

Заполните шаблон следующим образом:

После нажатия клавиши Spacebar на экране появится шаблон для ввода стоимости перевозок (или прибыли от перевозок).

Введите данные, как показано ниже:

После нажатия Spacebar на экране появится функциональное меню.

В функциональном меню выберите опцию 5 – Решение задачи. На экране появится меню опции <Решение>:

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

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

Для поиска оптимального плана применён метод потенциалов. При этом признаком оптимальности плана является существование таких чисел U(i) и V(j), для которых выполняются условия:

U(i)+V(j)=C(i,j) для x_{i j} > 0;

U(i)+V(j)£C(i,j) для x_{i j} = 0, (*)

где C(i,j) и x_{i j} – стоимость перевозки единицы груза и количество перевозимого груза от i-го поставщика (i = 1...m) j-мц потребителю (j = 1...n).

Выберите опцию 2 – Решение и просмотр всех таблиц. Результаты решения на каждой итерации представлены одинаковыми по форме таблицами.

В первой таблице показан начальный допустимый план прикрепления поставщиков к потребителям (потенциалы U(i) и V(j) полагаются равными нулю, значение ЦФ = 2050).. Переход к следующей таблице осуществляется нажатием любой клавиши, кроме G ,при нажатии которой вычислительный процесс пойдёт без остановки до конца.

В этой таблице вычислены потенциалы по формуле (*). Признак оптимальности плана не выполнен для клетки (S3, D1), а именно U(i)+V(j)=4+7=11 превосходит стоимость перевозки от поставщика S3 к потребителю D1 на 9, что изображено в виде и в этой клетке поставлены две звёздочки (**). Это значит, что в данную клетку следует поместить перевозку, объём которой равен 60 (определяется из цикла (3,1)-(3,3)-(2,3)-(2,2)-(1,2)-(1,1)).

На следующей итерации фиксируется перемещение перевозок по циклу, вычисляется текущее значение ЦФ (=1510), определяется клетка (S1, D3), для которой не выполнен признак оптимальности (е(1,3)=–8) и т.д. Процесс поиска оптимального решения заканчивается на четвёртой итерации. После нажатия любой клавиши на экране появляется меню способов представления полученного решения задачи.

Выберите опцию 1 – просмотр итогового решения. На экране появится таблица с результатами решения задачи:

После 4 итераций получили оптимальный план, согласно которому от первого поставщика везётся ко второму потребителю 10, к третьему 110, к четвёртому 90; от второго поставщика – в первому потребителю 90; к третьему 10; от третьего поставщика – ко второму потребителю 80.