Порядок решения транспортных задач с помощью QSB рассмотрим на следующем примере.
Пример. Требуется составить такой план прикрепления трёх потребителей к трём поставщикам, при котором общая стоимость перевозок будет минимальной. Тарифы перевозки единицы продукции от поставщиков к потребителям, объёмы предложения поставщиков и спроса потребителей заданы в таблице.
Поставщики
Тарифы перевозок
Предложение поставщиков
Спрос потребителей
Обозначим через xi j – количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю.
Тогда ЭММ:
Здесь предполагается, что суммарное предложение равно суммарному спросу. Такая задача называется закрытой или замкнутой. Если это условие не выполнятся, то задача называется открытой. Для сведения открытой задачи к закрытой вводится или фиктивный поставщик или фиктивный потребитель.
Подготовьте ЭММ задачи для решения на ЭВМ, причём объёмы предложения поставщиков и спроса потребителей должны быть целыми числами, а тарифы перевозок могут быть вещественными. Итак, в нашей задаче: ЦФ на минимум, 3 поставщика, 3 потребителя. Предложение поставщиков: 120, 100 и 80. Спрос потребителей: 90, 90 и 120.
Выберите опцию 3 – Транспортная задача в главном меню системы. На экране появится функциональное меню, идентичное рассмотренному ранее.
В функциональном меню выберите опцию 2- Ввод новой задачи, введите название задачи (например, prim3 ), ответьте на вопросы о задаче. Варианты ответов: ЦФ на минимум, 3 поставщика, 3 потребителя, будем использовать заданные обозначения поставщиков (S1, S2,...Sn) и потребителей (D1, D2,...,Dn). По окончании нажмите клавишу Spacebar .На экране появится шаблон для ввода объёмов предложения поставщиков и спроса потребителей.
Заполните шаблон следующим образом:
постав.:
S1: 120____ S2: 100____ S3: 80___
D1: 90____ D2: 90____ D3: 120___
После нажатия клавиши Spacebar на экране появится шаблон для ввода стоимости перевозок (или прибыли от перевозок).
Введите данные, как показано ниже:
от к
S1: D1: 7____ D2: 6____ D3: 4___
S2 D1: 3____ D2: 8___ D3: 5___
S3 D1: 2____ D2: 3____ D3: 7____
После нажатия Spacebar на экране появится функциональное меню.
В функциональном меню выберите опцию 5 – Решение задачи. На экране появится меню опции <Решение>:
Меню опции <Решение>
пункт
1---- Решение и просмотр начальной таблицы
2---- Решение и просмотр всех таблиц
3---- Решение и просмотр итоговой таблиц
4---- Решение без просмотра таблиц
5---- использовать метод Фогеля
6---- Возврат в функциональное меню
Выбор опции 6 обеспечивает возврат в функциональное меню без решения задачи. При выборе остальных опций задача будет решена. При этом для задач небольшой размерности доступны все режимы, а для больших задач – только опции 4-5.
Для построения начального допустимого плана по умолчанию используется метод северо-западного угла, который можно заменить на метод аппроксимации Фогеля с помощью опция 4.
Для поиска оптимального плана применён метод потенциалов. При этом признаком оптимальности плана является существование таких чисел U(i) и V(j), для которых выполняются условия:
U(i)+V(j)=C(i,j) для xi j > 0;
U(i)+V(j)£C(i,j) для xi j = 0, (*)
где C(i,j) и xi 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)).
Начальн. решение NWC
SN/DN
D1
D2
D3
предлож.
U(i)
S1
7.000
6.000
4.000
120.00
90.00
30.00
S2
3.000
8.000
5.000
100.00
60.00
40.00
S3
2.000
3.000
7.000
80.00
80.00
спрос V(j)
90.00
90.00
120.00
Минимум значение цф = 2050
На следующей итерации фиксируется перемещение перевозок по циклу, вычисляется текущее значение ЦФ (=1510), определяется клетка (S1, D3), для которой не выполнен признак оптимальности (е(1,3)=–8) и т.д. Процесс поиска оптимального решения заканчивается на четвёртой итерации. После нажатия любой клавиши на экране появляется меню способов представления полученного решения задачи.
Выберите опцию 1 – просмотр итогового решения. На экране появится таблица с результатами решения задачи:
итоговый результат prim3 Стр.: 1
от
к
груз
тариф
от
к
груз
тариф
S1
S1
S1
S2
S2
D1
D2
D3
D1
D2
0.0
10.0
110.0
90.0
0.0
7.000
6.000
4.000
3.000
8.000
S2
S3
S3
S3
D3
D1
D2
D3
10.0
0.0
80.0
0.0
5.000
2.000
3.000
7.000
миним. значение цф = 1060 итерация = 4
После 4 итераций получили оптимальный план, согласно которому от первого поставщика везётся ко второму потребителю 10, к третьему 110, к четвёртому 90; от второго поставщика – в первому потребителю 90; к третьему 10; от третьего поставщика – ко второму потребителю 80.