Номер части:
Журнал

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



Науки и перечень статей вошедших в журнал:


DOI:
Дата публикации статьи в журнале:
Название журнала: Евразийский Союз Ученых, Выпуск: , Том: , Страницы в выпуске: -
Автор:
, ,
Автор:
, ,
Автор:
, ,
Анотация:
Ключевые слова:                     
Данные для цитирования: . ВЛИЯНИЕ РАСПОЛОЖЕНИЯ ФИКСИРОВАННЫХ ПАРАМЕТРОВ ЗАДАЧИ ЛИНЕЙНОГО ПАРАМЕТРИЧЕСКОГО ПРОГРАММИРОВАНИЯ НА ВРЕМЯ ПОСТРОЕНИЯ ДЕРЕВА РЕШЕНИЙ // Евразийский Союз Ученых. Технические науки. ; ():-.





При построении моделей линейного параметрического программирования для решения прикладных задач оптимизации часто возникает возможность внести изменения в модель для обеспечения более высокой скорости работы используемых методов оптимизации. Однако направление таких изменений зависит от того, какие именно методы оптимизации используются и какие изменения в модели приведут к увеличению быстродействия. Одним из способов  решения задач линейного параметрического программирования является методика построения дерева решений [1, c. 140; 2, c. 139]. Одним из этапов в рамках этой методики является построение дерева решений для задачи линейного параметрического программирования. Поскольку алгоритм построения дерева решений является переборным алгоритмом, экспоненциально зависящим от размера задачи [3, с. 366;4, c.70], важно выполнять построение модели таким образом, чтобы время построения было минимальным.А для этого необходимо изучить, как расположение фиксированных параметров задачи влияет на время построения дерева решений.

Одной из особенностейпредставленного в статье [1] алгоритма построения дерева решений является зависимость времени построения дерева решений от расположения фиксированных параметров задачи[5, c. 144]. Можно выделить три основных случая расположения фиксированного параметра:

  1. фиксированный параметр расположен в матрице ограничений A;
  2. фиксированный параметр расположен в векторе свободных членов ?;
  3. фиксированный параметр расположен в критерии оптимизации ?.

Согласно [1], класс задач линейного параметрического программирования ?(?, ?, ?) состоит из задач линейного параметрического программирования, у которых n оптимизируемых переменных, mограничений типа «равенство» (другие ограничения можно привести к этому типу при помощи введения дополнительных оптимизируемых переменных), а также множество фиксированных параметров ?. В случае, если ?пустое, то класс обозначается: ?(?, ?).

Визуальный анализ дерева решения для задачи ?(2, 4) показывает, что параметры вA и ?влияют на глубину дерева, в то время, как параметры в ?влияют, в основном, на количество дочерних элементов у каждого из узлов дерева.

Для более подробного исследования влияния расположения фиксированных параметров задачи на время расчета, была проведена серия экспериментов. В качестве основы эксперимента использовалась задача ?(2, 4). В ходе экспериментов изменялось количество фиксированных параметров и их расположение в задаче, для каждого варианта задачи измерялось время построения дерева. А по итогам было посчитано время построения дерева относительно времени построения в задаче ?(2, 4).

Задачей эксперимента было исследования следующих вопросов:

  • влияние расположения фиксированного параметра вA, ? или ? на время построения дерева;
  • влияние количества фиксированных параметров различных типов на время построения дерева;
  • влияние взаимного расположения параметров одного или нескольких типов на время построения дерева.

Результаты эксперимента приведены в таблице 1.

Таблица 1: Результаты исследования влияния расположения и количества 
фиксированных параметров задачи на время построения дерева

Решаемая задача Время построения дерева, c Время построения относительно ?(2, 4)
1 ?(2,4) (202 ± 8) ⋅ 10 1,000
2 ?(2, 4, {?11}) (72 ± 3) ⋅ 10 0,36
3 ?(2, 4, {?11, ?12}) 159 ± 5 0,079
4 ?(2, 4, {?11, ?21}) 220 ± 7 0,109
5 ?(2, 4, {?11, ?22}) 270 ± 8 0,134
6 ?(2, 4, {?11, ?12, ?21}) 54 ± 2 0,027
7 ?(2, 4, {?11, ?12, ?21, ?22}) (580 ± 16) ⋅ 10−2 0,00288
8 ?(2, 4, {?1}) (172 ± 4) ⋅ 10 0,85
9 ?(2, 4, {?1, ?2}) (152 ± 6) ⋅ 10 0,75
10 ?(2, 4, {?11, ?1}) (60 ± 3) ⋅ 10 0,30
11 ?(2, 4, {?21, ?1}) 634 ± 10 0,315
12 ?(2, 4, {?11, ?12, ?1}) 124 ± 4 0,062
13 ?(2, 4, {?1}) (86 ± 4) ⋅ 10 0,43
14 ?(2, 4, {?1, ?2}) 214 ± 6 0,106
15 ?(2, 4, {?11, ?1}) 276 ± 14 0,137
16 ?(2, 4, {?11, ?2}) 282 ± 10 0,140
17 ?(2, 4, {?11, ?1, ?1}) 205 ± 10 0,102
18 ?(2, 4, {?11, ?2, ?1}) 228 ± 13 0,114
19 ?(2, 4, {?11, ?1, ?2}) 222 ± 11 0,111
20 ?(2, 4, {?11, ?2, ?2}) 234 ± 9 0,116
21 ?(2, 4, {?11, ?21, ?1}) 74 ± 3 0,037
22 ?(2, 4, {?11, ?12, ?1}) 60 ± 2 0,030

