3. Многокритериальные задачи оптимизации. Под нормализацией векторного критерия при многокритериальной оптимизации понимается
5. Принятие решений в условиях многокритериальности
5.1 Источники многокритериальности в зпр в управлении экономикой
В общем, любая задача принятия решения в условиях рыночной экономики является многокритериальной. Поэтому отдельного внимания заслуживают вопросы поиска причин подобной многокритериальности и возможности использования для этих целей соответствующих математических методов.
Известно, что на протяжении длительного периода социалистической экономики конструирование так называемых оценочных показателей (примеры: удельный вес продукции ВКК, «нормативно-чистая», «товарная», «реализованная» и другие виды продукции и т.п.) относилось к главным прикладным задачам экономической науки. Сегодня ситуация иная – становление рыночных отношений. В условиях рынка показатель эффективности один – прибыль, и таким образом, как бы исчерпывается возможный набор критериев принятия решений его свободным участником. Возникает вопрос: а нужны ли в условиях рынка все эти методы многокритериальной оптимизации, и если да, то зачем? На первую половину вопроса можно легко ответить, обратившись к опыту развитых стран с рыночной экономикой. Есть ли там такие методы? Ответ: да, есть. Попробуем понять, почему. Действительно генеральная цель фирмы на рынке - максимизация прибыли. Но достигается она не непосредственно, а путем преследования частных целей более низкого уровня. Проиллюстрируем данное утверждение рис.14
максимизация прибыли
достижение снижение правильное наилучшее
максимального производствен- решение продвижение
качества ных издержек вопроса «что товара
выпускать»
(совокупности
параметров (статьи затрат)
качества)
Рис.14 Иерархия целей предприятия (организации)
Т.е. цель «максимизации прибыли» сводится к установлению значений большего числа качественных и количественных параметров - частных целей. Эти цели могут конкурировать между собой (причины здесь могут быть как чисто технические - например - мощность автомобиля и расход топлива, так и «ресурсо - экономические» - например - средств в различные виды рекламы - печатную, аудио-видео и т.д.). Связь значений этих примеров с прибылью во многих случаях чрезвычайно сильно опосредована, неформальна и достаточно не изучена, т.е. пересчитывать всё в деньги достаточно надёжно и просто не удаётся.
Вторая причина многокритериальности ЗПР в экономике - влияние фактора времени - пространства. И результаты экономической деятельности, и затраты распределены, поэтому приходится соизмерять «ценность» прибыли сегодня, завтра и через год, перспективы развития отделений фирмы в разных регионах (даже - странах) и т.д. Известные приёмы свёртки (например, для распределения во времени - дисконтирование) несут в себе изрядную долю субъективизма (причём субъективизма автора методики, а не эксперта - ЛПР!)
Постановка задач принятия решений при многих критериях принципиально связана с двумя обстоятельствами. С одной стороны, эти задачи близки к задачам принятия решений в условиях неопределенности, так как различные варианты решений должны оцениваться также и в отношении вероятности их успеха и связанного с этим риска. С другой стороны, в многокритериальных задачах принятия решений в условиях определенности учет большого числа критериев основан на отказе от традиционного допущения того, что выбор одной из альтернатив всегда осуществляется на основе лишь одного критерия. В таких ситуациях скалярная задача оптимизации заменяется задачей векторной оптимизации.
Стремление учета этих двух обстоятельств вело по пути разработки математической модели, которая отображала бы многомерную систему целевых функций в скалярный критерий оптимальности. Такой подход неявно требует допущения о наличии у лица, принимающего решение, специальных функций предпочтения. Справедливость этого допущения заранее не очевидна. Однако это направление имеет довольно развитую теорию решений таких задач.
Рассмотрим некоторые примеры типичных постановок многокритериальных задач оптимизации.
Требуется определить необходимое количество ресурса (средств) K1 и рациональный способ его использования (за критерий можно принять результат использования этого ресурса К2). Примером такой постановки служит задача проектирования оборудования для изготовления пластиковых стаканчиков, характеризуемого стоимостью производства и эксплуатации (К1) и максимальным сроком службы (К2).
Если ресурсы, требующиеся для достижения поставленных целей неоднородны, то общий векторный критерий будет сформирован из частных, где Кi – количество «ресурса» i-го типа. Примером является задача планирования комплексной научно-исследовательской работы специалистов разных профилей.
Многокритериальная ЗПР возникает при множественности поставленных целей. В качестве составляющих общего критерия принимают Ki – степень достижения i-ой цели. Соответственно наилучшим образом такая формализация подходит для задач проектирования многоцелевых систем.
При структуризации общей цели в виде иерархии (“дерева целей”) построение векторного критерия будет осуществлено из Кij – степени достижения i-ой подцели j-го уровня. Типичным случаем подобных постановок являются задачи программно-целевого планирования развития сложных систем.
Задача заключается в необходимости оценки эффективности системы на всем ее жизненном цикле. Составными частями векторного критерия будут выступать показатели эффективности функционирования системы на выделенных этапах цикла Ki, где i – количество этапов жизненного цикла. Например, при планировании развития сложных систем необходимо оценивать стоимость создания системы, работу ее в период эксплуатации и эффективность возможного применения.
Характер многокритериальности носит и задача оценки эффективности сложной системы, функционирующей в различных условиях. В этом случае сводный критерий формируется из Кi – критерия эффективности системы, работающей при i-ом варианте условия. Так, полет авиалайнера должен происходить и днем, и ночью, а также при различных погодных условиях.
Следует рассматривать возможность использования векторного критерия при необходимости оценки эффективности совокупности взаимосвязанных систем. В качестве частного критерия принимается критерий эффективности i-ой (под) системы Кi. Примером может служить оценка ущерба предприятия, состоящего из нескольких цехов или производственных помещений с установленным технологическим оборудованием.
При необходимости оценивания эффективности системы в динамике, за определенный период времени, следует формировать общий критерий из критериев эффективности в i-ый «контрольный» момент времени Ki (на i-ом шаге). Примером служит задача планирования развития сложной системы за m-летний период.
В случае оценки эффективности с разных “точек зрения” также возникает многокритериальная постановка задачи. При необходимости принятия решения по инвестиционному проекту его следует оценивать по всем показателям (NPV, IRR, PV, рентабельности и др.).
Общая задача заключается в следующем:
Векторная целевая функция F(X)=[fi(X)] включает такие частичные целевые функции fi(X), которые не сводятся (по крайней мере, на первом этапе моделирования) в единую целевую функцию и выражают степени удовлетворения различных потребностей. Решение, оптимальное по одной из частичных целевых функций, называется субоптимальным. В общем случае субоптимальные решения для различных частичных целевых функций не совпадают. Отсюда вытекает необходимость выбора таких решений, которые являются наилучшими с точки зрения совокупности частичных целевых функций.
Самым простым решением таких задач является исследование множества эффективных значений функции F=(fi) на основе принципов оптимальности по Парето. Это - классическая задача векторной оптимизации. Однако решить такую задачу крайне не просто. Ситуация облегчается, если множество эффективных решений X* замкнуто и выпукло, а максимизируемые функции fi(X) – вогнутые (т.е. задачи субоптимизации есть задачи выпуклого программирования). Если множество X* невыпукло и не все fi(X) вогнутые, то нахождение эффективных решений усложняется. Применяются разнообразные приемы зондирования Парето – границы и нахождение ее характерных точек (например, с помощью теоремы Гермейера). Выделение множества Парето при решении многокритериальных задач часто не является удолетворительным решением. Это связано с тем, что при большом исходном множестве вариантов множество Парето оказываетсям недопустимо большим для того, чтобы ЛПР было бы в состоянии осуществить окончательный выбор самостоятельно.
Кроме того, следует учесть тот момент, что выявление эффективеых альтернатив может происходить и тогда, когда сравниваемые альтернативы заданы в векторной форме. Традиционным способом найти множество эффективных решений X* нельзя. Сравнение векторов следует проводить с использованием следующих определений.
Пусть заданы вектор a=(a1,a2,,ai,an) и b=(b1,b2,,bi,,bn).
Вектор a доминирует по отношению () вектор b, если ai bi, i = 1,n
Вектор a доминирует по отношению () вектор b, если ai > bi, i = 1,n
Тогда множество недоминируемых по отношению () решений является множеством эффективных оценок, а множество недоминируемых решений по отношению (>) называется множеством слабоэффективных оценок. Построив матрицу БО по заданным отношениям можно решить задачу выделения эффективных и слабоэффективных решений для альтернатив, заданных вектором.
Но и здесь возможна некоторая проблема. Суть ее состоит в том, что все сравниваемые альтернативы могут быть эффективны. Тогда, применяя специальные процедуры многокритериальной оптимизации, следует выделять ядро бинарных отношений, в которое входят эффективные и несравнимые с ними альтернативы.
Таким образом, выделение множества Парето можно рассматривать лишь как предварительный этап оптимизации, и налицо проблема сокращения этого множества.
Дальнейший поиск во множестве эффективных решений может быть осуществлен только на основе некоторых принципов принятия решений. Рассмотрим некоторые из них. При этом полагаем, что все критерии являются нормализованными, т.е. приведенными к одному, часто безразмерному масштабу времени.
Принцип равономерности. Состоит в стремлении к равномерному и гармоничному улучшению решения по всем локальным критериям.
Принцип равенства. Наилучшим решением является такое, при котором достигается равенство всех локальных критериев. Данный принцип очень «жесткий» и может приводить к решениям вне множества эффективных решений и даже не иметь их, особенно в дискретных случаях.
Принцип максмина. Идея равномерности состоит в стремлении повышать уровень всех критериев за счет максимального «подтягивания» наихудшего из критериев (имеющего наименьшее значение).
Принцип квазиравенства. Решение считается наилучшим, если значения отдельных критериев отличаются друг от друга не более чем на величину .
Принцип справедливой уступки.
Принцип абсолютной уступки. Наилучшим является такое решение, при котором суммарный абсолютный уровень снижения одного или нескольких критериев не превосходит суммарного абсолютного уровня повышения других. Принцип оптимальности состоит в максимизации суммы критериев.
Принцип относительной уступки. Наилучшим считается такое решение, при котором суммарный относительный уровень снижения одного или нескольких критериев не превосходит относительного суммарного уровня повышения по остальным критериям. Принцип оптимальности состоит в произведении локальных критериев.
Принцип выделения главного критерия. Из совокупности локальных критериев выбирается один и принимается в качестве главного. К уровню других критериев предъявляется требование, чтобы они были не меньше некоторых заданных значений, образуя область, в которой ищется решение, наилучшее в смысле главного критерия.
Принцип последовательной уступки. Предположим, что локальные критерии расположены в порядке убывания важности. Процедура поиска наилучшего решения сводится к следующему. Сначала ищется решение наилучшее в смысле критерия f1. Затем назначается из некоторых практических соображений и точности исходных данных некоторая «уступка» f1, которую мы согласны допустить для того, чтобы найти решение, наилучее в смысле критерия f2. Далее описанная процедура последовательно повторяется для оставшихся критериев. Такой способ поиска наилучшего критерия хорош тем, что сразу видно ценой какой «уступки» в одном критерии приобретается выигрыш в другом.
Конкретная реализация принципов принятия решений выступает в виде алгоритмов или процедур решения задач многокритериальной оптимизации. Практически все известные подходы к решению этих задач предполагают их скаляризацию. При этом одним из главных вопросов является учет предпочтений ЛПР в процессе выбора наилучшего решения. В соответствии с этим принципом методы решения задач многокритериальной оптимизации можно классифицировать в соответствии с характеристикой информации о предпочтениях ЛПР.
Принятие решения в условиях определенности;
Принятие решения в условиях отсутствия информации о системе предпочтения ЛПР;
Принятие решения в условиях постепенного получения информации о системе предпочтения ЛПР.
Классификация многокритериальных методов принятия решений приведена на рис.
Методы решения задач МКО
Имеется Нет никакой Имеется возможность
полная информации последовательного
информация о системе (постепенного)
о системе предпочтений получения частичной
предпочтений ЛПР информации о системе
(функция предпочтений
ценности) ЛПР ЛПР
Построение Лексико- Целевое Выделение Апостери- Последовательное
и графическое программи- всех орное выявление
максимиза- упорядочева рование эффектив- выявление предпочтений
ция ФЦ ние решений ных предпочте- в процессе
ЛПР решений ний на оптимизации
эффективном
множестве
Рис. Классификация методов решения многокритериальных задач.
Рассмотрим первую группу задач, связанных с ситуацией определенности, относительно системы предпочтения ЛПР.
Одним из методов принятия решений в многокритериальной оптимизации для сужения паретовского множества является понятие упорядочения критериев по важности. Вопросы о важности критериев, адресованные ЛПР, оказываются, с одной стороны, достаточно понятными ЛПР, а с другой – его советы могут быть эффективно использованы в алгоритмах оптимизации. Однако, во многих методах требуется, чтобы важность критериев ЛПР выразил точно (сообщил весовые коэффициенты). Примеров качественного упорядочения критериев (без определения весовых коэффициентов) является лексикографическое упорядочение, а многокритериальные задачи со строго ранжированными по важности критериями называются лексикографическими задачами оптимизации. Ясно, что круг многокритериальных задач с лексикографическим упорядочением слишком узок.
Например, лексикографические задачи могут возникать путем введения дополнительных критериев в задачи оптимизации с неединственным решением, такие как организация перевозок грузов (машин, товаров, оборудования и т.д.). При возникновении нескольких оптимальных по критерию минимума общих затрат на перевозку планов, можно ввести новый критерий (минимум времени на перевозку) и в соответствии с ним выбрать наилучший план.
Принцип лексикографического упорядочения может использоваться и в случаях, когда на критериальном пространстве задаются пороговые (минимально допустимые) значения критериев. Тогда указанное упорядочение исходных критериев по важности будет определятся очередностью максимизации этих критериев до соответствующих пороговых значений и многокритериальная задача превращается в лексикографическую задачу с векторным критерием.
Лексикографическая постановка весьма удобно для задач с ограничениями, которые могут оказаться противоречивыми. И если такие ограничения являются “физическими”, т.е. отражают те или иные требования, обуславливаемые сущностью моделируемых процессов и явлений (например, количество расходуемых финансовых средств не должно превышать суммы выделенных денежных ресурсов; доли финансовых средств, выделяемых для различных целей должны быть неотрицательны и в сумме давать единицу и т.д.), то совместность этих ограничений есть условие корректности модели.
Однако, следует отметить, что в общем случае лексикографическая задача оптимизация может оказаться неустойчивой, поскольку незначительные изменения входящих в нее параметров (исходных данных) могут серьезно сказаться на выборе оптимальных альтернатив. Поэтому для их решения применяются специальные методы [ ].
Кроме того, можно предположить, что для многокритериальной задачи важность одного критерия перед другим определяется важностью увеличения на несколько единиц оценок по первому из них перед уменьшением оценок по второму, но на столько же единиц. Отсюда следует, что понятие важности критериев имеет смысл только благодоря процедуре перестановки оценок по различным критериям, но при этом необходимо измерение этих критериев в одних и тех же единицах. Введение такого требования снижает практическую ценность понятия упорядочения критериев
Особенно большой класс принципов принятия решения основан на существовании на множестве векторных оценок отношения предпочтения, зависящего только от системы целевых функций. В этом случае возможно построение соответствующей функции ценности. Кроме этого, знание функции ценности однозначно определяет структуру предпочтения ЛПР. Более подробную информацию о теории функции ценности можно найти в [].
Еще одним алгоритмом принятия решений в условиях определенности являются методы целевого программирования.
Основу целевого программирования, предложенного Чарнсом и Купером, составляет сведение всех критериев в один обобщенный критерий, направленный на минимум, интерпритируемый как некоторое расстояние d от рассматриваемой векторной оценки x до недостижимой, «идеальной» точки x* = (x*1, x*2,, x*m), к которой лицо, принимающее решение, стремиться приблизиться как можно ближе (с точки зрения d). В качестве метрики d могут выступать
Таким образом, задача целевого программирования сводится к решению задачи:
где, U –множество исследуемых на оптимальность стратегий; K – векторный критерий.
Идею целевого программирования для m=2, d=d2, 1=2=1 поясняет рис.
X2 d2(x*, K(u*))
K(u*)
H
K(u) d2(x*, K(u))
X1
Рис.
Следует указать на некоторые особенности, присущие критериальному пространству в целевом программировании. Во-первых, однородные критерии Кi должны иметь общую шкалу отношений (для целевого программирования достаточно шкалы интервалов), а коэффициенты i – измерять важность критериев в единой шкале отношений. Отсюда следует, что исходные неоднородные критерии должны иметь количественные шкалы. При менее совершенных шкалах (в частности, порядковой) строить обобщенный критерий бессмысленно.
Недостатки данного метода связаны с тем, что у ЛПР имеется в распоряжении только вектор x* (не говоря о вопросах, связанных с реализуемостью данного вектора) и параметр d; а также отсутствует инвариантность множества допустимых решений относительно преобразований шкал, применяемых для оценки допустимых решений по критериям Ki.
В случае, когда нет никакой информации о системе предпочтений ЛПР, применяются стандартные процедуры выявления эффективных решений. Затем ЛПР выбирает наилучшую альтернативу, путем явного оценивания.
Для случая постепенного получения частичной информации о системе предпочтений ЛПР имеются две группы многокритериальных методов принятия решений.
К методам апостериорного выявления предпочтений на эффективном множестве относят метод Электра.
Вторую группу составляют т.н. интерактивные или человеко-машинные процедуры решения задач МКО (ЧМП). Наиболее развитая разновидность таких ЧМП - это процедуры решения многокритериальных задач линейного программирования. Эти процедуры предназначены для решения задач следующего типа:
,
где m критериев - взаимонезависимы по предпочтению. При этом последнем условии (как нам уже известно) целевая функция имеет вид:
,
поэтому большинство ЧМП ориентировано на поиск соответствующих коэффицентов k (ЧМП Зайонца-Валлениуса).
В то же время ряд процедур ориентирован (явно) на решение задачи поиска т.н. «удовлетворительного» (а НЕ оптимального) решения, такого, что
,
и речь идёт о поиске соответствующих значений lk (процедура Михайловского).
Общая структура ЧМП приведена на рис. . На основе этой общей структуры дадим классификацию ЧМП. Если в ЧМП отсутствует шаг А, то она - прямая (или неструктуризованная). В противном случае ЧМП - структуризованная (используется также промежуточный термин - псевдоструктуризованная). Для ЧМП, ориентированных на поиск lk, используется термин - ЧМП поиска удовлетворительных решений. Есть также и другие классификационные рубрики.
В настоящее время предпочтение отдается структуризованным и псевдоструктуризованным процедурам, т.к. неструктуризованные не гарантируют получения решения даже тогда, когда оно существует. В целом эффективность таких процедур определяется, прежде всего, квалификацией ЛПР.
Стадия оптимизации (выполняется ЭВМ)
А | Определений значений весовых коэффицентов к и/ или коррекция D |
Б | Нахождение оптимального решение х* и соответствующей векторной оценки. |
В | Формирование дополнительной информации, используемой ЛПР для анализа полученного решения. |
Стадия анализа
(выполняется ЛПР)
Г | Оценивание полученного решение и дополнительной информации. |
Решение да
удовлетворительно Конец
нет
Д | Формирование информации ЛПР, используемой ЭВМ на шаге Г |
Рис.
studfiles.net
3. Многокритериальные задачи оптимизации
Многокритериальная задача линейного программирования состоит в следующем. Пусть область допустимых решений задана системой линейных неравенств:
. (14)
Качество вектора из области допустимых решений оцениваетсяскалярными критериями:
, (15)
вектор, координатами которого являются значения отдельных локальных критериев, называют векторным критерием или векторной целевой функцией.
Необходимо найти оптимальное решение , определяемое двумя условиями:
Решение должно быть осуществимо, т.е. должно принадлежать допустимому множеству .
Решение должно быть наилучшим, т.е. оптимизировать вектор эффективности .
В векторной задаче математического программирования (14), (15) точки оптимума, полученные при решении задачи по каждому критерию отдельно, в общем случае, не совпадают. Поэтому с математической точки зрения векторная задача (14), (15) является некорректной, т.е. если один из критериев достигает своего оптимума, то улучшение по другим координатам векторного критерия невозможно, без ухудшения по данному критерию.
Отсюда вытекает, что решением векторной задачи математического программирования может быть только какое-то компромиссное решение, удовлетворяющее в том или ином смысле всем координатам векторного критерия. На решение этой проблемы и направлены основные методы решения векторных задач математического программирования. Первой попыткой формулировки оптимального решения в данном случае сделано в работах Парето.
Определение (оптимальность по Парето). В векторной задаче математического программирования точка оптимальна по Парето, если она допустима и не существует другой точки, для которой
, (16)
и хотя бы для одного критерия выполнялось строгое неравенство.
Множество таких точек называется множеством точек, оптимальных по Парето. Их также называют множеством неулучшаемых точек, т.е. нельзя найти другой такой точки, чтобы улучшался какой-либо из критериев, а остальные при этом не ухудшались. Множество точек, оптимальных по Парето, лежит между точками оптимума, полученных при решении векторной задачи математического программирования отдельно по каждому критерию.
При многокритериальной оптимизации возникают три основные проблемы
Нормализация векторного критерия. Она вызвана тем, что очень часто локальные критерии, являющиеся координатами вектора эффективности, имеют различные масштабы измерения, что и затрудняет их сравнение. Поэтому приходится приводить критерии к единому масштабу измерения, т.е. нормализовать их.
Выбор принципа оптимальности. В задачах векторной оптимизации принцип оптимальности строго определяет свойства оптимального решения и отвечает на вопрос, в каком смысле оптимальное решение превосходит все остальные допустимые решения. В отличие от задач однокритериальной оптимизации, у которых только один принцип оптимальности , в данном случае имеется большое количество различных принципов, и каждый принцип может приводить к выбору различных оптимальных решений. Принцип оптимальности - это основная проблема векторной оптимизации. Она непосредственно связана с проблемой нормализации критериев.
Учет приоритета критериев. Обычно из физического или экономического смысла понятно, что локальные критерии имеют различную важность при решении задачи, т.е. один локальный критерий имеет приоритет над другим локальным критерием. Поэтому обычно для учета приоритета вводится вектор распределения важности критериев ,,c помощью которого корректируется принцип оптимальности.
С этими проблемами связаны основные трудности многокритериальной оптимизации. Решение задач векторной оптимизации идет в нескольких направлениях:
методы, основанные на свертывании критериев в единый критерий;
методы, построенные на наложении ограничений на критерии;
методы, основанные на отыскании компромиссного решения;
В данной лабораторной работе рассмотрим алгоритм STEM, который состоит из следующих этапов.
Перед решением задачи необходимо произвести нормирование критериев, определив диапазон их изменения от 0 до 1:
, ,
где оптимальные планы задачи при оптимизации только по-му и-му критериям соответственно.
Производится оптимизация по каждому критерию отдельно, при этом значения всех остальных критериев заносятся в табл.1.
Таблица 1
Таблица безразмерных критериев
Критерии/опт. план | … | |||
1 | … | |||
1 | … | |||
… | … | … | … | … |
… | 1 |
В табл.1 нормированное значениего критерия, вычисленного в точке оптимального плана, определенной при оптимизации пому критерию. Ясно, что диагональные элементы равны единице, а все прочие меньше единицы.
После нормирования значение каждого критерия находится в промежутке от нуля до единицы.
По табл.1 вычисляются индексы критериев.
Пусть среднее значение, взятое по всем элементамой строки (кроме единицы). Тогдаиндексго критерия, вычисляется из соотношений:
, , (17)
где в качестве рекомендуется принять.
Если все элементы ой строки в табл.1 близки к единице, то среднее значение тоже близко к единице,мало и соответствующий индекс мал. Действительно, если при оптимизации по другим критериям значение данного критерия близко к наилучшему, то ему вряд ли стоит уделять внимание. Наоборот, критерию, сильно зависящему от изменений других критериев (мало), должны соответствовать большие значения индекса. Индексы называют иногда техническими весами потому, что в отличие от весов они не назначаются ЛПР, а вычисляются.
Производится оптимизация по глобальному критерию. Глобальный критерий имеет вид:
. (18)
Решение, найденное при оптимизации, предъявляется ЛПР.
4. Характеристика информационно-аналитической системы
Постановка задачи содержит величины, значения которых предполагаются известными. Отсутствие информации хотя бы по одной из них делает решение задачи оптимизации производственной программы предприятия невозможным. Задача оперативного планирования чаще всего разбивается на следующие две задачи:
Производственная программа задана. Требуется определить фонд времени, затрачиваемый каждым типом оборудования, т.е. условия обеспеченности процесса выполнения программы производственными мощностями, а также требуемое количество материальных и энергетических ресурсов каждого вида.
Заданы условия обеспеченности процесса выполнения программы производственными мощностями, а также материальные и энергетические ресурсы каждого вида. Требуется определить оптимальный объем производства.
Для решения этих задач на кафедре ММПТ разработана информационно-аналитическая система оперативного планирования производства ОАО "Ижевский подшипниковый завод", содержащая следующие данные: номенклатура выпускаемых изделий; комплектующие детали изделий; технологические процессы обработки деталей и сборки изделий; парк оборудования; основные материалы; нормы затрат времени, энергии и материалов на производство каждой детали.
Стоимостные величины, такие как прибыль, цена, себестоимость используются в рублях на единицу изделия; количество изделия; количество основных материалов в тоннах. Нормы времени, нормы энергии, нормы затрат материалов используются в часах на тысячу штук, киловатт в час на тысячу штук и килограмм на тысячу штук соответственно.
Вся исходная информация размещена в 6 таблицах (рис.2).
Рис.2. Структура информационно-аналитической системы производства
Таблица 1 предназначена для определения номенклатуры изделий, а также содержит информацию о стоимостных характеристиках изделий (себестоимость, цена) и нормативную информацию о времени сборки изделия.
Таблица 2 содержит данные о комплектующих деталях изделия и их количестве в изделии.
Таблица 3 предназначена для определения технологического процесса изготовления детали и содержит нормативную информацию о времени изготовления детали и количестве энергии потребляемой оборудованием.
Таблица 4 содержит данные о сериях и количестве готовых деталей, имеющихся на складе.
Таблица 5 содержит информацию о видах оборудования, их количестве и времени работы в планируемом периоде, а также о количестве потребляемой энергии.
Таблица 6 содержит информацию о материалах, имеющихся в наличии на складе и их количестве.
studfiles.net
Нормализация критериев - Энциклопедия по экономике
Нормализация критериев. Критерии Rk,k e К имеют разный смысл и [c.119]Свойство (3.31) вытекает из условий нормализации критериев (3.9). Кроме того, с учетом нормализации из (3.37) следует [c.135]
Нормализация критериев с целью унификации размерности, диапазона изменения и направления оптимизации критериев эффективности (3.41)-(3.44) по формуле [c.144]Критериями выбора одной из трех альтернатив могут быть количество дополнительной памяти, требующейся в результате нарушений нормализации, возникающих при слиянии отношений частота запросов атрибутов данных отношений (для сокращения времени запроса следует иметь в виду, что чем выше частоты запроса атрибута, тем ближе к корню его следует располагать). При соединении отношений следует учесть, что все взаимосвязи соединяемых отношений перейдут на новое отношение. [c.26]
Вторая трудность связана с нормализацией вектора Y и вызвана различными масштабами и единицами измерения локальных критериев. [c.107]
В случае многокритериальной оптимизации возникают три проблемы. Первая проблема связана с выбором принципа оптимальности. В математическом отношении эта проблема эквивалентна задаче упорядочения векторных множеств, а выбор принципа оптимальности — выбору отношений порядка. Вторая проблема связана с нормализацией векторного критерия F(x). Дело в том, что частные критерии имеют различные единицы измерения, поэтому их необходимо привести к единому масштабу измерения, т. е. нормализовать (обычно приводят к безразличным величинам). Третья проблема связана с учетом приоритета (степени важности) частных критериев. Часто для учета приоритета вводится вектор распределения важности или значимости критериев а = (аг а2,. .., ап). [c.99]
Так как критерии могут иметь различные масштабы и шкалы измерения, то прежде, чем приступить к решению многокритериальной задачи, их необходимо привести к одной единице измерения (обычно к безразмерному виду). Этот процесс называется нормализацией. Существуют различные методы нормализации. Предлагается следующий способ получения безразмерной формы критериев [c.101]
Критерии нормализации. Какое воздействие оказывает нормализация на процессы и работников организации и управления производством [c.158]
В условиях рыночных отношений нормализация трудовых процессов основана на интересах инвестора, товаропроизводителя и общества, выражаемых системой технических, экономических, физиологических и социально-психологических критериев. В решении, например, проблем специализации эти критерии служат своего рода предельными границами разделения труда. [c.158]
Физиологические критерии нормализации трудовых процессов обеспечивают работоспособность трудящихся на протяжении различных рабочих периодов (в течение смены, недели и т.д.). Известно, что в процессе трудовой деятельности под воздействием условных и безусловных рефлексов у человека формируется рабочий динамический стереотип, характер и устойчивость которого зависят от режима труда и отдыха, санитарно-гигиенических и эстетических условий производственной среды и выражают работоспособность человека. Трудовой процесс считается нормализованным, если он сохраняет работоспособность человека в течение установленного рабочего времени, оказывает положительное воздействие на его здоровье, содействует развитию физического и умственного потенциала трудящихся. [c.159]
Прежде всего осуществляется проверка (4.4) соответствия ППР локальным критериям нормализации (см. 5.4) и условиям производства. Если выявляются неразрешимые противоречия, рекомендуется вернуться к седьмому модулю, чтобы изменить в ППР интенсивность или последовательность работ. [c.286]
В соответствии с принципами системного анализа решение проблем совершенствования организационной системы — это определение различия между существующей и желаемой системой с целью нормализации и оптимизации каждой ее подсистемы в соответствии с критерием эффективности. Исходя из этого естественно начинать аналитическую работу с определения [c.369]
Выбор логистического посредника может быть произведен на основе решения многокритериальной задачи. Выбор модели решения многокритериальной задачи зависит от того, насколько равна важность критериев, в соответствии с которыми производится выбор, см. рис. 4.2. Часто критерии выбора противоречат друг другу в большей или меньшей степени. В этом случае необходим поиск компромиссного решения. Решение. многокритериальных задач осложняется также разными единицами измерения оценки результатов альтернатив по разным критериям. Поэтому прежде, чем приступить к решению многокритериальной задачи, критерии необходимо привести к одной единице измерения (обычно к безразмерному виду), т. е. нормализовать. Существуют различные варианты нормализации, например может быть применен следующий способ, по которому безразмерная (относительная) величина критериев определяется по формуле [c.80]
Таким образом, в результате осуществления процедуры "G-нормализации" нами получен вывод об области действия теоремы G2B аналогичный выводу, полученному в результате доказательства теоремы G2B на базе критерия типа X - Y теорема G2B справедлива только для случаев, когда коэффициент, отражающий ожидания по поводу изменения моментальной стоимости бизнеса А и бизнеса Б, больше единицы, т.е. е>1. [c.12]
Нормализация представляет собой один из наиболее изученных способов преобразования отношений, позволяющих улучшить характеристики БД по перечисленным критериям. [c.75]
Очевидно, первый вариант оборудования по двум частным стоимостным критериям будет оптимальным, так как Fmax = fi(fly) = = 5,666. В примере 9.1 четыре локальных критерия не однородны, т.е. имеют различные единицы измерения. В этом случае требуется нормализация критериев. Под нормализацией критериев понимается такая последовательность процедур, с помощью которой все критерии приводятся к единому, безразмерному масштабу измерения. К. настоящему времени разработано большое количество схем нормализации. Рассмотрим некоторые из них. [c.313]
Должность компонуется из управленческих работ с учетом системы технических, экономических, физиологических и социально-психологических критериев нормализации трудовых процессов. Не допускается Бключение в одну должность управленческих работ, реализующих различные функции, не связанных между собой технологических циклов. [c.538]
Нормализация. На третьей стадии развиваются тесные взаимоотношения, и группа демонстрирует сплоченность, Чувства товари щеогва и общей ответственности за проект возрастают, Эта стадия завершена, когда структура группы укреплена, и группа выработала общую систему ожиданий и критериев относительно того, как ее члены должны вместе работать. [c.336]
Алгоритм решения двухкритериальной задачи. В случае К=2 аппроксимирующая зависимость является гиперболой. С учетом нормализации вершина гиперболы принадлежит началу координат, так как асимптотами являются координатные оси. Линия (П) тг-оптимальных сочетаний критериев имеет вид, показанный на рис. 3.1. [c.122]
Какой же вывод об области действия теоремы G2B является справедливым Для ответа на этот вопрос осуществим процедуру "G-нормализации", которая позволяет нейтрализовать эффект "G-гиперболизма". Использование процедуры "G-нормализации" позволяет получить эталонную модель численного сравнения двух величин на базе критерия X/Y [www.galasyuk.dnepr.net]. [c.12]
economy-ru.info
Раздел 2
Задачи непрерывной многокритериальной оптимизации в конечномерных пространствах.
Глава 11. Задачи многокритериальной оптимизации и методы их решения.
Входные термины:
критерий оптимальности;
множество допустимых значений вектора варьируемых параметров.
Выходные термины:
задача многокритериальной оптимизации;
векторный критерий оптимальности;
частный критерий оптимальности;
скалярный критерий оптимальности;
нормализация критериев;
пространство критериев;
пространство варьируемых параметров;
отношение предпочтения ;
отношение эквивалентности;
множество Парето; переговорное множество; область компромисса;
весовые множители (коэффициенты) частных критериев оптимальности.
§1. Постановка задачи многокритериальной оптимизации. Множество Парето
В задачах САПР часто возникает задача обеспечить оптимальность объекта проектирования одновременно по нескольким критериям оптимальности . Обычно эти критерии противоречивы и оптимизация по каждому из них приводит к различным значениям вектора варьируемых параметров Х*. Поэтому выделяется отдельный класс задач многокритериальной оптимизации.
Постановка задачи многокритериальной оптимизации
Будем называть скалярные критерии оптимальности частными критериями оптимальности. Совокупность частных критериев оптимальности Фбудем называть векторным критерием оптимальности. Положим, что ставится задача минимизировать каждый из частных критериев в одной и той же области допустимых значений.
Условно задачу многокритериальной оптимизации будем записывать в виде
Ф(X)=Ф,(1)
где - множество допустимых значений вектора варьируемых параметровX.
Решение задачи многоэкстремальной оптимизации в общем случае не является оптимальным ни для одного из частных критериев, а оказывается некоторым компромиссом для вектора Ф(Х) в целом.
Прежде, чем применить тот или иной метод решения задачи (1), обычно производят нормализацию критериев, приводя все частные критерии оптимальностик одному масштабу. Чаще всего при этом используют относительные отклонения частных критериев от их минимальных значений:
,
где
,
.
Если не оговорено противное, будем полагать далее, что частные критерии нормализованы, и сохраним за нормализованными частными критериями оптимальности обозначения .
Множество Парето
Введем понятие пространства критериев . Пространство критериев имеет размерностьs (по числу частных критериев) и образуется s ортогональными осями координат, вдоль которых откладываются значения частных критериев оптимальности - рисунок 1.
Рисунок 1 - К определению пространства критериев: случай
Векторный критерий оптимальности Φ(X) выполняет отображение множества допустимых значений в некоторую область(область достижимости), где .- пространство варьируемых параметров (рисунок 1).
Введем на множестве DX отношение предпочтения.
Отношение предпочтения . Будем говорить, что вектор предпочтительнее вектора, и писать, если среди равенств и неравенств
,
имеется хотя бы одно строгое неравенство (рисунок 2).
Рисунок 2 - К определению отношения предпочтения (s=2). Для всех точек заштрихованной области , т.е. заштрихованной области пространства критериев соответствуют векторы варьируемых параметров, для которых
Наряду с этим будем говорить, что вектор критериев оптимальности предпочтительнее вектора критериев оптимальности, и писать, если(рисунок 2).
Заметим, что введенное отношение предпочтения является транзитивным, т.е.
если и, то.
Выделим из множества подмножествоточек, для которых в этом множестве нет более предпочтительных точек. Множество, соответствующее, называетсямножеством Парето (переговорным множеством, областью компромисса) – рисунок 3. Таким образом, если , то. Множествоназываетсяфронтом Парето.
Другими словами множество Парето можно определить как множество, в котором значение любого из частных критериев оптимальности можно улучшить (уменьшить) только за счет ухудшения (увеличения) других критериев – любое из решений, принадлежащее множеству Парето, не может быть улучшено одновременно по всем частным критериям. Точки, принадлежащие множеству Парето, не связаны между собой отношением предпочтения!
Рисунок 3 - К определению множества Парето (s=2). Если множество является выпуклым, то множествоесть часть границы множества- дугаAB, в которой точка A соответствует , а точкаB - . Среди точекнет более предпочтительных, поскольку, но
Пример 1. Пусть множество допустимых значений (рисунок 4) и заданы два частных критерия оптимальности,. Можно показать, что множествопри этом имеет вид, представлены на рисунке 5, а множество Паретопредставляет собой отрезок прямой, соединяющий точки (0,0), (1,1) – рисунок 4. Заметим, что точки (0,0), (1,1) являются точками минимума частных критериев оптимальности,, соответственно●
Рисунок 4 - К примеру 1. Множество допустимых значений вектора варьируемых параметров и множество Парето
Рисунок 5 - К примеру 1. Множества ,
Роль множества Парето при решении задач многокритериальной оптимизации определяется следующей теоремой.
Теорема 1. Если для некоторых весовых множителей ,имеет место равенство
(2)
где , то векторХ* оптимален по Парето.
Доказательство. Пусть вектор Х* не оптимален по Парето. Тогда существует такой вектор , что
, (3)
причем хотя бы одно из неравенств строгое. Умножая каждое из неравенств (3) на и складывая, получим
,
что противоречит условию теоремы●
Теорема 1 показывает, что выбор определенной точки из множества Парето эквивалентен указанию весов для каждого из частных критериев оптимальности. На этом факте основано большое количество численных методов решения многокритериальных задач оптимизации.
Заметим, что теорема 1 задает лишь необходимое условие оптимальности по Парето вектора . Т.е. из того факта, что точкапринадлежит множеству Парето, не следует, что эта точка обязательно удовлетворяет условию (2) – случай невыпуклого множества(см. ниже).
В постановке задачи многокритериальной оптимизации (1) фиксируется лишь множество допустимых значений и вектор критериев Ф.Этой информации недостаточно для однозначного решения задачи (1). Указанная информация позволяет лишь выделить соответствующее множество Парето (можно сказать, что решением задачи многокритериальной оптимизации в постановке (1) является множество Парето). Для однозначного решения задачи (1) нужна дополнительная информация. |
Пример 2 (для самостоятельной аудиторной работы). Приближенно построить множество Парето для следующей задачи двухкритериальной оптимизации (s=2):
(рисунок 6).
Покроем множество равномерной сеткой с шагом, равным 1, и пронумеруем узлы сетки так, как показано на рисунке 6.
Рисунок 6 - К примеру 2. Множество допустимых значений покрыто равномерной сеткой с шагом 1 по обеим осям координат. Звездочками выделены узлы сетки, кружками – точки, соответствующие множеству(см. ниже)
Результаты вычислений значений частных критериев оптимальности в узлах построенной сетки занесем в таблицу 1, а затем отобразим в пространстве критериев (рисунок 7).
Аппроксимируем границу множество ломаной и выделим множество(рисунок 7). Отметим точки, соответствующие множеству, на множествеи аппроксимируем полученные точки отрезком прямой. Этот отрезок прямой и представляет собой приближение к искомому множеству Парето (рисунок 6)●
Таблица 1 - К примеру 2.
Значения критериев оптимальности в узлах сетки
x | y |
|
| Номер узла |
0 | 1 | 4 | 41 | 1 |
2 | 5 | 34 | 2 | |
3 | 8 | 29 | 3 | |
4 | 13 | 26 | 4 | |
5 | 20 | 25 | 5 | |
1 | 1 | 1 | 32 | 6 |
2 | 2 | 25 | 7 | |
3 | 5 | 20 | 8 | |
4 | 10 | 17 | 9 | |
5 | 17 | 16 | 10 | |
2 | 1 | 0 | 25 | 11 |
2 | 1 | 18 | 12 | |
3 | 4 | 13 | 13 | |
4 | 9 | 10 | 14 | |
5 | 16 | 9 | 15 | |
3 | 1 | 1 | 20 | 16 |
2 | 2 | 13 | 17 | |
3 | 5 | 8 | 18 | |
4 | 10 | 5 | 19 | |
5 | 17 | 4 | 20 | |
4 | 1 | 4 | 17 | 21 |
2 | 5 | 10 | 22 | |
3 | 8 | 5 | 23 | |
4 | 13 | 2 | 24 | |
5 | 20 | 1 | 25 | |
5 | 1 | 9 | 16 | 26 |
2 | 10 | 9 | 27 | |
3 | 13 | 4 | 28 | |
4 | 18 | 1 | 29 | |
5 | 25 | 0 | 30 |
Рисунок 7 - К примеру 2. Примерный вид множеств
Входные термины:
задача многокритериальной оптимизации;
векторный критерий оптимальности;
частный критерий оптимальности;
скалярный критерий оптимальности;
множество допустимых значений;
весовые коэффициенты частных критериев оптимальности;
множество Парето; переговорное множество; область компромисса;
нормализация пространства критериев.
Выходные термины:
методы, основанные на сведении задачи многокритериальной оптимизации к задаче однокритериальной оптимизации.
метод весовых множителей.
studfiles.net