Виктор Васильевич Шкурба

Задача трёх станков

*** 1976 ***

DjVu

От нас: 500 радиоспектаклей (и учебники)
на SD‑карте 64(128)GB — ГДЕ?..

Baшa помощь проекту:
занести копеечку — КУДА?..

В этой маленькой книжке рассказывается о задачах, простых и вместе с тем сравнительно новых для математики, о методах их решений, основанных на совсем элементарных идеях. Большая часть приводимых задач относится к теории расписаний — разделу математики, имеющему большое прикладное значение.       Книжка ориентирована в основном на учеников старших классов, для которых она может стать своеобразным введением в дискретную математику и теорию оптимальных решений, с одной стороны, в широкую область прикладной деятельности — составление оптимальных календарных планов — с другой. Книга может стать полезной и для всех тех, кто сталкивается в своей работе с решением различных задач упорядочения и другими дискретными оптимизационными задачами.       ОГЛАВЛЕНИЕ       Предисловие       § 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 г.).       Звездочкой в тексте отмечены упражнения, представляющие скорее «вопросы для размышления», чем традиционные задачи. Символ (§ б, п. 3) в тексте означает ссылку на § 6, пункт 3. Формулы нумеруются внутри параграфа, так что символ (2, § 6) означает ссылку на формулу (2) в § 6. Ссылка (2) означает обращение к формуле (2) того же параграфа.       Я буду благодарен читателям, которые пришлют замечания.       Хочу также выразить свою признательность В. С. Танаеву и всем тем, кто способствовал выходу книги в свет.       В. В. Шкурба             § 1. РАСПИСАНИЯ       1. Календарное планирование. Понятие о расписании уже сложилось у каждого школьника: занятия в классе проводятся по расписанию, не последнюю роль в успеваемости играет режим дня школьника, а в приготовление домашних заданий иногда существенные коррективы вносит футбольный календарь или программа телевидения. По существу, вся человеческая деятельность планируется во времени: без этого невозможна координированная работа предприятий и производственных участков, по графику идет строительство крупной электростанции и детской спортивной площадки, строго во времени расписаны исследования, проводимые космонавтами на борту орбитальной станции, даже время выхода из дома на работу и рабочие, и служащие, и ученые, и инженеры определяют, сообразуясь с графиком работы городского транспорта или движения пригородных поездов.       Расписание — это синоним организованности, одно из важнейших средств эффективного выполнения любого рода деятельности, любого рода работ. Чем лучше составлено расписание, тем выше производительность труда, тем меньше затраты (особенно «нервной энергии»), связанные с той или иной деятельностью, тем лучше и сами достигаемые результаты, и условия их достижения.       Так что расписания надо уметь составлять, да и притом возможно лучше — оптимально, как говорят математики.       Расписания — и часто неплохие — люди научились составлять давно, но вот составление оптимального расписания стало возможным с тех пор, как к этой работе были привлечены новые аккуратные и быстрые «информационные помощники» человека — электронные       вычислительные машины. Правда, помощь ЭВМ требуется в составлении расписаний для сравнительно сложных комплексов работ, оптимальные расписания во многих простых случаях можно составить и, как говорят, вручную. Однако для этого прежде всего надо поставить задачу составления оптимального расписания как математическую задачу, и хотя это сделать довольно просто, но на первый взгляд все же неочевидно.       2. Формулировки математических задач. Начиная с первого класса, школьники привыкают думать о задаче как о требовании найти некоторое неизвестное поначалу число, удовлетворяющее условиям задачи.       Выраженные словами условия задачи необходимо перевести на язык алгебраических формул, связывающих обозначаемое обычно через х неизвестное с исходными данными некоторой «цепочкой отношений» (уравнений, преобразований). Пролбжив такую «цепочку отношений» от исходных данных к неизвестному, не так уж трудно вычислить и само неизвестное.       Пример (из задачника по алгебре для 8-го класса).       Поезд шел со скоростью 36 км/час, затем на перегоне, равном 1,5 км, поезд шел равноускоренно с ускорением 0,1 м/сек2. Найти время, в течение которого поезд прошел перегон.       Сообразительный ученик быстро свяжет слово «равноускоренно» с формулой       и обнаружит, что S, vq, а заданы условиями задачи, составит уравнение       и найдет t, правильно применяя формулу решения квадратного уравнения к нашему случаю       Решения, подобные (1), где представлен способ решения задачи (связывающая с неизвестным исходные данные, замененные буквами, «цепочка отношений») без выполнения самих вычислений, называют решениями в общем виде, формульными решениями.       Решение некоторой задачи в общем виде, составленное в форме четкой инструкции, точно следуя которой получают однозначный правильный ответ в каждом конкретном случае (при подстановке исходных данных), называют алгоритмом *).       В школьной математике, где приходится решать сравнительно простые задачи, не предъявляется сколько-нибудь серьезных требований к строгости, единообразию и обозримости представления способа решения задачи — разговор заходит разве что об аккуратности записи отыскания конечного результата.       В данной брошюре алгоритмы решения задач записываются с помощью так называемых блок-схем, получивших широкое распространение в наши дни (образец блок-схемы представлен на рис. 1, на рис. 2 представлены стандартные блоки для записи некоторых типичных правил в алгоритме).       В так называемых «задачах на доказательство» —¦ обычно некоторого тождества — требовалось проложить «цепочки отношений», связывающие элементарными преобразованиями левые и правые части равенств. Это те же задачи, но как бы с известными ответами.       В задачах на построение в геометрии требовалось найти некоторый неизвестный графический объект определенной условиями задачи конфигурации (окружность, треугольник, угол и т. п.).       Здесь объект поиска — не число, более того, здесь обычно еще требуется выполнить построение с помощью некоторых инструментов — например, одного циркуля или одной линейки**).       *) См., например, «Популярные лекции по математике» (ПЛМ), выпуск 26.       **) Такие задачи подробно рассмотрены в выпусках 25 и 29 ПЛМ.       KOHEЦ ФPAГMEHTA