В первой колонке таблицы 1 указан номер эксперимента. Во второй колонке указывается тип решаемой задачи, все задачи являются модификациями ?(2, 4), различаясь только количеством и составом зафиксированных параметров. В третьей колонке указано среднее время построения дерева. В четвертой, посчитано отношение времени построения дерева к времени построения дерева в задаче ?(2, 4).

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

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

  • Полученные результаты позволяют сделать следующие выводы:
  1. Наиболее существенное влияние на время построения дерева оказывают фиксированные параметры в матрице ограничений A;
  2. На время построения дерева влияет количество фиксированных параметров в матрице ограничений (отличие в экспериментах 1 и 2 в 2,5 раза, а в между 6 и 7 на порядок);
  3. При этом на время построения дерева существенно влияет и взаимное расположения фиксированных параметров в матрице ограничений (эксперименты 3, 4, 5):
  4. Расположение фиксированных параметров в матрице ограничений влияет на время построения дерева сильнее, чем количество фиксированных параметров, что подтверждается существенной разницей между временем построения в экспериментах 1, 2, 5 и между 1, 2, 6, 7. В первом случае фиксированные параметры были не связаны между собой, менялось лишь количество заданных параметров, а во втором случае, в экспериментах 6 и 7, между фиксированные переменные находились, как в одном ограничении, так и при одной оптимизируемой переменной;
  5. Фиксирование параметров в столбце свободных членов b влияет на время построения дерева значительно меньше, чем фиксирование параметров в матрице ограничений, после фиксирования одного свободного члена время снизилось на 15% (эксперимент 8), а после фиксирования второго еще на 10% (эксперимент 9);
  6. Вывод о более существенном влиянии фиксации параметров в матрице ограничений подтверждается относительно небольшой разницей во времени построения дерева при фиксировании параметра в столбце свободных членов, при уже зафиксированных параметрах в матрице ограничений, как в экспериментах 2 и 10, а также в экспериментах 3 и 12;
  7. При этом, согласно экспериментам 10 и 11, расположение фиксированного параметра в столбце свободных членов относительно фиксированного параметра в матрице ограничений не сильно влияет на время построения дерева;
  8. Фиксирование параметра в коэффициентах критерия оптимизации c оказывает существенное влияние на время построения дерева, согласно экспериментам 1, 13 и 14 разница, соответственно, в 2,3 раза и в 9,4 раза, что соответствует влиянию фиксации параметров в матрице ограничений в среднем случае, с точки зрения расположения фиксированных параметров (см. эксперименты 2 и 3, 4, 5);
  9. При этом взаимное расположение фиксированных параметров в коэффициентах критерия оптимизации и фиксированных параметров в матрице ограничений практически не влияет на время построения дерева, согласно результатам пар экспериментов 15 и 16, 17 и 19, 18 и 20, 21 и 22;
  10. Взаимное расположение фиксированных параметров в коэффициентах критерия оптимизации и фиксированных параметров в столбце свободных членов также практически не влияет на время построения дерева, согласно результатам пар экспериментов 17 и 18, 19 и 20.

Список литературы:

  1. Кокуев А.А., Ктитров С.В. Построение дерева решений в задачах линейного программирования // Вестник Национального исследовательского ядерного университета «МИФИ». – 2014. – Т. 3, № 1. – С. 119–124.
  2. Кокуев А.А., Ктитров С.В. Использование дерева решений в задачах линейного параметрического программирования // НАУЧНАЯ СЕССИЯ НИЯУ МИФИ-2015. Аннотации докладов. – Т. 3. – М. : НИЯУ МИФИ, 2015. – С. 139.
  3. ТахаХэмди А. Введение в исследование операций. – 7 изд. – М. : Издательский дом «Вильямс», 2007. – 912 с.
  4. Алгоритмы: построение и анализ / Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн. – 2 изд. – М. : Издательский дом «Вильямс», 2012. – 1296 с.
  5. Кокуев А.А., Ктитров С.В. Построение дерева решений для задач линейного параметрического программирования // НАУЧНАЯ СЕССИЯ НИЯУ МИФИ-2015. Аннотации докладов. – Т. 3. – М. : НИЯУ МИФИ, 2015. – С. 144.[schema type=»book» name=»ВЛИЯНИЕ РАСПОЛОЖЕНИЯ ФИКСИРОВАННЫХ ПАРАМЕТРОВ ЗАДАЧИ ЛИНЕЙНОГО ПАРАМЕТРИЧЕСКОГО ПРОГРАММИРОВАНИЯ НА ВРЕМЯ ПОСТРОЕНИЯ ДЕРЕВА РЕШЕНИЙ» description=»Целью настоящего исследования является выявление влияния расположения фиксированных параметров задачи линейного параметрического программирования на время построения дерева решений. Для этого проводится измерения времени построения дерева в зависимости от расположения фиксированных параметров, а затем делаются выводы о выявленных зависимостях.» author=»Кулябичев Юрий Павлович, Кокуев Александр Александрович» publisher=»БАСАРАНОВИЧ ЕКАТЕРИНА» pubdate=»2017-03-28″ edition=»ЕВРАЗИЙСКИЙ СОЮЗ УЧЕНЫХ_30.04.2015_04(13)» ebook=»yes» ]
Список литературы:


Записи созданы 6778

Похожие записи

Начните вводить, то что вы ищите выше и нажмите кнопку Enter для поиска. Нажмите кнопку ESC для отмены.

Вернуться наверх