Найти $$ \max_{\mathbb S} F(X) $$ где множество $ {\mathbb S} \subset {\mathbb R}^n $ определяется как множество решений системы неравенств $$ g_1(X) \ge 0, \dots, g_K(X) \ge 0 \ . $$ Здесь $ \{F(X), g_1(X), \dots, g_K(X) \} \subset {\mathbb R}[X] $ (т.е. полиномы с вещественными коэффициентами от $ X=(x_1,\dots,x_n) $).

В частном случае, когда минимизируемая функция $ F(X) $, а также каждое ограничение, накладываемое системой неравенств, являются линейными по $ X $ функциями, рассматриваемую оптимизационную задачу называют задачей линейного программирования (не совсем удачный перевод английского выражения linear programming¹⁾). Основоположником теории линейного программирования считается лауреат Нобелевской премии, академик Л.В.Канторович.

Пример. Предприятие выпускает $ n $ видов продукции с использованием $ m $ видов ресурсов. На производство $ k $-го вида продукции требуется $ a_{1k} $ единиц первого ресурса, $ a_{2k} $ единиц второго ресурса, и т.д., $ a_{mk} $ единиц $ m $-го ресурса. Заданы предельные объемы $ b_1, \dots, b_m $ расхода каждого ресурса и величины прибылей $ c_1,\dots,c_n $ от продаж каждого вида продукции. Требуется указать сколько продукции какого вида следует выпустить для получения максимальной прибыли.

Если предприятие произведет $ x_k $ единиц продукции $ k $-го вида, то оно израсходует $$ a_{j1}x_1+\dots + a_{jn} x_n $$ единиц $ j $-го ресурса. Этот расход не должен превышать предельно возможного расхода $ b_j $: $$ a_{j1}x_1+\dots + a_{jn} x_n \le b_j \ npu \ j\in \{1,\dots, m \} \ . $$ Общая прибыль от выпуска всей продукции будет равна $$ F(X)=c_1x_1+\dots + c_n x_n \ . $$ Требуется подобрать неотрицательные величины $ x_1,\dots, x_n $, удовлетворяющие заданной системе линейных неравенств и обеспечивающие максимальное значение функции прибыли $ F(X) $.

Источник.

Канторович Л.В. Математические методы организации и планирования производства. Л. Изд-во ЛГУ, 1959

Беклемишев Д.В. Дополнительные главы линейной алгебры. М.Наука. 1983

Пример. На железнодорожных станциях отправления $ A_1 $ и $ A_2 $ находятся соответственно 20 и 30 одинаковых единиц груза. Этот груз следует доставить на три станции назначения $ B_1, B_2 $ и $ B_3 $, причем в каждый из них должно быть завезено соответственно 5, 30 и 15 единиц груза. Известны стоимости $ c_{jk} $ перевозки груза из пункта $ A_j $ в пункт $ B_k $: $$ c_{11}=4, \ c_{12}=9,\ c_{13}=3, $$ $$ c_{21}=4, \ c_{22}=8,\ c_{23}=1. $$ Пусть $ x_{jk} $ означает количество единиц груза, предназначенного к отправке со станции $ A_j $ на станцию $ B_k $. При каких значениях $ x_{jk} $ общая стоимость перевозок груза будет наименьшей?

