Методичні вказівки до організації самостійної та індивідуальної роботи студентів з дисципліни Дослідження операцій, НУДПСУ
« НазадМЕТОДИЧНІ ВКАЗІВКИдо організації самостійної та індивідуальної роботи студентів з дисципліни«ДОСЛІДЖЕННЯ ОПЕРАЦІЙ»
ВСТУПКурс «Дослідження операцій» – обов'язковий компонент загальної та професійної освіти. Значення курсу «Дослідження операцій» у загальноосвітній підготовці визначається насамперед тим, що будь-які дослідження є фундаментом науково-дослідницької діяльності та науково-технічного прогресу. Дисципліна «Дослідження операцій» призначена для оволодіння майбутніми бакалаврами спеціальності «Інтелектуальні системи прийняття рішень» основами знань у галузі дослідження операцій, на базі яких провадиться подальше вивчення спеціальних дисциплін, пов’язаних з фаховою діяльністю. У результаті вивчення дисципліни студент повинен одержати фундаментальні теоретичні знання у галузі дослідження операцій і закріпи їх на практичних заняттях. Програма курсу «Дослідження операцій» охоплює достатній обсяг матеріалу, який дозволяє підготувати бакалаврів належного рівня. Вона складена згідно з вимогами «Положення про програму дисципліни» і є нормативним документом, який визначає мету і завдання курсу, місце курсу серед дисциплін професійної підготовки. Типова програма відповідає діючим підручникам, що використовується у навчальному процесі. Мета курсу полягає в тому щоб забезпечити загальний розвиток світогляду студентів, їх ознайомлення з методологією дослідження операцій, на основі яких додатково розглянути сучасні уявлення про методи аналізу та синтезу систем. Дослідження операцій спрямоване на розв'язання складних проблем. Метою застосування дослідження операцій до конкретної проблеми є підвищення ступеня обґрунтованості рішення, що приймається. Досягнення цієї загальної мети у практиці викладення курсу можна здійснювати різними шляхами:
Завдання курсу полягає у тому, щоб навчити студента системі методів дослідження систем. Критерії оцінки успішності повинні відповідати навчальній програмі й найбільш важливим вимогам до знань студентів: 1. Знання фактів, явищ. Вірне, науково достовірне їх пояснення. 2. Оволодіння науковими термінами, поняттями, законами, методами, правилами; вміння користуватися ними при пояснені нових фактів, розв‘язуванні різних питань і виконанні практичних завдань. 3. Максимальна ясність, точність думки, вміння відстоювати свої погляди, захищати їх. Методи і форми викладання дисципліниВивчення дисципліни передбачає лекційні та практичні заняття.. Значна частина матеріалу дисципліни відведена під індивідуальні заняття студентів під керівництвом та СРС. СРС використовується студентами для проробки лекційного матеріалу, навчально-методичної літератури, при підготовці до практичних та лабораторних занять. Навчальна дисципліна «Дослідження операцій» розглядається як елемент загальної освіти і відіграє роль апарату вивчення та засвоєння закономірностей навколишнього світу та фундаменту професійних знань галузевої техніки чи технології. Навчання слід спрямувати на розв'язання задач, формування уміння використовувати наукові знання для розв'язання практичних завдань у відповідних галузях професійної діяльності, прийняття обґрунтованих конструкторсько-технологічних рішень в конкретних виробничих завданнях, застосування фізичних методів і теорій у поясненні суті технічних і технологічних процесів. Навчальна дисципліна забезпечує поглиблене вивчення наступних дисциплін: «Архітектура комп‘ютера», «Комп’ютерна схемотехніка», «Комп’ютерні мережі». Форми і засоби проміжного та підсумкового контролю: експрес-контроль рівня готовності студента до проведення та практичних робіт; перевірка виконання позааудиторних завдань; оцінка роботи студента під час заняття (виступи, доповнення, участь у дискусії); виконання домашних завдань; контрольні роботи в кінці залікового кредиту. Оцінка індивідуальних результатів здобуття знань студентами проводиться у формі заліку за кредитно-модульною методологією навчання, критерії якої визначаються у навчальній робочій програми за стобальною системою, яка трансформується у стандартні залікові диференційовані оцінки відповідно до вимог Міністерства освіти та науки України.
ТЕОРЕТИЧНІ ОСНОВИ1. Задача лінійного програмуванняЛінійне програмування є найбільш простим і краще всього вивченим розділом математичного програмування. Характерні риси задач лінійного програмування наступні: 1) показник оптимальності f(х) є лінійною функцією від елементів рішення x = (x1, x2,..., xn); 2) обмежувальні умови, що накладаються на можливі розв'язки, мають вид лінійних рівностей або нерівностей. Задачею лінійного програмування називається задача дослідження операцій, математична модель якої має вигляд. При цьому система лінійних рівнянь (2.3) і нерівностей (2.4), (2.5), що визначає допустиму множину розв'язків задачі W, називається системою обмежень задачі лінійного програмування, а лінійна функція f(х) називається цільовою функцією або критерієм оптимальності. У окремому випадку, якщо I = Ø, то система (2.3) – (2.4) складається тільки з лінійних нерівностей, а якщо I = M, то – з лінійних рівнянь. При описі реальної ситуації за допомогою лінійної моделі слід перевіряти наявність у моделі таких властивостей, як пропорційність і адитивність. Пропорційність означає, що внесок кожної змінної в цільовій функції і загальний об'єм споживання відповідних ресурсів повинні бути прямо пропорційні величині цієї змінної. Наприклад, якщо, продаючи j-й товар в загальному випадку за ціною 100 рублів, фірма робитиме знижку при певному рівні закупівлі до рівня ціни 95 рублів, то буде відсутня пряма пропорційність між доходом фірми і величиною змінної xj. Тобто в різних ситуаціях одна одиниця j-го товару приноситиме різний дохід. Адитивність означає, що цільова функція і обмеження повинні бути сумою внесків від різних змінних. Прикладом порушення адитивності служить ситуація, коли збільшення збуту одного з конкуруючих видів продукції, вироблюваних однією фірмою, впливає на об'єм реалізації іншого. Допустимий розв'язок – це сукупність чисел (план) x = (x1, x2,..., xn), що задовольняють обмеженням задачі. Оптимальний розв'язок – це план, при якому цільова функція приймає своє максимальне (мінімальне) значення. Якщо математична модель задачі лінійного програмування має вигляд. то говорять, що задача представлена в канонічній формі. Будь-яку задачу лінійного програмування можна звести до задачі лінійного програмування в канонічній формі. Для цього в загальному випадку потрібно уміти зводити задачу максимізації до задачі мінімізації; переходити від обмежень нерівностей до обмежень рівностей і замінювати змінні, які не підкоряються умові позитивності. Максимізація деякої функції еквівалента мінімізації тієї ж функції, узятої з протилежним знаком, і навпаки. Правила приведення задачі лінійного програмування до канонічного вигляду полягають в наступному:1) якщо в початковій задачі потрібно визначити максимум лінійної функції, то слід змінити знак і шукати мінімум цієї функції; 2) якщо в обмеженнях права частина негативна, то слід помножити це обмеження на – 1; 3) якщо серед обмежень є нерівності, то шляхом введення додаткових ненегативних змінних вони перетворяться в рівність; 4) якщо деяка змінна xk не має обмежень по знаку, то вона замінюється (у цільовій функції і у всіх обмеженнях) різницею між двома новими ненегативними змінними: хk = х1k – хl, де l – вільний індекс х1k ³ 0, хl ³ 0. Приклад. Приведення до канонічної форми задачі лінійного програмуванняminZ = 2х1 + 3х2 – х3; 2х2 – х3 ≤ 5; х1 + х2 – х3 ³ – 1; 2х1 – х2 ≤ – 3; х1 ≤ 0, х2 ³ 0, х3 ³ 0. Введемо в кожне рівняння системи обмежень вирівнюючі змінні x4, x5, x6. Система запишеться у вигляді рівностей, причому в перше і третє рівняння системи обмежень змінні x4, x6 вводяться в ліву частину із знаком «+», а в друге рівняння вводиться x5 із знаком «–». 2х2 – х3 + х4 = 5; х1 + х2 – х3 – х5 = – 1; 2х1 – х2 + х6 = – 3; х4 ³ 0, х5 ³ 0, х6 ³ 0. Вільні члени в канонічній формі повинні бути позитивними, для цього два останні рівняння помножимо на – 1 2х2 – х3 + х4 = 5; – х1 – х2 + х3 + х5 = 1; – 2х1 + х2 – х6 = 3; У канонічній формі запису задач лінійного програмування всі змінні, що входять в систему обмежень, повинні бути негативними. Допустимо, що х1 = х11 – х7 де х7 ³ 0. Підставляючи даний вираз в систему обмежень і цільову функцію і записуючи змінні в порядку зростання індексу, отримаємо задачу лінійного програмування, представлену в канонічній формі minZ = 2х11 + х2 – х3 – 2х7, 2х2 – х3 + х4 = 5; – х11 – х2 + х3 + х5 + х7 = 1; – 2х11 + х2 – х6 + 2х7 = 3; х11 ³ 0, хі ³ 0, і = 2,…,7. 2. Побудова економіко-математичних моделей задач лінійного програмуванняРозглянемо процес побудови математичних моделей задач лінійного програмування на прикладах. Приклад. Визначення оптимального асортименту продукціїПідприємство виготовляє два види продукції – П1 і П2, яка поступає в оптовий продаж. Для виробництва продукції використовуються два види сировини – А і В. Максимально можливі запаси сировини на добу складають 9 і 13 одиниць відповідно. Витрата сировини на одиницю продукції виду П1 і виду П2 дана в табл. 2.1. Таблиця 1. Витрати сировини продукції
Досвід роботи показав, що добовий попит на продукцію П1 ніколи не перевищує попиту на продукцію П2 більш ніж на 1 од. Крім того, відомо, що попит на продукцію П2 ніколи не перевищує 2 од. на добу. Оптові ціни одиниці продукції рівні: 3 г.о. (грошові одиниці) – для П1 і 4 г.о. для П2. Яку кількість продукції кожного виду повинно виготовляти підприємство, щоб дохід від реалізації продукції був максимальним? Процес побудови математичної моделі для вирішення даної задачі починається з відповідей на наступні питання: 1. Для визначення яких величин повинна бути побудована модель, тобто як ідентифікувати змінні даної задачі? 2. Які обмеження повинні бути накладені на змінні, щоб виконувалися умови, характерні для модельованої системи? 3. У чому полягає мета задачі, для досягнення якої зі всіх допустимих значень змінних потрібно вибрати ті, які відповідатимуть оптимальному (якнайкращому) розв'язку задачі? Відповіді на вище перелічені питання можуть бути сформульовані для даної задачі так: фірмі потрібно визначити об'єми виробництва кожного виду продукції в тонах, щоб максимізувати дохід в г.о. від реалізації продукції з урахуванням обмежень на попит і витрату початкових продуктів. Для побудови математичної моделі залишається тільки ідентифікувати змінні і представити мету і обмеження у вигляді математичних функцій цих змінних. Припустимо, що підприємство виготовить х1 одиниць продукції П1 і х2 одиниць продукції П2. Оскільки виробництво продукції П1 і П2 обмежено сировиною кожного виду, що є у розпорядженні підприємства, і попитом на дану продукцію, а також враховуючи, що кількість виробів, що виготовляються, не може бути негативною, повинні виконуватися наступні нерівності 2х1 + 3х2 ≤ 9; 3х1 + 2х2 ≤ 13; х1 – х2 ≤ 1; х2 ≤ 2; х1 ³ 0; х2 ³ 0. Дохід від реалізації х1 одиниць продукції П1 і х2 одиниць продукції П2 складе F = 3х1 + 4х2. Таким чином, приходимо до наступної математичної задачі: серед всіх ненегативних розв'язків даної системи лінійних нерівностей потрібно знайти таке, при якому функція F приймає максимальне значення Fmax. 3. Графічний розв'язок задачі лінійного програмуванняГрафічно спосіб розв'язку задач лінійного програмування доцільно використовувати для:
Запишемо задачу лінійного програмування з двома змінними цільова функція Zmax = с1х1 + с2х2 (2.34) обмеження х1 ³ 0, х2 ³ 0. (2.36) Графічний розв'язок задачі лінійного програмування базується на тому факті, що кожна з нерівностей (2.35) – (2.36) системи обмежень задачі геометрично визначає напівплощину відповідно з граничними прямими ai1x1 + ai2x2 = bi, (i = 1,…,m), x1 = 0, x2 = 0. В тому випадку, коли система нерівностей (2.35) – (2.36) сумісна, область розв'язків є множина точок, що належать всім вказаним напівплощинам. Оскільки множина точок перетину даних напівплощин – опукла, то областю допустимих значень є опукла множина, яка називається багатокутником розв'язків. Сторони цього багатокутника лежать на прямих, рівняння яких виходять з початкової системи обмежень заміною знаків нерівностей на знаки рівності. Областю допустимих розв'язків системи нерівностей (2.35) – (2.36) можуть бути:
Цільова функція (2.34) визначає на площині сімейство паралельних прямих, кожній з яких відповідає визначене значення Z. Вектор з координатами с1 і с2, перпендикулярний до цих прямих, указує напрям найшвидшого зростання Z, а протилежний вектор – напрям убування Z. Цей вектор ще називають градієнтом цільової функції. Якщо в одній і тій же системі координат зобразити область допустимих розв'язків системи нерівностей (2.35) – (2.36) і сімейство паралельних прямих (2.34), то задача визначення максимуму функції Z зведеться до знаходження в допустимій області точки, через яку проходить пряма з сімейства Z = const, і яка відповідає найбільшому значенню параметра Z. Ця точка існує тоді, коли багатокутник розв'язків не порожній і на ньому цільова функція обмежена зверху. За вказаних умов в одній з вершин багатокутника розв'язків цільова функція приймає максимальне значення. Для визначення даної вершини побудуємо лінію рівня, що проходить через початок координат і перпендикулярну вектору, і пересуватимемо її у напрямі вектора-градієнта С = (с1;с2) до тих пір, поки вона не торкнеться останньої крайньої (кутової) точки багатокутника розв'язків. Координати вказаної точки і визначають оптимальний план даної задачі. Закінчуючи розгляд геометричної інтерпретації задачі (2.35) – (2.36), відзначимо, що при знаходженні її розв'язку можуть зустрітися випадки, зображені на мал.1 – 4. Мал. 1 характеризує такий випадок, коли цільова функція приймає максимальне значення в єдиній точці А. Із мал. 2 видно, що максимальне значення цільова функція приймає в будь-якій точці відрізка АВ. На мал. 3 зображено випадок, коли максимум недосяжний, а на мал. 4. – випадок, коли система обмежень задачі є несумісною. Відзначимо, що знаходження мінімального значення Z при даній системі обмежень відрізняється від знаходження її максимального значення при тих же обмеженнях лише тим, що лінія рівня Z пересувається не у напрямі вектора, а в протилежному напрямі. Таким чином, відмічені вище випадки, що зустрічаються при знаходженні максимального значення цільової функції, мають місце і при визначенні її мінімального значення. Отже, для практичного розв'язку задач лінійного програмування (2.34) – (2.36) на основі її геометричної інтерпретації необхідно наступне: 1. Побудувати прямі, рівняння яких виходять в результаті заміни в обмеженнях (2.35) – (2.36) знаків нерівностей на знаки рівності. 2. Знайти напівплощини, що визначаються кожним з обмежень. 3. Визначити багатокутник розв'язків. 4. Побудувати вектор-градієнт С = (с1;с2). 5. Побудувати пряму, що проходить через початок координат і перпендикулярну вектору С = (с1;с2). 6. Пересувати пряму Z у напрямі вектора С, внаслідок чого або знаходять точку (точки), в якій функція приймає максимальне значення, або встановлюють необмеженість функції зверху на множині планів. 7. Визначити координати точки максимуму функції і обчислити значення цільової функції в цій точці. Приклад.Розглянемо розв'язок задачі про асортимент продукції геометричним способом. Розв'язок Побудуємо багатокутник розв'язків (мал. 5). Для цього в системі координат x10x2 на площині зобразимо граничні прямі 2x1 + 3x2 = 9, (L1); 3x1 + 2x2 = 13, (L2); x1 – 3x2 = 1, (L3); x2 = 2. (L4). Узявши яку-небудь точку, наприклад, початок координат, встановимо, яку напівплощину визначає відповідна нерівність. Напівплощини, визначувані нерівностями, на мал. 5 показані стрілками. Отже, областю розв'язків є багатокутник OABCD. Для побудови прямої Z = 3x1 + 4x2 = 0 будуємо вектор-градієнт С = (3;4) і через початок координат проводимо пряму, перпендикулярну йому. Побудовану пряму Z = 0 переміщуємо паралельно самій собі у напрямі вектора С = (3;4). З мал. 5 виходить, що по відношенню до багатокутника розв'язків опорною ця пряма стає в точці C, де функція приймає максимальне значення. Точка С лежить на перетині прямих L1 і L3. Для визначення її координат розв'яжемо систему рівнянь. Оптимальний план задачі x1 = 2,4; x2 = 1,4. Підставляючи значення х1 і х2 в лінійну функцію, отримаємо: Zmax = 3x1 + 4x2 = 3 2,4 + 4 1,4 = 12,8. Отриманий розв'язок означає, що об'єм виробництва продукції П1 повинен бути рівний 2,4 од., а продукції П2 – 1,4 од. Дохід, що отримується в цьому випадку, складе: Z = 12,8 г.о. 4. Симплекс-методДля початку роботи потрібно, щоб задана система обмежень виражалася рівностями, причому в цій системі обмежень повинні бути виділені базисні невідомі, тобто обрано базис, інші ж змінні називаються вільними. Розв'язок задачі за допомогою симплекс-метода розпадається на ряд кроків. На кожному кроці від даного базису переходять до іншого, нового базису з таким розрахунком, щоб значення функції Z зменшувалося. Для переходу до нового базису із старого базису віддаляється одна із змінних і замість неї вводиться інша з числа вільних. Після кінцевого числа кроків або знаходиться такий базис, для якого є шуканий мінімум для лінійної функції Z, а відповідний базисний розв'язок є оптимальним, або з'ясовується, що задача не має розв'язку. Розглянемо систему лінійних обмежень і лінійну форму вигляду Zmin = c0 + c1x1 + … + cnxn, (2.38) xi ³ 0, i = 1,2,…,n. (2.39) тобто обмеження мають форму рівностей. Введемо умовні позначення: х1, x2 ..., xr– базисні змінні; xr+1, xr+2,..., xn– вільні змінні. Тепер приведемо записану систему до вигляду, де виділено базисні змінні, тобто виразимо базисні змінні через вільні. Це можна зробити різними способами, зокрема, за допомогою метода Жордана-Гауса. Вирази для базисних змінних підставимо і в цільову функцію. Отримаємо наступну систему співвідношень Zmin = g0 – (gr+1xr+1 + gr+2xr+2 + … + gnxn). (2.41) За останньою системою обмежень і цільовою функцією Z побудуємо табл. 2.3. Таблиця 2.3. Симплекс-таблиця
Дана таблиця називається симплекс-таблицею. Всі подальші перетворення симплекс-методу пов'язані із зміною змісту саме цієї таблиці. Алгоритм симплекс-методу зводиться до наступного.1. У останньому рядку симплекс-таблиці знаходять найменший позитивний елемент, не рахуючи вільного члена. Стовпець, що відповідає цьому елементу, вважається вирішуючим. 2. Обчислюють відношення вільних членів до позитивних елементів вирішуючого стовпця (симплекс-відношення). Знаходять найменше з цих симплекс-відношень, воно відповідає вирішуючому рядку. 3. На перетині вирішуючого рядка і вирішуючого стовпця знаходиться вирішуючий елемент. 4. Якщо є декілька однакових по величині симплекс-відношень, то вибирають будь-яке з них. Те ж саме відноситься до позитивних елементів останнього рядка симплекс-таблиці. 5. Після знаходження вирішуючого елементу переходять до наступної таблиці. Невідомі змінні, що відповідають вирішуючому рядку і стовпцю, міняють місцями. При цьому базисна змінна стає вільною змінною і навпаки. Симплекс-таблиця перетворюється наступним чином (табл. 2.4). В таблиці 2.4 перетворення рядка і стовпця зроблені у припущенні, що вирішуючим елементом є a1r+2. 6. Елемент табл. 2.4, що відповідає вирішуючому елементу табл. 2.3, дорівнює зворотній величині вирішуючого елементу. 7. Елементи рядка табл. 2.4, що відповідають елементам вирішуючого рядка табл. 2.3, знаходять шляхом ділення відповідних елементів табл. 2.3 на вирішуючий елемент 8. Елементи стовпця табл. 2.4, що відповідають елементам вирішуючого стовпця табл. 2.3, знаходять шляхом ділення відповідних елементів табл. 2.3 на вирішуючий елемент і беруться з протилежним знаком. 9. Решта елементів обчислюється за правилом прямокутника: у думках викреслюємо прямокутник в табл. 2.3, одна вершина якого співпадає з вирішуючим елементом, а інша – з елементом, образ якого шукаємо; останні дві вершини визначаються однозначно. Тоді шуканий елемент з табл. 2.4 дорівнюватиме відповідному елементу табл. 2.3 мінус дріб, в знаменнику якого стоїть вирішуючий елемент, а в чисельнику – добуток елементів з двох невикористаних вершин прямокутника. 10. Як тільки вийде таблиця, в якій в останньому рядку всі елементи негативні, вважається, що мінімум знайдено. Мінімальне значення функції дорівнює вільному члену в рядку цільової функції, а оптимальний розв'язок (тобто значення базисних змінних) визначається вільними членами при базисних змінних. Всі ж вільні змінні в цьому випадку дорівнюють нулю. 11. Якщо у вирішуючому стовпці всі елементи негативні, то задача не має розв'язків (мінімум не досягається). Зауваження.Для побудови симплекс-таблиці слід обов’язково всі співвідношення (2.40)-(2.41) привести саме до поданої форми: вільний член мінус дужки, в дужках – лінійна комбінація вільних змінних. Таблиця 2. Перетворення симплекс-таблиці
Приклад. Розв'яжемо наступну задачу симплекс-методом Zmax = 2x1 – x2 + 3x3 – 2x4 + x5. Приведемо завдання до вигляду, що допускає застосування симплекс-алгоритму, обравши в якості базисних змінних х3, х4, х5. Отримаємо х3 = 1 – (– х1 + х2), х4 = 1 – (х1 – х2), х5 = 2 – (х1 + х2). Підставимо у вираз Zmax величини x3, x4, x5 Zmax = 6x1 – 7x2 + 3. За алгоритмом цільова функція повинна прагнути до мінімуму Zmin = – Zmax = – 6x1 + 7x2 – 3 = – 3 – (6x1 – 7x2). Складемо початкову симплекс-таблицю
Розшукуємо в останньому рядку найменший позитивний елемент, в нашому прикладі він дорівнює +6, отже, перший стовпець коефіцієнтів буде вирішуючим. Визначимо відношення вільних членів до позитивних елементів вирішуючого стовпця. Мінімальне симплекс-відношення дорівнює 1, отже, вирішуючий елемент знаходиться на перетині рядка зі змінною x4і стовпця – x1. Переходимо до наступної таблиці, використовуючи правило прямокутника
У останньому рядку немає позитивних елементів, отже, оптимальний розв'язок знайдено: Zmin = – 9; x = (1; 0; 2; 0; 1), Zmax = – Zmin = 9. 5. Методи складання початкового опорного плануБазисний план складається послідовно в декілька кроків (точніше, m + n – 1 кроків). На кожному з цих кроків заповнюється одна клітка, причому так, що, або повністю задовольняється один із замовників (той, в стовпці якого знаходиться заповнювана клітка), або повністю вивозиться весь запас вантажу з однієї з баз (з тої, в рядку якої знаходиться заповнювана клітка). У першому випадку можна виключити стовпець, що містить заповнену на цьому кроці клітку, і вважати, що завдання звелося до заповнення таблиці з числом стовпців, на одиницю меншим, ніж було перед цим кроком, але з тією ж кількістю рядків і з відповідно зміненим запасом вантажу на одній з баз (на тій базі, якою був задоволений замовник на даному кроці). У другому випадку виключається рядок, що містить заповнювану клітку, і вважається, що таблиця звузилася на один рядок при незмінній кількості стовпців і при відповідній зміні потребі замовника, в стовпці якого знаходиться заповнювана клітка. Починаючи з початку даної таблиці і повторивши (m + n – 2) раз описаний крок, прийдемо до «таблиці», що складається з одного рядка і одного стовпця (інакше кажучи, з однієї порожньої клітки). Іншими словами, приходимо до задачі з однією базою і з одним споживачем, причому потреби цього єдиного замовника дорівнюють запасу вантажу на цій єдиній базі. Заповнивши останню клітку, звільняємо останню базу і задовольняємо потребу останнього замовника. В результаті, зробивши (m + n – 1) кроків, отримаємо шуканий опорний план. Зауваження. Може трапитися, що вже на деякому (але не на останньому!) кроці потреба чергового замовника виявиться рівною запасу вантажу на черговій базі. Тоді після заповнення чергової клітки об'єм таблиці як би одночасно зменшується на одні стовпець і на один рядок. Але і при цьому слід вважати, що зменшення об'єму таблиці відбувається або на один стовпець, а на базі зберігається «залишок» рівний нулю, або на один рядок, а у замовника ще залишилася незадоволена «потреба» в кількості нуля одиниць вантажу, яка і задовольняється на одному з наступних кроків. Цей нуль («запас» або «потреба» – байдужі) треба записати в чергову заповнювану клітку на одному з подальших кроків. Оскільки при цьому виявляється рівною нулю одна з базисних невідомих, то маємо справу з виродженим випадком. 1. Діагональний метод, або метод північно-західного кута. При цьому методі на кожному кроці побудови першого опорного плану заповнюється ліва верхня клітка (північно-західний кут) частини таблиці, що залишилася. При такому методі заповнення таблиці починається з клітки невідомого x11 і закінчується в клітці невідомого xmn, тобто йде як би по діагоналі таблиці перевезень. Приклад
Заповнення таблиці починається з її північно-західного кута, тобто клітки з невідомим x11. Перша база A1 може повністю задовольнити потребу першого замовника B1 (a1 = 300, b1 = 170, a1 > b1). Вважаючи x11 = 170, вписуємо це значення в клітку x11 і виключаємо з розгляду перший стовпець. На базі A1 залишається змінений запас a11 = 130. У новій таблиці, що залишилася, з трьома рядками A1, A2, A3 і чотирма стовпцями B1, B2, B3, B4; північно-західним кутом буде клітка для невідомого x12. Перша база із запасом може повністю задовольнити потребу другого замовника B2 (a11 = 130, b2 = 110, a11 > b2). Вважаємо x12 = 110, вписуємо це значення в клітку x12 і виключаємо з розгляду другий стовпець. На базі A1 залишається новий залишок (запас) a111 = 20. У новій таблиці, що залишилася, з трьома рядками A1, A2, A3 i трьома стовпцями B3, B4, B5 північно-західним кутом буде клітка для невідомого x13. Тепер третій замовник B3 може прийняти запас з бази A1 (a111 = 20, b3 = 100, a111 < b3). Вважаємо x13 = 20, вписуємо це значення в клітку x13 і виключаємо з розгляду перший рядок. У замовника з В3 залишається ще незадоволеною потреба b13 = 80. Тепер переходимо до заповнення клітки для невідомого x23 і т.д. Через шість кроків у нас залишиться одна база A3 із запасом вантажу (залишком від попереднього кроку) a13 = 200 і один пункт B5 з потребою b5 = 200. Відповідно цьому є одна вільна клітка, яку і заповнюємо, поклавши x35 = 200. План складений. Базис утворений невідомими x11, x12, x13, x23, x24, x34, x35. Правильність складеного плану легко перевірити, підрахувавши суми чисел, що стоять в заповнених клітках по рядках і стовпцях. Загальний об'єм перевезень в тонно-кілометрах для цього плану складе S1 = 70*170 + 50*110 + 15*20 + 40*80 + 60*70 + 11*50 + 25*200 = 30650. 2. Метод найменшої вартості. При цьому методі на кожному кроці побудови опорного плану першою заповнюється та клітка, що залишилася i яка має найменший тариф. Якщо така клітка не єдина, то заповнюється будь-яка з них. Приклад
В даному випадку заповнення таблиці починається з клітки для невідомого x32, для якого ми маємо значення c32 = 10, найменше зі всіх значень cij. Ця клітка знаходиться на перетині третього рядка і другого стовпця, відповідним третій базі A3 і другому замовникові B2. Третя база A3 може повністю задовольнити потребу другого замовника B2 (a3 = 250, b2 = 110, a3 > b2). Вважаючи x32 = 110, вписуємо це значення в клітку x32 і виключаємо з розгляду другий стовпець. На базі A3 залишається змінений запас a13 = 140. У новій таблиці, що залишилася, з трьома рядками A1, A2, A3 і чотирма стовпцями B1, B3, B4, B5 кліткою з найменшим значенням cij клітка, де c34 = 11. Заповнюємо описаним вище способом цю клітку і аналогічно заповнюємо наступні клітки. В результаті виявляються заповненими (у приведеній послідовності) наступні клітки x32 = 110, x34 = 120, x13 = 100, x35 = 20, x15 = 180, x11 = 20, x21 = 150. На п'ятому кроці кліток з найменшими значеннями cij опинилося дві (c11 = c15 = 70). Ми заповнили клітку для x15, поклавши x15 = 180. Можна було вибрати для заповнення іншу клітку, поклавши x11 = 170, що приведе в результаті до іншого опорного плану. Загальний об'єм перевезень в тонно-кілометрах для цього плану складе S1 = 70*20 + 15*100 + 70*180 + 80*150 + 10*110 + 11*120 + 25*20 = 30420. Зауваження. У діагональному методі не враховуються величини тарифів, в методі ж найменшої вартості ці величини враховуються, і часто останній метод приводить до плану з меншими загальними витратами (що і має місце в нашому прикладі), хоча це і не обов'язково. Окрім розглянутих вище способів іноді використовується, так званий, метод Фогеля. Суть його полягає в наступному: У розподільній таблиці по рядках і стовпцях визначається різниця між двома найменшими тарифами. Наголошується найбільша різниця. Далі в рядку (стовпці) з найбільшою різницею заповнюється клітка з найменшим тарифом. Рядки (стовпці) з нульовим залишком вантажу надалі в розрахунок не приймаються. На кожному етапі завантажується тільки одна клітка. Розподіл вантажу проводиться, як і раніше. 6. Визначення характеристик систем масового обслуговуванняПростою одноканальною моделлю з імовірнісними вхідним потоком і процедурою обслуговування є модель, що характеризується показовим розподілом як тривалості інтервалів між надходженнями вимог, так і тривалості обслуговування. При цьому щільність розподілу тривалості інтервалів між надходженнями вимог має вигляд f1(x) = λ e-λt, (4.1) де λ – інтенсивність надходження заявок в систему Щільність розподілу тривалості обслуговування f2(x) = μ e-μt, (4.2) де μ – інтенсивність обслуговування Потоки заявок і обслуговуванні прості. Хай система працює з відмовами. Необхідно визначити абсолютну і відносну пропускну спроможність системи. Представимо дану систему масового обслуговування у вигляді графа (мал. 4.1), у якого є два стани: S0 – канал вільний (очікування); S1 – канал зайнятий (йде обслуговування заявки). Позначимо імовірність станів: P0(t) – імовірність стану «канал вільний»; P1(t) – імовірність стану «канал зайнятий». За розміченим графом станів (мал. 4.1) складемо систему диференціальних рівнянь Колмогорова для імовірності станів. Система лінійних диференціальних рівнянь (4.3) має розв'язок з урахуванням умови нормування P0(t) + P1(t) = 1. Розв'язок даної системи називається нестаціонарним, оскільки воно безпосередньо залежить від t і виглядає таким чином P1(t) = 1 – P0(t) = 1. (4.5) Неважко переконатися, що для одноканальної СМО з відмовами імовірність P0(t) є не що інше, як відносна пропускна спроможність системи q. Дійсно, P0(t) – імовірність того, що у момент t канал вільний і заявка, що прийшла до моменту t, буде обслужена, а отже, для даного моменту часу t середнє відношення числа обслужених заявок до тих, що поступили також дорівнює P0(t), тобто q = P0(t). (4.6) Після закінчення великого інтервалу часу (при t®¥) досягається стаціонарний (сталий) режим q = P0 = μ/(μ + λ). (4.7) Знаючи відносну пропускну спроможність, легко знайти абсолютну. Абсолютна пропускна спроможність (А) – середнє число заявок, яке може обслужити система масового обслуговування за одиницю часу А = λ*q = λμ/(λ + μ). (4.8) Імовірність відмови в обслуговуванні заявки дорівнюватиме імовірності стану «канал зайнятий» Pвідм = 1 – Р1 = 1 - μ/(μ + λ) = λ/(μ + λ). (4.9) Дана величина Pвідм може бути інтерпретована як середня частка необслужених заявок серед поданих. Приклад. Хай одноканальна СМО з відмовами є одним постом щоденного обслуговування (ЩО) для миття автомобілів. Заявка – автомобіль, що прибуває в момент, коли пост зайнятий – дістає відмову в обслуговуванні. Інтенсивність потоку автомобілів λ = 1,0 (автомобіль на годину). Середня тривалість обслуговування – tc = 1,8 години. Потік автомобілів і потік обслуговуванні є простими. Потрібно визначити в сталому режимі граничні значення: - відносної пропускної спроможності q; - абсолютної пропускної спроможності А; - імовірності відмови Pвідм. Порівняти фактичну пропускну спроможність СМО з номінальною, яка була б, якби кожен автомобіль обслуговувався точно 1,8 години і автомобілі слідували один за іншим без перерви. Розв'язок 1. Визначимо інтенсивність потоку обслуговування μ = 1/tc = 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/tc = 1/1,8 = 0,555 (автомобілів на годину). Виявляється, що Аном в 1,5 раза (0,555/0,356 ≈ 1,5) більше, ніж фактична пропускна спроможність, обчислена з урахуванням випадкового характеру потоку заявок і часу обслуговування. 7. Моделювання випадкових подій із заданим законом розподілуХай потрібно розіграти дискретну випадкову величину, тобто отримати послідовність її можливих значень xi (i = 1,2,3...n), знаючи закон розподілу X
Позначимо через R безперервну випадкову величину. Величина R розподілена рівномірно в інтервалі (0,1). Через rj (j = 1,2...) позначимо можливі значення випадкової величини R. Розіб'ємо інтервал 0 < R < 1 на осі 0r точками з координатами P1, P1 + P2, P1 + P2 + P3, P1 + … + Pn-1 на n часткових інтервалів D1, D2,…,Dn. Тоді отримаємо: Довжина D1 = P1 – 0 = P1, Довжина D2 = (P1 + P2) - P1 = P2, Довжина Dn = 1 – (P1 + P2 + … + Pn-1). Видно, що довжина часткового інтервалу з індексом i дорівнює імовірності Рi з тим же індексом, тобто Di = Pi. Таким чином, при попаданні випадкового числа ri в інтервал Di випадкова величина Х приймає значення xi з імовірністю Pi. Існує наступна теорема: Якщо кожному випадковому числу, яке потрапило в інтервал, поставити у відповідність можливе значення xi, то розігрувана величина матиме заданий закон розподілу. Алгоритм розігрування дискретної випадкової величини заданою законом розподілу
1. Потрібно розбити інтервал (0,1) осі 0r на n часткових інтервалів D1 – (0;P1), D2 – (P2;P1 + P2),…, Dn – (P1 + P2 + … + P n-1;1). 2. Вибрати (наприклад, з таблиці випадкових чисел, або в комп'ютері) випадкове число rj. Якщо число rj потрапило в інтервал, то розігрувана дискретна випадкова величина прийняла можливе значення xi. Приклад. Розіграти 8 значень дискретної випадкової величини Х, закон розподілу якої задано у вигляді таблиці
Розв'язок 1. Розіб'ємо інтервал (0,1) осі Оr точками з координатами 0,25; 0,25 + 0,16 = 0,41 на три часткові інтервали D1 = (0;0,25), D2 = (0,25;0,41), D3 = (0,41;1), 2. Випишемо з таблиці випадкових чисел 9 чисел, наприклад 0,10; 0,37; 0,08; 0,99; 0,12; 0,66; 0,31; 0,85. 3. Випадкове число r1 = 0,10 належить першому частковому інтервалу, тому розігрувана випадкова величина прийняла можливе значення x1 = 3. Випадкове число r2 = 0,37 належить другому частковому інтервалу, тому розігрувана величина прийняла можливе значення x2 = 11. Аналогічно набудемо інших можливих значень дискретної випадкової величини Х. Отже: розіграні можливі значення Х такі: 3; 11; 3; 24; 3; 24; 11; 24. Як бачимо, можна отримати множину значень випадкової величини Х із заданим законом розподілу. Хай потрібно розіграти безперервну випадкову величину Х, тобто отримати послідовність її можливих значень xi (i = 1,2...). При цьому функція розподілу F(X) відома. Існує наступна теорема: Якщо ri - випадкове число, то можливе значення xi розігруваної безперервної випадкової величини Х з відомою функцією розподілу F(X) відповідне ri, є коренем рівняння F(xi) = ri. Алгоритм розігрування безперервної випадкової величини: 1. Необхідно вибрати випадкове число ri. 2. Прирівняти вибране випадкове число відомої функції розподілу F(X) і отримати рівняння F(xi) = ri. 3. Розв'язати дане рівняння відносне xi. Набуте значення xi відповідатиме одночасно і випадковому числу ri і заданому закону розподілу F(X). Приклад. Розіграти 3 можливих значення безперервної випадкової величини Х, розподіленої рівномірно в інтервалі (2;10). Розв'язок Функція розподілу величини Х має наступний вигляд За умови а = 2, b = 10, отже Відповідно до алгоритму розігрування безперервної випадкової величини прирівняємо F(X) вибраному випадковому числу ri. Отримаємо звідси. Далі відповідно до алгоритму виберемо три випадкові числа, розподілених рівномірно в інтервалі (0;1). Наприклад r1 = 0,11; r2 = 0,17; r3 = 0,66. Підставимо ці числа в рівняння (5.3). Отримаємо відповідні можливі значення х х1 = 8*0,11 + 2 = 2,88; х2 = 8*0,17 + 2 = 3,36; х3 = 8*0,66 + 2 = 7,28. Приклад. Безперервна випадкова величина Х розподілена за показовим законом з відомою функцією F(x) = 1 – e-λx (x > 0, параметр λ > 0 відомий). Потрібно знайти формулу для розігрування можливих значень Х. Розв'язок Відповідно до алгоритму розігрування безперервної випадкової величини отримаємо рівняння 1 – e-λx = ri. Розв'яжемо це рівняння відносно xi. Отримаємо. Випадкове число ri знаходиться в інтервалі (0,1). Отже число (1 – ri) також випадкове і належить інтервалу (0,1). Тобто випадкові величини R і 1 – R розподілені однаково, рівномірно в одному і тому ж інтервалі (0,1). Тому для відшукання значення xi можна скористатися більш простою формулою. Відомо, що якщо випадкова величина R розподілена рівномірно в інтервалі (0,1), то її математичне очікування М(R)= 1/2, а дисперсія D(R)= 1/12. Складемо суму n незалежних випадкових величин Rj (j = 1,2,...,n), які розподілені рівномірно в інтервалі (0,1). Пронормуємо цю суму. Для цього знайдемо спочатку її математичне очікування і дисперсію. Відомо, що математичне очікування суми випадкових величин дорівнює сумі математичних очікувань доданків. Сума Ri містить n доданків. Математичне очікування кожного доданку рівна 1/2. Отже математичне очікування суми дорівнює. Аналогічно для дисперсії суми Rj отримаємо. Звідси середнє квадратичне відхилення суми Rj. Тепер пронормуємо суму Rj. Для цього віднімемо з суми Rj математичне очікування цієї суми і розділимо на середнє квадратичне відхилення суми Rj. Отримаємо (тобто ). На підставі центральної граничної теореми теорії імовірності при n®¥ розподіл цієї нормованої випадкової величини прагне до нормального закону з параметрами а = 0 і s = 1. При кінцевому n розподіл можна розглядати як приблизно нормальне. Наприклад, при n = 12 отримаємо достатньо точне для практики наближення. Таким чином, отримуємо, що для того, щоб розіграти можливе значення xi нормальної випадкової величини Х з параметрами а = 0 і s = 1, потрібно скласти 12 незалежних випадкових чисел і з отриманої суми відняти 6 тобто. Приклад. 1. Розіграти 100 можливих значень випадкової величини Х розподіленою нормально з параметрами а = 0 і s = 1. 2. Оцінити параметри розіграної випадкової величини Х. Розв'язок 1. Виберемо 12 випадкових чисел розподілених рівномірно в інтервалі (0,1) з таблиці випадкових чисел, або з комп'ютера. Складемо ці числа і з суми віднімемо 6, у результаті отримаємо х1 = (0,10 + 0,09 + … + 0,67) – 6 = – 0,99. Поступаючи аналогічним чином, знайдемо решту можливих значень х2, х3,…, х100. 2. Виконавши необхідні розрахунки, знайдемо вибіркову середню, яка є оцінкою і вибіркове середнє квадратичне відхилення, яке є оцінкою s*. Отримаємо. Як бачимо, оцінки задовільні, тобто a* близько до нуля, а s* близько до одиниці. Якщо потрібно розіграти значення нормальної ненормованої випадкової величини з математичним очікуванням a, відмінним від нуля і відмінним від одиниці, то спочатку розігрують можливі значення x нормованої випадкової величини, а потім знаходять шукане значення за формулою zi = s xi + a, яка отримана із співвідношення Таблиця 5.1. Формули для моделювання випадкових величин
8. Характеристика моделей управління запасамиНехай Т – протяжність періоду планування, Q – обсяг (партія) або розмір замовлення, y, h, Н (h £ y £ Н) – запас ресурсу відповідно поточний, нижній (мінімальний або пороговий) і верхній (максимальний або граничний). Для періодичних стратегій характерним є замовлення, які формуються окремо для кожного періоду Т. Серед таких стратегій виділимо наступні: стратегія постійного рівня, позначається (Т,Н), відповідно до якої через кожний проміжок часу Т запас поповнюється до граничного значення Н, обсяг замовлення вважається змінною величиною Q = Н – y; стратегія фіксованої поставки, позначається (Т,Q), відповідно до якої через інтервал часу Т видається замовлення розміром Q. У стратегіях з критичними рівнями постійно стежать за рівнем поточного запасу і тільки-но він опускається нижче порогового рівня, видається замовлення на поповнення запасу. Це такі стратегії: стратегія фіксованого розміру замовлення, позначається (h,Q), сутність якої полягає у наступному: - якщо y < h – замовити Q, - якщо y ³ h – нічого не замовляти; Стратегія двох рівнів, позначається (h,Н): - якщо y < h – замовити Q = H – y, - якщо y ³ h – нічого не замовляти. Зауважимо, що вибір стратегії керування запасами, який є найвідповідальнішим моментом під час складання математичних або імітаційних моделей, має грунтуватися на ретельному аналізі системи постачання. Отже, розв’язок задачі керування запасами потрібно знаходити спочатку в просторі стратегій керування, а потім, згідно з обраною стратегією – у просторі її параметрів. Для більш глибокого розуміння сутності задачі керування запасами і необхідності її розв’язання методом машинного моделювання розглянемо найбільш відому постановку задачі керування запасами, результати якої широко застосовуються на практиці – це статична детермінована однопродуктова модель. Модель формується за наступних передумов: 1. Розглядається процес керування однопродуктовим запасом на ізольованому складі; процес руху запасів – нескінченний. 2. Попит неперервний і має сталу інтенсивність l. 3. Поповнення запасів – миттєве. 4. Дефіцит не допускається, тобто витрати на штрафи Z1 (витрати через дефіцит) відсутні і вважаються такими, що дорівнюють нулю, Z1 = 0. 5. Кожній поставці відповідають сталі витрати Z2 = G. 6. Вартість зберігання Z3 пропорційна до середнього рівня запасу і часу його існування, коефіцієнт пропорційності дорівнює k. 7. Обирається стратегія керування запасами (Т,Н). 8. Треба знайти оптимальні параметри стратегії керування запасами Т* і Н*, які мінімізують загальні витрати за одиницю часу. Схему руху запасу матеріалу на складі зображено на мал. 6.2. Оскільки рух запасу циклічний, то для створення економіко-математичної моделі достатньо розглянути один цикл (трикутник на схемі). Загальні витрати за період Т ZТ = Z1 + Z2 + Z3. Витрати на зберігання згідно з шостою передумовою мають вигляд Z3 = kHT, оскільки середній рівень запасу дорівнює Н. Тоді дістанемо ZТ = G + kHT. Цільова функція – витрати за одиницю часу, тобто Z = . Крім того, згідно з другою передумовою Н = lТ. Отже, знаходимо цільову функцію, яку потрібно мінімізувати: Z = ®min. Оскільки цільова функція є опуклою і унімодальною, то її мінімум знаходиться стандартним методом (перша похідна дорівнюється до нуля). Звідси Т* = . Неважко знайти оптимальне значення граничного запасу Н* = lТ* = . Оскільки в даних умовах граничний запас дорівнює партії поставки, то Q* = . Останню формулу дістав Уїлсон (1928 р.), тому її названо на його честь. Іноді цю формулу називають формулою для визначення найбільш економічної партії поставок. Незважаючи на досить жорсткі та ідеальні умови її створення, формула Уїлсона (або її модифікації) часто застосовується на практиці. Загальні оптимальні витрати обчислюються за формулою Z* = = . D – величина попиту за період планування, D = lT, N = D/Q*, (оптимальний час між замовленням) t* = Q/l = T/N. Приклад. Добовий попит деякого товару (l) складає 100 од. Витрати на розміщення кожного запасу (G) постійні і дорівнюють 100 уо. Добові витрати на збереження одиниці запасу (k) складають 0,02 уо. Визначити економічний розмір партії і точку замовлення при терміну виконання замовлення 12 діб. Розв’язок З формули Уїлсона маємо Q* = = 1000 од. Оптимальна протяжність циклу складає Т* = Q*/l = 1000/100 = 10 діб. Оскільки за умови термін виконання замовлення складає 12 діб, а протяжність циклу складає 10 діб, то відновлення замовлення відбувається тоді, коли рівень запасу достатній для задоволення попиту на 12 – 10 = 2 доби. Таким чином, замовлення розміром Q* = 1000 од розміщується, коли рівень запасу досягає 2*100=200 од. Можна вважати, що ефективний термін виконання замовлення: дорівнює L – Т* при L > Т*, при цьому величина (L – Т*) менше Т* і дорівнює L в противному випадку (тут L – заданий термін виконання замовлення). Для розглянутого прикладу визначити точку замовлення в наступних випадках: а) термін виконання замовлення L=15 діб. (Відповідь 500 од.) б) L=23 доби. (Ответ. 300 од.) в) L=8 діб. (Ответ. 800 од.) г) L=10 діб. (Ответ. 0 од.) З повагою ІЦ “KURSOVIKS”! |