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


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

5.3. Методы отыскания исходной угловой точки

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

Метод искусственного базиса. Рассматривается задача отыскания угловой точки множества


Не умаляя общности, можно предполагать, что b≥0. Построим следующую вспомогательную задачу в пространстве Еn+m:


(5.12)

с заранее известной угловой точкой


множества W. Применяя симплексный метод, находят (x*u*) - решение задачи (5.12). Обозначим


Теорема 5.1.Если μ = 0, то х* - угловая точка множества R0. Если μ > 0, то R0=∅.

Доказательство. Во-первых, ясно, что задача (5.12) разрешима, поскольку W ≠ ∅ а целевая функция


ограничена снизу нулем. Если μ = 0, то


- оптимальная угловая точка задачи (5.12), поскольку эта задача решается симплексным методом, который осуществляет перебор угловых точек. Очевидно, что х* - угловая точка множества R0. Пусть теперь μ > 0. Предположим, что R0≠∅, то есть найдется x∈R0. Но тогда


будет решением задачи (5.12), что противоречит предположению о положительности величины μ.

Заметим, что метод искусственного базиса является составной частью большинства стандартных программ для ЭВМ симплексного метода решения задач линейного программирования.

Применение метода искусственного базиса приводит к тому, что задачу (5.1) приходится решать в два этапа: сперва решать вспомогательную задачу (5.12), а затем собственно задачу (5.1). Следующий метод позволяет объединить оба этапа.

М - метод. Рассмотрим следующую вспомогательную задачу:


(5.13)

Теорема 5.2.Если разрешима задача (5.1), то найдется такое число М0, что для всех М ≥ М0 в любом решении (x*u*) задачи (5.13) точка х* будет оптимальной для задачи (5.1).

Доказательство этой теоремы по сути дела является частным вариантом доказательства теоремы 10.9 о сходимости M-метода для задачи выпуклого программирования. Первую часть этого доказательства мы здесь воспроизведем.

По условию задача (5.1) разрешима, то есть существует оптимальная точка х*. Но тогда разрешима и двойственная задача



По теореме 4.4 х* и y* будут удовлетворять следующей системе:

Ах = b, x≥0, ATy≤с, <с, x> = <b, y>, (5.14)

Поскольку задача


является двойственной к (5.13), то необходимым и достаточным условием существования решения задачи (5.13) (а следовательно, и двойственной к ней) будет существование решения системы неравенств

(5.15)

Поскольку х* и y* удовлетворяют системе (5.14), то х = х*, u = u* = 0, y = y* будут удовлетворять системе (5.15) для всех


Доказательство того, что при М≥М0 в любом решении x*, u* задачи (5.13) будет u*=0 и, следовательно, x* является решением задачи (5.1), читатель найдет в теореме 10.9.

Обсуждение. Очевидно, что при b≥0 точка


является угловой точкой множества W. Именно эту точку и выбирают в качестве исходной для применения симплексного алгоритма.

На практике нет нужды определять число М0. В качестве М обычно выбирают достаточно большое число,

например


Наконец, заметим, что если М-задача (5.13) имеет решение, то существует решение системы неравенств (5.15), а следовательно, Qo≠∅. Ввиду этого из теоремы 4.6

получаем, что если R0≠∅ и существует решение М-задачи, то существует решение исходной задачи (5.1). Поэтому теорема 5.2 справедлива в условиях существования решения M-задачи и не пустоты множества R0. Отсюда приходим к следующему выводу: если существуют сколь угодно большие значения М такие, что в решении (x*u*) задачи (5.13) будет


то исходная задача (5.1) неразрешима.

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





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


Диски от INNOBI.RU




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