Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Міністерство освіти і науки України
ХАРКІВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ
УНІВЕРСИТЕТ БУДІВНИЦТВА ТА АРХІТЕКТУРИ
Н.Ю.Іохвидович, Е.В. Поклонський,
І.В. Подкопай, Р.В. Посилаєва
ДОСЛІДЖЕННЯ ОПЕРАЦІЙ
Навчально – методичний посібник
Харків 2010
Міністерство освіти і науки України
ХАРКІВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ
УНІВЕРСИТЕТ БУДІВНИЦТВА ТА АРХІТЕКТУРИ
Н.Ю.Іохвидович, Е.В. Поклонський,
І.В. Подкопай, Р.В. Посилаєва
ДОСЛІДЖЕННЯ ОПЕРАЦІЙ
Рекомендовано
методичною радою університету
як навчально–методичний посібник
для студентів напряму 6.030601
Харків 2010
Рецензенти:
А.А.Янцевич, доктор фіз.-матем. наук, професор каф. вищої математики і інформатики Харківського національного університету ім. В.Н.Каразіна
О.О. Аршава, канд. фіз.-мат. наук, доцент, зав. кафедри вищої математики Харківського державного технічного університету будівництва та архітектури
Рекомендовано кафедрою вищої математики,
протокол № 9 від 27.05.09
Затверджено методичною радою університету,
Протокол № 1 від 30..09.09
Автори: Н.Ю.Іохвидович
Е.В. Поклонський
І.В. Подкопай
Р.В. Посилаєва
Н.Ю.Іохвидович, Е.В. Поклонський, І.В. Подкопай, Р.В. Посилаєва. Дослідження операцій: навчально – методичний посібник – Харків, ХДТУБА, 2010. – 80 с.
У навчально-методичному посібнику викладаються основні задачі теорії дослідження операцій: задачі теорії графів; задачі, що розв’язуються методом гілок та меж; задачі теорії ігор та теорії масового обслуговування. Наведена велика кількість економічних задач з розв’язаннями та задач для самостійної роботи. Також є питання для самоперевірки. Посібник призначається для студентів економічних спеціальностей та осіб, що займаються самоосвітою.
Іл: ; табл.: ;бібліогр.: назв
© Н.Ю.Іохвидович, Е.В. Поклонський, І.В. Подкопай, Р.В. Посилаєва, 2010
Теорія операцій досліджує методи, які дають досліднику (керівнику) кількісні результати для прийняття відповідних рішень.
Під операцією розуміють сукупність взаємно погоджених дій, що спрямовані на досягнення певної мети. Операція – це захід, що управляється. Наприклад, монтаж обладнання з метою забезпечення випуску продукції в задані терміни. Якщо мета визначена, бажано серед різних шляхів її досягнення (різних рішень) знайти кращий з точки зору показника якості вибраного засобу дій.
Критерій ефективності (цільова функція) характеризує відповідність між результатом вжитих дій і метою операції. Наприклад, критерієм ефективності може бути вартість перевезення вантажу зі складів в місця призначення, довжина шляху, ймовірність знаходження несправності і т.п. Інтерес викликають ті рішення, які дозволяють досягти мінімальних (або максимальних) значень критерію.
Критерій ефективності визначається прагненням забезпечити достатньо повну його відповідність призначенню системи і оцінити ті її властивості, що визначають першочерговий інтерес. Очевидно, що вибір критерію непроста задача, бо потрібно враховувати різноманітні інтереси учасників операції, що планується.
Математична модель операції – це формальні співвідношення, що встановлюють зв’язок вибраного критерію ефективності з умовами і обставинами, що впливають на наслідок операції. Жодна формальна модель не дає вичерпних відомостей про розвиток реальних подій (бо завжди присутні неконтрольовані фактори), але рішення, одержані з її допомогою, дозволяють орієнтуватися в навколишньому середовищі, вносити уточнення в модель, аналізувати різноманітні можливості поведінки, виявляти другорядні обставини і умови.
Розглянемо типові моделі задач теорії дослідження операцій.
Маємо обмежений ресурс коштів, потрібних для виробництва. Необхідно так розподілити ресурси, щоб досягти максимальної ефективності.
До задач розподілу можна віднести транспортну задачу, яка розглядається в курсі «Математичне програмування», задачу про призначення (маємо n посад та m претендентів на них, потрібно так розподілити претендентів, щоб витрати на заробітну плату були мінімальними).
Ці задачі виникають в аналізі процесів, що призводять до затримки обслуговування і черг.
Потрібно виконати велику кількість робіт, при цьому роботи треба розподілити так, щоб витрати часу були мінімальними.
Сформулюємо типові етапи розв’язання задач теорії дослідження операцій.
У подальшому детально розглянемо деякі з означених вище задач.
Постановка задачі. Маємо n деталей і m верстатів. Кожна з n деталей повинна пройти обробку на m верстатах. Час обробки деталей на кожному верстаті задано. Слід вказати такий порядок обробки, щоб сумарний час обробки деталей був мінімальний. З другого боку, це означає мінімальний простій верстатів.
Така задача повністю розв’язана для випадку n деталей і 2-х верстатів.
Для двох верстатів існує (n!)2 можливостей обробки деталей (для одного верстата це n! способів обробки n деталей).
Доведено, що деталі на другому верстаті повинні оброблятися в тому ж порядку, що і на першому. Це скорочує число можливих варіантів обробки з (n!)2 до n! Ідея полягає в тому, щоб максимально скоротити простої другого верстата при повному винятку переривання в роботі першого.
Алгоритм Джонсона для розв’язання цієї задачі полягає в наступному. Нехай ai – час обробки i-ї деталі на I-му верстаті,
bi – час обробки i-ї деталі на II-му верстаті,
i=1,2,…,n.
Знаходимо min(a1, a2,…, an, b1, b2,…, bn). Якщо цей мінімум дорівнює aj (знаходиться серед ai), то j-та деталь обробляється першою. Якщо цей мінімум дорівнює bk (знаходиться серед bi), то k-та деталь обробляється останньою. Далі процедура повторюється.
Приклад. Маємо 5 деталей, задано час їх обробки на I-му та II-му верстатах.
|
I |
1 |
2 |
3 |
4 |
5 |
|
ai (I верстат) |
7 |
1 |
6 |
9 |
3 |
|
bi (II верстат) |
4 |
3 |
5 |
7 |
2 |
|
Послідовність обробки |
4 |
1 |
3 |
2 |
5 |
З часових осей бачимо, що час простою дорівнює 8 одиниць часу.
Задача розкладу для n деталей і трьох верстатів у загальному випадку не розв’язана. Але у випадку, коли min ai ≥ max bi або min ci ≥ min bi , де ai, bi, ci – це час обробки i-ї деталі відповідно на I, II і III верстатах, оптимальний порядок обробки деталей визначається за сумами ai+bi, і bi+ci, що зводиться до задачі про два верстати.
Питання для самоперевірки
Задачі для самостійної роботи
|
I |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
ai (I) |
20 |
13 |
17 |
8 |
11 |
25 |
10 |
11 |
7 |
6 |
|
bi (II) |
17 |
6 |
21 |
14 |
4 |
18 |
19 |
21 |
16 |
15 |
|
I |
1 |
2 |
3 |
4 |
5 |
|
ai (I) |
8 |
12 |
9 |
8 |
7 |
|
bi (II) |
7 |
6 |
4 |
6 |
4 |
|
ci (III) |
5 |
13 |
8 |
9 |
4 |
Глава 2 ЕКСТРЕМАЛЬНІ ЗАДАЧІ НА ГРАФАХ
2.1 Основні поняття
Графом називається сукупність двох множин U (точок) та V (ліній), між елементами яких визначено відношення інцидентності, причому кожний елемент інцидентний точно двом елементам . Елементи множини U називають вершинами графа G, елементи множини V – його ребрами. Ребро називають інцидентним вершині, якщо воно заходить у вершину або виходить з неї.
В деяких задачах інцидентні ребру вершини нерівноправні: вони розглядаються в певному порядку. Тоді кожному ребру можна приписати напрям від однієї з інцидентних вершин до іншої. Ребра, які мають напрям, називають дугами. Граф, що складається з неорієнтованих ребер, називається неорієнтованим. Граф, що складається з орієнтованих ребер (дуг), називається орієнтованим.
Послідовність вершин і ребер, де кожне ребро з’єднує дві суміжні вершини, називається маршрутом у графі. Маршрут починається з вершини і закінчується у вершині. Якщо початок і кінець маршрута співпадають, то маршрут називається циклічним.
Маршрут, усі ребра якого різні, називається ланцюгом.
Якщо початкова і кінцева вершини ланцюга співпадають, то це цикл.
Ланцюг простий, якщо всі його вершини різні (не повторюються).
Цикл простий, якщо співпадають лише початкова і кінцева вершини.
Шлях – це маршрут в орієнтованому графі, по якому потрібно рухатись, погоджуючись з покажчиком напряму. Шлях, у якому початкова і кінцева вершини співпадають, називається контуром.
Граф називається зв’язним, якщо для будь-яких вершин існує ланцюг, що їх з’єднує.
Зв’язний граф називається ейлеровим, якщо існує цикл, що проходить через кожне його ребро.
Граф називається гамільтоновим, якщо існує цикл, що проходить тільки один раз через кожну вершину графа.
2.2 Способи задання графа
Зображення графів на площині у вигляді множини точок і множини ребер (дуг) – найбільш прийнятний і наочний спосіб, але його не можна використати тоді, коли для розв’язання тієї чи іншої задачі, пов’язаної з графами, необхідне застосування комп’ютера.
Існують різні способи задання графа:
1 Матриця суміжності вершин
Нехай у графі число вершин дорівнює n. Матриця суміжності вершин орієнтованого графа R=(rij) має розмір ,
де
Якщо граф неорієнтований, вершини з’єднуються ребрами і матриця R=(rij) є симетричною.
Наприклад,
,
.
2 Матриця суміжності ребер графа
Нехай у графі m ребер. Матриця суміжності ребер неорієнтованого графа B=(bij) має розмір ,
де
Для орієнтованого графа
Наприклад,
,
.
3 Матриця інцидентності
Якщо граф неорієнтований і має n вершин і m ребер, то матриця інцидентності S=(sij) має розмір ,
де
Для орієнтованого графа
Наприклад,
,
.
За матрицею інцидентності можна відновлювати граф.
2.3 Дерева та ліс. Остовне дерево графа
Зв’язний граф без циклів називається деревом. Дерево графа має n–1 ребер, де n – кількість вершин. Ліс – це незв’язний граф без циклів.
Остовним називається дерево графа, що містить усі його вершини.
Існує спосіб підрахунку числа остовних дерев графа. Знайдемо матрицю R=(rij) – матрицю суміжності вершин графа. Далі утворюємо матрицю М за правилом: діагональні елементи матриці R замінюємо сумою елементів відповідного рядка, а елементи цього рядка, що дорівнюють «1», замінюємо на «-1». Можна довести, що алгебраїчне доповнення будь-якого елемента матриці М дорівнює числу остовних дерев даного графа.
Приклад. Маємо граф
n=5 – кількість вершин графа
m=6 – кількість ребер.
Підрахуємо кількість остовних дерев графа
.
Знайдемо матрицю М
.
Знайдемо алгебраїчне доповнення елемента m11
.
Розкладемо визначник за елементами другого рядка
.
Даний граф має 11 остовних дерев.
2.4 Алгоритм побудови остовного дерева зв’язного графа
При виконанні алгоритму деякі ребра і вершини будемо зафарбовувати.
Крок І Беремо будь-яке не зафарбоване ребро, фарбуємо його і інцидентні з ним вершини. Ця конструкція називається букетом.
Крок ІІ Беремо будь-яке не зафарбоване ребро. При цьому можуть трапитися такі випадки.
Якщо кожному ребру відповідає вага cij > 0, то можна будувати остовне дерево мінімальної (максимальної) довжини. Для цього ребра упорядковуємо відповідно зростанню (спаданню) їх ваги, а далі алгоритм працює так , як сказано вище.
Наприклад, система міст з’єднується шляхами (тобто маємо граф), і потрібно проїхати з одного міста в інше так, щоб витрати на проїзд були мінімальними. Ця задача зводиться до побудови остовного дерева мінімальної довжини.
Приклад.
В даному графі 5 вершин, тобто дерево повинно мати 4 ребра. Сумарна вага остовного дерева мінімальної ваги (довжини) 2+3+7+5=17.
2.5 Знаходження найкоротшого шляху в орієнтованому графі
Задано орієнтований граф. Кожній дузі, що з’єднує вершину ui з вершиною uj (ui → uj), відповідає невід’ємне число cij > 0. Це число називаємо вагою дуги.
Питання, що тут виникають:
Один із методів розв’язання таких задач – це алгоритм Дейкстри (розв’язок одержано у 1960р., автор – Дейкстра).
При роботі цього алгоритма будемо користуватись такими правилами:
Крок І Початковій вершині присвоюється остаточна позначка «0», а іншим вершинам – тимчасова позначка «∞».
Крок ІІ Кожній вершині х, яка не має остаточної позначки, присвоюється нова тимчасова позначка за правилом :
min(dx, dy+cyx),
де dx – стара тимчасова позначка вершини х;
у – вершина, яка одержала остаточну позначку на попередньому кроці;
cyx – вага дуги (у,х).
Крок ІІІ Знаходимо найменшу з усіх тимчасових позначок і оголошуємо її остаточною позначкою відповідної вершини. Ця вершина грає роль вершини у для наступного кроку.
Приклад. Маємо орієнтований граф, де задані ваги дуг.
Знайдемо найкоротший шлях у графі від вершини до вершини .
1 d1=0, di=∞, де i = 2,3,4,5,6.
2 = => dy = 0,
d2 = min(∞,0+4) = 4,
d3 = min(∞,0+2) = ,
d4 = min(∞,0+7) = 7,
d5 = min(∞,0+∞) = ∞,
d6 = min(∞,0+∞) = ∞.
Зауважимо, що cyx=0, якщо немає шляху (дуги) y→x. Вибираємо мінімальну позначку, це d3 = 2.
3 = => dy = 2,
d2 = min(4,2+∞) = ,
d4 = min(7,2+∞) = 7,
d5 = min(∞,2+3) = 5,
d6 = min(∞,2+∞) = ∞.
4 = => dy = 4,
d4 = min(7,4+3) = 7,
d5 = min(5,4+2) = ,
d6 = min(∞,4+∞) = ∞.
5 = => dy = 5,
d4 = ,
d6 = min(∞,5+2) = 7.
6 = => dy = 7,
d6 = min(7,7+2) = 7.
Всі вершини мають остаточні позначки.
При розв’язанні слід відразу на графі позначати остаточні позначки вершин.
Таким чином найкоротший шлях з початкової вершини до кінцевої вершини дорівнює 7.
Також ми маємо найкоротший шлях з початкової вершини до будь-якої вершини графа.
На графі слід також позначити цей найкоротший шлях.
Існує ще один спосіб для знаходження екстремального шляху в графі – спосіб позначок.
Розглядаємо орієнтований граф, який називається мережевим. В такому графі існує одна вершина, з якої дуги лише виходять (витік, джерело), і одна вершина, в яку дуги лише входять (стік). Крім того, вершини такого графа можуть бути пронумеровані таким чином, що наступні по напрямку руху вершини (послідовники) мають більші номери, ніж попередні (попередники). Тоді всі вершини графа можна розбити на шари таким чином, що вершини кожного шару з номером m (m > 1) будуть послідовниками вершин із шарів з меншими ніж m номерами і попередниками вершин із шарів з більшими ніж m номерами.
Приклад. Розглянемо приклад мережевого графа.
Знайдемо для цієї мережі найкоротший шлях методом позначок, для якого використаємо формулу
де dj – позначка j-ї вершини, cij – вага дуги (i,j).
Вершини, що остаточно позначені, об’єднаємо в множину I*.
Вершини, сусідні з позначеними, об’єднаємо в множину ω(I*).
В сусідні вершини включаються ті вершини, для яких існує хоча б одна дуга, що йде з позначеної вершини.
I d1 = 0 (за формулою). Тобто вершина остаточно позначена і має позначку .
На цьому етапі
I* = {1},
ω(I*) = {2,3,4} – множина вершин, сусідніх з позначеними.
Знайдемо тимчасові позначки вершин множини ω(I*) за формулою .
d2 = 0+2 = 2,
d3 = 0+1 = 1,
d4 = 0+4 = 4.
З усіх тимчасових позначок вибираємо найменшу: . Таким чином, вершина одержує остаточну позначку .
II I* = {1,3}, ω(I*) = {2,4,5,6}.
d2 = 0+2 = 2,
d4 = min(0+4,1+2) = 3,
d5 = 1+5 = 6,
d6 = 1+6 = 7.
– вершина одержує остаточну позначку .
III I* = {1,2,3}, ω(I*) = {4,5,6,7}.
d4 = min(2+3,0+4,1+2) = 3,
d5 = min(2+4,1+5) = 6,
d6 = 1+6 = 7,
d7 = 2+6 = 8.
– остаточно позначається вершина позначкою .
IV I* = {1,2,3,4}, ω(I*) = {5,6,7}.
d5 = min(1+5,3+1,2+4) = 4,
d6 = 1+6 = 7,
d7 = 2+6 = 8.
– остаточно позначається вершина позначкою .
V I* = {1,2,3,4,5}, ω(I*) = {6,7,8}.
d6 = min(1+6,4+1) = 5,
d7 = min(2+6,4+3) = 7,
d8 = 4+5 = 9.
– остаточно позначається вершина позначкою .
VI I* = {1,2,3,4,5,6}, ω(I*) = {7,8}.
d7 = min(2+6,4+3) = 7,
d8 = min(5+2,4+5) = 7.
– остаточно позначається вершина позначкою .
Тут ми одержали дві однакові позначки. В цьому випадку остаточно позначаємо вершину з меншим номером.
VII I* = {1,2,3,4,5,6,7}, ω(I*) = {8}.
d8 = min(7+4,5+2,4+5) = 7.
Остаточно позначаємо вершину позначкою .
Таким чином, довжина найкоротшого шляху в графі дорівнює 7. Зобразимо граф з позначками і покажемо найкоротший шлях з вершини до вершину .
Найкоротший шлях в графі:
.
Спосіб позначок можна застосувати і для знаходження найдовшого шляху в мережевому графі. При цьому в сусідні вершини (множина ω(I*)) будемо включати лише ті, для яких усі дуги, що ведуть в цю вершину, починаються в I* – множині остаточно позначених вершин.
Формула, за якою треба діяти в цьому випадку, має вигляд
На кожному кроці роботи алгоритма в якості остаточно позначеної вершини беремо вершину з максимальною позначкою.
Приклад. Знайти найдовший шлях у графі
d1 = 0 – остаточно позначена вершина позначкою .
d2 = 0+2 = 2,
d3 = 0+1 = 1.
– остаточно позначається вершина позначкою .
d3 = 0+1 = 1.
Остаточно позначається вершина позначкою .
d4 = max(0+4,2+3,1+2) = 5.
Остаточно позначається вершина позначкою .
d5 = max(2+4,5+1,1+5) = 6.
Остаточно позначається вершина позначкою .
d6 = max(1+6,6+1) = 7,
d7 = max(2+6,6+3) = 9.
Остаточно позначається вершина позначкою .
d6 = max(1+6,6+1) = 7,
Остаточно позначається вершина позначкою .
d6 = max(9+4,6+5,7+2) = 13.
Вершина остаточно позначається позначкою .
Це і є довжина найдовшого шляху в графі. Зобразимо цей шлях і позначимо вершини.
Найдовший шлях у графі
Довжина цього шляху дорівнює 13.
2.6 Мережевий граф та його розрахунок
У практиці дослідження операцій часто зустрічаються задачі планування різноманітних робіт. Під комплексом робіт (операцій) слід розуміти будь-яку задачу, для виконання якої необхідно здійснити велику кількість різноманітних робіт. Це може бути і будівництво споруди, корабля, літака або будь-якого іншого складного об’єкта, і розробка проекту цієї споруди, і навіть процес побудови планів реалізації проекту.
Для того, щоб створити план робіт по здійсненню великих і складних проектів, які складаються з великої кількості окремих досліджень і операцій, необхідно описати їх за допомогою математичної моделі. Таким засобом є мережева модель. Вона являє собою план виконання деякого комплексу взаємопов’язаних робіт (операцій), заданих в специфічній формі мережі, графічне зображення якої називається мережевим графом.
Головними елементами мережевого графа є події і роботи. Термін «робота» використовується в мережевому плануванні в широкому сенсі. По-перше – це дійсно робота – процес, на який потрібно витратити час і ресурси. Кожна така робота повинна бути конкретно описана.
По-друге – це чекання – процес, який не потребує затрат праці, але потребує часу (наприклад, процес сушки виробів, затвердіння бетону і т.п.)
По-третє – це залежність, або фіктивна робота. Вона показує, що можливість однієї роботи безпосередньо залежить від результатів іншої. Ця робота не потребує часу і ресурсів.
Подія – момент завершення деякого процесу (роботи), який відображає окремий етап виконання проекту. Подія може статися лише після того, як закінчаться усі роботи, що їй передують. Наступні роботи можуть початися лише тоді, коли подія здійсниться. Звідси витікає двоїстий характер події: для всіх робіт, що їй безпосередньо передують, вона є кінцевою, а для всіх робіт, які безпосередньо слідують за нею – початковою. При цьому вважають, що подія не має тривалості і здійснюється миттєво. Тому кожна подія, що включена до мережевої моделі, повинна бути повністю означена. Серед подій мережевої моделі виділяють окремо початкову і завершальну. Початкова подія не має попередніх робіт і подій, завершальна не має наступних подій і робіт. Події на мережевому графі відображаються вершинами графа, а роботи – дугами, що вказують зв’язок між роботами.
Таким чином, для побудови мережевого графа необхідно задати:
При побудові мережевого графа необхідно виконувати ряд правил.
Щоб уникнути цього,рекомендується ввести фіктивну подію і відповідно фіктивну роботу. Зауважимощо фіктивна робота відображається на графі пунктирною лінією. Тобто, зробити треба так
Одна з паралельних робіт (1,2’) замикається на фіктивну подію.
Фіктивні роботи і події необхідно вводити і в інших випадках. Один із них – відображення залежності подій, не пов’язаних з реальними роботами. Наприклад, роботи А і B можуть бути виконані незалежно одна від іншої, але за умовами виробництва робота B не може початися раніше, ніж закінчиться робота А. Ця обставина потребує введення фіктивної роботи С.
Другий випадок – неповна залежність робіт. Наприклад, робота С потребує для свого початку завершення робіт А і В, але робота D зв’язана лише з роботою В, а від роботи А не залежить. Тоді потрібно ввести фіктивну роботу Е і фіктивну подію 3’:
Введемо деякі числові характеристики мережевого графу.
Для будь-якої події позначимо через E(x) – найбільш ранній з можливих термінів настання події , а через L(x) – найпізніший термін настання події , який ще припускає своєчасне закінчення проекту.
Раніше було зауважено, що подія не може настати раніше, ніж завершаться всі попередні роботи. Якщо подія має декілька шляхів, що передують цій події, тобто шляхів від початкової події до -ї, то E(у) зручно знаходити за формулою
,
де txy – час виконання роботи (x,y).
Якщо подія має декілька наступних шляхів і, відповідно, декілька наступних подій , то найпізніший термін настання події зручно знаходити за формулою
.
З цих формул і означень випливає наступне:
E(x) – це довжина найдовшого шляху від початкової події до події ;
L(n)–L(x) – це довжина найдовшого шляху від події до завершальної події .
При розрахунку мережевих моделей цікавляться такими питаннями.
RП(x,y) = L(y)–E(x)– txy.
RВ(x,y) = E(y)–E(x)– txy.
RН(x,y) = E(y)–L(x)– txy.
Зауважимо, що має місце очевидне співвідношення
RН(x,y) ≤ RВ(x,y) ≤ RП(x,y).
Далі дамо наступне означення. Операція називається критичною, якщо будь-яка затримка в її виконанні призводить до затримки виконання всього проекту (тобто повний резерв часу цієї операції дорівнює нулю).
Для некритичних операцій можлива затримка, що не перевищує її повного резерву. Шлях, що складається тільки з критичних операцій, називається критичним шляхом.
Приклад. Розглянемо проект будівництва житлового будинку (за приведеною нижче таблицею).
|
Етап |
Робота, що виконується |
Необхідний час |
Попередні етапи |
|
А |
Підготовка будмайданчика |
1 |
- |
|
Б |
Споруждення фундамента |
3 |
А |
|
В |
Подводка магістральних ліній електро-, газо- і водопостачання |
2 |
А |
|
Г |
Монтаж вертикальних стін і перекрить |
6 |
Б |
|
Д |
Спорудження кровлі |
1 |
Г |
|
Е |
Укладання підлог |
2 |
Г |
|
Ж |
Установка дверей і вікон |
1 |
Г |
|
И |
Монтаж електропроводки |
1 |
В, Г |
|
К |
Монтаж систем опалення, водо- і газопостачання |
2 |
В, Г |
|
Л |
Установка сантехніки |
1 |
К |
|
М |
Оздоблювальні роботи |
4 |
Е, Ж, И, К |
Потрібно скласти:
Е(1) = 0 – проект починається з нульового моменту часу.
Е(2) = Е(1) + 1 = 0 + 1 = 1.
Е(3) = Е(2) + 3 = 1 + 3 = 4.
Е(4) = Е(3) + 6 = 4 + 6 = 10.
Е(5) = max (Е(2)+2, Е(4)+0) = max (1+2, 10+0) = 10.
Е(6) = Е(5) + 2 = 10 + 2 = 12.
Е(7) = Е(4) + 2 = 10 + 2 = 12.
Е(8) = max (Е(4)+1, Е(5)+1, Е(6)+1) = max (10+1, 10+1, 12+1) = 13.
Е(9) = max (Е(4)+1, Е(8)+4) = max (10+1, 13+4) = 17.
Таким чином, найбільш ранній термін настання завершальної події дорівнює 17 одиниць часу.
Помітимо це на графі. Ці терміни вказані на графі як числа в квадратика х біля відповідної вершини.
Далі знайдемо найбільш пізній термін настання події.
L(9) = 17.
L(8) = L(9) – 4 = 13.
L(7) = L(8) – 0 = 13 – 0 =13.
L(6) = L(8) – 1 = 12.
L(5) = min( L(8) – 1, L(6) – 2) = min( 13 – 1, 12 – 2 ) = 10.
L(4) = min(L(9)–1, L(7)–2, L(8)–1, L(5)–0) = min(17–1, 13–2, 13–1,10) = 10.
L(3) = L(4) – 6 = 10 – 6 = 4.
L(2) = L(3) – 3 = 4 – 3 =1.
L(1) = L(2) – 1 = 1 – 1 =0.
На графі ці терміни позначимо цифрами у колах біля кожної вершини.
Критичні операції – це операції (1,2), (2,3), (3,4), (4,5), (5,6), (6,8), (8,9) і відповідно це і є критичний шлях у графі.
2.7 Задача про максимальну течію в мережі
Означення.
Наприклад. Маємо граф
Розглянемо такі розбивальні множини його ребер:
З цих розбивальних множин розрізом будуть лише {u1, u2} і {u3, u6, u7, u8}.
Розглянемо орієнтований граф, де вага дуги сij > 0 – це пропускна спроможність дуги.
Пропускна спроможність розрізу – це сума пропускних спроможностей дуг, що утворюють розріз.
Мінімальний розріз – це розріз з мінімальною пропускною спроможністю.
Приклад. Маємо орієнтований граф
Розглянемо декілька розрізів цього графа і обчислимо пропускні спроможності цих розрізів.
Розріз R1: (1,4), (2,4), (3,4)
с14=1 с24= 4 с34=2.
Пропускна спроможність розрізу R1 дорівнює 1+ 4 + 2 = 7.
Розріз R2: (1,2), (1,4), (1,3)
с12=3 с14=1 с13= 5.
Пропускна спроможність розрізу R2 дорівнює 3 + 1+ 5 = 9.
Розріз R3: (1,2), (1,4), (2,3), (3,2), (3,4)
с12=3 с14=1 с23= 3 с32= 4 с34= 2.
Пропускна спроможність розрізу R3 дорівнює 3 + 1+ 3 + 4 + 2 = 13.
Розріз R4: (1,3), (3,2), (2,3), (1,4), (2,4)
с13=5 с32= 4 с23= 3 с14=1 с24= 4.
Пропускна спроможність розрізу R4 дорівнює 5 + 4 + 3 +1 + 4 = 17.
Дамо деякі означення.
Будемо вважати, що в мережі задано течію, якщо:
Таким чином, течія в проміжних вершинах нічого не лишає і приносить на вихід стільки одиниць товару (інформації), скільки вийшло з входу. Ця кількість і є величина течії.
Величина течії в одній і тій же мережі може бути різною.
Наприклад, розглянемо орієнтований граф
Таким чином, через даний граф пройшла течія, що дорівнює 5 одиниць продукту: f = 5.
2) f12 = 5
f14 = 2 .
Таким чином, через даний граф пройшла течія, що дорівнює f = 3 + 2 + 2 = 7 одиниць продукту.
3) f13 = 3 ,
f12 = 5 ,
f14 = 2 .
Таким чином, через даний граф пройшла течія, що дорівнює
f = 3 + 5 + 2=10 одиниць продукту.
Задача про максимальну течію складається з того, щоб знайти течію найбільшої величини, яку можна пропустити через задану мережу.
Теорема Форда – Фалкерсона.
Для кожної мережі величина максимальної течії дорівнює пропускній спроможності мінімального розрізу.
Введемо в розгляд деякі поняття.
Дуги графа можна віднести до двох категорій:
- дуги, в яких течію можна збільшити, − це ненасичені дуги, їх об’єднаємо в множину І – множина ненасичених дуг;
- дуги, в яких течію можна зменшити, − це невільні дуги, їх об’єднаємо
в множину R – множина обернених дуг.
Дуга, в якій течія дорівнює нулю, називається вільною. В такій дузі течію зменшити не можна.
Дуга може належати і множині І, і множині R одночасно.
Введемо в розгляд величини:
На рисунку маємо ланцюг, що збільшує, він містить прямі дуги (1,2), (2,3), (3,4). Течію з вершини 1 в вершину 4 можна збільшити на min(i(1,2), i(2,3), i(3,4)) = min (3;2;1) = 1;
2) r(x,y) − максимальна величина, на яку можна зменшити течію в дузі
На рисунку маємо ланцюг, що збільшує, який містить обернені дуги. Зменшення течії з вершини 4 до вершини 1 приводить до збільшення течії з вершини 1 до вершини 4. У мережі на рисунку течія з вершини 4 у вершину 1 може бути зменшена на min(r (2,1), r (3,2), r (4,3)) = min (1;2;1) = 1, і тим самим течію з вершини 1 у вершину 4 збільшимо на 1.
Сформулюємо алгоритм пошуку ланцюга, що збільшує.
Крок І Визначимо склад множин І і R. Зафарбуємо початкову вершину.
Крок ІІ Будемо зафарбовувати дуги і вершини відповідно до наведених нижче правил доти, поки або не буде зафарбована кінцева вершина, або
фарбування нових вершин стане неможливим.
Правило фарбування.
Якщо вершина х зафарбована, тоді фарбування вершини у і дуги (х,у) відбувається таким чином:
а) якщо дуга (х,у)І, то зафарбовується вершина у і дуга (х,у)
б) якщо дуга (у,х)R, тоді зафарбовується вершина у і дуга (у,х)
в) інших випадках вершина у і дуга (х,у) не фарбуються.
Можна довести, що, якщо кінцева вершина зафарбована, тоді в мережі знаходиться єдиний ланцюг з початкової вершини у кінцеву, який включає зафарбовані дуги (це ланцюг, що збільшує). Якщо кінцева вершина не зафарбована, тоді в мережі відсутні ланцюги з початкової до кінцевої вершини, що збільшують.
Зауваження.
Дуга фарбується лише тоді, коли одна з її вершин зафарбована, а інша ні. Отже не може бути зафарбована дуга, обидві вершини якої були раніше зафарбовані. Тому зафарбовані дуги не можуть утворювати цикл. Зафарбовані дуги утворюють дерево. Якщо зафарбовується кінцева вершина, то існує ланцюг з початкової вершини в кінцеву. Це і буде ланцюг, що збільшує, оскільки процедура фарбування гарантує, що прямі дуги цього ланцюга збільшують, а обернені – зменшують течію в мережі.
Далі розглянемо алгоритм пошуку максимальної течії у графі.
Ідея, що лежить в основі цього алгоритму Форда – Фалкерсона така: беремо деяку початкову течію з початкової в кінцеву вершину і за допомогою алгоритму пошуку ланцюга, що збільшує, виконуємо пошук такого ланцюга. Якщо він виявляється успішним, то течія вздовж знайденого ланцюга збільшується до максимально можливого значення. Потім знаходять новий ланцюг, що збільшує. Якщо на якомусь етапі цієї процедури ланцюг, що збільшує, знайти не вдається, виконання алгоритму закінчується, тобто знайдена течія з початкової до кінцевої вершини є максимальною.
Крок І Беремо будь-яку початкову течію з початкової до кінцевої вершини, наприклад, нульову.
Крок ІІ Сформуємо множини дуг І і R. На цих множинах застосуємо алгоритм пошуку ланцюга, що збільшує.
Якщо ланцюг, що збільшує, знайти не вдається, закінчуємо процедуру алгоритму. У протилежному випадку здійснюємо максимально можливе збільшення течії вздовж цього ланцюга і повертаємось до кроку ІІ.
Приклад. Знайти максимальну течію у графі при даних пропускних спроможностях дуг в мережі.
(1,2), (2,3), (3,5)
і(1,2) = 2 – 0 = 2 і(2,3) = 3 – 0 = 3 і(3,5) = 2 - 0 =2.
Через цей ланцюг можна пропустити течію, що дорівнює min( 2;3;2) = 2.
Течія в дугах даного ланцюга збільшується на дві одиниці.
Повертаємось до кроку ІІ.
(1,3), (2,3), (2,4), (4,5)
І R І І
і(1,3) = 3 – 0 = 3 r(2,3) = 2 і(2,4) = 4 - 0 = 4 і(4,5) = 1 - 0 = 1.
Тепер течія через мережу буде дорівнювати 2 + 1 = 3.
Це максимальна течія, тому що ланцюг, що збільшує, побудувати вже не можна, бо у кінцеву вершину ведуть дуги, що належать до множини R, у яких течію можна лише зменшувати.
Далі розглянемо метод знаходження максимальної течії в неорієнтованому графі.
Маємо неорієнтований граф.
Шляхів із А в В немає. Течія із А в В дорівнює 2 + 2 + 3 = 7.
Питання для самоперевірки
Задачі для самостійної роботи
1 Маємо граф
Побудувати матриці суміжності вершин графа, дуг графа і матрицю інцидентності орграфа.
2 Маємо граф
Побудувати матриці суміжності вершин і ребер не орграфа.
S=
Для цього графа:
а) обчислити кількість остовних дерев графа;
б) побудувати остовне дерево графа, мінімальне остовне дерево і максимальне остовне дерево;
5 Маємо граф
Для цього графа обчислити:
а) найкоротший шлях методом Дейкстри;
б) найкоротший та найдовший шлях методом поміток;
в) максимальну течію в графі.
6 Маємо проект будівництва спортивної споруди (за нижеподаною таблицею).
|
Етап |
Робота, що виконується |
Попередній етап |
Потрібний час (тиж) |
|
А |
Підготовка будмайданчика |
- |
1 |
|
Б |
Побудова фундаменту |
А |
3 |
|
В |
Підводка магістральних ліній електро- і водопостачання |
А |
2 |
|
Г |
Монтаж вертикальних стін |
Б |
4 |
|
Д |
Монтаж стріха |
Г |
2 |
|
Е |
Укладання дерев’яних перекриттів |
Г |
2 |
|
Ж |
Установка дверей та вікон |
Г |
1 |
|
З* |
Монтаж електрообладнання |
Д |
1 |
|
І |
Монтаж системи опалення |
В, Г |
1 |
|
К |
Установка сантехніки |
В, Г |
1 |
|
Л |
Оздоблювальні роботи |
З*, І, К |
3 |
За даними проекту побудувати мережевий граф, для кожної роботи (операції) розрахувати повний вільний та незалежний резерви часу, побудувати критичний шлях у графі.
Глава 3 МЕТОД ГІЛОК ТА МЕЖ
3.1 Основні поняття
Цей метод буде застосовано для розв’язання задачі про рюкзак та задачі комівояжера.
Сформулюємо основні ідеї метода гілок та меж.
Деяка функція має бути мінімізована f(x)→min, де Х складається з дискретних точок (наприклад, цілочисельних). Це задача нелінійного програмування, навіть якщо f(x) – лінійна функція.
Якщо множина Х складається з невеликої кількості елементів, то можливий перебір всіх елементів, якщо кількість елементів множини Х є великою, то потрібен метод спрямованого перебору. Одним з таких методів є метод гілок та меж . В цьому методі треба вказати дві речі:
Множину Х розбиваємо на дві – три частини
Х11, Х12, Х13 – кінцеві множини 1-го кроку.
На другому кроці за деякою ознакою вибираємо одну з множин 1-го кроку і розбиваємо її. Одержані множини разом з нерОзгалуженими множинами другого кроку називаються кінцевими множинами другого кроку.
Для системи оцінок множин запроваджується функція ρ(Х*), Ця функція повинна задовольняти наступним вимогам:
з цього випливає, що при розбитті оцінка ρ(Х) не може спадати;
Ми розглянемо реалізацію метода гілок та меж, яка називається повне галуження.
Для цього на першому кроці обчисляємо оцінку множини Х − ρ(Х) за означеним правилом. Після цього обчислюється оцінка ρ для підмножин Х11, Х12. Зі знайдених оцінок ρ(Х11), ρ(Х12) обирається найменша, і далі галузиться та множина, для якої оцінка ρ найменша. Після цього процедура повторюється.
Далі галузимо ρ(Х12):
З трьох множин Х11, Х21, Х22 вибираємо ту, для якої оцінка є найменшою. Галузимо доти, поки не доберемося до множини, що складається з однієї
точки, оцінок кінцевих множин останнього кроку.
3.2 Задача про рюкзак
Є n предметів. Відомі вага p кожного i вартість c, i =. Потрібно покласти у рюкзак сукупність предметів з мінімальною сумарною вагою за умови, що вартість вантажу не менша за С. Введемо в розгляд змінну :
Тоді одержуємо задачу:
Це повна постановка задачі про рюкзак. Опишемо алгоритм галуження i зв'язану з ним систему оцінок. Для того, щоб обчислити оцінку ρ(х), треба розв’язати задачу лінійного програмування (неперервну), тобто розв’язуємо свою задачу, але умову замінимо на 0 ≤ хі ≤ 1. Таким чином
ρ(х) =min f(x) за умови 0 ≤ хі ≤ 1. За умови 0 ≤ хі ≤ 1 min f(x) може тільки зменшитися, тобто ρ(x) ≤ minf (x), і вимога на ρ(х) виконана.
Складаємо відношення – це відносна вага предмета на одиницю вартості. В першу чергу будемо класти в рюкзак ті предмети, що мають min. Умова 0 ≤ хі ≤ 1 означає, що маємо право дробити предмети. При цьому множина припустимих значень збільшується, a min функції може лише зменшуватися.
Приклад. Маємо п’ять предметів, які треба покласти в рюкзак за умови, що вартість предметів у рюкзаку
|
і |
1 |
2 |
3 |
4 |
5 |
|
|
сі |
10 |
5 |
16 |
4 |
6 |
вартість |
|
рі |
6 |
2 |
5 |
8 |
4 |
Вага |
Математична модель задачі така: ми шукаємо min ваги
f(x) = 6х1 + 2х2 + 5x3 + 8х4 +4х5 → min
за умови, що вартість вантажу
10х1 + 5x2 + l 6x3 + 4x4 + 6x5≥ 30. (1)
Коли задача буде розв'язана, ми одержимо такий граф-дерево:
Зробимо оцінку планів задачі (1), тобто будуємо оцінку ρ.
(2)
Це задача (2) лінійного програмування. Розв'яжемо її.
Розташовуємо предмети в порядку зростання i відповідно перенумеруємо предмети.
|
і |
1 |
2 |
3 |
4 |
5 |
|
поперед. ном. |
3 |
2 |
1 |
5 |
4 |
|
сі |
16 |
5 |
10 |
6 |
4 |
|
рі |
5 |
2 |
6 |
4 |
8 |
Задача (2) тоді має вигляд (з новою нумерацією предметів):
Якщо візьмемо перший предмет, тоді його вартість 16<30; якщо перший і другий, то їх вартість 16+5=21<30. Якщо візьмемо перший, другий і третій предмети, то їх вартість буде 16 + 5 + 10=31, 31 > 30 на одиницю. Яку частину третього предмета треба взяти? Одиниця – це вартості третього предмета, тобто треба взяти предмета. Тоді опорний план задачі (2): (1; 1; 0,9; 0; 0); ρ(х) = 5 + 2 + б*0,9 = 12,4.
Будемо галузити множину опорних планів по третій координаті, оскільки вона не ціла. Розбиваємо множину Х, тобто сукупність планів задачі (2),на дві підмножини.
З’являються задачі (3) і (4):
(3)
(4)
Для задачі (3) третього предмета немає.
1пр. + 2пр. + 4пр. 16 + 5 + 6 = 27 < 30,
1пр. + 2пр. + 4пр.+ 5пр. 16 + 5 + 6 + 4 = 31 > 30.
П’ятий предмет перевищує вартість на одиницю, тобто на 1/4 його вартості, тоді потрібно взяти 3/4 п’ятого предмета. Опорний план для задачі (3) наступний: (1; 1; 0; 1; 3/4),
ρ(х11) = 5 + 2 + 4 + 8*(3/4) = 17.
Розв’язуємо задачу (4):
1 пр. + 2 пр. 16 + 5 = 21>20.
Вже другий предмет перевищує вартість на одиницю, тобто на 1/5 його вартості; треба взяти 4/5 другого предмета. Опорний план (1;4/5, 1; 0; 0),
ρ(х12)= 5 + 2*(4/5)+6+0=12,6.
Із ρ(х11) i ρ(х12) вибираємо min, це ρ(х12), і далі галузимо х12 за другою координатою:
З'являються задачі (5) i (6):
(5)
(6)
Розв’язуємо задачу (5).
1 пр.+ 4 пр. 16 + 6 = 22 > 20. Четвертий предмет перевищує вартість на 2 одиниці або на його вартості, тобто потрібно взяти четвертого предмету. Опорний план такий: (1; 0; 1; ;0),
ρ (х21) = 5+6+4*=13.
Розв’язуємо задачу (6).
1 пр. 16 > 15. Перший предмет перевищує вартість на 1 одиницю, тобто на своєї вартості треба взяти від першого предмету. Опорний план (6) задачі (; 1; 1; 0: 0), ρ(х2,2) =5*+ 2 + 6 = 8 + = 12.
Кінцеві множини цього кроку X11, Х21, Х22
min ρ = ρ(X22) = l2.
Далі треба галузити Х22 за першою координатою:
Задачі (7) i (8):
(7)
(8)
Розв’яжемо задачу (7).
4пр.+5 пр. с=10<15 множина планів порожня. Тоді відповідну оцінку вважаємо рівною ∞, тобто ρ(X31) = ∞. Така множина галуженню не підлягає.
Розв’язуємо задачу (8). Розв'язок цієї задачі (1;1; 1; 0; 0), ρ(X32) = 13.
Кінцеві множини третього кроку Х11, X21, X31, X32; min ρ = ρ(X3,2) = l3.
План задачі (8) цілочисельний, тому множина Х3,2 розбивається таким чином: одноелементна підмножина Х4,1 = {1,1,1,0,0} – одна точка, i X4,2=X3,2\X4,1. Вважаємо при цьому ρ(Х4,1) = ρ(Х4,2) =ρ(Х3,2) =13. Елемент Х4,1 є розв'язком задачі.
Оптимальне значення цільової функції 13. Якщо перейти до старої
нумерації, тоді в рюкзак треба покласти 3,2 і 1 предмети.
3.3 Задача комівояжера
Далі розглянемо іншу задачу, яку можна розв’язати за допомогою методугілок та меж.
Постановка задачі. Маємо n міст, комівояжер повинен відвідати кожне з міст тільки один раз і повернутися в перше. Його маршрут повинен мінімізувати сумарну довжину ( або вартість) пройденого шляху. В теорії графів такий шлях називається гамільтоновим контуром. Тобто задача комівояжера – це знаходження гамільтонового контуру мінімальної довжини.
Мінімізується функція де Х – множина всіх припустимих маршрутів, тобто гамільтонових контурів, cij – вага дуги (i,j) (довжина або вартість шляху). Будемо вважати крім того, що cii = ∞,
cij = ∞, якщо немає шляху з пункту і в пункт j.
Сформулюємо загальну схему розв’язання задачі.
Маємо матрицю С = (cij ), де cij – вага дуги( i,j). Віднімаємо з усіх елементів кожного рядка матриці С мінімальний елемент цього рядка, далі в матриці, що одержана, від усіх елементів кожного стовпця віднімаємо мінімальний елемент цього стовпця. Матриця, що виникає, називається зведеною, позначимо її , крім того позначимо через – мінімум в рядку і; – мінімум у стовпці j; – назвемо константами зведення, i,j=1,2,…,n.
Для будь-якого гамільтонового контуру виконується наступне:
У якості ρ(х) вибираємо , і тоді виконуються вимоги, які накладаються на оцінку ρ(х), ρ(х) ≤ f(x).
Після операції зведення довжина всіх гамільтонових шляхів зменшуються на одну й ту ж величину, тому оптимальний гамільтонів контур, знайдений з використанням зведеної матриці, буде оптимальним і для початкової матриці.
Множину X ми повинні галузити. Множина Х11 складається з уcіx гамільтонових контурів із X, що не містять деякої дуги (r,s). Множила Х12 складається з ycix гамільтонових контурів з X, що містять дугу (r,s).
Правило вибору дуги (r,s) полягає в наступному: оцінку ρ(Х12) прагнуть зробити меншою, оцінку ρ(Х11) – більшою з метою збільшити ймовірність подальшого галуження множини Х12. Бажання зменшити оцінку ρ(Х12) означає, що кандидатами на вибір дуги (r,s) можуть бути лише ті дуги, яким у зведеній матриці відповідають нульові елементи. Їх може бути декілька. Тоді знайдемо суму констант зведення кожного з нульових елементів матриці . Позначимо цю суму для елемента (i,j) через Θ(і, j). Як дугу (r,s) вибираємо таку, для якої оцінка знизу максимальна, тобто Θ(r,s) =max Θ (i,j).
Наступний етап – побудова зведених матриць i обчислення оцінок знизу.
Замінимо в матриці нульовий елемент, що відповіднє дузі (г,s), на ∞. Нову матрицю позначимо С1. Зведена матриця відстаней для гамільтонових контурів із Х11, що не містять дуги (r,s), одержується зведенням матриці C1. Сума констант зведення для матриці С1 дорівнює Θ(r,s).
Оцінка знизу для функції f(x) на множині Х11 така: ρ(Х11) = ρ(Х) + Θ(r,s).
Гамільтонові контури з Х12 містять дугу (r,s). Викреслимо в матриці рядок i стовпець, що відповідають дузі (рядок відповідає місту r і стовпець відповідає місту s), Елемент, що відповідає дузі (s,r), замінюємо на ∞ (назад із s в r їхати не можна).
Отриману матрицю позначимо С2 (її розмір менше, ніж у попередньої). Зведена матриця відстаней для контурів з X12 одержується зведенням матриці С2. При цьому оцінка знизу ρ(Х12) = ρ(Х) + τ(r,s), де τ(r,s) – сума констант зведення матриці С2.
Якщо в кожному рядку і стовпцю матриці С1 або С2 виявилося лише по одному елементу, відмінному від ∞, тоді множина X11 (або Х12) містить єдиний маршрут, довжина якого дорівнює ρ(Х11) (або ρ(Х12)).
Приклад. ( Задача комівояжера).
Є 5 міст. Дана матриця відстаней (вартості):
Потрібно знайти гамільтонів контур найменшої довжини.
Розв’язання.
І етап – операція зведення.
.
ІІ етап – операція галуження.
Галуження треба проводити за дугою (5,3):
ІІІ етап – побудова зведених матриць.
.
Кінцеві множини першого кроку Х11 і Х12. Галуженню підлягає Х12 ( з мінімальною оцінкою).
Зведемо матрицю С2:
Галуження буде за дугою (4,2).
Галуженню підлягає Х22 за дугою (3,4):
Галуженню підлягає Х32 за дугою (2,1):
Побудуємо отримане дерево:
Запишемо гамільтонів контур:
f(x) = 6+7+1+10+10 =34.
Питання для самоперевірки
Задачі для самостійної роботи
Маємо 5 предметів, де − вартість i-го предмета, − вага i-го предмета.
Дані про предмети наведені в таблиці:
Варіант А
С=40
Варіант Б
C=45
Варіант А Варіант Б
Глава 4 ЗАДАЧА ПРО ПРИЗНАЧЕННЯ (ВИБІР)
Постановка задачі. Є n різноманітних робіт A, A, ... , A i n механізмів B, В, ... , В, кожний з яких може виконувати будь-яку роботу. Продуктивність механізму Bі при виконанні роботи Aj позначимо с (i,j=l,2„..,n).
Вимагається так розподілити механізми за роботами, щоб сумарний ефект від їхнього використання був максимальним. Це задача вибору.
Формально задача вибору записується так. Необхідно вибрати таку послідовність елементів з матриці
, щоб їх сума була максимальною, при цьому з кожного рядка і стовпця матриці С був вибраний тільки один елемент.
Опис алгоритму угорського методу.
На підготовчому етапі знаходимо найбільший елемент j-гo стовпчика (βj), i всі елементи цього стовпця послідовно віднімаємо від максимального. Цю операцію проводять над усіма стовпцями матриці С (l≤j≤n).
У новій матриці знаходимо найменший елемент αi в кожному і-му рядку i віднімаємо його від елементів i-ого рядка, (1≤i≤n). У результаті одержуємо матрицю з невід’ємними елементами, в кожному стовпцю i рядку якої є принаймні один нуль.
Задача максимального вибору в матриці С звелася до задачі мінімального вибору в матриці .
Вирішальну роль в подальшому відіграє поняття незалежних нулів. Це нульові елементи матриці ,. будь-які два з яких належать до різних рядків i різних стовпців. Незалежні нулі позначимо 0*.
Спочатку в матриці знаходимо всілякі незалежні нулі і вилучаємо знаком "+" стовпці, що містять 0*.
При цьому, якщо таких незалежних нулів виявилося рівно n, тоді задача вирішена і елементи, що стояли в матриці С на місцях 0*, є шуканими.
У протилежному випадку, якщо число незалежних нулів менше за n, переходимо до наступного кроку алгоритму. Для полегшення опису наступних кроків алгоритму намалюємо його блок-схему з описом блоків.
І Вилучаємо знаком "+" стовпці, що містять незалежні нулі 0*.
ІІ Пошук невилученого нуля (тобто нуля, що стоїть в непозначеному знаком "+" рядку або стовпцю); невилучений нуль позначимо 0’.
ІІІ Пошук 0* в рядку з 0’.
ІV Вилучаємо знаком "+" рядок з 0’ i знищуємо "+" над стовпцем з 0*.
V Будуємо ланцюжок від знайденого 0’ по стовпцю. до 0*, від цього 0* по рядку до 0’ i т.д. Якщо в одному стовпцю. з 0’ немає 0*, тоді ланцюжок складається з одного 0’. Ланцюжок завжди починається з 0’ і закінчується 0’.
VI Знищуємо в ланцюжку всі "*" і ставимо "*" замість"‘".
VII Знищуємо в матриці всі "‘" і всі знаки вилучення (стовпців і рядків).
VIII Знаходимо найменший елемент серед невилучених елементів (що потрапили в невилучені рядки i стовпці). Позначимо його h>0.
ІХ Віднімаємо h з елементів невилучених рядків і додаємо h до елементів вилучених стовпців.
Після закінчення роботи цього алгоритму одержуємо матрицю, в якій є n незалежних нулів.
Приклад. Дана матриця продуктивностей
Розв’язати задачу про вибір (призначення).
Розв’язання. На підготовчому етапі знаходимо найбільший елемент j-гo стовпчика (βj), i всі елементи цього стовпця послідовно віднімаємо від максимального. Цю операцію проводять над усіма стовпцями матриці С (l≤j≤n).
У новій матриці знаходимо найменший елемент αi в кожному і-му рядку i віднімаємо його від елементів i-го рядка, (l≤j≤n). У даному випадку всі мінімальні елементи рядків дорівнюють нулю, тому отримана матриця є матрицею. Далі діємо за алгоритмом.
Число незалежних нулів менш 5
Є невилучений
нуль
У рядку 0’ немає 0*, тобто переходимо до етапу V, і будуємо ланцюжок.
Є 0* в рядку з 0’, здійснюємо етап ІV, а після цього повертаємось до етапу ІІ
Переходимо до етапів VІ і VІІ:
Знову переходимо до етапу І, помітивши, що число незалежних нулів збільшилось на одиницю:
− тут пройдені етапи ІІ, ІІІ, ІV. Переходимо до етапу ІІ.
Тепер уже невилученихнулів немає. . Переходимо до етапу VІІІ. Тут h=1 і переходимо до етапу ІХ. В результаті одержуємо матрицю:
Переходимо до етапу ІІ. Далі діємо за алгоритмом.
Отже, одержуємо матрицю:
.
Таким чином, у первісній матриці треба вибрати елементи с12. с25, с31, с43, с54: 4+3+4+2+2=15.
Питання для самоперевірки
Задачі для самостійної роботи
Розв’язати задачу про призначення, якщо задана матриця продуктивностей.
1
2
Глава 5 ТЕОРІЯ ІГОР
Розділ теорії дослідження операцій, який вивчає математичні моделі прийняття оптимальних рішень у конфліктних ситуаціях, називається теорією ігор.
Математична модель конфліктної ситуації називається грою, сторони, що беруть участь у конфлікті – гравцями, а результати конфлікту – виграшем. Для кожної формалізованої гри вводяться правила, тобто система умов, що визначає:
Як правило, виграш (програш) може бути заданий кількісно. Наприклад, можна оцінити програш нулем, виграш – одиницею, а нічию − .
Гра називається парною, якщо в ній беруть участь два гравця, множинною, якщо кількість гравців більше двох. Будемо розглядати тільки парні ігри. В них беруть участь лише два гравця A і B, інтереси яких протилежні, а під грою будемо розуміти ряд дій зі сторони гравців A і B.
Гра називається грою з нульовою сумою, якщо виграш одного з гравців дорівнює програшу другого, тобто для повного задання результату гри достатньо вказати величину виграшу одного з них. Якщо позначити a – виграш одного з гравців, b – виграш другого, то для гри з нульовою сумою b = - a, тобто достатньо розглядати, наприклад, a.
Вибір і здійснення однієї з передбачених правилами дій називається ходом гравця. Ходи можуть бути особистими і випадковими. Особистий хід – це свідомий вибір гравцем однієї з можливих дій (наприклад, хід в шаховій грі). Випадковий хід – це випадково вибрана дія (наприклад, вибір карти з колоди). У подальшому будемо розглядати тільки особисті ходи.
Стратегією гравця називається сукупність правил, що визначають вибір його дій при кожному особистому ході в залежності від ситуації, що склалася. Гра називається скінченою, якщо кожний гравець має скінчену кількість стратегій, і нескінченною – в протилежному випадку.
Для того, щоб розв’язати гру або знайти розв’язок гри, потрібно для кожного гравця вибрати стратегію, яка задовольняє умові оптимальності, тобто один з гравців повинен одержати максимальний виграш, коли другий дотримується своєї стратегії. В той же час другий гравець повинен мати мінімальний програш, якщо перший дотримується своєї стратегії. Оптимальні стратегії повинні також задовольняти умові стійкості, тобто будь-якому з гравців повинно бути невигідно відмовитись від своєї стратегії в цій грі.
Якщо гра повторюється достатньо багато разів, то гравців може цікавити не виграш і програш в кожній конкретній партії, а середній виграш (програш) у всіх партіях.
Метою теорії ігор є визначення оптимальної стратегії для кожного гравця. При виборі оптимальної стратегії природно передбачати, що обидва гравці ведуть себе розумно з точки зору своїх інтересів. Важливе обмеження теорії ігор – єдиність виграшу як показника ефективності, в той час як у більшості реальних економічних задач може бути більше одного показника ефективності. Крім того, в економіці, як правило, виникають задачі, в яких інтереси партнерів
не обов’язково антагоністичні.
5.1 Платіжна матриця. Нижня та верхня ціна гри
Розглянемо парну кінцеву гру. Нехай гравець А має m особистих стратегій, які позначають А1, А2,…, Аm. У гравця В є n особистих стратегій, позначимо їх В1, В2,…, Вn. В цьому випадку кажуть, що гра має розмір . В результаті вибору гравцями будь-якої пари стратегій Аi і Вj (i = 1, 2,…, m; j = 1, 2,…, n) однозначно визначається результат гри, тобто виграш aij гравця А (додатній або від’ємний) і програш (–aij) гравця В. Припустимо, що значення aij відомі для будь-якої пари стратегій (Аi, Вj). Матриця Р = (aij), (i = 1, 2,…, m; j = 1, 2,…, n) називається платіжною матрицею, або матрицею гри. Загальний вигляд такої матриці:
.
Приклад. Гра «вірю – не вірю». Правила гри: Гравець А має на руках 8 карт – 4 тузи і 4 двійки. Він витягує карту, не показуючи її гравцю В, і говорить: «туз» (при цьому він може збрехати, а може сказати правду). Якщо гравець В вірить, то він сплачує гравцю А 1 грн. Якщо гравець В не вірить, то гравець А показує карту і якщо це дійсно «туз», то гравець В платить гравцю А 2 грн. Якщо це «двійка», то гравець А сплачує гравцю В 2 грн. Якщо гравець А витягує «двійку» і говорить правду, то він сплачує гравцю В 1грн.
Розв’язання. У гравця А є дві стратегії: А1 – правда, А2 – брехня. У гравця В є дві стратегії: В1 – вірю, В2 – не вірю. Складемо матрицю платежів. Вона має вигляд
.
Знайдемо елементи матриці aij.
Нагадаємо, що ймовірність витягти «туз» дорівнює 0,5 і ймовірність витягти «двійку» теж дорівнює 0,5. При цьому зауважимо, якщо гравець А твердить, що він витягнув «двійку», то гравцю В не має сенсу не вірити, і якщо гравець витягнув «туз», то йому немає сенсу брехати. Тоді при стратегіях
А1В1 : а11 = 0,5·1+0,5·(-1) = 0,
А1В2 : а12 = 0,5·2+0,5·0 = 1,
А2В1 : а21 = 0,5·0+0,5·1 = 0,5,
А2В2 : а22 = 0,5·0+0,5·(-2) = -1.
Таким чином, маємо наступну платіжну матрицю:
.
Далі розглянемо гру з матрицею Р = (aij), (i = 1, 2,…, m; j = 1, 2,…, n) і визначимо найкращу серед стратегій А1, А2,…, Аm.
Наведемо міркування гравця А. Вибираючи стратегію Аi, гравець А повинен розраховувати, що гравець В відповість на неї стратегією Вj, для якої виграш для гравця А є мінімальним.
Позначимо через i – найменший виграш гравця А при виборі ним стратегії Аi для всіх можливих стратегій гравця В (найменше число в і-му рядку платіжної матриці), тобто . Серед всіх чисел і (i = 1, 2,…, m) виберемо найбільше . Назвемо – нижньою ціною гри, або максиміном. Це гарантований виграш гравця А при будь-якій стратегії гравці В.
.
Стратегія, що відповідає максиміну, називається максимінною стратегією.
Гравець В зацікавлений у тому, щоб зменшити виграш гравця А. Вибираючи стратегію Вj, він враховує максимально можливий при цьому виграш для А. Позначимо . Серед всіх чисел j виберемо найменше . І назвемо – верхньою ціною гри, або мінімаксом. Це гарантований програш гравця В.
Стратегія, що відповідає мінімаксу, називається мінімаксною стратегією.
Встановимо зв’язок між і . Нехай досягається на r-й стратегії (тобто = r), а на стратегії s (тобто =s). На перетині r-го рядка s-го стовпця знаходиться елемент ars. Тоді ≥ ars ≥ . Тобто ≤ .
Якщо верхня та нижня ціни гри співпадають, то їх спільне значення позначається v і називається чистою ціною гри, або ціною гри. В такому випадку в платіжній матриці існує елемент ars , який дорівнює ціні гри, тобто
= ars = = v.
При цьому гравець А має максимальний гарантований виграш v, який не залежить від поведінки гравця В, якщо застосує стратегію Аr, а гравець В досягне мінімального програшу v (незалежного від поведінки гравця А), якщо застосує стратегію Вs. Кажуть, що розв’язок гри має стійкість, тобто, якщо один з гравців дотримується своєї оптимальної стратегії, то для другого не може бути вигідним відхилення від своєї оптимальної стратегії. Елемент ars у цьому випадку називається сідловою точкою.
Позначимо через А* і В* – пару чистих стратегій, на яких досягається розв’язок гри в задачі з сідловою точкою (А*= Аr, В*= Вs). Введемо в розгляд функцію виграшу у першого гравця на кожній парі стратегій: F(Аi, Вj) = aij.
Тоді з умови оптимальності у сідловій точці виконується подвійна нерівність:
F(Аi, В*) ≤ F(А*, В*) ≤ F(А*, Вj),
1 ≤ i ≤ m, 1 ≤ j ≤ n.
Дійсно, вибір стратегії А* першим гравцем при оптимальній стратегії В* другого гравця максимізує мінімальний можливий виграш:
F(А*, В*) ≥ F(Аi, В*),
а вибір стратегії В* другим гравцем при оптимальній стратегії А* першого гравця мінімізує максимальний програш:
F(А*, В*) ≤ F(А*, Вj).
Приклад. Визначити нижню і верхню ціну гри, що задана платіжною матрицею:
У даному прикладі
= max(i) = 3 ,
= min(j) = 3,
= = 3.
Таким чином, А3, В3 – урівноважені стратегії. Гра має сідлову точку а32 і ціну гри v = 3.
5.2 Розв’язання гри у мішаних стратегіях
Якщо гра не має сідлової точки, то застосування чистих стратегій не дає оптимального розв’язку гри. В такому випадку одержати оптимальний розв’язок можна випадковим чином перебираючи чисті стратегії.
Мішаною стратегією SА гравця А називається застосування чистих стратегій А1, А2,…, Аm з ймовірностями p1, p2,…, pm. При цьому очевидно, що .
Мішані стратегії гравця А записують у вигляді матриці
,
або .
Аналогічно, мішані стратегії гравця В позначаються так:
,
або .
Чисті стратегії можна вважати окремим випадком мішаних у випадку, коли чистій стратегії відповідає ймовірність 1, а ймовірність інших стратегій дорівнює 0.
На основі принципу мінімакса визначається оптимальний розв’язок (або розв’язок) гри: це пара оптимальних стратегій , які мають наступні властивості: якщо один з гравців додержується своєї оптимальної стратегії, то іншому не може бути вигідним відходити від своєї. Виграш, що відповідає оптимальній стратегії (ціна гри v), задовольняє нерівності
≤ v ≤ .
Введемо в розгляд функцію виграшу
.
Гравець А орієнтується на найгірше, тобто на втрати, що дорівнюють мінімуму функції виграшу F(SA,SB) по всім стратегіям гравця В, тобто грає роль i.
Тоді найкращою стратегією для гравця А є та, на якій буде досягнуто – це грає роль .
Аналогічно для гравця В найкращою стратегією буде та, на якій буде досягнуто – це грає роль .
Виникає питання: чи існують оптимальні мішані стратегії гравців , на яких гравець А має найбільший виграш і відповідно гравець В – найменший програш.
На це питання дає відповідь основна теорема теорії ігор – теорема Неймана.
Будь-яка матрична гра має ціну v в мішаних стратегіях, яка досягається у процесі використанні оптимальних мішаних стратегій , тобто
.
З цієї теореми випливають наступні висновки:
Теорема 1 Стратегії оптимальні тоді і тільки тоді, коли виконується умова
.
Тобто, якщо гравець В застосовує оптимальну стратегію , то кращою відповіддю на це є застосування гравцем А стратегії . І якщо гравець А застосовує оптимальну стратегію , то кращою відповіддю на це є застосування гравцем В стратегії .
Перш ніж сформулювати другу теорему, що випливає з основної теореми, дамо наступне означення.
Стратегії, які входять до складу оптимальних мішаних стратегій з ненульовими ймовірностями, називаються активними стратегіями.
Теорема 2 Якщо гравець В застосовує оптимальну мішану стратегію , а гравець А застосовує активну стратегію Аі, то . Аналогічно,
.
5.3 Ігри 2x2
Така гра є найпростішим випадком гри. Якщо така гра має сідлову точку, то оптимальний розв’язок – це пара чистих стратегій, що відповідають цій точці.
Гра, в якій відсутня сідлова точка, відповідно до основної теореми теорії ігор, має оптимальний розв’язок, який визначається парою мішаних стратегій , .
Нехай платіжна матриця має вигляд
.
Для того, щоб знайти оптимальні мішані стратегії , скористуємося теоремою 2.
,
.
Ми одержали систему рівнянь для визначення p* і v. Аналогічним чином шукаємо стратегію :
.
Звідси вже можна знайти q* і шукати вже не потрібно.
Приклад. Розв’язати гру «вірю – не вірю».
Правила цієї гри розглянуті в 6.1 і там же знайдена платіжна матриця цієї гри
.
Розв’язання. Оптимальні мішані стратегії гравця А – , гравця В – , =0, =1. Тоді
,
.
Розв’язуючи цю систему рівнянь, знаходимо
,
.
Тоді
.
Таким чином, оптимальні мішані стратегії гравців А і В такі:
.
Ціна гри дорівнює 0,2. Це означає, що гравець А в шести випадах з 10 має казати «правду», а в решті 4 – «неправду». Гравець В у восьми випадках з 10 має «вірити», а в решті – не вірити. Середній виграш в цій грі дорівнює
0,2 грн.
5.4 Геометрична інтерпретація гри
Розв’язання гри допускає наглядну геометричну інтерпретацію. Запишемо платіжну матрицю цієї гри:
.
Мішані стратегії гравців
.
За теоремою 2 маємо:
,
.
З точки зору геометрії маємо рівняння двох прямих в системі координат (p,v):
v = a11 p + a21 (1–p),
v = a12 p + a22 (1–p).
Побудуємо графіки цих прямих.
Гравець А розраховує на min(F(SA,B1), F(SA,B1)) – жирно виділена ламана на графіку. Він гарантовано одержує виграш на цій ламаній і, очевидно, вибирає на ній найвищу точку. Координати цієї точки (p*,v) задають ціну гри v і оптимальну мішану стратегію гравця А:
.
Для гравця В за теоремою 2 маємо:
.
Так само в системі координат (q,v) побудуємо прямі
v = a11 q + a12 (1– q)
v = a21 q + a22 (1– q)
Гравець В розраховує на max(F(A1,SB), F(A2,SB)) – жирно виділена ламана на графіку. Він гарантовано одержує програш на цій ламаній і, очевидно, вибирає на ній найнижчу точку. Координати цієї точки (q*,v) задають ціну гри v і оптимальну мішану стратегію гравця B:
.
Приклад. Розв’язати геометрично гру з платіжною матрицею
,
.
Будуємо відповідні прямі
Знайдемо координати точки перетину прямих
2p–3(1–p) = –p+4(1–p),
10p = 7, p*=0,7,
v = 2·0,7–3·0,3=0,5.
– оптимальна мішана стратегія гравця А.
Для гравця В
,
3q=1,5, q*=0,5.
– оптимальна мішана стратегія гравця B.
Ціна гри v=0,5.
5.5 Розв’язання ігор та
Такі ігри мають наступні платіжні матриці:
.
Ці ігри краще за все розв’язувати геометрично.
Для визначеності розглянемо гру і застосуємо теорему 2, враховуючи, що мішана стратегія гравця А має вигляд
.
Тоді
,
,
… ,
.
Далі будуємо графіки всіх прямих і обираємо нижню ламану, тобто ламану min(F(SA,B1), F(SA,B1),…, F(SA,Bn)), а потім найвищу точку цієї ламаної. Її координати (p*,v) задають ціну гри v і оптимальну мішану стратегію гравця А. Відрізки цієї ламаної відокремлюють також і активні стратегії гравця В. Решта стратегій не грають ніякої ролі. На активних стратегіях гравця В шукаємо, знаючи ціну гри v, оптимальну мішану стратегію .
Аналогічно розв’язується і гра , але в ній обирають верхню ламану max(F(A1,SB), F(A2,SB),…, F(Am,SB)), а в ній найнижчу точку та її координати.
Приклад. Розв’язати гру з платіжною матрицею
.
Розв’язання. Перш за все зауважимо, що стратегія А2 є більш вдалою, ніж А1 і А4. Тобто зрозуміло, що А1 і А4 – неактивні стратегії, і платіжна матриця стає такою:
, .
Застосуємо теорему 2.
,
,
,
.
Будуємо відповідні прямі
Нижня точка виділеної ламаної знаходиться на перетині ліній і , тобто стратегії А2 і А3 є активними. Розв’яжемо систему відповідних рівнянь
2q+15q+3, 7q2,
.
Таким чином, оптимальна мішана стратегія гравця В має вигляд
.
Далі знайдемо оптимальну мішану стратегію гравця А. Ми вже знаємо, активними стратегіями гравця А є А2 і А2, тобто
.
Тоді
, , .
Таким чином, оптимальна мішана стратегія гравця А
.
Ціна гри .
5.6 Розв’язання ігор
Ігри можуть бути розв’язані трьома методами:
Розглянемо кожен з методів окремо.
І Метод розв’язання системи лінійних рівнянь.
Розглянемо приклад – гру «монетка під пару». Правила гри. Кожний з двох гравців має монети 5, 10, 25 коп. За командою обидва гравці показують свої монети. Якщо монети однакові, тоді вони переходять гравцю А, якщо різні – гравцю В. Розв’язати гру.
Розв’язання. Складемо матрицю платежів цієї гри. Кожен гравець має три стратегії: А1 – 5 к., А2 – 10 к., А3 – 25 к., теж саме для гравця В. Тоді
.
Мішана стратегія гравця А
.
Складаємо систему рівнянь
.
Розв’язуючи цю систему рівнянь, одержимо
,
.
Таким чином, оптимальна стратегія гравця А така:
.
Перейдемо до гравця В.
.
Складаємо систему рівнянь
.
Розв’язуючи цю систему рівнянь, одержимо
і , ціна гри .
ІІ Зведення матричної гри до задачі лінійного програмування.
Якщо в матриці платежів є від’ємні елементи, то потрібно додати до кожного елемента матриці таке число, щоб всі елементи стали додатними. Розв’язувати гру методом лінійного програмування потрібно за новою матрицею, а потім від ціни гри відняти те число, яке додавали до елементів матриці.
Гравець А застосовує стратегію , а гравець В відповідає стратегією Вj.
Тут v0 – ціна гри за новою матрицею.
Розділимо обидві частини нерівностей на v і введемо позначки
,
де xi ≥ 0, i0,1,…,m.
Гравець А намагається збільшити ціну гри v. Тоді одержуємо таку задачу лінійного програмування:
Аналогічними діями одержимо задачу лінійного програмування для гравця В, враховуючи те, що гравець В бажає зменшити ціну гри v.
де .
ІІІ Наближений метод розв’язання ігор .
Розглянемо наближений метод, що має назву метод Брауна–Дж.Робінсон. Він складається з наступного. Проводиться багато партій гри, причому на кож ному n–му кроці сторона В вибирає таку свою чисту стратегію, яка найкращим чином протидіє накопиченому виграшу сторони А при перших (n–1) ходах. Аналогічним чином діє і сторона А при виборі своєї стратегії.
Приклад. Розв’яжемо гру з платіжною матрицею
.
Літерою «с» позначимо виграш. Якщо зустрінуться однакові числа «с», то будемо вибирати стратегію з меншим номером (за нижчеподаною таблицею).
|
N партії к |
Вибір Аі |
Сумарний виграш гравця А при стратегіях Вj |
Вибір Bj |
Сумарний виграш гравця B при стратегіях Ai |
|||||||
|
B1 |
B2 |
B3 |
A1 |
A2 |
A3 |
||||||
|
1 |
A3 |
1 |
7 |
3 |
1 |
B1 |
4 |
1 |
8 |
4,5 |
|
|
2 |
A1 |
1+8 |
7+2 |
3+4 |
B3 |
4+6 |
1+3 |
||||
|
3 |
A1 |
9+8 |
9+2 |
7+4 |
B2 |
12+2 |
4+7 |
||||
|
4 |
A2 |
21 |
16 |
17 |
4 |
B2 |
16 |
18 |
5 |
4,5 |
|
|
5 |
A2 |
25 |
21 |
23 |
4,2 |
B2 |
18 |
25 |
5 |
4,6 |
|
|
6 |
A2 |
29 |
26 |
29 |
B2 |
20 |
30 |
||||
|
7 |
A3 |
30 |
33 |
32 |
B1 |
28 |
33 |
||||
|
8 |
A2 |
34 |
38 |
38 |
B1 |
36 |
34 |
4,5 |
|||
|
9 |
A2 |
38 |
43 |
44 |
B1 |
42 |
35 |
||||
|
10 |
A1 |
46 |
45 |
48 |
4,5 |
B2 |
46 |
42 |
4,7 |
4,6 |
Зроблено 10 кроків задачі. Послідовність чисел в останньому стовпці збігається до ціни гри.
За 10 кроків стратегія А1 зустрілась 3 рази, А2 – 5 разів, А3 – 2 рази, В1 – 4 рази, В2 – 5 разів, В3 – 1 раз. Тоді емпіричні оптимальні мішані стратегії на 10 кроках такі:
, .
Якщо кількість партій прямує до нескінченності, то емпіричні стратегії прямують до оптимальних стратегій.
Питання для самоперевірки
Задачі для самостійної роботи
Кожний з двох гравців має 3 монети номіналом 5; 10; 25 копійок. Обидва гравця одночасно показують по одній монеті. Якщо монети однакові, то вони переходять до першого гравця, якщо різні − до другого.
Полковник має 5 полків і захищає дві рівноцінні позиції. Його противник має 4 полки і атакує ці позиції. Кожний з противників може виділити цілу кількість полків. Полковник виграє 1 грошову одиницю, якщо на кожній з позицій зосередить не менше полків, ніж його противник. У всіх інших випадках він програє 1 грош. одиницю. Скласти матрицю гри.
Варіант 1 Варіант 2
. .
Варіант 3
.
Варіант 1 Варіант 2
. .
.
.
Глава 6 ЕЛЕМЕНТИ ТЕОРІЇ МАСОВОГО ОБСЛУГОВУВАННЯ
6.1 Основні поняття
Під час дослідження операцій часто доводиться мати справу з системами, призначеними для багаторазового використання при розв’язанні однотипних задач. Процеси, які при цьому виникають, одержали назву процесів обслуговування, а системи – систем масового обслуговування (СМО). Прикладами таких систем є телефонні системи (АТС), ремонтні майстерні, обчислювальні комплекси, білетні каси, магазини, перукарні і т.п.
Кожна СМО складається з визначеного числа одиниць, що обслуговуються (прибори, пристрої, пункти, станції), які будемо називати каналами обслуговування. Каналами можуть бути лінії зв’язку, робочі точки, обчислювальні машини, продавці та ін. За числом каналів СМО розподіляють на одноканальні та багатоканальні.
Заявки поступають у СМО не регулярно, а випадково, утворюючи так звану випадкову течію заявок (викликів). Обслуговування заявок теж продовжується випадковий час. Випадковий характер течії заявок і часу їх обслуговування призводить до того, що СМО є завантаженою нерівномірно: в якісь періоди часу накопичується дуже велика кількість заявок ( вони або стають у чергу, або покидають СМО необслугованими), в інші ж періоди СМО працює з недовантаженням або простоює.
Предметом теорії масового обслуговування є побудова математичних моделей, які пов’язують задані умови роботи СМО (число каналів, їх продуктивність, характер течії заявок і т.п.) з показниками ефективності СМО, які описують її спроможність упоратися з течією заявок.
У якості показників ефективності СМО використовуються: середнє число заявок, які обслуговуються в одиницю часу; середнє число заявок у черзі; середній час очікування обслуговування; ймовірність того, що число заявок в черзі перевищить визначене значення і т.п.
СМО розподіляють на два основних типи (класи): СМО з відмовами і СМО з очікуванням (чергою). У СМО з відмовами заявка, що надходить в момент, коли всі канали зайняті, одержує відмову, залишає СМО і в подальшому процесі обслуговування не бере участі (наприклад, заявка на телефонну розмову в момент, коли всі канали зайняті, одержує відмову і залишає СМО не обслугованою). В СМО з очікуванням заявка, яка приходить в момент, коли всі канали зайняті, стає в чергу на обслуговування.
СМО з очікуванням поділяються на два види залежно від того, як організована черга: з обмеженою чи необмеженою довжиною черги, з обмеженим часом очікування і т.п.
Для класифікації СМО важливим є також дисципліна обслуговування, яка визначає порядок вибору заявок з числа, що надійшли і порядок розподілу їх між вільними каналами.
Вважаємо течію викликів (заявок), що поступають в СМО, найпростішою. Нагадаємо, що ця течія задовольняє три умови:
В цьому випадку закон, якому підпорядковується течія подій (викликів), що надійшли в СМО, є законом Пуассона з параметром λt, де λ – інтенсивність течії (тобто число викликів, які поступають в СМО в одиницю часу), t – час.
Тоді ймовірність того, що в систему надійшло k викликів за час t визначається за формулою
.
Час обслуговування у СМО – це теж випадкова величина. Позначаємо її τ. Вважається, що час обслуговування розподілен по показниковому закону. Нагадаємо, що диференціальна функція такого розподілу має вигляд
Нагадаємо також, що математичне сподівання такої випадкової величини дорівнює
Робота системи масового обслуговування являє собою випадковий процес. Ми розглядаємо його як процес з дискретними станами і неперервним часом; тобто його можливі стани S0, S1 ,S2,… можна перерахувати, і перехід системи зі стану у стан відбувається миттєво, а моменти можливих переходів системи зі стану у стан є випадковими.
Стани n – канальної системи S0, S1 ,S2,…,Sn опишемо наступним чином:
S0 – система вільна, тобто всі її канали вільні;
Sk – k каналів зайняті;
pk(t) – ймовірність того, що в момент часу t система знаходиться у стані
Sk, k = 0,1,2,..., n.
Задачі, що тут розв’язуються є такими:
k =0,1,2,…,n;
Перелічимо ті параметри системи, які характеризують її ефективність:
Взагалі кажучи, всі ці характеристики залежать від часу, але для багатьох систем встановлюється режим, близький до стаціонарного.
У будь-якій системі масового обслуговування, в якій інтенсивність вхідної течії викликів λ не залежить від стану системи, справедливі формули Літтла, а саме:
6.2 Системи масового обслуговування з відмовами
А Розглянемо одноканальну систему з відмовами. На один канал надходить течія заявок з інтенсивністю λ. Течія обслуговувань має інтенсивність μ. Система має два стани s0 – система вільна і s1 – система зайнята.
Граф станів має такий вигляд:
Потрібно знайти р0(t) – ймовірність того, що в момент часу t система вільна, і р1(t) – ймовірність того, що в момент часу t система зайнята. Зауважимо, що р0(t) + р1(t) =1.
Позначимо через С подію, яка полягає в тому, що в момент часу t + ∆t система знаходиться у стані s0. В цьому стані система може опинитися, якщо:
(це подія А);
Тоді С = А+В. Події А і В несумісні, тобто Р(С) = Р(А) + Р(В).
За означеннями Р(С) = р0(t + ∆t), а Р(А) = р0(t)*е-λ∆t, Р(В) = р1(t)*(1-е-μ∆t), тому що ймовірність того, що ні одна заявка не поступила за час ∆t, дорівнює
е-λ∆t, а ймовірність того, що заявка була обслужена за час ∆t, дорівнює 1-е-μ∆t. Скористаємось тим, що при малих ∆t
е-λ∆t ≈ 1 - λ∆t; 1-е-μ∆t ≈ μ∆t.
Тоді
р0(t + ∆t) = р0(t)*(1-λ∆t) + р1(t)*μ∆t,
Переходимо до границі, якщо ∆t→0, і одержуємо
.
Очевидна початкова умова р0(0) = 1. Розв’яжемо відповідну задачу Коші для диференціального рівняння 1-го порядку, пам’ятаючи, що р1(t) = 1 – р0(t).
Розв’язок цієї задачі
Якщо t→ ∞, то маємо режим, що є близьким до стаціонарного, і тоді
Знайдемо характеристики системи:
Б Далі розглянемо n – канальну систему з відмовами.
Система має n каналів, на які надходить течія заявок з інтенсивністю λ. Течія обслуговувань має наступні стани (нумеруємо їх, як завжди, за числом заявок, що знаходяться в системі): s0,s1,s2,…, sk ,...,sn, де sk – стан системи, коли в ній знаходиться k заявок, тобто k каналів зайнято.
Граф станів такої системи має вигляд
Течія заявок послідовно переводить систему з будь-якого лівого стану у сусідній правий з однією й тією ж інтенсивністю λ. Інтенсивність течії обслуговування, що переводить систему з будь-якого правого стану в сусідній лівий, постійно змінюється в залежності від стану. Дійсно, якщо СМО знаходиться в стані s2 ( два канали зайняті), то вона може перейти у стан s1 (один канал зайнято), коли закінчить обслуговування або перший, або другий канал, тобто сумарна інтенсивність їх течій обслуговування буде дорівнювати 2μ. Аналогічно, сумарна течія обслуговувань, що переводить СМО зі стану s3 в s2 буде мати інтенсивність 3μ, тобто може звільнитися будь-який з трьох каналів і т.д.
Аналогічно тому, як це було зроблено у випадку n =1, одержимо такі формули для граничної (t→∞) ймовірності станів:
Ці формули мають назву формули Ерланга на честь засновника теорії масового обслуговування.
Далі знайдемо параметри системи, які характеризують її ефективність, а саме:
Але середнє число зайнятих каналів можна знайти простіше, якщо взяти до уваги, що абсолютна пропускна спроможність системи А – це інтенсивність течії заявок, що обслуговані системою за одиницю часу. Оскільки кожний зайнятий канал обслуговує в середньому μ заявок ( в одиницю часу), то середнє число зайнятих каналів
6.3 Системи масового обслуговання з очікуванням (чергою)
А Розглянемо одноканальну систему з необмеженою чергою (наприклад, телефон-автомат з однією будкою). Течія заявок, що поступають у СМО, має інтенсивність λ, а течія обслуговань – інтенсивність µ. Система може знаходитися в одному зі станів , , , …, , … за числом заявок, що знаходяться у СМО: − канал вільний; − канал зайнятий ( обслуговує заявку), черги немає; − канал зайнятий, одна заявка стоїть у черзі; … − канал зайнятий, ( k–1) заявок стоять у черзі і т.д.
Граф станів має такий вигляд
Перш ніж записати формули граничних ймовірностей відповідних станів, необхідно бути упевненим в їх існуванні, тому що у випадку коли час t→ ∞, черга може необмежено зростати. Доведено, що якщо , тобто середне число заявок, що надходять, менше середнього числа заявок, що обслужені (в одиницю часу), то граничні ймовірності існують. Якщо , то черга зростає до нескінченості.
Відповідні формули одержані аналогічно тому, як це було зроблено в 6.2.
Якщо , то
Граничні ймовірності утворюють спадаючу геометричну прогресію із знаменником , тобто ймовірність − найбільша. Це означає, що якщо СМО справляється з течією заявок ( при ), то найбільш ймовірним буде відсутність заявок в системі.
Далі визначимо показники ефективності системи:
Таким чином одержуємо
.
Зауважимо, що черга утворюється зі стану .
тобто
.
.
.
.
Б Розглянемо n-канальну систему з необмеженою чергою. Течія заявок, що надходять в СМО, має інтенсивність λ, а течія обслуговань – інтенсивність µ.
Система може знаходитись в одному зі станів ..., занумерованих за числом заявок, що знаходяться у СМО, або у станах , в яких n каналів зайняті, r – число заявок у черзі.
Граф станів такої системи має такий вигляд
Можна довести, що при граничні ймовірності існують і мають вигляд
,
при 1≤ k ≤ n,
Для СМО, що розглядається використовуючи тіж прийоми, що і раніше, знайдемо показники ефективності системи,
.
.
.
.
.
В Розглянемо СМО с обмеженою чергою. Вони відрізняються від задач, що розглянуті вище, лише тим, що число заявок в черзі обмежено і не перевищує заданого числа m. Якщо нова заявка надходить в момент, коли всі місця у черзі заняті, то вона залишає СМО необслугованою. Для обчислення граничних ймовірностей і показників ефективності таких СМО використовується той самий підхід, що і раніше. Відповідні формули зведено в нижеподану таблицю.
|
Показники |
Одноканальне СМО з обмеженою чергою довжини m |
n-канальна СМО з обмеженою чергою довжини |
|
Граничні ймовірності |
||
|
Ймовірність відмови |
||
|
Відносна пропускна спроможність |
Q=1- |
Q=1- |
|
Абсолютна пропускна спроможність |
A=λQ=λ(1- |
A = λ (1-) |
|
Середнє число заявок у черзі |
||
|
Середнє число зайнятих каналів |
= |
Середній час перебування заявки в системі і в черзі обчислюється за формулами Ерланга , .
Приклади.
Задача 1 Заявки на телефонні перемовини в телеательє надходять з інтенсивністю λ=90 заявок за годину, а середня тривалість розмови Визначити показники ефективності роботи СМО (телефонного зв’язку) при наявності одного телефонного номера.
Розв’язання. Маємо λ=90, . Тоді інтенсивність течії обслуговання
Відносна пропускна спроможність в цьому випадку , тобто в середньому тільки 25% заявок, що надходять, здійснять перемовини по телефону. Відповідно ймовірність відмови в обслугованні складає . Абсолютна пропускна спроможність СМО А=λQ=90*0,25=22,5 , тобто в середньому 22,5 заявки. Очевидно, що при наявності одного телефонного номера СМО погано справляється с течією заявок.
Задача 2 В умовах задачі 1 визначити оптимальне число телефонних номерів в телеательє, якщо умовою оптимальності вважати задоволення в середньому з кожних 100 заявок не менше ніж 30.
Розв’язання. За формулою маємо , тобто за час середної за тривалостю телефонної розмови надходить в середньому 3 заявки на перемовини.
Будемо поступово збільшувати число каналів (телефонних номерів) n=2,3,4,… і визначимо за відповідними формулами характеристики обслуговання. Наприклад, при n=2
.
Значення характеристик зведено до нижеподаної таблиці
|
Характеристика |
Число каналів |
|||||
|
1 |
2 |
3 |
4 |
5 |
6 |
|
|
Q |
0,25 |
0,47 |
0,65 |
0,79 |
0,90 |
0,95 |
|
A |
22,5 |
42,4 |
58,8 |
71,5 |
80,1 |
85,3 |
За умовою оптимальності Q ≥ 0,9 ,тобто в телеательє потрібно встановити 5 телефонних номерів (в цьому випадку Q = 0,9). При цьому за годину буде обслуговано в середньому 80 заявок ( А=80,1), а середнє число зайнятих телефонних номерів (каналів) за формулою
.
Задача 3 В порту є один причал для розвантаження суден. Інтенсивність течії суден дорівнює 0,4 ( суден за добу ). Середній час розвантаження одного судна дорівнює 2 доби. Припускаємо, що черга може бути необмеженої довжини. Знайти показники ефективності роботи причалу, а також ймовірність того, що чекають розвантаження не більше, ніж 2 судна.
Розв’язання. Маємо , тобто черга на розвантаження не може нескінченно зростати і граничні ймовірності існують.
Ймовірність того, що причал є вільним , а ймовірність того, що він зайнят Ймовірність того, що у причала знаходяться 1,2,3 судна (тобто чекають розвантаження 0,1,2 судна), дорівнюють:
;
.
Ймовірність того, що чекають розвантаження не більше ніж 2 судна становить
=0,16+0,128+0,1024=0,3904.
Середнє число суден, що чекають розвантаження,
.
Середній час очікування розвантаження
.
Середнє число суден, що знаходяться біля причалу,
(діб).
Середній час перебування судна біля причалу
(діб).
Очевидно, що ефективність розвантаження суден невелика. Для того, щоб збільшити її, необхідно зменшення середнього часу розвантаження судна або збільшення числа причалів.
Задача 4 В універсамі до вузла розрахунку поступає течія покупців з інтенсивністю 81 людина за годину (λ= 81). Середня тривалість обслуговування контролером – касиром одного покупця дорівнює 2 хвилини Визначити:
а) мінімальну кількість контролерів-касирів (, при якій черга не буде зростати до нескінченості і відповідні характеристики обслуговування;
б) оптимальну кількість ( ) контролерів – касирів, при якій відносна величина затрат , пов’язана з витратами на утримання каналів обслуговування і з перебуванням покупців у черзі, що задається як ,буде мінімальною, і порівняти характеристики обслуговання при ;
в) ймовірність того, що в черзі буде не більше трьох покупців.
Розв’язання.
А За умовою λ= 81 = .
= .
Очевидно, що черга не буде зростати до нескінченості за умови , тобто n >=2,7
Таким чином, мінімальна кількість контролерів-касирів . Ймовірність того, що у вузлах розрахунку відсутні покупці, становить
, тобто в середньому 2,5% часу контролери-касири будуть простоювати. Ймовірність того, що у вузлі розрахунку буде черга, обчислимо за формулою
.
Середнє число покупців, що знаходяться у черзі,
.
Середній час очікування в черзі
.
Середнє число покупців у вузлі розрахунку
.
Середнє число перебування покупців у вузлі розрахунку
(хв.)
Середнє число контролерів – касирів, зайнятих обслугованням покупців, .
Абсолютна пропускна спроможність вузла розрахунка
А=λ=1,35 =81.
Аналіз характеристик обслогування свідчить про значне навантаження вузла розрахунку при наявності трьох контролерів-касирів.
Б Відносна величина витрат при n=3
.
Розрахуємо відносну величину витрат при інших значеннях n.
|
Характеристика |
Число контролерів-касирів |
||||
|
3 |
4 |
5 |
6 |
7 |
|
|
Ймовірність простою |
0,025 |
0,057 |
0,065 |
0,067 |
0,067 |
|
Середній час (хв.) перебування в черзі |
5,47 |
0,60 |
0,15 |
0,03 |
0,01 |
|
Відносна величина витрат |
18,63 |
4,76 |
4,15 |
4,53 |
5,21 |
Як бачимо з таблиці, мінімальні витрати одержуємо, якщо
Визначимо характеристику ефективності при n=5.
.
; ; ; ; .
Як ми бачимо при n=5 в порівнянні з n=3 суттєво зменшилась ймовірність виникнення черги і середній час перебування в черзі і, відповідно, середне число покупців і середній час перебування їх у вузлі розрахунку . А середнє число зайнятих обслуговуванням касирів и абсолютно пропускна спроможність вузла розрахунку А не змінились (вони не залежать від n).
В ймовірність того, що в черзі буде не більше трьох покупців, визначається:
- у випадку n=3,
;
- у випадку n=5,
+=0,986;
Задача 5 При умовах задачі 3 знайти показники ефективності роботи причалу, якщо відомо, що судно залишає порт (без розвантаження), за умови, що в черзі на розвантаження стоїть більше 3 суден.
Розв’язання. За умовою m=3 – це СМО з обмеженою чергою.
Ймовірність того, що причал вільний
.
Ймовірність того, що судно залише причал без розвантаження,
.
Відносна пропускна спроможність причалу
- .
Абсолютна пропускна спроможність причалу
Q = 0,4 * 0,878+0,351, тобто в середньому за добу розвантажується 0,35 суден.
Середнє число суден, що чекають розвантаження,
.
Середній час очікування розвантаження
.
Середнє число суден біля причалу
.
Середній час перебування судна буля причалу
.
Питання для самоперевірки
а) абсолютна пропускна спроможність системи;
б) відносна пропускна спроможність системи;
в) ймовірність відмови в обслуговуванні;
г) середнє число заявок в СМО;
д) середнє число заявок в черзі;
е) середній час перебування заявки в СМО;
ж) середній час перебування заявки в черзі;
з) середнє число зайнятих каналів.
Розглянути формули для всіх видів наведених вище систем.
Задачі для самостійної роботи
з/с. Знайти ймовірність відмови та середнє число зайнятих каналів.
а) середнє число клієнтів, яких обслуговано за годину;
б) середню частку клієнтів, які обслуговані, з числа клієнтів, які прийшли;
в) середнє число зайнятих в коридорі стільців;
г) середній час, який клієнт перебуває в коридорі та на обслуговуванні.
а) авт./год.
б) авт./год.
Середній час обслуговування в системі хв/з, течія заявок пуасонівська з з/хв.
Знайти:
а) ймовірність того, що канал є зайнятим у момент надходження заявки;
б) середній час очікування початку обслуговування;
в) середню довжину черги.
СПИСОК ЛІТЕРАТУРИ
ЗМІСТ
Вступ..............................................................................................................3
Глава 1 Задача теорії розкладу...........................................................................4
Питання для самоперевірки........................................................................5
Задачі для самостійної роботи.....................................................................5
Глава 2 Екстремальні задачі на графах...............................................................5
2.1 Основні поняття......................................................................................5
2.2 Способи задання графа...........................................................................6
2.3 Дерева та ліс. Остовне дерево графа.....................................................8
2.4 Алгоритм побудови остовного дерева зв’язного графа.....................10
2.5 Знаходження найкоротшого шляху в орієнтованому графі...............11
2.6 Мережевий граф та його розрахунок....................................................16
2.7 Задача про максимальну течію в мережі..............................................21
Питання для самоперевірки.........................................................................27
Задачі для самостійної роботи.....................................................................29
Глава 3 Метод гілок та меж.................................................................................31
3.1 Основні поняття...................................................................................31
3.2 Задача про рюкзак................................................................................32
3.3 Задача комівояжера..............................................................................35
Питання для самоперевірки.........................................................................41
Задачі для самостійної роботи.....................................................................41
Глава 4 Задача про призначення (вибір).............................................................44
Питання для самоперевірки.........................................................................46
Задачі для самостійної роботи.....................................................................46
Глава 5 Теорія ігор................................................................................................47
5.1 Платіжна матриця. Нижня та верхня ціна гри..................................48
5.2 Розв’язання гри у мішаних стратегіях...............................................50
5.3 Ігри 2x2..................................................................................................52
5.4 Геометрична інтерпретація гри .................................................53
5.5 Розв’язання ігор та .........................................................55
5.6 Розв’язання ігор...................................................................................57
Питання для самоперевірки.........................................................................60
Задачі для самостійної роботи.....................................................................60
Глава 6 Елементи теорії масового обслуговування...........................................62
6.1 Основні поняття....................................................................................62
6.2 Системи масового обслуговування з відмовамию............................64
6.3 Системи масового обслуговання з очікуванням (чергою)...............67
Питання для самоперевірки........................................................................75
Задачі для самостійної роботи....................................................................76
Список літератури................................................................................................77
Навчальне видання
ІОХВИДОВИЧ Нона Юзефівна
ПОКЛОНСЬКИЙ Евген Васильович
ПОДКОПАЙ Ірина Василівна
ПОСИЛАЄВА Раїса Вікторівна
ДОСЛІДЖЕННЯ ОПЕРАЦІЙ
Навчально – методичний посібник
Відповідальний за випуск О.М. Стасенко
Редактор Л.І. Христенко
План 2010р., поз. 13. Формат 60х84 1/16. Папір друк. №2.
Підп. до друку Обл.-вид. арк. 4,0.
Надруковано на ризографі. Умов. друк. арк. 3,8
Тираж 50 прим. Зам. № 1741. Безкоштовно.
__________________________________________________________________
ХДТУБА, Україна, 61002, Харків, вул. Сумська, 40
__________________________________________________________________
Підготовлено та надруковано РВВ Харківського державного технічного університету будівництва та архітектури
1
2
4
6
3
5
4
3
2
2
2
3
2
7
6
y
1
y
3
2
1
4
y
2
5
y
5
y
7
4
7
7
d7 = 7
5
6
d6 = 5
4
5
d5 = 4
3
4
d4 = 3
2
2
1
3
d3 = 1
0
1
d2 = 2
1
6
1
5
1
3
5
5
4
2
1
6
4
2
4
6
2
6
3
8
7
2
1
1
4
5
1
5
4
1
4
2
3
5
4
1
6
2
4
6
2
8
7
8
1
7
7
5
2
0
4
7
2
3
2
2
2
3
4
5
3
6
4
2
1
6
3
8
7
2
1
0
1
2
3
4
5
7
7
3
2
6
4
8
5
2
4
6
1
2
5
1
1
2
4
5
4
1
3
2
4
6
5
6
3
8
1
1
7
2
1
3
3
3
2
d2 = 2
1
3
4
1
0
2
5
5
6
7
9
6
7
8
13
3
5
1
5
4
1
4
2
3
5
4
1
6
2
4
6
2
6
3
8
7
2
1
0
2
1
7
13
9
5
6
3
1
3
5
4
2
4
7
2
8
1
9
I:
1
a2
a4
a3
a1
a5
b5
b1
b3
b4
b2
II:
6
1
v1
EMBED Equation.3
v4
v3
v2
v1
EMBED Equation.3
EMBED Equation.3
v4
v3
v2
u2
u1
u3
u4
u5
EMBED Equation.3
u2
u1
u3
u4
u5
u6
v1
v2
v4
v3
EMBED Equation.3
u1
u4
u3
v5
u2
v2
v3
v1
v4
EMBED Equation.3
u2
u1
u5
u4
u9
u3
u6
u8
u7
1
4
2
5
3
2
6
8
4
10
9
7
8
3
5
3
D
B
5
4
3
А2
2'
2
1
2
1
2
2
1
1
B2
C
5
4
C2
3'
А2
А2
3'
E
6
0
2
1
3
5
4
B2
C2
D2
D2
C2
B2
4
4
3
А2
2
1
2
1
х
y
y
х
y
х
х
х
х
n
E(x)
0
a12
a11
x
n
v
L(n)– L(x)
p
a22
a21
0
p*
1
1
q*
0
a21
a22
a12
a11
v
q
1
p*
1
-1
4
-3
2
v
p
2
3
4
1
q*
-2
3
-3
2
v
q
1
1
2
4
3
2
1
u3
u1
u4
u8
u2
u5
u6
u7
1
3
2
4
3
4
3
2
4
5
1
2
3
1
5
4
5
3
3
6
9
8
2
13
Є
2
3
1
4
і(1,2) = 3
і(3,4) = 1
і(2,3) = 2
2
3
1
4
r(3,1) = 1
і(4,3) = 3
r(3,2) = 2
Є
(х,у) EMBED Equation.3 І;
X02х
у
Xх
у
(у,х) EMBED Equation.3 R;
2
3
1
5
3
3
4
4
2
2
1
2
3
1
5
3
3/2
4
4
2/2
2/2
1
2
3
1
5
3/1
3/2/1
4
4/1
2/2
2/2
1/1
R
R
R
B
v1
v2
А
5
4
3
2
3
4
v3
v4
2
6
2
v1
v2
А
3
4
3
2
3
4
v3
v4
4
2
B
v1
v2
А
3
4
1
3
4
v3
v4
4
B
v1
v2
А
3
1
1
4
v3
v4
1
B
Х
Х11
Х12
Х13
Х
Х11
Х12
ρ(Х12) ≤ρ(Х11)
Х
Х11
Х12
Х21
Х22
Х
Х11
Х12
Х21
Х22
Х31
Х32
Х41
Х42
17
12,4
12,6
12 EMBED Equation.3 EMBED Equation.3
13
13
13
12 EMBED Equation.3 EMBED Equation.3
∞
Х
Х11
Х12
EMBED Equation.3
EMBED Equation.3
Х11
Х12
Х
EMBED Equation.3
[5,3]
EMBED Equation.3
34
31 + 10 =41
Х21
Х22
X12
EMBED Equation.3
[4,2]
EMBED Equation.3
53
Х31
Х32
X22
[3,4]
EMBED Equation.3
59
34
Х12
Х
[5,3]
31
53
Х11
Х21
Х22
Х32
Х42
Х31
Х41
34
34
34
41
34
59
∞
[4,2]
[3,4]
[2,1]
[1,5]
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
34
34
34
34
6
10
10
34
1
1
1
ІІ
ІІІ
VIII
ІV
IX
V
VI
VII
Кількість 0*= n
Кількість 0*< n
Кінець задачі
s0
μ
λ
s1
λ
s0
μ
λ
sk
s2
s1
sn
λ
λ
λ
λ
2μ
3μ
kμ
(k+1)μ
nμ
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
. . .
. . .
. . .
. . .
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
. . .
. . .
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
4
1
Л
2
К
2
Е
Ж 1
1
А
8
1
7
2
В
1
И
4
М
1
Д
6
Г
3
Б
6
5
9
3
2
4
М
2
В
1
И
1 Л
2
К
Ж 1
2
Е
1
Д
6
Г
3
Б
1
А
17 17
12 13
1
1
10 10
12 12
13 13
10 10
4 4
0 0
9
6
8
7
4
5
3
2
1
EMBED MSPhotoEd.3
u6
u5
u4
u3
u1
u2
9
4
3
2
1
u5
u4
u3
u1
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
u2
4
3
2
1
5
6
4
7
4
3
5
2
1
8
4
6
3
7
5
2
1
7
5
3
4
3
6
9
10
7
5
8
3
2
1
6
5
4
9
8
7
112
10
х
С=30
ні
ні