Материал: 62_201

2.Які задачі розв'язує така математична дисципліна, як дослі­ дження операцій?

3.Як математичне програмування пов'язане з дослідженням опе­ рацій?

4.Яке відношення має математичне програмування до теорії прийняття рішень?

5.На які два типи можна поділити всі задачі математичного про­ грамування? Які їх характерні ознаки?

6.Які класи задач виділяються окремо у математичному програму­ ванні?

7.Як формулюється задача про використання сировини? Обґрун­ туйте, чому її можна віднести до задач лінійного програмування.

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

9.Як формулюється задача про рюкзак? Обґрунтуйте, чому її мож­ на віднести до задач лінійного програмування.

10.Як формулюється транспортна задача? Обґрунтуйте, чому її можна віднести до задач лінійного програмування.

11.Як формулюється загальна задача лінійного програмування?

12.Що називають системою обмежень задачі лінійного програму­ вання?

13.Що називають цільовою функцією задачі лінійного програмування?

14.Що називають допустимими розв'язками або планами задачі лінійного програмування? Скільки їх може бути? Обґрунтуйте свою відповідь.

15.Який розв'язок задачі лінійного програмування називається оп­ тимальним планом?

16.У чому полягає методика використання «заглушок» у програмі?

17.Сформулюйте алгоритм геометричного розв'язування задачі лінійного програмування від двох параметрів.

18.Виконайте алгоритм геометричного розв'язування задачі ліній­ ного програмування від двох параметрів на власному прикладі, пояснюючи його кроки.

Р19. Які можливі випадки одержання розв'язку задачі лінійного про­ грамування? Обґрунтуйте свою відповідь.

Задача про призначення

До задач лінійного програмування відноситься і задача про призначення. Вона формулюється наступним чином.

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

190

формація була занесена у таблицю Щ (і = 1, 2, ..., п; j = 1, 2, ..., пі). Необхідно знайти таке призначення всіх кандидатів на вакант­ ні посади, яке принесе максимальну користь підприємству.

Розглянемо конкретний приклад. Нехай кількість кандидатів на вакантні посади і кількість цих посад є однаковою (п = 5,т = 5), а таблиця коефіцієнтів корисності визначається за 10-бальною системою і представлена на малюнку 113, а.

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

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

Розглянемо наведений приклад (мал. 113, а). Він навмисне підібраний так, щоб найкращий варіант призначення можна було підібрати без спеціально розробленого алгоритму, а візу­ ально аналізуючи вхідні дані. Почнемо з кандидата 4. Він пре­ тендує лише на одну посаду 2'. Отже, перше призначення зроб­ лено 4 <» 2'. Другу посаду надалі виключаємо з перегляду. Розглянемо кандидата за номером 5, оскільки тепер його мож­ на призначити тільки на посаду 4': 5 о 4'. На посаду 5' претен-

191

дує лише один кандидат за номером 3, тому іншого вибору не­ має: 3 о 5'. Залишилось дві вакантні посади V і 3', на які пре­ тендує два кандидати 1 і 2. Однак на посаду V претендує тільки один кандидат за номером 1. Робимо це призначення: 1 <t> V. Останній крок є однозначним, оскільки залишився непризначеним кандидат за номером 2 і вакантною посада 3': 2 о З'. Вартість отриманого призначення становить 31.

Спробуємо знайти інший розподіл призначень: 1 <=> 3' (8), 2 » 2 ' (7), 3 о 1' (4). На цьому ланцюг призначень перери­ вається, оскільки кандидат за номером 4 претендує лише на одну посаду 3', а вона вже зайнята. Виявляється, що й інші спроби сформувати призначення для наведеного прикладу без­ перспективні.

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

Як бути в ситуації, коли кількість кандидатів і посад різна?

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

Утакому разі вони просто не будуть призначені.

Сформулюємо задачу про призначення в термінах лінійного програмування. Нехай задана таблиця корисності С при при­ значенні кожного з п кандидатів на кожну з т посад. Оскільки необхідно зробити вибір по одному елементу таблиці С у кожному її рядку і стовпці, сформуємо додаткову таблицю X, у якій всі елементи дорівнюють 0 або 1 (х^ {0,1}, і = 1, 2,..., п, j = 1, 2,.., т), у кожному рядку і стовпці розташовано лише по одному зна­ ченню 1

п

і=1

т

2jJfy$ 1,і = 1, 2, ...,п,

г=і

а сумарна кількість значень 1 у таблиці X дорівнює тіп(п, т)

пт

Х Х ^ ч = тіп(п,т).

і=1 ;=1

192

Виконання останньої умови означає, що зроблено макси­ мально можливе призначення: всі кандидати призначені на можливі посади {п < т), або всі посади зайняті кандидатами, що на них претендували (т < п).

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

Проаналізуємо роль таблиці X у побудові розв'язку задачі. Якщо елемент xtj = 0, то це означатиме, що відповідний елемент ctj не враховується в результуючому призначенні, якщо xtj - 1, то це означатиме, що кандидат і призначається на поса­ ду j і значення ctj додається до сумарної корисності призначен­ ня. Таким чином, якщо розглянути добуток Щ>Хф ТО ВІН врештірешт і визначатиме, враховується чи ні призначення кандида­ та і на посаду у.

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

пт

(=1 j=i

При формулюванні поставленої задачі необхідно знайти та­ ке розміщення значень 1 у таблиці X, при якому L сягне макси­ мального значення.

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

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

Переформулювати поставлену задачу з пошуку максимуму на пошук мінімуму зовсім не складно. Замінимо матрицю С на С", виконавши такі дії: знайдемо в ній максимальний елемент (наприклад, г) і віднімемо від нього кожний елемент матриці

с' • — г - С-.

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

пт

Оскільки значення Z-iZ-irxtj є константою, бо не залежить від

£=1 / = 1

вхідних даних таблиці С, а вираз zS^jCiixij є досліджуваною

j = l j=l

цільовою функцією L, то цільова функція L' запишеться так:

Тобто максимізуючи цільову функцію L, ми цим самим міні­ мізуємо відповідну їй функцію І/ і навпаки.

А тепер перейдемо до опису алгоритму розв'язування задачі про призначення, який носить назву «угорського» тому, що ба­ зується на ідеях наукової роботи угорця Егерварі, написаної в 1931 р.

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

Мал. 114

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

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

З тими самими міркуваннями підійдемо до коефіцієнтів призначення на кожну ./-ту посаду: зменшимо значення у кож­ ному стовпці таблиці С на значення найменшого елемента в кожному з них. Приведення по стовпцях таблиці, зображеної на малюнку 114, б, показано на малюнку 114, в. Коефіцієнт

194