Метод глобального перебора (перебора на сетке).

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

Рис.1.12

Предположим, что экстремум отыскивают одним из градиентных методов. Если движение начнется из точки , то будет найден максимум в точке А. Если же исходной точкой будет точка , то поиск закончится в точке В. Стрелки, выхо­дящие из точек и 02, указывают направления градиента функции в этих точках. Это указывает на возможность модер­низации рассмотренных методов поиска с тем, чтобы приспосо­бить их для отыскания глобального экстремума многоэкстре­мальных функций. Для этого можно рекомендовать повторение процедуры поиска несколько раз из различных исходных точек. Полученные значения локальных экстремумов сравниваются между собой, и из них выбирается наибольшее (при поиске глобального максимума). Для выбора положений исходных точек может использоваться как случайная, так и детермини­рованная процедура.

Существует другой метод, позволяющий отыскать глобаль­ный экстремум целевой функции с заданной точностью — ме­тод глобального перебора, или сканирования. Пред­положим, что для каждого из аргументов целевой функции у = задан диапазон его изменения: В пространстве переменных системе этих неравенств соответствует многомерный парал­лелепипед, являющийся областью допустимых значений аргу­ментов целевой функции. Для случая функции двух переменных

у = имеем прямоугольник (рис. 2.12).

Рис.2.12

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

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

Практически он применим только при числе пере­менных целевой функции не больше 3—4 из-за того, что его трудоемкость быстро возрастает с ростом размерности задачи. В самом деле, пусть заданная точность решения задачи будет достигнута, если на каждом отрезке [ ] взять 10 рав­ноотстоящих точек. Тогда для отыскания экстремума функции двух переменных надо вычислить ее значения в 100 точках, яв­ляющихся узлами полученной сетки. Для функции трех переменных потребуется уже 10 =1000 ее вычислений и т. д. Если переменных 5, то целевую функцию нужно рассчитывать уже 20⁵ раз.

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

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

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

Рассмотри, сначала, алгоритма метода глобально перебора для отыскания максимума функции одной переменной. Блок –схема этого алгоритма показана на рис.3.12. Будем считать, для определенности, что требуется найти решение оптимизационной задачи, математическая модель которой имеет вид:

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

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

.

Зарезервируем в памяти ЭВМ ячейку, в которой будем хранить одно единственное, наибольшее по всем предыдущем шагам значение целевой функции. Обозначим соответствующую переменную через М. В начале работы программы в эту ячейку запишем «0» (блок 2). То есть присвоим М значение равное «0»: М=0 (= символ присваивания).

Рис.3.12

Вычисление значений ограничения и целевой функции начинаем с левого конца отрезка на котором осуществляется поиск максимума. Для этого присваиваем (блок3) переменной Х значение равное :Х= .

Далее, (блок 4) вычисляем значение ограничения и производим (блок 5) сравнение полученного результата с правой частью ограничения ( )

Допустим, что условие

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

Если условие ( ) не выполняется, целевая функция не вычисляется и сразу переходим к блоку 10 .

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

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

данной точке Х будет больше, чем во всех предыдущих. В этом случае (блок 9) переменной М присваивается новое значение М=W, и она снова становится равной наибольшему среди всех рассмотренных значений целевой функции. В блоке 9 переменной присваивается текущее значение переменной X: . Таким образом переменная показывает, какому значении Х соответствует текущее максимальное значение целевой функции.

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

Рассмотрим алгоритм глобального перебора для решения задач нелинейного программирования с 2-мя переменными. Пусть требуется решить следующую задачу:

Схема алгоритма, основанного на идее пе­ребора значений переменных , приведена на рис. 4.12.

Предварительно выбраны величины шагов по и , обеспечивающие удовлетвори­тельную точность решения задачи. Обозначим их и пусть ; . Вначале (блок 1) переменные и полагают равными их исходным значениям: Переменная М в имеет тот же смысл и выполняет те же функции, что и в алгоритме поиска экстремума функции одной переменной (см. рис. 3.12) Поэтому вначале ее следует положить равной любому числу, заведомо меньшему максималь­ного значения целевой функции. Поскольку в данной задаче целевая функция неотрица­тельна, можно положить М=0, что и сделано в блоке 1. Далее проверяется, удовлетворяет ли исходная точка { Х=; Х= ограничению решаемой задачи: С этой целью в блоке 2 вычисляется значение функции из этого ограничения, а полученное число­вое значение присваивается переменной z. В блоке проверки условия 3, имеющем на схеме вид ромба, проверяется выполнение записанного внутри него соотношения (в данном случае неравенства z<9). Если это неравенство оказа­лось справедливым, т. е. рассматриваемая точка удовлетворяет данному ограничению, то осу­ществляется переход по стрелке «Да» к блоку 4, где вычисляется значение целевой функции в той же точке { }. Оно присваи­вается переменной у. Невыполнение условия в блоке 3 означает, что эта точка не

Рис.4.13

при­надлежит области допустимых значений. По­этому не имеет смысла вычислять в ней значе­ние целевой функции, а следует сразу же пе­рейти к следующей точке. Это и реализовано переходом к блоку 8. Соответствующее ему дей­ствие означает, что к зафиксиро­ванному ранее значению переменной добав­ляется число 0,1. Значит, при первом обраще­нии к блоку 8 примет значение и таким образом будет исследоваться точка { }. Обратимся к операциям в блоке 5, выполняемым вслед за операциями в блоке 4. Здесь анализируется выполнение неравенства у>М, т. е. проверяется, будет ли только что найденное значение целевой функции больше М. При первом обращении к этому блоку М= = 0 (блок 1), поэтому неравенство у>М в этом случае наверняка будет выполнено и, следовательно, произойдет переход к блоку 6. Выполняемое здесь присваивание М:=у означает, что переменная М примет теперь значение, равное значению целевой функции в анализируемой точке. Согласно блоку 7, значения аргу­ментов X и Х присваиваются новым переменным и , которые тем самым будут хранить значения переменных и х ,соответствующие значению целевой функции, равному М. Далее выполняется переход к следующей точке с большим значением (блок 8) и проверяется, не превысит ли это значе­ние максимальной для него величины =4 (блок 9). Если оказалось, что < 4, то осуществляется возврат к блоку 2, т. е. все описанные выше про­цедуры, начиная с проверки выполнения ограничения <9, выполня­ются для новой точки { }. Отметим, что при втором и последующих об­ращениях к блоку 5 уже возможны разные случаи. До тех пор, пока значе­ние целевой функции в очередной точке больше чем в предыдущей, нера­венство у>М будет выполняться и согласно блоку 6 переменная М будет каждый раз принимать значение, равное очередному возрастающему значе­нию целевой функции У( . Если же в некоторой точке ее величина ока­жется меньше, чем в предыдущей точке (или равна ей), то вследствие невы­полнения неравенства у>М присваивание М:=у не будет сделано (блоки 6 и 7 обходятся). Благодаря этому переменная М сохраняет значение, равное максимальному значению целевой функции по всем предыдущим точкам, при­надлежащим области допустимых решений, а переменные а и равны зна­чениям аргументов х и в точке максимума.

Вернемся к блоку 9 и рассмотрим случай, когда записанное в нем усло­вие не выполняется. Это означает, что для данного значения Х=25 перебор по х следует завершить и возобновить его вновь, начиная с =2, уже для следующего значения . Поэтому в блоке 10 реализовано присваивание 1: = 2, а согласно блоку 11 значение х увеличивается на величину ее шага. После этого осуществляется возврат к блоку 2, т. е. анализируется очеред­ная точка. Невыполнение неравенства < в блоке 12 свидетельствует о необходимости завершить перебор. В этом случае согласно блоку 13 выво­дится найденное оптимальное решение: значение М, равное макси­мальному значению целевой функции по всем точкам из области допустимых решений, и значения переменных а и , равные аргументам и в точке оптимума. Этим завершается работа алгоритма. Реализация его на ЭВМ по­зволила получить следующие результаты: а= ; М .

Лекция 13

Общие сведения о задачах календарного планирования

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

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