ВЕТОШКИН А.А., КОСТЯКОВА А.И. ТРАНСПОРТНАЯ ЗАДАЧА МЕТОДЫ ЗАДАНИЯ БАЗОВОГО ПЛАНА ПЕРЕВОЗОК. ВЫРОЖДЕННОСТЬ ТРАНСПОРТНОЙ ЗАДАЧИ И КАК С НЕЙ БОРОТЬСЯ


ВЕТОШКИН А.А., КОСТЯКОВА А.И. ТРАНСПОРТНАЯ ЗАДАЧА МЕТОДЫ ЗАДАНИЯ БАЗОВОГО ПЛАНА ПЕРЕВОЗОК. ВЫРОЖДЕННОСТЬ ТРАНСПОРТНОЙ ЗАДАЧИ И КАК С НЕЙ БОРОТЬСЯ


Рубрика: 01.00.00 ФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:
// Современные научные исследования и инновации. 2012. № 2 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2012/02/6800 (дата обращения: 28.09.2017).

Транспортная задача

Методы задания базового плана перевозок

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

Одной из распространенных задач оптимизации является транспортная задача.

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

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

 

1) Метод северо-западного угла. Просматривается матрица  перевозок D, начиная с левого верхнего угла (клетки). Находится незанятая клетка, в нее записывается величина Dij=MIN(Ai, Bj). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс повторяется для левой верхней клетки оставшейся матрицы до тех пор, пока весь запас товаров не будет исчерпан.

 

2) Метод Двойного Предпочтения.  Просматривается  вся матрица тарифов перевозок и из нее выбирается клетка с наименьшим значением тарифа Cij. И в строке и в столбце значение должно быть минимальным. Затем в данную клетку записывается величина D=MIN(Ai, Bj). Она вычитается из запасов и потребностей соответствующего склада и магазина. При наличии нескольких клеток с одинаковыми значениями выбирается произвольная. Обнулившаяся строка и столбец исключаются из рассмотрения, затем процесс повторяется для оставшейся части матрицы до тех пор, пока весь запас товаров не будет исчерпан.

 

3) Метод минимального элемента. Просматривается вся матрица тарифов перевозок, и из нее выбирается клетка с наименьшим значением тарифа Cij, При наличии нескольких клеток с одинаковыми значениями выбирается произвольная. Затем в данную клетку записывается величина D=MIN(Ai, Bj). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс повторяется для оставшейся части матрицы до тех пор, пока весь запас товаров не будет исчерпан.

 

4) Метод Фогеля. Просматриваются все строки и столбцы матрицы тарифов, вычисляется разность между двумя наименьшими элементами в строке или в столбце. Затем из всех этих разностей максимальная. По индексу наименьшего элемента, соответствующего этой разности выбираются строка и столбец. Затем в данную клетку записывается величина D=MIN(Ai, Bj). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс повторяется для оставшейся части матрицы до тех пор, пока весь запас товаров не будет исчерпан.

 

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

 

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

 

1) Метод Приоритета Больших перевозок. Основой для него является метод Минимального Элемента. Просматривается вся матрица тарифов перевозок, и из нее выбирается клетка с наименьшим значением тарифа Cij, При наличии нескольких клеток с одинаковыми значениями выбирается та, в которой Dij=MIN(Ai, Bj) максимально (этот этап определяет различие методов). При наличии нескольких клеток с одинаковыми значениями выбирается произвольная.. Затем в данную клетку записывается величина Dij=MIN(Ai, Bj). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс повторяется для оставшейся части матрицы до тех пор, пока весь запас товаров не будет исчерпан.

 

2) Метод Размена Больших значений. Он заключается в том, что просматриваются значения параметров складов и магазинов. Из этих параметров выбирается наибольшее значение. При наличии нескольких одинаковых значений в соответствующих строках или столбцах выбирается минимальное значение тарифа в этих строках (столбцах). Если опять получилось несколько одинаковых значений, то выбирается максимальное Dij=MIN(Ai,Bj). При наличии нескольких одинаковых на этом этапе выбирается первое из имеющихся с приоритетом складов. Затем в выбранную клетку записывается величина Dij=MIN(Ai, Bj). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс повторяется для оставшейся части матрицы до тех пор, пока весь запас товаров не будет исчерпан.

 

Сравнительное исследование известных методов и разработанных нами показало, что метод Приоритета Больших Перевозок практически равноценен методу минимальных значений, а метод Размена больших Значений не уступает методу Фогеля, а в ряде случаев превосходит его. В сравнительной таблице приводятся результаты решения задач, взятых из произвольных источников. Задачи с номерами от 15 до 35 приведены из книги Лунгу К. Н. Линейное программирование. Руководство к решению задач. М. Физматлит, 2005, глава 2.

 

