Содержание работы или список заданий
|
ЗАДАНИЕ 1
1. Найти решение игры двух лиц с нулевой суммой графическим методом. Для сокращения числа стратегий использовать отношение доминирования. В приведенных ниже вариантах платежных матриц строки соответствуют стратегиям 1-го игрока, а столбцы – стратегиям 2-го. Платежи имеют смысл выигрыша или проигрыша для 1-го игрока (обозначено буквами В и П соответственно после номера варианта).
Варианты задач
1 (П) 2 (В) 3 (П) 4 (В)
–2 4 0 5 7 4 2 –2 0 5 3 –1 0 1 3 0 4
3 –2 1 4 5 2 –1 4 7 –2 1 2 2 –5 1 –6 2
1 –3 –2 –1 7 1 0 –2 –1 5 6 7 7 3 –2 3 –1
0 4 1 6 8 3 –4 4 5 3 4 3
2 5 2 6
5 (В) 6 (П) 7 (П) 8 (В)
4 0 2 1 4 –2 6 3 4 5 –2 1 2 6 2 5 –1
6 7 1 7 2 5 2 6 1 0 –8 8 0 4 –4 2 5
5 1 2 1 –1 4 0 4 –1 3 0 6 3 5 2 3 –1
9 (П) 10 (В) 11 (П) 12 (В)
1,5 3 –5 0 8 3 2 –2 0 7 2 –1 4 4 –1 7 4
7 1 4 2 5 2 –1 4 7 3 0 2 5 –2 0 1 –1
1 2 –5 0 7 1 0 –2 –1 8 2 6 4 5 3 2 5
7,5 2 6 3 4 2 –2 3 6 3 –2 1 5 0 –2 –5 1
13 (П) 14 (В) 15 (П) 16 (В)
30 10 40 28 1,5 0,51 0,44 0,6 3 –1 4 10 6 9 –2
90 50 90 85 0,4 1,5 1,5 1,6 –5 2 –3 4 –1 7 11
40 80 50 30 1,08 1,1 1,0 1,1 2 7 2 12 6 10 –1
20 30 20 20 0,9 1,25 1,22 1,3 4 3 6 4 5 7 13
17 (П) 18(В) 19(П) 20 (В)
–5 0 –2 1 3 –1 5 0 5 –1 4 5 2 –1 4 7
4 3 –1 7 –2 6 0 2 4 3 –2 7 1 0 –2 –1
8 –3 4 –2 7 –3 7
–2 –1 1 –3 8 4 2 –2 0
–4 2 –3 1 6 0 4
21(П) 22(В) 23(П) 24(В)
–5 0 –2 1 3 –1 5 0 5 –1 4 5 2 –1 4 7
4 3 –1 7 –2 6 0 2 4 3 –2 7 1 0 –2 –1
8 3 4 –2 7 –3 7 –2 –1 1 –3 8 4 2 –2 0
–4 2 –3 1 6 0 4
25(П) 26(В) 27(П) 28(В)
–2 1 2 2 3 0 4 9 –2 5 1 0 3 –1 5
8 3 –4 4 1 –6 2 –5 0 –2 1 7 –2 6 0
3 0 –1 0 –2 3 –1 4 3 –1 7 –2 7 –3 7
5 6 7 7 3 4 7 8 –3 4 –2 3 –4 2 –3
5 2 6
29(П) 30(В) 31(П) 32(В)
–1 4 0 5 8 4 2 –2 0 3 0 –1 0 2 3 0 4
3 –2 2 4 5 2 –1 4 7 –2 1 2 2 –5 1 –6 2
1 –3 –2 –1 7 1 0 –2 –1 5 6 7 7 3 –2 3 –1
0 4 1 6 8 3 –4 4 5 3 4 7
2 5 2 6
33(П) 34(В) 35(П) 36(В)
1 2 3 5 4 3 6 0 5 8 7 –1 3 1 0 3
–2 0 –1 4 –2 0 7 1 2 4 1 0 2 –2 1 1
3 –1 4 3 1 2 6 0 –1 2 0 4 –2 –3 4 5
2 6 2 4 –2 –2 5 4 –1 6 6
0 4 5 7 0 –1
37(П) 38(В) 39(П) 40(В)
–2 1 2 2 3 0 4 9 –2 5 1 0 3 –1 5
8 3 –4 4 1 –6 2 –5 0 –2 1 7 –2 6 0
3 0 –1 0 –2 3 –1
4 3 –1 7 –2 7 –3 7
5 6 7 7 3 4 7 8 –3 4 –2 3 –4 2 –3
5 2 1
41 (П) 42 (В) 43 (П) 44 (В)
–1 4 0 5 8 4 2 –2 0 3 0 –1 0 2 3 0 4
3 –2 2 4 5 2 –1 4 7 –2 1 2 2 –5 1 –6 2
1 –3 –2 –1 7 1 0 –2 –1 5 6 7 7 3 –2 3 –1
0 4 1 6 8 3 –4 4 5 3 4 7
2 5 2 6
45 (П) 46 (В) 47 (П) 48(В)
1 2 3 5 4 3 6 0 5 8 7 –1 3 2 0 3
–2 0 –1 4 –2 0 7 1 2 4 1 0 2 –2 1 1
3 –1 4 3 4 2 6 0 –1 2 0 4 –2 –3 4 5
2 6 2 4 –2 –2 5 4 –1 6 6
0 4 5 7 0 –1
2. Формализовать следующую ситуацию. Два игрока имеют в течение всей игры по две карты одной масти, например у одного пики, у другого буби. Игра состоит из множества розыгрышей. В розыгрыше каждый игрок кладет по одной карте на стол, затем каждый пытается угадать, что положил противник, называя его карту. После этого карты на столе открываются и тот, кто угадал, получает сумму очков, а второй такую сумму проигрывает. Так , если на кону были дама и король, то выигравший получает 7. Если оба угадали или оба не угадали, то выигрыш и проигрыш равны нулю. Карты возвращаются игрокам для следующего розыгрыша.
Составить платежную матрицу этой игры с указанием смысла платежей для первого игрока. Определить верхнюю и нижнюю цену игры и область, в которой игра имеет решение.
Выбор карт для игроков произвольный, в том числе у игроков могут быть одинаковые карты, но разной масти.
Контрольные вопросы
1. В чем заключается постановка задачи в виде игры?
2. Что значит решить игру?
3. Что такое игра с нулевой суммой?
4. Когда имеет место отношение доминирования между двумя стратегиями?
5. Чем отличаются решения игры в чистых и смешанных стратегиях?
6. Каков смысл для каждого из игроков верхней и нижней цены игры?
7. Как соотносятся допустимые множества чистых и смешанных стратегий игры (пересекаются, одно включает другое и т.п.)?
8. Каков смысл цены игры при решении в смешанных стратегиях?
9. В чем состоит оптимальное поведение игрока в случае решения в смешанных стратегиях?
10. Как определить вероятность выпадения конкретного платежа, если известно решение игры?
11. Сколько примерно получит один игрок и проиграет другой за 1000 розыгрышей при оптимальном поведении обоих игроков?
12. Что такое активные стратегии?
13. В каком случае выигрывающий игрок при оптимальном поведении может получить больше цены игры?
14. Что ожидает игрока, отклонившегося от расчетного распределения вероятностей?
15. Если оба игрока ведут себя оптимально и при этом выигрывающий игрок получил за 1000 розыгрышей 7000 , то какова примерно цена игры?
ЗАДАНИЕ 2
Необходимо решить задачу линейного программирования симплекс-методом. Результаты представить в виде последовательности симплекс-таблиц. Показать построение начального решения и вычисления при переходе от начальной таблицы к первой. Выписать оптимальное решение (значения критерия и всех переменных).
Решить также задачу графически (если переменных три и есть равенство, то предварительно преобразовать условия к стандартному виду, что сократит число переменных до двух). Сравнить результаты решений.
Варианты задания
№1 L=2x1 – 4x2 min
8x1 – 5x2 16
x1 + 3x2 2
2x1 + 7x2 9
xj 0 №2 L= x1 + x2 max
x1 + 2x2 14
4x1 + 6x2 24
–5x1 + 3x2 15
xj 0
№3 L= – x1 – x2 min
2x1 + 3x2 6
4x1 + 2x2 40
–3x1 + 5x2 30
x1,x2 0 №4 L= 8x1 – 2x2 min
3x1 – x2 4
4x1 – 2x2 5
8x1 – x2 15
xj 0
№5 L= 4x1 + 6x2 max
2x1 + 3x2 6
4x1 + 2x2 40
–3x1 + 5x2 30
x1,x2 0 №6 L= 2x1 – 4x2 max
8x1 – 5x2 16
2x1 + x2 2
2x1 + 7x2 9
xj 0
№7 L= x1 + 2x2 max
x1 + x2 6
3x1 + 10x2 26
4x1 + 2x2 7
xj 0 №8 L= 2x1 + 3x2 max
2x1 + x2 10
–2x1 + 3x2 6
2x1 + 4x2 8
xj 0
№9 L= x1 + 2x2 max
4x1 – 2x2 12
2x1 + 4x2 16
–x1 + 3x2 6
xj 0 №10 L= 2x1 + x2 max
20x1 + 10x2 75
12x1 + 7x2 55
25x1 + 10x2 90
xj 0
№11 L= 3x1 + 7x2 max
3x1 + 5x2 15
x1 + x2 2
5x1 + 2x2 10
xj 0 №12 L= 2x1 + 3x2 min
x1 + x2 4
6x1 + 2x2 8
x1 + 5x2 4
xj 0
№13 L= – 2x1 + x2 min
3x1 – 2x2 12
– x1 + 2x2 8
2x1 + 3x2 6
xj 0 №14 L= 2x1 + 3x2 min
3x1 + 2x2 6
x1 + 4x2 4
x1 + x2 3
xj 0
№15 L= x1 + 2x2 – x3 max
– x1 + 4x2 –2x3 12
x1 + x2 + 2x3 17
2x1 – x2 + 2x3 = 4
xj 0 №16 L= x1 + x2 max
2x1 + 4x2 16
–4x1 + 2x2 8
x1 + 3x2 9
xj 0
№17 L= 2x1 + 3x2 max
2x1 + x2 10
2x1 + 4x2 8
–2x1 + 3x2 6
xj 0
№18 L= 3x1 + x2 max
x1 + x2 5
2x1 + 3x2 21
7x1 + x2 35
xj 0
№19 L= x1 + x2 max
x1 + 2x2 14
2x1 + 3x2 12
–5x1 + 3x2 15
xj 0 №20 L= 5x1 – 2x2 min
3x1 + x2 1
–x1 + x2 25
7x1 – 2x2 8
xj 0
№21 L= 2x1 + 4x2 max
4x1 – 2x2 12
2x1 + 4x2 16
–2x1 + 6x2 12
xj 0 №22 L= 2x1 – 4x2 min
8x1 – 5x2 16
x1 + 3x2 2
2x1 + 7x2 8
xj 0
№23 L= x1 + 2x2 – x3 max
– x1 + 4x2 –2x3 6
x1 + x2 + 2x3 6
2x1 – x2 + 2x3 = 4
xj 0 №24 L= 9x1 + 5x2 max
3x1 – 6x2 1
5x1 + 2x2 28
x1 + 7x2 42
xj 0
№25 L= x1 + 0,5x2 max
2x1 + x2 3
5x1 + 2x2 7
–3x1 + 5x2 10
xj 0 №26 L= –x1 – 0,5x2 max
3x1 + x2 10
x1 + 2x2 7
–3x1 + 11x2 30
xj 0
№27 L= 2x1 + 3x2 max
–x1 + 3x2 9
8x1 + 3x2 32
7x1 + 3x2 6
xj 0
№28 L= x1 – x2 min
7x1 + 3x2 6
–x1 + 3x2 9
8x1 + 3x2 32
xj 0
№29 L= 3x1 + 2x2 max
–x1 + 3x2 9
8x1 + 3x2 32
7x1 + 3x2 6
xj 0
№30 L= 3x1 + 2x2 max
–x1 + 3x2 9
5x1 + 3x2 32
7x1 + 3x2 6
xj 0
№31 L= 3x1 + 2x2 max
7x1 + 3x2 6
–x1 + 2x2 9
5x1 + 3x2 32
xj 0
№32 L= x1 + 2x2 max
7x1 + 3x2 6
–x1 + 2x2 9
5x1 + 3x2 32
xj 0
№33 L= 4x1 + 7x2 max
3x1 + 2x2 6
–2x1 + 5x2 10
7x1 – 3x2 21
xj 0
№34 L= 5x1 + 7x2 max
7x1 – 3x2 21
3x1 + 4x2 6
–2x1 + 5x2 10
xj 0
№35 L= x1 + 3x2 min
2x1 + 3x2 13
–2x1 + 4x2 3
3x1 + 5x2 10
xj 0
№36 L= 3x1 + 2x2 max
3x1 – 2x2 15
x1 + 2x2 14
x1 + x2 1
x2 5
xj 0
№37 L= 2x1 + 3x2 max
2x1 – 3x2 6
3x1 + 2x2 21
–x1 + x2 3
x2 4
xj 0 №38 L= –2x1 + x2 min
3x1 + 2x2 21
2x1 – 3x2 6
4x1 + 5x2 20
xj 0
№39 L= 2x1 +5x2 min
2x1 – 3x2 6
–x1 + x2 3
4x1 + 5x2 20
xj 0
№40 L= x1 – 2x2 min
2x1 + 3x2 30
–2x1 + x2 6
x1 + x2 4
xj 0
№41 L= x1 – 2x2 max
x1 – x2 4
–7x1 + 4x2 28
3x1 + 2x2 6
xj 0
№42 L=2x1 + 3x2 max
x1 – x2 4
–x1 + 3x2 15
3x1 + 2x2 6
xj 0
№43 L= 5x1 + 4x2 max
x1 – 2x2 2
3x1 + 3x2 15
7x1 + 17x2 119
xj 0
№44 L= x1 – 4x2 min
–x1 + 2x2 8
x1 + x2 5
7x1 + 17x2 119
xj 0
Контрольные вопросы
1. Что такое базисное решение?
2. Чем определяется размерность базисного решения?
3. Для чего необходимы искусственные переменные?
4. С какой целью искусственные переменные вводятся в линейную форму?
5. Как вычисляется ?
6. Какие из полученных симплекс-таблиц соответствуют допустимому решению?
7. Где в симплекс-таблице находятся значения базисных переменных и критерия?
8. Что показывает относительная оценка?
9. Что означает наличие искусственной переменной в последней симплекс-таблице?
10. Как распознается неразрешимость задачи из-за неограниченности критерия?
11. Какими способами можно вычислить относительную оценку?
12. На какой итерации обнаруживается неразрешимость задачи из-за противоречивости условий?
13. Можно ли определить по оптимальной симплекс-таблице, сколько решений имеет задача?
14. Как установить без вычислений, какие из неравенств задачи выполняются как строгие неравенства, а какие как равенства (в оптимальном решении)?
15. К чему приведет одно симплекс-преобразование в задаче на максимум, если в качестве направляющего столбца взять столбец с положительной оценкой?
Задание 3.
Следующие Т-задачи решить методом потенциалов. Начальный план строить по правилу северо-западного угла. Матрицу оценок (кроме начальной) получать преобразованием предыдущей. Записать математическую модель задачи.
№1 №2
bj
ai 10 20 20 10 bj
ai 80 30 50 40
10 10 15 15 8 70 8 7 4 7
20 40 10 30 5 40 3 5 6 4
10 35 25 40 10 20 9 2 5 3
№3 №4
bj
ai 30 25 18 20 bj
ai 20 60 55 45
40 1 2 6 4 45 2 5 3 4
30 3 1 3 2 35 6 1 2 5
20 5 7 5 1 70 3 4 3 8
№5 №6
bj
ai 120 40 60 80 bj
ai 20 18 44 75
180 2 3 4 3 40 1 7 2 5
60 5 3 1 2 30 3 8 4 1
80 2 1 4 2 50 6 3 5 3
№7 №8
bj
ai 10 40 20 60 bj
ai 15 40 20 50
30 2 7 3 6 48 4 7 2 5
70 9 4 5 7 25 3 5 8 6
50 5 7 6 2 30 6 10 9 7
№9 №10
bj
ai 2 3 3 16 bj
ai 10 20 30 40
68 18 2 9 7 45 5 4 0 5
55 30 4 1 55 20 3 5 3 0
40 6 4 8 3 35 0 6 7 6
№11 №12
bj
ai 75 80 60 85 bj
ai 45 45 100 160
100 6 7 3 5 180 6 7 3 2
150 1 2 5 6 90 5 1 4 3
50 8 10 20 1 170 3 2 6 2
№13 №14
bj
ai 25 30 40 15 bj
ai 35 80 25 70
20 1 3 3 8 30 1 9 7 2
20 8 6 2 6 40 3 1 5 5
40 7 7 3 8 70 6 8 3 4
45 5 2 4 5 60 2 3 1 3
№15 №16
bj
ai 5 15 15 10 bj
ai 35 40 40 30
15 10 0 20 11 40 3 2 4 1
25 12 7 9 20 50 2 3 1 5
5 0 14 6 18 30 3 2 4 4
№17 №18
bj
ai 30 60 45 25 bj
ai 400 800 200 500
50 4 7 1 3 500 3 5 6 1
70 5 9 6 2 700 5 1 3 3
40 8 2 9 11 600 4 5 8 1
№19 №20
bj
ai 80 80 60 80 bj
ai 20 34 16 10 25
160 5 4 3 4 40 2 6 3 4 8
140 3 2 5 5 30 1 5 6 9 7
60 1 6 3 2 35 3 4 1 6 10
№21 №22
bj
ai 80 60 170 80 bj
ai 180 110 60 40
110 8 1 9 7 175 9 7 5 3
190 4 6 2 12 125 1 2 4 6
90 3 5 8 9 140 8 10 12 1
№23 №24
bj
ai 70 90 60 bj
ai 25 30 40 15
20 1 5 3 10 1 3 3 8
40 1 2 4 20 8 6 2 6
50 5 5 1 35 4 7 7 3
40 3 5 2 45 5 2 4 5
№25 №26 №27
bj
ai 27 10 30 bj
ai 18 37 50 bj
ai 28 37 50
15 8 5 10 60 4 7 3 35 4 7 3
35 6 7 9 42 9 5 13 42 9 5 13
20 10 12 8 20 11 8 9 20 11 8 9
10 5 3 4 75 7 12 20 75 7 12 20
№28 №29
bj
ai 110 90 120 80 150 bj
ai 80 50 50 70
180 7 12 4 6 5 80 4 2 3 1
350 1 8 6 5 3 140 6 3 5 6
20 6 13 8 7 4 70 3 2 6 3
№30 №31
bj
ai 56 74 100 bj
ai 56 74 60 54
70 8 14 6 30 8 14 6 4
84 18 10 26 84 7 10 9 7
40 22 16 18 20 12 16 18 6
150 14 24 40 110 14 24 10 9
№32 №33 №34
bj
ai 27 10 31 bj
ai 78 37 50 bj
ai 58 37 60
15 9 5 11 60 6 7 3 35 10 7 3
35 4 7 9 42 9 5 13 42 9 5 13
20 10 6 8 20 11 8 9 20 11 8 9
10 5 3 4 75 7 12 5 75 7 12 11
№35 №36
bj
ai 35 30 45 15 bj
ai 35 80 25 70
20 4 3 3 8 30 1 4 7 2
20 8 6 2 6 45 3 1 5 5
40 9 7 3 8 75 6 8 3 4
45 5 2 4 5 60 2 3 1 3
№37 №38
bj
ai 10 20 20 10 bj
ai 65 30 50 40
15 10 9 15 8 70 8 7 4 7
20 25 10 18 5 40 3 5 6 4
10 14 25 12 10 20 9 2 5 3
№39 №40 №41
bj
ai 27 12 31 bj
ai 72 37 51 bj
ai 48 37 60
19 9 5 11 60 6 7 3 35 6 7 3
35 4 7 9 42 9 5 13 42 9 5 13
20 10 6 8 20 10 8 9 20 11 8 9
10 5 3 4 75 7 12 5 75 7 12 11
№42 №43 №44
bj
ai 37 10 30 bj
ai 23 67 58 bj
ai 25 37 50
18 8 5 6 55 4 7 3 31 4 7 3
35 6 4 9 42 9 5 13 42 9 5 13
20 10 12 8 20 11 8 9 20 11 8 9
10 5 3 4 65 7 12 10 75 6 12 7
Контрольные вопросы?
1. Чему равна размерность базисного решения транспортной задачи?
2. Что означает вырожденность базисного решения?
3. Каково условие разрешимости Т-задачи?
4. Как строится цикл пересчета?
5. Что будет, если переместить по циклу >o?
6. Что будет, если переместить по циклу <o?
7. Как вычисляются потенциалы пунктов?
8. Что показывает относительная оценка ij?
9. Может ли в оптимальном решении выполняться неравенство Vj–Ui>Cij?
10. Как установить неединственность оптимального решения Т-задачи?
11. Если задача имеет множество решений, то можно ли отличить случаи расположения его на ребре и грани?
12. Каков смысл переменных в фиктивном столбце, в фиктивной строке?
13. Как устанавливается оптимальность решения?
14. Какой смысл имеют значения в фиктивной строке (столбце) оптимального плана перевозок?
15.
ЗАДАНИЕ 4. Целочисленное программирование
Решить задачи методом ветвей и границ. Корневую задачу решить симплекс-методом, остальные графически. Построить дерево решений.
№1 L=7x1 + 4x2 max
4x1 + x2 14
3x1 + 2x2 12
xj 0, цел. №2 L= 2x1 + 3x2 min
7x1 + 20x2 140
2x1 + x2 18,2
xj 0, цел.
№3 L=6x1 + 4x2 min
4x1 + 2x2 7
x1 – x2 1
xj 0, цел. №4 L= 6x1 + 9x2 max
5x1 + 7x2 35
4x1 + 9x2 36
xj 0, цел.
№5 L=4x1 + 4x2 max
3x1 + 2x2 10
x1 + 2x2 9
xj 0, цел.
№6 L= 2x1 + 7x2 max
4x1 + 5x2 20
– x1 + 2x2 1
xj 0, цел.
№7 L=6x1 + 9x2 max
8x1 + 18x2 72
5x1 + 7x2 35
xj 0, цел.
№8 L= –2x1 – 3x2 min
5x1 + 7x2 35
4x1 + 9x2 36
xj 0, цел.
№9 L=9x1 + 12x2 max
14x1 + 9x2 51
– 6x1 + 3x2 1
xj 0, цел.
№10 L= x1 + x2 min
2x1 + 4x2 7
10x1 + 3x2 15
xj 0, цел.
№11 L=6x1 + 8x2 max
– 12x1 + 6x2 1
14x1 + 9x2 51
xj 0, цел.
№12 L= 9x1 + 12x2 max
–12x1 + 6x2 2
14x1 + 9x2 51
xj 0, цел.
№13 L= 14x1 + 8x2 max
6x1 + 4x2 24
4x1 + x2 14
xj 0, цел.
№14 L= 2x1 + 6x2 max
10x1 + 11x2 110
– x1 + 2x2 7
xj 0, цел.
№15 L= 4x1 + 6x2 max
10x1 + 14x2 70
4x1 + 9x2 36
xj 0, цел.
№16 L= 6x1 + 8x2 max
6x1 –3x2 – 1
14x1 + 9x2 51
xj 0, цел.
№17 L=x1 + x2 max
2x1 + 5x2 16
6x1 + 5x2 27
xj 0, цел. №18 L= 2x1 + 7x2 max
– 2x1 + 4x2 2
4x1 + 5x2 20
xj 0, цел.
№19 L=x1 + x2 max
4x1 + 5x2 18
– x1 + 2x2 1
xj 0, цел.
№20 L= 4x1 + 14x2 max
8x1 + 10x2 40
– 2x1 + 4x2 2
xj 0, цел.
№21 L=3x1 + 3x2 min
4x1 + 8x2 14
10x1 + 3x2 15
xj 0, цел. №22 L= x1 + x2 max
2x1 + 11x2 38
4x1 –5x2 5
xj 0, цел.
№23 L=7x1 + 2x2 max
4x1 + x2 14
6x1 + 4x2 24
xj 0, цел.
№24 L=x1 + x2 max
4x1 + 5x2 18
–x1 + 2x2 1
xj 0, цел.
№25 L=8x1 + 5x2 max
x1 + x2 6
9x1 + 5x2 45
xj 0, цел.
№26 L=5x1 + 9x2 max
–6x1 + 3x2 1
2x1 + 5x2 28
xj 0, цел.
№27 L= x1 –x2 min
2x1 + x2 6
– 5x1 + 2x2 0
xj 0, цел.
№28 L= 4x1 + 3x2 max
6x1 – 12x2 1
9x1 + 14x2 51
xj 0, цел.
№29 L=3x1 + 2x2 min
20x1 + 7x2 140
x1 + 2x2 18
xj 0, цел. №30 L=x1 + x2 max
5x1 + 4x2 18
2x1 – x2 1
xj 0, цел.
№31 L= 2x1 + 3x2 max
5x1 + 7x2 70
4x1 + 9x2 72
xj 0, цел.
№32 L=13x1 – 6x2 max
12x1 + 11x2 132
4x1 – 5x2 20,5
xj 0, цел.
№33 L=–11x1 + 6x2 min
12x1 + 11x2 132
–x1 + 2x2 2,2
xj 0, цел. №34 L=11x1 – 6x2 max
8x1 + 13x2 104
–x1 + 2x2 2,2
xj 0, цел.
№35 L= 7x1 + 3x2 max
5x1 + 2x2 20
4x1 + 2x2 19
xj 0, цел.
№36 L=4x1 + 7x2 max
x1 + 4x2 14
2x1 + 3x2 12
xj 0, цел.
№37 L=x1 + x2 max
11x1 + 2 x2 38
–5x1 + 4x2 5
xj 0, цел.
№38 L=5x1 + 1,6x2 max
–0,6x1 + x2 2,5
5x1 + 1,5x2 22,5
xj 0, цел.
№39 L=25x1 + 8x2 max
x1 + 0,3x2 5
–1,2x1 + x2 5
xj 0, цел.
№40 L=5x1 + 2x2 max
12x1 + 11x2 132
–x1 + 2x2 2,2
xj 0, цел.
№41 L=–11x1 + 7x2 min
12x1 + 11x2 132
–x1 + 2x2 3
xj 0, цел №42 L=9x1 + 6x2 max
10x1 + 3x2 46
–6x1 + 5x2 25
xj 0, цел.
№43 L=x1 + 2x2 min
5x1 + 7x2 17,5
2x1 + 5,5x2 11
xj 0, цел
№44 L=–x1 + 3x2 max
23x1 + 40x2 184
–11x1 + 10x2 22
xj 0, цел.
Контрольные вопросы
1. Что такое выпуклая оболочка целочисленной задачи?
2. В чем состоит идея метода отсечения?
3. Как изменяется допустимое множество задачи ЛП при добавлении требования целочисленности?
4. В каких случаях обрывается ветвь дерева решений?
5. При выполнении каких условий порождаются две новые задачи? В каком порядке они проверяются?
6. Условие завершения работы алгоритма?
7. Что такое рекорд?
8. Что такое верхняя оценка (граница) в задаче на максимум?
9. Как соотносятся допустимые множества задач, лежащих в разных ветвях?
10. При каких исходных параметрах алгоритма не найдется решение разрешимой задачи?
11. Как и почему изменяется значение критерия задач в одной ветви?
12. Какое решение дает алгоритм ветвей и границ: точное или приближенное?
13. Метод применяется для полностью целочисленных задач или для смешанных, или для тех и других?
14. Как после завершения алгоритма можно быстро определить: задача имеет решение или нет?
15. Какое решение находит алгоритм: локальное или глобальное? Обоснуйте ответ.
16. Метод ветвей и границ содержит признак оптимальности?
Задание 5. Динамическое программирование
Задача замены оборудования
Условия. Известны характеристики станка, зависящие от его возраста t на начало года:
r(t) – стоимость продукции, производимой за год;
u(t) – годовые эксплуатационные затраты;
s(t) – остаточная стоимость (выручка от продажи станка).
На начало планового периода в N лет станок имеет возраст t=t0. В начале любого года станок можно не заменять (сохранить) или продать и купить такой же новый по цене P (включая установку и пр.). Продолжительность замены много меньше года.
Необходимо методом ДП разработать оптимальную политику замены станка для N=10 и t0=0-6. Исходные данные приведены в табл.1 и 2 (рассматривается замена одного станка). Показать все шаги решения согласно процедуре динамического программирования. Результаты представить в виде таблицы, в клетках которой должны быть оптимальные значения критерия и переменной (заголовки столбцов – возраст от 0 до 9, заголовки строк – номера шагов). Понять, как из итоговой таблицы получать решение для конкретных значений t0 и N.
Таблица 1
Тип станка Характе-ристики t
0 1 2 3 4 5 6 7 8 9 10
A r(t) 29 27 27 25 24 23 23 21 20 18 16
u(t) 7 8 9 10 11 11 12 14 15 15 16
B r(t) 25 24 23 21 20 20 19 19 18 17 17
u(t) 9 10 10 11 12 13 13 14 15 16 17
C r(t) 33 32 32 30 29 28 27 26 24 22 20
u(t) 10 12 12 14 14 15 16 17 17 18 19
Таблица 2
Вариант 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Тип станка A B B A C C A B A C B A A C C
P 20 18 17 19 21 22 20 18 19 21 17 19 20 24 22
S 9 6 8 7 8 11 7 8 10 11 7 9 11 12 10
Продолжение таблицы
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
C A C B C A B C A A B C C A B B B
25 21 27 22 26 23 20 25 21 22 18 26 24 23 18 16 19
11 12 14 10 15 11 9 13 12 8 7 14 12 11 9 6 9
Продолжение таблицы
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
B C A B C A B C A B B C C A B B A
20 25 21 22 26 21 20 26 23 22 18 26 24 23 18 16 19
11 12 14 11 14 11 11 13 12 13 8 15 13 13 10 7 10
Окончание таблицы
50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
C A C B C A B C A A B C C A B A B
25 21 27 22 26 23 20 25 21 22 19 25 24 23 18 22 19
15 11 16 12 14 12 10 14 11 13 7 14 12 11 9 10 8
Контрольные вопросы
1. Каковы условия применимости метода ДП?
2. Чем определяется размерность вектора состояний?
3. Каков смысл функции f6?
4. В чем заключается оптимальное решение при t0=2?
5. Можно ли воспользоваться полученным решением, если из планового периода исключается последний год?
6. Можно ли воспользоваться полученной таблицей, если в 1-й год планового периода сделана замена станка?
7. Чему равна прибыль за первый год планового периода при t0=2 и N=8?
8. Чему равна прибыль за последний год планового периода при t0=2 и N=8?
9. Как получить решение для периода планирования с 01.01.2019 по 31.12.2027 и t0=3?
10. Как определить прибыль за один промежуточный год в конкретном оптимальном решении?
|