Автоматика.
    Автоматизация.
        Электротехнические
            комплексы и системы.

УДК 519.2

СПОСОБ АДАПТИВНОЙ АЛГОРИТМИЗАЦИИ ЗАДАЧ РАСЧЕТА

ПРОИЗВОДСТВЕННОЙ ПРОГРАММЫ

Балтовский А.А.

Введение

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

Как правило, для решения задач такого типа применяются методы отыскания точного решения или приближенные методы целочисленного программирования, связанные с различными схемами упорядоченного перебора, которые оговариваются заранее т.е. составляются согласно некоторым жестким программам перебора.

Работа выполнялась нами согласно постановления Верховного Совета Украины от 16.10. 1992 г. «О приоритетных направлениях развития науки и техники».

 

Анализ последних исследований

Как следует из анализа литературных источников [1-3] для решения задач такого типа чаще всего применяется метод ветвей и границ. Однако эффективность работы алгоритма, основанного на данном методе, существенно зависит от того насколько выбор конкретного метода отражает специфику задачи.

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

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

Предметом исследований – модели, методы и алгоритмы решения задач планирования с булевыми переменными.

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

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

Для достижения поставленной цели в работе решались следующие задачи:

- перехода к осредненной задаче оптимизации с булевыми переменными на основе рандомизации переменных;

-          задание итеративного движения в множестве случайных векторов.

Исследования проводились с использованием методов статистики и математического моделирования, теории оптимального управления.

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

Практическое значение полученных результатов состоит в повышении эффективности процесса планирования.

 

 

Основная часть

Переход к осредненной задаче с булевыми переменными:

 

, ; х – целое,

 

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

Итак, рассмотрим задачу

 

 

где  х – случайный вектор с плотностью распределения , реализации которого удовлетворяют требованию

 

, j = 1,2,…, n.

 

Зададим итеративное движения во множестве случайных векторов в виде

 

,                                                         (1)

 

где - случайный вектор, определяющий направление движения;

      - величина шага в направлении .

Определяя далее направление движения с помощью правила локального улучшения

,

 

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

Применим описанную выше схему вероятностных алгоритмов к задаче линейного программирования с булевыми переменными

 

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

 i = 1,2,…, m,

,  j = 1,2,…, n,

 

; х – целое, j = 1,2,…, n, k = 1,2,…,.

 

Свяжем с данной задачей соответствующую функцию Лагранжа и перейдем к вероятностной постановке задачи:

 

 

где  - блочное представление векторах, причем

 

 , ; х – целое, k = 1,2,…,,                    (2)

 

,  j = 1,2,…, n.                                                  (3)

 

т.е. к задаче вида где х – случайный вектор, реализации которого удовлетворяют требованиям (2), (3), и который имеет некоторую плотность распределения .

Будем задавать движение в пространстве случайных векторов итеративной формулой

 

,

 

где - случайный вектор, определяющий направление движения, такой что его реализации удовлетворяют требованиям (2), (3), т.е.

 

 , ,

, k = 1,2,…,,,

с плотностью распределения . U – булева случайная величина, такая что , .

Будем как и раньше, определять направление движения, выполняя правило локального улучшения в виде

 

.

 

Распишем подробнее :

 

 

Тогда разность    запишется следующим образом:

 

.

 

,      ,

 

Заметим, что

,

 

и, следовательно, в силу независимости случайных векторов y и x

 

.

 

При этом

.

 

Таким образом, задача состоит в определении случайного вектора , такого, что

 

.                        (5)

 

Булева случайная величина U на первом уровне работы алгоритма не меняется, т.е. N = 1,2,… .

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

 

, если ,

 

                                                  , для всех i = 1,2,…,, .

 

Движение (4) понимается в этом случае как действие над реализациями случайных  векторов.

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

 

,

 

где .

Определим переменные и следующим образом:

 

, N = 1,2,…,

если ,

 

 для всех .

 

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

 

, k = 1,2,…,.                                        (6)

 

В нашем случае

 

, ,.

 

После проведения осреднения по всем случайным переменным, присутствующим в неравенстве (5) имеем

 

Полагая , =1,2,… можно определить  из следующих условий:

 

,

 

 

 

При этом движение осуществляется по (6).

 

Выводы

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

 

 

1. Живоглядов В.П. Автоматизированный синтез алгоритмов активно-адаптивного управления // Изд. АН Кирг.ССР. Физ.-техн. и матем.науки.-1987.-№2.- С.33-40.

2. Сельвестров А.Н., Папченко О.М. Многократно адаптивные системы идентификации. – К.: Техника,1983.-111 с.

3. Математическое моделирование и методы оптимизации: Межвуз.сб.научн.ст. /Горьков. государств. ун-т им Н.И.Лобачевского; под ред. А.В.Сергиевского. - Горький: Б.ч., 1989. – 160 с.

4. Батурин А.Н., Тихомиров А.А. Моделирование экономических систем (целевой подход). – М.: Изд-во Московского ун-та, 1987.— 86с.

5. Оптимизация: модели, методы, решения. Сб.научн.тр. /Рос.АН СО. Сибир. энерг. ин-т. Отв.ред.В.П.Булатов. – Новосибирск: наука, 1992.- 357 с.