В.В.Ш КУ РБА

Задача
ТРЕХ
СТАНКОВ
В. В. ШКУРБА

ЗАДАЧА

ТРЕХ СТАНКОВ

ИЗДАТЕЛЬСТВО «НАУДА»
ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
Москва 1976
518

Ш 67

УДК 519.95

Задача трех станков. В. В. Шкур б а, Главная
редакция физико-математической литературы изд-ва
«Наука», М., 1976.

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

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

Илл. 36, табл. 23.

20204—141

053(021-76

82-76

Ш

© Главная редакция

физико-математической литературы
издательства «Наука»t 1976
ОГЛАВЛЕНИЕ

Предисловие ................................................. 4

§ 1.	Расписания............................................. 5

1.	Календарное планирование (5). 2. Формулировки математи-
ческих задач (6). 3. Представление расписаний (8). 4. Опти-
мальные расписания (12).

§ 2.	Экстремальные перестановки.............................13

1.	Перестановки (13). 2. Задача директора (15). 3. Экстремаль-
ные перестановки и задачи очередности (16). 4. Задача о назна-
чениях, или как рассадить класс за партами (17).

§ 3.	Метод перебора и схема конструирования вариантов . . 20

1.	Метод перебора (20). 2. Алгоритмы построения «.-переста-
новок (23). 3. Схема конструирования вариантов. Порфири-
ан (27).

§ 4.	Где достаточно построить порфириан.....................30

1.	Путешествие бродячего торговца по плоскости и на графе
(30). 2. Расстановка оборудования вдоль кругового конвей-
ера (33). 3. Загадка маленькой мушки (37).

§ 5.	Перестановочный прием..................................42

1.	Решение задачи директора (42). 2. Задача одного станка (43).

3.	Задача двух станков (46;. 4. Интервалы очередности (51).

§ 6.	Последовательное отсеивание~вариантов. Доминирова ше 54

1.	Отсеивание по правилам доминирования (54). 2. Решение
задачи бродячего торговца (56). 3. Поиск «критического пути» (53).

§ 7.	Последовательное отсеивание вариантов. Ветви и границы 64

1.	Схема «ветвей и границ» (61). 2. Задача о рюкзаке (65).

3.	Решение задачи бродячего торговца методом ветвей и гра-
ниц (69).

§ 8.	Задача трех станков....................................78

1.	Постановка задачи и свойства оптимального решения (78).

2.	Решение методом последовательного отсеивания вариантов (80;.

3.	Решение по схеме «ветвей и границ» (86).

§ 9.	И более сложные задачи.................................83

1.	Задача четырех станков (88). 2. Приоритеты (91). 3. Случайные
ветвления и т. д. (92).

Заключение...................•...............................94

Предметный указатель.......................................  95
ПРЕДИСЛОВИЕ

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

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

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

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

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

В основу книги положены занятия, проведенные со школь-
никами 8—10 классов, участниками летней сессии Малой Акаде-
мии наук Крыма «Искатель» (пос. Фрунзенское, 1972 г.).

Звездочкой в тексте отмечены упражнения, представляю-
щие скорее «вопросы для размышления», чем традиционные за-
дачи. Символ (§ 6, п. 3) в тексте означает ссылку на § 6,
пункт 3. Формулы нумеруются внутри параграфа, так что сим-
вол (2, § 6) означает ссылку на формулу (2) в § 6. Ссылка (2)
означает обращение к формуле (2) того же параграфа.

Я буду благодарен читателям, которые пришлют замечания.

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

В. В. Шкурба
§ 1. РАСПИСАНИЯ

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

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

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

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

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

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

Пример (из задачника по алгебре для 8-го
класса).

Поезд шел со скоростью 36 км;час, затем на пере-
гоне, равном 1,5 км, поезд шел равноускоренно с уско-
рением 0,1 м!сек2. Найти время, в течение которого
поезд прошел перегон.

Сообразительный ученик быстро свяжет слово
«равноускоренно» с формулой

С / I ai2

и обнаружит, что S, и0, а заданы условиями задачи,
составит уравнение

и найдет t, правильно применяя формулу решения
квадратного уравнения к нашему случаю

-.,,±7»;+^	(1)

а	' '

учтя при этом, что t 0.
Решения, подобные (1), где представлен способ
решения задачи (связывающая с неизвестным исход-
ные данные, замененные буквами, «цепочка отноше-
ний») без выполнения самих вычислений, называют
решениями в общем виде, формульными решениями.

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

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

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

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

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

Здесь объект поиска — не число, более того, здесь
обычно еще требуется выполнить построение с по-
мощью некоторых инструментов — например, одного
циркуля или одной линейки**).

Общим для этих рассмотренных типов задач яв-
ляется то, что с самого начала известно, к какому
классу принадлежат искомые объекты (первый — к

*) См., например, «Популярные лекции по математике»
(ПЛМ), выпуск 26.

**) Такие задачи подробно рассмотрены в выпусках 25 и
29 ПЛМ.
числам, второй — геометрическим фигурам), с по-
мощью каких операций (арифметических вычислений
или вычерчиваний) можно найти эти объекты.

Расписания тоже мы поначалу научимся формаль-
но представлять, а затем уже — строить.

Рис. 1. Блок-схема алго-
ритма вычисления произ-
ведения первых N нату-
ральных чисел.

Вычисления

^Комментарии,
замечания,
предупреждения

Рис. 2. Некоторые
стандартные обозна-
чения для блок-схем.

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

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

доты \	По недель - ник	Вторник	Среда	; Четверг,	\ Пятница	Суддота Понедель- ник	Вторник	Среда	Четверг	I
1						I I  I j				
										
2						i i ।				
										
Ъ	I					I				
4						I I I	ежяиж			
5						I I  I				
6						I I  I				
										

Рис. 3. Примерная временная диаграмма подготовки сочинения
по русской литературе.

1. Продумывание темы, основных высказываемых мыслей, наметка плана
сочинения. 2. Просмотр литературы, подбор материалов, эпиграфа, цити-
руемых высказываний. 3. Составление подробного оглавления, плана — го
абзацам. 4. Окончательный подбор материалов, высказываний, цитат со-
гласно плану, шлифовка плана сочинения по абзацам. 5. Написание чер-
новика. 6. Переписывание набело, проверка сочинения.

Сетевым графиком (или стрелочной диаграммой)
обычно представляют логическую взаимосвязь во вре-
мени отдельных работ, на которые разбивается вы-
полнение некоторого задания. На рис. 4 сетевой гра-
фик представлен в так называемой форме «вершины—
работы». На рисунке кружочками, называемыми вер-
шинами сетевого графика, обозначены отдельные ра-
боты, на которые расчленяется общий комплекс ра-
бот, стрелочки информируют о взаимозависимости
очередности выполнения работ. Так из рис. 4 видно,
что приступить к выполнению работы 5 следует (раз-
умно, должно) только после того, как выполнены ра-
боты 2 и 3.

Рис. 4. Сетевой график подготовки вечера, посвященного твор-
честву Владимира Маяковского.

1. Предварительное обсуждение программы вечера, выделение ответствен-
ных по разделам. 2. Определение индивидуальных исполнителей, продумы-
вание их выступлений. 3. Обсуждение плана подготовки сцен из пьес
«Клоп» и «Баня», подбор исполнителей. 4. Выяснение вопроса о возмож-
ности приглашения иа вечер известных поэтов, артистов, демонстрации
документального кинофильма. 5. Составление плана обеспечивания вечера
(оформление зала, реквизит для спектакля). 6. Окончательное обсуждение и
согласование программы и сроков проведения вечера, списка приглашений.
7. Подготовка индивидуальных выступлений. 8. Репетиции индивидуальных
выступлений. 9. Подготовка ролей в спектаклях. 10. Первая репетиция сцен.
11. Вторая репетиция сцен. 12. Подготовка костюмов. 13. Подготовка деко-
раций и стендов для оформления зала. 14. Оформление зала. 15. Генераль-
ная репетиция. 16. Доставка кинофильма. 17. Приглашения на вечер. 18. Про-
ведение вечера.

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

На рис. 5 представлен тот же сетевой график, что
и на рис. 4, только каждой вершине поставлено в со-
ответствие число — оценка времени выполнения от-
дельной работы в днях. Жирными стрелками обозна-
чен так называемый критический путь’, если сложить
продолжительности работ, составляющих этот путь
в нашем примере, то станет ясно, что от принятия ре-
шения о проведении вечера до дня проведения вечера
должно пройти не менее 16 дней (при данных оцен-
ках времени выполнения отдельных работ). Любая
другая последовательность взаимоувязанных во вре-
мени работ — другой путь в сетевом графике — не

Рис. 5. Сетевой график с оценками продолжительностей отдель-
ных работ и указанием критического пути.

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

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

Упражнение 1. Составьте временную диаграмму вы-
полнения работ для сетевого графика, представленного на рис. 4
и рис. 5, исходя из целей подготовки вечера в кратчайшие сроки.
Можно ли сдвинуть во времени (передвинуть вправо па
один день отрезок во временной диаграмме) работу 12? а 14?
Насколько можно сдвигать сроки выполнения работ, лежащих
и не лежащих на критическом пути?

Упражнение 2. Попробуйте на примерах отыскать кри-
тический путь и написать общую инструкцию определения кри-
тического пути в сетевом графике. Сравните его с алгоритмом,
описанным в § 6, п. 3.

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

Теперь вы, наверное, убедились и в сложности за-
дачи составления расписаний, и в необходимости со-
ставления расписаний: очень часто, когда кто-то
«разрывается» между многими делами и запустил
учебу, причина — в неумении «раскроить» время, упо-
рядочить дела и поручения во времени.

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

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

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

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

Упражнение 3*. Как вы думаете, в чем трудности со-
ставления наилучшего школьного расписания? наилучшего фут-
больного календаря? и что означает в этих случаях «наилучшее
расписание»?

§ 2.	ЭКСТРЕМАЛЬНЫЕ ПЕРЕСТАНОВКИ

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

Произвольную n-перестановку мы будем обозна-
чать символом

О,/г===(^1> ^*2, •••>	•••?	(О

таким образом, ik (или г\(оп))—число, стоящее в пе-
рестановке оп на k-м (от начала) месте; k(i) (или
k(i/o))—номер места, которое занимает в переста-
новке о число i. В перестановке (2, 4, 1, 3), например,
*з = 1, /Д3) = 4.

Число Р(п) всех возможных различных п-переста-
новок равно произведению чисел от 1 до п, называе-
мому п-факториалом и обозначаемому п\ = 1 - 2-3 ... п.

Действительно, легко доказать справедливость сле-
дующего рекуррентного *) соотношения:

Р(п) = Р(п-\)-п,	Р(1) = 1,	(2)

*) Рекуррентными соотношениями называют формулы для
общего члена ип последовательности, если ип можно выразить
как функцию некоторого числа I предыдущих членов последова-
тельности ип = f(un-i, Un-z, .ип-\). Такие последователь-
ности называют также возвратными (см. ПЛМ, выпуск 1).
откуда и следует, что

Р (п) = п\.

(3)

Доказательство строится по индукции. Справедли-
вость Р(1)= 1 очевидна. Различных ^-перестановок
с зафиксированным и, очевидно, столько, сколько
можно построить различных перестановок остальных
п— 1 элементов в огп, т. е. Р(п— 1). Кроме того, оче-
видно, что и может принимать п значений. Отсюда и
следует (2).

Число Р(п) быстро растет с возрастанием п
(табл. 1)—быстрее, чем даже показательная функ-

Таблица 1

Значения и!, вычисленные непосредственно*)
и по формуле Стирлинга (п!	S(n))

п	п !	5 (п)	п	п !	S (п)
1	1	0,9221	8	40 320	39 901
2	2	1,9189	9	362 880	359 536
3	6	5,8362	10	3 628 800	3 598 690
4	24	23,5052	15	1,308- 1012	1,3005- 1012
5	120	118,017	20	2,433- 10'8	2,423- 1018
6	720	710,06	25	1,511 • 1025	1,546- 1025
7	5 040	4980,4	50	3,041 • 1061	3,037- 1061
	*) То есть п	о формуле	100  (3) с ]	9,333 • 10157  последующим	9,327- 10157  [ округле-
нием. В табл. 1		приведены результаты вычислении, выпол- «Млгр». На ЭВМ «Мир» удается в явном			
ненн	ых на ЭВМ				
виде	: выписать число 100 !  ЮО! = 93 323 215 443 !		941 152	! 681 699 238	856
	2 о 9	700 490 715 !	968 234	• 381 621 468	592
	963 ;	895 217 599 993 229		। 915 608 941	463
	976	156 518 286 253 697		920 827 223	758
	251	185 210 916 1	364 000	000 000 000	000
ООО 1  На других ЭВМ		000 000  чаще всего :	приходится довольствоваться		

। приближенными вычислениями (как и в табл. 1).

ция ап при любом наперед заданном а (так что
п\ > ап начиная с некоторого /г). Порядок роста
функции Р(п) устанавливает следующая формула

Н
Стирлинга *) •

п\ \//2лп • ппе п.	(4)

Многие практические задачи сводятся к определению
некоторой перестановки. Например, как /гперестанов-
ка (I) может быть представлено распределение н
претендентов по п местам: ik здесь — номер претен-
дента, распределенного на й-е место. Как п-переста-
новка может рассматриваться также решение задачи
об очередности последовательного выполнения п
(перенумерованных предварительно) работ; здесь—>
номер той работы, которая, согласно решению, будет
выполнена k-й по порядку.

