И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 43
Текст из файла (страница 43)
1". Случай неограниченности множества Хт. Предположения 1' (1).— Множество Х', определяемое условиями (4.11) — (4.12)— !Ао1 неограничено; (!!) — гапд ~,] = т + т,; (!!!) — т + т,( и. Обозначим через х', ! 1, ..., 1,, вершины множества Х', а направляющие векторы неограниченных ребер Х' через х '+, х'+', ... х. Если выполняются предположения 1', то исходная задача 1 сводится к решению г-задачи, в которой условие (4.14) следует заменить на с Езг =1 к з гдее,= 1 при!=1;2, ..., 1,;е;=Опри1=1+1, ...,1. Кизмененной г-задаче можно применить алгоритм 1 со следующими изменениями: поскольку на шаге ЧП алгоритма 1 подзадача Хл не всегда разрешима (целевая функция может быть неограниченной на множестве Х'), то возможны два случая: 1') оптимальное решение хч подзадачи Хл существует; 2') при решении подзадачи Хл есть оценка Ь; ( О, для которой все им ( О, А = 1, ..., т, (т.а.
целевая функция подзадачи Хл не огранйчена сверху). В случае 1' шаги алгоритма 1 останутся без изменений. В случае 2' шаги 1 — Ч1 останутся без изменений, а на шаге Ч1! алгоритма 1 в качестве вектора х' выбирается и-мерный вектор, у которого кооРдинаты с номеРами 1,, 1,, ..., 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, ..., з — матрица размера т, х и,. Исходная задача линейного программирования записывается в ниде. 5 Зада ч а 2. Найти ага шах ~; (с', х') при ограничениях г е ~~.", А~х' = Ье, (4.17) А,х' = д', ( = 1, 2, ..., з, х' ~ О, С = 1, 2, ..., з, (4.19) (4.19) 223 Метод разложения, описанный в предыдущем пункте, особенно эффективен при специальной блочно-диагональной структуре матрицы А' в задаче 1: А, О ...
О Ф где х — и;мерный вектор-столбец; Ас — — (сссс) — матрица размера о со. т Х и;, А,= (ас>) — матРица РазмеРа тсХ и;, Ьо — и>-меРный вектор-столбец; Ь' — л>с-мерный вектор-столбец; с' — пс-мерный вектор- строка; х = (х', х', ..., х'). Решение задачи 2 сводится к решению следующей аадачи л1 линейного программирования размера (сп + з) х 1~1 = Е 1> ' с > » х;задача.
Найти агя шах ~ ~'„асх( при ограничениях сс с=> с с ~~ Р~ох; = Ь > (4.20) с=>с > ~ е!гс = 1, 1 = 1, ..., з; (4.20 г>с~0, >=1 2» ° » 1>', 1=1, 2» ° ° ° з» (4.22) с . с ос. с где ос с= (с, хсс>); Рш — — Асхш, хйь 1 = 1, ..., 1с при каждом 1Е Е П: з) — соответствует вершинам и направляющим векторам неограниченных ребер многогранного множества 6„6, 1> (х' ~ А,х' = = Ь', х' ~ 0)„(предполагается, что при с Е [1: 1>), хс~о соответствует вершине, а при с Е ((1с + 1): 1с) — направляющим векторам неограниченных ребер 6с); 1, если х,'„соответствует вершине множества 6с, О, если х,'„ соответствует бесконечному ребру множества 6,. Для удобства записи ограничения (4.20) и (4.21) перепишем в виде где Рю Ь ° здесьос — з-мерный вектор с единицей на 1-м месте; 1, — з-мерный вектор с единичными компонентами.
Оптимальное решение г,-задачи однозначно определяет опти*с мальное решение задачи 2, т. е. если числа >и определяют решение г;задачи, то векторы ° с с с с хс = ~~ ~гсхсс>» 1 = 1, ..., з» (4.23) 224 составляют оптимальное решение х* = (х', х', ..., х') (б.зб1 задачи 2. Для решения г,-задачи нет необходимости знать заранее все вершины многогранников 65, 1 = 1, ..., з (необходима лишь информация о вершинах, входящих в исходный базис).
г5-задача распадаегся на з (по числу блоков) подзадач размера т5 х пь =1„..., з, каждая из которых решается модифицированным симплекс- методом. Оптимальные значения линейных форм этих подзадач используются для проверки опорного решения гмзадачи на оптимальность и для обновления базиса г5-задачи, если исследуемое опорное Решение не оптимально. Алгоритм 2 Н а ч а л о.
1. Найти исходный базис г5-задачи 55>+5 >~!1»»"!1*5> ' »'5>»>+5>> базисные переменные опорного решения г,-задачи, отвечающие этому базису, 55>+5 ° > аб +5 и коэффициенты линейной формы г5-задачи, отвечающие исходному базису, а„о,, ...,о,+,. П. Вычислить матрицу В ', обратную к матрице, составленной из базисных векторов р ", й = 1, ..., т + >л аь)' ! / 5,...,5+5> = (()п)5-!;:".,~ !,. Ос н о в н о й ц и кл.
11[. Положить 5гб„= (о!5'„..., а' .!'). й»+5 1Ч. Вычислить вектор Л А! (Л', Л') = ()!б5, ..., Х„'„)>~!, ..., Л',) по формуле ! Л = оба>В Ч. Положить у>б = г,.", й = 1, 2, ..., т + а, Ч1. Положить 1= 1. Ч11. Решить следующую задачу линейного программирования размера т, х а5 (Х'б!-задачу): найти аги шах (с' — Л'Аб, хх) при ограничениях А!х'=Ь', х ~0 (при этом считаются известными вершины х!5,', х';,*, ..., х""+'. бб+5' З 555! Процесс решения Хь-задачи может закончиться одним из двух ис((( ходов: исход 1о — Ха('(-задача разрешима; исход 2о — линейная форма Х7-задачи неограничена на множеатве 6().
Если Х(("-задача разрешима, то обозначить ее решение через х~(„р и перейти к шагу ЧП1; если Х~к'-задача неразрешима (т. е. линейная форма ХР-задачи неограничена на множестве С((), то обозначить через х(о(> направляющий вектор неограниченного ребра множества 6„порождающий вектор р<,(> с отрицательной оценкой Л.п и перейти к шагу 1Х. (Правило выбора такого х((„„описано в пункте 1). ЧП1. Вычислить оценку Ь,, — (с — Л А(, х(„р)+)о( ( ( о ( 2 я перейти к шагу Х. 1Х.
Вычислить оценку Ь„, по формуле с ( о ( Л,, = — (с — Л А(, х(,()) и перейти к шагу Х. Х. Если 1(з, то положить г 1+ 1 и перейти к шагу ЧП; иначе перейти к шагу Х1. Х1. Если выполняется условие пп'п Л'„О, (4.25) (еню то исследуемое опорное решение и баяно з,-задачи оптимальны; в этом случае найти оптимальное решение исходной задачи 2 по (4.23) — (4.24), где г( равны соответствующим базисным переменным г;задачи при 1= 1м 1 (м й 1, ..., л(+з, их( О, в противном случае (векторы х(, соответствующие номерам базисных перес менных, тоже известны), и прекратить вычисления. Если условие (4.25) не выполняется, то перейти к шагу Х11.
На последующих шагах алгоритма осуществляется переход н новому базису г(-задачи. ХП. Вычислить индекс р Е П ( з1, для которого выполняется Л,„ш(п Лог (о(1(ч Х1П. Вычислить (т+ з)-мерный вектор р(",„> и соответствующий коэффициент линейной формы з;задачи ~ о о /А„° х(,„Д р(".,с - о 9 ° 1 очи (з"е х(оо)).
~о Х1Ч. Вычислить вектор (т. е. вычислить коэффициенты разло- ження вектора ры ~ по базисным векторам) г 1-н (ую . ю УО4+ен) В р(тн) индекс г с П: (т + в)1, удовлетворяющий , ХЧ. Вычислить условию У4у н = ш! и (уесlуен) у, ) О. Рен>0 ХЧ1. Положнть()У = Ди, 1 1, ..., т+ з; 1= 1, ..., т+ з, яусс=ум, 1=1, ..., т+з. ХЧП. Перейти к новому базису р~)н ..., р<',"+ем который полУчаетсн заменой вектоРа Р~",~ в пРедыдУщем базисе вектоРом Рнн> (т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
