Многокритериальные задачи

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

ПРИМЕР 1.8. Реорганизуется предприятие. Один показатель эффективности – валовый доход (максимизировать), другой – производительность труда (максимизировать), третий – себестоимость (минимизировать).

Методы решения.

1. Сведение к однокритериальной задаче.

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

б) Составление обобщенного показателя эффективности в виде взвешенной суммы частных показателей, в которую каждый из них входит с каким-то весом, отражающим его важность. W=a₁W₁+ a₂W₂+…+ a_nW_n. Коэффициенты выбираются положительными, если показатель требуется максимизировать и отрицательные, если минимизировать. Значения коэффициентов выбираются, взвесив все «за» и «против». Недостаток метода: весовые коэффициенты меняются в зависимости от обстоятельств и трудно оценить вес несовместимых критериев. Выбор коэффициентов субъективен, а следовательно и оптимальное решение получится субъективным.

ПРИМЕР 1.9. Студент опаздывает на занятия. Перед ним задача с двумя критериями: среднее время опоздания Т (минимизировать), стоимость проезда S (минимизировать).

W=a₁T+a₂S → min

Если студент только что получил стипендию, то уменьшаем коэффициент при S; если опоздание абсолютно невозможно, увеличиваем коэффициент при Т.

2. Построение множество Парето

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

Для двухкритериальной задачи отбраковку удобно делать графически.

ПРИМЕР 1.10. Рассмотрим задачу об опоздании студента. Имеется несколько вариантов. Необходимо найти оптимальный вариант по двум критериям: минимум времени ожидания и минимум стоимости проезда.

	Вид транспорта	Ср.время ожидания	Ср. время в пути	Стоимость проезда	Решение
1.	Автобус	15 мин	25 мин	3 руб.	–
2.	Троллейбус	10 мин	30 мин	3 руб.	–
3.	Трамвай	5 мин	30 мин	3 руб.	-
4.	Такси	5 мин	10 мин	20 руб.	–
5.	Маршр.такси 1	10 мин	15 мин	7 руб.	–
6.	Маршр.такси 2	10 мин.	20 мин	5 руб.	-
7.	Личная машина	0 мин	15 мин	10 руб.	+
8.	Машина друга	10 мин	15 мин	0 руб.	+
9.	Пешком	0 мин	60 мин	0 руб.	–

S

20

7

5

3

T

0 5 10 15 20 25 30 35 40 45 60

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

ПРИМЕР 1.11. Выделить множество Парето.

Необходимо составить рацион питания оптимальный по двум критериям: минимум стоимости и максимум калорийности. Имеется несколько вариантов.

№	Наименование	Стоимость S	Калорийность K	Решение
1.	Молоко	10 руб.		+
2.	Хлеб	8 руб.
3.	Мясо	50 руб.
4.	Творог	25 руб.
5.	Картофель	5 руб.		+
6.	Рожки	12 руб.
7.	Шоколад	100 руб.		+
8.	Гречка	10 руб.
9.	Яблоки	25 руб.		+

РЕШЕНИЕ.

K

30

20_

10

7

5

S

0 5 10 15 20 25 30 35 40 45 50 100

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

3. Метод ограничений.

Выделяется один главный показатель, а на остальные накладываются ограничения.

ПРИМЕР 1.12. При оптимизации плана работы предприятия главным можно считать прибыль предприятия. При этом план должен быть выполнен, а себестоимость продукции не превышать заданную.

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

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

Раздел II. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.

Дата добавления: 2014-01-20