Задачи линейного программирования(ЛП). Регуляризация задач ЛП.Стр 1 из 4Следующая ⇒
При оптимизации экономических планов возникают задачи на минимум линейной функции n переменных при наличии линейных дополнительных условий 3-ёх типов: L(x)=
усл. (2) или (4) определяют полупространство, ограниченное гиперплоскостью, все эти усл. определяют выпуклый n-мерный многогранник J , кот. явл. пересечением соотв. полупр-в. С математической точки зрения эти усл. однотипны. Усл.(3) выделяют из n-мерного пр-ва (n-m)-мерную плоскость. Её пересечение с областью J даёт выпуклый (n-m)-мерный многогранник G, наша задача в том, чтобы найти минимум линейной ф-ии (1) в этом многограннике G. Примером такой задачи явл. распределение производства однотипной продукции по разным заводам.
при 2
(4) – расход сырья по всем заводам, а L – себестоимость общей продукции. X – удовл. всем дополнит. усл. , наз. планом, решение(1)-оптимальным планом. А – вектор усл., В – вектор огр. Приведём задачу к каноническому виду, для этого введём в качестве новых переменных невязки усл. 3-го типа:
Доопределим коэфф. (1) следующим образом:
Каноническая форма з. ЛП: Многогранник канонических усл. образован пересечением новой (N-M)-мерной пл-ти усл. с первым координ. углом. Значит у Строки новой м-цы А линейно-независимы. Все ЛНЗ наборы столбцов А соотв. точкам пересечения пл-ти усл. с координатными гиперплоскостями. Далее перенумеруем переменные так, чтобы первыми были базисные переменные
Если найденные координаты неотрицательны, то точка явл. вершиной многогранника канонических усл. Если хотя бы 1 Различные столбцы А могут образовывать 2)Регуляризация задач ЛП. Задача ЛП часто оказывается плохо обусловленной . поэтому не удаётся даже проверить, может ли Для регуляризации задач ЛП будем искать нормальное реш. х, т.е. наименее уклоняющееся от некоторого заданного х0 (х0- ранее составленный план) Возьмём (7). Дополнительное усл Ах=b, вводим штрафную ф-ию
Норма определяется как Усл. близости реш. к заданному вектору можно считать малость
Эту величину можно считать штрафом и прибавлять в качестве дополнит. слагаемого в левую часть (12), тогда получаем регуляризованную задачу: M[x]= При решении (14) усл. неотрицательности можно не принимать во внимание M[x] – квадратичная форма, поэтому нахождение min сводится к решению с-мы линейных у-ий. Т.к. задача регуляризованна, то линейная с-ма будет хорошо обусловлена, тогда её реш. при большом числе неизв. N При численном реш. (14) приходится находить серию регуляриз. реш., соотв. разным знач. 𝝀 и ©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|