- •6.030509 «Облік і аудит»
- •Тема 1. Предмет, методи і моделі завдання дисципліни. Класифікація задач.
- •Тема 2. Загальна задача лінійного програмування та деякі з методів її розв’язування.
- •Тема лекції: Математичне моделювання. Економічна та математична постановка матричних та оптимізаційних задач
- •Предмет математичного моделювання.
- •Класификація економіко – математичних моделей. Формальна класіфикація моделей.
- •Задачі математичного програмування.
- •4. Класифікація методів математичного програмування.
- •5. Задачі планування та організації виробництва.
- •5.1. Задача про максимальну рентабельність підприємства.
- •5.2. Задача про завантаження обладнання
- •6. Модель міжгалузевого балансу „Витрати - випуск”.
- •Коефіціети прямих та побічних витрат.
- •Питання для самоконтролю.
- •Тема 3.Загальна задача лінійного програмування та деякі зметодів її розв’язання
- •Тема лекції: Основні теореми та властивості задач лінійного програмування (лп).
- •1. Загальна форма задачі лінійного програмування (лп).
- •2. Основні теореми та властивості задачі лп.
- •3. Графічний метод розв’язання задач мп.
- •Алгоритм знаходження розв’язку задачі мп графічним методом.
- •Питання для самоконтролю.
- •Тема 3.Загальна задача лінійного програмування та деякі з методів її розв’язання
- •Тема лекції: Вирішення задач лп симплекс-методом.
- •1. Представлення задач лп в матричній та векторній формі.
- •2. Симплексний метод розв’язання задач лп. Теоретичні основи симплекс-метода.
- •3. Метод штучної бази.
- •Питання для самоконтролю.
- •Тема лекції: Транспортна задача
- •1 Економічна та математична моделі транспортної задачі.
- •2 Основні теореми транспортної задачі.
- •3. Метод північно-західного кута (діагональний.)
- •5. Метод потенціалів.
- •Питання для самоконтролю.
- •Тема 4. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач.
- •Тема лекції: Двоїста задача лінійного програмування
- •1 Математичні моделі двоїстих задач.
- •3 Взаємозв’язок розв’язків прямої та двоїстої задач.
- •Питання для самоконтролю.
- •Тема 5. Цілочислові задачі лінійного програмування
- •Тема 6. Елементи нелінійного програмування
- •Тема лекції: Задачі нелінійного програмування
- •1. Задачі дробово-лінійного програмування.
- •2. Задачі цілочислового програмування.
- •3. Класичні методи розв’язання задач нелінійного програмування.
- •4. Метод множників Лагранжа.
- •Задачі опуклого програмування.
- •Питання для самоконтролю.
- •Тема 7. Елементи теорії ігор
- •Тема лекції: Матричні ігри
- •1. Акулич и.Л. Математическое программирование в примерах и задачах. – м.: Высшая школа, 1993. – 336 с.
- •2. Іванюта і.Д. Практикум з математичного програмування: Навчальний посібник/ і.Д. Іванюта, в.І. Рибалка, і.А. Рудоміра – Дусятська. – к. : «Слово», 2008. – 296 с.
- •1. Постановка задач теорії ігор з нульовою сумою.
- •Задачі з сідловою точкою. Задачі в чистих стратегіях.
- •Ігри в мішаних стратегіях. Основна теорема теорії ігор.
- •Зведення задач теорії ігор до задач лп.
- •Питання для самоконтролю.
- •Тема 8. Аналіз та управління ризиком в економіці
- •Тема 8. Система показників кількісного оцінювання ступеня ризику
- •Тема лекції: Ризики. Оцінка ризиків.
- •1. Поняття ризику. Причини виникнення, класифікація.
- •Кількісні методи оцінки ризиків
- •Питання для самоконтролю.
4. Метод множників Лагранжа.
Розглянемо задачу НП з обмеженнями – рівностями:
Z=f(x1, x2,….. xn) →max/ min (10)
за умов
gi(x1, x2,….. xn)=bi, i=1,2…..m (11)
в якій f і gi двічі неперервно диференційовані функції.
Для визначення оптимальних точок цієї задачі, введемо набір змінних λi (i=1,2,….m), які називаються множниками Лагранжа, і побудуємо функцію Лагранжа
L(x1, x2,….. xn, λ1, , λ2,...., λm)= f(x1, x2,….. xn) + ∑ λi(bi - gi(x1, x2,….. xn)) (12)
Відшукання умовного екстремуму задачі зводиться до знаходження безумовного екстремуму функції Лагранжа (12). Характер оптимальності з’ясовується аналогічно, як і у випадку безумовного екстремуму.
5. Задачі опуклого програмування.
Означення 1. Функція f(x1, x2,….. xn), що задана на опуклій множені Х, називається опуклою, якщо для будь – яких двох крапок Х1,Х2 є Х і довільного µє[0;1] виконується співвідношення:
f(µX1+(1-µ) X2) ≤ µ f(X1) +(1-µ) f(X2)
Означення 2. Функція f(x1, x2,….. xn), що задана на опуклій множині Х, називається вгнутою, якщо для будь яких двох крапок Х1,Х2 є Х і довільного µє[0;1] виконується співвідношення
f(µX1+(1-µ) X2) ≥ µ f(X1) +(1-µ) f(X2).
Якщо f(x1, x2,….. xn) – опукла, то - f(x1, x2,….. xn) – вгнута.
Загальна постановка задачі опуклого програмування:
Z=f(x1, x2,….. xn) →max (13)
за умов
gi(x1, x2,….. xn) ≤bi, i=1,2…..m (14)
xj ≥0 j=1,2,…..n (15)
де f – вгнута і gi - опуклі функції
Надалі припустимо, що ОДР задачі (13) – (15) не порожня й обмежена.
Теорема 3. Довільний локальний максимум (мінімум) задачі опуклого програмування є глобальним максимумом (мінімумом).
Означення 3. Говорять, що множина ОДР задовольняє умову регулярності, якщо існує хоча б одна крапка
Означення 4. Говорять, що множина допустимих планів (13) – (15) задовольняє умові регулярності, якщо існує хоча б одна крапка х i з області допустимих розв’язків така, що gi(xi)<bi (i=1,2,….m).
Означення 5. Крапка (Х*,Λ*) називається сідловою крапкою функції Лагранжа, якщо L(Х,Λ*) ≤L(Х*,Λ*)≤L(Х*,Λ) для всіх xj ≥0 (j=1,2,…n) і λi≥0 (i=1,2,….m).
Теорема 4. (Куна-Такера). Нехай для ОДР задачі опуклого програмування (13) – (15) виконується умова регулярності. План Х*буде оптимальним планом цієї задачі тоді і тільки тоді, коли існує такий вектор Λ*, λi≥0 (i=1,2,….m), що пара (Х*,Λ*) – сідлова крапка функції Лагранжа.
Зазначимо, що умови Куна-Такера мало придатні для знаходження оптимального розв’язку, вони лише характеризують розв’язок, тобто дають можливість перевірити деякий розв’язок на оптимальність.
Задачі опуклого програмування.
Розглянемо задачу квадратичного програмування, яка є окремим випадком задач опуклого програмування.
Означення 6. Квадратичною формою відносно змінних x1, x2,….. xn називається функція Z, яка має вигляд Z=∑∑сjixixj.
Означення 7. Квадратична форма Z називається додатньо (від’ємно) – визначеною, якщо Z(Х)>0 ( Z(Х)<0) для всіх значень змінних Х, окрім крапки Х=(0,0,……0).
Означення 8. Квадратична форма Z називається додатньо (від’ємно) – напіввизначеною, якщо Z(Х) ≥0 ( Z(Х) ≤0) для будь якого набору значень змінних Х =(x1, x2,….. xn) і, крім того, існує такий набір змінних Х*, де не всі змінні одночасно рівні нулю, що Z(Х) =0.
Теорема 5. Квадратична форма є опуклою функцією, якщо вона додатньо-напіввизначена.
Постановка задачі квадратичного програмування має вигляд:
Z=∑∑сjixixj.+ ∑djxj→max/ min (16)
за умов
∑aijxj ≤bi, (i=1,2…..m) ,
xj ≥0 (j=1,2…..n) ,
де ∑∑сjixixj - від’ємно (додатньо) – напіввизначена квадратична форма.
Алгоритм знаходження розв’язку задачі квадратичного програмування.
Складаємо функцію Лагранжа.
Записуємо необхідні і достатні умови існування сідловок точки для функції Лагранжа.
Використовуючи метод штучного базису, встановлюємо відсутність сідловок крапки для функції Лагранжа, або знаходимо ії координати.
Записуємо оптимальний план початкової задачі й обчислюємо значення цільової функції.