О создании и использовании  в учебном процессе программного обеспечения  для решения экстремальных  задач

Бухвалова В. В.,  Рогульская А. С.

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

1. требования, предъявляемые к компьютеру для его установки, должны быть минимальными;
2. наличие дружественного интерфейса, в частности, использование стандартных постановок задач и обозначений;
3. поддержка стандартных способов ввода данных задачи и сохранения решения;
4. возможность не только решения задачи (получения оптимального решения, если оно существует), но и просмотра  процесса решения по итерациям;
5. возможность исследования полученного решения на устойчивость (определения интервалов изменения параметров задачи, при которых оптимальное решение либо остается неизменным, либо легко вычисляется);
6. возможность проведения тестирования алгоритмов, в частности, по времени решения задачи и количеству выполненных итераций;
7. возможность генерации случайной экстремальной задачи заданной размерности.

 

  Авторам известен только один пример учебного ПО, которое удовлетворяет первым пяти требованиям из перечисленных выше – это программа TORA. Студенческая версия  этой программы распространяется вместе с, видимо, самым популярным в мире учебником по исследованию операций Х. Тахи ([4]). Однако возможность проводить тестирование алгоритмов (п.6) также является важным элементом обучения. Имея результаты тестирования, можно, например, сравнивать алгоритмы и оценивать увеличение времени решения задач с ростом их размерности. Что касается генераторов задач (п. 7), то они предназначены, прежде всего, преподавателям. Их использование существенно упрощает процесс составления большого числа индивидуальных заданий и их проверку.

  Работы  по созданию ПО, удовлетворяющего всем перечисленным выше требованиям, проводятся в течение ряда лет на кафедре исследования операций СПбГУ под руководством В. В. Бухваловой. Так как при создании ПО, ориентированного на решение слишком широкого класса оптимизационных задач, как это сделано, например, в надстройке Excel «Поиск решения», трудно выполнить требования, перечисленные выше, было принято решение создать несколько программ (пакетов). Каждый из пакетов предназначен для решения определенного класса экстремальных задач. К настоящему моменту создано три пакета для решения оптимальных задач следующих классов:

• линейное и квадратичное программирование – пакет FinPlus;
• геометрическое программирование – пакет GP;
• дискретные задачи исследования операций – пакет ORP.

 

  В качестве платформы, на базе которой  создается ПО, была выбрана программа Microsoft Excel со встроенным в нее языком программирования Visual Basic for Applications (VBA, [6]). Этот выбор был обусловлен тем, что программа Microsoft Office установлена на большинстве компьютеров, работающих под управлением операционной системы Windows. Таким образом, наличие программы Microsoft Excel и является основным системным требованием. Установка на компьютере любого из созданных пакетов предельно проста – достаточно открыть главный xls-файл пакета в режиме, когда допускается использование макросов. Для размещения пакетов (полного набора файлов) на компьютере требуется совсем немного памяти: 1. 90 Мб для пакета FinPlus, 1.07 Мб для пакета GP и 670 Кб для пакета ORP.

  Еще раз подчеркнем, что создано ПО, предназначенное, прежде всего, для  использования в учебном процессе. Это означает, во-первых, что для  реализации были выбраны алгоритмы, которые изучаются в стандартных  курсах. Например, задача линейного программирования в пакете FinPlus решается стандартным модифицированным двухфазным симплекс-методом. Но с учетом того, что в курсах по математическому программированию симплекс-метод часто излагается с помощью симплекс-таблиц, предусмотрена возможность просмотра этих таблиц по итерациям. Во-вторых,  не ставилась цель решать реальные задачи большого размера также быстро, как это делается коммерческим ПО. Хотя заметим, что, например, решение ряда задач линейного программирования в пакете FinPlus с 30 переменными занимало несколько секунд.

  Все пакеты имеют одинаковый дизайн. В качестве примера на рис. 1 приведено главное меню пакета FinPlus. Выбор языка программирования VBA позволяет в полной мере использовать принцип модульности, который упрощает модификацию ПО и использование ранее разработанных модулей при создании нового ПО.  

  О пакете FinPlus ([1]). Стандартные курсы, посвященные экстремальным задачам, одними из первых рассматривают задачи линейного программирования (ЛП), а как метод их решения – симплекс-метод. Задачи квадратичного программирования (КП) можно решать, используя модификации того же симплекс-метода. Именно поэтому ПО для этих двух классов задач было объединено в один пакет. Для решения задачи КП в пакете реализован метод дополнительного базиса ([3]), который изучают студенты кафедры исследования операций СПбГУ. Версия пакета FinPlus для свободного копирования размещена на сайте exponenta.ru:

    http://www.exponenta.ru/educat/systemat/buhvalova/index2.asp. 

  

  Рис. 1. Пакет FinPlus: главное меню

  Перечислим  основные возможности пакета FinPlus:

1. решение задачи ЛП общего вида;
2. решение задачи КП общего вида;
3. формирование листа с отчетом о решении задачи;
4. ознакомление с работой пакета на примере демонстрационной задачи;
5. поддержка стандартных способов ввода-вывода и сохранения решения задачи;
6. редактирование данных задачи на рабочем листе MS Excel;
7. формирование отчета по итерациям;
8. для задач ЛП:

• формирование отчета «Постоптимальный анализ»;
• тестирование модуля;
• генерация задачи с заданными параметрами.

На рис. 2 показано, как выглядит лист с данными  задачи ЛП:

   

  

  Рис. 2. Пакет FinPlus: рабочий лист с данными задачи ЛП

  Отчет «Постоптимальный анализ» отражает результаты исследования решения задачи на устойчивость (рис. 3):  

  

  Рис. 3.  Пакет FinPlus: отчет «Постоптимальный анализ» 

  Существует  расширенная версия пакета FinPlus, позволяющая дополнительно решать задачи целочисленного ЛП (алгоритм Балаша) и некоторые задачи финансового планирования и портфельного анализа.  

  О пакете GP. Задачи геометрического программирования (ГП) гораздо реже изучаются в курсах экстремальных задач, чем задачи ЛП и КП. Однако в последние годы ситуация существенно изменилась. Это связано с тем, что были разработаны, во-первых, эффективные методы решения этих задач ([7], [10], [11], [12]), а, во-вторых, методы сведения довольно широкого класса оптимизационных нелинейных задач к задачам ГП ([2], [9]). Для популяризации идей и методов ГП авторы статьи разработали вводный интернет-курс по геометрическому программированию, который, в частности, предполагает использование пакета GP.

  Для решения задач ГП в пакете GP реализован двойственный метод, предложенный в [12], который на данный момент считается одним из самых эффективных. Перечислим возможности  пакета GP:

1. решение задачи ГП с ограничениями;
2. поддержка  русского  и английского языков;
3. поддержка стандартных способов ввода-вывода, сохранения данных и решения задачи (рис.4);
4. формирование отчета по итерациям;
5. формирование листа с отчетом о решении задачи;
6. получение информации о времени решения задачи и количестве итераций.

 

  Рис. 4. Пакет GP: рабочий лист с данными задачи ГП

  Создание  генератора нетривиальных задач ГП является сложной задачей, для решения которой пока не существует подходящего алгоритма. Поэтому в качестве его замены авторами был создан банк задач ГП, состоящий на данный момент из 74 объектов. Банк задач представляет из себя текстовый файл в csv-формате. В нем для каждой задачи указывается: источник, из которого она взята, данные задачи, оптимальное решение и значение целевой функции. Нам представляется, что банк задач ГП будет полезен не только преподавателям при составлении контрольных заданий, но и разработчикам нового ПО для решения нелинейных задач оптимизации в процессе его тестирования. 

  

  

  Рис. 5.  Пакет GP: фрагмент банка задач ГП

  О пакете ORP ([5]). Текущая версия пакета предназначена для решения следующих дискретных экстремальных задач: о назначениях, коммивояжера, кратчайший путь в графе, минимальное остовное дерево в графе. К настоящему моменту полностью сформирован модуль, связанный с задачей о назначениях (ЗН). Для решения ЗН можно использовать три алгоритма: аукционный ([8]), Мака, эвристический жадный.

  Для решения сетевых задач в текущей  версии пакета реализованы следующие  алгоритмы: задача о кратчайшем пути – алгоритм Дейкстры, задача о минимальном остовном дереве – алгоритм Краскала, задача о коммивояжере – метод ветвей и границ и жадный (эвристический) алгоритм. Перечислим реализованные возможности  пакета ORP: 