Решение. Задача сводится к нахождению такого решения системы линейных уравнений $$ \left\{\begin{array}{lcl} x_{11}+x_{21} & = & 5, \\ x_{12}+x_{22} & = & 30, \\ x_{13}+x_{23} & = & 15, \\ x_{11}+x_{12}+x_{13} & = & 20, \\ x_{21}+x_{22}+x_{23} & = & 30 \end{array} \right. $$ с неотрицательными значениями переменных, при которых функция $$ F=4x_{11}+9x_{12}+3x_{13}+4x_{21}+8x_{22}+x_{23} $$ принимает минимальное значение. Система линейных уравнений является неопределенной с общим решением, содеращим 2 основные переменные. Выберем в качестве этих основных переменных $ x_{13} $ и $ x_{21} $, тогда общее решение системы имеет вид: $$ x_{11}=5-x_{21},\ x_{12}=15-x_{13}+x_{21},\ x_{22}=15+x_{13}-x_{21},\ x_{23}=15-x_{13} \ . $$ Подставляем эти выражения в функцию $ F $: $$ F=290+x_{13}+x_{21} \ . $$ По условию задачи переменные $ x_{13} $ и $ x_{21} $ неотрицательны. Понятно, что $ \min F $ достигается при $ x_{13}=0, x_{21}=0 $.

Ответ. $ x_{11}=5, x_{12}=15, x_{13}=0, x_{21}=0, x_{22}=15, x_{23}=15 $.

Источник. Пример взят из

Окунев Л.Я. Сборник задач по высшей алгебре. М. Просвещение. 1964

Каноническая форма задачи линейного программирования : найти $$ \max (c_1x_1+\dots+c_nx_n) $$ при всевозможных неотрицательных значениях переменных $ x_1,\dots,x_n $, удовлетворяющих системе уравнений $$ \left\{ \begin{array}{lllll} a_{11}x_1 &+a_{12}x_2&+ \ldots&+a_{1n}x_n &=b_1,\\ a_{21}x_1 &+a_{22}x_2&+ \ldots&+a_{2n}x_n &=b_2,\\ \dots & & & \dots & \\ a_{m1}x_1 &+a_{m2}x_2&+ \ldots&+a_{mn}x_n &=b_m. \end{array} \right. $$

Геометрически, область допустимых значений $ x_1,\dots,x_n $, определяемая этими условиями, представляет собой многогранник в пространстве $ \mathbb R^n $.

Идея решения задачи: экстремум линейной функции

$$ F(X)= c_1x_1+\dots+c_nx_n $$ – если существует – то достигается на границе указанного многогранника, т.е., как правило, в его вершине, или в исключительных случаях – на ребре или грани. Грубо говоря, для нахождения максимума функции $ F(X) $ достаточно перебрать все вершины многогранника и сравнить в них значения $ F(X) $. Однако, в практических приложениях количество переменных $ n $ и ограничений $ m $ может быть настолько велико, что простой перебор вершин многогранника не будет эффективен. Для более направленного перебора — так, чтобы на каждом шаге переходить к новой вершине с увеличением значения $ F(X) $ придуман

Пусть область $ \mathbb{S} \subset \mathbb{R}^{n} $ содержит начало координат: $ \mathbb{O} \in \mathbb{S} $. Функция $ F_{}(X) $ называется положительно (отрицательно) определенной в области $ \mathbb{S}_{} $ если $ F(X)\ge 0 $ (соответственно $ F(X)\le 0 $) всюду в $ \mathbb{S}_{} $ и $ F_{}(X)=0 $ тогда и только тогда, когда $ X=\mathbb{O} $. При этом функцию $ F_{}(X) $ будем называть глобально положительной (отрицательной), если $ \mathbb{S}=\mathbb{R}^n $. Функция $ F_{}(X) $ называется знакопостоянной (положительной или отрицательной) если в области $ \mathbb{S}_{} $ она может принимать значения только одного определенного знака, и $ F(\mathbb{O})=0 $ (но $ F_{}(X) $ может обращаться в нуль и при $ X\ne \mathbb{O},X\in \mathbb{S} $). В дальнейшем мы рассматриваем в качестве функции $ F_{} $ только полиномы.

Пример. При $ n_{}=3 $ функция

а) $ x_1^2+3\,x_2^2+4x_3^6 $ будет положительно определенной;

б) $ x_1^2+x_3^2x_4^2 $ или $ (x_1+{\sqrt 2} x_2-x_3)^2 $ будет неотрицательной, но не положительно определенной;

в) $ -x_1^2 $ будет неположительной, но не отрицательно определенной;

г) $ -x_1^2-2x_2^2-4\,x_3^2 $ будет отрицательно определенной;

д) $ x_1x_2+x_2x_3 $ будет неопределенной.

Теорема. Разложим полином $ F(X) $ по степеням переменных. Допустим, что в этом разложении минимальная степень мономов равна $ m $, так что можно записать

$$ F(X)=F_m(X)+F_*(X), $$ Здесь $ F_m(X) $ – однородный полином (форма) порядка $ m $, а $ F_*(X) $ – полином, содержащий мономы более высоких порядков. Тогда, если $ F_m $ есть форма знакоопределенная (-переменная), то и функция $ F(X) $ будет знакоопределенной (-переменной) в некоторой области $ \mathbb{S} \subset \mathbb{R}^n $.

В виду этой теоремы начнем с установления коэффициентного критерия знакоопределенности формы $ F_m(X) $. Заметим, что для формы свойство положительной (отрицательной) определенности в некоторой области $ \mathbb{S} $ эквивалентно глобальной положительности (отрицательности), т.к. $ F_m(cx_1,\dots,cx_n) \equiv c^m F_m(x_1,\dots,x_n) $. Поэтому слова «в некоторой области $ \mathbb{S} $» будем опускать. Без ограничения общности можно исследовать $ F_m(X) $ на положительную определенность (п.о.)

