- •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. Пример решения задач оптимального быстродействия.
12. Свой-ва решений злп.
Угловая точка у=(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)
Пусть предлагается произвести продукцию вида А3. Для производства продукции вида А3 требуется 10 кг сырья, 5 чел/ч физического труда. Выяснить, стоит ли браться за изготовление этой продукции, если прибыль от реализации 1-ой ед. продукции вида А3 составит с тыс. рублей.
Х6 – кол-во ед. продукции вида А3, которую следует выпустить. Тогда каноническая форма новой задачи имеет вид:
Тогда последняя таблица имеет вид:
|
|
80 |
70 |
0 |
0 |
0 |
с |
|
|
|
|
|
|
|
|
|
8 |
0 |
1 |
1/20 |
-1/20 |
0 |
1/4 |
|
75 |
1 |
0 |
-1/32 |
5/32 |
0 |
-15/32 |
|
30 |
0 |
0 |
-7/32 |
3/32 |
1 |
105/32 |
|
|
0 |
0 |
1 |
9 |
0 |
|
Т.о. не имеет смысла производить 3-ю продукцию, если выполняется последнее соотношение. Если оно не выполняется, то задачу следует дорешать.
Св-во решение ЗЛП Т.1(О разрешимости ЗЛП): Для того чтобы ЗЛП была разрешима, т.е. существ x* из Х, (с, x*)>=(с, x) для люб х из Х <=> чтобы мно-ство Х не было пустым и целев ф-я огранич сверху на Х. Д-во: =>) Очевидно существ x* из Х, (с, x*)>=(с, x) для люб х из Х, Х<>0 Г(х) огран в силу неравенства (с, x*)>=(с, x), т.е. (с, x*)>=Г(х). <=) Х<>0, то по утверждению в мн-ве Х существ углов точка=> можно примен симплекс метод, а так как ф-я Г(х) огран сверху на мн-ве планов, то симплекс метод придет к реш задачи. Теор.2:если ЗЛП разрешима то среди её решений обязат найдётся углов точка.Д-во: так как ЗЛП разрешима то по т.1 Х<>0. Но так как у Х существ углов точка=> примен симплекс метод получим решение задачи в угловой точке мн-ва Х.
13. Постановка тз. Построение плана перевозок методом северо-западного угла.
Пусть имеется m пунктов пр-ва однородной продукции с объемами пр-ва аi, i=1,m, и n пункт. потребления этой продукции с потребностями bj, j=1,n и ∑i=1m ai=∑j=1n bj .
Известны стоимости cij перевозки одной еденицы продукции из i-го пункта производства в j-ый пункт потребления. Требуется определить объем перевозок xij≥0 чтобы ∑i=1m ∑j=1n сij xij→min при условии, что ∑j=1n xij=ai и ∑i=1m xij=bj .
Положим 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} (с северо-западного угла), то метод получил название «Северо-западного угла».