- •1.Понятие решения задачи мат. Программиров.
- •2. Основн. Формы злп. Правила сведения злп к канон.Форме. Геометр.Интерпретация злп. Понятие угловой точки мн-ва.
- •4. Определение базиса угловой точки. Невырожденные угловые точки. Примеры.
- •5. Связь между переменными задачи лп
- •6. Формула приращения целевой функции злп.
- •7. Достаточное условие оптимальности в злп. Достаточное условие неразрешимости злп
- •8. Итерация симплекс–метода
- •11. Нахождение базиса угловой точки. Пример
- •12. Постановка тз. Построение нач. Плана перевозок методом северо-западного угла, методом мин. Элемента.
- •13. Определение закрытой модели тз. Критерий существования решения тз.
- •14. Исследование мн-ва клеток транспортной таблицы
- •15. Достаточное условие минимальности стоимости перевозок
- •16. Классический метод решения задачи безусловной минимизации функции многих переменных. Пример.
- •17. Метод исключения решения задачи на условный минимум. Пример.
- •18. Обобщенное правило множителей Лагранжа в задаче оптимизации с ограничениями типа равенств.
- •19. Классическое правило множителей Лагранжа в задаче оптимизации с ограничениями типа равенств. Необходимые условия второго порядка в задаче оптимизации типа равенств.
- •20. Достаточные условия экстремума в задаче оптимизации с ограничениями типа равенств
- •21.Опр-ия выпуклого мн-ва, выпуклой функции. Св-ва выпуклых множеств. Сумма выпуклых функций. Св-во неотрицательности остатка выпуклой функции
- •22.Теорема о точках минимума выпуклой функции. Теорема о стационарной точке выпуклой функции
- •26.Теорема о седловой точке функции Лагранжа (достаточные условия оптимальности).
- •27. Критерий существования седловой точки функции Лагранжа для задачи выпуклого программирования.
- •28.Определение двойственной задачи к задаче математического программирования.
- •29. Связь между двойственной и прямой задачами математического программирования.
- •30.Пример решения задачи оптимизации с помощью теории двойственности
- •31.Основные определения в задаче одномерной минимизации. Примеры.
- •33. Метод золотого сечения решения задачи одномерной минимизации.
- •34. Обоснование метода ломаных решения задачи одномерной минимизации.
- •35. Алгоритм и условия сходимости метода ломаных решения задачи одномерной минимизации. Пример. Описание метода ломаных
- •36.Алгоритм метода скорейшего спуска решения змм.
- •37.Алгоритмы метода условного градиента и метода проекции градиента решения задачи многомерной условной минимизации.
- •38.Алгоритм метода покоординатного спуска решения задачи многомерной минимизации. Геометрическая иллюстрация.
- •39.Сходимость метода скорейшего спуска.
- •41. Метод вариаций Лагранжа
- •42. Уравнение Эйлера
- •43. Случаи интегрируемости ур-ния Эйлера. Примеры.
- •44.Задача вариационного исчисления с незакрепленными концами и фиксированным отрезком интегрирования.
- •45.Задача вариационного исчисления с незакрепленными концами и нефиксированным отрезком интегрирования
- •46. Задача вариационного исчисления с движущимся по кривой концом.
- •47. Примеры задач динамического программирования, их особенности
- •48.Принципы динамического программирования и функциональные уравнения Беллмана.
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.