5. Сравнение результатов решения двух базисных планов

Вывод на минимум: из приведенных выше распределений различными способами мы видим, что распределение методом аппроксимации (Фогеля) дает наиболее выгодный результат с экономической точки зрения, чем метод северо-западного угла и метод наилучшего элемента, следовательно, данное распределение является наилучшим. (28050 руб.)

6. Проверка базисного плана, составленного методом наилучшего элемента на максимальное значение функции цели, на оптимальность методом потенциалов. Улучшение плана до оптимального результата

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

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

Ui+Cij=Vj,

где

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

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

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

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

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

		В1	В2	В3	В4	ВФ	Объем потреб.
	Ui\ Vj	V1=21	V2=12	V3=4	V4=16	Vф=1
А1	U1=0	15 -	2 -	4 220	19 -	1 100	320
А2	U2=-10	3 -	4 -	14 780	19 -	1 -	780
А3	U3=-1	22 200	13 990	5 40	15 -	1 -	1230
А4	U4=-11	2 -	6 -	15 460	3 -	1 -	460
А5	U5=-13	8 -	25 460	11 -	29 600	1 -	1060
Объем пр-ва		200	1450	1500	600	100	3850 3850

F=65170 руб.

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

Kij=Vj-Ui-Cij, где

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

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

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

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

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

К11=21-0-15=6

К12=12-0-2=10

К14=16-0-19=-3

К21=21+10-3=28

К22=12+10-4=18

К24=16+10-19=7

К2ф=1+10-0=11

К34=16+1-15=2

К3ф=1+1-0=2

К41=21+11-2=30

К42=12+11-6=17

К44=16+11-3=24

К4ф=1+11-0=12

К51=21+13-8=26

К53=4+13-11=6

К5ф=1+13-1=13

Вывод: В данном случае распределение ресурсов методом наилучшего элемента не является наилучшим планом, так как при расчете характеристик свободных клеток присутствуют отрицательные значения (К14).

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

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

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

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

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

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

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

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

Таблица 8 – Расчет потенциалов при решении на максимум после улучшения.

		В1	В2	В3	В4	ВФ	Объем потребления
	Ui\ Vj	V1=24	V2=15	V3=7	V4=19	Vф=1
А1	U1=0	15 -	2 -	4 -	19 220	1 100	320
А2	U2=-7	3 -	4 -	14 780	19 -	1 -	780
А3	U3=2	22 200	13 770	5 260	15 -	1 -	1230
А4	U4=-8	2 -	6 -	15 460	3 -	1 -	460
А5	U5=-10	8 -	25 680	11 -	29 380	1 -	1060
Объем пр-ва		200	1450	1500	600	100	3850 3850

F=65830 руб.

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

Наиболее часто совершаются ошибки при расчете потенциалов и характеристик не занятых клеток. Для контроля используют формулу:

∑ Vj*Bj - ∑Ui*Ai=F

∑Vj*Bj-∑Ui*Ai=24*200+15*1450+7*1500+19*600+1*100-0*320+

(-7)*780+2*1230+(-8)*460+(-10)*1060=65830

F=65830

Условие выполняется, следовательно, случайных ошибок не допущено.

Данный план не оптимален, так как при расчете характеристик свободных клеток присутствуют отрицательные значения (К3ф). Вновь производим улучшение плана.

Таблица 9 – Расчет потенциалов при решении на максимум после улучшения.

		В1	В2	В3	В4	ВФ	Объем потребления
	Ui\ Vj	V1=24	V2=15	V3=7	V4=19	Vф=3
А1	U1=0	15 -	2 -	4 -	19 320	1 -	320
А2	U2=-7	3 -	4 -	14 780	19 -	1 -	780
А3	U3=2	22 200	13 670	5 260	15 -	1 100	1230
А4	U4=-8	2 -	6 -	15 460	3 -	1 -	460
А5	U5=-10	8 -	25 780	11 -	29 280	1 -	1060
Объем производства		200	1450	1500	600	100	3850 3850

F=66030 руб.

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