Оптимизация опорного решения
Метод оценки циклов Метод состоит в том, что для каждой свободной клетки составляется и оценивается цикл. Цикл, это прямоугольная фигура, в которой все клетки, кроме первой, заняты. Наиболее типичные примеры циклов приведены на рисунке. 2.5.2.
В таблице 2.5.3 приведены циклы для исходной задачи, представленной в таблице 2.5.1. В пустой клетке ставим минус, а далее по порядку плюс, минус, плюс, минус и т.д. Таблица 2.5.3
Оценки циклов:
Перестановки осуществляются по циклу с наибольшей по модулю отрицательной оценкой. В данном случае это цикл, составленный для клетки А2-В4, имеющий оценку минус 40. По циклу переставляется минимальное число, стоящее в отрицательной вершине. Здесь в отрицательных вершинах стоят 154 и 127 единиц товаров. Переставляем 127, путем вычитания этого числа из отрицательных вершин и прибавления в положительные. В результате получается новый план, приведенный в таблице 2.5.4. Таблица 2.5.4
Для этого плана снова составляются и оцениваются все циклы, Процедура повторяется до тех пор, пока есть отрицательные циклы. После каждой итерации вычисляется целевая функция – суммарные затраты на перевозку. В данном случае F=70×100+22×52+4×127+16×148+40×50+ При использовании данного метода для наглядности каждый цикл рекомендуется обозначать своим цветом.
|
