Главная страница
Навигация по странице:

  • 2. Основн. формы ЗЛП. Правила сведения ЗЛП к канон.форме. Геометр.интерпретация ЗЛП. Понятие угловой точки мн-ва.

  • 3.Критерий угловой точки множества. Пример .Рассмотрим задачу в канонической форме: (1), (2) . Теор(Критерий угловой точки)

  • Достаточность

  • 4. Определение базиса угловой точки. Невырожденные угловые точки. Примеры. Опр

  • 6. Формула приращения целевой функции ЗЛП.

  • Замеч

  • 7. Достаточное условие оптимальности в ЗЛП. Достаточное условие неразрешимости ЗЛП И

  • Достаточное усл. оптимальности: Т.

  • 8. Итерация симплекс–метода

  • 9. Обоснование конечности симплекс – алгоритма

  • 10. Обоснование непустоты мн-ва планов в ЗЛП. Пример .(1) Рассм след вспомог задачу: Введем в рассм искусств перемен , ()=y≥0. Т.к. мн-во : (2)

  • 11. Нахождение базиса угловой точки. Пример Рассм след вспомог задачу: Введем в рассм искусств перемен , ()=y≥0.(1)

  • 1 случай

  • шпоры методы оптимизации. Задача матго программирования (змп) заключ в нахождении min фии f ( X ), если. (1) Под реш змп понимают


    Скачать 1.38 Mb.
    НазваниеЗадача матго программирования (змп) заключ в нахождении min фии f ( X ), если. (1) Под реш змп понимают
    Анкоршпоры методы оптимизации.docx
    Дата29.01.2017
    Размер1.38 Mb.
    Формат файлаdocx
    Имя файлашпоры методы оптимизации.docx
    ТипЗадача
    #1070
    страница1 из 5
      1   2   3   4   5

    1.Понятие решения задачи мат. программиров.

    Пусть на некотором мн-ве задана скалярная ф-я f(x), точки назыв допустимыми, а X – допустимым, f(x) – целевая ф-я.

    Задача мат-го программирования (ЗМП) заключ в нахождении min ф-ии f(x), если . (1)

    Под реш ЗМП понимают:

    1. найти точку min ф-ии f(x) на мн-ве X, т.е. найти : или (3) или (4)

    2. найти точную нижнюю грань ф-и (5)

    Пусть

    Если , то найдя одно из значений (2) – (4), то автоматчески решается зад (5)

    Если , то (5) приобретает самостоятельное решение

    1. Убедиться в том, что ф-яf(x) неограниченна снизу на X, т.е

    2. убедиться в том что

    В случаях 3) – 4) говорят что задача (1) не имеет решений

    2. Основн. формы ЗЛП. Правила сведения ЗЛП к канон.форме. Геометр.интерпретация ЗЛП. Понятие угловой точки мн-ва.

    В ЛП выделяют 2 основных формы задачи:

    1. Каноническая форма ЗЛП



    2) Нормальная форма ЗЛП

    Можно перейти от одной задачи к другой.

    Любая ЗЛП сводится к канонической с помощью:

    1. если в исходной постановке ищется min целевой ф-ии , то –(c,x)превращает исх задачу в задачу о max.

    2. если , то соотв ограничения умножаем на (-1), чтобы превратить правую часть в положительную.

    3. если m0, т.е. в исх постановке присутствуют огранич нер-ва то вводятся и ограничение нер-ва приводят к виду

    и

    переменные назыв свободными, они характеризуют величину неиспользованного ресурса.

    1. если на некот переменную не наложено ограничение на знак, то делают замену c соотв изменением целевой ф-и, если то замена

    2. в некот задачах м присутствовать двусторонние прямые ограничения , тогда правое нер-во относится к основным ограничениям и применяют 3)

    3. двусторонние прямые огранич вида сводятся к или соотв изменениями в целевой ф-и

    Рассм задачу ЛП внорм форме:

    Если множество планов выпуклое, тогда решение сущ., то найдется хотя бы 1 угл.т. мн-ва в которой это решение достигается.

    УГЛОВОЙ ТОЧКОЙ мн-ва наз. точка xX, кот не может быть представлена как точка отрезка

    для любых произв т.

    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), она имеет единичный базис.










    0

    0

    0

    0

    0

    -1




    Сб



    СЧ
















    0



    80

    14

    15

    18

    1

    0

    0

    14/3

    -1



    4

    5

    7

    2

    0

    -1

    1

    4/7->









    -5


    -7



    -2


    0

    1

    0
















    0

    0

    0

    0

    0

    -1

    Сб



    СЧ













    0



    500/7

    23/7

    0

    96/7

    1

    15/7

    -15/7

    0



    4/7

    5/7

    1

    2/7

    0

    -1/7

    1/7









    0

    0

    0

    0

    0

    1

    ;

    Базис точки не содержит искусственной переменной поэтому совпадает с базисом угловой точки мн-ва X.

    Для завершения решения задачи, во второй таблице удаляем ∆-оценки, заменяем коэффициент целевой функции на коэффициент целевой функции исходной задачи. Если не предполагается дополн. анализ задачи, то столбцы искуссст. перем. можно удалить.










    -3

    -2

    -6

    0

    0

    Сб



    СЧ











    0



    500/7

    23/7

    0

    96/7

    1

    15/7

    0



    4/7

    5/7

    1

    2/7

    0

    -1/7




    J=-8/7




    11/7

    0

    38/7

    0

    2/7
      1   2   3   4   5
    написать администратору сайта