2. Проверка найденного опорного плана на оптимальность.

Найденное опорное решение проверяют на оптимальность с помощью метода потенциалов или вычисляя ПТЗ - прирост транспортных затрат

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

Строим для каждого нуля плана Х₁ замкнутый цикл пересчета с вершинами в загруженных клетках (ячейках матрицы). Вершинам этого цикла условно приписывают знаки: свободной ячейке (нулевой) «+», следующей по часовой стрелке занятой клетке знак « - » и т.д. чередуя знаки.

Примеры построения циклов (многоугольников с четным количеством вершин):

Находим алгебраическую сумму стоимости перевозки одной единицы товара по схеме контура. Если ПТЗ < 0, то план Х₁ не оптимальный и его надо улучшать, перераспределяя груз по контуру, в котором ПТЗ < 0; составляем новый план Х₂, вычисляем стоимость новых перевозок (они должны уменьшится) и вновь проверяем план на оптимальность до тех пор, пока все ПТЗ станут неотрицательными.

Пример. В трех городах производится однородная продукция в объемах а₁, а₂, а₃ соответственно и поставляется в другие четыре города. Потребности городов-потребителей соответственно b₁, b₂, b₃, b₄ . Известно, что c_ij - цена транспортировки продукции от i - го производителя к j – му потребителю. Определить план самой дешевой транспортировки грузов, если

, , , где С – матрица цен.

Решение. Проверим условие закрытости задачи , т.е. 240 = 240.

1) Изобразим процедуру составления первого опорного плана: построим решетки и используя матрицу себестоимости, (методом минимальной стоимости) выбираем наименьшую стоимость перевозок и начинаем распределять груз:

1 2 3

●				60		40			●	20		40			20	0
				80						80						80
				100						100			●			100
40	60	80	60	240		0	60	80	60	200		0	60	80	40	180

4 5 6

40			20	0		40			20	0		40			20	0
			●	80				●	40	40				40	40	40
	60			40			60	●		40			60	40		40
0	0	80	40	120		0	0	80	0	80		0	0	0	0	0

Составим первый опорный план и определим его стоимость ,

(проверяем, что заполнено 4 + 3 – 1= 6 ячеек в матрице плана)

F(x₁) = 1∙40 + 2∙20 + 8∙40 + 3∙40 + 3∙60 + 6∙40 = 940 (ден. ед.)

2) Проверим план Х₁ на оптимальность:

1 2 3

Х

0

Х

Х

0

Х

Х

Х

Х

Х

Х

Х

0

Х

Х

Х

Х

Х

Х

Х

Х

птз: 3-2+3-8+6-3= -1 птз: 4-2+3-8= -3 птз: 4-1+2-3= 2

4 5 6

Х

Х

Х

Х

Х

Х

0

Х

Х

Х

Х

Х

Х

Х

Х

0

Х

Х

Х

Х

0

птз: 5-8+6-3= 0 птз: 2-1+2-3+8-6= 2 птз: 7-3+8-6= 6

Т.к. по 2-му контуру имеем наименьшее отрицательное птз, то перераспределяем груз по контуру 2. Из отрицательных углов вычитаем min(20, 40) = 20, в положительные углы добавляем 20:

0 20 20 0

+ – – +

40 40 20 60

Составим второй опорный план и определим его стоимость ,

F(x₂) = 1∙40 + 4∙20 + 8∙20 + 3∙60 + 3∙60 + 6∙40 = 880 (ден. ед.)

3) Проверим план Х₂ на оптимальность:

1 2 3

Х

0

Х

Х

Х

0

Х

Х

Х

Х

Х

Х

0

Х

Х

Х

Х

Х

Х

Х

Х

птз: 3-4+3-0-3= 2 птз: 2-4+8-3= 3 птз: 4-1+4-8= -1

4 5 6

Х

Х

Х

Х

Х

Х

0

Х

Х

Х

Х

Х

Х

Х

Х

0

Х

Х

Х

Х

0

птз: 5-8+6-3= 0 птз: 2-1+4-6= - 1 птз: 7-6+8-3 = 6

Т.к. по 3 контуру имеем отрицательное птз, то перераспределяем груз по контуру 3:

40 20 20 40

– + + –

0 20 20 0

Составим третий опорный план и определим его стоимость ,

F(x₃) = 1∙20 + 4∙40 + 4∙20 + 3∙60 + 3∙60 + 6∙40 = 860 (ден. ед.)

3) Проверим план Х₃ на оптимальность:

1 2 3

Х

0

Х

Х

Х

0

Х

Х

Х

Х

Х

Х

Х

0

Х

Х

Х

Х

Х

Х

Х

птз: 3-4+6-3= 2 птз: 2-1+4-3= 2 птз: 5-4+1-4+6-3 = 1

4 5 6

Х

Х

Х

Х

Х

Х

Х

0

Х

Х

Х

Х

Х

Х

Х

0

Х

Х

Х

Х

0

птз: 8-4+1-4= 1 птз: 2-1+4-6= - 1 птз: 7-6+4-1+4-3 = 5

Т.к. по 5 контуру имеем отрицательное птз, то перераспределяем груз по контуру 5:

20 40 0 60

– + + –

0 40 20 20

Составим четвертый опорный план и определим его стоимость ,

F(x₄) = 4∙60 + 4∙20 + 3∙60 + 2∙20 + 3∙60 + 6∙20 = 840 (ден. ед.)

4) Проверим план Х₄ на оптимальность:

1 2 3

0

Х

0

Х

Х

0

Х

Х

Х

Х

Х

Х

Х

Х

Х

Х

Х

Х

Х

Х

Х

птз: 1-2+6-4= 1 птз: 3-3+6-4 = 2 птз: 2-3+4-2+6-4 = 3

4 5 6

Х

Х

Х

Х

0

Х

Х

0

Х

Х

Х

Х

Х

Х

Х

Х

Х

Х

Х

Х

0

птз: 5-4+2-3 = 0 птз: 8-4+2-6 = 0 птз: 7-3+4-2 = 6

Т.к. все ПТЗ неотрицательные делаем вывод, что план оптимальный.

ОТВЕТ: F_min = F(x₄) = 840 (ден. ед.)

6