- •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. Пример решения задач оптимального быстродействия.
16.Достаточное условие минимальности стоимости перевозок
Выпишем ограничения ТЗ
=
=
…………………………………………………………………..
+ =
+ + … + =
…………………………………………………………….
+ + + … + =
Умножим эти ограничения на вектора , и полученное выражение вычтем из целевой функции (1)
Величины называются потенциалами соотв. ограничениям-строкам, - потенциалами, соотв. ограничениям-столбцам.
Подстав. в рав-во (1) значение начального плана перевозок. Если является небазисной т.е. =0, то соотв. слагаемое в (1) =0. Если же базисная, то для невырожденного плана >0, но тогда коэф-т положим =0 путем выбора потенциалов. =0, , поэтому для нахождения потенциалов можно любой из потенциалов положить =0 а остальные определить из системы линейных уравнений в кол-ве . Вычислим величины по небазисному множеству клеток.
Т. Выполнение нер-ва по небазисному множеству клеток (i,j) является достат. для оптимальности плана перевозок.
Док-во. Из рав-ва (1) следует, что если значения небазисных перевозок для которых >0 изменить на положит., то ст-ть перевозок увеличится. С другой стороны, если существует <0, (i,j) , то путем увеличения соотв. значения перевозки с нулев. на положит. стоимость перевозок можно уменьшить.
Изменяя знач. Небазисной перевозки, для кот. <0 необходимо изменить другие значения базисных перевозок т.о. чтобы выполнялись все ограничения задачи и кол-во базисных перевозок осталось равным .
Алгоритм метода потенциалов.
Проверит условие баланса. В случае открытой модели ввести фиктивного поставщика или потребителя.
Заполнить транспортную таблицу.
Составить начальный план перевозок.
Вычислить потенциалы по базисному множеству клеток
Вычислить по . Проверить достаточное условие оптимальности.
Найти min , если <0, (i,j) . Начиная с выбранн. клетки по базисному мн-ву строится цикл. Этот цикл дает возможность построить новый план перевозок. Перейти к п.4
17. Определения выпуклого множества, выпуклой функции. Свойства выпуклых множеств. Сумма выпуклых функций. Свойство Лебега выпуклых функций. Свойство неотрицательности остатка выпуклой функции.
(1) (2)
Если функция является выпуклой на выпуклом множестве X, то задача (1), (2) называется задачей выпуклого программирования.
Опр: Мн-во наз выпуклым, если для любых двух точек отрезок, соединяющий эти точки полностью принадлежит этому множеству, т.е. Опр: Функция , определенная на выпуклом множестве Х, называется выпуклой, если для выполняется
Т1: Пусть функция является выпуклой, дифференцируемой на выпуклом множестве Х, тогда выполняется
Док-во: Т.к. функция является выпуклой, то .
Т.к. функция является дифференцируемой, то приращение этой функции можно разложить в ряд Тейлора:
(!!!!!)= Последнее неравенство делим на и устремим к 0. Т.док-на.
Замечание: Теорема1 называется свойством неотрицательности остатка.