- •1. Понятие реш задач мат программирования. Постановка задач линейного программирования. Примеры. 1.
- •2 . Основные формы задача лп. Правило сведения злп к канон форме. Геометр интерпр злп. Понятие угловой точки мн-ва
- •3. Критерий угловой точки множества.
- •4. Определение базиса угловой точки. Невырожденные угловые точки. Примеры.
- •5. Связь между переменными злп.
- •7. Построение симплекс-таблицы. Достаточное условие оптимизации в задаче лп. Достаточное условие неразрешимости задачи лп.
- •8. Итерация симплекс-метода.
- •9. Обоснование конечности симплекс-алгоритма.
- •10. Обоснование непустоты множества планов в злп. Пример.
- •11.Нахождение базиса угловой точки. Пример. Св-во решений злп.
- •12. Свой-ва решений злп.
- •13. Постановка тз. Построение плана перевозок методом северо-западного угла.
- •14.Определение закрытой модели тз. Критерий существования решения тз.
- •Замечание Транспортная задача, для которой выполняется условие (1) называется закрытой, в противном случае – открытой.
- •15.Исследование множества клеток транспортной таблицы.
- •16.Достаточное условие минимальности стоимости перевозок
- •17. Определения выпуклого множества, выпуклой функции. Свойства выпуклых множеств. Сумма выпуклых функций. Свойство Лебега выпуклых функций. Свойство неотрицательности остатка выпуклой функции.
- •18. Теорема о точках минимума выпуклой функции. Теорема о стационарной точке выпуклой функции.
- •20.Классический метод решения задачи безусловной минимизации функции многих переменных. Пример.
- •21.Метод исключения решения задачи на усл минимум. Пример.
- •23.Классич правило мн л в задаче опт-ции с огранич типа равенств. Необходим условия первого и второго порядка в задаче опт-ции типа равенств.
- •24.Достат условия экстремума в задаче опт-ции с ограничениями типа равенств.
- •25. Задача проектирования на выпуклое и замкнутое множество. Свойства проекции. Примеры.
- •27. Основные определения в задаче одномерной минимизации. Примеры.
- •Пример . Множ-во решений задачи min-ции f(X)
- •28.Метод деления отрезка пополам решения задачи одномерной минимизации.
- •29.Метод золотого сечения.
- •30.Метод ломаных. Обоснование и алгоритм. Пример.
- •31.Обоснование сходимости метода ломаных решения задачи одомерной минимизации
- •33. Алгоритм метода условного градиента
- •Теорема3
- •35. Сходимостсь метода скорейшого спуска
- •36. Постановка задачи вариационного исчисления. Пр.
- •Определим множество:
- •Замечание
- •37. Метод вариаций лагранжа Пусть в задаче , где и исследуется на минимум кривая , тогда все допустимые кривые X(t), из множества X можно представить в виде:
- •38. Уравнение Эйлера.
- •39. Случай интегрируемости ур-ния Эйлера. Пример.
- •40. Задача вариационного исчисления с незакрепленными концами и фиксированным отрезком интегрирования.
- •41. Задача вариационного исчисления с незакрепленными концами и нефиксированным отрезком интегрирования.
- •42. Задача вариационного исчисления с движущимся по кривой коцом.
- •43. Примеры задач динамического программирования, их особенности.
- •44. Принципы динам програм и функцон ур-ния Беллмана.
- •45. Постановка задачи оптимального быстродействия.
- •46 Достат условия оптимальности для линейной задачи оптимального быстродействия (зоб).
- •47. Пример решения задач оптимального быстродействия.
9. Обоснование конечности симплекс-алгоритма.
Алгоритм решения з. оптимизации назыв. Конечным, если для его реализации на компе требуется конечное число операций для нахождения оптимального плана.
ЗЛП невырожденная, если все угловые точки мн-ва Х невырожденные.
Теорема. Если в невырожд. ЗЛП известна какая-либо угл. т-ка, то отправляясь от нее либо б. найден оптимальный план, либо б. показано, что цел. Ф-я неограниченна и для этого понадобится конечное число итераций.
Док-во. Пусть у – угл. т-ка мн-ва Х. Т.к. ЗЛП невырожд., то . Разрешающий эл-т . Если не вып. достат. усл-е оптимальности , то
Т.е. переход к др. угловой точке происходит со строгим возрастанием, а достигается только в 1 строчке, т.е. выбор координаты, выводимой из базиса однозначный. Число угл. т-к конечно. Из всего этого следует конечность симплекс-алгоритма.
10. Обоснование непустоты множества планов в злп. Пример.
(1)
Рассм след вспомог задачу:
Введем в рассм искусств перемен . Т.к. множество : (2)
И рассм задачу: (3)
В покоординатной форме ограничения (2) им след вид
Замеч: 1). Если вектор ,то система основных ограничений (2) переходит в систему основных ограничений (1)
2). Множество , т.к.
3). Т. является угловой точкой мн-ва Z с базисом
4). Целев ф-ия , т.о. зад (3) – есть ЗЛП в канонической форме, к кот удобно применить симплекс метод, при этом в силу огр-ти целев ф-ии на Z зад (3) обяз-но им решение.
Непустота мн-ва планов
Пусть - реш зад (3) и знач целев ф-ии зад (3).
Возможны 2 случая: 1.
2.
Утверждение: Если
Док-во: Предположим, что , но , т.е. , тогда противоречие с тем, что - реш зад (3). ЧТД
Утверждение: Если , то угловая точка этого мн-ва.
Док-во: Рассм случай, когда из подстановки в зад (3) полагаем, что и в силу того, что .
Покажем, что - угловая точка X: . Построим точки тогда , но
- - угловая точка мн-ва Z, как решение ЗЛП (3), полученное симплекс методом послед рав-во возможно, когда -угловая точка мн-ва X.
11.Нахождение базиса угловой точки. Пример. Св-во решений злп.
Угловая точка у=(0,0,800,640,145)
|
|
|
|
|
|
|
|
800 |
8 |
25 |
1 |
0 |
0 |
|
640 |
8 |
5 |
0 |
1 |
0 |
|
145 |
1 |
5 |
0 |
0 |
1 |
|
||||||
|
|
|
|
|
|
|
|
8 |
0 |
1 |
1/20 |
-1/20 |
0 |
|
75 |
1 |
0 |
-1/32 |
5/32 |
0 |
|
30 |
0 |
0 |
-7/32 |
3/32 |
1 |
|
|
0 |
0 |
1 |
9 |
0 |
Г=6560 х=(75,8,0,0,30) Рассм посл симплекс таблицу. В общем случае среди базисных пер-ых этой таблицы будут присутствовать как осн пер-ые, так и искусств. Будем рассм случай, когда Г1(z*)=0
xB |
yB |
x1 |
… |
xr |
xr+1 |
… |
xn |
xn+1 |
… |
xn+m-r |
… |
xn+m |
xn+m-z+1 |
x1…xr |
y1…yr |
1,0…,0 |
|
0…01 |
|
|
|
0…0 |
|
0…0 |
|
|
|
xn+1...xn+m-r |
0…0 |
0…0 |
|
0…0 |
|
n+i,j |
|
1,0…0 |
|
0…0, 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Г1(z*)=0 1 случай: В табл (*) отсутсв. строки, строки соотв исскуств Эл-там, т.е. r=m. Это значит, rang A= числу осн ограничений и вектора A1,…,Ar представляют собой базис угловой , когда z*=( ,0).2 случай: В табл (*) на пересечении строк, соотв исскуств перемен, и столбцов, соотв осн переем, есть положит элементы n+1,j >0, i{1,…,n-r}, j{r+1,…n}Выбирая элемент n+1,j в кач-ве разрешающего, исскуств переменную xn+1 выводим из базиса, т.к. xn+I=0: то в результате провед вычисл остаёмся в той же угловой точке мн-во Z*, только заменив её базис.3 случай: все коэф выделеной части табл (*) <=0 3.1 случай:найдется строчка соотв исскуств перемен, в котор на пересечении с столбцами соотв оси переменных, все коэф =0. Это означ, что выбран строка соотв осн огранич, котор явл лин комбин остальных осн ограничений. В данном случае строка удал из таблицы.3.2 случай: в некотор строке, соотв исскуств перем, на пересеч со столбцами соотв осн элементам, есть отриц элемент, а остальн коэф в этой строке =0. В этом случае осн огранич (1) могут выполн только при условии xj=0, где xn+1,j<0. Столбец для xj удаляется и продолж решение для ост части таблицы. По окончанию решения добавл решение xj=0
Замечание: задача (3) задача 1-ой фазы.Зам: если нет необходим дальнейш анализа исх задачи, то когда в процессе реш исх задачи (3) исскуств перемен перешла в небазисное, т.е. этого столбца в дальнейшем разрешающ элемент брать не следует. Более того, столбец для этой исскуств перем можно удалить.