Метод последовательных уступок.

 

Рассмотрим решение следующей задачи:

1. Предприятие может выпускать три вида продукции: П1, П2, П3, используя три вида ресурсов: материальные (М), трудовые (Т) и финансовые (Ф). Ресурсы ограничены некоторой предельной величиной. Единица продукции каждого вида характеризуется объемом выпуска и качеством изготовления. Объем выпуска будем измерять в руб., качество будем определять трудоемкостью изготовления в н-ч (оценить показатель качества числом в общем случае трудно и не всегда возможно). Исходные данные задачи представлены в таблице 4.1.

 

 

 

Таблица 4.1.Исходные данные к задаче 1.

 

Характеристика	Вид продукции			Располагаемый ресурс
	П1	П2	П3
Продукция:
объем выпуска качество	7 9	12 7	13 10	- -
Ресурсы:
трудовые	0,2	0,3	0,4	35
материальные	0,5	0,4	0,3	42
финансовые	0,6	0,8	1,2	100

 

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

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

Примем сначала в качестве ЦФ объем выпуска, который надо максимизировать. При этом качество будет играть роль ограничения К>=Кзад (требуется, чтобы продукция выпускалась не ниже заданного уровня качества). Матмодель задачи будет выглядеть следующим образом:

 

    (4.1)

 

Данная задача относится к задачам линейного программирования. Результаты ее решения приведены в табл.4.2. В ходе решения заданный уровень качества варьировался от 0 до 970.

Анализ результатов позволяет сделать следующие выводы:

1. Повышение требований к качеству приводит к уменьшению объема выпуска.

2. В зависимости от требований к качеству меняется структура выпуска (в варианте 1 продукция П1 вообще не выпускается).

3. Дальнейший рост выпуска продукции лимитируется ресурсами.

 

Таблица 4.2.Результат оптимизации по критерию Об.

Характеристика	Вариант
	1	2	3
	0	900	970
	830	900	970
	1340	1284	1198
П1	0	14	31,7
П2	90	62	29,5
П3	20	34	47,8
Резерв ресурсов:
трудовых	0	0	0,7
материальных	0	0	0
финанасовых	4	1,2	0

 

Далее решим задачу в другой постановке – максимизируем качество при заданном объеме выпуска. Матмодель будет иметь следующий вид:

 

   (4.2)

 

Результаты решения при различных  приведены в табл.4.3.

 

Таблица 4.2. Результат оптимизации по критерию К.

Характеристика	Вариант
	1	2	3
	0	1180	1260
	1108	1180	1260
	1028	981	930
П1	48,6	35	20
П2	0	23,8	50
П3	59	50	40
Резерв ресурсов:
трудовых	1,7	0,9	0
материальных	0	0	0
финанасовых	0	0	0

 

Из таблицы видно, что с ростом объема выпуска качество продукции снижается.

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

 

 

Рис.4.1. Определение зависимости между критериями оптимальности по результатам метода последовательных уступок.

21.Метод поиска Парето – эффективных решений.

 

 

Рассмотрим его суть на примере использования двух критериев. Критерии при использовании данного метода являются равнозначными.

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

Рис.4.2. Иллюстрация поиска Парето – эффективных решений.

 

На рис.4.2 приняты следующие обозначения:

К₁ и К₂ – критерии оценки вариантов решения;

Y = {y₁, y₂, …, y_m}- множество оценок альтернативных вариантов решения;

К₁₁, К₁₂, …, К_1m - значения первого критерия для 1, 2, …, m - го варианта решения;

К₂₁, К₂₂, …, К_2m – значения второго критерия для 1, 2, …, m - го варианта решения;

P(Y) – множество Парето – эффективных оценок решений.

 

Правило. Множество Парето – эффективных оценок P(Y’) представляет собой «северо – восточную» границу множества Y без тех его частей, которые параллельны одной из координатных осей или лежат в «глубоких» провалах.

Для случая, изображенного на рис.4.2, Парето – эффективные оценки состоят из точек кривой (bc), исключая точку (c), и линии (de).

Преимущества метода: 1) Критерии равнозначны; 2) Метод математически объективен.

Недостаток метода: 1) Одно окончательное решение получается только в частном случае, т.е. количество Парето – эффективных решений, как правило, более одного.

Пример. Имеется 10 вариантов металлорежущих станков, среди которых для проектируемого участка необходимо выбрать наилучший. Станки оценены экспертами по двум показателям (критериям): производительности и надежности. Оценивание производилось по 11 - бальной шкале от 0 до 10. Результаты оценки станков приведены в таблице 4.4.

 

Таблица 4.4. Экспертные оценки станков по критериям производительности и надежности.

 

Представим множество оценок вариантов металлорежущих станков в пространстве критериев (рис.4.3):

Парето – эффективными решениями здесь являются варианты станков С₅, С₇ и С₉.

Рис.4.3. Пример поиска Парето – эффективных решений.

22.Метод решения многокритериальных задач оптимизации с использованием обобщенного (интегрального) критерия.

 

 

Суть данного метода заключается в том, что частные критерии каким - либо образом объединяются в один интегральный критерий (ЦФ):

 

 

Затем находится максимум или минимум данного критерия. Таким образом, ЦФ является определенным компромиссом между всеми критериями.

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

В зависимости от того, каким образом частные критерии объединяются в обобщенный критерий различают следующие виды обобщенных критериев:

1. Аддитивный критерий;

2. Мультипликативный критерий;

3. Максиминный (минимаксный) критерий.

 

23.Аддитивный критерий.

 

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

 

 

где K – количество объединяемых частных критериев;

 – весовой коэффициент k – го частного критерия (показывает «степень компромисса» или важность каждого критерия);

 – числовое значение k – го частного критерия;

 – k– й нормирующий делитель;

– нормированное значение k – го частного критерия.

 

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

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

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

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

Критерии, входящие в формулу делятся на ухудшающие (с их ростом значение ЦФ ухудшается) и улучшающие. Улучшающие критерии входят в формулу со знаком «+», а ухудшающие со знаком «-».

Коэффициенты веса наиболее часто назначаются при условии:

 

 

с помощью различных методов экспертных оценок.

 

Пример. Решим рассмотренную ранее задачу, используя построение интегрального аддитивного критерия.

Объединенная ЦФ запишется следующим образом:

 

 

В качестве нормирующих значений  и Кн примем их максимальные значения, полученные в результате оптимизационного расчета по каждому параметру отдельно: =1340, Кн=1028. Математическая модель будет выглядеть следующим образом:

 

Результаты решения при различных значениях коэффициентов веса приведены в табл.4.5.

 

Таблица 4.5.Результат оптимизации при использовании интегрального аддитивного критерия.

Характеристика	Вариант
	1	2	3
	1	0,5	0
	0	0,5	1
	100	94,4	100
	1340	1260	1108
	830	930	1028
П1	0	20	49
П2	90	50	0
П3	20	40	59
Резерв ресурсов:
трудовых	0	0	1,7
материальных	0	0	0
финанасовых	4	0	0

 

Анализируя результаты можно сделать выводы:

1. С точки зрения объема выпуска наиболее выгодной является продукция П2. По мере снижения коэффициента веса  (падению значимости критерия «объем») ее выпуск уменьшается. Самой невыгодной оказывается продукция П1, которая при =1 вообще не производится.

2. Наиболее выгодной с позиции качества является продукция П1. наиболее невыгодной – продукция П2, которая при =1 не выпускается.

3. Для обеспечения дальнейшего роста объема выпуска продукции необходимо увеличить трудовые и материальные ресурсы, а для повышения качества продукции – материальные и финансовые.

Преимущество данного метода: как правило, всегда удается определить единственный оптимальный вариант решения.

 

Недостатки:

 

1. Трудности (субъективизм) в определении весовых коэффициентов.

2. Аддитивный критерий не вытекает из объектной роли частных критериев и поэтому выступает как формальный математический прием.

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

 

 

24. Мультипликативный критерий.

 

 

Целевая функция здесь записывается следующим образом:

где П – знак произведения;

- весовой коэффициент i -го частного критерия;

- числовое значение i -го частного критерия.

Преимущества мультипликативного критерия:

1. Не требуется нормирование частных критериев.

2. Практически всегда определяется одно оптимальное решение.

Недостатки:

1. Трудности (субъективизм) в определении весовых коэффициентов.

2. Перемножение разных размерностей.

3. Взаимная компенсация значений частных критериев.

 

25.Максиминный (минимаксный) критерий

 

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

где - весовой коэффициент i -го частного критерия;

– нормированное значение i -го частного критерия;

K – константа.

При большом количестве частных критериев из-за сложных взаимосвязей добиться выполнения указанного выше соотношения очень сложно. Поэтому на практике так варьируют значениями переменных проектирования x ₁, x ₂, …, x _m, при которых последовательно «подтягиваются» те нормированные критерии, численные значения которых в исходном решении оказались наименьшими. Т.к. эта операция производится в области компромисса, подтягивание «отстающего» критерия неизбежно приводит к снижению значений части остальных критериев. Но при проведении ряда шагов можно добиться определенной степени уравновешивания противоречивых частных критериев, что и является целью принципа максимина.

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

Такой принцип выбора иногда носит название гарантированного результата. Он заимствован из теории игр, где является основным принципом.

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

.

 

 

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

 

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

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

При наличии нескольких критериев выбирают:

а) аддитивный критерий, если существенное значение имеют абсолютные значения критериев при выбранном векторе параметров X;

б) мультипликативный критерий, если существенную роль играет изменение абсолютных значений частных критериев при вариации вектора X;

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