Методика перехода к лучшему опорному решению

Наличие положительной оценки свободной клетки (D_ij ≥ 0) при проверке опорного решения на оптимальность свидетельствует о том, что полученное решение не оптимально, и для уменьшения значения целевой функции надо перейти к другому опорному решению. При этом надо перераспределять грузы, перемещая их из занятых клеток в свободные. Свободная клетка становится занятой, а одна из ранее занятых – свободной.

Для свободной клетки, имеющей максимальную положительную величину оценки, , строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках, углы прямые, число вершин четное. Форма цикла может быть разной, например:

Но для клетки с положительной оценкой он является единственным.

Около свободной клетки цикла ставится знак (+), затем, используя правило чередования знаков, поочередно проставляют знаки (–) и (+). У вершин со знаком (–) выбирают минимальный груз q = min[x_ij^(-)], его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (–). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность, и т.д. до тех пор, пока не получим оптимальное решение.

Замечание. В некоторых случаях поставка, перераспределяемая по циклу, может оказаться равной нулю. Это возможно тогда, когда клетка со знаком «–» содержала нулевую поставку . В этом случае по циклу передается нулевая поставка. В результате свободная клетка, для которой был построен цикл, становится заполненной (нулевой поставкой), а клетка с нулевой поставкой – свободной.

Если при перераспределении поставки по циклу поставка обращается в нуль сразу в нескольких заполненных клетках, то свободной следует считать только одну (любую) из них. Остальные клетки, поставка в которых стала равной нулю, следует считать заполненными нулевой поставкой .

 

Переход к следующему опорному решению.

Выбираем клетку, от которой начнем построение цикла перераспределения поставок, по правилу , или , т.е. максимальную величину оценки имеет свободная клетка (1, 2). Для этой клетки можно построить следующий цикл: 0^*-14-1- -15-5-0^* (все вершины цикла, кроме первой, находятся в занятых клетках, углы прямые, число вершин четное). У вершин цикла с соответствующими значениями поставок по правилу чередования знаков ставим знаки (+) и (–).У вершин со знаком (–) выбираем минимальный груз q = min[14, , 5] = . Поскольку перемещаемый по циклу груз имеет нулевое значение, то произойдет только перемещение нулевой поставки  в клетку(1, 2), а клетка (4, 3), где ранее была нулевая поставка, станет свободной.

 

                     

Фактически решение задачи (план перевозок) не изменилось, однако необходимо пересчитать потенциалы и найти новые оценки свободных клеток, учитывая, что клетка (1, 2) теперь занята, а клетка (4, 3) свободна:

.

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

u ₁ = 0;

клетка (1, 1): v ₁ = c ₁₁ – u ₁ = 6 – 0 = 6;

клетка (4, 1): u ₄ = c ₄₁ – v ₁ = 5 – 6 = -1;

клетка (1, 2): v ₂ = c ₁₂ – u ₁ = 10 – 0 = 10;

клетка (2, 2): u ₂ = c ₂₂ – v ₂ = 7 – 10 = -3;

клетка (3, 2): u ₃ = c ₃₂ – v ₂ = 14 – 10 = 4;

клетка (3, 3): v ₃ = c ₃₃ – u ₃ = 5 – 4 = 1;

клетка (4, 4): v ₄ = c ₄₄ – u ₄ = 4 – (-1) = 5.

Расчет оценок свободных клеток:

D₁₃ = u ₁ + v ₃ - c ₁₃ = 0 + 1 – 7 = –6 < 0,

D₁₄ = u₁ + v₄ - c₁₄ = 0 + 5 – 5 = 0,

D₂₁ = u₂ + v₁ - c₂₁ = – 3 + 6 – 10 = –7 < 0,

D₂₃ = u₂ + v₃ - c₂₃ = – 3 + 1 – 6 = –8 < 0,

D₂₄ = u₂ + v₄ - c₂₄ = – 3 + 5 – 9 = –7 < 0,

D₃₁ = u₃ + v₁ - c₃₁ = 4 + 6 – 13 = –3 < 0,

