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

Таблица 27.

Таблица 26.

Таблица 25

После определения потенциалов находим оценки для свободных клеток по правилу , записываем их в верхнюю часть каждой свободной клетки. Решение является оптимальным, если все найденные оценки неположительны (меньше или равны 0).

Пример 5. Проверить оптимальность решения, построенного в примере 4 (см. таблицу 24).

Решение. Сначала по таблице 24 определяем потенциалы.

Занятыми являются клетки (1;1), (2;1), (2;2), (2;3), (3;2). С учетом стоимостей, записанных в этих клетках, составляем систему уравнений

В А				u_i
		-	-

	-		-	-2
v_j			-1

Пусть . Далее последовательно: из первого уравнения , из второго уравнения , из третьего , из четвертого , из пятого . Результаты собраны в таблице 26.

Расчет оценок проводится по формуле непосредственно в таблице 27, с учетом найденных выше потенциалов

В А				u_i
		0+4-3=1>0 -	0+(-1)-0=-1<0 -

	-2+1-4=-5<0 -		-2+(-1)-0=-3<0 -	-2
v_j			-1

Итак, видно, что в ячейке (1;2) оценка положительна, т.е. предложенное решение не является оптимальным.

Одним из основных понятий в этом пункте является цикл – последовательность клеток таблицы транспортной задачи, в которой две и только две соседние клетки расположены в одной строке или в одном столбце, причем первая и последняя клетки также находятся в одной строке или в одном столбце. Известно, что в таблице транспортной задачи, содержащей опорное решение, для любой свободной клетки можно построить единственный цикл, содержащий эту клетку и часть занятых.

Если решение не оптимальное, то среди положительных оценок выбираем наибольшую (в случае равенства наибольших оценок – выбираем ячейку с наименьшей стоимостью). Для выбранной ячейки строим цикл, включающий эту клетку и часть занятых клеток, причем свободная клетка получает знак «+», а далее знак чередуется. Для попавших в цикл ячеек определяем величину

Перемещаем перевозки по циклу в соответствии с правилом: в ячейках со знаком «+» q добавляется к значению x_ij, а в ячейках со знаком «-» q из x_ij вычитается. При этом клетка, в которой изначально находился объем перевозок, равный q, становится пустой, а свободная с выбранной «плохой» оценкой - занятой.

Замечание. Если минимальное значение q достигается в нескольких клетках, то только одна из них становится пустой, а в остальных объем перевозок выставляется равным 0; это позволяет сохранить необходимое количество занятых клеток.

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

Пример 6. Найти оптимальное решение для транспортной задачи из примера 4.

Решение. Условия были приведены в таблице 14. Задача была открытой, поэтому сначала был введен фиктивный потребитель. Начальное опорное решение, построенное методом минимальной стоимости – в таблице 24. Таблица 27 (с потенциалами и оценками) свидетельствует, что построенное решение не оптимальное, а ячейка (1;2) – единственная ячейка с положительной оценкой. С нее и начнем строить цикл. По таблице 27 видно, что его образуют ячейки (1;2), (2;2), (2;1), (1;1). В силу сказанного выше ячейки