Задачи дискретного программирования и метод ветвей и границ для их решения

Методические указания к курсовой работе по дисциплине «Методы оптимизации и принятия решений» для магистров 09.04.01 и 09.04.04

Трудоемкость (СРС): 12 часов.

Типовые варианты:

-Решить задачу дискретного программирования методом ветвей и границ

-Решить задачу целочисленного программирования методом ветвей и границ

-Решить задачу целочисленного линейного программирования методом ветвей и границ

Общие сведения

ЗАДАЧИ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ И МЕТОД ВЕТВЕЙ И ГРАНИЦ ДЛЯ ИХ РЕШЕНИЯ

Задачи дискретного программирования (ЗДП) - это задачи математического программирования при условии дискретности пространства управляемых параметров, т.е. X ϵ D, где D - конечное или счетное множество точек.

ЗДП в формализованном виде записывается следующим образом:

extr f(X)

XϵXD

XD = { X | φ (X) = 0, ψ (X) ≤ 0, X ϵ D }.

Условие дискретности чаще всего задается для каждой компоненты:

__

X_i ϵ D_i (i = 1,n).

Если лишь часть управляемых параметров X дискретна, то это задача частично - дискретного программирования. Если для параметра x вводится двустороннее прямое ограничение вида

___

x_imin ≤ x_i ≤ x_imax, тогда D_i (i = 1,n) - это конечное множество, и ЗДП становится

комбинаторной.

Наиболее распространенным методом решения ЗДП является метод ветвей и границ. Он заключается в разбиении множества XD допустимых значений X на несколько подмножеств и выяснении перспективности каждого из них.

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

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

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

min f(X).

X ϵ XD

1. Вычисление оценок границ целевой функции.

___

Предполагается, что для множества XD и его любого подмножества XD_v ϵ XD (v = 1,V) можно найти

оценку нижней границы целевой функции f(X), т.е. такое число ʓ (XD_v), что для всех X ϵ XD_v выполняется равенство ʓ (XD_v) ≤ f(X). На рис.1 показан пример функции f(x) и ее нижней границы ʓ (XD_v).

Оценку нижней границы желательно формировать как можно ближе к значению минимума функции на рассматриваемом множестве, чтобы снизить трудоемкость метода ветвей и границ.

Помимо оценки нижней границы функции, если возможно, формируется верхняя оценка оптимального значения целевой функции для всего множества XD. Если достаточно просто получить какое - либо допустимое решение X_д ϵ XD, то можно принять β = f(X_д).

 

2. Правила ветвления (разбиения) множеств.

Метод ветвей и границ связан с разбиением каждого перспективного множества на подмножества, в результате чего получается дерево подмножеств. Поэтому для каждого конкретного класса задач должны быть сформулированы свои правила разбиения. Часто применяют следующее правило: каждое множество разбивается на два подмножества, и дальнейшему разбиению подлежит то подмножество, для которого оценка ʓ нижней границы функции будет меньше. На рис. 2 приведен пример дерева подмножеств.

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

V

При получении полного разбиения множества XD на подмножества XD_v: XD = U XD_v, -

v=1

может быть введена нижняя граница ʓ (XD) целевой функции для всей ЗДП: ʓ (XD) = min ʓ (XD_v).

___

v=1,V

 

В полное разбиение множества XD входят подмножества его дерева подмножеств, соответствующие его листьям.

Для дерева подмножеств, изображенного на рис.2, полное разбиение имеет вид:

XD = XD₁ U XD₂₂ U XD₂₁₁ U XD₂₁₂.

3. Признак оптимальности решения.

Предполагается, что для конкретных типов задач существуют способы определения оптимального решения X_v задачи нахождения минимума функции на каждом подмножестве XD_v: min f(X).

Xϵ XD_v

V

Если при полном разбиении множества XD = U XD_v для некоторого подмножества XD_s

v=1

найдено оптимальное решение X_s, удовлетворяющее следующим двум условиям:

1) f(X_s) = ʓ (XD_s);

2) ʓ (XD_s) = min ʓ (XD_v),

___

v=1,V

то X_s является оптимальным решением всей ЗДП min f(X).

X ϵXD

Если для некоторого подмножества XD_s выполняется первое условие, но не выполняется второе, то можно

или сформировать верхнюю оценку оптимального значения целевой функции как β= ʓ (XD_s), если она ранее не была получена,

или скорректировать прежнее значение верхней оценки, если

ʓ (XD_s) < β, принимая новое значение β = ʓ (XD_s).

 

4. Приближенное решение задачи.

V

Если XD =U XD и для некоторого XD_s получено оптимальное решение X, причем выполняется

v=1

только первое условие, то можно ограничиться приближенным решением X_s ЗДП. При этом имеем следующую точность полученного решения δ = f(X_s) - min ʓ (XD_v).

___

v=1,V

Поделиться:

Воспользуйтесь поиском по сайту: