Составление сметы на весь комплекс проектно-изыскательских работ по форме 2П. Модель транспортной задачи в аналитическом виде, страница 7

U_i + V_j  = C_ij                            (8)

Если теперь для всех свободных клеток, т.е. клеток, в которых x_ij = 0, оценки

δij= Ui+Vj-Cij

                    >= 0 при решении задачи на максимум,

<= 0 при решении задачи на минимум, то полученный план является оптимальным. Поскольку в нашем примере необходимо получить максимальную производительность труда (задача решается на максимум), то признаком оптимальности будет δ_ij>=0 для всех свободных клеток.

Согласно табл. 3.5 число потенциалов всегда будет m+n, а число условий (8), из которых они могут быть получены, равно числу базисных клеток, т.е. m+n–1. Поэтому для определения всех потенциалов достаточно задать произвольное значение одного из них. Обычно принимают U₁ = 0. Остальные потенциалы вычисляют по формулам                V_j = C_ij - U_i

илиU_i = C_ij - V_j,

где в правой части C_ij - коэффициент целевой функции базисной (заполненной) клетки (i,j), a U_i и V_j - известные (вычисленные) значения потенциалов.

Если в результате проверки допустимого плана на оптимальность окажется, что для свободных клеток не все δ_ij положительны или равны нулю, следует провести улучшение опорного плана. С этой целью выбирается максимальное по абсолютной величине отрицательное значение δ_ij и, начиная со свободной клетки, соответствующей этому значению, строится цикл пересчета - замкнутый контур с углами поворота на базисных (заполненных) клетках. Углы поворота нумеруют, начиная с исходной клетки (i,j). Затем определяют минимальный ресурс, находящийся в четной вершине, и его величину вычитают из ресурсов, расположенных в четных вершинах, и прибавляют к ресурсам, расположенным в нечетных вершинах.

Для полученного таким образом нового опорного плана вновь вычисляют систему потенциалов и проводят проверку его на оптимальность. Решение продолжается до тех пор, пока в результате проверки на оптимальность все δ_ij окажутся неотрицательными. В этом случае полученный план является оптимальным, и на его основании вычисляется оптимальное значение целевой функции.

Пример

Пусть трудоемкость составляет соответственно Т₁=534, Т₂=670, Т₃=412, Т₄=1072, а реальные значения трудовых ресурсов – R₁=403, R₂=806, R₃=269, R₄=1210.

Матрицу коэффициентов производительности труда, перепишем из условия задачи. Тогда таблица исходных данных будет выглядеть так

Таблица 3.6

	534	670	412	1072
403	2,0	1,0	1,2	1,1
806	1,2	1,4	1,5	1,3
269	1,4	1,3	1,7	1,4
1210	1,6	1,2	1,5	1,5

В табл. 3.7 представлен исходный базисный план, полученный по методу северо-западного угла, и рассчитаны  соответствующие значения потенциалов. Последовательность вычисления U_i и V_j соответствует последовательности вычисления по базисным клеткам базисного плана, т.е. сначала вычисляем V₁ = 2,0 - 0 = 2, затем U₂ = 1,2 - 2,0 = - 0,8, затем V₂ = 1,4 – (-0,8) = 2,2, затем V₃ = 1,5 - (-0,8) = 2,3, затем U₃= 1,7 – 2,3 = -0,6, затем U₄= 1,5 – 2,3 = -0,8, затем V₄= 1,5 – (-0,8) = 2,3. Здесь же подсчитаныU_i и V_j в свободных клетках (вне клеток базисного плана) в верхнем углу справа. Замечаем, что план не является оптимальным, так как имеется оптимальное значение δ₄₁.

Устанавливаем цикл пересчета (помечен пунктиром с нумерацией углов в кружках) и согласно изложенному выше правилу осуществляем этот пересчет, получив значение таб. 3.8

Таблица 3.7

Потребности Ресурсы		Т1	Т2	Т3	Т4	Ui
		537	670	412	1072
R1	403	2.0 403	1.0  2.2	1.2  2.3	1.1  2.3	0
R2	806	1.2   130  2	1.4 670	1.5  5   3	1.3  1.5	-0.8
R3	269	1.4  1.4	1.3  1.6	1.7 269	1.4  1.7	-0.5
R7	1210	1.6  1.2    1   1	1.2  1.4	1.5 138  4	1.5 1072	-0.8
vj		2.0	2.2	2.3	2.3