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


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


61

кроме этого метод предполагает наличие некоторого правила ветвления, суть которого состоит в следующем. Пусть имеется некоторое разбиение множества X на систему подмножеств. Правило предполагает выбор некоторым способом одного из подмножеств и разбиение (ветвление) его на непересекающиеся подмножества. Как правило, в качестве подмножества для ветвления выбирается подмножество с максимальным значением оценки. Иногда говорят не о ветвлении допустимого множества, а о ветвлении задачи (разбиение на подзадачи).

Далее для вновь появившихся в результате ветвления подмножеств X строятся их оценки сверху. При этом могут возникнуть следующие ситуации:

1)подмножество X оказалось пустым;

2)полученная оценка R{X) меньше или равна наибольшему из уже вычисленных к этому моменту значений функции F(x), которое называется текущим значением рекорда. Отсюда следует, что оптимальное

решение исходной задачи (6.10) находится вне множества X ;

3)точка из расширенного множества, в которой достигается оценка

R{ X ), принадлежит самому множеству X .

Во всех трех случаях подмножество X исключается из рассмотрения. В случае 3, кроме того, вычисленное значение max F(x) на множестве х е X сравнивается с текущим значением рекорда. В качестве нового значения текущего рекорда выбирается максимальное из этих чисел.

Важным достоинством метода ветвей и границ является то обстоятельство, что в процессе решения на каждом шаге мы располагаем двусторонними оценками для оптимального значения задачи (6.10). А именно, это значение ограничивается снизу значением текущего рекорда и ограничивается сверху максимумом из всех имеющихся оценок R{X ). Эти оценки в процессе решения уточняются, поэтому если точность оценок на каком либо шаге удовлетворяет, процесс вычисления по данному алгоритму может быть прекращен.

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

Рассматриваемый метод решения задачи целочисленного программирования также опирается на решение задач с ослабленными ограничениями. Однако в отличие от методов отсечений метод ветвей и границ



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

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

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

<х. <

или >

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

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

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

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



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

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

Пример. Предприятие может выпускать металлические шкафы и металлические стеллажи. Для производства шкафа требуется 1 человек/час рабочего времени и 9 м. листового металла, а для производства стеллажа- 1 человек/час рабочего времени и 5 м. металла. Имеется 6 человек/часов рабочего времени и 45 м листового металла. Один шкаф приносит прибыль 8 тыс. руб., а один стеллаж- 5 тыс. Необходимо определить, сколько изготавливать шкафов и сколько стеллажей, чтобы прибыль предприятия была бы максимальной.

Решение. В качестве переменных задачи рассмотрим - количество произведенных шкафов, 2 - количество произведенных стеллажей.

Поскольку данные переменные должны быть неотрицательным целыми по смыслу задачи, мы имеем следующую задачу ЦЛП:

z = Sxj + 52 шах,(6.11)

+ 2 < 6,

9xi + 5x2 < 45 ,

Xi,X2 >0, х,,Х2 gZ.

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