ММДО_РАБ ПРОГ(+)

Харківський національний університет радіоелектроніки

Кафедра «Інформаційних управляючих систем» Кафедра «Штучного інтелекта» Кафедра «Системотехніки»

ЗАТВЕРДЖУЮ Декан факультету __КН__

___________ В.П. Машталір

(підпис, ініціали, прізвище)

"____" ____________20___ р.

РОБОЧА ПРОГРАМА НАВЧАЛЬНОЇ ДИСЦИПЛІНИ

____________Математичні методи дослідження операцій__________

(шифр і назва навчальної дисципліни)

напрям підготовки ______6.050101 «Комп’ютерні науки»____________

(шифр і назва напряму підготовки)

спеціальність ___________________________________________________________

(шифр і назва спеціальності)

спеціалізація____________________________________________________________

(назва спеціалізації)

факультет ___________________Комп’ютерних наук_______________________

(назва факультету)

Харків – 2013 р.

Робоча програма з дисципліни «Математичні методи дослідження операцій» для студентів усіх форм навчання за напрямом підготовки 6.050101 «Комп’ютерні науки» "___” ________ 2013 р. – 14 с.

Розробники: А.М. Гвоздинський, проф. каф. ШІ, к.т.н., професор Н.В. Васильцова, доц. каф. ІУС, к.т.н., доцент

Робочу програму схвалено на засіданні кафедри «Інформаційних управляючих систем»

Протокол від “ 25 ” грудня 2013 р. № 6

Завідувач кафедри ІУС ____________ В.М. Левикін

(підпис)

“_____”___________________ 2013 р.

Робочу програму схвалено на засіданні кафедри «Штучного інтелекта»

Протокол від “ 9 ” січня 2014 р. № 15

В.о. завідувача кафедри ШІ ____________ Н.В. Рябова

(підпис)

“_____”___________________ 2013 р.

Робочу програму схвалено на засіданні кафедри «Системотехніки»

Протокол від “ ”		20				р. №
Завідувач кафедри СТ				____________			І.В. Гребеннік
				(підпис)
“_____”___________________ 20						р.

Схвалено методичною комісією факультету КН
Протокол від “ 22 ” січня			2014 р. № 5
Голова методичної комісії			_______________	А.В. Міхнова
			(підпис)	(ініціали, прізвище)

“_____”___________________ 2014 р.

Гвоздинський А.М., 2013Васильцова Н.В., 2013ХНУРЕ, 2013

2

1 ОПИС НАВЧАЛЬНОЇ ДИСЦИПЛІНИ

Характеристика навчальної

Найменування

Галузь знань, напрям

дисципліни

підготовки, освітньо-

показників

денна

заочна форма

кваліфікаційний рівень

форма

навчання

навчання

Галузь знань

Кількість кредитів

0501 «Інформатика та

Цикл

природничо-наукової

обчислювальна техніка»

підготовки (бакалавр)

4

Напрям підготовки

6.050101 «Комп’ютерні науки»

Модулів 2

Рік підготовки:

Змістових модулів

3-й

4-й

3

Спеціальності:

Індивідуальних

завдань: 2

7.05010101 «Інформаційні

Семестр

управляючі системи та

технології»

5-й

7-й

Загальна кількість

Кількість годин

годин 120

120

120

Аудиторні: 1) лекції, год

32

4

2) практичні, год

12

4

3) лабораторні, год

Тижневих годин

12

8

4) консультації, год

для денної форми

8

-

навчання:

Освітньо-кваліфікаційний

Самостійна робота, год

аудиторних –

рівень: бакалавр

56

104

самостійної

в тому числі: 1) інд. завд., год.

роботи студента –

2

20

2) курсова робота, год

-

Вид контролю:

Комб.

іспит

іспит

Примітка.

Співвідношення кількості годин аудиторних занять до загальної кількості годин становить: для денної форми навчання – 53,33%; для заочної форми навчання – 13,33%.

3

2 МЕТА І ЗАВДАННЯ НАВЧАЛЬНОЇ ДИСЦИПЛІНИ

Мета:

Вивчення загально-методологічних принципів побудови операційних моделей, основних етапів і сутності операційних досліджень і здатність їх застосовувати під час аналізу та синтезу інформаційних систем різного призначення та в завданнях організаційноекономічного управління.

Завдання: за результатом вивчення дисципліни студенти повинні:

знати:

загальну методологію та методику проведення дослідження операцій;

типові класи задач дослідження операцій;

математичні моделі оптимізаційних задач та класифікацію задач математичного програмування;

методи розв'язання лінійних оптимізаційних задач (графічні та аналітичні);

загальні методи розв'язання задач дискретного, параметричного, динамічного, стохастичного програмування;

математичний апарат розв'язання задач нелінійного програмування, основні алгоритми відшукання розв'язку;

основні методи оптимізації функцій, що диференціюються і що не диференціюються;

основні методи оптимізації в задачах великої розмірності;

основні задачі та методи багатокритеріальної оптимізації;

методи аналізу розв'язку задач оптимізації.

вміти:

аналізувати та моделювати проблемні ситуації;

обґрунтовувати застосування методів оптимізації щодо розв'язання конкретних

задач;

проводити геометричну інтерпретацію задач лінійного програмування;

розв'язувати лінійні оптимізаційні задачі за допомогою симплексного методу та його модифікацій;

розв'язувати лінійні оптимізаційні задачі (транспортні задачі, задачі про призначення) за допомогою спеціальних методів;

розв'язувати нелінійні задачі цілочислового програмування методом Гоморі та методом віток і меж;

здійснювати комп’ютерну реалізацію розв’язання задач лінійного програмування та багатокритеріальних оптимізаційних задач;

аналізувати розв'язки задач оптимізації.

володіти (перелік компетенцій):

знаннями загально-методологічних принципів побудови операційних моделей, основних етапів і сутності операційних досліджень та вміннями їх застосовувати під час здійснення аналізу та синтезу інформаційних систем різного призначення та в завданнях організаційно-економічного управління;

базовими знаннями в області загальної постановки задач математичного програмування, в області лінійного математичного програмування, в області вирішення задач лінійного програмування симплексним методом, області вирішення спеціальних задач математичного програмування (транспортних задач), в області параметричного програмування, нелінійного, дискретного програмування, квадратичного програмування;

базовими знаннями в області оптимізації функцій, що диференціюються, та функцій, що не диференціюються, в області оптимізації в задачах великої розмірності;

вміннями застосовувати базові знання в науково-дослідній і професійній діяльності.

4

3 ПРОГРАМА НАВЧАЛЬНОЇ ДИСЦИПЛІНИ

Змістовий модуль 1. Лінійне та нелінійне програмування Тема 1. Введення в дисципліну. Побудова математичних моделей проблемних

ситуацій. Загальна методологія дослідження операцій. Модель операції, основні принципи її побудови. Методика проведення дослідження операцій. Типові класи задач дослідження операцій.

Тема 2. Задачі математичного програмування (МП). Загальна постановка задачі МП. Класифікація задач МП. Типи максимумів. Теорема Вейєрштрасса та теореми про достатні умови глобального максимуму. Специфіка задач математичного програмування.

Тема 3. Лінійне програмування. Загальна постановка задачі лінійного програмування (ЗЛП). Форми запису ЗЛП.

Тема 4. Приклади практичних задач лінійного програмування: задача оптимального використання ресурсів виробництва; задача оптимального вибору технологій; задача про суміші; задача про розкрій; транспортна задача; задача про призначення; задача оптимізації міжгалузевих зв’язків (сам. роб.).

Тема 5. Геометрична інтерпретація ЗЛП. Графічний метод розв'язання ЗЛП. Умови графічного розв'язання ЗЛП. З’ясування основних особливостей та властивостей розв’язків ЗЛП за допомогою геометричної інтерпретації. Основні етапи графічного розв'язання ЗЛП (Алгоритм геометричної інтерпретації ЗЛП).

Тема 6. Симплексний метод розв'язування ЗЛП. Аналітичні методи розв'язування ЗЛП. Ідея симплексного методу розв'язування ЗЛП. Основні теореми, на яких базується симплексний метод. Симплекс-алгоритм розв'язування невироджених ЗЛП.

