Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
Постановка задачи
Задача 1.
Задача 1. Аналитическое решение
Задача 1. Графическое решение
Задача 1a. Графическое решение
Задача 1б, 1в. Графическое решение
Задача 2.
Задача 2. Аналитическое решение
Задача 2. Графическое решение
Задача 3.
Задача 3. Аналитическое решение
Задача 3. Графическое решение
Задача 4.
Задача 4. Аналитическое решение
Задача 4. Графическое решение
Задача 4. Графическое решение
Задача 5.
Задача 5. Аналитическое решение
Задача 5. Графическое решение
Задача 6.
Задача 6. Графическое решение
Задача 6. Графическое решение
Задача 7.
Задача 7. Аналитическое решение
Задача 7. Графическое решение
Задача 7. Графическое решение
Задача 8.
Задача 8. Графо-аналическое решение
Конец фильма
1.37M
Категория: ИнформатикаИнформатика

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

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
English     Русский Правила