Алгоритм решения специальной задачи выпуклого программирования

Метод Франка-Вульфа [10]

Пусть задана исходная форма специальной задачи выпуклого программирования:

min Z = f(X) = f(x₁, x₂,...,x_n),

где f(X) – выпуклаяфункция.

I шаг. Считаем, что исходное допустимое решение X⁰ (x⁰₁, x⁰₂,...,x⁰_n) найдено.

II шаг.

I. Направление спуска Y ищется в следующем виде

Y=(X - X⁰)= (x₁-x⁰₁, x₂-x⁰₂,...,x_n-x⁰_n), где X (x₁, x₂,...,x_n) Î w, w - область допустимых решений (ОДР). Y = X - X⁰. Необходимо найти координаты точки X (x₁, x₂,...,x_n) такой, чтобы: 1) grad Z × Y = grad Z ×(X - X⁰) < 0, при этом Z убывает; 2) кроме того X (x₁, x₂,...,x_n) Î w.

II. Составим вспомогательную задачу.

Запишем min Z = grad Z(X⁰) × Y = grad Z(X⁰) × (X - X⁰) =

= [¶Z(X⁰)/(¶x₁)]× (x₁-x⁰₁) + [¶Z(X⁰)/(¶x₂)]× (x₂-x⁰₂) + [¶Z(X⁰)/(¶x₃)]× (x₃-x⁰₃) + ∙∙∙ +[¶Z(X⁰) (¶x_n)]× (x_n-x⁰_n)

, i = 1 ¸ m.

X (x₁, x₂,...,x_n) ³ 0.

3. Решаем вспомогательную задачу, являющуюся задачей линейного программирования постоянных размеров.

Так как ищется min Z = grad Z(X⁰) × Y = grad Z(X⁰) × (X - X⁰), то при отрицательном значении Z во вспомогательной задаче в окрестности точки X⁰ целевая функция f(X) по направлению Y = X - X⁰ будет убывать. Этот минимум ищется с учетом системы ограничений. Система ограничений с условием неотрицательности переменных требует, чтобы точки X и X⁰ принадлежали области допустимых решений. Вспомогательная задача линейного программирования позволяет среди всех направлений спуска выбрать направление с максимально возможным спуском. Таким образом, определение направления спуска сводится к определению координат точки X (x₁, x₂,...,x_n). Эти решения можно получить, решая вспомогательную задачу любым известным методом (графическим, симплексным, двойственным и так далее).

III шаг. Движение по направлению спуска осуществляется шагами до тех пор, пока функция убывает. Точка X^* c минимальным значением направления спуска принимается за начальную (исходную) X⁰ для следующего приближения Х тек. = X⁰+t ·Y = X⁰+t · (X - X⁰), где t Î[0, 1].

IV шаг. Критерий оптимальности - признак оптимальности решения.

Первый признак. Градиент целевой функции равен нулю grad f(X⁰) = 0. Это условие является необходимым условием экстремума функции без ограничений. Более подробная и привычная запись - система дифференциальных уравнений:

¶f(X⁰)/(¶x₁) = 0;

¶f(X⁰)/(¶x₂) = 0;

¶f(X⁰)/(¶x₃) = 0;

……………….

¶f(X⁰)/ (¶x_n) = 0.

Так как в задаче выпуклого программирования любой локальный минимум совпадает с глобальным (абсолютным), то необходимое условие экстремума функции можно принять в качестве признака (критерия) оптимальности. Классические методы математики позволяют выявить, является ли седловая точка точкой минимума, точкой максимума или точкой перегиба. При решении на ПК получить точное равенство нулю очень трудно, поэтому при расчетах принимают |¶f(X⁰)/(¶x_j)| ≤ ε (j = 1 ¸ n), где ε – малая величина, заданная точность расчета.

Второйпризнак. Расстояние между двумя точками (между двумя последовательно полученными приближенными решениями) меньше либо равно заданного числа – точности расчета ε: | X⁰ _t - X⁰ _t+1| ≤ ε.

