АННОТАЦИЯ

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

Перечислим основное содержание четырех разделов данной работы.

Раздел 1 посвящен алгоритмическим основам программы pdlev. В р. 1.1 описана блок-схема обобщенного метода уровней применительно к задаче минимизации на многограннике собственной выпуклой, вообще говоря, недифференцируемой функции, которая принимает конечные значения лишь на некотором непустом подмножестве этого многогранника. В отличие от стандартного метода уровней (получающего с помощью оракула локальную информацию о функции в точке, т.е. значение функции и один из ее субградиентов), на каждой итерации предлагаемого метода оракул сначала отвечает на вопрос, принадлежит ли текущая точка множеству эффективности функции dom f или нет и, в зависимости от ответа на этот вопрос, либо выдает локальную информацию о функции (если Да), либо строит гиперплоскость, отделяющую текущую точку от dom f (если Нет). Приведена теоретическая оценка сходимости этого метода.

В р. 1.2 блок-схема применяется к частной задаче - задаче линейного программирования, разбитой на два вертикальных блока, в этом случае минимизируемая функция и множество заданы неявно. Приводится пример построения оракула для этой задачи. Получившийся при этом прямой декомпозиционный алгоритм в р. 1.3 тестируется для линейных задач, в которых один из блоков имеет блочно-диагональную структуру; приведенные численные результаты демонстрируют высокую вычислительную эффективность алгоритма. В р. 1.4 уточняются некоторые детали алгоритма (чистка пучка, частота проверки критерия окончания счета и т.д.), реализованного в программе pdlev.

Раздел 2 содержит информацию о программе pdlev как о процедуре, написанной на ФОРТРАН'е; в нем дано описание параметров (входные и выходные параметры, рабочие массивы, области common, используемые процедуры), указаны максимальные размеры решаемой задачи и т.д. Приведен схематический вид процедуры fun, создаваемой пользователем и реализующей работу оракула; отмечено, что для каждого класса задач должен быть создан свой оракул, использующий особенность решаемой задачи.

Для применения программы pdlev пользователь должен самостоятельно приготовить процедуру fun, что в большинстве случаев довольно сложно. Поэтому раздел 3 посвящен примеру применения программы pdlev к задаче линейного программирования, разбитой на два блока, один из которых имеет блочно-диагональную структуру: для этой задачи составлены программа main (в которой происходит подготовка исходных данных, решение задачи с помощью прямого декомпозиционного алгоритма и обработка полученных результатов) и согласованная с ней процедура fun, реализующая работу оракула для данной задачи. В р. 3.1 представлена тестовая задача небольшого размера; р. 3.2 показывает, как нужно приготовить файл входных данных как для общей задачи, так и для тестовой задачи из предыдущего раздела; в р. 3.3 приведен стандартный вид выдачи результатов на примере тестовой задачи. В р. 3.4 описана организация хранения в рабочих массивах данных, которые используются в main и fun. Этот раздел предназначен для тех, кто хочет познакомиться с устройством программ, в частности, для внесения изменений в текст процедур в целях адаптации их к оракулу, отличному от предлагаемого. В р. 3.5 приведено несколько заключительных замечаний.

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

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


Copyright © ЦЭМИ 1999 г.
117418, Москва, Нахимовский пр, 47 
На первую страницу сайта
тел: (095) 129-10-11, факс: (095) 718-96-15
Отправить письмо: director@cemi.rssi.ru