Математическое моделирование. Курс лекций [Электронный ресурс [для студентов специальностей 130102.65 «Технология геологической разведки» и 210503.03 «Технология и техника разведки месторождений полезных ископаемых» всех форм обучения]]

Министерство образования и науки Российской Федерации Сибирский федеральный университет

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ. КУРС ЛЕКЦИЙ Учебно-методическое пособие

Электронное издание

Красноярск СФУ 2017

УДК 519.6.001.57(07) ББК 22.181я73 М340

Составитель: Карелин Олег Игоревич Шигина Анна Александровна

М340 Математическое моделирование. Курс лекций : учеб.-метод. пособие / сост. : О.И., Карелин, А.А. Шигина. – Электрон. дан. – Красноярск : Сиб. федер. ун-т, 2017. – Систем. требования: PC не ниже класса Pentium I ; 128 Mb RAM ; Windows 98/XP/7 ; Adobe Reader V8.0 и выше. – Загл. с экрана. Содержит основные понятия и методологические вопросы математического моделирования. Рассмотрены основные подходы к построению математических моделей систем различного назначения. Изложены широко применяемые в настоящее время численные методы исследования моделей. Рассмотрены вопросы идентификации математических моделей. Каждая тема снабжена контрольными вопросами. Курс лекций предназначен для студентов специальностей 130102.65 «Технология геологической разведки» и 210503.03 «Технология и техника разведки месторождений полезных ископаемых» всех форм обучения. УДК 519.6.001.57(07) ББК 22.181я73 © Сибирский федеральный университет, 2017

Электронное учебное издание Подготовлено к публикации издательством Библиотечно-издательского комплекса Подписано в свет 19.05.2017. Заказ № 1398 Тиражируется на машиночитаемых носителях Библиотечно-издательский комплекс Сибирского федерального университета 660041, г. Красноярск, пр. Свободный, 82а Тел. (391)206-26-67; http://rio.sfu-kras.ru E-mail: [email protected]

СОДЕРЖАНИЕ Введение…………………………………………………………………….. Лекция 1. Общие сведения о математическом моделировании ………... Лекция 2. Классификация видов моделирования систем ...……………... Лекция 3. Идентификация моделей систем.………………........................ Лекция 4. Линейное программирование ………………………………..... Лекция 5. Динамическое программирование…………………………….. Лекция 6. Построение эмпирических регрессионных моделей ………… Лекция 7. Постановка и классификация задач условной оптимизации… Лекция 8. Численные методы безусловной оптимизации……………….. Библиографический список …………………………………...…………...

3

4 5 11 21 29 52 61 82 88 93

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

4

Лекция 1. ОБЩИЕ СВЕДЕНИЯ О МАТЕМАТИЧЕСКОМ МОДЕЛИРОВАНИИ План лекции 1.1 Основные понятия и определения. 1.2 Обобщенный алгоритм построения математической модели. 1.3 Постановка задачи моделирования в общем виде. 1.1 Основные понятия и определения Система – множество упорядоченных элементов (компонентов), взаимосвязанных друг с другом, образующих целостность или органическое единство и взаимодействующих между собой так, чтобы могла реализоваться функция системы. Система называется сложной, если в ней не хватает ресурсов (главным образом, информационных) для эффективного описания (состояний, законов функционирования) и управления системой - определения, описания управляющих параметров или для принятия решений в таких системах (в таких системах всегда должна быть подсистема принятия решения). Пример. Сложными системами являются, например, химические реакции, если их исследовать на молекулярном уровне; клетка биологического образования, взятая на метаболическом уровне; мозг человека, если его исследовать с точки зрения выполняемых человеком интеллектуальных действий; т.е макроэкономика; человеческое общество - на политико-религиозно-культурном уровне; ЭВМ (особенно пятого поколения) как средство получения знаний; язык - во многих аспектах его рассмотрения. Сложность системы определяется целями и ресурсами (набором задач, которые она призвана решать). Пример. Сложность телекоммуникационной сети определяется: - необходимой скоростью передачи данных; - протоколами, связями и типами связей (например, для селекторного совещания необходима голосовая телеконференция); - необходимостью видеосопровождения. Само понятие сложности системы не является чем-то универсальным, неизменным и может меняться динамически, от состояния к состоянию. При этом и слабые связи, взаимоотношения подсистем могут повышать сложность системы. 5

Система называется большой, если ее исследование или моделирование затруднено из-за большой размерности, т.е. множество состояний системы S имеет большую размерность. Какую же размерность нужно считать большой? Об этом мы можем судить только для конкретной проблемы (системы), конкретной цели исследуемой проблемы и конкретных ресурсов. Большая система сводится к системе меньшей размерности использованием более мощных вычислительных средств (или ресурсов) либо разбиением задачи на ряд задач меньшей размерности (если это возможно). Пример. Это особенно актуально при разработке больших вычислительных систем, например, при разработке компьютеров с параллельной архитектурой или алгоритмов с параллельной структурой данных и с их параллельной обработкой. Управление — такое преобразование поступающей в систему информации и формирование таких управляющих воздействий, при которых обеспечивается достижение (по возможности наилучшее) заданных целей управления Обратная связь — обратное воздействие результатов процесса на его протекание или управляемого процесса на управляющий. передача информации о протекании процесса, на основе которой вырабатывается то или иное управляющее воздействие. Модель – это объект-заместитель объекта-оригинала, обеспечивающий изучение некоторых свойств оригинала. Моделирование – процесс замещения одного объекта другим с целью получения информации о свойствах объекта-оригинала путем изучения объекта-модели. Процесс моделирования включает 3 элемента: субъект, объект исследования, модель объекта. Цели моделирования: 1) оценка – оценить действительные характеристики проектируемой или существующей системы, определить, насколько система предлагаемой структуры будет соответствовать предъявляемым требованиям. 2) сравнение – сравнить конкурирующие системы одного функционального назначения или сопоставить несколько вариантов построения одной и той же системы. 3) прогноз – оценить поведение системы при некотором предполагаемом сочетании рабочих условий.. 6

4) анализ чувствительности – выявить из большого числа факторов, действующих на систему, те, которые в большей степени влияют на ее поведение и определяют ее показатели эффективности. 5) оптимизация – найти или установить такое сочетание действующих факторов и их величин, которое обеспечивает наилучшие показатели эффективности системы в целом. 1-4 – задачи анализа, 5 – задача синтеза. Математической моделью некоторого объекта, процесса или явления будем называть запись его свойств на формальном языке с целью получения нового знания (свойств) об изучаемом процессе путем применения формальных методов. Математическое моделирование позволяет до создания реальной системы (объекта) или возникновения реальной ситуации рассмотреть возможные режимы работы, выбрать оптимальные управляющие воздействия, составить объективный прогноз будущих состояний системы. Является основой интенсивно разрабатываемых автоматизированных систем проектирования, управления и обработки данных. Основная задача математического моделирования – выделение законов в природе, обществе и технике и запись их на языке математики. Например: 1) Зависимость между массой тела m, действующей на него силой F и ускорением его движения а записывается в форме 2-го закона Ньютона: F = m a; 2) Зависимость между напряжением в электрической цепи U, ее сопротивлением R и силой тока I записывается в виде закона Ома: I = U/R. Альтернативой формальному (математическому) подходу является экспериментальный подход. К его недостаткам можно отнести: 1) высокая стоимость подготовки и проведения экспериментов; 2) получение частного знания (знания о конкретном объекте исследования, а не о классе объектов). Модель сложного объекта (процесса, системы) не может быть простой. Из чего следует, что процесс использования математических моделей реальных систем является итерационным процессом, когда последовательно уточняется (дорабатывается) математическая модель и методы решения стоящих задач. Важнейшей характеристикой моделей является их точность, адекватность действительности. При этом важно иметь в виду, что все модели представляют собой приближенное описание реальных объектов (процес7

сов) и поэтому принципиально неточны. Интегральная оценка модели может быть получена путем сравнения результатов моделирования и экспериментальных данных для конкретных объектов или режимов. Для оценки значимости совпадения или несовпадения модельных и экспериментальных результатов широко используются методы математической статистики. Вместе с тем не следует переоценивать результаты такой проверки. Хорошее совпадение модельных и экспериментальных данных, вообще говоря, не доказывает точности модели, а лишь подтверждают ее функциональную пригодность для моделирования. Всегда может быть предложена модель, обеспечивающая лучшее совпадение с экспериментом, но не лучшее описание моделируемого объекта или процесса. 1.2 Обобщенный алгоритм построения математической модели Процедуру построения математической модели реальной системы, процесса или явления можно представить в виде алгоритма. Блок-схема, иллюстрирующая алгоритм построения математической модели, приведена на рис.1.1. 1 Начало

5 Построение внутреннего опис ания

2 Выбор аппарата формализации Нет

3 Построение внешнего описания

Нет

6 Проверка адекватности 7 Идентификация параметров

4 Проверка адекватности

8 Конец

Рис. 1.1 Алгоритм построения модели системы

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

8

3. Построение внешнего описания сводится к поиску области определения (в пространстве входных воздействий) и области значений (в пространстве выхода), размерность которых была определена на этапе 1, и определении соответствия между входными и выходными параметрами. 4,6.Если проверка адекватности показывает, что построенная модель не удовлетворяет предъявляемым к ней требованиям и причиной этого является более сложный характер поведения системы, то производится выбор нового метода математического описания. 5. В случае удачного построенного внешнего описания производится переход к внутреннему описанию, при этом размерность пространства со стояний системы (то есть размерность вектора q ) должна быть минимальной. 7. Определение (идентификация) качественных и количественных характеристик параметров, определяющих функционирование системы. Среди представленных этапов построения математической модели методы идентификации параметров наиболее хорошо разработаны. При их использовании предполагается, что структура системы известна, а неизвестны только значения параметров. Задача параметрической идентификации в этом случае сводится к поиску значений параметров, обеспечивающих минимизацию некоторой функции ошибки. Особое значение на всех этапах построения математической модели является проверка адекватности, непротиворечивости модели и ее достаточности для реализации целей исследования. 1.3 Постановка задачи моделирования в общем виде С развитием системных исследований и расширением экспериментальных методов изучения реальных объектов большое значение приобретают математические методы анализа и синтеза. Подобие и моделирование позволяют по-новому описать реальный процесс и упростить экспериментальное его изучение. Моделирование базируется на некоторой аналогии реального и мысленного эксперимента (выявление влияния изменения химического состава шихты на технико-экономические показатели (TЭП) процесса плавки). Для объяснения реальных процессов выдвигаются гипотезы, с целью их подтверждения ставится эксперимент, т.е. некая процедура организации и наблюдения явлений, которую осуществляют в условиях, близких к реальным или имитирующих их. В основе любого вида моделирования лежит модель, имеющая соответствие, базирующееся на общем качестве, которое 9

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

Организационная структура системы моделирования во многом зависит от сложности модели и степени совершенства средств моделирования. Управляемость модели дает возможность обеспечивать управлении процессом в различных условиях, имитирующих реальные. К этому можно отнести управление технологическим процессом как в нормальном, так и в предаварийном состоянии. Возможность развития модели позволяет создавать мощные системы моделирования для исследования многих сторон функционирования реального объекта. Модель должна быть открытой: обеспечивать включение в ее состав новых подмоделей или подсистем управления (например, подсистем управления энергетическим и тепловым режимами, шихтоподготовкой и выпуском металла и т.д.). Любую модель строят в зависимости от цели моделирования, поэтому одной из основных проблем при моделировании является проблема целевого назначения. При создании АСУ целью оптимизации может быть максимальная производительность, минимум потерь цветных металлов, снижение себестоимости продукции и некоторые другие цели. Контрольные вопросы 1. Что понимается под объектом моделирования? 2. Что такое гипотеза в моделировании? 3. Дайте определение модели. 4. Что такое математическая модель? 5. Приведите пример аналогии в физических процессах. 6. Дайте классификацию процессов как объектов моделирования. Лекция 2. КЛАССИФИКАЦИЯ ВИДОВ МОДЕЛИРОВАНИЯ СИСТЕМ План лекции 2.1 Классификация методов моделирования. 2.2 Основные различия и признаки подходов к моделированию.

11

2.1 Классификация методов моделирования. В основе моделирования лежит теория подобия, согласно которой абсолютное подобие может иметь место лишь при замене одного объекта другим, точно таким же. При моделировании невозможно добиться абсолютного подобия и нужно стремиться к тому, чтобы модель достаточно хорошо отражала исследуемую сторону функционирования объекта (например, процессы восстановления или осаждения металла). Поэтому в качестве одного из признаков классификации видов моделирования можно выбрать степень полноты модели и разделить модели в соответствии с этим признаком на полные, неполные и приближенные. В основе полного моделирования лежит полное подобие, которое проявляется как во времени, так и в пространстве. Для неполного моделирования характерно неполное подобие модели изучаемому объекту. Приближенное моделирование опирается на приближенное подобие, при котором отдельные стороны функционирования реального объекта не моделируются совсем («холодная» модель электролизера). В зависимости от характера изучаемых процессов в системе все виды моделирования могут быть сведены в схему, представленную на рис. 2.1. Детерминированное моделирование отображает детерминированные процессы (т.е. процессы, в которых предполагается отсутствие всяких случайных воздействий); стохастическое моделирование – вероятностные процессы и события. Статическое моделирование служит для описания поведения объекта в какой-либо момент времени (в статике). Динамическое моделирование отражает закон изменения состояния объекта во времени. Дискретное моделирование служит для описания дискретных процессов. Непрерывное моделирование позволяет отразить непрерывные во времени процессы. Дискретно-непрерывное моделирование используют, когда необходимо выделить наличие как дискретных, так и непрерывных процессов. Линейное моделирование применяют для описания линейных процессов, т.е. процессов, связь между входными и выходными параметрами которых линейна. Нелинейное моделирование предназначено для описания нелинейных процессов, в которых связь между выходом и входом системы нелинейна. В зависимости от формы представления объекта можно выделить мысленное и реальное моделирование. При реальном моделировании используется возможность исследования характеристик либо на реальном 12

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

Рис. 2.1 Классификация видов моделирования систем

13

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

мого реального объекта. Математическое моделирование для исследования характеристик процесса функционирования систем можно разделить на аналитическое, имитационное и комбинированное. Для аналитического моделирования характерно то, что процесс функционирования элементов системы (физико-химические превращения, загрузка, выпуск, тепло- и массоперенос) описывается в виде некоторых функциональных соотношений (алгебраических, дифференциальных, конечноразностных) или логических условий. Аналитическая модель может быть исследована различными методами: - аналитическим, когда искомые характеристики пытаются найти в общем виде; - численным, когда, не зная решения в общем виде, стремятся получить числовые результаты при конкретных начальных условиях; - качественным, когда, не имея решения в явном виде, можно установить некоторые его свойства по самой модели. Наиболее полное исследование процесса функционирования системы можно провести, если известны явные зависимости, связывающие искомые характеристики с начальными условиями, параметрами и переменными системы S. Однако такие зависимости удается получить только для сравнительно простых систем. При усложнении систем исследование их аналитическим методом наталкивается на значительные трудности, которые часто бывают непреодолимыми. Поэтому, желая использовать аналитический метод, в этом случае идут на существенное упрощение первоначальной модели, чтобы иметь возможность изучить хотя бы общие свойства системы. Такое исследование на упрощенной модели аналитическим методом помогает получить ориентировочные результаты для определения более точных оценок другими методами. Численный метод позволяет исследовать по сравнению с аналитическим методом более широкий класс систем, но при этом полученные решения носят частный характер. Численный метод особенно эффективен при использовании ЭВМ. В отдельных случаях исследования системы могут удовлетворить и те выводы, которые можно сделать при использовании качественного метода анализа математической модели. Такие качественные методы широко используются, например, в теории автоматического управления для оценки эффективности различных вариантов систем управления. В настоящее время распространены методы машинной реализации исследования характеристик процесса функционирования больших систем. 15

Для реализации математической модели на ЭВМ необходимо построить соответствующий моделирующий алгоритм. Аналитический метод широко применяется для простых систем, с усложнением систем использование этого метода возможно при упрощении первоначальной модели. Численный метод по сравнению с аналитическим позволяет исследовать более широкий класс систем, но при этом полученные решения носят частный характер. Численный метод особенно эффективен при использовании ЭВМ. При имитационном моделировании имитируются элементарные явления, составляющие процесс, с сохранением их логической структуры и последовательности протекания во времени. Основным преимуществом имитационного моделирования перед аналитическим является возможность решения более сложных задач. Имитационные модели позволяют относительно просто учитывать следующие факторы: наличие дискретных и непрерывных элементов, нелинейные характеристики элементов системы, многочисленные случайные воздействия. Основным преимуществом имитационного моделирования, по сравнению с аналитическим, является возможность решения более сложных задач. Имитационные модели позволяют достаточно просто учитывать такие факторы, как наличие дискретных и непрерывных элементов, нелинейные характеристики элементов системы, многочисленные случайные воздействия и др., которые часто создают трудности при аналитических исследованиях. В настоящее время имитационное моделирование – наиболее эффективный метод исследования больших систем, а часто и единственный практически доступный метод получения информации о поведении системы, особенно на этапе ее проектирования. Когда результаты, полученные при воспроизведении на имитационной модели процесса функционирования системы S, являются реализациями случайных величин и функций, тогда для нахождения характеристик процесса требуется его многократное воспроизведение с последующей статистической обработкой информации и целесообразно в качестве метода машинной реализации имитационной модели использовать метод статистического моделирования (Монте-Карло). Данный метод применяется для численного решения аналитической задачи. Особенно эффективны статистические методы при неполной информации о процессе. Затем этот прием стали применять и для машинной имитации с целью исследования характеристик процессов функционирования систем, подверженных случайным воздействиям, т. е. появился метод статистиче16

ского моделирования. Таким образом, методом статистического моделирования будем в дальнейшем называть метод машинной реализации имитационной модели, а методом Монте–Карло – численный метод решения аналитической задачи. Метод имитационного моделирования позволяет решать задачи анализа больших систем S, включая задачи оценки: вариантов структуры системы, эффективности различных алгоритмов управления системой, влияния изменения различных параметров системы. Имитационное моделирование может быть положено также в основу структурного, алгоритмического и параметрического синтеза больших систем, когда требуется создать систему, с заданными характеристиками при определенных ограничениях, которая является оптимальной по некоторым критериям оценки эффективности. При решении задач машинного синтеза систем на основе их имитационных моделей помимо разработки моделирующих алгоритмов для анализа фиксированной системы необходимо также разработать алгоритмы поиска оптимального варианта системы. Далее в методологии машинного моделирования будем различать два основных раздела: статику и динамику, – основным содержанием которых являются соответственно вопросы анализа и синтеза систем, заданных моделирующими алгоритмами. Комбинированное моделирование позволяет объединить достоинства аналитического и имитационного моделирования. При этом часть подсистем описывается аналитическими моделями, а часть – имитационными. При построении комбинированных моделей проводится предварительная декомпозиция процесса функционирования объекта на составляющие подпроцессы и для тех из них, где это возможно, используются аналитические модели, а для остальных подпроцессов строятся имитационные модели. Такой комбинированный подход позволяет охватить качественно новые классы систем, которые не могут быть исследованы с использованием только аналитического и имитационного моделирования в отдельности. 2.2 Основные различия и признаки подходов к моделированию С развитием техники и проникновением в глубь процессов, протекающих в реальных системах, возрастает техническая оснащенность современного научного эксперимента. Он характеризуется широким использованием средств автоматизации проведения, применением весьма разнообразных средств обработки информации, возможностью вмешательства человека в процесс проведения эксперимента, и в соответствии с этим поя17

вилось новое научное направление — автоматизация научных экспериментов. Отличие эксперимента от реального протекания процесса заключается в том, что в нем могут появиться отдельные критические ситуации и определяться границы устойчивости процесса. В ходе эксперимента вводятся новые факторы и возмущающие воздействия в процессе функционирования объекта. Одна из разновидностей эксперимента — комплексные испытания, которые также можно отнести к натурному моделированию, когда вследствие повторения испытаний изделий выявляются общие закономерности о надежности этих изделий, о характеристиках качества и т. д. В этом случае моделирование осуществляется путем обработки и обобщения сведений, проходящих в группе однородных явлений. Наряду со специально организованными испытаниями возможна реализация натурного моделирования путем обобщения опыта, накопленного в ходе производственного процесса, т. е. можно говорить о производственном эксперименте. Здесь на базе теории подобия обрабатывают статистический материал по производственному процессу и получают его обобщенные характеристики. С точки зрения математического описания объекта и в зависимости от его характера модели можно разделить на модели аналоговые (непрерывные), цифровые (дискретные) и аналого-цифровые (комбинированные). Под аналоговой моделью понимается модель, которая описывается уравнениями, связывающими непрерывные величины. Под цифровой понимают модель, которая описывается уравнениями, связывающими дискретные величины, представленные в цифровом виде. Под аналого-цифровой понимается модель, которая может быть описана уравнениями, связывающими непрерывные и дискретные величины. Особое место в моделировании занимает кибернетическое моделирование, в котором отсутствует непосредственное подобие физических процессов, происходящих в моделях, реальным процессам. В этом случае стремятся отобразить лишь некоторую функцию и рассматривают реальный объект как «черный ящик», имеющий ряд входов и выходов, и моделируют некоторые связи между выходами и входами. Чаще всего при использовании кибернетических моделей проводят анализ поведенческой стороны объекта при различных воздействиях внешней среды. Таким образом, в основе кибернетических моделей лежит отражение некоторых информационных процессов управления, что позволяет оценить поведение реального объекта. Для построения имитационной модели в этом случае необходимо выделить исследуемую функцию реального объекта, попы18

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

Аналитические

Имитационные

Теоретические

Эмпирические

Теоретические

Линейные

Нелинейные

Нелинейные

Статические

Динамические

Динамические

Детерминированные

Стохастические

Детерминированные

Аналитически разрешимые

Численно разрешимые

Численно разрешимые

Рис. 2.2 Классификации математических моделей

Все математические модели по использованному формальному языку можно разбить на аналитические и имитационные. Аналитические – модели, в которых используется стандартный математический язык. Имитационные – модели, в которых использован специальный язык моделирования или универсальный язык программирования. Аналитические модели могут быть записаны в виде формул или уравнений. Если какой-либо процесс не может быть описан в виде аналитической модели, его описывают с помощью спец. алгоритма или программы. Такая мо19

дель является имитационной. Аналитические модели в свою очередь разбиваются на теоретические и эмпирические модели. Теоретические модели отражают реальные структуры и процессы в исследуемых объектах, то есть, опираются на теорию их работы. Эмпирические модели строятся на основе изучения реакций объекта на изменение условий окружающей среды. При этом теория работы объекта не рассматривается, сам объект представляет собой так называемый «черный ящик», а модель – некоторую интерполяционную зависимость. Эмпирические модели могут быть построены на основе экспериментальных данных. Эти данные получают непосредственно на исследуемых объектах или с помощью их физических моделей. По форме описания аналитические модели подразделяются на линейные и нелинейные. Если все входящие в модель величины не зависят от времени, то имеем статическую модель объекта или процесса, в противном случае получаем динамическую модель. В детерминированных моделях все взаимосвязи, переменные и константы заданы точно, что приводит к однозначному определению результирующей функции. Если часть или все параметры, входящие в модель по своей природе являются случайными величинами или случайными функциями, то модель относят к классу стохастических моделей. В стохастических моделях задаются законы распределения случайных величин, что приводит к вероятностной оценке результирующей функции. Если аналитическое исследование может быть доведено до конца, модели называются аналитически разрешимыми. В противном случае говорят о численно разрешимых аналитических моделях. Контрольные вопросы 1. Дайте общую классификацию видов моделирования систем. 2. Чем отличаются стохастические процессы от детерминированных? 3. Дайте характеристику статическим и динамическим моделям. 4. Чем отличаются мысленное от реального моделирования? 5. Охарактеризуйте дискретные, дискретно-непрерывные и непрерывные модели. 6. Чем отличаются наглядное, натурное, физическое, символическое, математическое моделирование? 7. Дайте классификацию математическим моделям. 20

Лекция 3. ИДЕНТИФИКАЦИЯ МОДЕЛЕЙ СИСТЕМ 3.1 Основные понятия идентификации 3.2 Структурная идентификация 3.3 Параметрическая идентификация 3.4 Методы идентификации, их характеристика 3.1 Основные понятия идентификации Под идентификацией объектов понимается построение оптимальных в некотором смысле математических моделей по реализации их входных и выходных параметров. Для управления объектом необходимо иметь модель в виде математического описания, устанавливающего связь между входными и выходными переменными в форме, на основе которой может быть выбран закон управления, обеспечивающий заданное функционирование объекта. Взаимодействие объекта с окружающей средой поясним с помощью простейшей схемы (рис. 3.1). Воздействия внешней среды на объект в обобщенном виде изображены стрелками, направленными к объекту. Объект воздействует на f окружающую среду. Это воздействие показано стрелкой, направленной от объекта и обозначенной через y. Величину y принято называть выходным воздействием или выходной величиной объекта.

Рис. 3.1 Взаимодействие объекта с окружающей средой

Получаемое описание должно давать правило преобразования воздействия на объект u в реакцию объекта у. Переменные u и y могут представлять собой функции одинаковых или разных аргументов. Преобразование одной функции в другую производится оператором, который определяет совокупность математических или логических операций: y(t)=A(f)u(t)

21

где A(f) – оператор, зависящий от возмущений (операторных воздействий); y(t) – вектор выходных координат объекта; u(t) – вектор управления (входа). В качестве примера можно назвать операторы дифференцирования, интегрирования и т. п. Для стационарных линейных одномерных объектов оператор может быть задан в виде дифференциального уравнения или системы дифференциальных уравнений первого порядка, интегральной свертки, частотной характеристики объекта. На практике объекты стремятся описывать линейными стационарными моделями, хотя в действительности все объекты в той или иной мере обладают свойствами нелинейности, нестационарности, распределейности, стохастичности. После формулировки целей управления необходимо выделить объект управления из среды, т. е. определить границы объекта и установить его взаимодействие со средой. Последнее характеризуется моделью возмущений. Далее строится структура и проводится идентификация параметров модели объекта. В процедуре синтеза управления, являющейся оптимизационной задачей, модель объекта выступает как ограничения. С помощью же модели возмущений можно оценить некоторые качественные показатели управления. Комплекс задач при идентификации модели объекта разделяется на три этапа: на первом этапе выбирается структура модели по результатам изучения объекта или по имеющимся априорным сведениям, на втором этапе - критерий близости (подобия) модели и объекта, на третьем этапе по экспериментальным данным определяются параметры модели исходя из выбранного критерия. Задача идентификации заключается в количественной оценке степени идентичности модели реальному объекту. Оценка делается на основе сравнения истинной характеристики объекта F0 (рис. 3.2), представленной его выходными параметрами Y0(t), и оценки Fм этой характеристики, описываемой выходными переменными Yм, математической модели, зависящими от входных данных Х(t).

22

Рис. 3.2 Структурная схема процесса идентификации

Критерием идентичности модели является минимум её ошибки q, вычисляемой чаще всего по формуле:

Идентификация может быть адаптивной (подстраиваемой, или обучаемой) и неадаптивной (неподстраиваемой). При неадаптивной идентификации выбираются или рассчитываются коэффициенты модели и в дальнейшем эти коэффициенты не изменяются. Основным свойством адаптивной идентификации является то, что коэффициенты математической модели по мере необходимости изменяются или подстраиваются. В зависимости от априорной (исходной) информации об объекте различают структурную и параметрическую идентификацию. Предметом структурной идентификации является определение вида функции Yтеор, связывающей входные переменные Х. Структурная идентификация включает в себя: 1) постановку задачи; 2) выбор структуры модели и её математическое описание; 3) исследование модели. На этапе параметрической идентификации выполняется экспериментальная проверка модели. Существующие представления об объекте и его выходные параметры отражаются в виде определенной функции Y(Х, b) с неизвестными коэффициентами B = (b1, …, bn). Процедуры же конкретной реализации функции основываются на функциональном представлении зависимости выходных переменных модели от входных. Задача идентификации ставится как задача оптимизации Q(B) → min, Y ∈ F0 (Fм), 23

где Q – мера расхождения между выходными экспериментальными параметрами объекта и выходными переменными выбираемой модели (суммарная невязка). При структурной идентификации Fм(F0) – класс операторов, среди которых выбирается структура модели. При параметрической идентификации Fм(F0) – допустимая область в пространстве внутренних параметров Y модели. 3.2 Структурная идентификация Выбор структуры модели и её математическое описание осуществляются с учетом характера протекания процесса как объекта моделирования. Непрерывные металлургические процессы происходят при непрерывной загрузке материалов и выгрузке продуктов переработки (процесс спекания глинозема, электролиз алюминия, плавка сульфидных руд в печах и т.д.). Полунепрерывные процессы характеризуются непрерывной загрузкой материала в течение какого-то времени проведения процесса, отключением агрегата и выпуском продуктов переработки. Периодические (циклические) процессы связаны с разовой загрузкой материалов, проведением технологического процесса и выгрузкой готовых продуктов переработки (выращивание монокристаллов кремния, обжиг керамики). Для определения структуры модели необходимо решить две задачи. 1. Выделение входных и выходных параметров объекта по степени их влияния на конечный целевой показатель. При построении структуры модели в неесообразно включать не все входные и управляющие параметры, а только те, которые оказывают решающее влияние на выходную переменную. Не следует вводить в модель несущественные параметры, так как это приводит к значительному усложнению модели. 2. Определение характера связи между входными и выходными параметрами, т.е. выбор класса операторов Fм. По характеру связи математические модели делят на линейные и нелинейные. Линейные модели используются для описания линейных процессов, т.е. процессов, в которых связь между входной и выходной переменными характеризуется линейной зависимостью. Нелинейные модели применяются для описания нелинейных процессов, т.е. процессов, в которых связь между входной и выходной переменными характеризуется нелинейной зависимостью. 24

Исследование модели на адекватность объекту осуществляется с помощью анализа остатков модели 3.3 Параметрическая идентификация Целью параметрической идентификации является уточнение (подстройка) внутренних параметров, т.е. коэффициентов математической модели в тех случаях, когда с помощью структурной идентификации не удается достичь необходимой адекватности модели реальному объекту. Для стохастических объектов предполагается, что свойства случайной составляющей не зависят от входной переменной Х, т.е. полностью оцениваются определенной плотностью вероятности, в качестве которой часто принимают плотность нормального закона распределения. После структурной идентификации, при которой неизвестная функция объекта Y(Х) представляется в виде известной функции с неизвестными параметрами Y(Х, b), осуществляется экспериментальная проверка модели. Для уточнения коэффициентов решается следующая оптимизационная задача. Образуются невязки выходных параметров модели и объекта на каждом i-м измерении, называемые локальными невязками: qi(b) = Yi – Y(x, b) i = 1, ..., n. Оцениваемые параметры выбираются таким образом, чтобы все эти невязки были минимальны по модулю, т.е. решается задача минимизации n функций: qi(b) → min, i = 1, …, n, где вектор b может принимать любые значения. Эта задача является многокритериальной и может быть заменена однокритериальной задачей минимизации суммарной невязки Q(b) → min, ЛАБОРАТОРНАЯ РАБОТА 6. ИДЕНТИФИКАЦИЯ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ НА ВСЕМ ПРОСТРАНСТВЕ ВЕКТОРОВ B .

25

На практике используют какой-либо из следующих критериев (рис. 3.3):

Рис. 3.3 Критерии идентификации

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

не превышает 5 % от суммы квадратов экспериментальных Yi выходного параметра объекта, то модель считается адекватной. 3.4 Методы идентификации, их характеристика К выбору метода идентификации нельзя подойти однозначно, поскольку в самой постановке задачи заранее предполагается неопределенность (неполнота знаний об объекте, ограничения в наблюдениях объекта во времени и т. п.). По способу тестирования исследуемого объекта методы параметрической идентификации делятся на активные и пассивные (рис. 3.4). 26

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

Рис. 3.4 Методы параметрической идентификации

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

Требуемая точность анализа может быть достигнута дополнением детерминированных алгоритмов обработки статистическим усреднением (сглаживанием) получаемых результатов. По признаку временных затрат методы идентификации разделяются на оперативные и ретроспективные. При оперативной идентификации обеспечивается отслеживание меняющихся параметров объекта. При ретроспективной идентификации значительно упрощают условия решения задачи идентификации. В этом случае можно многократно обращаться к накопленным экспериментальным данным и подбирать наиболее эффективные алгоритмы их анализа. Важной особенностью при идентификации является наличие (разомкнутая схема) или отсутствие процедур сравнения получаемой модели с объектом (замкнутая схема). Результатом решения задачи идентификации является математическая модель. При этом полученная модель адекватна объекту по поведению в соответствии с выбранным при идентификации критерием подобия. Контрольные вопросы 1. В чем состоит задача идентификации? 2. Опишите структурную схему процесса идентификации. 3. Что является критерием адекватности модели и объекта? 4. Что такое адаптивная и неадаптивная идентификация? 5. Что является предметом структурной идентификации? 6. Какие задачи необходимо решить при выборе структуры объекта? 7. Какова цель параметрической идентификации? 8. Что такое функция локальной невязки? 9. Какие критерии могут быть использованы в качестве суммарной невязки? 10. При каком значении суммарной невязки модель считается адекватной?

28