Второй признак (критерий) может считаться основным, так как он включает в себя первый признак (критерий), как частный случай.

Укрупненная схема алгоритма

1. Определение исходного (начального) допустимого решения.

2. Формулировка и решение вспомогательной задачи линейного программирования постоянных размеров. Нахождение вектора Y. Y = X - X⁰.

3. Определение величины шага по направлению Y, задача на поиск минимума функции от одной переменной.

4. Признак (критерий) оптимальности. Если решение не оптимально, то переход к пункту 2.

Пример 14. min Z = х₁²+х₂²

х₁+х₂≤ 2

х₁≤ 2

х₂≤ 1

х₁³ 0, х₂³ 0

Выполним решение по блокам схемы.

I шаг. Возьмем за начальную точку приближения исходное допустимое решение X⁰(1;1). Зададим точность расчетаε = 0,02.

II шаг.

1) Найдем grad Z(X) в общем виде: grad Z(X) =

={¶ Z(X)/(¶x₁); ¶ Z(X)/(¶x₂)} = {2x₁; 2x₂}.

Вычислимзначение grad Zв точке X⁰grad Z(X⁰)={2 · 1;2 · 1 }={2; 2}.

2) Составим вспомогательную задачу линейного программирования. Определим целевую функцию

min Z_всп= grad Z(X⁰) × Y = grad Z(X⁰) × (X - X⁰) = [¶Z(X⁰)/(¶x₁)]× (x₁-x⁰₁) + +[¶Z(X⁰)/(¶x₂)]× (x₂-x⁰₂) ={2; 2} · [(x₁-1); (x₂-1)] = 2x₁–2+2x₂–2 = 2x₁+2x₂–4.

К этой целевой функции припишем систему ограничений и условия неотрицательности переменных основной задачи:

min Z_всп = 2x₁+2x₂–4.

х₁+х₂≤ 2

х₁≤ 2

х₂≤ 1

х₁³ 0, х₂³ 0.

3) Решаем вспомогательную задачу, являющуюся задачей линейного программирования постоянных размеров.

Решим вспомогательную задачу графическим методом:

1) х₁+х₂≤ 2 – полуплоскость;

х₁+х₂= 2 - граничная прямая. Строим ее по двум точкам.

х_j	Первая точка	Вторая точка
х₁
х₂

Точка «начало координат» (0,0) принадлежит полуплоскости.

2) х₁≤ 2, точка (0,0) принадлежит полуплоскости.

3) х₂≤ 2, точка (0,0) принадлежит полуплоскости.

Рис. 8. Решение вспомогательной задачи графическим методом

4) х₁³ 0,

х₂³ 0 I четверть.

5) Область допустимых решений - четырехугольник ABCD.

6) Z_всп= 2x₁+2x₂–4 – целевая функция

antigrad Z _всп =- grad Z _всп ={(¶Z)/(¶x₁); (¶Z)/(¶x₂)} = {2; 2 }. Начало вектора антиградиента – начало координат, точка (0; 0). Конец вектора антиградиента – точка (2; 2). Вектор антиградиент показывает направление минимизации.

7) Строим линию уровня Z = 2x₁+ 2x₂– 4 = const, перпендикулярную вектору антиградиенту. Таких линий уровня бесчисленное множество. Все они параллельны между собой. Перемещаем линию уровня в направлении вектора антиградиента до первого соприкосновения с областью допустимых решений ABCD. Первое соприкосновение - точка A(0;0) – оптимальное решение, в котором вспомогательная задача имеет минимальное значение: min Z_всп(A)= Z_всп(0;0)= 2 × 0 +2 × 0 – 4 = - 4. Следовательно, направление спуска есть, так как скалярное произведение grad Z(X) × Y = grad Z(X) × (X - X⁰) = {2; 2} · [(0 - 1); (0 - 1)] = -4 имеет отрицательное значение. Точка X^*(0,0) оптимальное решение вспомогательной задачи.

)

Находим координаты текущей точки приближения

Х тек. = X⁰+t ·Y = X⁰+t · (X - X⁰), где t Î[0, 1], а точка X⁰= (1;1).

Общий вид приближения Х тек. = (1;1) + t · [(x₁-1); (x₂-1)], где t Î[0, 1].

x_1тек= 1 + t · (x₁-1);

x_2тек= 1 + t · (x₂-1);

Х тек. = [x_1тек; x_2тек ] = [1 + t · (x₁-1); 1 + t · (x₂-1) ].

Однако из решения вспомогательной задачи мы нашли, что решение вектор X имеет значение Х (x₁; x₂), так как Х (0; 0) – оптимальное решение вспомогательной задачи. Подставим в Х тек. значение точек X⁰ (1;1) и Х (0; 0), получим x_1тек= 1 + t · (0 - 1);

x_2тек= 1 + t · (x₂- 1);

Х тек. = [x_1тек; x_2тек ] = [1 + t · (0 - 1); 1 + t · (0 - 1) ] или

x_1тек= 1 - t; x_2тек= 1 - t;

имеем Х тек. = [x_1тек; x_2тек ] = [1 - t; 1 - t ].

Составим таблицу нахождения текущих точек, меняющихся в зависимости от значения t, t Î[0, 1].

Таблица 4

Нахождение текущих точек

Номер текущей точки	Значение tÎ[0, 1].	Координаты текущей точки Х тек.	Значение целевой функции основной задачи Z = х₁²+х₂²
x_1тек= 1 - t;	x_2тек= 1 - t;

	0,5	0,5	0,5	0,5
	0,7	0,3	0,3	0,18

Точка Х(0,0) при t=1 является начальной точкой для следующего приближения, то есть является X⁰ (0; 0). Проверяем эту точку на признак (критерий) оптимальности, для этого находим ¶ Z(X)/(¶x₁); ¶ Z(X)/(¶x₂) в точке X⁰ основной задачи.

¶ Z(X)/(¶x₁) =2 · х₁; ¶ Z(X⁰)/(¶x₁) = 2 · 0 = 0;

¶ Z(X)/(¶x₂) =2 · х₂; ¶ Z(X⁰)/(¶x₂) = 2 · 0 = 0;

По первому признаку (критерию) получено оптимальное решение X^* (0; 0). Проверим решение по второму признаку (критерию)

min Z_всп (X⁰) = grad Z(X⁰) × Y = grad Z(X⁰) × (X - X⁰) = [¶ Z(X⁰)/(¶x₁)]× (x₁-x⁰₁) + +[¶ Z(X⁰)/(¶x₂)]× (x₂-x⁰₂) ={0; 0} · [(x₁-0); (x₂-0)] = 0

х₁+х₂≤ 2

х₁≤ 2

х₂≤ 1

х₁³ 0, х₂³ 0.

Получили, что Z_всп(X⁰) = 0, не зависит от Х, направления спуска нет. Поэтому любое допустимое решение является оптимальным. Например, возьмем за оптимальное решение X^опт= X^* (2; 0).

Переходим к отысканию координат текущей точки Х тек. = X⁰+t ·Y = X⁰+t · (X - X⁰), где t Î[0, 1], а точка X⁰= (0;0),

получим x_1тек= 0 + t · (х₁ - 0); x_2тек= 0 + t · (x₂-0);

Х тек. = [x_1тек; x_2тек ] = [0 + t · (х₁ - 0); 0 + t · (х₂ -0) ] или

x_1тек= t · х₁; x_2тек= t · х₂;

имеем Х _тек. = [x_1тек; x_2тек ] = [ t · х₁; t · х₂ ].

Подставляем в Х _тек. = [x_1тек; x_2тек ] = [ t · х₁; t · х₂ ] координаты точки X^* (2; 0), которую мы приняли за X^опт. Получаем Х тек. (2 · t; 0 · t).

Составим таблицу нахождения текущих точек, меняющихся в зависимости от значения t, t Î[0, 1] и X⁰= (0;0).

Таблица 5

Нахождение текущих точек

Номер текущей точки	Значение tÎ[0, 1].	Координаты текущей точки Х тек.	Значение целевой функции основной задачи Z = х₁²+х₂²
x_1тек= 2·t	x_2тек= 0

	0,01	0,02		0,0004
	0,1	0,2		0,04
…	…	…	…	…

Проверим полученные решения Х _тек._tпо второму признаку (критерию) оптимальности: | X⁰ _t - X⁰ _t+1| ≤ ε, где ε = 0,02?

| X⁰ _t - X⁰ _t+1| = | X⁰ _t - X⁰ | = √[ (x₁_t-x₁⁰)² + (x₂_t-x₂⁰)² ].

| X⁰ ₁ - X⁰ | = √[ (0 - 0)² + (0 - 0)² ] = 0; 0 <0,02 = ε, испытание удачное.

| X⁰ ₂ - X⁰ | = √[ (0,02 - 0)² + (0 - 0)² ] = √ 0,0004 = 0,02; 0,02=0,02= ε, испытание удачное.

| X⁰ ₃ - X⁰ | = √[ (0,2 - 0)² + (0 - 0)² ] = √ 0,04 = 0,2; 0,2>0,02= ε, испытание неудачное.

Примем за оптимальное решение точку X^опт= X^* (0,02; 0). Но точка X⁰ ₁(0;0) тоже удовлетворяет второму признаку (критерию). Кроме того, она удовлетворяет первому признаку оптимальности (критерию), поэтому ее и необходимо принять за оптимальное решение.

Замечание. В отличие от алгоритма общей задачи выпуклого программирования алгоритм решения специальной задачи выпуклого программирования обладает следующей особенностью: вспомогательная задача линейного программирования имеет постоянную размерность и не надо решать нелинейные уравнения. Это существенно упрощает программирование алгоритма для реализации решения на ПК.

Пример 15

min Z =9х₁²+9х₂²+12х₁- 6х₂

0 ≤ х₁≤ 4

1 ≤ х₂≤ 5

х₁³ 0, х₂³ 0

Выполним решение по блокам схемы.

I шаг. Возьмем за начальную точку приближения исходное допустимое решение X⁰(3;4). Зададим точность расчетаε = 0,02.

II шаг.

1) Найдем grad Z(X) в общем виде:

grad Z(X) ={¶ Z(X)/(¶x₁); ¶ Z(X)/(¶x₂)} = {18x₁+12; 18x₂- 6}.

Вычислимзначение grad Zв точке X⁰:

grad Z(X⁰) = {18 · 3+12+18 · 4 - 6}=132.

2) Составим вспомогательную задачу линейного программирования. Определим целевую функцию

min Z_всп= grad Z(X⁰) × Y = grad Z(X⁰) × (X - X⁰) = [¶Z(X⁰)/(¶x₁)]× (x₁-x⁰₁) + +[¶Z(X⁰)/(¶x₂)] × (x₂-x⁰₂) ={18 ·3 +12; 18 ·4 - 6} · [(x₁-3); (x₂-4)] ={66; 66} · [(x₁-

-3); (x₂-4)] = 66x₁–198 + 66x₂–264 = 66x₁+66x₂–462.

min Z_всп = 66x₁+66x₂–462.

0 ≤ х₁≤ 4

1 ≤ х₂≤ 5

х₁³ 0, х₂³ 0

3) Решаем вспомогательную задачу, являющуюся задачей линейного программирования постоянных размеров.

Решим вспомогательную задачу графическим методом:

1. х₁≤ 4 – полуплоскость;

х₁= 4 - граничная прямая, проходящая через точку (4;0), параллельно оси ОХ₂. Точка «начало координат» (0,0) принадлежит полуплоскости.

2. х₂≤ 5 – полуплоскость;

х₂= 5 - граничная прямая, проходящая через точку (0;5), параллельно оси ОХ₁. Точка (0,0) принадлежит полуплоскости.

3. х₂³ 1 – полуплоскость;

