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


[Старт] [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]


90

Сделаем замечание о структуре коэффициентов, формирующих ограничения. В столбце, соответствующем переменной хц, всегда в строке / стоит +1, а в строке

j--1. Остальные коэффициенты равны нулю. Такая структура коэффициентов

типична для сетевых моделей.

Для переменных, представляющих потоки через дуги, имеющие ненулевые нижние границы пропускных способностей, выполняем замену

хи = х1* + 50>

ХЫ = *» + 70,

х46 = xv> + 100.

В результате получаем следующую задачу линейного программирования.

Минимизировать

Узел 1

= 50

Узел 2

= 200

УзелЗ

= -20

Узел 4

= -130

Узел 5

= -80

Узел 6

= -20

Верхние границы

□0

Соответствующая сеть после исключения нижних границ пропускных способностей дуг показана на рис. 6.39. Отметим, что данную сеть можно получить непосредственно из сети, представленной на рис. 6.37, с помощью преобразований, показанных на рис. 6.38, причем без необходимости записи в виде задачи линейного программирования.

[-80]

Рис. 6.39. Сеть из примера 6.5.2 после исключения нижних границ пропускных способностей



Пример 6.5.3. Распределение рабочих

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

Месяц

Январь

Февраль

Март

Апрель

К-во рабочих

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

Время трудоустройства (месяцы)

Стоимость найма одного рабочего (долл.)

Обозначим через х количество рабочих, нанятых на начало (-го месяца и освобожденных на начало у-го. Например, х12 - это количество рабочих, нанятых в январе только на один месяц.

Чтобы сформулировать задачу линейного программирования, нужно добавить еще пятый месяц (май). Тогда, например, переменная х{5 будет обозначать количество рабочих, нанятых в апреле на один месяц. Естественно, на май нет заказа на рабочих.

Ограничения строятся так, чтобы спрос на рабочих в месяц к можно было бы удовлетворить за счет всех рабочих хц, где / < к < j. Обозначив через s, (s, > 0) количество рабочих, "лишних" в месяце /, получим следующую задачу линейного программирования.

х14,

х45 s1

S2 S3 S4

Янв.

Фев.

-1 120

Март

-1 80

Апр.

-1 170

В данной задаче ЛП нет той специальной структуры коэффициентов ограничений, что была в модели из примера 6.5.2. Тем не менее эта задача имеет свою специфику, которая позволит преобразовать ее в сетевую модель. Выполним следующие действия.

1. Из п-го уравнения (ограничения) задачи создадим новое (п + 1)-е уравнение, умножив п-е уравнение на -1.

2. Оставляем первое уравнение без изменений.

3. Для /= 2, 3, п последовательно заменяем г-е уравнение разностью ;-го и (/- 1)-го уравнений.



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

х45 s1

Янв.

Фев.

Март

Апр.

-170

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

Рис. 6.40. Сеть для примера 6.5.3

УПРАЖНЕНИЯ 6.5.2

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

(0, да) (10, оо)

[-40]

Рис. 6.41. Сеть для задачи из упражнения 1

[Старт] [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]