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

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

Рис. 5.46. К решению задачи трех станков методом ветвей и границ (пример).

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

Как показывает простой пример, представленный на рис. 5.47, последовательность выполнения первых двух и последних двух операций в оптимальном решении может не совпадать между собой. На рисунке представлены все возможные соединения очередности выполнения двух деталей (a1 = b1 = с1 = d1 = 3, а2 = d2 = 3, b2 = c2 = 1), допустимые с учетом сказанного в предыдущем абзаце.

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

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

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

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

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

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

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

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

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

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

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

Схема ветвления с приоритетами имеет очень простую структуру. На каждом σk вычисляется некоторое φ(σk) — его приоритет. Ветвлению подлежит то σk, у которого приоритет наибольший (в правиле кратчайшей операции ).

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

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

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

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

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

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

Индивидуальные тестовые задачи

Упражнение 1. Показать, что σ1k лучше σ2k, если

М (σ1k) содержит все М (σ2k), a F (σ 1l) ≤ F (σ 1l).

Упражнение 2. Как мы отмечали, каждая часть критического пути есть критический путь в том смысле, что лежащие на критическом пути пункты i и j также соединены «наиболее длинно» и не существует другого пути, который соединяет эти пункты «более долгим образом». Докажите это.

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

Упражнение 4.

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

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

Доказать эти утверждения, воспользовавшись формулировкой: показать, что значение функции-критерия при этом уменьшается на

Упражнение 5. Число ветвлений можно сократить, если лучше «прогнозировать» значение F(σn), вычисляя b(σk). Для этого, получив σk, например, можно вычеркнуть все строки i, где i берется из М(σk-1), a матрицу, которая осталась, преобразовать согласно утверждениям 1 и 2. Продумайте это предложение и постарайтесь использовать при решении задачи.

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

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

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

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

Упражнение 10. Постройте что-то аналогичное «интервалам очередности» для задачи трех станков.

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

Упражнение 12. Объясните, откуда в формуле (5.94) взялось последнее слагаемое.

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

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

Таблица 5.23

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

Комбинаторика и нечеткие структуры

5.21. Введение в теорию трансверсалей

(представителей)

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

Определение

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