Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Метод_МО_2к.doc
Скачиваний:
8
Добавлен:
01.07.2025
Размер:
1 Мб
Скачать
☆

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

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

Приклад задачі о плануванні штатного розкладу. Для працівників з п’ятиденним робочим тижнем та двома вихідними днями потрібно підібрати графік роботи, що забезпечує потреби обслуговування клієнтів за умови мінімальних витрат на оплату праці. Потреба у працівниках по дням тижня та ставка денної оплати працівників задані. Умови задачі представлені на рис. 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)).

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

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

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

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

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

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

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

Рис. 14.

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

Таблиця 28

Викладачі

Погодинна оплата занять

1

2

3

4

1

350

420

610

200

2

890

130

650

900

3

430

520

600

720

4

830

600

780

470

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

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

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

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

Рис. 15.

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

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

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

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

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

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

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

Рис. 16.