Комбинирование методов поиска оптимальных решений

Метод динамического программирования может применяться не только как самостоятельный, но и как метод, применяющийся совместно с другими.

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

Рассмотрим пример оптимизации эффективности производственной программы (ситуация 3), в котором целевая функция и ограничения задачи имеют вид

где Wj(Xj), t(x), V:(x) — соответственно показатель экономической эффективности, расход ресурсов и продолжительность выполнении производства j-го вида продукции по х-му варианту,у = 1,..., N.

Оценку верхней границы решения на дереве вариантов будем вычислять но формуле

где

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

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

Решение задачи выполним при N = 4, Т = 25, V = 15 и другим данным, приведенным в табл. 11.3.15.

Таблица 11.3.15

Исходные данные задачи

j

1

  • 1
  • 2
  • 5
  • 8
  • 2
  • 4
  • 12
  • 21

2

  • 1
  • 2

3

  • 4
  • 6
  • 9
  • 1
  • 3
  • 6
  • 8
  • 15
  • 20

3

  • 1
  • 2
  • 6
  • 10
  • 3
  • 5
  • 10
  • 18

4

  • 1
  • 2

3

  • 5
  • 7
  • 10
  • 3
  • 4 6
  • 9
  • 16
  • 22

Последовательность построения дерева вариантов показана на рис. 11.3.2. Расчеты верхней границы приводятся в табл. 11.3.16.

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

Поиск решения на дереве вариантов

Рис. 11.3.2. Поиск решения на дереве вариантов

Таблица 11.3.16

Порядок расчетов верхней границы для вершин дерева вариантов

w

yvn-1

n

T

1 n+1

н,ю

0

1

  • 1
  • 2
  • 12
  • 21
  • 20
  • 17
  • 40
  • 34
  • 52
  • 55

21

2

  • 1
  • 2

3

  • 8
  • 15
  • 20
  • 13
  • 11
  • 8
  • 26
  • 19
  • 0
  • 55
  • 55
  • 0

29

3

  • 1
  • 2
  • 10
  • 18
  • 7
  • 3
  • 16
  • 0
  • 55
  • 0

39

4

  • 1
  • 2

3

  • 8
  • 16
  • 22
  • 2
  • 0
  • 3
  • 0
  • 0
  • 0

48

  • 55
  • 0

Таблица 11.3.17

Определение членов функционального уравнения /7,(71,) для 5= 3

t3(^>

  • 9
  • 5
  • 16
  • 7
  • 22
  • 10

10

19

26

32

6

11

13

16

13

27

34

40

10

15

17

20

На первом ярусе дерева вариантов (см. рис. 11.3.2) имеем верхние границы #,( 1) = 52 и #,(2) = 55. Вторая вершина имеет большую границу, поэтому в первую очередь из нее проводим очередное ветвление. По такому же правилу осуществляем и последующие ветвления. На последнем ярусе получаем решение W* = 55 для вектора X* = (2, 1, 1, 2).

Как видим, все верхние границы неветвленных вершин не больше значения W*. Следовательно, полученное решение является оптимальным.

Х. ад

т3

Щ(х2)

t2(x2)

  • 19
  • 11
  • 26
  • 13
  • 27
  • 15
  • 32
  • 16
  • 34
  • 17
  • 40
  • 20

8

27

34

35

40

0

0

4

15

17

19

20

21

24

15

34

41

0

0

0

0

6

17

49

21

22

23

23

20

39

0

0

0

0

0

9

20

22

24

25

26

29

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >