- •Математическое программирование
- •Математическое моделирование задачи.
- •Метод Гауса.
- •Переход от одной формы модели к другой форме модели , различные формы моделей з.Л.П.
- •Переход от стандартной формы к канонической форме.
- •Переход от канонической к стандартной.
- •Переход от задачи max к min и наоборот.
- •Графический метод решения л.П.
- •Геометрическая интерпретация линейного неравенства.
- •Геометрическая интерпретация системы линейны неравенств.
- •Графический метод .
- •Опорный план. Свойства допустимых планов.
- •Свойства допустимых планов.
- •Идея симплекс метода.
- •Алгебра симплекс метода.
- •Альтернативный оптимум.
- •Монотонность и конечность алгоритма симплекс метода.
- •Проблема выражденности.
- •Метод искусственного базиса.
- •Теория двойственности .
- •Стандартная форма.
- •Правило построения двойственных задач к общей з.Л.П.
- •Теорема двойственности.
- •Часть теоремы.
- •Вторая теорема двойственности и свойства двойственных оценок.
- •Свойства двойственных оценок.
- •Транспортная задача.
- •Особенности т.З.
- •Теорема о ранге матрицы.
- •Этапы решения т.З.
- •Метод нахождения первоначального опорного плана.
- •Переход от одного опорного плана к другому.
- •Проверка плана на оптимальность. Теорема об оптимальности плана или теорема о потенциальности плана.
- •Задачи о назначении.
- •Математическая модель.
- •Алгоритм решения.
- •Задача коммивояжера.
- •Метод ветвей и границ.
- •Ветвлениею
- •Признак оптимальности.
Ветвлениею
Ветвление на множестве Д такое разбиение множества Д на k 2 подмножеств. Дi (i =1,k) для которых справедливы следующие 2 условия.
Пересечение 2 подмножеств Дi1 Дi2 = есть пустое множество, а
Обьединение всех подмножеств Дi = Д
В результате ветвей получим дерево решений.
Вершина от которой нет ответвлений называется висячей вершиной. Если выходит две стрелки , то дерево называется диадическое дерево
Перспективное ветвление.
Пусть на каком то шаге дерево возможных вариантов , каждый из которых имеет нижнюю оценку , на очередном шаге выбирается для ветвления вершина с наименьшей минимальной оценкой. и та вершина становится перспективной.
Признак оптимальности.
F(x)=min оценки Д (последней) Пусть есть матрица Х* принадлеж Дк , такой что f(x*)= сигма (Дк) => Х* оптимальное решение.