Методы оптимальных решений (стр. 2 )

Таблица 4

№ Темы	Устный опрос	Письменные работы	Технические формы контроля	Информа-циионные системы и технологии	Итого количество баллов
коллоквиумы	собеседование	ответ на семинаре	лабораторная работа	контрольная работа	тест	реферат, эссе	программы компьютерного тестирования	комплексные ситуационные задания	решение задач с помощью ППП	другие формы
Модуль 1
1.1.	0-4	-	-	-	-	0-4
1.2	0-4	-	0-3	-	-	0-7
1.3	0-4	-	-	-	-	0-4
1.4	0-4	0-4	0-8
1.5	0-4	0-7	0-11
Всего	0-20	0-7	0-3	0-4	-	0-34
Модуль 2
2.1.	0-4	-	-	-	-	0-4
2.2	0-4	-	-	0-4-	-	0-8
2.3	0-4	-	-	-	-	0-4
2.4	0-4	0-7	-	-	0-11
2.5	0-4	-	-	-	0-4
2.6	-	-	0-4	0-4
Всего	0-20	0-7	-	0-4	0-4	0-35
Модуль 3
3.1.	0-4	-	-	0-4	0-4	0-12
3.2	0-4	-	0-3	-	-	0-7
3.3	0-4	0-8	-	-	-	0-12
Всего	0-12	0-8	0-3	0-4	0-4	0-31
Итого	0-52	0-22	0-6	0-12	0-8	0-100

5. Содержание дисциплины.

Тема 1.1. Введение в дисциплину.

Этапы решения задач о принятии решения. Примеры математических моделей с экономическим содержанием.

Тема 1.2. Постановка задачи линейного программирования.

Основная задача линейного программирования, стандартная, каноническая. Понятие плана, опорного плана, оптимального плана. Выпуклые множества. Внутренние, граничные, крайние точки. Выпуклый многоугольник, многогранник, опорная плоскость. Выпуклость множества планов. Достижение оптимального решения в угловой точке многогранника решений. Соответствие угловой точки многогранника решений линейно независимой системе векторов. Соответствие линейно независимой системы векторов угловой точке многогранника решений.

Тема 1.3. Геометрическая интерпретация задачи ЛП. Графический метод

Графический метод решения: стандартной задачи ЛП с двумя переменными. Графический метод решения канонической задачи ЛП с числом переменных больше двух. Примеры задач, решаемых графически. Особенности графического метода.

Тема 1.4. Симплекс-метод.

Построение опорных планов. Теорема о возможности улучшения плана для задачи на минимум. Теорема о возможности улучшения плана для задачи на максимум. Критерии оптимальности. Алгоритм симплекс-метода.

Тема 1.5. Метод искусственного базиса.

Теорема о переходе от оптимального плана расширенной задачи к оптимальному плану исходной задачи. Признак неразрешимости. Задачи со смешанными ограничениями.

Тема 2.1. Двойственность в ЛП.

Понятие о двойственности (примеры построения двойственных задач). Правила построения двойственных задач. Виды математических моделей двойственных задач в линейном программировании. Теоремы двойственности.

Тема 2.2. Экономическая интерпретация двойственных задач.

Задача использования ресурсов. Задача об относительных ценах. Анализ линейной модели на чувствительность. Статус ресурсов. Ценность ресурсов. Максимальное изменение запаса ресурса. Максимальное изменение коэффициентов удельной прибыли.

Тема 2.3. Целочисленное программирование.

Постановка задачи и методы решения. Алгоритм Гомори построения отсекающих плоскостей. Некоторые экономические задачи целочисленного программирования.

Тема 2.4. Транспортная задача. Метод потенциалов.

Матричная постановка задачи и ее математическая модель. Экономический и математический смысл модели. Свойства решений, необходимое и достаточное условие разрешимости задачи. Допустимый план. Оптимальный план. Понятие вырожденности, признак вырожденности. Методы построения первоначального опорного плана: метод северо-западного угла; метод минимального элемента; метод двойного предпочтения; эвристический метод Фогеля. Критерий оптимальности Канторовича. Метод потенциалов. Алгоритм метода потенциалов для решения задачи с ограниченными пропускными способностями.

