- •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. Поняття ризику. Причини виникнення, класифікація.
- •Кількісні методи оцінки ризиків
- •Питання для самоконтролю.
3 Взаємозв’язок розв’язків прямої та двоїстої задач.
Розглянемо пару двоїстих задач ЛП (1) – (3) і (1)* - (3)*, пряма задача якої записана у канонічному вигляді. Наступна теорема встановлює взаємозв’язок між розв’язками прямої і двоїстої задачами.
Теорема 3. Якщо пряма задача ЛП має оптимальний план Х*, отриманий симплекс методом, то оптимальний план Y* двоїстої задачі визначається за формулою:
Y*=CбазР-1 (4)
де Cбаз – вектор рядок, що складається з коефіцієнтів цільової функції прямої задачі при невідомих, які є базисними в оптимальному плані; Р-1 – матриця, обернена до матриці Р, складеної з компонент базисних векторів оптимального плану задачі.
Таким чином, якщо знайти симплекс методом оптимальний план задачі (1) –(3), то використовуючи останню симплекс таблицю, можна визначити Cбаз і Р-1 та за допомогою співвідношення (5.4), знайти план двоїстої задачі.
Відмітимо, що існує взаємно-однозначна відповідність між змінними: основним змінним прямої задачі відповідають додаткові змінні двоїстої задачі і навпаки:
Змінні прямої задачі |
|||||||
Основні |
Додаткові |
||||||
Х1 |
Х2 |
…….. |
Хк |
Хк+1 |
Хк+2 |
………. |
Хn |
Yn-k+1 |
Yn-k+2 |
…….. |
Yn |
Y1 |
Y2 |
……… |
Yn-k |
Додаткові |
Основні |
||||||
Змінні двоїстої задачі |
|||||||
Ідея двоїстого симплексного методу полягає у зв’язку між розв’язуваннями прямої та двоїстої задач ЛП. Немає потреби окремо розв’язувати пряму задачу, а окремо двоїсту, оскільки розв’язок обох задач можна знайти за одними й тими самими симплекс таблицями, пам’ятаючи, що невідомим прямої задачі відповідають стовпчики таблиці, а невідомим другої – рядки таблиці.
Двоїстий симплекс метод використовується для знаходження розв’язку задачі ЛП, записаної у канонічному вигляді, для якої серед векторів Рj, складених з коефіцієнтів при невідомих у системі рівнянь, є рівно m одиничних.
Також цей метод можна використовувати для знаходження розв’язку задач ЛП, коли вільні члени системи рівнянь є довільними числами (для розв’язування задач симплекс методом числа bi припускались невід’ємними).
Питання для самоконтролю.
Нехай є задача про оптимальне використання ресурсів. Дайте економічну інтерпретацію двоїстої задачі.
Сформулюйте першу теорему двоїстості.
Сформулюйте другу теорему двоїстості.
Перечисліть ознаки взаємно двоїстих задач.
Як по рішенню прямої задачі знайти рішення двоїстої задачі.
В чому полягає ідея двоїстого симплекс методу.
Який економічний зміст основних змінних двоїстої задачі?
Який економічний зміст додаткових змінних двоїстої задачі?
Який економічний зміст перевірки системи обмежень прямої задачі для знайденого оптимального плану?
Що дає перевірка обмежень двоїстої задачі?
Як проводиться аналіз стовбців останньої симплекс таблиці, для яких Δi>0?