х₂= 1 - граничная прямая, проходящая через точку (0;1), параллельно оси ОХ₁. Точка (0,0) не принадлежит полуплоскости.

4. х₁³ 0,

х₂³ 0, I четверть.

5. Область допустимых решений - четырехугольник ABCD.

6. Z_всп= 66x₁+66x₂–462 – целевая функция

antigrad Z _всп = - grad Z_всп ={(¶Z)/(¶x1); (¶Z)/(¶x2)} = {66; 66}. Начало вектора антиградиента – начало координат, точка (0; 0). Конец вектора антиградиента – точка (66; 66). Можно вектор антиградиент масштабировать в 11 раз, тогда конец вектора антиградиента – точка (6; 6). Вектор антиградиент показывает направление минимизации.

7. Строим линию уровня Z = 66x₁+66x₂– 462 = const, перпендикулярную вектору антиградиенту. Таких линий уровня бесчисленное множество. Все они параллельны между собой. Перемещаем линию уровня в направлении вектора антиградиента до первого соприкосновения с областью допустимых решений ABCD. Первое соприкосновение - точка A(0;1) – оптимальное решение, в котором вспомогательная задача имеет минимальное значение: min Z_всп(A)= Z_всп(0;1)= 66 × 0 +66 × 1 – 462 = - 396 < 0. Следовательно, направление спуска есть, так как скалярное произведение grad Z(X) × Y = grad Z(X) × (X - X⁰) ={18x₁+12; 18x₂- 6} · [(x₁-3); (x₂-4)]= 66x₁+66x₂– 462 = 66 × 0 +66 × 1 –462 = - 396 имеет отрицательное значение. Точка X^*(0,1) - оптимальное решение вспомогательной задачи.

Находим координаты текущей точки приближения

Х тек. = X⁰+t ·Y = X⁰+t · (X - X⁰), где t Î[0, 1], а точка X⁰= (3;4).

