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

РГб ОА " 6 СЕН 7ППП

На правах рукописи

Красилышкова Мария Владимировна

МЕТОДЫ ДЕФОРМИРУЕМЫХ КОНФИГУРАЦИЙ ДЛЯ РЕШЕНИЯ ЗАДАЧ ЧАСТИЧНО-ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

Специальность 05.13.16. - Применение вычислительной техники, математических методов и математического моделирования в научных исследованиях

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Москва 2000

Работа выполнена на кафедре АСУ Московского Государственного института Стали и Сплавов (Технологического университета)

Научный руководитель: доктор технических наук

профессор А.С.Рыков

Официальные оппоненты:

доктор технических наук, профессор В.А.Лотоцкий кандидат технических наук, доцент Ф.Н. Григорьев

Ведущая организация: АО ЧЕРМЕ/ГАВТОМАТИКА

Защита состоится ")^ ^СиСЬ^_2000 г. в [Ч часов на заседании диссертационного совета Д.053.08.07 в Московском Государственном институте стали и сплавов (Технологическом университете) по адресу: 117936, г. Москва, Ленинский просп., 4 .

С диссертацией можно ознакомиться в библиотеке Московского Государственного института стали и сплавов (Технологического университе-

та)

Автореферат разослан" "

2000 г.

Ученый секретарь диссертационного совета

к.т.н., Е.А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

В соответствие с поставленной целыо проводятся следующие исследования:

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

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

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

- разработка методики исследования и сравнения предлагаемых и известных методов на основе вычислительного эксперимента.

Методы исследования. Исследования были выполнены на основе теории частично-целочисленного программирования и методов оптимизации. Для разработки программного обеспечения использовались методы структурного программирования.

Научная новизна результатов. Основным научным результатом диссертации является разработка методов решения задач частично-целочисленного нелинейного программирования малой и средней размерности.

Новизна диссертации состоит в следующем:

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

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

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

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

Теоретическая значимость исследования заключается в том, что в работе:

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

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

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

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

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

2. Новые алгоритмы прямого поиска из класса деформируемых конфигураций для условных задач частично-целочисленной оптимизации малой и средней размерности.

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

Апробация работы. Основные положения и результаты работы обсуждались на Международной научно-технической конференции "Структурная перестройка металлургии: экономика, экология, управление, технология" (Новокузнецк) и на семинарах в Кемеровском Государственном Университете, в Институте проблем и управления, на семинарах кафедры АСУ МИСиС.

Публикации. По теме диссертации опубликовано 4 работы.

Структура и объем диссертационной работы. Работа состоит из введения, шести глав, заключения и списка литературы, включающего 76 наименований. Основной текст занимает 137 машинописных страниц, в том числе 27 рисунков и 20 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ.

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

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

Рассмотрим общую формулировку задачи частично-целочисленного программирования:

пппДх.У) (1)

при ограничениях

$к(х,у)<0, к - \,т

ЛА. (х,у) = 0, к = тх +1 ,ш2

У = Ь'!,^,.-,^} е У"1, >и е {0,1,2,...}, - 1 ,п2

где х - вектор п{ непрерывных переменных, у - вектор щ целочисленных переменных, #д(х,у)^0, к = I,//г, - ограничения тина неравенства, ЛА.(Х,у) = (>, к - т] + \,ш2 - ограничения типа равенства. Предполагается непрерывность и выпуклость функции /(х,у) ^к(х,у), к = 1,^] и

линей-

ность функции|лд.(х,у), к = ту +1 ,т2 - Размерность задачи л = пх \ пг.

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

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

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

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

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

- решение непрерывной и целочисленной части задачи одновременно;

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

- решение задачи за относительно небольшое число шагов.

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

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

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

Рис. 1

Процесс дискретизации одной вершины

Алгоритм А1.

1. Построить начальный симплекс.

2. Измерить значения функции в вершинах симплекса.

3. Оценить значение функции в центре симплекса.

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

5. Выбрать и отобразить наихудшие вершины.

6. В новых вершинах симплекса измерить значения функции.

7. Оценить значение функции в центре симплекса.

8. Проверить выполнение успешности шага.

9. При его выполнении перейти к п.4, при невыполнении запомнить наилуч шую вершину с минимальным значением функции и перейти к п. 10.

10. Проверить выполнение условия целочисленности для целочисленных пере менных наилучшей вершины. При выполнении этого условия перейти ] п. 12, при невыполнении перейти к п.11

