Решение задачи оптимизации.

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

4. Опрос: Решение, Элементы решения, оптимизация, показатель эффективности

5. Домашняя работа: Выучить конспект лекции, будет опрос на отметку

Лекция №2

Тема 1.2. Математические модели. Общие принципы построения математических моделей.

Введение

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

Модель - это объект любой природы, который создается исследователем с целью получения новых знаний об объекте-оригинале и отражает только существенные свойства оригинала.
Любая модель субъективна, она несет на себе печать индивидуальности исследователя.
Математическая модель имеет форму функциональной зависимости Y = F(X), где Y = {y1,…,ym} и X = {x1,…,x2} - соответственно характеристики и параметры моделируемой системы и F - функция, воспроизводимая моделью. Построение модели сводится к выявлению функции F и представлению ее в форме, пригодной для вычисления значений Y = F(X). Модель позволяет оценивать характеристики Y для заданных параметров X и выбирать значения параметров, обеспечивающие требуемые характеристики, с использованием процедур оптимизации. Впервые математические модели были использованы для решения практической задачи в 30-х годах в Великобритании при создании системы управления противовоздушной обороной. Для разработки данной системы были привлечены ученые различных специальностей. Система создавалась в условиях неопределенности относительно возможных действий противника, поэтому исследования проводились на адекватных математических моделях. В то время впервые был применен термин: "операционное исследование", подразумевавший исследования военной операции. В последующие годы операционные исследования или исследования операций развиваются как наука, результаты которой применяются для выбора оптимальных решений при управлении реальными процессами и системами.
Можно выделить следующие основные этапы операционного исследования:
1) наблюдение явления и сбор исходных данных;

2) постановка задачи;

3) построение математической модели;

4) расчет модели;

5) тестирование модели и анализ выходных данных.

Если полученные результаты не удовлетворяют исследователя, то следует либо вернуться на этап 3, т.е. предложить для решения задачи другую математическую модель; либо вернуться на этап 2, т.е. поставить задачу более конкретно;

6) применение результатов исследований.

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

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

Рассмотрим классификацию и принципы построения математических моделей.

Можно выделить следующие основные этапы построения математической модели:

1. Определение цели, т.е. чего хотят добиться, решая поставленную задачу.

2. Определение параметров модели, т.е. заранее известных фиксированных факторов, на значения которых исследователь не влияет.

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

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

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

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

Рассмотрим классификацию математических моделей, которая представлена на рис.1.

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

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

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

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

В детерминированных моделях неизвестные факторы не учитываются.

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

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

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

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