Читать онлайн «Семиотика и информатика. Выпуск 08»

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СОВЕТА МИНИСТРОВ СССР ПО НАУКЕ И ТЕХНИКЕ АКАДЕМИЯ НАУК СОЮЗА СОВЕТСКИХ СОЦИАЛИСТИЧЕСКИХ РЕСПУБЛИК ВСЕСОЮЗНЫЙ ИНСТИТУТ НАУЧНОЙ И ТЕХНИЧЕСКОЙ ИНФОРМАЦИИ СЕМИОТИКА И ИНФОРМАТИКА ВОСЬМОЙ ВЫПУСК МОСКВА 1 977 1—9968 РЕДАКЦИОННАЯ КОЛЛЕГИЯ главный РЕДАКЮР^профессор А. И. Михайлов, оцент Р. С. Гиляревский, Т. Н. Лаппалайнен (ответственный секретарь) профессор В. А. Успенский, канд. филол. наук С. Я. Фокин, канд. техн. наук А. И. Черный (зам. главного редактора), канд. физ. -мат. наук Ю. А. Шрейдер © ВИНИТИ, 1977 УДК 519. 85 С. И. Самойленко СУБОПТИМАЛЬНОЕ ПРОГРАММИРОВАНИЕ ВВЕДЕНИЕ К настоящему времени в рамках математического программирования разработан ряд эффективных мето- методов поиска оптимальных решений для задач различных классов. Наиболее сильные результаты получены для задач, решаемых методами линейного программирова- программирования. Разработаны способы решения некоторых классов нелинейных и целочисленных задач. Вместе с тем следует отметить, что значительное число сложных задач большой размерности не могут быть решены разработанными методами математическо- математического программирования вследствие того, что они либо не сводятся к классам задач, для которых известны методы нахождения оптимального решения, либо же не удов- удовлетворяют чисто практическим ограничениям, наклады- накладываемым предельным объемом памяти или быстродейст- быстродействием используемых ЭВМ. К числу таких задач сводятся и многие проблемы ин- информатики, среди которых задача выбора структуры территориально рассредоточенной ИПС, выбор пропуск- пропускной способности каналов связи в таких системах, рас- распределение средств повышения помехоустойчивости и другие оптимизационные задачи. Для решения таких задач целесообразно применять субоптимальные методы поиска решений, которые не обязательно приводят к оптимальному результату, но дают «хорошее» решение, удовлетворяющее ограниче- ограничениям задачи, причем это «хорошее» решение может 1* 3 последовательно улучшаться и приближаться к опти- оптимальному по мере увеличения затрат машинного вре- времени. Целью настоящей работы является описание некото- некоторых методов поиска субоптимальных решений. В первой части рассматривается процедура поиска решения в диалоговом режиме, при котором алгоритм строится так, чтобы человек, решающий задачу, мог ис- использовать ЭВМ для оценки своих предположений о перспективных направлениях поиска и уточнять их с учетом результатов машинного эксперимента. Для некоторых задач возможно использование не- нескольких эвристических гипотез, определяющих рацио- рациональные направления поиска решений, причем их эф- эффективность может быть различной. В таких условиях возникает задача выбора рациональной композиции эв- эвристических процедур, которые дают наилучший эффект для данных условий. В этом случае удобно использовать адаптивные методы организации поиска, при которых композиция эвристических процедур формируется из заданного множества в процессе решения задачи с уче- учетом успешности использования создаваемых композиций на предыдущих этапах поиска.