Дослідження операцій і дискретний аналіз - Навчально-методичні матеріали (О.С. Катуніна)

Теми практичних І семІнарських занять

 

Заняття 1

 

ТЕМИ 5—6. Елементи теорії множин і комбінаторного

аналізу. Математична логіка і теорія графів

 

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

Поняття відповідностей, відношень та іх властивостей щодо відображення взаємозв’язків економічних систем.

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

Проблематика й використання комбінаторного аналізу в економіці.

Поняття алгебри висловлювань. Нормальні диз’юнктивні та кон’юнктивні форми.

Елементи теорії доведень на підґрунті раціональних гіпотез щодо економічних процесів і систем.

Прикладне застосування теорії графів.

 

Заняття 2

 

ТЕМА 9. Детерміновані моделі та методи оптимізації

 

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

Симплексний метод розв’язання задач ЛП.

Постановка й методи розв’язання транспортної задачі ЛП. Двоетапні економічні задачі.

Методи розв’язання цілочисельних задач ЛП.

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

 

Заняття 3

 

ТЕМА 10. Стохастичні моделі та методи

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

 

Економіко-математична постановка задачі стохастичного програмування.

Практичні підходи до побудови системи гіпотез щодо формалізації задач СП.

Методи стохастичних квазіградієнтів та імітаційного моделювання розв’язання задач СП.

Розв’язання задачі планування обсягу реалізації продукції за невизначеного попиту як одноетапної статичної задачі СП.

Побудова, розв’язання й аналіз прикладних двоетапних задач СП на прикладі виробничо-транспортної задачі.

 

Заняття 4

 

ТЕМА 12. Дискретні динамічні моделі економічних систем. Динамічне програмування

 

Приклади дискретних динамічних моделей економічних систем.

Поняття багатокрокового процесу прийняття рішень і побудова моделей динамічного програмування.

Метод рекурентних співвідношень і принцип оптимальності Белмана щодо розв’язання задач ДП.

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

 

ТИПОВІ ЗАВДАННЯ ДЛЯ ПРАКТИЧНИХ ЗАНЯТЬ

 

ТЕМИ 5—6. Елементи теорії множин і комбінаторного аналізу. Математична логіка і теорія графів

 

Розглянути на прикладі конкретної економічної ситуації виконання властивостей множин (товарів, послуг, проектів, стратегій): ідемпотентності, еквівалентності, рефлексивності, комутативності, асоціативності, поглинання.

Виконати операції об’єднання, перетинання і доповнення для множин заданих типів.

Визначити метричний простір (сукупність множини та заданих у ній відстаней, що задовольняють певні умови) для досліджуваного економічного об’єкта. Задати відповідні метрики і дати їх змістовне тлумачення.

Побудувати диз’юнктивну та кон’юнктивну нормальні функції для заданої функції.

Проілюструвати напрямки побудови і використання алгебри висловлювань в економіці.

Задати відповідності та відношення. Дослідити їх властивості щодо відображення взаємозв’язків факторів функціонування конкретної економічної системи.

Визначити і побудувати нечітку множину. Виконати операції над нею.

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

Розв’язати задачу обґрунтування і доведення ефективності проекту (об’єкта) на підґрунті висунутих дослідником раціональних гіпотез щодо суперпозиції та взаємодії зовнішньо-внутрішньо-економічних факторів.

Представити ситуацію прийняття рішень щодо конкретної економічної задачі у вигляді графа (дерева). Визначити його властивості. Виконати можливі операції на ньому.

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

Розв’язати задачі стохастичної сіткової оптимізації, оптимізації на багатополюсних сітках, сітках із штрафами та виграшами тощо.

 

ТЕМА 9. Детерміновані моделі та методи оптимізації

 

На практичному занятті, в процесі індивідуальної роботи та самопідготовки студентів розв’язуются задачі лінійного, цілочисельного і нелінійного програмування, які викладені в науково-методичній розробці кафедри економіко-математичних методів КНЕУ — «Збірнику задач з курсу математичне програмування»:

1. Наконечний С. І., Гвоздецька Л. В. Збірник задач з курсу «Математичне програмування». Ч.1: Навч. посібник. — К.: ІСДО, 1996.

2. Наконечний С. І., Вітлінський В. В., Верченко П. І., Роскач О. С. Збірник задач з курсу «Математичне програмування». Ч.2. — К.: КНЕУ, 1998.

Відповідно до програми курсу та з урахуванням профілювання викладання дисципліни для різних економічних спеціальностей рекомендується розглянути задачі з наступних розділів вище зазначених посбників:

Лінійне програмування: математична постановка задачі та її графічне розв’язання: [1], задачі 1.5—1.40, с. 17—25.

Симплексний метод розв’язання задач ЛП: [1], задачі 2.5—2.51, с. 44—50.

Двоїстість у лінійному програмуванні: [1], задачі 3.4—3.35, с. 60—65.

Економічний аналіз оптимальних планів: [1], задачі 4.3—4.21, с. 82—91.

Транспортна задача: [1], задачі 5.5—5.40, с. 114—122.

Цілочисельне програмування: [2], задачі 1.5.1—1.5.9, с. 27—36.

Нелінійне програмування: [2], задачі 3.3.1 — 3.3.11, с. 85 — 94.

 

ТЕМА 10. Стохастичні моделі та методи

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

 

