ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Н.Ю.Іохвидович, Е.В. Поклонський,

Загрузка...

Н.Ю.Іохвидович, Е.В. Поклонський,

І.В. Подкопай, Р.В. Посилаєва

ДОСЛІДЖЕННЯ ОПЕРАЦІЙ

 

Навчально – методичний посібник

 

 

 

Харків 2010

Міністерство освіти і науки України

 

ХАРКІВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ

УНІВЕРСИТЕТ БУДІВНИЦТВА ТА АРХІТЕКТУРИ

 

 

Н.Ю.Іохвидович, Е.В. Поклонський,

І.В. Подкопай, Р.В. Посилаєва

 

ДОСЛІДЖЕННЯ ОПЕРАЦІЙ

 

 

Рекомендовано

методичною радою університету

як навчально–методичний посібник

для студентів напряму 6.030601

 

Харків 2010

 

 

Рецензенти:

 

А.А.Янцевич, доктор фіз.-матем. наук, професор каф. вищої математики і інформатики Харківського національного університету ім. В.Н.Каразіна

 

О.О. Аршава, канд. фіз.-мат. наук, доцент, зав. кафедри вищої математики Харківського державного технічного університету будівництва та архітектури

 

 

Рекомендовано кафедрою вищої математики,

протокол № 9 від 27.05.09

Затверджено методичною радою університету,

Протокол № 1 від 30..09.09

 

 

Автори: Н.Ю.Іохвидович

Е.В. Поклонський

І.В. Подкопай

Р.В. Посилаєва

 

 

Н.Ю.Іохвидович, Е.В. Поклонський, І.В. Подкопай, Р.В. Посилаєва. Дослідження операцій: навчально – методичний посібник – Харків, ХДТУБА, 2010. – 80 с.

 

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

 

 

Іл: ; табл.: ;бібліогр.: назв

 

 

© Н.Ю.Іохвидович, Е.В. Поклонський, І.В. Подкопай, Р.В. Посилаєва, 2010

Загальні відомості

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

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

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

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

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

Розглянемо типові моделі задач теорії дослідження операцій.

IЗадачі розподілу.

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

До задач розподілу можна віднести транспортну задачу, яка розглядається в курсі «Математичне програмування», задачу про призначення (маємо n посад та m претендентів на них, потрібно так розподілити претендентів, щоб витрати на заробітну плату були мінімальними).

IIЗадачі масового обслуговування.

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

IIIЗадача мережевого планування.

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

IVЗадачі теорії розкладу.

VЗадачі вибору маршруту (задача комівояжера).

VIЗадача про пошук.

VIIЗадачі теорії ігор.

Сформулюємо типові етапи розв’язання задач теорії дослідження операцій.

IПорушення проблеми:

а) виявлення проблеми;

б) формулювання мети і критерію ефективності;

в) аналіз проблеми;

г) побудова математичної моделі задачі.

IIЗнаходження оптимального розв’язку:

а) розв’язок математичної моделі з різноманітними цільовими функціями;

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

IIIПрийняття і реалізація рішень.

У подальшому детально розглянемо деякі з означених вище задач.

 

Глава 1 Задача теорії розкладу

Постановка задачі. Маємо 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
ai (I верстат)
bi (II верстат)
Послідовність обробки

 

З часових осей бачимо, що час простою дорівнює 8 одиниць часу.

Задача розкладу для n деталей і трьох верстатів у загальному випадку не розв’язана. Але у випадку, коли min ai ≥ max bi або min ci ≥ min bi , де ai, bi, ci – це час обробки i-ї деталі відповідно на I, II і III верстатах, оптимальний порядок обробки деталей визначається за сумами ai+bi, і bi+ci, що зводиться до задачі про два верстати.

Питання для самоперевірки

1 Сформулюйте постановку задачі про розклад.

2 Опишіть алгоритм Джонсона для розв’язання задачі про розклад.

3 Для якого випадку застосовується цей алгоритм?

Задачі для самостійної роботи

1 Маємо 2 верстати і 10 деталей. Скласти розклад обробки.

I
ai (I)
bi (II)

2 Маємо три верстати і 5 деталей. Скласти розклад обробки.

I
ai (I)
bi (II)
ci (III)

 

Основні поняття

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

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

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

Маршрут, усі ребра якого різні, називається ланцюгом.

Якщо початкова і кінцева вершини ланцюга співпадають, то це цикл.

Ланцюг простий, якщо всі його вершини різні (не повторюються).

Цикл простий, якщо співпадають лише початкова і кінцева вершини.

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

Граф називається зв’язним, якщо для будь-яких вершин існує ланцюг, що їх з’єднує.

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

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

Способи задання графа

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

Існують різні способи задання графа:

1) за допомогою матриці суміжності вершин;

2) за допомогою матриці суміжності ребер (дуг) графа;

3) за допомогою матриці інцидентності.

Матриця суміжності вершин

Нехай у графі число вершин дорівнює n. Матриця суміжності вершин орієнтованого графа R=(rij) має розмір ,

де

Якщо граф неорієнтований, вершини з’єднуються ребрами і матриця R=(rij) є симетричною.

Наприклад,

а)

,

б)

.

Матриця інцидентності

Якщо граф неорієнтований і має n вершин і m ребер, то матриця інцидентності S=(sij) має розмір ,

де

Для орієнтованого графа

Наприклад,

а)

,

б)

.

За матрицею інцидентності можна відновлювати граф.

Означення.

1 Розбивальна множина зв’язного графа – це така множина його ребер, вилучення яких призводить до незв’язного графа.

2 Розрізом називається така розбивальна множина, для якої ніяка власна підмножина не є розбивальною множиною.

Наприклад. Маємо граф

Розглянемо такі розбивальні множини його ребер:

1) {u1, u2, u5};

2) {u3, u6, u7, u8};

3) {u1, u2}.

З цих розбивальних множин розрізом будуть лише {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.

Дамо деякі означення.

1 Течією по дузі (i,j) називається невід’ємна цілочислова величина fij ≥ 0, яка менше чи дорівнює пропускній спроможності дуги, тобто fij ≤ cij.

2 Дуга називається ненасиченою, якщо течія через неї менше її пропускної спроможності, тобто fij < cij.

3 Дуга називається насиченою, якщо fij = cij.

 

Будемо вважати, що в мережі задано течію, якщо:

1) для будь–якої проміжної вершини (не початкової і не завершальної) кількість продукту, що надійшла і що відправляється, рівні;

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

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

Величина течії в одній і тій же мережі може бути різною.

Наприклад, розглянемо орієнтований граф

 

1) f12 = 5

Таким чином, через даний граф пройшла течія, що дорівнює 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) і(х,у) =сху - fxy − це максимальна величина, на яку можна збільшити течію в дузі.

 

На рисунку маємо ланцюг, що збільшує, він містить прямі дуги (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Всі дуги мережі відносяться до множини І. Розглянемо ланцюг, що збільшує

 

(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.

Течія в дугах даного ланцюга збільшується на дві одиниці.

 

Повертаємось до кроку ІІ.

3Знову шукаємо ланцюг, що збільшує. Зауважимо, що дуги (1,2) і (3,5) належать до множини R. Розглянемо ланцюг

(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, у яких течію можна лише зменшувати.

Далі розглянемо метод знаходження максимальної течії в неорієнтованому графі.

Маємо неорієнтований граф.

1 По Av1v2B можна пропустити течію, що дорівнює min(5,2,6) = 2. Ребро з мінімальною спроможністю (v1,v2) вилучається, із решти пропускних спроможностей віднімаємо число 2.

2 По Av3v4B можна пропустити течію, що дорівнює min(2,3,2) = 2. Повторюємо процедуру пункту 1.

3 По Av4v2B можна пропустити течію, що дорівнює min(3,4,4) = 3. Тоді одержуємо:

Шляхів із А в В немає. Течія із А в В дорівнює 2 + 2 + 3 = 7.

Питання для самоперевірки

1 Сформулюйте означення графа.

2 Сформулюйте означення орієнтованого та неорієнтованого графа.

3 Сформулюйте означення маршруту у графі.

4 Сформулюйте означення ланцюга, ланцюга простого, цикла, простого цикла, шляха, контура у графі.

5 Який граф називається ейлеровим, гамільтоновим?

6 Що таке матриця суміжності вершин графа?

7 Що таке матриця суміжності ребер (дуг графа)?

8 Що таке матриця інцидентності графа?

9 Дайте означення остовного дерева графа.

10 Як підрахувати число остовних дерев графа?

11 Сформулюйте алгоритм побудови остовного дерева графа, остовного дерева максимальної та мінімальної довжини.

12 Сформулюйте алгоритм Дейкстри побудови найкоротшого шляху в графі.

13 Сформулюйте метод поміток побудови найкоротшого та найдовшого шляху в графі.

14 Дайте означення мережевого графа.

15 Сформулюйте правила, яких необхідно дотримуватись при побудові мережевого графа.

16 Як на мережевому графі відображаються роботи (операції проекта)?

17 Що таке найбільш ранній і найбільш пізній термін настання події?

18 Як їх обчислити?

19 Що таке повний, вільний та незалежний резерв часу операції? Чи є зв’язок між ними?

20 Що таке критична операція?

21 Що таке критичний шлях у мережевому графі?

22 Дайте означення розбивальної множини графа та розрізу графа.

23 Що таке пропускна спроможність розрізу? Що таке мінімальний розріз?

24 Дайте означення течії по дузі.

25 Яка дуга називається насиченою, ненасиченою, вільною?

26 Сформулюйте задачу про максимальну течію в графі.

27 Сформулюйте теорему Форда-Фалкерсона.

28 Сформулюйте алгоритм пошуку ланцюга, що збільшує.

29 Сформулюйте алгоритм пошуку максимальної течії у графі.

 


Задачі для самостійної роботи

1 Маємо граф

 

Побудувати матриці суміжності вершин графа, дуг графа і матрицю інцидентності орграфа.

2Маємо граф

 
 


Побудувати матриці суміжності вершин і ребер не орграфа.

3За матрицею інцидентності відновити граф.

S=

4Маємо граф

 

Для цього графа:

а) обчислити кількість остовних дерев графа;

б) побудувати остовне дерево графа, мінімальне остовне дерево і максимальне остовне дерево;

 

 

5Маємо граф

 
 

 


Для цього графа обчислити:

а) найкоротший шлях методом Дейкстри;

б) найкоротший та найдовший шлях методом поміток;

в) максимальну течію в графі.

6Маємо проект будівництва спортивної споруди (за нижеподаною таблицею).

 

Етап Робота, що виконується Попередній етап Потрібний час (тиж)
А Підготовка будмайданчика -
Б Побудова фундаменту А
В Підводка магістральних ліній електро- і водопостачання А
Г Монтаж вертикальних стін Б
Д Монтаж стріха Г
Е Укладання дерев’яних перекриттів Г
Ж Установка дверей та вікон Г
З* Монтаж електрообладнання Д
І Монтаж системи опалення В, Г
К Установка сантехніки В, Г
Л Оздоблювальні роботи З*, І, К

 

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


Глава 3 МЕТОД ГІЛОК ТА МЕЖ

Основні поняття

Цей метод буде застосовано для розв’язання задачі про рюкзак та задачі комівояжера.

Сформулюємо основні ідеї метода гілок та меж.

Деяка функція має бути мінімізована f(x)→min, де Х складається з дискретних точок (наприклад, цілочисельних). Це задача нелінійного програмування, навіть якщо f(x) – лінійна функція.

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

1)алгоритм розбиття множини Х;

2)деяку систему оцінок будь-якої підмножини Х.

Множину Х розбиваємо на дві – три частини

 

Х11, Х12, Х13 – кінцеві множини 1-го кроку.

На другому кроці за деякою ознакою вибираємо одну з множин 1-го кроку і розбиваємо її. Одержані множини разом з нерОзгалуженими множинами другого кроку називаються кінцевими множинами другого кроку.

Для системи оцінок множин запроваджується функція ρ(Х*), Ця функція повинна задовольняти наступним вимогам:

1)оцінка будь-якої підмножини ρ(Х*) при розбиті повинна бути меншою, ніж min f(x), ;

2)оцінка будь-якої підмножини повинна бути меншою за оцінку тієї множини, з якої ця підмножина одержана, тобто ρ(Х*) ≥ ρ(Х), ;

з цього випливає, що при розбитті оцінка ρ(Х) не може спадати;

3)оцінка множини, що складається з однієї точки, дорівнює значенню цільової функції f(x) в цій точці.

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

Для цього на першому кроці обчисляємо оцінку множини Х − ρ(Х) за означеним правилом. Після цього обчислюється оцінка ρ для підмножин Х11, Х12. Зі знайдених оцінок ρ(Х11), ρ(Х12) обирається найменша, і далі галузиться та множина, для якої оцінка ρ найменша. Після цього процедура повторюється.

Далі галузимо ρ(Х12):

З трьох множин Х11, Х21, Х22 вибираємо ту, для якої оцінка є найменшою. Галузимо доти, поки не доберемося до множини, що складається з однієї

точки, оцінок кінцевих множин останнього кроку.

Задача про рюкзак

Є 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 функції може лише зменшуватися.

Приклад. Маємо п’ять предметів, які треба покласти в рюкзак за умови, що вартість предметів у рюкзаку

і
С=30

сі вартість
рі Вага

Математична модельзадачі така: ми шукаємо 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 відповідно перенумеруємо предмети.

і
поперед. ном.
сі
рі

Задача (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. Якщо перейти до старої

н

Загрузка...

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти