следовательно, могут обратиться в нуль. Если все суммы Sa при данном / отрицательны, то это ребро неограниченное и весь многогранник условий - тоже.

Подставляя найденное Xi в формулы (47), получим координаты новой вершины и вычислим в ней значение функции L{x) = Li. Поочередно меняя каждую внебазисную переменную, найдем все N - М ребер, выходящих из исходной вершины и проводящих в смежные вершины. Сравним все значения функции в смежных вершинах L, и выберем из них наименьшее. Если оно меньше, чем значение функции в исходной вершине Lq, то переместимся в наинизшую из новых вершин и повторим процесс. Если же ттLiLq, то минимум уже достигнут в исходной вершине.

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

мм м

г = 1 / = 1 i = 1

Если эта величина отрицательна, то задача линейного программирования вообще не имеет решения {mmL(x) = - со). Если же она неотрицательна, то это ребро не ведет к минимуму, и оно нас не интересует.

Нетрудно оценить, что для выполнения всех шагов и получения минимума требуется примерно до ЮЛМ арифметических действий. Это уже приемлемо для крупных современных ЭВМ.

Симплекс-метод является примером высоко специализированного метода. Он пригоден только для нахождения минимума линейной функции в многомерном выпуклом многограннике определенного вида - симплексе. Зато он позволяет решать задачи с огромным числом переменных.

5. Регуляризация линейного программирования. Задача линейного программирования часто оказывается плохо обусловленной. Так, себестоимость единицы продукции или норм расхода сырья на разных заводах не должна сильно отличаться. Поэтому даже заметное перераспределение заказов между заводами слабо влияет на суммарную стоимость продукции. Соответственно малая вариация суммарной стоимости приводит к большой вариации распределения заказов.

По тем же причинам небольшое изменение себестоимости или других показателей на отдельных заводах сильно меняет оптимальный план, так что решение очень чувствительно к вариациям коэффициентов. А сами эти коэффициенты не вполне точно известны. Поэтому на практике задача (41) нередко оказывается настолько плохо обусловленной, что не удается даже проверить, совместна ли система дополнительных условий, т. е. может ли существовать решение поставленной задачи.

Для регуляризации задачи линейного программирования воспользуемся тем же способом, что и для решения плохо обусловленных линейных систем (см. главу V, § 1). Будем искать нормальное решение х, т. е. наименее уклоняющееся от некоторого заданного вектора лго- Обычно в качестве х берут ранее составленный план. Тогда регуляризованное решение будет почти не уступать оптимальному по величине L (дг) и в то же время мало отличаться от старого плана, так что перестройка планов будет небольшой.

Возьмем исходную задачу в канонической форме (44) и рассмотрим формулы регуляризации. Надо минимизировать положительную функцию L {х) или, что то же самое, функцию U {х). Дополнительным условием служит система уравнений Ах = Ь с прямоугольной матрицей. Поскольку коэффициенты системы известны не точно, то достаточно найти приближенное решение. Тогда требование приближенного соблюдения этих условий эквивалентно введению штрафной функции 1Лл: -т. е. постановке следующей задачи:

D{x)-\-\i\\Ax-b\\ = m\n, fi>0. (50)

Здесь норму будем определять, как 1з; = (,); тогда все минимизируемые выражения будут квадратичными функциями х, что облегчит вычисления. Заметим, что пока мы не учитывали требования неотрицательности компонент решения.

Условием близости решения к заданному вектору можно считать малость величины Цл: -лГоИ или, в более общем виде, малость величины

{x]=Y,pdxi-Xiof, р,>0. (51)

Эту величину также можно считать штрафом и прибавлять в качестве дополнительного слагаемого в левую часть (50); тогда получаем регуляризованную задачу

М[х]1Цх) + [1\\Ах-ЬГ + Х[х] = тт, [i,K>0. (52)

Отклонение регуляризованного решения от jCq не должно быть большим. Но Хо есть некоторый план; следовательно, его компоненты неотрицательны. Значит, если у решения, найденного из условия (52), и будут отрицательные компоненты, то небольшие по абсолютной величине, что в итоге несущественно. Поэтому при решении регуляризованной задачи (52) условия неотрицательности (446) обычно можно не принимать во внимание.

Величина М [х] является квадратичной формой, так что нахождение ее минимума (путем обычного дифференцирования по координатам) сводится к решению системы линейных уравнений. Поскольку задача регуляризована, то полученная линейная система

будет хорсЗшо обусловлена; тогда ее решение даже при большом числе неизвестных N 200 легко вычислить методом исключения Гаусса.

Более сложен вопрос о выборе параметров регуляризации (х и Я. Величину ц подбирают так, чтобы для найденного регуляризован-ного решения выполнялось условие Лл;- «б6, где 66- допустимая погрешность вектора Ь, связанная с тем, что его компоненты и коэффициенты матрицы А известны неточно. Аналогичным образом величину К связывают с погрешностями коэффициентов С; и с допустимыми отклонениями функции L{x) от своего минимального значения.

При численном решении задачи (52) приходится, находить серию регуляризованных решений, соответствующих разным значениям параметров р и Я, и выбирать оптимальные параметры. Несмотря на это, общий объем вычислений в описанном методе, по-видимому, не больше, чем в симплекс-методе для нерегуляри-зованной задачи (44).

§ 4. Минимизация функционала

1. Задачи на минимум функционала. Если каждой функции у{х) из некоторого множества функций Y сопоставлено число Ф[г/(х)], то говорят, что на множестве Y задан функционал. Задача минимизации функционала формулируется так: найти функцию у (х) е Y, на которой функционал достигает своей точной нижней грани на этом множестве:

Ф(x)] = inf Ф [у (х)], у (х), д{х)У. (53)

Иногда эту задачу называют минимизацией функционала по аргументу, а просто минимизацией называют нахождение числа Ф = inf Ф[у (л:)], когда не требуется определять функцию, минимизирующую этот функционал.

Не всякий функционал и не на всяком множестве имеет минимум. Например, решения задачи (53) не существует, если функционал не ограничен снизу на заданном множестве: решения может также не существовать, если множество не компактно в себе, или функционал разрывен и т. д. (хотя условия непрерывности или компактности не являются, вообще говоря, необходимыми). Но мы не исследуем постановки задач и дальше будем предполагать, что конкретные решаемые нами задачи типа (53) корректно поставлены.

Дадим несколько примеров задач на минимум функционала. Пусть требуется решить операторное уравнение

Ay(x) = f{x), axb. (54)