Математическое моделирование ( дополнительные главы математики )

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

Изучаемый ( управляемый ) процесс в этом случае также описывается математической моделью, так что имеется совокупность соотношений, связывающих входные и выходные параметры процесса. Среди всего множества параметров существуют такие, которые доступны нам для изменения, величиной которых мы можем управлять. Такие параметры процесса называются переменными управления. Например, при моделировании процесса электрического пробоя воздушного промежутка величина пробивного напряжения зависит от многих параметров : U р = f(d, E max, E cr, p, T, …). В зависимости от задачи моделирования один или несколько параметров можно менять, например E max и d. Переменные управления 3

В общем случае переменных управления может быть много (u = {u 1, u 2, …, u n }) и каждая комбинация этих переменных описывает определенное состояние системы. Поскольку результат каждого действия можно оценить количественно, то существует некоторая функция, сопоставляющая каждой возможной в данной модели комбинации значений переменных управления некоторое число, количественно описывающее состояние системы (u)=f(u 1, u 2, …, u n ). Эта функция называется целевой функцией. Целевая функция 4

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

В простейшей модели для выбора сечения провода учтем затраты на сооружение линии ( главным образом на покупку провода ) и потери энергии в линии ( на активном сопротивлении ). Затраты на провод : Ф 1 = S L C 1 + C 2, Потери на нагрев : Суммарные затраты : Ф = Ф 1 + Ф 2 Пример. Выбор сечения проводов ЛЭП 6

7 S

Виды оптимизационных задач В зависимости от вида модели и функции Ф (u) используют различные методы для решения соответствующих оптимизационных задач. Однокритериальные оптимизационные задачи Функция одной переменной Функция нескольких переменных Линейное программирование Нелинейное программирование Многокритериальные модели 8

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

Решаться такая задача может как аналитически, так и численными методами, в зависимости от вида анализируемой функции. При этом надо иметь в виду : 1) существует область определения и область допустимых значений анализируемой функции ; 2) производная обращается в нуль как в максимумах, так и в минимумах, а решением является экстремум только одного вида ; 3) функция может иметь несколько экстремумов, при этом решением задачи является наибольший максимум или наименьший минимум. Однокритериальные оптимизационные задачи 10

Пример 11 Ф(х) dФ(х)/dx

1. Определить область определения и область допустимых значений функции. 2. Вычислить производную целевой функции. 3. Найти корни производной целевой функции. При нахождении корней численными методами поиск надо начинать из разных точек, с разными начальными приближениями, чтобы по возможности найти все экстремумы. 4. Выбрать те корни, которые входят в область определения функции. 5. Вычислить значения целевой функции для значений переменной управления, являющихся корнями производной. 6. Вычислить значения целевой функции для крайних точек ее области определения. 7. Исключить из вычисленных значений те, которые не принадлежат области допустимых значений функции. 8. Выбрать среди вычисленных значений целевой функции то значение, которое соответствует критерию оптимальности. Последовательность решения 12

Рассмотрим задачу. Пусть имеется m видов сырья в количествах b 1, b 2, …, b m. ( Медный провод, электротехническая сталь, трансформаторное масло и др.) Из этого сырья можно изготовить n видов продукции ( трансформаторы, электродвигатели, реакторы и т. д.). Для изготовления каждого вида продукции нужно использовать разное количество разных видов сырья. Вопрос : какую продукцию и в каких количествах выгоднее всего изготавливать ? Функция нескольких переменных 13

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

Обозначим : x j – количество продукции j- го вида ; c j – стоимость единицы продукции j- го вида. Тогда целевую функцию, максимум которой надо искать, можно записать в виде суммарной стоимости произведенной продукции : x 1 c 1 + x 2 c 2 + … + x j c j + … + x n c n или Целевая функция 15

Для производства единицы продукции j- го вида требуется сырье разных видов в количествах a 1j, a 2j, …, a ij, …, a mj, соответственно для x j единиц продукции потребуется a ij x j единиц i- го вида сырья. Поскольку каждый вид сырья используется для производства разных видов продукции, то суммарный расход каждого вида сырья не должен превышать имеющееся количество этого сырья, т. е. a 11 x 1 + a 12 x 2 + … + a 1n x n b 1 a 21 x 1 + a 22 x 2 + … + a 2n x n b 2 или в общем виде Ограничения на сырье 16

Добавим к этому ограничения на неотрицательность количества произведенной продукции: x 1 0, x 2 0, … x j 0, … x n 0, и получим следующую экстремальную задачу: найти при условиях 1)x j 0, j = 1, 2, …, n; 2) Формулировка задачи 17

Всякий набор значений x 1, x 2, …, x n, удовлетворяющий условиям 1 и 2, называется допустимым планом (стратегией, управлением). Тот допустимый план, при котором целевая функция имеет максимальное значение, называется оптимальным планом (стратегией, управлением). Рассматриваемая задача имеет простую структуру – целевая функция и все ограничения линейны, т.е. описываются линейными уравнениями. Такие экстремальные задачи получили название задач линейного программирования. Допустимый и оптимальный планы 18

Пример решения задачи Рассмотрим случай с выпуском продукции двух видов (x 1 и x 2 ), для которых используется сырье четырех видов (a 1, a 2, a 3, a 4 ). Целевая функция в этом случае выглядит следующим образом : x 1 c 1 + x 2 c 2. Проведем геометрический анализ этой задачи. 19

Геометрический анализ задачи Найдем область определения целевой функции. Из условия x j 0 следует, что любой допустимый план обязательно находится в первом квадранте 20 x1x1 x2x2

Геометрический анализ задачи Условие 2 представляет собой уравнения : a 11 x 1 + a 12 x 2 b 1 a 21 x 1 + a 22 x 2 b 2 a 31 x 1 + a 32 x 2 b 3 a 41 x 1 + a 42 x 2 b 4 21 x1x1 x2x2

Геометрический анализ задачи 22 Преобразуем первое уравнение ( выразим x 2 ): a 11 x 1 + a 12 x 2 b 1 x 2 b 1 / a 12 –(a 11 /a 12 )x 1 Построим график : x1x1 x2x2

Геометрический анализ задачи 23 Аналогично для остальных трех уравнений : x1x1 x2x2

Геометрический анализ задачи 24 Множество допустимых планов представляет собой область, расположенную внутри и на границах многоугольника, ограниченного осями и линиями, соответствующими количеству сырья : x1x1 x2x2

Геометрический анализ задачи 25 Среди всех этих планов надо найти точку, соответствующую оптимальному плану Целевая функция x 1 c 1 + x 2 c 2 также представляет собой прямую. Зададим число Ц так, чтобы x 1 c 1 + x 2 c 2 = Ц пересекала область допустимых планов x1x1 x2x2

Геометрический анализ задачи 26 x1x1 x2x2 Общие точки этой прямой и многоугольника допустимых планов соответствуют планам с одинаковой экономической эффективностью – стоимость произведенной продукции для каждого из этих планов в точности равна Ц

Геометрический анализ задачи 27 x1x1 x2x2 Начнем теперь перемещать прямую x 1 c 1 + x 2 c 2 = Ц параллельно самой себе в сторону возрастания Ц – ведь чем больше Ц, тем выгоднее план

Геометрический анализ задачи 28 В конце концов прямая x 1 c 1 + x 2 c 2 = Ц совпадет с одной из вершин многоугольника или с одной из его сторон x1x1 x2x2

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

Большее количество переменных 30 В случае, когда переменных управления больше двух, т. е., например, оптимизируется выпуск 3- х, 4- х и т. д. видов продукции, многоугольник допустимых планов превращается в многогранник, а секущая критериальная прямая – в плоскость, проходящую через одну или несколько вершин

Нелинейное программирование В рассмотренном примере расход сырья может быть не пропорционален объему выпуска, а зависеть от него нелинейно, либо стоимость единицы продукции может зависеть от объема выпуска ( накладные расходы ) Экстремальные задачи, в которых либо ограничения, либо целевая функция, либо и то и другое нелинейны, называются задачами нелинейного программирования 31

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

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

Многокритериальные модели Рассмотренные ситуации имели очень важное свойство – в каждой из них имелась единственная целевая функция. Единственность целевой функции обеспечила возможность создания эффективных методов решения оптимизационных задач. Однако, возникает вопрос : хорошо ли такие оптимизационные модели описывают реальную ситуацию ? Ответ на него неоднозначен 34

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

Методы решения многокритериальных задач при условиях 1) x j 0, j = 1, 2, …, n; 2) Усложним, добавив в него еще одну цель : допустим, надо максимизировать выпуск продукции первого вида ( х 1 ) 36

Многокритериальная задача ( А ) max x 1 ( Б ) при условиях 1) x j 0, j = 1, 2, …, n; 2) 37

Задача А Если забыть о целевой функции Б, то решение оптимизационной задачи А мы рассмотрели в предыдущем примере и нашли оптимальные значения х 1 и х 2. Но при этом нет никакой уверенности, что найденное значение х 1 соответствует целевой функции Б. 38

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

40 x1x1 x2x2

Оптимальный план Вообще говоря, в многокритериальной задаче понятие оптимального плана претерпевает изменение. Действительно, можно сказать, что план х 1 хуже, чем план х 2, если выполняются неравенства < и х 1 1 < x 1 2 Но определить, какой план называется оптимальным, в такой задаче невозможно, так как не существует такого плана, который одновременно обеспечил бы максимум целевым функциям А и Б 41

Как быть ? По этой причине методы решения многокритериальных задач предусматривают учет мнения лица, принимающего решение ( ЛПР ). Этим лицом может быть директор завода, начальник цеха и т. д., т. е. человек, отвечающий за решение той или иной задачи и принимающий управленческие решения, обеспечивающие ее выполнение. ЛПР может решить многокритериальную задачу методом сведения нескольких критериев к одному либо методом последовательных уступок 42

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

Метод последовательных уступок При этом методе также необходимо волевое решение ЛПР, принятое из внемодельных соображений ( знания проблемы, накопленного опыта и т. д.). При решении задачи находится экстремум одной из целевых функций, например Б (max x 1 = min(b i /a i1 )). Теперь, понимая, что при этом значении x 1 до максимума целевой функции А далеко, ЛПР делает уступку. Он согласен, чтобы x 1 не равнялось точно оптимальному значению, но отличалось от него не более, чем на 10%. 44

При этом исходная задача преобразуется к следующему виду : при условиях 1) x j 0, j = 1, 2, …, n; 2) 3) 0,9max x 1 < x 1 < 1,1max x 1 45 Метод последовательных уступок

Таким образом, надо найти экстремум целевой функции А в диапазоне изменения x 1 [0,9max x 1 ; 1,1max x 1 ]. Это задача с единственной целевой функцией, она может быть решена известными методами. ЛПР должен проанализировать найденное решение. Если результат удовлетворяет его – решение найдено. Если же нет – ЛПР может сделать еще одну уступку, например, он согласен, чтобы x 1 отличалось от оптимального значения не более, чем на 20%. В этом случае условие (3) запишется в виде 3) 0,8max x 1 < x 1 < 1,2max x 1 и задача снова может быть решена. 46 Метод последовательных уступок

47 x1x1 x2x2