Тема 2.5. Транспортная задача о назначениях.

Постановка задачи о назначениях и ее математическая модель. Задача о разборчивой невесте, особенность математической модели. Алгоритм венгерского метода. Борьба с вырожденностью. Особенности метода потенциалов для задачи выбора. Приложение задачи о назначениях в экономике.

Тема 2.6. Решение задач ЛП в EXCEL.

Решение задач линейного программирования в EXCEL. Графическое представление результатов решения. Анализ задач линейного программирования в EXCEL. Анализ оптимального решения. Отчет по результатам. Отчет по устойчивости. Отчет по пределам.

Тема 3.1. Нелинейное программирование.

Общий вид задач нелинейного программирования. Основная задача нелинейного программирования. Графический метод решения задач нелинейного программирования. Метод Лагранжа. Решение задач нелинейного программирования в EXCEL.

Тема 3.2. Динамическое программирование.

Особенности решения многошаговых задач оптимизации. Задача о кратчайшем маршруте. Задача об оптимальном распределении инвестиций. Задача о загрузке рюкзака.

Тема 3.3. Графы и сети.

Основные понятия теории графов. Характеристики графов. Способы задания графов. Основы сетевого планирования и управления. Дерево решений. Задача о соединении городов. Максимальный поток. Задача нахождения кратчайшего пути.

6. Планы (темы) семинарских (практических) занятий.

Основная задача линейного программирования. Графический метод.

Стандартная задача ЛП. Каноническая задача ЛП. Эквивалентность задач: переход от задачи минимизации к задаче максимизации; преобразование стандартной формы в каноническую с помощью дополнительных переменных; переход от канонической формы к стандартной; выражение произвольных переменных в виде разности двух неотрицательных переменных.

Понятие плана, опорного плана, оптимального плана. Выпуклые множества. Внутренние, граничные, крайние точки. Выпуклый многоугольник, многогранник, опорная плоскость.

Графический метод решения стандартной задачи ЛП с двумя переменными. Примеры задач, решаемых графически. Особенности графического метода решения.

Симплекс-метод.

Построение начального плана. Структура симплекс-таблицы. Вычисление значения функции. Вычисление оценок. Правила выбора разрешающего элемента. Преобразование таблицы. Виды контроля преобразования таблиц. Признак неограниченности целевой функции. Признак оптимальности плана. Решение задачи о ресурсах.

Метод искусственного базиса.

Понятие искусственной переменной. Построение расширенной задачи. Коэффициенты при искусственных переменных в целевой функции расширенной задачи. Теорема о переходе от оптимального плана расширенной задачи к оптимальному плану исходной задачи. Признак неразрешимости. Виды неразрешимости задачи ЛП.

Транспортная задача. Метод потенциалов.

Матричная постановка задачи и ее математическая модель. Экономический и математический смысл модели. Методы построения первоначального опорного плана: метод северо-западного угла; метод минимального элемента; метод двойного предпочтения; эвристический метод Фогеля. Критерий оптимальности Канторовича. Метод потенциалов.

Транспортная задача о назначениях.

Постановка задачи о назначениях и ее математическая модель. Задача о разборчивой невесте, особенность математической модели. Алгоритм венгерского метода. Борьба с вырожденностью. Особенности метода потенциалов для задачи выбора. Приложение задачи о назначениях в экономике.

Графы и сети.

Основные понятия теории графов. Характеристики графов. Способы задания графов. Задача о соединении городов. Максимальный поток. Задача нахождения кратчайшего пути.  Основы сетевого планирования и управления. Дерево решений. Задача о соединении городов. Максимальный поток. Определение кратчайшего расстояния между начальной и остальными вершинами сети.

7. Темы лабораторных работ.

Лабораторный практикум не предусмотрен учебным планом.