http://npc-news.ru/

Каждой из клеток присваиваем знак

Каждой из клеток, связанных с данной циклом при­сваивают определённый знак, причём свободной клет­ке — знак (+), а всем остальным поочередно знаки (—) и (+) по циклу.

В данную свободную клетку переносят меньшее из чи­сел Xjj, стоящих в минусовых клетках. Одновременно это число необходимо прибавить к соответствующим числам, находящимся в плюсовых клетках и вычесть из чисел, находящихся в минусовых клетках. Клетка, которая раньше была свободной, становится занятой, а минусовая клетка с минимальным числом становит­ся свободной (пустой).

Таким образом, получаем новый опорный план, который следует проверить на оптимальность (переход к этапу 2).

В нашем случае необходимо заполнить клетку (1,4), так как а\4 > 0. Соответствующая разметка клеток, образующих цикл, показана в табл. 2.15. В результате перемещения ресурса в ко­личестве 90 единиц, получаем новое решение (табл. 2.16).

F = 70 + 2 • 90 + 8 • 20 + 3 • 120 + 2 • 50 + 4 • 120 = 1350.

Полученное решение лучше предыдущего. Проверяем его на оптимальность В результате получаем для заполненных клеток:

Можно легко проверить, что данный вариант является опти­мальным.


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