Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 14.4. ДВОЙСТВЕННЫЙ МЕТОД ОТСЕЧЕНИЙПри решении задачи (14.15) или ее модификаций с помощью рассмотренных до сих пор методов отсечений пытаются аппроксимировать допустимую область F. В двойственном алгоритме отсечений вместо этого используется функция Лагранжа и двойственная задача. Некоторые результаты, вытекающие из анализа функций Лагранжа. Напомним некоторые функции, введенные в гл. 2: функция Лагранжа имеет вид
где Прямая функция —
двойственная функция —
В гл. 2 было доказано, что
Прямая задача определения
Двойственная задача определения
при
Было доказано, что если Двойственный метод отсечений действует, аппроксимируя задачу (14.28). Предполагается, что целевая функция и все функции, входящие в ограничения, непрерывны и вогнуты, причем существует точка
Множество X также предполагается выпуклым и компактным в Множества
где Исходное множество определяется соотношением
где Алгоритмическое отображение. Алгоритмическое отображение заключается в следующем. Процедура начинается с множества В общем случае пусть для заданного
или в явной форме
В обозначениях, использованных ранее, соотношение Далее определяется точка
Благодаря компактности X и непрерывности Тест решения заключается в проверке равенства
Если
Вычисленное Наконец, определим множество
Короче говоря, при заданном
Теперь докажем сходимость. Условие 1. Так как Сначала определим точку х следующим соотношением:
где х существует благодаря компактности X. Очевидно, Из выражения (14.29), определения
Поэтому
и, так как Овсе ограничены. Следовательно, Заметим также, что все Условие 2. Это условие тривиально. Условие 3. Ранее было отмечено, что А замкнуто. Ясно, что Условие 4. Если
Но в этом случае
Кроме того, точка Интерпретация сходимости. Докажем теперь, что если
то решение задачи (14.27) определено. Перепишем подзадачу (14.32):
Двойственной к задаче ЛП (14.36) является задача
где
а Рассматривая выражение (14.37), учитывая вогнутость целевой функции и ограничений и свойство
удовлетворяет неравенству
Выбирая
При этом — допустимая точка прямой задачи (14.27). Это следует из того, что аналогично выражению (14.39)
Кроме того, X выпукло, и используя свойство (е) п. 2.3.1 гл. 2, получаем Эти рассмотрения приводят к важному результату. Полагая, что
Теперь вычисляются точки
по
Из соотношений (14.26), (14.42) и (14.43) получаем, что
Отсюда сразу следует, что если
Поведение переменных. Теперь рассмотрим точку
Следовательно, предел
должен быть оптимальной точкой задачи (14.27) (упр. 8). Интерпретация двойственности. Используя задачу (14.36), покажем, что алгоритм аппроксимирует двойственную задачу. Двойственная задача заключается в определении
Допустим, что
Пусть
Теперь задача (14.46) может быть переписана в виде
Но задача (14.47) совпадает с задачей (14.36). Упражнения(см. скан) (см. скан) Примечания и ссылки§ 14,1. Построение методов отсечений этим подходом является новым. § 14.2. Алгоритм был предложен Келли и в работе Ченея и Гольдштейна, см. также Вольф (1961). Доказательство с помощью теоремы сходимости для методов отсечений является новым. § 14.3. Этот алгоритм основан на статье Вейногта (1967), но доказательство является новым. § 14.4. Алгоритм этого раздела является двойственным к алгоритму, разработанному Данцигом и Вольфом (см. Данциг (1963), гл. 24). Представление, приведенное в этой работе, является принципиально другим, основанным на построении новых столбцов, а не на отсечениях.
|
1 |
Оглавление
|