Исходный опорный план, построенный методом двойного предпочтения

Станция Отправления	Избыток порожних вагонов	Станция назначения и недостаток порожних вагонов
		B1=65	B2=35	B3=50	B4=30	B5=45	B6=35	B7=40
А1	100	46 40	36*	51 45	43	48 15	54	41
А2	100	40 * 25	35	46	42	46	28** 35	37* 40
А3	60	44	47	40	34** 30	37** 30	57	45
А4	40	45	29** 35	38* 5	38	42	52	42

Значение целевой функции составит:

L = 46*40+40*25+29*35+51*45+38*5+34*30+48*15+37*30+28*35+37*40 = 11650 ваг-км

Как видно из приведенных расчетов наименьшее значение целевой функции (суммарный пробег порожних вагонов) получено при построении начального опорного плана методом наименьшего критерия в строке (L = 11310 ваг-км). Так как целью данной задачи является получение минимального суммарного пробега порожних вагонов, то для дальнейшего рассмотрения выбирается исходный опорный план, построенный именно этим методом.

Алгоритм решения транспортной задачи закрытого типа, представленной в матричной форме, без ограничений пропускной способности методом потенциалов

1. Исходный опорный план проверяется на условие "вырождения".

Согласно теореме Данцига количество занятых клеток в оптимальном плане не должно превышать суммарного числа строк и столбцов (суммы количества пунктов отправления и назначения):

К_з  m + n – 1 ,

где К_з – число занятых клеток; m – число строк матрицы (пунктов отправления); n – число столбцов (пунктов назначения).

Естественно, этому же условию должен отвечать исходный опорный план. Если это условие не выполняется, то исходный опорный план составлен неверно.

Если К_з = m + n – 1 , задача решается обычным порядком.

Если К_з < m + n – 1 , задача называется "вырожденной" и распадается на несколько самостоятельных задач. Чтобы этого избежать, назначаются дополнительные фиктивные перевозки (перевозки равные 0).

В нашей задаче 9 < 4+7-1, задача является "вырожденной". Для устранения “вырождения” назначаем фиктивную перевозку в клетку на пересечении строки 2 и столбца 2 (табл. 7).

Таблица 7

Станция Отправления	Избыток порожних вагонов	Станция назначения и недостаток порожних вагонов
		B1=65	B2=35	B3=50	B4=30	B5=45	B6=35	B7=40
А1	100	46	36 35	51	43 25	48	54	41 40
А2	100	40 65	35 0	46	42	46	28 35	37
А3	60	44	47	40 10	34 5	37 45	57	45
А4	40	45	29	38 40	38	42	52	42

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

Таблица 8

Станция Отправления	Избыток порожних вагонов	Станция назначения и недостаток порожних вагонов							Ui
		B1=65	B2=35	B3=50	B4=30	B5=45	B6=35	B7=40
А1	100	46	36 35	51	43 25	48	54	41 40	100
А2	100	40 65	35 0	46 н2	42	46	28 35	37 н3	101
А3	60	44	47	40 10	34 5	37 45	57	45	109
А4	40	45	29	38 40	38	42	52	42	111
Vj		141	136	149	143	146	129	141

Значение целевой функции составит:

L =40*65+36*35+35*0+40*10+38*40+43*25+34*5+37*45+28*35+41*40=11310

Проверка на оптимальность. План считается оптимальным, если соблюдаются следующие условия:

V_j - U_i Ј c_ij, при x_ij = 0 (клетка свободна),

                                                                                                                                     

V_j - U_i = c_ij, при x_ij > 0 (в клетке назначена перевозка).

В табл. 8 для клетки (1,3) 149 – 101 = 48 >46, т.е. нарушение в данной клетке составляет 2. Для клетки (2, 7) 141 – 101 = 410 >37, нарушение 3. Для остальных свободных и занятых клеток условия оптимальности выполняются. Так как в матрице перевозок имеются нарушения условий оптимальности, данный начальный опорный план не является оптимальным. Он может быть улучшен за счет клеток с нарушениями.

Таблица 9

Станция Отправления	Избыток порожних вагонов	Станция назначения и недостаток порожних вагонов							Ui
		B1=65	B2=35	B3=50	B4=30	B5=45	B6=35	B7=40
А1	100	46	36 35	51	43 25	48	54	41 40	100
А2	100	40 65	35	46 0	42	46	28 35	37 н1	103
А3	60	44	47	40 10	34 5	37 45	57	45	109
А4	40	45	29	38 40	38	42	52	42	111
Vj		143	136	149	143	146	131	141

Значение целевой функции составит:

L =40*65+36*35+46*0+40*10+38*40+43*25+34*5+37*45+28*35+41*40=11310

Станция Отправления	Избыток порожних вагонов	Станция назначения и недостаток порожних вагонов							Ui
		B1=65	B2=35	B3=50	B4=30	B5=45	B6=35	B7=40
А1	100	46	36 35	51	43 25	48	54	41 40	100
А2	100	40 65	35	46	42	46	28 35	37 0	104
А3	60	44	47	40 10	34 5	37 45	57	45	109
А4	40	45	29	38 40	38	42	52	42	111
Vj		144	136	149	143	146	132	141

Полученный новый план перевозок (табл.10) имеет конечное значение целевой функции:

L =40*65+36*35+46*0+40*10+38*40+43*25+34*5+37*45+28*35+41*40=11310

Условие “вырождения” выполняется. После присвоения потенциалов всем столбцам и строкам новой матрицы (табл.10) нарушений условия оптимальности нет, значит данный план перевозок является оптимальным.