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

российская академия наук

ордена ленина институт проблем управления

на правах рукописи

турдалиев насирдин шамаратович

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

Специальность 05.13.06 - автоматизированные

системы управления

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

Москва 1992

Работа выполнена в Институте проблем управления РАН.

Научный руководитель.- доктор технических наук,

профессор Мамиконов А.Г.

Официальные оппоненты: доктор технических наук,

профессор Бурков В.Н. кандидат технических наук, с.н.с. Темкин В.И.

Ведущая организация - Институт народно-хозяйственного

прогнозирования РАН (г. Москва).

Защита состоится ••_" "^/е-^е. 1992 г. в_

часов на заседании специализированного совета К.002.68.01

Института проблем управления по адресу:

117806, г. Москва, ул. Профсоюзная 65, тел. 334-93-29. .

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

Института проблем управления.

Автореферат разослан ^^/т^- 1992 г.

Ученый секретарь специализированного совета.

К • Т • Н • 9 С.Н.С.

Пащенко Ф.Ф.

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

. ,. I

- --! '

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

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

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

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

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

Таким образом, актуальность построения и исследования механизмов натурального обмена обусловлена необходимостью в

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

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

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

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

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

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

функционирования системы обмена.

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

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

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

Связь с планом работ. Работа выполнялась в соответствии с плановой тематикой Института проблем управления в рамках следующих тем: "Модели управления перераспределением ресурсов в слаборегламентированных системах" N 01.86.0.101789, "Разработка задачи автоматизации подбора вариантов обмена в отделе перераспределения ресурсов" (хоз. договор и 164-89/20).

Апробация работы. Основные результаты докладывались автором и обсуждались на Всесоюзном научно-техническом семинаре "Автоматизация управления материальными ресурсами" /г. Тула, 1989 г./; Научно-технической конференции "Средства и системы автоматизации управления процессами сельскохозяйственного производства" /г. Паланга, 1991 г./

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и включает 132 стр.

машинописного текста и 9 рисунков.

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

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

Глава I посвящена анализу проблем перераспределения ресурсов, вопросам описания ресурсов. Рассмотрены некоторые вида запросов, которые могут быть предъявлены к информационно-справочной подсистеме системы обмена.

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

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

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

Особенности информационной системы, обслуживающей систему обмена, • состоят в том, что: I) заранее не известно множество ресурсов, которые могут находиться в системе обмена; 2) номенклатура ресурсов постоянно меняется; 3) множество ресурсов, находящихся в любой момент в системе обмена составляет небольшую

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

Будем считать, что описание ресурса состоит из .ключевого слова и нескольких атрибутов. Запрос на поиск тех или иных предлагаемых или спрашиваемых ресурсов составляется в два этапа. На первом этапе находится ключевое слово, соответствующее вводимому ресурсу, т.е. фактически определяется класс ресурса, или другими словами отношение в РБД (реляционной базе данных). Это нетрудно будет сделать, т.к. предполагается, что проведена классификация всех ресурсов. Затем составляется собственно запрос. Будем обозначать запрос в виде а( и, •$ ), где к -отношение в РБД, а у - условие отбора записей.

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

требуемый телевизор размер экрана цена

> 50 см < 3000

[ 40, 60 ] [ 2000, 3000 ] большой не очень дорогой Запрос: "Найти все предлагаемые телевизоры с большим экраном" —>-о ( предлагаемые телевизоры; размер экрана = "большой") тоже относится к запросу второго вида, т.к. здесь а задано в нечетком виде.

Необходимость в запросах такого типа велика, т.к.

s

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

Для формирования и . обработки запросов такого типа предлагается использовать аппарат теории нечетких множеств.

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

Рассмотрим запрос о( R, s ) с условием s вида:

(V»ta4) л <А2ега2) л ... л (AnenaJ. Задана допустимая степень выполнимости условия - Ks. Обозначим через к степень выполнимости условия Aioia. , i= 1, п. Для любого просматриваемого ресурса хе R

K(s(x)) = min (Kt(s), .... кп(х)). Если для Vxe R. K(s(x)) с Ks, то возникает задача распшрения запроса. Пусть N - допустимое число простых условий в которые можно изменять с целью расширения запроса. Построим матрицу S такую, что s. . = К (х), 1= 1, п, 3= Т7~т - степень выполнимости i-ro простого условия для ресурса х <= R.

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

большой. Обозначим эти значения через а*, ..., а^. Будем считать, что при расширении запроса а. может принимать значения только близлежащие от текущего. Т.е., если а = а^, то возможны только переходы: з? ->- а?** и а^ ->- а*"1. Обозначим такие переходы через

а* И а" .

) 1

Те же саше соображения можно отнести к операции сравнения ej , у которой есть множество значений, которое мокно каким-то образом упорядочить, например: намного меньше - меньсе - равно -

около - больше - намного больше. Обозначим их через е*, ____ е'.

Будем считать, что если ^ = о?, то разрешены перехода: а^ -> е^ ->- в^"1- Обозначим эта переходы через е* и е~.

Тогда для условия (А. вj а ) допустимы следующие переходы: (А.в'а. ). (А.е'а.), (Л.^а-). (А, в, * ).

В соответствии с этими переходами из матрицы Б получаем матрицу Э' такую, что V 1, о, Б.' > кз, т.е. каждой строке матрицы Э' соответствует ресурс близкий, в смысле заданных условий, первоначальному запросу.

Функции информационно-справочной подсистемы системы обмена используются при реализации найденные вариантов обмена, выдаче справок владельцам ресурсов и при поиске вариантов обмена ••вручную". В 1.3 описываются различные типы запросов, которые могут быть предъявлены информационно-справочной подсистеме.

Глава 2 посвящена задаче поиска и достройки многократных вариантов'обмена ресурсов общего вида.

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

множество ресурсов, при этом он треоует ресурс 1е Б. в количестве, не Оольшем, чем ь* и предлагает ресурс ке Р. в количестве, не большем а*. Каждый владелец 1е N на множестве своих запросов и предложений задает обменные отношения 1: за

1е I

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

Необходимо найти множество {у" , 1, д'е и, 1е Р^ э. , к« Р^}, удовлетворяющее условиям:

е е у)* < 4 • ке Р4 п Б. , 1е N (2.1)

) е N I е Рк I J

Здесь Р*- множество ресурсов 1, для которых пг* * о. Уравнение (2.1) - это ограничение сверху на количество ресурса к, отдаваемое владельцем 1. Аналогичное ограничение сверху вводится на количество ресурса 1, лолучаемое владельцем 1:

с е у*. < . 1бР; П5., 16 к (2.2) ¿бНкбР'

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

е' е У-1 < еч" еУ" • м, кб Р (2.3) ¡еК^еР1 ' $. ¡6 Н

У*' > о , 1, о е II, 1<= Т. л а, ке Р^ (2.4)

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

ЕЕ Е . Е о1 у^ —->.шзх (2.5),

J€ N ve И kgP: i6S. '

i / i. 1 1

здесь о1- стоимость ресурса 1. Задачу (2.1)-(2.5) можно преобразовать в задачу поиска оптимального потока на сети с усилением в дугах.

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

Рассмотрим формальную постановку этой задачи. В результате решения задачи (2.1)-(2.5) получено множество {у^ }. Необходимо это множество разбить на два множества (у^'} и }, где у*.' -количество ресурса 1, которое владелец j должен отдать владельцу i, - количество ресурса 1, которое владелец i передает

посреднику. Рассмотрим все уравнения (2.3), где выполняется строгое неравенство.

Е Е У-; < Е Е У-) . U N. ке Р. . ,е N ie Pk i€ S. js N

j* i J 1 i* i

Пусть i\ = Е111*1 Еу" - E E E E

i«S J€Ii jg N ie Pk je N ie Pk

1 i* i i 1 ¡j. i 1

Посредник может либо взять ресурс к у владельца i, либо уменьшить

количество ресурсов, отдаваемых за ресурс к, либо то и другое

одновременно. Пусть х количество ресурса к, которое посредник

хочет взять у владельца i, х" часть, от у", записать:

+ Ей" Е г- . ie N, lee Р

П1 . _ С! 1 : _ IT L J 1 1

le s.

kl . kl X . < y. . .

ч 4

M

i, Je N, le Pj n s.

ke P

-

> O,

Í£ H, te P.

i,á e N, le Pj n S. , ke P*

x > 0,

nv '

Тогда, можно

(2.6)

(2.7)

(2.8)

(2.9)

(2.10)

но никем не (2.1 )-(2.3)

ie N, ke P.

V

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

получении. Пусть

tk = min {ak, Em"1 Е К ie N, ke U Р. / U S. .

1 ie S.1 je N iе N 1 i е N *

v i* i Тогда можно записать

х*< t , ie N, ke U Р. / U S, m 1 ¡6 H 1 De N

(2.11)

Решение посредник должен получить в виде множества {хп. }: 4 = Е м 2 N. ке 34 (2.12)

J

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

бюджетное ограничение (если требуются выплаты .за ресурс):

е е о" < и, (2.13)

1<= N ке а т

здесь 0. - величина денежного фонда посредника. Пусть посредник Евел оценки всех ресурсов и оценка ресурса к раина вк. Тогда в

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

Е Е Вк хк. ----->- тах (2.14).

1е N ке Б. П1

Заметил, что в задаче (2.6)-(2.14) под к понимается множество владельцев, вошедших в вариант обмена, найденный в результате решения задачи (2.1)-(2.5). Таким образом, мы получаем двухэтапную оптимизационную процедуру: на первом этапе решается задача (2.1)-(2.5) и в рамках найденного варианта обмена решается задача (2.6)-(2.14).

Найденный вариант обмена рассылается всем владельцам, вошедшим в него. В результате опроса владельцев, для каждого владельца 1 получаем множества V: = , 1<= р. п Б. , ¿е N } -согласие на получение, = , 1се р. л sj, д'е N } - согласие на отдачу. На основе полученной информации посредник кокет определить варианты обмена, не разрушенные в результате отказов (задача выделения), подбирать новые варианты замыканий разрушенных вариантов обмена (задача достройки), либо сначала решать задачу выделения, а на оставшемся множестве согласий -задачу достройки.

Рассмотрим задачу выделения. Необходимо вначале проверить, можно ли реализовать множество ъ= .} в виде варианта обмена, т.е. необходимо показать (если это возможно) каждому владельцу 1, что множество не уступает по обменной стоимости множеству Ъ'. Т.о. для каадого владельца 1 необходимо найти множество

>, удовлетворяющее следующим ограничениям:

Е а* < Е а!^ Е ¿1.. ке Рс (2-15)

1 6 N/1 8. '¡€ЙА 1

Е а.к1 < 1 , 1е Б. , . (2.16)

к€ Р1 '

ак[ >0, кб Р. , 1с Э. (2.17).

Неравенство (2.15) означает, что владельцу 1 за ресурс к дают совокупность ресурсов не меньшей, с его точки зрения; обменной стоимости. Эту задачу необходимо решить для каждого владельца

и. Если найдется хоть один владелец 1, для которого нельзя найти множество (а" }, удовлетворяющее (2.15) - (2.17), то это значит, что множество {г^. , 1, N. 1е Б^ п } не может Оыть реализовано в виде варианта обмена. В этом случае из множеств и 1" выделяется множество вариантов обмена,сгодных к реализации. В 2.2 приводится постановка- этой задачи и метод сведения ее к задаче поиска оптимального штока на сети с усилением в дугах.

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

Задачу достройки нельзя сформулировать однозначно. Ее формулировка зависит от:

1) способа предъявления варианта обмена владельцам ресурсов;

2) вида отказов;

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

