Учебно-методический комплекс по дисциплине «Блочное программирование»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«Алтайский государственный университет»

Математический факультет

Кафедра теоретической кибернетики и прикладной математики

УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС
по дисциплине

«Блочное программирование»

Направление 010500.62 «Прикладная математика и информатика»

Степень — Бакалавр прикладной математики и информатики

Рассмотрено и утверждено на заседании кафедры от 27 апреля 2012 г., протокол №11

Барнаул

2012

Структура

1.	РАБОЧАЯ ПРОГРАММА ……………………………….	3
2.	Методические указания ………………………………….	8
3.	Промежуточный итоговый контроль …………………..	9
	3.1. Формы контроля …………………………………….	8
	3.2. Контрольные вопросы и задания …………………..	8
	3.3. Критерии оценивания ……………………………….	10

МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Алтайский государственный университет"
(ФГБОУ ВПО «АлтГУ»)
	УТВЕРЖДАЮ
Декан
__________________________
06.06.2012 г.
Блочное программирование
рабочая программа дисциплины
	Закреплена за кафедрой:		Кафедра теоретической кибернетики и прикладной математики
Учебный план:	01050003_62-00-34-2623.plm подготовки бакалавра по профессионально-образовательной программе 010500.62- "Прикладная математика и информатика" Специализация "Исследование операций и системный анализ"
Часов по ГОС (из УП):	124		Часов по рабочему учебному плану:	124
Часов по прим. программе:		Часов по рабочей программе:	124
Часов на самостоятельную работу по ППД:
Часов на самостоятельную работу по РУП:	52 (41%)
Часов на самостоятельную работу по РПД:	52 (41%)
Коэффициент уникальности дисциплины:	0
Виды контроля в семестрах (на курсах)
	Экзамены 7		Зачёты 7		Курсовые проекты		Курсовые работы
Распределение часов дисциплины по семестрам
Вид занятий	№ семестров, число учебных недель в семестрах
1	19	2	17	3	19	4	18	5	18	6	17	7	18	8	11	Итого
УП	РПД	УП	РПД	УП	РПД	УП	РПД	УП	РПД	УП	РПД	УП	РПД	УП	РПД	УП	РПД
Лекции													36	36			36	36
Лабораторные
Практические													36	36			36	36
КСР
Ауд. занятия													72	72			72	72
Сам. работа													52	52			52	52
Итого													124	124			124	124

УП: 01050003_62-00-34-2623.plm		стр. 2
Программу составил(и):
к. т.н., ст. преподаватель _________________
Рецензент (председатель методической комиссии факультета):
к. ф.-м. н., доцент _________________
Рабочая программа дисциплины
Блочное программирование
разработана в соответствии с ГОС ВПО:
ГОС ВПО по направлению 010500.62 «Прикладная математика и информатика», утвержденный приказом Министерства образования и науки РФ от 23 марта 2000 г. № 000ен/бак.
составлена на основании учебного плана:
подготовки бакалавра по профессионально-образовательной программе 010500.62- "Прикладная математика и информатика" Специализация "Исследование операций и системный анализ"
утвержденного учёным советом вуза от 01.01.2001 протокол № 7.
Рабочая программа одобрена на заседании кафедры
Кафедра теоретической кибернетики и прикладной математики
Протокол от 27 апреля 2012 г. № 11 Срок действия программы: 2008-2014 уч. г. Зав. кафедрой профессор, д. т.н.

УП: 230100_62-00-34-2623.plm		стр. 3
Визирование РПД для исполнения в очередном учебном году
Утверждаю: Декан
20 мая 2008 г.
Рабочая программа пересмотрена, обсуждена и одобрена для исполнения в 2008–2009 учебном году на заседании кафедры
Кафедра теоретической кибернетики и прикладной математики
	Протокол от 01.01.01 г. № 9 Зав. кафедрой д. т.н., профессор
Визирование РПД для исполнения в очередном учебном году
Утверждаю: Декан
18 мая 2009 г.
Рабочая программа пересмотрена, обсуждена и одобрена для исполнения в 2009–2010 учебном году на заседании кафедры
Кафедра теоретической кибернетики и прикладной математики
	Протокол от 01.01.01 г. № 9 Зав. кафедрой д. т.н., профессор
Визирование РПД для исполнения в очередном учебном году
Утверждаю: Декан
28 июня 2010 г.
Рабочая программа пересмотрена, обсуждена и одобрена для исполнения в 2010–2011 учебном году на заседании кафедры
Кафедра теоретической кибернетики и прикладной математики
	Протокол от 28 июня 2010 г. № 12 Зав. кафедрой д. т.н., профессор
Визирование РПД для исполнения в очередном учебном году
Утверждаю: Декан
31 мая 2011 г.
Рабочая программа пересмотрена, обсуждена и одобрена для исполнения в 2011–2012 учебном году на заседании кафедры
Кафедра теоретической кибернетики и прикладной математики
	Протокол от 01.01.01 г. № 12 Зав. кафедрой д. т.н., профессор
Визирование РПД для исполнения в очередном учебном году
Утверждаю: Декан
27 апреля 2012 г.
Рабочая программа пересмотрена, обсуждена и одобрена для исполнения в 2012–2013 учебном году на заседании кафедры
Кафедра теоретической кибернетики и прикладной математики
	Протокол от 01.01.01 г. № 11 Зав. кафедрой д. т.н., профессор

1 Цели и задачи дисциплины
1.1	Целью преподавания курса является дать студентам комплексное представление о роли и месте дисциплины «Блочное программирование» в специальной профессиональной подготовке студентов по прикладной математике и информатике, формирование процессного мышления при анализе прикладных задач, основных методах и моделях принятия оптимальных решений, в том числе в системах с многими центрами планирования и реализации действий.
1.2	К основным задачам курса относятся: знакомство с основными понятиями блочного программирования; изучение опыта построения и использования математических и имитационных моделей при исследовании реальных экономических задач большой размерности; обучение навыкам исследования моделей принятия решений в больших системах; знакомство с современными методами теории оптимизации больших систем управления.
2 Требования к уровню освоения содержания дисциплины
2.1	Студент должен иметь представление:
2.1.1	Студент должен иметь представление о назначении, методах и основных составных приложениях блочного линейного и нелинейного программирования; иметь представление о критериях выбора оптимальных решений, порядке и вариантах построения численных методов в блочном программировании; иметь представление о технологиях исследования реальных систем с использованием математических моделей и компьютерных программ.
2.2	Студент должен знать и уметь:
2.2.1	Студент должен уметь решать задачи линейного и нелинейного программирования.
2.3	Студент должен иметь навыки:
2.3.1	Работы в компьютерных программах, необходимых для решения различных задач блочного программирования.
4 Содержание дисциплины
4.1 Обязательный минимум содержания образовательной программы
(выписка из ГОСа)
Блок	Наименование дисциплины и ее основные разделы	Всего часов
СД(M).Ф		124
Код занятия	Наименование разделов и тем /вид занятия/	Литература	Часов
	Раздел 1. Общая блочная структура задач блочного программирования.
1.1	Формальная декомпозиция в блочном программировании. /Лек/	Л1.1 Л1.2 Л2.1	6
1.2	Формальная декомпозиция в блочном программировании. /Пр/	Л1.1 Л1.2	6
1.3	Формальная декомпозиция в блочном программировании. /Ср/	Л1.1 Л1.2	4
	Раздел 2. Классификация декомпозиционных моделей иерархических систем.
2.1	Детерминированные задачи блочного программирования. Аддитивно-блочные структуры. /Лек/	Л1.1 Л1.2 Л2.1	6
2.2	Детерминированные задачи блочного программирования. Аддитивно-блочные структуры. /Пр/	Л1.1 Л1.2	6
2.3	Детерминированные задачи блочного программирования. Аддитивно-блочные структуры. /Ср/	Л1.1 Л1.2	4
	Раздел 3. Метод Данцига-Вульфа.
3.1	Задача планирования объединения предприятий. Симплекс метод решения задач линейного программирования с обратной к базису матрицей. /Лек/	Л1.1 Л1.2 Л2.1	6
3.2	Задача планирования объединения предприятий. Симплекс метод решения задач линейного программирования с обратной к базису матрицей. /Пр/	Л1.2	6
3.3	Задача планирования объединения предприятий. Симплекс метод решения задач линейного программирования с обратной к базису матрицей. /Ср/	Л1.1 Л1.2	4
	Раздел 4. Метод декомпозиции Корнаи-Липтака.
4.1	Схема декомпозиции и построение формальной системы. Алгоритм Корнаи-Липтака. Варианты алгоритмов в методе Корнаи-Липтака. /Лек/	Л1.1 Л1.2 Л2.1	6
4.2	Схема декомпозиции и построение формальной системы. Алгоритм Корнаи-Липтака. Варианты алгоритмов в методе Корнаи-Липтака. /Пр/	Л1.1 Л1.2	6
	Раздел 5. Двойственность и декомпозиция.
5.1	Формальные системы и их декомпозиция. Лагранжевая задача и ее свойства. Схемы численных методов блочного программирования. /Лек/	Л1.1 Л1.2 Л2.1	6

УП: 01050003_62-00-34-2623.plm		стр. 5
5.2	Решение задачи Лагранжа. /Пр/	Л1.1 Л1.2	6
5.3	Схема декомпозиции и построение формальной системы. Алгоритм Корнаи-Липтака. Варианты алгоритмов в методе Корнаи-Липтака. /Ср/	Л1.1 Л1.2	6
5.4	Решение задачи Лагранжа. /Ср/	Л1.1 Л1.2	4
	Раздел 6. Формальная декомпозиция путем разделения ограничений.
6.1	Схемы закрепления ограничений в аддитивно-блочных и сетевых задачах большой размерности. Вычислительные схемы метода декомпозиции, основанного на теории двойственности. /Лек/	Л1.1 Л1.2 Л2.1	6
6.2	Вычислительные схемы метода декомпозиции. /Пр/	Л1.1 Л1.2	6
6.3	Вычислительные схемы метода декомпозиции /Ср/	Л1.1 Л1.2	30
5 Тематика лабораторных и письменных работ
5.1	Лабораторные работы:
5.2	Письменные работы:
5.2.1	Методы декомпозиции
6 Учебно-методическое обеспечение дисциплины
6.1 Рекомендуемая литература
6.1.1 Основная литература
	Авторы, составители	Заглавие	Издательство, год
Л1.1		Введение в системный анализ и исследование операций: учеб. пособие	Барна0
Л1.2	,	Моделирование иерархических систем: учеб. для вузов	Барнаул : Изд-во АлтГУ, 2007
6.1.2 Дополнительная литература
	Авторы, составители	Заглавие	Издательство, год
Л2.1	,	Теория игр в управлении организационными системами	М.: Синтег, 2002
6.2 Электронные образовательные ресурсы
6.2.1	Сайт библиотеки АлтГУ: www. lib. asu. ru;
6.2.2	электронно-библиотечная система издательства «Лань»: www. ;
6.2.3	электронно-библиотечная система «Университетская библиотека online»: www. biblioclub. ru;
6.2.4	свободная энциклопедия «Википедия»: http://ru. wikipedia. org
6.3 Программное обеспечение
6.3.1	Программное обеспечение для проведения практических работ: Microsoft Office Excel, Microsoft Office Word.
7 МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ (МОДУЛЯ)
7.1	Программное обеспечение для проведения практических работ: Microsoft Office Excel, Microsoft Office Word, Adobe Reader.

2. Методические указания

Курс «Блочное программирование» является базовым курсом, читаемым для студентов специализации кафедры ТКПМ на четвертом курсе их обучения. С учетом дальнейшей программы обучения студентов по основным дисциплинам и по специализации в данном курсе предполагается углубленное изучение математических методов численного решения задач оптимизации большой размерности, которые используются в задачах системного анализа, исследования операций и теории управления. Прикладная направленность учебного материала – моделирование процессов принятия решений в социальных и экономических системах

Целью преподавания курса является дать студентам комплексное представление о роли и месте дисциплины «Блочное программирование» в специальной профессиональной подготовке студентов по прикладной математике и информатике, формирование процессного мышления при анализе прикладных задач, основных методах и моделях принятия оптимальных решений, в том числе в системах с многими центрами планирования и реализации действий.

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

