автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.07, диссертация на тему:Декомпозиционные методы решения задач управления компьютерно-интегрированным производством



I На правах рукописи

Болодурина Ирина Павловна

Декомпозиционные методы решения задач управления компьютерно-интегрированным производством

05.13.07 — Автоматизация технологических процессов и производств

Автореферат диссертации на соискание ученой степени кандидата технических наук

Оренбург - 1996

Работа выполнена в оренбургском государственном университете.

НАУЧНЫЕ РУКОВОДИТЕЛИ:

Доктор технических наук, профессор Кацман В.Е.

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

Доктор технических наук, профессор

Туккель И. Л. Кандидат технических наук

Пщухин A.M.

ВЕДУЩАЯ ОРГАНИЗАЦИЯ:

АО "Стрела-инжиниринг"

Защита состоится nJ<t~cxZ/'j 1995 ГОда в/^часов на заседании диссертационного Совета К 064.64.01 при Оренбургском государственном университете по адресу: г. Оренбург, пр. Победы, д. 13. ауд. 1415.

С содержанием диссертации можно ознакомиться в библиотеке Оренбургского государственного университета.

Автореферат разослан 1996 г.

Доктор технических наук, профессор Абдрашитов Р. Т.

Учений секретарь диссертационного совета

и

/

- г -

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

Актуальность темы. Кардинальным путем повышения производительности труда, повышения качества выпускаемой продукции, а также снижение затрат производства является его автоматизация на основе широкого использования вычислительной техники. Наибольший экономический эффект достигается з случае объединения автоматизированных систем проектирования, подготовки производства и производства б единую интегрированную систему автоматизации под управлением ЭВМ с периферией в виде отдельных единиц технологического оборудования, РТК, станков с ЧПУ и т.д. Такие системы получили название компьютерно-интегрированных производств (CIM). -

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

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

обеспечения.

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

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

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

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

Работа выполнена в соответствии с заданием Федеральной иннс вационной программы "Инжинирингсеть России".

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

Задачи исследования. В соответствии с поставленной целью и состоянием решаемой проблемы определены основные задачи исследования:

- анализ состояния проблемы решения задач управления С1М;*

- разработка теоретического подхода к решению задач управления С1М высокой размерности с упорядоченным множеством параметров на основе метода многоуровневой декомпозиции;

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

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

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

Научная новизна. Предложен единый подход к рассмотрению методов управления и планирования С1М с большим количеством параметров. основанный на следующих результатах:

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

2. Доказана возможность получения нереккурентных количественна- оценок возможных схем разбиения для различных классов задач.

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

4. Приложение рассмотренной теории проверено на эффективность при решении следующих задач:

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

- оптимизация оперативного управления на ориентированных графах.

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

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

Реализация результатов. Система планирования производства внедрена на Оренбургском заводе "Сверл", что позволило автоматизировать выбор наиболее выгодного "портфеля" заказов.

Действенность,предложенного подхода проверена на задаче оптимизации управления взаимозачетами между предприятиями, реализованной в Оренбургском банке "Южный Урал".

Аппообация работы. Основные результаты работы были доложены и обсуждены на научном семинаре при генеральной дирекции федеральной. программы "Инжинирингсеть Рссии", на научно-технической конференции в ОГУ, опубликованы в информационных листках Оренбургского центра научно-технической информации.

На защиту выносятся:

1. Теоретическое обоснование и применение методики многоуровневой декомпозиции к решению задач высокой размерности с упорядоченным множеством параметров.

2. Зависимость числа вариантов декомпозиции задач от мощности заданного упорядоченного множества параметров и числа уровней разбиения.

3. Алгоритмы генерирования и синтеза схем разбиения.

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

5. Методика решения оптимизационных задач теории ориентированных графов методом декомпозиции.

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

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

Структура и обьем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 71 наименований и пяти приложений. Основное содержание работы изложено на 100 страницах, содержит 5 рисунков и 3 таблицы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ.

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

задач в процессе функционирования С1М.

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

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

В задачах большой размерности мы сталкиваемся также с проблемой "реального времени", то есть с необходимостью нахождения решения с помощью имеющейся вычислительной техники в требуемые сроки. Это приводит к особенностям управления С1М, когда оперативность решения задачи более важна по сравнению с точностью получаемого решения.

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

