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

Розглянемо можливості засобу Пошук рішення для вирішення задачі про призначення.

У нашому конкретному випадку задача про призначення формулюється таким чином. Є чотири робітники і чотири види робіт. Вартість сij виконання i-м робітником j-ї роботи приведені в таблиці 5.8, де під рядком розуміємо робітника, а під стовпцем — роботу, яку він виконує

Таблиця 5.8 - Вартість виконання робіт

РобітникиВиди робіт

1463

91079

45117

8785

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

Примітка

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

Для рішення даної задачі спочатку побудуємо її математичну модель. Позначимо символом хij змінну, що має тільки два допустимих значення: 0 чи 1. Такі змінні називаються двоїстими. Причому, будемо вважати, що:

- хij = 1, якщо і-м робітником виконується j-а робота;

- хij = 0, якщо і -м робітником не виконується j-а робота.

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

• мінімізувати

,

• при обмеженнях

Î{0,1}, іÎ[1,4], јÎ[1,4].

Для рішення цієї задачі за допомогою засобу Пошук рішення необхідно виконати деякі попередні дії:

1. В чарунки діапазону А2 : D5 уведіть вартості робіт.

2. Відведіть чарунки діапазону F2 : І5 під невідомі.

3. Введіть в чарунку Ј1 цідбову функцію, що обчислює вартість робіт