Новое в науке технике

СЕРИЯ

математика кибернетика

1969

10

В. И. МУДРОВ

ЗАДАЧА

о коммивояжере

В. И. Мудров,

профессор, доктор технических наук

ЗАДАЧА О КОММИВОЯЖЕРЕ

Издательство «Знание» Москва 1969

517.8 M89

Глава I

Математическая формулировка задачи о коммивояжере

§ 1. ПОСТАНОВКА ВОПРОСА

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

Надо прямо сказать, что таких людей, по крайней мере среди инженеров и математиков, в настоящее время нет, но к задаче, известной под этим названием и насчитывающей более чем двухсотлетнюю историю, интерес не только не ослабевает, но, наоборот, постоянно возрастает, и многие знаменитые ученые, начиная с Эйлера1 и Гамильтона2 и кончая выдающимися математиками современности Д. Данцигом3,

1 Эйлер, Леонард (1707—1783 гг.) — великий математик, механик и физик. С 1727 г. академик Российской академии наук. Круг занятий Эйлера был необыкновенно широким и охватывал все разделы современной ему математики и механики, теорию упругости, математическую физику, оптику, теорию машин, теорию музыки, баллистику, морскую науку, страховое дело и т. д. Во всех без исключения разделах он получил основополагающие результаты.

2 Гамильтон, Уильям Роуан (1805—1865 гг.) — знаменитый английский математик и механик. С 1827 г. и до конца жизни — профессор астрономии в Дублинском университете. Является одним из основоположников векторного исчисления, теории гиперкомплексных чисел и вариационных методов механики.

3 Данциг, Джордж Бернард (род. 1914 г.) — известный американский математик, профессор Калифорнийского университета, сотрудник корпорации RAND, один из основоположников теории линейного программирования.

Р. Беллманом1 и другими, предлагали методы ее решения, проверяя одновременно на ней возможности новых вычислительных приемов и методов.

Хотя первоначально задача возникла как чисто развлекательная, впоследствии она утратила этот характер и нашла многочисленные практические применения. Так часто бывает в истории науки. Решения многих задач, казавшихся поначалу развлечениями и головоломками, впоследствии послужили ключом для решения важных теоретических и практических вопросов. Укажем, например, на задачу кавалера Де-Мере2, которая была решена Паскалем3 и послужила толчком для возникновения одного из основных понятий теории вероятностей— понятия математического ожидания, или на игры типа игры в «орлянку», размышления над которыми привели Бореля4 к формулировке основной теоремы теории игр, являющейся в настоящее время главным инструментом при изучении конфликтных ситуаций. При этом, конечно, нужно иметь в виду, что выдающиеся ученые, занимаясь подобными задачами, предвидели фундаментальную роль научных теорий, кладущихся в основу их решения.

Задача о коммивояжере удивительно просто формулируется: коммивояжер, выходящий из какого-нибудь города, желает посетить (n—1) других городов и вернуться к исходному пункту. Известны расстояния между всеми этими городами. Требуется установить, в каком порядке он должен посещать города, чтобы общее пройденное расстояние было минимальным.

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

Простота постановки задачи о коммивояжере сочетается с чрезвычайной трудностью ее решения, причем трудности эти

1 Беллман, Ричард Эрнест (род. 1920 г.) — знаменитый современный американский математик, сотрудник корпорации RAND, основоположник теории динамического программирования. Получил многочисленные результаты, связанные с применением динамического программирования в различных областях математики (вариационное исчисление, автоматическое регулирование, теория аппроксимации, исследование операций и др.).

2 Задача Де-Мере заключается в следующем: два игрока условились сыграть ряд партий, выигравшим считается тот, кто первым выиграл S партий. Игра была прервана тогда, когда один из игроков выиграл a (a<S), а другой b (b<S) партий. Спрашивается, как должна быть разделена ставка.

3 Паскаль, Блез (1623—1661 гг.) — выдающийся французский математик и физик, автор большого числа работ по геометрии, теории чисел, теории вероятностей и т. д. В 1641 г. одним из первых сконструировал суммирующий автомат.

4 Борель, Эмиль (1871 — 1956 гг.) — французский математик, известен своими работами в области анализа, теории множеств и теории вероятностей.

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

В самом деле, выходя из первого города, коммивояжер может направиться в один из (n— 1) городов, откуда в один из (n — 2) оставшихся городов и т. д., пока не останется один-единственный город, откуда он вышел. Таким образом, общее число вариантов, подлежащих просмотру, составляет (n — 1 ) (n — 2) ... 2 ⋅ 1 = (n — 1 )! вариантов. С увеличением числа городов это число чрезвычайно быстро возрастает и уже при 15—20 городах достигает астрономических цифр. Пропорционально возрастает и время на перебор этих вариантов. Поэтому от полного перебора всех вариантов приходится с самого начала отказаться из-за невозможности уложиться в любое разумно назначенное время, а вот поиск методов (алгоритмов), позволяющих быстро находить оптимальный маршрут, оказался чрезвычайно трудным.

О трудности отыскания таких алгоритмов говорит хотя бы тот факт, что за решение одного из контрольных вариантов задачи (для 33 городов) некая мыловаренная компания США установила премию в 10 000 долларов. Только несколько человек угадали оптимальный маршрут, но и их ответы не были признаны решением, поскольку, помимо четких математических предписаний, допускалось применение не более 25 слов текста для обоснования догадки.

Надо заметить, что, учитывая предшествующий опыт неудачных попыток решения задачи, компания не очень сильно рисковала. Примерно такая же по размерам премия, установленная до этого за решение сходной задачи фирмой RAND-Corporation1, так и осталась неприсужденной.

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

1 RAND Corporation — американская компания, проводящая исследования в области отыскания наилучшей политики в организации боевых действий, а также в организации экономики. Название происходит от английских слов Research and Development (исследования и развитие). В числе сотрудников RAND находятся многие выдающиеся математики-прикладники США.

§ 2. НЕКОТОРЫЕ ПРИМЕРЫ

1. Задача Гамильтона

Выдающийся английский математик и механик Гамильтон изобрел игру, получившую в свое время широкое распространение. Игрушка представляет собой додекаедр (правильный многогранник с 12 пятиугольными гранями и 20 вершинами). Считается, что этот додекаедр приблизительно изображает земной шар. Пусть каждая из вершин изображает «столицу» одного из государств. Требуется, двигаясь по ребрам додекаедра, обойти все «столицы», заходя в каждую из них один и только один раз, и вернуться в исходный пункт (рис. 1). Каждый такой путь, если он существует, называется гамильтоновым контуром, или гамильтоновым циклом.

Для того чтобы свести эту задачу к задаче о коммивояжере, будем считать, что расстояние между двумя «столицами» равно 1, если они находятся на одном ребре, и что оно бесконечно (dij=∞) в противоположном случае. Таким образом, мы получим следующую матрицу взаимных расстояний между 20 городами (табл. 1.1, в которой для удобства набора те клеточки, в которых должен стоять знак ∞, оставлены пустыми).

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

Практически установлено, что для указанного додекаедра существует несколько совершенно равноценных гамильтоновых циклов (рис. 2).

Рис. 1

Рис. 2

Таблица 1.1

Номера городов

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

1

X

1

1

1

2

1

X

1

1

3

1

X

1

1

4

1

X

1

1

5

1

1

X

1

6

1

X

1

1

7

1

X

1

1

8

1

1

X

1

9

1

X

1

1

10

1

1

X

1

11

1

X

1

1

12

1

X

1

1

13

1

1

X

1

14

1

1

X

1

15

1

X

1

1

16

1

1

X

1

17

1

1

X

1

18

1

1

X

1

19

1

1

X

1

20

1

1

1

X

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

2. Задача об обходе шахматной доски

Почти аналогично выглядит задача об обходе конем шахматной доски, рассмотренная еще Эйлером.

