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


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


41

Комплексные задачи

территории США.* Когда грузы поступают на терминал, они сортируются: часть груза, предназначенная местному потребителю, ему же и поступает, остальной груз отправляется к следующему терминалу. Терминальные доки обслуживают как постоянные, так и временные работники, набираемые по найму. Постоянным работникам гарантирована 40-часовая рабочая неделя. Они работают в одну из трех стандартных смен непрерывно в течение пяти дней, но их рабочая неделя может начаться в любой день недели. Временные работники нанимаются на любое количество рабочих часов при пиковых поступлениях грузов, превышающих возможности их обработки постоянными работниками.

Грузы могут поступать на терминалы в любое время, причем неравномерно в течение суток. Изучение статистических данных показывает, что распределение поступления грузов примерно одинаково каждую неделю, и пик поступления грузов обычно приходится на конец недели (пятница-воскресение). Политика компании требует, чтобы грузы задерживались на терминалах не более, чем на 16 часов.

Разработайте модель, с помощью которой можно было бы назначать в рабочие смены постоянных работников и нанимать временных.

Эта задача основана на исследованиях, проводимых автором для национальной транспортной компании.



ГЛАВА 4

ДВОЙСТВЕННОСТЬ И АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ

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

Мы уже встречались с анализом чувствительности (на элементарном уровне) в разделе 2.3. В этой главе мы подробнее рассмотрим методы анализа чувствительности, основанные на теории двойственности.

4.1. ОПРЕДЕЛЕНИЕ ДВОЙСТВЕННОЙ ЗАДАЧИ

Исходную задачу линейного программирования будем называть прямой. Двойственная задача - это задача, формулируемая с помощью определенных правил непосредственно из прямой задачи. В этом разделе рассмотрены правила построения двойственных задач.

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

Максимизировать или минимизировать целевую функцию г = при ограничениях



В состав п переменных х} входят также дополнительные переменные. Стандартная форма задачи ЛП предполагает выполнение следующих условий.

1. Все ограничения записаны в виде равенств с неотрицательной правой частью.

2. Все переменные неотрицательны.

3. Оптимизация определяется как максимизация или минимизация целевой функции.

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

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

1. Каждому из т ограничений прямой задачи соответствует переменная двойственной задачи.

2. Каждой из п переменных прямой задачи соответствует ограничение двойственной задачи.

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

4. Коэффициенты целевой функции двойственной задачи равны правым частям ограничений прямой задачи.

Графически эти правила представлены в табл. 4.1.

Таблица 4.1.

Формирование двойственной задачи из прямой

Переменные

Переменные прямой задачи

двойственной

задачи

... в,;

a-in

щшшшш

шШШШШШШШШШФШ

j-e ограничение двойственной задачи

Коэффициенты целевой функции двойственной задачи

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

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