Построение цикла

Проверка решения на оптимальность

Для всех не занятых ячеек (с нулевым объемом перевозки) вычисляют оценки клеток распределительной таблицы Δij по формуле Δ_ij = С_ij – U_i – V_j, где U_i и V_j берутся из вычислений, выполненных в разделе выше (здесь они вписаны в заголовки таблицы).

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

	V1=2	V2=3	V3=6	V4=10
U1=0	Δ11=0	Δ12=0	Δ13 = 2–0–6 = –4	Δ14=4–0–10 = –6
U2=–1	Δ21=3–(–1)–2 = 2	Δ22=0	Δ23=0	Δ24=1–(–1)–10 = –8
U3=–4	Δ31=4–(–4)–2 = 6	Δ32=3–(–4)–3 = 4	Δ33=0	Δ34=0

Если в получившейся таблице нет отрицательных значений Δ_ij, то план перевозок оптимален и задача решена (переход к шагу 10).

В нашем примере есть отрицательные значения. Наличие отрицательных значений Δ_ij означает, что решение не оптимально.

	B1	B2	B3	B4
A1	Δ11=0	Δ12=0	Δ13=–4	Δ14=–6
A2	Δ21=2	Δ22=0	Δ23=0	Δ24= –8
A3	Δ31=6	Δ32=4	Δ33=0	Δ34=0

Наименьшее отрицательное значение Δ₂₄ = –8 (начальная вершина для цикла перераспределения поставок, о котором см. ниже) отмечено красным цветом.

Допустимые циклы для транспортной задачи.

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

1. Все вершины, кроме начальной, находятся в занятых ячейках таблицы (ячейки с ненулевыми перевозками или «введенные в базис» на шаге 4 (в разделе «Проверка плана на вырожденность» ячейки с нулевой перевозкой — здесь они отмечены в примерах зеленым цветом), при этом охвачены циклом могут быть не все, а лишь некоторые занятые ячейки.

2. В каждой вершине цикла встречаются ровно два звена ломаной линии, причем одна из них находится по строке, а другая — по столбцу. Иначе говоря, они пересекаются под прямым углом.

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

4. Линия может пересекать саму себя, при этом точка пересечения не включается в цикл (исходя из п.2).

	B1, 20 кг	B2, 30 кг	B3, 30 кг	B4, 10 кг
A1, 30 кг	X11=20 кг	Х12=10 кг
A2, 40 кг		Х22=20 кг	(*) Х23=20 кг	(*)
A3, 20 кг			(*) Х33=10 кг	(*) Х34=10 кг

Вершины цикла в этом примере помечены звездочкой (*). Горизонтальные и вертикальные линии, соединяющие вершины, в этом примере не показаны. По вершинам цикла нужно перераспределить объемы, чтобы получить следующее приближение к оптимальному решению задачи, как это показано далее.

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

Дата добавления: 2015-03-29