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

Учитывая условия баланса наличия и потребления

,

имеем a ₁ - b ₂ -…- b_n = b ₁ - a ₂ - … - a_m.

Таким образом, оба полученных выражения для x ₁₁ (1.35) и (1.36) совпадают.

В результате система (1.25) и (1.26) разрешена относительно неизвестных, стоящих в первой строке и первом столбце матрицы перевозок, и число этих неизвестных равно r=m+n-1.

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

Продемонстрируем это на примере. Пусть на матрице стоимостей

C =

определен оптимальный план перевозок X^опт и значение целевой функции F^опт:

F^опт = .

Изменим в матрице стоимостей С k - строку на величину q, т.е.

C^* = .

Подсчитаем стоимость перевозок на оптимальном плане старой задачи для новой матрицы стоимостей:

F^* = + = F^опт + = F^опт + q_k a_k = =F^опт + const.

Здесь = a _k.

По условию F^опт - это минимальное значение целевой функции, F* отличается от нее на некоторую постоянную величину, значит, и F* имеет минимальное значение. Что и требовалось доказать. Можно так же показать, что теорема останется справедливой и для любого столбца, и вообще для любых строк и столбцов. При этом строки и столбцы можно изменять на любые величины, но обязательно одинаковые для каждого столбца и каждой строки.

Обозначим через U_i потенциалы станций отправления A_i, а через V_j - потенциалы станций назначения B_j.

Тогда условия оптимальности принятого плана могут быть записаны так:

- если загруженная клетка (ij) определяет какой - либо маршрут перевозки

U_i + V_j + C_ij = 0; (1.37)

- если незагруженная клетка (ij) не определяет маршрут перевозки

U_i + V_j + C_ij ; (1.38)

- если среди незагруженных клеток (ij) имеются отрицательные

U_i + V_j + C_ij < 0. (1.39)

то за счет перераспределения грузопотоков можно уменьшить стоимость перевозок. Следовательно, план не является оптимальным и потенциалы используются для определения оптимальности плана перевозок.

В ТЗ потенциалы имеют простой экономический смысл. Они выступают как локальные поясные цены (или наценки к единой цене), создающие заинтересованность в правильном направлении перевозок. Если какая-то перевозка выполняется, то цена на станции назначения должна быть равна цене на станции отправления плюс транспортные издержки, в остальных случаях цена Vj не может быть больше, чем U_i + C_ij, так как груз на станции j можно было получить по той же цене привозя его с затратами C_ij из станции i. Таким образом, в обоих указанных случаях разность цен не превышает затрат по перевозке.