2.	Задача директора. В приемной в ожидании лич-
ной встречи с директором собралось п посетителей.
Предварительный опрос позволил выяснить, сколько
времени должен уделить директор рассмотрению во-
проса каждого посетителя: для г-го посетителя (со-
гласно тому, как мы их перенумеровали) это время
обозначим через 7\. Директор, зная, что хотя общее
(суммарное) время, которое он уделит всем посетите-
лям, одно и то же, Г = 22 Tj**) (независимо о т о ч е-

i

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

Решением задачи директора, очевидно, будет не-
которая ^-перестановка чисел

= (Zj, z*2, • • ♦, ik • • •,	(5)

соответствующая очередности приема посетителей.

*) Джеймс Стирлинг, шотландский математик (1692-—*
1770 гг.). Из его построений следует формула, носящая его имя
(в явном виде в его трудах не встречалась).

**) Сумма п последовательных чисел (аД обозначается
п	п

е- Zа.~а{ + а2 + ... Где не возникает недо-
i=1	i=l

разумений, используют запись 22 аг

i
Обозначим через т/г(оп) время ожидания в прием-
ной посетителя й? при очередности приема, задавае-
мой перестановкой оп.

Очевидно, что

Tfe(a„) = Tfe_1(a„) + r/A_1, Ti(a„) = 0,	(6)

причем, естественно, предполагается, что директор не
делает заметных (не равных 0) перерывов между
приемами двух посетителей.

Директор ставит задачу: найти такую перестанов-
ку (уп, на которой величина

F (<т„) = z (ст„)	(7)

к

принимает наименьшее значение.

Другими словами, требуется среди всех возмож-
ных перестановок оп найти такую, которая минимизи-
рует значение функции F(<yn). Последняя фраза —
уже почти «математическая» постановка задачи ди-
ректора: здесь определено множество объектов, среди
которых надо искать решение задачи — перестановки
(о посетителях и директоре мы уже на время — до ре-
шения задачи — забыли). Здесь же указано свойство
искомого решения (для него значение F(<уп) является
минимальным); ранее было определено, как вычис-
лить F (on) для каждой перестановки.

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

В задачах поиска экстремальной перестановки тре-
буется найти ^-перестановку ап, на которой некото-
рая функция F(c)n) достигает экстремума (минимума
или максимума в зависимости от постановки задачи,
в нашем примере — минимума) и задан способ вы-
числения F(on) на каждой перестановке оп.

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

Упражнение 4. Покажите, что задачи поиска очередно-
сти приема посетителей по критерию минимизации общего вре-
мени ожидания в приемной, по критерию минимизации среднего
времен ожидания в приемной

S т1 (»п)

гы-\—

и по критерию минимизации общего времени нахождения в при-
емной, включая и время приема

эквивалентны. Более общо: умножение функции-критерия на
константу или прибавление к ней константы приводит к эквива-
лентной постановке.

То, что выбор функции-критерия — далеко не оче-
видная вещь — показывает следующая задача.

4.	Задача о назначениях, или как рассадить класс
за партами. Эта задача больше известна как задача о
женихах и невестах. В некотором царстве-государстве
на одиноком острове живут п женихов и п невест. Во-
прос состоит в том, как лучшим образом всех их
переженить. Решение становится невозможным,
если принять во внимание, что

«Оля любит Сашу,
И Зоя любит Сашу,
А Саша любит Лилю,
Лиля же любит Андрея,
Да Андрей никого не любит,
Но зато вот Сережа
По-прежнему любит Олю...».

Отношения между «женихами и невестами», соот-
ветствующие приведенному утверждению, схематиче-

2 В. В, Шкурба

17
ски отражены на графе *) рис. 6. Патриархальные
островитяне уважают чувства молодых людей, но и
заботятся об интересах острова в целом. Противоре-
чивый узел отношений молодых людей ими разру-
бается следующим образом. Считается, что не исклю-
чена возможность заключения любого брака, но
одни браки предпочтительнее других. Эта предпочти-
тельность выражена численно: для брака между i-м
женихом и /г-й невестой она получает значение aih.
Это означает, что в общую суммарную «пользу» (для

Рис. 6. Граф взаимоотношений в одном коллективе, стрелочка
соответствует отношению «любит» (тот, от кого стрелочка на-
правлена, того, на кого направлена).

островного государства) каждая свадьба вносит свое
слагаемое, равное aih.

В общей постановке задачи о назначениях тре-
буется п претендентов назначить на п должностей —1
на каждую должность по одному. Общая польза рас-
сматривается как выгода, суммируемая по всем на-
значениям, а выгода от назначения i-го претендента
на k-ю должность оценивается в aih независимо от
других назначений.

Как уже говорилось (§ 2, п. 1), всякая переста-
новка On представляет возможное решение задачи
о назначениях. Требуется найти такую перестановку

*) В математике конструкции, составленные из кружочков и
соединяющих их стрелочек, принято называть графами. Кру-
жочки в нем принято называть вершинами, стрелочки — дугами
графа. Так сетевой график есть граф. (Подробнее о графах
см в статье М. И. Башмакова «Паросочетания и транспортные
сети», «Квант», 1970, № 4.)
Gn, которая максимизирует F(vn):

F{on)-=Yai^ .	(8)

k *

Определять выгоду aik от назначения Fro претен-
дента на fe-ю должность принято с помощью гак
называемых экспертных оценок, для чего собирают не-
который представительный консилиум специалистов-
экспертов, и они выставляют свои оценки — напри-
мер, в шестибалльной системе — выгодности каждого
возможного назначения (аналогично тому, как вы-
ставляют оценки за исполнение программы в фигур-
ном катании на коньках). Крайние оценки (наимень-
шая и наибольшая), как правило, отбрасываются,
оставшиеся усредняются (суммируются и делятся на
их число), эта усредненная оценка и принимается за
значение alh. Повторяем, такая оценка должна быть
заранее поставлена любому возможному назначе-
нию— любой паре (t, k). Явная нежелательность ка-
кого-то назначения фиксируется в самой низкой
оценке для этого назначения.

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

Таблица 2

	Оля	Зоя	Лиля
Саша	5	4	3
Андрей	2	2	4
Сережа	4	1	3

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

. *) Дополнение к упражнению 5. Вы согласны
.с тем, что табл. 2 соответствует рис. 6? Как бы вы проводили
экспертизу и назначали оценки Особенно в случае задачи
упражнения 5, где решение в конце концов обязательно.
Упражнение 7*. А если в классе не поровну юношей
л девушек, можно ли и в этом случае задачу о размещении уча-
щихся за партами свести к решению задачи о назначениях?
Точнее: если вы уже знаете, как решать задачу о назначениях,
как бы вы решали задачу о размещении учащихся за партами,
если в классе не поровну юношей и девушек?

Упражнение 8*. Задача бродячего торговца или ком-
мивояжера формулируется следующим образом: некий комми-
вояжер должен объехать п городов, чтобы в каждом побывать
только один раз, и совершить это, сделав минимальный путь
(расстояния aih между любыми двумя городами i и k заданы).
Покажите, что задачу бродячего торговца можно свести к поиску
экстремальной перестановки. Что вы можете сказать о функции-
критерии в этой задаче? В чем существенное отличие формаль-
ных постановок задачи бродячего торговца от задачи о назна-
чениях? Изменилась бы постановка задачи, если бы вместо
расстояний указывалось время путешествия между городами и
требовалось совершить объезд городов за минимальное время*)?

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

Упражнение 9*. Подскажите секретарю комитета ком-
сомола в школе, что при планировании повестки дня заседаний
комитета неплохо вспомнить о задаче директора. Как в этом
случае надо сформулировать задачу?

§ 3.	МЕТОД ПЕРЕБОРА

И СХЕМА КОНСТРУИРОВАНИЯ ВАРИАНТОВ

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

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

♦) В такой постановке задача бродячего торговца может
рассматриваться как задача составления расписания.

**) В английской терминологии — «метод проб и ошибок».
жества допустимых решений и притом сравнительно
малочисленного, чтобы можно было провести
все вычисления и сравнения в приемлемое время.

Табл. 3 демонстрирует применение метода пере-
бора в решении задачи, заданной упражнением 5.

Таблица 3

Возможные решения	Значения критерия	На и луч- шее?	Возможные решения	Значения критерия	Наилуч- шее?
<1, 2, 3)	10	—	(2, 3, 1)	12	Да
<1, 3, 2)	10	—	<3, 1, 2)	6	—
(2, 1, 3)	9	—-	(3, 2, 1>	9	—

Здесь нетрудно выписать все возможные решения
(первый столбец табл. 3), затем вычислить значения
функции-критерия (8, § 2) для каждого варианта
(второй столбец табл. 3), указать (после просмотра
этого столбца) наилучшее значение (2, 3, 1).

В некотором смысле метод перебора — самый при-
митивный метод решения задачи, который «чистые»
математики вряд ли даже назовут математическим.
Однако математики-прикладники не так уж редко ис-
пользуют этот метод для решения практических за-
дач, особенно с появлением ЭВМ.

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

Пример*). Рассмотрим задачу определения экстремума
функции f(x) = Зх4 + 4х3—12х2, заданной на отрезке [—2, 2].
Экстремум такой функции достигается либо в крайних точках
отрезка, либо внутри отрезка в точках, где производная функ-
ции обращается в нуль. Таким образом, вместо бесконечного
множества точек отрезка [—2, 2] экстремум функции следует

*) При решении этого примера предполагается знание того,
как находить экстремум функции одной переменной с помощью
производной, т. е. раздела математики, изучаемого в 10-м классе.
Для тех, кто еще не овладел этими понятиями, достаточно за-
помнить, что в задачах рассмотренного в примере типа вопрос
об экстремуме функции удается подменить решением вспомога-
тельной задачи поиска корней уравнения.
искать среди значений f(x) для точек —2, 0, 1, 2, (—2, 0, 1 —•
корни уравнения f'(x) — 0, производная же нашей функции есть
j'(x) = 12х3 4- 12х2— 24% — 12х(х2-|-х — 2)). Максимум f(x)
достигается, как это нетрудно проверить теперь методом пере-
бора, в точке х — 2, f(x) = 32, минимум достигается в точке
X = —2, f(x) = —32.

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

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

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

Упражнение 10. Проверьте это утверждение, исходя из
предположения, что ЭВМ выполняет сотни тысяч операций в се-
кунду, а на построение одной перестановки и вычисление функ-
ции-критерия на ней вы тратите не более 10 операций.

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

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

2.	Алгоритмы построения п-перестановок. Однако,
чтобы «улучшать» метод перебора, нужно, прежде
всего, уметь им пользоваться — для задач поиска эк-
стремальных перестановок это означает уметь строить
все возможные n-перестановки, другими словами, надо
знать алгоритм построения всех п-перестановок.

Нетрудно после некоторых попыток «нащупать»
элементарный регулярный прием получения последо-
вательности всех n-перестановок (чем мы уже неявно
воспользовались при формировании табл. 3 из преды-
дущего пункта), начиная с начального упорядочения
чисел 1, 2, п по возрастанию (пусть п = 5):

1,	2,	3,	4,	5

1,	2,	3,	5,	4

1,	2,	4,	3,	5

1,	2,	4,	5,	3

1,	2,	5,	3,	4

1,	2,	5,	4,	3

1,	3,	2,	4,	5

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

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

Рассмотрим некоторую перестановку оп. Найдем
первую с конца перестановки упорядоченную пару.
Так в перестановке оп — (1, 3, 5, 4, 2) первая с конца
упорядоченная пара есть пара (3, 5). Первое число
такой пары назовем обрывающим. Перестановочный
хвост в оп образует последовательность чисел, начи-
ная с обрывающего.

Реупорядочитъ перестановочный хвост означает:

1)	заменить обрывающее число на наименьшее из
перестановочного хвоста число, превосходящее
обрывающее;
Рис. 7. Блок-схема Алгоритма-1 получения всех и-перестановок.
2)	все остальные числа изгперестановочного хво-
ста (вместе с обрывающим) расположить в порядке
возрастания.

Так в нашей перестановке оп = (1, 3, 5, 4, 2) об-
рывающее число есть 3, перестановочный хвост есть
последовательность (3, 5, 4, 2).

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

Введение понятий «обрывающего числа», «пере-
становочного хвоста», «реупорядочения» позволяет
упростить описание алгоритма построения всех п-пе-
рестановок. Этот алгоритм — назовем его Алгорит-
мом-].— представлен блок-схемой на рис. 7. Получе-
ние первых нескольких перестановок по этому алго-
ритму отображено в табл. 4.

Таблица 4

Первые 6 перестановок,
полученные согласно Алгоритму-1

№	Перестановка	Обрывающее число	Перестановочный хвост и его реупорядочение
1	<1, 2, 3, 4, 5)	4	(4, 5) —> (5, 4)
2	(1, 2, 3, 5, 4)	3	(3, 5, 4) —> (4, 3, 5)
3	<1, 2, 4, 3, 5)	3	(3, 5) —> (5, 3)
4	<1, 2, 4, 5, 3)	4	(4, 5, 3) —> (5, 3, 4)
5	(1, 2, 5, 3, 4)	3	(3, 4) —> (4, 3)
6	(1, 2, 5, 4, 3)	2	(2, 5, 4, 3) —> (3, 2, 4, 5)

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

Другой алгоритм — Алгоритм-2 — получения всех
n-перестановок представлен блок-схемой на рис. 8.

Рис. 8. Блок-схема Алгоритма-2 по пучения всех я-перестановок.

Только один термин в блок-схеме рис. 8 нуждается
в пояснении.

Назовем «вращением» некоторой последователь-
ности А чисел замену ее другой последовательностью
В, где число, стоящее в А на первом месте, оказы-
вается в В на последнем месте, взаимное располо-
жение других чисел не меняется. Так вращение (1,
2, 3) приводит к (2, 3, 1).	,

Табл. 5 поясняет ход решения по этому алгоритму
при получении первых нескольких перестановок.

Таблица 5

Первые перестановки,
полученные согласно Алгоритму-2

№	Перестановка	Вращаемая часть	Результат вращения
1	<1, 2, 3, 4, 5)	т = 5 :(1, 2, 3, 4, 5)	<2, 3, 4, 5, 1)
2	(2, 3, 4, 5, ]>	/п==5:<2, 3, 4, 5, 1)	<3, 4, 5, 1, 2)
3	(3, 4, 5, 1, 2)	т = 5 : <3, 4, 5, 1, 2)	<4, 5, 1,2. 3)
4	<4, 5, 1, 2, 3)	ш = 5:(4, 5, 1, 2, 3)	<5, 1, 2, 3, 4)
5	<5, 1, 2, 3, 5)	/и = 5: (5, 1, 2, 3, 4)	(1, 2, 3, 4, 5)
		/п = 4:(1, 2, 3, 4)	<2, 3, 4, 1)
6	(2, 3, 4, 1, 5)	т = 5:(2, 3, 4, 1, 5)	(3, 4, 1, 5, 2)

Упражнение 11*. Понравилось ли вам изложение Ал-
горитма-1? Могли бы вы улучшить его разъяснение? Могли бы
вы доказать, что по Алгоритму-2 действительно получают все
«-перестановки?

Упражнение 12*. Не могли бы вы предложить алго-
ритм получения всех /г-перестановок, отличный от изложенных?
Уверены ли вы, что по этому алгоритму можно получить дей-
ствительно все перестановки?

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

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

Изобразим графически кружочком множество всех
возможных n-перестановок. Разобьем это множество
на п подмножеств, отнеся к одному подмножеству все
те перестановки, у которых на первом месте стоит
одно и тоже число i\. В первое подмножество попадут
все перестановки, у которых на первом месте рас-
положена 1 (Zi = l), во второе подмножество попа-
дут ап с i( = 2 и т. д.

Изобразим эти подмножества графически также
кружочками, внутри кружочков запишем значения iif
соединим стрелочками
кружочки со знаком мно-
жества всех возможных
//-перестановок, как это
показано на рис. 9.

В свою очередь каж-
дое из этих подмножеств
i1 можно еще разделить на
непересекающиеся под-

Рис. 9.	множества в зависимости

от того, какое число рас-
положено в перестановке на втором месте (рис. 10),
вновь образованные подмножества можно разбить на
части в зависимости от того, какое число расположено

на третьем месте и т. д. Процесс такого последова-
тельного разбиения множеств оборвется тогда, когда
мы дойдем до отдельных, единичных перестановок. На
рис. 11 представлен результат такого последователь-
ного разбиения множества всех перестановок чисел
1, 2, 3.

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

Каждая вершина в порфириане располагается, как
мы будем говорить, на некотором уровне. В нашем
примере вершины, соответствующие фиксации Ц, рас-
положены на первом уровне, фиксации i2 — на втором

Рис. 11.

уровне. Вершине, расположенной на k-м уровне, соот-
ветствуют отрезки длины k п-перестановок

&k	• • • >

Вершинам, расположенным на n-м уровне, соответ-
ствуют «полные» перестановки оп.

Построение вершин (k + 1)-го уровня порфириана,
исходя из некоторой вершины Л-го уровня, будем
в дальнейшем называть операцией ветвления, или
ветвлением.

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

*) По имени Порфирия, еще в III веке построившего это
свое «древо Порфирия» для наглядного отражения взаимосвязи
более широких понятий с узкими (см. Н. Я. Виленкин, По-
пулярная комбинаторика, М., «Наука», 1975).
которые удовлетворяют всем условиям задачи, за
исключением условия приводить к экстремуму функ-
ции-критерия).

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

Для нас важнее, что порфириан задает способ по-
строения (точнее, им определяется этот способ) —•
конструирования — всех возможных вариантов, удо-
влетворяющих условиям задачи (за исключением, еще
раз подчеркнем, условия приводить к экстремуму
функции-критерия).

В этом смысле каждая вершина порфириана (кро-
ме начальной) замыкает собой как бы некоторый
фиксированный фрагмент в представлении некоторого
возможного решения. Так отмеченная на рис. 10 зна-
ком + вершина соответствует, если проследить путь
от исходной вершины до отмеченной, последователь-
ному закреплению сначала ii = 2, затем f2 = 1- Та-
ким образом, будем считать, что отмеченная вершина
представляет собой фрагмент о2 = (2, 1) *).

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

§ 4. ГДЕ ДОСТАТОЧНО ПОСТРОИТЬ
ПОРФИРИАН

1. Путешествие бродячего торговца по плоскости
и на графе. В самой общей постановке в задаче бро-
дячего торговца (упр. 8 из § 1, п. 4) не предполагается,
что расстояния между городами измерены циркулем

*) В аспекте классификации это означает, что отмеченная
вершина представляет то подмножество вариантов, которое на-
чинается с чисел 2 и 1 (й — 2,	= 1), и (2, 1) есть класси-

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

Для такой постановки оказываются справедливы-
ми следующие утверждения.

Утверждение 1. Путь бродячего торговца
(в задаче на плоскости) не имеет самопересечений.

Назовем отрезок пути oh — (и, 1’2, ..., ih) разде-
ляющим, если

1)	он разбивает множество всех городов — точек

на плоскости, отличных от
/ь ife, на две части
такие, что

2)	не существует отрез-
ка, соединяющего точку
нз одной части множества
и точку из другой части
множества и не пересе-
кающего при этом ад.

Утверждение 2.
Оптимальный маршрут не
содержит разделяющих
отрезков 0h (k < п).

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

Рис. 12.
граница этого многоуголь*

Упражнение 13. Докажите эти утверждения.

Так для совокупности пунктов на плоскости, пред-
ставленных рис. 12, где внутри выпуклого многоуголь»
ника расположен всего один пункт, заведомо ясно,
что решением будет контур, близко подходящий к гра*
нице многоугольника (согласно утверждению 3). Чи-
сто визуально оценив, что в пункт 4 можно зайти из
пунктов.3, 5 или 6, а из других пунктов явно нецеле-
сообразно, легко получить множество возможных ре-
шений в таком случае — всего три варианта, пред-
ставленных порфирианом

©	на рис. 13:

(1, 2, 3, 4, 5, 6, 7, 8),

<1, 2, 3, 5, 4, 6, 7, 8),

<1,2, 3,5, 6, 4,7, 8)*).

(р	В задаче, подобной

Рис. 13.

приведенной, можно ска-
зать, что мы используем
схему построения порфи-
риана как в случае пои-
ска множества всех пере-
становок, однако в опера-
ции ветвления (§ 3, п. 4)
при переходе от к ц
проверяем прежде всего
допустимость такого пере-
хода— в нашем примере,
сообразуется ли путь бро-
дячего торговца Ok+i с
дорогами, нанесенными
на карту рис. 12.

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

В нашем примере на-
несение на карту ограни-
чивающих передвижение

«дорог» явилось резуль-

татом теоретического ис-
следования свойств оптимального решения. Во многих

практических постановках такие ограничивающие пе-

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

Фиксация возможных переходов на графе резко
сужает множество допустимых решений.

Рассмотрим поиск пути бродячего торговца на
графе, приведенном на рис. 14.

Операция ветвления при построении пор-
фириана в этом случае при переходе от оъ ==
= (и, f2, .. •, ik} к = (щ?., j) требует строить вер-
шины (k + 1)-го уровня (обозначая их /), если в гра-
фе рис. 14 имеется стрелочка, соединяющая ik с /.

В нашем примере мы тоже получим всего три воз-
можных решения:

(1,	2,	7,	8,	3,	4,	5,	6),

(1,	2,	7,	8,	3,	5,	6,	4),	(1)

(1,	2,	7,	8,	3,	6,	4,	5).

Упражнение 14.	Постройте	порфириан для примера

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

2	. Расстановка оборудования вдоль кругового кон-
вейера. Круговой конвейер движется в одном направ-
лении. Вдоль конвейера требуется расставить п стан-
ков. Обработанные на станке i детали передаются
на другой станок / в количестве а^ по конвейеру.

3	В. В. Шкурба	33
Р</ (оп) =

Требуется расставить станки в таком порядке, чтобы
минимизировать общее время передачи деталей от
станка к станку. Последнее означает, что если tij —
время передачи детали от станка i к станку /, то тре-
п п
буется минимизировать £ Z
z = 1 / = 1

Будем считать, что время пропорционально рас-
стоянию pij между станками вдоль конвейера, а это
расстояние полностью определяется тем, «как далеко»
отстоят i и / в перестановке ап.

Пусть k(i) и k(j)—соответственно места, кото-
рые занимают i и j в перестановке сгп. Конвейер дви-
жется вдоль станков в направлении от начала сгп
к концу. Это означает, что

— если k(i)<k(j),
п + k(j) — k (z), если k (z) > k (j).

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

(3)

Z—1

где рц(вп) определяется по формуле (2).

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

Зададимся вопросом: что произойдет, если мы в
перестановке ап поменяем местами два каких-либо
соседних станка i и /? Ясно, что все то, что направ-
лялось к первому станку i (вдоль перестановки), бу-
дет теперь идти на единицу времени дольше, за
исключением тех деталей, которые шли к i от вто-
рого станка /, для них время пути сократилось на
п — 2 единиц. Все, что шло к второму станку f рас-
сматриваемой пары, будет находиться в пути на еди-
ницу времени меньше, зато все, что шло от этого
станка к другим, будет находиться в пути на единицу
времени дольше. То, что шло к нему от соседнего
станка z, будет находиться в пути на п— 2 единиц
времени дольше (см. схему рис. 15).
Окончательный эффект от этой перестановки бу-
дет таким:

ф// — Zali— 1^аП +	— 2)+

/=/=/ i¥=i

+ X ait — X аи — ац (n — 2).	(4)

I ¥= i	I =£i

Очевидно, что если < 0, значит, выгодно по-

менять местами сосед-
ние станки i и / в пере-
становке оп — общее
.число «передач» при
этом уменьшится, если
фг; 0, значит, ЭТОГО
не следует делать.

Рассмотрим пример,
в котором исходные
данные представлены
табл. 6.

Для каждой пары
станков проведем вы-
числение того, в каком
порядке выгодно в пе-
рестановке On распола-
гать станки i и / при

условии, что они сосед-

ние.

Вычисления рекомендуем произвести с помощью
специальной расчетной таблицы (РТ) (табл. 7).

Запишем согласно формуле (4):

1)	все элементы строки I матрицы ctij из табл. 6
'(за исключением стоящего в столбце/) в графу II РТ;

Таблица 6

Матрица

X / 1  •X  1		2	3	4	5
1		30		100	40
2	10		20	20	50
3		40		20	30
4		10	100		
5	30	20	40	10	

Таблица 7

Расчетная
таблица (РТ)

+	—
I	II
X	У
2)	все элементы, стоящие в столбце с номером I
(за исключением стоящего в строке /), в графу I РТ;

3)	все элементы, стоящие в строке / (за исключе-
нием i-ro столбца), в графу I;

4)	все элементы, стоящие в столбце j (за исклю-
чением f-й строки), в графу II;

5)	(п — 2)ац в графу I;

6)	(п — 2)а^ в графу II.

Суммируем все числа, выписанные в графе I, и
полагаем х равным этой сумме; затем суммируем все
числа, выписанные в графе II, и полагаем у равным
этой сумме.

Если х > у (что соответствует cp4-j > 0), в таблице
Sij в клетке f-й строки, /-м столбце пишем +> в клет-
ке /-й строки, f-го столбца пишем —.

Если х у (что соответствует 0), в таблице
S[j в клетке f-й строки, /-м столбце пишем —, в клетке
j-й строки f-го столбца рисуем +•

Знак + в таблице 9 означает, что переход от i к /
при постронии порфириана допустим. Знак—, что не-
допустим.

Описанные правила вычислений иллюстрирует
табл. 8 для i — 1, j = 2.

заносим 4-.

Окончательный результат вычислений представлен
табл. 9,
Рис. 16 определяет граф, соответствующий табл. 9.

Этот граф задает допустимые

новки — как и в задаче
бродячего торговца как
бы «направляя» построе-
ние порфириана. Нетруд-
но убедиться, что оп —
= (1, 4, 3, 2, 5) есть един-
ственное решение нашей
задачи (рис. 17). При по-
строении порфириана, со-
ответствующего гр афу
рис. 16, поиск марш-
рута удобно начинать
с пункта и = 1, в этом

пути поиска переста-

случае h — 4 — единственное z2 в порфириане.

3. Загадка маленькой мушки. Маленькая мушка—•
дрозофила — любимый объект экспериментирования

генетиков: за одну неделю

можно пронаблюдать не-
сколько поколений мушки.

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

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

Перенумеруем наблю-

даемые признаки и соста-
вим таблицу результатов проведенных опытов, где бу-
дем отмечать на пересечении f-й строки и /-го столбца

1, если признаки i и j одновременно

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

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

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

= 1. Задача состоит в том, чтобы перестановкой i

(г. е. одновременно строк и столбцов) привести таб-
лицу к виду, соответствующему рис. 18,6, где закра-
шенные клетки некоторым образом «прилегают» к
главной диагонали таблицы.

Это свойство «прилегания» к главной диагонали
можно выразить и аналитически:



для всех

(6)

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

ИсследуехМ для начала некоторые свойства иско-
мого решения.
Назовем «хвостом» *) I для о все те /, которые
не ВОШЛИ В (5k И ДЛЯ которых бг} = 1.

Утверждение 4. Если (5k и Ok+\ = (оъ/) —
фрагменты искомого решения, то j входит во все (не-
пустые) «ХвОСТЫ» (5k.

Утверждение 5. Пусть для <5k выбраны два
каких-то «хвоста». Если каждый из выбранных «хво-
стов» содержит по одному j, не входящему в другой
«хвост», то полученный (5ь не может быть фрагментом
искомого решения.

Четвертое утверждение доказывается способом от
обратного. Пусть / не входит в «хвост» некоторого !,
принадлежащего и пусть

А •••> А •••>

— искомое решение, I — первый индекс из «хвоста» I.
ДЛЯ On

6;/==0, а вц = 1»

в то время как k(j)<Zk(l), что противоречит усло-
вию (6).

Докажем и пятое утверждение.

Действительно, пусть «хвост» it содержит д, но не
содержит /2, а «хвост» i2 не содержит /ь но содержит
/2. Тогда в перестановке

=(ай......А» • • •» А* • • •)>

т. е. при fe(/i)< k(j2),

6i?h =0, a bt,j, = 1,
иначе говоря, нарушается свойство (6), в перестанов-
ке же

CTn = (fffe’ •••» А» •••» А)’

т. е. при fe(/i) > fe(/2),
6/,ь = 0, а =

т. е. опять же нарушается свойство (6).

Так в нашем примере при О2 = (1, 2) «хвост» I
содержит / = 4, «хвост» 2 содержит / — 5. Если мы
образуем перестановку

=	2, 4, 5,

*) Не путайте с «перестановочным хвостом» (§ 3, п. 2).
в ней 624 — 0, а 625 = 1- Если мы образуем нереста
новку

=	2, 5, 4,

в ней 6)5 = 0, а би = 1.

Рис. 19.

Воспользуемся общей схемой построения порфи-
риана, с гой только разницей, что в операции «вет-
вления»

1)	при переходе от к сц+1 к можно присо-
единить только /, содержащееся во всех непустых
«хвостах» для 7, вошедших в вь', если все «хвосты»
пустые — любую / (не из конечно).

2)	(5h, удовлетворяющее условию утверждения 5,
отмечаем (крестиком) как недопустимое, дальней-
шему «ветвлению» неподлежащее.

Рис. 19 представляет общую схему алгоритма по-
строения порфириана в нашем примере, табл. 10—1
в несколько своеобразной (приспособленной для за-
писи) форме результат решения задачи.

Таблица 10

№		Реше- ние ?	№		Реше- ние ?
1	1, 2Х	__	22	6, 2, 9Х	—
2	1, 4, 9, 2Х	— '	23	6, 9, 2Х	—
3	1, 9, 2Х	—	24	7, 9, 1, 2 X	—
4	1, 9, 4, 2Х	—	25	7, 9, 1, 4, 2 X	—-
5	2, 1, X	—	26	7, 9, 2 X	—
6	2, 3, 5 X	—	27	7, 9, 4, 1, 2Х	——
7	2, 3, 9 X	—•	28	7, 9, 6, 2 X	—-
8	2, 5Х	—	29	8, 5, 2, 3, 9, IX	
9	2, 6, 9 X	—	30	8, 5, 2, 3, 8, 6,	
10	2, 9 X	—-		1, 4, 7	да
11	3, 2, 5 X	——	31	8, 5, 3, 2 X	—
12	3, 2, 9 X	—-	32	9, 1, 2Х	—.
13	3, 5Х	——	33	9, 1, 4, 2Х	—
14	3, 9Х	—	34	9, 2Х	—
15	4, 1, 9, 2 X	—	35	9, 4, 1, 2 X	—
16	4, 9, 1, 2Х	—-•	36	9, 6, 2 X	——
17	5, 2Х	—-	37	9, 7, 1, 2 X	—
18	5, ЗХ	—	38	9, 7, 1, 4, 2Х	—
19	5, 8, 2, 3, 9, IX	—	39	9, 7, 2 X	•—•
20	5, 8, 2, 3, 8,		40	9, 7, 4, 1, 2Х	—
	6, 1, 4, 7	да	41	9, 7, 6, 2 X	—
21	5, 8, 3, 2Х	—-			

Обратите внимание: вместо нескольких сот тысяч
перестановок (если пользоваться методом перебора)
в нашем методе оказалось достаточным построить
всего 41 фрагмент ofe.

Упражнение 15. Вы получили записку, где написано:
абвллсююя. Попробуйте расшифровать таинственную запись, по-
строив всевозможные осмысленные буквосочетания с помощью
порфириана («осмысленность» Gk может быть проверена по
словарю).
Упражнение 16. Найдите решение известной задачи
о волке, козе и капусте с помощью порфириана. Напомним за-
дачу. Требуется переправить через реку волка, козу и капусту,
в лодке же можно поместить только один предмет. Если оста-
вить козу с капустой, коза съест капусту, если оставить волка
с козой, волк съест козу.

Упражнение 17. Решите с помощью порфириана сле-
дующую задачу, где требуется восстановить стершиеся цифры:

*8*

О

§ 5. ПЕРЕСТАНОВОЧНЫЙ ПРИЕМ

1. Решение задачи директора. Хороший директор
интуитивно давно определил, в какой очередности сле-
дует принимать посетителей: прежде всего надо пере-
говорить с теми, кто пришел с короткими вопросами,
оставив «на потом» вопросы посложнее.

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

Предположим

< ==(/р .... i, i,.... in}

— оптимальное решение.

Напомним (§ 2, п. 2), что

П)