D₃₄ = u₃ + v₄ - c₃₄ = 4 + 5 – 7 = 2 > 0,

D₄₂ = u₄ + v₂ - c₄₂ = – 1 + 10 – 10 = –1 < 0,

D₄₃ = u₄ + v₃ - c₄₃ = – 1 + 1 – 6 = –6 < 0.

Результаты расчета представлены в распределительной таблице:

 

bj ai		1	2	3	4	ui
		15	16	15	20
1	14	6 14	10	7 (–6)	5 (0)	0
2	11	10 (–7)	7 11	6 (–8)	9 (–7)	–3
3	20	13 (–3)	14 5	5 15	7 (2)	4
4	21	5 1	10 (–1)	6 (–6)	4 20	-1
vj		6	10	1	5

 

Клетка (3, 4) имеет положительную оценку D₃₄ = 2 > 0, следовательно, решение Х₁ не оптимальное, а для клетки строим новый цикл: 0^*-5- -14-1-20-0^* (все вершины цикла, кроме первой, находятся в занятых клетках, углы прямые, число вершин четное). У вершин цикла с соответствующими значениями поставок по правилу чередования знаков ставим знаки (+) и (–), начиная со свободной клетки. У вершин со знаком (–) выбираем минимальный груз q = min[14, 20, 5] = 5.

       

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

Получили новое решение задачи (план перевозок):

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

Значение целевой функции:

(ед.).

Значение целевой функции уменьшилось на 10 ед.

 

Проверка решения Х₂ на оптимальность. Расчет потенциалов для занятых клеток:

u ₁ = 0;

клетка (1, 1): v ₁ = c ₁₁ – u ₁ = 6 – 0 = 6;

клетка (4, 1): u ₄ = c ₄₁ – v ₁ = 5 – 6 = -1;

клетка (1, 2): v ₂ = c ₁₂ – u ₁ = 10 – 0 = 10;

клетка (2, 2): u ₂ = c ₂₂ – v ₂ = 7 – 10 = -3;

клетка (4, 4): v ₄ = c ₄₄ – u ₄ = 4 – (-1) = 5;

клетка (3, 4): u ₃ = c ₃₄ – v ₄ = 7 – 5 = 2;

клетка (3, 3): v ₃ = c ₃₃ – u ₃ = 5 – 2 = 3;

 

Расчет оценок свободных клеток:

D₁₃ = u ₁ + v ₃ - c ₁₃ = 0 + 3 – 7 = –4 < 0,

D₁₄ = u₁ + v₄ - c₁₄ = 0 + 5 – 5 = 0,

D₂₁ = u₂ + v₁ - c₂₁ = – 3 + 6 – 10 = –7 < 0,

D₂₃ = u₂ + v₃ - c₂₃ = – 3 + 3 – 6 = –6 < 0,

D₂₄ = u₂ + v₄ - c₂₄ = – 3 + 5 – 9 = –7 < 0,

D₃₁ = u₃ + v₁ - c₃₁ = 2 + 6 – 13 = –5 < 0,

D₃₂ = u₃ + v₂ - c₃₂ = 2 + 10 – 14 = –2 < 0,

D₄₂ = u₄ + v₂ - c₄₂ = – 1 + 10 – 10 = –1 < 0,

D₄₃ = u₄ + v₃ - c₄₃ = – 1 + 3 – 6 = –4 < 0.

Результаты расчета представлены в распределительной таблице:

 

bj ai		1	2	3	4	ui
		15	16	15	20
1	14	6 9	10 5	7 (–4)	5 (0)	0
2	11	10 (–7)	7 11	6 (–6)	9 (–7)	–3
3	20	13 (–5)	14 (–2)	5 15	7 5	2
4	21	5 6	10 (–1)	6 (–4)	4 15	-1
vj		6	10	3	5

 

Все оценки свободных клеток положительные, следовательно, решение Х₂ оптимально.

Оценка клетки (1, 4) D₁₄ = 0 означает, что задача имеет альтернативные решения.

⇐ Предыдущая567891011121314Следующая ⇒

Поделиться: