Классификация оптимизационных методов и моделей

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

1. По характеру взаимосвязи между переменными -

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

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

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

а) задачи в условиях полной определенности (детерминированные),

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

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

Сочетание признаков 1-5 позволяет группировать (классифицировать) в самом общем виде задачи и методы оптимального программирования.

Если критерий эффективности Z = f(x₁, x₂, …, a₁, a₂, …) (5.1.2) представляет линейную функцию, а функции j _i(x₁, x₂, …, x_n) в системе ограничений (5.1.1) также линейны, то такая задача является задачей линейного программирования. Если, исходя из содержательного смысла, ее решения должны быть целыми числами, то эта задача целочисленного линейного программирования. Если критерий эффективности и (или) система ограничений задаются нелинейными функциями, то имеем задачу нелинейного программирования. В частности, если указанные функции обладают свойствами выпуклости, то полученная задача является задачей выпуклого программирования.

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

Если критерий эффективности (5.1.2) и система ограничений (5.1.1) задаются функциями вида

то имеем задачу геометрического программирования. Если функции f и (или) j в выражениях (5.1.1) и (5.1.2) зависят от параметров, то получаем задачу параметрического программирования; если эти функции носят случайный характер - задачу стохастического программирования. Если точный оптимум найти алгоритмическим путем невозможно из-за чрезмерно большого числа вариантов решения, то прибегают к методам эвристического программировании, позволяющим существенно сократить просматриваемое число вариантов и найти если не оптимальное, то достаточно хорошее, удовлетворительное с точки зрения практики, решение.

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

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

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

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

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

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

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

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

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

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

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

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

Для того чтобы из множества критериев, в том числе и противоречащих друг другу (например, объем реализации и затраты), выбрать целевую функцию, необходимо установить приоритет критериев. Обозначим f₁(x), f₂(х),.... f_n(x) (здесь х - условный аргумент). Пусть они расположены в порядке убывания приоритетов. В зависимости от определенных условий возможны в основном два варианта:

• в качестве целевой функции выбирается критерий f,(x), обладающий наиболее высоким приоритетом;

где w₁, w₂, …, w_n - некоторые коэффициенты (веса).

Величина f(х), учитывающая в определенной степени все критерии, выбирается в качестве целевой функции.

В условиях определенности w_i - числа, f(x)_i - функции. В условиях неопределенности f_i(х) могут оказаться случайными и вместо f(x) в качестве целевой функции следует рассматривать математическое ожидание суммы (5.1.6).

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

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

Значительный вклад в формирование и развитие исследования операций внесли зарубежные ученые Г. Данциг, Р. Акоф, Р. Беллман, Г. Кун, Дж. Нейман, Т. Саати, Р. Черчмен, А. Кофман и др.

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

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

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

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

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

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

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

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

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

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

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

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: