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

При проверке плана на оптимальность воспользуемся методом потенциалов.

Каждому поставщику и потребителю поставим в соответствие некоторые числа и , называемые потенциалами, таким образом, чтобы для всех заполненных (базисных) клеток выполнялось равенство:

, (i=1, 2, n; j=1, 2, m). (5)

Количество неизвестных потенциалов составит m+n, а уравнений (1) всего m+n–1. Поэтому один из потенциалов задается произвольно, после чего остальные потенциалы из системы уравнений (5) определяются однозначно. Обычно полагают .

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

, (i=1, 2, n; j=1, 2, m). (6)

Если ввести понятие оценки клетки:

, (7)

то условие (6) оптимальности плана можно сформулировать как условие неотрицательности оценок всех пустых клеток:

. (8)

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

По заполненным клеткам определим потенциалы поставщиков U_i и потребителей V_j, которые будем вписывать справа и внизу транспортной таблицы соответственно.

Положим U₁ =0. Для заполненных клеток запишем условие (5) и найдем неизвестные потенциалы:

(1;3): , откуда V₃=10;

(2;3): U₂ +10 = 12, U₂ = 2;

(3;3): U₃ +10 = 8, U₃ = –2;

(3;1): –2 + V₁= 5, V₁ = 7;

(4;1): U₄ + 7= 2, U₄ = –5;

(4;2): –5+ V₂ = 1, V₂ =6.

Вычислим оценки пустых клеток по формуле (7):

Поскольку среди оценок клеток есть отрицательные, согласно условию (8) построенный план не является оптимальным и может быть улучшен.

3. Улучшение плана.

Если среди оценок свободных клеток построенного плана есть хотя бы одна отрицательная, план может быть улучшен. Среди пустых клеток с отрицательными оценками выбираем клетку с наименьшей величиной и для нее строим цикл пересчета. Одна вершина цикла находится в пустой клетке (i;j), а остальные — в заполненных. В вершинах цикла, начиная с пустой клетки, последовательно расставляем знаки «+» и «–». Cреди клеток, помеченных знаком «–» определяется наименьшее значение перевозки . Внутри цикла происходит перераспределение перевозок: в клетки со знаком «+» добавляется, а из клеток со знаком «–» вычитается величина . Таким образом пустая клетка (i;j) с наименьшей величиной получает поставку ; поставки клеток, не входящих в цикл, остаются прежними.

В результате получаем новый план перевозок. Он может оказаться вырожденным, поэтому нужно следить за тем, чтобы каждый новый план содержал ровно m+n–1 заполненных клеток.

Для нашей задачи среди отрицательных оценок наименьшую оценку имеет клетка (1;2), для нее строим цикл пересчета.

Из клетки (1;2) звено ломаной можно провести только вправо (слева нет заполненной клетки), затем вниз до клетки (3;3) (вершина ломаной не может быть в клетке (2;3), поскольку в этой строке больше нет заполненных клеток). Затем влево до клетки (3;1), далее (4;1), (4;2) и возвращаемся в (4;1). Расставляем чередующиеся знаки «+» и «–» в вершинах ломаной, начиная с вершины в пустой клетке (1;2) (табл. 9).

Таблица 9.

	10 —	3 — +	10 - 9	0
	7 —	8 —	12 8	2
	5 10 -	5 —	8 + 2	-2
	2 2 +	1 9 -	7 —	-5
	7	6	10

Вычислим = min{9;10;9}=9 — количество груза, перераспределяемое внутри цикла. Величина прибавляется к перевозкам в клетках, помеченных знаком «+», и вычитается из перевозок в клетках, помеченных знаком «–». Изменение величины перевозок происходит только в вершинах цикла, остальные значения х_ij остаются прежними.

Новый план Х₂ должен содержать 6 заполненных клеток, в построенном нами плане их всего 5, т.е. план вырожденный. Так получилось потому, клетки (1;3) и (4;2) одновременно стали пустыми. Чтобы снять вырождение плана, надо в одну из этих клеток дать перевозку, равную нулю, тогда клетка станет базисной. Поставим 0, например, в клетку (1;3), эта нулевая поставка переводит свободную клетку в разряд базисных. План Х₂ транспортной задачи представлен в табл.10. (В этой же таблице записаны потенциалы и изображен цикл пересчета, получаемые в дальнейшем).

Таблица 10. План Х₂.

	10 —	3 9	10 0	0
	7 — +	8 —	12 - 8	2
	5 1 ^_	5 —	8 ^+ 11	-2
	2 11	1 —	7 —	-5
	7	3	10

Изменение значения целевой функции можно вычислить как =, где — оценка клетки, для которой построен цикл, — количество перемещаемого по циклу груза.

=+=265+9(-3)=238.

Исследуем план Х₂ на оптимальность.

Вычислим потенциалы U_i и V_j. Положим U₁ =0 и для заполненных клеток (напомним, что клетка (1;3) является заполненной) запишем условие (8.5):

(1;3): , откуда V₃=10;

(1;2): 0+V₂= 3, V₂ = 3;

(2;3): U₂+10 = 12, U₂= 2;

(3;3): U₃ +10= 8, U₃= –2;

(3;1): –2+ V₁= 5, V₁ = 7;

(4;1): U₄+7 = 2, V₁ = –5;

Сделаем оценки пустых клеток:

Для плана X₂ условие оптимальности (8) не выполнено, т.к. клетка (2;1) получила отрицательную оценку, для нее строим цикл пересчета. Расставляем чередующиеся знаки «+» и «–» в вершинах цикла, начиная с вершины (2;1).

Вычислим = min{8;1}=1. Прибавим это значение к величине перевозок в клетках со знакам «+», вычтем из перевозок в клетках со знакам «–». Получим новый невырожденный план X₃, представленный в таблице 11.

Таблица 11. План X₃.

	10 —	3 1	10 8	0
	7 —	8 8	12 —	2
	5 1	5 —	8 11	-2
	2 11	2 —	7 —	-3
	5	3	10

=+=238+1(-2)=236.

Проверим план на оптимальность. Найдем потенциалы, полагая U₁ =0:

(1;3): , откуда V₃=10;

(1;2): 0+V₂= 3, V₂ = 3;

(2;3): U₂+10 = 12, U₂= 2;

(2;1): 2+ V₁= 7, V₁ = 5;

(3;3): U₃ +10= 8, U₃= –2;

(4;1): U₄+5 = 2, U₄= –3.

Вычислим оценки пустых клеток:

Поскольку все оценки неотрицательны, план X₃ является оптимальным.

X₃=,=236.