Файл: Голенко Д.И. Статистические модели в управлении производством.pdf

к перестановке, принимаемой за исходную в третьей ите­ рации.

Описанная выше процедура повторяется до выполне­

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

Достоинством эвристических методов является удоб­ ство реализации их на ЭВМ даже яри решении громозд­ ких задач, поскольку формирование расписания связано •с его моделированием во времени. Основным недостат­ ком этих методов, отнюдь не препятствующих их прак­ тическому применению, является сравнительно невысо­ кая точность, которая объясняется тем, что трудно скон­ струировать правило, одинаково хорошее для всех раз­ новидностей задач. Другой недостаток заключается в невозможности построения опенок близости полученных расписаний к оптимальным. Развитием чисто эвристиче­ ских методов (развивается и обобщается идея модели­

ЭВМ и располагаемым для решения задач временем, что

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

При решении задач больших «площадей», когда чис­ ло N ограничено несколькими десятками испытаний, до-

вольно эффективными являются комбинации метода ста­ тистических испытаний с различными эвристическими правилами предпочтения.

Ниже мы рассмотрим статистические методы и их «комбинации с эвристическими для исследования моделей календарного планирования.

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

Под поиском понимается процесс отыскания хотя бы одного расписания А\ из множества допустимых рас­ писаний D, которое близко к оптимальному, т. е.

K(AR*)<mmK(A)+e, A<=D

где є > 0 наперед заданное число.

•расписания, которое является приближением к оптималь­ ному.

Различают ненаправленный случайный поиск; направ­ ленный случайный поиск без самообучения; направлен­ ный случайный поиск с самообучением.

Если поиск оптимального плана ведется среди дей­ ствительных планов, то область D конечна и существует

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

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

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

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

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

сравнение показателя качества производится с ранее рас­ считанным (лучшим) показателем. Более общие приемы локального поиска будут рассмотрены отдельно.

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

вперестройке вероятностных характеристик поиска, т. е.

вопределенном целенаправленном воздействии на слу­

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

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

§2. 4. Методы ненаправленного случайного поиска

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

Пусть, например, при моделировании случайной пе­ рестановки я = ( ї ь і2, із, ц, is) получены следующие 5 ре­ ализаций |: 0,01214;А 0,31256^0,11255; 0,84257; 0,38142, тогда я = (53412). Методика моделирования случайной величины, равномерно распределенной в интервале (0,1), представлена в ряде монографий, например в [2.11].

Чтобы построить вероятностные оценки сходимости расписаний, полученных по методу Монте-Карло, к опти­ мальному, необходимо построить плотность или функцию распределения значений критерия, рассматривая их как случайные величины. Можно показать, что при достаточ­ но большом числе деталей это распределение является приблизительно нормальным (результаты демонстриру­ ются на двух задачах — одна объемом 100x10, дру­ г а я — 20X10). Если, далее, известен вид этого распреде­ ления, то можно, в частности, ответить на вопрос о том (проблема решения с риском), сколько испытаний ме­ тодом Монте-Карло следует произвести, прежде чем сто­ имость очередного испытания будет больше средней