/
Автор: Мудров В.И.
Теги: издательство знание новое в жизни науке технике - серия математика кибернетика брошюра знание
Год: 1969
Текст
1969 I
Новое жизниi
мауне । технике
кибернетика
ЗАДАЧ
I
О НОММИ вояжере
В. И. Мудров,
профессор, доктор технических наук
ЗАДАЧА КОММИВОЯЖЕРЕ
Издательство «Знание» Москва 1969
517.8 М89
2-2-3
77-69
Глава 1
Математическая формулировка задачи о коммивояжере
§ 1. ПОСТАНОВКА ВОПРОСА
Название этой книги у некоторых читателей, по-видимому, способно вызвать ироническую улыбку. Неужели находятся чудаки, интересующиеся деятельностью и заботами коммивояжеров, которые навсегда исчезли в нашей социалистической стране? Ведь даже в капиталистических странах они почти прекратили свои путешествия с целью выяснения конъюнктуры, рекламирования образцов товаров и заключения соглашений об их поставке, поскольку владельцы предприятий предпочитают пользоваться для этого более современными способами поддержания дедовых контактов.
Надо прямо сказать, что таких людей, по крайней мере среди инженеров и математиков, в настоящее время нет, но к задаче, известной под этим названием и насчитывающей более чем двухсотлетнюю историю, интерес не только не ослабевает, но, наоборот, постоянно возрастает, я многие знаменитые ученые, начиная с Эйлера1 и Гамильтона2 й кончая выдающимися математиками современности Д. Данцигом3,
1 Эйлер, Леонард (1707—1783 тг.) — великий математик, механик и физик. С 1727 т. академик Российской академии наук. Круг занятий Эйлера был необыкновенно широким и охватывал все разделы современной ему математики и механики, теорию упругости, математиЧёскуй физику, Оптику, теорию машин, теорию музыки, баллистику, морскую науку, страховое дело и т. д. Во всех без исключения разделах он получил основополагающие результаты.
2 Гамильтон, Уильям Роуан (1805—1865 гг.) —знаменитый английский математик и механик. С 1827 г. и до конца жизни — профессор астрономии в Дублинском университете. Является одним из основоположников векторного исчисления, теории гиперкомплексных чисел н вариационных методов механики.
3 Данциг, Джордж Бернард (род. 1914 г.) —известный американский математик, профессор Калифорнийского университета, сотрудник корпорации RAND, один из основоположников теории линейного программирования.
3
Р. Веллманом1 и другими, предлагали методы ее решения, проверяя одновременно на ней возможности новых вычисли* тельных приемов и методов.
Хотя первоначально задача возникла как чисто развлекательная, впоследствии она утратила этот характер и нашла многочисленные практические применения. Так часто бывает в истории науки. Решения многих задач, казавшихся поначалу развлечениями и головоломками, впоследствии послужили ключом для решения важных теоретических и практических вопросов. Укажем, например, на задачу кавалера Де-Мере2, которая была решена Паскалем3 и послужила толчком для возникновения одного из основных понятий теории вероятностей— понятия математического ожидания, или на игры типа игры в «орлянку», размышления над которыми привели Бо-реля4 к формулировке основной теоремы теории игр, являющейся в настоящее время главным инструментом при изучении конфликтных ситуаций. При этом, конечно, нужно иметь в виду, что выдающиеся ученые, занимаясь подобными задачами, предвидели фундаментальную роль научных теорий, кладущихся в основу их решения.
Задача о коммивояжере удивительно просто формулируется: коммивояжер, выходящий из какого-нибудь города, желает посетить (п— 1) других городов и вернуться к исходному пункту. Известны расстояния между всеми этими городами. Требуется установить, в каком порядке он должен посещать города, чтобы общее пройденное расстояние было минимальным.
Если несколько видоизменить постановку задачи и не требовать возвращения к исходному пункту, то получим незамкнутую задачу о коммивояжере. В последующем мы покажем, что эта новая постановка задачи без труда может быть сведена к первоначальной.
Простота постановки задачи о коммивояжере сочетается с чрезвычайной трудностью ее решения, причем трудности эти
1 Веллман, Ричард Эрнест (род. 1920 г.) — знаменитый современный американский математик, сотрудник корпорации RAND, основоположник теории динамического программирования. Получил многочисленные результаты, связанные с применением динамического программирования в различных областях математики (вариационное исчисление, автоматическое регулирование, теория аппроксимации, исследование операций и др.).
* Задача Де-Мере заключается в следующем: два игрока условились сыграть ряд партий, выигравшим считается тот, кто первым выиграл S партий. Игра была прервана тогда, когда один из игроков выиграл a (a<S), а другой b (Ь<^5) партий. Спрашивается, как должна быть разделена ставка.
» Паскаль, Блез (1623—1661 гг.) — выдающийся французский математик и физик, автор большого числа работ по геометрии, теории чисел, теории вероятностей и т. д. В 1641 г. одним из первых сконструировал суммирующий автомат.
4 Борель, Эмиль (1871—1956 гг.) — французский математик, известен своими работами в области анализа, теории множеств и теории вероятностей.
4
йё принципиального, а вычислительного характера, так как легко указать приём, прямо ведущий к цели: перебрать все маршруты и взять из них наименьший. Принципиально это возможно, поскольку общее число мыслимых маршрутов является конечным числом. Но все дело в том, что ни одна, даже самая быстродействующая вычислительная машина не в состоянии осуществить этот перебор при сколько-нибудь значительном числе городов.
В самом деле, выходя из первого города, коммивояжер гложет направиться в один из (п — 1) городов, откуда в один из (п — 2) оставшихся городов и т. д., пока не останется один-единственный город, откуда он вышел. Таким образом, общее число вариантов, подлежащих просмотру, составляет (п —’ 1) (п — 2) ... 2 > 1 = (л — 1)1 вариантов. С увеличением числа городов это число чрезвычайно быстро возрастает й уже при 15—20 городах достигает астрономических цифр. Пропорционально возрастает и время на перебор этих вариантов. Поэтому от'полного перебора всех вариантов приходится с самого начала отказаться из-за невозможности уложиться в любое разумно назначенное время, а вот поиск методов (алгоритмов), позволяющих быстро находить оптимальный маршрут, оказался чрезвычайно трудным.
О трудности отыскания таких алгоритмов говорит хотя бы тот факт, Ито за решение одного из контрольных вариантов задачи (для 33 городов) некая мыловаренная компания США Установила премию в 10 000 долларов. Только несколько человек угадали оптимальный маршрут, но и их ответы не были признаны решением, поскольку, помимо чётких математических предписаний, допускалось применение не более"25 слов Текста для обоснования догадки.
Надо заметить, что, учитывая предшествующий опыт неудачных попыток решения задачи, компания не очень сильно рисковала. Примерно такая же по размерам премия, установленная до этого за решение сходной задачи фирмой RAND-Corporation так и осталась неприсужденной.
К настоящему времени предложено большое количество алгоритмов для решения задачи о коммивояжере. Наиболее интересные из них нами будут описаны, а пока мы рассмотрим несколько задач, математическая формулировка которых совпадает с формулировкой задачи о коммивояжере. Это рассмотрение начнем с задач Эйлера и Гамильтона, так как именно от них и ведет свою историю задача о коммивояжере.
* RAND Corporation — американская компания, проводящая исследования в области отыскания наилучшей политики в организации боевых действий, а также в организации экономики. Название происходит от а'нг-лийскйх слов Research and Development (исследования ' й ' развитие). В числе сотрудников RAND находятся многие выдающиеся ' математики-прикладники США.
5
$ 2. НЕКОТОРЫЕ ПРИМЕРЫ
1. Задача Гамильтона
, Выдающийся английский математик к механик Гамильтон изобрел игру, получившую в свое время широкое распространение, Игрушка представляет собой додекаедр {правильный
многогранник с 12 пятиугольными гранями и 20 вершинами). Считается, что этот доде-каедр приблизительно изображает земной шар. Пусть каждая из вершин изображает «столип царств.
ребрам додекаедра,, обойти все «столицы** заходя а каждую из них один и только один раз* ж вернутвся в исходный пункт (рис. 1). Каждый таков путь* если он существует,, назы-
одного из гоеу->уется, двигаясь по
Рйа. t
вается гамильтоновым контуром» ила гамильтоновым- циклив. Для того чтобы жстя эту задачук задаче Q коммивояжере, будем считать, что расстояние «4» междудвумя «столицами» равно1, если они находятся ва одном ребр^ ж что оно бесконечно л
противоположном случае Таким образом, мы: полу-
Рис. 2
взанмных расстояний’ между 2® городами (табл.
1.1, в которой для удобст-ванабОра теклеточки* в» которых должен стоять знак осх, оставлены пустыми).
Нетрудно догадаться, что если гамильтонов, маршрут существует, то его длина будет равна 20, если же такого маршрута нет, то длина пути обхода будет равна бесконечно
сти. Поэтому если, используя эту матрицу в качестве входных данных, решить задачу о коммивояжере, то сразу же получается ответ на вопрос о том, возможен ли такой обход, и если он возможен, то одновременно с этим указывается и один из вариантов этого обхода.
Практически установлено, что для указанного додекаедра существует несколько совершенно равноценных гамильтоновых циклов (рис, 2),
б
Тлблица 1.1
Если несколько усложнить задачу -и каждому ребру поставить в соответствие некоторые, вообще говоря, не равные между собой числа, именуемые «расстояниями между соседними столицами», то решение задачи о коммивояжере должно привести к указанию, как правило, одного-единственного маршрута. :
I
2. Задача об обходе шахматной доски
Почти аналогично выглядит задача об обходе конем шахматной доски, рассмотренная еще Эйлером.
Перенумеруем все клетки шахматной доски и будем считать, что «расстояние» между двумя клетками равно единице,
если конь может за один ход перескочить с одной из них на другую, и что это «расстояние» равно бесконечности в противоположном случае. Составив таким образом «матрицу расстояний» по типу таблицы 1.1 и считая, что конь первоначально;стоит на поле al, попробуем решить незамкнутую t задачу о коммивояжере. В этом случае решением задачи о коммивояжере может быть либо £=63, либо £=оо. Если-окажется, что £=63, то такой обход воз-
можен, и полученное решение укажет один из искомых вариантов. Если же £=оо, то обход невозможен. Надо сказать, что любители головоломок'нашли пути решения, не прибегая к помощи математики, и один из возможных вариантов такого обхода показан на рис. 3.
3. Сбор по тревоге
Рассмотрим еще одну задачу, в которой развлекательная сторона выражена менее резко, чем в двух предыдущих примерах. Задача выглядит следующим образом.
Пионеры одного звена проживают в разных местах города. Время на. движение любого из них до всех других обозначим tij, где i и /—их порядковые номера. Для быстрого сбора звена установлен такой порядок: вожатый, получив сигнал тревоги, идет к одному из пионеров, извещает его о полученном сигнале, а сам направляется на место сбора звена. Этот пионер подобным же образом извещает другого.и также направляется на место сбора, и так далее. Последний из пионеров, получив сигнал, прямо отправляется на пункт сбора. Спрашивается, как нужно составить эту цепочку, чтобы время сбора по тревоге всего звена было минимальным.
Сформулированная таким образом задача является задачей о кратчайшем n-звенном маршруте. Отличие этой задачи от незамкнутой задачи о коммивояжере сострит в том, что в последней пункт окончания маршрута не имеет значения, а в задаче о кратчайшем п-звенцом маршруте заранее указаны как пункт старта, так и пункт финиша. В дальнейшем будет показано, что как и незамкнутая задача о коммивояжере, эта, тоже сводится к задаче о коммивояжере в общей постановке, 8 '
4. Проводка и энергоснабжение
Можно указать бесконечное множество задач, связанное с объездом ряда пунктов с какой-либо целью и возвращением в исходную точку, например, развозка почты, продуктов питания и т. п. Аналогичный характер носят задачи соединения этих пунктов кольцевыми линиями энергопередач, газоснабжения и т. п. / ' ' . ’ :|''й
Рассмотрим, например, задачу подводки,электроэнергии к рабочим местам. Отправляясь от одного полюса . источника
/ 1 фбаяа b а ъенко Передняя стенка Прадая стенка Задняя стенка
пол
Рис. 4
энергии, требуется подвести провод к п потребителям и затем замкнуть проводник на другом полюсе. При этом расстояние между точками можно определить по формуле
(XZ - - ytf+(zt - Zjf
(х, у, z — координаты места потребления энергии), если допустимо проведение соединяющей проводки напрямую от одной точки до другой, или же несколько более сложным образом, если проводку разрешается осуществлять с соблюдением некоторых ограничений (например, только по стенкам помещения и обязательно параллельно его ребрам). Так, кратчайшее расстояние между точками I и определяемое с учетом указанных правил, изображено на рис. 4. Оно'складывается из отрезков ia, ab, bj.
Особое значение задачи подобного рода могут иметь прй разработке технологии автоматического монтажа радиоаппаратуры.
9
5. Определение оптимальной п&еледо&ателыгости обработки деталей
Пусть у нас имеется дна станка и совокупность различных деталей, каждая из которых должна быть последовательно обработана на этих станках (например, токарная обработка и фрезерование). Будем- считать, что:
а) на каждом станке может обрабатываться не более одной детали;
6J начавшаяся обработка детали не прерывается вплоть до ее окончания;.
в) время на переналадку станков при переходе на обработку следующей детали пренебрежимо мало.
Время обработки k-й детали на каждом: из станков обозначим и Ьк- Спрашивается, в каком порядке надо обрабатывать детали, чтобы вся их совокупность была обработана возможно быстрее?
Легко заметить, что какую бы последовательность мы ни выбрали, токарный станок простаивать не. будет, обрабатывая одну деталь з^ другой. Простаивает фрезерный станок, и вот время-to его простоя с момента начала выполнения закар за, по существу, и требуется, минимизировать. ।
Подобного рода задачи часто возникают при планирований работы многомашинных вычислительных комплексов, в кото* рых каждая из машин предназначена для выполнения определенных операций в ходе решения задач. Например, можно представить себе такой двухмашинный комплекс, в котором одна из машин осуществляет проверку правильности составления программы, записанной на алгоритмическом языке, и ее трансляцию, а вторая осуществляет собственно решение.
.Пусть у цас имеются две детали, подлежащие обработке. Путем непосредственного просмотра различных комбинаций величин Ou it, а.*, можно установить, что в случае, если
в обработку сначала нужно пускать нерву» деталь. В протии воположном случае, т. е. когда
птШ(а2, 5i)<nrfe(at, й2}, в обработку следует пускать сначала вторую деталь.
Наконец, в случае, если
m!h(au Z>2)=min(a2,
порядок, в котором детали пускаются в обработку, не сказывается на общей длительности обработки.
Оказывается, что и в более общем случае нескольких деталей i-я деталь должна обрабатываться ранее f-й детали, если
min (at, fy)<min(ay, bt), (1,1.)
10
Если деверь поставить в соответствие каждой i-й детали совершенно произвольную точку на плоскости и считать, что расстояние между i-й и j-i точкамиравно 1, если соблюдается соотношение (1.1) и r<j=oo в противоположном случае, то получим «матрицу расстояний».
Йо аналогии с введенным яонятием гамальтоаова контура будем называй, гамильтоновым путем незамкнутый маршрут, соединяющий все точки. Оказывается, каждая гамижш* нрв путь обхода точек соответствует оптимальной последова-тельиости обработки деталей. А задача отыскания гамильтоновых путей, как было отмечено в первых двух примерах, есть частный случай задачи о коммивояжере.
Составим небольшой численный пример.
Пусть дан набор деталей, каждая из которых требует следующих затрат времени на токарную обработку и фрезерование:
Таблиаа 1.2
йшяер детали j Время на товарную L обрабозчсу J Время на фрезерование
1 • 2 4 S и • ' 7 - ’ > 13 . s’ и 3 j 1
«Матрица расстояний» между тот», ъ зажорой тажо чтоудоминалось, нмеетвяд; Та<вя««а 13
Мм«е> j . летели ; I • « i 8 .! 4 1
1 ; г 2 3 1 4 | 5 X Л ; ОФ ОФ 1 ФО X оо оо оо 1 ' 1 1 X 1 1 ; 1 1 * 1 ! ' Ж । 1 00 1 об «0 X
Зададимся произвольным порядком обработки деталей ’(например, 1,2,3, 4, 5) и покажем, как в этом случае ояреде* лить общее время, затраченное на обработку деталей. Ясно, что первый станок может немедленно начинать обработку очередной г-й детали, как только закончится обработка предыдущей (г — 1)-й детали. Со вторым станком дело обстоит несколько сложнее. Время начала обработки гчй детали на фрезерном станке зависит от двух обстоятельств, а именно:
а) закончилась ли ее обработка на токарном стайке;
б) освободился ли в это время фрезерный ставок^
Таким образом, момент начала фрезерования Г-й детали равен
(—момент окончания обработки Ли детали на токарном max {. станке;
(— момент конца фрезерования (1—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 (наименее выгодный вариант) приводит к тому, что детали будут обработаны в течение <6-1. часа. Время простоя фрезерного станка' соответственно составляет 21, .16 и 28 часов *.
Таблица 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 Сведение указанной задачи к задаче о коммивояжере представляет Лишь один из путей ее решения. Другим и, пожалуй, наиболее простым способом решения задачи является следующий способ:
а) выбрать наименьшее среди всех чисел ад и6$;
б) если таким числом окажется то соответствующую деталь поставить самой первой;
в) если таким числом окажется Ьь, то соответствующую деталь поставить самой последней;
г) повторить эту процедуру по отношению к оставшимся деталям.
12
Таблица 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. Переналадка станков
Рассмотрим другую задачу, также имеющую отношение к обработке деталей, но в смысле допущений прямо противоположного характера. Именно, пусть некоторая совокупность деталей подлежит обработке на автоматической линии, но в отличие от предыдущей задачи будем считать, что время наладки линии для обработки t-й детали достаточно велико и зависит от того, какая деталь обрабатывалась перед этим. Совокупность времен переналадки сведем в таблицу Спрашивается, в каком порядке надо обрабатывать детали, чтобы затраты времени на наладку были минимальными. В данном случае мы не интересуемся, временем обработки деталей, поскольку это время входит постоянной величиной в общее время выполнения заказа при любом порядке обработки деталей.
Нетрудно видеть, что сформулированная задача есть в чистом виде задача о коммивояжере для п городов. Надо, чтобы поточная линия побывала в п состояниях, причем сумма времен перехода из одного состояния в другое была бы минимальна.
7. Оптимизация программ
В области вычислительной техники в настоящее время получают распространение вычислительные машины с так называемой предварительной подготовкой и модификацией команд. Модификация состоит в прибавлении какой-то константы к коду команды. При каждом такте работы такой машины осуществляется просмотр программы и параллельно с завершением выполнения какой-то команды совершаются предварительные операции, подготавливающие осуществление последующих команд. Такими операциями, например, могут быть:
а) засылка результата предыдущей операции;
б) вызов чисел из оперативного запоминающего устройства по модифицированным адресам очередной команды;
в) модификация адресов следующей за очередной команды и т. д.
.13
Число таких операций может доходить до десяти. Эффект от предварительной подготовки команд снижается, если в программу включена команда условного перехода, которая может передать управление не очередной, следующей за командой условного перехода, команде, а какой-то другой. В этом случае затраты времени на подготовку очередной команды могут безвозвратно теряться. При большом количестве команд условного перехода в программе эти потери могут оказаться значительными.
Обозначим арифметические блоки, входящие а программу, В\, В2,...,Вп, причем предполагается, что вычисления всегда начинаются с блока Bi и заканчиваются в Сажоаее а сами блоки разделены операторами условного перехода. Предположим, кроме того, что нз каких-либо соображений (например, опытным путем) удалось установить вероятность pit3 то-то» что после завершения расчетов в f-м блоке управление будет передано j-му блоку, т. е. будем считать, что задана таблица переходных вероятностей UpjjJ.
Таблица 1.7
Обвяодчение Фзюка в* Ав 1 ' • Д-1 вп
д 5 I Л •* Л J А»#—4 А» л
Д i О X #2>3 J 1 • • • 1
Д о Л 22 X J
• • • • • • • • • • • « ] • ♦ • • • • • • ♦
о I At— 1 Аг-пз I -х.’ j А®—1»л
д | ° о ! D I • <л л О : X
Используя эту таблицу, можно установить математическое ожидание числа случаев использования /-го блока в ходе расчетов (6J. Величина
riJ=Nt(l-Pu)
будет численно выражать математическое ожидание числа случаев, когда в ходе расчетов нет непосредственного следования блока Bj за блоком 8$.
Изображая блоки Bt и В} точками на плоскости, считая fi,i «расстоянием» от /-й точки до /-й и находя наиболее ко-14
роткий гамильтонов путь, ведущий от точки 1 к точке я, найдем такую последовательность расположения арифметических блоков Bh В*, Вы^ВЛг[^,Вп, реализующих программу, доя которой математическое ожидание числа нарушений естественной очередности вычислений будет иметь наименьшее значение.
§ X НЕОБХОДИМЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ ГРАФОВ
В ходе предыдущего изложения мы обещали показать, каким образом незамкнутую задачу о коммивояжере к задачу о кратчайшем ге-звепном нута междуднумя тачками можно свести к задаче о коммивояжере в общей постановке. Hi»
прежде чем приступить к осуществлению этого намерения, целесообразна дать некоторые, самые первоначальные сведения из теории графов.
Графом (X, U j- называется некоторое множества точек X, соединенных, направленными отрезками (множества U}. Эти направленные отрезки не следует путать с векторами, так как графы, строятся без какого бы. то ни была учета масштабных соотношений.
Элементы множества X называются вершинами (или точками, или узлами) графа, а направленные отрезки —дугами. Например, на рис. 5 граф (Л”, С/) образован множеством точек, состоящим из xu Хд, х3 и х4, и множеством дуг (xh,x2), (х2>. Xi), (х2, ха), (ха, х4) и (Хз, ха).
Граф называется конечным, если конечны множества X и множество СЛ.
Путем в графе называется такая последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом последующей. Путь, в котором никакая вершина не
1а
встречается дважды, называется элементарным. Элементарный путь, проходящий через все вершины графа, называется гамильтоновым путем. Контур — это конечный путь у которого начальная вершина совпадает с конечной. Контур называется элементарным, если все его вершины различны. Контур, проходящий через все вершины графа, называется гамильтоновым контуром.
Иногда каждой дуге графа ставят в соответствие некоторое число r(Xi, Xj) =rij, называемое «весом» или «длиной» дуги. Тогда длиной пути, проходящего через Хь х2,...,хк, считается сумма длин дуг, его составляющих, т. е. Г1,2-|-Г2,з+ .+ ... +/•*-!, ft.
Граф (X, U) называется симметричным, если из существования дуги (%i, Xj) обязательно следует существование дуги (Xj, Xi) и при этом Для упрощения графического
представления в этом случае обе точки соединяют одной непрерывной линией без стрелок.
Граф называется полным, если любые его две вершины соединены хотя бы в одном направлении.
Задача о коммивояжере представляет собой задачу отыскания гамильтонова пути кратчайшей длины в конечном полном графе. При этом предполагается, что любые две
Рис. 6
вершины рассматриваемого графа соединены в обоих направлениях. На рис. 6 изображен такой полный граф для четырех
точек.
Здесь важно учесть одну особенность. Условия задачи о коммивояжере часто появляются в результате рассмотрения некоторой сети коммуникаций, которая также представима в виде графа (рис. 7). На этом рисунке крупные города Минск, Бобруйск, Полоцк и др. являются вершинами графа, а железнодорожные магистрали, соединяющие эти города, — дугами. Такого рода граф редко является полным графом, в котором все точки попарно соединены дугами в обоих направлениях. В зависимости от ряда условий полный граф, требуемый формулировкой задачи о коммивояжере, может быть образован на основе изучения графа сети коммуникаций различным образом.
16
Так, в задаче об обходе вершин додекаедра вершины, не соединенные непосредственно между собой ребрами, мысленно соединяются дугами, длины которых предполагаются равными бесконечности. Именно таким образом получена матрица расстояний на стр. 7. Можно было бы слегка видоизменить постановку задачи Гамильтона и считать' расстояния между «столицами» равными длине кратчайшего пути между ними, не интересуясь тем, заходят ли такие пути в другие вершины додекаедра. Полные графы, соответствующие этим двум задачам, будут различными, и свойства полученных решений будут также различными. Так, в первой постановке категорически запрещаются маршруты, дважды проходящие через одну вершину додекаедра. Во второй постановке такие
заходы допускаются и требуется лишь одно: обход всех до единого гофодой с минимальной длиной пути, так как в Полном графе эти заходы «по пути» никак не отображаются.
Полный граф с числом вершин более пяти—шести изобразить на каком-либо рисунке почти невозможно, так как вследствие обилия дуг рисунок теряет всякую наглядность. Поэтому дуги, длина-(«вес») которых равна со, на рисунках не 2354—2
показывают, и тогдаизображение графа несколько упрощается. Именно таким образом получен граф, соответствующий задаче о коммивояжере, осуществляющем кругосветное, путе-шествие, изображенный; на рис. 2. На этом же рисунке жирной, чертойвыделенод ин изгамильтоновых путей.
На рис. 8 изображен граф, соответствующий численному примеру, в задаче об; определении оптимальной последовательности обработка деталей на. двух станках.
ются аналитически в виде матрицы взаимных расстояний между пунктами. Поскольку построение матрицы расстояний для задачи о коммивояжере на основе изучения графа крмму-никЙцйй Имеет большой самостоятельный интерес, то мы, сде-циаЛБноуделим внимание этому вопросу. Пока же заметим, чтб Ъ помощью незначительного изменения полного гр а<фа не? трУдЙЪ незамкнутый вариант задачи о коммивояжере свести к'замкнутому варианту. .
"Напрймер, пусть дан граф (X, U) и в этом графе указано местдстарта (начальная точка С), но не указано место фи-нйша' Заменяя длины всех дуг, кончающихся в точке С, ну-, лямй, й'решая задачу о коммивояжере в замкнутой форме, (в, кбторЬй место старта не играет никакой роли), сведем задачу о.‘нахфкден»н гамильтонова пути н задаче* отыскания гамнль-тонова контура., В самом деле, любой гамильтонов* контур эт^гб графа* содержит; гамильтонов путь «Г», Я* .... л^я),< проходящий черезвсевершины графа, плюс дугу С), имеющую нулевую длину. Если, найден, гамильтонов. контур кратчайшей длины; то автоматически найден и. кратчайший гамильтоновпуть, начинающийся в точке С.
В задаче о выборе оптимальной последовательности обработки деталей на двух станках был построен граф (см.-рис.в), для которого требуется найти гамильтонов путь, и при этом не указано ни место старта, ни место финиша (такое же положение имеется и в задаче об обходе конем шахматной доски, если не фиксируется начальный пункт обхода). Для того чтобы свести эту задачу к общей постановке, введем фиктивную точку л, которую соединимдугами нулевой длины е каждой из точек графа в обоях направлениях. Построив,для этого графа кратчайший гамильтонов контур а исключая из него дуги (Х{, л) и (л, , имеющие нулевую длину, получим га-
мильтонов путькратчайшейдлины.
Расширенная таким образом «матрица ^расстояний», показанная на стр.11, приметследующий вид: ,
В задаче о сборе по тревоге и в задаче оптимизации про* грамм нами была сформулирована задача об обходе п. пунктов, причем указан как пункт старта (точка С), так и пункт финиша (точка Ф). Эта задача сводится к задаче о комми-вояжере следующим образом. Заменим длины всех дуг, входящих в точку С, бесконечно большими числами. Это не касается дуги (Ф, С), длину которой примем равной нулю*, Точно также Поступим со всеми дугами, исходящими из точки Ф. После этих изменений графа любой гамильтонов контур, конечной Длины содержит Дугу (Ф, С), имеющую, нулевую цлину. Если же теперь исключить эту Дугу из рассматривав-, кого контура, то оставшийся гамильтонов Дуть будет наяй* натьсяв точке С, и заканчиваться в точке Ф. Гамильтонову контуру кратчайшей длины в этом измененном грифе соответ- [ ствует кратчайший^тймийьЮиои дуть н исходном грифе,’'
$ 4. ПОСТРОЕНИЕ ПОЛНОГО ГРАФА
ЗАДАЧИ О КОММИВОЯЖЕРЕ
НА ОСНОВЕ АНАЛИЗА ГРАФА КОММУНИКАЦИЙ
(Задача о кратчайшем пути)
.... В предыдущем параграфе мы отметили, что условия задачи о коммивояжере часто появляются в результате анализа некоторого графа коммуникаций и что методика такого анализа имеет большой самостоятельный интерес. Рассмотрим эту методику более подробно.
Пусть задан граф коммуникаций и пусть требуется найти совокупность величин характеризующих кратчайшие пути между двумя произвольными точками графа.
Указанная задача является одной из простейших задач теории графов. Из множества алгоритмов, предложенных для ее решения, мы опишем лишь один, опирающийся на идеи динамического программирования. Поскольку более подробно о динамическом программировании будем говорить несколько ниже, мы без каких-либо подробных пояснений сразу напишем алгоритм.
Итак, дан граф коммуникаций (например, такой, как на рис. 7). Будем считать, что расстояние между пунктами I и / равно d?j. Величина d,^<oo, если пункты непосредственно соединены между собой элементарными дугами, и d^j — oo, если из одного пункта в другой нельзя проехать, минуя другие вершины графа. Кроме того, положим d^ =0.
Построим совокупность величин , djj , ... по правилу [3]
rf’,y=tnin (d°t,i i
dlj=min (dh-j-d^j)
djj — min • • • ••••••
Расчеты следует прекратить, когда матрица ||d< II будет в точности совпадать с матрицей
Эта матрица (обозначим ее lldijfl) представляет собой матрицу кратчайших расстояний между любыми двумя пунктами сети и с незначительным изменением может быть использована для описания свойств полного графа, в котором отыскиваются гамильтоновы маршруты.. Незначительное -изменение, о котором идет речь, состоит в замене' нулевых элементов
вдоль главной диагонали (J/j всегда jpaBiio нулю) йа бесконечно большие числа, так как в лйбом случае гамильтонов маршрут не должен содержать петель, а указайное преобразование облегчает дальнейшее решение задачи о коммивояжере аналитическими методами..........
Расчет матрицы кратчайших расстояний по указанному правилу чрезвычайно прост и даже Для матриц больших размеров без труда может быть осуществленкак на универсальных Цифровых машинах, так и во мйргйх случаях вручную. > =
методы решения задачи о коммивояжере
$ 1. ЭВРИСТИЧЕСКИЕ МЕТОДЫ И МЕТОДЫ МОНТЕ-КАРЛО
: РИС, 9
Эвристическими называются алгоритмы, построенные по догадке и не претендующие на нахождение точного решения. Применение эвристических алгоритмов к какой-либо практической задаче обычно, приводит к рекомендациям, которые намного лучше произвольного, взятого наугад решения, и которые обычно близки к наилучшему варианту, но они никогда не дают полной уверенности в том, что найлучЩеё решение достигнут^ *.
Простейший из эвристических алгоритмов может выглядеть, например, таКГ выбираем1 произвольный гамильтонов контур и меняем в нем местами соседние две вершины. Если уменьшения пути не произошло, то удерживают в памяти прежний путь и переходят к следующей паре точек. Если же произошло
Настоящая брошюра еще находилась в производстве, когда в журнале «Operations Research», v. 16, № 3 за 1968 год появился подробный обзор методов решения задачи о коммивояжере, сделанный Беллмором и Немха-узером [13]. В этом обзоре решения, полученные при помощи эвристических приемов, очень удачно названы аппроксимирующими решениями.
22
улучшение маршрута, то запоминают новый контур и посту* кают с ’ним аналогичным образом.
Для задачи о коммивояжере о симметричными условиями наиболее эффективным алгоритмом такого рода является.по-видимому.следующий алгоритм JHJ-
Берем более или менее наугад какой-то ^контур, проходящий через все точки графа, например, в такой последовательности A, it,.... in, ti. Перенумеруем заново точки графа о тем, чтобы в рассматриваемом контуре они встречались в последовательности 1, 2,...,п. Для . произвольных двух точек i и ] этого графа вводится операция, именуемая инверсией. Инвер»
ПнильяюшЛ наршрда'Ио инверсии:i,2,3,4Afi,7,3,6,10,71,12,1 -
Гшшмюоюв мршррп поем иивщюш: 4,2/1,3,3,6,7,40,9АИ>12>1 ; -
Рис. 10
сия состоит в следующем. Из контура исключаются дуги (i, М-1) и (/, f+1). Взамен этого в контур кключаются дуги «, /) н {/+!,/+1), а ’путь, расположенной между4+1 и /. проходят в обратном направлении (рис. 9). В .результате
эдераши получается новый контур 1, 2, -.Д /»i— 1, i+2, -i+1, j+1, /+2,..„ ti—1, п. Длина этого контура отли* чается от длины исходного контура на величину j, где
^r+iJ*T“ #ы<н—4л/+р
Если составить двухмерную таблицу с входами jt' и J, где ibJ изменяются в -пределах <</,и выбрать наимень-
щее значение Вад, то мы перейдем к новому контуру, в пределах которого совершенно аналогичным образом можно искать Малоприятную инверсию. Путем этих своеобразных итераций можно довольно хорошо улучшить результат первого приближения. Отметим, что *в отдельных случаях,, таких, йацример, кйк. *иЗб!ф£$еяиыд на. рис. 1D, '.можно в тфедей» одной., итерации отыскать несколько благоприятных вяверсвй*
Если улучшение с помощью инверсий на какой-то этапе станет невозможным, то можно попробовать произвести даль-нейшее улучшение маршрута Другим способом. Например, Можно попытаться исключить точку Т из ее первоначального места в контуре и Поставить'’ее вслед за точкой 7 (рис. 11).
маршрут др улушетш: '
Тамильтоноб маршрут меле улучшения,-Рис. II .. ,-z.rr
В этом случае разность длин контурдв*сдставит‘ > ;й!
i, ''.г.:--.>.. , } - Д>'-, ;.!.«> ' '
н 4'd};i*Fdt.f+i ~'''j- <
Может оказаться, что для какой-либо пары точек эта операция приведет к уменьшению общей длины контура.
Особое значение^эвристические алгоритмы нмёютдля решения задачи о коммивояжере методами'Монте-^арло. *
Методами Монте-Карло называют любуяг вйгкйёлй^^ную процедуру, включающую в себя приемы статистической выборки. Например, для задачи о коммивояжере можно.предло-жй*Гь такой вариант йоиска оптимального рещёния. Д' урну закладываются жетоны с номерами от 2 до п (п соответствует 'чйсйу городов). Тщательно перемешав щетовы,^ вытаскивают йакой'-тр номер it, затем 1з и так др конца. В результате подуг чайт нёкрторйй замкнутый' маршрут /, 4, i3, 1„ подсчи-
fывают его Длину и хранят эти сведения в памяти. После это-W/прДтрря^Т процедуру,, rtj если норьщ марщрут оказцааётря /ужё‘ йрёДыД^щегб, то его тотчар ^а^ыДают, а если он дка? зывается лучше, то в дальнейшем в качестве эталона для сравнения используют именно eroi При достаточно малых затратах времен'# йа проведение ддного такого испытания можно с высокой степенью вероятности рассчитывать на то, чтр^в конпе концов удастся угадать, если не наилучший, то достаточно хороший маршрут. Поэтому для Проведения таких испытаний привлекаются обычно ЭВМ, снабженные датчиками случайных чисел, что позволяет Затрачивать на один эксперимент тысячные ДОлн секунды, -2*
. j ДОетоды Монте-Карло становятся особенно эффективными, если их дополнить эвристическими методами улучшения маршрута. В этом случае время на проведение одного статистического эксперимента несколько увеличивается, нр здте резко увеличивается и эффективность эксперимента..
Метод Монте-Карло в сочетании с эвристическими методами является одним из самых мощных средств решения задачи большого размера; при этом не предъявляется сколько-нибудь жестких требований к памяти и быстродействию машины. Необходимо учесть,/что проблема запоминания больших массивов промежуточнойинформациипри решении задачи о коммивояжере другими методами является одной из самых острых проблем. • 1
Недостатком этого метода является то, что йри ограниченном числе экспериментов (а ©на всегда являемся ограниченным) решение носит приближенный, а' не точный характер, причем не всегда удается оценить характер погрешности. Хотя с практичёсжю^точ^и’ зрения это/ ^еСу^ерхдёЗйд^й недостаток, он все же заставляет искать другие, 'Детерминированные алгоритмы поиска оптимального маршрута, которые нужны хотя бы. для того, чтобы оценить качество решений задачи, полученных методами,Монте-Карло., ?: »<• •,> voj<- Л
Указанными способами даже вручную можно довольно успешно улучшать длины гамильтоновы?, контуров в задачах с 15—20 городами.
л ^.СВЕДЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ < К ЗАДАЧАМ ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ • ..-Г. ‘
Пусть зйдан/некоторый контур в графе (X,. U) ./Его,, криеч-йо/можно описать, указав точки, через которые он проходит, найрийёр, 1, /г, 4, ...,in, 1. Но/этот же контур мржн.р задать совокупностьюдуг, которое его составляют, т: е. (/,. j$„ |з), В свою, очередь, эта совойупнбёть
ДуНЫфкет быть описана с помощью неотрйцатёлрных величин где 1/ если д^га; (i, .ft входит' в рассматриваемый кОИТур; й р<,/^0/в протййрполойсном ёлучйе. Такй^ ббрйЗом, получим йекоторую матрицу/ ’ ,: / / : '
>' М>||
У2,1У2.2 • * • ’ р2;я
(2.1)
\ > И
(2.2)
л» которой Рввнъ1 нулю или единице at соблюдается 2 я условий ,
4—1
•я
<—1,2,..., я
J-l
Эти условия вытекают из требования, чтобы в искомой маршруте в каждую точку входила и из 'каждой точки. выходила одна-единственная дуга.
j г Длина пути, изображаемая этим контуром, как нетрудно проверить, будет равна . - . >
£ =1?. :у '* .. 4-1.j—1
То •обстоятельство, что все должны быть положительными в целочисленными, можно учесть, наложив следующие •ограничения:
я,/3®® I, 2, •«>..,да, (2.3)
<2«4) где-Е^уу) —есть операция взятия полой части числа yxj.
Итак, мы установили, что каждому конщру можно поставить в соответствие некоторую матрицу Ну^О, удовлетворяющую условиям (2.2)—(2.4). Обратно, если дана матрица У, удовлетворяющая этим условиям, то нетрудно указать некоторый контур. Для этого нужно в волнам графе U) выделить те дуги (i, /), для которых yt,j—1. Однако, ж сожалению, полученный при этом контур не обязательно будет гамильтоновым (рис. 12).
/А
7
ц)
Для того..чтобы полученный контур был гамильтоновым, необходимо выполнение еще. одного требования, а именно» чтобы матрица Г была матрицей, так называемой циклической подстановки. Матрица Y',, содержащая в каждой строке, ц каждом столбце но одной, единице,, называется матрицей циклической подстановки,, если соблюдаются следующие условия:
(£—единичная матрица)
где любая подматрица Y- подучаемая в м»>
бора некоторых диагональных элементов и выделениясоответствующих строк и столбцов.
Например, матрица. г; ! /
О I Oft О О 0 0 0 1 0 0 [а а а a a i[' 1а о ® а > в г о aiaaft^ t ft ft ft ft.(й ..
является матрицей циклической подстановки, аматрица
о! о о ft ер 0 0 0 10 ft;
0 ft О 0 0 1 1 00000 ’ft ft I 0- 0 0 • ,0 0 0 0 1 о
не является таковой» так. как,, выделяя элементы. Рш а д» и соответствующие столбцы и строки» ми лолуЩ^м. матрицу
Н®а.
для которой
р Gift’ « • I
Ift ft Iff
»
Итак, повторяем, матрица Y должна быть матрицей.циклической подстановки. В противном случае мы будем иметь не один контур, обегающий все точки графа, а два.или более замкнутых контуров, каждый из которых обегает только часть точек, (рис, 12, б). При этом условия (2.2) г-(2.4), требующие, чтобы в каждую точку входила и из каждой точки исходила только одна дуга, удовлетворяются.
. После того как. установлено взаимнооднозначное-соответствие между совокупностью гамильтоновых-путей, в графе и совокупностью матриц У, удовлетворяющих условиям. (2.2) т? (2.5), можно задачу о коммивояжере сформулировать в следующем,виде: <
убмиидмизлровать выражение.: ; *,- Й
< / : ” - • - 'X- .
у..;.. i-lJ-V . .
при ограничениях (2.2)'—^’(2.5). - ц- ; ,
j Оказывается, что'относительно легко решить Задачуесли на-Лййкены только ограничения (2.2) и (2,3). При,: этом авто* матически будут выполнены ограничения .^(2.4)ч^Гораздо труднее удовлетворить-условию (2.5). В ряде ра бот. показано, что этому-требованию можно удовлетворить,, наложив, целый ряд) специальных линейных ограничений на переменные''лц$. Например, в работе [4] показано, что матрица '(2.Н:будет матрицей циклической подстановки, если, кроме (2.2)^ (2,4) наложены следующие условия:
(« — 1)УМ + UJ~ut<n — 2 'i,
где 'некоторые вспомогательные неотрицательные ' целые величины. с--,
. „Другой, прием, приводящий к той же цеди,, оррсйвается' в работеТЭ]. - ....
Можно указать еще несколько формулировок задачи о коммивояжере, имеющих прдо&ный же вид.
Задачи указанного типа относятся к Числу задач целочисленного линейного программирования. Напомним, что основной задачей линейного программирования является отыскание ЙЙймуЖР'лййеЙнЬЙ Чфб£йы при линейных. д^'^нййе’вгйЯх, list* йЬУ&н1^ условйй нёотриц'ателЬ'ностй
вёеХ'пё^^нййх.^гаЗвнрй‘ задачей ^Пелдчйсэ^й^^:;ййнеЙЙУ^ гсг1 ^рй^мййрбванйя является
Т^^^б^’т^еббвййЙй йелойисйёнй661и;й^рембн‘нйх;;.л^''
Для задач целочисленного линейного программирования ^бтфаммы1••«х ’рейеййй нйд"ЭВМ;
$
практика показывает, что задача о коммивояжере, сформулированная в виде задачи линейного целочисленного программирования, очень плохо поддается решению. Для мало-маль: ски сложной задачи (например, для 10 городов) приходится обрывать вычисления из-за того, что на решение затрачивается непомерно много машинного (на ЭВМ) времени. Так, при решении несложного варианта задачи о коммивояжере для шести городов после 18 часов непрерывной работы быстродействующую машину пришлось остановить, так и не дож-давшись результата (см. также [7]). Помимо больших затрат машинного времени, задачи указанного типа предъявляют очень высокие требования и к,объему машинной памяти. •
В настоящее время ведется усиленный поиск приемов более эффективного решения задач линейного целочисленного программирования, поэтому можно предположить, что и решение задачи о коммивояжере с помощью этого метода со временем окажется достаточно успешным. Пока же обычно ограничиваются тем, что решают задачу, не требуя соблюдения условия (2.5). В этом случае, формулировка задачи со-впадает с формулировкой так называемой задачи назначения являющейся одной из простейших задач линейного программирования.
Если «повезет», на что обычно мало надежды, то в результате решения задачи назначения будет получен гамильтонов контур. Если же «не повезет», то будет получена совокупность изолированных контуров по типу рис. 12, б и некоторая оценка (снизу) длины оптимального маршрута.
Чтобы воспрепятствовать получению этого не удовлетворяющего нас решения, можно наложить дополнительное условие такого вида:
У1,2+У2,з+Уз,7+У7,1^£3,
которое запрещает образование негамильтонова контура (1,2, 3, 7, 1); никак не сказываясь на множестве гамильтоновых путей задачи.
После этого вновь решается задача минимизации выражения :
при ограничениях (2.2)—(2.4) и этом дополнительном.условии. Вновь, если «повезет», то в результате решения задачи будет, получен гамильтонов контур, который и является решением задачи о коммивояжере. Если же опять получится совокупность нескольких контуров, то, изучая дуги, образую-
< &чяее подробные сведения л задаче назначения можно найти л работе (4).
щие контура, можно указать еще одно дополнительноеограничение на переменные запрещающее и это ,решение. Продолжая действовать в том же духе, иногда за короткое время удается найти точное решение задачи о коммивояжере. Так появились сведения о том [13],что с помощью линейногопро-граммирования удалось решить да из вариантов задачи о коммивояжере для 42 городов, т. е, задачи тень большого размера.
4 3..РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ
-МЕТОДАМИ «ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ .
Прежде чем описывать алгоритм .решения задачи методами Динамического программирования,деобходидо, <жазатьне-скбййкбслово самом динамическом программировании.
Теория динамического программирования—это теория принятая решений в, многошаговых процессах. Для того чтобы применить Методику динамического 'программирования, нужно прежде всего увидеть в решаемой задаче шаги или этапы, на которые можно разбить процесс принятия решения. Затем перечислить возможные решения на каждом этапе и указать способ выбора, наилучшего решения. Вбольшинстве случаев это требует хорошо развитой интуиции и незаурядной Йобретателвности. Дело в том, что эти этапы должны быть намечены так,-чтобы функцию выигрыша за последние fe этапов можно было бы представить в виде суммы двух величин, из которых одна выражает непосредственный выигрыш на текущем этапе принятия решения, а другая представляет выигрышна (Й—Т) оставшихся этапов.
В случае задачи о коммивояжере эта идея представления задачи в виде многошагового процесса реализуется следующим образом. Отметим среди а точек, которые нужно обойти, произвольную точку, которую будем считать тачкой старта и финиша. Первым этапом принятия решения будем считать выбор первой точки, в которую надо идти из места старта, вторым этапом — выбор следующей точки и т. д.
Вычислим функцию потерь на одном из этапов принятия решения. Для этого допустим, что нам удалось каким-то образом правильно выбрать решение на всех предыдущих этапах и мы пришли в точку I. Пусть при этом остались непройден-ными /ь /г,.... Д. Спрашивается, как нам поступить дальше и какова минимальная длина пути, обхода оставшихся точек? Обозначим поспешною A (ft, Д, подчеркнув -тем самым/
«его,^.находимся в точке/i и осталось:обойти множество то? чек с мидексами/ь Д,.
. /Е?ЛН яз точки / направиться в точку ft и затем?.двигаться но.наи^атчайш^у маршруту, то коммивояжеру предстоит пройти путь,ДЛИНОЮ , , :>< ., >•_ ;GVi; ..
Если же направиться в тачку J2, то коммивояжеру предстоит пройти путь длиною
Вообще пр» движении в точку jm коммивояжеру предстоит проделать дуть длиною <
(Jh /2, • • • . Jm-Ъ Jm+U • • •. Л)-
Очевидно;! чтоаправдльйым решением будет то,*цря котором эта сумма имеет минимальное значение. Тём самым мы укажем, Куда следует Двигаться ^коммивояжеру иф точки если осталось пройти точки 7ь'7», •••»/» и одновременно величину оставшегося пути : '
. . Л (A, • • ',’,’7*)==й11п. . ......
dhZ/att/l» /2» • ’ • 1 Jm-~h 7<n+l. • • • »-/*}]• (&7)
Таким образом»-намг удалоо» выразить, функцию ftdu «4®з аналогичные по смыслу функцийTwi. A* 'Uk* Wu-Ja)» во от меньшего числа аргументов. Все.’значения функций 7*01) для одного аргумента известны —это сумма расстояний от точки Z до 71 и от точки Д До. точки старта— финища/о. ..
Опираясьна знание значений этих? функций,но формуле (2.7) легко вычислить совокупность всех значений функций тде /ь hi * — неравные между собой числа, заключенные между 1 и п, именно
. • 7zU1’ Мл+AC/i)/
Аналогично
Ct - ’ >• '=-i5‘- :
, -Zf (Zfe Л»,: —
,4*Ц2»; J&i
+ /hUbJal fl» (Л» Jaff'
В T: Д; л-- tvC'' , -W::c
Преимущество, которое дает динамическое программирЦ-. ванне; по сравнению с-полным перебором; состоит в4 том» чтб вместо прямот сравнения (п—1)7 вариантой просматривает* ся значительно меньшее число- комбинаций и на. всех этапах
решения- задачи производится сравнений. Основная трудаостыдри; решении.-зэдачг ст коммивояжере методами- динамического' программирования— это проблема запоминания промежуточных- результатов? Для того; например, чтобы вы-
31
числить все значения функции /И7ь 7г), необходимо предварительно запомнить С„2 чисел Чтобы вычислить значения fi (Ji, 7з> /»), необходимо помнить С„3 чисел и т. д. Наиболее критическим является случай, когда k достигает значения -и~1 . На этом этапе в задаче с 11 городами приходится запоминать 300 чисел, в задаче с 17 городами— 12000 чисел, в задаче с 23 городами — 1 300000 чисел.
. Несмотря на эти трудности, динамическое программирование является одним из самых перспективных методов решения задачи о коммивояжере и сходных с нею сложных комбинаторных задач.
§ 4. МЕТОД ВЕТВЕЙ И ГРАНИЦ
Метод ветвей и границ в настоящее время является, по-видимому, наиболее эффективным способом получения точного решения задачи о коммивояжере, хорошо приспособленным как для ручной, так и для машинной реализации.
Основная идея метода довольно проста. Вначале строится некоторая оценка снизу длины маршрута для множества всех гамильтоновых контуров. После этого множество всех гамильтоновых маршрутов разбивается на два подмножества. Первое Подмножество состоит из гамильтоновых контуров, включающих некоторую дугу (z, 7) (обозначим его {/, 71), а другое подмножество состоит из контуров, не включающих эту дугу (обозначим его [z, 7D- Для каждого из подмножеств по тому же правилу, что и для первоначального множества гамильтоновых маршрутов, определяется нижняя граница. Каждая новая нижняя граница оказывается не меньше нижней границы, определенной для всего множества. Сравнивая нижние границы, можно отделить подмножество гамильтоновых путей, внутри которого с большей вероятностью содержится оптимальный маршрут. Это подмножество по аналогичному, правилу разбивается еще на два', и вновь находятся измененные нижние границы, и так поступают до тех пор, пока не останется единственный цикл. Процесс разбиения подмножеств сопровождается построением некоторого дерева по Типу рис. 17.
.Получив некоторый гамильтонов цикл, просматривают оборванные ветви дерева и, если нижние границы подмножеств, соответствующие оборванным ветвям, окажутся меньше, чем длина найденного цикла, то эти ветви развивают по тому же правилу, пока не получат маршрута с меньшей длиной или не. убедятся, что среди этих подмножеств не может ‘Содержаться подобного маршрута. Те же ветви, для которых нижняя оценка окажется больше длины -полученного маршрута, исключают из рассмотрения, "32
. В дальнейшем подмножества гамильтоновых путей, включающее дуги (ц, 1’2), (is, 1’4),... и не включающее дуги (ji, /2), (/з, А),-, мы будем обозначать так [и, AL —»171» Ji]. 1/з» AL— Множество всех гамильтоновых путей обозначим [С/4
Основная «изюминка» метода состоит в указании способа вычисления нижней границы для соответствующих подмножеств и в указании дуги (i, /), включение или невыключение которой в маршрут разбивает изучаемое множество гамильтоновых путей на подмножества. Остановимся вкратце на этих двух вопросах.
Для определения нижней границы множества (НГМ) можно было бы воспользоваться задачей назначения, о чем упоминалось в § 3 настоящей главы, однако этот способ несколько громоздок. В работе [8] предложен другой способ оценки, который хотя иногда и дает несколько менее точную оценку, чем решение задачи назначения, но зато чрезвычайно прост с точки зрения вычислений.
Идея получения этой оценки связана с тем, что если решить задачу о коммивояжере с некоторой матрицей расстояний, а затем из какой-нибудь строки или столбца этой матрицы вычесть произвольное положительное число, то решение задачи о коммивояжере с этой измененной матрицей расстояний. совпадает с прежним решением, а длина маршрута изменится на это же самое число. Если эту операцию проделать и для других строк и столбцов, то длина маршрута будет отличаться на сумму всех чисел, вычитаемых из строк . и столбцов.
Опираясь на эту теорему, осуществляют так называемое приведение матрицы, состоящее в следующем. В каждой строке матрицы находят минимальный элемент и вычитают его из всех элементов этой строки. В результате по крайней мере один из элементов строки будет нуль. Так поступают со всеми строками. Полученная матрица называется приведенной по строкам.
После этого аналогичным образом осуществляется приведение полученной матрицы по столбцам.
Приведенная по строкам и столбцам матрица содержит по крайней мере один нуль в каждой строке и каждом столбце. Так как длина Lt оптимального маршрута в задаче с приведённой матрицей отличается от длины L маршрута в задаче с нёприведенной матрицей на сумму констант приведения h, то
Z=Zj+A.
В приведенной матрице все элементы неотрицательны^ поэтому £г^0, а сумма констант приведения h может служить нижней границей длины гамильтонова маршрута. >
- 33
Априорное исключение какой-нибудь дуги (i, J) из маршрута выражается в замене соответствующего элемента dfj в исходной (а также в приведенной) матрице на оо. В резуль-' таге такой замены, появляется- возможность провести дополнительное приведение матрицы и улучшение опенки.
, Априорное включение дуги (i, j) в маршрут автоматически ведетк сокращению размеровматрицы(таккаквычеркивает-ся /-я строка и /-Йстоябед). Одновременно появляется возможность.исключить однуиздуг.
; Пасколы^ исключение.этой дуги, представляет важный* рлементалгоритма, то нанемследуетостановитьсянесколько подробнее,. Включение дуги (Z, /) приводит: & образованию сй^зноро пу.тщ соединяющего некоторые тачки р и (рис.13). /^рпусхимые; маршруты .доджей проХедить через ./вее тсгайн.
1 ’ ' графа; t поэтому запрещается
‘ ...• V&w-- : включенное;маршрут, дугр
" :> - - А)' ♦ образуется
< /Ж ;> ааметуЫй контур, проходящий
.У .............. только через часть точек. Впро-
стейщемслучае включение ду-' га (ц /) означает невключение
дуги '
* Сокращение раадеров мат?
! । Рис Ш f ; рипы и исвдючедт* элемента;
( (&. р) ноэмдаед щийвйэтй до»
^олйртельное приведение матрицы; и тем- самым ^улучшить, циж^юю, оценку длины любого гамильтонова маршрута, ср* фержащеТюся; в йоДмноЖестве^./}, ' “ j
Рассмотрим теперь вопрос о выборе дуги (г, /), играющей ctqjmh аажкуао роль-ярд разбиении множества г<а?мк»тоновых п^ейда ййдмножестваа.
Иайбояее вероятно, что в оптимальный маршрут входят дуЕИ,.^1Я которых в нриюеденной матрице 1Ьяинвяе» ние в маршрут; нменно дтнк дуг резкоувеличивает нижиюмг рцерк^ Жак уже( отменалога^, исключая дугу (г<; /)^ мы* должны положить dij=oo и, осуществляя приведение вновь полу-ченной матрицы, улучшить оценку. Константами приведения являются минимальный;1элвмент в i-й строке и такой-же в столбце^ Поэтому наиболее резкое изменение оценки:прризой-дег>;т<Ш сл-учаа^ Кбгдиа выбирается тот- элемент матрицы расстояний, длй! которого:
а) - —
•б) яосле; замены на сумма, минимальных
элементов в i-й строке и /-м столбце имеет наибольшее зна? чение.
Учитывая принципиальную важность рассматриваемого алгоритма, для- большей отчетливости его предписаний разберем- конкретный численный' пример.
Пусть матрица: расстояний-имеет вид:
34
'Тжвжжка 2.1
: 1 ’2 j j. -3 ; 4 5
1 2 < Л 4 5 6 г оо 58 ( 63 17 i 60 ' : ' 68 '«О ' 9 34 я те 82 1 73 16 ? OQ 76 3 11 24 44 1 86 { 'ОО 45 60 70 11 13 52 ' оо 48 : f t & 18 70 58 ' о© 9 11 & 17 *8 1ж.
’•хДая-яоидяешм Лижией границы множества -.осуществим' приведение но строкам. .Для зтхй^цели в «аяй^сетроке^вн-'* раемминимальныйэлементи вычитаем его иэ всех элементов строки. В данном случае константами приведения но строкам являются 9, Н. После приведенияпо строкам ма-
трицарасстоянийприобретаетследующийвид: ,х у
4 2 - Ч, .38. г” й" Г/Г"' ! •‘US
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 ’ до '
А/ _ 0 О 0 15 О
Сумма констант приведения и дает некоторую >нижнюю драницу длин всех гамильтоновых путей ДОГМ
Эта .оценка может быть улучшена за счет приведения па столбцам. Константы приведения показаны внизу табл.2.2. В результате получим НГМ [1/Р]=60+2Л,=60+15= 75, а матрица расстояний, приведенная по строкам и столбцам, приобретает вид
. ^3«®|МИПГ;.,23';
1 2 : 3 4 5 €
59 J Гб4.~? лН 61 ‘ S • '• - Й15 М '-и-с
2 * 47 оо 5 18 ow 61
ъЗ/ '/'• i-;54< л !т 4 9 г х,. ^ \ ’
©0 35 . 53 X Х-, V. . f ' !-
5 57 15 о(15<’ (5) 27 ? . ' 90, - 55 < .. - >’? ге‘ ч WMsKFij&Wir’
6 5 71 0* ' 34 37 оо V
В соответствии с предписанием мы должны просмотреть все нулевые элементы этой матрицы и выбрать тот, для которого сумма констант приведения матрицы, получаемой в результате замены на d<j=oo, была бы максимальна. Поэтому подсчитываем сумму этих констант приведения для всех нулевых элементов.
Начнем с элемента di,t. Если положить d1>4=oo, то константа приведения по сторонам была бы равна 0, а константа приведения по столбцам —18. Сумма констант приведения равна 18. Поступая аналогичным образом, устанавливаем, что для dtfi она равна 0+9=9, для элемента —4+5=9 и т. д. В табл. 2.3 эти суммы констант приведения помещены над каждым нулевым элементом. Максимальная из этих сумм соответствует дуге (4,1). Разбиваем множество [t/г] на два подмножества [4,1] и [4,1].
< Исключение дуги (4,1) из числа дуг, входящих в искомый маршрут, достигается заменой этого элемента знаком оо. В результате такой замены появляется возможность осуществить дополнительное приведение матрицы путем вычитания из четвертой строки 17 и из первого столбца 5. В результате такого приведения матрица расстояний для множества [4,1] примет вид:
Таблица 2.4
< г 2 3 4 5
1 оо 59 64 0 61 0
2 42 ОО 5 18 0 81
3 49 0 оо 62 4 9
4 оо 0 42 оо 18 36
5 52 15 0 27 оо 55
6 0 71 0 34 37 оо НГМ [4~1=97
а^Йижняя граница длин гамильтоновых контуров для этого подмножества равна НГМ [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). Для улучшения оценки должны быть использованы числа матрицы, которая получается после удаления четвертой строки и первого столбца и замены величины 4^4 знаком, оо, т, е. числа такой матрицы:
Таблиц? 2.5
1 59 64 оо 61 0
2 оо 5. 18 , 0 ч . 81
3 0 оо 62 4 9
5: 15 1 а 27, cto' 55 -. • j- • •
6. 71 о 34 • - 37 - >' -ОО : НГМ [4,1]=75
' . -
, Эта матрица также допускает; дополнительное- приведение пр .четвертому столбцу на 1$ единиц и соответствующее; улучк щенидлоценки» После приведения; матрица расстояпий'приоб* рётает вид: .ч
* . 2 * >' : :4; т Гл • :5 .. у • . ч , Т4
V'.'-' . * ч
59 Г Hi!/; ОО :< 61 v - О..(68);
2 ОО 5 0(9) о(4> 81
3 0(19) оо 44 4 9
ж .... о(19) 9 ... ОО 55 .
6 71 0(1» 16 37 . оо НГМ [4,1] = 93
Нижняя граница множества [4,1] теперь равна; 93. ’ :
Таким образом, мы начали процесс образования дерева (рис. 14). ; - . . . 1 !
Процесс дальнейшего ветвления рекомендуется вести так,. чтобы возможно скорее получить некоторой маршрут. Длину' этого маршрута можно использо- , '
вать для того, чтобы обрезать большое число ветвей с нижней ( ц Ja-zj
грёнйцёй? Превышающей' длину \.
этого маршрута. Именно поэтому ' ' Л~л ’ ’ В первую очередь мы-будем; др©’ • / \ч
бить на подмножества множество >—/ ;•
fW а не мно^еЙвЬ [4.1J. ’ * ; \ 4>1
•Множество [4, 1] имеет1 в ка'-
честив нижней границы h=93 и ' рщС
дОпускаёт длй^построенНяколЬ- * ’ ' *< '*
цевбёб маршрутаг;5йспдльзойанйё дуг,, 'длйны которых прййё-' ДенЫ вТВбл.26.— - — cm
й; В cbottefci'Pfth 'c предписанием =ййго$и?Ма^Ьтйюк'й^йРЙ^ 1^??ЙсШючёЙйё ДоГорЬЙ'йаксймайьПб бй- увелИ^лдлЙЙЖй4йЙ. оценку. Для этого выйбМНйёМ тё'ДЬе ДёЙ&вйП}-к&кйё,:й^1йрй»’
37
делали .при выборе дуги [4,1], т. е. просматриваем нулевые элементы; предварительно помеченные суммой констант приведения, образующихся после замены </»,г=0 на dii3-=oo (эти величины помещены в углах; над нулевыми элементами в табл, 2.6). Максимальное значение суммы констант приведения соответствует элементу di.6, Поэтому будем улучшать НГМ [4,1], [1,6] й НГМ [4,1]г [1,6].
Исключение дуги (1,6), приводит к улучшению оценка на ^единрд, Поэтому НГМ\[4,1]^[1,6]=93-1-68=д161,
Включение дуги (1,6) связа-носиеключениемвердойстро-кн и шестояь столбца*. Крммк того, дляустранения негамильтоноваконтура(4,1,6^ 4): должна быть запрещена дуга ; . ,(6Д). Ддя.дальнейщасоудуч.-шения оценки: должна, быть ис-J пользована таблица 2.7, не до-! пускающая приведения и поэтому не изменяющая нижней границы.
Т'а блдаца 2.7
2 а i ;; 4 б -•I
2t OQ " ow ; aw :«
3 ОО 44.
5 15 0(9) 9< оо
6 ! 71 0(37) ОО 37 НГМ [4,1], [1,6] = 93
Дерево разбиения на подмножества*, приобретает вид, показанный на рис. 15,
Действуя в том же Духе, будем рассматривать подмножества гамильтоновых контуров &Ц [Кб], [6<3] в [4>Ц, [1,6k [6,3]. Для первого^ подмножества НГМ [4,1k [УД [6>ffi= 1301
• -Рассмотрим второеглодмножестаатВключение: д^вц артоматически исключает шестую строку и третий столбец,.
устранения негамильтонов^ контурм нео&со-
д№йа Вйретяшадру (ЖХ- Для» дальнейшего улучщввдшьоДенг-кииспользуетсяматрица;
3»
ТабладЗв О
допускающая приведение по.пятой строке н улучшение Оцен-ки-надевять единиц. ч
После приведения эта матрица выглядит ^ледующимоб-' разом: " j
ТаЭДж0 2S
—Г-1-1^----Т“”Т~~; --..... ./.'''''V
«
<•
, •«••
J г Л
а.;< в л
в
W,» О
о
.. . 4 ео
Т !
в 1
Дерево разбиения на подмножества представлено на рис, 16.
Дальйейщим ifflaasM ^является рассмотрение подмножества И,t], [1,6], f6,3], Jig НГМ^ 102+10= 112 Й пЬДмнбШЬт^
[ЫЬ [1 .б], [б>3], [ЗД Включение дуги $,2) запрещает исщзьлв? зование элементов третьей строки и второго сЮлбца^ а +агкже 1»
дуги; (2,4).'Поэтому для последующих оценок . используется -матрица:
; £ Таблица 2.10
4 5 НГМ (4,1], м.(6,3],: [3;2] —102
....... .. Г- 5 оо ; о О оо
Эта матрица прямо указывает на то, что в искомый маршрут надо включить дуги- (2,5),'н’ (5,4), йе меняя при этом нижней оценки, которая становится точной оценкой длины 1га^шрутй. ’ v 1 '-"у /
‘^WftitM рб|)азой^ дальнейшееразвйтиедерёва (рйС?17) г^И‘ велок образованию определенного гамиль^онЬва маршрут^ ДЛйнбЮ’ 102 единицы. СопбётавЛяя длину найденного маршрута с нижней границей длин маршрутов, вкбййщйх-’в подмножества [4,1]; [4, it [1,6], [4,1], [1Ж Kfl; [4,1], [1Ж [6М [ЗЖ не рассмотренных до конца, мы видим, что рассмотрение подавляющего большинства из них не имеет никакого смысла.
Это обстоятельство отражено на рис. 17 обрывом соответствующих ветвей ([4,1], [1,6] и др.).
Однако может оказаться, что среди гамильтоновых контуров подмножества [4,1] с нижней границей h—^i7 имеется луч-, ший маршрут. Поэтому надо изучить это подмножество, работая с матрицей, показанной в табл. 2.4.
Следуя методике, мы должны рассмотреть подмножества гамильтоновых контуров [4,1], [6,1] и [4,1], [6,1]. Нижняя граница первого подмножества равна
- НГМ [4Д], 0=97+42=139, ! п;
в силу чего это подмножество может в дальнейшем, не рцс^ сматриваться. Чго касается второго, из, указанных подмножеств, товкц^ченне дуги (6,1) ..требует изъятия шестой строки и первого столбца в табл. £4, Кроме того, во? избежание цо* явления негамильтрновых циклов надо положить , d\$='op. В результате'этих преобразований получим таблицу:
,Ха,блдц^ ,24tl
2 3 4 5 V 6
1 59 64 0 61 оо
2 оо 5 18 0 81
3 0 оо 62 . 4 9
4 0 42 оо 18 36
5 15 0 27 оо 55
которая допускает приведение по шестому столбцу. Приведение улучшает нижнюю оценку, которая становится равной
НГМ [4Л], [6,1]= 97 +9=106.
Следовательно, каждое из рассмотренных подмножеств .в качестве нижней границы, имеет величину большую, чем найденный гамильтонов контур (4,1,6,3,2,5,4) длиною 102 единицы, и их нет смысларассматривать.
Дерево разветвлений в окончательном виде с указанием нижних гранцц показано на.рис. i8.
Отметим elite раз? что помимо использованного в этом алгоритме способа получения нижней оценки (сумма констант приведения)^;^о^цд;4>^юэмендовать и более точные методы, например, связанные решением задач линейного программирования.. Применение более точных оценок в принципе сокращает число рассматриваемых ветвей, но требует почти в обязательном порядке привлечения электронных вычислительных машин.
«
Один из алгоритмов такого рода предложен Шапиро. Начальная оценка снизу длины любого гамильтонова контура получается при помощи решения задачи назначения. -Если при этом задача назначения позволила указать какой-либо гамильтонов контур, то, как указывалось ранее (§ S), это означает, что получено решение задачи о коммивояжере. Если же решение задачи назначения привело к образованию нескольких разрозненных негамильтоновых контуров по типу рис. 12,6, то поступают следующим образом. Берут один из контуров {например, 0 и решают одну за другой k
новых задач назначения, отличающихся от исходной задачи тем, что в первой из них предполагается, что ^„{,=оо, во второй rf.4bi,=oo и т. д. Решение первой задачи дает нижнюю оценку длины множества гамильтоновых контуров Д14], решение второй задачи дает ЫГМ(«ь У я т. д.
Результаты расчетов сопровождаются построением соответствующего дерева. Если в результате решения одной из таких задач удалось получить гамильтонов контур и его длина оказалась меньше, чем все ранее полученные оценки снизу, то это и есть искомое решение задачи о коммивояжере. Если же в каждой из задач вновь получилась совокупность 42
разрозненных контуров, то результаты решения этих задач используют для улучшения оценок и выбора направления дальнейшего развития дерева. В конце концов этот процесс, как и только что описанный метод, неизбежно приведёт к точному решению задачи о коммивояжере.
Разумеется, еще более точная оценка снизу получается в результате решения задачи линейного программирования соответствующей задачи о коммивояжере, в которой соблюдя* ются все ограничения, кроме условия целочисленности. В этом случае число ветвей и общие размеры дерева1 сокращаются, но сам процесс построения, Дерева становится намного более сложным. / ft
Материалы этой главы, дают достаточно оснований счи-тать, что наиболее эффективным способом облегчения вычислений явилось бы уменьшение,числа городов, которые предстоит обойти коммивояжеру. Если рассмотрение расположения городов в пространстве ийиже анализ, матрицы; расстояний подсказываю*, что какая-то дуга или последовательность дуг входит в искомы й гамильтонов контур, то в дальнейшем такие дуги или последовательность дуг можно рассматривать как один обобщенный город и на несколько столбцов и строк сократить. исходную матрицу расстояний. Помимо этого существует ещ» ИельШ; ря»: способов» сокращения размеров задачу которые можно использовать для. получения приближенного решения[13Ь ?
Глава III /
Экстремальные Д комбинаторные задачи \ \
Экстремальными комбинаторными* задачами называются задачи, в которых имеется ограниченное число возможных решений, причем это'число обычно столь велико, что поиск наилучшего решения путём Перечисления их всех и попарного сравнения заведомо исключается. Одна из наиболее интересных задач подобного рода —задача о коммивояжере— подробно описана в предыдущих главах. Другие задачи этого типа также имеют большое практическое значение и в этом отношении не уступают подчас задаче о коммивояжере. При этом все те идеи, которые используются при создании алгоритмов решения, задачи о коммивояжере, с некЬторыми дополнениями и изменениями пригодны й для решения Других комбинаторных экстремальных задач. ' ‘ ' ...
Из большого числа таких задач мы более или менее,.под-рббйЬ опйшём три: ’ ’ ’ ’ ’ ’*’ :
а) задачу балансирования сборочной линии;
, р б), задачу срстайления расписанияра^от;ч / ; ~
в) задачу последовательной .обработки изделий да-,^И станках. -г' :
s< сДдя того, чтобы продемонстрировать, что к указанны^ задачам применимы те же самые идеи и,методы, котррыефеша-,ю£ э,адану О козммцвояжерр, докажем, что псррувр. из них ’'мЬ^к^ с^брмулйровать. как задачу целочисленного дид^др-*го программирования, а вторую как Задачу динамического программирования. Одновременно мы.опишем, медод решения ^рет^Ьй^Чщ’^^йё айалЬТи^н^ НётДд^’йетдеО гр|рд, изложенному в предыдущей £лав£ ' ’ “ t '•- < • v *
•<4
$ 1. ЗАДАЧА БАЛАНСИРОВАНИЯ СБОРОЧНОЙ ЛИНИИ ’
Пусть для того чтобы изготовить некоторое изделие, нужно произвести совокупность работ At, А2,...,Ап, причем указано время, необходимое для осуществления каждой работы tk. Кроме того, указаны условия предшествования, вытекающие из технологии процесса сборки, т. е. условия вида «работа Ai должна быть сделана прежде, чем начнется работа А*». Коротко условия предшествования записывают так: « знак предшествования), а всю совокупность этих условий
изображают в виде некоторого ориентированного гр.афа (но типу рис. 19), в котором каждому отношению соответствует дуга, идущая от вершины i к вершине k. Наконец, пусть указано число Af последовательно расположенных рабочих мест на конвейере.
Требуется так распределить работы между рабочими местами, чтобы:
а) удовлетворялись условия предшествования;
б) сумма времён выполнения работ, приписанных /-му месту, не превышала времени такта работы конвейера Т;
в) время такта Т было бы минимальным.
При соблюдении этих условий вся работа закончится за время, не превышающее МТ.
Иногда эту задачу формулируют несколько иначе, требуя мйнимизНии числа-рабочих мест М при заданном времени такта Т.
Покажем, каким образом сформулироватьэту задачу как задачу линёйнбго программДрованця. ' -
45
Обозначим через //^неизвестную величину, принимающую два значения (0 или 1) и будем считать, что i-я работа производится на /-м рабочем -месте, тогда и только тогда, когда 1, и имеет место-обратное, если ^j=»0.
Каждая работа должна быть обязательно выполнена на одном из рабочих мест, поэтому
; Суммы вйда^КА чцсленноь равны сумме времен выполнения всех работ на /-М рабочем йес^ На эти суммы накладываются ограничения
-Z = . . .... . . ' - I :; , > • I :
2%»^ 2> • *», 2И-
•1. ... ' - - < ••• - ч
Изотношения предшествования следует; что
2 УМ^ 2 ^*7» ш=1, 2,...,, ЛГ, .,,1 J-l 7-1 •
Собирая вместе все ограничения, получим следующую формулировку задачи в терминах линейного целочисленного про- * граммирования:
минимизировать Т при следующих ограничениях
«) Г>2^ /=1, 2,..., М,
1-1 .
to 7=4 2,..»., п,
m m
В) 2*»** 4,, M {для задех
/и для которых
г),
д) \Е т«е • должныбыть Целочисленными.
В таком виде задача готова для ее решения *®а' вычисли-тельных машинах, снабженных программами решения задач целочисленного линейного программирования. Но при -ЩРм надо сразу отметить, что подобные задачи большого объема в настоящее время чрезвычайно трудны для решения. .Кац и для задачи & коммИвоИНгёрё тЦрй^'г1б^ё '^
М ’ ' !' "п':' •i''
методами Являются различные эвристические приемы в сочетании с Методами статистической выборки, методы динамического программирования и метод ветвей и границ. В частности, для задачи балансировки сборочных линий эффективным алгоритмом является алгоритм, описанный в работе [12].
§ 2. ЗАДАЧА РАСПИСАНИЯ с ’
Проблема составления расписаний порождает обширный класс задач самой разнообразной- структуры. Одна из возможных ее'nocTaHOBOH ёдсТойт в следующем [4]. Ймеется М станков и п рабрт, причем как,и в только что рассмотренной , задаче о балансировке сборочной линии.на некоторые рабр: ты наложены, ограничения тмпа предшествования /•<£ (-< — знак предшествования)'. Предполагается известным время обработки 1-й Детали на /-м станке и время ^^переналадки /-го станка при переходе с i-й на /*-ю деталью Требуется так распределит!» работы, между станками,, чтобм время^выцолне-ния всего заданий'бйло минймальйым.
В настоящее время большинство таких задач сформулировано в виде зйдач целочнслейнок линейного, Программирования, однако ввиду большого числа вводимых переменных и ограддч.ениД формулировки оказываются мало, пригодными, для практического использования.
К задачам расписания относят также изадачи такого типа [2]. Имеется срвокупность работ 41, Л2,...,ЛЯ и одна машина. Каждая работа требует для своего выполнения ^единиц времени. Заданы функции^ характеризующие- выгоду, связанную с окончанием выполнения i-й работы’ в момент t (например, срочное и обыкновенное исполнение заказа, выплата неустойки за несвоевременное исполнение и т. д. (рис. 20). Предполагается, ,что машина загружена постоянно и никакая работа, раз начатая, не прерывается до ее завершения. Требуется установить такую очередности выполнения работ, при которой суммарная выгода максимальна. Покажем, каким odpWoM'эта задача может быть сформулирована какрадача динамического программирования.
Выделим из всей совокупности работ некоторое подмножество 5, состоящее из k работ /1, Общее время выполнения этик работ обозначим is, а суммарную выгоду, свяэ!ецну|р ^.выподцениеэд’ первчирдедяыж рабСмг в. оптимальном порядке, f (S). Допустим, что среди* работ jt, j2, последней , выполняемой работой, была раббтаг Д, ТоЩа» и$к оптимальном порядке выполнения, остальных работ выгода составит
где S—jm обозначает подмножества работ, <§, из которого исключена работа*/ы.
47
По определению функция f(S) представляет собой максимальную выгоду при выполнении «У работ, поэтому
/(S)=niaX[C;m(Z5)+/(S-ym)]. к«<* '
Вспоминая смысл множеств <5 и S — jm, эту формулу можно переписать более подробно
/ /(Л, Л, .... /^тахК?,Л(/$)+
1<Ш<Л т
*"bZkJb /29 • 1 Jтг-Ъ /ш+1» • • • > /л11*
48 ?
Таким образом, нам удалось выразить функцию f(jt, от k аргументов через известные Cjm (/4) и аналогичные ПО смыслу функции f(/i, /2,...,/т-1, /т+1, ...» jk), НО ОТ меньшего числа аргументов. Функции f(jm) для одного аргумента известны, это просто-напросто значения
Для небольших по размеру задач вычисления по выведенным формулам без труда могут быть проведены вручную.
$ 3. ПОСЛЕДОВАТЕЛЬНАЯ ОБРАБОТКА ДЕТАЛЕЙ
НА ТРЕХ СТАНКАХ
В § 2 главы I был рассмотрен один из важных случаев задачи расписания — задача определения оптимального порядка обработки деталей на двух станках (например, токарном и фрезерном) и показано, что эта задача может быть сведена к задаче о коммивояжере. Далее было показано, что одним из наиболее эффективных способов решения задачи о коммивояжере является метод «ветвей и границ».
В настоящем параграфе мы покажем, что метод ветвей и границ можно было бы применить и непосредственно к исходной задаче, без предварительного ее сведения к задаче о коммивояжере. Такой подход обладает большей общностью, так как на его основе можно решать задачи не только для двух машин, участвующих в последовательной обработке деталей, но и задачи с большим количеством машин. Вообще говоря, такого рода задачи не сводятся к задаче о коммивояжере.
В качестве примера мы будем рассматривать последовательную обработку деталей на трех станках (например, на токарном, фрезерном и шлифовальном), причем, не уменьшая общности, мы можем считать, что каждая деталь должна пройти все три стадии обработки. Случай трех станков интересен в том отношении, что здесь в оптимальном варианте обработки на каждый из станков детали поступают в одной и той же последовательности. В случае же большого числа станков, вообще говоря, последовательность обработки деталей на каждом станке будет различной.
Итак, пусть заданы времена (i = l, 2 п;. /=1, 2, 3)
обработки каждой детали на каждом из станков. Заданы общие для всех деталей условия предшествования, состоящие в том, что каждая деталь сначала обрабатывается на первом, затем на втором и наконец на третьем станке. Время переналадки станков при переходе на новую деталь будем считать пренебрежимо малым. Требуется установить оптимальную очередность выполнения работ, а именно такую, при которой общее время завершения всех работ было бы минимальным.
49
Доказэд&ъ что, в» общем случае, кос да? имеевся М станков, число; возможных аарнаитов икноайениа заказа равно (aty**-2; в. данном конкретном случае, когда М=3, это чдиа равно п£ Метод «ветвей и. границ», к оинсаиию которогв мы сейчас нриетупаем, позволяет на каждом этапе расчетов отсеивать большое количество заведомо невыгодных вариантов.
Чтобы ироменчтБ этот метод, мы должны указать способ, разбиения всего- множества допустим®* вариантов на подмножества и уметь оценивать нижнюю границу основного показателя эффективности— времени выполнения заказа для каждого подмножества, а для конкретного варианта очередности работ уметь найти и точное значение выбранного показателя.
Начнем е последнего в пр» з.тея, чтобы не- повторять рас-сужжи, сраэу же зададимед конкретными величинами- времен обработки,, которые- будем использовать в ижнаетратив-шве® примере'.
Пустьдадан: порядок обработки: деталей (Ыиример^ 4-, Sf № тщетен определить время окончания: работ. Как ж рвиъше (гл; f, f 2> будем вести график начала и конца вы> по&яеаия работ та каждом станке;
/ ТГавогкцак 3.2
тймено* ванне: ва^ат? i Ш?рвый? ставок | станок | Третий! ставок:
начало ковен: НШШЛф | кюнед; J- начало* 1 коион;
ЙШ * Ф р 7 1 Ъ (• 25 25 к 29 1 29 р 38 38 К 44 ? 2& 37 ' 65 » ? t 54 F 65 68‘ ? 2В 4i й & f 65 7Ф i 4> ; 51 ? 74 й 80
При, составлении, этого, графика принималось, что время, начала обработки некоторой детали на. первом станке совпадает со временем окончания обработки предыдущей детали.. 50.
Точно также начало обработки детали ii на втором я третьем станках -совпадает «о временем окончания ее обработки я а предыдущем станке.
Что же касается остальных случаев, то -время начала обработки какой-то ik-й детали на /-м станке совпадает либо с моментом 'окончания обработки предыдущей Детали ва данном «танке, либо с моментом окончания обработки Этой же детали на предыдущем станке, а точнее
^=.тах
Способ ветвления дерева можно принять самый естественный* а именно — исходное множество возможных последовательностей, содержащее п! вариантов, разобьем на i подмножеств, причем варианты первого подмножества начинаются с ii=l, второго подмножества с h=2 и т. д. (рис. 21).
В дальнейшем одно из этих подмножеств разбивается еще на п— 1 подмножеств по аналогичному правилу и так до тех пор, пока не дойдет до единственного варианта, эффектив-ность которого может быть точно определена на основе поч строения таблиц по типу табл. 3.2.
Осталось указать способ вычисления нижней границы для каждого из подмножеств. Это можно сделать различным способом. Например, годятся такие оценки:
й] —время, необходимое для выполнения на всех трех станках работ й, <2, ...,4, выполняемых в первую очередь, плюс время, необходимое для выполнения оставшихся работ на последнем станке, предполагая, что, начиная с этого момента станок работает без простоев;
h2 — время, необходимое для первых k работ на первых двух станках, плюс время, необходимое для выполнения всех
61
оставшихся работ на втором станке, плюс минимальное из времен выполнения оставшихся работ на третьем станке;
йз— время, необходимое для выполнения всех работ на первом станке, плюс минимум суммы времен обработки одной из оставшихся деталей на втором и третьем станке.
Ясно, что намного более точна оценка такого рода h— :=max(fti, h2, h3), но зато она и несколько сложнее вычисляется.
В целях иллюстрации мы остановимся именно на последней оценке и, используя ее, закончим решение начатого примера.
Допустим, что мы решили начать обработку с работы ii = 1. Тогда начало таблицы, построенной по типу табл. 3.2, име?ет вид:
Таблица 3.3
Наименование работы Первый станок Второй станок Третий станок
н к н к е н к
/1=1 0 7 7 20 20 41
Откуда, используя табл. 3.1, получим:
/11 = 41 + 15+5+9+6=76, /12=20+12+17+11 + 3+5 =
=68,
й3=7+18+4+9+6+min (27, 22, 20, 9) =53 ft=max ;(76, 68, 53) =76.
Совершенно аналогично для /1=2, /1=3, Л =4 и /5=5 имеем:
Таблица 3.4
Наименование работ Первый станок Второй станок Третий станок
н к н к н к
4=2 0 18 18 30 30 45
ftI=86. Л2=79, Л3=53. Л=86
52
Таблица 3.5
Наименование работ Первый станок Второй станок Третий станок
н к н к н к
Л=з 0 4 4 21 : ' 21. 26
Л1=77, Л2=66, Л3=53; Й=77
Таблица 3.6
Наименование работ Первый станок Второй станок (Третий станок
н к н к н к
М 0 9 9 20 20 29
Лг=76, ft2=70i Лз=53, Л==76
Таблица 3.7
Наименование работ Первый станок Второй станок Третий станок
н к н к н к
*1 = 5 0 6 6 * 9 9 15
Л^65, Л5«67, Лз=64, Л=67
53
Разбиение исходного множества вариантов на подмножества с указанием нижних оценок продолжительности работ представлено на рис. 21.
В дальнейшем естественно продолжить развитие дерева в вершине <i=5, так как именно этой вершине соответствует минимальная нижняя оценка.
Нам предстоит рассмотреть варианты, в которых последовательно 1, ^=2, t2=3, ij=4. Имеем
Таблица 3.8
Нмймековйяке Первый станок Второй станок Третий станок f * 1
* 1 * » 1 < * 1 К
4=5 5Н j 0 | б б 1 13 -t б 1 9 1 .» I 26 ' ' .9 '.. » 1 15 - - «7 ]
й2=71, ^==64, Л«=76
Таблица 3.9
Нанменоаание Первый станок Второй станок Третий станок ‘
работ и к к к К
4=5 . 4=2 0 -6 6, • 24 6 24 9 36 9 36 . 15 1 51
Л1=86, Л2=82, Л3=66. Л=86
54
Таблица 3.10
Наименование > ' работ Первый станок . : .Второй станок Третий станок
н к Н к н Ж
71=5 0 о ) 6 9 15
6.1 Ю ( ю К \ 27
*1=77 1 Л2=72, Л3==64, Л =*=77
Таблица 3/11
Наименование Первый станок Второй станок Третий станок
работ ; Л L Г м
Ы л Л -6 6 Й 6 15 : S9 v , 26\ 1э Ж 15 35 ;
/^===76, ^2^73, Лз«зз66, *=76 -
Дерево подмножеств приобретает вид (рис. 22 на стр. 55).
Из двух совершенно равноценных продолжений выберем продолжение 4=1- Теперь нам предстоит рассмотреть случаи £з=2,7з=3, 4=4. Для построения дальнейших таблиц используем последнюю строку табл. 3.8.
Таблица 3.12
Наименование . работы Первый станок Второй станок Третий станок
н к н к н к
/1=5
4=1 Г 13 13 26 26 47
4=2 13 31 31 43 47 62
Лх=76, Л2=76, *з== 64, Л—76 '
Таблица 3.13
Наименование работы Первый станок Второй станок * Третий станок
н к н к н к
4=5
/9=1 б" 13 1з 26 26 47
4=3 13 17 26 43 47 52
*i=76, Л2=75, Л3=64, Л—76
Таблица 3.14
Наименование работы Первый станок Второй станок Третий станок.
н к н к н к
4=5
4=1 6 13 13 26 26 47
4=4 13 22 26 37 47 56.
Л1=с76, Л2=71, Лз==6б, Л=76
5$
Мы видим, что все три полученных подмножества равнозначны и любое из них может быть выбрано для дальнейшего развития дерева. Остановимся на первом из. них. Дальнейшие подмножества различаются тем, что 4=3 либо 4=4.
Таблица 3.15
Наименование работы Первый станок Второй станок Третий станок
н к н ж ’ н, к
4=5 -— -мм __ __
4=1 «мш ««м __
4=2 13 31 31 43 47 62
/4=3 31 35 43 60 62 . 67
*1=76, Л2=80, Лз=64, Л=80
Таблица 3.16
Наименование работы Первый станок Второй станок Третий станок
н к н к н к /
4=5 — «м» «мш» -м» мм
1*2=1 мм им ММ «мм мм» мм
4=2 13 31 31 43 47 62
4=4 31 40 43 54 62 71
Л1=76, *2=76, Л3=66 Л=76
Третий станок 1 1 |РЕ
1 1 ISP
Второй станок SS 1 lisp
% 1 1 RS
Первый станок м 1 1 RS
! 1 1 1
Наименование работы U5-4<N'*« II " И LIL
В итоге нам удалось установить, что подмножество вариантов, которое начинается работами о = 5, ij—l, /з=2, 4=4 и, следовательно, заканчивается работой ts=3 имеет нижнюю границу продолжительности работ h=76 (рис. 23). Оценим в точности продолжительность полученного варианта (табл. 3.17).
Полученный результат показывает, что этот конкретный вариант выполнения работ имеет общую продолжительность, меньшую или равную нижней оценке любого из рассмотренных подмножеств. Следовательно, этот вариант относится к числу наилучших. При желании можно было бы исследовать и другие подмножества с нижней оценкой 76. единиц и получить, возможно, несколько равноценных с точки зрения общей продолжнгейьяоетн выполнения заказа вариантов.
Заключение
Рассмотренные в настоящей брошюре задачи и методы их решения имели целью дать представление об одном из интенсивно развивающихся разделов математики — теории упорядочения и показать ее связь с запросами и нуждами практики. При этом необходимо заметить, что реальные жизненные ситуации обычно оказываются намного сложнее тех искусственных схем, которые изложены в настоящей брошюре. Тем не менее методы решения и этих упрощенных схем во многих случаях могут подсказать пути отыскания наиболее выгодного из множества конкурирующих вариантов.
Литература
I. К. Бер ж. Теория графов и ее применения. М., Изд-во иностр, лит., 1962.
2. М. Хелд, Р. М. Карп. Применение динамического программирования к задачам упорядочения.—•Кибернетический сборник, № 9. М., «Мир», 1964.
3. Р. Б е л л м а н, С. Д р е й ф у с. Прикладные задачи динамического программирования. М„ «Наука», 1965.
4. Е. Г. Гольштейн, Д. Б. Юдин. Новые направления в линейном программировании. М., «Сов. радио», 1966.
5. Ю. С. Голубев-Новожилов. Многомашинные комплексы вычислительных средств. М., «Сов. радио», 1966.
6. С. Джонсон. Оптимальное расписание для двух-и трехступенчатых процессов с учетом времени наладки.— Кибернетический сборник (новая серия), вып. 1, 1965.
7. С. Е. Miller, A. W. Tucker, R. A. Zemlin. Integer programming formulation and traveling salesman problems. — Journal of the Association for Computing Mashinery, v. 7. 1960, No. 4, Oct., pp. 326—339.
8. Д ж. Литл, К. M у p т и, Д. С у и н и, К. К э р е л. Алгоритм для решения задачи о коммивояжере. — «Экономика и математические методы», т. 1, вып. 1, 1965.
9. В, И. Мудр о в. Определение гамильтоновых путей кратчайшей длины в полном графе методами целочисленного программирования. — Известия АН СССР. Техническая кибернетика, 1965, № 2.
10. A. L о m n i с k i. 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. Математическая формулировка задачи о комми» вояжере .... . .?. '.-«j.? < •; «к. 3
§ 1. Постановка вопроса Л •»3
4} 2. Некоторые примеры .w. ,.. ....... 6
$ & Необходимые сведения из теории графов ... 15 § 4, Построение полного графа задачи о коммивояжере на основе анализа графа коммуникаций 20
Глава Я. Методы решения задачи о коммивояжере . . 22
§ 1« Эвристические методы я методы Монте-Карло . 22 § 2. Сведете задачи о коммивояжере к задачам целочисленного линейного программирования... 25 § 3. Решение задачи о коммивояжере методами динамического программирования •„ .?< . «...... 30
§ 4. Метод ветвей я границ . 32
Глава /Я. Экстремальные ком&шаторные задачи ... 44
§ 1« Задача балансирования сборочной линии . . 45
| & Задача рашисания 47
$ 3. Последовательная обработка деталей на трех €танКах &*••= «г«те . •••*,. 49
^иовмеме <<< ., • ».•>:«’'< .Л . 60
Литература . 61
Владимир Имновя* МУД РО®
ЗАДАЧА О КОММИВОЯЖЕРЕ
Редактор В. Ю. ИВАНИЦКИЙ* Художник. Л,. FL РОМАСЕНК0 Художественнее редактора В*. Ей. СОКОЛОВ Технический редактор EL Ml ЛОПУХЗОВА Корректор С. Гк ТКАЧЕНКО
А 01845 Сдано в наб. 18/IV-69 р. Подо, к печ. 25/VI 11-69 г. Формат бумаги 60x90/1в. Бумага типографская № 3. Бум. л. 2,0 Печ. л. 4,0 Учлизд. л. 2,99
Тираж 41000 экз. Издательство «Знание». Москва, Центр, Новая пл., д. 3/4. Заказ 3795. Цена 12 коп.
Московская типография № 8 Главполиграфпрома Комитета пб печати при Совете Министров СССР, Хохловский пер., 7._________________________________
Отпечатано в типографики изд-ва «Знание». Зак. 2354.
УВАЖАЕМЫЕ ТОВАРИЩИ!
ИЗДАТЕЛЬСТВО «ЗНАНИЕ» ПРЕДЛАГАЕТ ВАМ СЕРИЮ ПОДПИСНЫХ НАУЧНО-ПОПУЛЯРНЫХ БРОШЮР
«МАТЕМАТИКА, КИБЕРНЕТИКА»
В брошюрах серии будут освещаться проблемы, связанные с применением математики и кибернетики в различных областях знаний. Читатель найдет здесь обзорные статьи ведущих советских специалистов о значении математики и кибернетики, ознакомится с достижениями современной математической науки. В 1970 ГОДУ ПОДПИСЧИКИ СЕРИИ ПОЛУЧАТ 12 БРОШЮР, СРЕДИ НИХ:
• ДЕМИДОВ С. С., кандидат физико-математических наук. Великие проблемы Гильберта.
@ ИВАНИЦКИЙ Г. Р., кандидат технических наук. Геометрия живого.
• ПРУДНИКОВ В. Е., кандидат физико-математических наук. П. Л. ЧЕБЫШЕВ (К 150-ЛЕТИЮ СО ДНЯ РОЖДЕНИЯ).
• БЕСКОНЕЧНОСТЬ В МАТЕМАТИКЕ.
• ПРОБЛЕМЫ СОВРЕМЕННОЙ МАТЕМАТИКИ (сборник переводных статей).
• ПОСТРОЕНИЕ ЭМПИРИЧЕСКИХ ЗАВИСИМОСТЕЙ. Серия «Математика, кибернетика» в каталоге «Союзпечати» расположена в разделе «Научно-популярные журналы» под рубрикой «Брошюры издательства «Знание». Индекс серии 70096.
ВЫПИСЫВАЙТЕ!
ЧИТАЙТЕ!
СЕРИЮ НАУЧНО-ПОПУЛЯРНЫХ БРОШЮР «МАТЕМАТИКА, КИБЕРНЕТИКА».
ПОДПИСНАЯ ЦЕНА НА ГОД 1 РУБ. 08 КОП.
Издательство «Знание»
12 коп.
Индекс
70096
ИЗДАТЕЛЬСТВО «ЗНАНИЕ» Москва 1969