- •Введение
- •Раздел I. Математические методы в исследовании операций.
- •1. Основные понятия.
- •2. Классификация моделей.
- •3. Выбор решения в условиях неопределенности.
- •4. Многокритериальные задачи.
- •Раздел II. Линейное программирование.
- •1. Математические модели задач линейного программирования.
- •Задача о пищевом рационе.
- •Задача производственного планирования.
- •Задачи раскроя.
- •2.Основная задача линейного программирования (озлп)
- •Найти неотрицательные значения переменных x1 , x2 , …, xn , которые удовлетворяли бы условиям-равенствам
- •3. Геометрическая интерпретация озлп.
- •4. Симплекс-метод.
- •4. Двойственные задачи линейного программирования.
- •5. Транспортная задача.
- •Раздел III. Графовые модели.
- •1.Элементы теории графов.
- •2. Задача о кратчайшем пути.
- •3. Кратчайший путь в ориентированном графе.
- •4. Построение графа наименьшей длины.
- •5. Транспортная задача в сетевой постановке.
- •6. Метод ветвей и границ.
- •7. Максимальный поток на сети.
- •Раздел IV. Динамическое программирование.
- •Раздел V. Имитационное моделирование
- •Теория игр.
- •Антагонистические матричные игры.
- •Задачи, приводимые к матричным играм.
- •Преобразование матричных игр.
- •Методы решения матричных игр.
- •Игры с природой.
- •Раздел VI. Теория массового обслуживания.
- •Задачи теории массового обслуживания.
- •Формула Литтла.
- •Простейшие системы массового обслуживания.
- •Решение задач
4. Многокритериальные задачи.
В крупномасштабных операциях эффективность не может быть охарактеризована с помощью одного единственного показателя. Такие задачи, в которых существует множественность показателей эффективности, из которых одни желательно обратить в максимум, другие – в минимум, называются многокритериальными.
ПРИМЕР 1.8. Реорганизуется предприятие. Один показатель эффективности – валовый доход (максимизировать), другой – производительность труда (максимизировать), третий – себестоимость (минимизировать).
Методы решения.
Сведение к однокритериальной задаче.
а) Строится функция следующим образом: в числитель вносятся все показатели, увеличение которых желательно, а в знаменатель – те, увеличение которых нежелательно. Такой способ не рекомендуется, т.к. здесь недостаток в одном показателе может быть скомпенсирован за счет другого.
б) Составление обобщенного показателя эффективности в виде взвешенной суммы частных показателей, в которую каждый из них входит с каким-то весом, отражающим его важность. W=a1W1+ a2W2+…+ anWn. Коэффициенты выбираются положительными, если показатель требуется максимизировать и отрицательные, если минимизировать. Значения коэффициентов выбираются, взвесив все «за» и «против». Недостаток метода: весовые коэффициенты меняются в зависимости от обстоятельств и трудно оценить вес несовместимых критериев. Выбор коэффициентов субъективен, а следовательно и оптимальное решение получится субъективным.
ПРИМЕР 1.9. Студент опаздывает на занятия. Перед ним задача с двумя критериями: среднее время опоздания Т (минимизировать), стоимость проезда S (минимизировать).
W=a1T+a2S → min
Если студент только что получил стипендию, то уменьшаем коэффициент при S; если опоздание абсолютно невозможно, увеличиваем коэффициент при Т.
Построение множество Парето
Метод заключается в выбраковке из множества возможных решений заведомо неудачных. Пусть имеется задача с k критериями, которые надо максимизировать (от минимума всегда можно перейти к максимуму). Пусть в составе множества возможных решений есть два решения такие, что все критерии для первого решения больше или равны соответствующим критериям для второго решения. Говорят, что первое решение доминирует над вторым. Второе решение выбрасывается, как неконкурентоспособное. В результате такой процедуры среди множества решений остаются только эффективные. Окончательный выбор делает человек.
Для двухкритериальной задачи отбраковку удобно делать графически.
ПРИМЕР 1.10. Рассмотрим задачу об опоздании студента. Имеется несколько вариантов. Необходимо найти оптимальный вариант по двум критериям: минимум времени ожидания и минимум стоимости проезда.
|
Вид транспорта |
Ср.время ожидания |
Ср. время в пути |
Стоимость проезда |
Решение |
|
Автобус |
15 мин |
25 мин |
3 руб. |
– |
|
Троллейбус |
10 мин |
30 мин |
3 руб. |
– |
|
Трамвай |
5 мин |
30 мин |
3 руб. |
- |
|
Такси |
5 мин |
10 мин |
20 руб. |
– |
|
Маршр.такси 1 |
10 мин |
15 мин |
7 руб. |
– |
|
Маршр.такси 2 |
10 мин. |
20 мин |
5 руб. |
- |
|
Личная машина |
0 мин |
15 мин |
10 руб. |
+ |
|
М ашина друга |
10 мин |
15 мин |
0 руб. |
+ |
|
Пешком |
0 мин |
60 мин |
0 руб. |
– |
S
2 0
7
5
3
T
0 5 10 15 20 25 30 35 40 45 60
Варианты с такси и с маршрутным такси отбраковываются, т.к. при том же времени есть варианты менее дорогостоящие. Варианты с автобусом, троллейбусом и пешком также отбраковываются, т.к. при одинаковых затратах есть варианты с меньшим временем. Для варианта с трамваем и маршрутным такси 2 есть вариант с машиной друга, который лучше сразу по 2 критериям. Паретовское множество будет содержать варианты, помеченные +.
ПРИМЕР 1.11. Выделить множество Парето.
Необходимо составить рацион питания оптимальный по двум критериям: минимум стоимости и максимум калорийности. Имеется несколько вариантов.
№ |
Наименование |
Стоимость S |
Калорийность K |
Решение |
|
Молоко |
10 руб. |
20 |
+ |
|
Хлеб |
8 руб. |
7 |
|
|
Мясо |
50 руб. |
15 |
|
|
Творог |
25 руб. |
10 |
|
|
Картофель |
5 руб. |
5 |
+ |
|
Рожки |
12 руб. |
5 |
|
|
Шоколад |
100 руб. |
30 |
+ |
|
Гречка |
10 руб. |
10 |
|
|
Яблоки |
25 руб. |
25 |
+ |
РЕШЕНИЕ.
K
3 0
2 0_
1 0
7
5
S
0 5 10 15 20 25 30 35 40 45 50 100
Задание 1.3. Придумать двухкритериальную задачу, подобрать данные и построить множество Парето.
Метод ограничений.
Выделяется один главный показатель, а на остальные накладываются ограничения.
ПРИМЕР 1.12. При оптимизации плана работы предприятия главным можно считать прибыль предприятия. При этом план должен быть выполнен, а себестоимость продукции не превышать заданную.
Метод последовательных уступок.
Показатели эффективности располагаются в порядке убывающей важности. Сначала ищется решение, обращающее в максимум первый показатель. Затем на первый показатель накладывается ограничение, чтобы он незначительно отклонялся от найденного максимума, и ищем решение, обращающее в максимум второй показатель. И т.д. В методе сразу видно, ценой какой уступки в одном показателе приобретается выигрыш в другом.