- •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. Пример решения задач оптимального быстродействия.
14.Определение закрытой модели тз. Критерий существования решения тз.
ТЕОРЕМА 1:Транспортная задача имеет решения тогда, и только тогда, когда (1)
– называется условием баланса.
Док-во. Необходимость. Пусть решение транспортной задачи существует ,
, . ,
Достаточность. Пусть выполняется условие баланса (1) . Построим след. план перевозок
,
Из условия следует, что множество планов является замкнутым. Кроме этого оно является ограниченным. Действительно, если возьмем любую перевозку. Целевая функция является линейной, следовательно и непрерывной. Отсюда по теореме Вейерштрасса решение задачи существует.
Замечание Транспортная задача, для которой выполняется условие (1) называется закрытой, в противном случае – открытой.
Замечание Открытую ТЗ можно свести к закрытой след. образом:
если , то вводим фиктивный пункт производства с запасами продукции в нем в кол-ве и нулевыми стоимостями перевозок из него.
Если то вводим фиктивный пункт потребления с потребностямипродукции в нем
и нулевыми стоимостями перевозок в него.
15.Исследование множества клеток транспортной таблицы.
Множество всех клеток трансп. табл. обозначим
Опред. Цепью назовем последовательность клеток, в которой каждые две соседние клетки лежат в одной строке или в одном столбце, но ни в одной строке и ни в одном столбце нет трех послед. клеток.
Опред. Циклом наз. цепь, крайние клетки которой лежат в одной строке или в одном столбце.
Замеч. Если в трансп. табл. соседние клетки соединить отрезками прямых (звеньями цепи), то соседние звенья всегда будут перпендикулярны.
Опред. Мн-во клеток наз. базисным , полным, если их кол-во равно и из его элементов невозможно создать ни одного цикла.
Все остальные клетки наз. небазисными
Опред. План перевозок из i в j наз. базисным, если все перевозки за исключением равны 0, а остальные находятся в клетках, составляющих базисные множества клеток.
Опред. Перевозки , где (i,j) наз. базисными, а если (i,j) , то небазисными.
Опред. Базисный план наз. невырожденным, если все базисные перевозки строго >0, в противном случае – вырожденным.
Св-ва базисного множества клеток:
В каждой строке и каждом столбце трансп. табл. обязательно найдется базисная клетка.В противном случае не будет выполнено какое-либо из огр зад.
Найдется строка или столбец, в котором есть ровно 1 базисная клетка.
Док-во. От противного. Пусть в каждой строке 2 базисных клеток и в каждом столбце 2 базисных клеток, тогда если посчитать все клетки по строкам то их кол-во получится 2m, а если по столбцам, то 2n. Следовательно всех клеток m+n. Но по определению их должно быть . Следовательно предположение неверно.
Удаление любой строки или столбца, в котором находится 1 базисная клетка приводит к уменьшению транспортной таблицы т.о., что в новой таблице базисное множество клеток будет базисным.
Любую пару из строк и столбцов можно соединить единственной цепьб из элементов базисного множества клеток.
Добавление небазисной клетки к небазисному множеству создает цикл.