В настоящее время декомпозиционным методам решения сложных

задач посвящено значительное число работ . Классическими трудами Дхс. Данцига, в. Вулфа и И. Корнай, Л. Липтака; фундаментальными отечественными исследованиями Б. А. Булавского, Е.Г.Гольштейна. Р.А.Звягиной, П. с. Краснощекова, В.С.Танаева, В.И.Цуркова . Д.Б. Юдина, Г.С.Поспелова; известными зарубежными авторами К.Беером, Ляс. Бендерсом, М. Месаровича, Л. Лэсдоном, Дж. Розеном заложены основы теории декомпозиции. В зтих работах рассмотрены декомпозиционные методы и алгоритмы решения для задач оптимизации, принадлежащим различным областям математического программирования. Они основаны на том, что "большая система" обладает свойством наличия в структуре функциональных связей специфики, указывающей на возможность более или менее полного расчленения системы на подсистемы меньшей размерности. Однако 'в разработанных "структурно ориентированных" методах не определено, каким образом производится процедура разбиения системы на блоки и не установлено общее количество возможных схем разбиения.

Б работах В.Е. Кацмана при решении задач территориального планирования и управления используется методология многоуровневых разбиений множества параметров на блоки в процессе декомпозиции. В них исследованы теоретические вопросы структурирования системы на основе процедуры многоуровневого разбиения множества параметров слокной задачи, что позволяет получить подзадачи относительно невысокой размерности. Теория таких многоуровневых разбиений дает возможность проводить целенаправленную и обоснованную декомпозицию задач высокой размерности. Предложенный подход широко отражен в опыте создания региональных АСУ.

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

тором любые два элемента сравнимы, причем операция сравнения обладает свойством рефлексивности." антисимметричности и транзитивности.

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

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

Во второй главе рассмотрены теоретические аспекты процедуры разбиения задачи большой размерности с упорядоченным множеством параметров методом многоуровневой декомпозиции. Теория основывается на понятии "схемы разбиения" упорядоченного множества, которое позволяет формализовать процесс многоуровневой декомпозиции задач высокой размерности.

Рассмотрим задачу. Пусть X - упорядоченное множество параметров некоторой модели управляемого процесса, задано отображение Ь е Н этого множества в множество У - множество значений параметров и известна функция цели этой модели С„. Ставится задача на-

хождения такого отображения Ь : X -»"У" г при котором достигается

оптимальное значение целевой функции Сь. Эту задачу обозначим

г-а. у. н. с„ >.

Рассматривается случай, когда мощность упорядоченного множества X высока, что затрудняет оперативное решение поставленной задачи.

Предлагается проводить многоуровневую декомпозицию задачи 1

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

Рассматриваемый декомпозиционный подход предусматривает следующие этапы решения исходной задачи:

- выбор схемы-разбиения упорядоченного множества X. удовлетворяющей заданным ограничениям,

- формирование подзадач 11} = < Хи. У , Н13. СЛ >.

- их последовательное решение.

Этап формирования подзадач 11} ( Ы,...г , 3=1____к^

состоит з описании множеств Н отображений Ьи: Хи - У и задании целевых функций С„ подзадач.

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

Число решаемых подзадач совпадает с числом блоков разбиений всех уровней, значит число вариантов декомпозиции исходной задачи равно числу возможных схем разбиения множества переменных. Поэтому обоснован интерес к количественным характеристикам возможных схем разбиения и изучению свойст семейства" таких схем.

С помощью аппарата дискретной математики рассмотрены основные свойства схем разбиения упорядоченных множеств . Установлено, что семейство схем разбиения образует решетку, причем для упоря-

Исходная задача Ъ [ „

Ъп ; Подзадача 1-го уровня

Подзадачи I 2-го уровня I

тКт д Подзадачи ; ш-го уровня

Схема многоуровневой декомпозиции задач.

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

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

бинаторике известны числа Стирлинга 2-го рода и числа Белла. Аналогичные понятия введены для упорядоченного множества, для которых получены следующие реккурентные зависимости. Числа типа чисел" Стерлинга 2-го рода для упорядоченного множества определенные как число разбиений n-элементного упорядоченного множества на к блоков связаны соотношениями:

S (n, Ю -S (n-1, R-1) + S (г.-1, к) для 0<к<п,

S(n,n)=l при п)0.

S(n,0)=0 при п>0.

Установлена еще одна реккурентная зависимость:

п-1

S(n,K)= X S(l,k-1) для k>2.

1 = К -1

Число ВГ| типа чисел Белла для упорядоченного множества определено как число всех 'разбиений упорядоченного n-элементного множества:

л

В„= 2 S(n.k) . к = о

и установлено, что

п

Bn",j= I в, , где В0=1. 110

Для заданного упорядоченного множества вводится число K(n.m). определенное как число m-уровневых схем разбиения п-эле-ментного упорядоченного множества. Проведена оценка этого числа, получена реккурентная зависимость через числа типа чисел Стирлинга 2-го рода вида:

п

К(п,ш) = I sen, i) K(i,m-1) при n>0 , а>1 ,

1=0

K(n, 0) = 1 при 11)0 ,

