Материал: 62_201

8.Виконати завдання 7 для повного зваженого графа з кіль­ кістю вершин N^5. Результат виконання програми вивести у файл.

9.Виконати завдання 7 для повного зваженого графа з кіль­ кістю вершин N ^ 12. Результат виконання програми вивес­ ти у файл.

10.Виконати порівняльний аналіз виконання завдань 2-3, 5-6 та 8-9 щодо ефективності роботи відповідних алгоритмів.

•Запитання для самоконтролю

1.Яка відмінність між точними, наближеними й евристичними ме­ тодами розв'язування задач?

2.У чому полягає суть евристичних методів?

3.У чому полягає суть наближених методів?

4.На яких відомих вам методах базується алгоритм Ейлера, що реалізує наближений розв'язок задачі про комівояжера?

5.Продемонструйте на власному прикладі покрокове виконання алгоритму Ейлера.

6.Сформулюйте алгоритм Ейлера знаходження наближеного розв'язку задачі комівояжера, обґрунтовуючи при цьому той факт, що отриманий розв'язок буде близьким до точного.

7.Яким чином в алгоритмі Ейлера використовується нерівність трикутника?

8.Запишіть фрагмент програми, що реалізує алгоритм Ейлера, і прокоментуйте його.

9.До якого типу методів можна віднести метод гілок і границь?

10.У чому полягає ідея застосування методу гілок і границь до розв'язання задачі про комівояжера, запропонованої Літтлом?

11.На власному прикладі продемонструйте роботу методу гілок і границь.

12.Якою є роль дерева розв'язку в знаходженні рішення задачі про комівояжера методом гілок і границь?

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

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

15.Якими є доведення щодо ефективності використання методу гілок і границь порівняно з повноперебірними алгоритмами?

16.Яким чином можна удосконалити алгоритм повного перебору варіантів для розв'язання задачі про комівояжера із застосуван­ ням методу гілок і границь? У чому полягає евристичний підхід щодо такого удосконалення?

17.Запишіть текст фрагментів програми, що реалізують цей алго­ ритм.

•

180

Основи лінійного програмування

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

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

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

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

математичного програмування.

181

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

Задачі математичного програмування поділяють на задачі

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

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

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

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

Перейдемо до конкретних прикладів задач лінійного про­ грамування.

Приклади задач лінійного програмування

Задача про використання сировини

Нехай деяке підприємство виробляє два види продукції Рх і Р 2 . Для випуску цих видів продукції необхідно використати три види сировини Of;, С2 та С3. Відомо, яка кількість кожної сировини витрачається для виробництва продукції Pj і Р2

182

відповідно. Відома також інформація про наявність усіх видів сировини на складі (табл. 1).

Таблиця 1

Прибуток від реалізації одиниці продукції Р1 становить 50 грн., а продукції Р2 - 40 грн.

Необхідно знайти розв'язок такої задачі: скільки необхідно виробити продукції Рх і Р2 для отримання максимального при­ бутку.

Створимо математичну модель даної задачі. Позначимо хх - кількість одиниць продукції Р 1 ? а х2 - кількість одиниць про­ дукції Р 2 . Тоді, враховуючи кількість одиниць сировини, що витрачається на виготовлення одиниці продукції, а також за­ паси сировини, одержимо систему нерівностей, яка одночасно є системою обмежень для розв'язку поставленої задачі:

'2хх+Ьхг <20;

• 8^+5^2 ^ 40; 5^+6x2 <30 .

Ці обмеження говорять про те, що кількість сировини не мо­ же перевищувати її запасів на складі підприємства.

За умовою задачі прибуток підприємства складається з при­ бутку від реалізації х1 одиниць продукції Рг (50 грн. за кожну) та х2 одиниць продукції Р2 (40 грн. за кожну). Сумарний прибу­ ток розраховуватиметься за формулою:

L = 50:^ + 40х2.

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

Задача про складання харчового раціону

Сільськогосподарське підприємство виробляє корми для відгодівлі худоби. Для спрощення вважатимемо, що є два види кормів Р1іР2. При відгодівлі кожна тварина має отримувати на добу не менше 9 одиниць корисної речовини Сх, не менше 8 оди­ ниць сировини С2 і не менше 12 одиниць сировини С3. Вміст кількості одиниць корисних речовин в 1 кг кожного виду кор­ мів наведено у таблиці 2.

183

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

Для створення математичної моделі задачі позначимо х1 і х2 - кількість кілограмів корму Р1 і Р2 у денному раціоні відповідно. З урахуванням умов задачі отримаємо систему обмежень:

ох, т Хп ^ У5

• xl+2x2 ^ 8;

х1+6х2 > 12.

Якщо відомо, що 1 кг корму Рг коштує 4 грн., а 1 кг кор­ му Р2 - 6 грн., то загальну вартість раціону можна представи­ ти у вигляді такої лінійної функції:

L = 4х1 + 6х2 .

Сформульована задача зводиться до наступного: вибрати такі невід'ємні значення змінних хх і х2, які задовольняють систему обмежень і дають мінімальне значення L.

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

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

Нехай xv х2,..., хп - змінні, сенс яких полягає у наступному:

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

xt = 0 або X; = 1 для і = 1, 2, ..., п;

OJXJ + а2х2 + ... + апхп^А,

при яких функція L = с1х1 + с2х2 + ... + спхп набуває максималь­ ного значення.

184