МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ

РОЗРОБЛЕНО ТА ВНЕСЕНО: Київським інститутом економіки і менеджменту «ЕКОМЕН».

Обговорено і рекомендовано до друку Президією науково-методичної комісії з напряму підготовки «Менеджмент», 19 жовтня 2001 р., протокол № 4.

ВСТУП

Програма вивчення нормативної дисципліни «Математичне програмування» складена відповідно до місця та значення дисципліни за структурно-логічною схемою, передбаченою освітньо-професійною програмою підготовки бакалавра з напряму 0502 «Менеджер», і охоплює всі змістовні модулі, визначені анотацією для мінімальної кількості годин, передбачених стандартом.

Предметом вивчення дисципліни «Математичне програмування» є математичні властивості та закономірності пошуку екстремуму функцій і функціоналів, методи та алгоритми оптимізації. Міждисциплінарні зв'язки: дисципліна «Математичне програмування» викладається після вивчення студентами курсу «Вища математика» та передує вивченню курсу «Дослідження операцій», «Економетрія». Програма дисципліни «Математичне програмування» складається з таких розділів:

1. Мета та завдання дисципліни.
2. Зміст дисципліни.
3. Список рекомендованої літератури.

2. МЕТА ТА ЗАВДАННЯ ДИСЦИПЛІНИ «МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ»

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

1.2.Основними завданнями, що мають бути вирішені у процесі викладання дисципліни, є надання студентам систематизованих знань з основних математичних методів розв'язування оптимізаційних задач та формування умінь:

- постановки та формалізації економіко-управлінськиих задач;
- класифікувати задачі та методи математичного програмування;
- розв'язувати задачі лінійного прямування, використовувати симплекс-метод;
- економічно Інтерпретувати теореми двоїстості;
- розв'язувати транспортні задачі;
- здійснювати цілочисельне програмування, нелінійне програмування, динамічне програмування, стохастичне програмування;
- використовувати ПЕОМ і відповідне програмне забезпечення при проведенні оптимізаційних розрахунків та аналізі результатів цих розрахунків.

2. ЗМІСТ ДИСЦИПЛІНИ

Тема 1. Предмет дисципліни

Загальна постановка оптимізаційної задачі, її структура: цільова функція, обмеження як спосіб опису множини допустимих планів. Змістовні приклади задач математичного програмування в економіці, менеджменті. Означення розв'язку задачі математичного програмування: оптимальний план, оптимальне значення цільової функції, точка оптимуму; проблема його пошуку. Геометрична ілюстрація простих оптимізаційних задач з однією та двома змінними.

Класифікація задач і методів математичного програмування: лінійне та нелінійне, цілочислове (дискретне). Поняття про дробово-лінійне, квадратичне, геометричне, опукле, динамічне, потокове, параметричне та стохастичне програмування.

Тема 2. Лінійне програмування

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

Канонічна задача лінійного програмування, основні форми її запису: розгорнута, за допомогою векторів умов, матрична. Правила переходу від загальної задачі лінійного програмування до канонічної.

Дослідження канонічної задачі лінійного програмування: поняття опорного плану, теореми про існування опорного плану, оптимального опорного плану, про геометричні властивості опорного та не опорного планів, про розв'язування канонічної задачі.

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

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

Розв'язування задач лінійного програмування на ПЕОМ.

Тема 3. Двоїстість у лінійному програмуванні

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

Теорія двоїстості для випадків, коли вихідною є загальна задача лінійного програмування або канонічна задача. Поняття про двоїстий симплекс-метод.

Опрацювання стандартної інформації про післяоптимізаційний аналіз розв'язування задачі лінійного програмування на ПЕОМ.

Тема 4. Методика розв'язування транспортної задачі

Постановка транспортної задачі, умова існування її розв'язку. Пошук оптимального опорного плану перевезень за методом потенціалів. Розв'язування транспортної задачі на ПЕОМ.

Тема 5. Цілочислове програмування

Економічні приклади, математична постановка задач цілочислового (дискретного) програмування. Метод відтинань і метод розгалуженого пошуку для розв'язування задач цілочислового лінійного програмування. Розв'язування оптимізаційних задач з цілочисловими або логічними (бульовими) змінними на ПЕОМ.

Тема 6. Нелінійне Програмування

Причини виникнення і приклади нелінійностей в оптимізаційних економічних задачах. Класи задач нелінійного програмування: одновимірні та багатовимірні, з обмеженнями або без обмежень. Поняття про окремі підкласи задач: квадратичного, геометричного, дробово-лінійного, опуклого програмування тощо. Різниця між глобальним та локальним оптимумами, точним та наближеним розв'язками задачі. Огляд методів одновимірної оптимізації: непрямих (класична схема пошуку стаціонарних точок, половинного поділу, дотичних, січних), прямих (рівномірний пошук, рівномірний випадковий пошук, метод ламаних, пошук за золотим перерізом). Багатовимірна задача оптимізації без обмежень, її основні властивості (достатня умова існування розв'язку; необхідна умова локального екстремуму першого порядку - теорема Ферма, необхідна і достатня умови другого порядку, особливості задачі максимізації вгнутої функції). Класична схема багатовимірної оптимізації без обмежень за теоремою Ферма; обмеженість класичної схеми. Непрямі методи (градієнтний та його різновиди за правилом вибору крокового множника; поняття про метод Ньютона та квазіньютонівські методи); прямі методи (на основі скінченно-різницевої апроксимації градієнта та гессіана цільової функції, покоординатного підйому тощо).