I -

Здесь ti(o)— время начала приема f-ro посетителя.

Поменяем порядок приема каких-то двух посети-
телей, принимаемых в о1п один непосредственно за
другим:

< = Ср .... Л i....«;>•

Можно записать, что

г («',) = А +/,«)+',«)

Л — общая неизменная часть F(o), так как времена
ожидания в приемной посетителей, имеющих номер,
отличный от i и /, не изменились в о^ по сравнению
с а1п.

Так как сН — по предположению оптимальное
решение, то

(»Э-	13)

Пусть т — момент окончания приема предыдущего
посетителя для /-го в /-го в а2п.

Тогда для а1п

i (»!)=’ +Л-

ДЛЯ

',«) = ’ ',(’Э = ’ + ТГ

Согласно (2) и (3)

Л + т + т + Л-^^ + ^ + ^ + Т1/
или

Ti<Th	(4)

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

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

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

Директор должен рассмотреть п вопросов; дли-
тельность рассмотрения /-го вопроса равна 7\; по во-
просу / к директору заходит аг- посетителей; допу-
стим, что нет посетителя, пришедшего одновременно
по двум вопросам.

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

=== Ab • • •,
с функцией-критерием

F (<rn) = Za^.	(5)

I

Если считать, что ссг- — не только целые числа, мы
получим задачу одного станка: установить очеред-
ность обработки п различных деталей, если время об-
работки f-й детали известно заранее; по детали I
за каждую минуту ожидания обработки взимается
«штраф» ОС;.

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

Пусть

— оптимальное решение, а

о2 =	/, /, .... i \

п \ 1>	’	»	> nJ

— вариант, отличающийся перестановкой только двух
каких-то соседних элементов в о1п.

И в этом случае, так как —по предположе-
нию оптимально,

Обозначив (о^) через т, как и в предыдущем
пункте, получим, что неравенство (6) эквивалентно

atr + a7 (т + Л-Xa/T + (т + Тj)
или

а так как все Л > 0, то

Последнее выражение и устанавливает свойство
оптимального решения, легко позволяющее это реше-
ние построить.
Утверждение (решающее правил о)'.

Перестановка «

тогда есть решение задачи одного станка по крите-
рию (5), когда

(8)

Прием исследования, который мы успешно при-
менили и в задаче директора, и в задаче одного стан-
ка, получил название перестановочного приема.

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

Упражнение 18. Введем в задаче одного станка кри-
терий

F(%)=E<₽<(.4)’	(9)

i

назовем его суммой штрафов, q)i(ti)—функция штрафа. Най-
дите решающее правило, если

Ф/ О = аг + р/,

где аг > 0, Pi > 0 заданы.

Упражнение 19*. Найдите решающее правило в задаче
одного станка, если чд (/) =	.

Упражнение 20. Заданы последовательности {од} и {pj,
i — 1, 2, ..., п, при этом

«1 < «2 < • • .

Покажите, что V а.р. максимальна, если р. Р9	р ,

X шя1 I Ь	L	&	Гь

i

и минимальна, если pj р2 ... Рп-

Упражнение 21. В задаче директора и в задаче одного
станка с самого начала мы молчаливо предполагали, что опти-
мальное решение плотно, т. е. что не делается перерывов между
приемами посетителей (в обработке деталей). Покажите, что
свойство быть плотным оптимального расписания в задаче од-
ного станка связано с монотонностью изменения (возра-
станием, например) функций ср» в (9).

Упражнение 22. Покажите, что если

Ф/ (0 =

<М'-ч)

рдт.-о

при

при
то оптимальное расписание, вообще говоря, не обязательно
плотно *).

Упражнение 23. В какой очередности следует выпол-
нять сегодня домашние задания, если оценить для каждого
предмета i влияние утомляемости через аг7г-, где — время на-
чала работы над t-м предметом.

3.	Задача двух станков. Еще одно эффективное
применение перестановочного приема — задача двух
станков.

В- этой задаче требуется за минимальное время
закончить обработку п деталей. Каждая деталь i об-
рабатывается сначала на первом станке (первая опе-
рация), длительность обработки равна ait затем на
втором станке (вторая операция), длительность об-
работки bi.

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

di = (1, 2, 3, 4, 5, 6). Важно отметить, что для за-
дачи двух станков вторая операция не может начать
выполняться, пока не закончилась предыдущая, а так-
же пока станок еще занят выполнением предыдущей
операции.

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

Для этого, прежде всего, надо установить, что в
оптимальном решении не может быть такого, чтобы
для двух каких-то деталей f, j на первом станке опе-
рации выполнялись в очередности j (Н — знак
«предшествует»), а на втором станке j H I. Такой слу-
чай демонстрируется несколько схематически на
рис. 21.

*) К такой постановке, например, сводится задача управ-
ления взлетами и посадками в аэропорту.
Рис. 21 помогает увидеть, что в графике, отобра-
женном на рисуцке, можно деталь i на первом станке
начать обрабатывать непосредственно после детали /,

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

Станок / • • • Е ™ 1 • • • F— 1 • • •

Станок 2	... F—Z—1	. pJ---1

Рис. 21.

а вместе с ним и срок окончания обработки всех де-
талей.

Итак, мы можем считать, что в оптймальном ре-
шении порядок обработки деталей на первом станке
и на втором один и тот же и задается перестановкой

(Уп = (/’1,	• • • >

Рассмотрим некоторый фрагмент графика вь =
= (и, is, • • •, ik}, k < п. Введем обозначения:	—

время окончания выполнения обработки деталей гра-
фика o/i первым станком, В(с^)—вторым станком.
Очевидно, что

A (fffe+i) = А (ак) + ai>	,|g

В (ак+х) = max [Л (<rft+i)> В (<тА)] + Ь(,

где or/t+i — {ak, 0 (рис. 22). Критерий оптимально
сти, следовательно, — минимизация В(оп).

Я(бк)

Станок 1 -------------------------—-j

Станок 2

Hoh)

Рис. 22.

Пусть теперь
q1 = (I . i i j . i \

«— некоторое решение. Построим

4=<ч> •••> /> г‘> •••> Q-

Обозначим

A (ст*) = т, В (ст*) = т + Д.

Тогда в

^(aL+i) = T + aP

В (4+1) = шах (т + т + Д) + Ьр
далее,
Л(4+2) = Т + а/ + а/’

В(4+2) —rnax('r+ai+a/'> тах(т+аг, т+Д) + Ь^+Ь{
или

в (4+г) = г + bj + max (а« + ар ai + 4 д + bt)- <п)

Аналогично для Кп

Л(4+2) = т + 4 + йг’

В (а^+2) = т + + max (а;. + а{, 0/ + Д + Ь,)-
Нетрудно сообразить, что если

(°1 + 2)	В (°£+2)’

(12)

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

Очевидно, неравенство (12) эквивалентно следую-
щему:

т + &z + max(az + ah аь + Ьь A + &z)<

т + bt + max (az + at, -\-bj, A + £/)
или

т +	+ bt + CLt + aj + max (— bh — а;, Д —• at — az)

<т + bi + bj + aj + at + max (— bj, — at, A — ai — Qj),
или

max (— bh — aj, A — at — aj)

<max(- bh — at, Д — at — aj), (13)
Неравенство (13) выполняется, если выполняется
max(— bt, —	max(— bj, —а^.	(14)

Неравенство (14) эквивалентно:

min(az, bj)	min(az, bt).	(15)

Итак, если соотношение (15) имеет место, то i Ч j
(i предшествует /) в оп. Нетрудно обнаружить, что
(15) выполняется, если

< a};

а)
б)
в)

az<&z,
az>&z,

ai < bh
а, > bf,
a{>bf,

a! > bt.

(16)

Последнее утверждение эквивалентно следующему.

Утверждение (решающее правило).
Пусть имеется k таких I, что Ь+

Тогда, если а и Ьц для I k и, кроме того,
an Яг,i+i При I < fe; ait > Ьц для I > k и, кроме
того, Ьц biu+\ при l> k, то

•••> ik+ii •••> ^п)	(17)

оптимально.
'Готовим Cnucoi<{aifiih
и п „клеток*для 7

нет

Решение б/
получено у

Рис. 23.
Согласно утверждению сначала выбираются де-
тали /, у которых» первая операция короче второй
операции Эти детали обрабатываются в порядке
возрастания сц. Остальные детали обрабатываются
в порядке убывания Ь{.

Алгоритм, представленный рис. 23, воплощает про-
цедурно приведенное решающее правило, а рис. 24
демонстрирует оптимальное решение (4, 2, 6, 3, 5, 1)
нашего примера.

4. Интервалы очередности. Если в задаче одного
станка фД/) = аг72, то применение перестановочного
приема приведет нас к сравнению двух функций от т:

2а.т7; + а/2 и 2а.т7\ + а.П, (18)
/ ь J ь	ь I	* i

Упражнение 24. Покажите это.

Сравнение (18) эквивалентно выяснению знака
следующего выражения:

2(а/7’/-а;7’/)т + а/П-а^.	(19)

а, аг

Если <XjTi — сцТj = 0, т. е. = т0

при — atT2 0 г -? /,
при ауТ? — а.Т2] > 0 jSi.

Если ajT{ — a,iTj =Д 0, то определим

VU ; JL ; -- JL :

/ а, а.

Теперь из (20) следует, что I пусть

при	i Ч /,	(21)

при т <	т?у	/ Ч /.	(22)

Там, где	т^. <10 или	У, 71.,	можно	заранее

установить согласно (21), (22) I Ч / или /Ч I. Если
попадает в интервал (О, У вопрос 4 Ч/ или
j Ч i решается по-другому.

Общая схема решения в таком случае — построе-
ние порфириана. В операции ветвления конкретно
определяется в зависимости от ?(оЦ, какие продолже-
ния Uk+2 = (ofe, i, j) согласно (21), (22) могут быть
разрешены, какие запрещены.

Упражнение 25. Покажите, что если а. с^,
то i —} / при т 0.

Упражнение 26. Воспользовавшись результатом упраж-
нения 25, покажите, что в примере, заданном табл. 12,

аЛ = <5, 4, 3, 2, 1)

— оптимальное решение при

ФЛ-0 =

Решим пример задачи одного станка, представлен-
ный табл. 13, где требуется минимизировать =
= Z (*)•

В табл. 13 операции перенумерованы в порядке
а.

убывания .

Таблица 12	Таблица 13

I	1  'i	1 2	3	4	5
Ui  Tl	1  3	2  3	2  2	3  2	3  1

i	1	2	3	4	5
at  Ti	6  3	1  1	2/9  1/3	1  2	1/6  1/2

Таблица 14

	1	2	3	4	5
1	—	Г1 A 12 ’ °°)	Г 1 A  [2 ’ 00)	[0, 00)	[0, °°)
2	[» 4)	—	[j> °°)	[0, 00)	[0, 00)
3	[°4)	[G)	—	[0, 00)	[0, 00)
4			—	—	Г 5	\  1 — , 00 I L4 ’	)
5	—	—	—		—
Вычислим по формуле (20) значения и резуль-
таты вычислений представим в табл. 14, где в клет-
ках (Z, /) указаны соответствующие интервалы оче-
редности: в этих интервалах [a, b) i /, если только
а т < Ь.

Так, для i = 1, j = 2 по формуле (20) имеем

о _	1 • З2 — 6• I2 _ 1

Т12“'	2 (1 • 3 — 6 • 1) — 2 '

Таким образом, 1	2 для всех	что и отме-

чено в табл. 14 в клетке (1, 2) интервалом очеред-
ности jy , oo) .

Отсюда следует, что 2	1 для всех т при — оо <

<т<у, что и отмечено в клетке (2, 1) интервалом
очередности £о, у) (так как в наших условиях т^О).

Для i— 1, / = 4 вычисления по формуле (20)
дают т$4 = — у < 0. Отсюда 1	4 при всех т 0,

так что 4 -? 1 не может ни при каком интересующем
нас т.

Построение порфириана приведет нас к трем воз-
можным решениям:

(2, 1,	3,	4,	5),

<3, 1,	2,	4,	5),	(23)

(3, 2,	1,	4,	5).

Упражнение 27. Постройте	порфириан, соответствую-

щий табл. 14.

Указание. Например, i\ = 4 недопустимо, так как в мо-
мент г = 0 i — 4 согласно табл. 14 не может предшествовать
никакому /. Сочетание аг = (1, 4) в момент т = 0 допустимо,
более того, представляется, что допустимо и аз = (1, 4, 5), так
как при т == t\ = 3, согласно табл. 14,4—? 5. Однако дальнейшее
исследование показывает, что аз = (1, 4, 5) недопустимо, так
как в момент т = Ц = 5 i = 5 не может предшествовать ни-
какому /.	;

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

