Оптимизация опорного решения

Метод оценки циклов

Метод состоит в том, что для каждой свободной клетки составляется и оценивается цикл. Цикл, это прямоугольная фигура, в которой все клетки, кроме первой, заняты. Наиболее типичные примеры циклов приведены на рисунке. 2.5.2.

Рисунок 2.5.2 – Примеры циклов транспортных перестановок

 

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

Таблица 2.5.3

Составление и оценка циклов для оптимизации плана перевозок

 

Оценки циклов:

	- +72-22+16-40=+26;
	- +25-22+16-52=-33;
	- +40-22+16-52+12-11=-17;
	- +15-70+22-8=-41;
	- +10-8+16-40=-22;
	- +4-8+16-52=-40;
	- +15-11+12-52+16-8=-28;
	- +27-70+22-16=-37;
	- +52-52+12-11=+1;
	- +55-70+22-16+52-12=31;
	- +8-16+52-12=+32;
	- +52-40+52-12=+52.

Перестановки осуществляются по циклу с наибольшей по модулю отрицательной оценкой. В данном случае это цикл, составленный для клетки А₂-В₄, имеющий оценку минус 40. По циклу переставляется минимальное число, стоящее в отрицательной вершине. Здесь в отрицательных вершинах стоят 154 и 127 единиц товаров. Переставляем 127, путем вычитания этого числа из отрицательных вершин и прибавления в положительные.

В результате получается новый план, приведенный в таблице 2.5.4.

Таблица 2.5.4

План перевозок после первой перестановки
Запасы поставщиков	Потребности потребителей
B1=100	B2=200	B3=50	B4=252	B5=77
A1=152
A2=127
A3=225
A4=175

 

Для этого плана снова составляются и оцениваются все циклы, Процедура повторяется до тех пор, пока есть отрицательные циклы.

После каждой итерации вычисляется целевая функция – суммарные затраты на перевозку. В данном случае

F=70×100+22×52+4×127+16×148+40×50+
+52×27+12×98+11×77=16447 у.д.е.

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