• Тема 12. Методи експертних оцінок
  • ДОДАТКОВА ТЕМАТИКА
  • Тема Б. Нелінійне програмування
  • Тема 8.
  • Тема 10. Методи теорії масового обслуговування


  • Дата конвертації26.04.2017
    Розмір84.7 Kb.
    Типконтрольна робота

    Математичні методи економічних досліджень

    фференціруемой. Тоді значення q знаходиться з рівняння:

    або,

    звідки

    ,

    де q * - оптимальний розмір партії, званий також оптимальним замовленням.


    Модель виробничих поставок

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

    Вважаємо, що замовлення надходять безперервно.

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

    За кожен цикл зміни запасів на склад надходить q одиниць товару. Це кількість йде з виробничої лінії, яка працює зі швидкістю p. Попит протягом року постійний і його інтенсивність d. Як тільки рівень запасів стане нульовим, з лінії почне надходити таку кількість товарів. Величина q - розмір партії, тобто кількість товару в одній поставці. Описана картина представлена ​​в наступній діаграмі:

    Ефективна швидкість поповнення запасів протягом часу поставки дорівнює p - d.

    Рівняння витрат:

    С = С1 + С2 + С3.

    Для С1 маємо наступне. Попит дорівнює d товарів в рік. Отже, якщо одна поставка містить q - товарів, то за рік потрібно зробити поставок, а саме:

    .

    Для С2 маємо:

    С2 = сd.

    Для С3 (витрати на зберігання запасів) маємо:

    С3 = (середній рівень запасів) h.

    Середній рівень запасів знаходиться наступним чином:

    1. Максимальний рівень RT = (p - d) t, де t _ тривалість поставки.

    2. pt = q (кількість товарів в одній поставці).

    Звідси:

    (Середній рівень запасів) = (максимальний рівень запасів) =.

    отже:

    .

    Оптимальний розмір партії знаходиться з рівняння:

    .

    Звідси

    .


    Модель, що враховує штрафи

    Розглянемо третю модель, яка включає штрафи.

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

    Нехай за контрактом підприємство має поставити q одиниць товару протягом кожного проміжку часу тривалістю L, за одиницю часу поставляється d одиниць товару (q = Ld). Значення q і L постійні. Нехай далі на початку кожного періоду L підприємство робить запас одиниць товару y
    За несвоєчасну поставку на підприємство накладається штраф, величина якого залежить від того, на скільки була затримана поставка. (Іноді вигідніше заплатити штраф, ніж витрачати кошти на зберігання запасів, що перевищують величину у).

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

    Розглянемо витрати одного циклу. Загальні витрати в моделі нехай будуть:

    h - витрати зберігання одиниці товару за одиницю часу;

    p - витрати на штраф в розрахунку на одиницю товару за один день відстрочки.

    Графік зміни запасів буде:

    Знаходимо витрати одного циклу.

    Для С1 маємо наступне. Товари знаходяться на складі протягом періоду АВ, середній рівень запасів за цей період дорівнює у / 2. Тривалість періоду АВ дорівнює у / d. Звідси:

    .

    Для С2. Штраф виплачується за невиконання поставок протягом періоду. Загальна кількість "товаро-днів", за які накладається штраф, дорівнює площі BCD. але

    S BCD =.

    Звідси:

    .

    Cледовательно:

    .

    Оптимальне значення у знаходимо з умови:

    ,

    звідси:

    ,.

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

    Тема 12. Методи експертних оцінок

    1. Основні поняття методів експертних оцінок.

    2. Поняття множини неулучшаемих альтернатив.

    3. Основні підходи до пошуку бажаних експертних оцінок.

    4. Основні етапи підготовки і проведення експертних оцінок.


    Короткий зміст теми

    Як показує досвід практичної економічної діяльності, особливо в тій її частині, яка пов'язана з управлінням в області економіки, де істотну роль грає такий аспект дій як прийняття рішень, одного арсеналу формально вирішуваних завдань в більшості випадків буває недостатньо. У таких випадках доводиться звертатися до компетентних фахівців, в інтуїції яких зосереджений ірраціональний досвід господарювання і управління та раціонального пізнання економіки у вигляді формалізованих моделей. Такі фахівці, які в "досконало" володіють певною проблемою, називаються експертами. Результатом їхньої праці є різного роду оцінки, рекомендації та пропозиції. При залученні значної кількості експертів до вироблення варіантів рішень постає завдання обробки результатів роботи експертів. Тут знову постає проблема використання формалізованих методів - методів експертних оцінок.

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

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

    Технологія проведення експертних оцінок включає в себе три складові:

    інтуїтивно-логічний аналіз;

    формування і видача характеристик (власне оцінка, результат рішення);

    обробка результатів експертизи _ різних альтернатив.

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

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

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

    З подоланням альтернатив пов'язані два фундаментальних поняття:

    безліч різних варіантів рішень (альтернатив), позначимо його {X};

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

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

    , (12.1)

    де {X *} - вибрані альтернативи.

    Залежно від ступеня формалізації введених понять розрізняють наступні типи завдань:

    1. Завдання оптимального вибору - якщо безліч {X} однозначно визначено, а принцип вибору Ф формалізований (тобто може бути описаний, переданий і результати його застосування до елементів з {X} не залежить від суб'єктивних умов).

    2. Завдання вибору (просто) - якщо безліч {X} однозначно визначено, але принцип вибору Ф не може бути формалізований або просто фіксований. Вибір залежить від того, хто і на основі якої інформації його робить.

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

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

    Які ж ці природні обмеження?

    По-перше, в реальній задачі, як правило, завжди існує так зване початкове безліч альтернатив {X (0)}, на основі якого приступають до прийняття рішення. Надалі це безліч змінюється, але можна вважати, що на будь-який момент процесу експертизи ми маємо справу з фіксованим безліччю {X (i)}:

    .

    По-друге, мається на увазі, що альтернатива X? з безлічі всіх мислимих альтернатив {X (M)} може бути оцінена з точки зору корисності включення її в безліч {X}. Це робиться за допомогою деякого допоміжного принципу вибору Ф (M). Найчастіше цей принцип неформалізовані. Таким чином, і саме безліч {X}, взагалі кажучи, є підсумком експертної оцінки, яку можна представити у вигляді:

    . (12.2)

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

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

    Практичні шляхи вирішення в повному обсязі певних завдань 3 і 2 складаються у використанні для цієї мети ряду завдань з фіксованим, але мінливим від завдання до завдання безліччю {X} і фіксованим (хоча необов'язково формалізованим) принципом вибору Ф. Це відбувається із застосуванням ряду прийомів. Перший з них - організація ітераційного процесу вирішення набору завдань виду 1. Вона складається в початковому рішенні однієї або декількох формалізованих завдань, аналізі результатів їх вирішення, призначення змінених множин альтернатив {X} і змінених принципів вибору Ф, нового рішення набору завдань і т.д . до отримання задовільного результату. Інший прийом полягає в рішенні ослабленого варіанта завдання 1, коли принцип вибору формалізований в повному обсязі, а допускає участь експертів, кожен з яких по-своєму, звичайно неформальним чином, фіксує принцип Ф. У цьому випадку кожен з експертів породжує свою задачу типу 1, а рішення вихідної завдання формується на основі їх рішень. Наступною прийом близький до першого. Тут завданням типів 3 або 2 зіставляється деякий аналог, обраний серед завдань типу 1, а отримане рішення є основою для неформального пошуку рішення необхідної задачі.

    Таким чином, завдання типу 1 є ядром в процесі вирішення інших типів завдань.

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

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

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

    Порівняння альтернатив за окремими частинами (властивостями) може бути виконано наступним чином:

    1) на основі парного (рідше групового) порівняння альтернатив по даній властивості;

    2) на основі введення природних числових характеристик виділеного властивості;

    3) на основі введення штучних числових характеристик виділеного властивості.

    Розглянемо ці способи порівнянь.

    Парне порівняння. Нехай для двох альтернатив X 1 і X 2 з безлічі {X} можна зробити вибір найбільш кращою по даній властивості. Спосіб вибору в загальному випадку не конкретизується. Якщо він пов'язаний з використанням числових характеристик, то така ситуація відноситься до способу (2) або (3). Виникає питання: «Чи існує об'єктивний спосіб вибору, не пов'язаний з числами?» З практичної точки зору можемо вважати цілком об'єктивними і не заснованими на числові характеристики такі твердження: "Цей варіант розміщення пунктів споживання більш кращий для розгортання широкої торгівлі", "Ця людина більш вдало впорається з поставленим завданням "і т.п.

    З формальної точки зору для альтернатив X 1 і X 2 з {X} вводиться бінарна операція порівняння за ознакою (властивості) R. Запис цієї події можна представити у вигляді:

    X 1 RX 2, (12.3)

    що означає: альтернатива X 1 краще (або "не гірше") альтернативи X 2 за ознакою R. Зазначена операція може бути застосована як до будь-якої парі (X 1, X 2) з {X} {X}, так і не до всіх з них. В останньому випадку допускається, що щодо деяких пар не можна зробити вибір, як то кажуть, елементи множини {X} тільки частково можна порівняти за ознакою R.

    Для операції R природною є аксіома транзитивності, яка полягає в тому, що з X 1 RX 2 і X 2 RX 3 слід X 1 RX 3.

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

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

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

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

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

    Додатковим прийомом, який в ряді випадків полегшує всі наведені вище способи порівняння, є розподіл елементів по підмножини. Тоді будь-яка альтернатива X з {X} в цілому або по своїй властивості R відноситься до одного з фіксованих підмножин {X 1}, {X 2},.... Такий розподіл називається завданням класифікації і може як зводитися до перерахованих способів порівняння, так і бути самостійною задачею. Окремим випадком класифікації є поділ властивостей альтернатив за ступенем важливості в цьому завданню. Сенс цього прийому полягає в звуженні числа властивостей, що беруться до уваги в першу чергу.

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

    Безліч неулучшаемих альтернатив отримало назву безлічі Парето.

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

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

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

    Вище розглянуті основні методи експертних оцінок, які можуть застосовуватися в ході проведення експертиз та обробки їх результатів. Але, як організовується експертиза? Форми організації експертизи можуть бути досить різноманітними і численними в залежності від умов проведення експертизи і контингенту залучених експертів. Класичні форми роботи з експертами - це заповнення анкет (таблиць), інтерв'ю, запит аналітичного звіту.

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

    Слід мати на увазі, що людина більш обгрунтовано призводить якісні відповіді, ніж кількісні.

    Експертизи розрізняються і за формою взаємодії експертів. Обмін думками може бути вільним, регламентованим і неприпустимим. Всі ці способи мають свої переваги і недоліки.

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

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

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

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

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

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

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

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

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

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

    Метод Дельфи дає можливість поліпшити просте усереднення оцінок експертів.

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

    постановку задачі (проблеми), що підлягає експертизі;

    підбір і вибір експертів;

    виконання експертизи;

    отримання узагальненої експертної оцінки;

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

    Для прикладу уявімо назва деяких завдань і проблем, у вирішенні яких застосовуються методи експертних оцінок.

    це:

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

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

    встановлення питомих ресурсних витрат на виконання будь-яких робіт, норм витрат матеріалів, нормативної трудомісткості виготовлення виробу і його складових, вартості окремих етапів науково-дослідних і дослідно-конструкторських робіт;

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

    встановлення параметрів календарно-планових нормативів, розмірів партій запуску-випуску виробів (деталей), величини заділів;

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

    багатокритеріальна оцінка діяльності підприємства;

    визначення послідовності виконання робіт;

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

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

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

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

    ДОДАТКОВА ТЕМАТИКА

    Тема А. Елементи теорії ймовірності

    1. Поняття ймовірності. Загальні властивості ймовірності.

    2. Основні формули теорії ймовірності.

    3. Поняття випадкової величини. Дискретна і безперервна випадкова величина.

    4. Поняття розподілу випадкової величини. Основні закони розподілу.


    Короткий зміст теми

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

    Тема Б. Нелінійне програмування

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

    2. Метод множників Лагранжа.

    3. Опукле програмування.

    4. Градієнтні методи.

    5. Метод штрафних функцій.


    Короткий зміст теми

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

    f (x 1, x 2,..., x n) (Б.1)

    за умови, що змінні задовольняють співвідношенням:

    , (Б.2)

    де, f і g i деякі відомі функції, b i - задані числа.

    Вирішення цього завдання X * = (x 1 *, x 2 *, ..., x n *), яке задовольняє (Б.1) і (Б.2), таке, що для будь-якого іншого X = (x 1, x 2,..., x n), що задовольняє (Б.2), маємо:

    f (x 1 *, x 2 *, ..., x n *) f (x 1, x 2,..., x n) - для завдання максимізації;

    f (x 1 *, x 2 *, ..., x n *) f (x 1, x 2,..., x n) - для завдання мінімізації.

    Співвідношення (Б.2) називаються системою обмежень. Умови невід'ємності змінних можуть бути задані безпосередньо. В евклідовому просторі E n (Б.2) визначає область допустимих рішень поставленого завдання (на відміну від завдань лінійного програмування ця область може бути не опуклою).

    Якщо область допустимих рішень визначена, то знаходження рішення задачі (Б.1) - (Б.2) зводиться до визначення такої точки цієї області, через яку проходить гіперповерхность найвищого (найнижчого) рівня: f (x 1, x 2,... , x n) = h.

    Ця точка може бути як на кордоні, так і всередині області.

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

    визначення області допустимих рішень, відповідних (Б.2) (якщо вона порожня, то рішень завдання - немає);

    побудова гіперповерхні f (x 1, x 2,..., x n) = h;

    визначення гіперповерхні найвищого (найнижчого) рівня або встановлення нерозв'язності завдання через необмеженість (Б.1) зверху (знизу) на безлічі допустимих рішень;

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


    Метод множників Лагранжа

    Загальна постановка задачі полягає в знаходженні максимуму (мінімуму) функції: f (x 1, x 2,..., x n) за умови: g (x 1, x 2,..., x n) = b i, i = 1, 2, ..., m.

    Умови невід'ємності x j можуть бути відсутні. Маємо завдання на умовний екстремум - класична задача оптимізації.

    Завдання виконується в такий спосіб. Вводять набір змінних i (i = 1, 2, ..., m) - множників Лагранжа і складають функцію:

    .

    Далі визначають приватні похідні:

    (J = 1, 2, ..., n) і, (i = 1, 2, ..., m).

    На наступному кроці розглядають систему n + m рівнянь:

    Будь-яке рішення цієї системи визначає точку, в якій може мати місце екстремум функції f (x 1, x 2,..., x n). Таким чином, дозволивши побудовану систему, визначають всі крапки, в яких функція f може мати екстремум. Подальше дослідження йде як в разі безумовного екстремуму.

    Отже, етапи рішення задачі нелінійного програмування методом множників Лагранжа полягають в наступному:

    Складають функцію Лагранжа.

    Знаходять приватні похідні функції Лагранжа по x j і i і прирівнюють їх 0.

    Вирішуючи отриману систему, знаходять точки, в яких цільова функція завдання може мати екстремум.

    Серед точок, підозрілих на екстремум, знаходять точки, в яких досягається екстремум, обчислюють значення f (x 1, x 2,..., x n) в цих точках і серед них вибирають ті, які задовольняють умовам задачі.


    опукле програмування

    Суть загальної постановки завдання полягає у визначенні максимального (мінімального) значення функції:

    f (x 1, x 2,..., x n)

    за умов:

    g i (x 1, x 2,..., x n) b i (i = 1, 2, ..., m), x j 0 (j = 1, 2, ..., n).

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

    Кілька визначень.

    Функція f (x 1, x 2,..., x n) на опуклому безлічі X називається опуклою, якщо для будь-яких двох точок X 2 і X 1 з X і будь-якого 0 1, виконано співвідношення:

    f [X 2 + (1 -) X 1] f (X 2) + (1 -) f (X 1).

    Безліч допустимих рішень задовольняє умові регулярності, якщо існує хоча б одна точка X i цій галузі така, що g k (X i) k (k = 1, 2, ..., m).

    Завдання опуклого програмування виникає, якщо функція f є увігнутою (випуклою), а g i - опуклі.

    Будь-який локальний максимум (мінімум) є глобальною максимумом (мінімумом). Найбільш характерним методом вирішення завдань опуклого програмування є метод множників Лагранжа. При цьому точка (X 0, 0) називається сідловою функції Лагранжа, якщо:

    F (x 1, x 2,..., x n,) F ()

    F (), для всіх x j 0 і i 0.

    Для завдання опуклого програмування, безліч допустимих рішень якої має властивість регулярності, точка X 0 = () є оптимальним рішенням тоді, коли існує такий вектор 0 = (), що точка (X 0, 0) є сідловою функції Лагранжа, побудованої для вихідної завдання.

    Для завдання визначення максимуму, умовами сідлової точки будуть:

    (Приватні похідні беруться в седловой точці).

    Для завдання знаходження мінімуму сідлова точка визначається співвідношеннями:

    F () F ()
    F ().

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

    ,

    .


    градієнтні методи

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

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

    Перша група, коли досліджувані точки не виходять за межі області допустимих рішень (тут використовується метод Франка-Вулфа).

    Друга група, коли ці точки не обов'язково входять тільки в область допустимих рішень, однак в ітераційне процесі такі точки будуть. (Тут використовується метод штрафних функцій і метод Ерроу-Гурвіца).

    Знаходження рішення йде ітераційним процесом до тих пір, поки градієнт функції f (x 1, x 2,..., x n) в черговий точці X (k + 1) не стане рівним 0, або поки | f (X (k + 1)) - f (X (k)) | <, де досить мале позитивне число. Цю величину часто називають точністю отриманого рішення.

    Метод Франка-Вулфа

    Знайти максимум увігнутої функції: f (x 1, x 2,..., x n), за умови:

    .

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

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

    f (X (k)) =

    і будують лінійну функцію:

    F =.

    Знаходять максимум функції F при сформульованих обмеженнях. Нехай рішення цього завдання Z (k). Тоді за нове допустиме рішення приймають:

    X (k + 1) = X (k) + k (Z (k) - X (k)),

    де k _ деяке число, зване кроком обчислень (0 k 1).Число k - довільне і вибирають його так, щоб значення функції в точці X (k + 1), залежне від k, було максимальним. Для цього треба знайти рішення рівняння і вибрати його найменший корінь. Якщо коріння рівняння більше 1, то береться k = 1. Потім визначають X (k + 1) і f (X (k + 1)) і з'ясовують необхідність переходу до точки X (k + 2). Якщо така необхідність є, то в точці X (k + 1) обчислюють градієнт цільової функції і переходять до відповідної задачі лінійного програмування і вирішують її. Визначають координати точки X (k + 2) і необхідність подальших обчислень. Після кінцевого числа кроків отримують з необхідною точністю рішення вихідної задачі.

    Отже, етапи рішення задачі методом Франка-Вулфа полягають в наступному:

    1. Визначають одне з допустимих рішень.

    2. Знаходять градієнт функції f в точці допустимого рішення.

    3. Будують функцію F і знаходять її максимальне значення за умов початкового завдання.

    4. Визначають крок обчислень.

    5. За формулою X (k + 1) = X (k) + k (Z (k) - X (k)) знаходять наступне допустиме рішення.

    Перевіряють необхідність переходу до наступного допустимому рішенням. У разі необхідності переходять до етапу 2, якщо такої необхідності немає, то прийнятне рішення знайдено.


    Метод штрафних функцій

    Нехай маємо увігнуту функцію f (x 1, x 2,..., x n). Необхідно знайти максимум цієї функції за умов: g i (x 1, x 2,..., x n) b i, (i = 1, 2, ..., m), x j 0, де g i - опуклі функції.

    Будується функція: F (x 1, x 2,..., x n) = f (x 1, x 2,..., x n) + H (x 1, x 2,..., x n), де функція H (x 1, x 2,..., x n) визначається системою обмежень і називається штрафний функцією. Вона може бути побудована багатьма способами. Найчастіше ця функція будується в вигляді:

    , де

    a i _ вагові коефіцієнти,

    q i = b i - g i.

    Використовуючи H, послідовно переходять від однієї точки в іншу до тих пір, поки вийде прийнятне рішення. При цьому координати наступної точки знаходять за формулою:

    (Б.3)

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

    Отже, процес вирішення включає етапи:

    Визначають вихідне допустиме рішення.

    Вибирають крок обчислень.

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

    По (Б.3) визначають координати точки - можливе нове рішення.

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

    Встановлюються значення вагових коефіцієнтів і переходять до етапу 4.

    ющее подія - це кінцевий результат всього комплексу робіт. Наприклад: 9.

    Є ще кілька типів подій.

    Початкова подія - подія, безпосередньо передує кожній роботі.

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

    Наприклад: на попередньому графіку для роботи 2 - 3 подія 2 - початкова, 3 - кінцеве.

    Граничними подіями називаються події, здатні фіксувати закінчення робіт будь-якого виконавця (організації). Наприклад: факт передачі вихідних даних, випуск креслень і т.п.

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

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

    Мережеві графіки володіють важливою властивістю - наочністю.

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

    Графічне представлення мережевої моделі значно спрощує її складання, розрахунок, аналіз і вивчення.

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

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

    кількості виконавців;

    трудомісткості;

    вартості і т.п.

    Одним з найважливіших понять мережевих методів є поняття критичного шляху. Його визначають при розрахунку мережевого графіка (мережевий моделі).

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

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

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

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

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

    Крім виявлення критичного шляху, розрахунок мережевого графіка дозволяє отримати цілий ряд інших показників:

    ранні і пізні терміни початку і закінчення робіт;

    резерв часу;

    ймовірність настання подій і т.д.

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

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

    Таким чином, мережеві методи зводяться до використання для цілей управління:

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

    мережевого графіка як наочного відображення мережевої моделі;

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

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

    Отже, мережеві методи - це сукупність прийомів і способів, що дозволяють на основі застосування мережевих графіків (моделей) раціонально здійснювати управлінський процес: планувати, організовувати, координувати і контролювати будь-яку складну роботу.

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

    Нехай tij - тривалість роботи, яка вимірюється, наприклад, в днях. Індекси i та j вказують на початковий і кінцевий події роботи.

    У процесі розрахунку мережевого графіка (моделі) визначаються і аналізуються наступні основні параметри:

    t (L) - тривалість шляху L;

    t кр - тривалість критичного шляху Lкр;

    ti (p), ti (п) - ранній і пізній терміни здійснення подій;

    tij (pн), tij (пн) - ранній і пізній терміни початку роботи;

    tij (ро), tij (по) - ранній і пізній терміни закінчення роботи;

    R (L) - повний резерв часу шляху;

    Rij (п) - повний резерв часу роботи;

    - приватні резерви часу.

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

    Тривалість шляху t (L) є сума тривалості робіт, що складають цей шлях.

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

    Розглянемо один з них.

    Введемо ряд додаткових умов. Якщо мережевий графік не містить відрізка, що з'єднує роботи i і j, то вважаємо tij = -. Далі покладемо tii = 0. Тоді з математичної точки зору завдання полягає в наступному: знайти такий шлях, де Еj - роботи, n - число робіт, при якому величина досягає максимуму.

    В основі методу лежить метод динамічного програмування. Позначимо через vi (i = 1, 2, ..., n-1) величину максимального шляху від вершини i до кінцевої вершини. (Передбачається, що вершини пронумеровані так, що початкова має номер 1, а остання, завершальна, _ номер n).

    Пошук критичного шляху здійснюється в кілька етапів.

    На першому етапі визначаємо величини:

    , I = 1, 2, ..., n-1;

    , I = 1, 2, ..., n-1.

    Ясно, що вони висловлюють тривалості часу, необхідного для того, щоб досягти вершини n від i-ої вершини за один крок.

    Далі переходимо до обчислення:

    , I = 1, 2, ..., n-1; , J = 1, 2, ..., n,

    виражають величини максимальних шляхів, що з'єднують вершини мережевого графіка з вершиною n і складаються з двох ланок.

    Міркуючи аналогічно, крок за кроком, обчислюємо:

    , I = 1, 2, ..., n-1,

    , J = 1, 2, ..., n,

    до тих пір, поки не виявиться, що виконані умови:

    , I = 1, 2, ..., n.

    Знайдене значення vi (k) буде висловлювати величину критичного шляху, що з'єднує першу та n-ую вершини, а число k вкаже, зі скількох ланок цей шлях полягає. Можна вказати, що якщо графік складається з n вершин, то для знаходження критичного шляху досить n-2 етапи послідовних обчислень.

    Тема 8.Методи теорії ігор

    1. Основні поняття теорії ігор.

    2. Підхід до вирішення задач теорії ігор.


    Короткий зміст теми

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

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

    Результат або результат гри, навіть в тому випадку, коли він не має прямого кількісної оцінки, зазвичай характеризується деяким числом, наприклад: виграш +1, програш - -1, нічия - 0.

    Гра може бути парною або множинної (багато учасників).

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

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

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

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

    Гра називається кінцевої, якщо у кожного гравця є лише кінцеве число стратегій.

    Результати кінцевої парної гри з нульовою сумою (КПІНС), можна задати матрицею, рядки і стовпці якої відповідають різним стратегіям, а її елементи є відповідні виграші одного боку (рівні програшів інший). Ця матриця називається платіжною матрицею або матрицею гри. При цьому зручно програш першої сторони розглядати як її негативний виграш, а виграш другий - як її негативний програш.

    Якщо перша сторона має m стратегій, а друга - n, то маємо справу з грою mn.

    Розглянемо гру mn з наступною матрицею:

    B 1

    B 2

    ...

    B j

    ...

    B n

    A 1

    a 11

    a 12

    ...

    a 1j

    a 1n

    A 2

    a 21

    a 22

    ...

    a 2j

    a 2n

    ...

    ...

    ...

    ...

    ...

    ...

    ...

    A i

    a i1

    a i2

    ...

    a ij

    a in

    ...

    ...

    ...

    ...

    ...

    ...

    ...

    A m

    a m1

    a m2

    ...

    a mj

    a mn


    де Ai (i = 1, 2, ..., m) - стратегії першого гравця, Bj (j = 1, 2, ..., n) - стратегії другого гравця, аij - плата в сеансі гри зі стратегіями Ai і Bj .

    Якщо перший гравець застосовує стратегію А i, то інший буде прагнути до того, щоб вибором відповідної стратегії звести виграш першого гравця до мінімуму. З "арсеналу" - набору своїх стратегій другий вибирає таку стратегію В j, щоб величина а ij була б мінімальною, тобто якщо? i є величина цього мінімуму, то:

    .

    C точки зору першого гравця (при будь-яких відповідях противника) доцільно прагнути знайти таку стратегію, при якій? i буде звертатися в максимум. Нехай цей максимум дорівнює?. Він називається нижньою ціною гри. Так як значення? обчислюється за формулою: або, то його називають Максиміна. Йому відповідає Максиміна стратегія (їх може бути декілька), дотримуючись якої перший гравець при будь-яких стратегіях противника забезпечить собі виграш, не менший ніж? (В залежності від знака? Це може бути програш, який в цьому випадку виявиться мінімальним).

    Аналогічним чином визначається мінімальний програш (який може бути в дійсності і виграшем) для другого гравця:

    .

    Величина? називається верхньою ціною гри або МІНІМАКСІ. Їй відповідає мінімаксна стратегія другого гравця.

    Має місце нерівність:.

    При?

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

    Відомо, що для будь-якої КПІНС існує пара оптимальних стратегій (взагалі кажучи змішаних).

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

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

    Ціна гри полягає між нижньою і верхньою ціною гри:

    .

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

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

    Відомо, що у гри mn число корисних стратегій з кожного боку не перевищує мінімального з чисел m і n.

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

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

    Так як при оптимальної стратегії середній виграш першого гравця не менше ?? при будь-якої стратегії супротивника, то шукаємо n нерівностей:

    Вводимо нові невідомі:

    .

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

    Так як

    = 1, то.

    Таким чином, маємо систему нерівностей:

    , (8.1)

    де всі .

    Так як мета оптимальної стратегії - максимізація виграшу, то при її досягненні лінійна функція:

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

    при, що задовольняють системі нерівностей (8.1).

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

    Знаючи ціну гри, оптимальну стратегію (а1, а2, ..., аn) другого гравця можна знаходити вже без рішення задачі лінійного програмування (хоча оптимальну стратегію другого гравця можна знаходити і через рішення цієї задачі, якщо поміняти гравців місцями). Для цього вибирається n-1 корисних стратегій першого гравця (маючи можливість міняти місцями гравців можна вважати, що) і для кожної з них записується середній виграш, який при цьому повинен бути обов'язково дорівнює ціні гри. Наприклад, якщо для першого гравця корисна стратегія Аi, то їй відповідає рівняння:

    .

    Крім цього є ще одне рівняння:

    .

    Всього маємо n рівнянь для n величин q1, q2, ..., q n.

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

    Тема 9.Імітаційне моделювання

    1. Поняття імітаційного моделювання.

    2. Загальна постановка задачі імітаційного моделювання.

    3. Метод Монте-Карло.


    Короткий зміст теми

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

    Отже, практиці потрібен був метод для дослідження складних систем, і такий метод з'явився - це імітаційне моделювання ( "simulation modeling").

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

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

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

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

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

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

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

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

    Основними етапами методу є:

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

    2. Декомпозиція (розбиття) системи на більш прості частини - блоки. В один блок об'єднуються "родинні", тобто преобразующиеся по близьким правилами, компоненти вектора стану і процеси, їх перетворю щие.

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

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

    5. Формалізованим чином задаються необхідні феноменологічні властивості систем в цілому і окремих її частин. (Часто ці властивості не можуть бути обгрунтовані на сучасному рівні знань, а спираються на досвід - тривале спостереження за поведінкою системи). Іноді одне таке властивість виявляється еквівалентним безлічі складних математичних співвідношень і з успіхом їх замінює, що, звичайно, вимагає глибокого знання системи.

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

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

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


    Загальна постановка задачі

    Під імітаційним моделюванням будемо розуміти покрокове моделювання поведінки об'єкта за допомогою ЕОМ. Це означає, що фіксуються певні моменти часу t 1, t 2,..., t n, і стан моделі визначається (обчислюється на ЕОМ) послідовно в кожному з цих моментів часу. Для реалізації цього необхідно задати правило (алгоритм) переходу моделі з одного стану в наступне, тобто перетворення:, де Y i - стан моделі в i-й момент часу.

    Нехай, як зазвичай, стан моделі визначається вектором:, тобто m - числами, стан середовища вектором:, n - числами, а стан управління вектором:, q - числами.

    Тоді імітаційна модель визначається оператором F, за допомогою якого можна визначити стан моделі в наступний момент часу, тобто визначити вектор Y i + 1, знаючи стан моделі в попередній момент часу Y i і значення Х i + 1 і U i + 1, тобто .

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

    ,

    де F - оператор імітацій зміни стану моделі. Він і визначає імітаційну модель об'єкта.

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

    .

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

    , I = 1, ..., N, (9.1)

    де необхідно знати, яким чином фактор Е впливає на стан Y об'єкта, тобто слід добре розібратися в об'єкті і вказати точно, як входить неконтрольований фактор Е в оператор об'єкта з тим, щоб ці дані відобразити в операторі F об'єкта. Для роботи з такою моделлю необхідно знати конкретні значення фактора E, який, як відомо, неспостережуваних. Виникає протиріччя, яке вирішує так званий метод Монте-Карло. Власне, як правило, він і є основним методом імітації.

    Для реалізації методу Монте-Карло необхідно знати деякі статистичні властивості фактора Е (наприклад, закон його розподілу). Ці властивості, взагалі кажучи, можуть залежати від Y, X і U. Маючи цими відомостями, можна моделювати неспостережний фактор у вигляді випадкових рядів:

    , J = 1, 2, ..., N,

    де індекс внизу відповідає дискретного часу, а верхній _ номеру моделируемого ряду (всього моделюється N таких статистично еквівалентних рядів). Природно, жоден з цих рядів не є точною реалізацією дійсності, але кожен має такі ж статистичні властивості, що й реальний. Саме тому ряди дозволяють досліджувати статистичні властивості моделі (9.1).

    Так поведінку моделі "в середньому" описується як:

    ,,

    де Y i j - j-я реалізація поведінки моделі в i-ий момент часу:

    i = 1,2, ...., N.

    Дисперсія виходу моделі обчислюється за формулою:

    .

    Таким чином, метод Монте-Карло дозволяє оцінити статистичні властивості поведінки об'єкта шляхом імовірнісного "розігрування" поведінки моделі, причому одна реалізація поведінки відрізняється від іншої різними значеннями неспостережуваного фактора Е.

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

    У завданнях дослідження операцій метод Монте-Карло застосовується в трьох основних ролях:

    1. Моделювання складних, комплексних об'єктів і операцій, де є багато взаємодіючих випадкових факторів.

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

    3. З метою вироблення поправок до аналітичними формулами "типу емпіричних формул" в техніці.

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

    Головний же недолік таких моделей - їх громіздкість і трудомісткість. Величезне число реалізацій, необхідне для знаходження шуканих параметрів з прийнятною точністю, вимагає великої витрати машинного часу. Крім цього, результати такого моделювання важче осмислити, ніж розрахунки аналітичними методами і, відповідно, важче оптимізувати рішення (в основному, на дотик). Найбільш доцільним є поєднання аналітичних і імітаційних методів. Як правило, аналітичними методами розраховуються окремі елементи і блоки складної системи, а потім, як з "цеглинок", будується велика складна імітаційна модель.

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

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

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

    Тоді потрібно "киданням жереба" вирішити питання: відбулася подія чи ні? Як можна здійснити цей жереб? Необхідно привести в дію будь-якої механізм випадкового вибору.

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

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

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

    Домовимося називати "одиничним жеребом" будь-який досвід з випадковим результатом, який відповідає на одне з наступних питань:

    1. Сталося чи ні подія А?

    2. Яка з подій А1, А2, ..., Аk сталося?

    3. Яке значення прийняла випадкова величина Х?

    4. Яку сукупність значень прийняла система випадкових величин Х1, Х2, ..., Хk?

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

    Одиничний жереб може бути розіграний різними способами, але є один стандартний механізм, за допомогою якого можна здійснити будь-який різновид жереба. А саме, для кожної з них достатньо вміти отримувати випадкове число R, все значення якого від 0 до 1 різновірогідні (тобто мають однакову щільністю ймовірності).

    Умовно назвемо величиною R "випадкове число від 0 до 1". За допомогою такого числа можна розіграти будь-який з чотирьох видів одиничного жереба.

    Тема 10. Методи теорії масового обслуговування

    1. Основні поняття теорії масового обслуговування.

    2. Постановка задачі теорії черг.

    3. Підходи вирішення завдань теорії черг.


    Короткий зміст теми

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

    Будь-яка система масового обслуговування може включати в себе наступні елементи:

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

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

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

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

    Вихід двійкового обслужених вимог. Цей елемент може виявитися дуже важливим в тих випадках, коли вихідний потік обслужених вимог є вхідним для іншої системи масового обслуговування.

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

    Основними компонентами моделі черги є:

    опис вхідного потоку вимог;

    опис способу, яким виконується обслуговування (тобто опис дисципліни обслуговування);

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

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

    Принциповими характеристиками черзі є:

    довжина черги в різні моменти часу;

    загальна тривалість перебування вимоги в системі обслуговування (тобто час, витрачений на очікування в черзі, плюс власний час обслуговування);

    час, протягом якого обслуговуючий пристрій було вільно.

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

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

    1. Вимоги надходять через однакові інтервали часу. Кожен інтервал має довжину a одиниць.

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

    3. Дисципліна черги встановлюється за правилом "Перший прийшов - перший обслуговується". Іншими словами, очікують вимоги утворюють чергу, і, коли обслуговуючий пристрій звільниться, на обслуговування надходить вимога, що має більший час очікування.

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

    Поведінка системи залежить від того, як пов'язані між собою величини a і b. Можливі три випадки: 1) b> a; 2) b = a; 3) b

    1) Випадок b> a. Це означає, що швидкість обслуговування 1 / b менше, ніж швидкість надходження вимог 1 / a, тобто вимоги обслуговуються і залишають систему повільніше, ніж прибувають. Отже, в цьому випадку буде утворюватися чергу і вона буде постійно зростати.

    2) Випадок b = a. Якщо в черзі немає вимог, то перше що надійшла вимога відразу почне обслуговуватися. Його обслуговування закінчиться в той же самий момент, в який надійде на обслуговування наступну вимогу. Отже, вимог, які очікують обслуговування, не буде.

    Якщо ж спочатку є чергу, то її довжина буде залишатися постійною.

    3) Випадок b

    Нехай на початку процесу число вимог в черзі r 2 (якщо спочатку є тільки одна вимога (r = 1), то воно буде обслуговано перш, ніж надійдуть на обслуговування таких вимог, і черга буде порожній).

    У загальному випадку, нехай маємо r вимог, що стоять в черзі перед початком обслуговування. Тоді число вимог (N), що надійшли після початку процесу обслуговування до тих пір, поки зберігається чергу, можна визначити за формулою:

    , (10.1)

    де позначення [x] означає цілу частину числа x. Дійсно, черга буде відсутній, якщо через обслуговуючий пристрій повністю пройде N + r вимог. Для цього буде потрібно (N + r) b одиниць часу. За цей час на обслуговування надійде N вимог, так що до вступу (N + 1) -го вимоги обслуговуючий пристрій буде вільно і готово обслужити його відразу без всякої черги. Але (N + 1) -е вимога надійде на обслуговування через (N + 1) a одиниць часу, при цьому буде виконано співвідношення:

    .

    звідси,

    . (10.2)

    Доведемо, що в отриманому співвідношенні N більше правій частині не більше ніж на 1. Дійсно, перше що стоїть в черзі вимога буде вже обслуговано, а перше знову надходить на обслуговування вимога ще не з'явиться в черзі (a> b). Тому справедливо співвідношення:

    aN (N + r-1) b або.

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

    Очевидним є те, що N є ціле число. Отже, якщо від правої частини в співвідношенні (10.2) взяти цілу частину і додати до неї 1, то, виходячи з попередніх міркувань, отримаємо для обчислення N вираз (10.1).

    Аналогічними міркуваннями і використовуючи (10.1) можна знайти, що для обчислення часу, який необхідний для обслуговування всіх очікують вимог, справедлива формула:

    . (10.3)

    В теорії черг важливою функцією є функція часу очікування обслуговування. Позначимо її через W (t). Визначимо W (t) як час, який необхідно витратити на очікування обслуговування вимоги, що надійшов в момент часу t (вважаємо, що t = 0 відповідає початку процесу обслуговування).

    Визначимо формулу для W (t). Легко бачити, що вимога, що надійшла на обслуговування в момент t Tb (величина T визначається з використанням формули (10.3)), знайде систему обслуговування порожній або тільки що звільнилася. Такому вимогу не доведеться стояти в черзі. Вимога, що надійшла в момент часу tT-b, знайде перед собою вимог, що стоять в черзі, причому перше з них в цей же момент надійде на обслуговуючий пристрій. Ця величина отримують у такий спосіб:

    (Початкова (число вимог, обслужен- (число поступ-

    чергу) - них до моменту часу t) + лений)

    r - +.

    Таким чином, час очікування W (t) для розглянутого вимоги може бути виражено формулою:

    . (10.4)

    Розглянемо i-е вимога в початковій черзі (0

    Узагальнюючи отримані результати щодо функції W (t), отримаємо для неї такий вираз:

    ,

    де i - номер i-го вимоги в початковій черзі; вимоги надходять в моменти часу a, 2a, ...; b = na (n = 1, 2, ...).

    Тема 11.Управління запасами

    1. Поняття завдання управління запасами.

    2. Основне завдання управління запасами.

    3. Управління запасами в умовах виробничих поставок.

    4. Управління запасами в умовах дефіциту.


    Короткий зміст теми

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

    Підприємства в процесі своєї діяльності роблять різні запаси. Запаси - це сукупність предметів (товарів), що представляють собою тимчасово не використовуються економічні ресурси.

    Причини створення запасів можуть бути різними.

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

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

    Основні типи прийнятих рішень з управління запасами наступні:

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

    2. Визначити, в який час необхідно проводити поповнення запасів.

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

    Розглянемо три найпростіші математичні моделі, що включають:

    а) основну модель управління запасами - визначення оптимального розміру партії;

    б) модель виробничих поставок;

    в) модель, що враховує штрафи.

    Отже, предмет вивчення - кількість запасу на складі і час t, для якого розглядається цей запас, тобто досліджується функція = f (t), що відповідає величині запасу в момент часу t. Графік такої функції називається графіком зміни запасу.

    З приводу зміни функції запасів зробимо наступні припущення:

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

    2. Якщо = 0, то має місце дефіцит товару.

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

    Витрати, пов'язані з запасами, можна представити таким чином:

    Організаційні витрати - витрати, пов'язані з оформленням та доставкою товарів, необхідні для кожного циклу складування. Це підготовчо-заключні операції при надходженні товарів і подачі заявок.

    Якщо запаси потрібно поповнити, то на склад завозиться чергова партія. Витрати на поставку - організаційні витрати.

    Кількість товарів, що поставляється на склад, - розмір партії товарів.

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

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

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


    Основна задача

    Отже, маємо таку таблицю параметрів моделі і припущення (допущення) щодо зміни їх величин.

    Назва параметра

    позначення

    Одиниці виміру

    припущення

    інтенсивність попиту

    d

    Од-ці товару в рік

    Попит постійний і безперервний. Весь попит задовольняється.

    організаційні витрати

    s

    $ За одну партію

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

    Вартість товару

    c

    $ За од-цу товару

    Ціна од-ці товару постійна, маємо тільки один вид товару

    Витрати утримання запасів

    h

    $ За од-цу товару в рік

    Вартість зберігання од-ці товару протягом року постійна

    Розмір партії

    q

    Од-ца товару в одній партії

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


    Завдання управління: визначити значення q, при якому мінімізуються річні витрати.

    Розглянемо графік зміни запасів. Відповідно до припущеннями цей графік має вигляд:

    Щоб повністю задовольнити річний попит d в розмірі поставки, рівному q, потрібно за рік зробити поставок. Партія - це поставка.

    Середній рівень запасів дорівнює.

    Складаємо рівняння витрат. Це буде:

    .

    Щоб знайти мінімум С, вважаємо функцію f (q) ді ...........