Дискретно-непрерывная математика (стр. 50 )

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

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

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

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

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

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

Таблица 5.2

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

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

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

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

Упражнение 9. Улучшите разъяснение Алгоритма-1. Докажите, что по Алгоритму-2 действительно получают все п-перестановки?

Упражнение 10. Предложить алгоритм получения всех n-перестановок, отличный от изложенных? Докажите, что по алгоритму-2 возможно получить действительно все перестановки (а возможно – нет).

Упражнение 11. Докажите утверждения 1, 2, 3 п. 5.16.

Упражнение 12. Постройте порфириан для примера рис. 5.25 и покажите, что только варианты (5.52) удовлетворяют условиям задачи, отмечая крестиком как недопустимый вариант с повторным попаданием в город.

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

Упражнение 14. Найдите решение известной задачи о волке, козе и капусте с помощью порфириана. Напомним задачу. Нужно переправить через реку волка, козу и капусту, в лодке же можно поместить только один предмет. Если оставить козу с капустой, коза съест капусту, если оставить волка с козой, волк съест козу.

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

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

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

(*)

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

где αi > 0, βi > 0 заданы.

Упражнение 17. Найдите решающее правило в задаче одного станка, если .

Упражнение 18. Заданы последовательности {αi} и {βi}, i = 1, 2.....п, при этом

Покажите, что

максимальна, если

и минимальна, если

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

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

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

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

Упражнение 22. Покажите, что если αi≥αj Тi≤Тj, то i j при τ ≥0.

Упражнение 23. Воспользовавшись результатом упражнения 22, покажите, что в примере, заданном табл. 5.12,

σп = 5, 4, 3, 2, 1

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

Таблица 5.12

Упражнение 24. Постройте порфириан, соотетствующий табл. 5.14.

Указание. Например, i1 = 4 недопустимо, так как в момент τ = 0 i = 4 согласно табл. 5.14 не может предшествовать никакому j. Сочетание σ2 = 1, 4 в момент τ=0 допустимо, более того, представляется, что допустимо и σ3 = 1, 4, 5, так как при τ = = 3, согласно табл. 5.14, 4 5. Однако дальнейшее исследование показывает, что σ3=1, 4, 5 недопустимо, так как в момент τ= =5 i=5 не может предшествовать никакому j.

Микромодуль 19

Методы отсеивания вариантов

5.18. Последовательное отсеивание вариантов. Доминирование.

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

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

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

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

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

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