Microsoft Excel как инструмент решения комбинаторных задач
- 1 инженер, зам. начальника отдела, АО «Тайфун» (г. Калуга)
- 2,3 к.т.н., доцент, кафедра «Информационные системы и сети», Калужский филиал МГТУ им. Н.Э. Баумана
Аннотация
Постановка проблемы. Комбинаторные задачи занимают особое место при проектировании электронных устройств.
Цель. Предложить оригинальных подход к решению одной самых интересных комбинаторных задач – задачи покрытия.
Результаты. Рассмотрены различные варианты данной задачи и решения их средствами Excel на примере организации, занимающейся сопровождением разнообразных проектов. Приведено распределение сотрудников по проектам. Выбрано четыре варианта данной задачи и показаны способы их решения.
Выриант 1 задачи: необходимо оптимизировать структуру организации так, чтобы минимальное число сотрудников могли выполнять все проекты. В статье показано решение данной задачи методом Петрика. В работе рассмотрено решение данного варианта инструментарием Excel «Поиск решения». Найденное решение совпадает с одним из оптимальных, полученным алгебраическим образом.
Вариант 2 задачи: необходимо выбрать такое минимальное число сотрудников, чтобы в случае болезни одного из них, оставшиеся могли работать над этим проектом. То есть необходимо обеспечить дублирование. Чтобы решить задачу средствами Excel, необходимо только изменить условие. В результате было получено решение, что необходимо оставить четырех сотрудников для выполнения всех проектов с дублированием.
Вариант 3 задачи: считается, что сотрудники имеют разный приоритет в организации. Необходимо было подобрать таких сотрудников, чтобы их суммарный приоритет был максимальным.
Вариант 4 задачи: определенных сотрудников необходимо оставить. В работе было показано, что для решения данного варианта задачи инструментарием Excel достаточно добавления к таблице нового столбца, со значениями равным 1, если сотрудника в соответствующей строке необходимо оставить, и равным 0 в противном случае. Также в диалоге параметров поиска решения следует добавить число сотрудников, которых необходимо оставить.
Практическая значимость. На конкретном примере показано, что Excel является хорошим средством решения комбинаторных задач.
Для цитирования
Аксенов А.Е., Донецков А.М., Николаев А.С. Microsoft Excel как инструмент решения комбинаторных задач // Электромагнитные волны и электронные системы. 2019. № 3. С. 40–44. DOI: https://doi.org/10.18127/j15604128-201903-07
Список источников
- Коновалов И.В., Коновалов В.Н., Максимов А.В., Максимова Е.А., Онуфриева Т.А. Логический синтез специализированных вычислительных устройств в САПР «Decomposer» // Электромагнитные волны и электронные системы. 2018. № 3. Т. 23. С. 18−25.
- Жукова И.В., Родионов А.В., Чухраев И.В. Система тестового окружения и моделирования микросборки речепреобразующего устройства // Электромагнитные волны и электронные системы». 2018. № 3. Т. 23. С. 52−56.
- Еремеев А.В., Заозерская Л.А., Колоколов А.А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискретный анализ и исследование операций (г. Новосибирск). Сер. 2. 2000. Т. 7. № 2. С. 22−46.
- Galinier P., Heztz A. Solution techniques for the large set covering problem // Discrete applied Mathematics. 2007. V. 155. № 3. P. 312−326.
- Listrovoy S.V., Gul A.Yu. Method of Minimum Covering Problem Solution on the Basis of Rank Approach // Engineering Simulation. 1999. V. 17. P. 73−89.
- Balachandar S., Kannan K. A Meta-Heuristic algorithm for Vertex covering problem Based on Gravity // World Academy of Science, Engineering and Technology. 2009. V. 35. P. 555−561.
- Барышев А.В., Федотова Е.Л. К вопросу использования надстройки Excel «поиск решения» в задачах линейного программирования // Науковедение (интернет-журнал). 2015. Т. 7. № 3. http://naukovedenie.ru/PDF/54TVN315.pdf (14.03.2019).
- https://www.allaboutcircuits.com/technical-articles/prime-implicant-simplification-using-petricks-method (17.03.2019).
- Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка. 1979. 200 с.
- Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Физматлит. 2005. 368 с.