Лекция 4. ЛИНЕЙНОЕ И НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ План лекции 4.1 Постановка задачи линейного программирования. 4.2. Теория двойственности. 4.3. Постановка задачи нелинейного программирования 4.1 Постановка задачи линейного программирования. Математическая дисциплина, которая является теоретической основой решения многих задач управления и планирования названа математическим программированием. Предметом изучения дисциплины являются количественные характеристики различных экономических процессов, протекающих в промышленном производстве, сельском хозяйстве, торговле и прочее, изучение их взаимосвязей на основе экономико-математических методов и моделей. Математическое программирование – это математическая дисциплина, которая занимается изучением экстремальных задач и разработкой методов их решения. Экстремальная задача заключается в нахождении наибольшего (наименьшего) значения числовой (вещественной) функции на определенном множестве и хотя бы одной точки этого множества, в которой функция и принимает своё наибольшее (наименьшее) значение. Общая постановка задачи математического программирования: вычислить max(min) f ( x1 , x2 ,..., xn ) (4.1) при условиях



(4.2)

x1 , x2 ,..., xn  0 ,

(4.3)

i ( x1 , x2 ,..., xn ) , , }bi , i  1, m ;

где f ,i - заданные функции, bi - действительные числа.

Функция (4.1) называется целевой функцией или функцией цели; условия (4.2) – специальными ограничениями задачи математического программирования; условия (4.3) – общими ограничениями задачи математического программирования. В зависимости от свойств функций f , i математическое программирование можно рассматривать как ряд самостоятельных дисциплин. 29

Признаки классификации задач математического программирования: 1) по типу данных: определенные (детерминированные), случайные; 2) по характеру изменения переменных: переменные непрерывные, дискретные (целочисленные); 3) по характеру взаимосвязей между переменными: линейные, нелинейные. В таблице 4.1 приведем основную классификацию задач математического программирования. Таблица 4.1 – Основная классификация задач математического программирования Исходные данные

Переменные

Зависимость

Определенные

Непрерывные

Линейная

Целочисленные

Линейная

Непрерывные/ целочисленные Непрерывные

Нелинейные

Случайные

Линейные

Раздел математического программирования Линейное программирование Целочисленное программирование Нелинейное программирование Стохастическое программирование

Линейное программирование – это метод решения оптимизационных задач, в моделях которых целевые функции и ограничения строго линейны. Линейное программирование успешно применяется в различных сферах для решения, прежде всего, экономических и управленческих задач (военной области, промышленности, сельском хозяйстве, транспортной отрасли, здравоохранении и др., а также в социологических науках). Модель задачи линейного программирования может быть записана в одной из следующих форм: Общая форма max(min) z  c1 x1  c2 x2  ...  cn xn ; а11х1  а12 х2  ...  а1n xn  b1 ,  a21x1  a22 x2  ...  a2 n xn  b2 , ...  ak1 x1  ak 2 x2  ...  akn xn  bk , a x  a k 1, 2 x 2  ...  a k 1, n x n  bk 1 ,  k 1,1 1 ...  am1 x1  am 2 x2  ...  amn xn  bm , x1 , x2 ,..., xn  0.

Симметричная, или стандартная форма задачи линейного программирования 30

max z  c1 x1  c2 x2  ...  cn xn ;

min z  c1 x1  c2 x2  ...  cn xn ;

а11х1  а12 х2  ...  а1n xn  b1 , a x  a x  ...  a x  b ,  21 1 22 2 2n n 2  ... am1 x1  am 2 x2  ...  amn xn  bm , x1 , x2 ,..., xn  0.

а11х1  а12 х2  ...  а1n xn  b1 , a x  a x  ...  a x  b ,  21 1 22 2 2n n 2  ... am1 x1  am 2 x2  ...  amn xn  bm , x1 , x2 ,..., xn  0.

Каноническая, или основная форма задачи линейного программирования max z  c1 x1  c2 x2  ...  cn xn ; а11х1  а12 х2  ...  а1n xn  b1 , a x  a x  ...  a x  b ,  21 1 22 2 2n n 2  ... am1 x1  am 2 x2  ...  amn xn  bm , x1 , x2 ,..., xn  0.

Определение 1 Совокупность чисел ( x1 , x2 ,..., xn ), удовлетворяющих ограничениям задачи линейного программирования, называется допустимым решением задачи линейного программирования или опорным планом. Определение 2 Множество всех допустимых решений задачи линейного программирования называется областью (множеством) допустимых решений. Определение 3 Допустимое решение, при котором целевая функция задачи линейного программирования принимает наибольшее (наименьшее) значение, называется оптимальным решением задачи линейного программирования ( x1* , x2* , ..., xn* ) или оптимальным планом. Существуют преобразования, позволяющие из одной формы задачи линейного программирования получать любую другую. В связи с этим, формы задач линейного программирования считаются эквивалентными. Идея перехода от общей формы задачи линейного программирования к канонической форме заключается в преобразовании ограничения в виде неравенства в уравнение путем добавления неотрицательных переменных, которые одновременно включаются в целевую функцию с коэффициентом равным нулю. При необходимости задачу на нахождение максимума целевой функции z можно заменить задачей на минимум новой целевой функции, и наоборот, воспользовавшись следующим равенством min z= - max (-z).

31

 

Если дано неравенство вида аi1 х1  аi 2 х2  ...  аin xn  bi , то необходимо ввести в левую часть неравенства дополнительную (балансовую) неотри   

цательную переменную хn1  0 : аi1 х1  аi 2 х2  ...  аin xn   xn1  bi . Каждая переменная задачи имеет определенный экономический смысл, в том числе и вводимые дополнительные переменные. Дополнительные переменные в задаче «об оптимальном использовании ресурсов» показывают количество неизрасходованного ресурса соответствующего вида. В задаче «о диете» эти переменные характеризуют объем потребления соответствующего вещества, превышающего норму. Таким образом, вводимые дополнительные переменные не могут принимать отрицательных значений. Пример. Привести к канонической форме задачу линейного программирования: найти минимум линейной функции z  3x1  x2  2 x3  x1  2 x2  3 x3  5,  3 x  x  5 x3  4, при условиях  1 2 2 x1  3 x2  7 x3  8, x1 , x2 , x3  0.

Решение. Начнем с преобразования смешанной системы ограничений в систему уравнений. Первое ограничение является уравнением, поэтому не требует изменений. Необходимо перейти для второго и третьего ограничения от вида неравенства к виду уравнения. Для этого введем неотрицательные «балансовые» переменные x4 и x5 в левые части неравенств со знаками «плюс» или «минус» в зависимости от знака неравенства. Получим систему ограничений в следующем виде  x1  2 x2  3 x3  5,  3 x1  x2  5 x3  х4  4, 2 x  3 x  7 x  х  8, 2 3 5  1 x1 ,..., x5  0.

Переход к задаче максимизации линейной функции осуществляется путем введения новой функции из равенства z1   z  3x1  x2  2 x3 Итак, каноническая форма задачи линейного программирования имеет вид: найти максимум функции z1  3x1  x2  2 x3

32

 x1  2 x2  3 x3  5,  3 x  x  5 x3  х4  4, при условиях  1 2 2 x1  3 x2  7 x3  х5  8, x1 ,..., x5  0.

Геометрическая интерпретация задачи линейного программирования. Графический метод решения задачи линейного программирования Рассмотрим геометрическую интерпретацию задачи линейного программирования в двумерном пространстве. Построения на плоскости отличаются своей наглядностью. max(min) z  c1 x1  c2 x2 ; а11х1  а12 х2  b1 , a x  a x  b , 22 2 2  21 1 ...  ai1 x1  ai 2 x2  bi , ...  a m1 x1  am 2 x2  bm , x1 , x2  0.

Рассмотрим геометрическую интерпретацию области допустимых решений. Каждое из неравенств системы ограничений задачи геометрически определяет полуплоскость, содержащую граничные прямые аi1х1  аi 2 х2  bi , i  1, m и расположенную по одну сторону от неё. Для определения полуплоскости, являющейся решением неравенства, необходимо выбрать точку с известными координатами на плоскости. Выбранная точка не должна принадлежать граничной прямой. Координаты этой точки требуется подставить в исследуемое неравенство. Если после подстановки координат точки в неравенство будет получено справедливое неравенство, то полуплоскость, определенная исследуемым неравенством, содержит данную точку. Иначе, полуплоскость, определенная исследуемым неравенством не содержит данную точку. Условия вида x1 , x2  0 определяют полуплоскости, соответственно, с граничными прямыми x1  0, x2  0 . Неравенства x1 , x2  0 показывают, что множество допустимых решений задачи будет располагаться в первом квадранте, т.е. выше оси x1 и правее оси x2 .

33

Система неравенств, если она совместна, определяет пересечение этих полуплоскостей. Оно может представлять собой выпуклую многоугольную область, отрезок, луч, одну точку или быть пустым множеством. Перейдем к геометрической интерпретации целевой функции. Уравнение z  c1 x1  c2 x2 при фиксированном значении z=h ( h const ) определяет на плоскости прямую c1 x1  c2 x2  h . При изменении h получаем семейство параллельных прямых, которое называется линиями уровня. В каждой точке этой прямой (линии уровня) целевая функция принимает фиксированное значение, равное h. Рассмотрим функцию z  f ( x1, x2 ) , дифференцируемую в некоторой точке M ( x1, x2 ) . Определение Градиентом функции z  f ( x1, x2 ) в точке M ( x1, x2 ) называется вектор, координаты которого равны соответственно частным производным

z z в этой точке. , x1 x2

 z z   . ;  x1 x2 

Для обозначения градиента используется символ grad z  

Градиент показывает направление, вдоль которого в данной точке функций имеет максимальную скорость роста, а длина его характеризует абсолютную величину скорости роста. Вектор-градиент целевой функции  z z    c1, c2  перпендикулярен к линиям уровня и показыс  grad z ( x)   ;  x  x 2  1

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

ции z , и в направлении вектора - с при поиске минимума функции z (рис. 4.1). Рассмотрим ситуацию, когда исходная линия уровня и многоугольник допустимых решений не пересекаются, на многоугольник допустимых  решений указывает вектор с . При параллельном смещении исходной ли нии уровня в направлении вектора с первая общая точка с многоугольником решений определяет точку минимума целевой функции z , а последняя общая точка – точку максимума целевой функции z (рис. 4.2).

Рис. 4.1 Многоугольник допустимых решений и исходная линия уровня  пересекаются, вектор с лежит во втором квадранте

Рис. 4.2 Многоугольник допустимых решений и исходная линия уровня не  пересекаются, вектор с лежит в первом квадранте

В процессе решения задачи линейного программирования возможны случаи, когда система ограничений задачи линейного программирования несовместна (рис. 4.3) и задача решений не имеет; целевая функция на множестве допустимых решений неограниченно возрастает или неограни35

ченно убывает (рис. 4.4); целевая функция принимает экстремальное значение в любой точке некоторого отрезка (рис. 4.5).

Рис. 4.3 Система ограничений задачи линейного программирования несовместна

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

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

Если целевая функция задачи линейного программирования на множестве допустимых решений неограниченно возрастает, то ответ записывается в следующем виде z max   . При неограниченном убывании целевой функции на множестве допустимых решений, в качестве ответа к задаче принимают значение zmin   .

36

Рис. 4.5 Целевая функция принимает экстремальное значение в любой точке некоторого отрезка: минимальное значение – отрезок АВ, максимальное значение – отрезок CD

Если целевая функция принимает экстремальное значение на отрезке, то задача имеет бесчисленное множество решений, поскольку отрезок содержит бесчисленное множество точек. Графическим метод решения применяется для неканонических форм задач линейного программирования с двумя переменными. Этапы решения задачи линейного программирования графическим методом рассмотрим на примере Пример. max z  2 x1  3x2 ;  х1  3х2  15,  3х1  х2  13, х1 , х2  0.

Решение. Построим систему координат. По горизонтальной оси откладывают значения переменной x1 , а по вертикальной – значения переменной x2 . Этап 1. Строим прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств. Границей полуплоскости x1  3x2  15 является прямая x1  3x2  15 . Рассмотрим первое уравнение x1  3x2  15 , обозначим его цифрой (I) и выразим переменную х2 через переменную х1 . В результате преобразова1 3

ний получим следующее уравнение прямой х2  5  х1 . Данная прямая проходит через точки с координатами (0;5) и (6;3). Построим прямую на графике (рис. 9). 37

Для второго уравнения 3x1  x2  13 , обозначенного цифрой (II), выражение переменной х2 через переменную х1 примет следующий вид х2  13  3х1 . Прямая (II) проходит через точки с координатами (3;4) и (4;1).

Эту прямую также построим на графике.

 Рис. 4.6 Многоугольник допустимых решений, исходная линия уровня и вектор с задачи

Этап 2. Находим полуплоскости, определяемые каждым из ограничений задачи. Рассмотрим неравенство x1  3x2  15 . Прямая (I) делит всю плоскость на две части и рассматриваемое неравенство определяет только одну из них. Для определения полуплоскости, заданной неравенством возьмем контрольную точку, не принадлежащую прямой (I), с известными координатами, например точку О(0;0). Координаты контрольной точки подставим в неравенство x1  3x2  15 и получим выражение вида 0  3  0  15 . Неравенство выполняется, координаты контрольной точки удовлетворяют ему, следовательно, полуплоскость, которой принадлежит точка О, и определяется исследуемым неравенством x1  3x2  15 . На рисунке полуплоскость, заданную неравенством x1  3x2  15 , отмечаем короткими штрихами. Аналогично, для исследования неравенства 3x1  x2  13 выберем, в качестве контрольной точке, вновь точку О(0;0). После подстановке координат указанной точки, получаем верное неравенство 3  0  0  13 . Неравенство 3x1  x2  13 задает ту полуплоскость, которой принадлежит контрольная точка О(0;0). Отметим короткими штрихами допустимую полуплоскость. 38

Условие неотрицательности переменных x1, x2  0 требует рассмотрения той части многоугольника решений, которая находится в первой координатной четверти, т.е. выше оси x1 и правее оси x2 . Этап 3. Находим многоугольник решений как часть плоскости, которая одновременно удовлетворяет требованиям первого, второму неравенства и условию неотрицательности. В нашем случае, это выпуклый многоугольник ОАВС – область допустимых решений данной системы неравенств. Этап 4. Строим исходную линию уровня z  0 . Прямая примет вид 2 x1  3х2  0 . Выразим переменную х2 через переменную х1 и получим 2 3

равенство х2   х1 . Эта прямая проходит через точки с координатами (0;0) и (3;-2).   Этап 5. Строим вектор с  (с1 , с2 ) . Вектор с =(2;3) перпендикулярен исходной линии уровня z  0 и указывает направление, в котором эта функция возрастает с наибольшей скоростью. Этап 6. Определяем точку, в которой целевая функция z принимает максимальное значение. Для этого исходную линию уровня передвигаем в  направлении вектора с . При движении в этом направлении последней общей точкой прямой с многоугольником решений является точка В. В этой точке целевая функция принимает максимальное значение. Этап 7 Определяем координаты точки B и вычисляем значение целевой функции в этой точке. Точка B лежит на пересечении прямых (I) и (II). Для нахождения координат точки В решим систему уравнений  х1  3х2  15( I ),   3х1  х2  13( II )

 х1  3х2  15  (3),  3х1  9 х2  45,  8 х2  32,     3 х  х  13 х  3 х  15 3 х  х  13 1 2 1 2   2  1  х2  4,  х  4,  х  4,  2  2   х1  15  3х2  х1  15  3  4  х1  3.

В результате решения системы уравнений найдены координаты точки В(3;4). Подставим координаты этой точки в выражения для целевой функции и получим максимальное её значение zmax ( В)  2  3  3  4  18 . Ответ: z max  18 при х1=3, х2=4. Экономическая интерпретация полученных результатов выглядит следующим образом: необходимо выпускать 3 изделия вида П1 и 4 изделий вида П2 . В этом случае предприятие получит максимальную прибыль в размере 18 ден. ед. 39

4.2. Теория двойственности Любой задаче математического программирования можно поставить в соответствие так называемую двойственную задачу оптимизации. Между этими задачами обнаруживаются тесные связи, изучение которых составляет предмет теории двойственности. Эта теория тесно связана с теорией условий оптимальности. Рассмотрим теорию двойственности только применительно к задачам линейного программирования. Двойственная задача к задаче линейного программирования также является задачей линейного программирования, причем, как будет видно из определения, ее можно выписать в явном виде с помощью данных исходной задачи. Определение 1. Если задана общая задача ЛП f(x) = c1x1 +…+ cj xj + cj+1xj+1 +…+ cn xn → min, x ∈ X,

(4.4)

где Х определяется системой уравнений и неравенств:

то двойственной по отношению к ней называется общая задача ЛП (4.5) где Х* определяется системой уравнений и неравенств:

Соответственно, задача (4.4) по отношению к задаче (4.5) называется прямой (или исходной). 40

Из определения 1 вытекает важное свойство − симметричность отношения двойственности, т.е. задача, двойственная по отношению к двойственной, совпадает с прямой (исходной) задачей. Тем самым имеет смысл говорить о паре взаимно двойственных задач. Перед тем как строить двойственную задачу, исходную задачу ЛП следует привести к виду (4.4). Правила построения задачи, двойственной по отношению к общей задаче ЛП, наглядно представлены схемой (рис. 4.7).

Рис. 4.7 Схема построения двойственной задачи

