автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Эволюционные алгоритмы решения задач смешанной целочисленной оптимизации

ВВЕДЕНИЕ.

ГЛАВА 1. Практические задачи принятия решений и выбора вариантов при управлении техническими и организационными системами

§1.1. Задача составления расписания посадок самолетов для аэропортов средних размеров.

§1.2. Задача составления расписания посадок самолетов для аэропортов с интенсивным воздушным движением.

§1.3. Формирование кредитного портфеля банка: нахождение оптимального набора кредитных заявок при согласованном виде структуры активов - ' пассивов.

§ 1.4. Задача формирования заявки на отгрузку товара в крупном торговом предприятии.

Выводы.

ГЛАВА 2. Методы решения задач дискретной оптимизации

§2.1. Метод ветвей и границ.

§2.2. Генетические алгоритмы.

§2.3. Поисковые методы оптимизации и гибридные алгоритмы.

Выводы.

ГЛАВА 3. Генетические алгоритмы решения задач смешанного целочисленного математического программирования

§3.1. Генетический алгоритм для решения задач СЦП.

§3.2. Сравнительный анализ алгоритмов эволюционного типа и метода ветвей и границ в решении тестовых задач СЦЛП.

§3.3. Сравнительный анализ метода ветвей и границ и генетического алгоритма в решении задач нелинейного СЦП.

§3.4. Решение тестовых задач СЦП гибридными алгоритмами.

Выводы.

ГЛАВА 4. Применение поисковых адаптивных алгоритмов к решению практических задач СЦП

§4.1. Описание пакета программ для решения задач СЦЛП.

§4.2. Описание пакета программ для решения задач нелинейного СЦП.

§4.3. Решение задачи составления расписания посадок самолетов в аэропорту.

§4.4. Решение задачи формирования кредитного портфеля банка.

§4.5. Решение задачи формирования заявки на отгрузку товара.

Выводы.

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

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

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

Состоящие проблемы. Задачи смешанного целочисленного линейного программирования (СЦЛП) являются важнейшим классом задач математического программирования. К ним сводятся многие практические задачи оптимизации, в частности, к полностью целочисленным задачам линейного программирования сводится большинство известных комбинаторных задач [14]. Доказано, что задачи СЦЛП относятся к классу NP - полных задач [10]. Это означает, что для отыскания оптимального решения требуется экспоненциальное время. Несмотря на отсутствие доказательства того, что из NP - полноты следует труднорешаемость, NP -полнота задачи означает, что для ее решения полиномиальным алгоритмом требуется по крайней мере крупное открытие [10]. Практическое значение понятия NP - полной задачи состоит в том, что такие задачи по существу трудно решаемы с вычислительной точки зрения. Из этого, в частности, следует, что построение точных алгоритмов является нецелесообразным, что, в свою очередь, приводит к необходимости разработки приближенных эвристических методов, особенно для решения практических задач большой размерности.

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

Идея метода отсечения для общей задачи ЦДЛ впервые была изложена Данцигом. Известны три алгоритма Гомори, реализующие идею методов отсечения для решения задач полностью целочисленного линейного программирования и СЦЛП [41]. Упомянутые и подобные им алгоритмы отсечения, использующие двойственный симплекс - метод, составляют класс двойственных алгоритмов методов отсечений, каждый из которых отличается способом построения отсечений. Поиску более сильных отсечений посвящен ряд работ [9, 57, 58]. В работе [58] предложены специальные линейные ограничения, позволяющие реализовать конечный алгоритм метода отсечения для дискретной задачи нелинейного программирования. Более широкий обзор литературы по методам отсечения содержится в работах [18, 20, 27, 45] и др.

Сходимость методов секущих плоскостей к оптимальному целочисленному решению после конечного числа шагов доказана теоретически [2]. Однако их применение ограничивается задачами небольшой и средней размерности, кроме того, в [21] указаны следующие недостатки методов отсечений: как правило, медленная сходимость к оптимальному решению; непредсказуемость, т. е. для ряда задач оптимизации решение не удавалось найти после многих тысяч итераций; нерегулярность, т. е. число итераций существенно зависит от выбора порождающей строки, перенумерации переменных.

