ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 29.05.2024
Просмотров: 12
Скачиваний: 1
Алгоритми, що дозволяють вирішувати на електронних обчислювальних машинах задачу про комівояжера, використовуються не тільки при виборі маршрутів автотранспорту при кільцевій доставці товарів (наприклад, в торгову мережу), але і при рішенні таких задач, які на перший погляд ніякого відношення до задачі комівояжера не мають, наприклад в плануванні виробництва на конвейєрах, що випускають машини різних моделей. На ЕОМ за допомогою таких алгоритмів розраховують оптимальні партії, що дозволяють випускати заданий об'єм продукції з мінімумом витрат на переналагодження конвейєра.
Розподільні задачі — клас економіко-математичних задач, пов'язаних з розподілом ресурсів по роботах, які необхідно виконати. Якщо ресурсів достатньо, щоб кожну роботу виконати найбільш ефективно, задача не виникає. В зворотному випадку перекидання, передача ресурсів з однієї роботи на іншу приводить до зміни загальної ефективності всіх робіт, разом узятих. Тому розподільна задача полягає у відшуканні якнайкращого розподілу ресурсів, при якому або максимізовувався загальний дохід або результат, виражений в якій-небудь іншій формі, або мінімізуються витрати.
Такі
задачі частіше за все приводяться до
лінійного вигляду (іноді штучно за
рахунок спрощень) і розв'язуються методом
лінійного програмування. Якщо
черезз
позначити
об'єм ресурсуа
,
виділеного на роботуу
,
то математичне формулювання розподільної
задачі таке: знайти мінімум або максимум
цільової функції (мінімум витрат
min
або
максимум ефекту max
при
обмеженнях за об'ємом ресурсів і потреби
в них. При цьому розрізняються два види
таких задач:
а)
збалансована (закрита), якщо загальний
об'єм ресурсівв
рівний
загальній потребі в нихх
;
б)
незбалансована (відкрита), колиа
і
вимагається не тільки розподілити
ресурси по роботах (споживачам), але
також вирішити, які роботи не слід
виконувати (тобто яких споживачів не
задовольняти), якщо ресурси менше потреб,
або які ресурси не використовувати —
в протилежному випадку.
До розподільних задач відносяться такі широко поширені задачі, як транспортна задача, задача про призначення і багато інших. Задачі розподілу можуть розв'язуватися в статичній (однократної) і в динамічній постановці. В останньому випадку часто застосовують методи стохастичного програмування (в яких ухвалення рішень засновано на оцінках вірогідності майбутніх значень параметрів).
Задача про призначення — вид задачі лінійного програмування, за допомогою якої розв'язуються питання типу: як розподілити робітників по верстатах, щоб загальне вироблення було найбільшим або витрати на заробітну платню якнайменшими (оскільки для кожної комбінації «робітник— верстат» характерна своя продуктивність праці), як найкращим чином розподілити екіпажі літаків, як призначити людей на різні посади (звідси і назва задачі) і т.д.
Математично
такі задачі — окремий випадок розподільних
задач з тією особливістю, що в них об'єми
наявних і потрібних для виконання кожної
роботи ресурсів рівні одиниці, тобто.
=
=1, іи
=1,
якщо працівникк
призначений
на роботу
,
або нулю в решті випадків. Інакше кажучи,
для виконання кожної роботи витрачається
тільки один вид ресурсу, а кожний ресурс
може бути використаний на одній роботі:
ресурси неподільні між роботами, а
роботи — між ресурсами. Початкові дані
групуються в таблиці, яка називається
«матрицею оцінок», результати — в
«матриці призначень».
Кількість можливих варіантів призначень рівна факторіалу числа робіт і ресурсів і величезно навіть в невеликій задачі. Тому для знаходження оптимального варіанту застосовують спеціальні алгоритми. Серед них особливо ефективний при рішенні задачі уручну так званий «угорський метод».
Задача про розкрій — окремий випадок задач про комплексне використовування сировини, звичайно що зводяться до методу лінійного програмування. Вироблений математиками метод рішення задачі про розкрій допомагає з якнайменшими відходами використовувати прутки і листи металу, листи скла, картону і інших матеріалів при розкроі їх на задану кількість деталей різних розмірів.
Постановку
задачі в загальному вигляді можна
сформулювати так: вимагається знайти
мінімум лінійної форми, що виражає число
витрачених листів матеріалу (листів і
т. п.) за всіма j-м способами їх розкроу:
за умови,
що змінні задовольняють обмеженню
Це
означає, що дотримана комплектність:
всі необхідні заготівки зроблені в
достатній кількості,
((
—
число заготівок i-го типу при j-м способі
розкроу;;
—
число листів, розкроєних j-м способом).
Нарешті, приймається умова позитивності::
0,
тобто число листів не може бути негативне.
Способи постановки і рішення таких задач добре відпрацьовані і їх можна застосовувати на будь-якому підприємстві. При правильній постановці задачі вживання методу лінійного програмування гарантує скорочення відходів до мінімально можливого. Часто на підприємствах відходи скорочуються у декілька разів.
Задачі пошуку — клас задач, що полягають у відшуканні якнайкращого способу отримання такої інформації, яка однозначно визначила б рішення. Критерієм в такій задачі є мінімум витрат двох видів: вартості отримання інформації і ціни помилки, обумовленої її використовуванням. В першому випадку йдеться про вартість вибірки, планування якої зводиться до визначення способу вибору наглядів або вибору спостережуваних об'єктів, в другому випадку — про помилки двох пологів: помилці вибірки (виявлення того, що насправді відсутній — «помилкова тривога») і помилці нагляду (пропуск того, що насправді має місце — «пропуск мети»).
Задачі узгодження — клас задач, пов'язаних з узгодженням сукупності окремих робіт і приватних операцій в часі для отримання оптимального загального результату. Це звичайно задачі мережного планування і управління.
Задачі впорядкування — клас задач, в яких проводиться вибір дисципліни обслуговування. Таким чином, вони як би протилежні задачам теорії масового обслуговування, в яких дисципліна (тобто порядок виконання вимог) задана. Вибір порядку обслуговування називається впорядкуванням. Найбільш поширені серед задач (моделей) впорядкування задачі теорії розкладів. До них відносяться також методи ситуаційного управління і деякі інші.
Задачі теорії розкладів — один з видів задач дослідження операцій, об'єднуваних в класі задач впорядкування. Теорією розкладів називається тут сукупність моделей календарного планування і розроблених для їх вирішення методів дискретного програмування.
Складність таких задач можна проілюструвати прикладом: вимагається спланувати виготовлення чотирьох виробів, кожне з яких проходить обробку на кожному з п'яти верстатів. Існує (4!) 5 або майже 7962 тис. різних варіантів обробки (послідовностей); деякі з них до того ж треба якось відсіяти, оскільки певні операції слід виконувати в заданому порядку. На практиці, зрозуміло, задачі набагато складніше.
Простіше за інші розв'язуються так звані задачі одного верстата: пошук якнайкращої послідовності обробки на ньому деякої безлічі деталей (якнайкращої з погляду мінімуму витрат на пролежування деталей до обробки і після неї, мінімуму часу затримки у видачі деталей в порівнянні зі встановленим терміном, мінімального об'єму незавершеного виробництва і т. п.).
Існує також ряд моделей планування роботи виробничої ділянки (методичну основу для них дає модель Джонсона для п деталей і двох верстатів, але вона представляє лише теоретичний інтерес і малоприменима на практиці). Нарешті, теорія розкладів містить методи складання календарних планів роботи підприємств. Звичайно задача ставиться таким чином: скласти план виготовлення всіх виробів, в якому не порушувалися б технологічні обмеження, обмеження по потужності устаткування, а також терміни запуску і випуску. Такі задачі розв'язуються звичайно наближеними методами, у тому числі методом Монте-Карло і ін. В описаних умовах велике значення мають способи скорочення розмірності задач. Теорія розкладів — теоретична база оптимального календарного планування. Використовує ряд методів лінійного програмування, дискретного програмування, методи гілок і меж, мережного планування і управління і ін. Моделі теорії розкладів дозволяють, наприклад, вирішувати такі задачі, як визначення оптимальної послідовності обробки деталей на верстатах, планування роботи виробничої ділянки, складання программы-«диспетчера» для управління роботою електронної обчислювальної машини в мультипрограмному режимі.
Задача про розміщення складів — одна із задач, звичайно вирішувана методом нелінійного програмування (але за деяких умов вона може зводитися і до звичайної транспортної задачі лінійного програмування). Полягає в мінімізації загальної суми транспортних і складських витрат при наступних обмеженнях: з кожного заводу повинна бути відвантажена вся продукція, місткість будь-якого складу не повинна бути перевищена, потреби всіх покупців повинні бути задоволені. По суті справа зводиться до відшукання трехзвенных комбінацій підприємство — склад — споживач, в сукупності забезпечуючих мінімум витрат.
Управління запасами — комплекс моделей і методів, призначених для оптимізації запасів, тобто ресурсів, що знаходяться на зберіганні і призначених для задоволення попиту на ці ресурси. Терміни ресурси і запаси тут розуміються узагальнено: можна говорити про запаси кінцевої продукції, про запаси напівфабрикатів (тоді відповідна задача буде задачею про оптимізацію незавершеного виробництва), про запаси сировини, природних і трудових ресурсів, грошових коштів і т.д. Роль виробництва зводиться тут до поповнення рівня запасів у міру виникнення потреби в них. Іншим джерелом задоволення заявок на ресурси є склад, власне запас.
Як цільова функція в задачах управління запасами виступають сумарні витрати на зміст запасів, на складські операції, втрати від псування при зберіганні і моральне старіння, втрати від дефіциту і штрафи і т.д. Природно, що відстежується мінімум цієї функції. Керованими змінними в таких задачах є об'єм запасів, частота і терміни їх поповнення (шляхом виробництва, закупівлі і т. д.), ступінь готовності продукції, що зберігається у вигляді запасів і ін. Задачі статичні (коли ухвалюється разове рішення про рівень запасу на певний період) і динамічні, або багатокрокові, коли ухвалюються послідовні рішення або коректується раніше ухвалене рішення з урахуванням змін, що відбуваються. Спрощеним прикладом задач управління запасами може служити задача про оптимальну партію.
Теорія ігор — розділ, що вивчає математичні моделі конфліктних ситуацій (тобто ситуацій, при яких інтереси учасників або протилежні і тоді ці моделі називаються іграми антагоністів, або не співпадають, хоча і не протилежні, і тоді йдеться про ігри з непротилежними інтересами.) Основоположники теорії Дж. фон Нейман і О. Моргенштерн спробували математично описати явища конкуренції як якусь «гру». В найпростішому випадку йдеться про протиборство тільки двох супротивників, наприклад двох конкурентів, що борються за ринок збуту. В складніших випадках в грі бере участь багато хто, причому вони можуть вступати між собою в постійні або тимчасові коаліції, союзи. Гра двох осіб називається парною; коли в ній беруть участь п гравців, це гра п осіб, у разі утворення коаліцій гра називається коаліційною.
Суть гри в тому, що кожний з учасників ухвалює такі рішення (тобто вибирає стратегії дій), які, як він вважає, забезпечують йому найбільший виграш або якнайменший програш, причому цьому учаснику гри ясно, що результат залежить не тільки від нього, але і від дій партнера (або партнерів), іншими словами, він ухвалює рішення в умовах невизначеності. Ці рішення відображаються в таблиці, яка називається платіжною матрицею. Часто виявляється така точка (седловая), в якій досягається рівновага, прийнятна для партнерів.
