И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 38

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 38)

Для нахождения исходного базиса и опорного решения используют, алгоритм 2: 11. Разложить по исходному базису ас, а'*, ..., ас векторы по, а', ..., а" (т. е. найти числа гм, й = 1, 2, ..., лс; 1 О, 1, 2, ..., а, такие, что ае = гсеа' + гтеас*+ ° " + г ог'к; от =гыас +гтсас ° + ° ° ° +г са аа = гма' + гт„асв + ° ° ° + г„„а «) по формулам ! 1 а1ч = Х1,, 'Хм = Хся ° ° ° э алвО = Х! т Т (гп, гз/, ..., Х,ч) =В (а!/, аз/, ..., а /), /=1, ..., а.

Отметим, что заранее известно разложение по исходному базису базисных векторов а'ь, й = 1, ..., пп ги = О при й ~1; хп = 1 при Й = 1, А = 1, 2, ..., т; 1 1,2,...,т. Ос н о в н ой ц и к л. П1. Для каждого / ~ [1: а[ вычислить оценку ш Ь = х,! С!ах/ — С. (4.3) А ! 1Ч.

Если все Л! ~ О (/ = 1, ..., и), то положить х*= х' и прекратить вычисления (в этом случае опорное решение оптимально и оптимум целевой функции равен 1„с! га!); а 1 если при некотором / р [1 и[ выполняется Ь1( О, то перейти к шагу Ч. Ч. Положить / = 1. Ч1.

