2.2. Оптимальное моделирование

Допустим, имеется некоторая система Е, функционирование которой (деятельность) зависит от значений вектора управляемых параметров ͞X=(x₁,x₂, …., x_m). Эффективность системы Е оценивается вектором численных критериев ͞q=(q₁,q₂ ….q_s), причем q_i =q_i (͞x, ͞͞ω), i=͞1,͞s (ω – вектор неуправляемых параметров). Тогда задачу выбора оптимального решения (управления) можно формализовать следующим образом:

(14)

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

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

Неопределенность характеризуется вектором неуправляемых параметров ͞ω. Если ͞ω=const, то задача (14) сводится к детерминированной и имеет вид

(15)

Посмотрим, как можно свести задачу (14) к виду (15).

Если ͞͞ω представляется в виде случайных величин (или случайных функций), распределение которых хотя бы приближенно известно, то в задаче (14) они заменяются соответственно их математическими ожиданиями. Этот прием применяется при ориентировочных расчетах, когда дисперсии случайных величин малы, а также когда q_i. зависит от ͞ω линейно.

В целом случайный характер ͞ω приводит к моделям стохастического программирования, которые требуют специального рассмотрения.

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

Пример. Модель выбора оптимальной годовой производственной программы.

Допустим, известен ассортимент продукции, предполагаемый к выработке на предприятии. Пусть j – номер соответствующего сорта продукции ( ). Известны также группы оборудования, реализующие переработку каждого сорта. Обозначим время переработки j-го сорта на ρ-й группе оборудования через tρ_i ( ), реальный годовой фонд времени работы оборудования каждой группы через Tρ, затраты на переработку единицы измерения продукта через C_j , отпускаемую цену единицы измерения продукта через U_j. , объем выпуска j-сорта продукции через X_j.

Тогда задачу оптимизации программы выпуска продукции можно, например, записать так

(16)

(17)

(18)

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

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

1. Задача линейного программирования. Если критерий оптимизации q и функции fρ, характеризующие ограничения в D, линейные относительно переменных X_j , то задача оптимизации является задачей линейного программирования и может быть решена симплекс-методом.

2. Задача динамического программирования. Здесь процесс оптимизации заключается в поэтапном синтезе и последовательном анализе вариантов на каждом из N этапов. Критерий представляется в виде аддитивной

или мультипликативной функции

Функции векторов

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

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

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

5. Задача геометрического программирования. В этой задаче критерий оптимизации и ограничения представляются в виде полиномов вида

6. Задача дискретного программирования. Любая модель оптимизации, в которой имеются ограничения типа дискретности по всем координатам вектора ͞X (полностью дискретная задача) или по отдельным его координатам (частично дискретная задача) относится к классу задач дискретного программирования. Частным случаем являются задачи целочисленного программирования. В них требуется, чтобы все или часть X_j были целыми числами.

В зависимости от вида критерия оптимизации q(͞x) экстремум (максимум или минимум) может быть локальным, глобальным, внутренним, граничным, условным и безусловным.

В точке ͞X достигается локальный минимум, если q(͞x*) есть наименьшее значение функции q(͞x) в некоторой Ԑ - окрестности этой точки. Наименьший из всех локальных минимумов называется глобальным. Понятно, что если во всей области D имеется один локальный минимум, то он будет глобальным. В этом случае критерий оптимизации q(͞x) называется унимодальным (одноэкстремальным). Если q(͞x) в области имеет несколько локальных минимумов, то он называется многоэкстремальным.

Экстремумы называются граничными, если они достигаются в граничных точках области D, и внутренними, если они достигаются во внутренних точках области D .

Если экстремумы критерия q(͞x) ищутся в условиях отсутствия ограничений на вектор ͞X, то они называются безусловными, в противном случае – условными.

Допустим, например, что в модели (15) используются два критерия q₁(x) и q₂(x), значения которых необходимо минимизировать. Область допустимых решений формально зададим отрезком оси действительных чисел x [а,b]. Характер изменения значений критериев в нормированном масштабе приведен на рис. 2.5, который показывает, что оптимумы (минимумы) по каждому из критериев достигаются в точках X₁ и X₂ соответственно для q₂ и q₁. Далее, для x [a,x₁] и x [x₂, b] критерии q₂ и q₁ ведут себя согласованно, одновременно уменьшаясь либо увеличиваясь. Поэтому эти области «не интересны» с точки зрения поставленной задачи. Рассматривая теперь область допустимых решений x [x₂,x₁], видим, что уменьшение значений критерия ведет к увеличению значений критерия q₂, т.е. критерии конфликтуют.

Рис. 2.5. Поведение критериев q₁(x) и q₁(x) x [a,b]

Этот конфликт отображается в определенную область в пространстве критериев {q} (рис. 2.6), которое называется множеством Парето (переговорным множеством, конфликтным множеством).

Свойства этого множества зависят от свойств критериев оптимизации и области допустимых решений D.

При таких условиях решения x D, которые определяют множество Парето, будем называть не худшими или конфликтными решениями. Множество не худших решений обозначим через М₀.

а б

в

Рис. 2.6. Примеры множества Парето (Par): а – непрерывное; б – несвязное;

в – с изолированными точками

В общем случае для векторной модели оптимизации введем правило, позволяющее оценивать решения – безусловный критерий предпочтения (БКП). Решение X₂ безусловно лучше решения ͞x₁( ) в смысле векторного критерия ͞q, если q_i(͞x₂)≤ q_i(͞x₁) для всех i и хотя бы одно неравенство строгое. Если все q_i(͞x₂)= q_i(͞x₁), то решение ͞x₂ эквивалентно решению ͞x₁ (͞x₂ ͞x₁).

Из всего множества D допустимых решений БКП выделяет подмножество M₀ наихудших конфликтующих между собой, определяющих множество Парето. Другими словами, оператор БКП реализует принцип оптимизации по Парето.

Действительно (рис.2.6), x [a, x₁], x₁ , т.к. q₂ (x₁)<q₂(x)и q₁(x₁)<q₁(x). То же самое – x₂ x x₂,b], в области те же [x₁,x₂] любые x конфликтуют по критериям.

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

• для выпуклых областей D и выпуклых q_i(x), :

,

• для невыпуклых задач:

при всех:

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

Имея в своем распоряжении множество компромиссных вариантов , ЛПР в большинстве случаев не может выбрать «наилучшие» из-за большого их количества и большого числа критериев их оценки. Поэтому актуальной задачей является сужение множества , выдача для оценки специалистам ограниченного числа решений. В каждом случае такое сужение можно проводить с учетом поставленных целей, конкретных условий (наличие определенной ПК, времени и средств), при помощи алгоритмов, разработка которых в настоящее время представляет важную для практики задачу. Естественно, сужение приводит к потере информации о множестве и только ценой этих потерь можно более кратко его описать. Наиболее простым способом в решении указанной проблемы является покрытие множества сетью с некоторым шагом по критериям с тем, чтобы в каждом полученном разбивкой гиперпараллелепипеде оставить по одному элементу множества . Длину шага можно выбирать из практических соображений на основе экспертного анализа. Более общим является использование алгоритмов распознавания образов.

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

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