МЕТОДИЧНІ ВКАЗІВКИ

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

«ДОСЛІДЖЕННЯ ОПЕРАЦІЙ»

ПЕРЕДМОВА

Курс «Дослідження операцій» – обов'язковий компонент загальної та професійної освіти. Значення курсу «Дослідження операцій» у загальноосвітній підготовці визначається насамперед тим, що будь-які дослідження є фундаментом науково-дослідницької діяльності та науково-технічного прогресу.

Дисципліна «Дослідження операцій» призначена для оволодіння майбутніми бакалаврами спеціальності «Інтелектуальні системи прийняття рішень» основами знань у галузі дослідження операцій, на базі яких провадиться подальше вивчення спеціальних дисциплін, пов’язаних з фаховою діяльністю.

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

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

Типова програма відповідає діючим підручникам, що використовується у навчальному процесі.

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

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

• конкретизацією теорій, явищ і процесів під час вивчення курсу та закріпленні знань, використовуючи навчальний матеріал предметів профциклу;

• показом практичного використання в даній професійній діяльності знань, отриманих під час вивчення курсу;

• складанням задач з професійно спрямованим змістом, виконанням при їх рішенні розрахунків, пов'язаних з майбутньою професійною діяльністю студентів;

• проведенням практичних робіт із курсу, інтегрованих з деякими практичними роботами профциклу;

• використанням діафільмів, кіно- і відеофільмів із загальноосвітніх дисциплін профциклу з ілюстрацією в них наступності та взаємозв'язку основ системного аналізу і професійних знань.

Завдання курсу полягає у тому, щоб навчити студента системі методів дослідження систем.

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

1. Знання фактів, явищ. Вірне, науково достовірне їх пояснення.

2. Оволодіння науковими термінами, поняттями, законами, методами, правилами; вміння користуватися ними при пояснені нових фактів, розв‘язуванні різних питань і виконанні практичних завдань.

3. Максимальна ясність, точність думки, вміння відстоювати свої погляди, захищати їх.

Карта ПРАКТИЧНИХ ЗАНЯТЬ З НАВЧАЛЬНОЇ ДИСЦИПЛІНИ «Дослідження операцій»

Пояснення за розділами ТА темами

ТЕМА 5. Побудова економіко-математичних моделей задач лінійного програмування

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

Практичне заняття №1. Побудова економіко-математичних моделей задач лінійного програмування

Мета: засвоїти основні питання побудови економіко-математичних задач лінійного програмування.

План заняття

1. Основні питання, що розглядаються в процесі побудови математичних моделей задач лінійного програмування.

2. Формування та ідентифікація множини змінних.

3. Типові задачі оптимізації виробничої програми підприємства.

4. Критерії оптимальності в таких задачах.

Теоретичні відомості, що необхідні для виконання даної роботи, містяться в конспекті лекцій за темами 5 та 6.

Приклад розв’язку типових задач

Розглянемо прилад побудови економіко-математичної задачі лінійного програмування – визначення оптимального асортименту продукції.

Підприємство виготовляє два види продукції – П₁ і П₂, яка поступає в оптовий продаж. Для виробництва продукції використовуються два види сировини – А і В. Максимально можливі запаси сировини на добу складають 9 і 13 одиниць відповідно. Витрата сировини на одиницю продукції виду П₁ і виду П₂ дана в таблиці.

Таблиця. Витрати сировини продукції

Досвід роботи показав, що добовий попит на продукцію П₁ ніколи не перевищує попиту на продукцію П₂ більш ніж на 1 од. Крім того, відомо, що попит на продукцію П₂ ніколи не перевищує 2 од. на добу.

Оптові ціни одиниці продукції рівні: 3 г.о. (грошові одиниці) – для П₁ і 4 г.о. для П₂.

Яку кількість продукції кожного виду повинно виготовляти підприємство, щоб дохід від реалізації продукції був максимальним?

Розв'язок

Процес побудови математичної моделі для вирішення даної задачі розпочинається з відповідей на наступні питання:

1. Для визначення яких величин повинна бути побудована модель, тобто як ідентифікувати змінні даної задачі?

2. Які обмеження повинні накладатися на змінні, щоб виконувалися умови, характерні для модельованої системи?

3. У чому полягає мета задачі, для досягнення якої зі усіх допустимих значень змінних потрібно вибрати ті, які відповідатимуть оптимальному (якнайкращому) розв'язку задачі?

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

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

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

2х₁ + 3х₂ ≤ 9;

3х₁ + 2х₂ ≤ 13;

х₁ – х₂ ≤ 1;

х₂ ≤ 2;

х₁ ³ 0;

х₂ ³ 0.

Дохід від реалізації х₁ одиниць продукції П₁ і х₂ одиниць продукції П₂ складе Z = 3х₁ + 4х₂.

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

Розглянута задача відноситься до розряду типових задач оптимізації виробничої програми підприємства. Як критерії оптимальності в цих задачах можуть бути також використані: прибуток, собівартість, номенклатура вироблюваної продукції і витрати виробничого часу.

Задачі для самоконтролю

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

Задача 1. Для збереження нормальної життєдіяльності чоловік повинен за добу споживати білків не менш 100 умовних одиниць (ум. од.), жирів – не менш 50 і вітамінів – не менш 10 ум. од. Зміст їх в кожній одиниці продуктів П₁ і П₂ дорівнює відповідно (0,2; 0,1; 0,05) і (0,1; 0,2; 0,3) ум. од.

Вартість 1 од. продукту П₁ – 3 гр., П₂ – 2 гр.

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

Задача 2. При відгодівлі кожна тварина повинна отримати не менш 9 од. білків, 8 од. вуглеводів і 11 од. протеїну. Для складання раціону використовують два види корму, представлених в наступній таблиці

Вартість 1 кг корму першого виду – 4 гр., другого – 6 гр.

Побудуйте математичну модель задачі денного раціону поживності, який має мінімальну вартість. Сформульовану задачу розв’яжіть графічним методом.

Задача 3. Цех випускає трансформатори двох видів. Для виготовлення трансформаторів обох видів використовуються залізо і дріт. Загальний запас заліза – 3 тони, дроту – 18 тон. На один трансформатор першого виду витрачається 5 кг заліза і 3 кг дроту, а на один трансформатор другого виду витрачається 3 кг заліза і 2 кг дроту. За кожен реалізований трансформатор першого виду завод отримує прибуток 3 гр., другого – 4 гр.

Складіть план випуску трансформаторів, який забезпечить заводу максимальний прибуток. Сформульовану задачу розв’яжіть графічним методом.

Задача 4. Звіроферма вирощує чорно-бурих лисиць і песців. На звірофермі є 10000 кліток. У одній клітці можуть бути або 2 лисиці, або 1 песець. За планом на фермі повинно бути не менш 3000 лисиць і 6000 песців. У одну добу необхідно видавати кожній лисиці корми – 4 од., а кожному песцеві – 5 од. Ферма щодня може мати не більше 200000 одиниць корму. Від реалізації однієї шкірки лисиці ферма отримує прибуток 10 гр., а від реалізації однієї шкірки песця – 5 гр.

Яку кількість лисиць і песців потрібно тримати на фермі, щоб отримати найбільший прибуток? Сформульовану задачу розв’яжіть графічним методом.

Задача 5. З двох сортів бензину утворюються дві суміші – А і В. Суміш А містить бензину 60% 1-го сорту і 40% 2-го сорту; суміш В – 80% 1-го сорту і 20% 2-го сорту. Ціна 1 кг суміші А – 10 гр., а суміші В – 12 гр.

Складіть план утворення сумішей, при якому буде отримано максимальний дохід, якщо в наявності є бензину 50 тон 1-го сорту і 30 тон другого сорту. Сформульовану задачу розв’яжіть графічним методом.

Задача 6. Є дві грунтово-кліматичні зони, площі яких відповідно рівні 0,8 і 0,6 млн. га. Дані про врожайність зернових культур приведено в наступній таблиці

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

Задача 7. При виготовленні виробів П₁ і П₂ використовують сталь і кольорові метали, а також токарні і фрезерні верстати. За технологічними нормами на виробництво одиниці виробу П₁ потрібно 300 і 200 станко-годин відповідно токарного і фрезерного устаткування, а також 10 і 20 кг відповідно сталі і кольорових металів. Для виробництва одиниці виробу П₂ потрібно 400, 100, 70 і 50 відповідних одиниць тих же ресурсів.

Цех має у своєму розпорядженні 12400 і 6800 станко-годин відповідно токарного і фрезерного устаткування і 640 і 840 кг відповідно сталі і кольорових металів. Прибуток від реалізації одиниці виробу П₁ складає 6 гр. і від одиниці виробу П₂ – 16 гр.

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

Задача 8. Для збереження нормальної життєдіяльності чоловік повинен за добу споживати білків не менш 140 умовних одиниць (ум. од.), жирів – не менш 70 і вітамінів – не менш 20 ум. од. Зміст їх в кожній одиниці продуктів П₁ і П₂ дорівнює відповідно (0,2; 0,08; 0) і (0,1; 0,2; 0,1) ум. од.

Вартість 1 од. продукту П₁ – 4 гр., П₂ – 3 гр.

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

Задача 9. При відгодівлі кожна тварина повинна отримати не менш 11 од. білків, 8 од. вуглеводів і 9 од. протеїну. Для складання раціону використовують два види корму, представлених в наступній таблиці

Вартість 1 кг корму першого вигляду – 6 гр., другого – 4 гр.

Побудуйте математичну модель задачі денного раціону поживності, який має мінімальну вартість. Сформульовану задачу розв’яжіть графічним методом.

Задача 10. Цех випускає електродвигуни двох видів. Для виготовлення обмоток двигуна обох видів використовуються дріт і залізо. Загальний запас дроту – 15 тони, заліза – 5 тон. На один двигун першого виду витрачається 2 кг дроту і 1 кг заліза, а на один двигун другого виду витрачається 3 кг дроту і 2 кг заліза. За кожен реалізований трансформатор першого виду завод отримує прибуток 5 гр., другого – 6 гр.

Складіть план випуску електродвигунів, що забезпечує заводу максимальний прибуток. Сформульовану задачу розв’яжіть графічним методом.

Задача 11. Звіроферма вирощує кроликів та ондатр. На звірофермі є 8000 кліток. У одній клітці можуть бути або 1 кролик, або 2 ондатри. За планом на фермі повинно бути не менш 3500 кроликів і 5000 ондатр. У одну добу необхідно видавати кожному кролику корми – 4 од., а кожній ондатрі – 3 од. Ферма щодня може мати не більше 150000 одиниць корму. Від реалізації однієї шкірки кролика ферма отримує прибуток 10 гр., а від реалізації однієї шкірки ондатри – 15 гр.

Яку кількість кроликів і ондатр потрібно тримати на фермі, щоб отримати найбільший прибуток? Сформульовану задачу розв’яжіть графічним методом.

Задача 12. З двох сортів автомобільної фарби утворюються дві суміші – А і В. Суміш А містить фарби 50% 1-го сорту і 50% 2-го сорту; суміш В – 60% 1-го сорту і 40% 2-го сорту. Ціна 1 кг суміші А – 12 гр., а суміші В – 10 гр.

Складіть план утворення сумішей, при якому буде отримано максимальний дохід, якщо в наявності є фарби 40 тон 1-го сорту і 25 тон другого сорту. Сформульовану задачу розв’яжіть графічним методом.

Задача 13. Є дві лісові зони, площі яких відповідно рівні 0,9 і 0,7 тис. га, на яких заготовляють деревину. Дані про наявність порід дерев в зонах приведені в таблиці

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

Задача 14. При виготовленні молочних П₁ і П₂ використовуються молоко і додатки (сіль, цукор, спеції і т.д.), а також чани та холодильники. За технологічними нормами на виробництво одиниці виробу П₁ потрібно 250 і 150 праце-годин відповідно роботи на чанах і холодильниках, а також 25 і 15 кг відповідно молока і додатків. Для виробництва одиниці виробу П₂ потрібно 350, 75, 50 і 20 відповідних одиниць тих же ресурсів.

Цех має у своєму розпорядженні 10000 і 5000 праце-годин відповідно роботи на чанах і холодильниках і 540 і 440 кг відповідно молока і додатків. Прибуток від реалізації одиниці виробу П₁ складає 14 гр. і від одиниці виробу П₂ – 7 гр.

Побудуйте математичну модель задачі, використовуючи як показник ефективності прибуток. Сформульовану задачу розв’яжіть графічним методом.

ТЕМА 6. Графічний розв’язок задачі лінійного програмування

Доцільність використання графічного способу розв’язку задач лінійного програмування. Багатокутник розв’язків. Області допустимих розв’язків системи нерівностей. Інтерпретація обмежень. Інтерпретація цільової функції на графіку. Лінії рівня цільової функції. Правила практичного розв’язку задач лінійного програмування на основі її геометричної інтерпретації.

Практичне заняття №2. Графічний розв’язок задачі лінійного програмування

Мета: засвоїти основні прийоми графічного розв’язку задач лінійного програмування.

План заняття

1. Доцільність використання графічного способу розв’язку задач лінійного програмування.

2. Багатокутник розв’язків.

3. Області допустимих розв’язків системи нерівностей.

4. Інтерпретація обмежень.

5. Інтерпретація цільової функції на графіку.

6. Лінії рівня цільової функції.

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

Теоретичні відомості, що необхідні для виконання даної роботи, містяться в конспекті лекцій за темою 6.

Приклад розв’язку типових задач

Розв'яжемо наступну задачу лінійного програмування графічним методом

Z = 3x₁ + 4x₂ → max

2х₁ + 3х₂ ≤ 9;

3х₁ + 2х₂ ≤ 13;

х₁ – х₂ ≤ 1;

х₂ ≤ 2;

х₁ ³ 0;

х₂ ³ 0.

Розв'язок

Побудуємо багатокутник розв'язків (мал. 1.). Для цього в системі координат x₁0x₂ на площині зобразимо граничні прямі

2x₁ + 3x₂ = 9, (L1);

3x₁ + 2x₂ = 13, (L2);

x₁ – 3x₂ = 1, (L3);

x₂ = 2. (L4).

Узявши яку-небудь точку, наприклад, початок координат, встановимо, яку напівплощину визначає відповідна нерівність. Напівплощини, визначувані нерівностями, на мал. 1. Показані стрілками. Отже, областю розв'язків є багатокутник OABCD.

Для побудови прямої Z = 3x₁ + 4x₂ = 0 будуємо вектор-градієнт С = (3;4) і через початок координат проводимо пряму, перпендикулярну йому. Побудовану пряму Z = 0 переміщуємо паралельно самій собі у напрямі вектора С = (3;4). З мал. 1 виходить, що по відношенню до багатокутника розв'язків опорною ця пряма стає в точці C, де функція приймає максимальне значення. Точка С лежить на перетині прямих L₁ і L₃. Для визначення її координат розв'яжемо систему рівнянь

Оптимальний план задачі x₁ = 2,4; x₂ = 1,4. Підставляючи значення х₁ і х₂ в лінійну функцію, отримаємо:

Z_max = 3x₁ + 4x₂ = 3 2,4 + 4 1,4 = 12,8.

Отриманий розв'язок означає, що об'єм виробництва продукції П₁ повинен бути рівний 2,4 од., а продукції П₂ – 1,4 од. Дохід, що отримується в цьому випадку, складе: Z = 12,8 г.о.

Задачі для самоконтролю

Розв’яжіть наступні задачі лінійного програмування графічним методом і проведіть їх аналіз на чутливість:

В даній роботі в якості задач для самоконтролю також використовуються задачі з роботи №1 (задачі 1-14).

ТЕМА 7. Аналіз моделей на чутливість

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

Практичне заняття №3. Аналіз моделей на чутливість

Мета: засвоїти основні принципи методології аналізу моделей на чутливість.

План заняття

1. Процес аналізу моделей на чутливість.

2. Інтерпретація динамічних характеристик моделей.

3. Використання графічних методів.

4. Задача аналізу змін запасів ресурсів.

5. Задача визначення найбільш вигідного ресурсу.

6. Задача визначення меж зміни коефіцієнтів цільовій функції.

Теоретичні відомості, що необхідні для виконання даної роботи, містяться в конспекті лекцій за темою 7.

Приклад розв’язку типових задач

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

Задача 1. Аналіз змін запасів ресурсів

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

Після знаходження оптимального розв'язку представляється цілком логічним з'ясувати, як відіб'ється на оптимальному розв'язку зміна запасів ресурсів. Для цього необхідно відповісти на два питання:

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

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

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

На мал. 1. зв'язуючими обмеженнями є обмеження (1) і (3), представлені прямими L₁ і L₃ відповідно, тобто ті, що визначають запаси початкових ресурсів. Обмеження (1) визначає запаси сировини А. Обмеження (3) визначає співвідношення попиту на продукцію, що випускається.

Якщо деяке обмеження є таким, що зв'язує, то відповідний ресурс відносять до розряду дефіцитних ресурсів, оскільки він використовується повністю. Ресурс, з яким асоційовано незв'язуюче обмеження, слід віднести до розряду недефіцитних ресурсів (тобто наявних в деякому надлишку). У нашому прикладі незв'язуючими обмеженнями є (2) і (4). Отже, ресурс – сировина В – недефіцитний, тобто є в надлишку, а попит на продукцію П₂ не буде задоволений повністю (у таблиці – ресурси 2 і 4).

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

У нашому прикладі сировина А і співвідношення попиту на продукцію П₁ і П₂, що випускається, є дефіцитними ресурсами (у таблиці – ресурси 1, 3).

Розглянемо спочатку ресурс – сировина А. На мал. 2. при збільшенні запасу цього ресурсу пряма L₁ переміщається вгору паралельно самій собі до точки К, в якій перетинаються лінії обмежень L₂, L₃ і L₄. У точці К обмеження (2), (3) і (4) стають такими, що зв'язують; оптимальному розв'язку при цьому відповідає точка К, а простором (допустимих) розв'язків стає багатокутник AKD0. У точці К обмеження (1) (для ресурсу А) стає надмірним, оскільки будь-яке подальше зростання запасу відповідного ресурсу не впливає ні на простір розв'язків, ні на оптимальний розв'язок.

Таким чином, об'єм ресурсу А не слід збільшувати понад ту межу, коли відповідне йому обмеження (1) стає надмірним, тобто пряма (1) проходить через нову оптимальну точку К. Цей граничний рівень визначається таким чином. Встановлюються координати точки К, в якій перетинаються прямі L₂, L₃ і L₄, тобто знаходиться розв'язок системи рівнянь.

В результаті виходить х₁ = 3 і х₂ = 1. Потім, шляхом підстановки координат точки К в ліву частину обмеження (1), визначається максимально допустимий запас ресурсу А

2x₁ + 3x₂ = 2 3 + 3 2 = 12.

Мал. 3. ілюструє ситуації, коли розглядається питання про зміну співвідношення попиту на продукцію П₁ і П_2.

Новою оптимальною точкою стає точка Е, де перетинаються прямі L₁ і L₂. Координати даної точки знаходяться шляхом розв'язку системи рівнянь (1) і (2) таким чином.

В результаті виходить х₁ = 4,2; х₂ = 0,2, причому добовий попит на продукцію П₁ не повинен перевищувати попит на продукцію П₂ на величину х₁ – х₂ = 4,2 – 0,2= 4 од.

Подальше збільшення розриву в попиті на продукцію П₁ і П₂ не впливатиме на оптимальний розв'язок.

Розглянемо питання про зменшення правої частини незв'язуючих обмежень. Обмеження (4) фіксує граничний рівень попиту на продукцію П₂. З мал. 2.5 витікає, що, не змінюючи оптимального рішення, пряму L₄ (АВ) можна опускати вниз до перетину з оптимальною точкою С. Так як точка С має координати х₁ = 4,2; х₂ = 1,4 зменшення попиту на продукцію П₂ до величини х₂ = 1,4 ніяк не вплине на оптимальність раніше отриманого розв'язку.

Розглянемо обмеження (2) 3x₁ + 2x₂ ≤ 13, яке є обмеженням на недефіцитний ресурс – сировина В. І в цьому випадку праву частину – запаси сировини В – можна зменшувати до тих пір, поки пряма L₂ не досягне точки С. При цьому права частина обмеження (2) стане рівною 3x₁ + 2x₂ = 3 2,4 + 2 1,4 = 10, що дозволяє записати це обмеження у вигляді: 3x₁ + 2x₂ ≤ 10. Цей результат показує, що раніше отриманий оптимальний розв'язок не зміниться, якщо добовий запас ресурсу В зменшити на 3 од.

Результати проведеного аналізу можна звести до наступної таблиці

Задача 2. Визначення найбільш вигідного ресурсу

У задачі 1 аналізу на чутливість досліджено вплив на оптимум збільшення об'єму дефіцитних ресурсів. При обмеженнях, пов'язаних з додатковим залученням ресурсів, природно поставити питання: якому з ресурсів слід віддати перевагу при вкладенні додаткових витрат? Для цього вводиться характеристика цінності кожної додаткової одиниці дефіцитного ресурсу, що виражається через відповідний приріст оптимального значення цільової функції. Таку характеристику для даного прикладу можна отримати безпосередньо з таблиці, в якій приведені результати розв'язку задачі 1 на чутливість. Позначимо цінність додаткової одиниці ресурсу i через y_i. Величина y_i визначається із співвідношення.

Результати розрахунку цінності одиниці кожного з ресурсів представлені в наступній таблиці

Отримані результати свідчать про те, що додаткові вкладення в першу чергу слід направити на збільшення ресурсу А і лише потім – на формування співвідношення попиту на продукцію П₁ і продукцію П₂. Що стосується недефіцитних ресурсів, то, як і слід було чекати, їх об'єм збільшувати не слід.

Задача 3. Визначення меж зміни коефіцієнтів цільової функції

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

При аналізі моделі на чутливість до змін коефіцієнтів цільової функції необхідно досліджувати наступні питання:

1. Який повинен бути діапазон зміни того або іншого коефіцієнта цільової функції, при якому не відбуваються зміни оптимального розв'язку?

2. На скільки слід змінити той або інший коефіцієнт цільової функції, щоб зробити деякий недефіцитний ресурс дефіцитним, і, навпаки, дефіцитний ресурс зробити недефіцитним?

Відповімо на поставлені питання на прикладі.

Розглядаючи перше питання, позначимо через c₁ і c₂ доходи підприємства від продажу одиниці продукції П₁ і П₂ відповідно. Тоді цільову функцію можна представити в наступному вигляді:

Z = с₁х₁ + с₂х₂.

На мал. 1. видно, що при збільшенні c₁ або зменшенні c₂ пряма, що представляє цільову функцію Z, обертається (навколо точки С) за годинниковою стрілкою. Якщо ж c₁ зменшується або c₂ збільшується, ця пряма обертається в протилежному напрямі – проти годинникової стрілки. Таким чином, точка С залишатиметься оптимальною точкою до тих пір, поки нахил прямої не вийде за межі, визначувані нахилами прямих для обмежень (1) і (3).

Коли ж нахил прямої Z стане рівним нахилу прямої L₁, отримаємо дві альтернативні оптимальні кутові точки – С і В. Аналогічно, якщо нахил прямої Z стане рівним нахилу прямої для обмеження (3), матимемо альтернативні оптимальні кутові точки С і D. Наявність альтернативного оптимуму свідчить про те, що одне і те ж оптимальне значення Z може досягатися при різних значеннях змінних х₁ і х₂. Як тільки нахил прямої вийде за межі вказаного вище інтервалу c₁, отримаємо деякий новий оптимальний розв'язок.

Розглянемо, яким чином можна знайти допустимий інтервал зміни c₁, при якому точка С залишається оптимальною. Початкове значення коефіцієнта c₂ = 4 залишимо незмінним. На мал. 1. видно, що значення c₁ можна зменшувати до тих пір, поки пряма Z не співпаде з прямою L₁ (відрізок ВС).

Це крайнє мінімальне значення коефіцієнта c₁ можна визначити з рівності кутів нахилів прямої Z і прямої L₁. Оскільки тангенс кута нахилу для прямої Z дорівнює (c₁/4), а для прямої (1) дорівнює 2/3, то мінімальне значення c₁ визначимо з рівності c₁/4 = 2/3, звідки min c₁ = 8/3. На мал. 2.5 видно, що значення c₁ можна збільшувати безмежно, оскільки пряма Z при c₂ = 4 і c₁®+¥ не співпадає з прямою L₃ (відрізок DC) і, отже, точка С при всіх значеннях коефіцієнта c₁ ³ 8/3 буде єдиною оптимальною.

Інтервал зміни c₁, в якому точка С як і раніше залишається єдиною оптимальною точкою, визначається нерівністю 8/3 < c₁ < +¥. При c₁ = 8/3 оптимальними кутовими точками будуть як точка С, так і точка В. Як тільки коефіцієнт c₁ стає менше 8/3, оптимум зміщується в точку В.

Можна відзначити, що, як тільки коефіцієнт c₁ виявляється менше 8/3, ресурс 3 стає недефіцитним, а ресурс 4 – дефіцитним. Для підприємства це означає наступне; якщо дохід від продажу одиниці продукції П₁ стане менше 8/3 г.о., то найбільш вигідна виробнича програма підприємства повинна передбачати випуск максимально допустимої кількості продукції П₂ (повністю задовольняти попит на продукцію П₂). При цьому співвідношення попиту на продукцію П₁ і П₂ не лімітуватиме об'єми виробництва, що зумовить недефіцитність ресурсу (3). Збільшення коефіцієнта c₁ понад 8/3 г.о. не знімає проблему дефіциту ресурсів (1) і (3). Точка С – точка перетину прямих L₁ і L₃ – залишається весь час оптимальною.

Задачі для самоконтролю

В даній роботі в якості задач для самоконтролю використовуються задачі з робот №1 (задачі 1-14) та №2 (задачі 1-16).

ТЕМА 8. Симплекс-метод

Загальна ідея симплекс-методу. Алгоритм симплекс-методу. Симплекс-таблиця. Приклади.

Практичне заняття №4. Симплекс-метод

Мета: засвоїти основні етапи алгоритму симплекс-методу.

План заняття

1. Загальна ідея симплекс-методу.

2. Алгоритм симплекс-методу.

3. Побудова симплекс-таблиць.

4. Приклад.

Теоретичні відомості, що необхідні для виконання даної роботи, містяться в конспекті лекцій за темою 8.

Приклад розв’язку типових задач

Розв'яжемо наступну задачу симплекс-методом

Z_max = 2x₁ – x₂ + 3x₃ – 2x₄ + x₅.

Приведемо задачу до вигляду, що допускає застосування симплекс-алгоритму, обравши в якості базисних змінних х₃, х₄, х₅. Отримаємо

х₃ = 1 – (– х₁ + х₂),

х₄ = 1 – (х₁ – х₂),

х₅ = 2 – (х₁ + х₂).

Підставимо у вираз Z_max величини x₃, x₄, x₅

Z_max = 6x₁ – 7x₂ + 3.

За алгоритмом цільова функція повинна прагнути до мінімуму

Z_min = – Z_max = – 6x₁ + 7x₂ – 3 = – 3 – (6x₁ – 7x₂).

Складемо симплекс-таблицю

Розшукуємо в останньому рядку найменший позитивний елемент, в нашому прикладі він дорівнює +6, отже, перший стовпець коефіцієнтів буде вирішуючим. Визначимо відношення вільних членів до позитивних елементів вирішуючого стовпця. Мінімальне симплекс-відношення дорівнює 1, отже, вирішуючий елемент знаходиться на перетині рядка зі змінною x₄ і стовпця – x₁.

Переходимо до наступної таблиці, використовуючи правило прямокутника

У останньому рядку немає позитивних елементів, отже, оптимальний розв'язок знайдено: Z_min = – 9; x = (1; 0; 2; 0; 1), Z_max = – Z_min = 9.

Задачі для самоконтролю

В даній роботі в якості задач для самоконтролю можуть використовуватися задачі з попередніх робіт.

ТЕМА 9. Постановка задачі

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

Практичне заняття №5. Транспортна задача

Мета: засвоїти основні етапи постановки транспортних задач.

План заняття

1. Поняття транспортної задачі.

2. Загальні особливості транспортних задач.

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

4. Таблиця транспортної задачі.

5. Закриті та відкриті транспортні задачі.

6. Опорний план.

Теоретичні відомості, що необхідні для виконання даної роботи, містяться в конспекті лекцій за темою 9.

Приклад розв’язку типових задач

Розглянемо приклад постановки транспортної задачі.

Є три постачальники і чотири споживачі однорідної продукції. Відомі витрати на перевезення вантажу від кожного постачальника кожному споживачеві. Позначимо їх c_ij (j = 1,2,3,4, i = 1,2,3). Запаси вантажів у постачальників дорівнюють a_i (i = 1,…,3). Відомі потреби кожного споживача b_i (j = 1,…,4)_. Вважатимемо, що сумарні потреби дорівнюють сумарним запасам.

Потрібно скласти такий план перевезень, щоб забезпечити мінімальні сумарні витрати при повному задоволенні потреб.

Введемо змінні х_ij – кількість вантажу, що перевозиться від i-го постачальника j-му споживачеві.

Цільова функція – мінімізувати сумарні витрати на перевезення

Кількість постачальників і споживачів в загальному випадку може бути довільною.

Задачі для самоконтролю

Задача 1. У пунктах A і B знаходяться відповідно 150 і 90 т пального. Пунктам 1, 2, 3 потрібні відповідно 60, 70, 110 т пального. Вартість перевезення 1 т пального з пункту A в пункти 1, 2, 3 рівна відповідно 60, 10, 40 тис. грн. за 1 т відповідно, а з пункту B в пункти 1, 2, 3 - 120, 20, 80 тис. грн. за 1 т відповідно.

Складіть план перевезень пального, що мінімізує загальну суму транспортних витрат.

Задача 2. Три заводи випускають вантажні автомобілі, які відправляються чотирьом споживачам. Перший завод поставляє 90 платформ вантажівок, другий – 30 платформ, третій – 40 платформ. Потрібно поставити платформи наступним споживачам: першому – 70 штук, другому – 30, третьому – 20, четвертому – 40 штук. Вартість перевезення однієї платформи від постачальника до споживача вказана в наступній таблиці (г.о.)

Складіть оптимальний план доставки вантажних автомобілів

Задача 3. Будівництво магістральної дороги включає завдання заповнення вибоїн, що є на трасі, до рівня основної дороги і зрізає в деяких місцях дороги виступів. Зрізаним ґрунтом заповнюються вибоїни. Перевезення ґрунту здійснюється вантажівками однакової вантажопідйомності. Відстань в кілометрах від зрізів до вибоїн і об'єм робіт вказані в наступній таблиці

Складіть план перевезень, що мінімізує загальний пробіг вантажівок.

Задача 4. Вантаж, що зберігається на трьох складах і вимагає для перевезення 60, 80, 106 автомашин відповідно, необхідно перевезти в чотири магазини. Першому магазину потрібно 44 машини вантажу, другому – 70, третьому – 50 і четвертому – 82 машини. Вартість пробігу однієї автомашини за 1 км. складає 10 г.о. Відстані від складів до магазинів вказані в наступній таблиці

Складіть оптимальний за вартістю план перевезення вантажу від складів до магазинів.

Задача 5. На складах А, В, С знаходиться сортове зерно 100, 150, 250 т, яке потрібно доставити в чотири пункти. Пункту 1 необхідно поставити 50 т, пункту 2 – 100, пункту 3 – 200, пункту 4 – 150 т сортового зерна. Вартість доставки 1 т зерна з складу А у вказані пункти відповідно рівна (г.о.) 80, 30, 50, 20; з складу В – 40, 10, 60, 70; з складу С -10, 90, 40, 30.

Складіть оптимальний план перевезення зерна з умови мінімуму вартості перевезення.

Задача 6. Завод має три цехи – А, В, С і чотири склади – 1; 2; 3; 4. Цех А проводить 30 тис. шт. виробів, цех В – 40; цех З – 20 тис. шт. виробів. Пропускна спроможність складів за той же час характеризується наступними показниками: склад 1 – 20 тис. шт. виробів; склад 2 – 30; склад 3 – 30 і склад 4 – 10 тис. шт. виробів. Вартість перевезення 1 тис. шт. виробів з цеху А на склади 1, 2, 3, 4 – відповідно (г.о.): 20, 30, 40, 40; з цеху В – відповідно 30, 20, 50, 10; а з цеху С – відповідно 40, 30, 20, 60.

Складіть такий план перевезення виробів, при якому витрати на перевезення 90 тис. шт. виробів були б найменшими.

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

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

Задача 8. Є два сховища з однорідним продуктом, в яких зосереджене 200 і 120 т продукту відповідно. Продукти необхідно перевезти трьом споживачам відповідно в кількості 80, 100 і 120 т. Відстані від сховищ до споживачів (8 км.) наступні:

Витрати на перевезення 1 т продукту на 1 км. постійні і рівні 5 г.о.

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

Задача 9. Промисловий концерн має два заводи і п'ять складів в різних регіонах країни. Кожного місяця перший завод проводить 40, а другою 70 од. продукції. Вся продукція, вироблювана заводами, повинна бути направлена на склади. Місткість першого складу рівна 20 од. продукції; другого – 30; третього – 15; четвертого – 27; п'ятого – 28 од. Витрати транспортування продукції від заводу до складу наступні (од.)

Розподілите план перевезень з умови мінімізації щомісячних витрат на транспортування.

Задача 10. Три нафтопереробні заводи з добовою продуктивністю 10, 8 і 6 млн. галонів бензину забезпечують три бензосховища, попит яких складає 6, 11 і 7 млн. галонів. Бензин транспортується в бензосховища по трубопроводу. Вартість перекачування бензину на 2 км. складає 5 г.о. на 100 галонів. Завод 1 не пов'язаний з сховищем 3. Відстань від заводів до бензосховищ наступне

Сформулюйте відповідну транспортну задачу і розв'яжіть на мінімум транспортних витрат.

Задача 11. Автомобілі перевозяться на трайлерах з трьох центрів розподілу п'яти продавцям. Вартість перевезення з розрахунку на 1 км. шляху, пройденого трайлером, рівна 60 г.о. Один трайлер може перевозити 15 автомобілів. Вартість перевезень не залежить від того, наскільки повно завантажується трайлер. У приведеній нижче таблиці вказані відстані між центрами розподілу і продавцями, а також величини, що характеризують щомісячний попит і об'єми постачань, що обчислюються кількістю автомобілів

Визначите мінімальні витрати на доставку автомобілів.

Задача 12. Вирішите задачу розподілу верстатів чотирьох різних типів за шістьма типами робіт. Хай є 30, 45, 25 і 20 верстатів відповідних типів. Шість типів робіт характеризуються 30, 20, 10, 40, 10 і 10 операціями відповідно. На верстаті 3 не може виконуватися операція 6. Виходячи з коефіцієнтів вартості операції, представлених в наступній таблиці, побудуйте модель і виконайте оптимальний розподіл верстатів за роботами

Задача 13. У даному транспортному завданні сумарний попит перевершує сумарний об'єм виробництва. Хай штрафи за недопостачу одиниці продукції в пункти призначення 1, 2 і 3 рівні відповідно 5, 3 і 2.

Початкові дані наступні:

Знайдіть оптимальний розв'язок.

Для задач 14 – 25 задано наступні умови.

Є три пункти постачання однорідного вантажу – A₁; A₂; A₃ і п'ять пунктів споживання цього вантажу B₁; B₂; B₃; B₄; B₅. У пунктах A₁; A₂; A₃ знаходиться вантаж a₁; a₂; a₃ відповідно. Вантаж необхідно доставити в пункти B₁; B₂; B₃; B₄; B₅  в кількості b₁; b₂; b₃; b₄; b₅ відповідно. Відстані між пунктами в км. задані наступною матрицею.

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

Задача 14.  = (200; 450; 250);  = (100; 125; 325; 250; 100);

Задача 15. = (250; 200; 200); = (120; 130; 100; 160; 110);

Задача 16. = (300; 250; 200); = (210; 170; 220; 150; 200);

Задача 17. = (350; 200; 300); = (170; 140; 200; 195; 145);

Задача 18. = (230; 250; 170); = (140; 90; 160; 110; 150);

Задача 19. = (200; 350; 300); = (270; 130; 190; 150; 110);

Задача 20. = (150; 150; 200); = (110; 70; 130; 110; 90);

Задача 21. = (330; 270; 350); = (220; 170; 220; 150; 200);

Задача 22. = (150; 200; 100); = (90; 150; 75; 60; 75);

Задача 23. = (300; 300; 250); = (150; 140; 115; 225; 220);

Задача 24. = (300; 230; 320); = (190; 150; 130; 180; 200);

Задача 25. = (200; 300; 250); = (120; 140; 160; 180; 150);

ТЕМА 10. Методи складання початкового опорного плану

Базисний план. Діагональний метод, або метод північно-західного кута. Метод найменшої вартості. Метод Фогеля.

Практичне заняття №6. Методи складання початкового опорного плану

Мета: засвоїти основні методи складання початкового опорного плану.

План заняття

1. Базисний план.

2. Діагональний метод, або метод північно-західного кута.

3. Метод найменшої вартості.

4. Метод Фогеля.

Теоретичні відомості, що необхідні для виконання даної роботи, містяться в конспекті лекцій за темою 10.

Приклад розв’язку типових задач

1. Діагональний метод, або метод північно-західного кута. При цьому методі на кожному кроці побудови першого опорного плану заповнюється ліва верхня клітка (північно-західний кут) частини таблиці, що залишилася. При такому методі заповнення таблиці починається з клітки невідомого x₁₁ і закінчується в клітці невідомого x_mn, тобто йде як би по діагоналі таблиці перевезень.

Приклад

Заповнення таблиці починається з її північно-західного кута, тобто клітки з невідомим x₁₁. Перша база A₁ може повністю задовольнити потребу першого замовника B₁ (a₁ = 300, b₁ = 170, a₁ > b₁). Вважаючи x₁₁ = 170, вписуємо це значення в клітку x₁₁ і виключаємо з розгляду перший стовпець. На базі A₁ залишається змінений запас a¹₁ = 130. У новій таблиці, що залишилася, з трьома рядками A₁, A₂, A₃ і чотирма стовпцями B₁, B₂, B₃, B₄; північно-західним кутом буде клітка для невідомого x₁₂. Перша база із запасом може повністю задовольнити потребу другого замовника B₂ (a¹₁ = 130, b₂ = 110, a¹₁ > b₂). Вважаємо x₁₂ = 110, вписуємо це значення в клітку x₁₂ і виключаємо з розгляду другий стовпець. На базі A₁ залишається новий залишок (запас) a¹¹₁ = 20. У новій таблиці, що залишилася, з трьома рядками A₁, A₂, A₃ i трьома стовпцями B₃, B₄, B₅ північно-західним кутом буде клітка для невідомого x₁₃. Тепер третій замовник B₃ може прийняти запас з бази A₁ (a¹¹₁ = 20, b₃ = 100, a¹¹₁ < b₃). Вважаємо x₁₃ = 20, вписуємо це значення в клітку x₁₃ і виключаємо з розгляду перший рядок. У замовника з В₃ залишається ще незадоволеною потреба b¹₃ = 80.

Тепер переходимо до заповнення клітки для невідомого x₂₃ і т.д.

Через шість кроків у нас залишиться одна база A₃ із запасом вантажу (залишком від попереднього кроку) a¹₃ = 200 і один пункт B₅ з потребою b₅ = 200. Відповідно цьому є одна вільна клітка, яку і заповнюємо, поклавши x₃₅ = 200. План складений. Базис утворений невідомими x₁₁, x₁₂, x₁₃, x₂₃, x₂₄, x₃₄, x₃₅. Правильність складеного плану легко перевірити, підрахувавши суми чисел, що стоять в заповнених клітках по рядках і стовпцях.

Загальний об'єм перевезень в тонно-кілометрах для цього плану складе

S₁ = 70*170 + 50*110 + 15*20 + 40*80 + 60*70 + 11*50 + 25*200 = 30650.

2. Метод найменшої вартості. При цьому методі на кожному кроці побудови опорного плану першою заповнюється та клітка, що залишилася i яка має найменший тариф. Якщо така клітка не єдина, то заповнюється будь-яка з них.

Приклад

В даному випадку заповнення таблиці починається з клітки для невідомого x₃₂, для якого ми маємо значення c₃₂ = 10, найменше зі всіх значень c_ij. Ця клітка знаходиться на перетині третього рядка і другого стовпця, відповідним третій базі A₃ і другому замовникові B₂. Третя база A₃ може повністю задовольнити потребу другого замовника B₂ (a₃ = 250, b₂ = 110, a₃ > b₂). Вважаючи x₃₂ = 110, вписуємо це значення в клітку x₃₂ і виключаємо з розгляду другий стовпець. На базі A₃ залишається змінений запас a¹₃ = 140. У новій таблиці, що залишилася, з трьома рядками A₁, A₂, A₃ і чотирма стовпцями B₁, B₃, B₄, B₅ кліткою з найменшим значенням c_ij клітка, де c₃₄ = 11. Заповнюємо описаним вище способом цю клітку і аналогічно заповнюємо наступні клітки. В результаті виявляються заповненими (у приведеній послідовності) наступні клітки

x₃₂ = 110, x₃₄ = 120, x₁₃ = 100, x₃₅ = 20, x₁₅ = 180, x₁₁ = 20, x₂₁ = 150.

На п'ятому кроці кліток з найменшими значеннями c_ij опинилося дві (c₁₁ = c₁₅ = 70). Ми заповнили клітку для x₁₅, поклавши x₁₅ = 180. Можна було вибрати для заповнення іншу клітку, поклавши x₁₁ = 170, що приведе в результаті до іншого опорного плану. Загальний об'єм перевезень в тонно-кілометрах для цього плану складе

S₁ = 70*20 + 15*100 + 70*180 + 80*150 + 10*110 + 11*120 + 25*20 = 30420.

Задачі для самоконтролю

В даній роботі в якості задач для самоконтролю можуть використовуватися задачі з попередніх робіт.

ТЕМА 11. Поняття потенціалу і циклу

Поняття циклу. Перерахунок по циклу. Обчислення суми алгебри тарифів. Поняття потенціалу. Обчислення потенціалів. Додаткова перевірка обчислених потенціалів.

Практичне заняття №7. Поняття потенціалу і циклу

Мета: засвоїти основні прийоми обчислення циклів та потенціалів.

План заняття

1. Цикл.

2. Перерахунок по циклу.

3. Обчислення суми алгебри тарифів.

4. Обчислення потенціалів.

5. Додаткова перевірка обчислених потенціалів.

Теоретичні відомості, що необхідні для виконання даної роботи, містяться в конспекті лекцій за темою 11.

Приклад розв’язку типових задач

Приклад

В таблиці перевезень, складеній по діагональному методу при розв'язку задачі з попереднього пункту, вільному невідомому x₂₁ відповідає цикл x₂₁, x₂₃, x₁₃, x₁₁, x₂₁ і т.д.

Хай тепер маємо деяку вільну клітку з відповідним до неї циклом. Якщо змінимо значення вільного невідомого, збільшивши його на деяке число x, то, переходячи послідовно від однієї вершини циклу до іншої, повинні будемо через незмінність сум по рядках і по стовпцях по черзі зменшувати і збільшувати значення невідомих в циклі на те ж саме число x. Наприклад, у вказаному вище циклі для вільного невідомого x₂₁ отримаємо:

- старі значення: x₂₁ = 0, x₂₃ = 80, x₁₃ = 20, x₁₁ = 170, x₂₁ = 0;

- нові значення: x¹₂₁ = х, x¹₂₃ = 80 – х, x¹₁₃ = 20 + х, x¹₁₁ = 170 – х, x¹₂₁ = х.

Очевидно, якщо забезпечити вершини циклу по черзі знаками «+» і «–», приписавши вершині у вільній клітці знак «+», то можна сказати, що у вершинах із знаком «+» число x додається до колишнього значення невідомого, такого, що знаходиться в цій вершині, а у вершинах із знаком «–» це число x віднімається з колишнього значення невідомого, такого, що знаходиться в цій вершині.

Зауважимо, що оскільки число вершин в циклі завжди парно, то, повертаючись у вільну клітку, слід приписати їй знак «+», тобто той знак, який їй вже приписаний при виході з неї. Це дуже істотна обставина, оскільки інакше прийшли б до суперечності. Байдуже також, в якому напрямі обходиться цикл при позначенні вершин.

Якщо як x обрати найменше з чисел, що стоять у вершинах, забезпечених знаком «–», то, принаймні, одна з колишніх базисних невідомих прийме значення нуль, і зможемо перевести його в число вільних невідомих, зробивши замість нього базисним те невідоме, яке було вільним.

Так, наприклад, в розглянутому циклі маємо негативні вершини x₂₃ і x₁₁; отже, вибравши х = min {80; 170} = 80, отримуємо:

старі значення: x₂₁ = 0, x₂₃ = 80, x₁₃ = 20, x₁₁ = 170, x₂₁ = 0;

нові значення: x¹₂₁ = 80, x¹₂₃ = 0, x¹₁₃ = 100, x¹₁₁ = 90, x¹₂₁ = 80, тобто замість колишнього базисного рішення отримуємо нове базисне рішення

Вибір як x мінімального серед чисел, що стоять в негативних вершинах циклу, забезпечує допустимість нового базису.

Для плану, отриманого за діагональним методом в розглянутій задачі, маємо

u₁ + v₁ = 70,

u₁ + v₂ = 50,

u₁ + v₃ = 15,

u₂ + v₃ = 40,

u₂ + v₄ = 60,

u₃ + v₄ = 11,

u₃ + v₅ = 25.

Система містить сім рівнянь з вісьма невідомими. Вибираючи довільно значення, знаходимо послідовно з перших трьох рівнянь значення, потім з четвертого рівняння –, з п'ятого рівняння –, з шостого рівняння u₃ = 11 – v₄ і, нарешті, з сьомого рівняння – v₅ = 25 – u₃.

Поклавши, наприклад, u₁ = 0, набуваємо значень потенціалів

v₁ = 70,

v₂ = 50,

u₁ = 0, v₃ = 70,

u₂ = 25, v₄ = 35,

u₃ = – 24, v₅ = 49.

Знайдемо тепер непрямі тарифи для вільних кліток і порівняємо їх з дійсними тарифами

с¹₁₄ = u₁ + v₄ = 35 < с₁₄, с¹₂₅ = u₂ + v₅ = 74 < с₂₅,

с¹₁₅ = u₁ + v₅ = 49 < с₁₅, с¹₃₁ = u₃ + v₁ = 46 < с₃₁,

с¹₂₁ = u₂ + v₁ = 95 > с₂₁, с¹₃₂ = u₃ + v₂ = 26 > с₃₂,

с¹₂₂ = u₂ + v₂ = 75 < с₂₂, с¹₃₃ = u₃ + v₃ = – 9 < с₃₃.

Для кліток з невідомими x₂₁ і x₃₂ непрямі тарифи більше істинних. Отже, для них ми матимемо негативні суми алгебри тарифів

S₂₁ = с₂₁ – с¹₂₁ = 80 – 65 = – 15,