Как следует из приведенной схемы, при переходе от прямой задачи ЛП к двойственной: 1. Тип оптимума меняется на противоположный, т.е. максимум на минимум, и наоборот. 2. Вектор коэффициентов целевой функции с и столбец ограничений b меняются местами. 3. Матрица ограничений А транспонируется. 4. Множество индексов переменных, на которые наложено условие неотрицительности в прямой задаче (например, xj ≥ 0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче. 5. Множество номеров ограничений, имеющих форму неравенств в прямой задаче, определяют множество индексов переменных в двойственной задаче, на которые налагается ограничение неотрицательности (иi ≥ 0). Особо отметим, как выглядят двойственные задачи к задачам ЛП в упомянутых ранее частных формах. Двойственной к основной задаче ЛП

41

является ЗЛП в канонической форме

Двойственной к ЗЛП в канонической форме

является задача ЛП в основной форме

ТЕМА 4. УПРАВЛЕНИЕ ТЕХНОЛОГИЧЕСКИМИ ПРОЦЕССАМИ Модели линейного программирования широко применяются при решении военных, экономических, промышленных и социальных задач. К числу главных пользователей моделей ЛП большой размерности относятся, например, нефтяные компании, применяющие их для решения задач распределения и транспортировки нефтепродуктов. Термин «разработка» означает построение моделей ЛП практических задач. Построение моделей не стоит рассматривать только как науку, скорее это искусство, которое постигается с опытом. Разработка модели ЛП включает следующие основные этапы: определение переменных задачи, представление ее ограничений в виде линейных уравнений или неравенств; задание линейной целевой функции, подлежащей минимизации или максимизации. В качестве примера, иллюстрирующего основные этапы разработки модели ЛП, рассмотрим построение классической экономико-математической модели. Транспортная задача Одним из наиболее важных частных случаев общей задачи линейного программирования является так называемая транспортная задача. Содержательно она формулируется следующим образом. Пусть в пунктах А1, А2, …, Аm производится некоторый однородный продукт, причем объем производства этого продукта в пункте Ai составляет 42

ai единиц, i = 1, …, m. Этот продукт должен быть доставлен в пункты потребления В1, В2, …, Вn, причем объем потребления в пункте Bj составляет bj единиц продукта. Предполагается, что транспортировка готовой продукции возможна из любого пункта производства в любой пункт потребления и транспортные издержки, приходящиеся на перевозку единицы продукта из пункта Аi в пункт Вj, составляют cij денежных единиц. Задача состоит в организации такого плана перевозок, при котором суммарные транспортные издержки были бы минимальными. План перевозки груза в данной транспортной сети представляет собой массив элементов размерности m × n:

Если реальная перевозка между пунктами i и j отсутствует, то полагают xi,j = 0. Ограничения на возможные значения x ∈ Rm n имеют вид: 1. Ограничения на удовлетворение потребностей во всех пунктах потребления: (4.6) 2. Ограничения на возможности вывоза запасов из всех пунктов производства: (4.7) 3. Условия неотрицательности компонентов плана: (4.8) Математическая постановка транспортной задачи: определить точку минимума функции суммарных транспортных издержек

при ограничениях (4.6)–(4.8). Существенной характеристикой описываемой задачи является соотношение параметров ai и bj. Если суммарный объем производства равен суммарному объему потребления, а именно выполняется условие баланса

43

(4.9) то система называется сбалансированной. При выполнении условия баланса разумно накладывать такие ограничения на суммарный ввоз и вывоз груза, при которых полностью вывозится весь груз и не остается неудовлетворенных потребностей, т.е. условия (4.6), (4.7) приобретают форму равенства. При таких ограничениях выполнение равенства (4.9) становится необходимым и достаточным условием для разрешимости транспортной задачи. Специфическими для транспортной задачи являются следующие два обстоятельства: а) каждая из переменных xi,j входит в два уравнения системы (4.6), (4.7); б) все коэффициенты при переменных xi,j принимают лишь два значения – 0 и 1. Эти особенности позволили разработать для решения транспортной задачи алгоритмы, существенно более простые, чем симплекс-метод. Наиболее известным из таких алгоритмов является метод потенциалов. Этот метод может трактоваться как разновидность симплексных процедур. Он представляет собой итерационный процесс, на каждом шаге которого рассматривается текущая опорная точка, проверяется ее оптимальность с помощью теорем двойственности, и при необходимости определяется переход к «лучшей» опорной точке. 4.3. Постановка задачи нелинейного программирования Если в линейном программировании обязательным является условие, согласно которому целевая функция и все ограничения должны быть представлены в виде линейных зависимостей, то в задачах нелинейного программирования эти зависимости могут быть любого вида. Общая задача нелинейного программирования имеет вид: вычислить max(min) z  f ( x1 , x 2 ,..., x n );



при условиях  i ( x1 , x 2 ,..., x n ) , , }bi , i  1, m.

где z,i - заданные функции; bi - действительные числа.

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

Рассмотрим частный случай общей задачи нелинейного программирования, предполагая, что система ограничений содержит только уравнения, отсутствуют условия неотрицательности переменных и z  f ( x1 ,..., xn ) и i ( x1 ,.., xn ) - функции, непрерывные вместе со своими частными производными: вычислить max(min) z  f ( x1 , x 2 ,..., x n ); при условиях  i ( x1 , x 2 ,..., x n )  bi .

Такая задача называется задачей на условный экстремум или классической задачей оптимизации, т.к. поведение независимых переменных ограничено определенными условиями. Пусть выполняется условие m  n . Необходимое условие существования экстремума в точке Если функция f ( x1 , x2 ) имеет экстремум в точке Р0(a,b), то в этой точке полный дифференциал либо тождественно равен нулю, либо не существует. Замечание Условие df ( x1 , x2 )  0 ,

f f dx1  dx2 =0 равносильно сисх1 x2

теме 2 равенств: f x/ ( x1 , x2 )  0, f x/ ( x1 , x2 )  0 . 1

2

Достаточное

условие существования экстремума Пусть Adx  2Bdx1dx2  Cdx есть второй дифференциал f ( x1 , x2 ) в ее критической 2 1

2 2

точке Р0(a,b) (Числа A  f x//x , B  f x//x , C  f x//x в точке Р0(a,b)). Если при этом 1 1

1 2

2 2

имеет место неравенство AC  B  0 , то функция f ( x1 , x2 ) имеет в точке 2

Р0(a,b) экстремум: максимум, если А (или С) отрицательно, минимум – если А (или С) положительно. Условным экстремумом функции z  f ( x1 ,..., xn ) называется максимум или минимум этой функции, достигнутый при условии, что x1 ,..., xn удовлетворяют дополнительным условиям i ( x1 ,..., xn )  bi , i  1, m . Условный экстремум находят с помощью функции Лагранжа. Для нахождения решения задачи вводят набор переменных 1 , 2 ,..., m , называемых множителями Лагранжа: 1) Составляют функцию Лагранжа L( x1 , x2 ,..., xn , 1 ,..., m )  f ( x1 , x2 ,..., xn )  1 (b1  1 ( x1 , x2 ,..., xn )  ...  m (bm  m ( x1 , x2 ,..., xn ))

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

45

2) Находят частные производные

L ( j  1, n) x j

и

L (i  1, m) i

и

рассматривают систему n+m уравнений  m 1 f  L  x  x  (1 x  ...  m x )  0, ( j  1, n),  j j j j   L  b   ( x ,..., x )  0 (i  1, m). i i 1 n  i

с n+m неизвестными x1 , x2 ,..., xn , 1 ,..., m . Всякое решение этой системы уравнений определяет точку ( x10 , x20 ,..., xn0 ) , в которой может иметь место экстремум функции f ( x1 , x2 ,..., xn ) . Точка ( x10 , x20 ,..., xn0 ) является укороченной (так как отсутствуют координаты 1 ,..., m ) подозрительной точкой локального условного

экстремума

функции

f ( x1 , x2 ,..., xn ) при

условиях

i ( x1 , x2 ,..., xn )  bi , i  1, m . Следовательно, решив систему уравнений, полу-

чаем все точки, в которых эта функция может иметь экстремальные значения. Этапы решения классической задачи оптимизации методом множителей Лагранжа: 1) составляют функцию Лагранжа; 2) находят частные производные от функции Лагранжа и приравнивают их к нулю; 3) решая систему уравнений), находят точки, в которых целевая функция задачи может иметь экстремум; 4) среди точек подозрительных на экстремум, находят такие, в которых достигается экстремум, и вычисляют значения функции z  f ( x1 , x2 ,..., xn ) в этих точках. Пример. Найти max(min) z  6  4 x1  3x2 при условии x12  x22  1 Решение. 1) L( x1 , x2 ,  )  6  4 x1  3x2 +  (1  x12  x22 ) ; 2)

L  4   2 х1  0 , x1

L  3   2 х2  0 , x2

L  1  x12  x22  0 ; 

46

2   х1   , 2х1  4,   3 25 25 5 3) 2х 2  3,   х 2  , ,   2  1 , 42  25 , 2  4 2 4 2  2  2 x  x  1 , 2  1 9 4  2  42  1, 

     5    5 ,   , 2 2     2 4 2 4    ,   х1    ,   х1  5 5 52 5    2   3 3  ,  х2   3 3 5 5  ,   х2   2 5  5  2 2( )  2 4 3 5 4 3 5 Итак, (  ; ; ), ( ; ; ). 5 5 2 5 5 2

Найдем A  f x//1 x1  2 , B  f x//1 x2  0, C  f x//2 x2  2 AC  B 2  42 42  0 экстремум существует.

4 5

3 5 5 2

Значение выражения А в точке (  ; ; ) принимает значение меньше нуля – это точка максимума. Значение выражения А в точке ( 4 3 5 ; ; ) принимает значение больше нуля – это точка минимума. 5 5 2

Значение целевой функции 4 3 16 9 3  6    11 , 5 5 5 5 4 3 z min  6  4  3  6  5  1 . 5 5 4 3 4 3 Ответ. z max  11 (  ; ), z min  1 ( ; ) 5 5 5 5 z max  6  4

Теорема Куна-Таккера. Решение задач нелинейного программирования Пусть задача нелинейного программирования имеет вид 47

max(min) f ( x1 , x2 ,..., xn ); hi ( x1 , x2 ,..., xn )  0, i  1...m.

Для решения поставленной задачи используется центральная теорема математического программирования – теорема Куна-Таккера, выдвигающая необходимые условия существования решения задачи нелинейного программирования. Достаточные условия существования решения формулируются в теоремах Куна-Таккера второго, третьего и т.д. порядках и в данном курсе не рассматриваются. Теорема (Куна-Таккера) Точка ( х10 ,....хт0 ) может являться решением задачи нелинейного программирования только в том случае, если в ней выполнены следующие условия: m

1) gradf    i gradhi  0 ; i 1

2) i hi  0, i  1,..., m ; 3) i  0, i  1,..., m(max) , i  0, i  1,..., m(min) . Пример Найти наибольшее и наименьшее значения функции f ( x, y)  x 2  y 2  y при заданных ограничениях при ограничениях y  1  x 2 и у  0.

Решение. Запишем ограничения в стандартном виде h1 ( x, y )  у  x 2  1  0, h2 ( x, y )   y  0.

Первое условие теоремы Куна-Таккера позволяет записать два уравнения: h h f  1 1  2 2  0 , x x x h h f  1 1  2 2  0 . y y y

Второе условие теоремы позволяет записать еще два уравнения: 1h1  0 , 2 h2  0 . Подставляя в них функции f , h1, h2 и вычислив производные, получаем систему из 4 уравнений с 4 неизвестными: 2 x  1 2 x  0, 2 у  1      0,  1 2  2 1 ( у  x  1)  0,  ( у )  0.  2

Рассмотрим несколько ветвей решения системы уравнений: 48

1  0, 1  0,   0,   0,  2  1)  2   x  0, 2 x  0,  2 у  1  0. у  1 .  2

1  0,  2  0,  2 x(1   )  0,  2  0,  1 2) 2 x  1 2 x  0,   . 2 у  1  1 , 2 у  1    0, 1  у  x 2  1  0.   2  у  x  1  0.

Вторая система распадается на два случая:  2  0,  х  0,  2а)  ; 2б) 2  у  х  1  1, 1  1  2 у  1.

 2  0,   х  0,  ; 1  1  0, 1  1, 2 у  1    1  1  2, у  1, 1  2  x  1  у  0.

1  0, 1  0,   0, 2  x  0,   3) 2 x  0, ;  2 у  1    0,  2  1, 2   у  0.  у  0. 1  0,   0,  2 2 x  1 2 x  0, 4)  , 2 у  1      0 , 1 2   у  0,   у  х 2  1  0.

2 x  1 2 x  0, 2 у  1      0,  1 2 Эта система распадается на  у  0 ,   х 2  1.

две  х  1,  х  1,  х  1,  х  1,  у  0,  у  0,  у  0,  у  0,     4а)  ; 4б)  . После того как    2  2   0 , 2   2  0 ,    1 ,    1 , 1 1 1 1      2  1  1.  2  1  1.  2  2.  2  2.

система решена результаты собираются в таблицу 4.2: Таблица 4.2 Р Р1

х

у

1

2

0

1 2

0

0

49

f -

1 4

Р2 Р3 Р4 Р5

0 0 1 -1

1 0 0 0

-1 0 -1 -1

0 -1 -2 -2

0 0 1 1

Предварительно убеждаемся, что все точки принадлежат допустимому множеству. Подставляя их координаты в ограничения-неравенства и видя, что они остаются истинными, рассчитываем значение целевой функции в каждой из них. Кроме того, убеждаемся, что третье условие теоремы Куна-Таккера также выполнено во всех точках. Сравнивая значение целевой функции в каждой из найденных точек, видим, что наибольшее значение функции 1 достигается в точках (1;0) и (-1;0), наименьшее (0;

1 в точке 4

1 ). 2

Геометрическая интерпретация задачи нелинейного программирования и ее решение графическим методом Рассмотрим общую задачу нелинейного программирования: вычислить max(min) z  f ( x1 , x 2 ,..., x n );



при условиях  i ( x1 , x 2 ,..., x n ) , , }bi , i  1, m.

где z,i - заданные функции; bi - действительные числа.

Если определена область допустимых решений, то нахождение решения задачи нелинейного программирования сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наинизшего) уровня: f ( x1 , x2 ,..., xn )  h . Указанная точка может находиться как на границе области допустимых решений, так и внутри нее. Если число переменных в задаче нелинейного программирования равно двум, то она может быть решена графическим методом. Математическая формулировка задачи имеет вид: max(min) z  f ( x1 , x 2 );



при условиях  i ( x1 , x 2 ) , , }bi , i  1, m, х1 , х 2  0.

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

50

1) находят область допустимых решений задачи, определяемую соотношениями. Экстремум функции может достигаться как внутри области, так и на ее границе; 2) строят гиперповерхность, в нашем случае гиперповерхность 2-го порядка – гиперплоскость z( x1 , x2 )  h . Записать уравнения линий уровня целевой функции, построить их графики и определить направление возрастания (убывания) целевой функции; 3) определяют гиперплоскость наивысшего (наинизшего) уровня или устанавливают неразрешимость задачи; 4) находят точку области допустимых решений, через которую проходит гиперплоскость наивысшего (наинизшего) уровня, и определяют в ней значение целевой функции. Пример. Найти наибольшее и наименьше значения функции f ( x, y)  x 2  y 2  y

при

заданных

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

при

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

y  1 x2 и у  0 .

Решение. Целевая функция f определяет в трехмерном пространстве окружность: 1 1 1 x2  y2  y  х2  у2  2 у    0 , 2 4 4 1 1 x2  ( y  )2  . 2 4 1 1 Центр окружности в точке (0; ), радиус равен . Построим область 2 4

допустимых значений (рис. 4.8)

Рис. 4.8 Область допустимых значений

На рис. 4.8 изображена парабола у  1  x 2 , ветви направлены вниз, вершина в точке (0;1). Строим окружность минимального радиуса. Это 51

точка – центр окружности (0;

1 1 ). В этой точке f=- . Увеличиваем радиус 2 4

окружности до тех пор, пока она не пересечет последнюю точку области определения. Это точки с координатами (1;0) и (-1;0), f=1. Контрольные вопросы 1. Сформулируйте общую задачу линейного программирования. 2. Чем отличается основная задача ЛП от общей? 3. Чем отличается общая задача ЛП от канонической? 4. Всегда ли общую задачу ЛП можно привести к канонической форме? 5. Понятие нелинейного программирования. 6. Геометрическая интерпретация задачи. 7. Алгоритм задачи нелинейного программирования графическим методом. Лекция 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 5.1 Постановка задачи динамического программирования. 5.2 Составление математической модели 5.3 Этапы решения задачи динамического программирования. 5.1 Постановка задачи динамического программирования. Метод динамического программирования используется как для дискретных, так и для непрерывных оптимизационных задач. Динамическое программирование представляет собой математический метод для нахождения оптимальных решений многошаговых (многоэтапных) задач оптимизации. Некоторые задачи математического программирования обладают специфическими особенностями, что позволяет свести их решение к рассмотрению некоего множества более простых «подзадач». В результате вопрос о глобальной оптимизации целевой функции сводится к поэтапной оптимизации промежуточных целевых функций. Пусть, например, на период времени Т, состоящий из m лет, планируется деятельность группы промышленных предприятий. В начале планируемого периода на развитие предприятий выделяются основные средства Q0, которые необходимо распределить между предприятиями. В про52

