Г Л А В А  5 ТРАНСПОРТНАЯ ЗАДАЧА

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

Рассмотрим постановку таких задач.

Пусть имеем m предприятий A1, A2,..., Am, производящих один и тот же продукт в количествах соответственно a1, a2,..., am.

Пусть, далее, имеется n потребителей B1, B2,..., Bn (складов) с потребностями (вместимостями) соответственно b1, b2,..., bn.

Пусть весь произведенный продукт может быть размещен на складах B1, B2,..., Bn при полном их заполнении.

Пусть, наконец,  перевозка  единицы  продукции из пункта Ai в пункт Bj оценивается величиной cij (cij - заданы).

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

Строим математическую модель.  Пусть xij - количество продукта, перевозимого  из  пункта  Ai в пункт Bj.  Из постановки задачи очевидно, что каждый склад вмещает

                                                                m

                                                      bj =  å xij ,         j = 1, 2, ...,  n

                                                              i=1

А так как производится столько продукции, сколько  ее  потребляется (складируется), то

                                                               n

                                                      ai = å  xij,           i = 1, 2,..., m

                                                              j=1

(продукт с предприятия вывозится полностью).

Далее, очевидным является то,  что количество  перевозимой  с предприятия на  склад продукции не может быть отрицательным,  т.е. xij 0 (i = 1, 2,...,m;  j = 1, 2,..., n).

Так как  необходимо  определить  наилучший  план перевозок по стоимости, то строим целевую функцию суммарных затрат на  перевозки. Она  должна  быть минимизирована.  Такая целевая функция имеет вид:

                                                                 m    n

                                                      L  =  å   å  cijxij.

                                                               i=1  j=1

Таким образом,  имеем следующую математическую постановку задачи. Найти  такие xij,  которые доставляют минимум линейной форме L, т.е.

                                                               m     n

                                                    min    å   å  cijxij

                                                    (xij)  i=1 j=1

и удовлетворяют условиям:

             m

å xij   =  bj,       j = 1, 2,..., n;

            i=1

              n

å xij   =  ai,       i = 1, 2,..., m;

            j=1

xij  0,      i = 1, 2,..., m;  j = 1, 2,..., n.

                                                          n            m

