III Международная студенческая научная конференция Студенческий научный форум - 2011

Так как прибыль предприятия напрямую зависит от издержек, то целесообразно стремиться минимизировать эти издержки. Прежде всего, издержки порождаются отклонениями от плана работы предприятия, а также задержками в работе предприятия, которые происходят из-за неэффективных способов планирования, отнимающих значительное время. Исходя из этого, логично предположить, что эффективность работы предприятия может быть повышена с помощью, во-первых, разработки эффективных планов и, во-вторых, с помощью использования как можно более быстрых способов разработки этих планов. Средством решения этих проблем может быть компьютерная система поддержки принятия решений, основанная на решении поставленных задач математического программирования с помощью известных методов оптимизации.

Задачу минимизации издержек можно рассматривать, как задачу оптимизации с ограничениями типа равенства и неравенства, в этом случае явные ограничения сверху и снизу на аргументы целевой функции могут рассматриваться как естественные технологические и экономические ограничения на объемы производства, существующие на предприятиях.

В настоящее время существует значительное количество разнообразных алгоритмов решения оптимизационных задач, подобных (3),(4). Так как такой алгоритм будет являться основой системы поддержки принятия решений, которая разрабатывается для использования на производстве пользователями без углубленных математических знаний, то основным критерием оценки алгоритма будет являться скорость его работы. Также важна точность и корректность результата работы алгоритма. В данном исследовании сравнивались три алгоритма: комплексный метод Бокса, генетический алгоритм и сравнительно недавно появившийся алгоритм роя частиц. Метод Бокса был выбран для исследования, как надежная, многократно проверенная модификация метода Нелдера-Мида[1],[2], работающая с ограничениями. Генетические алгоритмы интересны своими высокими возможностями по адаптации к задаче и широкими возможностями по модификации и варьированию шириной спектра решаемых задач. Метод роя частиц, также как и генетические алгоритмы, обладает большой универсальностью, но вместе с тем он намного проще для программирования. Существует много вариантов алгоритма роя частиц. Для данного исследования был выбран канонический алгоритм с рекомендованными для решения большинства задач параметрами[3],[4]. Алгоритмы были реализованы на языке C# и протестированы на нескольких конфигурациях вычислительных машин. Приведено время работы алгоритмов на конфигурации AMD Athlon X2 3.00 GHz под управлением системы Windows XP Professional SP3.

Решения, полученные с помощью алгоритма Бокса с разным значением параметра точности, отличаются между собой в 3-4м знаке после запятой, что может служить источником ошибок разной степени серьезности, в зависимости от размерности вводимых параметров (например, если мы вводим параметры задачи, подразумевая тонны ресурсов, от неточности после запятой предприятие понесет меньшие убытки, чем если бы под параметрами задачи подразумевались тысячи тонн или более).

В таблице 3 приведены результаты работы метода роя частиц в зависимости от количества точек в рое. Так как этот алгоритм является в большой степени алгоритмом случайного поиска, то увеличение размера роя и длительности работы алгоритма (количества итераций) очевидно повышает вероятность нахождения корректного решения задачи. В данной работе было выбрано следующее условие завершения алгоритма: работа завершается по достижению некоторого определенного числа итераций, в течение которых решение не было улучшено.  

Видно, как повышается точность решения с увеличением объема роя, но вместе с этим значительно возрастает время работы. Очевидно, что объем роя можно варьировать и подбирать под определенные типы задач для достижения желаемой точности решения.

Результаты работы генетического алгоритма представлены в таблице 4. Основным параметром алгоритма является размер набора хромосом[5],[6]. Причем, чем меньше объем этого набора - тем меньше вероятность получить «хорошую» хромосому, а чем больше - тем больше вычислительная нагрузка на каждой итерации метода. Приведены результаты для 50 хромосом. 

На данном этапе исследований метод роя частиц выглядит наиболее перспективным как по скорости работы, так и по точности итогового результата.

Работа поддержана федеральным грантом 02.740.11.0043.

Библиографический список

1. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике: в 2 кн. Кн. 1. Пер. с англ. - М.: Мир, 1986, 350с.

2. Медынский М.М., Антоний Е.В. Численные методы нелинейной оптимизации: алгоритмы и программы. Учебное пособие - Москва, МАИ, 2003, 192с.

3. Kennedy J., Eberhart R.. Particle swarm optimization. // Proceedings of IEEE International conference on Neural Networks. - 1995, pp. 1942 - 1948.

4. Pedersen, M.E.H.; Chipperfield, A.J. (2010). «Simplifying particle swarm optimization». Applied Soft Computing 10: рр. 618-628.

5. Darrel Whitley, A Genetic Algorithm Tutorial, Statistics and Computing (4): 65-85, 1994.

6. Deb K., Agrawal S., Understanding Interactions Among Genetic Algorithm Parameters, 1998.

Код для цитирования: Скопировать