^ = (2, 1, 3, 4, 5>, F(an) = 35.
§ 6. ПОСЛЕДОВАТЕЛЬНОЕ ОТСЕИВАНИЕ
ВАРИАНТОВ. ДОМИНИРОВАНИЕ

1. Отсеивание по правилам доминирования. В пре-
дыдущих разделах мы продемонстрировали, как вы-
явление отдельных свойств оптимального решения мо-
жет быть использовано для сокращения множества
рассматриваемых при построении порфириана вариан-
тов (вплоть до ликвидации вообще всякой вариант-
ности — § 5).

Характерным для методов § 5 было, что эти свой-
ства устанавливались заранее и проверялись с целью
(полного) «запрещения» ветвления в процессе по-
строения порфириана. В § 4 и § 5, п. 4, такое запре-
щение достигалось только частично.

Ниже мы рассмотрим другие способы последова-
тельного отсеивания вариантов при построении пор-
фириана путем выявления некоторых свойств реше-
ний в процессе ветвления.

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

Однако если при последовательном просмотре ва-
риантов оп в методе перебора надо было сравнивать
их по значению F(a?1), чтобы установить, какой из
них лучший (в конце перебора — оптимальный), для
фрагментов решений щ этого недостаточно.

Фрагменты сг{, и о~, по существу, как это уже
говорилось, в порфириане представляют собой множе-
ства вариантов ап, начинающихся с фиксированных
и а‘|. Сказать, что лучше о2 — это значит
установить, что среди всех продолжений oj, (т. е. эле-
ментов (тп, начинающихся с фиксированного ар най-
дется элемент а^ с F (пр, меньшим (для задач ми-
нимизации), чем F (ор любого продолжения а^.

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

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

Так в задаче коммивояжера в одно и то же со-
стояние приводят два пути и если

а)	они начинаются из одного и того же пункта,
т. е.

h (а1) = zi (О:

б)	они заканчиваются в одном и том же пункте,
т. е.

МО =4 (О

в)	эти пути проходят через одно и то же множе-
ство пунктов (только в разном порядке).

Последнее мы будем обозначать символом

—это множество пунктов Z, через которые про-
ходит crft (o/t, таким образом, — это некоторое упоря-
дочение M(ofe)). Такие варианты и о2 мы назо-
вем сравнимыми.

Так, пути а’—(2, 1, 3, 5, 4) и о^ = (2, 5, 3, 1, 4)
приводят в одинаковые состояния, пути о| = (2, 1, 3,
4, 5) и <т2 = (2, 3, 1, 5, 4) —в разные.

В дальнейшем (упражнение 28) станет ясно, что в некото-
рых случаях варианты о| = (2, 1, 3, 4) и (Г,—(2, 3, I, 5, 4)
также могут стать сравнимыми.

Пусть в задаче бродячего торговца
fe-i

Утверждение (правило доминирования).
В задаче бродячего торговца, если и a2k сравнимы
и при этом F (op F (а-p, то лучше <т| в том
смысле, что среди продолжений охк найдется ег)г, для
которого F (о'г) < F (о2') для всех а2, являющихся про-
должениями
Тем самым дальнейшие ветвления сг^ при построе-
нии порфириана явно нецелесообразны — в этом и со-
стоит последовательное отсеивание вариантов в про-
цессе построения порфириана согласно правилам до-
минирования.

Пусть

Й.... Й; ,1+,..

— лучшее решение среди продолжений =	...» /0,

«) + <₽«)>
где
п-1

<р(^)= S а.2.2 +а2.2.

7=6 + 1 ЧЧ + 1 Чг1\

Построим теперь решение

=	4, i'k+1.i'n),

продолжение == ^/},	которого совпадает с продолже-

пнем crk, т. е. /z — it для всех I > k.

Тогда нетрудно видеть, что так как F (о^) F (а|), то

р«)-жэ+^.)«^(<а

что и доказывает наше утверждение.

Упражнение 28. Показать, что лучше az, если

1\ (°Ц=»1 (ст?)- z‘fe (4) = li (а?);

М (оЦ содержит все AI (о,), a F (о-.) < F (о|).

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

Рис. 25 иллюстрирует схему решения задачи (уп-
рощенно изложенный алгоритм) бродячего торговца
методом отсеивания вариантов в процессе построения
порфириана согласно правилам доминирования.

Поясним некоторые блоки этой схемы.

В блоке «группировка сравнимых- Ok» собирают
вместе все с^, приводящие в одно и то же состояние.
Матрица atj

	1	2	3	4	5	6
1	—	7	4	7	8	2
2	6	—	7	6	4	8
3	5	8		6	7	5
4	8	7	6			7	6
5	7	4	8	6			8
6	2	7	7	7	7		

Нетрудно показать, что число таких различных
подмножеств — группировок — будет равно числу со-
четаний*) из п элементов по k — 2 элементов:

pk-2__	п\

~ (п - k + 2)! (k — 2)! ’

так как у всех сравнимых вариантов щ, фиксированы
начальный и конечный элементы i\ и

В блоке «отбора лучших производится перебор
всех элементов, попавших в одну и ту ж_е группировку
сравнимых вариантов, и в множестве Ph оставляется
по одному лучшему элементу из каждой такой груп-
пировки. Ветвление не попавших в Pk вариантов вь
в дальнейшем запрещается.

В блоке «операция ветвления» происходит после-
довательный просмотр всех k-ro уровня, не запре-
щенных для ветвления, от каждого такого вь (из Ph),

*) Напомним, что сочетанием из п элементов по k назы-
вается число всех различных подмножеств, состоящих из k эле-
ментов, взятых из фиксированного множества, состоящего из
п элементов.
производится построение всевозможных ал+i =’
е= i) — как и при построении порфириана

Процесс решения приведенного в табл. 15 при-
мера по схеме, представленной на рис. 25, воспроиз-

Рис. 25. Схема решения задачи бродячего торговца последова-
тельным отсеиванием вариантов.

1. Подготовка матрицы к решению. 2. Ветвление	построение

множества Р2 всех о2. 3. &==2. 4. Операция ветвления; каждому из Afe
ставятся в соответствие всевозможные	/ не пРинаДлежит

М (Ofc)» тем самым образуется множество таких р 5. Группировка
сравнимых Cfc+r °тбор «лучших»	согласно правилам доминирова-
ния, создание	всех «перспективных» + 7.^ + 1 ==> k, 8. Проверка:

k > п? 9. Решение закончено: Рп — решение.

водится в табл. 16. В табл. 16, как и ранее, крести-
ком X отмечены «бесперспективные» согласно прави-
лам доминирования варианты, т. е. отсеиваемые (за-
прещаемые для ветвления) блоком «отбора лучших
вариантов». Плюс (+) отмечает «перспективные» ва-
рианты.

3.	Поиск «критического пути». Определение «кри-
тического пути» в сетевом графике (§ 1, п. 3) можно
также провести с помощью построения порфириана.

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

= h> • • •, 4),

если только любые две соседние работы в о/г соеди-
нены на сетевом графике стрелочками.

Для наглядности (образности) можно считать, что
работы ik в сетевом графике есть некоторые «города»,
и интерпретировать задачу поиска критического пути
на сетевом графике как требование определить самый
длинный путь, который может пройти турист, между
исходным пунктом (начально?! работой) и конечным
(заключительной работой).

Будем обозначать через F(o/?) общую длину пути
т. е.

Е т,-,

i

если путь проходит через i (в сетевом графике п —
продолжительность работы z, в нашей интерпрета-
ции— время пребывания туриста в пункте z); здесь
перемещениями между пунктами мы пренебрегаем

Табл п ц а 16

Этапы решения примера
(при равенстве / (<гЛ)
лучшим считается
первый вариант)

а2

	
<1, 2>	7
<1, 3)	4
<1, 4)	7
<1. 5)	8
<1. 6>	2

а3

а/г		°k	F(°k)
<1, 2, 3)	14	(1, 4, 5)	14
(1. 2, 4)	13	(1, 4, 6)	13
<1, 2, 5)	11	<1, 5, 2)	12
<1, 2, 6)	15	<1, 5, 3)	16
<1, 3, 2)	12	<1, 5, 4)	14
(1. 3, 4)	10	<1, 5, 6)	16
<1, 3, 5)	11	<1. 6, 2)	9
(1, 3, 6)	12	(1, 6, 3)	9
<1, 4, 2)	14	<1, 6, 4)	9
(1, 4, 3)	13	(1, 6, 5)	9
Таблица 16 (продолжение)

(У4 (группировка и отбор лучших — отмечены знаком +)

°k	F (°k)	?		p(°k)	?	°k		?
<1,2, 3,4)	20	X	<1,2, 6,4)	22	X	(1, 3,6,5)	19	X
<1,3,2,4)	18	+	(1,6, 2,4)	15	+	(1,6, 3,5)	16	+
(1,2, 3,5)	21	X	<1,2,6,5)	22	X	(1,4,5,2)	18	+
<1,3,2,5)	16	+	<1,6, 2,5)	13	+	(1,5, 4,2)	21	X
<1,2, 3,6)	19	+	<1,3,4,2)	17	+	(1,4, 5,3)	22	X
<1,3, 2,6)	20	X	(1,4,3,2)	21	X	(1,5, 4,3)	17	+
<1,2,4,3)	19	+	<1,3, 4,5)	17	+	(1,4, 5,6)	22	X
(1,4, 2,5)	21	X	<1,4, 3,5)	20	X	(1,5, 4,6)	20	+
(1,2, 4,5)	20	X	(1,3,4,6)	16	+	(1,4,6,2)	20	X
(1,4, 2,5)	18	+	(1,4,3,6)	18	X	(1,6, 4,2)	16	+
(1,2, 4,6)	19	+	(1,3, 5,2)	15	+	(1,4,6,3)	20	X
(1,4, 2,6)	22	X I	(1,5, 3,2)	24	X	(1,6, 4,3)	15	+
(1,2, 5,3)	17	+ 1	(1,3, 5,4)	17	+	<1.4, 6,5)	20	x
(1,5,2,3)	18	х I	<1,5,3,4)	22	X	(1,6,4,5)	16	+
(1,2, 5,4)	15	+	(1,3,5,6)	19	+ j	(1,5, 6,2)	23	x
(1,5,2,4)	18	X	| (1,5, 3,6) ll	21	X	(1,6, 5,2)	13	+
(1,2, 5,6)	19	+	(1,3, 6,2)	19	х	(1,5,6,3)	23	x
(1, 5, 2,6)	20	X	(1.6, 3,2)	17	+	<1,6, 5,3)	17	+
(1,2, 6,3)	22	X	(1,3, 6,4)	19	X	<1,5, 6,4)	28	X
(1,6, 2,3)	16	+	(1,6, 3,4)	15	+	(1,6, 5,4)	15	+
(1,2, 3, 6,5)  (1,6, 2, 3,5)  (1,6, 3, 2, 5)	(1,2, 3, 6, 4) (1, 6, 2, 3, 4) (1,6, 3, 2, 4)	СО ND О  СП ОП ND tO 00 СП	(1,3, 2,5, 4)  <1,2, 5, 3, 4)  (1,3, 5, 2,4)	(1,3, 2, 4,6)  (1,2, 4, 3,6) (1, 3,4, 2,6)	(1,3, 2, 4,5)  <1, 2, 4, 3,5) (1,3, 4, 2,5)	Q Rr
to ND ND — 00 CD	tO ND ND CO ND CD	ND ND ND CO О	ND ND ND  >— СД ND	ND ND ND СД 4^	ND ND ND — CD СИ	
_ +XX		x+x	+XX	+XX	XX+	+XX	•v
(1,2, 5, 6,4) XI, 6, 2, 5,4) (1, 6, 5, 2,4)	(1,2, 5, 6,3) (1,6, 2,5,3)  (1, 6, 5, 2,3)	(1,2,4, 6,5) (1, 6, 2, 4,5) (1,6, 4, 2,5)	(1,2, 4,6, 3) (1, 6, 2, 4,3) (1,6, 4, 2,3)	(1,4, 5, 2,6) (1,4, 2, 5,6)  (1, 2, 5, 4,6)	(1,4, 5, 2,3)  (1,4, 2, 5,3)  (1,2, 5, 4,3)	Q Sr
►— i— ND ООО	ND ND ND 0 — 0	to to to О ND CD	26 2!  23	ND ND ND  CO CD CD	ND ND ND CO CD CH	'o'
X (1,6, 5, 4,2) X (1,5, 4, 6,2) + (1,6, 4, 5,2)	+XX  CD CD GO  СИ 00 СП  CO СИ О		+XX  CD CD CO  Jb, CO 4^ co CD ^CnjGi'CH	XXI,3, 4,6,2) 4- +l, 6, 3, 4,2) X +11, 6, 4, 3,2,  II	+XX  СЛ co co  4^ СП hU  CO 4*. СП  CD CD CD	X (1,3, 4, 5,2) X 1(1,3, 5, 4,2) + (1,5, 4, 3,2)	Q ar
22  27  20	СП ND О	23  22  22	О ND co	ND CO СП	ND ND ND О 4^ —	Dj  'o'
+XX	X+X	x+x	X+X	+XX	XX+	•v

Таблица 16 {продолжение)


%	F (%)	?	°k	P(°k)	?
<1, 5, 4, 3, 6, 2)	29	X	(1,3, 2, 4, 6, 5)	31	X
(1,6, 3, 4, 5, 2)	26	+	(1,6, 2, 3, 4, 5)	29	X
(1,6, 3, 5, 4, 2)	29	X	(1,6, 2, 4, 3, 5)	28	X
(1, 6, 4, 5, 3, 2)	29	X	(1, 6, 3, 4, 2, 5)	26	+
(1,2, 5, 4, 6,3)	30	X	(1,3, 4, 2, 5, 6)	29	X
(1,6, 4, 2, 5,3)	28	X	(1,3, 5, 2, 4, 6)	27	+
(1,6, 5, 2, 4, 3)	25	+	(1,2, 5, 4, 3, 6)	28	X
(1, 6, 4, 5, 2, 3)	27	X	(1,3, 4, 5, 2, 6)	29	X
(1,3, 5, 2, 6,4) (1,6, 3, 2, 5, 4) (1,6, 5, 2, 3, 4) (1, 6, 3, 5, 2, 4)	30  27  26  26	X X + X			

(а5,

°k

F(°k)

?

(1,6, 3, 4, 5, 2, 1)
(1,6, 5, 2, 4, 3, 1)
(1,6, 5,2, 3, 4, 1)
(1,6, 3, 4, 2, 5, 1)
(1,3, 5, 2, 4, 6, 1)

32

30

34

33

29

(турист считает только то время, в течение которого
он знакомится с достопримечательностями).

Два пути Ok и сч, приводящие в один и тот же
пункт (в наших обозначениях ik(ok) = ii(oi)), срав-
нимы. Правило доминирования естественно вытекает
из того, что можно говорить о критическом пути для
каждого пункта, так как можно построить для
каждого пункта самый длинный путь, соединяющий
его с начальным пунктом. Заметим, что каждая часть
критического пути есть критический путь в том смыс-
ле, что лежащие на критическом пути пункты i и j
также соединены «наиболее длинно» и не существует
другого пути, соединяющего эти пункты «более дол-
гим образом»*).

Упражнение 29. Докажите это.

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

Это утверждение следует из предыдущего заме-
чания.

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

Соединим предварительно с исходным пунктом те
вершины сетевого графика, в которые приводят пути
от исходного пункта и только от него. Отметим эти
пункты /, т. е. наведем дополнительно на графике
пути, соединяющие их с исходным пунктом, и проста-
вим возле них метку r(j)—пройденное расстояние,
длину пути.

Пусть теперь отмечены какие-то пункты. Найдем
пункт I, в который приводят стрелки только из отме-
ченных метками г(/) пунктов /. Построим теперь

г(/) + т(0	(1)

и выберем среди них максимальное. Тот пункт /, ко-
торый дает максимальное (1), соединим с пунктом z,
т. е. наведем стрелочку, соединяющую j с i, и отме-
тим i величиной (1).

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

Упражнение 30. Найдите критический путь на сетевом
графике рис. 5 по описанному алгоритму.

*) Во многих задачах поиска «наилучших» траекторий путь
обладает, как говорят, свойствам оптимальности
(удовлетворяет принципу оптимальности). В таких слу-
чаях правила доминирования находятся легко и естественно.
§ 7. ПОСЛЕДОВАТЕЛЬНОЕ ОТСЕИВАНИЕ
ВАРИАНТОВ. ВЕТВИ И ГРАНИЦЫ

