2015-08-21
653
Теорема (признак оптимальности опорного решения). Если существуют m чисел u 1, u 2, …, um и n чисел v 1, v 2, …, vn такие, что ui + vj = cij для базисных (занятых) клеток и ui + vj £ cij для свободных клеток, то план будет оптимальным планом транспортной задачи. Числа ui называются потенциалами пунктов отправления, числа vj называются потенциалами пунктов назначения
Группа равенств ui + vj = cij для базисных клеток используется как система уравнений для нахождения потенциалов. Данная система имеет m + n неизвестных ui и vj (). Число уравнений равно m + n -1. Следовательно, чтобы найти ее решение достаточно задать значение одной неизвестной произвольно (например, u1=0), а остальные найти из системы.
Группа неравенств ui + vj £ cij для свободных клеток используется для проверки оптимальности опорного решения.
Запишем неравенства в виде:
Числа D ij называются оценками свободных клеток таблицы ТЗ.
Оценки для свободных клеток ТЗ используются для улучшения опорного решения. С этой целью находят клетку (l, k) таблицы, соответствующую max D ij (). Если D lk £0, то решение оптимальное. Если D lk >0, то соответствующую клетку вводят в число базисных. Т.к. базисных клеток стало m + n, то по теореме 2 из них можно построить цикл. С помощью цикла улучшают решение. Для этого необходимо расставить в клетках, которые входят в цикл знаки «+» и «–» поочередно, начиная с вновь введенной базисной клетки, в которую ставится знак «+».В клетках, где стоит знак «–» выбрать клетку (p, q) с наименьшей перевозкой, т.е.. Затем осуществляют сдвиг по циклу на величину Q.
|
|
|
Сдвигом по циклу на величину Q называется увеличение объемов перевозок во всех клетках цикла, отмеченных знаком «+», на Q, и уменьшить – во всех клетках цикла, отмеченных знаком «–», на Q. Таким образом, клетка (p, q) выйдет из числа базисных и получаем новое опорное решение.