Очевидно, что для того чтобы $ F_m(X) $ была п.о. необходимо чтобы ее степень $ m $ была четной, а коэффициенты всех мономов $ x_1^m,\dots,x_n^m $ – положительными. В дальнейшем это и будем предполагать.

Более подробное изложение материалов пункта ☞ ЗДЕСЬ.

Теорема. Квадратичная форма

$$ \begin{array}{rllll} F_2(x_1,\dots,x_n)=&a_{11}x_1^2&+2a_{12}x_1x_2&+ \dots & +2a_{1n}x_1x_n+ \\ & &+a_{22}x_2^2 &+ \dots & +2a_{2n}x_2x_n+ \\ & &+\dots &+2a_{jk}x_jx_k & +\dots + \\ & & & &+a_{nn}x_n^2 \end{array} $$ будет положительно определенной тогда и только тогда, когда все главные миноры ее матрицы положительны: $$ a_{11}>0, \ \left| \begin{array}{cc} a_{11} & a_{12} \\ a_{12} & a_{22} \end{array} \right| >0, \ \left| \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{12} & a_{22} & a_{23} \\ a_{13} & a_{23} & a_{33} \end{array} \right| >0, \dots, \det A >0 \ . $$

В этом случае будем также говорить о положительной определенности матрицы $ A_{} $.

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

$$ a_{11}<0, \ \left| \begin{array}{cc} a_{11} & a_{12} \\ a_{12} & a_{22} \end{array} \right| >0, \ \left| \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{12} & a_{22} & a_{23} \\ a_{13} & a_{23} & a_{33} \end{array} \right| <0, \dots, (-1)^n\det A >0 \ . $$

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

$$ F_2(X) \ge 0 \ npu \ \forall X \in {\mathbb R}^n $$ превращением всех неравенств из критерий Сильвестра в нестрогие? — Вообще говоря, нет. Квадратичная форма $$f(x_1,x_2,x_3,x_4)=x_1^2+2x_1x_3+2x_2x_4+x_4^2= X^{\top} \left( \begin{array}{cccc} 1&0&1 &0 \\ 0&0&0&1 \\ 1&0&0&0 \\ 0&1&0&1 \end{array} \right)X $$ – неопределенная, т.к. $ f(1,0,-1,0)=-1_{}<0 $, а $ f(1,0,0,0)=1_{}>0 $. Тем не менее, все главные миноры ее матрицы неотрицательны. ♦

Теорема. Форма $$ F_m(x_1,x_2)=A_0x_1^m+A_1x_1^{m-1}x_2+\dots+A_mx_2^m $$ будет п.о. тогда и только тогда, когда $ A_0>0, A_m>0 $, а полином $ f(z)\equiv F_m(z,1) $ не имеет вещественных корней.

Последнее условие легко проверяется с помощью теоремы Якоби. Вычислим субдискриминанты полинома $ f(z) $.

Теорема. Для того, чтобы полином $ f(z) $ четной степени $ m $ не имел вещественных и кратных корней

a) необходимо, чтобы $ (-1)^{m/2}{\mathcal D} (f) > 0 $;

b) достаточно, чтобы $ {\mathcal V}(1,{\mathcal D}_{m-1},\dots,{\mathcal D}_0)=m/2 $.

Если же $ {\mathcal D} (f) =0 $, то для того чтобы $ f(z) $ был положителен при всех $ z\in \mathbb{R} $

c) необходимо, чтобы $ {\mathcal D}_{1}=0 $;

а если $ {\mathcal D}_0={\mathcal D}_{1}=\dots={\mathcal D}_{k-1}=0, {\mathcal D}_{k}\ne 0 $ то

d) необходимо, чтобы $ k $ было четным, а $ (-1)^{k/2}{\mathcal D}_{k} >0 $;

e) достаточно, чтобы $ {\mathcal V}(1,{\mathcal D}_{m-1},\dots,{\mathcal D}_k)=(m-k)/2 $.

Здесь $ {\mathcal V} $ – число перемен знака в соответствующей последовательности.

Пример. Условия положительной определенности биквадратной формы

$$ F_4(x,y)=A_0x^4+A_1x^3y+A_2x^2y^2+A_3xy^3+A_4y^4 $$

