Для определения максимального потока в агрегируем ой сети обозначим через Р; множество верш ин из множества Y агрегируем ой сети, см еж ны х с верш иной i множества X . Величина м аксимального потока равна 123 Фп,ах = Z in in W ( ; Z m in ( C , ; R j ScP. (2.3) Для обоснования этой формулы заметим, что если добавить к двудольному графу вход О и вы ход Z, то мы получим агрегируем ую сеть. Ф рагм ент этой сети, содержащ ий верш ину i множества X показан на рис. 2.9. Рис. 2.9. Ф рагм ент сети, содержащ ий верш ину i множества X Применяя к этому фрагменту алгоритм определения потока максимальной величины для агрегируемой сети и сум м ируя по всем фрагментам, получаем (2.3). ■ ■ ■ Для рассматриваемого примера имеем Фтах"^ 7 + 6 + 10 = 23. Д у ги и верш ины разреза минимальной п р оп ускн о й способности показаны на рис. 2.8 двойны м и дугами или вершинами. Видно, что разделенные верш ины либо обе принадлежат разрезу (верш ины 2 и 2 '), либо ни одна из них не принадлежит разрезу (верш ины (1,1') и (3,3'). Следовательно, получен поток максимальной величины 23 для исходной сети. 3.3. Оптимальное размещение работ между исполнителями П усть в организации имеются I подразделений, располагаю щ их мощ ностями ресурсов одного вида. Обозначим Qi объем проектны х работ, ко то |
89 I I I I --1-----------1------------1----------ri j l l l l l l L l I I I I j ! ' I I 1 Рис. 3.2.8 ной длины выделен толстыми дугами. Этому пути соответствует решение, в котором на субподряд передаются работы 1,3 и 5. 3.3. Оптимальное размещение работ межпу подразделениями проектной организации Пусть в организации имеются i подразделений, располагающих мощностями ресурсов одного вида. Обозначим Qi объем проектных работ, который может выполнить iое подразделение, Wi объем i-ой работы, i = l,n . Требуется распределить работы между подразделениями, так, чтобы загрузка подразделений (или их перегрузка) была максимально равномерной. Обозначим Xj = 1 если i-я работа выполняется подразделением j, x,j = Ов противном случае. Тогда уровень загрузки (перегрузки) подразделения i можно оценить величиной F ,= — 2w,Xy. 'Jt J (3.3.1) Задача заключается в распределении работ по подразделениям так, чтобы минимизировать 1 i (3.3.2) Рассмотр™ сначала частный случай, когда Qj=Q для всех i. В этом случае задача сводится к классической «задаче о камнях». |