- •1.1. Методы искусственного интеллекта в прикладных системах и системах принятии решений
- •1.2. Интеллектуальные информационные технологии в прикладных системах и системах принятия решений
- •1.3. Типология задач интеллектуализации систем
- •Лекция 2. Представление знаний в интеллектуальных системах
- •2.1. Модели представления знаний
- •2.2. Системы, основанные на правилах
- •2.3. Системы, основанные на автоматическом доказательстве теорем
- •2.4. Системы, основанные на автоматическом порождении (выдвижении) гипотез
- •Лекция 3. Структура и основные компоненты прикладных интеллектуальных систем
- •3.1. Прикладные системы, основанные на знаниях
- •3.2. Структура системы управления, основанной на знаниях
- •3.3. Структура интеллектуальных систем поддержки принятия решения
- •3.4. Обобщенная структура экспертной системы
- •Лекция 4. Классификация прикладных интеллектуальных систем
- •4.1. Классификация экспертных систем
- •4.2. Примеры прикладных интеллектуальных систем
- •Лекция 5. Основные понятия и определения теории принятия решений
- •5.1. Роли людей в процессе принятия решений
- •5.2. Альтернативы
- •5.3. Критерии
- •5.4. Основные этапы процесса принятия решений
- •5.5. Математические методы теории принятия решений
- •Лекция 6. Принятие решений с помощью статистической проверки гипотез
- •6.1. Статистические решения
- •6.2. Основные задачи статистических решений
- •6.3. Статистическая проверка гипотез
- •6.4. Ошибки решения
- •6.5. Решающее правило при проверке гипотез
- •Лекция 7. Байесовская и последовательная процедуры принятия решения.
- •7.1. Байесовские процедуры принятия решения
- •7.1.1. Байесовская процедура при проверке простой гипотезы
- •7.1.2. Байесовские процедуры в задаче классификации
- •7.2. Принятие решения с помощью последовательной процедуры Вальда
- •Лекция 8. Принятие решения методом дискриминантнного анализа
- •8.1. Классификация в случае, когда распределения классов определены полностью
- •8.1.1. Модель двух нормальных распределений с общей ковариационной матрицей (модель Фишера)
- •8.1.2. Модель двух нормальных распределений с разными ковариационными матрицами
- •8.1.3. Модель нескольких нормальных распределений с общей ковариационной матрицей
- •8.2. Классификация при наличии обучающих выборок
- •8.2.1. Подстановочный алгоритм в модели Фишера
- •8.2.3. Правила классификации
- •8.3. Ошибка решающего правила
- •Лекция 9. Древообразные классификаторы
- •9.1. Назначение древообразных классификаторов
- •9.1. Структура дерева классификации
- •9.3. Вычислительные задачи древообразных классификаторов
- •9.3.1. Определение качества предсказания
- •9.3.2. Выбор разбиений
- •9.3.3. Определение правила прекращения разбиения
- •Лекция 10. Деревья решений
- •9.1. Характеристики дерева решений
- •9.2. Построение дерева решений
- •Лекция 11. Методы прогнозирования
- •11.1. Анализ временных рядов
- •11.1.1. Модель временного ряда
- •11.1.2. Тренд, сезонная и циклическая компоненты
- •11.1.3. Декомпозиция временного ряда
- •11.1.4. Экспоненциальное сглаживание
- •11.2. Каузальные методы прогнозирования
- •11.3. Качественные методы прогнозирования
- •Лекция 12. Основная задача линейного программирования
- •12.1. Математическая модель основной задачи линейного программирования
- •12.2. Задача линейного программирования с ограничениями-неравенствами
- •12.3. Примеры задач линейного программирования
- •12.3.1. Транспортная задача
- •12.3.2. Задача о назначениях
- •Лекция 13. Симплекс-метода решения задачи линейного программирования
- •13.1. Характеристика симплекс–метода
- •13.2. Табличный алгоритм замены базисных переменных
- •13.3. Отыскание опорного решения основной задачи линейного программирования
- •13.4. Отыскание оптимального решения основной задачи линейного программирования
- •Лекция 14. Многокритериальные методы принятия решений при объективных моделях
- •14.1. Объединение критериев
- •14.2. Метод главного критерия
- •14.3. Метод последовательных уступок
- •14.4. Метод целевого программирования
- •14.5. Метод, использующий принцип гарантированного результата
- •14.6. Метод равных наименьших относительных отклонений
- •14.7. Процедура STEM поиска удовлетворительных значений критериев
- •Лекция 15. Выбор Парето–оптимальных решений
- •15.1. Основные определения
- •15.2. Графическая интерпретация
- •15.3. Постановка задачи
- •Лекция 16. Оценка многокритериальных альтернатив с помощью теории полезности
- •16.1. Теория полезности
- •16.2. Принятие решения на основе значения ожидаемой полезности
- •16.3. Многокритериальная теория полезности (MAUT)
- •Лекция 17. Сравнение альтернатив методом аналитической иерархии
- •17.1. Основные этапы метода аналитической иерархии
- •17.2. Декомпозиция задачи
- •17.3. Попарное сравнение критериев и альтернатив
- •17.4. Свойства идеальной матрицы сравнений
- •Лекция 18. Приоритеты для критериев и альтернатив и выбор наилучшей альтернативы в методе анализа иерархий
- •18.1. Вычисление собственных характеристик обратно симметричной матрицы
- •18.2. Вычисление величины приоритетов
- •18.3. Определение наилучшей альтернативы
- •18.4. Проверка согласованности
- •18.5. Пример применения метода анализа иерархий
- •Лекция 19. Оценка многокритериальных альтернатив методами ELECTRE
- •19.1. Этапы подхода, направленного на разработку индексов попарного сравнения альтернатив
- •19.2. Свойства бинарных отношений
- •19.3. Метод ELECTRE I
- •19.4. Метод ELECTRE II
- •19.5. Метод ELECTRE III
- •Лекция 20. Основные понятия и математическая модель игровых методов обоснования решений
- •20.1. Основные понятия теории игр
- •20.2. Математическая модель игры
- •20.3. Нижняя и верхняя цена игры. Принцип минимакса
- •Лекция 21. Методы решения игр
- •21.1. Решение игры в чистых стратегиях
- •21.2. Решение игры в смешанных стратегиях
- •21.3. Упрощение игр
- •21.4. Решение игры 2х2
- •21.5. Графический метод решения (2х2)-игр
- •Лекция 22. Игры 2 х п
- •Лекция 23. Решение игр т х 2 и т х п
- •23.1. Решение игр т х 2
- •23.2. Решение игр т х п
- •Лекция 24. Критерии принятия решений в условиях риска и неопределенности
- •24.1. Основные понятия. Математическая модель
- •24.3. Максиминный критерий Вальда
- •24.4. Критерий минимаксного риска Сэвиджа
- •24.5. Критерий пессимизма-оптимизма Гурвица
- •Литература
12.3.2. Задача о назначениях
Одной из проблем, укладывающейся в схему транспортной задачи, является так называемая задача о назначениях или задача выбора [5]. Задача заключается в наиболее экономном распределении п работ между п исполнителями, если известны времена (или средства), затрачиваемые каждым исполнителем на каждой работе.
Пусть, например, задано, что j-й исполнитель затрачивает на i-ю работу tij рабочих
часов. Будем считать наиболее экономичным такое распределение работ между исполнителями, при котором достигается минимум суммарного числа рабочих часов на выполнение всех работ.
Обозначим через xij число равное единице, если j-й исполнитель назначен на i-ю
работу, и нулю, если для i-й работы выбран другой исполнитель. Суммарное время, затраченное на выполнение всех работ, вычисляется по формуле
n n |
|
∑∑tij xij . |
(12.10) |
i=1 j=1 |
|
Условия, гарантирующие прикрепление исполнителя к каждой работе, записываются в
виде
n
∑xij = 1, i = 1, 2,…, п. (12.11)
j =1
Условия, гарантирующие закрепление за каждым исполнителем какой-то работы, имеют вид
n |
|
|
∑x = 1, j = 1, 2,…, п. |
(12.12) |
|
i=1 |
ij |
|
|
|
|
xij ≥ 0, i = 1, 2,…, п, j = 1, 2,…, п. |
(12.13) |
Задача состоит в минимизации линейной формы (12.10) при условиях (12.11) – (12.13). Оптимальный план задачи выбора представляет собой матрицу Х = ( xij ), у которой в каждой
строке и в каждом столбце стоит только один ненулевой элемент, равный единице.
Задача о назначениях является частной моделью транспортной задачи. В ней т = п, а
все ai = bi = 1.
Лекция 13. Симплекс-метода решения задачи линейного программирования
Для нахождения решения задачи линейного программирования в общем случае (при произвольном числе свободных переменных) применяются специальные вычислительные методы. Из них наиболее универсальным является симплекс–метод.
13.1. Характеристика симплекс–метода
Суть симплекс–метода заключается в следующем [5]. Пусть в задаче линейного программирования имеется п переменных и т независимых линейных ограничений, заданных в форме уравнений. Оптимальное решение, если оно существует, достигается в одной из опорных точек (вершин ОДР), где по крайней мере k = п – т из переменных равны нулю. Выберем какие-то k переменных в качестве свободных и выразим через них остальные т базисных переменных. Пусть в качестве свободных выбраны первые k = п – т переменных x1, x2,…, xk, а остальные т выражены через них:
67
xk +1 |
= αk +1,1x1 |
+αk +1,2x2 |
+...+αk +1,k xk |
+βk +1, |
|
|
|
||||||||
x |
= α |
x |
+α |
k +2,2 |
x |
2 |
+...+α |
k +2,k |
x |
k |
+β |
k + |
2 |
, |
|
k +2 |
|
k +2,1 1 |
|
|
|
|
|
(13.1) |
|||||||
............................................................................... |
|
||||||||||||||
xn = αn,1x1 +αn,2x2 +...+αn,k xk +βn. |
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
Если положить все свободные переменные равными нулю xi = 0, i = 1,…k, то получим: xk +1 = βk +1, xk +2 = βk +2 , …, xn = βп.
Полученное решение допустимо, если все свободные члены βk +1, βk +2 , βп
неотрицательны. Если это условие выполнено, то |
мы получили опорное решение. Чтобы |
проверить, является ли оно оптимальным, выразим минимизируемую линейную функцию L |
|
через свободные переменные x1, x2,…, xk: |
|
L = γ0 + γ1x1 + γ2x2+…+ γkxk. |
(13.2) |
При x1 = x2 =…= xk = 0 L = γ0. Можно ли улучшить решение? Если все коэффициенты γ0 , γ1, γ2,…, γk в формуле (13.2) положительны, то мы не можем уменьшить L; следовательно, найденное опорное решение является оптимальным. Если же среди коэффициентов в γ0 , γ1, γ2,…, γk в формуле (13.2) есть отрицательные, то увеличивая некоторые из переменных x1, x2,…, xk (те, коэффициенты при которых отрицательны), мы можем улучшить решение, уменьшив L.
Увеличивать свободные переменные нужно так, чтобы не стали отрицательными другие переменные xk +1 , xk +2 ,…, xn, выраженные через свободные переменные.
Пусть коэффициент γ1 в формуле (13.2) отрицателен. Тогда увеличение x1 делает функцию L меньше. Выберем ту из переменных xk +1 , xk +2 ,…, xn, которая раньше всех
обратится в нуль при увеличении x1. Это переменная xr, для которой величина – βl/αl1
меньше всего. Тогда целесообразно «переразрешить» систему уравнений (13.1) относительно других базисных переменных, выведя из числа свободных переменных x1 и переведя вместо нее в группу свободных переменных xr. Теперь можно перейти от опорного решения, задаваемого как x1 = x2 =…= xk = 0, к опорному решению, в котором x1 ≠ 0, а x2 =…= xk = xr = 0. Базисными переменными при этом будут x1, xk +1 ,…, xr−1 , xr+1,…, xn.
Теперь через новые свободные переменные можно выразить и линейную функцию L. Если все коэффициенты при переменных в этой формуле положительны, то мы нашли оптимальное решение: оно получится, если все свободные переменные положить равными нулю. Если среди коэффициентов при переменных есть отрицательные, то процедура улучшения решения продолжается. Система вновь переразрешается относительно других базисных переменных, и т.д., пока не будет найдено оптимальное решение, обращающее функцию L в минимум.
13.2. Табличный алгоритм замены базисных переменных
Процедура «переразрешения» системы уравнений–ограничений ОЗЛП относительно базисных переменных может быть упрощена, если ее формализовать и свести к заполнению стандартных таблиц по определенному алгоритму [5].
Рассмотрим этот алгоритм на примере пяти уравнений–ограничений:
y1 = a11x1 + a12x2 +...+ a1n xn +b1, y2 = a21x1 + a22x2 +...+ a2n xn +b2,
.............................................
y5 = a51x1 + a52x2 +...+ a5n xn +b5
с четырьмя свободными переменными . x1, x2,…, x4. Пусть требуется обменять местами переменные x2 и у3 (замену обозначим x2↔ у3).
68
Запишем приведенные выше уравнения в стандартной форме, заменив каждый
коэффициент аij на –αij:
y1 |
= b1 −(α11x1 +α12x2 +...+α1nxn ), |
|||
y2 |
= b2 |
−(α21x1 |
+α22x2 |
+...+α2nxn ), |
y3 |
= b3 |
−(α31x1 |
+α32x2 |
+...+α3nxn ), |
............................................. |
||||
y5 |
= b5 |
−(α51x1 |
+α52x2 |
+...+α5nxn ). |
(13.3)
Вместо записи уравнений (13.3) можно заполнить стандартную таблицу, в которой будут указаны только свободные члены и коэффициенты при переменных (табл.13.1).
Таблица 13.1
Стандартная таблица симплекс-метода
|
Свободный |
x1 |
x2 |
x3 |
x4 |
|
член |
|
|
|
|
у1 |
b1 |
α11 |
α12 |
α13 |
α14 |
у2 |
b2 |
α21 |
α22 |
α23 |
α24 |
у3 |
b3 |
α31 |
α32 |
α33 |
α34 |
У4 |
b4 |
α41 |
α42 |
α43 |
α44 |
у5 |
b5 |
α51 |
α52 |
α53 |
α54 |
Для выполнения замены x2↔ у3 (т.е. для перевода x2 в базисные, а у3 в число свободных) выделим в стандартной таблице разрешающий элемент α32. Строку и столбец, в которой находится разрешающий элемент, назовем разрешающей строкой и разрешающим столбцом.
Найдем |
коэффициенты, |
которые нужно |
будет поставить в таблице |
после обмена |
||||||
x2↔ у3. Решая третье уравнение (13.3) относительно x2, получим: |
|
|||||||||
x2 = |
b2 |
– ( α31 x + |
1 |
y |
+ α33 |
x |
+ α34 |
x ). |
(13.4) |
|
α32 |
α32 |
|||||||||
|
α32 1 |
3 |
α32 |
3 |
α32 |
4 |
|
|||
Найдем преобразованные элементы других строк. Для этого подставим в первое |
||||||||||
уравнение (13.3) вместо x2 его выражение (13.4). В результате получим |
|
у1 |
|
|
− |
α12b3 |
|
|
α |
− α12α31 |
|
|
− α12 |
y |
|
α |
− α12α33 |
|
|
+ |
= b |
|
− |
x |
+ |
x |
|||||||||||||
|
|
1 |
|
|
|
|
11 |
α32 |
|
1 |
α32 |
3 |
|
13 |
α32 |
|
3 |
|
|
|
|
|
α32 |
|
|
|
|
|
|
|
|
|
|
+α14 − α12α34 x4 )α32
Аналогичным образом преобразуются и все остальные строки. Поместив новые коэффициенты в стандартную таблицу, мы получим преобразованную таблицу (табл.13.2).
Проанализировав табл. 13.2, можно сформулировать алгоритм преобразования коэффициентов стандартной таблицы [5].
1.Разрешающий элемент заменяется на обратную ему величину.
2.Все остальные элементы разрешающей строки делятся на разрешающий элемент.
3.Все элементы разрешающего столбца (кроме самого разрешающего элемента) меняют знак и делятся на разрешающий элемент.
4.Каждый из остальных элементов подвергается следующему преобразованию. К нему прибавляется произведение элемента, стоявшего в прежней разрешающей строке на том же месте по порядку (т.е. в том же столбце), на элемент, стоящий в новом разрешающем столбце на соответствующим месте (т.е. в той же строке, что и наш элемент).
69
Таблица 13.2
Преобразованная стандартная таблица коэффициентов
|
Свободный |
|
|
|
x1 |
|
у3 |
|
|
|
x3 |
|
|
|
x4 |
||||
|
|
член |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
у1 |
b − |
α12b3 |
α − |
α12α31 |
– |
α12 |
α − |
α12α33 |
α − |
α12α34 |
|||||||||
|
1 |
|
α32 |
11 |
|
α32 |
|
α32 |
13 |
|
α32 |
14 |
|
α32 |
|||||
у2 |
b − |
α22b3 |
α |
|
− |
α22α31 |
– |
α22 |
α |
|
− |
α12α33 |
α |
|
− |
α22α34 |
|||
|
2 |
|
α32 |
|
21 |
|
α32 |
|
α32 |
|
23 |
|
α32 |
|
24 |
|
α32 |
||
х2 |
|
|
b3 |
|
|
α31 |
– |
1 |
|
|
|
α33 |
|
|
α34 |
||||
|
|
|
α32 |
|
|
|
α32 |
α32 |
|
|
|
α32 |
|
|
α32 |
||||
у4 |
b − |
α42b3 |
α |
|
− |
α42α31 |
– |
α42 |
α |
|
− |
α42α33 |
α |
|
− |
α42α34 |
|||
|
4 |
|
α32 |
|
41 |
|
α32 |
|
α32 |
|
43 |
|
α32 |
|
44 |
|
α32 |
||
у5 |
b − |
α52b3 |
α |
|
− |
α52α31 |
– |
α52 |
α |
|
− |
α52α33 |
α |
|
− |
α52α34 |
|||
|
5 |
|
α32 |
|
51 |
|
α32 |
|
α32 |
|
53 |
|
α32 |
|
54 |
|
α32 |
Алгоритм преобразования xi↔уj стандартной таблицы сводится к следующим шагам.
1.Выделить в таблице разрешающий элемент αij. Вычислить его обратную величину
λ= 1/ αij и записать в нижней части той же ячейки (в правом нижнем углу).
2.Все элементы разрешающей строки (кроме самого αij) умножить на λ; результат записать в нижней части той же ячейки.
3.Все элементы разрешающего столбца (кроме самого αij) умножить на – λ; результат записать в нижней части той же ячейки.
4.Подчеркнуть в разрешающей строке все верхние числа (прежние элементы), за исключением самого разрешающего элемента, а в разрешающем столбце – все нижние числа (новые элементы), исключением самого разрешающего элемента.
5.Для каждого элемента, не принадлежащего ни к разрешающей строке, ни к разрешающему столбцу, записать в нижнюю часть ячейки произведение выделенных чисел, стоящих в то же столбце и в той же строке.
6.Переписать таблицу, заменив:
•xi на уj и обратно,
•элементы разрешающей строки и столбца – числами, стоящими в нижних частях тех же ячеек,
•каждый из остальных элементов – суммой чисел, стоящих в верхней и нижней части той же ячейки.
После замены xi↔ уj линейную функцию L нужно выразить через новые свободные переменные. Для этого может быть применен тот же алгоритм, что и для преобразования любой строки стандартной таблицы. Сначала L (12.2) приводится стандартной форме
L= с0 – (γ1x1 + γ2x2+…+ γпxп),
азатем ее коэффициенты помещаются в отдельную строку стандартной таблицы. Эта
строка отличается от остальных строк тем, что в ней никогда не выбирается разрешающий элемент.
С помощью табличного алгоритма обмена переменных в уравнениях ОЗЛП можно решить любую задачу линейного программирования или же убедится, что она не имеет решения.
70