При построении моделей линейного параметрического программирования для решения прикладных задач оптимизации часто возникает возможность внести изменения в модель для обеспечения более высокой скорости работы используемых методов оптимизации. Однако направление таких изменений зависит от того, какие именно методы оптимизации используются и какие изменения в модели приведут к увеличению быстродействия. Одним из способов решения задач линейного параметрического программирования является методика построения дерева решений [1, c. 140; 2, c. 139]. Одним из этапов в рамках этой методики является построение дерева решений для задачи линейного параметрического программирования. Поскольку алгоритм построения дерева решений является переборным алгоритмом, экспоненциально зависящим от размера задачи [3, с. 366;4, c.70], важно выполнять построение модели таким образом, чтобы время построения было минимальным.А для этого необходимо изучить, как расположение фиксированных параметров задачи влияет на время построения дерева решений.
Одной из особенностейпредставленного в статье [1] алгоритма построения дерева решений является зависимость времени построения дерева решений от расположения фиксированных параметров задачи[5, c. 144]. Можно выделить три основных случая расположения фиксированного параметра:
- фиксированный параметр расположен в матрице ограничений A;
- фиксированный параметр расположен в векторе свободных членов ?;
- фиксированный параметр расположен в критерии оптимизации ?.
Согласно [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 раз, после чего вычислялось среднее и погрешность измерения по методу Стьюдента. Значения производных величин округлены соответственно полученным погрешностям.
- Полученные результаты позволяют сделать следующие выводы:
- Наиболее существенное влияние на время построения дерева оказывают фиксированные параметры в матрице ограничений A;
- На время построения дерева влияет количество фиксированных параметров в матрице ограничений (отличие в экспериментах 1 и 2 в 2,5 раза, а в между 6 и 7 на порядок);
- При этом на время построения дерева существенно влияет и взаимное расположения фиксированных параметров в матрице ограничений (эксперименты 3, 4, 5):
- Расположение фиксированных параметров в матрице ограничений влияет на время построения дерева сильнее, чем количество фиксированных параметров, что подтверждается существенной разницей между временем построения в экспериментах 1, 2, 5 и между 1, 2, 6, 7. В первом случае фиксированные параметры были не связаны между собой, менялось лишь количество заданных параметров, а во втором случае, в экспериментах 6 и 7, между фиксированные переменные находились, как в одном ограничении, так и при одной оптимизируемой переменной;
- Фиксирование параметров в столбце свободных членов b влияет на время построения дерева значительно меньше, чем фиксирование параметров в матрице ограничений, после фиксирования одного свободного члена время снизилось на 15% (эксперимент 8), а после фиксирования второго еще на 10% (эксперимент 9);
- Вывод о более существенном влиянии фиксации параметров в матрице ограничений подтверждается относительно небольшой разницей во времени построения дерева при фиксировании параметра в столбце свободных членов, при уже зафиксированных параметрах в матрице ограничений, как в экспериментах 2 и 10, а также в экспериментах 3 и 12;
- При этом, согласно экспериментам 10 и 11, расположение фиксированного параметра в столбце свободных членов относительно фиксированного параметра в матрице ограничений не сильно влияет на время построения дерева;
- Фиксирование параметра в коэффициентах критерия оптимизации c оказывает существенное влияние на время построения дерева, согласно экспериментам 1, 13 и 14 разница, соответственно, в 2,3 раза и в 9,4 раза, что соответствует влиянию фиксации параметров в матрице ограничений в среднем случае, с точки зрения расположения фиксированных параметров (см. эксперименты 2 и 3, 4, 5);
- При этом взаимное расположение фиксированных параметров в коэффициентах критерия оптимизации и фиксированных параметров в матрице ограничений практически не влияет на время построения дерева, согласно результатам пар экспериментов 15 и 16, 17 и 19, 18 и 20, 21 и 22;
- Взаимное расположение фиксированных параметров в коэффициентах критерия оптимизации и фиксированных параметров в столбце свободных членов также практически не влияет на время построения дерева, согласно результатам пар экспериментов 17 и 18, 19 и 20.
Список литературы:
- Кокуев А.А., Ктитров С.В. Построение дерева решений в задачах линейного программирования // Вестник Национального исследовательского ядерного университета «МИФИ». – 2014. – Т. 3, № 1. – С. 119–124.
- Кокуев А.А., Ктитров С.В. Использование дерева решений в задачах линейного параметрического программирования // НАУЧНАЯ СЕССИЯ НИЯУ МИФИ-2015. Аннотации докладов. – Т. 3. – М. : НИЯУ МИФИ, 2015. – С. 139.
- ТахаХэмди А. Введение в исследование операций. – 7 изд. – М. : Издательский дом «Вильямс», 2007. – 912 с.
- Алгоритмы: построение и анализ / Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн. – 2 изд. – М. : Издательский дом «Вильямс», 2012. – 1296 с.
- Кокуев А.А., Ктитров С.В. Построение дерева решений для задач линейного параметрического программирования // НАУЧНАЯ СЕССИЯ НИЯУ МИФИ-2015. Аннотации докладов. – Т. 3. – М. : НИЯУ МИФИ, 2015. – С. 144.[schema type=»book» name=»ВЛИЯНИЕ РАСПОЛОЖЕНИЯ ФИКСИРОВАННЫХ ПАРАМЕТРОВ ЗАДАЧИ ЛИНЕЙНОГО ПАРАМЕТРИЧЕСКОГО ПРОГРАММИРОВАНИЯ НА ВРЕМЯ ПОСТРОЕНИЯ ДЕРЕВА РЕШЕНИЙ» description=»Целью настоящего исследования является выявление влияния расположения фиксированных параметров задачи линейного параметрического программирования на время построения дерева решений. Для этого проводится измерения времени построения дерева в зависимости от расположения фиксированных параметров, а затем делаются выводы о выявленных зависимостях.» author=»Кулябичев Юрий Павлович, Кокуев Александр Александрович» publisher=»БАСАРАНОВИЧ ЕКАТЕРИНА» pubdate=»2017-03-28″ edition=»ЕВРАЗИЙСКИЙ СОЮЗ УЧЕНЫХ_30.04.2015_04(13)» ebook=»yes» ]