Комбинаторные методы по своему характеру весьма разнообразны [20]. Центральное место среди них занимают методы ветвей и границ. Они базируются на конечности числа допустимых решений СЦЛП и систематически уменьшают допустимое множество, исключая неперспективные, т. е. не содержащие оптимум, подмножества [2]. В настоящее время известен ряд общих схем метода ветвей и границ [27, 31, 36, 41, 65]. Алгоритмы ветвей и границ отличаются способами ветвления, вычисления оценок и др. Обзор литературы по методам ветвей и границ можно найти в работах [20, 21, 43, 44]. Основным недостатком методов ветвей и границ является экспоненциальный рост вычислений при увеличении размерности задачи [21].

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

Общая задача СЦЛП, по-видимому, трудна по существу, и для нее разработано большое число алгоритмов [31]. Некоторые из этих алгоритмов особенно эффективны для определенных классов задач СЦЛП, но можно без опаски утверждать, что неизвестен общий алгоритм, который хорошо работал бы на практике для больших задач (скажем, с несколькими десятками ограничений и переменных). Имеется несколько возможностей, которые менее безнадежны, чем попытки решить NP - полную задачу оптимизации точно и эффективно. Ниже приводится список основных возможностей.

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

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

3.Частные случаи. Частные случаи NP - полной задачи могут быть простыми.

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

5.Локальный поиск. Одним из наиболее успешных подходов к решению трудных комбинаторных задач является дискретный аналог "метода спуска", известный как локальный поиск.

6.Эвристики. Любой из описанных выше подходов без формальной гарантии хорошего поведения можно рассматривать как "эвристику". Такие подходы, будучи неудовлетворительными с математической точки зрения, уверенно работают в практических ситуациях.

Приведем краткий обзор описанных в литературе подходов.

Одним из подходов для получения приближенных решений является поиск аппроксимаций [20]. Самой интересной и многообещающей идеей является использование предварительной оценки отклонения от оптимума допустимого решения. Алгоритм, дающий допустимое решение с любой заданной точностью отклонения от оптимума, называется аппроксимирующей схемой. Полиномиальная аппроксимирующая схема должна иметь полиномиальную сложность для любой заданной точности. Существенно, что точная оптимизация некоторых NP - сложных задач ведет к аппроксимирующим схемам полиномиальной сложности.

Для частных случаев задач СЦЛП предложен метод узловых векторов [16]. С помощью переборной процедуры генерируются варианты - векторы фиксированных целочисленных переменных. Соответствующая некоторому варианту задача линейного программирования определяет так называемый узловой вектор разрешающих множителей - оптимальное решение двойственной ЛП - задачи. Узловые векторы используются при построении оценок для других вариантов. В результате метод отсеивает большинство перебираемых вариантов без решения соответствующих задач ЛП. Однако предполагается, что при увеличении размерности задач, а также при больших или нецелых значениях коэффициентов целевой функции применение этого метода может вызвать трудности.

К комбинаторным методам относится метод последовательного анализа вариантов, общий формализм которого был разработан В. С.

Михалевичем [28, 29]. Частным случаем схемы последовательного анализа вариантов является динамическое программирование, в основе которого лежит принцип оптимальности Р. Беллмана [40].

Общая схема методов построения последовательности решений предложена В. А. Емеличевым. В [14] предложен единый подход к решению широкого класса задач дискретной оптимизации. В его основе лежит идея построения последовательности планов вспомогательной задачи в порядке ухудшения оценочной функции (миноранты или мажоранты). При построении последовательности планов вспомогательная задача решается методом функциональных уравнений динамического программирования. Предлагается процедура упорядочивания планов вспомогательной задачи и изложен метод решения общей задачи дискретного программирования.

