шпоры методы оптимизации. Задача матго программирования (змп) заключ в нахождении min фии f ( X ), если. (1) Под реш змп понимают
 Скачать 1.38 Mb.
|
|
1.Понятие решения задачи мат. программиров. Пусть на некотором мн-ве задана скалярная ф-я f(x), точки назыв допустимыми, а X – допустимым, f(x) – целевая ф-я. Задача мат-го программирования (ЗМП) заключ в нахождении min ф-ии f(x), если . (1) Под реш ЗМП понимают:
Пусть Если , то найдя одно из значений (2) – (4), то автоматчески решается зад (5) Если , то (5) приобретает самостоятельное решение
В случаях 3) – 4) говорят что задача (1) не имеет решений 2. Основн. формы ЗЛП. Правила сведения ЗЛП к канон.форме. Геометр.интерпретация ЗЛП. Понятие угловой точки мн-ва. В ЛП выделяют 2 основных формы задачи:
2) Нормальная форма ЗЛП Можно перейти от одной задачи к другой. Любая ЗЛП сводится к канонической с помощью:
и переменные назыв свободными, они характеризуют величину неиспользованного ресурса.
Рассм задачу ЛП внорм форме: Если множество планов выпуклое, тогда решение сущ., то найдется хотя бы 1 угл.т. мн-ва в которой это решение достигается. УГЛОВОЙ ТОЧКОЙ мн-ва наз. точка xX, кот не может быть представлена как точка отрезка для любых произв т. 3.Критерий угловой точки множества. Пример. Рассмотрим задачу в канонической форме: (1), (2). Теор(Критерий угловой точки):Обозначим ч/з столбцы матр.А, тогда основные ограничения в системе (2) можно записать в виде: . Предположим, что матр.А в системе (2) имеет , т.е. матр.А ненулевая.Для того, чтобы точка была угловой точкой – G необходимо и достаточно, чтобы сущ. , что справедливо рав-во: (3), если и – ЛНЗ. Док-во: Необходимость:Пусть – угловая точка этого мн-ва. а) . Т.к. матр. А в соотношении (2) невырождена, то сущ. r ЛНЗ векторов , то выполнено . т.е. (3) справедливо; б) тогда основные ограничения в (2) превратятся в равенство: (4). Рассм. Рав-во (5). Построим точки и след. обр.: т.к. ,то к рав-ву (4) прибавим и отнимем рав-во (5) умноженное на получим что выполняются рав-ва: , т.е. Легко видеть , но х – угловая точка след-но след-но в (5),т.е.вектора – ЛНЗ след-но Если , то (3) – доказано, если , то к векторам можно добавить вектора так, чтобы – ЛНЗ, тогда (3) примет вид: . Достаточность: пусть для точки справедливо (3): – ЛНЗ, где . Предположим, что , что (6). Покажем, что (6) возможно только при. Рассмотрим нулевую координату точки х: , т.е. . Докажем (6) для тех координат, которые больше 0. Положительными коор-ами т. х могут быть только те, у которых индекс . Пусть Сл. когда или не исключается, тогда система осн-х огр-ий из (2) преобразуется к виду: . Докажем, что , если . Точки было доказано, что , когда след-но и . Вектора – ЛНЗ, а разложение произвольного вектора пр-ва по ЛНЗ-векторам явл. единственным, след-но для строго пол-ых координат. 4. Определение базиса угловой точки. Невырожденные угловые точки. Примеры. Опр. Система векторов входящие в рав-во , если наз. базисом угловой точки х, координаты наз. базисными, остальные координаты – небазисными. Опр. Если все базисные координаты точки х строго больше 0, тогда точка х называется невырожденной. Следствие. Если точка х – невырожденная угловая точка, то для нее существует единственный базис. Вырожденная угловая точка может обладать несколькими базисами. Пример: – невырожденная угловая точка, проверим это. , , где , . – вырожденная угловая точка, так как при рассмотрении рав-ва , где точка – не является угловой точкой, так как . Зам: Из nстолбцов м-цы А можно выбрать r ЛНЗ столбцов конечным числом способов, поэтому число угл.т. мн-ва Х конечно. 5. Связь между переменными задачи ЛП Пусть ,Аm*n,. Из системы осн. ограничений можно удалить ЛЗ ур-я, тогда . Если , то система имеют единств. решение. Если это реш-е не уд. прямым огр-ям, то , иначе . Рассм . Найдена угл. т-ка , - базисные компоненты,. Базис состоит из - ЛНЗ. Обозначения: Умножим на : Т.к. у – угловая, то , т.е. . Рав-во м. привести в виду . Из определения В (*) примет вид: . Из (3) выражаем - (4), обозначаем (3) перепишем в виде:(5) (3), (4), (5) – зависимость между базисными и небазисными переменными. 6. Формула приращения целевой функции ЗЛП. Рассм знач целев ф-ии в некот точке , т.е. , На основании того, что y есть угловая точка, имеем рав-ва Поэтому (1), где Вектор в-р оценок. Он имеет размерность n − r. Заметим, что величины имеют смысл и при k = . Действительно, при k= по определению обратной матрицы имеем , где через обозначен единичный вектор с единицей в k-ой координате. Поэтому Замеч: Величина имеет смысл и для k=1,…,r; действительно, - единичный в-р Замеч:Величина полностью определяются коэф. матрицы , в-ра и бази-сом угловой точки , при этом не зав-т от в-ра ресурсов Замеч: Из (1) виден физический смысл оценок. Величины представляют собой взятую с обратным знаком скорость зменения целев ф-ии при изменении i-ой небазисной переменной. 7. Достаточное условие оптимальности в ЗЛП. Достаточное условие неразрешимости ЗЛП Исходную задачу , можно переформулировать след. обр.: найти максимум ф-ции , где при ограничениях: , где и неотрицательности. Будем искать некот. точку , в которой не уменьшится по сравнению с найденным знач. в точке y. Выберем некот. небазисную перем. , и будем подбирать для нее неотрицат. значения. Остальные базисные перем. , , . Тогда соотнош. примет вид:, а выражение целевой ф-ции . Достаточное усл. оптимальности: Т.: Если , то план y является оптимальным. Рассм. произв. точку и целев. ф-ю Достаточное усл. неразрешимости: Т.: Если найдется небазисная переменная точки упри,к=r+1,n, то целевая ф-ция неограниченно возрастаетна Х. Док-во: в усл. Теор. Любой выбор полож. Небаз. Коорд. Приводит к построению точки, удовлт. Всем огр-ниям задачи, увеличивая только знач Хк, а остал оставляя без изм-ия, можно неогр увелич зн целевой ф-ции. 8. Итерация симплекс–метода Пусть такие номера i, k: и . В силу того, что , а , то знач. цел. ф-ции будет увел. Т.о. выбирается s() такой, что . Эл.наз. ведущим (разрешающим), i-ая строка и k-ый столбец – ведущими (разрешающими). В качестве знач. перем. . Пост.по ф-лам след.обр.: , ,, , , …, , , . , т.е. n-rкоорд. нулев. Не равн. 0 коорд. имеют инд.: 1,...,s-1,s+1,…, r, k. Рассм.лин.комб. (*). Покажем, что (*) может принимать знач. =0 только при усл., что все . Рассм. , тогда (*) предст. в виде: . Последняя сумма предст. собой лин. комб. ЛНЗ векторов ; , . След-но, вектора стоящие при базисных коорд. точк. - ЛНЗ. , где , Выражая из s-го ур-ния (**) знач. перем. и подставляя полученное выражение в остальные ур-ния (**) получим зависимость между базисными и небазисными коорд. точк. 9. Обоснование конечности симплекс – алгоритма. Алгоритм решения з. оптимизации назыв. Конечным, если для его реализации на компе требуется конечное число операций для нахождения оптимального плана. ЗЛП невырожденная, если все угловые точки мн-ва Х невырожденные. Теор. Если в невырожд. ЗЛП известна какая-либо угл. т-ка, то отправляясь от нее либо б. найден оптимальный план, либо б. показано, что цел. Ф-я неограниченна и для этого понадобится конечное число итераций. Док-во. Пусть у – угл. т-ка мн-ва Х. Т.к. ЗЛП невырожд., то . Разрешающий эл-т . Если не вып. достат. усл-е оптимальности , то Т.е. переход к др. угловой точке происходит со строгим возрастанием, а достигается только в 1 строчке, т.е. выбор координаты, выводимой из базиса однозначный. Число угл. т-к конечно. Из всего этого следует конечность симплекс-алгоритма. Зам:Если задача ЛП явл вырожденной, то в сл выбора вырожд угл точки х может произойти зацикливание, которое будет явл следств, изменения базиса вырожд угл точки. 10. Обоснование непустоты мн-ва планов в ЗЛП. Пример. (1) Рассм след вспомог задачу: Введем в рассм искусств перемен , ()=y≥0. Т.к. мн-во : (2) И рассм задачу: (3) В покоординатной форме ограничения (2) им след вид Замеч: 1). Если вектор ,то система основных ограничений(2)переходит в сис-му основных ограничений (1) 2). Мн-во , т.к. 3). Т. явл. угловой точкой мн-ва Z с базисом 4). Целев ф-ия , т.о. зад (3) – есть ЗЛП в канонической форме, к кот удобно применить симплекс метод, при этом в силу огр-ти целев ф-ии на Z зад (3) обяз-но им решение. Непустота мн-ва планов Пусть - реш зад (3) и знач целев ф-ии зад (3). Возможны 2 случая: 1. ; 2. Теорема: Если , то угловая точка этого мн-ва. Док-во:1)Это означает, что вектор y*,..,z* имеет строгополож координаты, тогда мн-во Х явл пустым. Действ, если мн-во Х пустым не явл, то в этом мн-ве найдется некоторая точка y, Ay=b, y≥0. Но тогда т z’=(y,0)пренад Z,а знач цел.ф в ней =0, что против предполож о том , что т z*явл решением задачи. 2)Рассм случай, когда из подстановки в зад (3) полагаем, что и в силу того, что . Покажем, что -угловая точка X: . Построим точки тогда , но - угловая точка мн-ва Z, решение ЗЛП (3), полученное симплекс методом послед рав-во возможно, когда -угловая точка мн-ва X. 11. Нахождение базиса угловой точки. Пример Рассм след вспомог задачу: Введем в рассм искусств перемен , ()=y≥0.(1) Т.к. мн-во : (2). И рассм задачу: . Если Г1(z*)<0?,то исх задача имеет несовместную с-му ограничений. Далее будем считать Г1(z*)=0 1 случай: В симплекс-табл в мн-ве базисных пер-нных отсутсв.искуственные, то полученную таблицу можно исп. в кач-ве исходной для применения симплек-метода в реш первонач зад. .2 случай: В с-т в соответ точке z*присутствуют искуственные переменные в списке базисных, но при этом все коэф, стоящие в строке, соответ этой искуств перем-ой и столбцам, соотв основным, перем =0, то соответс-ющие огра-ия явл линейной комбинацией ур-ний из с-мы Ах=в и это огр-ия следует удалить. Если в с-т реш зад (2,3)искуственные переменные присутствуют в мн-ве базисных и при этом в строке соответ. Этой искуственной переменной найдется положительный элемент, стоящий в столбцах соотв основ небаз пер-ным, то выбрав этот элемент в кач-ве разреш, следует перещитать с-т с целью перехода к другому базису, рассматрив угл точки. В оставшихся сл в мн-ве осн. Перем, по опред правилам выделяем переменные, значение которых для выполнения задачи могут быть только =0 Пример 1. Угловая точка мн-ва планов вспомогательной задачи легко определяется. Это точка x=(0; 0; 0; 80; 0; 4), она имеет единичный базис.
; Базис точки не содержит искусственной переменной поэтому совпадает с базисом угловой точки мн-ва X. Для завершения решения задачи, во второй таблице удаляем ∆-оценки, заменяем коэффициент целевой функции на коэффициент целевой функции исходной задачи. Если не предполагается дополн. анализ задачи, то столбцы искуссст. перем. можно удалить.
|