Исследование некоторых локальных алгоритмов решения квазиблочных задач дискретного программирования тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Академия наук СССР ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

^ольнь.й

ГІ-..ПЛЯР

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

ЩЕРБИНА Олег Александрович

ИМЕНОВАНИЕ НЕКОТОРЫХ ЛОКАЛЬНЫХ АЛГОРИТМОВ РЕШЕНИЯ КБАЗИБЛОЧНЫХ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ

01.01.09. - математическая кибернетика

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

Москва 1979

Работа выполнена в Вычислительном центре АН СССР.

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

доцент В.Б.КУДРЯВЦЕВ

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

профессор В.А.ЕМЕ1ИЧЕВ кандидат физико-математических наук, доцент Ю.Н.ЧЕРЕИНЫХ

Ведущая организация - Саратовский государственный университет

имени Н.Г.Чернышевского.

Защита состоится "_"_ 1979 г. в _час.__мин.

на заседании специализированного совета Д 002.32.02 по защите диссертаций на соискание ученой степени доктора физико-математических наук при Вычислительном центре АН СССР (ІІ7333, г.Москва, ул. Вавилова, 40).

С диссертацией можно ознакомиться в библиотеке МИ АН СССР - г. Москва, ул. Вавилова, 42,

Автореферат разослан "_"_1979 г.

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

кандидат технических наук

ІЇМм^/А-И.зенкин у

Ш1

1ССР

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

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

Метод декомпозиции впервые был использован для решения задач смешанного целочисленного программирования в [I] .впоследствие этот метод подвергся модификации в работе [2} Другие алгоритмы декомпозиции для решения задач дискретного программирования специальной структуры были предложены в работах [3 - 7]

Среди задач дискретного программирования, возникающих на практике, достаточно много задач с разреженными матрицами условий, которые поддаются разбиению на слабо связанные блоки (или, другими словами, имеют квазиблочную структуру). Для решения -подобных задач может быть использован локальный алгоритм [б - 10] имеющий декомпозиционный характер. Первоначально локальные алгоритмы были введены и исследованы в дискретном анализе для построения минимальных нормальных форм алгебры логики [83 Впервые применение локального алгоритма к задачам булевского линейного программирования с целыми коэффициентами дано в ([9] Локальный алгоритм для решения квазиблочных задач дискретного программирования с дополнительными ограничениями обобщен в [10]. Мажорантный локальный алгоритм для решения задач целочисленного программирования специального вида найден в [п] Алгоритм декомпозиции квазиблочной задачи линейного программирования получен в .

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

В диссертации рассматриваются следующие задачи. Исследуется локальный алгоритм в сочетании с алгоритмом дискретного

программирования, имеющим оценку эффективности £l3j для

решения к —кваэиблочной задачи Z дискретного программирования с tb булевскими переменными. Локальный алгоритм сводит решение задачи к решению к пакетов задач

{-, {21* J£ • Задачи каждого пакета моя-

но упорядочить (структуризовать) и решать их согласно этому упорядочению, используя при решении задач информацию, полученную в процессе решения предшествующих задач. Возникают следующие задачи:

1. Задача структурной оптимизации локального алгоритма

2. Сравнить У(л) и Ео^(п-,к) - оценку эффективности ло-каліного алгоритма ОІ.у> __

.где -А - матрица условий линейной задачи ^ lpl*>j D W

4. Оценить (Гчд | , где гч д - множество всех разбиений

матрицы А на ІС слабо связанных блоков;

5. Оценить

- число слабо связанных блоков, на которые

можно разбить А. ;

6. Найти к*

такие, что

(нахождение оптимального разбиения).

ЦЕЛЬЮ РАБОТЫ является:

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

2. Исследование эффективности локальных алгоритмов на классе квазиблочных задач дискретного программирования.

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

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

НАУЧНАЯ НОВИЗНА. В диссертационной работе впервые исследована эффективность локального алгоритма на классе квазиблочных задач дискретного программирования, причем выполнено теоретическое и экспериментальное исследование. В работе получена оценка эффективности постоптимального анализа, ранее неизвестная. Получен ряд новых результатов для квазиблочных матриц. Выявлена связь между локальным алгоритмом и постоптимальным анализом и с учетом этой связи проанализированы возможности структурной оптимизации локального алгоритма. Реализованы на ЭВМ 3 модификации локального алгоритма.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ. Результаты, полученные в диссертационной работе, могут быть использованы при решении возникавших на практике квазиблочных задач дискретного программирования большой размерности, в частности, для решения задач оптимального резервирования гостиничных номеров, задач оптимального управления системой туризма, задач оптимальной госпитализации больных и т.п.

АПРОБАЦИЯ РАБОТЫ. Основные результаты диссертационной работы докладывались на П Всесоюзной конференции по исследованив опера-

ций (г.Петрозаводск, 1976 г.), на заседании семинара "Теория оптимальных решений" под руководством академика АН УССР В.С.Ми-халевича (г.Киев, 1976 г.). не заседании семинара "Применение математических методов в экономических исследованиях и планировании" под руководством члена-корреспондента АН УССР А.А.Бакаева и доктора физ.-мат. наук Ь.З.Шора (г.Киев, 1977 г.), на 1У, У, УБ научных конференциях профессорско-преподавательского состава Симферопольского госуниверситета (г.Симферополь, 1975, 1716, 1978 гг.) на заседании УШ цикла семинаров по дискретной математике под руководством профессора А.А.Зыкова (г.Одесса, 1778 г.), на П школе-семинаре "Проблемы автоматизации проектирования и управления качеством продукции" (г.СимФерополь, 1978 г.), на семинаре лаборатории проблем распознавания ВЦ АН СССР (г.Москва, 1978 г.), на семинаре по многозначным логикам мехмата МГУ 1,г.Москва, 1978 г.), а также на заседаниях семинара кафедры прикладной математики Симферопольского госуниверситета (1974 - 1978 гг.).

ПУБЛИКАЦИИ. По материалам диссертации опубликовано 5 печатных

ОБЪЕМ РАБОТЫ. Диссертация состоит из введения, трех глав, заключения, библиографии (87 наименований), приложения и содержит 127 страниц машинописного текста.

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

Первая глава посвящена эффективной реализации локального алгоритма (X . В §1 вводятся основные понятия и определения.

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

Р&ссматривается задача дискретного программирования следующего вида

Н = СХ —* пыха: (I)

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

Ая^ё, (2)

Ху =0,4, У = 4^1, (3)

где с =

Определение I. Матрица А = /1£Ц/Л»п»пназывзется к -квазиблочной или состоящей из к слабо связанных блоков (ССБ) (см.рис.1), если множества индексов можно

разбить на к подмножеств ¿¿ъ и соответственно, так

что

СО

и^Л ¿¿^ = 0, г** г^ (5)

Л £->"1, (б)

Введем обозначения: _

1) = 5г/1

2) 5« = к, = 0

3) Л* = | , 1

4) ,ас,-,^ Б }, л* < • • • <¿4

5) = иЦ"... и

6) - фиксированное значение

Будем называть разбиение матрицы А на к ССБ невырожденным, если {1 = 4., к )

). В дальнейшем рассматриваются лишь невырожденные разбиения.

Рис.1. Квазиблочная матрица -А (возможно, после перестановки строк и столбцов; вне заштрихованных блоков находятся одни нули).

Локальный алгоритм (ЛА) QO решения задачи дискретного программирования (ДП) (1)-(3) состоит в следующем: п.О. Положить 1 = 0 • Ф перейти к

П.1.

п.Í. Если t-^k t перейти к п.2, в противном случае для каждого вектора ЗС{^,1} решить задачу ДП: Найти вектор Xv* такой, что

в

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

Y.aLjXj i¿ ->_(8)

Xs.,XswXw£ {ОД}, C9)

X^/X-^t. CIO)

_ Обозначим задачу (7)-(10) через ^ Если для данного

^О^^задача разрешима, отнести вектор в

множество и запомнить найденный вектор ■

Если для всех решена, вычеркнуть г и

; увеличить_Т на единицу и перейти к началу п.1.

Если же для. всех Х^ не имеет решения, перейти

к п.З.

п.2.Конец вычислений. Оптимальным решением задачи (1)-(3) является вектор "X. = , максимальное значение целевой функции (Ц§) равно п.З.Конец вычислений. Решения задачи (1)-(3) не существует.

Задачи внутри блоков можно решать либо с помощью пол-

