Транспортные задачи

    Заполнение  таблицы начинается с ее северо-западного  угла, т. е. клетки с неизвестным  x11. Первая база A1 может полностью удовлетворить потребность первого заказчика B1 (a1=300,b1=170,a1>b1). Полагая x11=170, вписываем это значение в клетку x11 и исключаем из рассмотрения первый столбец. На базе A1 остается измененный запас a’=130. В оставшейся новой таблице с тремя строками A1,A2,A3 и четырьмя столбцами B2,B3,B4,B5; северо-западным углом будет клетка для неизвестного x12. Первая база с запасом a’1=130 может полностью удовлетворить потребность второго заказчика B2 (a’1=130,b2=110,a’1>b2). Полагаем x12=110, вписываем это значение в клетку x12 и исключаем из рассмотрения второй столбец. На базе A1 остается новый остаток (запас) a’’1=20. В оставшейся новой таблице с тремя строками A1,A2,A3 и тремя столбцами B3,B4,B5 северо-западным углом будет клетка для неизвестного x13. Теперь третий заказчик B3 может принять весь запас с базы A1 (a’’1=20,b3=100,a’’1<b3). Полагаем x13=20, вписываем это значение в клетку x13 и исключаем из рассмотрения первую строку. У заказчика из B3 осталась еще не удовлетворенной потребность b’3=80.

    Теперь  переходим к заполнению клетки для  неизвестного x23 и т.д.

    Через шесть шагов у нас останется  одна база A3 с запасом груза (остатком от предыдущего шага) a’3=200и один пункт B5 с потребностью b5=200. Соответственно этому имеется одна свободная клетка, которую и заполняем, положив x35=200. План составлен. Базис образован неизвестными x11,x12,x13,x23,x24,x34,x35. Правильность составленного плана легко проверить, подсчитав суммы чисел, стоящих в заполненных клетках по строкам и столбцам.

    Общий объем перевозок в тонно-километрах для этого плана составит

    3.2  Метод наименьшей  стоимости

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

    Пример. 

    В данном случае заполнение таблицы начинается с клетки для неизвестного x32, для которого мы имеем значение c32=10, наименьше из всех значений cij. Эта клетка находится на пересечении третьей строки и второго столбца, соответствующим третьей базе A3 и второму заказчику B2. Третья база A3 может полностью удовлетворить потребность второго заказчика B2 (a3=250,b2=110,a3>b2). Полагая x32=110, вписываем это значение в клетку x32 и исключаем из рассмотрения второй столбец. На базе A3 остается изменённый запас a’3=140. В оставшейся новой таблице с тремя строками A1,A2,A3 и четырьмя столбцами B1,B3,B4,B5 клеткой с наименьшим значением cij клетка, где c34=11. Заполняем описанным выше способом эту клетку и аналогично заполняем следующие клетки. В результате оказываются заполненными (в приведенной последовательности) следующие клетки:

     .

    На  пятом шаге клеток с наименьшими  значениями cij оказалось две (c11=c15=70). Мы заполнили клетку для x15, положив x15=180. Можно было выбрать для заполнения другую клетку, положив x11=170, что приведет в результате к другому опорному плану. Общий объем перевозок в тонно-километрах для этого плана составит

     .

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

    Кроме рассмотренных выше способов иногда используется, так называемый, метод  Фогеля. Суть его состоит в следующем: В распределительной таблице  по строкам и столбцам определяется разность между двумя наименьшими  тарифами. Отмечается наибольшая разность. Далее в строке (столбце) с наибольшей разностью заполняется клетка с  наименьшим тарифом. Строки (столбцы) с  нулевым остатком груза в дальнейшем в расчет не принимаются. На каждом этапе загружается только одна клетка. Распределение груза производится, как и ранее.

    3.3 Метод потенциалов

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

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

    Одно  из неизвестных последовательности свободное, а все остальные –  базисные.

    Каждые  два соседних в последовательности неизвестных лежат либо в одном  столбце, либо в одной строке.

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

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

    Второе  условие означает, что у двух соседних неизвестных в цикле либо первые, либо вторые индексы одинаковы.

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

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

    Так, например, в таблице перевозок, составленной по диагональному методу при решения  задачи из предыдущего пункта, неизвестному x21 соответствует цикл x21,x23,x13,x11,x21 и т.д.

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

    старые  значения: x21=0,x32=80,x13=20,x11=170,x21=0;

    новые значения: x’21=x,x’32=80-x,x’13=20+x,x’11=170-x,x’21=x

    Очевидно, если снабдить вершины цикла поочередно знаками “+” и “–“, приписав вершине в свободной клетке знак “+”, то можно сказать, что в вершинах со знаком “+” число  прибавляется к прежнему значению неизвестного, находящегося в этой вершине, а в вершинах со знаком “–“ это число вычитается из прежнего значения неизвестного, находящегося в этой вершине.

    Замечание. Так как число вершин в цикле  всегда четно, то, возвращаясь в свободную  клетку, мы должны будем приписать  ей знак “+”, т. е. тот знак, который  ей уже приписан при выходе из нее. Это очень существенное обстоятельство, так как иначе мы пришли бы к  противоречию. Безразлично также, в  каком направлении обходится  цикл при “означивании” вершин.

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