Полная версия

Главная arrow Математика, химия, физика arrow Дискретная оптимизация. Модели, методы, алгоритмы решения прикладных задач

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Двухпараметрические задачи

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

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

В значительной мере эти трудности можно преодолеть, применяя метод динамического программирования с использованием множеств Парето.

Рассмотрим две двухпараметрические задачи и покажем как их можно решить с помощью этого метода.

Эти задачи рассматривались различными авторами [4,29], которые предлагали использовать для их решения классический алгоритм динамического программирования.

Задача о загрузке транспортных средств

Сначала вернёмся к задаче о загрузке транспортных средств и рассмотрим её в следующей постановке. Пусть имеется N различных предметов. Каждый из них обладает весом, объемом и своей стоимостью. Требуется загрузить транспортное средство ограниченной грузоподъемности и вместительности таким образом, чтобы суммарная стоимость погруженных предметов была максимальной. Согласно такой постановке задачи ресурсы (вес и объем) зависимы. Задача сводится к следующему:

Найти

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

Cj - стоимость i-ro предмета,

V,- - объем i-ro предмета,

Wj- вес i-ro предмета,

kj - количество взятых предметов i-ro типа,

V,W - максимально возможная вместительность и грузоподъемность соответственно. Неизвестными являются kt.

В рассматриваемой задаче очередной шаг - это определение количества предметов соответствующего типа в дополнение к уже погруженным в машину, а состояния системы - это соответствующие суммарный вес и объём.

Исходная задача однокритериальная: нужен максимум стоимости погруженных предметов. Но, используя метод погружения, удобнее решать трехкритериальную задачу: первый критерий - стоимость погруженных предметов (нужен максимум), а второй и третий - суммарный использованный ресурс по весу и объему соответственно (нужен минимум).

Состояние i на шаге t можно представить как пару: (Vti. Wti), где Vti - накопленный объем за t шагов,

Wt i- накопленный вес за t шагов.

На первом шаге решается задача о том, какое количество экземпляров предмета П] возьмем. Можно не взять ничего. Можно взять один предмет П1, два и т.д., пока выполняется система ограничений. Каждое полученное состояние запоминаем. Дойдя до максимально возможного числа предметов первого типа, получим множество состояний первого шага. На первом шаге нельзя отбраковать ни пути, ведущие в одно и то же состояние, ни сами состояния. Переходим на второй шаг. Для каждого из состояний, сформированных на первом шаге, рассматривается вопрос: можно ли взять предмет Ш и в каком количестве. Необходимо выполнение системы неравенств. Если оказывается, что несколько состояний из первого шага приводят в одно и то же состояние на 2 шаге, то необходимо оставить тот путь, который приводит в данное состояние с максимальным значением целевой функции (задача на максимум), а все остальные исключить. Оставшееся состояние необходимо запомнить (алгоритм Веллмана).

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

В общем случае на шаге t имеем следующий алгоритм. Рассматриваем все состояния на шаге t-1 и решаем вопрос о взятии предмета nt. Если оказывается, что несколько состояний на t-1-ом шаге приводят в одно и то же состояние на шаге t, то необходимо оставить тот путь, который приводит в данное состояние с максимальным значением целевой функции, а все остальные исключить. Перед тем как запомнить состояние его необходимо проверить. Пусть на t шаге имеется два состояния A(Vti, Wti) и B(Vt2,Wt2). «А» - рассматриваемое состояние, «В» - состояние из множества допустимых состояний на шаге t. Согласно новому принципу отбраковки состояний возможны следующие ситуации (значения целевой функции для текущего состояния обозначены Ft,):

Предполагается, что в каждом случае хотя бы одно из неравенств выполняется строго. Состояния A(Vti, Wti) и B(Vt2, Wt2) входят в множество Парето. Нельзя удалить ни одно состояние.

Состояние A(Vti, Wti) не эффективно по Парето и должно быть отбраковано.

Состояние B(Vt2, Wt2) не эффективно по Парето и должно быть отбраковано.

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

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

Таблица 4.3. Исходные данные для решения задачи

