Описание пакета GeomProg

Общая информация

Напомним постановку задачи ГП в канонической форме:

$$\mbox{ Задача GP:} \qquad g_{0}(x)\rightarrow \min$$

при ограничениях

$$g_{k}(x)\leq 1,\quad k = \overline{1,p},$$ $$x_{j}> 0 ,\quad j= \overline{1,m},$$

где

$$g_{k}(x)=\sum\limits_{i\in [k]}c_{i}\prod\limits_{j=1}^{m}{x_{j}}^{a_{ij}},\quad k= \overline{0,p},\quad c_{i}>0,\ a_{ij}\in \mathbb{R}.$$

Методы решения задач ГП в каноническом виде очень сложны, чаще всего используют метод внутренней точки ([7]) и метод Ражгопала-Бриккера ([9]). Метод внутренней точки реализован в пакетах MOSEK, TOMLAB, использующих MATLAB, а также в пакетах YALMIP и GGPLAB.

Авторами настоящего курса для решения задач ГП в каноническом виде создан пакет GeomProg. Этот пакет написан на языке программирования VBA и является приложением к программе MS Excel. Выбор средств реализации был обусловлен тем, что программа Microsoft Office установлена на большинстве компьютеров, работающих под управлением операционной системы Windows.

В пакете реализован метод Ражгопала-Бриккера, основанный на применении метода генерации столбцов для задачи обобщенного линейного программирования.

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

решение задачи ГП в канонической форме;

поддержка русского и английского языков;

поддержка стандартных способов ввода-вывода, сохранения данных и решения задачи;

формирование отчета по итерациям;

формирование листа с отчетом о решении задачи;

получение информации о времени решения задачи и количестве итераций.

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

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

Системные требования пакета GeomProg

Требования, предъявляемые к компьютеру для установки пакета GeomProg, минимальны:

операционная система: Windows 2000/2002(XP)/2003 ;

наличие программы Microsoft Excel ;

процессор не ниже Pentium 133 МГц;

память не менее 64 Mб RAM;

монитор Super VGA (800x600) или с более высоким разрешением с поддержкой 256 цветов;

cтандартные клавиатура и мышь.

Для корректной работы пакета рекомендуется использовать MS Excel 2003. При работе с данной версией программы рекомендуется закрыть все рабочие книги MS Excel, кроме книги, соответствующей программе GeomProg.

Установка пакета GeomProg

Для размещения пакета (полного набора файлов) на компьютере требуется совсем немного памяти: 670 Кб.

Для установки пакета достаточно создать на жестком диске папку GeomProg и разархивировать в нее все файлы архива GeomProg.rar. Для корректной работы пакета необходимо убедиться, что настройки используемой версии MS Excel позволяют использовать макросы ( Сервис | Макрос | Безопасность или Tools | Macro | Security ). Рекомендуется использовать средний уровень безопасности (решение о запуске макросов принимается пользователем).

Запуск пакета GeomProg

Для начала работы с пакетом необходимо запустить основной файл GeomProg.xls - откроется основное окно программы с главным меню (рис. 7.1).

В процессе загрузки программы может быть выдано сообщение о макровирусах. Для корректной работы программы следует выбрать кнопку Не отключать макросы ( Enable Macros ).

(рис 7.1) Главное меню пакета GeomProg

Навигация по пакету GeomProg

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

Завершение работы с пакетом GeomProg

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

Ввод данных задачи ГП с экрана

Для ввода исходных данных с экрана необходимо нажать кнопку Ввод данных с экрана (рис. 7.1). После этого на экране появляется диалоговое окно Ввод данных о задаче (рис. 7.2), позволяющее указать размерность задачи и задать ее имя.

(рис 7.2) Ввод данных о задаче

Окончание ввода параметров подтверждается кнопкой Принять. При выборе числа переменных и числа ограничений возможно указать только целые положительные числа. Затем появляется окно (рис. 7.3), в поле которого нужно ввести число мономов в целевой функции и нажать кнопку Принять. Имеется возможность ввести только целое положительное число.

(рис 7.3) Ввод числа мономов в целевой функции

После ввода числа мономов в целевой функции открывается рабочий лист DataProblem, на котором появляются диапазоны ячеек, в которые надо ввести коэффициенты и матрицу степеней целевой функции (рис. 7.4) и нажать кнопку Далее (рис. 7.5), которая станет активной после ввода данных. При выборе коэффициентов возможно указать только положительные числа. Аналогично ввод данных осуществляется для каждого ограничения. Для удобства пользователя области ввода данных имеют поясняющие имена ( $$A =,$$ $$c =$$ ).

(рис 7.5) Ввод коэффициентов и матрицы степеней целевой функции(рис 7.4) Рабочий лист DataProblem с данными о задаче

Ввод данных задачи ГП из csv-файла

Формат текстового файла, при котором в качестве разделителя единиц информации используется запятая, называется csv-форматом. Этот формат часто используется при записи больших массивов однородной информации. Он полностью совместим с MS Excel, поэтому был выбран для записи данных о задаче ГП в пакете GeomProg.

Чтобы ввести (импортировать) данные задачи ГП из файла необходимо нажать кнопку Ввод данных из файла (рис. 7.1). Если структура выбранного файла соответствует структуре, принятой в пакете GeomProg, то на экране появится рабочий лист DataProblem с данными задачи, прочитанными из файла. В программе предусмотрена проверка на соответствие файла требуемому формату. На рис. 7.5 приведен фрагмент рабочего листа DataProblem с данными задачи, импортированными из csv -файла Duffin.txt.

Опишем структуру файла с данными на примере следующей задачи:

$$g_{0}(x) = 40 x_{1}x_{2}+20 x_{2}x_{3}\rightarrow\min,$$

