- •Н.Г. Лядина, е.А. Ермакова, л.В. Уразбахтина
- •Математические методы в экономике апк
- •Нелинейное и выпуклое программирование
- •Учебное пособие
- •Содержание
- •Введение
- •Нелинейное программирование Постановка и особенности задач нелинейного программирования
- •4. Точки, соответствующие оптимальному решению, могут находиться как на границе, так и внутри области допустимых решений.
- •5. Целевая функция может иметь несколько локальных экстремумов, из которых затем находят точку глобального оптимума.
- •2. Область допустимых решений может иметь несколько оптимальных решений, находящихся в отличие от линейного программирования не на отрезке. Пример на рисунке 1.
- •3. Область допустимых решений может состоять из нескольких частей.
- •Контрольные вопросы
- •Экстремум функции1
- •Нахождение безусловных экстремумов непрерывных дифференцируемых функций
- •Контрольные вопросы
- •Индивидуальные задания 1
- •Нахождение условных экстремумов. Метод множителей Лагранжа5
- •Б) Алгоритм метода множителей Лагранжа
- •Контрольные вопросы
- •Выпуклое программирование
- •Свойства выпуклых и гладких функций
- •Классификация задач выпуклого программирования
- •Экономические показатели производства культур
- •Формы записи задачи выпуклого программирования
- •Градиент и производная по направлению
- •Алгоритм решения специальной задачи выпуклого программирования. Метод Франка-Вульфа 10
- •Индивидуальные задания 3
- •Методы поиска – методы решения задач выпуклого программирования Метод последовательного изменения аргументов (координат)
- •Индивидуальные задания 4
- •Индивидуальные задания 5
- •Градиентные методы Метод наискорейшего подъема (для самостоятельного изучения)
- •Метод наискорейшего спуска
- •Различные алгоритмы градиентного метода (для самостоятельного изучения)
- •Индивидуальные задания 6
- •Индивидуальные задания 7
- •Алгоритм нелокального случайного поиска на минимум целевой функции
- •Индивидуальные задания 8
- •Особенности метода локального случайного поиска
- •Индивидуальные задания 9
- •Метод штрафных функций
- •Индивидуальные задания 10
- •Квадратичное программирование (кп) Графический метод
- •Контрольные вопросы
- •Индивидуальные задания 11
- •Квадратичный симплекс-метод
- •Индивидуальные задания 12
- •Контрольные вопросы и задания
- •Тестовые задания Тесты - выпуклое программирование
- •Тесты - квадратичное программирование
- •Рекомендуемая литература
- •Словарь терминов
- •Приложение
- •Индивидуальные задания 1 - 30
- •127550, Москва, ул. Тимирязевская, 44
Тесты - квадратичное программирование
1. Какая задача называется задачей квадратичного программирования?
– задача, имеющая квадратичную целевую функцию (целевая функция содержит переменные во второй степени) и систему ограничений – квадратичные выражения;
– задача, имеющая квадратичную целевую функцию (целевая функция содержит переменные во второй степени), а система ограничений - линейные выражения;
– задача, имеющая квадратичную целевую функцию (целевая функция содержит переменные во второй степени), а система ограничений - нелинейные выражения.
2. Какие задачи квадратичного программирования удобнее всего решать графическим методом?
– имеющие n переменных;
– имеющие 3 переменные;
– имеющие 2 переменные.
3. Что представляет область допустимых решений (ОДР) задач квадратичного программирования?
– выпуклый многоугольник, либо выпуклая неограниченная область с конечным числом вершин;
– только выпуклый многоугольник;
– только выпуклая неограниченная область с конечным числом вершин.
4*. Что представляет линия уровня целевой квадратичной функции?
1 – прямую;
2 – кривую n порядка;
3 – кривую 3 порядка;
4 – кривую 2 порядка.
5. Какие перечисленные кривые относятся к целевой квадратичной функции?
1 – концентрические окружности;
2 – подобные эллипсы;
3 – подобные параболы;
4 – окружность, эллипс, гипербола, парабола.
6. Если в задаче квадратичного программирования Z(X1,X2) = =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11=C22>0, то к какому виду приводим целевую функцию?
1 – Z(X1,X2)= C11(X1 -a)2 -C22 (X2-b)2+C0;
2 – Z(X1,X2)= C11(X1 -a)2 +C22 (X2-b)2+C0;
3 – Z(X1,X2)= C11(X1 -a)2 +C22 (X2-b)2.
7. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11=C22<0, то к какому виду приводим целевую функцию?
1 – Z(X1,X2)= C11(X1 -a)2 +C22 (X2-b)2+C0;
2 – Z(X1,X2)= C11(X1 -a)2 -C22 (X2-b)2+C0;
3 – Z(X1,X2)= C11(X1 -a)2 +C22 (X2-b)2.
8. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11 не равно C22 и оба положительные; C11·C22>0, то к какому виду приводим целевую функцию?
1 – Z(X1,X2)= C11(X1 -a)2 -C22 (X2-b)2+C0;
2 – Z(X1,X2)= C11(X1 -a)2 +C22 (X2-b)2;
3 – Z(X1,X2)= C11(X1 -a)2 +C22 (X2-b)2 +C0.
9. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11 не равно C22 и оба отрицательные; C11·C22 >0, то к какому виду приводим целевую функцию?
1 – Z(X1,X2)= C11(X1 -a)2 -C22 (X2-b)2;
2 – Z(X1,X2)= C11(X1 -a)2 +C22 (X2-b)2+C0;
3 – Z(X1,X2)= C11(X1 -a)2 +C22 (X2-b)2.
10. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2.≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11 не равно C22 , а C11·C22 <0, то к какому виду приводим целевую функцию?
1 – Z(X1,X2)= C11(X1 -a)2 -C22 (X2-b)2+C0;
2 – Z(X1,X2)= C11(X1 -a)2 +C22 (X2-b)2+C0;
3 – Z(X1,X2)= C11(X1 -a)2 +C22 (X2-b)2.
11. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11·C22 =0, причём одновременно C11 и C22 равняться нулю не могут:
C22 =0 , C2 не равно нулю, то к какому виду приводим целевую функцию?
1 – Z(X1,X2)= C11(X1 -a)2 -C22 (X2-b)2+C0;
2 – Z(X1,X2)= C11(X1 -a)2 +C22 (X2-b)2+C0;
3 – Z(X1,X2)= aX1 2 +bX1+c - X2.
12. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11·C22 =0, причём одновременно C11 и C22 равняться нулю не могут:
C 11 =0 , C1 не равно нулю, то к какому виду приводим целевую функцию?
1 – Z(X1,X2)= aX2 2 +bX1+c - X1;
2 – Z(X1,X2)= C11(X1 -a)2 -C22 (X2-b)2+C0;
3 – Z(X1,X2)= C11(X1 -a)2 +C22 (X2-b)2+C0.
13. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11·C22 =0, причём одновременно C11 и C22 равняться нулю не могут:
C2= C22 =0, то к какому виду приводим целевую функцию Z(X1,X2)= C11X12 +C1X1+C0 ?
1 – Z(X1,X2)= aX2 2 +bX1+c - X1;
2 – Z(X1,X2)= aX1 2 +bX1+c;
3 – Z(X1,X2)= aX2 2 +bX2+c.
14. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11·C22 =0, причём одновременно C11 и C22 равняться нулю не могут:
C1=C11=0 ,то к какому виду приводим целевую функцию Z(X1,X2)= C22X22 +C2X2 +C0 ?
1 – Z(X1,X2)= aX2 2 +bX1+c - X1;
2 – Z(X1,X2)= aX1 2 +bX1+c;
3 – Z(X1,X2)= aX2 2 +bX2+c.
15. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2.≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11=C22>0, то в какой точке находится центр или вершина целевой функции?
1 – O`(a,b);
2 – O`(C11,C22);
3 – O`(-C11,-C22).
16. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2.≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11=C22<0, то в какой точке находится центр или вершина целевой функции?
1 – O`(C11,C22);
2 – O`(a,b);
3 – O`(-C11,-C22).
17. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2.≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11 не равно C22 и оба положительные; C11·C22>0, то в какой точке находится центр или вершина целевой функции?
1 – O`(C11,C22);
2 – O`(-C11,-C22);
3 – O`(a,b).
18. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2.≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11 не равно C22 и оба отрицательные; C11·C22 >0, то в какой точке находится центр или вершина целевой функции?
1 – O`(C11,C22);
2 – O`(a,b);
3 – O`(-C11,-C22).
19. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11 не равно C22 , а C11·C22 <0, то в какой точке находится центр или вершина целевой функции?
1 – O`(a,b);
2 – O`(C11,C22);.
3 – O`(-C11,-C22).
20. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11·C22 =0, причём одновременно C11 и C22 равняться нулю не могут:
C22 =0 , C2 не равно нулю, то в какой точке находится центр или вершина целевой функции?
1 – (-b/2a; X2);
2 – (X1;-b/2a);
3 – (a,b).
21. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11·C22 =0, причём одновременно C11 и C22 равняться нулю не могут:
C 11 =0 , C1 не равно нулю, то в какой точке находится центр или вершина целевой функции?
1 – (-b/2a; X2);
2 – (X1;-b/2a);
3 – (a,b).
22. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11·C22 =0, причём одновременно C11 и C22 равняться нулю не могут:
C2= C22 =0, то как изображается целевая функция Z(X1,X2)= C11X12 +C1X1+C0 ?
1 – подобные параболы, ось симметрии которых параллельна оси ОX2, а вершина имеет координаты (-b/2a; X2);
2 – подобные параболы, ось симметрии которых параллельна оси ОX1, а вершина имеет координаты (X1;-b/2a);
3 – прямые, параллельные оси ОX2 , если b2-4ac >0 и мнимое место точек, если b2-4ac <0;
4 – прямые, параллельные оси ОX1 , если b2-4ac >0 и мнимое место точек, если b2-4ac <0.
23. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11·C22 =0, причём одновременно C11 и C22 равняться нулю не могут:
C1=C11=0, то как изображается целевая функция Z(X1,X2)= C11X12 +C1X1+C0 ?
1 – подобные параболы, ось симметрии которых параллельна оси ОX2, а вершина имеет координаты (-b/2a; X2);
2 – подобные параболы, ось симметрии которых параллельна оси ОX1, а вершина имеет координаты (X1;-b/2a);
3 – прямые, параллельные оси ОX2 , если b2-4ac >0 и мнимое место точек, если b2-4ac <0;
4 – прямые, параллельные оси ОX1 , если b2-4ac >0 и мнимое место точек, если b2-4ac <0.
24. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11·C22 =0, причём одновременно C11 и C22 равняться нулю не могут:
C22 =0 , C2 не равно нулю, то как изображается целевая функция Z(X1,X2)= =C22X12 +C2X2+C0 ?
1 – подобные параболы, ось симметрии которых параллельна оси ОX2, а вершина имеет координаты (–b/2a; X2);
2 – подобные параболы, ось симметрии которых параллельна оси ОX1, а вершина имеет координаты (X1;–b/2a);
3 – прямые, параллельные оси ОX2 , если b2–4ac >0 и мнимое место точек, если b2–4ac <0;
4 – прямые, параллельные оси ОX1 , если b2-4ac >0 и мнимое место точек, если b2–4ac <0.
25. Если в задаче квадратичного программирования Z(X1,X2) = =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11·C22 =0, причём одновременно C11 и C22 равняться нулю не могут:
C22 =0 , C2 не равно нулю, то как изображается целевая функция Z(X1,X2)= =aX1 2 +bX1+c - X2?
1 – подобные параболы, ось симметрии которых параллельна оси ОX2, а вершина имеет координаты (-b/2a; X2);
2 – подобные параболы, ось симметрии которых параллельна оси ОX1, а вершина имеет координаты (X1;-b/2a);
3 – прямые, параллельные оси ОX2 , если b2-4ac >0 и мнимое место точек, если b2-4ac <0;
4 – прямые, параллельные оси ОX1 , если b2-4ac >0 и мнимое место точек, если b2-4ac <0.
26. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11·C22 =0, причём одновременно C11 и C22 равняться нулю не могут:
C 11 =0 , C1 не равно нулю, то как изображается целевая функция Z(X1,X2)= aX2 2 +bX2+c - X1.
1 – подобные параболы, ось симметрии которых параллельна оси ОX2, а вершина имеет координаты (-b/2a; X2);
2 – подобные параболы, ось симметрии которых параллельна оси ОX1, а вершина имеет координаты (X1;-b/2a);
3 – прямые, параллельные оси ОX2 , если b2-4ac >0 и мнимое место точек, если b2-4ac <0;
4 – прямые, параллельные оси ОX1 , если b2-4ac >0 и мнимое место точек, если b2-4ac <0.
27. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2.≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11=C22>0, то к какой из перечисленных кривых относится целевая квадратичная функция?
1 – концентрические окружности;
2 – подобные эллипсы;
3 – подобные гиперболы;
4 – подобные параболы;
5 – концентрические мнимые окружности;
6 – подобные мнимые эллипсы.
28. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2.≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11=C22<0, то к какой из перечисленных кривых относится целевая квадратичная функция?
1 – концентрические окружности;
2 – подобные эллипсы;
3 – подобные гиперболы;
4 – подобные параболы;
5 – концентрические мнимые окружности;
6 – подобные мнимые эллипсы.
29. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2.≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11 не равно C22 и оба положительные; C11·C22>0, то к какой из перечисленных кривых относится целевая квадратичная функция?
1 – концентрические окружности;
2 – подобные эллипсы;
3 – подобные гиперболы;
4 – подобные параболы;
5 – концентрические мнимые окружности;
6 – подобные мнимые эллипсы;
30. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2.≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11 не равно C22 и оба отрицательные; C11·C22 >0, то к какой из перечисленных кривых относится целевая квадратичная функция?
1 – концентрические окружности;
2 – подобные эллипсы;
3 – подобные гиперболы;
4 – подобные параболы;
5 – концентрические мнимые окружности;
6 – подобные мнимые эллипсы.
31. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2.≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11 не равно C22 , а C11·C22 <0, то к какой из перечисленных кривых относится целевая квадратичная функция?
1 –концентрические окружности;
2 – подобные эллипсы;
3 – подобные гиперболы;
4 – подобные параболы;
5 – концентрические мнимые окружности;
6 – подобные мнимые эллипсы.
32. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2.≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11 не равно C22 и оба положительные; C11·C22>0, то чему равно отношение полуосей целевой квадратичной функции?
1 – корню квадратному из отношения C22 к C11;
2 – корню квадратному из отношения C11 к C22;
3 – корню квадратному из модуля отношения C22 к C11;
4 – корню квадратному из модуля отношения C11 к C22 .
33. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2.≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11 не равно C22 и оба отрицательные; C11·C22 >0, то чему равно отношение полуосей целевой квадратичной функции?
1 – корню квадратному из модуля отношения C22 к C11;
2 – корню квадратному из отношения C11 к C22;
3 – корню квадратному из отношения C22 к C11;
4 – корню квадратному из модуля отношения C11 к C22 .
34. Если в задаче квадратичного программирования Z(X1,X2)= =C11X12+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2.≤aI 0 , i=1÷m,
X1≥0, X2≥0,
C11 не равно C22 , а C11·C22 <0, то какой вид имеют уравнения асимптот?
1 – X2 = b + K (X1 -a) и X2 =b -K (X1 -a). Коэффициент K равен корню квадратному из отношения C11 к C22;
2 – X2 = b + K (X1 -a) и X2 =b -K (X1 -a). Коэффициент K равен корню квадратному из модуля отношения C11 к C22;
3 – X1 = b + K (X2 -a) и X1 =b -K (X2 -a). Коэффициент K равен корню квадратному из модуля отношения C11 к C22;
4 – X1= b + K (X2 -a) и X1 =b -K (X2 -a). Коэффициент K равен корню квадратному из отношения C11 к C22.