Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

6.3. Применение метода штрафных функций в линейном программировании

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

Рассматривается задача (4.22)



Будем предполагать, что она разрешима, то есть


Построим штрафную функцию


и рассмотрим задачу

(6.10)

Так как по предположению задача (4.22) разрешима, то существует w - решение задачи, двойственной к (4.22), то есть такое, что

<b, w> = m
ATw≤c

Теорема 6.4. Если задача (4.22) разрешима, то существует


и

(6.11)

Доказательство. Заметим, во-первых, что для Любого x≥0 справедливо неравенство

<c, x>≥<w, Ax>.

Далее, для любого x≥0 получаем


Отсюда следует существование*


Но


и так как <с, y> = m и


то окончательно приходим к неравенствам (6.11). Пусть yβ-решение задачи (6.10):


Оценим величину


Так как


то, воспользовавшись тем, что

yβ≥0 и <c, yβ> ≥ <w, Ayβ>,

получаем


Поэтому


* (Можно доказать, что если квадратичная функция ограничена снизу на множестве x≥0, то существует yβ≥0 такой, что m(β)=Ψ(yβ, β))

Тогда


для всех i = 1,..., m. Далее,


И, следовательно,

(6.12)

Наконец, оценим величину |<c, yβ>-m|. Из (6.11) следует, что

(6.13)

Так как


то


Отсюда и из (6.12) и (6.13) получаем


Итак,

(6.14)
предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"