4) целей, которые преследует посредник при достройке варианта обмена.

Можно выделить два способа предъявления найденного варианта обмена.

I) Посредник одновременно сообщает каждому владельцу 1 множества } ресурсы, которые он может получить и {у*. } - ресурсы, которые он должен отдать, а затем, получив информацию на предложенный вариант обмена от всех владельцев, решать задачу достройки.

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

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

1) отказы, связанные с получением ресурсов;

2) отказы, связанные с отдачей ресурсов;

3) отказы, связанные с изменением обменных отношений.

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

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

2) Посредник может устанавливать свои цены в рублях на ресурсы из обменного фонда.

3) Посредник может одновременно устанавливать свои цены и задавать обменные отношения.

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

согласие владельца 1 участвовать в варианте обмена.

В соответствии с этими гипотезами формулируются две возможные цели посредника:

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

2) максимально реализовать фактические согласия владельцев на отдачу.

Таким • образом, выбор посредником стратегии достройки вариантов обмена зависит от конкретного набора перечисленных факторов. В 2.3 рассматривается задача достройки для различных наборов факторов.

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

В 3.1 рассматривается случай неделимых ресурсов.

Пусть каждый владелец пе н предлагает множество Рп неделимых ресурсов и спрашивает множество неделимых ресурсов, при этом Бпп Р. е 0, Бп, Рп€ Ы. з"=Бпп Рга - множество ресурсов, которое владелец п спрашивает у владельца ш. Все ресурсы в системе предполагаются равноценными. . Необходимо для владельца к разработать процедуру поиска и реализации вариантов обмена. Определим ориентированный граф см= (А.У) следующим оОразом: вершинами графа являются все владельцы, дуга (п, т) е V, если множество э® непустое. Тогда владельцы входят в один вариант

обмена, если на графе gn соответствующие им вершины образуют

контур с. , при этом на кавдой дуге (m,n)s с. определяются

о. о. о. 1 с.

множества (S^) 1, такие, что 4 = 1 (S„) 4 = --- = |(S™) |=Р„ .

i

PQ / о, n, n,..., te ct, т.е. казвдый владелец, вошедший в вариант i.

обмена, должен получить столько ресурсов, сколько он отдает, и количество этих ресурсов равно PQ . Обозначим через ок- множество

I

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

следующим образом:

Z к ----->- maz (3.1),

С.е С

при n (S^)°J = о • (3.2),

