Контрольная работа по предмету Системное и прикладное программирование на тему: 5 задач по исследованию операций. Вариант 24

ЗАДАНИЕ 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. Как определить прибыль за один промежуточный год в конкретном оптимальном решении?