Пусть на автопредприятии (или в подразделении автопредприятия) имеются 
водителей 
, 
, …, 
, …, 
, которых необходимо назначить (распределить) по 
маршрутам 
, 
, …, 
, …, 
. На каждом из указанных маршрутов может работать любой из этих водителей, однако выручка по разным водителям и по разным маршрутам различается. В результате проведенных наблюдений зафиксирована выручка водителей по разным маршрутам.
Обозначим 
- выручку 
-го водителя по 
-му маршруту, а 
- назначение -го водителя на -й маршрут: = 
Условие задачи о назначениях можно представить в табличном виде (табл. 4).
Из табл. 4 следует, что если водитель назначен на маршрут , то 
, а остальные элементы этой строки будут равны 0. Таким образом, сумма переменных для любой строки или столбца равна 1, т.е. можно записать следующие условия: 
(6.1)
В качестве целевой функции (критерия оптимальности) принимаем суммарную производительность сотрудников: 
(6.2)
Таким образом, сущность задачи о назначениях состоит в отыскании таких неотрицательных значений 
, чтобы целевая функция (общая выручка) была максимальной.
Таблица 4
Условие задачи о назначениях
| Водители | Маршруты | |||||
| R 1 | R 2 | … | Ri | … | Rn | |
| S 1 | 
| 
| … | 
| … | 
|
| S 2 | 
| 
| … | 
| … | 
|
| … | … | … | … | … | … | … |
| Si | 
| 
| … |
| … | 
|
| … | … | … | … | … | … | … |
| Sn | 
| 
| … | 
| … | 
|
Рассмотренную выше задачу можно классифицировать как комбинаторную (переборную) задачу. Пример решения подобной задачи представлен ниже.
Задача 3.1. На малом автопредприятии имеются три водителя, которых необходимо распределить по трем различным маршрутам. Предварительно была определена выручка 
каждого водителя по каждому из трех маршрутов (табл. 5).
Таблица 5
Выручка каждого водителя по каждому из трех маршрутов
| Работники | Работы | ||
| R 1 | R 2 | R 3 | |
| S 1 | 
| 
| 
|
| S 2 | 
| 
| 
|
| S 3 | 
| 
| 
|
Запишем все возможные распределения 3 водителей по 3 маршрутам в виде следующих триад:
1) 
; 2) 
; 3) 
;
4) 
; 5) 
; 6) 
.
Для каждой из триад рассчитаем суммарную выручку:
; 
;
; 
;
; 
.
Сравнивая полученные суммарные выручки, соответствующие каждой из триад, видим, что наибольшая выручка соответствует 6-й триаде: 
. Следовательно, оптимальное распределение водителей по маршрутам представлено триадой , т.е. 1-й водитель назначается на 3-й маршрут, 2-й - на 1-й, 3-й - на 2-й.
Как отмечалось выше, задача о назначениях является частным случаем ТЗ.
Задача 3.2. На автопредприятии имеются 6 водителей, которых необходимо распределить на пять различных маршрутов. Предварительно были определены выручка 
каждого водителя по каждому из пяти маршрутов (табл. 6) и штрафы каждого водителя по каждому из пяти маршрутов (табл. 7). необходимо назначить (распределить) водителей по маршрутам так, чтобы доход предприятия был максимальный.
Таблица 6
выручка каждого водителя по каждому из пяти маршрутов
| Σ по стр. | Выработка за неделю | Водители | |||||
| Маршрут: |
Таблица 7
Штрафы каждого водителя по каждому из пяти маршрутов
| Σ по стр. | Штрафы | Водители | |||||
| Маршрут: |
Полученную ЗРТ будем решать средствами Excel, используя надстройку Сервис \ Поиск решения.
Выполним последовательно следующие действия в среде Excel:
- Создадим форму для ввода условий задачи и введем в нее исходные данные из таблиц 6 и 7 (см. рис.11).
- Укажем адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). Оптимальные значения компонент матрицы решений будут помещены в ячейках B19:F24 (матрица «назначения»), оптимальное значение целевой функции – в ячейке F29. Значение суммарной выработки – в ячейке B29. Сумма штрафов – в ячейке D29.
- Введем зависимость для суммарной выработки, суммы штрафов и целевой функции, для этого нужно: установить курсор в ячейку В29, на панели инструментов нажать кнопку Мастер функций. В диалоговом окне Мастер функций выбрать категорию Математические и функцию СУМПРОИЗВ; в диалоговом окне Аргументы функций в строку «Массив 1» ввести B2:F7, в строку «Массив 2» ввести B19:F24. Добавить множитель 70000.
- Чтобы ввести зависимость для суммы штрафов нужно установить курсор в ячейку D29, на панели инструментов нажать кнопку Мастер функций. В диалоговом окне Мастер функций выбрать категорию Математические и функцию СУМПРОИЗВ; в диалоговом окне Аргументы функций в строку «Массив 1» ввести B11:F16, в строку «Массив 2» ввести B19:F24. Добавить множитель 700.
- Чтобы определить зависимость для целевой функции нужно ввести в ячейку F29 формулу: = B29 – F29.
Введем зависимости для ограничений:
- в ячейки В25:F25 нужно ввести функции СУММ(B19:B24), …, СУММ(F19:F24) соответственно; в ячейки G19:G24 нужно ввести функции СУММ(B19:F19), …, СУММ(B24:F24) соответственно.
- Присвоив значение «1» изменяемым ячейкам, получим следующую форму для решения задачи (рис. 11):
| A | B | C | D | E | F | G | H | I | |
| Выработка за неделю | Водители | ||||||||
| Маршрут: | |||||||||
| Штрафы | |||||||||
| Маршрут: | |||||||||
| Назначения | Водители | ||||||||
| Σпо столб | Σ по стр. | ||||||||
| Выработка | Штрафы | Сальдо | |||||||
| (Fцел) | |||||||||
Рис. 11. Форма для ввода условий задачи
Выполним команду меню Сервис \ Поиск решения. В диалоговом окне Поиск решения нужно:
a. назначить целевую ячейку – в данном случае В29;
b. ввести направление целевой функции – Максимальному значению;
c. в строке Изменяя ячейки ввести диапазон B19:F14 (адреса искомых переменных);
d. ввести ограничения, для этого нажать на кнопку Добавить и ввести данные в диалоговое окно Добавление ограничения: – значения в ячейках В25:F25 должны быть равны 1, а значения в ячейках G19:G24 должны быть равны 1 или 0.
В результате диалоговое окно Поиск решения выглядит так, как показано на рис.12.
7. Введем параметры для решения ЗЛП. Для этого в диалоговом окне Поиск решения нужно нажать на кнопку Параметры и в диалоговом окне Параметры поиска решения установить флажки в окнах Линейная модель и Неотрицательные значения (рис. 13). После этого нужно нажать на кнопку Выполнить диалогового окна Поиск решения.
Рис. 12. Диалоговое окно Поиск решения Рис. 13. Диалоговое окне Параметры поиска решения
Через некоторое время появляется диалог Результаты поиска решения и исходная таблица с заполненными ячейками B19:F24, оптимальное значение целевой функции – в ячейке F29. Значение суммарной выработки – в ячейке B29. Сумма штрафов – в ячейке D29 (рис. 14).
Полученное решение (табл. 8) означает, что на 1-й маршрут нужно назначить водителя под номером 6; на 2-й маршрут – водителя под номером 1; на 3-й маршрут – водителя под номером 5; на 4-й маршрут – водителя под номером 3; на 5-й маршрут – водителя под номером 2; водителя под номером 4 никуда не назначать, т.к. его работа приносит наименьший из всех доход.
Таблица 8
Матрица решений имеет вид
| Назначения на маршруты | ||||||
| Σ по стр. | Водители | |||||
Максимальный суммарный доход составит 1597400 ед.
| A | B | C | D | E | F | G | H | I | |
| Выработка за неделю | |||||||||
| Маршрут: | |||||||||
| Штрафы | |||||||||
| Маршрут: | |||||||||
| Назначения | Водители | ||||||||
| Σпо столб | Σ по стр. | ||||||||
| Выработка | Штрафы | Сальдо | |||||||
| (Fцел) | |||||||||
Рис. 14. Результаты поиска решения
Контрольные вопросы:
1. Какова постановка задачи о назначениях?
2. В чем отличие модели задачи о назначениях от модели ТЗ?
3. Каковы исходные и искомые параметры задачи о назначениях?
4. Как записывается математическая модель задачи о назначениях.
5. Почему полученное решение не поставило водителя под номером 4 ни на какой маршрут?
6. Посчитайте суммарные выработки и штрафы каждого водителя по исходным данным полученной индивидуальной задачи.