Автоматизация технологического проектирования. Смирнов О.Л. - 29 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

29
f
min(c, b)
(x) ≤ f
min(a, c)
(x). (50)
Чем более точно граница отслеживает минимум функции в ее облас-
ти определения, тем вероятнее соотношение (50). На основании этой
информации делается вывод о расположении глобального минимума в
области (c, b). Cледовательно, для дальнейшего поиска расположения
этого минимума в области (c, b) выполняется ее разделение на равные и
непересекающиеся области (c, d) и (d, b) и определение в них нижних
границ G(c, d) и G(d, b). На основании сравнения уже трех границ
G(a, c), G(c, d) и G(d, b) в еще нерасчлененных областях делается вы-
вод, что глобальный минимум, вероятно, расположен в области (c, d).
Далее производится ее разделение и вычисление границ в полученных
подобластях и т. д. Тонкость заключается в том, что при выборе подоблас-
ти с вероятным местонахождением глобального минимума функции нуж-
но сравнивать нижние границы для всех еще нерасчлененных подобла-
стей. Все это повторяется до тех пор, пока не определится подобласть с
двумя свойствами: она не может быть расчленена на подобласти (имеет
только одно значение аргумента х') и значение границы в ней G(x'),
равное f(x'), будет меньше или равно значению границ G(A) во всех еще
нерасчлененных подобластях определения А функции f(x). Поскольку
локальные минимумы функций f
min(A)
(x) ≥ G(A), то, по определению ми-
нимума, значение f(x') является глобальным минимумом f
min
(x), а значе-
ние x' является оптимальным значением x
opt
.
15. Целочисленное решение задач
линейного программирования методом ветвей и границ
В данном случае границей максимального значения целевой фун-
кции с целочисленным решением служит максимальное значение этой
функции с нецелочисленным решением, получаемое симплекс-ме-
тодом. Далее из всего множества допустимых решений исключается
подмножество решений с дробной частью оптимального нецелочис-
ленного значения одной из переменных. При этом происходит деле-
ние всего множества решений на два непересекающихся, в которых
вычисляется граница повторением нецелочисленного решения сим-
плекс-методом. Далее сравниваются границы и продолжается поиск
целочисленного решения повторением деления выбранного подмно-
жества решений и вычислением в образующихся подмножествах вер-

Страницы