Пример решения транспортной задачи методом потенциалов
Пример: Решить транспортную задачу, исходные данные которой приведены в табл. 6.13. Таблица 6.13
Решение. 1. Проверяем выполнение необходимого и достаточного условия разрешимости задачи. Находим суммарные запасы поставщиков и запросы потребителей
Задача с неправильным балансом. Вводим четвертого, фиктивного поставщика с запасами 2. Составляем начальное опорное решение методом минимальной стоимости (табл. 6.14). Таблица 6.14
Записываем матрицу стоимостей C. Находим в этой матрице наименьшие на каждом шаге стоимости и направляем в клетку, которая соответствует этим стоимостям, максимально допустимые объемы перевозок грузов. При этом исключаем на каждом шаге одного поставщика или потребителя. Кружочками в матрице C указаны минимальные элементы, а цифрами рядом со строками и столбцами - порядок исключения из рассмотрения поставщиков и потребителей. Напомним, что запасы фиктивного поставщика вывозятся в последнюю очередь. Полученное решение X1 имеет m+n-1=4+4-1=7 базисных переменных. Опорное решение является вырожденным, так как одна из его координат равна нулю. Вычислим значение целевой функции на этом опорном решении Z(X1)=100·1+0·2+100·3+100·4+200·7+100·12+200·0=3400. . Для проверки оптимальности опорного решения необходимо найти потенциалы. По признаку оптимальности в каждой занятой опорным решением клетке таблицы транспортной задачи сумма потенциалов равняется стоимости (ui+vj=cij при xij>0). Записываем систему уравнений для нахождения потенциалов u1+v1=1, u2+v1=2, u2+v2=3,2+v3=4,3+v3=7,3+v4=12,4+v4=0. Система состоит из семи уравнений и имеет восемь переменных. Система неопределенная. Одному из потенциалов задаем значение произвольно: пусть u2=0. Остальные потенциалы находятся однозначно |
