Головна

Теоретичні основи

  1.  I. Основи молекулярно-кінетичної теорії
  2.  V. ЗАБУТІ ОСНОВИ
  3.  А. Основи християнського життя
  4.  Адміністративно-правові основи діяльності виконавчої влади в галузі культури.
  5.  Адміністративно-правові основи діяльності виконавчої влади по керівництву охороною здоров'я.
  6.  Адміністративно-правові основи діяльності виконавчої влади по керівництву наукою.
  7.  Адміністративно-правові основи організації митної справи.

У завданнях оптимізації, коли необхідно враховувати деякий випадковий фактор (елемент або явище), який неможливо описати аналітично, використовують метод моделювання, званий методом статистичних випробувань або методом Монте-Карло [4,5]. За допомогою цього методу може бути вирішена будь-яка імовірнісна задача. Однак використовувати його доцільно в тому випадку, якщо вирішити задачу цим методом простіше, ніж будь-яким іншим.

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

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

У теорії ймовірностей ця задачу називають задачею про «зламаною тростини». Це завдання можна вирішити методами теорії ймовірності.

Позначимо через x і y відстані від лівого кінця тростини першої та другої точок перелому (Рис.1).

Рис.1. Умовні позначення для завдання про «зламаною тростини»

Тоді довжини сторін можливого трикутника виражаються через L, x і y такий спосіб

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

Після підстановки довжин сторін трикутника через L, x і y отримаємо

Рішення отриманої системи нерівностей можна наочно ілюструвати на двухкоординатной площині. (Рис.2). Т. к. Величини x і y мають рівномірний розподіл на відрізку [0; L], то безлічі точок зі всілякими координатами (x; y) відповідає квадрат OPRS зі стороною L. Тоді точки, координати яких задовольняють складеної системі нерівностей з урахуванням умови  , Належать області, обмеженою трикутником ABC. Якщо провести аналогічні міркування для випадку  , То отримаємо трикутник CDE.

Мал. 2. Графічна ілюстрація рішення задачі Прикладу 1.

Шукана ймовірність дорівнює частці сумарною площі трикутників від площі квадрата OPRS

Вирішимо цю задачу методом статистичних випробувань. Для цього в додатку MS Excel створимо таблицю, як показано на Рис. 3.

Рис.3. Структура таблиці для вирішення завдання Прикладу 1 методом статистичних випробувань.

На Ріс.4a-b показаний введення формул в осередки листа для вирішення завдання Прикладу 1 методом статистичних випробувань.

Ріс.4a. Введення формул для реалізації випадкового перелому тростини і перевірки можливості формування трикутника.

м

Ріс.4b. Введення формул для обробки серії випробувань.

Моделювання координат точок перелому x і y здійснюється за формулами «= Довжина * СЛЧИС ()» (див. Формули в осередках B2 і C2). Вбудована функція СЛЧИС () генерує випадкову величину, рівномірно розподілену на відрізку [0; 1]. Вибір в якості сторони a мінімального значення  і розрахунок сторін b и c за формулами

дозволяє врахувати обидва випадки, коли и  (Див. Формули в осередках D2, E2 і F2).

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

Формули в осередках H2, I2, J2 і K2 забезпечують підрахунок загального числа випробувань, числа сприятливих результатів і їх частку в загальній кількості випробувань.

При кожному натисканні функціональної клавіші F9 Excel перераховує функції СЛЧИС () і, таким чином, моделює нову серію випробувань. У кожній серії виходить нове значення ймовірності (на Рис. 3 вона дорівнює 0,26). В якості оцінки ймовірності беруть середнє арифметичне від декількох серій. Усереднення десяти вибіркових значень представлено в таблиці:

Отримане середнє значення 0,247 близько до значення, розрахованого теоретично 0,250. На практиці такий точності цілком достатньо.

Таким чином, алгоритм методу статистичних випробувань зводиться до наступного.

- Визначити, що собою являтиме випробування або розіграш.

- Визначити, яке випробування є успішним, а якесь немає.

- Провести велику кількість випробувань.

- Обробити отримані результати статистичними методами і розрахувати статистичні оцінки шуканих величин.

При проведенні статистичних випробувань необхідно відтворювати випадкові величини з потрібним законом розподілу. Додаток MS Excel має для цього достатню кількість коштів. Найпростішими є функція СЛЧИС () і СЛУЧМЕЖДу (a, b). Перша функція генерує випадкове число з рівномірним законом розподілу на полуінтервале [0; 1) (Рис. 5), друга - випадкове число з рівномірним законом розподілу на інтервалі (a; b) (Рис. 6).

Рис.5. Конструктор функції СЛЧИС ().

Рис.6. Конструктор функції СЛУЧМЕЖДу (a; b).

Крім того, MS Excel має у своєму розпорядженні надбудовою «Пакет аналізу», яка містить генератор випадкових величин з різними функціями розподілу (Рис.7).

Рис.7. Діалогове вікно генератора випадкових чисел.

Перераховані кошти надають практично необмежені можливості по моделюванню випадкових величин.

моделювання події. Нехай необхідно змоделювати поява деякої події А, ймовірність настання якого дорівнює р (А) = Р. Це можна змоделювати суперпозицией функцій:

= Якщо (СЛЧИС () <= P; "відбулася подія А"; "подія А не відбулося")

Мал. 8. Імовірність настання події А

Моделювання групи несумісних подій. Нехай є група несумісних подій А1, А2, ..,. аk. Відомі ймовірності настання подій р (А1), р (А2), ..., р (Аk). Тоді через несумісність випробувань  . На відрізку [0, 1] відкладемо ці ймовірності (Рис. 9).

Мал. 9. Вірогідність настання групи несумісних подій

Якщо число, сгенерированное функцією СЛЧИС () потрапило в i-й інтервал, то відбулася подія Аi.

Моделювання умовного події. Моделювання умовного події B, яке відбувається за умови, що настав подія A з ймовірністю р (B / A), показано на рис. 10. Спочатку моделюємо подія A. Якщо подія A відбувається, то моделюємо настання події B, якщо маємо  , То чи не моделюємо наступ події B.

Мал. 10. Моделювання умовного події B

Розглянемо приклад на моделювання умовних подій.

Приклад 2. У складальний цех надійшли деталі з трьох підприємств. На першому підприємстві виготовлено 51% деталей від їх загальної кількості, на другому підприємстві 24% і на третьому 25%. При цьому на першому підприємстві було виготовлено 90% деталей першого сорту, на другому 80% і на третьому 70%. a) Яка ймовірність того, що взята навмання деталь виявиться першого сорту? b) Яка умовна ймовірність того, що якщо взята навмання деталь виявилася бракованою, вона була виготовлена ??на першому підприємстві?

Рішення:Спочатку вирішимо завдання за формулами, використовуючи відповідні формули теорії ймовірностей.

a) Нехай A - Подія, що складається в тому, що взята деталь виявиться першого сорту, а H1, H2 і H3 - гіпотези, що вона виготовлена ??відповідно на 1, 2 і 3 підприємстві. Ймовірності цих гіпотез відповідно рівні:

Далі, з умови задачі випливає, що:

Використовуючи формулу повної ймовірності, отримаємо шукану ймовірність

b) Виріб вибирається навмання з усієї виробленої продукції і виявляється бракованим. Розглянемо три гіпотези: Hi - Деталь виготовлена ??на i-му підприємстві i = 1,2,3. Ймовірності цих подій дані:

Нехай виріб виявилося бракованим. Умовні ймовірності цього по окремих підприємствах:

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

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

Вихідні дані раціонально організувати, як показано на Рис.11. Таблиці ймовірностей доповнені трьома стовпцями «Перегляд», «Результат» і «Номер події». Це необхідно для реалізації моделювання групи несумісних подій і моделювання умовних подій. На Рис.12 даний фрагмент листа представлений в режимі показу формул. У стовпці «Перегляд» сформована сума ймовірностей наростаючим підсумком. Тим самим формуються межі подій згідно з ідеєю, представленої на Рис.9. Моделювання настання одного з несумісних подій реалізується за наступною схемою:

- Моделювання за допомогою функції СЛЧИС () випадкової величини з рівномірним законом розподілу на полуінтервале [0; 1);

- Пошук отриманого значення за допомогою функції перегляду () в стовпці «Перегляд» і витяг з таблиці назви події з шпальти «Результат» або його умовного номера колонки «Номер події».

Мал. 11. Організація таблиць вихідних даних

Мал. 12. Введення формул в вихідні таблиці даних

На Рис. 13-14a) -c) показані, відповідно, загальний вигляд таблиці статистичного моделювання і введені формули. Вибір значень умовних ймовірностей шлюбу і деталей першого сорту з таблиць здійснюється за допомогою суперпозиції функцій перегляду () і зміщений (). Перша здійснює безпосередньо вибір з таблиці, а звернення до потрібної таблиці в залежності від номера змодельованого підприємства відбувається за допомогою функції зміщений (). Для цього таблиці умовних ймовірностей повинні розташовуватися з однаковим кроком (в даному випадку з кроком 5).

Мал. 13. Загальний вигляд таблиці статистичних випробувань

a)

b)

c)

Мал. 14. Введення формул в таблицю статистичних випробувань

Усереднення результатів проведеного моделювання відповідно до пунктів завдання Прикладу 2 приведено в таблицях:

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

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

Алгоритм рішення зводиться до наступного:

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

- Вибір з сформованого безлічі підмножини точок, координати яких задовольняють системі обмежень;

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

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

На Рис. 15 показана отримана за цим алгоритмом область обмеження на змінні X і Y при вирішенні наступної нелінійної оптимізаційної задачі:

Оптимальне рішення досягається в точці з координатами: X = 5,53; Y = 7,54, в якій цільова функція приймає значення Zmax= 54,28. Точне рішення, отримане за допомогою засобу «Пошук рішення»: X = 5,54; Y = 7,57, Zmax= 54,49. Ілюстрація точного рішення показана на Рис.16. Як бачимо, похибка задовольняє практичним вимогам.

Мал. 15. Область обмежень, побудована методом статистичних випробувань.

Мал. 16. Графічна ілюстрація точного рішення задачі нелінійної оптимізації.

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


 Оптимальна суміш стратегій. |  Завдання для самостійного рішення |  Теоретичні основи |  Завдання для самостійного рішення |  Лабораторна робота №5 |  Завдання для самостійного рішення |  Вибір оптимального маршруту методом динамічного програмування |  Вибір оптимального маршруту за алгоритмом Дейкстри |  Знаходження оптимальних маршрутів. |  Визначення оптимального обсягу замовлення |

© 2016-2022  um.co.ua - учбові матеріали та реферати