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

Для определения оптимального плана транспортной задачи также разработано несколько методов. Наиболее часто используются метод потенциалов и метод дифференциальных рент.

1. Метод потенциалов. Общий принцип определения оптимального плана методом потенциалов прост: сначала находят опорный план, а затем его улучшают до получения оптимального плана. Для определения опорного плана пользуются одним из методов, описанных выше.

Если для некоторого опорного плана транспортной задачи существуют такие числа a₁, a₂,.., a_m, b₁, b₂,.., b_n, что

b_j  a_i = c_ij при x_ij > 0

c_ij  b_j - a_i при x_ij = 0

для всех i = 1,..., m и j = 1,..., n, то он является оптимальным планом транспортной задачи. Числа a_i и b_j (i=1,..., m; j=1,..., n) называются потенциалами соответственно пунктов назначения и пунктов потребления.

Сформулированное правило позволяет построить алгоритм нахождения решения транспортной задачи. Он состоит в следующем. Для каждого из пунктов отправления и назначения определяют потенциалы a_i и b_j (i=1,..., m; j=1,..., n ). Эти числа находят из системы уравнений b_j – a_i =c_ij, где c_ij — тарифы, стоящие в заполненных клетках таблицы. Поскольку число неизвестных превышает на единицу число уравнений, одно из неизвестных можно положить равным произвольному числу, например, a_i = 0, и найти последовательно значения остальных неизвестных.

После того, как все потенциалы найдены, для каждой из свободных клеток определяют числа a_ij = b_j – a_i – c_ij. Если среди них нет положительных, то найденный опорный план является оптимальным. Если же для некоторой свободной клетки a_ij>0, то необходимо перейти к новому опорному плану. Для этого рассматривают все свободные клетки, для которых a_ij > 0, среди данных чисел выбирают максимальное и производят сдвиг по циклу пересчета.

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

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

2) в данную свободную клетку переносят меньшее из чисел xij, стоящих в минусовых клетках. Это же число прибавляют к числам, стоящим в плюсовых клетках, и вычитают из чисел, стоящих в минусовых клетках. Минусовая клетка с минимальным из чисел xij считается свободной. Таким образом происходит переход к новому опорному плану.

В результате для решаемой задачи оптимальный план перевозки продукции выглядит так:

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

2. Метод дифференциальных рент. При нахождении решения транспортной задачи методом дифференциальных рент сначала наилучшим образом распределяют между пунктами назначения часть груза и на последующих операциях постепенно уменьшают общую величину нераспределенных поставок. На первом шаге в каждом столбце находят минимальный тариф, и клетки, в которых стоят указанные числа, заполняют максимально возможными числами. В результате получено некоторое распределение поставок груза в пункты назначения.

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

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

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

	В1	B2	В3	В4	Запасы	Недостаток(-), избыток(+)
А1	11	4 60	12	10 50	110	0
A2	4 20	6	2 170	12	190	0
А3	4 60	6	9	10 30	90	0
Потребности	80	60	170	80
Разность

,

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

3. Симплексный метод. Два предыдущие метода решения были разработаны непосредственно для транспортной задачи. Решение любой задачи линейного программирования, к которым относится и транспортная, можно также найти симплексным методом. Этот метод решения задачи линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает ( при условии, что данная задача имеет оптимальный план, и каждый её опорный план является невырожденным). Указанный переход возможен, если известен какой  нибудь исходный опорный план. Считается, что это наиболее эффективный способ решения, но по сравнению с остальными он самый трудоемкий и громоздкий.

Данная задача была решена таким способом за 10 шагов, при этом 5 раз совершался переход от одной симплекс таблицы к другой. Были получены следующие результаты:

,

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