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


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


137

Ь) Максимизировать г = Зх, 4- хг + Зх3 при ограничениях

-хл +2х2 + х3<4, 4х2 - Зх3 < 2, х1-3х2 + 2х3<3, xv х2, х3 > 0 и целые.

9.2.4. Вычислительный взгляд на задачи ЦЛП

На сегодняшний день, несмотря на 40 лет интенсивных исследований, не существует вычислительного алгоритма, приемлемого для решения всех разнообразных задач целочисленного программирования. Из представленных в этой главе двух алгоритмов метод ветвей и границ считается более эффективным - практически все коммерческие программы, предназначенные для решения задач ЦЛП, используют этот метод. Метод отсекающих плоскостей более сложен и менее надежен, кроме того его реализация порождает серьезные проблемы, связанные с ошибками машинного округления. Было много попыток сделать этот метод эффективным для компьютерных вычислений, но они не увенчались большими успехами. В большинстве случаев метод отсекающих плоскостей используется как дополнительный метод при решении подзадач, генерируемых в процессе применения метода ветвей и границ.

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

1. Аппроксимировать целочисленные переменные непрерывными, где это возможно.

2. Сузить, насколько возможно, интервалы допустимых значений целочисленных переменных.

3. Избегать в модели ЦЛП использования нелинейных функций.

Уровень развития методов решения целочисленных задач не удовлетворяет требованиям, которые диктуются их практической важностью. Маловероятно, что в целочисленном программировании будет получен новый теоретический прорыв. Представляется более вероятным, что новые технологические достижения в области компьютерной техники могут предложить новые пути повышения эффективности алгоритмов решения задач ЦЛП.

9.3. ЗАДАЧА КОММИВОЯЖЕРА

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



каждый пункт только один раз, называется циклом; цикл, проходящий через все пункты, называется полным, в противном случае - частичным или подциклом.) В задаче коммивояжера с п городами можно определить такие переменные:

1,если город j достижим из города i, У [0, в противном случае.

Имея значения dtj, расстояния от города i до города j (считается, что йц = °° при i=j), задачу коммивояжера можно формализовать следующим образом.

Минимизировать г = ХХЛ

при ограничениях

£х„= 1,1=1,2, п<

7=1 и

хц = 0 или 1,

решение должно быть полным циклом.

Ограничения задачи, кроме последнего, определяют обычную задачу о назначениях (см. раздел 5.4). В общем случае нет гарантии, что оптимальное решение задачи коммивояжера может быть получено путем решения соответствующей задачи о назначениях, т.е., что оптимальное решение задачи о назначениях образует полный цикл. Более вероятно, что оно будет содержать частичные циклы, соединяющие вместе некоторые подмножества узлов сети. На рис. 9.13 показана задача коммивояжера, состоящая из 5-ти городов. Ребра, соединяющие узлы (города) сети, соответствуют дорогам с двухсторонним движением. На этом рисунке показано решение задачи коммивояжера и частичные циклы, соответствующие решению задачи о назначениях. Если задача о назначениях формирует полный цикл, то это будет оптимальным решением задачи коммивояжера. Если оптимальное решение задачи о назначениях состоит из нескольких частичных циклов, то в эту задачу добавляются специальные ограничения, удаляющие решения с частичными циклами. Такие ограничения будут показаны далее в этом разделе.

Задача S-ти городов Решение задачи коммивояжера Решение задачи о назначениях (х12 - Хи - xw - х43 - х31 - 1) (хи - хп - х13 - хн - х41 - 1)

Рис. 9.13. Пример задачи коммивояжера для 5-ти городов



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

Пример 9.3.1

Дневной график работы предприятия, производящего краски, включает изготовление партий белой (Б), желтой (Ж), красной (К) и черной (Ч) красок. Так как предприятие использует одно и то же оборудование для изготовления всех четырех типов краски, необходима его надлежащая чистка между изготовлением различных партий краски. Приведенная ниже таблица содержит время чистки оборудования в минутах, если за изготовлением краски, указанной в строке, следует изготовление краски, указанной в столбце. Например, если за белой краской следует желтая, то время чистки равно 10 минут. Поскольку за определенным цветом краски не может следовать такой же цвет, то соответствующее время чистки полагается равным бесконечности. Необходимо определить оптимальную последовательность дневного производства четырех типов краски, которая минимизирует суммарное время чистки оборудования.

Время чистки в мин., если следующий цвет

Текущий цвет

белый

желтый

черный

красный

Белый

Желтый

Черный

Красный

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

Эту задачу можно решить путем полного перебора шести [(4-1)! = 3! = 6] возможных контуров сети. Приведенная ниже таблица показывает, что последовательность узлов Б-»Ж->К->Ч->Б определяет оптимальный контур.

Производственный цикл (контур) Суммарное время чистки

Б->Ж->Ч->К-»Б 10 + 19 + 25 + 45 = 99

Б-»Ж->К->Ч->Б 10 + 18 + 20 + 50 = 98

Б->Ч->Ж->К->Б 17 + 44 + 18 + 45 = 124

Б->Ч->К-»Ж->Б 17 + 25 + 40 + 20 = 102

Б->К->Ч-»Ж->Б 15 + 20 + 44 + 20 = 99

Б->К->Ж->Ч->Б 15 + 40 + 19 + 50 = 124

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