Дискретне програмування

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

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

Рис. 13.

Кожний співробітник працює п’ять днів поспіль з двома вихідними днями. Щоденна потреба у персоналі задана у масиві Е11:К11, ставка денної оплати працівника – Е12:К12.

Кількість зайнятих працівників по дням тижня (Е10:К10) підраховується як сума добутків кількостей робітників у кожній групі на відповідні позначки у графіку роботи (одиницю чи нуль). Одиниця у графіку роботи означає, що відповідна група у цей день працює, нуль позначає вихідний день. Відповідна формула вводиться у клітину Е10: {=СУММ($D$3:$D$9*E3:E9)} і потім копіюється на клітини масиву F10:K10.

Денна оплата працівників Е13:К13 визначається як добуток кількості працівників, працюючих у цей день, та ставки оплати за формулою масиву {=E10:K10*E12:K12}. Загальна тижнева зарплата (Е14) – це сума денних оплат співробітників (=СУММ(E13:K13)).

Формулювання математичної моделі задачі:

v змінні для вирішення задачі: кількість робітників у кожній групі (D3:D9);

v визначення цільової функції (критерію оптимізації): серед усіх припустимих значень змінних знайти таку кількість робітників у кожній групі, щоб витрати на оплату праці (Е14) були мінімальними;

v обмеження на змінні: кількість співробітників у кожній групі повинна бути цілим числом (D3:D9=целое) та не може бути від’ємною (D3:D9>=0);

v кількість зайнятих працівників кожного дня не може бути менше щоденної потреби (Е10:К10>=Е11:К11).

Для вирішення даної задачі будемо використовувати програму Excel, інструмент Поиск решения. Обираємо опцію Сервис, Поиск решения. У вікні Поиск решения встановлюємо мінімальне значення у цільовій клітині Е14, вказуємо для зміни клітини D3:D9 і додаємо обмеження. Обрання лінійної моделі у діалоговому вікні параметрів прискорить отримання результату.

Отриманий розв’язок показаний на рис. 14.

Рис. 14.

Приклад задачі про призначення. На кафедрі університету к ожен з викладачів може провести заняття за планом роботи. Погодинна оплата викладачу за заняття певного виду наведена у табл. 28.Скласти план проведення учбових занять, щоб усі види занять були проведені, кожен викладач проводив заняття одного виду, а сумарна вартість погодинної оплати була мінімальною.

Таблиця 28

Викладачі	Погодинна оплата занять

Для вирішення даної задачі будемо використовувати програму MS Excel, процедуру Поиск решения. Запишемо умови задачі у робочій книзі ( рис. 15).

У клітинах В4:Е7 одиниця означає, що відповідний викладач проводить вказаний вид занять, нуль – не проводить. Як вихідні дані вводимо нулі у масив клітин В4:Е7. У масиві F4:F7 підсумовуємо значення по рядках масиву В4:Е7, у масиві В8:Е8 – по стовпцях.

Сумарна вартість погодинної оплати у клітині Е16 підраховується як сума добутків погодинної вартості видів занять на відповідні позначки у таблиці призначень (одиницю чи нуль) {=СУММПРОИЗВ(B12:E15;B4:E7)}.

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

Рис. 15.

Формулювання математичної моделі задачі:

v змінні для вирішення задачі: таблиця призначень (В4:Е7);

v визначення цільової функції (критерію оптимізації): серед допустимих значень змінних знайти такі, що мінімізують сумарну вартість погодинної оплати (Е16);

v обмеження на змінні: клітини таблиці призначень можуть містити нулі або одиниці (В4:Е7=целое, В4:Е7≥0, В4:Е7≤1);

v кожен викладач проводить один вид занять, оскільки модель збалансована, то всі заняття повинні бути проведені, а всі викладачі задіяні, у загальному вигляді: F4:F7≥1, B8:E8≥1.

У вікні Сервис, Поиск решения встановлюємо мінімальне значення у цільовій клітині E16, вказуємо для зміни клітини В4:E7 і додаємо обмеження.

Результати вирішення задачі показані на рис. 16. Всі заняття проведені, кожен викладач проводить один вид занять.

Рис. 16.

Завдання до розділу «Дискретне програмування»

На кафедрі університету к ожен з викладачів може провести заняття за планом роботи. Погодинна оплата викладачу за заняття певного виду наведена у таблицях 29 - 40.Скласти план проведення учбових занять, щоб усі види занять були проведені, кожен викладач, бажано, проводив заняття одного виду, а сумарна вартість погодинної оплати була мінімальною.

1. Таблиця 29

Викладачі	Погодинна оплата занять

2. Таблиця 30

Викладачі	Погодинна оплата занять

3. Таблиця 31

Викладачі	Погодинна оплата занять

4. Таблиця 32

Викладачі	Погодинна оплата занять

5. Таблиця 33

Викладачі	Погодинна оплата занять

6. Таблиця 34

Викладачі	Погодинна оплата занять

7. Таблиця 35

Викладачі	Погодинна оплата занять

8. Таблиця 36

Викладачі	Погодинна оплата занять

9. Таблиця 37

Викладачі	Погодинна оплата занять

10. Таблиця 38

Викладачі	Погодинна оплата занять

11. Таблиця 39

Викладачі	Погодинна оплата занять

12. Таблиця 40

Викладачі	Погодинна оплата занять

Дата добавления: 2014-11-29