79
Для каждого работника
A
i
на рабочем месте
B
j
известна производитель-
ность труда
c
ij
. Необходимо определить, кого и на какую работу следует назна-
чить, чтобы добиться максимальной суммарной производительности при усло-
вии, что каждый работник может быть назначен только на одну работу.
Обозначим
x
ij
назначение
i
-го работника на
j
-ю работу. Так как количе-
ство работников равно количеству работ, то
x
ij
может принимать только два
значения: 1, если
i
-й работник назначен на выполнение
j
-й работы; 0, если не
назначен. При назначении
i
-го работника на
j
-ю работу производительность
равна
c
ij
x
ij
.
Следовательно, необходимо найти матрицу распределения по долж-
ностям
X
, которая обеспечивает максимальное значение линейной функции
m
i
n
j
ij
ij
x
c
X
F
1 1
max
при ограничениях:
. ,1 , ,1
,0
,
,1 ,1
, ,1 ,1
1
1
n jm i
x
n j
x
m i
x
ij
m
i
ij
n
j
ij
Умножая линейную функцию на «
1» приводим задачу к транспортной,
в которой объем запасов каждого поставщика и объем потребностей каждого
потребителя равны единице.
7. Построение кольцевых маршрутов.
Коммерческая деятельность
обычно связана с командировками, поездками по городам для заключения сде-
лок. Расстояние между любой парой множества из
n
городов известны и со-
ставляют
.
;
,1
;
,1
j i
n j
m i
a
ij
Если прямого маршрута между городами
i
и
j
не существует, то допускают, что
ij
a
.
Коммерсант, выезжая из какого-либо города, должен посетить все горо-
да, побывав в каждом из них один и только один раз, и вернуться в исходный
город. Необходимо определить такую последовательность объезда городов, при
которой длина маршрута была бы наименьшей.
Экономико-математическая постановка этой задачи может быть пред-
ставлена как задача целочисленного линейного программирования. Перемен-
ные определим следующим образом:
x
ij
= 1, если коммивояжер переезжает из
города
i
в город
j
; в противном случае
x
ij
= 0.