В результате изучения курса студенты должны: иметь представление о назначении, методах и основных составных приложениях блочного линейного и нелинейного программирования; иметь представление о критериях выбора оптимальных решений, порядке и вариантах построения численных методов в блочном программировании; иметь представление о технологиях исследования реальных систем с использованием математических моделей и компьютерных программ.

Виды контроля: текущий, итоговый (экзамен).

3. Промежуточный и итоговый контроль

3.1. Формы контроля

Промежуточный контроль

В течение семестра студенты выполняют:

-  домашние задания, выполнение которых контролируется и при необходимости обсуждается на практических занятиях;

-  промежуточные индивидуальные задания во время практических занятий для выявления знаний по основным элементам новых разделов теории;

Итоговый контроль

Экзамен в конце курса, включающий проверку теоретических знаний и умение решать практические задачи по всему пройденному материалу.

Учебно-методические материалы для проведения промежуточного контроля прилагаются ниже (на усмотрение преподавателя – либо материалы полностью, либо темы и краткое содержание, либо примерные тесты по дисциплине).

3.2. Контрольные вопросы и задания

1.  Моделей иерархических систем и их классификация. Общая блочная структура задач блочного программирования.

2.  Формальные системы и иерархические игры. Формальная декомпозиция в блочном программировании. Информационная структура систем поиска решений в блочном программировании.

3.  Классификация декомпозиционных моделей иерархических систем. Детерминированные задачи блочного программирования. Аддитивно-блочные структуры. Композиционно-блочные задачи оптимизации.

4.  Задачи блочного программирования с сетевой структурой. Варианты стохастических задач блочного программирования. Примеры.

5.  Метод Данцига-Вульфа. Задача планирования объединения предприятий и структура системы принятия решений. Главная задача. Симплекс метод решения задач линейного программирования с обратной к базису матрицей.

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

7.  Метод декомпозиции Корнаи-Липтака. Схема декомпозиции и построение формальной системы. Варианты алгоритмов в методе Корнаи-Липтака. Основной алгоритм метода Корнаи-Липтака.

8.  Алгоритм, использующий аппроксимацию целевой функции центра. Алгоритм Корнаи-Липтака. Структуры алгоритмов метода Корнаи-Липтака. Правила останова и оценки точности вычислений.

9.  Двойственность и декомпозиция. Теоремы двойственности в математическом программировании. Формальные системы и их декомпозиция. Лагранжевая задача и ее свойства. Схемы численных методов блочного программирования.

10.  Формальная декомпозиция путем разделения ограничений. Схемы закрепления ограничений в аддитивно-блочных и сетевых задачах большой размерности. Формальные системы и их декомпозиция.

11.  Вычислительные схемы метода декомпозиции, основанного на теории двойственности. Структуры алгоритмов. Условия останова. Скорость сходимости. Варианты задач и примеры.

12.  Метод аппроксимации касательными двойственной функции. Алгоритм наискорейшего спуска. Особенности программной реализации.

13.  Прикладные аспекты блочного программирования. Декомпозиционные модели управления персоналом в человеко-машинных системах.

3.3. Критерии оценивания

Итоговая оценка по дисциплине складывается из оценок:

за практические занятия,

за ответы на экзаменационные вопросы.

Критерии оценок за практические занятия:

1.  Выполнение плановых заданий практических занятий.

2.  Выполнение и успешная защита индивидуальных заданий.

3.  Освоение основных понятий по курсу.

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

Критерии оценок за выполнение экзаменационных заданий и собеседование по вопросам:

1. Выполнение зачетного задания по вопросам курса.

2. Оценка при собеседовании по 2 экзаменационным вопросам, выбор которых организовывает преподаватель по существующей процедуре.

В случае возникновения ситуации, когда ответ студента не соответствует ни одному из вышеперечисленных критериев, преподаватель имеет право задавать студенту ограниченное количество (2 – 3) дополнительных вопросов по курсу, допускающих ответ, как в письменной, так и в устной форме (на усмотрение преподавателя).