Выбор клетки, в которую необходимо послать перевозку

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

Если отождествлять занятые клетки с переменными, входящими в базис, а незанятые - с независимыми, варьируемыми переменными, то в транспортной задаче загрузке (ввод в базис) подлежит та клетка, которой соответствует max[(U_i+V_j)-С_ij].

В рассматриваемом примере mах(1;6;1) = 6, клетку А₂В₄ необходимо сделать занятой. Для этого сначала надо определить, сколько единиц груза может быть в нее перераспределено (аналог – определить максимально допустимое увеличение выбранной независимой переменной).

Построение цикла и определение величины перераспределения груза. Основной принцип перераспределения – неизменность построчных и постолбцовых сумм. Основная задача – построить цикл и найти максимальною величину груза , которую можно было бы перераспределить между клетками цикла без появления отрицательных перевозок. Для этого отмечаем знаком «+» незанятую клетку (А₂В₄), которую требуется загрузить. Это означает, что клетка присоединяется к занятым клеткам. В таблице занятых клеток стало m+n, поэтому появляется цикл, все вершины которого, за исключением клетки, отмеченной знаком «+», находятся в занятых клетках, причем этот цикл единственный.

Отыскиваем цикл (алгоритмически самостоятельная задача) и, начиная движение от клетки, отмеченной знаком «+», поочередно проставляем знаки «-» и «+» (принцип неизменности сумм). Затем находим = min(x_ij), где x_ij - перевозки, стоящие в вершинах цикла, отмеченных знаком «-».

В рассматриваемом примере знаком «-» помечены клетки (А₃В₄), (А₄В₅), (А₂В₂). Отсюда = min(0, 50, 50)=0. Напомним, что определяет, сколько единиц груза можно перераспределить по найденному циклу. Значение записываем в незанятую клетку (А₂В₄), отмеченную знаком «+», двигаясь по циклу, вычитаем из объемов перевозок, расположенных в клетках, которые отмечены знаком «-», и прибавляем к объемам перевозок, находящихся в клетках, отмеченных знаком «+». Если соответствуют несколько минимальных перевозок, то при вычитании оставляем в соответствующих клетках нулевые перевозки в таком количестве, чтобы во вновь полученном опорном плане занятых клеток было m=n- 1.

В рассматриваемом примере нулевую перевозку необходимо переместить в клетку А₂B₄, остальные числа при вычитании и прибавлении нуля, очевидно, не изменятся. В ячейке А₃B₄ ноль, как значимая цифра, отменяется.

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

Таблица 8.7

Поставщики	U	Потребители	Запасы
B1	B2	B3	B4	B5
V1=		V2=		V3=		V4=		V5=
А1	-6		10		7		4	-	1	+	4	a2
U1	-		-				100				100
А2	-1		2	-	7		10	+	6		11	a2
U2	200		50								250
А3	-11		8		5		3		2		2	a1
U3	-		-		-				200		200
А4			11	+	8		12		16	-	13	a2
U4	-		150		100		-		50		300
Спрос		200		200		100		100		250		850

Интересно заметить, что на втором этапе (табл. 8.7) загрузка ячейки А₁В₅ составляет 50 ед. Эти 50 ед. выводят из базы сразу две ячейки А₄В₅, и А₂В₂, то в одной из них, например А₂В₂ устанавливается активный ноль.

Окончательная таблица имеет вид табл. 8.8. Полученный план является оптимальным. Его стоимость равна 4150 ед.

Таблица 8.8

Не нашли, что искали? Воспользуйтесь поиском по сайту: