|
после чего будет произведен просмотр граничной точки первого уровня (единственный раз!). Данный алгоритм успешно применяется для безусловной оптимизации. Для учета ограничений используем метод штрафных функций. Первый предложенный метод метод ветвей и границ позволяет отыскать оптимум за конечное число шагов (исключая полный перебор) с использованием ограничений накладываемых на решение. В этом методе именно за счет ограничений происходит отбрасывание части булевою пространства тем самым, исключая полный его просмотр. К достоинствам метода можно отнести то, что он находит точное решение (точный метод), т.е. он всегда дает оптимальное решение за конечное число шагов. Кроме того, данный алгоритм имеет довольно простую реализацию. Для нахождения минимума необходимо провести не более (2/7-ь I) вычислений целевой функции. Конечно, нет смысла применять метод ветвей и границ для задачи с количеством переменных меньше 100, но при количестве свыше 100 данный алгоритм значительно уменьшит количество вычислений. Ведь если размерность задачи увеличивается, то почти пропорционально ей увеличивается количество вычислений. Второй метод — метод локального спуска относится к методам приближенного решения задачи и сравнительно недавно его стали применять как точный метод. Его, как и предыдущий метод нет смысла применять к задачам маленькой размерности (меньше 100). Количество вычислений целевой функции для этого метода зависит от номера уровня, на котором находится начальная точка относительно минимума. 73 |
135 реш ение находится среди граничных точек. Таким образом, при просмотре окрестности будем просматривать только граничны е точки. П ри этом все проекты были изначально отсортированы но увеличению среднеквадратичного отклонения. С окращ ение перебора будет обеспечено за счет того, что все точки нечетных по отнош ению к стартовой точке уровней не будут просматриваться до тех пор, пока не будет «накры та» точка минимума, после чего будет произведен просмотр граничной точки первого уровня (единственный раз!). Д анны й алгоритм успеш но применяется для безусловной оптимизации. Для учета ограничений используем метод ш траф ны х функций. П ервы й предлож енны й метод метод ветвей и границ позволяет отыскать оптимум за конечное число ш агов (исклю чая полны й перебор) с использованием ограничений накладываемых на реш ение. В этом методе именно за счет ограничений происходит отбрасы вание части булевого пространства тем самым, исклю чая полный его просмотр. К достоинствам метода можно отнести то, что он находит точное реш ение (точны й метод), т.е. он всегда дает оптимальное реш ение за конечное число ш агов. Кроме того, данны й алгоритм имеет довольно простую реализацию . Д ля нахож дения минимума необходимо провести не более (2п+1) вычислений целевой функции. К онечно, нет смы сла применять метод ветвей и границ для задачи с количеством переменны х меньш е 100, но при количестве свыш е 100 данный алгоритм значительно уменьш ит количество вычислений. Ведь если размерность задачи увеличивается, то почти пропорционально ей увеличивается количество вычислений. В торой метод “ метод локального спуска относится к методам приближенного реш ения задачи и сравнительно недавно его стали применять как точны й метод. 136 Его, как и предыдущий метод нет смысла применять к задачам маленькой размерности (меньше 100). Количество вычислений целевой функции для этого метода зависит от номера уровня, на котором находится начальная точка относительно минимума. Для оценки эффективности алгоритмов приближенного решения задачи условной псевдобулсвой оптимизации были разработаны программы, реализующие описанные алгоритмы. При проверке эффективности алгоритмов реш алась задача формирования инновационного портфеля, которая относится к задачам условной псевдобулевой оптимизации. Решение данной задачи было заведомо известно. Так как данные методы относятся к приближенным методам дискретного программирования, то необходимо оценивать алгоритмы по следующим признакам: по количеству вычислений целевой функции и функций ограничений; по точности решения (определяется величиной погрешности решения); по простоте (предпочтения отдается логически более простому алгоритму). Первому алгоритму для нахождения оптимального инновационного портфеля потребовалось п вычислений целевой функции. Для второго метода потребовалось не более п/2+2 вычислений, если п четное значение и не более (п-1)/2+2 вычислений, если п принимает нечетное значение. Так как мы изначально знаем оптимум, то погрешность полученных решений можно вычислить по формуле: |