<< Предыдущая

стр. 4
(из 5 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

[+0]


Рис. 3. Поиск максимального потока


Второе действие. Помечаем вершину i индексом -j, если, во-
первых, существует дуга (j; i), и, во-вторых, j ? Z, i ? Z, xij > 0
(легко видеть, что пометки первого типа увеличивают поток по
дуге, а пометки второго типа – уменьшают).
Если в результате этого типа пометок мы пометили выход, то
поток можно увеличить. Двигаясь обратно, можно найти цепь, в
которой каждая вершина помечена номером предыдущей (знак
пометки не важен).
Рассмотрим цепь µ = (0; 3; 2; 1; 4; 5), приведенную на рисун-
ке 3. Полученные в результате второго действия потоки обозначе-
ны жирным шрифтом.
Критерий остановки алгоритма следующий [7, 8]: если, при-
меняя пометки обоих типов, вершину n пометить не удалось, то
полученный поток имеет максимальную величину.
Поток минимальной стоимости. Предположим, что задана
сеть с пропускными способностями дуг cij. Пусть также для каждой
дуги (i; j) заданы число sij, интерпретируемое как затраты (напри-
мер, затраты на перевозку единицы груза из вершины i в вершину
j). Задача поиска потока минимальной стоимости заключается в
нахождении для заданной величины ? суммарного потока ее рас-
пределения по дугам, минимизирующего сумму затрат. Общие
методы решения задачи о потоке минимальной стоимости рас-
сматриваются в [5, 7, 19].
Частным случаем задачи о потоке минимальной стоимости яв-
ляется транспортная задача, в которой имеется двудольный граф
(двудольным называется граф, множество вершин которого может

19
быть разбито на два непересекающихся подмножества, причем
ребра (дуги) графа соединяют вершины только из разных подмно-
жеств), представленный на рисунке 4: вершины сети разбиты на
две группы – m поставщиков и n потребителей.
Известно [15], что граф является двудольным тогда и только
тогда, когда он не содержит циклов нечетной длины, или когда в
нем все простые циклы имеют четную длину (теорема Кенига).
Для поставщиков заданы имеющиеся у них количества единиц
товара (груза и т.д.) ai, i = 1, m , для потребителей – требуемые им
количества единиц товара bi, i = 1, n . Также известны затраты sij
перевозки единицы товара от i-го поставщика j-му потребителю.
m n

?a ?b
Пусть задача является замкнутой, то есть – суммар-
=
i i
i =1 i =1
ное предложение равно суммарному спросу (вводя фиктивного
поставщика или фиктивного потребителя любую незамкнутую
задачу можно свести к замкнутой). Требуется определить потоки
товаров от потребителей к поставщикам, минимизирующие сум-
марные затраты.

ПОСТАВЩИКИ ПОТРЕБИТЕЛИ

s11
1
1
s1j b1
...
...




si1
a1 bi
sij
0 z
j
i
sin
...
...




am bn
smj
n
m
smn

Рис. 4. Транспортная задача

Формально транспортную задачу можно записать в виде:
n
m

? ?x sij > min
(1) ij
{ xij ? 0}
i =1 j =1



20
n

?x = ai, i = 1, m
(2) ij
j =1
m

?x = bj, j = 1, n .
(3) ij
i =1
Добавляя к двудольному графу вход «0» и выход «z» и соеди-
няя вход и выход с остальными вершинами дугами с потоком
x0i = ai, , i = 1, m , xjz = bj, j = 1, n , получаем задачу о потоке мини-
мальной стоимости. Алгоритмы решения транспортной и двойст-
венной к ней задач описаны в [7, 12].
Частным случаем транспортной задачи является задача о на-
значении, заключающаяся в следующем: имеются n человек (ра-
ботников), которые могут выполнять различные работы (занимать
различные должности), число работ равно числу работников (введя
фиктивные должности и/или фиктивные работы, всегда можно
незамкнутую задачу привести к рассматриваемой замкнутой фор-
ме). Известны затраты sij на назначение i-го работника на j-ю
должность (например, минимальная зарплата, за которую он согла-
сится работать на этой должности). Требуется найти назначение
работников на должности (каждого работника на одну и только
одну должность), минимизирующее суммарные затраты (если sij
интерпретируется как эффективность от работы i-го работника на
j-ой должности, то оптимальное назначение должно максимизиро-
вать суммарную эффективность).
Формально задачу о назначении можно записать в виде (ср. с
(1)-(3)):
n
n

? ?x sij > min
(4) ij
{ xij ?{0 ; 1}}
i =1 j =1
n
? xij = 1, i = 1, n
(5)
j =1
n

?x = 1, j = 1, n .
(6) ij
i =1
Известны множество методов решения задачи о назначении
[7, 12]. Рассмотрим один из них на следующем примере.


21
Пусть имеются n = 3 работника и столько же работ. Матрица
123
затрат имеет вид: .
247
538
Алгоритм 8.
Шаг 0. Назначаем каждого человека на самую дешевую для
него работу (назначение выделено на рисунке 5 тонкими дугами),
если sij = min sik
? 1,
0
то есть положим xij = ? . Если при этом
k
0, в противном случае
?
назначение является допустимым (то есть все работы выполняют-
ся), то решение получено. Если имеется «дисбаланс», то есть не
n

?x 0
все работы выполняются (? j1: > 1), то переходим к сле-
ij1
i =1
дующему шагу.

РАБОТНИКИ ДОЛЖНОСТИ

1
[0]
[-1] 1
1
2

2
4 [1]
2
[-2] 2
7
3
3
5
8 [2]
[-2] 3
3



Рис. 5. Задача о назначении


Шаг k. Введем два подмножества множества дуг: P1 = {(i; j) |
xij = 1}, P2 = {(i; j) | xij = 0}. Примем множество вершин-работ, на
которых назначено несколько работников за вход сети, множество
вершин-работ, которые не выполняются – за выход сети. Изменим
направления дуг из множества P1 на обратные и примем их длины
равными (-sij), длины дуг из множества P2 примем равными sij.
Найдем путь µk минимальной длины в полученной сети (потенциа-
22
лы вершин, вычисляемые при нахождении кратчайшего пути в
рассматриваемом примере, приведены в квадратных скобках).
? xij ?1 , если (i; j ) ? µ k
?
k
k
=?
Далее полагаем xij .
k ?1
?1 ? xij , если (i; j ) ? µ
k
?
В результате в рассматриваемом примере за один шаг получим
оптимальное назначение, отличающееся от найденного на нулевом
шаге тем, что первому работнику назначается третья работа (см.
дугу, обозначенную двойными линиями на рисунке 5).
На каждом шаге число «дисбалансов» уменьшается на едини-
цу. Следовательно, число шагов алгоритма не превышает числа
«дисбалансов», которое конечно.
Аналогичным способом можно решить любую транспортную
задачу (искать кратчайший путь из множества вершин, в которые
доставили товара больше, чем требуется, во множество вершин,
где товара не хватает).
Решение общего случая задачи о потоке минимальной стоимо-
сти основывается на рассмотрении двойственной задачи [7, 12].


5. Задачи календарно-сетевого планирования и управления

Рассмотрим проект, состоящий из набора операций (работ).
Технологическая зависимость между операциями задается в виде
сети (сетевого графика). При этом дуги сети соответствуют опе-
рациям, а вершины событиям (моментам окончания одной или
нескольких операций). Для каждой операции (i; j) задана ее про-
должительность tij. Методы описания и исследования сетевых
графиков изучаются в теории календарно-сетевого планирования и
управления (КСПУ) [2, 3, 7, 8, 10, 11, 16].
Задача определения продолжительности проекта (управле-
ние временем). Легко видеть, что продолжительность проекта
определяется путем максимальной длины, называемым критиче-
ским путем. Методы поиска пути максимальной длины описаны
выше. Критический путь в сети на рисунке 6 выделен двойными
дугами и равен 16.



23
3
1 3
2
7
4
5
0
4 5

6 4

<< Предыдущая

стр. 4
(из 5 стр.)

ОГЛАВЛЕНИЕ

Следующая >>