S₃₂ = с₃₂ – с¹₂₃ = 10 – 26 = – 16.

Значення S₂₁ = – 15 вже було раніше, обчислюючи суму алгебри тарифів для цієї клітки безпосередньо по циклу.

Задачі для самоконтролю

В даній роботі в якості задач для самоконтролю можуть використовуватися задачі з попередніх робіт.

ТЕМА 12. Критерій оптимальності базисного розв'язку транспортної задачі. Методи відшукання оптимального рішення

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

Практичне заняття №8. Методи відшукання оптимального розв'язку

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

План заняття

1. Критерій оптимальності базисного розв'язку транспортної задачі.

2. Основний спосіб відшукання оптимального розв'язку транспортної задачі.

3. Методи підрахунку сум алгебри тарифів.

4. Розподільний метод.

5. Метод потенціалів.

Теоретичні відомості, що необхідні для виконання даної роботи, містяться в конспекті лекцій за темою 12.

Приклад розв’язку типових задач

Розглянемо приклади задачі транспортного типу.

Приклад. Одне фермерське господарство (A₁) має продовольче зерно двох видів: 3 тис. тонн – III класу і 4 тис. тонн – IV класу. Друге фермерське господарство (A₂) також має зерно двох видів: 5 тис. тонн – III класу і 2 тис. тонн – IV класу. Зерно повинне бути вивезене на два елеватори: на перший елеватор (B₁) необхідно поставити 2 тис. тонн пшениці III класу, 3 тис. тон пшениці IV класу та інші 2 тис. тонн пшениці будь-якого класу.

Аналогічно другий елеватор (B₂) повинен отримати 8,25 тис. тонн, з них пшениці – 1 тис. тонн III класу і 1,5 тис. тонн IV класу.

Вартість перевезення в г.о. 1 тонни зерна складає: з пункту A₁ в пункти B₁ і B₂ – 1 і 1,5 відповідно; з пункту A₂ в пункти B₁ і B₂ – 2 і 1 г.о. відповідно. Скласти оптимальний план перевезень.

Розв'язок

Кожного постачальника умовно розбиваємо на дві частини згідно до двох видів зерна (А³₁, А⁴₁, А³₂ і А⁴₂), аналогічно споживачів розбиваємо на три частини (пшениця III класу, IV класу і будь-який клас): В³₁ і В⁴₁, а також, В⁰₂. Потреби перевищують запаси, тому вводимо фіктивного постачальника A₃. Частину кліток в таблиці замикаємо великими числами М; наприклад, в клітці (1;2) ставимо велике число. Це означає, що постачальник А³₁ не може задовольнити споживача В⁴₁ пшеницею IV класу за рахунок наявної пшениці III класу.

З урахуванням зроблених зауважень складемо першу таблицю

Перевезення від фіктивного постачальника не проводяться, тому c₅₁ = c₅₂ + c₅₃ + c₅₄ + c₅₅ + c₅₆ = 0. Причому величина М набагато більше c_ij. Застосовуючи метод потенціалів, у результаті отримаємо таблицю з оптимальним розв'язком

Аналіз розв'язку

Перший постачальник поставить на перший елеватор (B₁) пшеницю III класу (x₁₂ = 2); пшеницю IV класу (x₂₂ = 3), а також пшеницю будь-якого класу (III або IV) (x₁₃ = 1; x₂₃ = 1).

Другий постачальник (A₂) поставить на другий елеватор (B₂) пшеницю III класу (x₃₁ = 1), пшеницю IV класу (x₄₅ = 1,5) і частково будь-яку пшеницю (x₃₆ = 4; x₄₆ = 0,5). Потреба елеватора в будь-якій пшениці не задоволена на 1,25 тис. тон (x₅₆ = 1,25). Мінімальні витрати на перевезення склали: Z_min = 14 г.о.

Задачі для самоконтролю

В даній роботі в якості задач для самоконтролю можуть використовуватися задачі з попередніх робіт.

ТЕМА 13. Компоненти і класифікація моделей масового обслуговування

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

Практичне заняття №9. Моделі масового обслуговування

Мета: засвоїти основні поняття СМО.

План заняття

1. Поняття системи масового обслуговування (СМО).

2. Приклади систем масового обслуговування.

3. Основні компоненти системи масового обслуговування.

Теоретичні відомості, що необхідні для виконання робіт №9-11, містяться в конспекті лекцій за темою 13.

Приклад розв’язку типових задач

Приклад. Хай одноканальна СМО з відмовами є одним постом щоденного обслуговування (ЩО) для миття автомобілів. Заявка – автомобіль, що прибуває в момент, коли пост зайнятий – дістає відмову в обслуговуванні. Інтенсивність потоку автомобілів λ = 1,0 (автомобіль на годину). Середня тривалість обслуговування – t_c = 1,8 години. Потік автомобілів і потік обслуговуванні є простими.

Потрібно визначити в сталому режимі граничні значення:

- відносної пропускної спроможності q;

- абсолютної пропускної спроможності А;

- імовірності відмови P_відм;

Порівняти фактичну пропускну спроможність СМО з номінальною, яка була б, якби кожен автомобіль обслуговувався точно 1,8 години і автомобілі слідували один за іншим без перерви.

Розв'язок

1. Визначимо інтенсивність потоку обслуговування

μ = 1/t_c = 1/1,8 = 0,555.

2. Обчислимо відносну пропускну спроможність

q = μ/(μ + λ) = 0,555/(1 + 0,555) = 0,356.

Величина q означає, що в сталому режимі система обслуговуватиме приблизно 35%, що прибувають на пост ЩО автомобілів.

3. Абсолютну пропускну спроможність визначимо по формулі

А = λ*q = 1*0,356 = 0,356.

Це означає, що система (пост ЩО) здатна здійснити в середньому 0,356 обслуговування автомобілів за годину.

4. Імовірність відмови

P_відм = 1 – q = 1 – 0,356 = 0,644.

Це означає, що близько 65% прибулих автомобілів на пост ЩО дістануть відмову в обслуговуванні.

5. Визначимо номінальну пропускну спроможність системи

А_ном = 1/t_c = 1/1,8 = 0,555 (автомобілів на годину).

Виявляється, що А_ном в 1,5 раза (0,555/0,356 ≈ 1,5) більше, ніж фактична пропускна спроможність, обчислена з урахуванням випадкового характеру потоку заявок і часу обслуговування.

Практичне заняття №10. Моделі масового обслуговування

Мета: засвоїти основні поняття СМО.

План заняття

1. Вхідний потік вимог.

2. Дисципліна черги.

3. Механізм обслуговування.

Приклад розв’язку типових задач

Приклад. Спеціалізований пост діагностики є одноканальною СМО. Число стоянок для автомобілів, що чекають проведення діагностики, обмежено і дорівнює 3 ((N – 1) = 3). Якщо всі стоянки зайняті, тобто в черзі вже знаходиться три автомобілі, то черговий автомобіль, прибулий на діагностику, в чергу на обслуговування не стає. Потік автомобілів, що прибувають на діагностику, розподілений за законом Пуассона і має інтенсивність λ = 0,85 (автомобіля на годину). Час діагностики автомобіля розподілений по показовому закону і в середньому дорівнює t_c = 1,05 год.

Потрібно визначити імовірнісні характеристики поста діагностики, що працює в стаціонарному режимі.

Розв'язок

1. Параметр потоку обслуговуванні автомобілів

μ = 1/t_c  = 1/1,05 = 0,952.

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

Y = λ/μ = 0,85/0,952 = 0,893.

3. Обчислимо фінальну імовірність системи

Р₁ = Y*Р₀ = 0,893*0,248 ≈ 0,221,

Р₂ = Y²*Р₀ = 0,893²*0,248 ≈ 0,198,

Р₃ = Y³*Р₀ = 0,893³*0,248 ≈ 0,177,

Р₄ = Y⁴*Р₀ = 0,893⁴*0,248 ≈ 0,158,

4. Імовірність відмови в обслуговуванні автомобіля

P_відм = Р₄ = Y⁴ Р₀@ 0,158.

5. Відносна пропускна спроможність поста діагностики

q = 1 - P_відм = 1 – 0,158 = 0,842.

6. Абсолютна пропускна спроможність поста діагностики

А = λ*q = 0,842*0,85 = 0,716.

7. Середнє число автомобілів, що знаходяться на обслуговуванні і в черзі (тобто у системі масового обслуговування)

8. Середній час перебування автомобіля в системі години.

9. Середня тривалість перебування заявки в черзі на обслуговування години.

10. Середнє число заявок в черзі (довжина черги)

Роботу розглянутого поста діагностики можна вважати задовільною, оскільки пост діагностики не обслуговує автомобілі в середньому в 15,8% випадків (P_відм= 0,158).

Практичне заняття №11. Моделі масового обслуговування

Мета: засвоїти основні поняття СМО.

План заняття

1. СМО з обмеженим очікуванням.

2. СМО з необмеженим очікуванням.

3. СМО з різним числом каналів обслуговування.

Приклад розв’язку типових задач

Приклад. Хай n-канальна СМО є обчислювальним центром (ОЦ) з трьома (n = 3) взаємозамінними ПЕОМ для вирішення завдань, що поступають. Потік завдань, що поступають на ВЦ, має інтенсивність λ = 1 завданню на год. Середня тривалість обслуговування t_c = 1,8 год. Потік заявок на рішення задач і потік обслуговування цих заявок є простими.

Потрібно обчислити фінальні значення:

- імовірність станів ОЦ;

- імовірність відмови в обслуговуванні заявки;

- відносної пропускної спроможності ОЦ;

- абсолютної пропускної спроможності ОЦ;

- середнього числа зайнятих ПЕОМ на ОЦ.

Визначити, скільки додатково треба придбати ПЕОМ, щоб збільшити пропускну спроможність ОЦ в 2 рази.

Розв'язок

1. Визначимо параметр μ потоку обслуговуванні

μ = 1/t_c = 1/1,8 = 0,555.

2. Приведена інтенсивність потоку заявок

Y = λ/μ = 1/0,555 = 1,8.

3. Граничну імовірність станів знайдемо по формулах Ерланга (4.27)

Р₁ ≈ 1,8*0,186 ≈ 0,344,

Р₂ ≈ 1,62*0,186 ≈ 0,301,

Р₃ ≈ 0,97*0,186 ≈ 0,180.

4. Імовірність відмови в обслуговуванні заявки

P_відм = Р₃ = 0,18.

5. Відносна пропускна спроможність ОЦ

q = 1 – P_відм = 1 – 0,18 = 0,82.

6. Абсолютна пропускна спроможність ОЦ

А = λ*q = 1*0,82 = 0,82.

7. Середнє число зайнятих каналів – ПЕОМ

Таким чином, при сталому режимі роботи СМО в середньому буде зайнято 1,5 комп'ютера з трьох – інші півтора простоюватимуть. Роботу розглянутого ОЦ навряд чи можна вважати задовільною, оскільки центр не обслуговує заявки в середньому в 18% випадків. Очевидно, що пропускну спроможність ОЦ при даних λ і μ можна збільшити тільки за рахунок збільшення числа ПЕОМ.

Визначимо, скільки потрібно використовувати ПЕМ, щоб скоротити число необслужених заявок, що поступають на ОЦ, в 10 разів, тобто щоб імовірність відмови в рішенні завдань не перевершували 0,0180. Для цього використовуємо формулу (4.28)

Складемо наступну таблицю:

Задачі для самоконтролю

Задача 1. Періодичність надходження заявок на обслуговування підпорядкована показовому закону розподілу Середній інтервал між надходженнями заявок в систему рівний t_c = 2 год. Визначите послідовність значень тривалості інтервалів між надходженнями заявок. Число реалізацій рівне 10.

Задача 2. Час обслуговування працівника підприємства касою бухгалтерії є випадковій величиною, розподіленою відповідно до закону Вейбула. Середній час обслуговування t_c = 3 хв., середнє квадратичне відхилення рівне σ = 2 хв. Потрібно змоделювати випадкову величину, що відповідає цим умовам. Число реалізацій прийняти рівним 10.

Задача 3. При обробці експериментальних даних було встановлено, що час, що витрачається на станції технічного обслуговування автомобілів для заміни двигуна, розподілений по нормальному закону, параметри якого х_c = 2,8 час. на один двигун і σ = 0,6 год. Потрібно змоделювати для відмічених умов випадкову величину – час X, що витрачається для заміни двигуна. Число реалізацій прийняти рівним 5.

Задача 4. Час перевірки приймання квартального звіту інспектором Податкової служби (t) величина випадкова, розподілена відповідно до закону Вейбула. Середній час перевірки і приймання рівний t_c = 20 хв. Коефіцієнт варіації величини t дорівнює V_t = 0,52. Потрібно змоделювати для заданих умов випадкові числа t (число реалізацій прийняти рівним 10).

Задача 5. Середнє число справних верстатів в токарному цеху на заводі рівне х_c = 6. Середнє квадратичне відхилення σ = 2,2. Потрібно змоделювати число справних верстатів в цеху (число реалізацій рівне 5) за умови, що випадкова величина X має гамма-розподіл.

Задача 6. Система має два елементи. Середня періодичність першого елементу t_c1 = 60 год., другого елементу – t_c2 = 85 год. Періодичності відмови першого і другого елементів – випадкові вели чини, підлеглі експоненціальному закону розподілу. Визначите параметр і функцію розподілу потоку відмов системи по інтервалах часу Δt = 8 год. Число реалізацій N = 10.

Задача 7. Періодичність перевірки підприємств податкової інспекції - величина випадкова (t), така, що підкоряється закону гама-розподілу. Середній інтервал перевірки Δt_c = 2,5 міс. Коефіцієнт варіації величини t рівний V =0,38. Потрібно змоделювати для заданих умов можливі моменти перевірок підприємства податковою інспекцією (число реалізацій прийняти рівним 10).

Задача 8. Середнє число працюючих машин на заводі х_c = 25. Коефіцієнт варіації числа тих, що працюють V = 0,6. Потрібно змоделювати число працюючих машин на заводі (число реалізацій рівне 10). Випадкова величина X має розподіл Вейбула.

Задача 9. Після кожної перевірки підприємства податковою інспекцією вірогідність появи необхідності аудиторської перевірки Даного підприємства Р = 0,72. Змоделюйте шість випробувань. Визначите послідовність проведення різних перевірок підприємства.

ТЕМА 14. Визначення характеристик систем масового обслуговування

Характеристики СМО. Проста одноканальна модель з відмовами. Абсолютна і відносна пропускна спроможність системи. Одноканальна СМО з очікуванням. Одноканальна СМО з очікуванням без обмеження на місткість блоку очікування. Багатоканальна СМО. Формули Ерланга. Багатоканальна СМО з очікуванням. Модель обслуговування машинного парку.

Практичне заняття №12. Визначення характеристик систем масового обслуговування

Мета: засвоїти основні поняття і характеристики СМО.

План заняття

1. Характеристики СМО.

2. Проста одноканальна модель з відмовами.

3. Абсолютна і відносна пропускна спроможність системи.

Теоретичні відомості, що необхідні для виконання робіт №12-16, містяться в конспекті лекцій за темою 14.

Практичне заняття №13. Визначення характеристик систем масового обслуговування

Мета: засвоїти основні поняття і характеристки СМО

План заняття

1. Характеристки СМО.

2. Проста одноканальна модель з відмовами.

3. Абсолютна і відносна пропускна спроможність системи.

Практичне заняття №14. Визначення характеристик систем масового обслуговування

Мета: засвоїти основні поняття і характеристики СМО.

План заняття

1. Одноканальна СМО з очікуванням.

2. Одноканальна СМО з очікуванням без обмеження на місткість блоку очікування.

3. Багатоканальна СМО.

Практичне заняття №15. Визначення характеристик систем масового обслуговування

Мета: засвоїти основні поняття і характеристики СМО.

План заняття

1. Одноканальна СМО з очікуванням.

2. Одноканальна СМО з очікуванням без обмеження на місткість блоку очікування.

3. Багатоканальна СМО.

Практичне заняття №16. Визначення характеристик систем масового обслуговування

Мета: засвоїти основні поняття і характеристики СМО.

План заняття

1. Формули Ерланга.

2. Багатоканальна СМО з очікуванням.

3. Модель обслуговування машинного парку.

ТЕМА 17. Моделювання систем масового обслуговування з використанням методу Монте-Карло

Метод статистичних випробувань (метод Монте-Карло). Початкові дані для вирішення задачі статистичного моделювання функціонування СМО. Етапи рішення задачі статистичного моделювання функціонування СМО.

Практичне заняття №17. Моделювання систем масового обслуговування з використанням методу Монте-Карло

Мета: засвоїти основні етапи статистичного моделювання функціонування СМО.

План заняття

1. Метод статистичних випробувань (метод Монте-Карло).

2. Початкові дані для вирішення задачі статистичного моделювання функціонування СМО.

3. Етапи рішення задачі статистичного моделювання функціонування СМО.

Теоретичні відомості, що необхідні для виконання даної роботи, містяться в конспекті лекцій за темою 17.

Приклад розв’язку типових задач

Для розв'язку задачі статистичного моделювання функціонування СМО повинні бути задані наступні початкові дані:

- опис СМО (тип, параметри, критерії ефективності роботи системи);

- параметри закону розподілу періодичності надходжень вимог в систему;

- параметри закону розподілу часу перебування вимоги в черзі (для СМО з очікуванням);

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

Розв'язок задачі статистичного моделювання функціонування СМО складається з наступних етапів.

1. Генерують рівномірно розподілене випадкове число r_i.

2. Рівномірно розподілені випадкові числа перетворюють у величини із заданим законом розподілу:

- інтервал часу між надходженнями вимог в систему (Dt_n);

- час відходу заявки з черги (для СМО з обмеженою довжиною черги);

- тривалість часу обслуговування вимоги каналами (Dt_a).

3. Визначають моменти настання подій:

- надходження вимоги на обслуговування;

- відхід вимоги з черги;

- закінчення обслуговування вимоги в каналах системи.

4. Моделюють функціонування СМО в цілому і накопичують статистичні дані про процес обслуговування.

5. Встановлюють новий момент надходження вимоги в систему і обчислювальна процедура повторюється відповідно до викладеного.

6. Визначають показники якості функціонування СМО шляхом обробки результатів моделювання методами математичної статистики.

ТЕМА 18. Моделювання потоків відмов елементів складних технічних систем

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

Практичне заняття №18. Моделювання потоків відмов елементів складних технічних систем

Мета: засвоїти основні прийоми моделювання потоків відмов елементів складних систем.

План заняття

1. Складні технічні системи.

2. Система взаємно незалежних випадкових величин.

3. Провідна функція.

Теоретичні відомості, що необхідні для виконання даної роботи, містяться в конспекті лекцій за темою 18.

Приклад розв’язку типових задач

Приклад. Закони розподілу напрацювань елементу системи до першої і другої відмов і відповідні параметри цих законів приведені в наступній таблиці

Визначите номери часових інтервалів, на яких про вийдуть перша і друга відмови в ході першого досвіду (випробування) (Dt_i = 1 година).

Розв'язок

1. Виберемо рівномірно розподілене випадкове число. Допустимо i = 0,725.

2. Обчислимо випадкові значення напрацювань на відмову елементу використовуючи формули табл. 5.1.

3. Визначимо номер часового інтервалу, на якому відбудуться відмови

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

В ході першої реалізації елемент системи перший раз відмовить на 21-му часовому інтервалі, а друга відмова відбудеться на 22-му часовому інтервалі.

ТЕМА 19. Моделі управління запасами

Поняття запасів. Причини, спонукаючі організації створювати запаси. Причини, спонукаючі підприємства прагнути до мінімізації запасів на складі. Витрати виконання замовлення (витрати замовлення). Витрати зберігання. Упущений прибуток. Сукупні витрати. Термін виконання замовлень. Точка відновлення.

Практичне заняття №19. Моделі управління запасами

Мета: засвоїти основні поняття моделювання управління запасами.

План заняття

1. Причини, спонукаючі організації створювати запаси.

2. Причини, спонукаючі підприємства прагнути до мінімізації запасів на складі.

3. Витрати виконання замовлення (витрати замовлення).

4. Витрати зберігання.

5. Упущений прибуток.

6. Сукупні витрати.

7. Термін виконання замовлень.

8. Точка відновлення.

Теоретичні відомості, що необхідні для виконання даної роботи, містяться в конспекті лекцій за темою 19.

Приклад розв’язку типових задач

Приклад. Отримання замовлення не миттєве

Торговий агент компанії займається продажем автомобіля. Річний попит оцінюється в 4000 од. Ціна кожного автомобіля дорівнює 90 тис. грн., а річні витрати зберігання складають 10% від ціни самого автомобіля. Агент провів аналіз витрат замовлення і зрозумів, що середні витрати замовлення складають 25 тис. грн. на замовлення. Час виконання замовлення дорівнює восьми дням. Протягом цього часу щоденний попит на автомобілі складає 20 од.

Чому дорівнює оптимальний розмір замовлення?

Чому дорівнює точка відновлення?

Які сукупні витрати?

Яка оптимальна кількість замовлень в рік?

Який оптимальний час між двома замовленнями, якщо припустити, що кількість робочих днів в році дорівнює 200?

Отже, визначимо початкові дані задачі:

величина попиту за рік D = 4000 од;

витрати на замовлення С₁ = 25 тис. грн.;

витрати на зберігання С₂ = 90*0,1/200 = 0,045;

ціна за одиницю с = 90 тис. грн.;

час виконання замовлення L = 8 діб;

щоденний попит l = 20;

число робочих днів T = 200 діб.

Розв'язок

Оптимальний розмір замовлення ;

точка відновлення R = 8*20 – 149 = 160 – 149 = 11;

число замовлень за рік N = D/Q* = 26,83;

сукупні витрати S дорівнюють сукупним витратам замовлення плюс сукупні витрати зберігання, тобто S = 4000*25/149 + 149*9/2 = 1341,64;

вартість продажів S₁ = 90*4000 = 360000;

число днів між замовленнями t = 149/20 = 7,45.

ТЕМА 20. Характеристика моделей управління запасами

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

Практичне заняття №20. Моделі управління запасами

Мета: засвоїти основні характеристики моделей управління запасами.

План заняття

1. Модель оптимального розміру замовлення в припущенні, що отримання замовлення не миттєве.

2. Модель оптимального розміру замовлення в припущенні, що допускається дефіцит продукту і пов'язаний з ним упущений прибуток.

3. Модель з урахуванням виробництва.

4. Модель з кількісними знижками.

5. Модель найбільш економічного розміру замовлення.

6. Модель оптимального розміру замовлення.

7. Модель виробництва і розподілу.

8. Модель з кількісними знижками.

Теоретичні відомості, що необхідні для виконання даної роботи, містяться в конспекті лекцій за темою 20.

Приклад розв’язку типових задач

Приклад. Кількісні знижки

Для збільшення об'єму продажів компанії часто пропонують кількісні знижки своїм покупцям. Кількісна знижка – скорочена ціна на товар у разі покупки великої кількості цього товару. Типові приклади кількісних знижок приведена в таблиці

Хай I – частка витрат зберігання в ціні продукту с.

Тоді

h = Ic,

оптимальний розмір замовлення.

Розглянемо приклад, що пояснює принцип ухвалення рішення в умовах знижки. Магазин «Ведмежа» продає іграшкові гоночні машинки. Ця фірма має таблицю знижок на машинки у разі покупок їх в певній кількості (табл. 6.1). Витрати замовлення складають 49 тис. грн. Річний попит на машинки рівний 5000, річні витрати зберігання у відношенні до ціни складають 20% або 0,2. Необхідно знайти розмір замовлення, що мінімізує загальні витрати.

Розв'язок

Розрахуємо оптимальний розмір замовлення для кожного виду знижок, тобто Q₁*, Q₂* і Q₃*, і отримаємо Q₁* = 700, Q₂* = 714, Q₃* = 718.

Оскільки Q₁* – величина між 0 і 999, то її можна залишити колишньою. Q₂* менше кількості, необхідної для отримання знижки, отже, його значення необхідно прийняти рівним 1000 одиниць. Аналогічно Q3* беремо рівним 2000 одиниць. Отримаємо Q₁* = 700, Q₂* = 1000, Q₃* = 2000.

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

Розглянемо наступну таблицю.

Виберемо той розмір замовлення, яке мінімізує загальні річні витрати. З таблиці видно, що замовлення у розмірі 1000 іграшкових гоночних машинок мінімізуватиме сукупні витрати.

Задачі для самоконтролю

Задача 1. Менеджер набуває протягом року 1500 телевізорів для роздрібного продажу в своє магазині. Витрати зберігання кожного телевізора рівні 45 тис. крб. в рік. Витрати замовлення – 150 тис. крб. Кількість робочих днів в році рівна 300, час виконання замовлення – 6 днів. Необхідний знайти:

- оптимальний запас замовлення;

- річні витрати замовлення;

- точку відновлення запасу.

Задача 2. Менеджер продає 400 водяних ліжок в рік, причому витрати зберігання рівні 1 тис. крб. за ліжко в день і витрати замовлення – 40 тс. Крб. Кількість робочих днів рівна 250 і час виконання замовлення – 6 днів.

Який оптимальний розмір замовлення?

Чому рівна точка відновлення запасу?

Який оптимальний розмір замовлення, якщо витрачання зберігання рівні 1,5 тис. грн.?

Задача 3. Власник маленької компанії, яка випускає електричні ножі, може проводити 150 ножів в день. Денний попит на ножі приблизно рівний 40. Фіксовані витрати виробництва рівні 100 тис. крб., витрати зберігання – 8 тис. крб. за ніж в рік. Яке максимальне замовлення слід мати на складі?

Задача 4. Компанія купує у заводу-виготівника лобові стекла вантажних автомобілів для роздрібного продажу. У рік, за 200 робочих днів, реалізується близько 10 000 стекол. Витрати замовлення для компанії складають 400 тис. крб., щоденні витрати зберігання одного скла – 6 тис. крб.

Чому рівний оптимальний розмір замовлення?

Які мінімальні річні сукупні витрати?

Задача 5. Річне замовлення на тостер рівне 3 000 одиниць, або 10 в день. Витрати замовлення рівні 25 тис. крб., витрати зберігання – 0,4 тис. крб. в день. Оскільки тостер є дуже популярним серед покупців, то у разі відсутності товару покупці зазвичай згодні почекати. Поки не підійде наступне замовлення. Проте витрати, пов'язані з дефіцитом, рівні 0,75 тис. крб. за тостер в день.

Скільки тостерів замовлятиме менеджер.

Який мінімальний дефіцит?

Чому рівні сукупні витрати?

Задача 6. Магазин користується популярністю у покупців завдяки широкому асортименту екологічно чистих продуктів. Більшість покупців не відмовляються від послуг магазина навіть  тому випадку, коли товар, що цікавить їх, відсутній у продажу. Вони залишають замовлення на товар і чекають, коли поступить нова партія.

Сирий – не найпопулярніший зі всього набору товарів, але адміністратор магазина регулярно замовляє цей продукт. Річний попит на сир складає 500 головок. Витрати замовлення – 40 тис. крб. за замовлення. Витрати зберігання – 5 тис. крб. в рік Упущений прибуток унаслідок дефіциту складає 100 тис. крб. в рік на одну головку сира.

Скільки головок сиру слід замовляти, щоб не допускати дефіциту і мати при цьому мінімальні загальні витрати?

Скільки сиру слід замовляти, якщо допустити можливість дефіциту?

Чому дорівнює точка відновлення запасу, якщо час виконання замовлення 10 днів і число робочих днів в році 250?

Чому дорівнює максимальний розмір дефіциту?

Задача 7. Компанія пропонує наступні знижки для лінолеуму розміром 2 3 м.

Магазин замовляє у компанії лінолеум. Витрати замовлення рівні 45 тис. крб. Річні витрати зберігання рівні 50% від ціни. Річний попит на лінолеум в магазині складає 100 шматків. Яку кількість необхідно придбати?

Задача 8. Меблевий салон продає в рік близько 1000 спальних гарнітурів за ціною 50 тис. крб. Розміщення одного замовлення на постачання гарнітурів обходиться в 40 тис. крб. Річна вартість зберігання гарнітура складає 25% його ціни. Салон може отримувати 3%-ную знижки у постачальника, якщо розмір замовлення складе не меншого 200 гарнітурів. Чи слід салону замовляти 200 або більш за гарнітури і користуватися знижкою?

З повагою ІЦ “KURSOVIKS”!