Перенумеруем все клетки шахматной доски и будем считать, что «расстояние» между двумя клетками равно единице, если конь может за один ход перескочить с одной из них на другую, и что это «расстояние» равно бесконечности в противоположном случае. Составив таким образом «матрицу расстояний» по типу таблицы 1.1 и считая, что конь первоначально стоит на поле a1, попробуем решить незамкнутую задачу о коммивояжере. В этом случае решением задачи о коммивояжере может быть либо L = 63, либо L = ∞. Если окажется, что L = 63, то такой обход возможен, и полученное решение укажет один из искомых вариантов. Если же L = ∞, то обход невозможен. Надо сказать, что любители головоломок нашли пути решения, не прибегая к помощи математики, и один из возможных вариантов такого обхода показан на рис. 3.

3. Сбор по тревоге

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

Пионеры одного звена проживают в разных местах города. Время на движение любого из них до всех других обозначим tij, где i и j — их порядковые номера. Для быстрого сбора звена установлен такой порядок: вожатый, получив сигнал тревоги, идет к одному из пионеров, извещает его о полученном сигнале, а сам направляется на место сбора звена. Этот пионер подобным же образом извещает другого и также направляется на место сбора, и так далее. Последний из пионеров, получив сигнал, прямо отправляется на пункт сбора. Спрашивается, как нужно составить эту цепочку, чтобы время сбора по тревоге всего звена было минимальным.

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

Рис. 3

4. Проводка и энергоснабжение

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

Рассмотрим, например, задачу подводки электроэнергии к рабочим местам. Отправляясь от одного полюса источника энергии, требуется подвести провод к n потребителям и затем замкнуть проводник на другом полюсе. При этом расстояние между точками можно определить по формуле

(x, у, z — координаты места потребления энергии), если допустимо проведение соединяющей проводки напрямую от одной точки до другой, или же несколько более сложным образом, если проводку разрешается осуществлять с соблюдением некоторых ограничений (например, только по стенкам помещения и обязательно параллельно его ребрам). Так, кратчайшее расстояние между точками i и j, определяемое с учетом указанных правил, изображено на рис. 4. Оно складывается из отрезков ia, ab, bj.

Особое значение задачи подобного рода могут иметь при разработке технологии автоматического монтажа радиоаппаратуры.

Рис. 4

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

Пусть у нас имеется два станка и совокупность различных деталей, каждая из которых должна быть последовательно обработана на этих станках (например, токарная обработка и фрезерование). Будем считать, что:

а) на каждом станке может обрабатываться не более одной детали;

б) начавшаяся обработка детали не прерывается вплоть до ее окончания;

в) время на переналадку станков при переходе на обработку следующей детали пренебрежимо мало.

Время обработки k-й детали на каждом из станков обозначим ak и bk. Спрашивается, в каком порядке надо обрабатывать детали, чтобы вся их совокупность была обработана возможно быстрее?

Легко заметить, что какую бы последовательность мы ни выбрали, токарный станок простаивать не будет, обрабатывая одну деталь за другой. Простаивает фрезерный станок, и вот время-то его простоя с момента начала выполнения заказа, по существу, и требуется минимизировать.

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

Пусть у нас имеются две детали, подлежащие обработке. Путем непосредственного просмотра различных комбинаций величин a1, b1, a2, b2 можно установить, что в случае, если

в обработку сначала нужно пускать первую деталь. В противоположном случае, т. е. когда

в обработку следует пускать сначала вторую деталь. Наконец, в случае, если

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

Оказывается, что и в более общем случае нескольких деталей i-я деталь должна обрабатываться ранее j-й детали, если

(1.1)

Если теперь поставить в соответствие каждой i-й детали совершенно произвольную точку на плоскости и считать, что расстояние между i-й и j-й точками равно 1, если соблюдается соотношение (1.1) и rj,j=∞ в противоположном случае, то получим некоторую «матрицу расстояний».

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

Составим небольшой численный пример.

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

Таблица 1.2

Номер детали

Время на токарную обработку

Время на фрезерование

1

11

5

2

7

14

3

5

3

4

10

3

5

13

8

«Матрица расстояний» между точками, о которой только что упоминалось, имеет вид:

Таблица 1.3

Номер детали

1

2

3

4

5

1

X

1

1

2

1

X

1

1

1

3

X

1

4

1

X

5

4

1

1

X

Зададимся произвольным порядком обработки деталей (например, 1, 2, 3, 4, 5) и покажем, как в этом случае определить общее время, затраченное на обработку деталей. Ясно, что первый станок может немедленно начинать обработку очередной i-й детали, как только закончится обработка предыдущей (i—1)-й детали. Со вторым станком дело обстоит несколько сложнее. Время начала обработки i-й детали на фрезерном станке зависит от двух обстоятельств, а именно:

а) закончилась ли ее обработка на токарном станке;

б) освободился ли в это время фрезерный станок.

Таким образом, момент начала фрезерования i-й детали равен

— момент окончания обработки i-й детали на токарном станке;

—момент конца фрезерования (i—1)-й детали. С учетом этих замечаний составим временной график загрузки станков (табл. 1.4—1.6) при различных вариантах их последовательной обработки.

Таблица 1.4

Номер детали

Токарная обработка

Фрезерование

начало

конец

начало

конец

1

0

11

11

16

2

11

18

18

32

3

18

23

32

35

4

23

33

35

38

5

33

46

46

54

Оказывается, что первый приходящий на ум порядок обработки привел к тому, что все детали будут обработаны за 54 часа. Оптимальный порядок 2, 5, 1, 4, 3 (как его определить, мы покажем позже) приводит к тому, что все детали будут обработаны за 49 часов. Обработка этих же деталей в порядке 3, 4, 1, 5, 2 (наименее выгодный вариант) приводит к тому, что детали будут обработаны в течение 61 часа. Время простоя фрезерного станка соответственно составляет 21, 16 и 28 часов1.

Таблица 1.5

Номер детали

Токарная обработка

Фрезерование

начало

конец

начало

конец

2

0

7

7

21

5

7

20

21

29

1

20

31

31

36

4

31

41

41

44

3

41

46

46

49

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

а) выбрать наименьшее среди всех чисел ak и bk;

б) если таким числом окажется ak, то соответствующую деталь поставить самой первой;

в) если таким числом окажется bk, то соответствующую деталь поставить самой последней;

г) повторить эту процедуру по отношению к оставшимся деталям.

Таблица 1.6

Номер детали

Токарная обработка

Фрезерование

начало

конец

начало

конец

3

0

5

5

8

4

5

15

15

18

1

15

26

26

31

5

26

39

39

47

2

39

46

47

61

6. Переналадка станков

Рассмотрим другую задачу, также имеющую отношение к обработке деталей, но в смысле допущений прямо противоположного характера. Именно, пусть некоторая совокупность деталей подлежит обработке на автоматической линии, но в отличие от предыдущей задачи будем считать, что время наладки линии для обработки i-й детали достаточно велико и зависит от того, какая деталь обрабатывалась перед этим. Совокупность времен переналадки сведем в таблицу ti,j. Спрашивается, в каком порядке надо обрабатывать детали, чтобы затраты времени на наладку были минимальными. В данном случае мы не интересуемся временем обработки деталей, поскольку это время входит постоянной величиной в общее время выполнения заказа при любом порядке обработки деталей.

Нетрудно видеть, что сформулированная задача есть в чистом виде задача о коммивояжере для n городов. Надо, чтобы поточная линия побывала в n состояниях, причем сумма времен перехода из одного состояния в другое была бы минимальна.

7. Оптимизация программ

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

а) засылка результата предыдущей операции;

б) вызов чисел из оперативного запоминающего устройства по модифицированным адресам очередной команды;

в) модификация адресов следующей за очередной команды и т. д.

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

Обозначим арифметические блоки, входящие в программу, B1, B2, ..., Bn, причем предполагается, что вычисления всегда начинаются с блока B1 и заканчиваются в блоке Bn, а сами блоки разделены операторами условного перехода. Предположим, кроме того, что из каких-либо соображений (например, опытным путем) удалось установить вероятность pi,j того, что после завершения расчетов в i-м блоке управление будет передано j-му блоку, т. е. будем считать, что задана таблица переходных вероятностей ||pi,j||.

Таблица 1.7

Используя эту таблицу, можно установить математическое ожидание Ni числа случаев использования i-го блока в ходе расчетов [5]. Величина

