[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4]

Распределительный метод решения транспортной задачи

Задача 7.7

Найти оптимальное распределение поставок из задачи 7.1 Решение. Начнем с базисного распределения поставок, полученного в задаче 7.3. Как было установлено (см. задачу 7.5),данное распределение не оптимально. Оценка свободной клетки - это коэффициент при соответствующей свободной переменной в выражении линейной функции. Учитывая результат задачи 7.6, имеем F = 810 - x13 + 3x31 + 5x22 - x11. Значение F0 = 810 для данного распределения поставок найдено в задаче 7.3. Далее поступаем так, как поступили бы, решая задачу симплексным методом: переменную x13, коэффициент при которой отрицателен, будем переводить в основные (базисные) переменные. Переменная x13 начинает возрастать от нуля. Как было показано в разд. 7.3, перевод поставки в свободную клетку вызывает перераспределение поставок (передвижение поставки по циклу). Означенный цикл пересчета для клетки (1,3) показан на рис. 7.3. Рис. 7.3 Подобно тому, как это было в симплексном методе, увеличиваем поставку x13 в клетке (1,3) до тех пор, пока поставка в одной из заполненных клеток не станет равной нулю (дальнейшее увеличение x13 уводит в область недопустимых решений). Эта клетка принадлежит, конечно, циклу, построенному на рис. 7.3 для клетки (1,3). Найдем ее. Если в клетку (1,3) передать поставку, равную Z, то поставка в клетках цикла со знаком "+" увеличится на Z, а в клетках со знаком "-" - уменьшится на Z.. Поэтому искомая клетка находится среди клеток цикла, имеющих знак "-". Более того, она имеет минимальную поставку среди таких клеток. Так как (см. рис. 7.3) min{60,40} = 40, то в нашем случае - это клетка (3,3), и для обнуления поставки в этой клетке по циклу следует передать 40 единиц груза, т.е. поставка, передаваемая по циклу, определяется как минимум среди поставок в клетках цикла со знаком "-". После этого клетка (1,3) считается заполненной, а клетка (3,3) - свободной. В клетках со знаком "+" цикла поставка увеличивается на передаваемую поставку: поставка клетки (3,2) станет равной 90 единицам, поставка клетки (1,3) - 40 единицам. Аналогично в клетках со знаком "-" поставка уменьшится на передаваемую поставку, например, поставка клетки (1,2) станет равной 20 единицам, что видно из табл. 7.12. Нетрудно доказать, что вновь полученное распределение поставок - базисное. И вновь возникает вопрос об оптимальности базисного распределения поставок - круг решения замкнулся. Найдем оценки свободных клеток (матрицу оценок) распределения поставок. Для этого, как и прежде, подберем потенциалы так, чтобы коэффициенты затрат заполненных клеток стали равными нулю (см. табл. 7.12). Тогда матрица оценок примет вид (7.14). Так как среди свободных клеток есть клетка (1,1) с отрицательной оценкой, то найденное распределение не оптимально и передача поставки в клетку (1,1) ведет к уменьшению суммарных затрат на перевозку. Означенный цикл пересчета для клетки (1,1) приведен на рис. 7.4. По правилу, сформулированному выше, поставка, передаваемая по циклу x11= {20, 20, 10} = 10. Передвигая эту поставку по циклу (см. рис. 7.4), приходим к новому распределению поставок (табл. 7.13). Найдя матрицу (7.15) оценок этого распределения, заключаем, что оно оптимально, так как среди оценок свободных клеток нет отрицательных. Суммарные затраты на перевозку этого распределения поставок в денежных единицах составляют: Fmin =1*10+2*10+5*40+1*10+2*110+3*100 =760. Таблица 7.13 Экономия ΔF, достигнутая в результате применения метода перераспределения поставок, составляет в денежных единицах ΔF = Fmin - F0 = 760 - 810 = 50. Знак "-" в данном случае показывает, что при переходе к оптимальному распределению суммарные затраты на перевозку уменьшились.

Замечание 1.
Поставка, передаваемая по циклу, не может быть ни меньше, ни больше минимума поставок клеток цикла со знаком "-". Действительно, в первом случае ни одна из клеток цикла не будет иметь нулевой поставки, а потому общее число заполненных клеток таблицы будет равно m + n и, следовательно, распределение не будет базисным. Во втором случае уходим в область недопустимых решений.

Замечание 2.
Оптимальное распределение поставок, найденное в задаче 7.7 (см. табл.7.13), не единственное, так как среди оценок свободных клеток есть нулевые, например клетка (2,3) в матрице (7.15). Аналогично при симплексном методе решение не единственное, если в выражении линейной функции оптимального решения через неосновные (свободные) переменные коэффициенты при некоторых свободных переменных равны нулю.

Замечание 3.

В некоторых случаях требуется определить изменение затрат ΔFi на перевозку (экономию затрат) для некоторого i-го шага решения (или для каждого из шагов) транспортной задачи. Из экономического смысла оценки свободной клетки следует, что экономия затрат ΔFi, достигнутая на некотором i-м шаге, равна произведению оценки клетки, в которую передается поставка, на передаваемую поставку. Например, при переходе от исходного распределения поставок (см. табл. 7.11) к распределению поставок по табл. 7.12 поставка 40 единиц передается в клетку, оценка которой равна -1. Тогда экономия затрат ΔF1 на первом шаге задачи 7.7 составит ΔF1 = (-1)40 = -40.

Последовательность действий по решению произвольной закрытой транспортной задачи теперь может быть изложена в виде следующего

алгоритма:

1. Для данного базисного распределения поставок подбираем потенциалы строк и столбцов таблицы поставок так, чтобы коэффициенты затрат заполненных клеток стали равны нулю. Составляем матрицу оценок. 2. Если оценки всех свободных клеток неотрицательны, то найденное распределение оптимально - решение закончено. Если среди оценок свободных клеток есть отрицательные, то выбираем одну из них для передачи в нее поставки (для определенности можно брать, например, одну из клеток с наименьшей оценкой). 3. Для избранной свободной клетки строится означенный цикл пересчета. Поставка z, передаваемая по циклу, определяется как минимум среди поставок в клетках со знаком "-". Найденная поставка передвигается по циклу. При этом поставка в клетках цикла со знаком "+" увеличивается на z, а в клетках со знаком "-" уменьшается на z. Клетка, поставка в которой при этом станет равной нулю, будет считаться свободной (далее рассмотрен случай, когда таких клеток несколько), остальные клетки цикла - заполненными. Таким образом, получено новое базисное распределение поставок. 4. Переходим к п. 1 алгоритма.

[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4] [В начало страницы]