1.             На підприємстві випускається три види продукції. Прибуток від реалізації одиниці продукції кожного виду є випадковою величиною. Для виробництва продукції використовується два види ресурсів, обсяг запасів яких також є випадковою величиною. Необхідно розробити план випуску продукції, який дозволить максимізувати прибуток від реалізації всіх видів продукції за умов, що витрати кожного ресурсу не перевищуватимуть його обсяг на підприємстві. За даними експертного оцінювання ситуації на ринку відомі значення ймовірностей одержання прибутку від реалізації кожного з видів продукції:

 

ВИД ПРОДУКЦІЇ

А

В

С

Прибуток

Ймовірність

Прибуток

Ймовірність

Прибуток

Ймовірність

12

0,3

15

0,5

12

0,1

17

0,2

18

0,2

14

0,3

21

0.4

20

0,1

15

0,4

24

0.1

10

0,2

8

0,2

 

У зв’язку з коливанням цін на ресурси і доцільністю маневрування їх запасами підприємство оцінює ймовірні обсяги ресурсів двох видів, які використовуватимуться у виробництві:

 

Ресурс 1-го виду

Ресурс 2-го виду

Обсяг

Ймовірність

Обсяг

Ймовірність

300

0,2

150

0,2

400

0,1

200

0,4

500

0,3

220

0,2

550

0,2

270

0,1

600

0,2

310

0,1

 

Технологічні норми затрат ресурсів на одиницю продукції є детермінованими величинами і становлять:

 

Продукція

Затрати на одиницю продукції ресурсу

1-го виду

2-го виду

А

3

4

В

5

2

С

1

3

 

2. Підприємство може закупати два види сировини, кожен з яких містить різну кількість «корисних» речовин трьох видів — А, В і С:

 

Сировина

Вміст корисних речовин у сировині

1-го виду

2-го виду

А

1

2

В

3

4

С

5

6

 

Відомо, що, затрати на придбання 1 кг сировини становлять відповідно 10 та 20 грн. Передбачається, що мінімально припустимі сумарні потреби в речовинах А, В, С у сумішах є випадковими величинами (позначимо їх як a, b, c), які розподілені рівномірно в інтервалах відповідно [100,160], [220,300], [400,800].

Необхідно знайти оптимальну кількість сировини кожного виду, яку слід придбати підприємству за умови мінімізації затрат на сировину, якщо мають виконуватися обмеження з мінімально припустимою потребою у всіх речовинах з ризиком (ймовірністю) їх невиконання не більше ніж 30 \%.

 

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

 

1-й споживач

2-й споживач

3-й споживач

попит

ймовірність

попит

ймовірність

попит

ймовірність

120

0,4

200

0,3

300

0,3

150

0,3

180

0,2

250

0,2

170

0,2

170

0,1

200

0,2

190

0,1

130

0,4

240

0,3

 

Відомі затрати на перевезення одиниці продукції від кожного постачальника до кожного споживача:

 

Постачальник

Споживач

1-й

2-й

3-й

А

3

5

7

В

4

2

3

 

Якщо попит на продукцію споживача перебільшить її наявність, то потрібно буде платити штраф за за недопостачання кожної одиниці продукції в сумі відповідно 20 грн., 17 грн., 25 грн., а якщо попит буде меншим, то виникають затрати, пов’язані зі зберіганням одиниці продукції в сумі відповідно 12 грн., 10 грн., 8 грн.

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

Побудувати математичну модель і розв’язати двоетапну задачу стохастичного програмування.

 

4. Для виробництва двох виробів А і В можна використати обладнання двох груп — I i II. Затрати часу цими групами обладнання на виготовлення продукції є випадковими величинами, розподіленими за нормальним законом з параметрами:

 

Група обладнання

Питомі затрати часу, чол... шт.

Продукція А

Продукція В

математичне сподівання

середньоквадратичне відхилення

математичне сподівання

середньоквадратичне відхилення

I

0,2

0,2

0,3

0,3

II

0,1

0,2

0,1

0,2

 

Собівартість одного виробу є також випадковою величиною, яка розподілена в інтервалі:

 

Група обладнання

Питома собівартість виробу

Продукція А

Продукція В

нижня межа інтервалу розподілу

верхня межа інтервалу розподілу

нижня межа інтервалу розподілу

верхня межа інтервалу розподілу

I

2

4

1

2

II

3

6

2

8

 

Відомо, що план випуску виробів першого типу становить 100 шт., другого — 200 шт. Фонд часу роботи двох груп обладнання — відповідно 50 та 65 год.

Визначити оптимальний план роботи обладнання, за якого мінімізуються сподівані сумарні виробничі затрати на випуск продукції, якщо ризик (імовірність) перевищення фонду часу на виконання контрактів становить не більш як 0,1, а ризик невиконання контракту не більший за 0,05.

 

5.             Відповідно до програми курсу та з урахуванням профілізації викладання дисципліни для різних економічних спеціальностей рекомендується розглянути задачі 5.1—5.7, с. 164—168 (Наконечний С. І., Вітлінський В. В., Верченко П. І., Роскач О. С. Збірник задач з курсу «Математичне програмування». Ч. 2. — К.: КНЕУ, 1998).

ТЕМА 12. Дискретні динамічні моделі економічних систем. Динамічне програмування

 

На практичному занятті, в процесі індивідуальної роботи та самопідготовки студентів розв’язуются задачі динамічного програмування, які викладені в науково-методичній розробці кафедри економіко-математичних методів КНЕУ:

Наконечний С. І., Вітлінський В. В., Верченко П. І., Роскач О. С. Збірник задач з курсу «Математичне програмування». Ч. 2. — К.: КНЕУ, 1998.

 

Відповідно до програми курсу та з урахуванням профілізації викладання дисципліни для різних економічних спеціальностей рекомендується розглянути задачі 4.4.1—4.4.21, с. 136—143.