1. Схема «ветвей и границ». Представьте, что
каким-то образом нам удается оценить для каждого
о/г, что среди продолжений Oft можно получить
в лучшем случае о^ с некоторым F(dfy. Такую оцен-
ку F (crQ мы будем называть «обещанием» и обо-
значать через fe(oft).

Рис. 26. Схема поиска критического пути методом расстановки
меток.

1. Подготовка информации о графе и значениях г (г). 2. «Отмечаем» исход-
ную вершину: полагаем для нее г (/)=0, ставим «метку» i=0. 3. Ищем
вершину /, в которую приходят стрелки только от отмеченных вершин.

4, Вычисляем для этой вершины г(/) + Ту, находим iQ, для которого эта
сумма максимальна, отмечаем вершину /: полагаем для нее г (/)=/• (/ ) +
+ и ставим «метку» iQ, б. Проверяем: конечная вершина отмечена?
6. Решение найдено, остается по меткам восстановить критический путь.

Оставим пока в стороне вопрос, как получено та-
кое «обещание» (насколько можно ему верить).
Рассмотрим следующую идею отсеивания вариан-
тов в процессе построения порфириана.

Будем подвергать ветвлению Gk с наиболее удоб-
ным (т. е. наибольшим в случае задачи максимиза-
ции, наименьшим при минимизации) «обещанием».

Это правило ветвления будем использовать до тех
пор, пока не получим некоторое (окончательное) о^.
Вычислим F (о*о). Теперь можно отсеять (запре-
тить ветвление) все те од, для которых b
^F(g^—- в задаче минимизации (или b (с^)
в задаче минимизации).

Поиск Gn (улучшающих по описанной схеме
продолжается до тех пор, пока не останется ни одного
Gk, который бы «предлагал лучшее» (чем у уже най-
денных оп) «обещание».

Таким образом, в схеме «ветвей и границ» (после
умения строить порфириан) главное — это умение
оценивать b(ofe) для каждого

Очевидно, при этом для каждого Gk необходимо
сформулировать некоторую вспомогательную
задачу (вычисления Ь(о&)) и, конечно, более про-
стую, чем исходная (поиск наилучшего оп среди про-
должений Gk)-

Чаще всего вспомогательная задача формулирует-
ся как некоторое (естественное) упрощение ис-
ходной задачи.

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

2. Задача о рюкзаке. Собираясь в поход, вы хотели
бы взять п предметов, каждый предмет i весом и
«ценностью» в походе сг*.

Вы можете взять предметов с собой по весу не бо-
лее А (предполагается, что	иначе не

i
было бы задачи!). Какие предметы взять?

Решение задачи можно представить последователь-
ностью

О'Л = (%1, Х2,
где

( 1, если мы берем с собой предмет

‘	(, 0, если не берем.
Таким образом, нам надо найти такую последова-
тельность оп, что на ней

и достигается максимум

i

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

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

В исходной задаче о рюкзаке может принимать
значения только 0 и 1. Отказ от этого предположения
и приводит к вспомогательной, легко решаемой за-
даче:

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

Решение задачи в случае сыпучих грузов очевидно.
с.

Найдем величину —, и пусть грузы упорядочены по
ai

с,
убыванию у-, т. е. по величине «ценности» единицы

веса груза,

ai а2 "" ’ ’ * ап *

Тогда необходимо брать груз, начиная с первого,
до тех пор, пока мы не «засыпем» рюкзак до веса Л.
Иными словами:

а)	если tzi Л, то х\ = 1;
k

б)	если	то Xk = 1;

Xе»!
k	й + 1

в)	если X ai < А У ai > А, то

k
A-i,ai
Xk+i = —„‘-1...- И Xi = Q, i>k + l.

ak+i
Рис. 27. Схема решения задачи о рюкзаке.

Множество возможных решений обозначим через а0. Положим рекорд f*
равным нулю. (Смысл рекордаf устанавливается в блоке 8.) Формулируем
вспомогательную задачу (0 < X/ < 1), находим • А 2. Проверяем,
есть ли в построенном фрагменте «висячие» вершины О& с А > f. («Ви-

сячие»—те, у которых нет еще «продолжений», они же—мажоранты пор-
фириана.) 3. Операция выбора: выбираем «висячую» вершину с A

и при этом с наибольшим А Можно выбирать с А > f
(при этом с наибольшим fe) —это определит более эффективный ' «чел-
ночный» вариант схемы решения. 4. Операция ветвления: добавляем
к порфириану две вершины: ст, , ,==/о,, 0\ и о, , »/а., 1\, вычер-
к 4-1	\ к /	«4-1 \« /

киваем

СТй + 1

если ею определяется решение,

недопустимое

неравен-

ством	< Д (нарушает это условие). 5. Проверяем, + j и

не являются ли они полными решениями, т. е. ^4-1=®п? 6. Вычисляем

для о и Q величину fe 4- 1=гг. 7. Проверяем, найдется ли f (а^ + 1) > f-
Rr 1 fv 1

8. Полагаем новое f равным максимальному из таких f (an) — это и есть
рекорд. Фиксируем —рекордный план. 9. Для найденных и ।
(если они допустимы) формулируем вспомогатёльную задачу (0 < xt-Ь
с учетом уже найденных Хр i <&4-1, уже определенных + находим
А (%4-1)« 10. Решение закончено: рекордный план и есть оптимальный ва-
риант загрузки рюкзака, а рекорд f—значение функции-критерия для этого
плана.
Решение задачи

п

с (а„) = £ С(Х{

1=1

в случае «сыпучих» грузов и может служить искомой
оценкой — «обещанием» — значений F(on), ибо, как

нетрудно видеть,

F(a„)<C(a„).

Построение порфириана достигается очевидным
способом. Множество всех возможных оп разбивается
на два: первое с Х] — 0, второе с хг — 1. Множества
второго уровня 02 есть разбиения полученных мно-
жеств в зависимости от того, х2 = 0 или х2 = 1 и т. п.

Рис. 28. К решению задачи о рюкзаке.

Возле вершины записаны с (х)/с' (х), где сг (х) вычисляется по формуле (1),
но xt- выбираются из х только целые.

На рис. 27 представлена общая схема решения
задачи о рюкзаке.

Блок «формулирование вспомогательной задачи
для оЛ» означает следующее,
68
Обозначим для бь
k	k

Д (о&) :== Х С (о&) 2-< Сi{X

Вспомогательная задача для о^. Найти
Xi (Z > k) такие, что 0 хг- =С 1,

п

X aiXi^A — Л(о*),

i = k +1

и при этом
п

С(х) = S cXi + C(ak)	(1)

i^k+1

достигает максимума.

Рис. 28 представляет конечный результат построе-
ния порфириана по схеме решения задачи о рюкзаке
(см. рис. 27) и данных, представленных табл. 17.

3. Решение задачи бродячего торговца методом
ветвей и границ. Отметим: вспомогательная задача в
методе ветвей и границ формулируется путем от-
каза от некоторых ограничений или ос-
лаблением каких-то ограничений (в за-
даче о рюкзаке — отказом от дискретности х^.

В задаче бродячего торговца вспомогательная за-
дача может быть сформулирована так.

Таблица 17

К задаче о рюкзаке

i	1	2	3	4	5
at	5	4	5	4	4
	15	12	10	8	8
Cj ai	3	3	2	2	2

Рассмотрим несколько другое, чем ранее, пред-
ставление решения задачи бродячего торговца.

Пусть

= S

1, если из пункта I торговец
направляется в пункт /,

О, если нет.
Такое представление упрощает представление спо«
соба вычисления значения функции-критерия для ре-
шения

=	(2)

где aij — расстояние между пунктами i и / (заданное
матрицей — таблицей расстояний (§ 2, п. 4)).

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

Вот от этого-то ограничения мы теперь и отка-
жемся.

Нетрудно видеть, что в оговоренном случае задача
превращается в задачу о назначениях, где требуется
найти максимум (2) при условиях, что для любого I
найдется такое /, что Хц = 1; для любого / найдется
такое I, что Хц = 1. Это можно записать и иначе:

и	п

^^хЦ — ^л^хЦ~^	(3)

для любых i и /.

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

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

Так что, прежде всего, желательно научиться ре-
шать задачу о назначениях.

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

Для этого выполним сначала следующие преоб-
разования.

Утверждение 1. Решение задачи о назначе-
ниях не изменится, если каждое а^ в i-й строке
уменьшить на одно и то же число Дг*.

Утверждение 2. Решение задачи о назначе-
ниях не изменится, если каждое ац в j-м столбце
уменьшить на одно и то же число bj.

Упражнение 31. Доказать эти утверждения, воспользо-
вавшись формулировкой: показать, что значение функции-крите-
рия при этом уменьшается на + X $/•
t i
Вычтем теперь из матрицы а/; величины Аг и б;
так, чтобы в каждой строке и каждом столбце обра-
зовались так называемые нулевые элементы или про-
сто «нули».

Для этого возьмем Z-ю строку, найдем в ней макси-
мальное *) и положим Аг- равным этому макси-
мальному dij. Затем во вновь образованной матрице
dij =	— А/ возьмем /-й столбец и положим б, рав-

ным максимальному элементу в столбце. Перей-
дем теперь к матрице	— Ai — fy. В ней в

каждых строке и столбце теперь есть a*; = 0 — это и
есть «нулевые элементы», а все ац 0.

Легко видеть, что, например, табл. 2 (§ 2, п. 4)
преобразуется к такому виду (табл. 18) Ai = 5, Аг =
= А3 = 4, di = б3 = 0, б2 = —1.

Таблица 18

	Оля	Зоя	Лиля
Саша	0	0	—2
Андрей*	—2	-1	0
Сережа	0	—2	— 1

Будем строить теперь порфириан для задачи о на-
значениях (рис. 29 воспроизводит решение для усло-
вий, заданных табл. 18). Множество возможных ре-
шений сначала разобьем (в зависимости от того, чему
равно i‘i). Возле каждой вершины ii запишем соответ-
ствующее b(i{)= аи — Ветвление будем про-
изводить для той вершины для которой b(ik) мак-
симально.

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

а)	среди них нет ни одного оп;

б)	получены оп, но найдется некоторый Ой(й < n)f
что &(ой) > F(on) для всех оп;

в)	нет такого Ой.

• *) Мы рассматривали задачу о назначениях как задачу м а к-
симизации, так ее и решаем, хотя, как вспомогатель-
ная для задачи бродячего торговца, задача о назначениях есть
задача минимизации — там выбирается минимальное ац.
В случае в) решение закончено и максимальное
F(on) есть экстремум, в случаях а) и б) ветвлению
подвергается элемент с максимальным

= &(ofe)+ aik+ik+{. (Если он не один, то са-
мый «нижний» и самый левый среди «нижних».)

Рис. 29. Решение задачи о назначениях методом «ветвей и границ»

Упражнение 32. Постройте блок-схему описанного ал-
горитма.

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

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

Нетрудно показать справедливость утверждений 1
и 2 и для задачи бродячего торговца. Табл. 19 пред-
ставляет матрицу табл. 15 (§ 6, п. 2) после пре-

*) Это замечание открывает путь (еще не пройденный) по-
строения целой иерархии задач дискретной оптимизации, сво-
дящихся к общим оценкам типа
образований вида ац = ац — А2— б2, где Л] = Д6 = 2,
A? = А5 Аз = 5, А4 = 6, 6] :=: ^2 == бз 65 =зи
— б6 = 0, ё4 = 1.

Таблица 19

Матрица

i  i	1	2	з	4	5	6
1		5	2	4	6	0
2	2	——-£Е=	3	1	0	4
3	0	3	=======	0	2	0
4	2	1	0					1	0
5	3	0	4	1		4
6	0	5	5	4	5	=====

Будем строить решение задачи бродячего торговца
как порфириан, производя ветвления и отсеивание
вариантов по следующим правилам. По-прежнему
считаем, что путешествие начинается с пункта 1, так
что все множество возможных вариантов отожде-
ствляется с множеством, где oi = (l); примем, что
6(oi) = 0.

Пусть построена какая-то часть порфириана, все
конечные вершины которого, как известно, можно
отождествить с некоторыми маршрутами Gk =»
= (zi, 1*2, ..., th) — множество этих маршрутов обо-
значим через Р,

Ветвление некоторого вь означает построение
о/г+1 = (пл,/), где / не входит в ЛЦо^), и соответству-
ющих вершин в порфириане. При этом
Выбор Oft для ветвления или останов решения опре-
деляется следующим.

Если в Р содержатся <уп, вычислим для них
ф (an) = Ь (<т„) + aZnl.

Нетрудно понять, что вследствие выполненного
преобразования матрицы aZj в матрицу ац, длина
Е(оп) полного пути (1,11, in, 1), т. е. (<rn, 1) бу-
дет равна

Е (<т„) = Ф (о„) + е,
где e = S&z + 2X.
i i

Назовем наименьшее в нашем случае <р(ап) рекор-
дом на Р, а соответствующее <тп— рекордным. Если

f(0)=24+5=2g

Рис. 30. Решение задачи бродячего торговца методом «ветвей и
границ».

рекорд <р(о„) не больше всех 6(ол) на Р, то, как легко
видеть, соответствующее рекордное оп представляет
оптимальное решение задачи бродячего торговца.

Если это не так, ветвлению подлежит щ, с мини-
мальным 6(ол), а если таких ал несколько, то край-
нее левое из них в построенной части порфириана.

Рис. 30 иллюстрирует решение задачи бродячего
торговца, представленной табл. 15, по схеме ветвей и
границ.
Упражнение 33. Число ветвлений можно сократить, если
лучше «прогнозировать» значение F(cn), вычисляя &(о,/1). Для
этого, получив ад, например, можно вычеркнуть все строки /,
где i берется из M(cta-i), а оставшуюся матрицу преобразовать
согласно утверждениям 1 и 2. Продумайте это предложение и
постарайтесь использовать при решении задачи.

Упражнение 34. Постройте блок-схему описанного алго-
ритма и проверьте по ней правильность решения примера. От
чего зависит количество ветвлений в решении? Оцените предло-
жение: пока не получено оп, ветвлению подвергается Ол с макси-
мальным k, а среди таких — уже с максимальным в 6(сгл).

Упражнение 35. Продумайте следующее практическое
замечание: «лучше вычислять b(ak) проще, чем точнее».

3. Обобщенная задача о рюкзаке. Мы будем назы-
вать обобщенной задачей о рюкзаке следующую по-
становку.

Максимизировать

S СЛ-

i

при условиях

j=l,
xz==0 или 1.

(4)

(5)

Отличие ее от «обычной» задачи о рюкзаке в том,
что решение должно удовлетворять больше чем од-
ному ограничению (не одному, а т — (4)). Как и обыч-
ная задача о рюкзаке, обобщенная также может быть
интерпретирована как задача теории расписаний (см,
п. 2).

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

