30 Апр

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




Номер части:
Оглавление
Содержание
Журнал
Выходные данные


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

При построении моделей линейного параметрического программирования для решения прикладных задач оптимизации часто возникает возможность внести изменения в модель для обеспечения более высокой скорости работы используемых методов оптимизации. Однако направление таких изменений зависит от того, какие именно методы оптимизации используются и какие изменения в модели приведут к увеличению быстродействия. Одним из способов  решения задач линейного параметрического программирования является методика построения дерева решений [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.
    ВЛИЯНИЕ РАСПОЛОЖЕНИЯ ФИКСИРОВАННЫХ ПАРАМЕТРОВ ЗАДАЧИ ЛИНЕЙНОГО ПАРАМЕТРИЧЕСКОГО ПРОГРАММИРОВАНИЯ НА ВРЕМЯ ПОСТРОЕНИЯ ДЕРЕВА РЕШЕНИЙ
    Целью настоящего исследования является выявление влияния расположения фиксированных параметров задачи линейного параметрического программирования на время построения дерева решений. Для этого проводится измерения времени построения дерева в зависимости от расположения фиксированных параметров, а затем делаются выводы о выявленных зависимостях.
    Written by: Кулябичев Юрий Павлович, Кокуев Александр Александрович
    Published by: БАСАРАНОВИЧ ЕКАТЕРИНА
    Date Published: 03/28/2017
    Edition: ЕВРАЗИЙСКИЙ СОЮЗ УЧЕНЫХ_30.04.2015_04(13)
    Available in: Ebook