37. Метод потенциалов тз. Проверка плана на вырожденность. Проверка решения транспортной задачи на оптимальность.

Проверка плана на вырожденность

После того как установлено начальное опорное решение его необходимо проверить на оптимальность и вырожденность.

Вырожденый план ТЗ – если число заполненных клеток не совпадает с числом m+n-1 где m – число поставщиков n – число потребителей. В этом случае число переменных системы окажется > числа уравнений, а значит система будет иметь бесконечное множество решений. Чтобы не допустить этого нужно любой вырожденный план привести к не вырожденному виду.

В случае вырожденности недостающее количество заполненных клеток устраняют внесением базисных нулей в пустые клетки.

ПРЕДПОЧТЕНИЕ для заполнения отдают тем клеткам у которых наименьшие тарифы, но при этом эти клетки не должны образовывать цикл с уже заполненными.

Проверка решения транспортной задачи на оптимальность.

Введём потенциалы поставщиков и потребителей. A1, A2, A3…Am – потенциалы поставщиков. А1, А2, А3,…Аn – потенциалы потребителей. Для нахождения потенциалов составим систему уравнений. Ai+Bj=Cij.

ЗАМЕЧАНИЕ. Данные уравнения составляются только для заполненных клеток.

Заполненных клеток m+n-1 a общее число потенциалов m+n. Значит система будет иметь бесконечное множество решений, а для того чтобы было единственное решение один из потенциалов приравнивают к нулю A1=0. Получаем систему m+n уравнений с m+n неизвестных. Решив систему и найдя потенциалы занесём их на соответствующие места транспортной таблицы. Подписываем в той же клетке где и название столбцов и строк. По найденным потенциалам определяем оценки свободных клеток Дельта(ij)=альфа(i)+бета(j)-Cij. Где Дельта(ij) – оценки свободных клеток, Альфа(i) – потенциал поставщиков, Бета(j) –потенциал потребителей, Cij – тарифы.

Критерий оптимальности. План транспортной задачи для целевой функции F(x)min считается оптимальным если все оценки свободных клеток не положительны, если есть хоть одна положительная оценка план считается не оптимальным.

38. Построение нового опорного решения тз. Понятие цикла.

Неоптимальный план можно улучшить путём перераспределения грузов по циклу.

Цикл – это замкнутая ломаная, которая строится по правилам: 1. Цикл начинается и заканчивается в пустой клетке с наибольшей положительной оценкой. 2. Остальные вершины цикла находятся только в заполненных клетках. 3. Звенья ломаной либо горизонтальны либо вертикальны. 4. В каждой вершине ломаная совершает поворот на 90 градусов. 5. Для любой свободной клетки цикл строится единственным образом. ЗАМЕЧАНИЕ. Не все заполненные клетки должны обязательно участвовать в цикле.

ЧАСТЫЕ ВИДЫ ЦИКЛОВ. 1. Прямоугольный 2. Ступенчатый 3. Перекрёстный.

В построенном цикле присваиваем каждой вершине поочерёдно начиная с пустой клетки знаки + и -. Начинаем с пустой и ставим +, хоть по хоть против часовой. Среди клеток со знаком минус выбираем наименьший объём груза. Гама=min{ij} (из клеток с минусом) где Гама – величина перераспределяемого груза. Отнимем гаму от объёмов грузов в клетках со знаком минус. И прибавим гаму к объёмам груза в клетках со знаком +. В результате пустая клетка цикла заполнится. А одна из клеток со знаком минус освободится, та которая содержала гаму. ЗАМЕЧАНИЕ. Освобождать можно только одну клетку. Если есть несколько то желательно освободить ту где тариф больше а в остальные базисные нули. В результате перераспределения получаем новый план который подвергаем проверке на оптимальность и вырожденность. Алгоритм повторяется до тех пор пока план не станет оптимальным невырожденным. ЗАМЕЧАНИЕ. На первом шаге значение целевой функции определяется как сума произведений тарифов на соответствующие объёмы грузов (сума от j=1 до n Сума от i=1 до m Cij*Xij). На всех последующих шагах также можно пользоваться этой формулой.