Приближенным методом, являющимся модификацией точных методов, является луч - метод, предложенный В. Р. Хачатуровым [46] для решения задач целочисленного программирования. Однако особенности проверки сформулированного в луч - методе критерия оптимальности затрудняют его применение для отыскания точного решения в практических задачах. Серия расчетов показала эффективность разработанных приближенных алгоритмов для специальных классов задач ЦЛП.

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

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

Этой же схемой можно описать широкий класс методов декомпозиции задач большой размерности [27, 29]. Суть этих методов состоит в различных способах разложения исходной задачи на ряд независимых блоков меньшей размерности и различных способах синтеза решений, полученных в блоках. Основная проблема, характерная для этих методов, состоит не столько в построении алгоритмов разбиения на блоки, сколько в построении алгоритмов синтеза, гарантирующих получение оптимального решения на основе решений задач по блокам. Как правило, на этом пути встречаются значительные теоретические и вычислительные трудности, поэтому в этих методах чаще всего ограничиваются получением приближенного решения исходной задачи.

Для решения специальных задач нелинейного целочисленного программирования следует выделить оригинальный метод последовательных расчетов, предложенный В. П. Черениным [59].

Из проведенного обзора можно сделать вывод, что надежда на создание точных методов, гарантирующих определение за приемлемое время оптимального решения для многих практических задач целочисленного программирования, является, по-видимому, иллюзорной [46]. В настоящее время для решения таких задач приходится довольствоваться приближенными подходами. Однако и приближенные методы в основном и разработаны для специальных классов задач или решают задачи небольшой и средней размерности. Одним из перспективных подходов к решению задач С ЦП большой размерности является применение методов эволюционного поиска. В [53] предложен генетический алгоритм для решения задач СЦП. Идея состоит в разбиении множества переменных на множество целочисленных и множество вещественных [82]. Целочисленные переменные фиксируются через эволюционную систему, а вещественные определяются как функции от них через решение задачи математического программирования. Решение тестовых задач показало перспективность такого подхода. Разрабатываются и гибридные алгоритмы. Дополнительным преимуществом генетического алгоритма для полностью целочисленных задач нелинейного программирования является возможность неаналитического задания целевой функции.

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

Эта цель обусловила необходимость решения следующих задач:

- анализ свойств практических задач принятия решений и выбора вариантов при управлении техническими и организационными системами, формализуемых в виде задач смешанного целочисленного программирования;

- разработка и программная реализация адаптивных поисковых алгоритмов, позволяющих решать задачи линейного СЦП;

- разработка и программная реализация адаптивных поисковых алгоритмов для решения задач нелинейного СЦП;

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

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

Научная новизна результатов, полученных в диссертации, состоит в следующем:

1. Выполнена модификация формальных моделей составления расписания посадок самолетов в аэропорту.

2. Построены новые формальные модели формирования кредитного портфеля банка, формирования заявки на отгрузку товара в крупном торговом предприятии.

3. Предложен новый генетический алгоритм для решения задач линейного С ЦП, отличающийся от известных алгоритмов способом представления переменных и видом генетических операторов и превосходящий известные алгоритмы по эффективности.

4. Впервые предложен генетический алгоритм для решения задач нелинейного С ЦП.

Практическое значение. Полученные в работе результаты позволяют решать практические задачи принятия решений и выбора вариантов при управлении техническими и организационными системами. Предложенные модели составления расписания посадок самолетов в аэропорту, формализованные в виде задач смешанного целочисленного линейного математического программирования, а также алгоритмы решения задач СЦЛП и программное обеспечение, реализующее указанные модели и алгоритмы, переданы Красноярскому филиалу ГУДП "Аэронавигация Центральной Сибири".

Отдельные разделы диссертации используются в учебном процессе при обучении студентов по курсам методов оптимизации и управления сложными системами на кафедре СА и ИО, по курсу математического программирования на кафедре высшей математики Сибирской аэрокосмической академии им. ак. М. Ф. Решетнева.