Если /ь/~ О, то перейти к шагу ЧП; иначе перейти к шагу ЧП1. ЧП. Если при всех й Р [1: л![ выполняется неравенство г„( О, то прекратить вычисления (в этом случае целевая функция (с, х) не ограничена (сверху) на допустимом множестве Х); иначе перейти к шагу ЧП1. ЧП1. Если /(п, то положить / = /+ 1 и перейти к шагу Ч1; иначе перейти к шагу 1Х. 1Х. Выбрать по заранее оговоренному правилу индекс ар Е П: л[ такой, чтобы Л, ( О. Обычно на практике за Л, принимают или наименьшую из отрицательных оценок Л/, илн же отрицательную оценку Ь/ с наименьшим индексом /.

Х. Вычислить отношение г!в/гм для тех й, для которых гм ) О, и обозначить минимальное из этих отношений через Ом Найти индекс г Е [1: т[ такой, что г„) О и г,0/вм = 0м Х!. При каждом /Е [1: а[ вычислить О1 —— г„/г„. ХП Положить гь/ = хць й = 1, ..., С1; / = 1, ..., и. Х1П Перейти к новому базису, который получается заменой вектора а ' в предыдущем базисе вектором а' (т.

е. положить 1, = з). Х1Ч. Вычислить координаты всех векторов а', а1, ..., а" в новом базисе по основным формулам: 7э 195 при наг гм=гм — О~его )=О, 1, ..., п; 2=1, ...,г — 1,г-1-1, ...,т; при я = г г„=йн )=О, 1, ..., ХЧ. Перейти к новому опорному решению х' (х~ь ..., х~)~ х,' =гзе~ я=1„..., п1, остальные координаты вектора х' равны нулю.

ХЧ1. Перейти и шагу П!. Теорема 1. Если выполнены предположения О и задача О невы- рожденная, то через конечное число итераций процесс решения за- дачи О алгоритмом 1 закончится либо на ишге П/ (в етом случае находится оптимальное решение задачи О), либо на шаге и'П (в етом случае устанавливается, что оптимального решения задачи О нет). Замечание 1. Оценки Ьр Г' = 1, ..., и, целесообразно вычислять по формуле (4.3) только на первой итерации. На последующих ите- рациях новую оценку Л~ следует вычислять через старую оценку Ьи полученную на предыдущей итерации, по формуле Ь~ Ь,— 8Д„)=*1, 2, ..., и.

2. Методы отыеиеиив иезодиого базиса А. П е р в ы й метод. Пусть исходная задача линейного программирования имеет виш 3 ад а ч а 2. Найти агя шах (с, х) для заданного вектора с вел (сы оз, ..., с„) и множества Х, задаваемого соотношениями а„х, + ° + аих, + х,+1 = а,; о.

а„х, + + ае„х, + х,ч.з = аз; амх, + ° ° ° + аых, +х„= азо; аз+глхз + ° ° ° + азеь,х, = ао,; а х+ ° ° ° +а х *ао' х~~О, 1=1 ° ..., и. В ограничениях задачи 2 выделены переменные х,+и ..., х„ с различными единичными векторами а*+', ..., а". Если таких переменных в задаче линейного программирования нет, то в задаче 2 следует положить в = и. 196 а« о а х + ° ° ° + амх, + х,.ь1 о =а„; амх, + ° ° ° 1- а«,,х, + х„ «««чшх»+ ' +с««+ах +у« «««+»лх, + " + а«+»,,х, + у, = а««+,, о =а а„ох,+ . ° +и„,х,+ . +у .«=аз", к7 .»О, 1= 1, 2, ..., и; У,~О, 1=1, 2, ..., т — й.

Задача 2' имеет опорное решение (О, ..., О, а«ь а»«, ..., а') с единичным базисом а'+', а'+', ..., а", а"+', ..., а"+ -«, поэтому к ней применим алгоритм 1 — симплекс-метод решения канонической задачи линейного программирования. При этом задача 2' заведомо имеет оптимальное решение, так как ее целевая функция ограничена сверху числом ноль. Переменные у,, ..., У„«называют искусственными переменными, а векторы а ~', ..., а"+ — «вЂ” искусственными векторами. Алгоритм 2 1.

Используя алгоритм 1, вычислить вектор (х«ь х», ..., х„', у«ь ... ..., у «) — оптимальное решение задачи 2' и оптимальный базис задачи 2' — а', аь, ..., а«~и. П. Если хотя бы при одном !' С Ц ~ т — й) выполняется неравенство у) ) О, то прекратить вычисления (в этом случае исходная задача 2 недопустима, т. е. не имеет допустимых решений); если о о о У1 = У» = - = У -« = О, то перейти к шагу 1П. 197 Предположение 2. Ограничения задачи 2 таковы, что а) ~ О, 1=1, ...,т. Лля отыскания исходного базиса и опорного решения задачи 2 в ограничения этой задачи искусственно вводят т — и новых переменных у„у», ..., у «с таким расчетом, чтобы новая система уравнений-ограничений имела полный единичный базис.

Затем с помощью алгоритма ! решают задачу линейного программирования с новыми ограничениями и со специально построенной целевой функцией. В результате решения «новой» задачи приходят либо к опорному решению исходной задачи 2, либо непосредственно к оптимальному решению задачи 2. Кроме того, если исходная задача 2 неразрешима, то это обнаруживается в результате решения «новой» задачи.

«Новая» задача является задачей линейного программирования в пространстве 11"~" (или 11*+"). 3 а д а ч а 2'. Найти ага шах ( — у, — у» †... — у «) ы„...,««,у,.,.,«~ ф«у для множества )', задаваемого неравенствами П!. Если оптимальный базис задачи 2' не содержит искусственных векторов аг, ! = и + 1, ..., и + т — й, то прекратить вычис. пения, так как оптимальный базис задачи 2' является исходным базисом задачи 2, а соответствующие ему значения основных перев о о менных хь хм ..., х„составляют исходное опорное решение задачи 2; если оптимальный базис задачи 2' содержит хотя бы один искусственный вектор аl, ! ~ [п+! ~ и+ т — й[, то перейти к шагу 1Ч.

1Ч. Вектор (хь хг, ..., хв) является опорным решением задачи 2. Для отыскания исходного базиса задачи 2 перейти к шагу Ч. Ч. Если в разложении векторов а1, а', ..., а" по базису а', а'*,,, а" все коэффициенты гм при искусственных векторах равны нулю, то, удалив из системы векторов а', а'*, ..., а искусственные векторы, получим исходный базис задачи 2, который соответ. ствует опорному решению (хвь ..., х„'); иначе перейти к шагу Ч1.

Ч1. Найти вектор а', (в~ П; п[), в разложении которого по базису а', а'*, ..., а'~ есть число г„при искусственном векторе а", отличное от нуля. Ввести в базис вектор а' вместо искусственного вектора а (т. е. положить 1, = з). ЧП. Если в новом базисе. нет искусственных векторов, то прекратить вычисления (в этом случае находится опорное решение задачи 2 и его базис); иначе перейти к шагу Ч1П.

ЧП1. Разложить по новому базису векторы а', ае, ..., а" (как на шаге Х1Ч алгоритма 1). 1Х. Если в разложении векторов а', а', ..., а" по базису а', а", ..., а~ все коэффициенты ге) при искусственных векторах равны нулю, то перейти к шагу Ч; иначе перейти к шагу Ч1. Теорема 2, При выполнении предположений 2 алгоритм 2 за конечное число итераций либо находит опорное решение задачи 2 и соответсомующий ему базис, состоящий из 1 векторов ('! — ранг матрицы А задачи 2), либо успшнавливает, что задача 2 не имеет допустимых решений. Б.

В то р о й метод. Ниже приводится алгоритм отыскания опорного решения задачи О и его базиса, который сводится к решению М-задачи — специально построенной задачи линейного программирования в пространстве Л"+ , содержащей параметр М (здесь М вЂ” достаточно большое ччсло). В процессе решения М-задачи либо устанавливается неограниченность целевой функции задачи О, либо находится оптимальное решение задачи О, либо устанавливается, что задача О не имеет допустимых решений.

Предположение 2'. Ограничения задачи О таковы, что а~~ ~ О, 1=1,2,...,т. Алгоритм 2' 1. Выбрать достаточно большое число М) О. П. Используя алгоритм 1, вычислить вектор (хь ..., х„, уь... о о о 198 ..., у ) — оптимальное решение следующей задачи линейного программирования: М-задача. Найти аго шах ((с, х) — Му,— Му,— ° ° ° — Му ) (кш..имм ...

о ) при ограничениях имх, + а„х, + ° ° ° + аых„+ у, ао. 1' 2' =по; ат,х, + а„х, + ° ° + се~„х„+ у, а~1хт + ам2 че + ' ' ' + чеехе + ум х, «О, 1=1, ..., и; у,~О, 1=1, ...,т. М-задача имеет исходное опорное решение (О, ..., О, ап ..., а ) о о с единичным базисом а"+', ..., а"+, поэтому к ней можно применить алгоритм 1. Если при решении М-задачи алгоритмом 1 окажется, что ее целевая функция неограничена (сверху) на допустимом множестве, то целевая функция задачи 0 также не ограниче. на (сверху) на допустимом множестве Х.

Характеристики

Список файлов книги