И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 41
Текст из файла (страница 41)
! Недостатком алгоритма 2' является проблема выбора подходящего числа (3 ) О. 3. Правило вмбора вектора а~, вводамого в баеве, гараитируиицее от оациклававиа в вырождевиом елучае Если при использовании алгоритма 1 для решения задачи линейного программирования в вырожденном случае возникло зацикливание (т. е. возврат к уже пройденному базису), то на шаге !Х алгоритма 1 следует применить следующую процедуру выбора индекса з Р (1: п1, гарантирующую от зацикливания. Алгоритм 3 Н а ч а л о. 1.
Обозначить через 2', совокупность индексов 1, на которых достигается О, = ппп ( — Ыап!). оо со П. Положить т = 1. Ъ!О Ос н он но й ц и к л. 1!1. Если Рч содержит один элемент, то этот элемент принять в качестве индекса з и прекратить вычисления; иначе перейти к шагу 1Ч. 1Ч. Если все индексы ! Е У» превосходят ! »+ь то положить з = ппп 1; иначе перейти к шагу Ч. /е.ч ч Ч.
Построить множество О,+ь объединяя в него те индексы 1, на которых достигается ш[я (е„,+ь1/ег1). мя» 1<'т — »4-1 Ч1. Если»(гп, то положить т = т+ ! и перейти к шагу Ш; иначе перейти к шагу ЧП. ЧП. Положить з = ппп !. И ччч[Л Библиографические укамглия. Пункт 1 написан на основании работы 12261, пункты 2 и 3 — иа основании работ [414, 415, 416!. Дополнительные сведения о двойственном симплекс-методе, способах построения исходного опорного решения и вырожденности в двойственном симплекс- методе можно найти в работах [61, 429, 226, 114!.
4.3. Методы последовательного совращения невяаок Процесс вычисления оптимального решения методом сокращения невязок не требует предварительного определения опорного решения прямой или двойственной задачи. Для начала процесса достаточно знать лишь произвольное допустимое решение сопряженной задачи. При наличии опорного решения исходной задачи 1.0 и произвольного допустимого решения сопряженной задачи 2.0 модификация метода сокращения невязок — метод двухсторонних оценок позволяет получать приближенное решение с наперед заданной ошибкой прн существенно меньшем числе итераций, чем это' требуется для получения оптимального решения.
1. Метод последовательного сокращении невивок Предположения 1. (з) — а~г ~ О, 1 = 1, 2, ..., пц (!!) — ранг матрицы А равен т; (!и) — п ) т; (!о) — двойственная задача 2.0 имеет допустимые решения. Метод последовательного сокращения невязок использует прямую и двойственную задачи линейного программирования. Правила перехода от одной итерации к другой обеспечивают сокращение невязок (разностей между правыми и левыми частями условий-равенств задачи 1.0).
Через конечное число итераций либо невязки сводятся к нулю (т. е. находится оптимальное решение задачи 1.0), либо устанавливается неразрешимость задачи 1.0. На каждой итерации алгоритма требуется вычислять оптимальные решения некоторой вспомогательной задачи и двойственной к ней. В методе йы требуется предварительное вычисление допустимого решения двойственной задачи 2.0. Алгоритм 1 Н а ч а л о.
1. Найти произвольное допустимое решение у = = (У! Уа " У ) двойственной задачи 2.0. Ос нов ной цикл. П. Найти все индексы /е (1: п), для которых Г=! и обозначить множество таких индексов через ~Й(1! !и .в /!) 1П. Используя модифицированный симплекс-метод, найти оптимальное решение (х!„х!о ..., х!и еа, еа, ..., е ) вспомогательной задачи 1 линейного программирования в пространстве В'+: Задача 1. Найти агя гп)п ~',е! при ограничениях !а,...,а., е,....а ! ! ! ! '"' О' ~ саа!х!+ е! = а;, ! = 1, ..., т; кя х!~0 при 1ЕО; а!~О, а=1, 2, ..., т.
1Ч. Найти оптимальное решение 1аа= (1а!, ра, ..., )а ) задачи, двойственной к приведенной выше вспомогательной задачи 1, которое можно вычислить по формуле ! р* (сао сао ..., с;„) В~, где В~' — матрица, обратная к оптимальной базисной матрице задачи 1; (га„ ..., с! ) — координаты вектора (О, ..., О, 1, 1, ..., 1), 3 "' я ! юа отвечающие оптимальному базису задачи 1.
При решении задачи 1 модифицированным симплекс-методом матрица В~' и вектор (га„ са,, ..., с! ) известны. Двойственная к задаче 1 имеет вид: найти агйшах ~ аа)а! при ограничениях «! о>! ! !ба!~О при ~~О; а-! 1а! я:,; 1, ! = 1, 2, ..., т. Ч. Если невязки е~', 1 = 1, 2, ..., т, удовлетворяют равенствам е,'=О, 1=1, 2, ..., т, то вычислить вектор х~ = (хп хл, ..., х„) по правилу х; =х; при /~81 х, =0 при /Яо' ~ и прекратить вычисления (в этом случае находится оптимальное решение хч задачи 1.0); если при некотором 1 ~ (1: т! е~' ) О, то перейти к шагу Ч1.
Ч1. Вычислить величины 6;= ~ау;, !=1, ..., и. ! ЧП. Если при всех ! Е 11: и) выполняется неравенство 6; ( ( О, то прекратить вычисления (в этом случае задача 1.0 не имеет допустимых решений); иначе перейти к шагу ЧП1. 'ЧП1. Вычислить величины Л! для тех /, для которых 6! ) 0: Ь! = ~, аиу,- — сп ! 1Х. Вычислить отношение Ь!/6! для тех /, для которых 6~ ) ) О, и минимальное из этих отношений обозначить через 8,. Х. Положить у = у. Х1. Перейти к новому допустимому решению у = (у,, ..., у ) двойственной задачи 2.0 по правилу у~ = ус — Ол3ла э ~ — !э .
° е ХП. Перейти к шагу П. Теорема 1. Если выполнены предположения 1 и расширенная мдача 1 невырожденная, то процесс решения задачи 1.0 алгоритмом ! через конечное число итераций закончится либо на шаге Р (находится оптимальное решение задачи !. О), либо на шаге У11 (устанавливается, опо задача 1.0 не имеет допустимых решений). Замечание 1. Алгоритм 1 можно применять для решения задачи 1.0 и в том случае, когда расширенная задача ! вырожденная.
Для этого необходимо при решении вспомогательных задач модифицированным симплекс-методом пользоваться правилом, гарантирующим от зацикливания. Замечание 1'. Исходное опорное решение каждой последующей вспомогательной задачи 1 следует составлять из соответствующих положительных компонент оптимального решения предыдущей вспомогательной задачи 1, что существенно сократит число итераций, необходимых для решения очередной вспомогательной задачи 1. 213 В. Метод детотояовввд овевов Для решения задач линейного программирования методом двусторонних оценок предварительно необходимо находить (кроме исходного допустимого решения сопряженной задачи 2.0) исходное опорное решение исходной задачи 1.0. На каждой итерации алгоритма вычисляется некоторая оценка (невязка е) уклонения полученного опорного решения от оптимального.
В методе двусторонних оценок требуется на каждой итерации решать вспомогательную задачу линейного программирования с известным исходным опорным решением и его базисом. Алгоритм 2 Н а ч а л о. 1. Найти опорное решение х = (х„..., х„) задачи 1.0 и допустимое решение у = (у„..., у ) сопряженной задачи 2.0. 11. Вычислить величины Ь~ — — ~, ауу, — сл /~11: и]. гвм Основ ной цикл. 111.
Найти все индексы 1~ (1: и1, для которых выполняется Ь~ — — О, и обозначить множество таких индексов через Ог. 1У. Обозначить через Ох множество индексов векторов базиса опорного решения х. Ч. Найти множество О=От () Ох. т'1. Используя модифицированный симплекс-метод, найти оп- тимальное решение х* следующей вспомогательной задачи линей- ного программирования. Задача 2. Найти агд ш!и 2; Ь,х, при ограничениях му ~а!х =ье / !ЕУ х,~О, /ЕР. Ч11.
Найти оптимальное решение р' = (рь ..., р„,) задачи, двойственной к задаче 2 р = (д,„ ..., л, ) в;/, где В~' — матрица, обратная к оптимальной базисной матрице задачи 2; („ ..., 1 — номера базисных векторов оптимального ре- шения задачи 2. Ч111. Вычислить невязку е= ~,Л;х*. м,у 214 Невязка е является разностью между значениями линейных форм двойственной и прямой задач при данных х и у. На практике вы- числения можно прекращать, когда е не превышает наперед задан- ной точности вычисления минимума целевой функции. 1Х.
Если е = О, то вычислить оптимальное решение хе = (хз, ... ..., х„) задачи 1.0 х1 = х]" при 1~6 ) 1=1, ...,л, х1 = 0 при 1'Я21 ) и прекратить вычисления; иначе перейти к шагу Х. Х. Вычислить параметры ~и 61 = ~ ап]ь~, 1 = 1, 2, ..., и. 1 Если при всех 1Е И: л! выполняется 61 «О, то прекратить вычисления (в этом случае задача 1.0 не имеет допустимых решений); иначе перейти к шагу Х1. Х1. Вычислить отношение Л1/61 для тех 1, для которых 61 ) О, и минимальное из этих отношений обозначить через О,. ХП. Перейти к новому опорному решению х = (х» ..., х„) за- дачи 1.0 Хг = Хг ПРи ]с77 1=1, ...,л. х;=0 при 1']сУ ) Х1П. Положить у = у; Лг — — Лр 1 1, ..., л. Х1Ч. Перейти к новому допустимому решению у (у„..., ум) сопряженной задачи 2.0 у = у — В,р.е. ХЧ. Вычислить величины Лр отвечающие новому допустимому решению у, Лу = Ьг — йе61, 1~ [1 '.л).
ХЧ1. Перейти к шагу П1. Тиаре а2. Если еыполнены предположения 1, то е нееырожденном случае процесс решения задачи 1.0 алгоритмом 2 через конечное число итераций закончится либо на шаге 1Х (находится оптимальное решение задачи 1.0), либо на шаге Х (устанаелиеается, что задача 1.0 не имеет допустимых решений). Алгоритм 2 может применяться и для вырожденного случая. Тогда при решении вспомогательной задачи 2 теоретически может возникнуть зацикливание. При зацикливании следует применять специальное правило, гарантирующее от зацикливания.
Библиографические указания. Параграф написан на основании работ [416, 416, 116]. Метод последовательного сокращения невязок и его варианты изучались также в работах 1414, 207, 241, 374]. 216 4.4. Обобщенный симплекс-метод 3 а д а ч а 1. Найти а»яшах ~ с~х! для заданного вектора с = кех !=! = (с„..., с„) и заданного множества Х ~ (х ) Ах = а', х ~ О, х е В" ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
