ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ
Федеральное государственное бюджетное образовательное учреждение высшего образования «САНКТ-ПЕТЕРБУРГСКИЙ
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ им. проф. М. А. БОНЧ-БРУЕВИЧА»
С. А. Владимиров
ОПТИМИЗАЦИЯ
И МАТЕМАТИЧЕСКИЕ МЕТОДЫ
ПРИНЯТИЯ РЕШЕНИЙ
Практикум
Санкт-Петербург
2019
УДК 519.86 (076) ББК 22.18 я73
В 57
Рецензент доктор технических наук,
профессор кафедры СС и ПД О. С. Когновицкий
Рекомендован к печати редакционно-издательским советом СПбГУТ
Владимиров, С. А.
В57 Оптимизация и математические методы принятия решений : практикум /
С.А. Владимиров ; СПбГУТ. — СПб, 2019. — 93 с.
Практикум призван ознакомить учащихся с основами теории принятия решений, включая методы оптимизации и математические методы принятия решений. Представленный материал служит справочным и методическим пособием при выполнении курса практических работ по дисциплинам «Теория принятия решений» и «Оптимизация и математические методы принятия решений».
Предназначено для студентов-бакалавров, обучающихся по направлениям 09.03.01 «Информатика и вычислительная техника» и 09.03.04 «Программная инженерия».
УДК 519.86 (076) ББК 22.18 я73
c Владимиров С. А., 2019
c Федеральное государственное бюджетное образовательное учреждение высшего образования «Санкт-Петербургский государственный университет телекоммуникаций им. проф. М. А. Бонч-Бруевича», 2019
Содержание
Практическая работа 1. Постановка функциональной задачи ли- |
|
нейного программирования |
5 |
1.1. Цели работы. . . . . . . . . . . . . . . . . . . . . . . . . . . |
5 |
1.2. Теоретические сведения . . . . . . . . . . . . . . . . . . . . . |
5 |
1.3. Варианты для выполнения задания . . . . . . . . . . . . . . . . |
9 |
1.4.Порядок выполнения задания . . . . . . . . . . . . . . . . . . 16
1.5.Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . 17
Практическая работа 2. Нахождение базиса и приведение задачи к |
|
базисным переменным |
18 |
2.1.Цели работы. . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.Теоретические сведения. . . . . . . . . . . . . . . . . . . . . 18
2.3.Варианты для выполнения задания. . . . . . . . . . . . . . . . 21
2.4.Порядок выполнения задания . . . . . . . . . . . . . . . . . . 21
2.5.Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . 21
Практическая работа 3. Принятие оптимального решения в усло- |
|
виях неопределенности |
23 |
3.1.Цель работы. . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.Теоретические сведения. . . . . . . . . . . . . . . . . . . . . 23
3.3.Варианты для выполнения задания. . . . . . . . . . . . . . . . 28
3.4.Порядок выполнения задания . . . . . . . . . . . . . . . . . . 34
3.5.Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . 34
Практическая работа 4. Способы задания нечетких множеств |
36 |
4.1.Цели работы. . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2.Теоретические сведения. . . . . . . . . . . . . . . . . . . . . 36
4.3.Варианты для выполнения задания. . . . . . . . . . . . . . . . 42
4.4.Порядок выполнения задания . . . . . . . . . . . . . . . . . . 42
4.5.Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . 43
Практическая работа 5. Построение игровых моделей |
44 |
5.1.Цели работы. . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.2.Теоретические сведения. . . . . . . . . . . . . . . . . . . . . 44
5.3.Варианты для выполнения задания. . . . . . . . . . . . . . . . 47
5.4.Порядок выполнения задания . . . . . . . . . . . . . . . . . . 50
3
5.5. Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . |
51 |
Практическая работа 6. Определение параметров систем массово- |
|
го обслуживания |
52 |
6.1.Цели работы. . . . . . . . . . . . . . . . . . . . . . . . . . . 52
6.2.Теоретические сведения. . . . . . . . . . . . . . . . . . . . . 52
6.3.Варианты для выполнения задания. . . . . . . . . . . . . . . . 65
6.4.Порядок выполнения задания . . . . . . . . . . . . . . . . . . 68
6.5.Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . 68
Практическая работа 7. Методы экспертных оценок в задачах при- |
|
нятия решений |
70 |
7.1.Цели работы. . . . . . . . . . . . . . . . . . . . . . . . . . . 70
7.2.Теоретические сведения . . . . . . . . . . . . . . . . . . . . . 70
7.3.Варианты для выполнения задания . . . . . . . . . . . . . . . . 74
7.4.Порядок выполнения задания . . . . . . . . . . . . . . . . . . 74
7.5.Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . 76
Практическая работа 8. Решение технологической задачи |
77 |
8.1.Цели работы. . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.2.Теоретические сведения. . . . . . . . . . . . . . . . . . . . . 77
8.3.Варианты для выполнения задания. . . . . . . . . . . . . . . . 77
8.4.Порядок выполнения задания . . . . . . . . . . . . . . . . . . 78
8.5.Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . 78
Практическая работа 9. Нахождение оптимальных решений в за- |
|
дачах нелинейного программирования с применением метода мно- |
|
жителей Лагранжа и теоремы Куна–Таккера |
80 |
9.1.Цели работы. . . . . . . . . . . . . . . . . . . . . . . . . . . 80
9.2.Теоретические сведения. . . . . . . . . . . . . . . . . . . . . 80
9.3.Варианты для выполнения задания. . . . . . . . . . . . . . . . 90
9.4.Порядок выполнения задания . . . . . . . . . . . . . . . . . . 91
9.5.Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . 92
4
Практическая работа 1
Постановка функциональной задачи линейного программирования
1.1. Цели работы
Научиться представлять функциональную задачу линейного программирования в различных формах. Научиться формулировать целевую функцию задачи, составлять матрицы коэффициентов, свободных членов и переменных системы ограничений задачи. Научиться представлять исходные данные задачи в векторной форме. Научиться оперировать направлением экстремума в целевой функции задачи.
1.2. Теоретические сведения
Рассмотрим основные определения и постановку задач на примере линейного программирования.
В общем виде задача формулируется в виде целевой функции, определяющей направление поиска оптимального (наилучшего) решения, и некоторых условий (функций или системы ограничений), задающих область поиска таких решений.
Целевая функция или критерий выбора оптимального решения (критерий эффективности) есть число или система чисел, являющихся мерой для сравнения количественных или качественных характеристик рассматриваемой системы или модели, представляет собой функцию многих переменных, несущую определенный физический смысл в зависимости от поставленной задачи. Для правильного определения и формулировки целевой функции необходимо использовать следующие принципы:
функция должна точно отражать конечную цель задачи и обеспечивать принятие оптимального решения;
функция должна быть чувствительна к изменению основных факторов, влияющих на результат решения задачи;
желательно, чтобы выбранная или составленная функция имела определенный физический смысл и представляла собой четкое аналитическое выражение.
Для задач линейного программирования характерно следующее:
целевая функция W = F(x) линейно зависит от некоторых элементов решения x1; x2; :::; xn;
ограничения, налагаемые на элементы решения, имеют вид линейных равенств или неравенств относительно x1; x2; :::; xn.
5
1.2.1. Постановка задачи
Дана целевая функция — цель задачи:
n
max(min)W = max(min)F(x) = å cjxj = c1x1 + c2x2 + ::: + cnxn
j=1
при ограничениях
a11x1 + a12x2 + ::: + a1nxn 6 b1 a21x1 + a22x2 + ::: + a2nxn 6 b2
:::
am1x1 + am2x2 + ::: + amnxn 6 bm
и при условии xj > 0; где ( j = 1;n).
Любое множество чисел x1; x2; :::; xj; :::; xn, удовлетворяющее ограничениям, называется допустимым решением (допустимым планом).
Запишем коротко ограничения разных типов:
уравнения |
n |
|
|
|
å ajxj = bi; |
где(i = 1;m); |
|
неравенства |
j=1 |
|
|
|
> |
|
|
|
n |
где(i = 1;m); |
|
|
j=1 |
||
|
å ajxj |
6 bi; |
|
уравнения и неравенства
n |
263 |
|
å ajxj |
= |
bi; где(i = 1;m); |
j=1 |
4>5 |
|
условия неотрицательности
xj > 0; j = 1;n:
Матричная форма
max(min)CX AX 6 B X > 0;
6
где A = |
0a21 |
a22 |
::: a2n |
1, B = |
0b2 |
1, |
|||
|
a11 |
a12 |
::: |
a1n |
|
b1 |
|
||
|
Ba::: |
a |
m2 |
::: |
a |
|
C |
Bb:::C |
|
|
B m1 |
|
|
|
mnC |
B mC |
|||
|
@ |
|
|
|
|
|
A |
@ |
A |
CX и AX — произведения матриц.
0 1
x1
Bx2 C
X = B:::C, C = (c1; c2; :::; cn).
@ A xn
Векторная форма
max(min)CX
x1A1 + x2A2 + ::: + xnAn 6 B ; X > 0
0 1
a1 j
Ba2 j C
где Aj = B C при j = 1; n вектор-столбец коэффициентов xj из элементов
@ ::: A
am j
j столбца матрицы A;
0 1 b1
Bb2 C
B = B C — вектор-столбец B свободных членов или значений уравнений
@:::A
bm
(неравенств) системы ограничений;
X = (x1; x2; :::; xn) и C = (c1; c2; :::; cn) — вектор-строки переменных в задаче и коэффициентов целевой функции соответственно,
CX — скалярное произведение векторов.
Символика теории множеств
max(min)[CX : AX 6 B; X > 0]:
1.2.2. Переходы в задачах
Задача max — min
Задача
n
max å ajxj > bi (i = 1; m)
j=1
эквивалентна задаче
n
min( å ajxj) 6 ( bi) (i = 1; m):
j=1
7
Приведение неравенства к равенству
К исходному неравенству
n
å ajxj 6 bi (i = 1; m)
j=1
прибавляем
xn+1 > 0
и получаем
n
å ajxj + xn+1 = bi (i = 1; m):
j=1
Пример.
Задана целевая функция
max(x1 + 2x2 + 5x3)
с системой ограничений
8
> 2x1 x2 + x3 = 2;
>
< x1 + 2x2 + 3x3 = 5; > x1 + x2 x3 6 4;
>
: x1 + 2x2 + x3 > 1:
Вводим две переменные x4 и x5:
x4 = 4 x1 x2 + x3; x5 = 1 x1 + 2x2 + x3;
при x4; x5 > 0.
Получаем систему уравнений
8
> 2x1 x2 + x3 = 2;
>
< x1 + 2x2 + 3x3 = 5; > x1 + x2 x3 + x4 = 4;
>
: x1 2x2 x3 + x5 = 1:
Приведение равенства к неравенству
n
å ai jxj = bi (i = 1; m)
j=1
8