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

Y₁ + Z₁ = С₁₁                  Y₃ + Z₂ = С₃₂

(9)

Y₂ + Z₂ = С₂₂                  Y₃ + Z₃ = С₃₃

Y₃ + Z₁ = С₃₁                  Y₃ + Z₄ = С₃₄

 

Положим Y₃ = 0, тогда (9) примет вид:

Y₁ + Z₁ = С₁₁                         Z₂ = С₃₂

(10)

Y₂ + Z₂ = С₂₂                      Z₃ = С₃₃

Z₁ = С₃₁                      Z₄ = С₃₄

Подставляя в (10) соответствующие C_ij и решая систему уравнений, окончательно получим

Y₁ = -3                  Z₁ =  5

(11)

Y₂ = -8                  Z₂ =  8

Y₃ =  0                  Z₃ = 15

Z₄ =  9

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

	(12)

 

Ã_ij = Y_i + Z_j – С_ij

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

Таким образом, пользуясь найденными значениями Y_i и Z_j из (11) и (12), находим оценки всех (m-1)(n-1) небазисных маршрутов

Y₁+Z₂-С₁₁=-3+8-3=2                      Y₂+Z₁-С₃₂=-8+5-1=-4

Y₁+Z₃-С₂₂=-3+15-11=1                   Y₂+Z₃-С₃₃=-8+15-6=1

Y₁+Z₄-С₃₁=-3+9-7=-1                     Y₂+Z₄-С₃₄=-8+9-1=0

Из всех положительных оценок выбирается максимальная, которая соответствует маршруту, вводимому в базис. В нашем случае это маршрут A₁B₂. При решении задачи на максимум выбирается маршрут с максимальной по абсолютной величине отрицательной оценкой.

При отыскании величин Y_i иZ_j, а также оценок r_ij небазисных маршрутов не следует отдельно составлять все необходимые уравнения и решать их. Выполнить все эти вспомогательные вычисления можно непосредственно по таблице, предварительно добавив к ней дополнительный столбец для Y_i и дополнительную строку для Z_j. Так, табл. 3.10 будет выглядеть следующим образом (табл. 3.11)

Таблица 3.11

	B1	B2	B3	B4	ai	Yi
A1	2 6	3	11	7	6	-3
A2	1	0 1	6	1	1	-8
A3	5 1	8 4	15 3	9 2	10	0
bj	7	5	3	2	17 17
Zj	5	8	15	9

Записывается нуль в любую из клеточек столбца Y_i или строки Z_j (вданном случае Y₃ = 0). Пользуясь выражением (8), отыскиваются все оставшиеся значения Y_i и Z_j. С этой целью из всех значений С_3j в заполненных клетках (базисных маршрутов), расположенных в строке A_3,   вычитается значение Y₃ = 0, т.е. получаем значения Z_j (в данном случае все маршруты в этой строке базисные, так что сразу получаем Z₁ = 5 - 0 = 5;  Z₂ = 8 - О = 8 и т.д.). Осталось найти Y₁ иY₂. Находим базисные маршруты, соответствующие этим переменным (в данном случае A₁B₁ и A₂B₂), и, пользуясь соответствующим Z (Z₁ и Z₂), по той же формуле (8) находим Y₁=С₁₁-Z₁=2-5=-3 и Y₂=С₂₂—Z₂=0-8=-8. Таким же образом по соответствующим Y_i и Z_j по формуле (12) для всех пустых клеток (небазисных маршрутов) вычисляются их оценки, которые записываются в пустые клетки. Для того, чтобы эти клетки отличать от базисных клеток, значения оценок обводятся кружком.

Шаг 3.