-

K(O.m) = 1 при m>0, а также'представление K(n,m) без использования чисел S(n,K):

n - 1

K(n.m) = 2 K(i.m) K(n-i.c-l) .

1 = 0

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

sen.« . (;;;)

Тогда числа Вп легко могут быть представлены в виде:

В„ - 2nl .

Проведено дополнительное исследование чисел К и найдено и: явное представление в компактной форме для упорядоченных мно жеств, не используя числа Стрилинга, что нельзя сделать в случа произвольного множества:

К (п. и) = (га+1)11"1 .

Установлена их связь с числом различных остовов полног связного неориентированного графа с п вершинами.

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

схем разбиения п-элементного упорядоченного множества

р

К (п. т. 1) = Б(п.т(1-1)+1) П Б (1+1—1,1) .

1 = 1

где п>1, шП, 1<1<[ ] , р=т(1-1)-1+2

В работе разработан алгоритм генерирования схем разбиения на

основе которого осуществляется построение и выбор схем разбиения. Этот процесс является универсальной процедурой, однотипно применимой для различных классов задач. Он основан на построении по заданной (т-1)-уровневой схеме разбиения упорядоченного множества X всех га-уровневых схем разбиения этого множества. Это позволяет генерировать все 0~.1-,.. ,т-уровневые схемы разбиения заданного п-элементного упорядоченного множества.

Другая процедура построения схем разбиения заключается в генерировании по заданной ж-уровневой схеме разбиения (п-1)-элементного упорядоченного множества X всех т-уровневых схем разбиения множества ХШх„}, в соответствии с которой по исходной ш-уровневой схеме разбиения одноэлементного множества можно последовательно генерировать п-уровневые схемы разбиения 2-.3-,... п-элементных упорядоченных множеств.

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

В процессе функционирования С1М встречаются ситуации, когда управляемые переменные могут принимать лишь вполне определенные целочисленные значения, по отношению к которым понятие бесконечно малой окрестности не имеет физического смысла.

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

•Метод многоуровневой декомпозиции основан на рациональном выборе схемы разбиения согласно критерию цинимума погрешности декомпозиции. Декомпозиция проводится по многоуровневой схеме разбиения упорядоченного множества параметров,- в результате чего исходное множество п переменных разбивается на к! блоков каждый из которых соответствует новой обобщенной переменной Хр

