ВУЗ:
Составители:
12
1.8. Задача о назначениях
Имеется n работников, которых требуется назначить на n работ. Извест-
но, что j-ю работу i-й работник будет выполнять с эффективностью c
ij
. Требу-
ется так распределить работников, чтобы максимизировать суммарную эф-
фективность.
Положим x
ij
=1, если i-й работник назначен на j-ю работу;
x
ij
=0, в противном случае, i, j= n,1 .
Математическая модель задачи выглядит следующим образом.
Целевая функция имеет вид:
∑∑
==
⋅
n
i
n
j
ijij
xc
11
→max.
ЦФ представляет суммарную эффективность.
Ограничения имеют вид:
∑
=
=
n
i
ij
x
1
1, j= n,1 , (1)
∑
=
=
n
j
ij
x
1
1, i= n,1 , (2)
x
ij
равно либо 0, либо 1.
Условия (1) означают, что каждый работник назначается только на одну
работу.
Условия (2) означают, что один работник выполняет только одну работу.
Данная задача является задачей линейного булева программирования.
1.9. Задача коммивояжера
Имеется n городов. Выезжая из исходного города А
1
, коммивояжер дол-
жен побывать во всех остальных городах по одному разу и вернуться в город
А
1
.
Задача заключается в определении последовательности объезда городов
при которой коммивояжеру требуется минимизировать некоторый критерий
эффективности: стоимость проезда, время в пути, суммарное расстояние и
т.д. Пусть задана матрица C=||c
ij
|| расстояний между городами и требуется
минимизировать суммарную длину пути.
Страницы
- « первая
- ‹ предыдущая
- …
- 10
- 11
- 12
- 13
- 14
- …
- следующая ›
- последняя »