Основные защищаемые положения.

1. Задачи составления расписания посадок самолетов в аэропорту, формирования кредитного портфеля банка, формирования заявки на отгрузку товара крупного торгового предприятия адекватно формализуются в виде задач смешанного целочисленного программирования.

2. Предлагаемые генетические алгоритмы обеспечивают более быстрое нахождение допустимого решения хорошего качества по сравнению с классическими подходами.

3. Разработанное программное обеспечение отвечает современным требованиям к прикладному ПО и позволяет эффективно решать реальные практические задачи, формализованные в виде задач СЦП.

Публикации. По теме диссертации опубликовано тринадцать печатных работ, которые приводятся в списке литературы под номерами 1113,25,48-56.

Апробация работы. Основные положения и отдельные результаты диссертационной работы докладывались и обсуждались на -1 Всесибирском конгрессе женщин - математиков (Красноярск, 2000);

- П Всесибирском конгрессе женщин - математиков (Красноярск, 2002);

- IV Королевских чтениях (Самара, 2001);

- Решетневских чтениях (Красноярск, 2000,2001);

- Краевой конференции "Интеллект - 2001" (Красноярск, 2001);

14

- научных семинарах кафедры системного анализа и исследования операций Сибирской аэрокосмической академии им. ак. М. Ф. Решетнева (Красноярск, 1999-2002).

Структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Изложение иллюстрируется 13 рисунками, 8 графиками и 13 таблицами. Общий объем -163 страницы, список литературы - 89 наименований.

Выводы

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

ЗАКЛЮЧЕНИЕ

Диссертационная работа посвящена разработке эффективного математического, алгоритмического и программного обеспечения методов решения задач смешанного целочисленного программирования.

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

Проделанная работа позволяет сделать следующие выводы:

- задачи составления расписания посадок самолетов в аэропорту, формирования кредитного портфеля банка, формирования заявки на отгрузку товара адекватно формализуются в виде задач смешанного целочисленного программирования;

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

- разработанные программные средства позволяют эффективно решать реальные практические задачи смешанной оптимизации;

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

1 л 1 i~r J.

1. Алексеев О. Г. Комплексное применение методов дискретной оптимизации. - М.: Наука, 1987. - 247 с.

2. Антамошкин А. Н. и др. Системный анализ: проектирование, оптимизация и приложения. В 2 т. Красноярск: САА, 1996. т. 1. - 206 е., т. 2. - 290 с.

3. Ачкасов А. И. Балансы коммерческих банков и методы их анализа. Вопросы ликвидности и их отражение в банковских балансах. М.: Консалтбанкир, 1993. - 73 с.

4. Ашманов С. А., Тихонов А. В. Теория оптимизации в задачах и упражнениях. М.: Знание, 1991. - 193 с.

5. Банди Б. Основы линейного программирования. М.: Радио и связь, 1989. 176 с.

6. Банки и банковское дело: Учеб. пособие / Под ред. Балабанова И. Т. -СПб.: Питер, 2000. 253 с.

7. Белых Л. П. Устойчивость коммерческих банков. Как банкам избежать банкротства. М.: Банки и биржи, ЮНИТИ, 1996. - 192 с.

8. Большая энциклопедия транспорта. В 8 томах. Том 2. Авиационный транспорт. / Под ред. проф. А. Г. Братухина, зам. гл. ред. Л. А. Гильберг. -М.: Машиностроение, 1995. 400 с.

9. Вотяков А. А. Целочисленное программирование, сравнение отсечений. // Экономика и мат. методы. 1972 - Вып. 1. Том 8. - с. 107 - 116.

10. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. - 416 с.

11. Емеличев В. А., Комлик В. И. Метод построения последовательности планов для решения задач дискретной оптимизации. М.: Наука, 1981. - 208г

12. Заславский А. А., Лебедев С. С. Метод узловых векторов в целочисленном программировании // Экономика и математические методы. -2000. Том 36. Вып. 4. - с. 108-120.