11. Провести дискретизацию целочисленной части переменных.

12. Поиск прекратить. Запомнить лучшую вершину.

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

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

Алгоритм А2.

1. Построить начальный симплекс.

2. Измерить значения функции в вершинах симплекса.

3. Оценить значение функции в центре симплекса.

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

5. Выбрать и отобразить наихудшие вершины.

6. В новых вершинах симплекса измерить значения функции.

7. Оценить значение функции в центре симплекса.

8. Проверить выполнение успешности шага. При выполнении перейти к п.4, при невыполнении - к и.9.

9. Вернуться к предыдущему симплексу.

10. Произвести сжатие симплекса.

11. Проверить условие останова. При выполнении этого условия перейти п. 15, при невыполнении перейти к п. 12

12. В новых вершинах симплекса измерить значения функции.

13. Оценить значение функции в центре симплекса.

14. Проверить выполнение успешности шага. При выполнении перейти к п. при невыполнении - к п. 9.

15. Запомнить наилучшую вершину с минимальным значением функции.

16. Проверить выполнение условия целочнсленности для целочисленной час переменных лучшей вершины. При выполнении этого условия перейти п. 19, при невыполнении перейти к п. 18.

17. Провести дискретизацию целочисленной части переменных.

18. Поиск прекратить. Запомнить лучшую вершину.

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

Рис.2

Структурная схема алгоритма .A3

Предложен также алгоритм А4, который является аналогом алгоритм АЗ, но использующий метод округления при дискретизации переменны; Алгоритм имеет вид.

Алгоритм А4.

1. Пункты с 1 по 5 совпадают с соответствующими пунктами алгоритма А2

6. Провести дискретизацию целочисленной части переменных.

7. В новых вершинах симплекса измерить значения функции.

8. Оценить значение функции в центре симплекса.

9. Проверить выполнение условия успешности шага. При его выполненш перейти к и. 4, при невыполнении — к п. 10

10. Вернуться к предыдущему симплексу.

11. Произвести сжатие симплекса.

12. Провести дискретизацию целочисленной части переменных.

13. Проверить условие останова. При выполнении этого условия перейти 1 п. 17, при невыполнении перейти к н.14.

14. В новых вершинах симплекса измерить значетм функции.

15. Оценить значение функции в центре симплекса.

16. Проверить выполнение успешности шага. При выполнении перейти ) п.4, при невыполнении - к п.10.

17. Запомнить вершину с минимальным значением функции.

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

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

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

Решаются задачи с различными типами ограничений в следующих постановках.

• Задача частично-целочисленной оптимизации с простыми ограничениями:

пип/(х.У) х.У

при ограничениях ^ ^ ^ (2)

У-{Л,.У2-».,Д'Я2}еКЯ2, у. <= {0,1,2,...}, / = 1,я2

где х - вектор /?, непрерывных переменных, у - векгор п2 целочисленных переменных, Л = {аг[,<72 }, В = {Ь1,Ь2,...,Ь1Ц}-вскторы констант, определяющие нижнюю и верхнюю границы изменения вектора X, А,В еЛЯ| , С-{с},с2,.-.,сп}, /)= {</1,</2>«»><*я3}- векторы констант, определяющие нижнюю и

верхнюю границы изменения у, с,-,*^ е{0,1,2,...}, / —1,«2 • Предполагается непрерывность и выпуклость функции /(х,у). Размерность задачи и = и, + п2 ■

• Задача частично-целочисленной оптимизации с линейными ограничениями типа неравенств:

min ДХ,У)

х,У

при ограничениях (3)

8к(Х>У)~(ак,(х,у))-Ьк, к - 1,/и,

