При этом значения алгебраической суммы тарифов для свободных клеток таблицы 3 оказываются равными

s₁₄ = c₁₄ - c'₁₄ = c₁₄ – (α₁ + β₄) = 80 – 50 = 30,

s₂₂ = c₂₂ - c'₂₂ = c₂₂ – (α₂ + β₂) = 90 – (10 + 50) = 30,

s₂₃ = c₂₃ - c'₂₃ = c₂₃ – (α₂ + β₃) = 40 – (10 + 15) = 15,

s₃₁ = c₃₁ - c'₃₁ = c₃₁ – (α₃ + β₁) = 50 – (– 40 + 70) = 20,

s₃₃ = c₃₃ - c'₃₃ = c₃₃ – (α₃ + β₂) = 90 – (– 40 + 15) = 115,

s₃₄ = c₃₄ - c'₃₄ = c₃₄ – (α₃ + β₄) = 11 – (– 40 + 50) = 1.

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

Ответ: При оптимальном плане перевозок потребность заказчика В₁ удовлетворяется как базой А₁, из которой поступает 140т. так и базой А₂, из которой поступает 30т. ; потребность заказчика В₂ удовлетворяется базами А₁, из которой поступает 60т. и А₃, из которой поступает 50т.; потребность заказчика В₃ удовлетворяет база А₁ , из которой поступает 100т., а потребность заказчика В₄ удовлетворяет база А₂, из которой поступает 120т. При этом стоимость перевозок составит

F_опт. = 70 ·140 + 50 · 60 + 15 · 100 + 80 · 30 + 60 ·120 + 10 · 50 = 24400 (т.км.),

что меньше стоимости перевозки по первоначальному плану (F_нач.= 25650 т.км.) на 1250 т.км.

Пример №2

На трёх базах находится однородный груз. На базе А₁ в количестве 22т., на базе А₂ в количестве 13т., на базе А₃ в количестве 10т. Весь этот груз необходимо развести трём заказчикам так, чтобы стоимость перевозок была наименьшей. Заказчику в пункте В₁ должно поступить 20т., в пункте В₂ - 15т., в пункте В₃ - 10т. груза. В угловых скобках таблицы 4 указаны стоимости перевозки одной тонны груза между базами и заказчиками в тысячах рублей.

Решение

1. Данная задача является сбалансированной. При определении начального плана перeвозок методом северо-западного угла внутренние клетки таблицы 4 примут значения:

Таблица 4

Базы

Заказчики Запасы на базах В₁ В₂ В₃ А₁ –   А₂ – –   А₃ – –   Потребности заказчика      

2. Оптимальность полученного плана исследуется методом потенциалов. Уравнения потенциалов, составленные для базисных клеток таблицы 4, имеют вид:

α₁ + β₁ = 4,

α₁ + β₂ = 3,

α₂ + β₂ = 5.

α₃ + β₃ = 2.

В четырёх уравнениях оказалось 6 неизвестных. Число неизвестных превышает число уравнений больше чем на 1. В этом случае циклы пересчёта можно построить не для всех свободных клеток данной таблицы. Так, в таблице 4 для клеток (1;3), (2;3), (3;1), (3;2) циклы пересчёта построить нельзя. Тогда в одной из этих клеток (например, в клетке (2;3)) записывается базисная переменная с нулевым значением количества перевозимого груза. Дополненная таким образом таблица 4 принимает вид

Таблица 4¢

Базы	Заказчики	Запасы на базах
В1	В2	В3
А1			–
А2	–
А3	–	–
Потребности заказчика

Теперь из системы пяти уравнений, составленных для базисных клеток таблицы 4¢

α₁ + β₁ = 4,

α₁ + β₂ = 3,

α₂ + β₂ = 5,

α₂ + β₃ = 3,

α₃ + β₃ = 2

находятся значения 6-ти неизвестных

α₁ = 0, β₁ = 4,

α₂ = 2, β₂ = 3,

