Определение оптимального плана транспортной задачи

Наиболее распространенным является метод потенциалов.

Теорема. Если для некоторого опорного плана X*=[x*_ij] транспортной задачи существуют числа и такие, чтопри x_ij>0 и при x_ij=0 для всех и , то Х* - оптимальный план.

Числа и называются потенциалами, соответственно, пунктов отправления и пунктов назначения.

Эта теорема позволяет построить алгоритм решения транспортной задачи:

1. Находят опорный план транспортной задачи одним из рассмотренных выше методов.

2. Вычисляют потенциалы пунктов отправления и пунктов назначения, используя соотношение:

1.

где C_ij – тарифы, стоящие в заполненных клетках таблицы условий транспортной задачи.

В результате получают систему линейных уравнений, состоящих из (m+n-1) уравнений с (m+n) – неизвестными, т.е система будет неопределенной.

Для ее решения одной из переменных придают произвольное значение и последовательно находят остальные неизвестные (например, считают α₁=0)

3. Для всех свободных клеток находят числа α_ij из условия:

2.

Если среди чисел α_ij нет положительных, т.е все α_ij≤0, то найденный опорный план является оптимальным.

Если для некоторой свободной клетки α_ij>0, то план можно улучшить.

4. Построение улучшенного плана:

Из всех чисел α_ij>0выбирают максимальное и клетку, соответствующую этому числу, необходимо заполнить. Это можно сделать с помощью циклического контура(цикла)

Примеры циклов:

Если ломаная, образующая цикл, пересекается, то точка самопересечения вершиной не является (рис. б)

Если опорный план построен правильно, то для любой свободной клетки можно построить только один циклический контур.

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

Его ведут по следующим правилам:

1. Каждой клетке, входящей в циклический контур, присваивают определенный знак, причем, свободной клетке знак «+», а остальным поочередно «-», «+».

2. В свободную клетку переносят меньшее из чисел х_ij, стоящих в «-» клетках. Это же число прибавляют к числам, стоящих в «плюсовых» клетках и вычитывают из чисел, стоящих «минусовых» клетках. В результате выбранная свободная клетка станет занятой, а «минусовая» клетка, в которой стояло минимальное из чисел х_ij, – свободной.

При сдвиге по циклу пересчета, число занятых клеток должно остаться неизменным, равным (m+n-1).

Если в «минусовых» клетках имеется два или более одинаковых числа х_ij, то освобождают одну клетку, а остальные считают условно занятыми с нулевыми перевозками.

При построении опорного плана или в процессе решения задачи может быть получен вырожденный план. Чтобы избежать в этом случае зацикливания, необходимо привести план к невырожденному, для чего свободные клетки (желательно с минимальными тарифами перевозок) заполняют сколь угодно малыми перевозками, т.е в этих клетках ставят, например, число Е=0,001 и считают клетки условно занятыми. При определении стоимости перевозок и в оптимальном плане принимают Е=0.

3. Улучшенный план вновь проверяют на оптимальность, т.е переходят к пункту 2.