при ограничениях

$$g_{1}(x) = 0.2 x_{1}^{-1}x_{2}^{-0.5}+0.6 x_{2}^{-1}x_{3}^{-2/3}\leq 1,$$ $$x_{1}>0,\ x_{2}>0,\ x_{3}>0.$$

Duffin min 0.0001 3,1 2 40,20 1,1,0 0,1,1 2 0.2,0.6 -1,-0.5,0 0,-1,-0.67

Прокомментируем каждую строчку этого файла:

Duffin - имя задачи (любая строка);

min - тип целевой функции;

$$0. 0001$$ - требуемая точность вычислений;

$$3, 1$$ - число переменных, число ограничений;

$$2$$ - число мономов в целевой функции;

$$40, 20$$ - коэффициенты мономов в целевой функции;

$$1, 1, 0$$ - степени переменных $$(x_1, x_2, x_3)$$ соответственно в первом мономе целевой функции;

$$0, 1, 1$$ - степени переменных $$(x_1, x_2, x_3)$$ соответственно во втором мономе целевой функции;

Пустая разделительная строка;

$$2$$ - число мономов в первом ограничении;

$$0.2, 0.6$$ - коэффициенты мономов в первом ограничении;

$$-1, -0.5, 0$$ - степени переменных $$(x_1, x_2, x_3)$$ соответственно в первом мономе первого ограничения;

$$0, -1, -0.67$$ -степени переменных $$(x_1, x_2, x_3)$$ соответственно во втором первого ограничения.

Сохранение задачи ГП в csv-файле

Для удобства повторного использования данных о задаче, реализована возможность сохранения этих данных в виде файла. Для этого необходимо нажать кнопку Сохранить задачу в файле (рис. 7.5). После этого появляется диалоговое окно Сохранение задачи (рис. 7.6), в котором пользователю предлагается указать тип сохранения. В данной версии программы реализована возможность сохранения:

условия задачи в файле;

условия задачи и ее решения в файле (в этом случае, кроме условий задачи, в файл записывается оптимальное значение целевой функции и компоненты вектора решения). Опция доступна только после решения задачи (кнопка Решить задачу (рис. 7.5)).

(рис 7.6) Диалоговое окно Сохранение задачи

Выбор варианта подтверждается кнопкой Ok. После этого в диалоговом окне Запись задачи в файл (рис. 7.6) пользователю предлагается задать имя файла, в котором будет сохранена задача. По умолчанию в качестве имени файла предлагается имя задачи (из графы Имя задачи (рис. 7.5)).

(рис 7.7) Диалоговое окно Запись задачи в файл

Если файл с указанным именем уже существует, то будет предложено заменить имя (рис. 7.8).

(рис 7.8) Выбор нового имени файла

Решение задачи ГП

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

(рис 7.9) Возможность формирования отчета по итерациям

Нажатие кнопки Yes означает желание получить не только решение задачи, но и отчет о выполненных итерациях. Фрагменты отчета приведены на рис. 7.10 и рис. 7.11.

(рис 7.10) Верхние строки рабочего лист Iterations (для задачи Duffin)

Отчет включает в себя данные для обобщенной задачи линейного программирования, эквивалентной двойственной задаче ГП, и данные для исходной задачи ГП, полученные из решения соответствующей обобщенной задачи ЛП.

(рис 7.11) Нижние строки рабочего лист Iterations (для задачи Duffin)

Отчет о решении задачи

Решение задачи завершается автоматическим формированием на рабочем листе DataProblem отчета о решении задачи. Этот лист содержит следующую информацию:

исходные данные задачи;

решение задачи: оптимальные значения переменных, оптимальное значение целевой функции (в случае, если отчет по итерациям не формировался);

время работы программы (сек.);

число переменных обобщенной задачи ЛП;

количество итераций.

На рис. 7.12 приведен рабочий лист DataProblem с решением задачи Duffin. Задача Duffin, имеет оптимальное решение $$(0. 511, 0. 97, 1. 039)$$. Значение целевой функции (оно обозначено через $$g_0$$ ) равно $$39. 996$$. Следует обратить внимание на то, что вычисления всегда выполняются с максимально возможной точностью (соответствующей типу Double в VBA ), а на рабочем листе с решением приводятся значения, округленные до трех знаков после десятичной точки. В том случае, если нужна большая точность, потребуется изменить формат рабочего листа с результатами.

(рис 7.12) Рабочий лист DataProblem c отчетом о решении

Выбор языка

В пакете предусмотрена возможность выбора языка (русский/английский), на котором будет работать приложение. Чтобы выбрать (или сменить текущий язык) нужно нажать кнопку Выбор языка (рис. 7.1). Появится диалоговое окно Выбор языка/Language adjustment (рис. 7.13). Выбрав требуемый язык, нужно нажать кнопку Ok.

(рис 7.13) Возможность выбора языка

Справочная система пакета GeomProg

Для удобства пользователя пакет GeomProg оснащен справочной системой, которая содержит следующие разделы:

справка о пакете GeomProg ;

справка об авторах пакета.

Справка о пакете GeomProg

Для получения краткой справки о возможностях пакета GeomProg нужно нажать кнопку О программе (рис. 7.1).

Справка об авторах пакета

Для получения краткой справки об авторах пакета GeomProg нужно нажать кнопку Об авторах (рис. 7.1).

Банк задач пакета GeomProg

Напомним, что банк задач представляет из себя текстовый файл в csv -формате. В нем для каждой задачи указывается: источник, из которого она взята, данные задачи, оптимальное решение и значение целевой функции (рис. 7.14).

(рис 7.14) Фрагмент банка задач ГП

Краткие итоги

Подробно описана работа с пакетом GeomProg, его возможности и интерфейс.