цессе функционирования предприятий выделенные им средства частично расходуются. Однако каждое из этих предприятий за определенный период времени (хозяйственный год) получает прибыль, зависящую от объема вложенных средств. В начале каждого года имеющиеся средства могут перераспределяться между предприятиями. Требуется определить, сколько средств надо выделить каждому предприятию в начале каждого года, чтобы суммарный доход от всей группы предприятий за период времени Т был максимальным. Эта задача является многошаговой. Шагом управления здесь будет хозяйственный год. Управление процессом состоит в перераспределении средств в начале каждого хозяйственного года. Обычно методами динамического программирования оптимизируют работу управляемых систем, эффект которой оценивается аддитивной целевой функцией. Аддитивной называется функция многих переменных f(x1, x2,…, xn) вида n

f ( x1 , x2 ,..., xn )   f j ( x j ), j 1

где каждая функция fj зависит только от одной переменной хj. Слагаемые аддитивной целевой функции соответствуют эффекту решений, принимаемых на отдельных этапах управляемого процесса. Принцип оптимальности и рекуррентное соотношение Метод динамического программирования позволяет одну задачу со многими переменными заменить рядом последовательно решаемых задач с меньшим числом переменных. Процесс решения задачи разбивается на шаги. При этом если задано начальное состояние управляемой системы, то нумерация шагов осуществляется от конца к началу, а если конечное, то – от начала к концу. Основным принципом, на котором базируется оптимизация многошагового процесса и особенности вычислительного метода динамического программирования, является принцип оптимальности Р. Беллмана. Приведем его формулировку: оптимальное поведение обладает тем свойством, что каковы бы ни были начальное состояние и начальное решение, последующие решения должны составлять оптимальное поведение относительно состояния, полученного в результате начального решения. 53

Этот принцип можно сформулировать и по-другому: оптимальное поведение в многошаговом процессе обладает тем свойством, что какими бы ни были решение, принятое на последнем шаге, и состояние процесса перед последним шагом, предыдущие решения должны составлять оптимальное относительно этого состояния поведение. Принцип оптимальности имеет конструктивный характер и непосредственно указывает процедуру нахождения оптимального решения. Математически он записывается выражением вида (5.1) f n1 ( S l )  optimumRl 1 ( S l ,U l 1 )  f n( l 1 ) ( S l 1 ), где U l  ( ul( 1 ) ;...; u (m) ) - решение (управление), выбранное на l-м шаге, l = 0, 1, l …, n-1;

S l  ( sl( 1 ) ;...; s (m) ) l

– состояние системы на l-м шаге; Rl –

непосредственный эффект, достигаемый на l-м шаге; fn-l – оптимальное значение эффекта, достигаемого за n–l шагов; n – количество шагов (этапов). «Optimum» в выражении (5.1) означает максимум или минимум в зависимости от условия задачи. Формула (5.1) назвается уравнением Беллмана или рекуррентным соотношением. Процесс вычисления fn-l, l = 0, …, n–1, осуществляется при естественном начальном условии f0(Sn) = 0, которое означает, что за пределами конечного состояния системы эффект равен нулю. Сформулированный принцип и уравнение Беллмана носят общий характер и применяются не только в задачах дискретной оптимизации. Метод динамического программирования широко используется для решения многих экономических и технологических задач, связанных с планированием производственных программ, оптимальным распределением ресурсов (денежных средств, рабочей силы, сырья и т. д.), а также управлением технологическими системами. Поскольку многие особенности реализации метода динамического программирования определяются конкретными задачами, не имеет смысла подробно описывать вычислительный алгоритм в общем случае. 5.2 Составление математической модели динамического программирования Динамическое программирование - метод оптимизации, приспособленный к операциям, в которых процесс принятия решений может быть разбит на отдельные этапы (шаги). Такие операции называются многошаговыми.

54

В основе метода динамического программирования лежит принцип оптимальности, сформулированный Р.Беллманом. Этот принцип и идея включения конкретной задачи оптимизации в семейство аналогичных многошаговых задач приводят к рекуррентным соотношениям - функциональным уравнениям - относительно оптимального значения целевой функции. Их решение позволяет последовательно получить оптимальное управление для исходной задачи оптимизации. Рассматривается управляемая система, которая под влиянием управления переходит из начального состояния  0 в конечное состояние  n . Предположим, что процесс управления системой можно разбить на n шагов. Пусть 1 ,  2 ,…,  n — состояния системы после первого, второго, ..., nго шага. Состояние  k системы после k-ro шага ( k =1, 2, ... ,n) характеризуется параметрами k(1), k(2),…,k(s) которые называются фазовыми координатами. Состояние  k , можно изобразить точкой s-мерного пространства, называемого фазовым пространством. Последовательное преобразование системы (по шагам) достигается с помощью некоторых мероприятий u1, u2 ,..., un которые составляют управление системой U=( u1, u2 ,..., un ) где uk — управление на k-м шаге, переводящее систему из состояния  k 1 в состояние  k . Управление uk , на k-м шаге заключается в выборе значений определенных управляющих переменных uk(1), uk(2),…, uk(n). Предполагаем впредь, что состояние системы в конце k-гo шага зависит только от предшествующего состояния системы  k 1 и управления uk на данном шаге . Такое свойство получило название отсутствия последействия. Обозначим эту зависимость в виде

 k = Fk(  k 1 , uk )

(5.2)

Равенства (5.2) получили название уравнений состояний. Функции Fk(  k 1 , uk ) полагаем заданными. Варьируя управление U, получим различную «эффективность» процесса , которую будем оценивать количественно целевой функцией Z, зависящей от начального состояния системы  0 и от выбранного управления U: Z=Ф(  0 ,U) 55

(5.3)

Показатель эффективности k-гo шага процесса управления, который зависит от состояния  k 1 в начале этого шага и управления uk , выбранного на этом шаге, обозначим через fk(  k 1 , uk ). В рассматриваемой задаче пошаговой оптимизации целевая функция (5.3) должна быть аддитивной, т.е. n

Z=  fk(  k 1 , uk )

(5.4)

k 1

Если свойство аддитивности целевой функции Z не выполняется, то этого иногда можно добиться некоторыми преобразованиями функции. Например, если Z — мультипликативная функция, заданная в виде n

Z=  fk(  k 1 , uk ) k 1

то можно рассмотреть функцию Z' = logZ, которая является аддитивной. Обычно условиями процесса на управление на каждом шаге uk накладываются некоторые ограничения. Управления, удовлетворяющие этим ограничениям, называются допустимыми. Задачу пошаговой оптимизации можно сформулировать так: определить совокупность допустимых управлений u1, u2 ,..., un , переводящих систему из начального состояния  0

в конечное состояние  n

и

максимизирующих или минимизирующих показатель эффективности (5.4). Начальное состояние  0 и конечное состояние  n могут быть заданы однозначно или могут быть указаны множество 0 начальных состояний и множество n конечных состояний так, что  0  0,  n n. В последнем случае в задаче пошаговой оптимизации требуется определить совокупность допустимых управлений, переводящих систему из начального состояния  0  0 в конечное состояние  n n и максимизирующих целевую функцию (5.4). Управление, при котором достигается максимум целевой функции (5.4), называется оптимальным управлением и обозначается через U*=( u1* , u2* ,..., un* ) Если переменные управления uk принимают дискретные значения, то модель ДП называется дискретной. Если же указанные переменные изменяются непрерывно, то модель ДП называется непрерывной. В зависимости от числа параметров состояний (s) и числа управляющих переменных на каждом шаге (r) различают одномерные и многомерные модели ДП . Число шагов в задаче может быть либо конечным, либо бесконечным. 56

В некоторых задачах, решаемых методом ДП, процесс управления естественно разбивается на шаги. Исходя из условий каждой конкретной задачи, длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений. Задача распределения ресурсов. Построение модели ДП и построение вычислительной схемы З а д а ч а 1. Планируется распределение начальной суммы средств 0 между п предприятиями П1, П2, ..., Пn. Предполагается, что выделенные предприятию ПK в начале планового периода средства xk приносят доход fk(xk) ( k = l , 2, ..., n). Будем считать, что: 1) доход, полученный от вложения средств в предприятие ПK, не зависит от вложения средств в другие предприятия; 2) доход, полученный от разных предприятий, выражается в одинаковых единицах; 3) общий доход равен сумме доходов, полученных от распределения всех средств по всем предприятиям. Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарный доход был максимальным. Запишем математическую постановку задачи. Суммарный доход определяется функцией n

Z=

 f (x ) k 1

k

k

(5.5)

Переменные xk должны удовлетворять условиям x1 + x2 +…+ xn = 0 ; xk  0 (k=1,…,n)

(5.6)

Требуется определить переменные х\, ..., хп, которые удовлетворяют ограничениям (5.6) и обращают в максимум целевую функцию (5.5). Аналогичная задача оптимизации решалась в классическом анализе с помощью множителей Лагранжа. В прикладных задачах классический метод Лагранжа, как правило, неприменим по многим причинам и прежде всего — по причине размерности. Искать абсолютный максимум функции п переменных, даже если эта функция дифференцируема, дело трудоемкое. Если к тому же учесть, что экстремум может достигаться на границе, то к исследованию стационарных точек внутри области прибавляется исследование стационарных точек на ее границе. В практических зада57

чах переменные xk могут принимать дискретные значения (например, средства выделяются в размерах, кратных 10 ед.), а функции дохода fk(xk) могут быть недифференцируемыми или даже заданными таблично. Во всех этих случаях классические методы оптимизации неприменимы. К решению задачи можно применить методы нелинейного программирования. Однако и они оказываются эффективными лишь при ряде дополнительных свойств функций fk(xk), которые на практике часто не выполняются. Наконец, иногда бывает важно не только получить решение конкретной задачи при определенных 0 и n, но и исследовать чувствительность решения к изменению этих исходных данных, что при использовании классических методов затруднительно. Покажем, как с помощью методов ДП указанные трудности легко преодолеваются. Перейдем к описанию задачи в виде модели ДП. Внутреннее свойство процесса распределения средств между п предприятиями позволяет рассматривать его как n-шаговый процесс. За номер k-гo шага примем номер предприятия, которому выделяются средства хk. На 1-м шаге выделяем 1-му предприятию средства х1, на 2-м шаге — 2-му предприятию выделяем средства х2 из оставшихся и т. д. Очевидно, что переменные xk ( k =1 , ..., n) можно рассматривать как управляющие переменные. Начальное состояние системы характеризуется величиной o средств, подлежащих распределению. После выделения х1 остается 1 = 0 –x1 средств и т. д. Величины go,  1,  2 ,…, n характеризующие остаток средств после распределения на предшествующих шагах, будем рассматривать как параметры состояния. Уравнениями состояния служат равенства k = k-1 –xk ( k =1 , ..., n) Суммарный доход за п шагов составляет n

Z = Ф (o ,U) =  f k ( xk ) k 1

и представляет собой показатель эффективности процесса, имеющий, как видно из этого равенства, аддитивную форму. Если к началу k-гo шага остаток средств равен k-1 то доход, который можно получить на оставшихся n-k+1 шагах (т. е. от выделения средств n

предприятиям Пk, Пk+1, ..., Пn), составит Zk =  fi ( xi ) i k

Максимальный доход за эти n-k + 1 шагов зависит от того, сколько средств осталось от предыдущих k-1 шагов, т. е. от величины k-1. Поэтому 58

будем его обозначать через Zk*(k-1). Очевидно, что Z1*(0) =Zmax, т. е. Z 1 * ( 0 ) представляет собой суммарный максимальный доход за п шагов (доход, полученный при оптимальном распределении средств 0 между п предприятиями). Рассмотрим любой k-й шаг. Очевидно, что xk можно выбирать из условия 0  xk  k-1 .Значение xk, удовлетворяющее этому двойному неравенству, называется допустимым. Принцип оптимальности в этом конкретном случае означает, что, выделив величину xk и получив от k-гo предприятия доход f k ( x k ) , мы должны распорядиться оставшимися средствами k = k-1 – xk наивыгоднейшим образом и получить от предприятий Пk+1, ..., Пn максимальный доход Zk+1*(k). Ясно, что величину xk следует определять из условия максимизации суммы f k ( x k ) + Zk+1*(k). Таким образом, получаем уравнение Беллмана Zk*(k-1) = max { f k ( x k ) + Zk+1*(k)}. (5.7) 0 xk  k 1

Перейдем к схеме вычислений. Нас интересует Z1*(0) , но если начать с 1-го шага, т.е. с решения задачи Z1*(0) = max { f 1 ( x 1 ) + Z2*(1)}, 0 x1 0

*

то необходимо знать Z2 (1). В свою очередь, при определении Z2*(1) нужно знать Z3*(2), и т. д. Однако имеется шаг, за которым нет последующих. Таким является n-й шаг, на котором выделяются средства последнему предприятию Пп. Для него равенство (5.7) имеет вид Zn-1*(n-1) = max { f n ( x n ) }, (5.8) 0 xn  n 1

Будем считать, что функция дохода f n ( x n ) монотонно возрастает, поэтому решением этой задачи является условное оптимальное управление x n * (n-1) при котором достигается условный максимум Zn*(n-1) = f n ( x n * ) . Следовательно, предприятию Пп выделяются все оставшиеся средства (n-1) , которые приносят доход fn(n-1). Вернемся к предыдущему, (n-1)-му шагу, в начале которого имеется остаток средств n-2 . Уравнение (5.7) в этом случае примет вид Здесь оптимальный выбор x n - 1 не столь очевиден, как при решении предыдущей задачи (5.8). Прежде всего, выразив из уравнения состояния n-1 через n-2- x n - 1 , получим Zn-1*(n-2) = max {f n - 1 ( x n - 1 ) + Zn*(n-2- x n - 1 )}. (5.9) 0 xn  2  n  2

59

Оба слагаемых в фигурных скобках — известные функции, зависящие от управляющей переменной x n - 1 . Параметр n-2 является начальным состоянием для данной задачи. Выполнив исследование на максимум функции Zn-1(x n - 1 , n-2) = f n - 1 ( x n - 1 ) + Zn*(n-2- x n - 1 ) от одной переменной x n - 1 получим условное оптимальное управление x n - 1 * ( n-2) и соответствующий условный максимум суммарного дохода Zn-1*(n-2). На языке данной задачи это решение означает, что если перед выделением средств предприятию Пn-1 в нашем распоряжении имеется остаток n-2, то предприятию Пn-1 необходимо выделить x n - 1 * ( n-2) средств. При этом сумма доходов от предприятий Пn и Пn-1 достигает максимума. Закончив решение задачи (5.9), перейдем к следующему с конца (n2)-му шагу, определим аналогичным образом условное оптимальное управление x n - 2 * ( n-3) и соответствующий остатку n-3 условный максимум Zn-2*(n-3). В результате, проходя последовательно все шаги с конца процесса распределения к его началу (т. е. к 1-му шагу), получим две последовательности функций: Zn*(n-1), Zn-1*(n-2),…, Z2*(), Z1*(0) (условные максимальные доходы) и x n * ( n-1), x n - 1 * ( n-2),…, x 2 * ( 1), x 1 * ( 0) (условные оптимальные управления). Этим завершается первый и основной этап вычислительного процесса, получивший название условной оптимизации. Теперь приступаем ко второму этапу вычислительной схемы - безусловной оптимизации. На этом этапе, прежде всего, зная функцию Z1*(0), по заданному значению 0* определяем Zmax= Z1*(0*). Далее, обращаемся к последовательности x k * ( k-1), которую проходим от начала к концу процесса. Выделяем x1*= x 1 * ( 0*) 1-му предприятию; тогда для распределения остается  1 * =  0 *- x1*. По этой величине определяем оптимальное количество средств х2* = х2*( 1*), выделяемых 2-му предприятию. Снова находим  2 * =  1 *- x2*, после чего определяем х3*, и т. д., пока не будет определено искомое оптимальное управление (х1*, х2*,...,хn*). 5.3 Этапы решения задачи динамического программирования Укажем основные этапы решения задачи динамического программирования. 60

