И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 42
Текст из файла (страница 42)
Предположения !. (1) — ранг матрицы А равен т; (11) — т ( (и; (й1) — множество Х непусто. В обобщенном симплекс-методе на каждой итерации алгоритма в базисе меняются не один, а несколько векторов. Для определения векторов, вводимых в базис и выводимых из него, требуется на каждой итерации решать вспомогательную задачу линейного программирования с ограничениями в виде неравенств.
В начальной стадии алгоритма требуется иметь опорное решение, его базис и матрицу, обратную к базисной. На последующих итерациях опорное решение, его базис и матрица, обратная к базисной, вычисляются по рекуррентным формулам. На начальных итерациях алгоритма число вводимых в базис векторов надо выбирать по возможности большим, а в конце решения задачи это число следует уменьшать. Обобщенный симплекс-метод требует меньшего, по сравнению с другими методами, числа итераций для получения оптимального решения, и важно, что этот метод менее чувствителен к ошибкам вычислений.
Алгоритм л Н а ч а л о. 1. Найти исходное опорное решение х' = (х!, ... ..., х„) и его базис а', ..., а Способы вычисления исходного опорного решения и его базиса приведены в ~ 4.1. П. Вычислить матрицу В,' = (р!;)1=~!,",",~, обратную к исходной базисной матрице В, = (а", ..., а' ). Основной цикл. П!. Положить гко=х~!,, й=1, ..., т; й!, (!„ ..., ! ). 1Ч.
Вычислить величины Л»= ~ с!рк!, !=1, ..., т. Ч. Вычислить оценки ап 1= 1, ..., и, к! Ь! = ~, а„Л! — с! для 1 Я $'к; !=! Ь! —— О для )ЕОк Ч1. Если все Л! ) О (1 — — 1, ..., и), то положить х* = х' и прекратить вычисления (т. е. в этом случае опорное решение х' оптимально); иначе перейти к шагу ЧП. ЧП. Задать множество Л, состоящее из произвольных 1 индексов 1 ~ И. таких, что Л,(0. Ч111. Вычислить коэффициенты гн, 1= 1, ..., л»; 1С („разложения векторов аг, (с Ь по базисным векторам гп= ~, а»йн», 1=1, ..., т; 1~1.
»-! 1Х. Применить алгоритм 7.1 (см. 5 4.7, алгоритм 1) к решению следующей вспомогательной задачи линейного программирования: найти агя шах 1 — ч~~ Л,О,) для заданных чисел Ль 1Е Ь при 9~ » ма ограничениях О~~О 161" За исходное опорное решение вспомогательной задачи можно принимать О, = О, 1Е Ь (базис этого опорного решения не содержит ни одного элемента). Решение вспомогательной задачи может завершиться либо признаком неразрешимости этой задачи, либо получением оптимального решения, базиса этого решения и матрицы, обратной к оптимальной базисной (см. $ 4.7). Если в процессе решения вспомогательной задачи обнаружится ее неразрешимость, то прекратить вычисления (в этом случае задача 1 также неразрешима, т.
е. ее целевая функция неограиичена на допустимом множестве Х); иначе получить оптимальное решение О~, 1Е !., вспомогательной задачи и его базис В„(1(т( ( 1), состоящий из элементов матрицы (ая),'~ь,.„»„которые расположены на пересечении строк и столбцов с номерами г„..., г, и й„..., Ф„соответственно, а также получить матрицу В, ', обратную к матрице В,. Х. Перейти к новому опорному решению х = (х„..., х„) по правилам ам — ~л~~~ а»яйя, если 1 = 1», Й = 1, ..., ш; иа. О! /с 7- О, в остальных случаях, где/=1, ...,а. Х!.
Перейти к новому базису В-, путем замены в старом базисе векторов а'~, », = 1, ..., т, векторами а», ..., а»', т. е. положить („„=йм 1=1, ..., т. ХП. Получить из матрицы В; путем перестановок ее столбцов матрицу А-, по следующему правилу: 2П первые т столбцов матрицы А„- образуются матрицей С,= (а', аМ, ..., аи'); остальные т — т столбцов матрицы образуются матрицей С„которая получается из матрицы В-, путем вычеркивания столбцов с индексами й„...„й,.
Указанный способ получения матрицы А; из В„- порождает набор чисел зи 1' = 1, ..., т, (з, е П: т)) такой, что 1-й (в порядке следования) столбец матрицы В-„ставится на место з,-го столбца матрицы А,-. Обозначить через /е1 Я1 (С) = = С) оператор, который 1-й (1 = 1, ..., т) столбец квадратной матрицы С ставит на место з,.-го (1 = 1, ..., т) столбца в матрице С, и обоаначить через Я, Я (О) = О) оператор, который 1-ю (1 = = 1, ..., т) строку квадратной матрицы О ставит на место з;-й строки в матрице О. ХП1. Составить матрицу )' размера т Х т, столбцами которой являются векторы ~х т г х =- (гых, гее„, ..., гтех), )1 = 1...;, т.
Х!Ч. Составить матрицу В,,„которая получается из матрицы 1' путем вычеркивания строк с индексами г,, гм ..., г,. ХЧ. Разбить матрицу В,' на две подматрицы /=1,...,т / 1, ..т (~1/)1:1,'."..'',т Н (~1+с,/)1-1."..".,'т —. размера т Х т и (т — т) ~с т, соответственно. ХЧ1. Вычислить матрицы 1 1,...,т /=1,...т (р+т )1 1,','.",' т И (~3, ); соответственно, по формулам /=1,...,т 1=1....,т (/Ч+т,/)1=1,...,т — т = (И/+т/)/ 1,...,т-с— =1 / 1,...,т. — В -..тВг ((11/)1 1,'..".л (()1/) 1"....'л = Вт ' (ея//)1==11,"..".д ° ХЧП.
Составить матрицу А-, ' размера т х т, первые т строк которой образованы матрицей (р//)';:1,"..",',„а остальные т — т— матрицей (р/ч и/); 1,"...", ХЧ1'П. Найти матрицу В,=' = ЯГ' (А=,'). Х1Х. Положить х = х, В„' = В„-', В„= В; и перейти к шагу П1. Теорема 1.
Если выполнены предположения 1, то в невырожденном случае процесс решения задачи! алгоритмом! через конечное число итераций закончится либо на шаге У! (находится оптимальное решение 218 х» задачи 1), либо на шаге 1Х (устанавливается, что целевая функция задачи 1 неограничена на допустимом множестве Х). Библио«сафич»енсы у«ив!нов. При написании параграфа испольэованы работы !414, 415, 416, 114!. 1. Метод равно«еевва Давввеа — Вулафа 3 а д а ч а 1. Найти ягошах (с, х) для заданного вектора с = «ех = (с„с„..., с„) и множества Х, задаваемого соотношениями А'х = Ь', (4.10) А'х = Ьс; (4.!1) х~О, (4.12) где А' — матрица размера т х и; А' — матрица размера тсх и; Ь = (Ь„..., Ь ); Ь = (Ь тв ..., Ь,), 1', Случай ограниченности множества Х'.
Предположения 1. (с) — множество Х', определяемое условиями (4.11) — (4.12)— !А»1 ограничено; (И) — гапд ~Ас/ = т + т„(И!) — т + тс( п. В методах разложения исходная задача 1 размера (т+ т!) )( )с п сводится к решению следующей задачи линейного программи- рования размера (т + 1) )с !. г-задача. Найти агяшах ~ асгс при ограничениях с-! ~, р'г, = Ь'1 (4.13) с-! Ее!=1; ! гс~О, 1=1, 2, ..., 1, (4.13) где х', х', ..., х' — вершины многогранника Х', о,=(с, х'), !=1, 2, ..., 1; р'=Аех', с'=1, 2...,!.
(4.13) Оптимальное решение (гс, гт, „гс) г-задачи однозначно опре- деляет оптимальное решение х» задачи 1 с: х» = ~ г,'.х'. с=! (4.14) 219 4.5. Методы блочного нрограммнроввннв Методы блочного программирования позволяют получить реше нне экстремальной задачи с помощью решения ряда вспомогатель иых задач, каждая из которых в определенном смысле является более простой, чем исходная. В линейном программировании методы блочного программирования применяются для решения задач большого размера и задач с блочной структурой матрицы ограничений. Для решения г-задачи не обязательно знать все вершины множества Х' (т. е. вектора х', х', ..., х'). Необходимо лишь знать вершины, входящие в исходный опорный базис г-задачи.
В процессе решения г-задачи модифицированным симплекс-методом проверка на оптимальность опорного решения г-задачи производится с помощью решения некоторой вспомогательной задачи линейного программирования с ограничениями (4.11) — (4.12). Алгоритм 1 'Н а ч ало. 1. Найти исходное опорное решение г' = (гс, ... ..., гс) г-задачн, базис(Р'( ...
(Р ! этого опорного решения В Ф и коэффициенты о;,, й = 1, ...! т + 1, линейной формы г-задачи, отвечающие исходному опорному решению. П. Вычислить матрицу В ', обратную матрице, составленной ст I ст+!'! из базисных векторов (Р с, ..., (Р ) В-! ~ (1 )1=!1- 1т+! Оси о в но й ци кл. П1. Положить ос„=(с!осси ..., пс„+!). 1У. Вычислить вектор л( (л, ц-(л„л„..., ), л) по формуле ! Л = па„В У. Положить уса = гс„, й = 1, 2, ..., т + 1. У1. Вычислить а-мерный вектор с" = (с~с, с~!, ..., с~) по формуле сл = с — ЛАО (в обычной форме записи координаты вектора сл вычисляются по формуле с,". = сс — ~; Хссгссл 1*= 1, 2, ..., а). с ! 'УП. Вычислить вектор л — оптимальное решение следующей задачи линейного программирования в пространстве г1".
Подзадача Хсп! найти агп шах (с~, х) прн ограничениях Ф Асх * (сс; х~О. Для решения подзадачи Хл удобно применять симплекс-метод или модифицированный симплекс-метод. Причем на каждой последующей итерации за исходное опорное решение и его базис можно брать оптимальное решение и его базис, полученные на предыдущей итерации. ЧП1. Если выполняется равенство (~с, х») = Х, то положить го= г' и перейти к шагу 1Х (т.
е. в этом случае опорное решение г' = (гь ..., г)) является и оптимальным решением г-задачи); иначе перейти к шагу Х. 1Х. Вычислить вектор хо — оптимальное решение задачи 1 я+1 х* = ~~'., г; х» А 1 'о и прекратить вычисления. Х. Вычислить вектор р" = !Р 1, где —,'1 / р» Аох» Х1. Вычислить вектор (т.
е. разложить вектор р по базисным векторам) 1-ч (у~»~ уз»~ ° ° °, ут-~-ьч) = В р ° ХП. Вычислить коэффициент линейной формы г-задачи о» =(с, х»). ХП1. Вычислить отношения уоо/уо» для тех й Р [1: (т+ 1)), для которых уь») О и обозначить минимальное из этих отношений через йо. Х1Ъ', Найти индексг Е П: (т+1)! такой, чтоу„) О ну о/у„= Оо' ХЪ'.
Положить бу= Ц, 1 = 1, ..., т + 1; / = 1, ..., т + 1 и уоо = ущ, й = 1, ..., т + 1. Перейти к новому базису (р'), ..., ~р'~, ..., ~р +' 1, который получается заменой вектора р'= (Р') впредыдущем базисе век- 11 ) тором рч = (р1 ) (т. е. положить 1,= ч). ХЧ1. Вычислить по основным формулам матрицу В ~~ (()~/)~~ 1,",",,',„ф1~,обратную к новой базисной матрице Ь=Ь/уиа /=1,-, +1 Д! = Ц вЂ” 4.|юг») Уоч, 1=1, ..., т+1; /=1, ..., т+1; (чьг. ХЧП. Вычислить по основным формулам новые значения базисных координат опорного решения Ую = У»о/У»ч! Уоо =Ум — (Ую/У»»)уоч /о = 1 ..., г — 1, г+ 1, ..., т+ 1. ХЧП1.
Перейти к новому опорному решению г-задачи г = (г', ..., г!): г), = уьь й = 1, ..., т+ 1, остальные координаты вектора г' равны нулю. Х1Х. Перейти к шагу 111. Теорема 1. Если допустимое множество решений Х задачи 1 непусто, то при выполнении предположений 1 алгоритм 1 за конечное число итераций приводит к оптимальному решению задачи 1 (предполагается, что если в вырожденном случае возникает зацикливание, то по аналогии с пунктом 3 р 4.1 применяется специальное правило выхода из цикла).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
