http://npc-news.ru/

Получение оптимального решения методом узло­вых потенциалов

Теорема. Если для некоторого опорного плана транспортной задачи существуют такие числа а\, а2,…, ат\ /3\, /32, • • •, /Зп, что (3j — <уj = Cjj для заполненных клеток (xjj > 0) и f3j — oii ^ Cjj для пустых клеток (xjj = 0), то такой план называется оптимальным. Числа п;. называются потенциалами соответственно пунктов отправления и пунктов назначения.

1. Составим систему уравнений для заполненных клеток:

Так как число заполненных клеток т + п — 1 = 6, а число неизвестных т + п = 7, то одно из неизвестных выбирают

произвольно. Пусть, например, а\ = 0. Тогда: Q3 = — 2, «2 = — 4, fa = i; /?4 = 4, /32 = о, А = 0.

2.  Для каждой свободной клетки определяются числа, такие что aij = — o?i — Cjj. Если все Qjj отрицательны, то опор­ное решение является оптимальным. В противном случае необходимо перейти к новому плану. Для данного примера:

Поскольку су 14 > 0, то имеющееся решение не является оптимальным.

3.  Для перехода к новому плану рассматривают все свобод­ные клетки, для которых а.ц > 0 и из них выбирают клетку с максимальным значением Qjj. Данную клетку следует заполнить. При этом следует изменить объёмы поставок в других клетках, связанных с данной клеткой циклом. Циклом называется замкнутая ломаная линия, вершины которой находятся в занятых клетках таблицы и в данной заполняемой клетке, а звенья располагаются вдоль строк и столбцов. Необходимо переместить ресурсы в пределах клеток цикла, для чего необходимо выполнить следующие действия.


Комментарии закрыты.