У - (j'l >--ч) 6 И"2, у,- е {0,1,2,...}, /-Л,^

г де х - вектор щ непрерывных переменных, у - вектор п2 целочисленных переменных, ак - вектор размерности п, Ьк - скаляр. Предполагается непрерывность и выпуклость функции /(х,у). Размерность задачи и = л, + п2.

• Задача частично-целочисленной оптимизации с ограничениями типа равенств и неравенств совпадаете (1).

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

При достижении симплексом этого размера определить число ограничений г (1 < г < п), за которые выходят вершины симплекса при попытке произвести шаг, т.е. определить г активных ограничений. Па пересечении этих ограничений расположить симплекс размерности </ = и - г . Затем симплекс размерности с! достроить до симплекса размерности п, выбран, локально оптимальное направление движения в соответствии с правилами алгоритма А2. В случае нарушения ограничений определить локально оптимальное направление смещения (I - мерной грани симплекса и произвести смещение в этом направлении путем отображения необходимого числа вершин [рани. Вершины, не лежащие на активных ограничениях, перемещаются параллельно г активным ограничениям и образуют новый симплекс размерности п.

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

Алгоритм А5.

1. На допустимом множестве построить начальный симплекс.

2. Измерить значения функции в вершинах симнлекса.

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

4. Выбрать и отобразить вершины симплекса.

5. Проверить выполнение ограничений (2). Если новые вершины симплекса не вышли за ограничения, то перейти к п.6, если вышли, то перейти к п.9.

6. В новых вершинах симплекса измерить значения функции.

7. Оцепить значение функции в центре симплекса.

8. Проверить выполнение правила успешности шага. При его выполнении перейти к п.З, при нарушении - к п.9.

9. Вернуться к предыдущему симплексу.

10. Произвести сжатие симплекса.

11. Проверить условие останова. При его выполнении перейти к п. 19, п] невыполнении - к и. 12.

12. В новых вершинах симплекса измерить значения функции.

13. Оценить значение функции в центре симплекса.

14. Проверить условие успешности шага. При его выполнении перейти к и при невыполнении - к п. 9.

15. Проверить выполнение условия достижения некоторого заданного нр межуточного размера симплекса. При его выполнении перейти к и.) при невыполнении - к п.9

16. Определить число нарушаемых ограничений (2).

17. Построить симплекс на пересечении нарушаемых ограничений.

18. Перейти к п.2.

19. Запомнить лучшую вершину и перейти к п.20.

20. Провести дискретизацию переменных.

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

Алгоритм А6, предложенный в диссертации, отличается от алгорит А5 тем, что дискретизация проводится при каждом изменении симплекса, т при отображении, сжатии или построении симплекса на активных огранн ниях. Условие выполнения ограничений обеспечивает метод деформируем конфигураций и при работе метода ветвей и границ выполнение ограничен не требуется.

Для решения задач частично-целочисленного профаммирования с . нейными ограничениями разработана модификация метода зеркальных строений Рыкова.

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

Пусть есть одно активное линейное ограничение (г) = (а1, г) + Ьх = ^(дс, >') < 0 и на N -м шаге одна вершина при отображении нарушила ограничение. Пусть в соответствии с правилами алгоритма на N -м шаге отображается локально-оптимальное количество

вершин симплекса Л"4' , и пусть для определенности вершина гЛГ+1'1 нового симплекса 5,/У+1 нарушила ограничение, т.е.

, N + 1,1, , N + 1,1 Л'Ч 1,1ч п

В этом случае предлагается провести следующие операции.

1. Построить проекцию точки ти такую точку н»^4"1,1 =(л:

м ,„N + 1,1 N+1,1 и . N+1,1 и

II и' -г П-ттЦс-г ||.

с

где с = 0,.у)

Проекция определяется по формуле:

ь,Л'+и = ^Л'41,1 + ((а1,;'4'1 и)1й,)-</1

II«1 II2

2. Построить точку симметричную точке гЛ+1'', относительно активного ограничения. Точка определяется по формуле

3. В точке г*Лц1'' измерить значение /(г.^11,1) и далее считать, ч

4. В остальных новых вершинах симплекса и произвести измерение :и чений функции /(г) и далее действовать по правилам исходного шн ритма безусловной минимизации.

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

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

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

Алгоритм А7, предложенный в диссертационной работе, решает задачу частично-целочисленного программирования (3) в две стадии. Сначала задача решается без учета требования целочисленности переменных, а затем проводится дискретизация с использованием элементов

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

Кроме алгоритма А7 в работе предложены также два других алгоритма с использованием метода зеркальных построений. В этих алгоритмах дискретизация проводится после каждого отображения симплекса или после каждого сжатия. В алгоритме А8 дискретизация целочисленных переменных проводится с использованием элементов метода ветвей и границ, в алгоритме А9 дискретизация проводится с помощью метода округления. Структурная схема алгоритма А8 представлена на рисунке 3.

Поисковые алгоритмы решения задач частично-целочисленного программирования с ограничениями типа равенства и/или неравенства используют метод скользящего допуска.

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

Рис. 3

Структурная схема алгоритма А8

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

В работе предложены еще два алгоритма решения задач (1). Алгоритм All отличается от алгоритма А10 тем, что процесс дискретизации, использующий элементы метода ветвей и границ, проводится после каждого отображения симплекса или после каждого сжатия (растяжения). Таким образом, алгоритм А10 решает непрерывную и целочисленную части задачи одновременно. Алгоритм Л12 аналогичен алгоритму All, однако, процесс дискретизации проводится с помощью метода округления.

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

Для сравнения работоспособности и эффективности различных алгоритмов использованы следующие критерии:

- достигнутое минимальное значение целевой функции;

- количество итераций;

- количество вычислений целевой функции до попадания в окрестности минимума;

- количество вычислений целевой функции в окрестности минимума;

В качестве тестовых функций для задач безусловной и условной от мизации малой и средней размерности были выбраны нелинейные функщ включающая в себя функцию Розенброка и наборы известных нелинсйн тестовых задач частично-целочисленного программирования.

Проведено сравнение предложенных алгоритмов с известными ме-дамп решения задач частично-целочисленной оптимизации (методом лек< кографического перебора, методом декомпозиции, методом случайного i иска MSGA). В результате сравнения показана работоспособность и эфф| тивность разработанных алгоритмов решения задач частич! целочисленного нелинейного программирования. Вычислительный экспе] мент показал, что наиболее эффективными методами являются алгоритм для решения задач безусловной оптимизации, алгоритм А6 для решения дач частично-целочисленной оптимизации с ограничениями простого ти алгоритм А8 для решения задач с линейными ограничениями чипа не венств и алгоритм АН для решения задач с ограничениями типа равен и/или неравенств.

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