Предметы

Транспортное средство

Предмет

Вес

Объем

Стоимость

Г рузоподъемность

Вместительность

1

п,

31

83

11

600

500

2

п2

45

18

96

3

Пз

86

49

27

4

П4

97

59

72

5

п5

22

9

61

6

Пб

89

22

38

7

П7

54

20

60

8

п8

91

86

87

9

П9

10

49

72

10

Ию

80

85

20

11

Пи

50

96

94

12

П12

35

11

80

13

П|з

96

62

9

14

Пн

12

13

35

15

П|5

37

9

38

16

Пн

67

65

62

17

П|7

52

74

1

18

П,8

96

89

9

19

П19

35

48

59

20

П20

75

70

90

21

П21

84

35

42

22

П22

91

23

66

23

П23

80

91

68

24

П24

48

72

16

25

П25

79

34

38

26

П26

65

33

41

27

П27

43

37

61

28

П28

59

43

34

29

П29

16

17

83

30

Изо

57

22

93

Эффективность нового алгоритма решения двухпараметрических задач распределения ресурса оценивалась в сравнении с классическим алгоритмом Веллмана. Последовательно увеличивалось число предметов, при фиксированной грузоподъемности и вместительности. Исходные данные представлены в таблице 4.3, а результаты в таблице 4.4.

Таблица 4.4. Результаты расчётов

Количество

предметов

(шт.)

Динамическое программирование (метод Беллмана)

Динамическое программирование на множествах Парето (новый алгоритм)

Число состояний

Время счета (сек.)

Число состояний

Время счета (сек.)

3

303

0,02

61

0,05

4

865

0,03

88

0,06

5

1316

0,14

116

0,14

6

5264

0,59

144

0,20

7

15689

3,04

172

0,23

8

18961

6,63

201

0,25

9

21454

8,67

423

0,27

10

23514

11,02

646

0,30

11

28621

14,03

869

0,33

12

32013

17,81

1967

0,53

13

58214

22,64

3065

0,84

14

86213

28,78

6216

3,65

15

107501

36,59

8270

7,91

16

160640

46,52

10040

8,86

17

212562

59,14

11809

9,72

18

283504

75,18

13578

10,28

19

352981

95,58

15347

11,56

20

479248

121,51

17116

12,23

21

547665

154,47

18885

13,12

22

618956

196,37

20654

14,02

23

717536

249,63

22423

14,79

24

774144

317,34

24192

15,52

25

856713

403,43

25961

16,44

26

970552

512,85

27730

17,57

27

1115954

651,97

29499

19,01

28

1250720

828,82

31268

20,05

29

1622112

1053,63

33794

23,53

30

1816000

1339,43

36320

25,30

Вычисления производились на персональном компьютере с процессором Intel Core 2 DUO 2400 МГц и оперативной памятью 2048 МБ.

По данным таблицы 4.4 видно, что новый алгоритм эффективнее классического алгоритма Веллмана. С ростом количества предметов растет и число состояний системы. Рост числа состояний присущ обоим алгоритмам, однако для алгоритма динамического программирования с использованием множеств Парето этот рост более медленный, и уже при числе предметов N= 30 количества состояний отличаются в 50 раз. Соответственно и время решения задачи различное, в зависимости от выбранного алгоритма решения. Так при использовании динамического программирования с использованием множеств Парето для числа предметов N=30 время решения составляет 25,3 секунды, что почти в 54 раза меньше, чем при решении той же задачи классическим алгоритмом.

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

При большем числе предметов были получены следующие результаты (таблица 4.5):

Таблица 4.5. Результаты расчётов. Продолжение

Количество пред- мстов (шт.)

Динамическое программирование (метод Веллмана)

Динамическое программирование на множествах Парето (новый алгоритм)

Число состояний

Время счета (сек.)

Число состояний

Время счета (сек.)

50

7409484

7314,21

145284

138,97

75

10589540

8580,46

203645

156,80

100

13871196

10773,10

256874

189,52

150

21588545

13108,23

392519

226,65

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>