будет численно выражать математическое ожидание числа случаев, когда в ходе расчетов нет непосредственного следования блока Bj за блоком Bi.

Изображая блоки Bi и Bj точками на плоскости, считая rij «расстоянием» от i-й точки до j-й и находя наиболее ко-

роткий гамильтонов путь, ведущий от точки 1 к точке n, найдем такую последовательность расположения арифметических блоков B1, Bk2, Bk3, Bkn_1, Bn, реализующих программу, для которой математическое ожидание числа нарушений естественной очередности вычислений будет иметь наименьшее значение.

§ 3. НЕОБХОДИМЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ ГРАФОВ

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

Графом (X, U) называется некоторое множество точек X, соединенных направленными отрезками (множество U). Эти направленные отрезки не следует путать с векторами, так как графы строятся без какого бы то ни было учета масштабных соотношений.

Элементы множества X называются вершинами (или точками, или узлами) графа, а направленные отрезки — дугами. Например, на рис. 5 граф (X, U) образован множеством точек, состоящим из x1, x2, x3 и x4, и множеством дуг (x1, x2), (x2, x1), (x2, x3), (x2, x4) и (x3, x3).

Граф называется конечным, если конечны множество X и множество U.

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

Рис. 5

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

Иногда каждой дуге графа ставят в соответствие некоторое число r(xi, xj) =ri,j, называемое «весом» или «длиной» дуги. Тогда длиной пути, проходящего через x1, x2, ...xk, считается сумма длин дуг, его составляющих, т. е. r1,2+r2,3+ ... +rk-1,k.

Граф (Х, U) называется симметричным, если из существования дуги (xi, xj) обязательно следует существование дуги (xj, Xi) и при этом ri,j = rj,i. Для упрощения графического представления в этом случае обе точки соединяют одной непрерывной линией без стрелок.

Граф называется полным, если любые его две вершины соединены хотя бы в одном направлении.

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

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

Рис. 6

Так, в задаче об обходе вершин додекаедра вершины, не соединенные непосредственно между собой ребрами, мысленно соединяются дугами, длины которых предполагаются равными бесконечности. Именно таким образом получена матрица расстояний на стр. 7. Можно было бы слегка видоизменить постановку задачи Гамильтона и считать расстояния между «столицами» равными длине кратчайшего пути между ними, не интересуясь тем, заходят ли такие пути в другие вершины додекаедра. Полные графы, соответствующие этим двум задачам, будут различными, и свойства полученных решений будут также различными. Так, в первой постановке категорически запрещаются маршруты, дважды проходящие через одну вершину додекаедра. Во второй постановке такие заходы допускаются и требуется лишь одно: обход всех до единого городов с минимальной длиной пути, так как в полном графе эти заходы «по пути» никак не отображаются.

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

Рис. 7

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

На рис. 8 изображен граф, соответствующий численному примеру в задаче об определении оптимальной последовательности обработки деталей на двух станках.

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

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

Рис. 8

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

Расширенная таким образом «матрица расстояний», показанная на стр. 11, примет следующий вид:

Таблица 1.8

Номер детали

1

2

3

4

5

π

1

X

1

1

0

2

1

X

1

1

1

0

3

X

1

0

4

1

X

0

5

1

1

1

X

0

π

0

0

0

0

0

X

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

§ 4. ПОСТРОЕНИЕ ПОЛНОГО ГРАФА ЗАДАЧИ О КОММИВОЯЖЕРЕ НА ОСНОВЕ АНАЛИЗА ГРАФА КОММУНИКАЦИЙ

(Задача о кратчайшем пути)

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

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

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

Итак, дан граф коммуникаций (например, такой, как на рис. 7). Будем считать, что расстояние между пунктами i и j равно d0ij. Величина d0i,j<∞, если пункты непосредственно соединены между собой элементарными дугами, и d0i,j = 00, если из одного пункта в другой нельзя проехать, минуя другие вершины графа. Кроме того, положим d0i,j = 0.

Построим совокупность величин d1i,j, d2i,j, ... по правилу [3]

Расчеты следует прекратить, когда матрица ||dki,j|| будет в точности совпадать с матрицей ||dk-1i,j||.

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

вдоль главной диагонали всегда равно нулю) на бесконечно большие числа, так как в любом случае гамильтонов маршрут не должен содержать петель, а указанное преобразование облегчает дальнейшее решение задачи о коммивояжере аналитическими методами.

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

Глава II

Методы решения задачи о коммивояжере

§ 1. ЭВРИСТИЧЕСКИЕ МЕТОДЫ И МЕТОДЫ МОНТЕ-КАРЛО

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

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

Рис. 9

1 Настоящая брошюра еще находилась в производстве, когда в журнале «Operations Research», v. 16, № 3 за 1968 год появился подробный обзор методов решения задачи о коммивояжере, сделанный Беллмором и Немхаузером [13]. В этом обзоре решения, полученные при помощи эвристических приемов, очень удачно названы аппроксимирующими решениями.

улучшение маршрута, то запоминают новый контур и поступают с ним аналогичным образом.

Для задачи о коммивояжере с симметричными условиями наиболее эффективным алгоритмом такого рода является, повидимому, следующий алгоритм [11].

Берем более или менее наугад какой-то контур, проходящий через все точки графа, например, в такой последовательности i1, i2, ..., in, i1. Перенумеруем заново точки графа с тем, чтобы в рассматриваемом контуре они встречались в последовательности 1, 2,..., n. Для произвольных двух точек i и j этого графа вводится операция, именуемая инверсией. Инвер-

сия состоит в следующем. Из контура исключаются дуги (i, i+1) и (j, j+1). Взамен этого в контур включаются дуги (i, j) и (i+1, j+1), а весь путь, расположенный между i+1 и j, проходят в обратном направлении (рис. 9). В результате такой операции получается новый контур 1, 2,..., i, j, j—l,..., i+2, i+1, j+2, n—1, n. Длина этого контура отличается от длины исходного контура на величину Di,j где

Если составить двухмерную таблицу с входами i и j, где i и j изменяются в пределах 2⩽i⩽n, i<j и выбрать наименьшее значение Di,j, то мы перейдем к новому контуру, в пределах которого совершенно аналогичным образом можно искать благоприятную инверсию. Путем этих своеобразных итераций можно довольно хорошо улучшить результат первого приближения. Отметим, что в отдельных случаях, таких, например, как изображенный на рис. 10, можно в пределах одной итерации отыскать несколько благоприятных инверсий.

Рис. 10

Если улучшение с помощью инверсий на каком-то этапе станет невозможным, то можно попробовать произвести дальнейшее улучшение маршрута другим способом. Например, можно попытаться исключить точку i из ее первоначального места в контуре и поставить ее вслед за точкой j (рис. 11).

В этом случае разность длин контуров составит

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

Особое значение эвристические алгоритмы имеют для решения задачи о коммивояжере методами Монте-Карло.

Методами Монте-Карло называют любую вычислительную процедуру, включающую в себя приемы статистической выборки. Например, для задачи о коммивояжере можно предложить такой вариант поиска оптимального решения. В урну закладываются жетоны с номерами от 2 до n (n соответствует числу городов). Тщательно перемешав жетоны, вытаскивают какой-то номер i2, затем i3 и так до конца. В результате получают некоторый замкнутый маршрут 1, i2, i3, ..., in, 1, подсчитывают его длину и хранят эти сведения в памяти. После этого повторяют процедуру, и, если новый маршрут оказывается хуже предыдущего, то его тотчас забывают, а если он оказывается лучше, то в дальнейшем в качестве эталона для сравнения используют именно ею. При достаточно малых затратах времени на проведение одного такого испытания можно с высокой степенью вероятности рассчитывать на то, что, в конце концов удастся угадать, если не наилучший, то достаточно хороший маршрут. Поэтому для проведения таких испытаний привлекаются обычно ЭВМ, снабженные датчиками случайных чисел, что позволяет затрачивать на один эксперимент тысячные доли секунды.

Рис. 11

Методы Монте-Карло становятся особенно эффективными, если их дополнить эвристическими методами улучшения маршрута. В этом случае время на проведение одного статистического эксперимента несколько увеличивается, но зато резко увеличивается и эффективность эксперимента.

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

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

Указанными способами даже вручную можно довольно успешно улучшать длины гамильтоновых контуров в задачах с 15—20 городами.

§ 2. СВЕДЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ К ЗАДАЧАМ ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Пусть задан некоторый контур в графе (X, U). Его, конечно, можно описать, указав точки, через которые он проходит, например, 1, i2. i3, in, 1. Но этот же контур можно задать совокупностью дуг, которые его составляют, т. е. (1, i2), (i2, i3), (i3, i4), ..., (in, 1). В свою очередь, эта совокупность дуг может быть описана с помощью неотрицательных величин yi,j, где yi,j = 1, если дуга (i, j) входит в рассматриваемый контур, и yi,j = 0 в противоположном случае. Таким образом, получим некоторую матрицу

(2.1)

в которой yi,j равны нулю или единице и соблюдается 2n условий

(2.2)

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

Длина пути, изображаемая этим контуром, как нетрудно проверить, будет равна

То обстоятельство, что все yi,j должны быть положительными и целочисленными, можно учесть, наложив следующие ограничения:

(2.3)

(2.4)

где E(yi,j) —есть операция взятия целой части числа yi,j.

Итак, мы установили, что каждому контуру можно поставить в соответствие некоторую матрицу ||yi,j||, удовлетворяющую условиям (2.2) — (2.4). Обратно, если дана матрица Y, удовлетворяющая этим условиям, то нетрудно указать некоторый контур. Для этого нужно в полном графе (X, U) выделить те дуги(i, j), для которых yi,j=1. Однако, к сожалению, полученный при этом контур не обязательно будет гамильтоновым (рис. 12).

Рис. 12

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

(2.5)

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

является матрицей циклической подстановки, а матрица

не является таковой, так как, выделяя элементы y11, y22 и у44 и соответствующие столбцы и строки, мы получим матрицу

для которой

Итак, повторяем, матрица У должна быть матрицей циклической подстановки. В противном случае мы будем иметь не один контур, обегающий все точки графа, а два или более замкнутых контуров, каждый из которых обегает только часть точек (рис. 12, б). При этом условия (2.2) —(2.4), требующие, чтобы в каждую точку входила и из каждой точки исходила только одна дуга, удовлетворяются.

После того как установлено взаимнооднозначное соответствие между совокупностью гамильтоновых путей в графе и совокупностью матриц У, удовлетворяющих условиям (2.2) — (2.5), можно задачу о коммивояжере сформулировать в следующем виде:

минимизировать выражение

при ограничениях (2.2) — (2.5).

Оказывается, что относительно легко решить задачу, если наложены только ограничения (2.2) и (2.3). При этом автоматически будут выполнены ограничения (2.4). Гораздо труднее удовлетворить условию (2.5). В ряде работ показано, что этому требованию можно удовлетворить, наложив целый ряд специальных линейных ограничений на переменные Например, в работе [4] показано, что матрица (2.1) будет матрицей циклической подстановки, если кроме (2.2) — (2.4) наложены следующие условия:

(2.6)

где ui — некоторые вспомогательные неотрицательные целые величины.

Другой прием, приводящий к той же цели, описывается в работе [9].

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

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

Для задач целочисленного линейного программирования имеются готовые программы их решения на ЭВМ. Однако

практика показывает, что задача о коммивояжере, сформулированная в виде задачи линейного целочисленного программирования, очень плохо поддается решению. Для мало-мальски сложной задачи (например, для 10 городов) приходится обрывать вычисления из-за того, что на решение затрачивается непомерно много машинного (на ЭВМ) времени. Так, при решении несложного варианта задачи о коммивояжере для шести городов после 18 часов непрерывной работы быстродействующую машину пришлось остановить, так и не дождавшись результата (см. также [7]). Помимо больших затрат машинного времени, задачи указанного типа предъявляют очень высокие требования и к объему машинной памяти.

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

Если «повезет», на что обычно мало надежды, то в результате решения задачи назначения будет получен гамильтонов контур. Если же «не повезет», то будет получена совокупность изолированных контуров по типу рис. 12, б и некоторая оценка (снизу) длины оптимального маршрута.

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

которое запрещает образование негамильтонова контура (1,2, 3, 7, 1), никак не сказываясь на множестве гамильтоновых путей задачи.

После этого вновь решается задача минимизации выражения

при ограничениях (2.2) — (2.4) и этом дополнительном условии. Вновь, если «повезет», то в результате решения задачи будет получен гамильтонов контур, который и является решением задачи о коммивояжере. Если же опять получится совокупность нескольких контуров, то, изучая дуги, образую-

1 Более подробные сведения о задаче назначения можно найти в работе [4].

щие контура, можно указать еще одно дополнительное ограничение на переменные yi,j, запрещающее и это решение. Продолжая действовать в том же духе, иногда за короткое время удается найти точное решение задачи о коммивояжере. Так появились сведения о том [13], что с помощью линейного программирования удалось решить один из вариантов задачи о коммивояжере для 42 городов, т. е. задачи очень большого размера.

§ 3. РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДАМИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

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

В случае задачи о коммивояжере эта идея представления задачи в виде многошагового процесса реализуется следующим образом. Отметим среди n точек, которые нужно обойти, произвольную точку, которую будем считать точкой старта и финиша. Первым этапом принятия решения будем считать выбор первой точки, в которую надо идти из места старта, вторым этапом — выбор следующей точки и т. д.

Вычислим функцию потерь на одном из этапов принятия решения. Для этого допустим, что нам удалось каким-то образом правильно выбрать решение на всех предыдущих этапах и мы пришли в точку i. Пусть при этом остались непройденными j1, j2, ..., jk. Спрашивается, как нам поступить дальше и какова минимальная длина пути обхода оставшихся точек? Обозначим последнюю fi(j1, j2, ..., jk), подчеркнув тем самым, что мы находимся в точке i и осталось обойти множество точек с индексами j1, j2, ..., jk.

Если из точки i направиться в точку j1 и затем двигаться по наикратчайшему маршруту, то коммивояжеру предстоит пройти путь длиною

Если же направиться в точку i2, то коммивояжеру предстоит пройти путь длиною

Вообще при движении в точку jm коммивояжеру предстоит проделать путь длиною

Очевидно, что правильным решением будет то, при котором эта сумма имеет минимальное значение. Тем самым мы укажем, куда следует двигаться коммивояжеру из точки i, если осталось пройти точки j1, j2, ..., jk и одновременно величину оставшегося пути

(2.7)

Таким образом, нам удалось выразить функцию fi(j1, j2, ..., jk) через аналогичные по смыслу функции fi(j1, j2, ...jm-1, jm+1, ..., jk), но от меньшего числа аргументов. Все значения функций fi(j1) Для одного аргумента известны — это сумма расстояний от точки i до j1 и от точки j1 до точки старта — финиша j0.

Опираясь на знание значений этих функций, по формуле (2.7) легко вычислить совокупность всех значений функций fi(j1, j2), где j1, j2, i — неравные между собой числа, заключенные между 1 и n, именно

Аналогично

и т. д.

Преимущество, которое дает динамическое программирование, по сравнению с полным перебором, состоит в том, что вместо прямого сравнения (n—1)! вариантов просматривается значительно меньшее число комбинаций и на всех этапах решения задачи производится n22n-1 сравнений. Основная трудность при решении задачи о коммивояжере методами динамического программирования — это проблема запоминания промежуточных результатов. Для того, например, чтобы вы-

числить все значения функции fi(j1, j2), необходимо предварительно запомнить Сп2 чисел fi(j1). Чтобы вычислить значения fi(j1, j2, j3), необходимо помнить Cn3 чисел и т. д. Наиболее критическим является случай, когда k достигает значения —. На этом этапе в задаче с 11 городами приходится запоминать 300 чисел, в задаче с 17 городами— 12 000 чисел, в задаче с 23 городами — 1 300 000 чисел.

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

§ 4. МЕТОД ВЕТВЕЙ И ГРАНИЦ

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

Основная идея метода довольно проста. Вначале строится некоторая оценка снизу длины маршрута для множества всех гамильтоновых контуров. После этого множество всех гамильтоновых маршрутов разбивается на два подмножества. Первое подмножество состоит из гамильтоновых контуров, включающих некоторую дугу (i, j) (обозначим его [i, j]), а другое подмножество состоит из контуров, не включающих эту дугу (обозначим его [i, j]). Для каждого из подмножеств по тому же правилу, что и для первоначального множества гамильтоновых маршрутов, определяется нижняя граница. Каждая новая нижняя граница оказывается не меньше нижней границы, определенной для всего множества. Сравнивая нижние границы, можно отделить подмножество гамильтоновых путей, внутри которого с большей вероятностью содержится оптимальный маршрут. Это подмножество по аналогичному правилу разбивается еще на два, и вновь находятся измененные нижние границы, и так поступают до тех пор, пока не останется единственный цикл. Процесс разбиения подмножеств сопровождается построением некоторого дерева по типу рис. 17.

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

В дальнейшем подмножества гамильтоновых путей, включающее дуги (i1 i2), (i3, i4), ... и не включающее дуги (j1, j2), (j3, j4), ..., мы будем обозначать так [i1, i2], [i3, i4], ..., [j1, j2], [j3, j4], ... Множество всех гамильтоновых путей обозначим [Ur].

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

Для определения нижней границы множества (НГМ) можно было бы воспользоваться задачей назначения, о чем упоминалось в § 3 настоящей главы, однако этот способ несколько громоздок. В работе [8] предложен другой способ оценки, который хотя иногда и дает несколько менее точную оценку, чем решение задачи назначения, но зато чрезвычайно прост с точки зрения вычислений.

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

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

После этого аналогичным образом осуществляется приведение полученной матрицы по столбцам.

Приведенная по строкам и столбцам матрица содержит по крайней мере один нуль в каждой строке и каждом столбце. Так как длина L1 оптимального маршрута в задаче с приведенной матрицей отличается от длины L маршрута в задаче с неприведенной матрицей на сумму констант приведения h, то

L = L1+h.

В приведенной матрице все элементы неотрицательны, поэтому L1⩾0, а сумма констант приведения h может служить нижней границей длины гамильтонова маршрута.

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

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

Поскольку исключение этой дуги представляет важный элемент алгоритма, то на нем следует остановиться несколько подробнее. Включение дуги (i, j) приводит к образованию связного пути, соединяющего некоторые точки р и q (рис. 13). Допустимые маршруты должны проходить через все точки графа, поэтому запрещается включение в маршрут дуги (q, р), так как иначе образуется замкнутый контур, проходящий только через часть точек. В простейшем случае включение дуги (i, j) означает невключение дуги (j, i), т. е. di,j=∞.

Сокращение размеров матрицы и исключение элемента (q, р) позволяет провести дополнительное приведение матрицы и тем самым улучшить нижнюю оценку длины любого гамильтонова маршрута, содержащегося в подмножестве [i, j].

Рассмотрим теперь вопрос о выборе дуги (i, j), играющей столь важную роль при разбиении множества гамильтоновых путей на подмножества.

Наиболее вероятно, что в оптимальный маршрут входят дуги, для которых в приведенной матрице di,j=0. Невключение в маршрут именно этих дуг резко увеличивает нижнюю оценку. Как уже отмечалось, исключая дугу (i, j), мы должны положить di,j=∞ и, осуществляя приведение вновь полученной матрицы, улучшить оценку. Константами приведения являются минимальный элемент в i-й строке и такой же в j-м столбце. Поэтому наиболее резкое изменение оценки произойдет в том случае, когда выбирается тот элемент матрицы расстояний, для которого:

а) di,j = 0;

б) после замены di,j = 0 на di,j = ∞ сумма минимальных элементов в i-й строке и j-м столбце имеет наибольшее значение.

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

Пусть матрица расстояний имеет вид:

Рис. 13

Таблица 2.1

1

2

3

4

5

6

hi

1

68

73

24

70

9

9

2

58

16

44

11

92

11

3

63

9

86

13

18

9

4

17

34

76

52

70

17

5

60

18

3

45

58

3

6

16

82

11

60

48

11

Для получения нижней границы множества осуществим приведение по строкам. Для этой цели в каждой строке выбираем минимальный элемент и вычитаем его из всех элементов строки. В данном случае константами приведения по строкам являются 9, 11, 9, 17, 3, 11. После приведения по строкам матрица расстояний приобретает следующий вид:

Таблица 2.2

1

2

3

4

5

6

1

59

64

15

61

0

2

47

5

33

0

81

3

54

0

77

4

9

4

0

17

59

35

53

5

57

15

0

42

55

6

5

71

0

49

37

hj

0

0

0

15

0

0

Сумма констант приведения и дает некоторую нижнюю границу длин всех гамильтоновых путей (HTM [Uг] = Σhi=60).

Эта оценка может быть улучшена за счет приведения по столбцам. Константы приведения показаны внизу табл. 2.2. В результате получим НГМ [Uг] = 60+Σhj = 60+ 15 = 75, а матрица расстояний, приведенная по строкам и столбцам, приобретает вид

Таблица 2.3

В соответствии с предписанием мы должны просмотреть все нулевые элементы этой матрицы и выбрать тот, для которого сумма констант приведения матрицы, получаемой в результате замены di,j = 0 на di,j = ∞, была бы максимальна. Поэтому подсчитываем сумму этих констант приведения для всех нулевых элементов.

Начнем с элемента d1,4. Если положить d1,4=∞, то константа приведения по сторонам была бы равна 0, а константа приведения по столбцам— 18. Сумма констант приведения равна 18. Поступая аналогичным образом, устанавливаем, что для d1,6 она равна 0+9 = 9, для элемента d2,5 — 4 + 5 = 9 и т. д. В табл. 2.3 эти суммы констант приведения помещены над каждым нулевым элементом. Максимальная из этих сумм соответствует дуге (4,1). Разбиваем множество [UГ] на два подмножества [4,1] и [4,1].

Исключение дуги (4,1) из числа дуг, входящих в искомый маршрут, достигается заменой этого элемента знаком ∞. В результате такой замены появляется возможность осуществить дополнительное приведение матрицы путем вычитания из четвертой строки 17 и из первого столбца 5. В результате такого приведения матрица расстояний для множества [4,1] примет вид:

Таблица 2.4

а нижняя граница длин гамильтоновых контуров для этого подмножества равна НГМ [4,1] = 75 + 17 + 5 = 97.

Включение дуги (4,1) в состав искомого маршрута ведет к автоматическому исключению из маршрута дуг (4,2) (4,3), (4,5) и (4,6), выходящих из четвертого пункта (т. е. всей четвертой строки), а также дуг (2,1) ,(3,1), (5,1) и (6,1), входящих в первый город (т. е. всего первого столбца). Кроме того, из числа дуг, входящих в маршрут, должна быть исключена дуга (1,4) с тем, чтобы воспретить образование замкнутого контура (4, 1,4). Для улучшения оценки должны быть использованы числа матрицы, которая получается после удаления четвертой строки и первого столбца и замены величины d1,4 знаком ∞, т. е. числа такой матрицы;

Таблица 2.5

Эта матрица также допускает дополнительное приведение по четвертому столбцу на 18 единиц и соответствующее улучшение оценки. После приведения матрица расстояний приобретает вид:

Таблица 2.6

Нижняя граница множества [4,1] теперь равна 93.

Таким образом, мы начали процесс образования дерева (рис. 14).

Процесс дальнейшего ветвления рекомендуется вести так, чтобы возможно скорее получить некоторый маршрут. Длину этого маршрута можно использовать для того, чтобы обрезать большое число ветвей с нижней границей, превышающей длину этого маршрута. Именно поэтому в первую очередь мы будем дробить на подмножества множество [4,1], а не множество [4,1].

Множество [4, 1] имеет в качестве нижней границы h = 93 и допускает для построения кольцевого маршрута использование дуг, длины которых приведены в табл. 2.6.

В соответствии с предписанием алгоритма отыскиваем дугу, исключение которой максимально бы увеличило нижнюю оценку. Для этого выполняем те же действия, какие мы про-

Рис. 14

делали при выборе дуги [4,1], т. е. просматриваем нулевые элементы, предварительно помеченные суммой констант приведения, образующихся после замены di,j = 0 на di,j =00 (эти величины помещены в углах над нулевыми элементами в табл. 2.6). Максимальное значение суммы констант приведения соответствует элементу d1,6. Поэтому будем улучшать НГМ [4,1], [1,6] и НГМ [4,1], [1,6].

Исключение дуги (1,6) приводит к улучшению оценки на 68единиц. Поэтому НГМ [4,1], [1,6] = 93 + 68= 161.

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

Таблица 2.7

Дерево разбиения на подмножества приобретает вид, показанный на рис. 15.

Действуя в том же духе, будем рассматривать подмножества гамильтоновых контуров [4,1], [1,6], [6,3] и [4,1], [1,6], [6,3].

Для первого подмножества НГМ [4,1], [1,6], [6,3]= 130.

Рассмотрим второе подмножество. Включение дуги (6,3) автоматически исключает шестую строку и третий столбец. Для устранения негамильтонова контура (4,1,6,3,4) необходимо запретить дугу (3,4). Для дальнейшего улучшения оценки используется матрица:

Рис. 15

Таблица 2.8

допускающая приведение по пятой строке и улучшение оценки на девять единиц.

После приведения эта матрица выглядит следующим образом:

Таблица 2.9

Дерево разбиения на подмножества представлено на рис. 16.

Рис. 16

Дальнейшим шагом является рассмотрение подмножества [4,1], [1,6], [6,3], [3,2] с НГМ= 102+10= 112 и подмножества [4,1], [1,6], [6,3], [3,2]. Включение дуги (3,2) запрещает использование элементов третьей строки и второго столбца, а также

дуги (2,4). Поэтому для последующих оценок используется матрица:

Таблица 2.10

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

Таким образом, дальнейшее развитие дерева (рис. 17) привело к образованию определенного гамильтонова маршрута длиною 102 единицы. Сопоставляя длину найденного маршрута с нижней границей длин маршрутов, входящих в подмножества [4,1]; [4,1], [1,6], [4,1], [1,6], [6,3]; [4,1], [1,6], [6,3], [3,2], не рассмотренных до конца, мы видим, что рассмотрение подавляющего большинства из них не имеет никакого смысла.

Рис. 17.

Это обстоятельство отражено на рис. 17 обрывом соответствующих ветвей ([4,1], [1,6] и др.).

Однако может оказаться, что среди гамильтоновых контуров подмножества [4,1] с нижней границей h = 97 имеется лучший маршрут. Поэтому надо изучить это подмножество, работая с матрицей, показанной в табл. 2.4.

Следуя методике, мы должны рассмотреть подмножества гамильтоновых контуров [4,1], [6,1] и [4,1], [6,1]. Нижняя граница первого подмножества равна

в силу чего это подмножество может в дальнейшем не рассматриваться. Что касается второго из указанных подмножеств, то включение дуги (6,1) требует изъятия шестой строки и первого столбца в табл. 2.4. Кроме того, во избежание появления негамильтоновых циклов надо положить d1,6 = ∞. В результате этих преобразований получим таблицу:

Таблица 2.11

которая допускает приведение по шестому столбцу. Приведение улучшает нижнюю оценку, которая становится равной

Следовательно, каждое из рассмотренных подмножеств в качестве нижней границы имеет величину большую, чем найденный гамильтонов контур (4,1,6,3,2,5,4) длиною 102 единицы, и их нет смысла рассматривать.

Дерево разветвлений в окончательном виде с указанием нижних границ показано на рис. 18.

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

Один из алгоритмов такого рода предложен Шапиро. Начальная оценка снизу длины любого гамильтонова контура получается при помощи решения задачи назначения. Если при этом задача назначения позволила указать какой-либо гамильтонов контур, то, как указывалось ранее (§ 2), это означает, что получено решение задачи о коммивояжере. Если же решение задачи назначения привело к образованию нескольких разрозненных негамильтоновых контуров по типу рис. 12,б, то поступают следующим образом. Берут один из контуров (например, i1, i2, ..., ik, i1) и решают одну за другой k новых задач назначения, отличающихся от исходной задачи тем, что в первой из них предполагается, что di1,i2 = ∞, во второй di2,i1 = ∞ и т. д. Решение первой задачи дает нижнюю оценку длины множества гамильтоновых контуров [i1, i2], решение второй задачи дает НГМ [i2, i3] и т. д.

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

Рис. 18.

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

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

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

Глава III

Экстремальные комбинаторные задачи

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

Из большого числа таких задач мы более или менее подробно опишем три:

а) задачу балансирования сборочной линии;

б) задачу составления расписания работ;

в) задачу последовательной обработки изделий на M станках.

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

§ 1. ЗАДАЧА БАЛАНСИРОВАНИЯ СБОРОЧНОЙ ЛИНИИ

Пусть для того чтобы изготовить некоторое изделие, нужно произвести совокупность работ A1, A2, ..., An, причем указано время, необходимое для осуществления каждой работы tk. Кроме того, указаны условия предшествования, вытекающие из технологии процесса сборки, т. е. условия вида «работа Ai должна быть сделана прежде, чем начнется работа Ak». Коротко условия предшествования записывают так: (< знак предшествования), а всю совокупность этих условий

изображают в виде некоторого ориентированного графа (по типу рис. 19), в котором каждому отношению i<k соответствует дуга, идущая от вершины i к вершине k. Наконец, пусть указано число M последовательно расположенных рабочих мест на конвейере.

Требуется так распределить работы между рабочими местами, чтобы:

а) удовлетворялись условия предшествования;

б) сумма времен выполнения работ, приписанных j-му месту, не превышала времени такта работы конвейера Т;

в) время такта Т было бы минимальным.

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

Иногда эту задачу формулируют несколько иначе, требуя минимизации числа рабочих мест M при заданном времени такта Т.

Покажем, каким образом сформулировать эту задачу как задачу линейного программирования,

Рис. 19

Обозначим через yi,j неизвестную величину, принимающую два значения (0 или 1) и будем считать, что i-я работа производится на j-м рабочем месте, тогда и только тогда, когда 1, и имеет место обратное, если yi,j = 0.

Каждая работа должна быть обязательно выполнена на одном из рабочих мест, поэтому

Суммы вида

численно равны сумме времен выполнения всех работ на j-м рабочем месте. На эти суммы накладываются ограничения

Из отношения предшествования i<k следует, что

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

минимизировать Т при следующих ограничениях

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

методами являются различные эвристические приемы в сочетании с методами статистической выборки, методы динамического программирования и метод ветвей и границ. В частности, для задачи балансировки сборочных линий эффективным алгоритмом является алгоритм, описанный в работе [12].

§ 2. ЗАДАЧА РАСПИСАНИЯ

Проблема составления расписаний порождает обширный класс задач самой разнообразной структуры. Одна из возможных ее постановок состоит в следующем [4]. Имеется M станков и n работ, причем как и в только что рассмотренной задаче о балансировке сборочной линии на некоторые работы наложены ограничения типа предшествования i<k (< — знак предшествования). Предполагается известным время til обработки i-й детали на l-м станке и время tli,j переналадки l-го станка при переходе с i-й на j-ю деталь. Требуется так распределить работы между станками, чтобы время выполнения всего задания было минимальным.

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

К задачам расписания относят также и задачи такого типа [2]. Имеется совокупность работ A1, A2, ..., An и одна машина. Каждая работа требует для своего выполнения единиц времени. Заданы функции Сi(t), характеризующие выгоду, связанную с окончанием выполнения i-й работы в момент t (например, срочное и обыкновенное исполнение заказа, выплата неустойки за несвоевременное исполнение и т. д. (рис. 20). Предполагается, что машина загружена постоянно и никакая работа, раз начатая, не прерывается до ее завершения. Требуется установить такую очередность выполнения работ, при которой суммарная выгода максимальна. Покажем, каким образом эта задача может быть сформулирована как задача динамического программирования.

Выделим из всей совокупности работ некоторое подмножество S, состоящее из k работ j1, j2, ..., jk. Общее время выполнения этих работ обозначим tS, а суммарную выгоду, связанную с выполнением перечисленных работ в оптимальном порядке, f(S). Допустим, что среди работ j1, j2, ..., jk последней выполняемой работой была работа jm. Тогда при оптимальном порядке выполнения остальных работ выгода составит

где S — jm обозначает подмножество работ S, из которого исключена работа jm.

По определению функция f(S) представляет собой максимальную выгоду при выполнении S работ, поэтому

Вспоминая смысл множеств S и S — jm, эту формулу можно переписать более подробно

Рис. 20.

Таким образом, нам удалось выразить функцию f(j1, j2, ..., jk) от k аргументов через известные Сjт(ts) и аналогичные по смыслу функции f(j1, j2, ..., jm-1, jm+1,..., jk), но от меньшего числа аргументов. Функции /(/m) для одного аргумента известны, это просто-напросто значения Cjm(tim).

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

§ 3. ПОСЛЕДОВАТЕЛЬНАЯ ОБРАБОТКА ДЕТАЛЕЙ НА ТРЕХ СТАНКАХ

В § 2 главы I был рассмотрен один из важных случаев задачи расписания — задача определения оптимального порядка обработки деталей на двух станках (например, токарном и фрезерном) и показано, что эта задача может быть сведена к задаче о коммивояжере. Далее было показано, что одним из наиболее эффективных способов решения задачи о коммивояжере является метод «ветвей и границ».

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

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

Итак, пусть заданы времена ti,l (i=1, 2, ..., п; l=1, 2, 3) обработки каждой детали на каждом из станков. Заданы общие для всех деталей условия предшествования, состоящие в том, что каждая деталь сначала обрабатывается на первом, затем на втором и наконец на третьем станке. Время переналадки станков при переходе на новую деталь будем считать пренебрежимо малым. Требуется установить оптимальную очередность выполнения работ, а именно такую, при которой общее время завершения всех работ было бы минимальным.

Доказано, что в общем случае, когда имеется M станков, число возможных вариантов исполнения заказа равно (п!)M-2; в данном конкретном случае, когда М = 3, это число равно п!. Метод «ветвей и гранил», к описанию которого мы сейчас приступаем, позволяет на каждом этапе расчетов отсеивать большое количество заведомо невыгодных вариантов.

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

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

Таблица 3.1

Номер станка

Номер детали

1

2

3

1

7

13

21

2

18

12

15

3

4

17

5

4

9

11

9

5

6

3

6

Пусть задан порядок обработки деталей (например, 1, 2, 3, 4, 5) и требуется определить время окончания работ. Как и раньше (гл. I, § 2) будем вести график начала и конца выполнения работ на каждом станке:

Таблица 3.2

Наименование работ

Первый станок

Второй станок

Третий станок

начало

конец

начало

конец

начало

конец

i1=1

i2=2

i3=3

i4=4

i5=5

0

7

23

29

38

7

25

29

38

44

7

25

37

54

65

20

37

54

65

68

20

41

56

65

74

41

56

61

74

80

При составлении этого графика принималось, что время начала обработки некоторой детали на первом станке совпадает со временем окончания обработки предыдущей детали.

Точно также начало обработки детали i\ на втором и третьем станках совпадает со временем окончания ее обработки на предыдущем станке.

Что же касается остальных случаев, то время tlik начала обработки какой-то ik-й детали на l-м станке совпадает либо с моментом окончания обработки предыдущей детали на данном станке, либо с моментом окончания обработки этой же детали на предыдущем станке, а точнее

Способ ветвления дерева можно принять самый естественный, а именно — исходное множество возможных последовательностей, содержащее п! вариантов, разобьем на i подмножеств, причем варианты первого подмножества начинаются с i1 = 1, второго подмножества с i1 = 2 и т. д. (рис. 21).

В дальнейшем одно из этих подмножеств разбивается еще на n — 1 подмножеств по аналогичному правилу и так до тех пор, пока не дойдет до единственного варианта, эффективность которого может быть точно определена на основе построения таблиц по типу табл. 3.2.

Осталось указать способ вычисления нижней границы для каждого из подмножеств. Это можно сделать различным способом. Например, годятся такие оценки:

h1 — время, необходимое для выполнения на всех трех станках работ i1, i2, ..., ik, выполняемых в первую очередь, плюс время, необходимое для выполнения оставшихся работ на последнем станке, предполагая, что, начиная с этого момента станок работает без простоев;

h2 — время, необходимое для первых k работ на первых двух станках, плюс время, необходимое для выполнения всех

Рис. 21.

оставшихся работ на втором станке, плюс минимальное из времен выполнения оставшихся работ на третьем станке;

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

Ясно, что намного более точна оценка такого рода h = max (h1, h2, h3), но зато она и несколько сложнее вычисляется.

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

Допустим, что мы решили начать обработку с работы i1 = 1. Тогда начало таблицы, построенной по типу табл. 3.2, имеет вид:

Таблица 3.3

Наименование работы

Первый станок

Второй станок

Третий станок

н

к

н

к

н

к

i1=1

0

7

7

20

20

41

Откуда, используя табл. 3.1, получим:

Совершенно аналогично для i1 = 2, i1 = 3, i1=4 и i5 = 5 имеем:

Таблица 3.4

Наименование работ

Первый станок

Второй станок

Третий станок

н

к

н

к

н

к

i1=2

0

18

18

30

30

45

h1=86. h2=79. h3=53. h=86

Таблица 3.5

Наименование работ

Первым станок

Второй станок

Третий станок

н

к

н

к

н

к

i1=3

0

4

4

21

21

26

h1=77, h2=66, h3=53, h=77

Таблица 3.6

Наименование работ

Первый станок

Второй станок

Третий станок

н

к

н

к

н

к

0

9

9

20

20

29

h1=76, h2=70, h3=53, h=76

Таблица 3.7

Наименование работ

Первый станок

Второй станок

Третий станок

н

к

н

к

н

к

i1= 5

0

6

6

9

9

15

h1=65, h2=67, h3=64, h=67

Разбиение исходного множества вариантов на подмножества с указанием нижних оценок продолжительности работ представлено на рис. 21.

В дальнейшем естественно продолжить развитие дерева в вершине i1 = 5, так как именно этой вершине соответствует минимальная нижняя оценка.

Нам предстоит рассмотреть варианты, в которых последовательно i2=1, i2 = 2, i2 = 3, i2 = 4. Имеем

Таблица 3.8

Наименование работ

Первый станок

Второй станок

Третий станок

н

к

н

к

н

к

i1=5

i2=1

0

6

6

13

6

13

9

26

9

26

15

47

h1=76, h2=71, h3=64, h=76

Таблица 3.9

Наименование работ

Первый станок

Второй станок

Третий станок

н

к

н

к

н

к

i1=5

i2=2

0

6

6

24

6

24

9

36

9

36

15

51

h1=86, h2=82, h3=66, h=86

Таблица 3.10

Наименование работ

Первый станок

Второй станок

Третий станок

н

к

н

к

н

к

i1=5

i2=3

0

6

6

10

6

10

9

27

9

27

15

32

h1=77, h2=72, h3=64, h=77

Таблица 3.11

Наименование работ

Первый станок

Второй станок

Третий станок

н

к

н

к

н

к

i1=5

i2=4

0

6

6

15

6

15

9

26

9

26

15

35

h1=76, h2=73, h3=66. h=76

Рис. 22.

Дерево подмножеств приобретает вид (рис. 22 на стр. 55).

Из двух совершенно равноценных продолжений выберем продолжение i2=1. Теперь нам предстоит рассмотреть случаи i3 = 2, i3 = 3, i3 = 4. Для построения дальнейших таблиц используем последнюю строку табл. 3.8.

Таблица 3.12

Наименование работы

Первый станок

Второй станок

Третий станок

н

к

н

к

н

к

i1=5

i2=1

6

13

13

31

13

31

26

43

26

47

47

62

h1=76, h3=64, h=76

Таблица 3.13

Наименование работы

Первый станок

Второй станок

Третий станок

н

к

н

к

н

к

i1=5

i2=1

i3=3

6

13

13

17

13

26

26

43

26

47

47

52

h1=76, h2=75, h3=64, h=76

Таблица 3.14

Наименование работы

Первый станок

Второй станок

Третий станок

н

к

н

к

н

к

i1=5

i2=1

i3=4

6

13

13

22

13

26

26

37

26

47

47

56

h1=76, h2=71, h3=66, h=76

Мы видим, что все три полученных подмножества равнозначны и любое из них может быть выбрано для дальнейшего развития дерева. Остановимся на первом из них. Дальнейшие подмножества различаются тем, что i4=3 либо i4 = 4.

Таблица 3.15

Наименование работы

Первый станок

Второй станок

Третий станок

н

к

н

к

н

к

i1=5

i2=1

i3=2

i4=3

13

31

31

35

31

43

43

60

47

62

62

67

h1=76. h2=80, h3=64, h=80

Таблица 3.16

Наименование работы

Первый станок

Второй станок

Третий станок

н

к

н

к

н

к

i1=5

i2=1

i3=2

i4=4

13

31

31

40

31

43

43

54

47

62

62

71

h1=76, h2=76, h3=66, h=76

Рис. 23.

Таблица 3,17

Наименование работы

Первый станок

Второй станок

Третий станок

н

к

н

к

н

к

i=5

i2=1

i3=2

i4=4

31

40

43

54

62

71

i5=3

40

44

54

71

71

76

В итоге нам удалось установить, что подмножество вариантов, которое начинается работами i1 = 5, i2=1, i3 = 2, i4 = 4 и, следовательно, заканчивается работой i5 = 3 имеет нижнюю границу продолжительности работ h = 76 (рис. 23). Оценим в точности продолжительность полученного варианта (табл. 3.17).

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

Заключение

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

Литература

1. К. Берж. Теория графов и ее применения. М., Изд-во иностр. лит., 1962.

2. М. Хелд, Р. М. Карп. Применение динамического программирования к задачам упорядочения. — Кибернетический сборник, № 9. М., «Мир», 1964.

3. Р. Беллман, С. Дрейфус. Прикладные задачи динамического программирования. М., «Наука», 1965.

4. Е. Г. Гольштейн, Д. Б. Юдин. Новые направления в линейном программировании. М., «Сов. радио», 1966.

5. Ю. С. Голубев-Новожилов. Многомашинные комплексы вычислительных средств. М., «Сов. радио», 1966.

6. С. Джонсон. Оптимальное расписание для двух-и трехступенчатых процессов с учетом времени наладки. — Кибернетический сборник (новая серия), вып. 1, 1965.

7. С. Е. Milier, A. W. Tucker, R. A. Zеmlin. Integer programming formulation and traveling salesman problems. — Journal of the Association for Computing Mashinery, v. 7. 1960, No. 4, Oct., pp. 326—339.

8. Дж. Литл, К. Мурти, Д. Суини, К. Кэрел. Алгоритм для решения задачи о коммивояжере. — «Экономика и математические методы», т. 1, вып. 1, 1965.

9. В. И. Мудров. Определение гамильтоновых путей кратчайшей длины в полном графе методами целочисленного программирования. — Известия АН СССР. Техническая кибернетика, 1965, № 2.

10. A. Lomnicki. A «Branch-and-Bound» Algorithm for the Exact Solution of the Three-Machine Scheduling Problem. — Operational Research Quarterly, v. 16, 1965, No. 1, pp. 89—100.

11. G. A. Groes. A Method for Solving Traveling-Salesman Problems. — Operations Research, v. 6, 1958, No. 5.

12. H. Held, R. M. Karp, R. Shareshian. Assembly-line balancing dynamic programming with precedence constraints. — Operations Research, v. 11, 1963, No. 3.

13. M. Bellmore, G. L. Nemhauser. The Traveling Salesman Problem: a Survey. Operations Research, v. 16, 1968, No. 3.

СОДЕРЖАНИЕ

Стр.

Глава I. Математическая формулировка задачи о коммивояжере .................. 3

§ 1. Постановка вопроса............. 3

§ 2. Некоторые примеры............. 6

§ 3. Необходимые сведения из теории графов ... 15

§ 4. Построение полного графа задачи о коммивояжере на основе анализа графа коммуникаций 20

Глава II. Методы решения задачи о коммивояжере . . 22

§ 1. Эвристические методы и методы Монте-Карло . 22

§ 2. Сведение задачи о коммивояжере к задачам целочисленного линейного программирования ... 25

§ 3. Решение задачи о коммивояжере методами динамического программирования.......... 30

§ 4. Метод ветвей и границ............ 32

Глава III. Экстремальные комбинаторные задачи ... 44

§ 1. Задача балансирования сборочной линии . . 45

§ 2. Задача расписания............. 47

§ 3. Последовательная обработка деталей на трех станках..................... 49

Заключение ..................... 60

Литература ..................... 61

Владимир Иванович МУДРОВ

ЗАДАЧА О КОММИВОЯЖЕРЕ

Редактор В. Ю. ИВАНИЦКИЙ Художник Л. П. РОМАСЕНКО Художественный редактор Е. Е. СОКОЛОВ

Технический редактор Е. М. ЛОПУХОВА Корректор С. П. ТКАЧЕНКО

А 01845 Сдано в наб. 18/IV-69 г. Подп. к печ. 25/VIII-69 г. Формат бумаги 60 × 90/16. Бумага типографская № 3. Бум. л. 2,0 Печ. л. 4.0 Уч.-изд. л. 2.99

Тираж 41 000 экз. Издательство «Знание». Москва, Центр, Новая пл., д. 3/4. Заказ 3795. Цена 12 коп.

Московская типография № 8 Главполиграфпрома Комитета по печати при Совете Министров СССР, Хохловский пер., 7.

Отпечатано в типографиии изд-ва «Знание», Зак. 2354.

УВАЖАЕМЫЕ ТОВАРИЩИ!

ИЗДАТЕЛЬСТВО «ЗНАНИЕ» ПРЕДЛАГАЕТ ВАМ СЕРИЮ ПОДПИСНЫХ НАУЧНО-ПОПУЛЯРНЫХ БРОШЮР

«МАТЕМАТИКА, КИБЕРНЕТИКА»

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

В 1970 ГОДУ ПОДПИСЧИКИ СЕРИИ ПОЛУЧАТ 12 БРОШЮР, СРЕДИ НИХ:

• ДЕМИДОВ С. С, кандидат физико-математических наук. Великие проблемы Гильберта.

• ИВАНИЦКИЙ Г. Р., кандидат технических наук. Геометрия живого.

• ПРУДНИКОВ В. Е., кандидат физико-математических наук. П. Л. ЧЕБЫШЕВ (К 150-ЛЕТИЮ СО ДНЯ РОЖДЕНИЯ).

• БЕСКОНЕЧНОСТЬ В МАТЕМАТИКЕ.

• ПРОБЛЕМЫ СОВРЕМЕННОЙ МАТЕМАТИКИ (сборник переводных статей).

• ПОСТРОЕНИЕ ЭМПИРИЧЕСКИХ ЗАВИСИМОСТЕЙ.

Серия «Математика, кибернетика» в каталоге «Союзпечати» расположена в разделе «Научно-популярные журналы» под рубрикой «Брошюры издательства «Знание». Индекс серии 70096.

ВЫПИСЫВАЙТЕ! ЧИТАЙТЕ!

СЕРИЮ НАУЧНО-ПОПУЛЯРНЫХ БРОШЮР «МАТЕМАТИКА, КИБЕРНЕТИКА».

ПОДПИСНАЯ ЦЕНА НА ГОД 1 РУБ. 08 КОП.

Издательство «Знание»

12 коп.

Индекс 70096

ИЗДАТЕЛЬСТВО «ЗНАНИЕ»

Москва 1969