4.3. Сравнение планов по критерию стоимости

Необходимо подсчитать суммарные затраты на транспортировку (значение целевой функции): W = f (x) =  с_ij x_ij.

Для примеров, рассмотренных в 4.1-4.2, получим:

• для плана, построенного по методу СЗУ:

W_СЗУ = 7  18  +  1  7 + 1  4 + 8  24 + 5  4 + 5  16 + + 7  15 + 9  13 + 9  21 = 840;

• для плана, построенного по методу минимума стоимостей: W_МС = 1  5 + 1  20 + 1  6 + 7  5 + 4  21 + 4  24 + + 7  7 +1  18 + 9  16 = 457.

Лучшим считается план с меньшей суммарной стоимостью перевозок. Для примеров п.п. 4.1-4.2, – это план, составленный по методу минимума стоимостей перевозок: W_МС = 457 < W_СЗУ = 840.

4.4. Проверка лучшего опорного плана на оптимальность

Для проверки плана на оптимальность можно применить метод потенциалов.

Для этого надо ввести так называемые псевдостоимости . Входящие в псевдостоимости величины _i и _j называют потенциалами. Псевдостоимости обладают следующими свойствами:

при x_ij  0 (базисные клетки); (4.1)

при x_ij = 0 (свободные клетки). (4.2)

Кроме того, псевдостоимости могут быть отрицательными.

Для транспортной задачи 4х6 введем величины ₁, ₂, ₃, ₄, соответствующие первым четырем ограничениям, и ₁, ₂, ₃, ₄, ₅, ₆ – остальным ограничениям.

Запишем условия (4.1) для базисных клеток:

 ₁ + ₂ = 1;

₁ + ₄ = 1;

₂ + ₂ = 1;

₂ + ₅ =7;

₂ + ₆ = 4;

₃ + ₃ = 4;

 ₃ + ₅ =7;



(4.3)

₄ + ₁ =1;

₄ + ₅ =9.

Запишем условия (4.2) для свободных клеток:

 ₁ + ₁  7;

₁ + ₃  8;

₁ + ₅  5;

₁ + ₆  3;

₂ + ₁  7;

₂ + ₃  8;

₂ + ₄  5;

₃ + ₁  3;

₃ + ₂  7;

₃ + ₄  5;

 ₃ + ₆  5;

₄ + ₂  2;



(4.4)

₄ + ₃  4;

₄ + ₄  9;

₄ + ₆  9.

Система (4.3) состоит из 9 уравнений и содержит 10 переменных: . Поскольку число независимых переменных в данной системе равно 4 + 6  1 = 9, то одна переменная из множества  или  свободная. Пусть это будет ₁. Положив ₁=0, получим: ₁ = 0, ₂ = 0, ₃ =2, ₄ = 4, ₁  = –3, ₂ =1, ₃ = 2, ₄ = 1, ₅ = 5, ₆ = 4. Составим таблицу перевозок, соответствующую данному решению (табл. 4.7).

Полученное решение ₁, ₂, ₃, ₄, ₁, ₂, ₃, ₄, ₅, ₆ подставляем в систему (4.4), т.е. в пустые клетки. Если ограничения системы (4.4) являются верными неравенствами при найденном решении, то проверяемый допустимый план исходной задачи является оптимальным, иначе  план не оптимален, и его надо улучшать.

Из табл. 4.7 видно, что при данном решении не выполняются четвертое, одиннадцатое, двенадцатое и тринадцатое неравенства системы (4.4) – им соответствуют клетки А₁В₆, А₃В₆, А₄В₂, А₄В₃. Это значит, что полученное решение не оптимально, его необходимо улучшить.

Таблица 4.7

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

	1 = –3	2 = 1	3 = 2	4 = 1	5 = 5	6 = 4
1 = 0	–3  7	1 = 1	2  8	1 = 1	5  5	4  3
		5		20
– 2 = 0	–3  7	1 = 1	2  8	1  5	5 = 5	4 = 4
		6			5	21
3 = 2	–1  3	3  7	4 = 4	3  5	7 = 7	6  5
			24		7
+ + – 4 = 4	1 = 1	5  2	6  4	5  9	9 = 9	8  9
	18				16