назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [ 87 ] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


87

непосредственно поставлять зерно определенным фермам. Пропускная способность маршрутов от зернохранилищ до птицеводческих ферм ограничена количеством используемых грузовиков и числом выполняемых ежедневно рейсов. В следующей таблице показаны ежедневные предложения зернохранилищ и ежедневный спрос птицеводческих ферм (в тысячах фунтов), в ячейках таблицы указаны пропускные способности соответствующих маршрутов.

Зернохранилища

Фермы

20 20 200

a) Найдите схему транспортировки зерна, обеспечивающую максимальный спрос птицеводческих ферм.

b) Существует ли при данных условиях схема транспортировки, обеспечивающая весь спрос птицеводческих ферм?

6. Пусть в задаче из предыдущего упражнения возможна транспортировка зерна между зернохранилищами 1 и 2, а также 2 и 3. Кроме того, возможна транспортировка между фермами 1 и 2, 2 и 3, 3 и 4. Максимальная пропускная способность в обоих направлениях указанных маршрутов составляет 50 тысяч фунтов. Как данные предположения скажутся на обеспечении пока неудовлетворенного спроса птицеводческих ферм?

7. Родители имеют пять детей подросткового возраста, которых ежедневно привлекают к пяти видам домашней работы. Опыт трудового воспитания детей показал, что принудительное (силовое) назначение на работу чревато конфликтами. Поэтому дети сами составили список своих предпочтений, который приведен в следующей таблице.

Ребенок "* Предпочтительные работы

Ральф 3, 4 или 5

Мэй 1

Бен 1 или 2

Ким 1,2 или 5

Кен 2

Теперь родителям осталось найти такое распределение работ, которое в наибольшей степени учитывало бы предпочтения детей. Найдите максимальное количество таких распределений работ.

8. Четыре фабрики получают заказ на производство четырех типов игрушек. В следующей таблице показано, какие игрушки должна производить каждая фабрика.



Фабрика

Тип игрушки

1,2,3

Ежедневные производственные возможности фабрик составляют 250, 180, 300 и 100 штук игрушек соответственно. Ежедневный спрос на игрушки четырех типов составляет 200, 150, 350 и 100 штук. Разработайте производственный план, максимально удовлетворяющий спрос на игрушки.

9. Студенческий совет университета рассматривает представления на шесть студентов, являющихся членами четырех студенческих обществ. Студенческий совет имеет три секции: естественных, гуманитарных и инженерных наук. Совет может принять не более двух студентов в каждую секцию. В следующей таблице показано членство студентов в каждом из четырех студенческих обществ.

Общество

Студент

1,2,3

1,3,5

3,4, 5

1,2, 4,6

Приведем также распределение студентов по возможному принятию их в различные секции совета.

Секция Студент

естественных наук 1,2,4 гуманитарных наук 3,4

инженерных наук 4, 5, 6

Каждый студент может быть принят только в одну секцию. Могут ли быть представлены в совете все четыре студенческих общества?

10. Максимальный и минимальный потоки в сети с нижними границами пропускных способностей. В этом разделе во время поиска максимального потока в сети неявно предполагалось, что нижние границы пропускных способностей всех ребер равны нулю. В некоторых задачах нижние границы пропускных способностей могут быть строго положительными. В таком случае возникает интерес к вычислению как максимального, так и минимального потоков в сети (см. комплексную задачу 6.3 в конце главы). Наличие положительных нижних границ пропускных способностей вызывает определенные затруднения, так как в этом случае сеть вообще может не иметь допустимого потока. Максимальный и минимальный потоки в сети можно найти, выполняя следующие действия.

Шаг 1. Найдите начальное допустимое решение для сети с положительными нижними границами пропускных способностей.



Шаг 2. Используя допустимое решение, найденное на первом этапе, определите максимальный и минимальный потоки в сети.

a) Покажите, что поток через дугу (i, j), величина которого ограничена неравенствами 1Ц < хц < иц, можно представить в виде стока со спросом J. в узле i, источником с предложением lif в узле j и потоком, ограниченным неравенствами 0 < xtj < иц - 1Ц.

b) Покажите, что нахождение допустимого решения в исходной сети эквивалентно нахождению максимального потока в сети, где 1) поток х через каждую дугу (£, заменен потоком x{j с ограничениями 0 < хч < иц - l,j (как показано в предыдущем пункте); 2) все источники "слиты" в один с выходящей из него дугой, имеющей пропускную способность I ; 3) все стоки "слиты" в один с входящей в него дугой, имеющей пропускную способность /,.; 4) конечный узел t соединен с узлом источника s исходной сети дугой с бесконечной пропускной способностью. Допустимое решение существует, если максимальный поток в новой сети равен сумме нижних границ пропускных способностей исходной сети. Примените описанную процедуру к следующей сети и найдите допустимое решение (поток).

С/у. Щ)

(5, 20) (0, 15) (4, 10) (3, 15) (0, 20)

Дуга (/,./)

(1,2) (1,3) (2, 3) (2, 4) (3, 4)

c) Чтобы вычислить минимальный поток в исходной сети, используйте допустимое решение, найденное в предыдущем пункте, совместно с алгоритмом поиска максимального пото-кд. (Совет. Сначала на основе имеющегося допустимого решения найдите остаточную сеть. Далее определите максимальный поток от конечного узла сети к начальному. Теперь, комбинируя допустимый и максимальный потоки, найдите минимальный поток в исходной сети.)

d) Используя алгоритм нахождения максимального потока с допустимым решением, найденным в п. Ь, определите максимальный поток в исходной сети. {Совет. Начните с определения остаточной сети. Далее примените алгоритм поиска сквозных путей к этой сети.)

6.4.3. Формализация задачи поиска максимального потока как задачи ЛП

Обозначим через * . величину потока, проходящего по дуге (£, j), пусть с,. - пропускная способность этой же дуги. Предположим, что необходимо найти максимальный поток между начальным узлом s и конечным узлом t.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [ 87 ] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]