5. Регуляризация линейного программирования.

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

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

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

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

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

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

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

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

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

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

Более сложен вопрос о выборе параметров регуляризации . Величину подбирают так, чтобы для найденного регуляризованного решения выполнялось условие , где — допустимая погрешность вектора b, связанная с тем, что его компоненты и коэффициенты матрицы А известны неточно. Аналогичным образом величину К связывают с погрешностями коэффициентов и с допустимыми отклонениями функции от своего минимального значения.

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