Тема 7. ЗЛП з штучним базисом. Ідея симплексного методу розв'язування ЗЛП із штучним базисом. М-задача. Алгоритм розв'язання ЗЛП із штучним базисом.

Тема 8. Двоїстість. Двоїстість (спряженість) у лінійному програмуванні. Поняття двоїстості у лінійному програмуванні. Моделі двоїстих задач лінійного програмування. Основні теореми двоїстості та їх економічний зміст.

Тема 9. Двоїстий симплекс-метод. Алгоритм розв'язання двоїстого симплекс-методу. (сам. роб.)

Тема 10. Спеціальні задачі МП. Спеціальні методи розв’язання ЗЛП. Транспортна задача (Т-задача) та її математична модель. Задача про призначення та її математична модель. Методи розв’язання Т-задач. Методи визначення опорного плану. Розв’язання Т- задач методом потенціалів.

Тема 11. Розв’язання задач про призначення (сам. роб.).

Тема 12. Постоптимальний аналіз. Аналіз розв'язку задач оптимізації. Напрямки аналізу.

Тема 13. Параметричне програмування. Зміст задач параметричного програмування. Моделі задач параметричного програмування. Алгоритми розв'язування задач параметричного програмування.

Тема 14. Нелінійне програмування. Загальна постановка задачі нелінійного програмування. Класичні умови екстремуму. Метод множників Лагранжа. Класичні методи оптимізації. ЗНП за умови невід’ємності змінних. Задача нелінійного програмування і сідлова точка. Умови Куна-Таккера для ЗНП. Теорема Куна-Таккера.

Тема 15. Задача квадратичного програмування (ЗКП). Модель задачі квадратичного програмування. Основні визначення ЗКЛ. Метод і алгоритм Франка-Вулфа.

Тема 16. Сепарабельне програмування. Визначення сепарабельної функції. Метод кусково-лінійної апроксімації. (сам.роб.)

Тема 17. Задачі дробово-лінійного (гіперболічного) програмування. (сам.роб.)

5

Змістовий модуль 2. Дискретне та стохастичне програмування.

Тема 1. Дискретне програмування. Загальні характеристики дискретних задач. Математичні моделі задач дискретного програмування. Класифікація задач дискретного програмування. Спеціальні методи розв'язування задач дискретного програмування.

Тема 2. Клас цілочислових лінійних задач. Особливості задач цілочислового програмування. Метод відсікань (метод Гоморі) розв’язування ЗЦЛП. Комбінаторні методи розв’язування ЗЦЛП.

Тема 3. Метод гілок та меж в задачах цілочислового програмування. Ідея методу гілок і меж, ознака оптимальності плану.

Тема 4. Динамічне програмування. Загальна структура задач динамічного програмування. Принципи динамічного програмування. Принцип оптимальності Беллмана. Приклади задач динамічного програмування.

Тема 5. Стохастичне програмування. Методи розв’язання задач стохастичного програмування. Приклади задач стохастичного програмування (сам. роб.).

Змістовий модуль 3. Методи оптимізації.

Тема 1. Методи оптимізації функцій, що диференціюються та що не диференціюються. Методи оптимізації функцій, що диференціюються. Методи оптимізації функцій, що не диференціюються.

Тема 2. Методи оптимізації в задачах великої розмірності та методи багатокритеріальної оптимізації. Методи оптимізації в задачах великої розмірності. Задачі та методи багатокритеріальної оптимізації.

4 СТРУКТУРА НАВЧАЛЬНОЇ ДИСЦИПЛІНИ

Назви змістових

Кількість годин

денна форма

Заочна форма

модулів і тем

Усь-

у тому числі

Усь-

у тому числі

го

л

пр

лб

конс

с.р.

ого

л

пр

лб

конс

с.р.

1

2

3

4

5

6

7

8

9

10

11

12

13

Модуль 1

Змістовий модуль 1. Лінійне та нелінійне програмування.

Тема 1.

Введення в дисцип-

4

2

1

1

