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

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

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


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

Задача об использовании двух видов сырья

Рассмотрим ещё одну двухпараметрическую задачу, которая состоит в следующем [29].

Предприятие может производить изделия, работая на двух видах сырья X и Y. Пусть производится N видов изделий. Для производства одного изделия i- го вида требуется Xi либо yj единиц сырья X и Y соответственно. Одно изделие производится только из одного вида сырья (любого), но различные изделия одного вида могут быть произведены при расходовании обоих видов сырья. Количество изделий, изготовленных за рассматриваемый период (например за месяц), ограничено производственной мощностью ai независимо от используемого сырья. Требуется определить количество и тип изделий, которые предприятие изготовит за месяц, такие, что их суммарная стоимость максимальна [29].

Согласно такой постановке ресурсы (X и Y) независимы в том смысле, что расходование одного из ресурсов не влечет расходование другого. Обратная ситуация была рассмотрена в задача о загрузке транспортного средства. Там, если предмет был загружен, то одновременно расходовались и остаточная грузоподъемность, и остаточная вместительность. В данной же задаче мы можем зафиксировать значение одного ресурса и изменять значение другого до тех пор, пока выполнено ограничение по производственной мощности. Далее увеличиваем значение первого ресурса и снова фиксируем его, при этом изменяем значение второго ресурса и т.д. Для большей наглядности представим исходные данные в табличном виде (таблица 4.6).

Таблица 4.6. Структура входных данных

Предметы

Сырье в наличии

Предмет

Сырье 1

Сырье 2

Цена

Мощность

Сырье 1

Сырье 2

1

П.

XI

У1

С1

ai

X

Y

2

П2

Х2

У2

С2

32

i

П;

Xi

У*

Ci

ai

N

Пи

XN

уы

CN

аы

Формальная постановка задачи сводится к следующему.

Найти при ограничениях

где Cj - цена одного изделия i-ro вида,

Xj - количество сырья X, необходимое для изготовления изделий i-ro вида, у- - количество сырья Y, необходимое для изготовления изделий i-ro вида,

С1- - максимальное количество изделий i-ro вида, которое может быть изготовлено предприятием за месяц,

к* - количество изделий i-ro вида, изготовленные при использовании сырья

X,

kj - количество изделий i-roвида, изготовленные при использовании сырья Y. Неизвестными являются

Задача является двухпараметрической. Её нельзя решать по частям (сначала решить задачу для первого ресурса, а потом для второго), так как количество предметов, изготовленных по первому ресурсу, и количество предметов, изготовленных по второму, связаны неравенством: hx + ку<а.

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

Эта задача может быть решена с помощью классического алгоритма Р. Веллмана [3]. Однако и в этом случае более эффективным оказывается алгоритм динамического программирования с использованием множеств Парето.

Графически состояние представляет собой точку на плоскости в координатах (X,Y).

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

На первом шаге определяем какое количество предметов П1 можно изготовить и из какого сырья. Можно ничего не произвести, тогда целевая функция будет равна нулю. Можно произвести несколько предметов. Предположим, что будем производить изделия только из первого сырья (X), тогда для изготовления одного предмета П| требуется затратить xi сырья X, для двух 2xi и так до ai или до исчерпания всего объёма сырья X. Каждое полученное состояние запоминаем. Теперь будем производить изделия только из сырья Y. Для изготовления одного предмета Hi требуется затратить yi сырья Y, для двух 2уi и так до ai или до исчерпания всего объёма сырья Y. П снова запоминаем каждое полученное состояние. Теперь будем производить изделия из обоих видов сырья. Произведем одно изделие из сырья X, а остальные из сырья Y. Фиксируем значение затрат по первому сырью (xi), а по второму - меняем (у 1, уг, уз, ...) до тех пор, пока не дойдём до ai или до Y. И снова запоминаем каждое полученное состояние. Далее увеличиваем значение затрат по первому сырью (2xi) и повторяем операцию. При исчерпании всех допустимых по ограничениям комбинаций количеств сырья первого и второго вида множество состояний на шаге 1 будет сформировано.

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

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

Аналогично поступаем на каждом следующем шаге. Алгоритм отбраковки непаретовских состояний в данной задаче полностью соответствует алгоритму, рассмотренному при решении задачи о загрузке транспортного средства. Как и в том алгоритме состояние - это пара: (Xti, Yti), где Xti и Yti - потраченные объемы ресурсов X и Y за t шагов соответственно. Отличие состоит в более сложной системе ограничений.

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

Эффективность нового алгоритма решения двухпараметрических задач распределения ресурса оценивалась в сравнении с классическим алгоритмом Веллмана. В расчётах последовательно увеличивалось число предметов при сохранении фиксированных количеств сырья 1 и сырья 2. Исходные данные представлены в таблице 4.7, а результаты расчётов приведены в таблице 4.8.

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

Предметы

Наличие сырья

Пред

мет

Затраты сырья 1

Затраты сырья 2

Цена

Производственая мощность (за месяц)

Сырье 1

Сырье 2

П1

31

83

11

45

261

259

П2

18

96

86

49

ПЗ

27

97

59

72

П4

22

9

61

89

П5

22

38

54

20

П6

60

91

86

87

П7

10

49

72

80

ПВ

85

20

50

96

П9

94

35

11

80

П10

96

62

9

12

П11

13

35

37

9

П12

38

67

65

62

П13

52

74

1

96

П14

89

9

35

48

П15

59

75

70

90

П16

84

35

42

91

П17

23

66

80

91

П18

68

48

72

16

П19

79

34

38

65

П20

33

41

43

37

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

Количество

предметов

(шг.)

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

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

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

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

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

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

2

547

0,01

111

0,13

3

2108

0,19

214

0,23

4

7729

2,16

649

2,07

5

15687

7,05

1084

4,08

6

25411

21,15

1519

4,40

7

45247

55,82

3027

8,02

8

57142

129,69

4535

12,15

9

75144

157,19

6043

14,43

10

98451

212,33

7551

15,38

11

134511

295,37

9684

23,43

12

195477

345,05

11742

27,16

13

261458

498,97

13750

29,64

14

321665

564,25

15258

41,87

15

381225

651,21

16766

43,35

16

456852

705,11

18274

45,72

17

534113

866,62

19782

50,31

18

617412

1088,74

21290

51,84

19

729531

1354,44

22798

54,51

20

850710

1547,21

24306

59,14

Таблица 4.8 иллюстрирует количество состояний и время решения задачи классическим алгоритмом Веллмана и новым алгоритмом.

По данным таблицы 4.8 видно, что новый алгоритм при решении задачи об использовании двух видов сырья эффективнее классического алгоритма Веллмана. С ростом количества предметов растет и число состояний системы. Как и в первой задаче наблюдается увеличение числа состояний при увеличении количества шагов, однако, при использовании нового алгоритма этот рост более медленный, чем при использовании классического метода, и уже на 20 шаге количества состояний системы отличаются в 35 раз. Соответственно и время решения задачи различное, в зависимости от выбранного алгоритма решения. Так при использовании динамического программирования с использованием множеств Парето для числа предметов N=20 время решения составляет 59,14 секунды, что почти в 26 раз меньше, чем при решении той же задачи классическим алгоритмом.

С увеличением количества состояний (числа шагов) количество отбракованных точек резко увеличивается.

Так, при большем числе предметов были получены следующие результаты:

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

Количество

предметов

(шт.)

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

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

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

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

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

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

30

2520180

2647,26

70005

108,34

50

3095198

3822,21

83654

147,63

75

3626036

4758,64

95422

186,71

100

4366722

6354,73

122519

226,65

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

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

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