№ за-да-чи

Опти-мальный План Пере-возок

Северо-Запад-ный Угол

Двойное Предпоч-тение

Мини-мальное Значение

Метод Фогеля

Размен Больших Значений

Приори-тет Больших Пере-возок

1

330,0

382,0

360,0

360,0

332,0

332,0

340,0

2

331,0

796,0

361,0

361,0

361,0

336,0

361,0

3

451,0

937,0

451,0

451,0

471,0

608,0

451,0

4

430,0

740,0

450,0

450,0

450,0

450,0

470,0

5

347,0

573,0

361,0

361,0

348,0

358,0

358,0

6

11770,0

13930,0

12040,0

12040,0

11770,0

12040,0

12040,0

7

703,0

1039,0

745,0

745,0

709,0

709,0

745,0

8

750,0

940,0

910,0

910,0

750,0

750,0

910,0

9

5715,0

5724,0

5731,0

5731,0

5715,0

5731,0

5743,0

10

4450,0

5650,0

4750,0

4750,0

4750,0

4750,0

4750,0

11

208,5

235,5

226,5

226,5

208,5

212,5

226,5

12

1680,0

2560,0

1880,0

1880,0

1680,0

1680,0

1880,0

13

3150,0

5750,0

5250,0

5250,0

3200,0

3950,0

5250,0

14

1940,0

2880,0

1950,0

1950,0

1950,0

2000,0

2000,0

15

665,0

1295,0

665,0

665,0

665,0

665,0

665,0

16

150,0

150,0

150,0

150,0

150,0

150,0

150,0

17

840,0

920,0

920,0

920,0

840,0

840,0

920,0

18

840,0

1950,0

1100,0

1100,0

840,0

1100,0

1100,0

19

1560,0

2644,0

1751,0

1751,0

1602,0

1830,0

1830,0

20

668,0

1906,0

1194,0

1194,0

720,0

952,0

1122,0

21

4102,0

7682,0

6077,0

6077,0

4257,0

5040,0

5905,0

22

2090,0

2770,0

2090,0

2090,0

2090,0

2090,0

2090,0

23

470,0

530,0

550,0

550,0

470,0

530,0

530,0

24

3500,0

4500,0

      3700,0

3700,0

3500,0

3800,0

3800,0

25

324,0

456,0

        354,0

354,0

324,0

324,0

354,0

26

400,0

620,0

        440,0

440,0

400,0

420,0

440,0

27

2150,0

3130,0

      2760,0

2760,0

2150,0

2170,0

2170,0

28

4980,0

7530,0

      7357,0

7357,0

6798,0

5732,0

7335,0

29

2370,0

4695,0

      2950,0

2950,0

2395,0

2960,0

3295,0

30

1610,0

2245,0

      1770,0

1770,0

1665,0

1740,0

1770,0

31

5590,0

13700,0

    10340,0

10340,0

5590,0

6880,0

10340,0

32

11380,0

22240,0

    11380,0

11380,0

11380,0

12340,0

11380,0

33

4280,0

5780,0

      4430,0

4430,0

4430,0

5330,0

4430,0

34

310,0

509,0

        316,0

316,0

316,0

329,0

316,0

35

31000,0

41000,0

    31000,0

31000,0

31000,0

33000,0

31000,0

36

180,0

340,0

        240,0

240,0

180,0

200,0

240,0

37

2312,0

3276,0

      2696,0

2696,0

2336,0

2696,0

2696,0

 

Из таблицы видно, что метод Приоритета Больших Перевозок в 7‑и задачах уступает методу Минимальных Значений, в 24-х дает одинаковую с ним оценку (отмечено жирным шрифтом) и в 6-и – превосходит этот метод (жирный наклонный шрифт).

Метод Размена Больших Значений определенно лучше метода Минимальных Значений, он в 18-х задачах дает лучшую оценку и в 7-и одинаковую. По сравнению с методом Фогеля в 12-и задачах оценка равна или лучше (жирный шрифт). Более того, В 7-и задачах метод дает сразу оптимальный план перевозок (шрифт жирный наклонный).

 

Выводы

 

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

Но, в свою очередь, метод Размена Больших Значений заслуживает внимания по нескольким причинам:

1) Оценка метода почти не уступает общепринятому методу Фогеля при более простой реализации;

2) Понятный физический смысл метода (перевозка больших объемов при прочих равных условиях предпочтительнее) делает его более привлекательным для реализации по сравнению с тем же методом Фогеля;

3) Реализация метода сама по себе не представляет больших сложностей.

Вырожденность транспортной задачи

и как с ней бороться

Как известно, транспортная задача бывает открытая и закрытая. Открытой называется задача, в которой баланс поставщиков и потребителей не равны между собой. Это явление обычно и встречается сплошь и рядом. Способ борьбы с этим единственен и прост: добавляем фиктивного поставщика, если баланс поставщиков меньше, чем баланс потребителей, и наоборот.

 

К сожалению, известно и то, что транспортная задача является вырожденной и невырожденной. Вырожденной является такая задача, в которой количество клеток в плане меньше m+n-1, где m - количество поставщиков, n – количество потребителей. Понятно, что это явление тоже часто встречается. Способ борьбы с ним у каждого свой: от случайно размещаемых нулевых клеток в плане до перебора по очереди всех пустых клеток. Ни то ни другое не дает гарантий в том, что вновь размещенная клетка не образует цикл с имеющимися клетками.

 

С первого взгляда кажется, что вырожденность задачи – явление случайное и никаким законам не подчиняется. Даже более того, базовые планы, созданные с помощью различных методов, например, Северо-западного угла и Минимальных значений, дают вырожденный и невырожденный планы для одной и той же задачи. Это, естественно, порождает мысли: скрыта вырожденность в задаче или метод создания плана создает ее. Но когда в другой задаче не срабатывает, наоборот, тот метод, который только что создал нормальный невырожденный план, остается одна мысль: вырожденность – явление потустороннее и не зависит от задачи и применяемого метода создания плана.

 

И все-таки существует способ не только избавиться от вырожденности, но и «уничтожить» ее насовсем. Каким образом? Какова природа вырожденности и откуда она возникает? Рассмотрим вопрос в таком порядке: природа вырожденности; откуда (и почему) возникает вырожденность; как с ней бороться.

 

Итак, природа вырожденности. Вырожденность – когда не хватает клеток-уравнений для определения потенциалов в плане. Это, когда необходимо для нормальной работы m+n-1 уравнение, а их, к сожалению, m+n-2. И еще хуже, если их получается только m, как в этой задаче (см. таблица 1) при использовании метода Северо-западного угла.

 

Таблица 1

Получатель> Источник   v

10

20

30

10

5

4

1

20

4

3

2

30

1

2

3

 

Как видим, в таблице (см. таблица 2) заполнены только 3 клетки при необходимом количестве 5. Ну, очень вырожденный план. Какие 2 из 4-х пустых клеток ввести в план? Кстати, оценка этого плана равна 200, оценка оптимального плана, который получится при решении задачи, будет равна 100. Такие задачи можно придумать для любого метода составления базового плана, даже в этой задаче, где все другие методы сразу дают оптимальный план, у них в плане участвуют только по 4 клетки.

 

Таблица 2

10

20

30

 

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

 

Таблица 3

10

0

20

10

20

 

Далее, откуда возникает вырожденность. Рассмотрим по шагам составление базового плана нашей задачи. Распределяя первую строку, получаем клетку (1,1), обнуляем поставщика и получателя. То есть, добавляя одну клетку, мы избавились (к сожалению) от двух переменных сразу. Со второй строкой получается аналогичная картина. И к окончанию создания плана мы имеем «недостачу» трех

 

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

 

Таблица 4

10

0

0

20

30

 

Таким образом, перебрав несколько (а в большой матрице много) вариантов, приходим к следующему плану (см. таблица 5).

 

Таблица 5

10

0

20

0

30

 

В дальнейшем будет показано и обосновано, как можно создать план, обладающий двумя очень важными достоинствами: количество клеток равно точно m+n-1, полное отсутствие циклов. Для этого необходимо в случае, когда обнуляются поставщик и получатель, добавлять клетку с нулевым значением в ЛЮБОЙ незанятый столбец (такая операция некоторыми, бывает, проводится интуитивно). Если незанятых столбцов нет, то никаких действий не производится. Просто это означает, что все столбцы обнулены, и план составлен. Естественно, возникают два вопроса: об образовании циклов с участием этой нулевой клетки и о вырожденности полученного плана. Для решения первого вопроса докажем теорему «О невозможном внедренном цикле». После этого посчитаем количество получившихся клеток и сравним с m+n-1.

 

Теорема: О невозможном внедренном цикле

 

Определения:

Занятый столбец – столбец, в котором находится клетка плана и значение получателя равно 0.

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

П-конструкция – вертикальный отрезок в столбце k (туловище) с концами на строках i и j и двумя горизонтальными «хвостами», направленными в одну сторону, например, вправо. Любые другие ориентации сводятся к данной путем поворотов или отражений.

 

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

 

Доказательство: любой цикл содержит в себе П-образную конструкцию, обозначены номерами от 1 до 4 (см. рисунок 1).

 

1         2   2    3         1          2

 

 

 

4         3   1                   4     3

4

 

Рисунок 1. Различные виды циклов.

 

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

 

Таблица 6

0

10

10

10

 

Если мы докажем, что такая конструкция не может появиться в нашем случае, это и будет означать, что циклы в созданном по правилам плане невозможны.

 

Лемма: В правильно составляемом плане П-конструкции не появляются.

 

Доказательство: Проверим варианты ситуаций, когда данная конструкция может образоваться. Во всех случаях обрабатывается строка j.

1. Строка i имеет одну занятую клетку, и обработка ее закончена.

2. Строка i имеет одну занятую клетку, и обработка ее не закончена.

3. Строка i имеет более одной занятой клетки.

 

Чтобы не запутывать доказательство, условно примем, что в других строках нет ни одной занятой клетки. В противном случае в качестве строки i необходимо проверить все строки по очереди.

В первом случае в строке j в том столбце, где строка i имеет занятую клетку, можно разместить как клетку плана, так и нулевую клетку, поскольку в строке i нет «хвоста», как одного из элементов П-конструкции. В дальнейшем рассмотрении  будем рассматривать случай 3 для столбца, в который мы поместили две клетки.

Во втором случае в строке j в том же столбце нельзя ничего разместить, поскольку столбец уже занят (вспомним, как появляются клетки плана). Так что основы для П-конструкции нет.

Значит, «краеугольным» в доказательстве является случай 3. Очевидно, что все столбцы, в которых расположены занятые клетки строки i, заняты, кроме одного, в котором строка обнулилась (Естественно, два и более незанятых столбцов при наличии клеток плана означают, что строка i обнулялась несколько раз, чего быть не может). Но и он может быть занят, если обнулился вместе со строкой. Если все столбцы заняты, то как и в случае 2, основы для П-конструкции нет.

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

 

Таким образом, П-конструкции в правильно составляемом плане не появляются. И, следовательно, циклы не образуются.  Что и требовалось доказать.

 

Вернемся к вопросу о вырожденности полученного плана. Вспомним, что каждая клетка плана есть по сути одно уравнение в методе потенциалов, связывающее две переменных v(i) и u(j). При расчетах одна переменная является определяемой, вторая определенной. Нам надо сосчитать, сколько определяемых переменных имеется во всех клетках-уравнениях.

Пусть в строке i находится m(i) клеток, не считая нулевой. Посмотрим, что определяют эти уравнения. Если строка i в процессе занесения в план клетки (i, j) обнуляется, а столбец j – нет, то  этим уравнением определяется переменная v(i) и (m(i) – 1) переменных u, кроме, естественно, переменной u(j), которая определится, когда обнулится столбец j. Если столбец обнуляется вместе со строкой, то определяется m(i) переменных u, а добавление нулевой ячейки определяется переменная  v(i) (не забываем, что в последней заполненной строке нет нулевой клетки). Теперь посчитаем уравнения и переменные. Поскольку все столбцы в процессе составления плана обнулены, то сумма m(i) равна общему количеству столбцов, то есть m. Поскольку при обнулении каждой строки (кроме последней) определяется одна переменная v(i), то при обнулении всех строк мы определили n‑1 переменных. Общее количество определенных переменных составляет m + (n‑1). Что и требовалось!

 

ВЫВОД: Применяя правило «Если при создании плана одновременно обнуляются поставщик и получатель, то нулевая клетка плана помещается в любой незанятый столбец» мы получаем невырожденный  и  незацикленный план, и без всяких ухищрений.

 

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

 

Таблица 7

План Разности Цена

10

0

0

0

-2

200

20

0

0

0

0

20

-4

-2

0

 

План Разности Цена

10

4

0

-2

160

10

10

4

0

0

10

20

0

-2

0

 

План Разности Цена

0

10

6

0

0

140

20

6

0

2

10

20

0

-4

0

 

План Разности Цена

10

6

4

0

140

20

2

0

-2

10

0

20

6

0

0

 

План Разности Цена

10

4

2

0

100

0

20

2

0

0

10

20

0

0

2

 

 

*   *   *

 

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

 



Все статьи автора «AnnK»


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

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться: