Модели исследования операций. Оптимизационные модели

Это очень важный класс моделей, имеющих непосредственное отношение к проектной задаче. Анализ искусственной системы (т.е. экспертная задача) важен не сам по себе, а для решения проектной задачи – улучшения существующей системы, или же создания новой системы с большими возможностями, более экономичной и т.п. То есть для рационализации и оптимизации системы, процессов в ней, улучшения её связей с надсистемой и внешней средой. Позже мы уточним понятия оптимальности и рациональности.

Из лекции 1 известно, что постановкой и решением оптимизационных задач в разных сферах деятельности, – экономике, технике, военном деле, транспорте, – занимается наука «исследование операций». Соответствующие математические модели называются оптимизационными.

Математическими методами и алгоритмами решения оптимизационных задач занимается наука «математическое программирование» ( это искаженный перевод англоязычного термина mathematical planning – «математическое планирование»). Не надо путать с программированием – составлением программ для компьютеров!

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

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

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

Напомним, что операцией называется любое действие либо последовательность действий, имеющие общую цель или систему целей. Исследование операций исходит из того, что субъект операции (оперирующая сторона), – исследователь, лицо принимающее решения (ЛПР), – способен количественно оценить соответствие результатов операции ее цели (целям) с помощью одной целевой функции (скалярной ЦФ) или нескольких целевых функций (векторной ЦФ).

У исследования операций две основные задачи:

1) Рассчитать целевые функции по модели системы – это прямая задача исследования операций;

2) Оптимизировать систему – найти максимальные (или минимальные) значения целевых функций и соответствующие им оптимальные значения параметров (оптимальный план) – это обратная задача.

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

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

Различают структурную оптимизацию, параметрическую оптимизацию и оптимальное управление.

Этапами исследования операций являются:

1) Техническая постановка задачи: построение содержательной модели объекта или процесса с определением целевой функции и оптимизируемых параметров.

2) Математическая постановка задачи – это и есть оптимизационная модель, которая имеет вид:

F( ) → max

G

Здесь F( ) – целевая функция (скалярная).

– вектор оптимизируемых параметров; часто – это матрица .

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

3) Решение оптимизационной задачи методами математического программирования.

4) Анализ результатов исследования и выдача рекомендаций.

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

Оптимизируемые параметры (или ) могут изменяться непрерывно, либо принимать дискретные значения, чаще всего – это целочисленные значения, например количество процессоров в системе управления.

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

Изучение этих разделов математического программирования, их методов и алгоритмов является предметом отдельного курса. Просто приведем некоторые примеры.

1)Линейное программирование (ЛП): здесь и целевая функция и все ограничения – линейные функции, т.е. они содержат оптимизируемые параметры в первой степени.

В качестве примера рассмотрим непрерывную транспортную задачу ЛП (например, перевозится зерно).

Имеются m пунктов («складов»), с товарами (продукцией) объемом соответственно. Имеются n пунктов назначения («потребителей») , которым надо поставить товары объемом не менее , соответственно. Обозначим через стоимость перевозки единицы груза между складом и потребителем . Оптимизируемые параметры: – количество (объем) товара, перевозимого со склада потребителю . Мы должны спланировать перевозки товара так, чтобы их суммарная стоимость была минимальной.

Оптимизационная модель этой задачи имеет вид:

Целевая функция:

Ограничения:

Объемы перевозок неотрицательны:

Запросы потребителей должны быть удовлетворены:

Ограничения на объемы поставок:

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

Любое решение задачи, – матрица , удовлетворяющая ограничениям, – называется планом или допустимым планом. Лучший из планов доставляет минимум (в нашем случае) целевой функции. Он называется оптимальным планом. Решение оптимизационной задачи – это оптимальный план и значения его ЦФ.

На могут быть положены требования целочисленности (мы перевозим автомобили, например). Тогда задача называется целочисленной транспортной задачей. В общем случае – целочисленной задачей линейного программирования (задачей ЦЛП).

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

2) В качестве примеров задачи булевого программирования (здесь параметры могут принимать всего два значения – это либо 0, либо 1) рассмотрим две задачи о назначениях – линейную («классическую») и минимаксную (нелинейную).

Содержательная постановка линейной задачи о назначениях.

Имеется исполнителей («рабочих») имеется столько же работ («станков») . Производительность i-го рабочего на j-том станке – . Соответственно имеем квадратную матрицу полезностей (она также называется матрицей выгод). Необходимо так расставить рабочих по станкам (каждому станку – одного рабочего), чтобы суммарная производительность была максимальной.

Целевая функция:

Ограничения:

В минимаксной задаче матрица – это матрица затрат и нужно найти план, в котором максимальные затраты минимальны:

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

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

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

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

1. Эти методы делятся на точные и приближенные.

2. Они содержатся в программных продуктах, таких как MATLAB, Maple, AnyLogic в виде библиотек или в виде универсального (поискового) оптимизатора.

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

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

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

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

Наконец, существуют модели, описывающие поведение аналогов «мыслящих» субъектов, так называемых «систем с рефлексией». Это – «системы, содержащие в себе модели других систем, сравнимых с ними по сложности» [Лефевр]. Этими вопросами занимаются теория рефлексивного управления, теория рефлексивных игр.