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

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

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

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

3. Задача 2.

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
3
Задача 2.
Укажите наименьшее целое значение А, при котором
выражение
(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
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
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
http://kpolyakov.spb.ru

6. Задача 2.

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
6
Задача 2.
Укажите наименьшее целое значение А, при котором
выражение
(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
http://kpolyakov.spb.ru

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

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
7
Задача 2. Аналитическое решение
(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
в запретной
зоне
x < 30
x = xmax
http://kpolyakov.spb.ru

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

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
8
Задача 2. Графическое решение
(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
http://kpolyakov.spb.ru

9. Задача 3.

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
9
Задача 3.
Укажите наименьшее целое значение А, при котором
выражение
(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
http://kpolyakov.spb.ru

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

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
10
Задача 3. Аналитическое решение
(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
http://kpolyakov.spb.ru

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

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
11
Задача 3. Графическое решение
НЕ прямоугольник
(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
x
http://kpolyakov.spb.ru

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

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
12
Задача 3. Графическое решение
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
2x 117
1 < –2·58 + A
117 < A
x – целое!
xmax = 58
Amax = 118
http://kpolyakov.spb.ru

13. Задача 4.

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

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

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
14
Задача 4. Аналитическое решение
(x > 0) (x <19) ∨ (x 5y) (y > 0)
xmax = 18
y max при xmax
y x/5
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
http://kpolyakov.spb.ru

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

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
15
Задача 4. Графическое решение
треугольник
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
Amin = 28
http://kpolyakov.spb.ru

16. Задача 5.

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

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

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
17
Задача 5. Аналитическое решение
(x > 0) (y – x = 5) (y > 0)
(A < 2x3 + y)
или (A < y2 + 16)
A < min(2x3 + y)
A < min(y2 + 16)
прямая
y=x+5
min(2x3 + y)
(x > 0) (y – x = 5)
при
A < max
(y > 0)
min(y2 + 16)
возрастающие при
x > 0, y > 0
луч
y=x+5
(xmin, ymin) на границе
x=1y=6
min(2·13 + 6)
y = 1 x = –4 A < max min(62 + 16) = max(8, 52)
Amax = 51
К.Ю. Поляков, 2018
http://kpolyakov.spb.ru

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

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
18
Задача 5. Графическое решение
y
y–x=5
20
15
y= x+5
(x > 0) (y > 0)
10
5
0
Для всех x на луче
нужно обеспечить
(1, 6)
1
5
10
x
A < min(2x3 + y)
A < min(2x3 + x + 5)
A < 2·13 + 1 + 5
A<8
К.Ю. Поляков, 2018
(A < 2x3 + y)
или
(A < y2 + 16)
A < min(y2 + 16)
A < 62 + 16
A < 52
Amax = 51
http://kpolyakov.spb.ru

19. Задача 6.

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
19
Задача 6.
(С.С. Поляков) Укажите наибольшее целое значение А,
при котором выражение
(y – x2 – 80) ∨ (A < 13x – 14) ∨ (A < y2 + 15)
истинно для любых целых положительных значений x и y.
не зависит от A
(A < 13x – 14) ∨ (A < y2 + 15) ∨ (y – x2 – 80)
истинно
ложно
(x > 0) (y – x2 = – 80) (y > 0)
К.Ю. Поляков, 2018
http://kpolyakov.spb.ru

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

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
20
Задача 6. Аналитическое решение
(x > 0) (y – x2 = – 80) (y > 0)
(A < 13x – 14)
или (A < y2 + 15)
A < min(13x – 14) парабола
2 – 80
y
=
x
A < min(y2 + 15)
2 = – 80)
min(13x – 14)
(x
>
0)
(y

x
при
A < max
2
(y > 0)
min(y + 15)
возрастающие при
x > 0, y > 0
y = x2 – 80
(xmin, ymin) на границе
x = 1 y = – 79
min(13·9 – 14)
y = 1 x = 9 A < max min(12 + 15) = max(103, 16)
Amax = 102
К.Ю. Поляков, 2018
http://kpolyakov.spb.ru

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

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
21
Задача 6. Графическое решение
y
4
y = x2 – 80
(x > 0) (y > 0)
3
2
(1, 9)
1
0
1
5
(A < 13x – 14)
или
(A < y2 +15)
x
10
A < min(13x – 14)
A < 13·9 – 14
A < 103
Для всех x на «луче»
нужно обеспечить
A < min(y2 + 15)
A < 12 + 15
или
A < 16
Amax = 102
К.Ю. Поляков, 2018
http://kpolyakov.spb.ru

22. Задача 7.

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
22
Задача 7.
Укажите наименьшее целое значение А, при котором
выражение
(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
http://kpolyakov.spb.ru

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

Линейное (и нелинейное) программирование в задачах ЕГЭ по информатике
23
Задача 7. Графо-аналическое решение
y
(y 20sin(x/5) + 10)
y = 20sin(x/5) + 10
∨ (y – x2/4 +30)
y = (x – A)2 + 10
(x > 0) (y > 0)
40
30
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
Amin = 11
http://kpolyakov.spb.ru

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

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