ного перебора (ПП), либо, с помощью одного из алгоритмов ДП, в качестве которого был взят алгоритм неявного перебора (НП). ЛА в сочетании с ПП обозначим ос* ДА в сочетании с НП - ОС^ • При использовании НП предполагается, что элементы матрицы удовлетворяют условию [13]

Алгоритм НП состоит в порождении последовательности частичных решений (ЧР) Б и зондировании их с помощью следующих 3-х тестов:

Тест I. ЧР 5 прозондировано, если

1,де 2 - рекорд.

Тест 2. ЧР 3 прозондировано, если_

</е5 _ -г'«*4* Тогда решение ЗС^ новый

рекор.

Тест 3. ЧР £ прозондировано, если ^¿'.(^¿<0 и

у? - »¿МО, а у) < О,

где

В §2 описывается важный оасс прикладных квазиблочных задач ДП - класс задам оптимального резервирования (ОР) ресурсов, распределенных во времени £14, 15^ частное задачи ОР: задача оптимального предварительного резервирования гостиничных номеров, задача оптимального распределения ресурсов на турбазах, задача оптимального выбора научно-исследовательских проектов, задача оптимального планирования электроснабжения при азарии, задача оптимальной госпитализации больных и т.д. Задача ОР является задачей ДП (1)-{3) с матрицей специального вида (аналог матрицы Петри):

Со - в противном случае. Смысл величин: у' = ^ (ъ - индекс заявки на резервирование^-единиц ресурса на срок с по ^ ¿ — iitn - период

времени ( нъ] - дискретный интервал планирования); С^ прибыль от принятия в обслуживание заявки ^ (заявка ^ принимается в обслуживание при СС^ ж ^ ); - наличное

количество ресурса в период

В §3 показывается, что 1А частная реализация мето-

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

- II -

( Х^ ) и по вектору-перемичке .Xg^ t

В §4 вскрывается связь ДА 01*. с постоптимальным анализом (ПА) в ДП. Действительно, нетрудно доказать от противного, что для каждого i Б оптимальном решении задачи (7)-(10)

является оптимальным решением задачи с ограничениями (8)-(Ю) и Ц$ вида

для некоторого г Таким образом, вместо решения задач

(7)-(10) можно решать задачи (7*)-(I0) для всех Хе Y.

ТГ /V \ I

а затем построить ' Задачи С7 (обозначим

эти задачи ZtOÎst-^* 1-Х s«,*** ^ для Различных значений и Xs* отличаются лишь вектором правых частей

При решении пакета IXgJ^^ задач 1П вида

z = ca: —f/ял« (13)

(f^ ) при ограничениях

Ах±ё<€1 см)

можно не решать с помощь® НП каддую из Lj задач (13)-(15) в отдельности, а построить вспомогательную задачу анало-

гичную но с другими ограничениями вместо (14):

СЮ

£ не)

где fi; =trtu% V/ £ £

Далее решается задача м с помощью НП и запоминаются лишь те 4P S » которые были прозондированы с помощью описанного

выше теста 3» Эти ЧР образуют множество / , , Задачи из пакета решаются не полностью, а лишь для ЧР 5 ^^^

Запоминание ЧР £ требует большого объема памяти и поэтому эта процедура была модифицирована: вначале зондируются ЧР 5 в задаче Р как только некоторое ЧР 5 прозондировано с помощью теста переходим к зондированию этого ЧР во всех

задачах пакета } Прозондировав ЧР 5 во всех задачах

пакета, возвращаемся к задаче Р и т.д.

В §5 показано, как можно эффективно использовать связь ЛА с ПА при реализации ЛА (К на ЭВМ. Показано, что в случае многомерной задачи о ранце ( ССс^' у О;^ ^ ^ О ) схема предшествования задач ¿^ (-Х^.,^) имеет ВИА> как пока~

зано на рис.2 для случая ¡¿^ *\ — 1 • Здесь задачи,

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

Е^ШН)

1г(а\о) гмон) Црш)

V •—■ -— —""Г 1 ' ^^ I

ЕМоЮ) ¿г(ОФ) ыоот

• - 1 __••— - —-

Е^(ООШ)

Рис.2. Структуризация пакета задач ^ „ ( ~%.г }

1С I 7 1С . -Г* '

при I С>1-<,11 — /С, I 1-1.