1. решение задачи о назначении;
2. решение задачи о коммивояжере;
3. решение задачи о минимальном остовном дереве в графе;
4. решение задачи о кратчайшем пути в графе;
5. поддержка стандартных способов ввода-вывода и сохранения решения задачи;
6. формирование листа с отчетом о решении задачи;
7. формирование отчета по итерациям;
8. тестирование модуля;
9. формирование файла статистики;
10. генератор задач.

 

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

  На  рис. 6 приведен лист с отчетом о  решении задачи о назначениях  эвристическим алгоритмом: 

  Рис. 6. Пакет ORP: лист c отчетом о решении задачи о назначениях

  Литература

1. Бухвалова В. В. Использование пакета прикладных программ FinPlus в учебном процессе / В. В. Бухвалова, А. В. Ковальчук // Обозрение прикладной и промышленной математики. – 2007. – Том 14, № 1. – с. 95-98.
2. Бухвалова В. В. Расширение области применимости методов геометрического программирования / В. В. Бухвалова, А. С. Рогульская // Обозрение прикладной и промышленной математики. – 2008. – Том 15, № 2. – с. 270-273. 
3. Даугавет В. А. Численные методы квадратичного программирования / В. А. Даугавет. – СПб.: Изд-во С.-Петерб. ун-та, 2004. – 128 с.
4. Таха Х. А. Введение в исследование операций / Х. А. Таха; пер. с англ., ред. А. А. Минько. – 7-изд. – М.: Издательский дом «Вильямс», 2005. – 912 с.
5. Филькина Т. Н. Алгоритмы решения задачи о назначениях: дипломная работа (СПбГУ, кафедра исследования операций). – СПб., 2008.
6. Уокенбах Д. Microsoft Office Excel 2007: профессиональное программирование на VBA / Д. Уокенбах; пер. с англ. – М.: Издательский дом «Вильямс», 2008. – 928 с.: ил. – (Прикладное программное обеспечение).
7. Alejandre J. L. A General Alternative Procedure for Solving Negative Degree of Difficulty Problems in Geometric Programming / J. L. Alejandre, A. Allueva, J. M. Gonzalez // Computational Optimization and Applications. – 2004. – No. 27. – p. 83-93.
8. Bertsekas D.P. A new algorithm for the assignment problem / D. P. Bertsekas // Math. Programming. – 1981. – Vol.1, No.21. - p. 152-171.
9. Boyd S. A Tutorial on Geometric Programming / S. Boyd, S., J. Kim, L. Vandenberghe, A. Hassibi // Optimization and Engineering. – 2007. – Vol. 8, No. 1. – p. 67-127.
10. Kortanek K. O. An infeasible interior-point algorithm for solving primal and dual geometric programs / K. O. Kortanek, X. Xu, Y. Ye // Mathematical Programming. – 1997. – No. 76. – p. 155-181.
11. Liu S. T. Posynomial geometric programming with interval exponents and coefficients / S. T. Liu // European Journal of Operational Research. – 2008. – No. 186. - p. 17-27.
12. Rajgopal J. Solving Posynomial Geometric Programming Problems via Generalized Linear Programming / J. Rajgopal, D. L. Bricker // Computational Optimization and Applications. – 2002. –No. 21. – p. 95-109.