Метод потенциалов

Теорема. Если план X^*=(x_i^*_j) транспортной задачи является оптимальным, то ему соответствует система из m+n чисел Ui^*  и V_j^*_, удовлетворяющих условиям

U_i^*+V_j^*=C_ij     для    x_i^*_j>0

U_i^*+V_j^*<=C_ij     для    x_i^*_j>0

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

{spoiler=Подробнее}

Числа U_i^* и V_j^* называются потенциалами соответственно поставщиков и потребителей.

Д о к а з а т е л ь с т в о.  Транспортную задачу минимизации линейной функции

при ограничениях

можно рассматривать как двойственную некоторой исходной задачи линейного программирования, условия которой получают по общей схеме, рассмотренной ранее в двойственной задаче, если каждому ограничению вида х_i1+х_i2+ ... +х_in =а_i  в исходной задаче соответствует переменная U_i(i=1,2, ...,m), а каждому ограничению вида х_1j +х_2j + ... +x_mj=b_j- переменная V_j(j=1,2,...,n),а именно максимизировать линейную функцию

f=åа_iU_i +åb_jV_j

 при ограничениях

  U_i + V_j £ C_ij.

 План Х^*  -оптимальный план двойственной задачи, поэтому план Y^* = (U_i^*, V_j^*) является планом исходной задачи и на основании теоремы двойственности

maxf=minZ

или

На основании теоремы двойственности  получаем, что  ограничения исходной задачи, соответствующие положительным компонентам оптимального плана двойственной задачи, удовлетворяются как строгие равенства, а соответствующие компонентам, равным нулю, - как неравенства, т.е.

U^*_i+V^*_j=C_ij для x_i^*_j>0,

U^*_i+V^*_j=C_ij для x_i^*_j=0.

На основании доказанной теоремы для того чтобы первоначальный опорный         план был оптимальным, необходимо выполнение следующих условий:

а) для каждой занятой клетки сумма потенциалов должна быть равна стоимости перевозки, стоящей в этой клетке;

U_i+V_j=C_ij

б)  для каждой незанятой клетки сумма потенциалов должна быть меньше или равна стоимости единицы перевозки, стоящей в этой клетке:

U^*_i+V^*_j£C_ij.

1. Построение  системы потенциалов. Для построения системы потенциалов используется условия

U_i+V_j=C_ij,

где С_ij - стоимость перевозки единицы груза занятой клетки в i-й строке и j-ой столбце.

1. Проверяется выполнения условий оптимальности для незанятых клеток матрицы планирования.
2. Выбирается клетку в которую необходима послать перевозку.

Транспортная задача линейного программирования решается на минимум линейной функции, поэтому алгоритм ее решения также следуют общим  принципам алгоритма симплексного метода решения задач на минимум.

{/spoilers}