2.1 Постановка
задачи
Предприятие планирует освоить
выпуск нового изделия в количестве не
менее 15 000 штук в год. Для этого ему необходимо
приобрести станки двух типов. Характеристики
станков, из которых делается выбор, приведены
в таблицах 2.1 и 2.2. При этом, на изготовление
изделия, предприятие может выделить не
более 150 часов в месяц. Существует также
ограничение по стоимости (не более 2000
млн.руб.) и по потребляемой мощности (не
более 100000 кВт-ч в месяц).
Таблица 2.1 – Технические характеристики
станков первого вида
Станок |
ST11 |
ST12 |
ST13 |
ST14 |
ST15 |
Производительность, изд./час |
8 |
5 |
19 |
13 |
11 |
Стоимость, млн. руб. |
930,0 |
310,0 |
1320,0 |
450 |
957,0 |
Энергоэффективность,кВт-ч/изд. |
15,3 |
30,5 |
27,0 |
25,0 |
13,6 |
Таблица 2.2 – Технические характеристики
станков второго вида
Станок |
ST21 |
ST22 |
ST23 |
ST24 |
ST25 |
Производительность, изд./час |
16 |
17 |
12 |
15 |
10 |
Стоимость, млн. руб. |
1400,0 |
1200,0 |
1100,0 |
700,0 |
550,0 |
Энергоэффективность,кВт-ч/ изд. |
22,0 |
14,0 |
33,0 |
20,0 |
21,3 |
Кроме того, при выборе станков необходимо
учесть мнение экспертов в отношении этого
оборудования (таблицы 2.3 и 2.4)
Таблица 2.3 – Эксплуатационные характеристики
станков первого вида
Станок |
ST11 |
ST12 |
ST13 |
ST14 |
ST15 |
Сервисное обслуживание |
да |
нет |
да |
да |
нет |
Надежность (наработка на отказ),ч |
100 000 |
170 000 |
50 000 |
90 000 |
110 000 |
Удобство в использовании |
отлично |
плохо |
плохо |
очень хорошо |
хорошо |
Таблица 2.4 – Эксплуатационные характеристики
станков первого вида
Станок |
ST21 |
ST22 |
ST23 |
ST24 |
ST25 |
Сервисное обслуживание |
да |
да |
да |
нет |
да |
Надежность (наработка на отказ),ч |
130 000 |
140 000 |
120 000 |
100 000 |
130 000 |
Удобство в использовании |
очень хорошо |
хорошо |
плохо |
плохо |
отлично |
Таблица 2.5 – Вариант задания
вариант |
Однокритериальная оптимизация |
Многокритериальная оптимизация |
метод |
параметр |
Метод экспертного анализа |
Число экспертов |
Метод отбора |
Выбор лучшего решения |
5 |
перебор |
энергоэф. |
Предпочтений |
2 |
Парето |
МАИ |
В соответствии с вариантом
задания на курсовой проект
(таблица 2.5) необходимо:
1) разработать программное
средство оптимизации по заданному критерию
в рамках существующих ограничений методом
полного перебора (критерий выбирает пользователь);
2) разработать программное
средство многокритериальной оптимизации
с учетом мнения одного или двух экспертов.
Для этого необходимо:
– реализовать перевод качественных
оценок в числовую форму по шкале Харрингтона;
– определить лучшую альтернативу
методом экспертного анализа (Метод предпочтений);
– реализовать отбор бесперспективных
альтернатив (Множество Парето);
– определить лучшую альтернативу
методом анализа иерархий.
2.2 Описание алгоритма
решения задачи
Согласно варианту поставленная
задача должна решаться методом полного
перебора для одномерной оптимизации.
Рассмотрим основную суть данного алгоритма.
Метод перебора или равномерного
поиска является простейшим из прямых
методов минимизации. В сущности, перебор - это решение задач, возникающих
из заданной, когда значение некоторого
искомого параметра фиксируется различным
образом, и производится выбор того из
рассмотренных значений, которое дает
наиболее подходящее решение.
Основная задача при реализации
переборных методов заключается в нахождении
такого порядка элементов перебора, при
котором искомый элемент встретится как
можно раньше [8].
Необходимо учесть, что сложность
полного перебора зависит от количества
всех возможных решений задачи. Если пространство
решений очень велико, то полный перебор
может не дать результатов в течение нескольких
лет или даже столетий.
Для получения оптимального
решения поставленной задачи при многомерной
оптимизации необходимо реализовать ряд
этапов. Рассмотрим их.
1. Для начала необходимо перевести
все качественные оценки в числовую форму
по шкале Харрингтона. Диапазон значений
по данной шкале приведён в таблице 2.6
Таблица 2.6 - Шкала Харрингтона
Качественные оценки |
Очень плохо |
Плохо |
Удовлетворительно |
Хорошо |
Отлично |
Количественные оценки |
0.0 – 0.2 |
0.2 – 0.36 |
0.36 – 0.63 |
0.63 – 0.8 |
0.8 – 1.0 |
Оценки типа «да/нет» так же
переводятся в числовую форму, причём
оценке «да» соответствует значение –
0.67, а «нет» – 0.33.
Все числовые оценки переводятся
в безразмерный вид (представить оценки
в долях единицы) и при этом лучшей оценке
соответствует большее значение. Для осуществления
такого перевода необходимо разделить
все значения оценок по данному критерию
на максимальное значение этого критерия.
2. Необходимо реализовать метод
экспертного анализа – метод предпочтений.
Данный метод основан на ранжировании
альтернатив, выполняемом группой экспертов.
Каждый из экспертов (независимо от других)
выполняет ранжирование альтернатив,
т.е. указывает, какая из альтернатив, по
его мнению, является лучшей, какая
следующей за ней, и т.д.
Пусть имеется m экспертов: Э1, Э2, ..., Эm и n критериев (альтернатив): Z1, Z2, ..., Zn [9].
Каждый эксперт проводит оценку
критериев, пользуясь числами натурального
ряда. Наиболее важной цели присваивается
значение 1, менее важной - 2 и т.д. В этих условиях веса
критериев определяются следующим образом:
- составляется исходная матрица k предпочтений размером m×n, причём 1≤ kij ≤ n, где
;
- составляется модифицированная
матрица K предпочтений. С оценками:
;
(2.1)
- находятся суммарные оценки
предпочтений по каждому критерию:
;
(2.2)
- вычисляются исходные веса критериев:
(2.3)
Наиболее предпочтительной
является альтернатива, имеющая максимальный
вес.
Для данного метода существует
возможность проверки согласованности
экспертных оценок. Для этого вычисляется
коэффициент конкордации по следующему
алгоритму. Сначала находятся суммы оценок,
указанных экспертами для каждой из альтернатив:
, где
. Затем находится вспомогательная
величина α:
(2.4)
Находится
. Находится коэффициент конкордации:
(2.5)
При υ ≥ 5, степень
согласованности экспертных оценок считается
достаточной, в противном случае требуется
уточнение и согласование экспертных
оценок.
3. Реализуется метод
Парето для отбора бесперспективных альтернатив.
Суть данного метода заключается
в следующем: одна альтернатива превосходит
вторую, если она превосходит ее, по крайней
мере, по одной компоненте и не хуже второй
по любой другой компоненте. Если альтернатива
удовлетворяет этому свойству относительно
всех других альтернатив, то ее называют
парето-оптимальной [10].
Применение принципа Эджворта
– Парето позволяет из множества всех
возможных исключить заведомо неприемлемые
решения, т.е. те, которые никогда не могут
оказаться выбранными, если выбор осуществляется
достаточно «разумно». После такого исключения
остается множество, которое называют
множеством Парето или областью компромиссов.
Выбор множества Парето производится
следующим образом. Все альтернативы попарно
сравниваются друг с другом по всем критериям.
Если при сравнении каких-либо альтернатив
оказывается, что одна из них не лучше
другой ни по одному критерию, то ее можно
исключить из рассмотрения.
Данный метод позволяет сократить
количество альтернатив, но не позволяет
получить окончательное решение.
4. Определяем лучшую альтернативу
методом анализа иерархий (МАИ). Рассмотрим
более подробно данный метод.
Метод анализа иерархий, разработанный
под руководством американского специалиста
по исследованию операций Т. Саати, применяется
в настоящее время при решении самых разнообразных
проблем, среди которых, в частности: проектирование
транспортных систем крупных городов,
разработка планов обеспечения энергетическими
ресурсами отраслей промышленности, оценка
сценария развития высшего образования,
определение приоритетных направлений
научных исследований и др.