Программа по дисциплине "Методы оптимизации" (Цель, задачи и содержание дисциплины)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ

П Р О Г Р А М М А

по дисциплине

« МЕТОДЫ ОПТИМИЗАЦИИ »

для высших учебных заведений

Направление подготовки: 0802 – Прикладная математика

Специальность:  7.080202 – Прикладная математика

(Разработана кафедрой прикладной математики ВНУ)

Программу составил   доц., к. т. н.  Малый В.В.

Рассмотрена и утверждена:

На заседании кафедры прикладной математики       5.09. 2000 г.

Зав. кафедрой прикладной математики                        проф. Грибанов В.М.

На заседании Совета факультета математики и информатики  17.09.2000 г.

Декан факультета математики и информатики             доц. Крамарь Н.М.

Луганск -2000

1. ЦЕЛЬ И ЗАДАЧИ ДИСЦИПЛИНЫ

1.1  Цель преподавания дисциплины.

   Дать студенту теоретическую базу современных методов оптимизации и привить навыки их практической реализации на ЭВМ при решении прикладных оптимизационных задач в различных областях  техники и экономики.

1.2  Задачи изучения дисциплины

   Изучив дисциплину, студент должен:

   1.2.1. Знать:

-  теорию и методы решения линейных оптимизационных задач;

-  теорию двойственности линейного программирования;

-  симплекс - метод решения задачи линейного программирования  и его модификации;

-  теорию и методы решения транспортной задачи линейного программирования;

-  основы теории потоков в сетях;

-  основы теории и методы решения задач целочисленного программирования;

-  основные понятия о динамическом программировании;

-  общую теорию решения нелинейных оптимизационных задач;

-  численные методы нелинейного программирования.

   1.2.2. Уметь:

-  строить и анализировать оптимизационные модели прикладных задач экономического и технического характера;

-  решать задачи линейного программирования с помощью симплекс-метода и двойственного симплекс-метода;

-  строить и решать задачи линейного программирования транспортного типа;

-  решать задачи целочисленного программирования методом  Гомори и комбинаторными методами;

-  применять принцип Беллмана при решении задач динамического программирования;

-  решать задачи нелинейного программирования градиентными методами, методами штрафных функций и возможных направлений.

   1.2.3. Иметь представление:

-  об основных понятиях теории матричных игр;

-  об основных понятиях теории оптимального управления.

2.  СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

2.1 Классификация оптимизационных задач: линейное, нелинейное и динамическое программирование. Задачи целочисленного программирования и оптимального управления. Построение и анализ оптимизационных моделей прикладных задач экономического и технического характера.

2.2.  Общая задача линейного программирования (ЗЛП). Стандартная и каноническая формы записи задач линейного программирования. Переход от одной из форм  задания ЗЛП к эквивалентной ей форме. Геометрическая интерпретация  и графический метод решения  ЗЛП.

2.3. Линейная зависимость векторов и базис векторного пространства. Преобразование однократного замещения  Жордана-Гаусса. Его применение в симплекс - преобразованиях  при построении базисных решений ЗЛП.

2.4. Основные свойства области допустимых решений ЗЛП. Обоснование симплекс-метода для невырожденных  ЗЛП. Необходимые и достаточные условия оптимальности опорного решения. Признак неограниченности  целевой функции.

2.5. Симплекс-метод в общем случае. Возможность зацикливания  процесса и его предупреждение. Алгоритм симплекс-метода и его реализация с помощью симплекс-таблиц.

2.6. Построение исходного базиса. Метод введения искусственного базиса (М-метод). Модифицированный симплекс-метод решения  ЗЛП. Его обоснование и реализация.

2.7. Применение общей задачи линейного программирования для решения  некоторых  экономических задач ( задача использования ресурсов, задача составления диеты и пр.)

2.8. Двойственность в линейном программировании. Симметричные и несимметричные двойственные задачи. Экономическая интерпретация  двойственных задач.

2.9. Свойства решений двойственных задач. Первая и вторая теоремы двойственности. Признаки неограниченности целевой функции и недопустимости решений двойственных задач.

2.10  Двойственный симплекс-метод решения  задач линейного программирования. Алгоритм  двойственного симплекс-метода. Его реализация с помощью симплекс-таблиц.

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

2.12. Двойственность в транспортных задачах. Решение транспортной задачи методом потенциалов. Алгоритм метода потенциалов.

2.13. Задача об оптимальных  потоках в сетях. Метод Форда-Фалкерсона  решения задачи о максимальном  потоке.

2.14. Задачи целочисленного программирования. Решение задач целочисленного программирования с помощью методов Гомори и  отсекающих плоскостей.  Алгоритм Дальтона-Левелина.

2.15. Комбинаторные методы  решения задач целочисленного программирования.