6. Построение нового опорного плана

В новой таблице значения в ячейках со знаками угла контура получают по правилам:

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

2. В клетках со знаком угла контура «+» выбранное число прибавляется к имеющемуся в этой клетке; в клетках со знаком «-» – выбранное число вычитается от числа, находящегося в этой клетке.

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

В результате получается новое решение.

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

Таблица 24

Вторая таблица транспортной задачи (ден. ед.)

Номер склада (Ai)	Номер магазина (Bj)						Количество груза на складах (ai)	ui
	1		2		3
1	40		70		20		8000		0
		8000
2	10		20		30		5000		-30
		4000		1000
3	30		40		10		10000		-10
				1000		9000
4	30		20		50		7000		30
				7000
Количество груза в магазинах (bj)	12000		9000		9000		30000
vj	40		50		20

Заполнив новую таблицу, проверяем правильность ее заполнения (суммы новых значений по строкам должны быть равны исходным данным a_i и по столбцам – равны b_j).

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

Выпишем решение из новой таблицы 24: х₁₁ = 8000 тонн; х₂₁ = 4000 тонн; х₂₂ = 1000 тонн; х₃₂ = 1000 тонн; х₃₃ = 9000 тонн; х₄₂ = 7000 тонн.

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

Z_min = 40 × 8000 + 10 × 4000 + 20 × 1000 + 40 × 1000 + 20 × 7000 + 10 × 9000 =

= 650000 (ден. ед.).

Проверим оптимальность нового плана, вычислим характеристики пустых клеток: l₁₂ = 70 – (0 + 50) = 20; l₁₃ = 20 – (0 + 0) = 0; l₂₃ = 30 – (-30 + 20) = 40;

l₃₁ = 30 – (-10 + 40) = 20; l₅₁= 50 – (-20+ 10) = 60.

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

Ответ: Наиболее рациональными являются поставки картофеля с минимальными затратами Z_min = 650000 ден. ед. со складов в магазины:

• в первый магазин необходимо перевезти х₁₁ = 8000 тонн картофеля из первого склада и х₂₁ = 4000 тонн картофеля со второго склада;

• во второй магазин необходимо поставить х₂₂ = 1000 тонн картофеля со второго склада, х₃₂ = 1000 тонн – из третьего склада, х₄₂ = 7000 тонн из четвертого;

• в третий магазин следует поставить картофель из третьего склада в объеме х₃₃ = 9000 тонн.