ОЦЕНКА ЭФФЕКТИВНОСТИ ИСПОЛЬЗОВАНИЯ ВЕКТОРНЫХ КОМАНД ПРОЦЕССОРОВ INTEL ПРИ РЕШЕНИИ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ В СРЕДЕ MICROSOFT EXCEL Шарипов М.И.

Уфимский государственный нефтяной технический университет


Номер: 5-1
Год: 2016
Страницы: 131-134
Журнал: Актуальные проблемы гуманитарных и естественных наук

Ключевые слова

Дискретная оптимизация, векторные команды, процессор, эффективность, discrete optimization, vector instruction, processor, efficiency

Просмотр статьи

⛔️ (обновите страницу, если статья не отобразилась)

Аннотация к статье

Рассматривается решение задач псевдобулевой оптимизации в среде Microsoft Excel. Исследуется эффективность использования векторных команд процессоров Intel в процессе решения задачи.

Текст научной статьи

В настоящее время информационные системы [1] класса ERP при всей своей многофункциональности, в том числе в плане подготовки самых разнообразных отчетов по самым разным критериям, все же не содержат инструменты для решения множества разнообразных задач дискретной оптимизации, к которым приводят многие проблемы принятия решений [2]. В то же время большинство современных информационных систем имеют возможности для экспорта отчетов в существующие средства для обработки и анализа данных, такие как Microsoft Excel. Следует особо подчеркнуть, что программное обеспечение MS Excel в отличие от специализированных математических пакетов (MathCAD, Math Lab, Maple), уже имеется в большинстве организациях, и не требуют докупки дополнительного математического программного обеспечения и обучения специалистов навыкам программирования в них задач оптимизации. Более того, MS Excel содержит в себе специальную надстройку «Поиск решения» [3], которая входит в состав программного обеспечения, но по умолчанию отключена. Эта надстройка специально предназначена для поиска решений уравнений, а также задач линейной и нелинейной оптимизации с непрерывными, дискретными и булевыми переменными [4, 5, 6], а также решения систем уравнений для выполнения расчетов для различных прикладных задач, например, анализа показателей надежности сложных технических систем [7]. Рассмотрим теперь простейшую задачу дискретной оптимизации на примере задачи закупки недостающих на складе запчастей при заданных коэффициентах важности (срочности) запчастей, стоимостях запчастей и ограниченной сумме денежных средств, доступной для закупки. Конкретные названия и типы запчастей не имеют никакого значения с точки модели и метода решения задачи, и мы их не будем приводить. Рассмотрим математическую модель задачи закупки 20 различных запчастей. Ограничивающее неравенство задачи оптимизации при заданных стоимостях запчастей (в тыс. рублей) и доступной сумме денежных средств: 10x1 + 15x2 + 12x3 + 40x4 + 20x5 + 40x6 + 30x7 + 20x8 + 36x9 + 22x10 + 12x11 + + 30x12 + 14x13 + 15x14 + 12x15 + 80x16 + 20x17 + 30x18 + 12x19 + 30x20 ≤ 100. Целевая функция задачи (максимизация суммарной важности закупаемых запчастей) при заданных коэффициентах важности запчастей (коэффициенты имеют безразмерную величину и определяются путем ранжирования запчастей по важности): 5x1 + 3x2 + 4x3 + 5x4 + 6x5 + 7x6 + 2x7 + 3x8 + 4x9 + 5x10 + 4x11 + + 10x12 + 6x13 + 7x14 + 2x15 + 4x16 + 11x17 + 3x18 + 4x19 + 5x20 → max. Решение задачи оптимизации при помощи надстройки «Поиск решения» в среде MS Excel дает следующий набор значений переменных: x1 = 1, x2 = 0 x3 = 1, x4 = 0, x5 = 0, x6 = 0, x7 = 0, x8 = 0, x9 = 0, x10 = 0, x11 = 1, x12 = 0, x13 = 1, x14 = 1, x15 = 0, x16 = 0, x17 = 1, x18 = 0, x19 = 1, x20 = 0. Целевая функция задачи при этом достигает значение 41. Левая часть ограничения при этом достигается значение 95, и оно не превышает 100. Время решения исходной задачи при этом занимает ~ 22,14 сек. Рассмотрим теперь время решения исходной задачи с одной целевой функцией и одним ограничением, а также модифицированных задач с дополнительными одним ограничением и двумя ограничениями. Число переменных при этом оставим неизменным равным 20. Для модифицированных задач будем использовать следующие второе и третье ограничение: Второе ограничение: 5x1 + 7x2 + 9x3 + 8x4 + 2x5 + 5x6 + 7x7 + 3x8 + 8x9 + 7x10 + 5x11 + + 6x12 + 8x13 + 9x14 + 6x15 + 5x16 + 2x17 + 3x18 + 4x19 + 5x20 ≤ 40. Третье ограничение: 19x1 + 13x2 + 17x3 + 20x4 + 25x5 + 35x6 + 12x7 + 8x8 + 14x9 + 22x10 + 33x11 + + 25x12 + 26x13 + 12x14 + 44x15 + 25x16 + 75x17 + 12x18 + 22x19 + 13x20 ≤ 140. Время решения задачи с дополнительным вторым ограничением составляет ~ 19,67 сек. Время решения задачи с дополнительными вторым и третьим ограничениями составляет ~ 16,89 сек. Приведенные выше результаты измерений времени являются усредненными значениями многократных измерений времени решения задач с одним, двумя и тремя ограничениями. Ниже на линейчатой диаграмме (рис. 1) наглядно показано сравнение времен решения в MS Excel исходной задачи с одним ограничением, и модифицированных задач с двумя и тремя ограничениями. Таким образом, с одной стороны при неизменном числе переменных рост количества ограничений все же приводит к заметному росту времени решения задач в MS Excel, поскольку, очевидно, дополнительные ограничения приводят к дополнительным операциям умножения и сложения. Рис. 1. Сравнение времени решения задач при различном числе ограничений С другой стороны, известно, что векторные команды (SSE) современных процессоров Intel [8] позволяют одной командой выполнять операции одновременно над 4-мя парами операндов одинарной точности или над 2-мя парами операндов двойной точности. Соответственно, вычисление целевой функции и левых частей ограничений, по сути являющихся аддитивно-взвешенными функциями задач оптимизации при поиске решений можно осуществлять параллельно. Однако, очевидно, что в MS Excel эти возможности не задействованы, поскольку при использовании команд SSE-команд в процессе решения задач добавление одного или двух дополнительных ограничений не приводило бы к росту времени решения за счет распараллеливания арифметических операций для группы из нескольких (до 4) аддитивно-взвешенных функций. Таким образом, подводя итог можно сказать, что хотя MS Excel содержит в себе специальную надстройку для решения задач линейной и нелинейной оптимизации с непрерывными, дискретными и булевыми переменными, но экспериментальное исследование показывает, что возможности векторной обработки множества данных одной командой современных процессоров Intel не задействуются.

Научные конференции

 

(c) Архив публикаций научного журнала. Полное или частичное копирование материалов сайта возможно только с письменного разрешения администрации, а также с указанием прямой активной ссылки на источник.