7. Проверка базисного плана, составленного методом аппроксимации (Фогеля) на минимальное значение функции цели, на оптимальность методом потенциалов. Улучшение плана до оптимального результата.

Для проверки любого решения на оптимальность используют потенциалы (Ui, Vj) по строкам и по столбцам.

Потенциалы рассчитываются по оценкам занятых клеток.

Ui+Cij=Vj,

где

Ui – потенциал строки,

Cij – оценка занятой клетки,

Vj – потенциал столбца.

Для расчета одному из потенциалов необходимо придать производное число, например, Ui=0

Таблица 10 – Расчет потенциалов.

		В1	В2	В3	В4	Вф	Объем потребл.
	Ui\ Vj	V1=2	V2=3	V3=5	V4=0	V5=-6
А1	U1=0	15 -	2 320	4 -	19 -	0 -	320
А2	U2=-1	3 -	4 780	14 -	19 -	0 -	780
А3	U3=-2	22 -	13 550	5 740	15 140	0 -	1430
А4	U4=1	2	6 -	15 -	3 460	0 -	460
А5	U5=-6	8 200	25 -	11 760	29 -	0 100	1060
Объем пр-ва		200	1650	1500	600		4050 4050

F=28050 руб.

Вывод: Все характеристики свободных клеток удовлетворяют условию оптимальности (Kij<0), следовательно, данное распределение является оптимальным.

Потенциалы необходимы для расчета характеристик свободных клеток Kij

Kij=Vj-Ui-Cij, где

Vj – потенциал столбца,

Ui – потенциал строки,

Cij оценка несвободной клетки.

Характеристики свободных клеток дают информацию о качестве плана. Характеристика отражает величину экономии на 1 груз за счет улучшения плана путем перераспределения данных свободных клеток.

Характеристика свободной клетки используется в качестве признака оптимальности плана. Формальным признаком является при решении задачи на минимум функции цели, отсутствие положительных характеристик.

К11=2-0-15=-13

К12=3-0-2=1

К13=5-0-4=1

К14=0-0-19=-19

К1ф=-6-0-0=-6

К23=5+1-14=-8

К24=0+1-19=-18

К2ф=-6+1-0=-5

К31=2+2-22=-18

К32=3+2-13=-8

К33=5+2-5=2

К34=0+2-15=2

К3ф=-6+2-0=-4

К41=2-1-2=-1

К42=3-1-6=-4

К43=5-1-15=-11

К44=0-1-3=-4

К4ф=-6-1-0=-7

К52=3+6-6=3

К54=0+6-29=-23

Вывод: В данном случае распределение ресурсов методом наилучшего элемента не является наилучшим планом, так как при расчете характеристик свободных клеток присутствуют положительные значения (К12; К13; К33; К34; К52 ).

Необходимо провести улучшение.

Для улучшения плана строится замкнутый контур – цепочка. Замкнутый контур – это многоугольник с прямыми углами, одной из вершин которого является клетка, подлежащая проверке на оптимальность. Остальные вершины контура – показатели занятых клеток.

Правила построения замкнутого контура:

1 Начало замкнутого контура берут в клетке, где не выполняется оптимальность, от нее проводят прямую линию до первой занятой клетки.

2. В занятой клетке делают поворот на 90° и ведут линию до следующей занятой клетки.

3. Повороты в занятых клетках делают до тех пор, пока контур не замкнется в исходной клетке, где не выполняется условие оптимальности.

В полученном контуре в клетке, где не выполняется условие оптимальности, всегда ставится «+», далее по часовой стрелке в вершинах контура расставляют поочередно «-», «+». По контуру перераспределяют наименьший ресурс при знаке минус.

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