13. Казаковцев Л. А. Система поддержки принятия решений коммерческой службой торгового предприятия по оперативной информации. Диссерт. на соиск. уч. степ. канд. техн. наук. Красноярск: НИИ СУВПТ, 2002. - 138 с.

14. Ковалев М. М. Дискретная оптимизация (целочисленное программирование). Минск: Изд-во Белорус, ун-та, 1977. - 192 с.

15. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности / Под ред. В. Р. Хачатурова М.: Наука, 2000. - 354 с.

16. Корбут А. А., Финкелыптейн Ю. Ю. Дискретное программирование. М.: Наука, 1969.-368 с.

17. Кротов В. Ф. Основы теории оптимального управления. М.: Высшая школа, 1990. - 432 с.

18. Кузнецов Ю. Н., Кузубов В. И., Волощенко А. Б. Математическое программирование. -М.: Высш. школа, 1980. 300с.

19. Лебедев С. С. О методе упорядочивающей индексации целочисленного линейного программирования // Экономика и математические методы. -1997. Том 23. Вып. 2. - с. 123-131

20. Лебедев С. С. Модификация метода Бендерса частично целочисленного линейного программирования // Экономика и математические методы. -1994. Том 30. Вып. 2. - с. 107-126.

21. Маслаченков Ю. С. Финансовый менеджмент в коммерческом банке. -М.: Перспектива, 1996. 159 с.

22. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990. - 488 с.

23. Михалевич В. С. Последовательные алгоритмы оптимизации и их применение. // Кибернетика. № 2. - 1965. с. 85 - 89.

24. Михалевич В. С., Кукса А. Й. Методы последовательной оптимизации в дискретной сетевых задачах оптимального распределения ресурсов. М.: Наука, 1983. - 207 с.

25. Панова Г. С. Кредитная политика коммерческого банка. М.: ИКЦ "ДИС", 1997.-467 с.

26. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация: алгоритмы и сложность. М.: Мир, 1985. - 512 с.

27. Пуртиков В. А. Постановка задачи оптимизации выбора кредитного портфеля. // Вестник НИИ СУВПТ. Красноярск: НИИ СУВПТ. - 1999. -Вып. 2. - с. 145 - 159.

28. Пуртиков В. А. Оптимизация управления формированием кредитного портфеля банка. Диесерт. на соиск. уч. степ. канд. техн. наук. Красноярск: САА, 2001,- 148 с.

29. Растригин JI. А. Статистические методы поиска. М.: Наука, 1968.

30. Реклейтис Г., Рейвиндран А., Рэксдел К. Оптимизация в технике: В 2-х кн. Кн. 2.-М.: Мир, 1986. 320с.

31. Романовский И. В. Методы неявного перебора для решения задачи целочисленного программирования с булевыми переменными. // Изв. вузов. Математика. 1970.- № 4. - с. 17 - 29.

32. Семенкин Е. С., Семенкина О. Э., Коробейников С. П. Оптимизация технических систем. Красноярск: СИБУП, 1996. - 285 с.

33. Семенкин Е.С., Семенкина О. Э., Коробейников С. П. Поисковые методы синтеза систем управления космическими аппаратами. Красноярск: СИБУП, 1996.-325 с.

34. Семенкина О. Э. Поисковые методы синтеза систем управления космическими аппаратами: Дисс. на соиск. уч. степ. канд. техн. наук. -Красноярск: САА, 1995. 181 с.

35. Сергиенко И. В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наук, думка, 1988. - 471 с.

36. Сергиенко И. В., Лебедева Т. Г., Рощин В. А. Приближенные методы решения дискретных задач оптимизации. Киев: Наук, думка, 1980. - 286 с.

37. Скрипкин К. Г. Финансовая информатика. М.: Финансы и статистика, 1997. - 160 с.

38. Схрейвер А. Теория линейного и целочисленного программирования. В 2-хтомах, т.2. -М.: Мир, 1991. 702 с.

