Случай. C11 не равно C22 , а C11·C22 < 0
Целевую функцию Z(X1,X2)= C11X12 +C22X22+C1X1+C2X2 +C0 приводим к виду Z(X1,X2)= C11(X1 -a)2 +C22 (X2-b)2+C0 . Линии уровня - подобные гиперболы с центром в точке O`(a,b). Асимптоты гипербол имеют вид: X2 - b = K (X1 -a) и X2 - b = -K (X1 -a). Коэффициент K равен корню квадратному из модуля отношения C11 к C22. Уравнения асимптот можно преобразовать к виду: X2 = b + K (X1 -a) и X2 =b - K (X1 -a).
4 случай. C11·C22 =0, причём одновременно C11 и C22 равняться нулю не могут. Линии уровня подобные параболы.
а) C22 =0 , C2 не равно нулю.
Целевую функцию Z(X1,X2)= C11X12 +C1X1+C2X2 +C0 приводим к виду Z(X1,X2)= aX1 2 +bX1+c - X2 . Линии уровня подобные параболы, ось симметрии которых параллельна оси ОX2 , а вершина имеет координаты (-b/2a; X2).
б) C 11 =0 , C1 не равно нулю.
Целевую функцию Z(X1,X2)= C22X22 +C2X2+ C1X1 +C0 приводим к виду Z(X1,X2)= aX2 2 +bX1+c - X1 . Линии уровня подобные параболы, ось симметрии которых параллельна оси ОX1 , а вершина имеет координаты (X1;-b/2a).
в) C2= C22 =0.
Целевую функцию Z(X1,X2)= C11X12 +C1X1+C0 приводим к виду Z(X1,X2)= aX1 2 +bX1+c. Линии уровня прямые, параллельные оси ОX2 , если b2-4ac >0 и мнимое место точек, если b2-4ac <0
г) C1=C11=0.
Целевую функцию Z(X1,X2)= C22X22 +C2X2 +C0 приводим к виду Z(X1,X2)= aX2 2 +bX2+c. Линии уровня прямые, параллельные оси ОX1 , если b2-4ac >0 и мнимое место точек, если b2-4ac <0.
Случай 1.
Пример 21.Найтиграфически максимум и минимум.
Решение.
1. Областью допустимых решений является четырехугольник ABCD (рис.10).
2. С12 = 0, С11 = С22 =1. Следовательно, линиями уровня целевой функции являются концентрические окружности. Найдем их центр. Для этого сведем данную квадратичную функцию к каноническому виду.
3. Центром концентрических окружностей является точка О1 (8;-2).
4. Минимальное значение целевой функции соответствует наименьшему радиусу и достигается в точке, в которой окружность в первый раз касается области допустимых решений, т.е. точке области допустимых решений, наименее удаленных от точки О1. Это точка C(3;1).
min Z(C) = (x1 -8)2 + (x2 +2)2 =(3-8)2 + (1+2)2 = 34.
Максимальное значение целевой функции соответствует наибольшему радиусу и достигается в точке, в которой окружность последний раз касается области допустимых решений, т.е. точке области допустимых решений наиболее удаленной от точки О1. Это точка В (0;4).
max Z(В) = (x1 -8)2 + (x2 +2)2 =(0-8)2 + (4+2)2 = 100.
Следовательно, min Z(3;1) =34, max Z(0;4) = 100.
|
Рис. 10. Целевая функция - концентрические окружности
Случай 2.
Если коэффициенты целевой функции С12 = 0, С11 ¹ С22, С11 · С22 > 0, то квадратичную целевую функцию можно свести к каноническому виду Z(X1,X2)= C11(X1 -a)2 +C22 (X2-b)2. В этом случае линиями уровня являются подобные эллипсы с центром в точке О1 (а, в) и отношением полуосей, равным 
.
Пример 21.Найти графически максимум и минимум.
Преобразуем целевую функцию Z:
Линии уровня – концентрические эллипсы с центром в точке с координатами (–1;1).
Решение.
1. Областью допустимых решений является четырехугольник ABCD (рис. 11).
2. С12 = 0, С11 ¹ С22, С11> 0, С22 > 0, С11 · С22 > 0. Следовательно, линиями уровня целевой функции являются подобные эллипсы. Найдем их центр, для этого сведем данную квадратичную функцию к каноническому виду:
3. Центром подобных эллипсов является точка О1(-1; 1). Отношение полуосей эллипсов равно 
.
4. Минимальное значение целевой функции достигается в точке Е (0;1), в которой эллипс касается области допустимых решение ABCD.
Максимальное значение целевой функции достигается в точке D(5; 0).
Рис. 11. Целевая функция – подобные эллипсы
Случай 3.
Если коэффициенты целевой функции С12 =0, С11·С22< 0, то квадратичную целевую функцию можно свести к каноническому виду:
Пусть С11> 0, С22 < 0. В этом случае линиями уровня являются подобные гиперболы с центром в точке О1 (а, в) и асимптотами 
или 
Пример 22.Найти графически максимум и минимум.
Решение.
1. Областью допустимых решений является четырехугольник ABCD (рис.12).
2. С12 =0, С11·С22 =16·(-9) = -144 < 0. Следовательно, линиями уровня целевой функции являются подобные гиперболы. Найдем их центр, для этого сведем данную квадратичную функцию к каноническому виду:
3. Центром подобных гипербол является точка О1( 
). Уравнение асимптот: 
4. Строим гиперболы:
Первый способ.
а) Положим const = 11, получим
Сделаем перенос начала координат в точку
О1 (1/4; -1). Пусть 
тогда 16х2 -9у2 =1 или
Вершинами гиперболы являются точки (-1/4; 0); (1/4; 0) в новой системе координат (ХО1У). Осью симметрии является ось О1Х.
б) Положим const = 154, получим
Разделим обе части уравнения на 144, получим 
.
Сделаем перенос начала координат в точку О1(1/4; -1). Пусть тогда 
Вершинами гиперболы являются точки (-3; 0) и (3; 0) в новой системе координат (ХО1 У). Осью симметрии являются ось О1Х.
в) Положим const = 9, получим 
или
Сделаем перенос начала координат в точку О1(1/4; -1). Пусть тогда -16х2 +9у2 =1 или
Вершины гиперболы – точки (0; -1/3); (0; 1/3) в новой системе координат (ХО1 У). Осью симметрии являются ось О1У.
г) Положим const = -134, получим 
или
Выполним сокращение, получим
Сделаем перенос начала координат в точку О1(1/4; -1). Пусть тогда 
Вершинами гиперболы являются точки (0; -4); (0; 4) в новой системе координат (ХО1 У). Осью симметрии являются ось О1У.
д) Положим const = 10, получим 
Сделаем перенос начала координат в точку О1(1/4; -1). Пусть тогда
16х2 – 9у2 = 0 или (4х – 3у) · (4х + 3у) = 0. Это уравнение распадается на два : (4х – 3у) = 0 и (4х + 3у) = 0. Откуда 
а это уравнения асимптот в новой системе координат (ХО1 У).
Второй способ.
Можно взять произвольную точку, подставить ее в целевую функцию, узнать значение Z и приближенно построить целевую функцию по отношению к асимптотам.
|
Рис.12. Целевая функция – подобные гиперболы
5. Минимальное значение целевой функции достигается в точке 
в которой гипербола касается области допустимых решений АBCD.
Максимальное значение целевой функции достигается в точке D(5; 0). 
Случай 4.
Если коэффициенты целевой функции С12 =0 и С11 · С22 = 0, причем одновременно С11 и С22 равняться нулю не могут, то квадратичную целевую функцию можно свести к каноническому виду: Z(X1,X2)= aX1 2 +bX1+c - X2 , если С2 ¹ 0, а С22 =0. В этом случае линиями уровня являются параболы, ось симметрии которых параллельна оси ОХ2.
Пример 24.Найти графически максимум и минимум задачи квадратичного программирования.
Z(x1, x2) = 
Решение.
1. Областью допустимых решений является четырехугольник ABCD (рис. 13).
2. С2 ¹ 0, С22 =0, С11 ¹ 0, следовательно, линиями уровня являются подобные параболы, ось симметрии которых параллельна оси ОХ2 .
3. Найдем каноническое уравнение параболы:
.
Положим const = 0, тогда 
то есть получим X2 =aX1 2 +bX1+c.
4. Найдем вершину параболы:
Х0 = 
или 
5. Сделаем перенос начала координат в точку О1 (Х0, У0), О1 (-1/3; 0).
6. В новых координатах (Х’О1У) уравнение параболы имеет вид у=ах2 или у= 
.
7. Положим const = - 9, тогда 
. 
.
|
, то есть получили X2 =aX1 2 +bX1+c.
Рис.13. Целевая функция – подобные параболы
8. Найдем вершину параболы:
.
9. Сделаем перенос начала координат в точку О2(х0, у0), О2 
.
10. В новых координатах (Х’О1У) уравнение параболы имеет вид у=ах2 или у= .
11. Минимальное значение целевой функции достигается в точке B(0;3). min Z = 9·02 +6·0 - 2·3 + 1 = - 5.
Максимальное значение целевой функции достигается в точке 
.
Замечание. Если в выражении 
коэффициент с12 ¹0, то кроме переноса начала координат, необходимо повернуть координатные оси на такой угол, чтобы исчез член с произведением переменных.
Контрольные вопросы
1. Какая функция называется выпуклой?
2. Какая функция называется гладкой?
3. Какая функция называется квадратичной?
4. Какая функция имеет локальный максимум, а какая - абсолютный?
5. В чем разница между локальным и абсолютным максимумом?
6. Какие методы поиска Вы знаете?
7. Какой вид линии уровня задач квадратичного программирования Вы знаете?
8. Всегда ли задача квадратичного программирования имеет решение?
Индивидуальные задания 11
Решить графическим методом, найдя максимум и минимум целевой функции, если задача имеет следующий вид:
Коэффициенты целевой функции и системы ограничений берутся из таблицы 8 в соответствии с номером варианта.
Таблица 8
Варианты индивидуальных заданий
| Варианты заданий | С11 | С22 | С1 | С2 | А11 | А12 | А10 | А21 | А22 | А20 |
| -10 | -2 | |||||||||
| -6 | -5 | |||||||||
| -8 | -3 | |||||||||
| -8 | -1 | |||||||||
| -32 | ||||||||||
| -25 | -25 | -10 | ||||||||
| -16 | -16 | -8 | -8 | -1 | ||||||
| -9 | -9 | -6 | -1 | |||||||
| -4 | -4 | -32 | ||||||||
| -1 | -1 | -6 | -1 | -1 | ||||||
| -12 | ||||||||||
| -36 | -36 | -12 | -1 | |||||||
| -16 | -5 | |||||||||
| -18 | ||||||||||
| -32 | ||||||||||
| -4 | -9 | -16 | -1 | -1 | -2 | |||||
| -1 | ||||||||||
| -25 | -16 | -8 | -1 | |||||||
| -1 | -1 | |||||||||
| -9 | -16 | -18 | ||||||||
| -2 | -1 | -4 | ||||||||
| -1 | -25 | -50 | ||||||||
| -1 | -1 | |||||||||
| -9 | -1 | -18 | -1 | |||||||
| -4 | -16 | -1 | ||||||||
| -25 | -4 | -50 | -1 | |||||||
| -1 | -1 | |||||||||
| -9 | ||||||||||
| -4 | -16 | |||||||||
| -16 | ||||||||||
| -25 | -50 | -5 | ||||||||
| -16 | -32 | |||||||||
| -9 | -18 | -32 | ||||||||
| -1 | -2 | -1 | -1 | |||||||
| -25 | -2 | |||||||||
| -4 | -32 | |||||||||
| -16 | -32 | -1 | ||||||||
| -4 | -1 | -1 | ||||||||
| -25 | -100 | -8 | ||||||||
| -9 | ||||||||||
| -1 | -18 | -1 | -1 | |||||||
| -9 | ||||||||||
| -9 | -18 | -3 | ||||||||
| -1 | ||||||||||
| -5 | ||||||||||
| -1 | ||||||||||
| -16 | -8 | -1 | ||||||||
| -25 | -1 | -1 | ||||||||
| -16 | -5 | |||||||||
| -9 | -2 | |||||||||
| -25 | -1 | |||||||||
| -4 | -1 | -1 | -1 | |||||||