шпоры методы оптимизации. Задача матго программирования (змп) заключ в нахождении min фии f ( X ), если. (1) Под реш змп понимают
 Скачать 1.38 Mb.
|
|
; ; Минимум целевой ф-ции достигается в точке x=(0; 4/7; 0) мин знач равно 8/7. 12. Постановка ТЗ. Построение нач. плана перевозок методом северо-западного угла, методом мин. элемента. Пусть имеется m пунктов пр-ва однородной продукции с объемами пр-ва аi,i=1,m, и n пункт.потребления этой продукции с потребностями bj, j=1,n и∑i=1mai=∑j=1nbj . Известны стоимости cijперевозки одной еденицы продукции из i-го пункта производства в j-ый пункт потребления. Требуется определить объем перевозок xij≥0 чтобы ∑i=1m∑j=1nсijxij→min при усл, что ∑j=1nxij=aiи ∑i=1mxij=bj ТЗ решается с использованием таблицы спец вида, кот. наз трансп таблицей. Строки соотв пунктам производ, столбцы- пунктам потребления.В правом нижнем углу каждой клетки записыв стоим перев ед прод из i-ого в j-ый.В левй верхний угол запис перевозки, если эти перевозки не нулевые. Сумма перевозки по строкам должны = объему производства, а сумма перевозок по столбцам = объему потребления. Положим x11=min{a1,b1}. Если a1>b1, то излишек a1-b1 завозим из А1 в пункт В2, т. е. полагаем x12=min{a1-b1,b2}. Если a1<b1, то остаток b1-a1 завозим из пункта А2, т. е. полагаем x21=min{b1-a1,а2}. Продолжая действовать по той же схеме, постепенно исчерпаем запасы в пунктах А1, … , Аn и удовлетворим запасы в пунктах В1, … , Вmт. е. получим допустимый план перевозок. Т. к. заполнение таблицы начинается с клетки {1,1} (с северо-западного угла), то метод получил название «Северо-западного угла». Метод минимального эл-та отличается только способом выбора клетки для заполнения очередной перевозки: на каждом шаге выбирается клетка с минимальной стоимостью перевозки. 13. Определение закрытой модели ТЗ. Критерий существования решения ТЗ. Опр: Транспортная задача, для которой выполняется усл (1) наз. закрытой, в противном случае – открытой. ТЕОРЕМА 1:Транспортная задача имеет решения тогда, и только тогда, когда (1)
Док-во. Необходимость. Пусть решение транспортной задачи сущ. , . , Достаточность. Пусть выполняется условие баланса (1) Построим след.план перевозок , Из условия следует, что множество планов является замкнутым. Кроме этого оно является ограниченным. Действительно, если возьмем любую перевозку. Целевая функция является линейной, следовательно и непрерывной. Отсюда по теореме Вейерштрасса решение задачи существует. Замеч.Открытую ТЗ можно свести к закрытой след. обр:
14. Исследование мн-ва клеток транспортной таблицы Мн-во всех клеток трансп. табл. обозначим U Опр. Цепью назовем посл-ность клеток, в которой каждые две соседние клетки лежат в одной строке или в одном столбце, но ни в одной строке и ни в одном столбце нет трех послед.клеток. Опр.Циклом наз. цепь, крайние клетки которой лежат в одной строке или в одном столбце. Замеч.Если в трансп. табл. соседние клетки соединить отрезками прямых (звеньями цепи), то соседние звенья всегда будут перпендикулярны. Опр. Мн-во клеток наз. Базисным , полным, если их кол-во равно m+n-1 и из его элементов невозможно создать ни одного цикла. Все остальные клетки наз. небазисными Опр. План перевозок из i в j наз. базисным, если все перевозки за исключением m+n-1 равны 0, а остальные находятся в клетках, составляющих базисные мн-ва клеток. Опр. Перевозки , где (i,j) наз. базисными, а если (i,j) , то небазисными. Опр. Базисный план наз. невырожденным, если все базисные перевозки строго >0, в противном случае – вырожденным. 15. Достаточное условие минимальности стоимости перевозок ;(1) ; Выпишем ограничения ТЗ = = …………………………… = + + … + = ……………………………… ++ … += Каждое ограничение на предложение умножим на нек. перем величины , a каждое огр на спрос умножим на . Полученное выражение вычтем из целевой ф-ции (1): Выберем значение перем таким образом чтобы выполн рав (2) Решение с-мы (2) назыв потенциалами. С-ма ур. (2) имеет более одного решения т.к. сост из m+n-1 неизв величин. В качестве потенциалов можно выбрать любое решение с-мы (2). Вычислим величины по небазисному мн-ву клеток. ТЕОР.Выполнение нер-ва по небазисному мн-ву клеток (i,j) является достат. для оптимальности плана перевозок. Док-во. Из рав-ва (1) следует, что если значения небазисных перевозок для которых >0 изменить на положит., то ст-ть перевозок увеличится, или не изменится. С другой стороны, если существует <0, (i,j), то путем увеличения соотв. значения перевозки с нулев. на положит.стоимость перевозок можно уменьшить. Изменяя знач. Небазисной перевозки, для кот. <0 необходимо изменить другие значения базисных перевозок т.о. чтобы выполнялись все ограничения задачи и кол-во базисных перевозок осталось равным m+n-1. 16. Классический метод решения задачи безусловной минимизации функции многих переменных. Пример. Под кл. методом подразум. подход к поиску точек экстремума ф-ций многих переменных, кот. основан на дифференц. исчислении. Т1 Вейерштрасса(о достижении верхней и нижней граней непрер. ф-ции., опред-й на огранич. замкнут.мн-ве). Пусть в задаче мн-во , ограничен-е, замкнутое, а ф-ция определена, конечна и непр-на на X. Тогда След.Пусть X - замкнуто, непреп. на X и сущ. Точка ,такая, что мн-во ограничено.Тогда. Т-ма2.Пусть ф-ция диф-ма в точке . Если y есть точка лок-го минимума ф-ции ,то выполн. усл.стационарности . Д-во. Возьмем произв. точку и построим приращение аргумента где . Рассм. Приращ. ф-ции в точке y, которое разложим на основании опред.диф.ф-ции Разделим последнее равенство на и устремим к нулю. В пределе получим нерав-во В соотн.(3) положим из чего получим нерав-во котрое может выпол. Только при усл. Зам1.Точки , для кот. выпол. Рав-во , наз. стационарными. Поиск точек минимума можно начинать с реш-я системы n ур-ний с n неизв-ми величинами Зам2.Не всякая стац. точка явл. точкой лок. экстр. Пример1.Исслед. на экстр. ф-ю двух переменных .Р-е.Выч. градиент данной ф-и Из усл. стац. получаем одну точку (0,0), подозрит. на экстр. Знач. ф-и в стац. т-ке равно нулю: .Но из чего след., что т-ка (0,0) эктр. не явл.Т-ма3.Пусть ф-ция дважды диф-ма в точке . Если у есть точка лок. миним. зад. (1),то матрица , составленная их вторых частных производ. ф-ии f в точке y, неотриц. Определена,т.е. для всех вып. нер-во Д-во Рассм. Приращение цел. ф-ии в т. y соотв-щее приращ. аргум. где малое, - произв. в-ор Т.к. ф-я f дважды диф., тосправедливо Т4 (достат.усл.оптим-ти). Пусть в з.(1) ф-я f(x) дважды диф-ма. Т-ка строго полож.опред-на,т.е. .Тогда y есть решение з.(1) Док-во. Пусть в т. у вып-ны усл-я т-мы, но т. y не явл. Реш. з.Это означает, что сущ. Посл-ть точек Представим , . Рассм. и учтем Получим Получим противоречие, кот. док-ет т-му.Пример.Исслед. на экстр. ф-ю .Строим матрицу 2-х произв.Подст. по крит.Сильвестра полож.опред. Т. т-ки минимума. ..Квадр.ф-я не явл. знакоопред. поэтому не вып-но необход.усл.2-го порядка и в т-х нет экстр.В т-ме3 и т-ме4 при исслед.з. на max знакоопред-ть квадр-й формы следует поменять на противоположную. 17. Метод исключения решения задачи на условный минимум. Пример. Рассм.(1) (2). Предпол-ся, что ф-ции определены и имеют производные 1-го порядка на всем пр-ве . Если систему ограничений (2) можно представить в виде , то зад. (1),(2) свод-ся к зад. безусловной минимизации.. Теорет-я возможность применения такого метода исключ.основывается на т-ие о неявных ф-ях. Т1 о неявных ф-циях. Пусть рассм. m-мерная ф-ция .Изв.т.,для кот. ,тогда сущ. m-мерная ф-я , уд.усл.:1);2);3.имеет в непрер-е производные того же порядка, что и ф-ция по . Т2. Метод искл.реш-я в з. (1),(2)применим, если в окрестности точки минимума ф-ции ф-ции диф-мы и . Д-во: Из усл.(3)=>что у м-цы сущ.хотя бы 1 ненулевой минор порядка m.Предпол-м, что минор распол-ся в первых m строках этой матрицы.В противном случае переобозн. переменные.В принятом предпол-и обозн. Первые m компонент в-ра x через z, а ост-е n-m компонент через в-ор u.Набор ф-ий тогда обозн. ч/з . Тогда система огран-ий примет вид и для этой ф-ии в т. вып-ны все усл. т-мы1. Замечание. Возможность прим-ия метода искл. сущ-но огранич-ся сложностью решения с-мы урав-ий в явном виде. Пример1.Исслед. на экстр. ф-ю . ; ; ; (0;-2)-стац точка. -знакопеременна(не вып.необход.усл. 2-го порядка).Т.(0,-2) не явл.экстр-й для ф-ии g..Исх.ф-я экстремума не имеет. 18. Обобщенное правило множителей Лагранжа в задаче оптимизации с ограничениями типа равенств. Ф-ей Лагранжа в з.(1), (2) наз. ф-ия Вектор наз. в-ом множ-лей Лагранжа, -обобщенным в-ом мн-лей Лагранжа. Т-ма1(обобщ.правило мн.Л.) Пусть точка явл реш-м з.(1),(2), и пусть ф-ции непр-но диф. В окрестности т. ,тогда сущ. Такие числа что Д-во. Т.к. в рав-ах (3) - ЛЗ.Предпол-м прот-ое. Пусть система векторов (4) ЛНЗ.Тогда их кол-во не превосходит размерности пространства, т.е.. Если , то систему в-ов(4) дополним нек-ми векторами так обр., чтобы получ.с-ма в-ов (5)оставалась ЛНЗ. Построим ф-ии, зав-щие от переменных x и t: , ; .Рассм. Тогда по т-ме о неявныхдля ф-циях найд. ,для которой вып.усл.1)Т.е. ф-ия удовлетворяет ограничениям з-чи и при т.е. нашли такую ф-ю удовл-щую огран-ям з-чи в кот., знач. цел.ф-ии строго<чем тому ,что -явл. реш-м з.(1),(2). Зам1. Поиск точек мин-ма начинается с реш-я с-мы уравн-й относительно -переменной величины, состоящей из урав-й(3) и урав-й из (2). Если есть решение с-мы(3), то явл. реш-м ур.(3). Т.е.множ-ли Лагранжа удовл-щие соотнош.(3) опред-ся с точностью до постоянного множителя, поэтому при реш-ии с-мы необ-х условий согласно обобщ-му правилу множ-лей Лагранжа дост-но рассм-ть случаи 19. Классическое правило множителей Лагранжа в задаче оптимизации с ограничениями типа равенств. Необходимые условия второго порядка в задаче оптимизации типа равенств. (1) (2) Опр. Задача (1),(2) наз нормальной в точке , если среди обобщенных векторов множ-лей Л., соотв. в точке нет таких для кот. , то вектор в таком случае наз. норм-ным. Опр. Точка наз. обыкновенным планом для задачи (1)-(2), если -ЛНЗ(3). Усл. (3) наз. условием Люстерика. Т-ма1Оптим. план для з.(1),(2) явл нормальнам тогда и только тогда, когда он обыкновенный. Д-во:Пусть -оптим. норм. план. Это значит, что сущ. вектора Среди которых Предположим, что при этом не явл. обыкновенным, это означает – ЛЗ.Тогда соотнош.(4) возможно при усл. , что -нормальный план. Пусть план явл. обыкнов., тогда вектора -ЛНЗ. План явл. оптимальным, то согласно обобщ-му правилу множ-лей Лагранжа сущ. множитель (,),что вып. рав-во . Предпол., что план не явл. не явл. нормальным. Но в силу того, что среди множ-лей Л. есть не нулевые из (5) следует что градиенты огран-ий ЛЗ, что противоречит обыкновенности плана . Т-ма2(классич. правило мн. Л.) Пусть оптим. План з-чи (1),(2) и пусть при , ограничений -ЛНЗ. Тогда сущ. ед-ный в-р множ-лей Л. (), такой, что справедливы рав-ва (6). Док-во. В усл. т-мы 2 план явл обыкн., след-но по т-ме 1 норм., тогда 1 из усл.(6) есть усл. из обобщ-го правила множлей Л. при условии, . , 2 из (6) совпадает с системой ограничений. Т-ма3.(необх. Усл. 2-го порядка) Пусть ф-я зад. (1)-(2) дважды непрерывно диф., если т. явл. т. лок. мин-ма этой з-чи и явл. обыкн-й т. с-мы огран-й и есть соотв. В-р множ-лей Л., тогда квадр-я форма, составленная по вторым произ. ф-ции Л. по переменным задачи выполненным в т. не отриц. опред. Для всех в-ров удовл. условиям (7), т.е. для всех в-ров удовл.(7) выполн.(8). 20. Достаточные условия экстремума в задаче оптимизации с ограничениями типа равенств (1) (1) Т-ма1 Пусть в задаче (1),(2) ф-ции дважды непр-но диф. Пусть точка удовл. класс-му правилу множ-лей Л., т.е. сущ. , что и пусть квадр-я форма вторых произв. ф-ции Л. в т. строго полож. опред. для всех ненулевых векторов удовл. усл. , т.е. для всех в-в удовл.(3) выполн. нер-во Тогда явл. т-кой строгого лок. минимума по задаче (1)-(2). 21.Опр-ия выпуклого мн-ва, выпуклой функции. Св-ва выпуклых множеств. Сумма выпуклых функций. Св-во неотрицательности остатка выпуклой функции (1) (2) Если ф-ция явл. выпуклой на выпуклом мн-ве X, то задача (1), (2) наз. задачей выпуклого программирования. Опр: Мн-во наз выпуклым, если для любых двух точек отрезок, соединяющий эти точки полностью принадлежит этому мн-ву, т.е. Примерами выпуклых мн-в могут служить шар произвольного радиуса, гиперплоскоть, все пр-ва. Опр: Ф-ция , определенная на выпуклом мн-ве Х, наз. выпуклой, если для выполняется (1) Замеч1: Если мн-во X явл. пустым или состоит из одной точки, то ф-цию, определенную на таком мн-ве, считают выпуклой. Замеч2: Если знак нерав-ва в (1) заменить на противоположный, то ф-ции наз.вогнутой. При выполнении строгого неравенства ф-ция наз. строго выпуклой(Соответственно строго вогнутой ). Примеры.
УТВ:сумма пересеч и умнож мн-ва на число явл. выпуклым мн-вами,если исходные мн-ва-выпуклые. Пустое мн-во и мн-во состоящ из 1 точки удобно считать выпуклыми. УТВ: сумма выпуклых ф-ций есть вып ф-ия. Т1(сво-во неотрицательности остатка)Пусть ф-ция явл. выпуклой, дифференцируемой на выпуклом мн-ве Х, тогда выполняется Док-во: Т.к. ф-ция явл.выпуклой, то . Т.к. ф-ция явл. дифференцируемой, то приращение этой ф-ции можно разложить в ряд Тейлора: (*)= Последнее неравенство делим на и устремим к 0. Теорема доказана. 22.Теорема о точках минимума выпуклой функции. Теорема о стационарной точке выпуклой функции Теор(о т. мин в-ой ф-ии): Пусть в задаче (1)-(2) ф-ия выпукла, определена на выпуклом мн-ве Х, тогда: 1) каждая точка ее локального минимума (если такая сущ-ет), явл-ся точкой глобального минимума; |