39. Финкелыптейн Ю. Ю. Приближенные методы и прикладные задачи дискретного программирования. Н.: Наука, 1976. - 264 с.

40. Фридман А. А. О некоторых современных направлениях в дискретной оптимизации. // Экономика и мат. методы. 1977. - № 13. Вып. 5. - с. 1115 -1131.

41. Хачатуров В. Р., Мирзоян Н. А. Решение задач целочисленного программирования луч-методом. М.: ВЦ АН СССР, 1987. - 25 с.

42. Химмельблау Д. Прикладной нелинейный анализ. М.: Мир, 1975. - 534с.

43. Хоролич Г. Б. Генетический алгоритм для задачи составления расписания посадок самолетов в аэропорту с несколькими ВПП // Вестник НИИ СУВПТ: Сб. науч. тр. Вып. 7. - Красноярск, 2001. - с. 24 - 29.

44. Хоролич Г. Б. Два подхода к решению задач СЦЛП генетическими алгоритмами //П Всесибирский конгресс женщин математиков: тезисы докладов конгресса, 15-17 января 2002 г. / под ред. д. т. н., проф. Проворовой О. Г. - Красноярск: КГУ, 2002. - с. 245-246.

45. Хоролич Г. Б. Решение задачи составления расписания посадок самолетов адаптивными поисковыми алгоритмами // Вестник Сибирской аэрокосмической академии имени акад. М. Ф. Решетнева: Сборник научн. тр. САА. Вып. 2. - Красноярск, 2001. - с. 175-180.

46. Хоролич Г. Б. Решение задач смешанного целочисленного программирования адаптивными поисковыми алгоритмами // Вестник НИИ СУВПТ: Сб. науч. тр. Вып. 7. - Красноярск, 2001. - с. 216 - 223.

47. Хоролич Г. Б. Решение задач смешанного целочисленного математического программирования эволюционными алгоритмами //

48. Всесибирский конгресс женщин математиков: тезисы докладов конгресса - ИВМ СО РАН: Красноярск, 2000. - с. 246

49. Хоролич Г. Б., Мори и А. В. Гибридный алгоритм для решения задач смешанного целочисленного программирования // Решетневские чтения: тезисы докладов V Всероссийской научной конференции. Красноярск: САА, 2001.-с. 77-78.

50. Хоролич Г. Б. Формализация и решение генетическими алгоритмами задачи формирования кредитного портфеля банка // Интеллектуальные технологии и адаптация. Красноярск: НИИ СУВПТ, 1999. - с. 42 - 45.

51. Хоролич Г. Б. Формальные модели задачи составления заявки на отгрузку товара в крупном торговом предприятии // Интеллектуальные технологии и адаптация. Красноярск: НИИ СУВПТ, 1999. - с. 37 - 41.

52. Червак Ю. Ю. Усиление одного класса правильных отсечений. // Экономика и мат. методы. 1976. - № 12. Вып. 2. - с. 339 - 406.

53. Червак Ю. Ю. Лексикографический поиск решений задач дискретного программирования (текст лекций). Ужгород: Изд-во Ужгород, ун-та. - 1997, 43 с.

54. Центральный банк РФ. Инструкция о порядке регулирования деятельности кредитных организаций. // Вестник Банка России. 1999. - 02 июня.

55. Beasley J. Е., Krishnamoorthy М., Sharaiha Y. М., Abramson D. Dynamically scheduling aircraft landings the displacement problem. // Imperial College, London SW7 2AZ. - 1995.

56. Beasley J. E., Krishnamoorthy M., Sharaiha Y. M., Abramson D. Scheduling aircraft landings the static case // Transportation Science. - 2000. - Vol. 34. - p. 180-197.

57. Beasley J. E. OR-Library: distributing test problems by electronic mail // Journal of the Operational Research Society. . 1990. - Vol. 41 - p. 1069 -1072.

