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

j=1

i=1

Например, если  S a_i = S b_j  = 10 тонн, то R₁,R₂ и R₃ будут соответственно равны 3 т, 1 т и 6 т, a Т₁,Т₂,Т₃,Т₄ будут соответственно равны 4 т, 3 т, 2 т и 1 т.

Пример

Имеется 3 пункта R_i с запасом r_i леса для постройки сигналов; соответственно 6, 1 и 10 м³; имеется 4 пункта T_j, в которых строятся наземные триангуляционные знаки, с потребностями t_j в лесе соответственно 7, 5, 3 и 2. Даны также стоимости перевозок C_ij единицы груза (1 м³) из пункта А_j в пункт В_j, которые помещены в табл. 3.9 в левых верхних углах каждой клетки.

ШАГ 1.

Выбирается набор m+n-1 маршрутов по методу минимального элемента матрицы затрат C_ij. С этой целью находится минимальный элемент матрицы, в нашем случае элемент (A₂B₂) с С₂₂ = 0, и по этому маршруту, т.е. A₁B₂, направляется максимально возможный поток, в нашем случае 1.

Таблица 3.9

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

Отметим правило загрузки, маршрутов. По данному маршруту всегда направляется такой поток груза, который или полностью удовлетворил данного потребителя, или полностью исчерпал весь запас груза в этом пункте. Далее находятся минимальные элементы из оставшихся, в нашем случае - элементы (A₂B₁) и (A₂B₄) с С₂₁ = С₂₄ = 1.

По этим Маршрутам не может быть направлен никакой поток, так как запас в пункте A₂ исчерпан - весь направлен в пункт B₂

Таблица 3.10

	(Z1) B1	(Z2) B2	(Z3) B3	(Z4) B4	ai
(Y1) A1	2 6	3	11	7	6
(Y2) A2	1	0 1	6	1	1
(Y3) A3	5 1	8 4	15 3	9 2	10
bi	7	5	3	2	17 17

Выбирается Следующий минимальный элемент из оставшихся, т.е. (A₁B₁) с С₁₁= 2. Направляем по маршруту A₁B₁ максимально возможный поток, т.е. 6. Действуя подобным образом, находятся все m+n-1 базисных маршрутов, которые и составляют исходный опорный план. В связи с тем, что при нахождении исходного и всех последующих опорных планов количество базисных маршрутов должно быть именно m+n-1, при недостаточном или избыточном количестве базисных маршрутов в первом случае добавляются любые недостающие маршруты с нулевым потоком, во втором - проверяется правильность распределения потоков по маршрутам, В табл. 3.10 показан исходный опорный план. Под таблицей подсчитано значение целевой функции, т.е. общая стоимость перевозок по этим маршрутам.

Шаг 2.

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

При этих значениях переменных (Y₁ и Z₁) двойственной задачи находятся по исходному опорному плану из уравнений

Y₁ + Z₁ = С₁₁

С этой целью составляется m+n-1 уравнений двойственной задачи; в нашем случае 6 уравнений, содержащих 7 неизвестных. При решении данной неопределенной системы любая из входящих в нее переменных принимается равной нулю, а остальные находятся обычным способом из решения 6 уравнений двойственной задачи, соответствующих базисным маршрутам с 7 неизвестными.