Министерство образования Республики Беларусь
Белорусский государственный университет
Механико-математический факультет
Кафедра уравнений математической физики
УТВЕРЖДАЮ
Проректор по учебной работе
________________________
Рег.№ __________________
«____» ______________ 2007 г.
Базовая учебная программа дисциплины
«ОСНОВЫ МАТЕМАТИЧЕСКОЙ КИБЕРНЕТИКИ»
для студентов специальности 1-31 03 01 «Математика»
Минск
2007
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
Кибернетика – наука об основных закономерностях процессов управления в сложных динамических системах способах получения, хранения, передачи и обработки информации. Наука начала интенсивно развиваться в середине ХХ века. Это было связано с необходимостью исследования так называемых больших систем, которые характеризуются большим числом составляющих элементов и связей между ними, сложной иерархией. Исследование таких систем невозможно без вычислительной техники.
Математическая кибернетика является теоретической базой кибернетики в целом. Она занимается изучением наиболее распространенных математических моделей, которые являются составляющими частями больших систем. Главная задача курса – это подготовка студентов к решению реальных производственных задач.
Программа предназначена для студентов-математиков специальности математическая электроника механико-математического факультета.
«ОСНОВЫ МАТЕМАТИЧЕСКОЙ КИБЕРНЕТИКИ»
Цель курса – научить студентов универсальным приемам решения комбинаторных задач, ознакомить их с наиболее распространенными математическим комбинаторными моделями и конкретными эффективными алгоритмами их исследования.
Тематический план курса «Основы математической кибернетики»
№ темы | Количество часов | |
Содержание курса: | Лекции | Семинарские занятия |
Введение. | 2 | |
Раздел 1. Элементы линейного программирования. | ||
1.1 Постановка задачи. Построение простейших моделей. | 1 | 4 |
1.2. Строение множества планов задачи. | 1 | 2 |
1.3. Основные теоремы симплекс-метода. | 2 | 1 |
1.4. Алгоритм симплекс-метода. Симплекс-таблицы. | 1 | 4 |
1.5 Метод искусственного базиса. | 2 | 3 |
1.6. Модифицированные способы записи симплекс-таблиц. | 1 | 4 |
1.7. Симплекс-метод как переход от одной системы уравнений к эквивалентной системе. | 1 | 1 |
1.7. Двойственные задачи. | 1 | 1 |
1.8. Теорема двойственности и ее применение. | 3 | 1 |
1.9. Двойственный симплекс-метод. | 2 | 4 |
1.10. Прямо-двойственный симплекс-метод. | 1 | 2 |
1.11. Решение транспортной задачи методом потенциалов. | 2 | 4 |
1.12. Целочисленное линейное программирование. | 2 | 3 |
1.12. Параметрическое линейное программирование. | 1 | 3 |
1.13. Декомпозиция задач большой размерности (КСР). | 2 | 3 |
1.14. Вырожденная задача линейного программирования (КСР). | 2 | 1 |
Раздел 2. Элементы теории игр. | ||
2.1. Классификация игр. | 1 | |
2.2. Матричная игра. Основная теорема матричных игр. Решение игр с помощью линейного программирования. | 3 | 4 |
2.3. Графическое решение игр. | 1 | 3 |
2.4 Игры с природой. | 1 | 1 |
2.5. Основная теорема позиционных игр с полной информацией. | 2 | 1 |
Итого | 34 | 50 |
Раздел 1. Элементы линейного программирования.
Значение кибернетики при исследовании больших динамических систем и управлении ими. Принципы построения математических моделей. Линейная модель. Постановка задачи линейного программирования. Определения базиса, плана, опорного плана, оптимального плана. Теорема о строении опорных планов. Теорема о существовании оптимального решения в опорном плане.
Теорема о возможности улучшения решения задачи. Теорема об оптимальном плане задачи. Алгоритм симплекс-метода. Симплекс-таблицы. Переход от одной симплекс-таблицы к другой. Решение задач с помощью искусственного базиса. Модифицированная форма записи симплекс-таблицы. Мультипликативная запись обратной матрицы. Симплекс-метод как метод перехода от одной системы ограничений задачи к другой, эквивалентной ей, с помощью преобразования Гаусса.
Двойственные задачи. Экономическая интерпретация двойственных задач. Теорема двойственности. Двойственно-допустимая система векторов. Двойственный симплекс-метод. Теорема Фаркаша. Одновременное решение исходной и двойственной задач. Прямо-двойственный симплекс-метод.
Закрытая транспортная задача, ее свойства. Построение начального опорного плана методом северо-западного угла. Решение задачи методом потенциалов. Сведение решения открытой транспортной задачи к решению закрытой. Транспортные задачи с промежуточными пунктами.
Целочисленное линейное программирование. Методы правильных отсечений Гомори. Задачи линейного программирования с целевой функцией, линейно зависящей от параметра. Метод декомпозиции задач большой размерности Данцига-Вулфа. Вырожденная задача линейного программирования.
Раздел 2. Элементы теории игр. Понятие игры. Классификация игр. Матричная игра. Чистые стратегии. Верхняя и нижняя цены игры и теорема об их соотношении. Седловая точка матрицы. Смешанные стратегии. Связь матричных игр и линейного программирования. Основная теорема матричных игр. Решение матричной игры с помощью симплекс-метода. Графическое решение игры. Различные стратегии при играх с природой. Определение позиционной игры. Существование седловой стратегии для позиционных игр с полной информацией.
ЛИТЕРАТУРА
по курсу "Основы математической кибернетики"
Основная:
инейное программирование. М.: Наука, 1961.
, , Шор и нелинейное программирование. Киев: Навукова думка, 1975.
Дополнительная:
Кириллова оптимизации. Минск: Вышэйшая школа, 1981.
еория линейного и целочисленного программирования. М.: Мир, 1981.
, , Кузнецов для экономистов на базе MathCad. С.-Пб.: БХВ-Петербург, 2003.
, , Метельский программирование. Минск: Вышэйшая школа, 2007.
Автор:
Профессор кафедры уравнений математической физики, доктор пед. наук
Рецензент:
Зав. кафедрой дискретной математики и алгоритмики факультета прикладной математики и информатики,
профессор, доктор физ.-мат. наук
Одобрена на заседании кафедры
уравнений математической физики
протокол № 7 от 01.01.01 г.
Одобрена на заседании Ученого совета механико-математического факультета
протокол № 7 от 01.01.01 г.
Ответственный за выпуск
вед. лаборант кафедры уравнений математической физики
