- •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. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач.
Лекція 5.
Тема лекції: Двоїста задача лінійного програмування
Мета: ознайомити студентів з методами розв’язання двоїстих задач лінійного програмування, показати взаємозв’язок прямої та двоїстої задач.
План лекції
1. Математичні моделі двоїстих задач.
2. Основні теореми теорії двоістості.
3. Взаємозв’язок розв’язків прямої та двоїстої задач.
Література:
Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.
2. Іванюта І.Д. Практикум з математичного програмування: Навчальний посібник/ І.Д. Іванюта, В.І. Рибалка, І.А. Рудоміра – Дусятська. – К. : «Слово», 2008. – 296 с.
3. Кучма М.І. Математичне програмування: приклади і задачі: Навчальний посібник/ М.І. Кучма. - Львів: «Новий Світ - 2000», 2006. – 344 с.
4. А. Черемис, Р. Юринець, О. Мищишин. Методи оптимізації в економіці. Навчальний посібник. – К.: Центр навчальної літератури, 2006. – 152 с.
1 Математичні моделі двоїстих задач.
З кожною задачею лінійного програмування зв’язана деяка інша цілком визначена, задача лінійного програмування яка називається двоїстою.
Початкова задача називається прямою задачею ЛП. Ці дві задачі тісно пов’язані між собою і утворюють єдину пару двоїстих задач.
Якщо пряма задача ЛП має вигляд:
Z=∑cixi →max (1)
за умов
∑aijxj ≤bi, (i=1,2…..m) (2)
xj ≥0 (j=1,2…..n) (3)
то двоїста задача записується так:
F=∑biyi →min (1*)
за умов
∑aijyi≥ cj, (j=1,2…..n) (2*)
yi≥0 (i=1,2…..m) (3*)
В матричному вигляді їх можна представити таким чином:
Пряма задача
, xj ≥0 (j=1,2…..n)
де А – матриця системи обмежень задачі розміром mxn;
В – вектор стовпець;
С – вектор строка;
АХ≤В;
Z →max.
Двоїста задача
tr = , yi ≥0 (i=1,2…..m)
де trA – транспонована матриця А;
trС – транспонований вектор С;
trB - транспонований вектор В;
AY ≥trC;
F →min.
У несиметричних парах двоїстих задач обмеження прямої задачі можуть бути записані як рівняння (у канонічному вигляді), а двоїстої – лише як нерівності. Якщо у цільовій функції двоїстої задачі вимагається знайти мінімум, то система обмежень матиме знак «≥», якщо максимум, то знак «≥» .
Моделі несиметричних пар цих задач можна зобразити у вигляді:
Пряма задача |
Двоїста задача |
Z=∑cixi →max/min за умов ∑aijxj =bi, (i=1,2…..m)
xj ≥0 (j=1,2…..n)
|
F=∑biyi →min/max за умов ∑aijyi≥/≤ cj, (j=1,2…..n)
yi є(-∞,∞) (i=1,2…..m)
|
Математична модель прямої задачі мішаної пари двоїстих задач містить обмеження, записані як рівняння, так і нерівності, причому знаків різних, за виглядом. Для складання двоїстої задачі необхідно привести всі нерівності системи обмежень прямої задачі до одного вигляду: якщо пряма задача на максимум, то всі нерівності обмежень приводимо до вигляду «≤», якщо на мінімум до вигляду «≥». Нерівності, для яких дані вимоги не виконуються, домножимо на (-1).
2. Основні теореми двоїстості.
Розглянемо пару даоїстих задач, утворену канонічною задачею ЛП і двоїстої до неї:
Пряма:
Z=∑cixi →max/min
за умов
∑aijxj =bi, (i=1,2…..m)
xj ≥0 (j=1,2…..n)
Двоїста:
F=∑biyi →min/max
за умов
∑aijyi≥/≤ cj, (j=1,2…..n)
yi є(-∞,∞) (i=1,2…..m)
Між прямою і двоїстою задачами ЛП існує тісний взаємозв’язок, який видно з наведених далі лем та теорем.
Лема 1. Якщо Х – деякий план прямої задачі, Y – довільний план двоїстої задачі, то значення цільової функції прямої задачі при плані Х не перевищує значення цільової функції двоїстої задачі при плані Y, тобто
Z(X)≤F(Y)
Лема 2. Якщо Z(X*)=F(Y*), та X* - оптимальний план прямої задачі, то Y* - оптимальний план двоїстої задачі.
Теорема 1. (перша теорема двоїстості). Якщо одна із пар двоїстих задач має оптимальний план, то і друга задача має оптимальний план і значення цільової функції при їх оптимальних планах рівні між собою, тобто Z(X*)=F(Y*).
Якщо ж цільова функція однієї із двоїстих задач необмежена (для прямої задачі - зверху, а для двоїстої з низу), то множина планів двоїстої задачі є порожньою.
Теорема 2. (друга теорема двоїстості) . Для того щоб плани Х* і Y* відповідно до задач (1) – (3) і (1*) – (3*) були оптимальними планами цих задач, необхідно і достатньо, щоб для кожного j (j=1,2…..n) виконувалась рівність:
(a1j(y1)* + a2j(y2)* + ……. + amj(ym)* - cj)(xj)* = 0
Економічну інтерпретацію двоїстої задачі розглянемо на прикладі задачі про оптимальне використання ресурсів, математична модель якої має вигляд:
Z=∑cixi →max
за умов
∑aijxj =bi, (i=1,2…..m)
xj ≥0 (j=1,2…..n)
Двоїста задача до неї буде така:
F=∑biyi →min
за умов
∑aijyi≥ cj, (j=1,2…..n)
yi ≥0 i=1,2…..m
Приклад. Підприємство виготовляє три види продукції А,В,С.
Дані задачі приведені у таблиці:
Види сировини |
Норми витрат сировини (кг) |
Запаси сировини |
||
А |
В |
С |
||
S1 |
18 |
15 |
12 |
360 |
S2 |
6 |
4 |
8 |
192 |
S3 |
5 |
3 |
3 |
180 |
Ціна від реалізації 1-ї одиниці продукції |
3 |
1 |
3 |
|
Знайти такий план випуску продукції, щоб прибуток від їх реалізації був максимальним.