Занесем рассчитанные потенциалы в таблицу 5. подсчитаем оценки свободных клеток, полагая что для них

=

Первый опорный план является не оптимальным, так как <0 и <0, поэтому переходим к его улучшению. Выбираем максимальную по модулю оценку свободной клетки - = =3.

5. Для клетки построим цикл перераспределения груза. Для этого в перспективную клетку поставим знак +, а в ос­тальных вершинах многоугольника чередующиеся знаки -,+,-

Затем из чисел , стоящих в минусовых клетках, выбираем наименьшее, т.е. min{2,4}=2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из стоящих в минусовых клетках. В результате получим новый опорный план II.

План II

Таблица 6

					Потенциалы
=4	=6	=8	=8
		1 4		4 2
		+		2
Потенциалы

6. Определяем значение целевой функции:

(руб.)

7. Число занятых клеток в II плане 7, следовательно план невырожденный.

8. Проверяем оптимальность плана методом потенциалов для этого находим потенциалы и занятым клеткам, полагая = 0:

Затем рассчитаем оценки свободных клеток:

План, полученный в таблице 6, не оптимальный, так как <0 и <0.

9. Проводим улучшение плана II путем перераспределения грузов. В качестве перспективной клетки для загрузки выбираем , в которую записываем +, затем строим цикл перераспределения:

- + + -

4 2 2 4

2 2 0

Груз перераспределения равен:

Это единственная положительная оценка, поэтому строим цикл для клетки =min (4,2)=2.

Перераспределив груз, получаем новый план III.

План III Таблица 7

					Потенциалы
=4	=6	=8	=8
		1 2 -		4
		4		2
Потенциалы

10. Число занятых клеток 7, а должно быть m+n-1=7, следовательно план III невырожденный.

11. Вычислим значение целевой функции:

12. Проверяем оптимальность плана III методом потенциалов.

Находим потенциалы по занятым клеткам:

Проверим оценку свободных клеток:

План не оптимальный.

13. Проводим улучшение плана III путем перераспределения груза. В качестве перспективной клетки для загрузки выбираем , в которую записываем +, затем строим цикл перераспределения:

- + + -

2 4 6

2 2

Определяем груз перераспределения = min(2;2) = 2, после проведения операции перераспределения получаем план IV.

План IV

Таблица 8

					Потенциалы
=4	=6	=8	=8
		0
Потенциалы

14. План получается вырожденный поскольку в минусовых клетках цикла находятся два одинаковых минимальных объе­ма груза 2. При перераспределении две клетки и оказались свободными, поэтому число занятых клеток б будет меньше, чем m+n-1=7. Для продолжения решения в одну из освободившихся клеток записываем нуль т.к. тариф С₁₁ меньше С₂₃.

15. Вычисляем значение целевой функции;

Проверяем оптимальность плана IV методом потенциалов. Находим потенциалы по занятым клеткам:

Проверим оценку свободных клеток:

Поскольку все оценки больше или равны нулю, то план оптимален.

тыс. руб.

Анализ плана. Из первой базы необходимо весь груз напра­вить в третий магазин, из второй базы направить в первый и второй магазин в количестве 2 ед. и 6 ед., а груз с третьей базы следует вывозить в первый и второй магазин в количестве 2 и 8 ед. соответ­ственно. При этом плане потребность третьего магазина остает­ся неудовлетворительной в размере 2 ед. Общая стоимость достав­ки груза потребителям будет минимальной и составлять 78 тыс. руб. Так как оценка свободной клетки , то задача имеет множество оптимальных планов.

КОНТРОЛЬНЫЕ ВОПРОСЫ