1. Определение множества возможных состояний Sm для последнего шага. 2. Проведение условной оптимизации для каждого состояния s  Sm на последнем m-м шаге и определение условного оптимального управления x(s), s  Sm. 3 Определение множества возможных состояний Si для i-го шага, i=2,3,…,m-1. 4. Проведение условной оптимизации i-го шага, i=2,3,…,m-1 для каждого состояния s  Sm и определение условного оптимального управления xi(s), s  Si, i=2,3,…,m-1. 5. Определение начального состояния системы s1, оптимального выигрыша W1(S1) и оптимального управления x1(S1) при i=1. Это есть оптимальный выигрыш для всей задачи W*= W1(x1*). 6. Проведение безусловной оптимизации управления. Для проведения безусловной оптимизации необходимо найденное определить следующее состояние системы S=f(s, x1). Для измененного состояния найти оптимальное управление x*= x2(S2). Для i-гo состояния Si найти Si+1= fi+1(si, x1*) и xi+1(si+1) и т.д. Контрольные вопросы 1. Для каких оптимизационных задач применяется метод динамического программирования? 2. В чем заключается суть метода динамического программирования? 3. Сформулируйте принцип оптимальности Беллмана. 4. Каким образом составляется задача динамического программирования? 5. Назовите этапы решения задачи динамического программирования. Лекция 6. ПОСТРОЕНИЕ ЭМПИРИЧЕСКИХ РЕГРЕССИОННЫХ МОДЕЛЕЙ 6.1 Планирование и проведение эксперимента 6.2 Регрессионные модели с одной входной переменной 6.3 Регрессионные модели с несколькими входными переменными 61

6.1 Планирование и проведение эксперимента С общефилософской точки зрения эксперимент (от лат. Experimentium – проба, опыт) – это чувственно-предметная деятельность в науке, в более узком смысле слова – опыт, воспроизведение объекта познания, проверка гипотез и т. д. [10]. Большинство научных исследований связано с экспериментом – физическим, психологическим или модельным. В последнее время наряду с физическими моделями все больше используются компьютерные, на которых можно производить имитационные эксперименты и получать новые сведения об объекте. При исследовании простых объектов достаточно проведения однофакторного эксперимента. Ранее считалось, что опыт должен быть чистым, т. е. все посторонние влияния исключены. Объект рассматривали изолированно от других, без обратных связей и сложных взаимодействий. С усложнением объекта исследования появилась потребность в оптимизации экспериментальных исследований. Эксперимент сам стал объектом исследования, и объектом очень сложным. В технической литературе эксперимент определяется следующим образом: эксперимент – это система операций, воздействий или наблюдений, направленных на получение информации об объекте исследования [10]. Хотя объекты исследований очень разнообразны, все методы экспериментальных исследований имеют много общего: - каким бы простым ни казался эксперимент, исследователи всегда начинают с его планирования; - исследователи всегда стремятся сократить число исследуемых входных факторов, чтобы уменьшить объем эксперимента; - исследователи всегда стараются контролировать ход эксперимента и исключить влияние случайных внешних факторов. Планирование эксперимента – раздел математической статистики, изучающий рациональную организацию измерений и наблюдений [4]. Планирование эксперимента состоит в процедуре выбора числа и условий проведения опытов, необходимых и достаточных для исследования объекта с заданной точностью. Планирование эксперимента обеспечивает [10, 11]: - одновременное варьирование всех факторов по специальным правилам; - использование математического аппарата, формализующего многие действия экспериментатора; 62

- выбор четкой стратегии, позволяющей принимать обоснованные решения после каждой серии экспериментов; - минимизацию числа опытов, ресурсов (финансовых, временных, материальных, человеческих). В основе построения эмпирических моделей лежит теория многофакторного эксперимента (МФЭ), разработанная Р. Фишером в 30-е гг. ХХ в., которая опирается на изучение состояния и поведения объекта при одновременном изменении нескольких входных факторов. Ранее мы уже говорили, что любой объект может находиться в бесконечно большом количестве состояний. Исходя из этого, эксперимент можно рассматривать как реализацию всех или части состояний, в которых может находиться объект. В теории многофакторного эксперимента сам эксперимент понимается как совокупность опытов. Опыт – воспроизведение исследуемого объекта в строго определенных условиях при возможности регистрации результатов. По форме проведения и представления результатов эксперименты бывают качественными и количественными [10]. Качественный эксперимент устанавливает сам факт наличия объекта, процесса или явления, но при этом не дает никаких количественных характеристик. Количественный эксперимент не только фиксирует сам факт существования того или иного объекта, процесса или явления, но и позволяет установить соотношение между количественными характеристиками поведения исследуемого объекта и количественными характеристиками внешнего воздействия. Ранее нами уже были введены понятия «фактор» и «уровень фактора». Вспомним их. Фактор – некоторая переменная величина, принимающая в каждый момент времени определенное значение из своей области определения и отражающая внешнее воздействие на объект или его отклик на это воздействие. Уровень фактора – конкретное значение фактора из его области определения при экспериментальном исследовании объекта. При проведении опытов очень важно, может ли исследователь во время опытов устанавливать те уровни факторов, которые представляют для него интерес. С этой точки зрения различают следующие факторы [10]: 63

- контролируемые и управляемые – это факторы, для которых можно не только зарегистрировать их уровень, но и задать в каждом опыте любое возможное значение; - контролируемые, но не управляемые – это факторы, уровни которых можно только регистрировать, но задавать в каждом опыте определенное значение практически невозможно; - неконтролируемые – это факторы, уровни которых не регистрируются исследователем, он даже может не подозревать об их существовании. Если исследователь имеет возможность контролировать и управлять уровнями факторов, то такой эксперимент можно назвать активным. Если исследователь может только наблюдать и регистрировать, но не имеет возможности управлять уровнями факторов, то это пассивный эксперимент. Во время экспериментального исследования объект рассматривается как «черный ящик» (рис. 6.1).

Рис. 6.1 Объект исследования в общем виде

Выходные факторы в эксперименте еще называют откликом, а зависимость Yj = f (X1, X2, … Xk), которую пытаются установить, – функцией отклика. Выбор уровней факторов План эксперимента – совокупность данных, определяющих число, условия и порядок реализации опытов. Ранее было сказано, что каждый фактор имеет свою область определения. Совокупность областей определения входных факторов назовем факторным пространством. Каждая точка факторного пространства представляет собой вполне определенное сочетание конкретных значений входных факторов и соответствует одному состоянию объекта. На основе анализа задачи исследования и априорной информации об исследуемом объекте для каждого входного фактора выделяется область, в пределах которой он будет изменяться во время эксперимента. Сочетание таких областей по всем входным факторам будем называть факторным пространством эксперимента.

64

Планирование эксперимента начинают с выбора нулевого уровня каждого входного фактора, в качестве которого может быть взята любая точка факторного пространства эксперимента. Но одной точки – нулевого уровня – для проведения эксперимента и получения необходимой информации недостаточно. Нужны еще точки. Построение плана эксперимента – это выбор точек (уровней входных факторов) относительно нулевого. Для определения других уровней входных факторов вводится интервал варьирования каждого входного фактора. Чтобы обозначить верхний уровень входного фактора, следует интервал варьирования прибавить к нулевому уровню данного фактора, а чтобы определить нижний уровень – вычесть интервал варьирования из нулевого уровня. На интервал варьирования накладываются ограничения естественного характера снизу и сверху. К интервалу варьирования входного фактора предъявляются следующие требования: - он не может быть менее ошибки, с которой измеряется данный фактор, иначе уровни фактора будут неразличимы; - он не может быть слишком большим, т. е. нижние и верхние уровни не должны покидать области определения фактора и области проведения эксперимента. Обычно при первичном планировании эксперимента количество уровней по всем входным факторам выбирают одинаковым. Тогда количество опытов в эксперименте (Nэ) может быть определено по формуле Nэ = pэkэ , где pэ – число уровней каждого входного фактора; kэ – число входных факторов, исследуемых в эксперименте. Если из анализа априорной информации известно, что исследуемая зависимость Yj=f (X1, X2, … Xk) является линейной, то достаточно реализовать эксперимент, в котором каждый входной фактор имеет в эксперименте только два уровня, т. е. Nэ = 2kэ. Такой план эксперимента называется планом первого порядка. Если из анализа априорной информации известно, что исследуемая зависимость Yj=f (X1, X2, … Xk) является нелинейной, то достаточно реализовать эксперимент, в котором каждый входной фактор имеет три уровня. Такой план называется планом второго порядка, а 65

Nэ = 3kэ Полный факторный эксперимент Полный факторный эксперимент (ПФЭ) – это эксперимент, в котором реализуются все возможные сочетания всех уровней всех входных факторов [4] (например, Nэ = 2kэ., Nэ = 3kэ.). Условия полного факторного эксперимента записывают в виде таблицы – матрицы планирования эксперимента. Для эксперимента, исследующего объект с двумя входными факторами, каждый из которых изменяется по двум уровням, матрица планирования имеет следующий вид (рис. 6.2).

Рис. 6.2 Матрица планирования полного факторного эксперимента NЭ = 22

Примечание. Знаком «+» обозначены верхние уровни факторов, знаком «–» – нижние. Так выглядит кодированная форма записи. Если для исследования входного фактора было выбрано три уровня, включая нулевой, то в матрице планирования они обозначаются знаками «–» (нижний), «0» (нулевой), «+» (верхний). На рис. 6.3 показана геометрическая интерпретация полного факторного эксперимента N = 22. Если выбрано два нижних и два верхних уровня, то они обозначаются как «–2» (второй нижний), «–1» (первый нижний), «+1» (первый верхний) и «+2» (второй верхний).

66

Рис. 6.3 Геометрическая интерпретация полного факторного эксперимента N = 22

Независимо от числа факторов матрицы ПФЭ обладают следующими общими свойствами [4]: - симметричность относительно центра эксперимента – алгебраическая сумма элементов вектора-столбца каждого фактора равна нулю; - условие нормировки – сумма квадратов элементов каждого столбца равна числу опытов; - ортогональность – сумма почленных произведений любых двух вектор-столбцов матрицы равна нулю; - рототабельность – точки в матрице планирования подбираются так, что точность предсказаний значений параметра оптимизации одинакова на равных расстояниях от центра эксперимента и не зависит от направления. Полный факторный эксперимент страдает избыточностью опытов. Если анализ априорной информации дает основания полагать, что в выбранной области эксперимента объект описывается линейной моделью, то количество опытов можно минимизировать, сократив матрицу планирования эксперимента. Такой эксперимент называется дробным факторным экспериментом (ДФЭ), а таблица его плана – дробной репликой [4, 10, 11, 13 и др]. Уменьшение числа опытов позволяет снизить затраты времени, средств, материалов на проведение и обработку эксперимента. 4.3. Проведение эксперимента Перед проведением эксперимента необходимо выяснить следующее: 1) можно ли установить выбранные уровни входных факторов на используемом для эксперимента оборудовании и удерживать их во время опыта; 67

2) возможно ли возникновение негативных последствий от реализации выбранных сочетаний уровней факторов; 3) возможно ли проведение параллельных опытов во время эксперимента; 4) когда были проверены и откалиброваны измерительные приборы. Параллельными называются опыты, в которых уровни факторов повторяются. Рекомендуется повторять эксперименты не менее трех раз. Проведение параллельных опытов дает возможность сделать более надежными оценки влияния входных факторов на выходной фактор и выполнить расчеты статистических характеристик. После составления матрицы планирования необходимо произвести рандомизацию опытов. Рандомизация (от англ. random – случайный) – введение случайной последовательности проведения опытов. Цель рандомизации – исключение появления и влияния систематических ошибок на результаты эксперимента. Опыты необходимо рандомизировать во времени. Для генерирования случайной последовательности опытов можно использовать программы-генераторы случайных чисел. Выбранную случайным образом последовательность опытов нарушать не рекомендуется. Эксперимент, который ставится для решения задач оптимизации, называется экстремальным. Если не ставится задача оптимизации, а требуется установить только количественную связь между входными и выходными факторами, то такой эксперимент часто называют интерполяционным. После проведения эксперимента следует тщательно проанализировать полученные результаты. Если среди результатов измерений выходного фактора одно-два-три резко отличаются от остальных, то следует проверить, не являются ли они грубыми выбросами, которые подлежат исключению. 6.2 Регрессионные модели с одной входной переменной Технологические процессы машиностроительного производства, особенно процессы обработки резанием конструкционных материалов, очень сложны по своей физико-химической природе. До сих пор отсутствуют принятые всеми аналитические модели, точно описывающие закономерности процессов изнашивания и нагружения инструмента, тепловых процессов в зоне резания и т. д. Поэтому в технологии машиностроения 68

очень часто используют модели, которые мы ранее обозначили как эмпирические. Эмпирические модели объектов и процессов представляют собой результат обработки экспериментальных данных о поведении объекта или процесса методами математического статистического анализа. Очень часто для построения моделей объектов по результатам экспериментальных исследований используют математический аппарат регрессионного и корреляционного анализа. Основная задача корреляционного анализа – выявление значимости связи между значениями различных случайных величин. Зависимость между величинами (в том числе и случайными), при которых одному значению одной величины (аргумента) отвечает одно или несколько вполне определенных значений другой величины, называется, соответственно, однозначной или многозначной функциональной зависимостью [11]. Зависимость между величинами, при которой каждому значению одной величины отвечает с соответствующей вероятностью множество возможных значений другой, называют вероятностной (стохастической, статистической). Примерами корреляционной связи являются зависимости между пределами прочности и текучести стали определенной марки, между погрешностями размера и погрешностью формы поверхности детали, между температурой испытания и прочностью материала и т. д. Математический аппарат регрессионного анализа позволяет: - оценить неизвестные параметры предлагаемой к исследованию регрессионной модели; - проверить статистическую значимость параметров модели; - проверить адекватность модели; - оценить точность модели. Вид регрессионной модели предлагает сам исследователь, при этом он исходит из следующего: - физической сущности изучаемого объекта или явления; - характера экспериментального материала; - анализа априорной информации. Самым простым для моделирования является объект, у которого один входной и один выходной фактор (рис. 6.4). Входной фактор характеризует воздействие на исследуемый объект. В технологических процессах машиностроения это могут быть температура, сила, время, геометрические параметры инструмента, характеристики обрабатываемого и инструментального материалов и т. д. Выходной фактор характеризует реакцию (отклик) объекта на воздействие входного фактора. Выходные факторы в тех69

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

Рис. 6.4 Объект исследования с одним входным и одним выходным фактором

Для начала построения эмпирической модели необходимо иметь данные экспериментальных исследований объекта (в виде таблицы или графика), в которых каждому значению входного фактора (X) соответствует значение выходного фактора (Y), т. е. известна пара чисел (хi, yi). Пары случайных переменных (x, y) подчиняются некоторому двумерному вероятностному распределению. Общее количество пар чисел пусть равно m (рис. 6.5).

Рис. 6.5 Графическое отображение результатов эксперимента

Данный график называется диаграммой рассеяния, или точечной диаграммой [12]. Необходимо найти такую кривую, которая бы наилучшим образом аппроксимировала экспериментальные точки. Для удобства дальнейшего исследования объекта эта кривая должна иметь для своего описания одну единственную формулу (функцию). Если мы соединим точки на графике, то получим ломаную линию, состоящую из нескольких прямых отрезков и описываемую соответствующим количеством линейных моделей. Это крайне неудобно для исследования. Необходимо найти кривую, наилучшим образом описывающую все экспериментальные точки (рис. 6.6). Такую кривую называют кривой регрессии, или регрессионной кривой Y по X. В общем случае кривая регрессии может иметь любой вид 70

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

Рис. 6.6 Построение линии регрессии

Обычно построение моделей и исследование объекта начинают с самых простых моделей – линейных. Линейной модели соответствует кривая регрессии в виде простой линии. Как видно из графика (см. рис. 6.6), всегда имеются отклонения экспериментальных точек от кривой регрессии, что вызвано влиянием других (неучтенных в модели) внешних факторов на исследуемый объект. В моделировании выходной фактор еще называют зависимой выходной переменной, а входной – независимой входной переменной. Во время исследования объекта входной фактор всегда носит детерминированный характер, а выходной – случайный. Выражение, которое устанавливает связь между случайной зависимой и детерминированной независимой переменными, представляет собой уравнение регрессии. Термин «уравнение регрессии», строго говоря, не совсем корректный [12], но общепринятый. Модель, построенная на основе уравнения регрессии, является регрессионной моделью. Как указывалось ранее, для получения регрессионных моделей (уравнений регрессии) используется математический аппарат регрессионного анализа. Итак, как мы уже говорили, подбор кривой регрессии и регрессионной модели обычно начинают с простой прямой линии и, соответственно, с линейной модели. Если иметь неограниченно большое количество экспериментальных точек, то линейная регрессионная модель имеет вид [12]

71

где ŷ – значения выходной переменной, рассчитанные (предсказанные) по линейной модели; x – значения входной переменной; β0 и β1 – коэффициенты регрессии; ε– остаток (невязка). Определение коэффициентов регрессии осуществляется на основе метода наименьших квадратов. Метод наименьших квадратов применяют в тех случаях, когда случайная вариация входного фактора пренебрежительно мала по сравнению с наблюдаемым диапазоном его измерения [12], т. е. значения входной переменной считаются фиксированными. Суть метода в том, что подбираются такие β0 и β1, при которых сумма квадратов отклонений измеренных величин y от предсказанных ŷ была бы минимальной. Для пар наблюдений можно записать Отклонение измеренной величины y от предсказанной ŷ Сумма квадратов отклонений выражается в виде

где S – функция суммы квадратов. Подберем b0 и b1 так, чтобы при подстановке их вместо β0 и β1 значение S было минимальным из возможных. Найдем частные производные (∂):

Наименьшее значение суммы квадратов отклонений достигается в том случае, когда коэффициенты β0 и β1 удовлетворяют условию [11]

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

объекта. Поэтому можно определить только оценки коэффициентов β0 и β1, которые обозначают, соответственно, b0 и b1. ŷ = b0 + b1x. Такие модели в литературе часто называют однофакторными регрессионными моделями. Коэффициент регрессии b1 определяется по формуле [12]

где хi – значение входного фактора во время эксперимента; yi – значение выходного фактора, соответствующее xi; x¯ – среднее значение входного фактора, определяемое по формуле

y¯ – среднее значение выходного фактора, определяемое по формуле (5.12)

Коэффициент регрессии b0

Получаем где x¯ и y¯ – координаты «центра тяжести» экспериментальных данных, через который обязательно проходит линия регрессии. Адекватность регрессионных моделей На определении коэффициентов регрессионной модели построение модели не заканчивается. Необходимо установить адекватность и точность предлагаемой модели. Адекватность модели характеризует соответствие модели экспериментальным данным и статистическую значимость уравнения регрессии. Адекватность регрессионной модели оценивается коэффициентом Фишера (Fрасч)

73

Критерий Фишера представляет собой отношение суммы квадратов отклонений, обусловленных регрессией, к сумме квадратов отклонений относительно регрессии. Формулируем нулевую гипотезу H0: b1 = 0. Расчетное значение коэффициента Fрасч необходимо сравнить с табличным значением Fтабл(m, α). В этой записи m – общее количество экспериментальных наблюдений (xi, yi), которое влияет на количество степеней свободы при определении критерия Фишера. α – уровень значимости – вероятность, с которой мы можем отвергнуть правильную гипотезу о модели как неправильную. Обычно в моделировании используют значения α = 0,05; 0,01. Если Fрасч > Fтабл, то нулевая гипотеза отвергается, модель считается адекватной, а регрессия – значимой. Если Fрасч < Fтабл, то регрессионная модель неадекватна и использовать ее для анализа и исследования объекта нельзя. В этом случае необходимо снова проанализировать априорную информацию, снова спланировать и провести эксперимент. Значения коэффициента Фишера обычно даны в справочниках по математической статистике и теории вероятностей. Точность регрессионных моделей Для оценки точности регрессионных моделей с одной входной используется выборочный коэффициент корреляции Пирсона (rxy), который определяется по формуле [12]

Коэффициент корреляции rxy характеризует тесноту связи между выходной переменной y и входной переменной x. Область определения коэффициента корреляции rxy лежит в пределах от –1 до +1 включительно. Можно выделить несколько частных случаев значения коэффициента корреляции (рис. 6.7).

74

Чем выше значение rxy, тем теснее связь между выходной переменной y и входной переменной x, тем точнее, а следовательно, лучше математическая модель. Если модель имеет низкое значение rxy, то она имеет низкую точность оценки и предсказания поведения или свойств объекта. Такую модель использовать для исследования, описания и предсказания объекта не рекомендуется. Из нескольких моделей, проанализированных во время моделирования, для исследования объекта выбирается та модель, у которой коэффициент корреляции rxy имеет наибольшее значение. После расчета коэффициента корреляции производят проверку его значимости при помощи критерия Стьюдента. Коэффициент корреляции, рассчитанный для модели (rрасч), сравнивается с табличным (граничным) значением (rтабл). Если rрасч > rтабл, то rрасч принимается как показатель тесноты связи и наоборот [10]. Табличные значения rтабл можно найти в справочниках по теории вероятностей и математической статистике. Если попытаться оценить стандартную ошибку для предсказанных значений выходного фактора y¯, то наилучшие предсказания будут в «центре тяжести» эксперимента [12]. Чем дальше от «центра тяжести», тем менее точными будут предсказания y¯.

75

Рис. 6.7 Частные случаи значения коэффициента корреляции

6.3 Регрессионные модели с несколькими входными переменными Многофакторная (множественная) линейная регрессия Рассмотрим основы построения регрессионных моделей для объекта с несколькими входными переменными (рис. 6.8).

Рис. 6.8 Объект исследования с несколькими входными факторами

76

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

Рис. 6.9 Данные экспериментальных исследований объекта

Моделирование объекта со сложным внешним воздействием в виде нескольких входных факторов, так же как и для объекта с одним входным фактором, начинается с линейной модели. Если иметь неограниченно большое количество экспериментальных точек, то линейная регрессионная модель с несколькими входными переменными имеет вид (6.1) где x1, x2, x3 и т. д. – значения входной переменной; β0, β1, β2, …, βk – коэффициенты регрессии. Имеющиеся экспериментальные данные в виде комбинаций (х1i, x2i, x3i, … xki, yi) являются лишь ограниченной выборкой из общего числа состояний исследуемого объекта. Поэтому можно определить только оценки коэффициентов β0, β1, β2, …, которые обозначают, соответственно, b0, b1, b2, b3, …, bk. (6.2) Такие модели в литературе часто называют многофакторными моделями. Однако определить коэффициенты регрессии bi так, как это делается для однофакторной модели – по методу наименьших квадратов, в данном случае не представляется возможным. Необходимо использовать основы алгебры матриц и матричного исчисления. 6.2. Матричный подход к определению коэффициентов регрессии Запишем для нашего случая матрицы X, Y, B: 77

(6.3) В матрице X все элементы первого столбика равны единице. Будем считать это фиктивной входной переменной X0 с постоянным значением.

(6.4) Определим размерность этих матриц: - Y – вектор наблюдений (m · 1); - X – матрица независимых переменных (m(k + 1)); - В – вектор коэффициентов регрессии ((k + 1) · 1). Правила умножения матриц и векторов требуют, чтобы они были согласованными и имели соответствующую размерность [9, 12]. Пусть А – матрица размерностью (n · p): - на матрицу А только слева может быть умножена матрица В размерностью (m · n): (6.5) - на матрицу А только справа может быть умножена матрица D размерностью (p · q): (6.6) Следовательно, произведение В · Х не существует и множественная линейная регрессия может быть записана в виде Y = X · B. (6.7) Использование аппарата линейной алгебры позволяет получить общую формулу для определения вектора, содержащего коэффициенты регрессии [9]: (6.8) –1

где (X' · X) – обратная матрица; X' – транспонированная матрица. 78

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

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

(6.9) Расчетное значение коэффициента (Fрасч) необходимо сравнить с табличным значением (Fтабл(m, α)), где m – общее количество экспериментальных наблюдений, α – уровень значимости. α – уровень значимости – вероятность, с которой правильная гипотеза о модели может быть отвергнута как неправильная. Обычно в моделировании (и мы об этом уже говорили) используют значения α = 0,05; 0,01. Однако для многофакторных моделей табличное значение F-критерия зависит еще и от числа входных переменных [9]. Если Fрасч > Fтабл, то модель считается адекватной, а регрессия статистически значимой. Если Fрасч < Fтабл, то регрессионная модель неадекватна и регрессия статистически незначима. Для оценки точности регрессионных моделей с несколькими входными переменными используется множественный коэффициент корреляции (R2) [4], который определяется по формуле

(6.10) Отношение R характеризует тесноту связи между выходной переменной и входными переменными. Область определения отношения R2 лежит в пределах от 0 до 1. При R2 = 0 выходной фактор y линейно не зависит от входных факторов x1, x2, …, xk – можно сказать, что корреляционная связь между выходным фактором и входными факторами отсутствует. 79 2

При R2 = 1 выходной фактор y линейно зависит от входных факторов x1, x2, …, xk – имеется в наличии сильная корреляционная связь. Чем выше значение R2, тем теснее связь в модели между выходной переменной (фактором) и входными переменными (факторами), тем точнее, а следовательно, лучше математическая модель. Если модель имеет низкое значение R2, то она имеет низкую точность оценки и предсказания поведения или свойств объекта. Использовать такую модель для исследования, описания и предсказания объекта не рекомендуется. Из нескольких моделей для исследования выбирается та, у которой отношение R2 имеет наибольшее значение. 6.4. Линейные регрессионные модели с несколькими входными переменными Если в результате расчета отношения R2 множественная линейная регрессия признана недостаточно точной, переходят к исследованию более сложных моделей: - полинома с одной независимой переменной y = b0 + b1x + b2x2 + b3x3; - полинома с несколькими независимыми переменными y = b0 + b1x1 + b2x2 + b3x2; - обратной модели

или

- комбинированной модели . Исследователь сам может предложить вид многофакторной модели на основе анализа априорной информации. Оценка коэффициентов регрессии, критерия адекватности модели и множественного коэффициента корреляции осуществляется по формулам (6.8), (6.9), (6.10), рассмотренным ранее для «классической» множественной регрессии. 6.5. Нелинейные регрессионные модели с несколькими входными переменными Если в результате построения линейных моделей ни одна из них не была признана достаточно точной, переходят к исследованию более сложных моделей. Любую модель, в результате преобразования записываемую в виде (6.1), можно анализировать методами линейного регрессионного анализа. Виды преобразований для нелинейных моделей [12]: - обратное преобразование; 80

- логарифмическое преобразование; - преобразование типа квадратного корня. Если при помощи каких-либо преобразований нелинейная модель может быть приведена к виду множественной линейной регрессии, то она называется нелинейной моделью с «внутренней линейностью» [11]. К таким моделям относятся: - степенная (мультипликативная) модель

.

Выполним преобразования:

Введем

переобозначения: . Данная модель имеет вид многофакторной линейной регрессии (см. формулу c2ж(6.1)), следовательно, степенная модель может быть преобразована логарифмированием к виду многофакторной линейной регрессии. Это позволяет использовать для расчета коэффициентов регрессии, критерия адекватности и множественного коэффициента корреляции формулы, рассмотренные выше. После вычислений необходимо выполнить потенцирование [11] и вернуться к исходному степенному виду модели; ● экспоненциальная модель Логарифмирование также позволяет преобразовать экспоненциальную модель к виду многофакторной линейной модели (6.1) и использовать для ее исследования аппарат линейного регрессионного анализа; ● обратная преобразования:

модель

Выполним

.

Введем

переобозначения:

,

. Следовательно, обратная модель также может быть преобразована к виду множественной линейной регрессии, что позволяет использовать для ее исследования аппарат линейного регрессионного анализа. Если при помощи любых преобразований нелинейная модель не может быть приведена к виду множественной линейной регрессии, то она называется нелинейной моделью с «внутренней нелинейностью». Для исследования этих моделей в математике разработан аппарат нелинейного регрессионного анализа [12]. 81

Контрольные вопросы 1. Что такое план и планирование эксперимента? Обозначьте цели планирования эксперимента. 2. Что такое нулевой уровень фактора и интервал варьирования? Как они выбираются? 3. Что такое полный факторный эксперимент? 4. Что такое матрица планирования эксперимента? Назовите ее свойства 5. Что такое линия регрессии и уравнение регрессии? Какие модели называются регрессионными? 6. Каким критерием оценивается адекватность модели с одним входным фактором? 7. Как оценивается точность однофакторной модели? 8. Что такое многофакторная линейная регрессия и как оценивается точность линейной регрессионной модели? 9. Как оценивается адекватность многофакторной линейной регрессионной модели? 10. Какие значения может принимать множественный коэффициент корреляции? 11. Что такое корреляционная матрица? Лекция 7. ПОСТАНОВКА И КЛАССИФИКАЦИЯ ЗАДАЧ УСЛОВНОЙ ОПТИМИЗАЦИИ 7.1 Понятие о задаче условной оптимизации. Классификация задач оптимизации. 7.2 Понятие о численных методах оптимизации. 7.3 Условия оптимальности в общей задаче оптимизации. 7.1 Понятие о задаче условной оптимизации. Классификация задач оптимизации. Ранее мы уже описали общую постановку задачи оптимизации и изучили простейший класс оптимизационных задач без ограничений. В данной лекции мы продолжим разговор о задачах оптимизации как математической основе теории управления технологическими процессами.

82

Задачи оптимизации находят эффективное применение во всех направлениях инженерной деятельности, и в первую очередь в следующих четырех ее областях. Проектирование систем и их составных частей. Сфера применения оптимизационных методов в инженерном проектировании достаточно широка: от проектирования отдельных структурных элементов технических систем до проектирования узлов оборудования и составления предварительных проектов промышленных предприятий в целом. Планирование и анализ функционирования существующих систем. Методы оптимизации в производственном планировании ориентированы главным образом на составление программ производства нескольких видов продукции на отдельном предприятии, а также на координирование производственных планов предприятий, которые связаны хозяйственными отношениями. Задачи анализа функционирования систем обычно возникают в тех случаях, когда требуется адаптировать существующую производственную систему к новым условиям функционирования, отличным от тех условий, которые были предусмотрены проектом этой системы. Инженерный анализ и обработка информации. Эта область применения оптимизационных методов в инженерной практике связана с задачами инженерного анализа, в частности с задачами нелинейного регрессионного анализа. Среди наиболее общих проблем, возникающих в процессе разработки инженерных моделей, можно выделить проблему определения параметров полуэмпирической модели на основе заданного множества экспериментальных данных. Такого рода задачи приводятся к некоторому виду оптимизационных задач. Управление динамическими системами. В этой области находит широкое применение наиболее сложный раздел теории оптимизации – математическая теория оптимального управления. Динамические системы могут быть описаны при помощи дифференциальных, интегральных или иных уравнений. Для любой практической оптимизационной задачи можно выделить следующие основные этапы её реализации: 1. Моделирование рассматриваемой физической ситуации с целью получения математической функции, которую необходимо оптимизировать, а также определение ограничений для параметров. 2. Проверка задачи на существование и единственность решения. 3. Выбор подходящей математической процедуры (метода) для осуществления оптимизации. 83

4. Реализация выбранной процедуры на практике, в частности на ЭВМ. 5. Анализ математического результата и интерпретация его в терминах физического содержания задачи. Вернемся к общей постановке задачи оптимизации. Как уже отмечалось в предыдущей лекции, с математической точки зрения различия между задачами минимизации и максимизации несущественны. Поэтому мы всегда можем ставить задачу оптимизации как задачу минимизации (7.1): f(x) → min, х ∈ X. (7.1) Так же как и в предыдущей лекции, функцию f(x) в (7.1), т.е. функцию, которую мы минимизируем, будем называть целевой функцией, множество Х в (7.1), на котором мы минимизируем f(x), – допустимым множеством задачи (7.1), любой элемент х ∈ Х – допустимой точкой задачи (7.1). Допустимую точку х*∈ Х, в которой целевая функция f(x) достигает своего минимума, будем называть решением задачи (7.1). В задачах условной оптимизации допустимая точка х может представлять собой некий набор параметров х = (х1, ..., хn). Значения этих параметров подчиняются некоторым ограничениям. Если, например, хi выражает количество производимого продукта i-го вида (сплав соответствующей марки и пр.) для каждого i = 1, ..., n, то при этом будет существовать ограничение на производственную мощность (например, 0 ≤ хi ≤ аi, i = 1, ..., n). Необходимо подчеркнуть, что само понятие точки минимума (решения задачи (8.1)) неоднозначно и требует уточнения. Определение 1. Точка х* ∈ Х называется точкой глобального минимума функции f(x) на множестве Х или глобальным решением задачи (9.1), если f(x*) ≤ f(x) при всех х ∈ Х. (9.1) Точка х* ∈ Х называется точкой локального минимума f на Х или локальным решением задачи (7.1), если существует такое подмножество Uδ(х*) = {x | x∈ X, || x − x* || ≤δ}, что f(x*) ≤ f(x) при всех x∈ Uδ(x*). (7.2) Здесь и далее 1/2

n  x  x *   ( xi  xi* )2  .  i 1 

Очевидно, что глобальное решение является и локальным; обратное неверно. 84

Определение 2. Если неравенство в (7.1) или (7.2) выполняется как строгое при x≠x*, т. е. f(x) < f(x*), x ∈ X (или x ∈ Uδ(x*)), то говорят, что x* – точка строгого минимума (строгое решение). Рассмотрим пример, иллюстрирующий введённые понятия. Пример. Пусть f(x) = x(x2 − 3). На отрезке Х = [−1,5; 2] функция f(x) достигает строгого локального минимума в точке х = −1,5 и строгого глобального минимума в точке х = 1. На отрезке Х = [–2, 2] она достигает глобального минимума в двух точках: х = –2, х = 1 (f(–2) = f(1) = –2). При изучении задач оптимизации в первую очередь возникает вопрос о существовании решения. Условия, гарантирующие разрешимость задачи (7.1), содержатся в следующей теореме из курса высшей математики. Теорема 1 (Вейерштрасса). Пусть Х – ограниченное замкнутое множество в Rn, f(х) – непрерывная функция на Х. Тогда существуют точки глобального минимума и максимума функции f на Х (глобальное решение задачи (7.1)). Теорема 1 отвечает на вопрос о существовании решения, но не даёт конструктивного алгоритма нахождения этого решения. Следует также учесть, что задача оптимизации может иметь несколько решений. Вопрос о единственности решения рассматривается отдельно для каждого класса задач. Классификацию задач оптимизации можно проводить по нескольким признакам в зависимости от вида исходных данных. Выделим наиболее важные из них. Задачи безусловной оптимизации – это задачи (8.1), в которых допустимым множеством Х является все пространство Rn. Задачами математического программирования называются задачи (8.1), если их допустимое множество задается системой конечного числа неравенств и уравнений, т. е. X={x ∈ P | gi(x) ≤ 0, i = 1, …, k; hi(x) = 0, i =k+1, …, m}. Среди них важнейшими являются следующие классы задач: - задачи линейного программирования; - задачи нелинейного программирования (задачи квадратичного программирования, задачи выпуклого программирования и др.). Задачами дискретного программирования называются задачи (7.1), если какие-либо из координат х1, …, хn пробегают дискретные множества на числовой оси, когда х пробегает Х.

85

Задачи оптимального управления относятся к классу бесконечномерных задач оптимизации, где в качестве допустимых множеств, по которым ведется минимизация, выступают множества функций. 7.2 Понятие о численных методах оптимизации. Любой численный метод (алгоритм) решения задачи оптимизации основан на точном или приближенном вычислении ее характеристик (значений целевой функции и функций, задающих границу допустимого множества, а также их производных). На основе полученной информации строится приближение к решению задачи – искомой точке минимума х* или, если такая точка не единственна, к множеству точек минимума. Иногда, если это требуется, строится приближение к минимальному значению целевой функции f*. Алгоритмы, использующие лишь информацию о значениях минимизируемой функции, называются алгоритмами нулевого порядка; алгоритмы, использующие также информацию о значениях первых производных, – алгоритмами первого порядка; алгоритмы использующие, кроме того, информацию о вторых производных, – алгоритмами второго порядка. Работа алгоритма состоит из двух этапов. На первом этапе вычисляются предусмотренные алгоритмом характеристики задачи. На втором этапе по полученной информации строится приближение к решению. Обычно для задания алгоритма достаточно указать способ выбора точек приближения xk = (х1k,…, хnk) ∈ Χ, k =1, 2, … (конечно, при условии, что уже решен вопрос о том, какие именно характеристики задачи следует вычислять). Определение 3. Выбор точек приближения называется поиском точек. Если все точки выбираются одновременно до начала вычислений, то алгоритм минимизации называется пассивным. Однако для решения большинства задач точки приближения выбираются поочередно, т.е. точка х(k+1) выбирается тогда, когда уже выбраны точки предыдущих вычислений х(1), х(2), …, х(k) и в каждой из них произведены предусмотренные алгоритмом вычисления. Такие алгоритмы называются последовательными. Определение 4. В последовательных алгоритмах вычисление характеристик задачи в точке х(k) и поиск точки х(k+1) вместе составляют шаг метода, или, что то же самое, итерацию метода. 86

Методы оптимизации можно условно разделить на две основные группы: конечношаговые и бесконечношаговые. Конечношаговыми, или конечными, называются методы, гарантирующие отыскание решения задачи за конечное число шагов. Бесконечношаговыми называются методы, для которых достижение решения гарантируется лишь в пределе. Важной характеристикой бесконечношаговых методов оптимизации является сходимость. Определение 5. Будем говорить, что метод сходится, если последовательность х(k) → х* при k → ∞, где х* – решение задачи (7.1). Если f(x(k)) → f(x*) при k → ∞, то последовательность х(k) называют минимизирующей. Заметим, что минимизирующая последовательность может и не сходиться к точке минимума. В случае, когда точка минимума х* не единственна, под сходимостью метода понимается следующее: для каждой точки х* минимума функции f можно построить данным методом такую последовательность х(k) ∈ Х, что х(k) → х* при k → ∞. Установление факта сходимости дает существенную информацию о выбранном методе минимизации. Прежде всего, требования, которые приходится налагать для обеспечения сходимости на минимизируемую функцию, показывают область применимости метода. Часто условия сходимости включают в себя в явном виде требования к начальному приближению. В то же время реальный процесс оптимизации не может быть бесконечношаговым. Кроме того, в ряде случаев условия сходимости труднопроверяемы. Поэтому при выборе подходящего метода решения реальных задач приходится во многом руководствоваться здравым смыслом, опытом, интуицией, а также результатами численных экспериментов. Необходимо также учитывать погрешность исходных данных. 7.3 Условия оптимальности в общей задаче оптимизации. При изучении любого типа задач оптимизации важное место занимает вопрос об условиях оптимальности, или, как еще говорят, условиях экстремума. Различают необходимые условия оптимальности, т.е. условия, которым должна удовлетворять точка, являющаяся решением задачи, и достаточные условия оптимальности, т.е. условия, из которых следует, что данная точка является решением задачи. Интерес к условиям оптимальности объясняется тем, что они, во-первых, составляют основу качественных методов теории оптимизации, т.е. методов, направленных на изучение свойств задач оптимизации; во-вторых, используются при по87

строении и обосновании численных методов решения этих задач; в третьих, позволяют в простых случаях явно решить задачу. Примером таких условий являются необходимые и достаточные условия локального экстремума, рассмотренные в предыдущей лекции. В общем случае суть всех критериев оптимальности для задачи (7.1) заключается в том, что из точки х*, являющейся локальным решением, нельзя осуществить сколь угодно малый сдвиг в каком бы то ни было направлении, приводящий к уменьшению значения целевой функции, и остаться при этом в пределах допустимого множества. Контрольные вопросы 1. Сформулируйте общую задачу оптимизации. 2. Дайте определение следующих понятий: целевая функция, допустимое множество, допустимая точка, решение задачи оптимизации. 3. Перечислите основные этапы реализации оптимизационной задачи. 4. Охарактеризуйте основные направления применения методов оптимизации в инженерной деятельности. 5. Приведите примеры оптимизационных задач из практики. 6. Дайте классификацию задач оптимизации. Лекция 8. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ План лекции 8.1 Постановка задачи и условия оптимальности. 8.2 Методы одномерной безусловной оптимизации. 8.3 Методы многомерной безусловной оптимизации 8.1 Постановка задачи и условия оптимальности В настоящее время промышленное производство, а вместе с ним и интенсивность эксплуатации ограниченных природных ресурсов достигли такого уровня, при котором человечество уже не может удовлетворять свои запросы только за счёт увеличения объёма производства и потребления ресурсов. Это заставило специалистов искать пути повышения эффективности производства посредством выбора наиболее выгодного техноло88

гического режима, обеспечивающего оптимальный объём выпускаемой продукции и высокое качество. Кроме того жёсткая конкуренция на рынках сбыта вынуждает уменьшать затраты на сырьё, рабочую силу, сокращать продолжительность производственного цикла, в том числе время на обработку информации. При всём разнообразии эти проблемы по существу сводятся к одной и той же схеме: имеется набор количественных параметров и некая количественная характеристика, зависящая от этих параметров; нужно найти те значения параметров, при которых данная характеристика достигает максимального или минимального значения, т.е. оптимизируется. Это и есть задача оптимизации 8.2 Методы одномерной безусловной оптимизации Изучение методов безусловной оптимизации начинается с наиболее простого типа оптимизационных задач, в которых целевая функция зависит от одной переменной. Необходимость отдельного рассмотрения численных методов поиска экстремума функций одной переменной диктуется следующими обстоятельствами. Во-первых, эти методы используются во многих алгоритмах поиска экстремума функций, зависящих от нескольких переменных. Вовторых, функции одной переменной служат удобной моделью для теоретического исследования эффективности методов оптимизации. В-третьих, иногда удаётся, используя те или иные приёмы, непосредственно с помощью алгоритмов одномерной оптимизации получить решение многомерных задач. Поскольку универсальных методов, пригодных для минимизации любых функций одной переменной, не существует, приходится строить алгоритмы, ориентированные на различные классы функций, встречающиеся в прикладных задачах. Рассмотрим методы минимизации так называемых унимодальных функций. Пусть Х = [a, b]. Определение 1. Функция f называется унимодальной на Х, если существует такая точка х*∈ Х, что для любых x1, x2∈ X f(x1) > f(x2), если х1 < x2 < x*, f(x1) < f(x2) , если х* < x1 < x2. Для непрерывных функций свойство унимодальности означает наличие у неё единственного локального минимума. 89

Если известен какой-либо отрезок [хk, хm], которому принадлежит х*, мы будем говорить, что точка минимума х* локализована в отрезке [хk, хm]. Сам отрезок при этом будем называть отрезком локализации минимума. В литературе интервал (хk, хm) называется интервалом неопределённости. Приступим к описанию алгоритмов минимизации унимодальных функций. Будем предполагать, если не оговорено противное, что минимизируемая функция унимодальна на отрезке [a, b] и используется информация лишь о значениях самой функции. Наиболее широкое применение в практике решения задач одномерной минимизации получили так называемые методы исключения интервалов, которые опираются на следующее утверждение. Теорема 2. Пусть функция f унимодальна на Х и х1 < x2. Тогда если f(x1) ≤ f(x2), то х* ≤ х2, если же f(x1) ≥ f(x2), то х* ≥ х1. Общая схема методов исключения интервалов состоит в следующем: 1. Задаем точность ε. 2. Рассчитываем x1 и x2. 3. Вычисляем e = f(x1) − f(x2). 4. Если x1 > x2 и е ≤ 0, то полагаем a = x2. Если x1 > x2 и e > 0, то полагаем b = x1. Если x1 < x2 и е ≤ 0, то полагаем b = x2. Если x1< x2 и е > 0, то полагаем a = x1. 5. Увеличиваем j: j = j + 1. 6. Если |b − a| > ε, то переходим к п. 2. В противном случае полагаем x* ≈ x1, fmin ≈ f(x*). Все методы исключения интервалов отличаются друг от друга тем, каким способом вычисляются точки x1 и x2. В процессе поиска очередного отрезка локализации методом золотого сечения на первом шаге точка x1 делит текущий отрезок в отношении золотого сечения. На всех остальных шагах в качестве точки x1 выбирается точка, уже лежащая внутри отрезка [a, b]. Точка x2 всегда вычисляется по формуле x2 = a + b – x1. 8.3 Методы многомерной безусловной оптимизации Первую группу классических методов минимизации составляют так называемые методы спуска. Наиболее важным среди методов второй группы является метод Ньютона и его модификации. Многие методы минимизации относятся к числу методов спуска. В методах спуска направление движения к минимуму на каждом шаге выбирается из числа направлений убывания минимизируемой функции. 90

Говорят, что вектор h = (h1, h2, ..., hn) задает направление убывания функции f в точке x, если существует такое число α0 > 0, что f(x + α h ) < f(х) при всех 0 < α < α0. Сам вектор h также называют направлением убывания. Множество всех направлений убывания функции f в точке x будем обозначать через U(x, f). Таким образом, если любой достаточно малый сдвиг из x в направлении вектора h приводит к уменьшению значения функции f, то h ∈ U(x, f). Заменив неравенство, фигурирующее в определении направления убывания, на противоположное, получим определение направления возрастания. В дальнейшем нам понадобятся следующие необходимое и достаточное условия направления убывания. Теорема 3. Достаточное условие. Пусть функция f дифференцируема в точке х ∈ Rn. Если вектор h удовлетворяет условию Необходимое условие. Если h ∈ U(х, f), то (∇ f(x),h) ≤ 0. Другими словами, теорема 3 утверждает, что вектор h задает направление убывания функции f, если он составляет тупой угол с вектором градиента ∇ f, указывающим, как известно из курса высшей математики, направление наискорейшего возрастания функции f. При n = 2 решению задачи безусловной оптимизации можно дать геометрическую иллюстрацию. Уравнению x3 = f(x1, x2) соответствует поверхность в трехмерном пространстве. Если функция f(x) достигает локального минимума в точке, то поверхность x3 = f(x1, x2) в некоторой окрестности точки x* имеет форму чаши. Геометрическая интерпрeтация двумерной задачи минимизации основана на понятии линии уровня. Напомним, что линиями уровня функции f(х1, х2) называют семейство линий плоскости R2, на которых функция принимает постоянное значение. Если функция f(x) имеет в R2 единственную точку локального минимума x* = (x1*, x2*), то такая функция называется мономодальной. Мультимодальными называются функции, у которых более одного экстремума. Такова, например, функция f(x) = ((x1)2 + (x2)2 +1)2 − 4(x1)2, имеющая две точки минимума: (1, 0) и (–1, 0). Общая идея методов спуска состоит в следующем. Для определения точки x* локального минимума функции f(x) строится последовательность точек {x(k)} (k = 0, 1, 2, …), сходящаяся к точке х* таким образом, чтобы последовательность значений функции f(х(k)) была монотонно убывающей и ограниченной: 91

f(x(0)) ≥ f(x(1)) ≥ … ≥ f(x(k)) ≥ … ≥ f(x*). Контрольные вопросы 1. Сформулируйте задачу безусловной оптимизации. 2. Каковы необходимые и достаточные условия оптимальности в задачах одномерной безусловной оптимизации? 3. Сформулируйте утверждение, на которое опираются все методы одномерной минимизации. 4. В чем состоит суть интерполяционных методов минимизации? 5. Дайте определение направления убывания. Сформулируйте необходимые и достаточные условия направления убывания. 6. Что такое моно- и мультимодальные функции?

92

Библиографический список 1. Блинов Ю.Ф. Методы математического моделирования / Ю.Ф. Блинов, В.В. Иванцов, П.В. Серба. – Ч.1, 2. [Электронный ресурс]. – Таганрог, ТТИ ЮФУ, 2012. – 42 с. 2. Барботько А.И. Основы теории математического моделирования: учебное пособие / А.И. Барботько, А.О. Гладышкин. – Старый Оскол: ТНТ, 2013 . – 212 с. 3. Маликов Р.Ф. Основы математического моделирования: учебное пособие / Р.Ф. Маликов. – Москва: Горячая линия-Телеком, 2010 . – 366 с. 4. Плохотников К.Э. Математическое моделирование и вычислительный эксперимент. Методология и практика / К.Э. Плохотников . – Изд. 2-е . – Москва : УРСС, 2011. – 280 с. 5. Сидняев Н.И. Теория планирования эксперимента и анализ статистических данных: учебное пособие / Н.И. Сидняев. – Москва: ЮРАЙТ, 2012 . – 399 с. 6. Советов Б.Я. Моделирование систем: практикум / Б.Я. Советов, С.А. Яковлев. – 4-е изд., перераб. и доп. – Москва: Юрайт, 2012. – 294 с. 7. Тарасевич Ю.Ю. Математическое и компьютерное моделирование: вводный курс: учебное пособие / Ю.Ю. Тарасевич. – Изд. 6-е. – Москва: ЛИБРОКОМ, 2013 . – 152 с. 8. Дьяконов В.П. MATLAB. Анализ, идентификация и моделирование систем. Специальный справочник / В.П. Дьяконов, В. Круглов. – СПб: “Питер”, 2001. 9. Хахулин Г.Ф. Основы конструирования имитационных моделей: учеб. Пособие / Г.Ф. Хахулин. – М.: НТК Поток, 2002. – 222 с. 10. Моделирование процессов и объектов в металлургии : учеб.-метод. пособие / Сиб. федерал. ун-т; сост.: Н.Н. Довженко, И.Н. Довженко, Э.А. Рудницкий. – 2013. 11. Чикуров Н.Г. Моделирование систем и процессов: учебное пособие / Н.Г. Чикуров. – 2013. 12. Моделирование обогатительных процессов: учеб.-метод. пособие для самостоят. работы / Сиб. федерал. ун-т; сост. В.И. Брагин. – 2012. 13. Морозов В.К. Моделирование информационных и динамических систем: учеб. пособие / В.К. Морозов, Г.Н. Рогачев. – 2011. 14. Моделирование систем: учебное пособие / И.А. Елизаров, Ю.Ф. Мартемьянов, А.Г. Схиртладзе, А.А. Третьяков. – Тамбов: Изд-во ФГБОУ ВПО «ТГТУ», 2011. – 96 с. 93

15. Лесин В.В. Основы методов оптимизации: учебное пособие / В.В. Лесин, Ю.П. Лисовец [и др.]. – 3-е изд., испр. – Санкт-Петербург: Лань, 2011 . – 340 с. 16. Моделирование процессов и объектов в металлургии. Версия 1.0 [Электронный ресурс] : конспект лекций / Б.М. Горенский, Л.А. Лапина, А.Ш. Любанова и др. – Электрон. дан. (2 Мб). – Красноярск: ИПК СФУ, 2008. 17. Беллман Р., Дрейфус С. Прикладные задачи динамического прграммирования. М.:Наука, 1965. 18. Хедли Дж. Нелинейное и динамическое программирование. М.:Мир, 1967. 19. Габасов Р., Кириллова Ф.М. Основы динамического программирования. Минск, БГУ, 1975.

94