(S") 1 л (S™) j - 0 (3.3),

для всех С. , Cj е ск , Пе С. , 1е С. , те С. л С. .

Условия (3.2) и (3.3) определяют допустимое множество

вариантов обмена. Условие (3.2) означает, что владелец, входящий

в допустимое множество вариантов обмена, может взять каждый

спрашиваемый гол ресурс только у одного владельца, а условие

(3.3)- что каждый предлагаемый им ресурс он может отдать только

одному владельцу.

В работе предлагается многоэтапная процедура поиска

вариантов обмена. Вводится понятие кратности вариантов обмена,

т.е. количества участвующих в нем владельцев ресурсов. Идея

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

кратности обладают более высокой степенью надежности и

"отказоустойчивости". Поэтому на каждом следующем этапе строятся

варианты, кратность которых на единицу больше предыдущих.

На перЕсм этапе находится оптимальное множество прямых

вариантов обмена, т.е. решается задача (ЗЛ)-(З.З), но при этом ск- множество всех контуров длины 2, проходящих через вершину к. Затем происходит реализация найденных вариантов обмена. В случае отказов некоторых владельцев от предложенных прямых вариантов обмена посредник может реализовать нераспавшиеся прямые варианты обмена и затем опять искать оптимальное множество прямых вариантов обмена, но уже на обновленном множестве владельцев и ресурсов. Данный этап считается законченным, если владелец обменял все свои ресурсы, или исчерпаны все прямые варианты обмена. В первом случае задача полностью решена, во втором случае переходим к следующему этапу, который во всем аналогичен первому, но множество Ск состоит из трехкратных вариантов обмена.

Рассмотрим в общем виде г. -й этап. На п-м этапе у владельца к еще остался неудовлетворенный спрос и отсутствуют варианты обмена кратности меньшей или равной п. Строится оптимальное множество (п+1)- кратных вариантов обмена для заданного владельца к, т.е. решается задача (ЗЛ)-(З.З), но при этом ск- множество всех контуров длины (п+1), проходящих через вершину к. Далее все аналогично этапу I.

Процедура заканчивается, если:

- спрос владельца к полностью удовлетворен;

- те ресурсы, которые владелец к предлагает в данный момент, никому не нужны;

- в связной компоненте графа 0ы, которой принадлежит владелец к, имеется п вершин и завершен (п-1 )-й этап.

Заметим, что в этой процедуре постоянно решается задача (3.1)-(3.3), но на очень узком множестве контуров ск (на первом этапе - .то множество контуров длины 2, на втором длины 3, и т.д.). Это обстоятельство позволяет свести рассматриваемую задачу

к задаче поиска максимального потока на сети.

В случае прямых вариантов обмена строим двудольный граф, вершинами которого являются ресурсы, составляющие опросы и предложения владельца к. Спрос Зк.е Зк, 1= 1, |8к | соединен с предложением р с Рк, 3= 1,|Рк|, если 3 1, 1=1,, 1* к, такое, что одновременно выполняются следующие условия: Зк1б Рк и Рк.е Бк. Необходимо найти такую совокупность попарно несмежных ребер графа, которая включала бы в себя максимальное количество верши, соответствующих спрашиваемым владельцем к ресурсам, т.е. неогходимо решить задачу о максимуме паросочетаний на двудольном графе, вершинами которого являются опросы и предложения заданного владельца.

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

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

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

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

предлагают ресурс и спрашивают ресурс х-^.,»- Обозначил

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

1 ' п- 1

количество возможных вариантов обмена равно N. = П л . , а всего

_ I

вариантов обмена - к= £ N . Нам же необходимо Еибрать 1

вариантов обмена. Их посредник выбирает, исходя из своих интересов: он может, минимизировать число владельцев, участвующих в n-кратпых вариантах обмена, либо же выбрать владельцев, которые ближе всего расположены к владельцу к и т.д. Эту задачу можно сформулировать в терминах задачи типа унификации, размещения (ЗТУР): требуется определить

min P(w)= Р(а), (3.4)

we I

где P(w)= £ г + Е min с. . , х= С 1, 2, , га ), lew 1 ¿sJ iew lJ

J= { 1, 2..... 1), r. , o.. > О, 0£ I.

Здесь I - множевтво владельцев, у которых владелец к может взять требуемые ему ресурсы, J - множество ресурсов, которые владелец к может получить,, с. . - мера предпочтения владельца к на ресурс J принадлежащий владельцу ie I. Будем считать, что ctj= со, если у владельца i отсутствует ресурс j. Это гарантия того, что найденное в результате решения задачи (3.4) множество-владельцев а с х имеет множество ресурсов полностью покрывающих множество J. В противном случае Р(а)= <*>. Заметим, что состав и количество найденного множества владельцев сильно зависит от соотношения величин г. и си . Если, например, для V 1<= I, г. будет на порядок больше о., (для о гв.со), то значит мы минимизируем количество владельцев, множество ресурсов которых покрывает J.

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

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

обмена не ведет к разрушению остальных вариантов обмена.

Определим понятие схемы варианта обмена. Рассмотрим ориентированный граф сн= ( А, V): вершинам! графа являются ресурсы из множества м, дуга («)6 V, если найдется владелец, который за ресурс X готов отдать ресурс I: ^х)е V: э 1, га '* о. Граф ск будем называть графом согласий на ресурсах.