Общий вид приближения Х тек. = [(3;4) + t · [(x₁-3); (x₂-4)], где t Î[0, 1].

Рис. 9. Решение графическим методом вспомогательной задачи

x_1тек= 3 + t · (x₁-3);

x_2тек= 4 + t · (x₂-4);

Х _тек. = [x_1тек; x_2тек ] = [3 + t · (x₁-3); 4 + t · (x₂-4) ].

Однако из решения вспомогательной задачи мы нашли, что решение X имеет значение Х (x₁; x₂), так как Х (0; 1) – оптимальное решение вспомогательной задачи. Подставим в Х _тек. значение точек X⁰ (3;4) и Х (0; 1), получим x_1тек= 3 + t · (0-3);

x_2тек= 4 + t · (1-4);

Х тек. = [x_1тек; x_2тек ] = [3 + t · (0-3); 4 + t · (1-4) ] или

x_1тек= 3 - 3t; x_2тек= 4 - 3t; имеем

Х тек. = [x_1тек; x_2тек ] = [3 - 3t; 4 - 3t].

Составим таблицу нахождения текущих точек, меняющихся в зависимости от значения t, t Î[0, 1].

Таблица 6

Нахождение текущих точек

Номер текущей точки	Значение tÎ[0, 1].	Координаты текущей точки Х тек.	Значение целевой функции основной задачи Z = = 9х₁²+9х₂²+12 х₁-6 х₂
x_1тек= 3 - 3t;	x_2тек= 4 -3t;

	0,4	1,8	2,8	118,12
	0,8	0,6	1,6	29,08

Точка Х(0,1) при t=1 является начальной точкой для следующего приближения, то есть является X⁰ (0; 1). Проверяем эту точку на критерий оптимальности, для этого находим ¶Z(X)/(¶x₁); ¶Z(X)/(¶x₂) в точке X⁰ основной задачи.

¶Z(X)/(¶x₁) =18 · х₁+ 12; ¶Z(X⁰)/(¶x₁) = 18 · 0 + 12= 12;

¶Z(X⁰)/(¶x₂) =18 · х₂- 6; ¶Z(X⁰)/(¶x₂) = 18 · 1 - 6 = 12.

По первому признаку (критерию) получено оптимальное решение X^* (0; 1). Проверим решение по второму признаку (критерию):

min Z_всп(X⁰) = grad Z(X⁰) × Y = grad Z(X⁰) × (X - X⁰) = [¶Z(X⁰)/(¶x₁)]× (x₁-x⁰₁) + [¶Z(X⁰)/(¶x₂)]× (x₂-x⁰₂) ={12; 12} · [(x₁-0); (x₂-1)] ={12 x₁; 12 x₂ -12}

min Z_всп = 12 x₁+ 12 x₂ -12

min Z_всп= 12 · 0+ 12 · 1 –12 =0

Переходим к отысканию координат текущей точки Х тек. = X⁰+t ·Y = X⁰+t · (X - X⁰), где t Î[0, 1], а точка X⁰= (0;1),

получим x_1тек= 0 + t · (х₁ - 0); x_2тек= 1 + t · (x₂-1);

Х тек. = [x_1тек; x_2тек ] = [0 + t · (х₁ -0); 1 + t · (х₂ -1) ] или

x_1тек= t · х₁; x_2тек= 1 + t · (х₂ -1);

имеем Х _тек. = [x_1тек; x_2тек ] = [ t · х₁; 1 + t · (х₂ -1)].

Подставляем в Х _тек. = [x_1тек; x_2тек ] = [ t · х₁; 1 + t · (х₂ -1) ] координаты точки X^* (2; 0), которую мы приняли за X^опт. Получаем Х тек. (2 · t; 1 + t · (0 -1)) =(2 · t; 1 - t).

Составим таблицу нахождения текущих точек, меняющихся в зависимости от значения t, t Î[0, 1] и X⁰= (0;1).

Таблица 7

Нахождение текущих точек

Номер текущей точки	Значение tÎ[0, 1]	Координаты текущей точки Х тек.	Значение целевой функции основной задачи Z = 9х₁²+9х₂²+ +12х₁- 6х₂
x_1тек=2·t	x_2тек= 1 - t;
	-

	0,01	0,02	0,99	3,2055
	0,1	0,2	0,9	4,65

Точка Х(0,1) при t=0 является начальной точкой для следующего приближения, то есть является X⁰ (0; 1).

Проверим полученные решения Х _тек._tи Х _тек._t+1по второму признаку оптимальности: | X⁰ _t - X⁰ _t+1| ≤ ε, ε = 0,02?

| X⁰ _t - X⁰ _t+1| = | X⁰ _t - X⁰ | = √[ (x₁_t-x₁⁰)² + (x₂_t-x₂⁰)² ].

| X⁰ ₁ - X⁰ | = √[ (0 - 0)² + (1 - 1)² ] = 0; 0 <0,02 = ε, испытание удачное.

| X⁰ ₂ - X⁰ ₁| = √[ (0 – 0,02)² + (1 – 0,99)² ] =√ 0,0004+0,0001=√ 0,0005; √ 0,0005 > 0,02 = ε, испытание неудачное.

| X⁰ ₃ - X⁰ ₂| = √[ (0,02 – 0,2)² + (0,99 – 0,9)² ] =√0,0324+0,0081= √ 0,0405 > 0,02= ε, испытание неудачное.

| X⁰ ₄ - X⁰ ₃| = √[ (2 - 0,2)² + (0 – 0,9)² ] = =√3,24+0,81= √ 4,05 > 0,02= ε, испытание неудачное.

Примем за оптимальное решение точку X^опт= X^* (0; 1). Но точка X⁰ ₁(0;1) тоже удовлетворяет второму признаку (критерию)оптимальности; кроме того, она удовлетворяет первому признаку оптимальности (критерию), поэтому ее и необходимо принять за оптимальное решение.

min Z = 3, оптимальное решение X*(0;1)

Индивидуальные задания 3

Решить задачи методом Франка- Вульфа.

1. Найти max z = 2x₁ + 3x₂ +2x₁² + 3x₂²

при условиях: x₁ + 4x₂≤ 4

x₁ + x₂≤ 2

x₁≥ 0; x₂≥ 0

2. Найти max z =3x₁² + 4x₂²+ 2x₁ + 3x₂

при условиях: x₁ - x₂≥ 0

- x₁ + 2x₂≤ 2

x₁ + x₂≤ 4

x₁≥ 0; x₂≥ 0

3. Найти max z = x₁ + 5x₂ + 2x₁² + 3x₂²

при условиях: 2x₁ + x₂≥ 2,0

3x₁ + x₂≤ 4

x₂≤ 4

x₁≥ 0; x₂≥ 0

4. Найти min z = 4x₁² + 3x₂²- x₁ - 3x₁

при условиях: x₁ - 2x₂≤ 8

x₂≤ 3

x₁≥ 0; x₂≥ 0

5. Найти max z = x₁ + 4x₂ - 6₁² + 3x₂²

при условиях: x₁ + x₂≤ 6

x₁ - x₂≤ 1

x₁≥ 0; x₂≥ 0

6. Найти min z =2x₁² + 5x₂²+ 2x₁ - 4x₂

при условиях: x₁ - x₂≤ 3

x₁ ≤ 5

x₁ + 2x₂≥ 1

x₁≥ 0; x₂≥ 0

7. Найти min z = - 2x₁ - 4x₂ + 2x₁² + 3x₂²

при условиях: 2x₁ - 3x₂≤ 0

x₂ ≤ 5

x₁≥ 0; x₂≥ 0

8. Найти max z = - 5x₁ - 2x₂ +3x₁² + 3x₂²- 2

при условиях: x₁ + x₂≥ 1

2x₁ + x₂≤ 4

x₁≥ 0; x₂≥ 0

9. Найти max z = 4x₁² + 2x₂²- 2x₁ + 2x₂ + 3

при условиях: x₁ + 2x₂≥ 3

2x₁ - x₂≤ 1

x₁ + x₂≤ 2

x₁≥ 0; x₂≥ 0

10. Найти min z = 2x₁ + 6x₂+2x₁² + 3x₂²- 1

при условиях: 2x₁ + x₂≤ 3

-x₁ + 2x₂≥ 1

x₁≥ 0; x₂≥ 0

11. Найти min z = -2x₁² + 3x₂²+ 4x₁ + x₂ + 1

при условиях: x₁ + x₂≤ 10

2x₁ - x₂≤ 10

x₁≥ 0; x₂≥ 0

12. Найти max z = - 8x₁ - 2 x₂+2x₁² + 4x₂² + 1

при условиях: 5x₁ + x₂≥ 6

3x₁ - 2x₂≤ 1

x₁ + 2x₂≥ 3

x₁≥ 0; x₂≥ 0

13. Найти max z = 4x₁ + x₂ -2x₁² + 4x₂²- 2

при условиях: x₁ - x₂≥ 0

x₁ + x₂≤ 4

x₁≥ 0; x₂≥ 0

14. Найти max z =3x₁² + 2x₂²+ 9x₁ + 4x₂ + 2

при условиях: x₁ - x₂≥ 0

x₁ + x₂≤ 4

x₁≥ 0; x₂≥ 0

15. Найти max z = 3x₁ - 2 x₂- 2x₁² + 4x₂²- 5

при условиях: x₁ - x₂≥ 0

x₁ + x₂≤ 4

x₁≥ 0; x₂≥ 0

16. Найти min z = -2x₁² + 3x₂²+ 4x₁ + 6 x₂ + 1

при условиях: x₁ + x₂≤ 5

2x₁ - x₂≤ 6

x₁≥ 0; x₂≥ 0

17. Найти min z = -2x₁² - 3x₂²+ 4x₁ +3x₂ + 1

при условиях: x₁ + x₂≤ 7

2x₁ - x₂≤ 7

x₁≥ 0; x₂≥ 0