достигнутое минимальное значение целевой функции или т ность методов минимизации;

среднее время вычислений для достижения минимума целе функции на один интервал дискретизации; максимальное время вычислений для достижения минимума левой функции в течение всего эксперимента.

Показана работоспособность и эффективность предложенных лоис вых алгоритмов.

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

Параметрическая задача синтеза системы теплообменника является задачей частично-целочисленной оптимизации. В диссертационной работе приведен метод случайного поиска МБОЛ. с помощью которого эту задачу решали ранее. Представлены полученные этим методом результаты. Дано решение параметрической задачи синтеза системы теплообменника с использованием алгоритма Л6. Показаны преимущества алгоритма А6.

Для решения задачи управления температурой потока в химическом реакторе был использован алгоритм АЗ. Показана эффективность нового алгоритма по сравнению с применявшимися ранее алгоритмами.

Заключение

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

Основные результаты диссертации состоят в следующем:

1. Проведен анализ и сформулированы требования к решению задач частично-целочисленного программирования малой и средней размерности.

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

3. Разработана методика исследования предложенных подходов и проведено сравнение с известными методами. Проведено тестирование разработанных алгоритмов, даны сравнительные оценки предложенных методов и показана их эффективность.

4. Разработанные методы использованы для решения задач управления системами с нредиктивным управлением и для решения задачи синтеза теплообменника.

Основные результаты диссертации опубликованы в следующих работах

1. Рыков A.C., Красильникова М.В. Метод деформируемых конфигуращ для решения частично-целочисленных (смешанных) задач нелинейно: программирования. // Международная научно-техническая конференш "Структурная перестройка металлургии: экономика, экология, управлени технология", Новокузнецк, 1998

2. Рыков A.C., Красильникова М.В. Методы деформируемых конфигуращ для решения задачи дискретной оптимизации со смешанными переменными. // Сборник научных трудов. Информационные технологии в образовании и металлургии - М.: МИСиС, 1999, с. 114-118

3. Рыков A.C., Красильникова М.В. Методы деформируемых конфигуращ для безусловных задач дискретной оптимизации со смешанны? переменными. // Математические и экономические модели в оперативш управлении производством. Выпуск 10, М.: Электрика, 1999, с. 4-8.

4. Рыков A.C., Красильникова М.В. Методы деформируемых конфигурац для условных задач дискретной оптимизации со смешанны! переменными. // Математические и экономические модели в оперативго управлении производством. Выпуск 10, М.: Электрика, 1999, с. 8-13.