Заметим, что если, как и в задаче о рюкзаке
(п. 2), отказаться от дискретности хг-, т. е. считать,
что «грузы сыпучи», 0 Xi 1, то мы придем к фор-
мулировке вспомогательной задачи как задачи л и-
нейного программирования, которую можно
решить стандартными методами.

Однако можно еще более упростить решение.
Вспомните наши рекомендации по формулированию
вспомогательной задачи (п. 1). Самое грубое «есте-
ственное» упрощение — это отбросить т—1 неравен-
ство и свести задачу к обычной задаче о рюкзаке. Но
какое неравенство оставить? Первое? А если второе?
А что будет, если мы решим т задач о рюкзаке, по
одной для каждого неравенства? Наверное, мы полу-
чим т «обещаний» по числу ограничений (4), каждое
из которых как бы отражает значение «своего» не-
равенства при построении решения.

Рассмотрим пример.

Максимизировать

S ^i^i
при условиях

Xf = O или 1.

Значения cit сц А, В представлены табл. 20.

Таблица 20

i	1	2	3	4	5	
Ci	15	12	12	15	10	
at	3	3	4	5	5	4=13
Ci/di	5	4	3	3	2	
bi	5	4	3	3	2	B=11
Ci/bt	3	3	4	5	5	

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

Максимизировать

Cj (х) =
при условиях
С помощью табл. 20 легко найти это решение: Xj
= х2 = х3 = 1, Xi = 3/5, %5 — 0, Ci (х) = 48.

Сформулируем вторую вспомогательную задачу,
выбрав второе ограничение:

Максимизировать

С2 (х) = 2^ CiXi

при условиях

£ biXi^B,

0=Ог < 1.

Легко получить, что Сг(х) = 46, Xi = 0, х% = 3/4,
Хз = Х4 = Х5 =2 1.

А8!\46=46

OVtOMO^O

42М2=42(О

Рис. 31. Решение обобщенной задачи
вей и границ» (крестиком отмечен

37К37=3?{0}

ниями вариант).

о рюкзаке по схеме «вет-
недопустимый ограниче-





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

F (<*») < С\ (х) и F (а„) < С2 (х).

Рис. 31 иллюстрирует ход решения в рассматри-
ваемом примере по схеме «ветвей и границ». Возле
каждой вершины выписан символ вида х А у =
= z(z(ofe)), где х — обещание по первому ограниче-
нию, у — по второму, z (или г(о/г))—наименьшее
из х и у. Ветвлению подвергается с наибольшим
z(aA).

Упражнение 36. Прокомментируйте еще раз упр. 35. Со-
ставьте блок-схему алгоритма решения обобщенной задачи о
рюкзаке.
§8. ЗАДАЧА ТРЕХ СТАНКОВ

1.	Постановка задачи и свойства оптимального
решения. Задача трех станков формулируется анало-
гично задаче двух станков (§ 5, п. 3). Дано п деталей,
каждая из которых обрабатывается последовательно
на трех станках. Продолжительность первой операции
на первом станке для Лй детали обозначим через ah
второй операции на втором станке bit третьей на
третьем станке сг*. Как и прежде, предполагаем, что
операция не может начаться, пока не закончилась
предыдущая.

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

Упражнение 37. Докажите это самостоятельно.

Таким образом, каждое расписание на трех стан-
ках может быть представлено как гг-перестановка

==	^*2> • • • >	• • • > Ci)*

Обозначим через A(ok) время окончания обработки k
первых операций в оп на первом станке, через
—время окончания обработки первых k опера-
ций в ап на втором станке, через C(oft)—время окон-
чания обработки первых k операций в оп на третьем
станке.

Тогда по условиям задачи (считая, что в момент
/ = 0 все станки готовы к выполнению работ)

A(oi) = aiit

В (oi) = а^ + Ьц = A (di) +	(1)

С (oi) = aZl + bix + ci{ = В (oi) +

и, далее,

Л(о/г) = Л(о/г-1) + aik,

В (о*) = max (A (afe), В (о^-О) + bik, (2)
С Ы = max (В (о*), С (ofe-i)) + cik.

Утверждение 1 (правила доминиро-
вания). Фрагменты решений и сравнимы,
если, как ив (§ 6, п. 1),
М(а')-М(Я=).

Вариант лучше варианта а£, если одновре-
менно

В	СМ)<С«)-	<3)

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

В частности, если

ai = 4, bi = lt Ci = 39

ТО В 02= О’» /’)

В(о2) = 9,
а в 02= (j, 1}

В(<т2) = 8,

а} = 3, bj — 2, Cj = l,

С(ст2) = 10,

С(ст2) = 11.

Заметим, что относительно пары (i, j) не очень-то
просто ответить на вопрос, I предшествует j в опти-
мальном решении, или j предшествует i, даже если

— довольно нетривиальна здесь зависимость от
и C(ak); довольно внимательно следует проводить вы-
кладки, если воспользоваться перестановочным прие-
мом.

Упражнение 38. Можете ли вы построить нечто анало-
гичное «интервалам очередности» для задачи трех станков?
В этом случае вы дадите ответ на вопрос, сформулированный в
предыдущем замечании.

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

Так, пусть детали перенумерованы таким образом,
что оказалось

<



Ь]


и, кроме того,
< bt < ct

для всех 1 I п.

(5)

Утверждение 2. При условиях (4) и (5)
=	2, .... п)

есть оптимальная очередность обработки деталей.

Доказательство этого утверждения очевидно: во-
первых, согласно (4) и (§ 5, п. 3) обработка деталей
на двух станках — втором и третьем — оптимальна,
и, кроме того, В (о0) = ctt для такой очередности ми-
нимальна (#i) из всех возможных.

Рассмотрим другой случай.

Пусть
mina/^maxft/.	(6)

/	i

Тогда, применяя перестановочный прием, несложно
показать, что i предшествует / в оптимальном реше-
нии как только

min (at + bif bj + cj) < min (az + bh bt + cz). (7)

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

Упражнение 39. Исходя из задачи двух станков, могли
бы вы сформулировать и решить другие частные случаи задачи
трех станков? Например, рассмотрев условие, аналогичное (7),
по второму и третьему станку.

2.	Решение методом последовательного отсеивания
вариантов. Рассмотрим пример, заданный табл. 21.

Таблица 21

Воспользуемся утверждением 1 (правилом домини-
рования) и построим блок-схему метода отсеивания
вариантов для задачи трех станков (рис. 32).

Следующий графический прием упрощает вычис-
ления.
Рис. 32. Схема решения задачи трех станков последовательным
отсеиванием вариантов.

1. Подготовка таблицы Ь-, к решению. 2. Построение	вычи-

сление A (Oi), В ((Ji), С ((Ji). Образуем Pi — множество (список) всех с .

3. fe=l. 4. Операция ветвления: каждая из порождает	/>,

уде / не входит в М (о&). 5. Группировка сравнимых <г^^.р вычисление
^(afe+l) и^(а^+1)« 6. Отбор «лучших» согласно пр авила м д о-
Минирования, образование Pfi^.l из «лучших» (Т^^р 7. Н1= Р.

8. /г=п? 9. Рп — решение.

Рис. 33. К вычислению А (ок), В (<rft), С (<тА) в задаче трех станков.
Решение задачи трех станков последовательным
отсеиванием вариантов

О’!

01	АВС	01	АВС	01	АВС
<1)  (2)	1, з, 6  3, 5, 8	1	2, 4, 6  2, 6, 8	<5)  <6)	1, 6, 9  3, 5, 2

(Т2

02	АВС	?	02	АВС	?	02	АВС	?
<1, 2)	4, 6, 9	+	<2, 3)	5,7, 10	+	<3, 6)	5, 7,8	+
<2, 1)	4, 7, 11	—	<3, 2)	5, 7, 10	—	<6, 3)	5, 7,9	
(1, 3)	3, 5, 8	+	<2, 4)	5, 9, 11	>—	<4, 5)	3, И, 14	—
<3, 1)	3, 6, 9	—	<4, 2)	5, 8, 11	+	<5, 4)	3, 10, 12	4-
<1. 4)	з, 7, 9	+	<2, 5)	4, 10, 13	—	<4, 6)	5, 8,9	+
<4, 1)	3, 8, 11	—	<5, 2)	4, 8, 12	+	(6, 4)	5, 9, 11	—
<1, 5)	2, 8, 11	+	(2, 6)	6, 8,9	+	<5, 6)	4, 8,9	+
<5, 1)	2, 8, 12	—	<6, 2)	6,8, И	—	<6, 5)	4, 10, 13	—
<1, 6)	4, 8, 10	—.	<3, 4)	3, 9, 12	+	<3, 5)	4, 3, 7	+
<6, 1>	4, 8, 10	+	<4, 3)	3, 8, 11	+	(5, 3)	3, 8, 11	—*

<Тз

03	АВС	? 1	1	03	АВС	?	03	АВС	?
<1,2,3)	6,8,11	+	<1,2,6)	7, 9, 10	+	<1,3,6)	6,8,9	+
<1,3,2)	6, 8, 11	—-.	<1,6,2)	7, 9, 12	—	<1,6,3)	6, 8, 10	—
<2, 3, 1)	6, 9, 13		<6,2, 1)	7, Ю, 14	—	<3,6,1)	6, 9, 12	—
<1,2, 4)	6, 10, 12	—	<1,3, 4)	5, 9, 11	+	<1,4, 5)	4, 12, 15	—,
<1,4,2)	6, 9, 12	+	<1,4, 3)	5, 9, 11	—	<1,5, 4)	4, 12, 14	+
<4, 2, 1)	6, 10, 14		<3, 4, 1)	5, 10, 13	—	<5, 4, 1)	4, 12, 15	—
<1,2,5)	5, 11, 14	— > 1	<1,3, 5)	4, 10, 13	+	<1,4,6)	6, 9, 10	+
<1,5,2)	5, 10, 14	+	<1, 5, 3)	4, 10, 13	—	<1,6, 4)	6, 10, 12	—
<5, 2, 1)	5, 10, 15	—	<5, 3, 1)	4, 10, 14	—	<4, 6, 1)	6, 10, 13	


0}	АВС		0.	АВС	?	Оз	АВС	1 ?
(1,5, 6)	5, 10, 12	+ 1	(4, 2, 5)	6, 13, 16		(3, 4, 6)	7, 10, 11	+
(1,6, 5)	5, И, 14	11	(5, 2, 4)	6, 12, 14	+ |	(3, 6, 4)	7, И, 13	—
(5, 6, 1)	5, 10, 13		(5, 4, 2)	6, 12, 15		(4, 6, 3)	7, 10, 12	—
(2,3, 4)	7, 11, 13	_||	(4, 2, 6)	8, 10, 12	+	(3, 5, 6)	6, 11, 13	—
(4, 2, 3)	7, 10, 13	+	(6, 2, 4)	8, 12, 14	—	(3, 6, 5)	6, 12, 15	—
(3, 4, 2)	7, 10, 13		(4, 6, 2)	8, 10, 13		(5, 6, 3)	6, 10, 12	+
(2, 3, 5)	6, 12, 15		(5, 2, 6)	7, 10, 13	+	(5, 4, 6)	6, 12, 13	+
(5, 2, 3)	6, 10, 14	+ ||	(6, 2, 5)	7, 13, 16	—	(4, 6, 5)	6, 13, 16	—
(5, 3, 2)	6, 10, 14		(5, 6, 2)	7, 10, 13	—	(5, 6, 4)	6, 12, 14	—
(2, 3, 6)  (6, 2, 3)  (3, 6, 2)	8, 10, 11  8, 10, 13  8, 10, 13	+ 1 1	(3, 4, 5) (5, 3, 4) (5,4,3)	5, 13, 16  5, 12, 14  5, 12, 14	1 +1			



О4	АВС	?	|	0-4	АВС	?	1 at	АВС	?
(1,2, 3, 4)	8, 12, 14	—	(1, 5, 2, 6)	8, 12, 15	+11(4, 2, 3, 5)		8, 13, 16	+
(1. 4, 2, 3)	8, 11, 14	+	(1, 2, 6, 5)	8, 14, 17		(5, 2, 3, 4)	8, 14, 16	—
(1,3, 4, 2)	8, 11, 14	—	(1, 5,6,2)	8, 12, 15		(5, 2, 4, 3)	8, 14, 16	—
(4, 2, 3, 1)	8, 12, 16	—	(5, 2, 6, 1)	8, 12, 16		(5, 3, 4, 2)	8, 14, 17	—
(1,2, 3, 5)	7, 13, 16	—	(1,3,4, 5)	6, 14, 17	—	!!(4, 2, 3, 6)	10, 12, 14	+
(1,5, 2, 3)	7, 12, 16	+	(1,3, 5, 4)	6, 14, 16	+ (2, 3, 6, 4)		10, 14, 16	—
(1, 3, 5, 2)	7, 12, 16	—	(1,5, 4, 3)	6, 14, 16	—	(4, 2, 6, 3)	10, 14, 16	—
(5,2, 3, 1)	7, 12, 17	—	(5, 3, 4, 1)	6, 14, 17		(3, 4, 6,2)	10, 12, 15	—
(1,2, 3, 6)	9, 11, 12	+	(1,3, 4,6)	° ’1, 12  8, 12, 14	+11(5, 2, 3, 6)		9, 12, 15	+
(1,2, 6, 3)	9, 11, 13	—	(1,3, 6, 4)		—	(2, 3, 6, 5)	9, 15, 18	—
(1,3, 6, 2)	9, 11, 14	—	(1,4, 6,3)	8, 11, 13	—	1(5, 2, 6, 3)	9, 12, 15	—
(2, 3,6, 1)	9, 12, 15	—	(3,4, 6, 1)	8, 12, 15		(3, 5, 6,2)	9, 13, 16	—
(1,4, 2, 5)	7, 14, 17	—	(1,3, 5,6)	7, 12, 14	+	1(5, 2, 4, 6)	9, 14, 15	+
(1,5, 2, 4)	7, 14, 16	+	(1,3, 6,5)	7, 13, 16	—	(4, 2, 6, 5)	9, 15, 18	—
(1,5, 4, 2)	7, 14, 17	—	(1,5, 6,3)	7, 12, 14	—	(5, 2, 6, 4)	9, 14, 16	—
(5,2, 4, 1)	7, 14, 18	—	(3, 5, 6, 1)	7, 13, 16	—	(5, 4, 6, 2)	9, 14, 17	—
(1,4, 2,6)	9, 11, 13		(1,5, 4, 6)	7, 14, 15	+	1(5, 3, 4, 6) (3, 4, 6, 5)	8, 14, 15	
(1, 2, 6, 4)	9, 13, 15	+j	(1,4, 6,5)	7, 14, 17	—		8, 15, 18	—
(1,4, 6, 2)	9, И, 14		(1,5, 6, 4)	7, 14, 16	—	(5, 6, 3, 4)	8, 14, 16	—
(4, 2, 6, 1)	9, 12, 15	-;;(5,4,6, о		7, 14, 17	—	|(5, 4, 6, 3)	8, 14, 15	—


05	АВС	?	05	АВС	?
<1, 4, 2, 3, 6)	9, 16, 19			<1, 5, 2, 4, 6)	10, 16, 18	+
(1, 5, 2, 3, 4)	9, 16, 18	+	(1, 4, 2, 6, 5)	10, 16, 19	—
(1, 5, 2, 4, 3)	9, 16, 18	—	<1, 5, 2, 6, 4)	10, 16, 18	—
<1, 3, 5, 4, 2)	9, 16, 19	—	<1, 5, 4, 6, 2)	10, 16, 19	—
(4, 2, 3, 5, 1)	9, 15, 19	+	(5, 2, 4, 6, 1)	10, 16, 19	
<1, 4, 2, 3, 6)	11, 13, 15	+	(1, 3, 5, 4, 6)	9, 16, 17	+
<1, 2, 3, 6, 4)	И, 15, 17	—	(1, 3, 4, 6, 5)	9, 16, 19	—
(1, 4, 2, 6, 3)	И, 13, 15	—	<1, 3, 5, 6, 4)	9, 16, 18	—
(1, 3, 4, 6, 2)	11, 13, 16	—	<1, 5, 4, 6, 3)	9, 16, 18	—
<4, 2, 3, 6, 1)	11, 14, 17	—	<5, 3, 4, 6, 1)	9, 16, 19	—
(1, 5, 2, 3, 6)	10, 14, 17	+	<4, 2, 3, 5, 6)	11, 15, 17	+
(1, 2, 3, 6, 5)	10, 16, 18	—	(4, 2, 3, 6, 5)	11, 17, 20	—
<1, 5, 2, 6, 3)	10, 14, 17	—	<5, 2, 3, 6, 4)	11, 16, 18	—
<1, 3, 5, 6, 2)	10, 14, 17	—	/5, 2, 4, 6, 3)	И, 16, 17	—
(5, 2, 3, 6, 1)	10, 14, 18	— 1	(5, 3, 4, 6, 2)	11, 16, 19	—

