Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике

1. Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике

К.Ю. Поляков
Линейное (и нелинейное)
программирование
в задачах ЕГЭ по
информатике
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru

2. Постановка задачи

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
2
Постановка задачи
Укажите наименьшее целое значение А, при котором
выражение
(y + 2x < A) ∨ (x > 20) ∨ (y > 30)
истинно для любых целых положительных значений x и y.
Укажите наименьшее целое значение А, при котором
выражение
(y + 2x < A) ∨ (3y +2x > 120) ∨ (3y – x > 30)
истинно для любых целых положительных значений x и y.
Укажите наибольшее целое значение А, при котором
выражение
(y – x 5) ∨ (A < 2x3 + y) ∨ (A < y2 + 16)
истинно для любых целых положительных значений x и y.
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru

3. Задача 1.

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
3
Задача 1.
Укажите наименьшее целое значение А, при котором
выражение
(y + 2x < A) ∨ (x > 20) ∨ (y > 30)
истинно для любых целых положительных значений x и y.
не зависит от A
(y + 2x < A) ∨ (x > 20) ∨ (y > 30)
истинно
ложно
(x > 0) (x 20) (y 30) (y > 0)
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru

4. Задача 1. Аналитическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
4
Задача 1. Аналитическое решение
(x > 0) (x 20) (y 30) (y > 0)
(y + 2x < A)
A > y + 2x для (x > 0) (x 20) (y 30) (y > 0)
A > max(y + 2x)
для (x > 0) (x 20) (y 30) (y > 0)
только x
только y
максимум линейной функции при линейных
ограничениях
!
Задача линейного программирования!
A > max(y + 2x) = max(y) + 2·max(x)
A > 30 + 2·20 = 70
К.Ю. Поляков, 2018-2019
Amin = 71
http://kpolyakov.spb.ru

5. Задача 1. Графическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
5
Задача 1. Графическое решение
(x > 0) (x 20) (y 30) (y > 0)
прямоугольник
y
y
y = –2x + A
30
20
x
(y + 2x < A)
(y < –2x + A)
y = –2x + A
30
точка
касания
20
x
30 < –2·20 + A
70 < A
Amin = 71
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru

6. Задача 1a. Графическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
6
Задача 1a. Графическое решение
Найти: Amax
(x > 0) (x 20) (y 30) (y > 0)
прямоугольник
y
30
y
30
y = –2x + A
точка
касания
y = –2x + A
20
x
(y + 2x > A)
(y > –2x + A)
20
x
1 > –2·1 + A
3>A
Amax = 2
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru

7. Задача 1б, 1в. Графическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
7
Задача 1б, 1в. Графическое решение
Найти: Amin
(y – 2x < A) (y < 2x + A)
y
Найти: Amax
(y – 2x > A)
y
y = 2x + A
(y > 2x + A)
y = 2x + A
30
30
точка
касания
20
точка
касания
x
30 < 2·1 + A
28 < A
Amin = 29
К.Ю. Поляков, 2018-2019
20
x
1 > 2·20 + A
– 39 > A
Amax = – 40
http://kpolyakov.spb.ru

8. Задача 2.

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
8
Задача 2.
Укажите наименьшее целое значение А, при котором
выражение
(5x + 3y 60) ∨ ((A > x) (A > y))
истинно для любых целых неотрицательных
значений x и y.
не зависит от A
((A > x) (A > y)) ∨ (5x + 3y 60)
истинно
ложно
(x 0) (5x + 3y = 60) (y 0)
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru

9. Задача 2. Аналитическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
9
Задача 2. Аналитическое решение
(x 0) (5x + 3y = 60) (y 0)
(A > x)
(A > y)
A > max(x) при (x 0) (5x + 3y = 60) (y 0)
A > max(y) при (x 0) (5x + 3y = 60) (y 0)
A > max(x) при (5x = 60) xmax = 12
A > max(y) при (3y = 60) ymax = 20
A > max(x) = 12
A > max(y) = 20
К.Ю. Поляков, 2018-2019
Amin = 21
http://kpolyakov.spb.ru

10. Задача 2. Графическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
10
Задача 2. Графическое решение
(x 0) (5x + 3y = 60) (y 0)
отрезок
y
A
20
A > max(x) = 12
A > max(y) = 20
5x + 3y = 60
12
К.Ю. Поляков, 2018-2019
A
(A > x)
квадрат
(A > y)
Amin = 21
x
http://kpolyakov.spb.ru

11. Задача 3.

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
11
Задача 3.
Укажите наименьшее целое значение А, при котором
выражение
(5y < (x – 30) 2 + A) ∨ (x > 20) ∨ (y > 30)
истинно для любых целых положительных значений x и y.
не зависит от A
(5y < (x – 30)2 + A) ∨ (x > 20) ∨ (y > 30)
истинно
ложно
(x > 0) (x 20) (y 30) (y > 0)
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru

12. Задача 3. Аналитическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
12
Задача 3. Аналитическое решение
(x > 0) (x 20) (y 30) (y > 0)
(5y < (x – 30)2 + A)
A > 5y – (x – 30)2
A > max(5y – (x – 30)2)
для (x > 0) (x 20) (y 30) (y > 0)
максимум НЕлинейной функции при линейных
ограничениях
A > max(5y – (x – 30)2) = 5∙max(y) – min(x – 30)2
A > 5·30 – (20 – 30)2 = 50
Amin = 51
К.Ю. Поляков, 2018-2019
в запретной
зоне
x < 30
x = xmax
http://kpolyakov.spb.ru

13. Задача 3. Графическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
13
Задача 3. Графическое решение
(x > 0) (x 20) (y 30) (y > 0)
(5y < (x – 30)2 + A)
y < (x – 30)2/5 + A/5
y
y = (x–30)2/5+A/5
30
20 30
x
y
y = (x–30)2/5+A/5
30
точка
касания
20 30
x
150 < (20 – 30)2 + A
50 < A
Amin = 51
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru

14. Задача 4.

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
14
Задача 4.
Укажите наименьшее целое значение А, при котором
выражение
(y + 2x < A) ∨ (3y +2x > 120) ∨ (3y – x > 30)
истинно для любых целых положительных значений x и y.
не зависит от A
(y + 2x < A) ∨ (3y +2x > 120) ∨ (3y – x > 30)
истинно
ложно
(x > 0) (3y +2x 120) (3y – x 30) (y > 0)
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru

15. Задача 4. Аналитическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
15
Задача 4. Аналитическое решение
(y + 2x < A) для
(x > 0) (3y +2x 120) (3y – x 30) (y > 0)
A > max(y + 2x) для
(x > 0) (3y +2x 120) (3y – x 30) (y > 0)
!
Задача линейного программирования!
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru

16. Задача 4. Графическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
16
Задача 4. Графическое решение
НЕ прямоугольник
(x > 0) (3y +2x 120) (3y – x 30) (y > 0)
(y –2x/3 + 40) (y x/3 + 10)
круче!
y
40
y = – 2x/3 + 40
30
y = –2x + A
y = x/3 + 10
20
(y + 2x < A)
(y < –2x + A)
точка касания с целыми
координатами!
10
10 20 30 40 50 60
К.Ю. Поляков, 2018-2019
x
http://kpolyakov.spb.ru

17. Задача 4. Графическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
17
Задача 4. Графическое решение
y
40
y = – 2x/3 + 40
y = –2x + A
y = x/3 + 10
30
20
точка касания с целыми
координатами!
10
10 20 30 40 50 60
x
Найти xmax: y = 1, y –2x/3 + 40
y = 1 –2x/3 + 40
(y < –2x + A)
К.Ю. Поляков, 2018-2019
2x 117
1 < –2·58 + A
117 < A
x – целое!
xmax = 58
Amax = 118
http://kpolyakov.spb.ru

18. Задача 5.

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
18
Задача 5.
Укажите наименьшее целое значение А, при котором
выражение
(x 19) ∨ (x < 5y) ∨ (xy < 2A)
истинно для любых целых положительных значений x и y.
не зависит от A
(xy < 2A) ∨ (x 19) ∨ (x < 5y)
истинно
ложно
(x > 0) (x <19) ∨ (x 5y) (y > 0)
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru

19. Задача 5. Аналитическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
19
Задача 5. Аналитическое решение
(x > 0) (x <19) ∨ (x 5y) (y > 0)
y x/5
xmax = 18
y max при xmax
ymax = [ xmax / 5 ]
ymax = [ 18 / 5 ] = 3
A > xy/2
целая
часть!
A > max(xy)/2
A > xmax·ymax/2 = 18·3/2 = 27
Amin = 28
(xy < 2A)
!
Нелинейная
функция!
Легко решить, если x и y max
1) независимо или …
2) одновременно
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru

20. Задача 5. Графическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
20
Задача 5. Графическое решение
треугольник
y
(x > 0) (x <19) ∨ (x 5y) (y > 0)
(xy < 2A)
4
y = 2A/x
3
2
(y < 2A/x)
y=x/5
1
x = 18
y=1
5
10
при x = 18: y x/5
точка
касания!
15
20
x
ymax = 3
2A > max(xy) = 3·18 = 54
A > 27
К.Ю. Поляков, 2018-2019
Amin = 28
http://kpolyakov.spb.ru

21. Задача 6.

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
21
Задача 6.
Укажите наибольшее целое значение А, при котором
выражение
(y +3x 20) ∨ (A < 2x + 16) ∨ (A < 3y)
истинно для любых целых положительных значений x и y.
не зависит от A
(A < 2x + 16) ∨ (A < 3y) ∨ (y + 3x 20)
истинно
ложно
(x > 0) (y + 3x = 20) (y > 0)
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru

22. Задача 6. Графическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
22
Задача 6. Графическое решение
y + 3x = 20
y = – 3x + 20 Для всех x на отрезке
нужно обеспечить
(x > 0) (y > 0)
(A < 2x + 16) или (A < 3y)
y
x = (A – 16)/2
const
20
(x > (A – 16)/2)
или (y > A/3)
15
10
y = A/3
5
0
1
x
5
10
y + 3x = 20
К.Ю. Поляков, 2018-2019
const
!
!
Весь отрезок в
красную зону!
Не обязательно
одним условием!
http://kpolyakov.spb.ru

23. Задача 6. Графическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
23
Задача 6. Графическое решение
y = – 3x + 20
A = 2x + 16
y
20
Критическая точка:
2x + 16 = 3y
15
A = 3y
10
5
0
1
5
10
2x + 16 = 3y
y = – 3x + 20
3y = – 9x + 60
2x + 16 = – 9x + 60
11x = 44
x = 4, y = 8
(A < 2x + 16) или (A < 3y)
A
<
3·8
=
24
x
Amax = 23
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru

24. Задача 7.

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
24
Задача 7.
Укажите наименьшее целое значение А, при котором
выражение
(y +3x 19) ∨ (A > 2x + 16) (A > 3y)
истинно для любых целых положительных значений x и y.
не зависит от A
(A > 2x + 16) (A > 3y) ∨ (y + 3x 19)
истинно
ложно
(x > 0) (y + 3x = 19) (y > 0)
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru

25. Задача 7. Аналитическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
25
Задача 7. Аналитическое решение
(x > 0) (y + 3x = 19) (y > 0)
(A > 2x + 16)
и (A > 3y)
A > max(2x + 16)
A > max(3y)
прямая
y = – 3x + 19
max(2x + 16)
при (x > 0) (y + 3x = 19)
A > max
(y > 0)
max(3y)
ymax при x = 1
возрастающие при
x > 0, y > 0
отрезок
ymax = – 3·1+ 19 = 16
xmax при y = 1
xmax= (19 – 1) / 3 = 6
max(2·6 + 16)
A > max
= max(28, 48)
max(3·16)
К.Ю. Поляков, 2018-2019
Amin = 49
http://kpolyakov.spb.ru

26. Задача 7. Графическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
26
Задача 7. Графическое решение
y + 3x = 19
y = – 3x + 19 Для всех x на отрезке
нужно обеспечить
(x > 0) (y > 0)
(A > 2x + 16) и (A > 3y)
y
x = (A – 16)/2
const
20
(x < (A – 16)/2)
и (y < A/3)
15
10
y = A/3
5
0
1
x
5
10
y + 3x = 19
К.Ю. Поляков, 2018-2019
const
!
!
Нужно перекрыть
весь отрезок!
Обязательно выполнить
оба условия!
http://kpolyakov.spb.ru

27. Задача 7. Графическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
27
Задача 7. Графическое решение
y = – 3x + 19
x = (A – 16)/2
x = (A – 16)/2
y = A/3
y
20
15
y = A/3
0
1
К.Ю. Поляков, 2018-2019
5
10
x=1
y = – 3·1+ 19 = 16
A > 3y = 48
y=1
x = (19 – 1) / 3 = 6
A > 2x + 16 = 28
10
5
Концы отрезка:
!
x
Одновременно!
Amin = 49
http://kpolyakov.spb.ru

28. Задача 8.

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
28
Задача 8.
Укажите наименьшее целое значение А, при котором
выражение
(y – 20sin(x/5) >10) ∨ (4y + x2 > 120)
∨ (y – x2 – A2 < 10 – 2Ax )
истинно для любых целых положительных значений x и y.
не зависит от A
(y – x2 – A2 < 10 – 2Ax ) ∨ (y – 20sin(x/5) >10)
∨ (4y + x2 > 120)
истинно
ложно
(y – 20sin(x/5) 10) (4y + x2 120)
(x > 0) (y > 0)
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru

29. Задача 8. Графо-аналическое решение

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
29
Задача 8. Графо-аналическое решение
y
40
30
(y 20sin(x/5) + 10)
y = 20sin(x/5) + 10
∨ (y – x2/4 +30)
y = (x – A)2 + 10
(x > 0) (y > 0)
20
y – x2 – A2 < 10 – 2Ax
10
y – x2/4 +30
0
y < (x – A)2 + 10
1
5
10
15 x
Найти наименьшее значение A, при котором решается
уравнение (x – A)2 + 10 = – x2/4 +30
5x2/4 – 2Ax + A2 – 20 = 0
при
касании!
D = 4A2 – 5(A2 – 20) = 0
A = 10
К.Ю. Поляков, 2018-2019
Amin = 11
http://kpolyakov.spb.ru

30. Конец фильма

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
30
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
К.Ю. Поляков, 2018-2019
http://kpolyakov.spb.ru