α₃ = 5, β₃ = 1,

при условии, что α₁= 0, и алгебраические суммы тарифов для свободных клеток таблицы 4' имеют значения:

s₁₃ = c₁₃ – c'₁₃ = c₁₃ – (α₁ + β₃) = 1 – 1 = 0,

s₂₁ = c₂₁ – c'₂₁ = c₂₁ – (α₂ + β₁) = 2 – 6 = – 4,

s₃₁ = c₃₁ – c'₃₁ = c₃₁ – (α₃ + β₁) = 6 – 5 = 1,

s₃₂ = c₃₂ – c'₃₂ = c₃₂ – (α₃ + β₂) = 4 – 4 = 0,

Вычисления показывают, что первоначальный план перевозок можно улучшить, производя цикл пересчёта со свободной клеткой (2; 1):

Улучшенный план перевозок представлен в таблице 5.

Исследуем его на оптимальность:

α₁ + β₁ = 4,

α₁ + β₂ = 3,

α₂ + β₁ = 2,

α₂ + β₃ = 3,

α₃ + β₃ = 2;

α₁ = 0, β₁ = 4,

α₂ = –2, β₂ = 3,

α₃ = –3, β₃ = 5.

Таблица 5

Базы	Заказчики	Запасы на базах
В1	В2	В3
А1			–
А2		–
А3	–	–
Потребности заказчика

s₁₃ = c₁₃ - c'₁₃ = c₁₃ – (α₁ + β₃) = 1 – 5 = – 4,

s₂₁ = c₂₁ - c'₂₁ = c₂₁ – (α₂ + β₂) = 5 – 1 = 4,

s₃₁ = c₃₁ - c'₃₁ = c₃₁ – (α₃ + β₁) = 6 – 1 = 5,

s₃₂ = c₃₂ - c'₃₂ = c₃₂ – (α₃ + β₂) = 4 – 0 = 4,

План перевозок, представленный таблицей 5, оптимален, так как, в единст-венном цикле пересчёта, который может дать уменьшение стоимости перевозок, количество перевозимого груза равно нулю.

Ответ:Стоимость перевозок принимает наименьшее значение

F_опт.= = 4·7 + 3·15 + 2·13 + 2·10 = 129 (т.руб.),

если потребность заказчика В₁ удовлетворяется 7т. груза с базы А₁ и 13т. груза с базы А₂; потребность заказчика В₂ полностью удовлетворяется 15т. груза с базы А₁, а потребность заказчика В₃ полностью удовлетворяется 10т. груза с базы А₃. При этом стоимость перевозок по сравнению с первоначальным планом F_нач.= = 4·20 + 3·2 + 5·13 + 2·10 = 171 (т.руб.) уменьшится на 42 т.руб.

Пример №3

Развести однородный груз, находящийся на базе А₁ в количестве 25 ед., на базе А₂ в количестве 45 ед. и на базе А₃ в количестве 20 ед. по двум заказчикам в пункты В₁ и В₂. Заказчик в пункте В₁ может принять не более 40 ед. груза, заказчик в пункте В₂ – не более 30 ед. В угловых скобках таблицы 6 даны условные стоимости перевозки одной единицы груза между базами и заказчи-ками. Стоимость перевозок должна быть наименьшей.

Таблица 6

Базы	Заказчики	Запасы на базах
В1	В2
А1
А2
А3
Потребности заказчиков

Решение

Данная задача является задачей открытого типа (несбалансированной), так как количество груза на базах не совпадает с количеством заявленного груза для пунктов В₁ и В₂. Такую задачу приводят к задаче закрытого типа. Для этого вводят дополнительного (фиктивного) заказчика с нулевыми тарифами (таблица 6¢).

Решение задач открытого типа отличается от решения задач закрытого типа тем, что опорный (первоначальный) план в задачах открытого типа не может определяться методом северо-западного угла. В этом случае применя-ется метод наименьшей стоимости, в котором заполнение клеток таблицы,

Таблица 6¢

Базы	Заказчики	Запасы на базах
В1	В2	В3
- А1		- 2
- - А2
А3
Потребности заказчика

так же как и в методе северо-западного угла, происходит с учётом предельных возможностей базы, лежащей с заполняемой клеткой в одной строке. И так же как в методе северо-западного угла после заполнения каждой клетки из таблицы исключается либо строка, либо столбец, в которых находится заполненная клетка. Разница же состоит в том, что в методе наименьшей стоимости заполняемая клетка определяется по наименьшему тарифу среди всех клеток, не попавших в исключенные строки и столбцы. Так в таблице 6¢ наименьший тариф среди реальных тарифов для реальных (не фиктивных) баз и заказчиков находится в клетке (1;1). Заполняем её с учётом предельных возможностей базы А₁ и исключаем из последующего рассмотрения первую строку. В двух оставшихся строках наименьший среди реальных тарифов находится в клетке (3;2). Заполняя её с учётом предельных возможностей базы А₃, исключаем из последующего рассмотрения третью строку таблицы 6¢. Не заполненной осталась лишь вторая строка таблицы 6¢, в которой наименьший реальный тариф равен 4. Заполняя эту клетку, берём из базы А₂ для заказчика В₁ недостающие 15 ед. груза. После чего исключается первый столбец таблицы 6¢ и остаётся единственная клетка с реальным тарифом 8 для базы А₂ и заказчика В₂. В эту клетку помещается недостающие для заказчика В₂ 10 ед. груза, которые так же берутся из базы А₂ (после заполнения клетки (3;1) на базе А₂ оставалось 30 ед. груза). В результате вычеркивается второй столбец таблицы 6¢ и, для завершения, в единственную незаполненную клетку (2;3) для фиктивного заказчика В₃ вписываются оставшиеся на базе А₂ 20 ед. груза, которые полностью удовлетворяют потребность фиктивного заказчика В₃. Обратим внимание на то, что потребность фиктивного заказчика удовлетворяется в последнюю очередь.

Метод наименьшей стоимости позволяет в отдельных случаях сократить объём вычислений при решении транспортной задачи. Так опорный план, найденный методом наименьшей стоимости в примере №1, сразу оказывается оптимальным.

План, представленный таблицей 6¢, исследуется на оптимальность методом потенциалов.

a₁ + b₁ = 1,

a₂ + b₁ = 4,

a₂ + b₂ = 8,

a₂ + b₃ = 0,

a₃ + b₂ = 3;

a₁ = 0, b₁ = 1,

a₂ = 3, b₂ = 5,

a₃ = –2, b₃ = –3.

S₁₂ = С₁₂ - С¢₁₂ = С₁₂ -(a₁ + b₂) = 2 - 5 = - 3,

S₁₃ = С₁₃ - С¢₁₃ = С₁₃ -(a₁ + b₃) = 0 + 3 = 3,

S₃₁ = С₃₁ - С¢₃₁ = С₃₁ -(a₃ + b₁) = 5 + 1 = 6,

S₃₃ = С₃₃ - С¢₃₃ = С₃₃ -(a₃ + b₃) = 0 + 5 = 5.

Улучшение плана перевозок возможно за счёт цикла пересчёта со свободной клеткой (1,2):

.

Улучшенный план перевозок представлен в таблице 7.

Таблица 7

Базы	Заказчики	Запасы на базах
В1	В2	В3
- - А1
- - А2
А3
Потребности заказчика

Исследование последнего плана на оптимальность приводит к выводу, что план оптимален.

a₁ + b₁ = 1,

a₁ + b₂ = 2,

a₂ + b₁ = 4,

a₂ + b₃ = 0,

a₃ + b₂ = 3;

a₁ = 0, b₁ = 1,

a₂ = 3, b₂ = 2,

a₃ = 1, b₃ = –3.

S₁₃ = С₁₃ - С¢₁₃ = С₁₃ -(a₁ + b₃) = 0 + 3 = 3,