06	АВС	?
<1, 5, 2, 3, 4, 6)	12, 18, 20	+
• <4, 2, 3, 5, 1, 6)	12, 17, 20	—
<1, 4, 2, 3, 6, 5)	12, 18, 21	—
(1, 5, 2, 3, 6, 4)	12, 18, 20	—
(1, 5, 2, 4, 6, 3)	12, 18, 20	—-
(1, 3, 5, 4, 6, 2)	12, 18, 20	—
(4, 2, 3, 6, 1, 5)	12, 17, 20	

Замечание. Мы ищем только одно оптимальное решение
Пусть мы построили

а3==(1, 2, 3).

Поставим в соответствие о3 ее с е т е в о й гра-
фик и проведем вычисления B($k} и С(ой) как кри-

Рис. 34. Схема решения задачи трех станков методом ветвей и
границ.

1. Подготовка информации к решению. 2. Формируем вспомогательные
задачи, вычисляем Д (<70)— для всего множества возможных решений.
3. Строим всевозможные (м)» Д° = оо. 4. Существует такой, что
Д (Oj) <	5. Выберем с наименьшим Д (о^). Применяем опера-
цию ветвления к нашему	т. е. образуем +	уУ / не при-

надлежит (сг^). 6. l=k. 7. & + 1=/г? 8. Формируем для вновь построен-
ных вспомогательные задачи, вычисляем Д фиксируем Д (#&),
Максимальное из всех Д (о^) при фиксированном (7&. 9. Вычисляем F
для вновь образованных $п, наименьшее F (а/г) и ofl— запоминаем. 10. Ре-
шение закончено, F° — экстремум.

тических путей в этом сетевом графике. Рис. 33
подробно иллюстрирует способ вычислений, впрочем,
совершенно идентичный формулам (2). Решение при-
мера представлено таблицей 20.

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

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

Так, если принимать во внимание только времена
обработки на третьем станке для всех /, не попавших
в М (о/О — обычно это делается тогда, когда вообще
X ct У at и У Ct X at *), ые обращая внимания
i

на значения ctj и bj (т. е. считая, что = bj = 0), то
мы получим совершенно тривиально решаемую вспо-
могательную задачу (рис. 34):

Д (а^) = С	Q-	(8)

м Ь)

Знак	здесь следует понимать как то, что

сумма длительностей Cj считается только по тем /, ко-
торые не входят в М (о.О.

Совершенно аналогично можно считать сущест-
венным только длительности вторых операций —
особенно если У bt Е с, Е i J &1’

i	i	i	i

В этом случае прогноз-обещание можно вычислять
по формуле

А (стА) = В (а*) + _Е Ь, 4- _min cz. (9)

Здесь знак М((Уь) означает, что минимум выби-
рается среди Cj, не входящих в М (о^).

Упражнение 40. Поясните, откуда в формуле (9) взя*
лось последнее слагаемое.

Точно так же, считая существенными только дли-
тельности первых операций — особенно если 2^ >2^

*) Знак > читается «значительно больше»,
Л--15,19,17,1!Ш^----© 15,21,19,22,22

Q 15,19,20,20,20

Д \7~''''~© 15,20, 18,21,21

/ (?) 15,21,19,21,21
y\15J9,17,19,19

16,21,17,22,22

\ \	15,19,20,19,20

\	(9)15,19,20,20,20

(3)15,20,17,20,20

3)^20,17,20,20

16,22,17,23,23

\	1^)15,20,19,21,21

(g) 15,20,18,20,20

q\ 15,20,17,20,20

\	~"~© 18,22,17,22,22

T) 15,20,19,20,20

7) 15,20:17^21,21

6) 19,23,20,23,23

15,20,20,20,20



Piic. 35. К решению задачи трех станков методом ветвей и гра-
ниц (пример).
и У at > 2 Ci — можно получить прогноз
i	i

A (<jfe) = А (о?*) + _£	+ min (b{ + С/).	(10)

М (^) М (°k)

Прогнозы, вычисляемые по формулам (10), (9),
(8), есть прогнозы со вспомогательными задачами
как бы задачами одного станка. Обозначим их соот-
ветственно через Дь Д2, Дз-

Прогнозы-обещания можно подсчитывать, если в
качестве вспомогательной решать (§ 5, п. 3) задачи
двух станков. Так, пренебрегая длительностями
выполнения первых операций, можно для всех /, не
входящих в Л4(од), решить задачу двух станков и
вычислить оптимальное значение функции-критерия
для такой вспомогательной задачи. Обозначим его

Тогда Д4(щ0 = В (ofe) + Cj, oh) мо-
жет быть принята за прогноз значений F(on) при
данном Ofc.

Так, пусть в нашем примере oh — (1,2,3).

Согласно рис. 33 В(ок) = 8. Упорядочим оптималь-
но оставшиеся детали 4, 5, 6, считая, что они обраба-
тываются только на втором и третьем станках. Со-
гласно алгоритму, приведенному на рис. 23, эти де-
тали надо обрабатывать в порядке убывания длитель-
ности третьих операций (так как они короче вторых
у всех деталей), т. е. в последовательности (5,4,6).

Легко подсчитать по правилам расчета В(ок)
задачи двух станков (формула (10) § 5, п. 3), что в
нашем случае Bz(bj, q, = 12, т. е. Д4(о/1) = 20
(Д4 в этом случае совпадает с Д2).

На рис. 35 приведено решение примера, заданного
табл. 21, по схеме «ветвей и границ» на рисунке ря-
дом с Gk выписаны Дь Д2, Дз, Д4, Д5, где Д5 — макси-
мум среди Дь Д2, Дз, Д4.

У п р а ж н е н и е 41. Докажите утверждение 2, воспользо-
вавшись схемой «ветвей и границ».

§ 9.	И БОЛЕЕ СЛОЖНЫЕ ЗАДАЧИ

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

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

Действительно, пусть заданы детали, последова-
тельно обрабатываемые на четырех станках, а^ ci9
di — продолжительности обработки детали i на 1, 2,
3, 4 станке.

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

Для первого случая надо в точности повторить до-
казательство § 5, п. 3, для второго случая в это дока-
зательство надо внести очевидное изменение: деталь i
на последнем станке можно поставить непосредствен-
но перед деталью /, «подвинув» вправо деталь /
(вместе с операциями, занимавшими место перед i
и /) на отрезок, равный продолжительности выполне-
ния последней операции детали i. Такое преобразо-
вание допустимо, значение функции-критерия не из-
менится (оно может только уменьшиться, если теперь
попытаться сделать график «плотным» (см. упр. 2,
§ 5, п. 2)).

Как показывает простой пример, представленный
на рис. 36, последовательность выполнения первых
двух и последних двух операций в оптимальном реше-
нии может не совпадать между собой. На рисунке
представлены все возможные сочетания очередности
выполнения двух деталей (tii — bi =	= di = 3,

a2 — d2 = 3, b2 = c2 = 1), допустимые с учетом ска*
занного в предыдущем абзаце.

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

Станок 7

2

Станон 2

1

2.

Станок 3_

Станок 4 _
~'O

a)

Рис. 36, Пример расписаний в задаче четырех станков.

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

Упражнение 41*. Вы могли бы построить схему «вет-
рей и границ» для задачи четырех станков? Могли бы с по-
мощью схемы «ветвей и границ» показать, что решение
/1 2 3 4\

) оптимально для условий задачи, заданных табл. 23.

’ ’3’	Таблица 23

дачи; в них, например, число станков tn велико, и по-
следовательность прохождения (в процессе обработ-
ки) станков деталями не одинакова.

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

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

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

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

В эвристических схемах обычно указывается неко-
торый приоритет, в соответствии с которым и реко-
мендуется отбирать операции к назначению из спи-
ска готовых к выполнению операций. Таким
образом, приоритет — это как бы решающее пра-
вило (§ 5, п. 2), относительно которого мы, правда,
в точности не знаем, ведет ли оно к оптимуму. У нас
просто есть какие-то основания быть уверенными
в этом.

Так, например, решающее правило кратчайшей
операции в задаче директора приводит, как мы знаем,
к оптимальному решению (§ 5, п. 1). Правило крат-
чайшей операции поэтому очень часто используется
в эвристических методах решения произвольных задач
составления расписаний: приоритет дается менее дли-
тельной операции.

Схема ветвления с приоритетами имеет очень про-
стую структуру. На каждом вычисляется некоторое
<p(o/i) — его приоритет. Ветвлению подлежит то Ok, У
которого приоритет наибольший (в правиле кратчай-
шей операции ср (ст^) =	.

3.	Случайные ветвления и т. д. Схема ветвления с
приоритетами благодаря своей простоте сплошь и ря-
дом применяется для решения практических задач
календарного планирования. Предложены десятки
простых и сложных приоритетов, каждый из которых
хорош, вообще говоря, для своего класса задач,—
мы видели, что в частном случае задачи трех станков
(§ 8, п. 1) приоритет приводит к оптимальному
решению.
Предложены и используются на практике и так
называемые случайные ветвления, когда сц выбирает-
ся для ветвления случайно, в соответствии с неко-
торой заданной или вычисляемой вероятностью
выбора Такие схемы ветвления являются есте-
ственным применением идей случайного поиска реше-
ний к отысканию оптимума.

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

Разработаны методы, в которых вероятность полу-
чения оптимума увеличивается по мере решения за-
дачи— такие методы получили название методов адап-
тации.

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

Перспективны, по-видимому, попытки продвинуть-
ся вперед в решении задач составления расписаний
созданием специализированных технических средств
(гибридных ЭВМ, многопроцессорных устройств и т. п.).
ЗАКЛЮЧЕНИЕ

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

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

В теории расписаний еще много вопросов не ре-
шенных и даже не поставленных, всякое продвижение
в этом направлении полезно. Даже решение вопросов,
сформулированных в упражнениях, может заинтере-
совать журнал «Квант», куда я и рекомендую посы-
лать особенно понравившиеся вам самим решения,
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ

Алгоритм 7

Блок-схема 7

«Ветвей и границ» схема 64

Ветвление 29

Вершина 10

Вращение 26

Временная диаграмма 10

Граф 18

Дерево 28

Доминирование 54

Задача 7

Задача бродячего торговца 18

-----«на графе 31

------ — плоскости 31

<	— двух станков 46

диагонализации 37

—	директора 15

•	— дискретной оптимизации 23

—	на доказательство 7

*	построение 7

*	— о назначениях 17

*	рюкзаке обобщенная 73

одного станка 43

очередности 16

—	поиска экстремальной переста-
новки 16

расстановки оборудования 33

—	трех станков 77—86

—	четырех станков 88—91

Задачи эквивалентные 17

Интервал очередности 51

Исходные данные 6

Конструирования вариантов схема 27

Критический путь 10

Метка 63

Метод адаптации 93

•— меток 63

— переобразований 20

Множество возможных решений 20

•— допустимых вариантбв 20

Неизвестное 6

Нулевой элемент 71

Обещание 65

Обрывающий элемент, число 23

Операция ветвления 29

Оптимальное решение 20

Оптимизируемая функция 16

Перестановка 13

Перестановочный прием 45

— хвост 23

Плотное расписание 45

Порфириан 28

Последовательное отсеивание вари-
антов 56

Правила доминирования 78

— кратчайшей операции 43

Приоритет 92

Работа 10

Расписание 5

Рекорд 74

Рекордное вп

Рекуррентные соотношения 13

Решающее правило 43

------ в задаче директора 43

--------- двух станков 49

--------- одного станка 45

Решения в общем виде 7

—• формульные 7

Сетевой график 10

Случайное ветвление 93

Сочетание 57

Сумма штрафов 45

Схема «ветвей и границ» 64

— последовательного конструирова-
ния вариантов 27

*— — отсеивания 56

Уровень дерева 28

Условия задачи 6

Факториал 13

Формула Стирлинга 14

Функция-критерий 16

штрафа 45

Хвост 39

— перестановочный 23

Экспертные оценки 19

Экстремальный элемент 20
Виктор Васильевич Шкурба

ЗАДАЧА ТРЕХ СТАНКОВ

М., 1976 г., 96 стр. с илл.

Редактор Н. П. Рябенькая
Техн, редактор Е. В. Морозова
Корректор Г. В. Подвольская

Сдано в набор 28.04.76. Подписано к печати 19.10.76.
Бумага 84X108732 тип. № 1. Физ. печ. л. 3. Усл. печ. л. 5,04.

Уч.-изд. л. 4,46. Тираж 75 000 экз. Т-15192,
Цена книги 15 коп. Заказ № 147

Издательство «Наука»

Главная редакция физико-математической литературы
117071, Москва, В-71, Ленинский проспект, 15

Ордена Трудового Красного Знамени
Ленинградская типография № 2
имени Евгении Соколовой Союзполиграфпрома
при Государственном комитете Совета Министров СССР
по делам издательств, полиграфии и книжной торговли

198052, Ленинград, Л-52, Измайловский проспект, 29
Школьные учебники (((Р

SHEBA.SPB.&U/SHKOLA