Обозначим $$ S_2=3A_1^2-8A_0A_2,\ S_3=36I_3+2S_2I_2,\ S_4=4I_2^3-27I_3^2\, $$ Здесь $$ I_2=4A_0A_4-A_1A_3 +\frac{1}{3}A_2^2 \ , $$ $$ I_3=-A_0A_3^2-A_1^2A_4+\frac{8}{3}A_0A_2A_4+ \frac{1}{3}A_1A_2A_3-\frac{2}{27}A_2^3 \ . $$

Теорема 1. Форма $ F_4(x,y) $ положительно определена тогда и только тогда, когда $ A_0>0 $ и
a) при условии $ S_4>0 $ выполняется хотя бы одно из условий: $ S_2<0 $ или $ S_3<0 $ ;
б) при условии $ S_4=0 $ выполняются условия: $ S_3=0 $ и $ S_2<0 $.

Источник. Условия из теоремы 1 известны давно. Хороший обзор приведен в решении задачи E 2878

When does a real quartic have no real zeros? American Math.Monthly 1984. Vol. 91, № 3.

Cмысл выражений $ I_2 $ и $ I_3 $ ☞ ЗДЕСЬ.

Статья не закончена!

Пример. Условия положительной определенности биквадратной формы $$ F_4(x_1,x_2,x_3)=x_1^4+x_2^4+x_3^4+\zeta x_1^2x_2x_3+\eta x_1x_2^2x_3 \ . $$

Обозначим $$ H_5=2^{16}(A+B-64)^4 - $$ $$ - AB[(A+B-512)^3-(A+B+256)((A+B-93056)^2-27AB-8755167232)]. $$ Здесь $ A=\zeta^4,\ B=\eta^4 $.

Форма $ F_{4}(x_1,x_2,x_3) $ положительно определена тогда и только тогда, когда $ H_{5}>0 $ и $ A+B <64_{} $. Кривая $ H_5(A,B)=0 $ касается осей $ A=0 $ и $ B=0 $ в точках $ (0,64) $ и $ (64,0) $ соответственно.

В частном случае $ A=B_{} \ (\zeta=\pm \eta) $, условие положительной определенности формы $$ F_4(x_1,x_2,x_3)=x_1^4+x_2^4+x_3^4+\zeta (x_1^2x_2x_3 \pm x_1x_2^2x_3) $$ заключается в выполнении неравенства $$ |\zeta| < 4/ \sqrt[4]{54} \approx 1.475575\ . $$

В частном случае $ B=0 \ (\eta=0)_{} $, условие положительной определенности формы $$ F_4(x_1,x_2,x_3)=x_1^4+x_2^4+x_3^4+\zeta x_1^2x_2x_3 $$ заключается в выполнении неравенства $ |\zeta| < 2\sqrt{2}_{} $.

Источник.

Утешев А.Ю. Использование символьных методов локализации решений для анализа полиномиальных систем. Диссертация на соискание ученой степени доктора физ.-мат. наук. СПб.1998

Критический случай: форма $ F_{m} $ знакопостоянна, но не знакоопределенна ☞ ЗДЕСЬ

Статья не закончена!

Пример. Найти максимум полинома

$$ F(x,y) = $$ $$ =-x^4+8\,x^3 y - 24\,x^2 y^2 +24\,x y^3 - 8\,y^4 -\frac{4}{3}\,x^3 - 8\,x^2 y +24\,x y^2- \frac{56}{3}\,y^3 + 10\,x^2 + 16\,x y + 60\,x + 32\,y \ . $$

Решение. Максимум $ F(x,y) $ совпадает с максимальным положительным корнем полинома $$ \begin{matrix} \mathcal F (z) &= & - 2460375\, z^9 + 13046305743\, z^8 - 20953332885564\, z^7 + 10858379628617100\, z^6-\\ &&- 1199221437495632850\, z^5 - 369773782407882562734\, z^4 + 33574934405487787787124\, z^3 + \\ &&+8363310121361184850064700\, z^2 + 438702308762940646094396529\, z + 6672685776490188470056561943. \end{matrix} $$

Ответ. $ \max F=2797.86763 \pm 10^{-5} $. Координаты соответствующей стационарной точки $$ (-8.07285 \pm 10^{-5}, -11.50294 \pm 10^{-5}). $$

Uteshev A.Yu., Cherkasov T.M. The search for the maximum of a polynomial. J. Symbolic Computation. 1998. Vol. 25, N 5. P. 587-618.