Властивості багатовимірної задачі оптимізації з обмеженнями (достатні умови існування розв'язку; необхідна умова локального екстремуму в термінах можливих напрямків і напрямків зростання цільової функції; особливості задачі опуклого програмування). Функція Дагранжа та її сідлові точки; двоїстість у нелінійному програмуванні. Умови оптимальності, засновані на застосуванні диференціального числення; теорема Куна-Таккера. Поняття про методи багатовимірної оптимізації з обмеженнями (проектування, можливих напрямків, лінеаризації, штрафних функцій).

Розв'язування задач нелінійного програмування на ПЕОМ.

Тема 7. Динамічне програмування

Загальна постановка задачі динамічного програмування. Основні типи задач і моделей динамічного програмування. Багатокроковий процес прийняття рішень і динамічне програмування. Метод рекурентних співвідношень. Принцип оптимальності Беллмана.

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

Тема 8. Стохастичне програмування

Загальна постановка задачі стохастичного програмування, її особливості щодо оперативного управління та перспективного планування. Класифікація задач стохастичного програмування. Методи розв'язування задач стохастичного програмування (непрямі, прямі), приклади їх реалізації. Можливість та ефективність застосування методів стохастичного програмування для розв'язування детермінованих оптимізаційних задач.

Тема 9. Основи теорії ігор

Основні поняття теорії ігор. Приклади ігрових задач в економіці та менеджменті. Матричні ігри двох осіб. Платіжна матриця. Гра у чистих стратегіях. Максимінна та мінімаксна стратегії. Сідлова точка. Змішані стратегії. Основна теорема теорії матричних ігор. Зведення антагоністичної матричної гри двох осіб до задачі лінійного програмування.

3. СПИСОК РЕКОМЕНДОВАНОЇ ЛІТЕРАТУРИ

1. Богаєнко І.М., Григорків В.С., Бойчук М.В., Рюмашин М.О. Математичне програмування: Навч. посіб. - К.: Логос, 1996.
2. Бугір М.К. Зошит для практичних занять з математичного програмування. - Тернопіль: Підручники і посібники, 1999.
3. Бугір М.К. Математика для економістів. Лінійна алгебра, лінійні моделі: Навч. посіб. - К.: ВЦ «Академія», 1998.
4. Гвоздинський А.М. Оптимізаційні задачі в організаційному управлінні: Навч. посіб. - Харків: ХДТУР, 1997.
5. Гетманцев В.Д. Лінійна алгебра і лінійне програмування: Навч. посіб. - К.: Либідь, 2001.
6. Григорків В.С., Бойчук М.В. Практикум з математичного програмування: Навч. посіб. -Чернівці: Прут, 1995.
7. Деордица Ю.С., Савченко В.Т. Компьютерные технологии в экономике и менеджменте: Учеб. пособие. - Луганск: ВУГУ, 1999.
8. Зайченко Ю.П. Дослідження операцій: Підручник, ж К.: ВІПОЛ, 2000.
9. Исследование операций в экономике: Учеб. пособие / Под ред. Н.Ш. Кремера. -М.: ЮНИТИ, 1999.
10. Кігель В.Р. Елементи лінійного, цілочислового лінійного, нелінійного програмування: Навч. посіб. -К.: ІСДО, 1995.
11. Мазаракі А.А., Толбатов Ю.А. Математичне програмування в ЕхсеШавч. посіб. - К.: Четверта хвиля, 1998.
12. Романюк Т.П., Терещенко Т.А., Присенко Г.В., Городкова І.М. Математичне програмування: Навч. посіб. - К.: ГЗМН, 1996.
13. Цегелик Г.Г. Лінійне програмування: Навч. посіб. - Львів: Світ, 1995.
14. Экономико-математические методы и прикладные модели: Учеб. пособие / Под ред. В.В. Федосеева. - М.: ЮНИТИ, 1999.
15. Крушевський А.В. Справочник по экономико-математическим моделям и методам. - К.: Техника, 1982, - 208 с.
16. Вивальнюк Л.М. Елементи лінійного програмування. - К.: Вищашк., 1975,-191 с.
17. Шуенкин В.А., Жуков И.А. Основы математического программирования. - К.: КМУГА, 1999, - 306 с.
18. Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высш. Шк.», 1986, -319с.
19. Ляшенко И.Н. Линейное и нелинейное программирование. -К.: Вища шк., 1975. - 371с.