Базовая учебная программа дисциплины «основы математической кибернетики» для студентов специальности 1-31 03 01 «Математика» Минск

Вид материалаПрограмма дисциплины

Содержание


«основы математической кибернетики»
Тематический план курса «Основы математической кибернетики»
Содержание курса
Раздел 1. Элементы линейного программирования.
Раздел 2. Элементы теории игр.
Автор:Профессор кафедры уравнений математической физики, доктор пед. наук
Подобный материал:
Министерство образования Республики Беларусь

Белорусский государственный университет

Механико-математический факультет

Кафедра уравнений математической физики


УТВЕРЖДАЮ

Проректор по учебной работе

________________________

Рег.№ __________________

«____» ______________ 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 от 06 июня 2007 г.


Одобрена на заседании Ученого совета механико-математического факультета

протокол № 7 от 20 июня 2007 г.


Ответственный за выпуск

вед. лаборант кафедры уравнений математической физики Л.Н. Кулибаба