5

2

3

ліну. Побудова математич-

них

моделей

проблемних

ситуацій. Загальна методоло-

гія

дослідження

операцій.

Модель

операції,

основні

принципи її побудови. Мето-

дика проведення дослідження

операцій. Типові класи задач

дослідження операцій.

Тема

2.

Задачі

математич-

3,5

1

1,5

3

3

ного програмування (МП).

Загальна

постановка

задачі

МП. Класифікація задач МП.

Типи максимумів.

Специфіка

2

задач МП.

Тема

3.

Лінійне

програму-

6

2

1

2

3

3

вання.

Загальна

постановка

задачі лінійного програмував-

ня (ЗЛП). Форми запису ЗЛП.

Тема 4.

Приклади практич-

2

-

2

3

3

них

задач

лінійного

програмування:

задача

оптимального

вико-ристання

6

ресурсів виробництва;

задача

оптимального

вибору

технологій; задача про суміші;

задача про розкрій; транспортна

задача; задача про призначен-

ня; задача оптимізмції між-

галузевих зв’язків. (сам. роб.)

Тема

5.

Геометрична

8

2

2

1

3

7

2

5

інтерпретація ЗЛП.

Графічний метод розв'язання

ЗЛП.

Умови

графічного

розв'язання ЗЛП. Основні

етапи графічного розв'язання

ЗЛП

(алгоритм

геометричної

інтерпретації ЗЛП).

Тема 6. Симплексний метод

10

2

1

4

3

3

розв'язування ЗЛП.

Аналітичні методи розв'язу-

вання ЗЛП. Ідея симплексного

методу розв'язування ЗЛП.

Основні теореми, на яких

базується симплексний метод.

2

4

Симплекс-алгоритм розв'язу-

вання невироджених ЗЛП.

Тема

7.

ЗЛП

з

штучним

9

2

4

11

4

7

базисом.

Ідея

симплексного

методу розв'язування ЗЛП із

штучним базисом. М-задача.

Алгоритм розв'язування ЗЛП

із штучним базисом.

Тема

8.

Двоїстість.

Двоїс-

3

2

1

3

3

тість

(спряженість)

у

лінійному

програмуванні.

Поняття двоїстості у ліній-

ному

програмуванні.

Моделі

двоїстих

задач

лінійного

програмування.

Основні

теореми

двоїстості

та

їх

економічний зміст.

Тема 9. Двоїстий симплекс-

2

-

2

3

3

метод. Алгоритм розв'язання

двоїстого

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

(сам. роб)

Тема

10.

Спеціальні задачі

19

4

2

4

1

8

7

2

5

МП.

Спеціальні

методи

розв’язання ЗЛП. Транспорт-

на задача (Т-задача) та її

математична

модель.

Задача

про призначення та її матема-

тична модель. Методи розв’я-

зання Т-задач. Методи визна-

чення

опорного

плану.

Розв’язання Т-задач методом

потенціалів.

Тема 11.

Розв’язання задач

10

-

4

6

11

4

7

про призначення (сам. роб.)

Тема

12.

Постоптимальний

2

-

2

3

3

аналіз. Аналіз розв'язку задач

оптимізації.

Напрямки

аналізу. (сам. роб.)

7

Тема	13.			Параметричне				1,5	1					0,5	3					3
програмування.					Зміст задач
параметричного					програмував-
ня. Моделі задач параме-
тричного				програмування.
Алгоритми розв'язування задач
параметричногопрограмування.
Тема 14. Нелінійне програ-								4	2				1	1	3					3
мування.						Загальна
постановка задачі нелінійного
програму-вання.						Класичні
умови		екстремуму.					Метод
множників Лагранжа. ЗНП за
умови невід’ємності змінних.
Задача					нелінійного
програмування					і		сідлова
точка. Умови Куна-Таккера
для ЗНП. Теорема Куна-
Таккера.
Тема 15. Задача квадратич-								3	2					1	3					3
ного програмування (ЗКП).
Модель задачі				квадратичного
програмування.						Основні
визначення ЗКЛ. Метод і
алгоритм Франка-Вулфа.
Тема		16.		Сепарабельне				2	-					2	3					3
програмування.					Визначення
сепарабельної				функції.			Метод
кусково-лінійної апроксимації.
(сам.роб.)
Тема	17.		Задачі			дробово-		2	-					2	3					3
лінійного			(гіперболічного)
програмування (сам.роб.).
Разом за зміст. модулем 1								91	22	8	12		6	43	77	2	4	8		63
Усього годин за мод. 1								91	22	8	12		6	43	77	2	4	8		63
										Модуль 2
				Змістовий модуль 2. Дискретне та стохастичне програмування.