S₂₂ = С₂₂ - С¢₂₂ = С₂₂ -(a₂ + b₂) = 8 - 5 = 3,

S₃₁ = С₃₁ - С¢₃₁ = С₃₁ -(a₃ + b₁) = 5 - 2 = 3,

S₃₃ = С₃₃ - С¢₃₃ = С₃₃ -(a₃ + b₃) = 0 + 2 = 2.

При анализе решения нулевой тариф между базой А₂ и заказчиком В₃ надо понимать в том смысле, что 20 ед. груза не вывозятся с базы А₂ (стоимость такой перевозки равна нулю или расстояние между базой А₂ и заказчиком В₃ равно нулю).

Ответ: Стоимость перевозок однородного груза из указанных баз А₁, А₂, А₃ указанным заказчикам В₁ и В₂ окажется наименьшей, если потребность заказчика В₁ будет удовлетворена 15 ед. груза из базы А₁ и 25 ед. груза из базы А₂. А потребность заказчика В₂ будет удовлетворена 10 ед. груза из базы А₁

и 20 ед. груза из базы А₃. При этом груз из баз А₁ и А₃ вывозится полностью, а на базе А₂ остается в количестве 20 ед.

Пример №4

Однородный груз, находящийся на базах А₁ и А₂ в количестве 42 ед. и 74 ед. соответственно, требуется развести трём заказчикам. Заказчик В₁ может принять не более 91 ед. груза, заказчик В₂ - не более 22 ед., а заказчик В₃ не более 39 ед. Условные стоимости перевозки одной единицы груза между базами и заказчиками даны в угловых скобках таблицы 8. Стоимость перевозок должна быть наименьшей.

Таблица 8

Базы	Заказчики	Запасы на базах
В1	В2	В3
А1
А2
Потребности заказчика

Решение

Данная задача является задачей открытого типа или несбалансирован-ной, так как количество груза на базах А₁ и А₂ меньше количества груза, заявленного заказчиками В₁, В₂ , В₃. Эту задачу приводят к задаче закрытого типа введением дополнительной (фиктивной) базы А₃ с нулевыми тарифами (таблица 8¢).

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

Таблица 8¢

-   Базы	Заказчики	Запасы на базах
В1	В2	В3
- А1
- - А2
А3
Потребности заказчика

План, представленный таблицей 8¢, сразу оказывается оптимальным, что выясняется при его исследовании методом потенциалов.

a₁ + b₁ = 14,

a₁ + b₃ = 11,

a₂ + b₁ = 17,

a₃ + b₁ = 0,

a₃ + b₂ = 0;

a₁ = 0, b₁ = 14,

a₂ = 3, b₂ = 14,

a₃ = -14, b₃ = 11.

S₁₂ = С₁₂ - С¢₁₂ = С₁₂ -(a₁ + b₂) = 15 - 14 = 1,

S₂₂ = С₂₂ - С¢₂₂ = С₂₂ -(a₂ + b₂) = 22 - 17 = 5,

S₂₃ = С₂₃ - С¢₂₃ = С₂₃ -(a₂ + b₃) = 21 - 14 = 7,

S₃₃ = С₃₃ - С¢₃₃ = С₃₃ -(a₃ + b₃) = 0 + 3 = 3.

При анализе решения нулевой тариф между базой А₃ и заказчиками В₁ и В₂ следует понимать в том смысле, что заказчику В₁ не довозиться 14 ед. груза, а к заказчику В₂ не поступает 22 ед. груза.

Ответ: Стоимость перевозки однородного груза из указанных баз А₁ и А₂ указанным заказчикам В₁, В₂, В₃ окажется наименьшей, если при вывозе всего груза из баз А₁ и А₂ потребность заказчика В₁ частично удовлетворяются 3 ед. груза из базы А₁ и 74 ед. груза из базы А₂. К заказчику В₂ груз не поступает совсем, а потребность заказчика В₃ удовлетворяется полностью.