58. Berkelaar R. E. and Ceria J. S., McZeal С. M. and Savelsbergh M. W. An updated mixed iteger programming library // Technical report. Rice Uneversity. -1998. -TR98-03.

59. Breu R., Burdet C. A. Branch and bound experiments in zero one programming I I Math. Program. Study 2. - 1974. - p. 1 - 50.

60. Carr G. C., Erzberger H., Neuman F. Airline arrival prioritization in sequencing and scheduling // Air Traffic Management R&D Seminar. Orlando. -1998. - http://www.ctas.arc.nasa.gov/publications.

61. Cerny V. A thermodynamic approach to the traveling salesman problem: An efficient simulation // J. Optim. Theory Appl. 45. 1985. - p. 41 -51.

62. De Jong K. An analysis of the behavior of a class of genetic Algorithms. Doctoral dissertation. University of Michigan. 1975.

63. Fogel D. B. System identification through simulated evolution. Needhaw Heights, MA: Ginn. 1991.

64. Gardner Martin. Mathematical Games // Scientific American 1972. - v.227. n.2. - p.106.

65. Geoffrion A. M. Generalized Benders decomposition // J. Optimiz. Theory and Appl. 1972. - n 7. - p. 237 - 260.

66. Goldberg David E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA. 1989.

67. Heath F. G. Origins of the Binary Code // Scientific American. -1972. V.1.? « о / . Ii. Z.

68. Holland J. H. Adaptation in natural and artifical system. Ann Arbor: The University of Michigan Press. 1975.

69. Hollstien R. B. Artificial Genetic Adaptation in Computer Control Systems // PhD thesis, University of Michigan. -1971.

70. Horowitz P. and Winfield H. The Art of Electronics // Second Edition. Cambridge University Press. 1989.

71. Kirkpatrick S., Gelett C. D., Vecchi M. P. Optimization by Simulated Annealing // Science 220. 1983. - p. 621 - 630.

72. Kozen D. The Design and Analysis of Algorithms. New York: Springer-Verlag, 1992.

73. Land A. H., Doig A. G. An automatic method of solving discrete programming problems // Econometrica. n. 3,1960. - p. 497 - 520.

74. Lawler E. L.,Wood D. E. Branch and - bound methods: a survey // Oper. Res. 4, 1966.-p. 699 - 717.

75. Little J. D., Murty K. G., Sweeney D. W., Karel C. An algorithm for traveling salesman problem // Oper. Res. n. 6,1963. - p. 972 - 989.

76. Pedroso J. P. Niche search: an evolutionary algorithm for global optimization // Parallel Problem Solving from Nature IV. Vol. 1141 of Lecture Notes in Computer Science. Berlin, Germany: Springer. - 1996.

77. William H. Press et al. Numerical Recipes in С // Second Edition. Cambridge University Press. -1992.

78. Rechenberg I. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Stuttgart: Frommann Holzboog. - 1973.

79. Reingold E. M. et al. Combinatorial Algorithms // Prentice Hall, Englewood Cliffs. NJ. 1977.

80. Schraudolph N. N., Belew R. K. Dynamic Parameter Encoding for Genetic Algorithms. // Machine Learning. 1992. - vol. 3. - p. 98 - 114.

81. Schwefel H. P. Kybernetische Evolution als Strategie der Stromangstechik. Diploma thesis, Technical University of Berlin. - 1965.

82. Shittkowski K. More Tests Examples for Nonlinear Programming Codes. Berlin Heidelberg: Springer - Verlag, 1987. - 266p.

83. Wong G. L. The dynamic planner: the sequencer, scheduler, and runway allocator for air traffic control automation. // Report NASA / TM-2000-209586. -USA, 2000. http://www.ctas.arc.nasa.gov/publications.1. Тестовые задачи СЦЛП

84. Задача Число переменных (из них целочисленных) Число ограничений Известное оптимальное решение Решение соответствующей задачи ЛП Примечанияbelt За 133 (71) 123 878430. 32 862578. 64 39 из целочисленных переменных бинарные