Выбирая различные схемы предшествования, можно оптимизировать структуру ЛА (УС .

В работе реализована на ЭВМ более простая схема предпество-вания с 2-мя уровнями: на первом уровне в качестве взята

задача в которой= (1 .....на _

втором уровне в качестве задач-потомков взяты задачи ¿ь^О^^О^ ) для всех остальных (при £ = ^ в качестве £**' взята задача 1Гг Х$гЛ+1 = (IЛ.....I). на втором

уровне - все остальные задачи).

Рассмотрен частный случай, когда наиболее просто реализуется процедура ПА, при Щ.х\:=1> • В этом случае каждая из за-

дач ¿т превращается в пакет задач о ранце. Используя алгоритм динамического программирования, можно решать лишь одну задачу из пакета (с максимальным вектором $ ), решения всех остальных задач будут содержаться в той же таблице. На ЭВМ реализованы 3 варианта ЛА: I) ЛА в сочетании с НП -

2) ЛА в сочетании с постоптимальным анализом -

3) ЛА в сочетании с динамическим программированием в случае

Ш'1

В главе П эффективность ЛА (УС исследуется теоретически и с помощью машинного эксперимента. В качестве оценки эффективности (ОЭ) ЛА 0~С- берется величина

= 2-2 УСЫ

(іб)

где Пол =Кт,1=О а - 03 алгоритма ДП, с

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

случае ГШ в слУчае ^ ПРИ выполнении условия (II), согласно результатам ¡13]

Пх

Представляет интерес вопрос, что эффективнее для решения квазиг-

блочных задач ДП, ЛА в сочетании с алгоритмом ДП или этот алгоритм сам по себе. Оказывается, что в случае невыронденного разбиения матрицы А на ССБ ЛА ОС^ всегда эффективнее ПП, т.е.

Ер^^ (п, к) ^ £ ^ а ^^ эффективнее НП при выполнении

УСЛОВИЯ + 4 ^ (у г)

Далее, в §2, решается вопрос оценки эффективности ПА при решении с помощью НП пакета задач (13)-(15), а также вопрос оценки эффективности ЛА СРС^

Совершенно естественно возникает задача нахождения экстремальных и среднего значений 03 ЛЛ, которая решена в §3 для ЛА Пусть Р £ - класс всех к -квазиблочных матриц с И, столбцами, невырожденными ССБ и фиксированным числом строк. Тогда справедливы:

Теорема I.

Теорема 2.

((Ік-к)^3^*1, К

гДе И - остаток от деления П-к+ { на к Теорема 3.

Следствие 3.1.

- 2л~г

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

выражения весьма громоздки уже при к =3. Поэтому найдена лишь асимптотическая формула: Теорема 4.

Ё^Т) ~$-(гк-г)!и-Г10"")

При П —*• СЖЭ к

В §4 приведены результаты машинного эксперимента с ЛА (УС Были реализованы на ФОРТРАН 1У для ЭВЧ ЕС-К22 алгоритмы (HszJ

и НП С помощью специальной подпрограммы по известным параметрам /П,П,к, генерировались задачи ОР и срав-

нивается время счета задач ОР с помощью ЛА 01, ^ ЛА 01, г и НП. Т.к. время счета приведенных в таблице 1 задач ОР с помощью НП оказалось больше 30 минут, то в таблице оно не приводится.Для простоты размеры блоков брались одинаковыми.

Таблица I (ЭВМ ЕС-1022).

Л*.

№ т п к I 2 з 4

Время счета (сек.)

01х 01, аи 01, (К* ои т*.

I 20 50 4 5,3 5,0 6,3 6,7 10,0 10,7 30,7 34,7

2 20 50 6 1,3 1.7 1.7 1,7 2,3 2,7 6,3 5,7

3 50 80 6- 6,0 5,7 13,7 12,0 32,0 31,3 38,0 38,7

4 50 80 Ю 2,0 2,0 3,3 3,0 6.0 6,7 12,7 10,3

5 90 120 10 8,7 7,3 16,0 15,0 31,0 30,3 58,7 55,0

6 90 120 14 4,3 3,7 9,7 8.7 12,0 II.з 28,3 23,3

7 130 160 13 14,0 13,3 21,3 20,7 48,7 43,7 118,3 113,0

8 130 160 19 6,0 5,0 8,3 8,0 20,7 19,0 43,3 32,7

5 150 180 15 14,7 13,3 32,3 27,7 50,7 47,3 100,0 107,0

10 150 180 19 10,0 9,0 14,0 13,3 27,3 25,3 55,0 47,0

II 170 200 16 17,0 16,0 38,0 31,7 72,3 68,7 143,7 150,7

12 170 200 18 И,7 и,з 25,3 23,3 44,0 42,7 73,0 75,0

Кроме того, приведены данные о времени счета ЛА в случае | ¿¿-е/ = £ Результаты машинного эксперимента свидетельствуют о существенном уменьшении времени счета за счет применения ЛА.

В главе Ш получен ряд результатов для квазиблочных матриц. Пусть А.**.»ц,- к -квазиблочная матрица и & число элементов внутри блоков А. Тогда справедливы Теорема 5.

¡(т-к+гхл-гк+4)+3к~£, к >2,

шляс!) =1 ,

I т,(п-1)} к = 2

Теорема 6. тля 2) + .

