Лабораторная работа 13. Решение транспортной задачи в матричной постановке
Рассмотрим пример, в котором требуется решить транспортную задачу методом потенциалов, что значения a[i], b[j], c[i, j] (iÎ [1..4], jÎ [1..3]), заданы в таблице 1.
Таблица 1.
Решение. Транспортная задача имеет решение тогда и только тогда, когда выполняется соотношение:
В данном случае, , поэтому необходимо ввести в рассмотрение фиктивного (внешнего) потребителя (№4): b[4]= =12-11=1 Положим для всех iÎ [1..4] с[i, 4]=100 Определим исходное базисное решение методом северо-западного угла.
Таблица 2.
Стоимость перевозок составит: L(x)= 127
По критерию оптимальности определим, является ли найденное решение наилучшим. d[3, 1] =max{ d[i, j]| iÎ [1..4], jÎ [1..4] }=2 ³ 0, значит полученное базисное решение не является оптимальным и необходимо перейти к новому базису.
Строим цикл П, который будет состоять из клеток x[3, 1], x[1, 1], x[1, 2], x[3, 2], в позициях q которых записываются соответственно ‘+’, ‘-’, ‘+’, ‘-’. Среди значений x[i, j], в клетках которых записаны, ‘-’ находим минимальное Q=min x[i, j]. Оно равно 1, и достигается на клетке [1, 1]. Т.о. клетку [3, 1] вводим в базис, а клетку [1, 1] выводим из базиса.
Пересчитаем значения x[i, j] для нового базиса.
Таблица 3.
Стоимость перевозок составит: L(x)=125. По критерию оптимальности определим, является ли найденное решение наилучшим. max{ d[i, j]| iÎ [1..4], jÎ [1..4] }£ 0, значит полученное базисное решение является оптимальным Стоимость перевозок без учета фиктивного потребителя составит L(x)=25 Задание. Решить транспортную задачу методом потенциалов, значения a[i] (iÎ [1..4]) и b[j] (jÎ [1..3]) заданы в таблице 4, значения c[i, j] задать произвольным образом. Таблица 4
|