Тема	1.	Дискретне				програ-		4	2				1	1	4	1				3
мування. Загальні характери-
стики		дискретних					задач.
Математичні				моделі			задач
дискретного				програмування.
Класифікація				задач		дискрет-
ного програмування. Спеці-
альні методи розв'язування
задач	дискретного						програ-
мування.
Тема 2.		Клас цілочислових						3,5	1					1,5	3					3
лінійних		задач.			Особливості
задач	цілочислового						програ-
мування.		Метод				відсікань
(метод Гоморі) розв’язування
ЗЦЛП.	Комбінаторні						методи			2
розв’язування ЗЦЛП.
Тема 3. Метод гілок та меж								3,5	1					1,5	3					3
в задачах				цілочислового
програмування.					Ідея		методу
гілок		і	меж,				ознака
оптимальності плану.
Тема 4.		Динамічне програ-						7	2	2				3	3					3
											8

мування. Загальна				структура
задач динамічного				програму-
вання. Принципи динамічного
програмування.				Принцип
оптимальності				Беллмана.
Приклади задач			динамічного
програмування.
Тема 5. Стохастичне програ-							2		-				2		3								3
мування. Методи розв’язання
задач	стохастичного				програ-
мування.		Приклади			задач
стохастичного програмування.
(сам. роб.)
Разом за зміст. модулем 2							20		6	4		1	9		16		1		-	-		-	15
					Змістовий модуль 3. Методи оптимізації.
Тема 1.		Методи оптимізації					4		2			1	1		4		1						3
функцій, що диференцію-
ються та що не диферен-
ціюються. Методи оптиміза-
ції функцій, що диференцію-
ються.		Методи		оптимізації
функ-
цій, що не диференціюються
Тема 2.		Методи оптимізації					3		2				1		3								3
в задачах великої розмір-
ності та методи багато-
критеріальної			оптимізації.
Методи оптимізації в задачах
великої розмірності. Задачі та
методи		багатокритеріальної
оптимізації.
Разом за зміст. модулем 3							7		4	-	-	1	2		7		1						6
Усього годин за мод. 2							27		10	4		2	11
								Індивідуальні завдання
Контрольна робота (аудиторна,							2						2
для денної форми навчання)
ІДЗ (позааудиторна контрольна													-		20								20
робота		для заочної			форми
навчання)
Усього годин за семестр							120		32	12	12	8	56		120		4		4	8		-	104
							5 ТЕМИ ПРАКТИЧНИХ ЗАНЯТЬ
№							Назва теми												Кількість годин
																		денна				заочна
1	Постановка та форми запису задач лінійного програмування																	2				-
2	Геометрична інтерпретація задач лінійного програмування																	2				2
3	Симплексний метод розв’язання задач лінійного програмування																	2				-
4	Розв’язання транспортних задач методом потенціалів.																	2				2
5	Методи вирішення ЗЦЛП. Метод Гоморі. Метод віток і меж																	2				-
6	Вирішення задач розподілу ресурсів.																	2				-
	Загальна кількість																	12				4
						5 ТЕМИ ЛАБОРАТОРНИХ ЗАНЯТЬ
№							Назва теми												Кількість годин
																		денна				заочна
1	Комп’ютерна				реалізація				розв’язання			задач	лінійного					4				4
											9

	програмування симплекс-методом
2	Комп’ютерна	реалізація	розв’язання	задач	лінійного	4	-
	програмування Т-типу
3	Розв’язання задач про призначення					4	4
	Загальна кількість					12	8

10