Отсюда непосредственно следуют теоремы 7 и 8:

Теорема 7. Лля того, чтобы мттрицв рп.« с количеством л

нулевых элементов была к -квазиблочной, необходимо, чтобы

~ ¡(k-ZMZ>n

Теорема 8. Если i^V«*,* - число всех к -квазиблочных матриц A-mjx с элементами 0-1, то

LZ^&JVl'í ±СЛЪ\

где Д, -i.

В §2 рассматривается вопрос оценки максимального числа ССБ,

на которые можно разбить данную матрицу jQ. Показывается,

t

что эта Задача эквивалентна задаче раскраски гиперграфа. Пусть

t £ - соответственно максимальное и минимальное число строк матрицы А. связанных с одной строкой (строки ¿j и Аг связаны, если CU+J¿O ): ^ ~ минимальное число ненулевых элементов в столбце матрицы

где ¿і и к СЛ.) максимальное число ССБ, на которые

можно разбить А Теорема Ю.

з , Ік ± і+і, І+Х + І

ЗЩ±]-2>> і

где К - остаток от деления на ¿^і

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

В §4 дается оценка числа разбиений матрицы инциденций задачи ОР на к ССБ:

Теорема II. Если І_і = ІпЛсс и ~ число

разбиений матрицы инциденций задачи ОР на к ССБ, число

всех разбиений матрицы инциденций задачи ОР на ССБ, то