(Из  (1)  и  (2)    следует,   что   å  bj = å ai.  Именно  в   этом   соотношении  заключается основная

                                                        j=1        i=1 

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

Итак, имеем задачу линейного программирования, т.е. задача нахождения минимума линейной функции при линейных ограничениях. Однако ограничения (1) и (2) специфичны.  Они и определяют класс задач, называемых  транспортными задачами.

Рассмотрим решение транспортной задачи на простейших примерах.

ЗАДАЧА. Два завода A1 и A2 производят продукцию, соответственно, в  объемах a1 = 4   и        a2 = 7.  Продукция полностью перевозится на склады B1 и B2 вместимостью, соответственно, b1 = 6  и   b2 = 5.  Перевозка единицы  продукции с завода Ai на склад Bj оценивается величинами cij, значения которых представлены в матрице:

                                                                    c11 = 4     c12 = 5

                                                                     c21 = 3     c22 = 7

Определить оптимальный план перевозок по стоимости.

Схему записи условий задачи можно представить в виде таблицы:

Такое представление удобно тем,  что оно сразу выявляет  специфику транспортной задачи, а именно: сумма чисел по строке «Вместимость» (6+5) равна сумме чисел по столбцу «Производство» (4+7).

В силу специфики задачи величины xij, удовлетворяющие условиям задачи, не могут оставаться независимыми друг от друга.  А, следовательно, одним из них можно распорядиться произвольным образом. Исходя из этого, задачу можно  преобразовать  так,  чтобы  осталась только одна переменная. Действительно, пусть x11 = x, тогда возможные размещения продуктов на складах можно представить в виде  следующей таблицы:

x12 = 4 - x, так  как объем общего производства в A1 равен 4. X21 = 6 -x, так как вместимость склада B1 равна 6, а x22 должен быть таким, чтобы общий объем производства A2 был  равен  7.  Эти  выводы легко получаются  из условий (1) и (2) постановки общей задачи путем простых вычислений.

По транспортным издержкам имеем:

L = 4x + 5(4 - x) + 3(6 - x) + 7(1 + x) = 45 + 3x.

(См. Структуру ценовой функции L и значения величин cij).

Так  как  имеет смысл говорить только о  неотрицательных  объемах продукции,  то имеем:

4 - x 0;  1 + x 0;  6 - x 0;  x 0.

Отсюда множество  допустимых решений x будет находиться на отрезке 0 x 4.  Но L = 45 + 3x есть линейная функция,  и речь идет о ее минимизации. На  отрезке  0  x 4 она принимает минимальное значение в точке x = 0.  Таким образом, имеем решение  поставленной задачи в виде следующей таблицы:

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

ЗАДАЧА. Запишем постановку задачи в виде таблицы:

Другими словами имеем транспортную задачу с двумя заводами и тремя складами.

Сводим поставленную  задачу к двухмерной задаче.  С этой целью полагаем x11 = x и x12 = y. Отсюда имеем:

Каждый из элементов этой таблицы должен быть неотрицательным. Следовательно, имеем следующие шесть ограничений:

x 0, y 0, x + y 10, x 8, y 10, x + y 3.

Общие затраты на перевозки составят:

L = 5x + 2y + 10 + (x + y) + 3(8 - x) + 3(10 - y) + 4(x +y) - 12 =

= 5x + 2y + 52.

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

Применяем графический метод решения.  Он приводит к плоскости (xy). Строим многоугольник решений задачи.

Строим прямую  нулевой ценности L = 5x + 2y и начинаем ее передвигать параллельно самой себе в сторону многоугольника решений. Первая точка встречи этой прямой с многоугольником решений определяет искомое оптимальное решение задачи.  В  данном  случае  такой точкой является точка A с координатами x = 0  и  y = 3.

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

Рассмотрим теперь подходы к решению транспортной задачи в общем виде, т.е. задачи размерности m x n.

Введем следующие понятия:

- прямоугольная цепь;

- независимые расположения;

- подходящие решения.

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

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

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

Подходящие решения - это последовательность допустимых  решений, удовлетворяющих условиям:

- матрица перевозок каждого решения содержит ровно (m +  n  - 1) ненулевых клеток;

- клетки матрицы перевозок независимо расположены.

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

Рассмотрим применение метода на примере указанной выше задачи размерности 2 х 3 (два завода и три склада).

Находим первое  допустимое решение.  Для этого используем уже известную схему представления решения в виде таблицы:

Начинаем искать решение с левого верхнего угла этой таблицы и полагаем, что  с  завода  A1 перевозится столько продукции, сколько вмещает склад  B1,  т.е. 8 единиц. Остальную продукцию завода A1 (2 единицы) размещаем на складе B2.  Очевидно, что при таком размещении продукция завода A1 на склад B3 не попадет,  т.е.  в клетке  с координатами A1 и B3 , будет 0.

Для второй строки в клетке с координатами A2 и B1 также будет 0, так как склад B1 полностью занят продукцией завода A1 и с завода A2 на этом складе разместить уже ничего  нельзя.  На  склад  B2 можно перевести 8 единиц продукции с завода A2, а остальные 7 единиц продукции этого завода можно отправить на склад B3.  Таким образом, получено  одно  из  допустимых решений поставленной задачи, которое можно схематически представить в виде следующей таблицы:

Полученное решение является подходящим,  так как оно имеет (2 + 3 - 1) = 4 ненулевых клетки,  а любая прямоугольная цепь таблицы решений содержит по крайней мере одну нулевую клетку.

Подсчитаем транспортные  затраты  исходя  из  данных  матрицы транспортных издержек cij:

Затраты L1 составят:

                                                               L1 = 8 5 + 2 2 + 8 3 + 7 4 = 96.

С целью анализа затрат на  предмет  минимальности  произведем изменение объемов перевозок. Для этого воспользуемся понятием прямоугольной цепи. Выделим цепь в таблице решений и произведем в ней изменение объемов перевозок на одну единицу. Например:

Изменение в общей сумме затрат будет равно:

 c13 - c23 + c22 - c12 = 1 - 4 + 3 - 2 = -2.

Отсюда делаем вывод, что изменение размещения продукции улучшает план перевозок.

Ясно, что указанный путь перебора различных размещений грузов и вычисления соответствующих затрат  весьма  утомителен  и  займет много времени.  Поэтому существуют разные методы упрощающие процедуру исследования всех допустимых изменений  размещения  грузов  и позволяющие быстро  находить  нужные  решения.  Рассмотрим один из них. Он называется методом теневых затрат.  Вводим теневые затраты ui по строкам и vj по столбцам. Эти затраты определяются следующим образом. Строится таблица теневых затрат в виде:

Смысл имеет рассматривать только непутевые клетки первого полученного допустимого  решения.  Эти  клетки  в таблице обозначены знаком * (звездочка).  Теневые затраты ui и vj ищутся такими,  что cij = ui + vj для  каждой клетки таблицы.  Например,  полагаем u1 = 0, тогда v1 = 5,  так как    c11 = 5 = 0 + 5 = u1 + v1.  Далее полагаем v2 = 2,  чтобы c12 = 2,  так как по определению u1 + v2 = c12.  Но тогда необходимо,  чтобы u2 = 1,  так как c22 = 3 = u2 + v2 = u2 + 2. Наконец, полагаем v3 = 3, чтобы c23 = 4.

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

                  c13 - c23 + c22 - c12 = c13 - (u2 + v3) + (u2 + v2) -  (u1 - v2) = c13 - (u1 +v3).

Если теперь для нулевых клеток таблицы, которые предполагается сделать ненулевыми в ходе поиска оптимального значения,  вычислить суммарные теневые затраты (в данном случае u1 + v3)  и  сравнить их  с истинными затратами (c13),  то сразу видно, уменьшают ли эти изменения общие затраты или нет.  Если в данном случае  c13  < (u1 + v3), то общие затраты при таком перемещении уменьшаются.

В предыдущей таблице значения cij и (ui  +  vj)  для  нулевых клеток представлены в скобках. Из сравнения их значений видно, что построенное первое допустимое решение не  является  оптимальным  и план перевозок, представленный этим решением, требует изменений.

Очевидным является также факт,  что наиболее предпочтительным направлением корректировки  первоначального  плана  представляется прямоугольная цепь с нулевой клеткой, где разность между cij и (ui + vj)  максимальна.

Продолжим дальнейшее рассмотрение поставленной задачи.  Перемещение в  выбранной  прямоугольной  цепи делаем до тех пор, пока в ней не появится новая нулевая клетка. Опять считаем теневые затраты и сравниваем их  с соответствующими cij.  Этот процесс продолжаем до тех пор, пока разность между cij и (ui + vj) для  любых  i,j  будет отрицательной.

Следуя указанным правилам, находим второе  допустимое  решение  задачи:

Простой расчет показывает, что это решение неоптимально. Общая сумма затрат в этом варианте составляет  92  единицы.  Однако, нулевая  клетка  в первой строке и втором столбце имеет превышение значения cij над суммой ui и vj,  поэтому при следующих изменениях решения  представляется  нецелесообразным  изменять данные второго столбца.

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

Общие транспортные затраты в этом варианте составляют 67 единиц, тем не менее это еще не оптимальное решение,  так как имеется нулевая клетка, где разность cij - (ui + vj)  £ 0.

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

Легко заметить,  что это уже оптимальное решение задачи в целом. Общие  транспортные  расходы  при таком плане перевозок будут минимальными и составят 58 единиц.

Рассмотрим один  важный  аспект  методов решения транспортной задачи, когда число используемых перевозок окажется меньше m + n - 1. Это - так называемый вырожденный случай.  При этом не представляется возможность вычислить теневые затраты, и  процесс  улучшения плана останавливается.

Одним из выходов из этой ситуации  является  следующий  алгоритм. Увеличиваем  искусственно  вместимость каждого из складов на малую величину x, а выпуск одного из заводов на nx единиц (n - число складов). Тогда процесс решения может быть продолжен,  а в окончательном решении величина x приравнивается 0.

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

Отсюда видно, что имеем только три ненулевых клетки, а следовательно это  вырожденный случай.  Вместимость каждого склада фиктивно увеличиваем на x единиц,  а выпуск завода A2 - на 3x.  Тогда таблица перевозок будет такой:

Подсчитываем разности cij и (ui + vj) для нулевых клеток. Одна из них, а именно cоответствующая индексам 1 и  3,  отрицательна. Следовательно, полученное решение не является оптимальным. Изменяем прямоугольную цепь, включающую второй и третий столбцы (пересылаем по  цепи 7 + x единиц продукции).  Получаем третье допустимое решение в виде таблицы:

Вновь подсчитываем разности истинных издержек и теневых  затрат в нулевых  клетках и убеждаемся в их положительности. Таким образом получили оптимальное решение.  Полагая в нем x = 0, получаем искомое решение исходной задачи.

З А Д А Ч И  П О  Т Е М Е

ЗАДАЧА 5.1.

Найти размещение, минимизирующее транспортные издержки,  при условиях, сформулированных в следующей таблице:

F - объем производства завода,  W - вместимость склада,  cij - стоимость перевозки с i-го завода на j-ый склад.

ЗАДАЧА 5.2.

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

F - объем производства завода,  W - вместимость склада,  cij- стоимость перевозки с i-го завода на j-ый склад.

ЗАДАЧА 5.3.

Найти размещение, минимизирующее транспортные издержки,  при условиях, сформулированных в следующей таблице:

F - объем производства завода,  W - вместимость склада,  cij - стоимость перевозки с i-го завода на j-ый склад.

ЗАДАЧА 5.4.

Найти размещение, минимизирующее транспортные издержки,  при условиях, сформулированных в следующей таблице:

F - объем производства завода,  W - вместимость склада,  cij - стоимость перевозки с i-го завода на j-ый склад.

ЗАДАЧА 5.5.

Найти размещение, минимизирующее транспортные издержки,  при условиях, сформулированных в следующей таблице:

F - объем производства завода,  W - вместимость склада,  cij - стоимость перевозки с i-го завода на j-ый склад.

ЗАДАЧА 5.6.

Найти размещение, минимизирующее транспортные издержки,  при условиях, сформулированных в следующей таблице:

F - грузоподъемность корабля,  W - вместимость порта,  cij - стоимость перевозки i-м кораблем в j-ый порт.

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

Рассмотрим постановку таких задач.

Пусть имеем m предприятий A1, A2,..., Am, производящих один и тот же продукт в количествах соответственно a1, a2,..., am.

Пусть, далее, имеется n потребителей B1, B2,..., Bn (складов) с потребностями (вместимостями) соответственно b1, b2,..., bn.

Пусть весь произведенный продукт может быть размещен на складах B1, B2,..., Bn при полном их заполнении.

Пусть, наконец,  перевозка  единицы  продукции из пункта Ai в пункт Bj оценивается величиной cij (cij - заданы).

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

Строим математическую модель.  Пусть xij - количество продукта, перевозимого  из  пункта  Ai в пункт Bj.  Из постановки задачи очевидно, что каждый склад вмещает

                                                                m

                                                      bj =  å xij ,         j = 1, 2, ...,  n

                                                              i=1

А так как производится столько продукции, сколько  ее  потребляется (складируется), то

                                                               n

                                                      ai = å  xij,           i = 1, 2,..., m

                                                              j=1

(продукт с предприятия вывозится полностью).

Далее, очевидным является то,  что количество  перевозимой  с предприятия на  склад продукции не может быть отрицательным,  т.е. xij 0 (i = 1, 2,...,m;  j = 1, 2,..., n).

Так как  необходимо  определить  наилучший  план перевозок по стоимости, то строим целевую функцию суммарных затрат на  перевозки. Она  должна  быть минимизирована.  Такая целевая функция имеет вид:

                                                                 m    n

                                                      L  =  å   å  cijxij.

                                                               i=1  j=1

Таким образом,  имеем следующую математическую постановку задачи. Найти  такие xij,  которые доставляют минимум линейной форме L, т.е.

                                                               m     n

                                                    min    å   å  cijxij

                                                    (xij)  i=1 j=1

и удовлетворяют условиям:

             m

å xij   =  bj,       j = 1, 2,..., n;

            i=1

              n

å xij   =  ai,       i = 1, 2,..., m;

            j=1

xij  0,      i = 1, 2,..., m;  j = 1, 2,..., n.

                                                          n            m

(Из  (1)  и  (2)    следует,   что   å  bj = å ai.  Именно  в   этом   соотношении  заключается основная

                                                        j=1        i=1 

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

Итак, имеем задачу линейного программирования, т.е. задача нахождения минимума линейной функции при линейных ограничениях. Однако ограничения (1) и (2) специфичны.  Они и определяют класс задач, называемых  транспортными задачами.

Рассмотрим решение транспортной задачи на простейших примерах.

ЗАДАЧА. Два завода A1 и A2 производят продукцию, соответственно, в  объемах a1 = 4   и        a2 = 7.  Продукция полностью перевозится на склады B1 и B2 вместимостью, соответственно, b1 = 6  и   b2 = 5.  Перевозка единицы  продукции с завода Ai на склад Bj оценивается величинами cij, значения которых представлены в матрице:

                                                                    c11 = 4     c12 = 5

                                                                     c21 = 3     c22 = 7

Определить оптимальный план перевозок по стоимости.

Схему записи условий задачи можно представить в виде таблицы:

Такое представление удобно тем,  что оно сразу выявляет  специфику транспортной задачи, а именно: сумма чисел по строке «Вместимость» (6+5) равна сумме чисел по столбцу «Производство» (4+7).

В силу специфики задачи величины xij, удовлетворяющие условиям задачи, не могут оставаться независимыми друг от друга.  А, следовательно, одним из них можно распорядиться произвольным образом. Исходя из этого, задачу можно  преобразовать  так,  чтобы  осталась только одна переменная. Действительно, пусть x11 = x, тогда возможные размещения продуктов на складах можно представить в виде  следующей таблицы:

x12 = 4 - x, так  как объем общего производства в A1 равен 4. X21 = 6 -x, так как вместимость склада B1 равна 6, а x22 должен быть таким, чтобы общий объем производства A2 был  равен  7.  Эти  выводы легко получаются  из условий (1) и (2) постановки общей задачи путем простых вычислений.

По транспортным издержкам имеем:

L = 4x + 5(4 - x) + 3(6 - x) + 7(1 + x) = 45 + 3x.

(См. Структуру ценовой функции L и значения величин cij).

Так  как  имеет смысл говорить только о  неотрицательных  объемах продукции,  то имеем:

4 - x 0;  1 + x 0;  6 - x 0;  x 0.

Отсюда множество  допустимых решений x будет находиться на отрезке 0 x 4.  Но L = 45 + 3x есть линейная функция,  и речь идет о ее минимизации. На  отрезке  0  x 4 она принимает минимальное значение в точке x = 0.  Таким образом, имеем решение  поставленной задачи в виде следующей таблицы:

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

ЗАДАЧА. Запишем постановку задачи в виде таблицы:

Другими словами имеем транспортную задачу с двумя заводами и тремя складами.

Сводим поставленную  задачу к двухмерной задаче.  С этой целью полагаем x11 = x и x12 = y. Отсюда имеем:

Каждый из элементов этой таблицы должен быть неотрицательным. Следовательно, имеем следующие шесть ограничений:

x 0, y 0, x + y 10, x 8, y 10, x + y 3.

Общие затраты на перевозки составят:

L = 5x + 2y + 10 + (x + y) + 3(8 - x) + 3(10 - y) + 4(x +y) - 12 =

= 5x + 2y + 52.

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

Применяем графический метод решения.  Он приводит к плоскости (xy). Строим многоугольник решений задачи.

Строим прямую  нулевой ценности L = 5x + 2y и начинаем ее передвигать параллельно самой себе в сторону многоугольника решений. Первая точка встречи этой прямой с многоугольником решений определяет искомое оптимальное решение задачи.  В  данном  случае  такой точкой является точка A с координатами x = 0  и  y = 3.

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

Рассмотрим теперь подходы к решению транспортной задачи в общем виде, т.е. задачи размерности m x n.

Введем следующие понятия:

- прямоугольная цепь;

- независимые расположения;

- подходящие решения.

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

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

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

Подходящие решения - это последовательность допустимых  решений, удовлетворяющих условиям:

- матрица перевозок каждого решения содержит ровно (m +  n  - 1) ненулевых клеток;

- клетки матрицы перевозок независимо расположены.

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

Рассмотрим применение метода на примере указанной выше задачи размерности 2 х 3 (два завода и три склада).

Находим первое  допустимое решение.  Для этого используем уже известную схему представления решения в виде таблицы:

Начинаем искать решение с левого верхнего угла этой таблицы и полагаем, что  с  завода  A1 перевозится столько продукции, сколько вмещает склад  B1,  т.е. 8 единиц. Остальную продукцию завода A1 (2 единицы) размещаем на складе B2.  Очевидно, что при таком размещении продукция завода A1 на склад B3 не попадет,  т.е.  в клетке  с координатами A1 и B3 , будет 0.

Для второй строки в клетке с координатами A2 и B1 также будет 0, так как склад B1 полностью занят продукцией завода A1 и с завода A2 на этом складе разместить уже ничего  нельзя.  На  склад  B2 можно перевести 8 единиц продукции с завода A2, а остальные 7 единиц продукции этого завода можно отправить на склад B3.  Таким образом, получено  одно  из  допустимых решений поставленной задачи, которое можно схематически представить в виде следующей таблицы:

Полученное решение является подходящим,  так как оно имеет (2 + 3 - 1) = 4 ненулевых клетки,  а любая прямоугольная цепь таблицы решений содержит по крайней мере одну нулевую клетку.

Подсчитаем транспортные  затраты  исходя  из  данных  матрицы транспортных издержек cij:

Затраты L1 составят:

                                                               L1 = 8 5 + 2 2 + 8 3 + 7 4 = 96.

С целью анализа затрат на  предмет  минимальности  произведем изменение объемов перевозок. Для этого воспользуемся понятием прямоугольной цепи. Выделим цепь в таблице решений и произведем в ней изменение объемов перевозок на одну единицу. Например:

Изменение в общей сумме затрат будет равно:

 c13 - c23 + c22 - c12 = 1 - 4 + 3 - 2 = -2.

Отсюда делаем вывод, что изменение размещения продукции улучшает план перевозок.

Ясно, что указанный путь перебора различных размещений грузов и вычисления соответствующих затрат  весьма  утомителен  и  займет много времени.  Поэтому существуют разные методы упрощающие процедуру исследования всех допустимых изменений  размещения  грузов  и позволяющие быстро  находить  нужные  решения.  Рассмотрим один из них. Он называется методом теневых затрат.  Вводим теневые затраты ui по строкам и vj по столбцам. Эти затраты определяются следующим образом. Строится таблица теневых затрат в виде:

Смысл имеет рассматривать только непутевые клетки первого полученного допустимого  решения.  Эти  клетки  в таблице обозначены знаком * (звездочка).  Теневые затраты ui и vj ищутся такими,  что cij = ui + vj для  каждой клетки таблицы.  Например,  полагаем u1 = 0, тогда v1 = 5,  так как    c11 = 5 = 0 + 5 = u1 + v1.  Далее полагаем v2 = 2,  чтобы c12 = 2,  так как по определению u1 + v2 = c12.  Но тогда необходимо,  чтобы u2 = 1,  так как c22 = 3 = u2 + v2 = u2 + 2. Наконец, полагаем v3 = 3, чтобы c23 = 4.

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

                  c13 - c23 + c22 - c12 = c13 - (u2 + v3) + (u2 + v2) -  (u1 - v2) = c13 - (u1 +v3).

Если теперь для нулевых клеток таблицы, которые предполагается сделать ненулевыми в ходе поиска оптимального значения,  вычислить суммарные теневые затраты (в данном случае u1 + v3)  и  сравнить их  с истинными затратами (c13),  то сразу видно, уменьшают ли эти изменения общие затраты или нет.  Если в данном случае  c13  < (u1 + v3), то общие затраты при таком перемещении уменьшаются.

В предыдущей таблице значения cij и (ui  +  vj)  для  нулевых клеток представлены в скобках. Из сравнения их значений видно, что построенное первое допустимое решение не  является  оптимальным  и план перевозок, представленный этим решением, требует изменений.

Очевидным является также факт,  что наиболее предпочтительным направлением корректировки  первоначального  плана  представляется прямоугольная цепь с нулевой клеткой, где разность между cij и (ui + vj)  максимальна.

Продолжим дальнейшее рассмотрение поставленной задачи.  Перемещение в  выбранной  прямоугольной  цепи делаем до тех пор, пока в ней не появится новая нулевая клетка. Опять считаем теневые затраты и сравниваем их  с соответствующими cij.  Этот процесс продолжаем до тех пор, пока разность между cij и (ui + vj) для  любых  i,j  будет отрицательной.

Следуя указанным правилам, находим второе  допустимое  решение  задачи:

Простой расчет показывает, что это решение неоптимально. Общая сумма затрат в этом варианте составляет  92  единицы.  Однако, нулевая  клетка  в первой строке и втором столбце имеет превышение значения cij над суммой ui и vj,  поэтому при следующих изменениях решения  представляется  нецелесообразным  изменять данные второго столбца.

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

Общие транспортные затраты в этом варианте составляют 67 единиц, тем не менее это еще не оптимальное решение,  так как имеется нулевая клетка, где разность cij - (ui + vj)  £ 0.

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

Легко заметить,  что это уже оптимальное решение задачи в целом. Общие  транспортные  расходы  при таком плане перевозок будут минимальными и составят 58 единиц.

Рассмотрим один  важный  аспект  методов решения транспортной задачи, когда число используемых перевозок окажется меньше m + n - 1. Это - так называемый вырожденный случай.  При этом не представляется возможность вычислить теневые затраты, и  процесс  улучшения плана останавливается.

Одним из выходов из этой ситуации  является  следующий  алгоритм. Увеличиваем  искусственно  вместимость каждого из складов на малую величину x, а выпуск одного из заводов на nx единиц (n - число складов). Тогда процесс решения может быть продолжен,  а в окончательном решении величина x приравнивается 0.

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

Отсюда видно, что имеем только три ненулевых клетки, а следовательно это  вырожденный случай.  Вместимость каждого склада фиктивно увеличиваем на x единиц,  а выпуск завода A2 - на 3x.  Тогда таблица перевозок будет такой:

Подсчитываем разности cij и (ui + vj) для нулевых клеток. Одна из них, а именно cоответствующая индексам 1 и  3,  отрицательна. Следовательно, полученное решение не является оптимальным. Изменяем прямоугольную цепь, включающую второй и третий столбцы (пересылаем по  цепи 7 + x единиц продукции).  Получаем третье допустимое решение в виде таблицы:

Вновь подсчитываем разности истинных издержек и теневых  затрат в нулевых  клетках и убеждаемся в их положительности. Таким образом получили оптимальное решение.  Полагая в нем x = 0, получаем искомое решение исходной задачи.

З А Д А Ч И  П О  Т Е М Е

ЗАДАЧА 5.1.

Найти размещение, минимизирующее транспортные издержки,  при условиях, сформулированных в следующей таблице:

F - объем производства завода,  W - вместимость склада,  cij - стоимость перевозки с i-го завода на j-ый склад.

ЗАДАЧА 5.2.

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

F - объем производства завода,  W - вместимость склада,  cij- стоимость перевозки с i-го завода на j-ый склад.

ЗАДАЧА 5.3.

Найти размещение, минимизирующее транспортные издержки,  при условиях, сформулированных в следующей таблице:

F - объем производства завода,  W - вместимость склада,  cij - стоимость перевозки с i-го завода на j-ый склад.

ЗАДАЧА 5.4.

Найти размещение, минимизирующее транспортные издержки,  при условиях, сформулированных в следующей таблице:

F - объем производства завода,  W - вместимость склада,  cij - стоимость перевозки с i-го завода на j-ый склад.

ЗАДАЧА 5.5.

Найти размещение, минимизирующее транспортные издержки,  при условиях, сформулированных в следующей таблице:

F - объем производства завода,  W - вместимость склада,  cij - стоимость перевозки с i-го завода на j-ый склад.

ЗАДАЧА 5.6.

Найти размещение, минимизирующее транспортные издержки,  при условиях, сформулированных в следующей таблице:

F - грузоподъемность корабля,  W - вместимость порта,  cij - стоимость перевозки i-м кораблем в j-ый порт.