(р=1____координирующей задачи. Тогда координирующая задача.

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

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

столбцов матрицы Т определяется по формуле:

ш к

им- I х1 I |113 - г1р|

1-1 р-1

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

вышеописанных процедур.

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

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

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

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

На основе предложенной методики к целочисленному программированию разработан декомпозиционный метод решения задачи плакирования прозводства. аппробированный на Оренбургском - заводе "Сверл".

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

ся следующей типовой моделью:

X

F(x)- =2 с3х3 max j-i

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

к к

1 х3 ( I V au ) < Ts , s=l____S .

1=1

Xj = 0 или 1 . где N - общее количество поступивших заказов;

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

S - общее количество оборудования, используемого для производства продукции;

аи - количество продукции 1-го наименования в 3-м заказе; V - трудоемкость обработки 1-го наименования продукции на s-оборудовании;

Т8 - максимально допустимая загрузка s-го оборудования в

планируемый период.

Под Cj понимается общая прибыль, получаемая предприятием в

результате выполнения J-ro заказа: м

сз - Z Cjau . i-i

где Cj - прибыль от одного сверла 1-го наименования. Если хЛ=0, то j-тый заказ не принимается; заказ выполняется в случае х3»1. Тем самым определяется оптимальная загрузка проиэ водсгва в планируемый период.

Предполагается, что предприятие полностью обеспечено сырь« на планируемый период.

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

Использованная методика решения значительно сокращается требуемый объем памяти и время счета ЭВМ при разработке планов, что позволяет оперативно реагировать на наиболее выгодный "портфель" заказов, поступающий на предприятие.

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

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

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

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

п-1

К(п.г) = X К(1. г)К(п-1, г-1) 1=0

где п - число вершин графа, г - число уровней разбиения.

Процедура выбора схемы разбиения множества вершин заданного графа заключается в поиске связных подграфов, соответствующих блокам разбиения. Формирование блоков разбиения происходит следующим образом. В блок' входят те вершины, у которых число связей с элементами блока больше, чем оставшееся количество связей. Предварительно, исходя из общего числа вершин п . определяется рациональное число г* "'¡уровней декомпозиции исходной задачи и максимально допустимое число кл вершин в каждом блоке разбиения ¿-того уровня (3=1.2____г').

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

При решении разнообразных задач граф кодируется-и хранится в оперативной памяти ЭВМ в виде списка смежности вершин. ■ В процессе работы метода происходит (г-1)-кратный просмотр списка смежности вершин заданного графа. Общее число вычислительных операций будет пропорционально числу вершин и этой величине.

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

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

Пусть задана система N предприятий с матрицей долгов Х={хпт; 1<п,пкЩ; будем считать, что хпп1>0, если п-е предприятие является кредитором т-го, и х„т<0 в обратном случае. Введем в

рассмотрение вектор сальдо всех предприятий Ь={Ь„; 1<п<Ш. где

N

Ь„(Х) = I хп Г1 и = 1

Взаимный зачет долгов можно рассматривать, как замену исходной матрицы долгов X на новую матрицу долгов Кп.гаШ, сохраняющую сальдо всех предприятий:

N

1 гпт = Ьп . п=1,. ..И .

Ш» 1

Критерием качества выберем сумму долгов всех предприятий:

N N

в(г) = I ? ы .

п=1 т=1

Очевидно, чем меньше Б(2). тем лучше проведен зачет долгов с экономической точки зрения.

Поставленная задача сводится к решению задач на графе. Сис-

тема долгов N предприятий изображается графом, в нем отыскиваются замкнутые'цепочки платежей, и все величины долгов в такой цепочке уменьшаются на величину минимального платежа. Число звеньев такого графа может достигать N(N-15/2. число цепочек будет .N1 . так что этот подход применим только при небольших N.

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

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

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

Предложенный подход к решению задачи о взаимозачетах внедрен в Оренбургском банке "Южный Урале", что позволило значительно усовершенствовать механизм регулирования финансовых отношений.

Основные результаты работы.

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

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

задачи.

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

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

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

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

7. Разработан комплекс программных средств, предназначений для эффективного решения больших оптимизационных задач управления на ориентированных сетях и графах, а также целочисленных задач высокой размерности с булевыми переменными. Программы составлены на языке ACCESS 2.'О для ПЭВМ IBM-486 и могут быть адаптированы для других моделей персональных ЭВМ. на которых установлены пакеты Microsoft Windows и Microsoft Access.

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ.

1. Кацман В.Е.. Болодурина И. П. Применение теории схем разбиения' для решения экономических задач высокой размерности. Тезисы XVI научно-технической конференции. Оренбург, Оренбургский политехнический инс-т , 1994 , 15 с.

г. Абдрашитов Р.Т.;" Болодурина И.П. -Программный комплекс оперативного решения оптимизационных экономических задач большой размерности. Оренб. гос. ун-т - Оренбург. 1996.. - 14 с.

3. Болодурина И. П. Решение задачи о зачете взаимных долгов методом многоуровневой декомпозиции. Оренбургский центр научно-технической информации. Информационный листок N 226-96, 1996 .

4. Болодурина И. П. Решение задачи планирования производства в условиях рыночной экономики методом многоуровневой декомпозиции. Оренбургский центр научно-технической информации. Информационный листок N 213-96. 1996 .