Материал: 4758
сумма переменных xij для любой строки или столбца равна 1, т.е. можно
n
записать следующие условия: xij 1, (i 1, 2, ..., n) (6.1)
i 1
n
xij 1, ( j 1, 2, ..., n)
j 1
xij 0.
В качестве целевой функции (критерия оптимальности) принимаем
суммарную производительность сотрудников: Z aij xij |
max . |
|
n |
n |
|
i 1 |
j 1 |
|
(6.2)
Таким образом, сущность задачи о назначениях состоит в отыскании таких неотрицательных значений xij , чтобы целевая функция (общая выручка)
была максимальной.
|
|
|
|
|
|
|
|
Таблица 4 |
|
|
|
Условие задачи о назначениях |
|
|
|
||||
Водите |
|
|
|
Маршруты |
|
|
|
||
ли |
R1 |
R2 |
… |
|
Ri |
… |
|
Rn |
|
|
x11 |
x12 |
|
|
x1 j |
|
|
x1n |
|
S1 |
a11 |
a12 |
… |
|
a |
|
… |
|
a1n |
|
|
|
|
|
1 j |
|
|
|
|
|
x21 |
x22 |
|
|
x2 j |
|
|
x2n |
|
S2 |
a21 |
a22 |
… |
|
a |
2 j |
… |
|
a2n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
… |
… |
… |
… |
|
… |
… |
|
… |
|
|
xi1 |
xi 2 |
|
|
xij |
|
|
xin |
|
Si |
ai1 |
ai 2 |
… |
|
a |
ij |
… |
|
ain |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
… |
… |
… |
… |
|
… |
… |
|
… |
|
Sn |
xn1 |
xn2 |
|
|
xnj |
|
|
xnn |
|
|
an1 |
an2 |
… |
|
a |
nj |
… |
|
ann |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рассмотренную выше задачу можно классифицировать как комбинаторную (переборную) задачу. Пример решения подобной задачи представлен ниже.
Задача 3.1. На малом автопредприятии имеются три водителя, которых необходимо распределить по трем различным маршрутам. Предварительно
была определена выручка |
aij каждого |
водителя по |
каждому из трех |
|||||
маршрутов (табл. 5). |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
Таблица 5 |
|
|
Выручка каждого водителя по каждому из трех маршрутов |
|||||||
|
|
|
|
|
Работы |
|
|
|
|
Работники |
|
R1 |
|
R2 |
|
R3 |
|
|
S1 |
|
x11 |
|
x12 |
|
x13 |
|
|
|
|
a11 10 |
|
a12 15 |
|
a13 25 |
|
|
S2 |
|
x21 |
|
x22 |
|
x23 |
|
|
|
|
a21 20 |
|
a22 10 |
|
a23 5 |
|
S3 |
x31 |
x32 |
x33 |
|
a31 15 |
a32 10 |
a33 10 |
Запишем все возможные распределения 3 водителей по 3 маршрутам в виде следующих триад:
1) |
(x11, x22 , x33 ) ; |
2) |
(x11, x23 , x32 ) ; |
3) |
(x12 , x21, x33 ) ; |
|
4) |
(x12 , x23 , x31 ) ; |
5) |
(x13 , x22 , x31 ) ; |
6) |
(x13 , x21, x32 ) . |
|
Для каждой из триад рассчитаем суммарную выручку: |
||||||
y1 1 10 1 10 1 10 30 ; |
y2 1 10 1 5 1 10 25 ; |
|||||
y3 1 15 1 20 1 10 45 ; |
y4 1 15 1 5 1 15 35 ; |
|||||
y5 1 25 1 10 1 15 45 ; |
y6 1 25 1 20 1 10 55 . |
|||||
Сравнивая полученные суммарные выручки, соответствующие каждой из триад, видим, что наибольшая выручка соответствует 6-й триаде: y6 55.
Следовательно, оптимальное распределение водителей по маршрутам представлено триадой (x13 , x21, x32 ) , т.е. 1-й водитель назначается на 3-й
маршрут, 2-й на 1-й, 3-й на 2-й.
Как отмечалось выше, задача о назначениях является частным случаем ТЗ. Задача 3.2. На автопредприятии имеются 6 водителей, которых необходимо
распределить на пять различных маршрутов. Предварительно были определены
выручка |
aij каждого водителя по каждому из пяти маршрутов (табл. 6) |
и |
штрафы |
каждого водителя по каждому из пяти маршрутов (табл. |
7). |
Необходимо назначить (распределить) водителей по маршрутам так, чтобы доход предприятия был максимальный.
Таблица 6 Выручка каждого водителя по каждому из пяти маршрутов
Σпо
стр. |
Выработка за неделю |
|
Водители |
||||
|
4 |
6 |
5 |
4 |
3 |
|
1 |
|
4 |
3 |
2 |
4 |
3 |
|
2 |
|
3 |
4 |
5 |
4 |
1 |
|
3 |
|
3 |
2 |
1 |
2 |
2 |
|
4 |
|
2 |
4 |
5 |
4 |
3 |
|
5 |
|
5 |
4 |
3 |
4 |
3 |
|
6 |
Маршр |
|
|
|
|
|
|
|
ут: |
1 |
2 |
3 |
4 |
5 |
|
|
Таблица 7 Штрафы каждого водителя по каждому из пяти маршрутов
Σпо
стр. |
Штрафы |
|
|
|
|
Водители |
|
|
3 |
5 |
4 |
3 |
2 |
|
1 |
|
3 |
2 |
1 |
3 |
2 |
|
2 |
|
2 |
3 |
4 |
3 |
0 |
|
3 |
|
2 |
1 |
0 |
1 |
1 |
|
4 |
|
1 |
3 |
4 |
3 |
2 |
|
5 |
|
4 |
3 |
2 |
3 |
2 |
|
6 |
Маршр |
|
|
|
|
|
|
|
ут: |
1 |
2 |
3 |
4 |
5 |
|
|
Полученную ЗРТ будем решать средствами Excel, используя надстройку
Сервис \ Поиск решения.
Выполним последовательно следующие действия в среде Excel:
1.Создадим форму для ввода условий задачи и введем в нее исходные данные из таблиц 6 и 7 (см. рис.11).
2.Укажем адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). Оптимальные значения компонент матрицы решений будут помещены в ячейках B19:F24 (матрица «назначения»), оптимальное значение целевой функции – в ячейке F29. Значение суммарной выработки – в ячейке B29. Сумма штрафов – в ячейке D29.
3.Введем зависимость для суммарной выработки, суммы штрафов и целевой функции, для этого нужно: установить курсор в ячейку В29, на панели инструментов нажать кнопку Мастер функций. В диалоговом окне Мастер функций выбрать категорию Математические и функцию СУМПРОИЗВ; в диалоговом окне Аргументы функций в
строку «Массив 1» ввести B2:F7, в строку «Массив 2» ввести B19:F24. Добавить множитель 70000.
4.Чтобы ввести зависимость для суммы штрафов нужно установить курсор в ячейку D29, на панели инструментов нажать кнопку Мастер функций. В диалоговом окне Мастер функций выбрать категорию
Математические и функцию СУМПРОИЗВ; в диалоговом окне Аргументы функций в строку «Массив 1» ввести B11:F16, в строку
«Массив 2» ввести B19:F24. Добавить множитель 700.
5.Чтобы определить зависимость для целевой функции нужно ввести в
ячейку F29 формулу: = B29 – F29.
Введем зависимости для ограничений:
-в ячейки В25:F25 нужно ввести функции СУММ(B19:B24), …, СУММ(F19:F24) соответственно; в ячейки G19:G24 нужно ввести функции СУММ(B19:F19), …, СУММ(B24:F24) соответственно.
6.Присвоив значение «1» изменяемым ячейкам, получим следующую форму для решения задачи (рис. 11):
|
|
|
|
A |
|
|
B |
|
|
C |
|
|
D |
|
|
E |
|
|
F |
|
|
G |
|
|
H |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
1 |
|
|
|
|
|
Выработка за неделю |
|
|
|
|
|
|
|
|
|
|
|
Водители |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
2 |
|
22 |
|
4 |
|
6 |
|
|
5 |
|
4 |
|
3 |
|
|
|
|
1 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
3 |
|
16 |
|
4 |
|
3 |
|
|
2 |
|
4 |
|
3 |
|
|
|
|
2 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
4 |
|
17 |
|
3 |
|
4 |
|
|
5 |
|
4 |
|
1 |
|
|
|
|
3 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
5 |
|
10 |
|
3 |
|
2 |
|
|
1 |
|
2 |
|
2 |
|
|
|
|
4 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
6 |
|
18 |
2 |
|
4 |
5 |
4 |
3 |
|
5 |
|
|
|
|
|
|||||||
|
7 |
|
19 |
5 |
|
4 |
3 |
4 |
3 |
|
6 |
|
|
|
|
|
|||||||
|
8 |
|
Маршру |
|
|
|
|
|
|
|
|
|
|
|
т: |
1 |
|
2 |
3 |
4 |
5 |
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
Штрафы |
|
|
|
|
|
|
|
|
11 |
|
17 |
3 |
|
5 |
4 |
3 |
2 |
|
1 |
|
|
|
|
|
|||||||
|
12 |
|
11 |
3 |
|
2 |
1 |
3 |
2 |
|
2 |
|
|
|
|
|
|||||||
|
13 |
|
12 |
2 |
|
3 |
4 |
3 |
0 |
|
3 |
|
14 |
|
5 |
2 |
|
1 |
0 |
1 |
1 |
|
4 |
|
15 |
|
13 |
1 |
|
3 |
4 |
3 |
2 |
|
5 |
|
16 |
|
14 |
4 |
|
3 |
2 |
3 |
2 |
|
6 |
|
|
|
|
|
|||||||
|
17 |
|
Маршру |
|
|
|
|
|
|
|
|
|
|
|
т: |
1 |
|
2 |
3 |
4 |
5 |
|
|
|
|
|
|
|
|
||||||
|
18 |
|
|
Назначения |
|
|
|
|
|
Водители |
|
|
19 |
|
|
1 |
|
1 |
1 |
1 |
1 |
5 |
1 |
|
20 |
|
|
1 |
|
1 |
1 |
1 |
1 |
5 |
2 |
|
21 |
|
|
1 |
|
1 |
1 |
1 |
1 |
5 |
3 |
|
22 |
|
|
1 |
|
1 |
1 |
1 |
1 |
5 |
4 |
|
23 |
|
|
1 |
|
1 |
1 |
1 |
1 |
5 |
5 |
|
24 |
|
|
1 |
|
1 |
1 |
1 |
1 |
5 |
6 |
|
25 |
|
Σпо столб |
6 |
|
6 |
6 |
6 |
6 |
Σ по стр. |
|
|
26 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Штраф |
|
Сальд |
|
|
|
|
27 |
|
|
|
|
|
|
|
|
||
|
|
|
|
Выработка |
|
ы |
|
о |
|
|
|
|
28 |
|
|
|
|
|
|
|
(Fцел) |
|
|
|
|
|
|
714000 |
|
|
|
|
708960 |
|
|
|
29 |
|
|
|
|
|
|
|
|
||
|
|
|
|
0 |
|
|
50400 |
|
0 |
|
|
Рис. 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
Матрица решений имеет вид
Назначения на маршруты |
|
|
|
||||
|
|
|
|
|
|
Σ по |
Водите |
1 |
2 |
3 |
4 |
5 |
стр. |
ли |
|
0 |
1 |
|
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
2 |
0 |
0 |
|
0 |
1 |
0 |
1 |
3 |
0 |
0 |
|
0 |
0 |
0 |
0 |
4 |
0 |
0 |
|
1 |
0 |
0 |
1 |
5 |
1 |
0 |
|
0 |
0 |
0 |
1 |
6 |
Максимальный суммарный доход составит 1597400 ед.
|
|
|
|
A |
|
|
B |
|
|
C |
|
|
D |
|
|
E |
|
|
F |
|
|
G |
|
|
H |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
1 |
|
|
|
|
|
Выработка за неделю |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
2 |
|
22 |
|
4 |
|
6 |
|
|
5 |
|
4 |
|
3 |
|
|
|
|
1 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
3 |
|
16 |
|
4 |
|
3 |
|
|
2 |
|
4 |
|
3 |
|
|
|
|
2 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
4 |
|
17 |
|
3 |
|
4 |
|
|
5 |
|
4 |
|
1 |
|
|
|
|
3 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
5 |
|
10 |
|
3 |
|
2 |
|
|
1 |
|
2 |
|
2 |
|
|
|
|
4 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
6 |
|
18 |
|
2 |
|
4 |
|
|
5 |
|
4 |
|
3 |
|
|
|
|
5 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
7 |
|
19 |
|
5 |
|
4 |
|
|
3 |
|
4 |
|
3 |
|
|
|
|
6 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
Маршру |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
т: |
1 |
|
2 |
|
|
3 |
|
4 |
|
5 |
|
|
|
|
|
|
|||||