Схемой варианта обмена будем называть любой контур из графа сн. Наличие такого контура означает, что на множестве формальных совпадений опросов и предложений существует вариант обмена, в котсром осуществляются передачи ресурсов, соответствующих вершинам контура. Заметим, что каждой дуге (1;, х)е V соответствует множество владельцев с параметрами: а' , ъ[ , тг.

Будем считать, что вариант' обмена, соответствующий схеме варианта обмена, должен удовлетворять следующим условиям:

- каждый владелец 1 , вошедший в этот вариант обмена, за каждый ресурс 1;, передаваемый владельцу 1 , получает только определенный ресурс X от владельца 1э;

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

Эти свойства варианта обмена позволяют реализовывать его независимо от других вариантов обмена.

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

со вторым по значению произведением и т.д.

Можно предложить различные процедуры реализации вариантов обмена, соответствующих схемам вариантов обмена. Например: ищется оптимальное множество вариантов обмена, соответствующих схемам длины 2 (т.е. прямые варианты обмена ), реализуем их, затем перехода к трехкратным вариантам обмена и т.д.

Глава_4_ посзящена вопросам использования механизмов

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

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

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

I) его технологической матрицы А|3 ^|Р |, где - множество

видов продукции, которое оно может выпустить, - множество видов продукции, которая для этого требуется. а1к - количество единиц ресурса вида 1е зп, необходимое для выпуска единицы продукции вида ке Рц;

2) информации о поставщиках: их опросах, предложениях и обменных отношениях.

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

Возникает необходимость в этане перераспределения.

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

В 4.3 работе описана информационно-справочная система "Обмен", внедренная в ГУМТО АН (ГУМТО - Главное управление материально-технического обеспечения). В ее функции входит:

1) Формирование базы опросов и предложений.

2) Выдача справок на следующие запросы:

- какие организации предлагают данный ресурс?

- какие организации требуют данный ресурс;

- о спросах и предложениях заданной организации.

3) Актуализация базы опросов и предложений.

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

5) Подбор прямых вариантов обмена для заданного владельца.

6) Подбор многократных вариантов обмена для одного владельца.

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

Два института 1 и 3 составляли прямой вариант обмена, если ^ пР)л <Р1 п ^ ) г 0. Для заданного института выдавались все прямые варианты обмена с информацией:

- об институте, с которил он входил в один вариант обмена;

- о ресурса;:, которые имелись у этого института, и которые были

нужны ему пР;)!

- о ресурсах, которые оыли у него и требовались этому институту (Р(. П Б, ).

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ И ВЫВОДЫ

В диссертационной работе

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

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

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

4. Рассмотрена задача выделения допустимых вариантов обмена после

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

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

6. Для случая ресурсов общего вида введено понятие схемы варианта обмена. Предложен алгоритм поиска для заданного владельца оптимального множества вариантов 'Обмена на множестве заданных схем.

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

3. Разработана информационно-справочная система "Обмен", знедренная в ГУМТО РАН.

Материалы диссертации опубликованы в следующих работах: Багатурова О.С., Турдалиев Н.Ш. Математическое и шформационное обеспечение реализации вариантов в системе [атурального обмена.- М., Институт проблем управления, 1991, 42 с

Багатурова О.С., Кацнельсон М.Б., Турдалиев Н.Ш. 1еханизмы натурального обмена при организации прямых связей и птовой торговле. - В кн.: Методы разработки модульных систем Зработки данных., М., 1990, с. 72-77, тр. ИПУ. . Кацнельссн М.Б., Турдалиев Н.Ш. Исследование методов

перераспределения запасных частей на региональном уровне. - В кн.: Метода разработки модульных систем обработки. данных., М., 1990, С. 69-72, тр. ИПУ.

4. Турдалиев Н.Ш. Поиск и реализация вариантов обмена с заданной структурой для одного владельца. - Научно- техническая конференция "Средства и системы автоматизации управления процессами сельскохозяйственного производства", Тез. докл., Москва, 1991, с. 32-30.

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

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

Подл, к печ. 02.03.92г. Заказ 27 Тирах 100

ВНШШ труда в строительстве