Алгебраические суммы тарифов для всех свободных клеток таблицы 3 оказались положительными. Следовательно, план перевозок, представленный таблицей 3, является оптимальным.
Ответ: При оптимальном плане перевозок потребность заказчика В1 удовлетворяется как базой А1, из которой поступает 140т. так и базой А2, из которой поступает 30т.; потребность заказчика В2 удовлетворяется базами А1, из которой поступает 60т. и А3, из которой поступает 50т.; потребность заказчика В3 удовлетворяет база А1, из которой поступает 100т., а потребность заказчика В4 удовлетворяет база А2, из которой поступает 120т. При этом стоимость перевозок составит
что меньше стоимости перевозки по первоначальному плану (Fнач.= 25650 т.км.) на 1250 т.км.
Пример №2
На трёх базах находится однородный груз. На базе А1 в количестве 22т., на базе А2 в количестве 13т., на базе А3 в количестве 10т. Весь этот груз необходимо развести трём заказчикам так, чтобы стоимость перевозок была наименьшей. Заказчику в пункте В1 должно поступить 20т., в пункте В2 - 15т., в пункте В3 - 10т. груза. В угловых скобках таблицы 4 указаны стоимости перевозки одной тонны груза между базами и заказчиками в тысячах рублей.
Решение
1. Данная задача является сбалансированной. При определении начального плана перeвозок методом северо-западного угла внутренние клетки таблицы 4 примут значения:
Таблица 4
Базы
Заказчики
Запасы на базах
В1
В2
В3
А1
–
А2
–
–
А3
–
–
Потребности заказчика
2. Оптимальность полученного плана исследуется методом потенциалов. Уравнения потенциалов, составленные для базисных клеток таблицы 4, имеют вид:
α1 + β1 = 4,
α1 + β2 = 3,
α2 + β2 = 5.
α3 + β3 = 2.
В четырёх уравнениях оказалось 6 неизвестных. Число неизвестных превышает число уравнений больше чем на 1. В этом случае циклы пересчёта можно построить не для всех свободных клеток данной таблицы. Так, в таблице 4 для клеток (1;3), (2;3), (3;1), (3;2) циклы пересчёта построить нельзя. Тогда в одной из этих клеток (например, в клетке (2;3)) записывается базисная переменная с нулевым значением количества перевозимого груза. Дополненная таким образом таблица 4 принимает вид
Таблица 4¢
Базы
Заказчики
Запасы на базах
В1
В2
В3
А1
–
А2
–
А3
–
–
Потребности заказчика
Теперь из системы пяти уравнений, составленных для базисных клеток таблицы 4¢
α1 + β1 = 4,
α1 + β2 = 3,
α2 + β2 = 5,
α2 + β3 = 3,
α3 + β3 = 2
находятся значения 6-ти неизвестных
α1 = 0, β1 = 4,
α2 = 2, β2 = 3,
α3 = 5, β3 = 1,
при условии, что α1= 0, и алгебраические суммы тарифов для свободных клеток таблицы 4'имеют значения:
s13 = c13 – c'13 = c13 – (α1 + β3) = 1 – 1 = 0,
s21 = c21 – c'21 = c21 – (α2 + β1) = 2 – 6 = – 4,
s31 = c31 – c'31 = c31 – (α3 + β1) = 6 – 5 = 1,
s32 = c32 – c'32 = c32 – (α3 + β2) = 4 – 4 = 0,
Вычисления показывают, что первоначальный план перевозок можно улучшить, производя цикл пересчёта со свободной клеткой (2; 1):
Улучшенный план перевозок представлен в таблице 5.
Исследуем его на оптимальность:
α1 + β1 = 4,
α1 + β2 = 3,
α2 + β1 = 2,
α2 + β3 = 3,
α3 + β3 = 2;
α1 = 0, β1 = 4,
α2 = –2, β2 = 3,
α3 = –3, β3 = 5.
Таблица 5
Базы
Заказчики
Запасы на базах
В1
В2
В3
А1
–
А2
–
А3
–
–
Потребности заказчика
s13 = c13 - c'13 = c13 – (α1 + β3) = 1 – 5 = – 4,
s21 = c21 - c'21 = c21 – (α2 + β2) = 5 – 1 = 4,
s31 = c31 - c'31 = c31 – (α3 + β1) = 6 – 1 = 5,
s32 = c32 - c'32 = c32 – (α3 + β2) = 4 – 0 = 4,
План перевозок, представленный таблицей 5, оптимален, так как, в единст-венном цикле пересчёта, который может дать уменьшение стоимости перевозок, количество перевозимого груза равно нулю.
Ответ: Стоимость перевозок принимает наименьшее значение
Fопт.= = 4·7 + 3·15 + 2·13 + 2·10 = 129 (т.руб.),
если потребность заказчика В1 удовлетворяется 7т. груза с базы А1 и 13т. груза с базы А2; потребность заказчика В2 полностью удовлетворяется 15т. груза с базы А1, а потребность заказчика В3 полностью удовлетворяется 10т. груза с базы А3. При этом стоимость перевозок по сравнению с первоначальным планом Fнач.= = 4·20 + 3·2 + 5·13 + 2·10 = 171 (т.руб.) уменьшится на 42 т.руб.
Пример №3
Развести однородный груз, находящийся на базе А1 в количестве 25 ед., на базе А2 в количестве 45 ед. и на базе А3 в количестве 20 ед. по двум заказчикам в пункты В1 и В2. Заказчик в пункте В1 может принять не более 40 ед. груза, заказчик в пункте В2 – не более 30 ед. В угловых скобках таблицы 6 даны условные стоимости перевозки одной единицы груза между базами и заказчи-ками. Стоимость перевозок должна быть наименьшей.
Таблица 6
Базы
Заказчики
Запасы на базах
В1
В2
А1
А2
А3
Потребности заказчиков
Решение
Данная задача является задачей открытого типа (несбалансированной), так как количество груза на базах не совпадает с количеством заявленного груза для пунктов В1 и В2. Такую задачу приводят к задаче закрытого типа. Для этого вводят дополнительного (фиктивного) заказчика с нулевыми тарифами (таблица 6¢).
Решение задач открытого типа отличается от решения задач закрытого типа тем, что опорный (первоначальный) план в задачах открытого типа не может определяться методом северо-западного угла. В этом случае применя-ется метод наименьшей стоимости, в котором заполнение клеток таблицы,
Таблица 6¢
Базы
Заказчики
Запасы на базах
В1
В2
В3
-
А1
-
2
-
-
А2
А3
Потребности заказчика
так же как и в методе северо-западного угла, происходит с учётом предельных возможностей базы, лежащей с заполняемой клеткой в одной строке. И так же как в методе северо-западного угла после заполнения каждой клетки из таблицы исключается либо строка, либо столбец, в которых находится заполненная клетка. Разница же состоит в том, что в методе наименьшей стоимости заполняемая клетка определяется по наименьшему тарифу среди всех клеток, не попавших в исключенные строки и столбцы. Так в таблице 6¢ наименьший тариф среди реальных тарифов для реальных (не фиктивных) баз и заказчиков находится в клетке (1;1). Заполняем её с учётом предельных возможностей базы А1 и исключаем из последующего рассмотрения первую строку. В двух оставшихся строках наименьший среди реальных тарифов находится в клетке (3;2). Заполняя её с учётом предельных возможностей базы А3, исключаем из последующего рассмотрения третью строку таблицы 6¢. Не заполненной осталась лишь вторая строка таблицы 6¢, в которой наименьший реальный тариф равен 4. Заполняя эту клетку, берём из базы А2 для заказчика В1 недостающие 15 ед. груза. После чего исключается первый столбец таблицы 6¢ и остаётся единственная клетка с реальным тарифом 8 для базы А2 и заказчика В2. В эту клетку помещается недостающие для заказчика В2 10 ед. груза, которые так же берутся из базы А2 (после заполнения клетки (3;1) на базе А2 оставалось 30 ед. груза). В результате вычеркивается второй столбец таблицы 6¢ и, для завершения, в единственную незаполненную клетку (2;3) для фиктивного заказчика В3 вписываются оставшиеся на базе А2 20 ед. груза, которые полностью удовлетворяют потребность фиктивного заказчика В3. Обратим внимание на то, что потребность фиктивного заказчика удовлетворяется в последнюю очередь.
Метод наименьшей стоимости позволяет в отдельных случаях сократить объём вычислений при решении транспортной задачи. Так опорный план, найденный методом наименьшей стоимости в примере №1, сразу оказывается оптимальным.
План, представленный таблицей 6¢, исследуется на оптимальность методом потенциалов.
a1 + b1 = 1,
a2 + b1 = 4,
a2 + b2 = 8,
a2 + b3 = 0,
a3 + b2 = 3;
a1 = 0, b1 = 1,
a2 = 3, b2 = 5,
a3 = –2, b3 = –3.
S12 = С12 - С¢12 = С12 -(a1 + b2) = 2 - 5 = - 3,
S13 = С13 - С¢13 = С13 -(a1 + b3) = 0 + 3 = 3,
S31 = С31 - С¢31 = С31 -(a3 + b1) = 5 + 1 = 6,
S33 = С33 - С¢33 = С33 -(a3 + b3) = 0 + 5 = 5.
Улучшение плана перевозок возможно за счёт цикла пересчёта со свободной клеткой (1,2):
.
Улучшенный план перевозок представлен в таблице 7.
Таблица 7
Базы
Заказчики
Запасы на базах
В1
В2
В3
-
-
А1
-
-
А2
А3
Потребности заказчика
Исследование последнего плана на оптимальность приводит к выводу, что план оптимален.
a1 + b1 = 1,
a1 + b2 = 2,
a2 + b1 = 4,
a2 + b3 = 0,
a3 + b2 = 3;
a1 = 0, b1 = 1,
a2 = 3, b2 = 2,
a3 = 1, b3 = –3.
S13 = С13 - С¢13 = С13 -(a1 + b3) = 0 + 3 = 3,
S22 = С22 - С¢22 = С22 -(a2 + b2) = 8 - 5 = 3,
S31 = С31 - С¢31 = С31 -(a3 + b1) = 5 - 2 = 3,
S33 = С33 - С¢33 = С33 -(a3 + b3) = 0 + 2 = 2.
При анализе решения нулевой тариф между базой А2 и заказчиком В3 надо понимать в том смысле, что 20 ед. груза не вывозятся с базы А2 (стоимость такой перевозки равна нулю или расстояние между базой А2 и заказчиком В3 равно нулю).
Ответ: Стоимость перевозок однородного груза из указанных баз А1, А2, А3 указанным заказчикам В1 и В2 окажется наименьшей, если потребность заказчика В1 будет удовлетворена 15 ед. груза из базы А1 и 25 ед. груза из базы А2. А потребность заказчика В2 будет удовлетворена 10 ед. груза из базы А1
и 20 ед. груза из базы А3. При этом груз из баз А1 и А3 вывозится полностью, а на базе А2 остается в количестве 20 ед.
Пример №4
Однородный груз, находящийся на базах А1 и А2 в количестве 42 ед. и 74 ед. соответственно, требуется развести трём заказчикам. Заказчик В1 может принять не более 91 ед. груза, заказчик В2 - не более 22 ед., а заказчик В3 не более 39 ед. Условные стоимости перевозки одной единицы груза между базами и заказчиками даны в угловых скобках таблицы 8. Стоимость перевозок должна быть наименьшей.
Таблица 8
Базы
Заказчики
Запасы на базах
В1
В2
В3
А1
А2
Потребности заказчика
Решение
Данная задача является задачей открытого типа или несбалансирован-ной, так как количество груза на базах А1 и А2 меньше количества груза, заявленного заказчиками В1, В2, В3. Эту задачу приводят к задаче закрытого типа введением дополнительной (фиктивной) базы А3 с нулевыми тарифами (таблица 8¢).
При составлении опорного плана в условиях преобразованной открытой модели транспортной задачи применяется метод наименьшей стоимости. При этом заполняемая клетка, находящаяся в не вычеркнутых строках и столбцах дополненной таблицы, определяется по наименьшему тарифу среди реальных (не фиктивных) баз и заказчиков. А запасы фиктивной базы или фиктивного заказчика распределяются в последнюю очередь.
Таблица 8¢
-
Базы
Заказчики
Запасы на базах
В1
В2
В3
-
А1
-
-
А2
А3
Потребности заказчика
План, представленный таблицей 8¢, сразу оказывается оптимальным, что выясняется при его исследовании методом потенциалов.
a1 + b1 = 14,
a1 + b3 = 11,
a2 + b1 = 17,
a3 + b1 = 0,
a3 + b2 = 0;
a1 = 0, b1 = 14,
a2 = 3, b2 = 14,
a3 = -14, b3 = 11.
S12 = С12 - С¢12 = С12 -(a1 + b2) = 15 - 14 = 1,
S22 = С22 - С¢22 = С22 -(a2 + b2) = 22 - 17 = 5,
S23 = С23 - С¢23 = С23 -(a2 + b3) = 21 - 14 = 7,
S33 = С33 - С¢33 = С33 -(a3 + b3) = 0 + 3 = 3.
При анализе решения нулевой тариф между базой А3 и заказчиками В1 и В2 следует понимать в том смысле, что заказчику В1 не довозиться 14 ед. груза, а к заказчику В2 не поступает 22 ед. груза.
Ответ: Стоимость перевозки однородного груза из указанных баз А1 и А2 указанным заказчикам В1, В2, В3 окажется наименьшей, если при вывозе всего груза из баз А1 и А2 потребность заказчика В1 частично удовлетворяются 3 ед. груза из базы А1 и 74 ед. груза из базы А2. К заказчику В2 груз не поступает совсем, а потребность заказчика В3 удовлетворяется полностью.
А1
А2
А3
Потребности заказчика
α1 + β1 = 4,
А1
А3
Потребности заказчика
α1 + β1 = 4,
α1 + β1 = 4,
А2
Потребности заказчика
= 4·7 + 3·15 + 2·13 + 2·10 = 129 (т.руб.),
А1
А2
А3
Потребности заказчиков
a1 + b1 = 1,
Улучшение плана перевозок возможно за счёт цикла пересчёта со свободной клеткой (1,2):
.
А1
Потребности заказчика
a1 + b1 = 1,
А2
Потребности заказчика