Ст.-к(і.-4>-і - С«-* „

Ст-ніи-іУі - А/, £

В §5 рассматривается задача оптимального разбиения на ССБ матрицы инциденций задачи ОР, причем в качестве критерия эффективности взята величина (16), которая минимизируется. Строится

сеть _/"Z следующим образом: каждой строке с матрицы ставится в соответствие вершина Vi сети п причем формально вводится еще вершина Va в J1 . Вершины Vù и )

соединяются дугой 2-CJ в сети £1 если строки L и j могут быть концами соседних блоков (чтобы не нарушалось требование (6) слабой СВЯЗНОСТИ блоков), причем вершина Те соединяется с вершиной ~Vg если строка £. выбирается концом первого блока. Дуге ¿¿J приписывается длина

» если веРшины с и j соединены дугой,

Ога - в противном случае,

где tl±(L,J)- число столбцов, начинающихся выше строки С и конец которых лежит между L+4. и J - число столб-

цов, начало которых лежит между строками L■*■ и j а конец -ниже J число столоцов, целиком лежащих меащу строками

C+i и J 03 для алгоритма ДП, с помощью которого

предполагается решать задачи Таким образом, каждому раз-

биению

i&JL матрицы на ССБ соответствует некоторый путь в сети £1 : "{Vo,T-tV,---, "Vês = т.е. задача оптимального разбиения матрицы инциденций задачи 0Р на ССБ эквивалентна задаче отыскания кратчайшего пути из ~Vo в V**. в сети IJ последняя задача решается с помощью алгоритма динамического программирования, реализованного на ЭВМ.

ЗАКЛЮЧЕНИЕ

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

фективнее, чем алгоритм дискретного программирования сам по себе.

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

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

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

5. Локальный алгоритм реализован на ЭВМ в 3-х вариантах (I вариант - локальный алгоритм в сочетании с неявным перебором для решения задач оптимального резервирования; П вариант - локальный алгоритм' в сочетании с неявным перебором и постоптимальным анализом для решения тех же задач; Ш вариант - локальный алгоритм в сочетании с алгоритмом динамического программирования для решения квазиблочных задач дискретного программирования, у которых каздый блок содержит одно ограничение) и произведен сравнительный машинный эксперимент с целью исследования реальных вычислительных возможностей локального алгоритма.

6. Исследован ряд свойств квазиблочных матриц: получены максимальное и минимальное число элементов внутри блоков к -ква-

зибдочной матрицы, необходимое условие к -квазиблочности матрицы, оценка числа всех -квазиблочных матриц с элементами 0-1, оценка максимального числа блоков, на которые можно разбить данную матрицу; оценка числа разбиений на слабо связанные блоки заданной матрицы; решена задача оптимального разбиения матрицы инциденций зада«и оптимального резервирования на слабо связанные блоки и реализован соответствующий алгоритм на ЭБМ.

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

ЛИТЕРАТУРА.

I. Benders J. F. Partitioning procedures for solving mixed

variables programming problems. Numerische Mathematik, 1962, N3.

2- Hrouda J. Modifikovany Bendersuv algorithms. Ekonomicko-

matematicky obzor, 1975, 11, N4. З.Бахтин A.E., Колоколов A.A. декомпозиционный метод решения целочисленных производственно-транспортных задач. 3 сб. "Вопросы анализа сложных систем", Новосибирск, 1974. Бахтин А.Е., Горстко А.Б. О решении нелинейных экстремальных задач с линейными ограничениями специального вида. В сб. "Математическое программирование", М., 1966. 5. Giulianelli S., Lucertini М. A decomposition technique in

integer linear programming. Lecture Botes in Computer Science, 1976, 41.

6. Иоффе В.M. и др. Система моделей и методы оптимизации производства пластмасс. Экономика и математические методы, 1970, 6, Н.

7. Mine H. et al. An algorithm for solving the weighted distribution linear program with 0-1 variables. Mémoires of Faculty of Engineering. Kyoto University, 1970, 32, N1.

8. Журавлев Ю.И. Локальные алгоритмы вычисления информации. 1,П. Кибернетика. 1965, !.. И; 1966 , 2, »2.

9. Журавлев Ю.И., Финкелыптейн Ю.Ю. Локальные алгоритмы для задач линейного целочисленного программирования. В сб. "Проблемы кибернетики", M., 1965, вып.14.

Ю.$инкельштейн Ю.Ю. Об одном классе задач дискретного программирования. Экономика и математические методы, 1968, £4.

II . Guba V. Sin maximaler lokaler Algorithmus fur Aufgaben der

ganzzahligen linearen Optimierung. Elektronische Informationsverarbeitung und Kybernetik, 1975, 11, N10-12.

12.Верина Л.S. О декомпозиции задач линейного программирования кваэиблочной структуры. Известия АН БССР. Серия фиэ.-мат. наук, 1975, »6.

13.Гришухин В.П. Оценка слояности алгоритма Балаша. В сб."Математические методы решения экономических задач". М., "Наука",

1972, f

14.Щербина O.A. О задаче оптимизации предварительного резервирования гостиничных номеров. В сб. "Исследование операций и АСУ", Киев, 1976, вып.7.

15.Щербина O.A. Математическая модель оптимального предварительного резервирования гостиничных номеров. "Сборник работ по математической кибернетике", М., ВЦ АН СССР, 1976, вып.1.

16.Щербина O.A. Оптимальное разбиение на блоки одной квазиблочной задачи булевого программирования. "Сборник работ по математической кибернетике", М., ВЦ АН СССР, 1976, вып.1.

17.Щербина O.A. Об одной задаче дискретного программирования. В сб. "Теория оптимальных решений", Киев, ИК АН УССР, 1978.

18.Щербина O.A. О квазиблочных экономико-математических моделях. В сб. "Экономико-математическое моделирование развития отраслей и транспорта", Киев, ИК АН УССР, 1978.

Бесплатно

-9*8»

Академия наук СССР Вычислительный центр

БЧ 0I6I8 Подписано к печати 3.05.1979 г. Объем I уч.-изд.лист. Тираж 100 экз. Зан. № 125 Бесплатно

Тип.гр. НПО "Эфирмасло" г. Симферополь, ул. Киевская 150.