Алгоритмы оптимизации, использующие свойства вложимости полиэдральных множеств тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

о

АКАДЕМИЯ НАУК БЕЛАРУСИ ИНСТИТУТ МАТЕМАТИКИ ■

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

УНГУРЯНУ Валерий Андреевич

АЛГОРИТМЫ ОПТИМИЗАЦИИ, ИСПОЛЬЗУЮЩИЕ СВОЙСТВА ВЛОШМОСТИ ПОЛИЭДРАЛЬНЫХ МНОЖЕСТВ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

МИНСК - 1992

Работа выполнена в Институте математики Акадо!.ш наук Республики Молдова.

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

наук Лоэовану Дмитрий Дмитриевич

Официальные опоненты

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

Ведущее учреждение

Киевский Госуниворситот

10

декабря

.1992 года в

16

Защита состоится часов " 00 " минут на засоданш специализированного совота К 006.019.01 в Институте математики Ali Беларуси по адресу : 22Q0Y2, г. Минск, ул. Сурганова 11, Институт математики АН Беларуси.

О диссертацией мошо ознакомиться в библиотеке Института математики АЛ Беларуси.

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

Н0ЯСра 1992 года.

учений секретарь специализированного сосата, кандидат физи- _

ко-математических наук А.И. Астровский

ОЕЦАЛ XAPAlCTEKICTiatA ДХСЕРШШЗГОЛ РАБОТЫ

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

Данная диссертационная работа посвящена исследованиям по созданию и алгоритмизации некоторых методов дискретной, вогнутой и многокритериальной оптимизации. Основное внимание в работе уделяется моделям задач минимизации кусочно-линейных вогнутых функций на многограннике решений систем линейных неравенств. К таким моделям сводятся многие задачи синтеза коммуникационных сетей, планирования перевозок и размещения пунктов производства, различные задачи стандартизации и унификации и др. Модели минимизации кусочно-линейных вогнутых функций на многограннике имеют и немаловажное теоретическое значение, ибо их исследование тесно связано с исследованием некоторых классов задач теории игр и многокритериальной оптимизации. Метода решения задач кусочно-линейного вогнутого программирования рассматривались в работах Д.А. Супруненко, В.А. Емеличево, М.М. Ковалева, В.Р. Хачатурова, B.C. Михалевича, В.П. Черенина, В.А. Трубина, Хоаиг Туя, В.П. Булатова, К.Л. Хофмана, II.М. Парда-лоса, Да.И. Роузена и др.

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

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

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

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

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

Пгхжпинесная энанилость. Предложенные алгоритмы могут быть применены при решении множества практических задач, таких как: задача синтеза сетей, задача размещения производства, задача линейного программирования с фиксированными доплатами, задача линейного булева программирования, некоторые задачи теории игр, задача оптимальной стандартизации деталей и др. Алгоритмы за-нрох'римшровашш на языке PL/1 на машинах серии ЕС ЭВМ. Проведены тестовые експерименты. Программа решения задачи кусочно-линейного вогнутого программирования сдана в 1'осФАП.

Ццблатит и туобаиия уабот. По теме диссертации опубликовано 12 работ. Основные результаты докладывались на I, II республиканских конференциях молодых ученых (Кишинев, 1986, 1980), на VI11 Всесоюзной конфзренцш по проблемам теоретическом кибернетики (Горький, 1988), на республиканской научно-технической конференции "Применение економико-математических методов и вычислительной техники в планировании и управлении народным хозяйством МССР", (Кишинев, 1988), на VI научной кон-феронщш "Методы математического программирования и программное

обеспечение" (Свердловск, 1989), на международной школе-семинаре "Метода оптимизации и их приложения" (Иркутск, 1989), на се.тагзрз по математической кибернетике в ИМ АН Беларуси, на семинарах по математической кибернетике на факультетах кибернетики Киевского и Молдавского госуниверситетов, на научных семинарах в Институте математики АН Молдовы.

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

СОДЕРЖАНИЕ дасаБРШШШОП РАБОТЫ

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

Основным объектом исследования в работе является задача кусочно-линейного вогнутого программирования, суть которой состоит в выборе точки

х* = argnln <ф(х) : х^Х), где Х={х<=Е" : Ах^Ь, хХ)>; А - матрица размерности m«n; b - вектор-столбец размерности т; <р(х) - кусочно-линейная вогнутая функция.

Главное внимание работе уделяется следующим двум функционалам:

1. <р(х) - 7 mln{cllx+c*\ 1=Т7г7),

где oil=(cfx, с*1,..., с*1) - вектор размерности п; с*1 - скалярная величина, l=T7q, 1=1

2. <р(х) = тШх^Су+а'х+сГт : y^Y"),

где Г={у«Еч : А( y<b', к4 - матрица размерности m, «k; ь'

- вектор-столбец размерности га,; С - матрица размерности n«k: й1, йг - вектор-строки размерностей соответственно п и к. Далее, под задачей кусочно-линейного вогнутого программирования первого (второго) рода будет подразумеваться задача с порш/м (вторым) функционалом.

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

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

В пеувоЯ главе проводится подробный анализ задач кусочно-линейного вогнутого программирования. Указывается на ваааше приложения задач кусочно-линейно го вогнутого программирования. Например: задача синтеза сетей, задача размещения производства, задача линейного программирования с фиксированными доплатами, задача линейного булева программирования и др. Для решения подобного рода задач могут быть использованы комбинаторные метода, которые учитывают их специфику: метод последовательного анализа вариантов, метод последовательных расчетов, аппроксима-ционно-комбинагоршй метод, метод построения последовательности планов, метод динамической декомпозиции в сочетании с направленным перебором, другие методы. Кроме того, при их решении могут бить использованы и метода глобальной вогнутой оптимизации: метод отсекающих плоскостей Хоанг Туя, метод ветвей и границ с различными приближениями целевой функции, метод перечисления с упорядочением экстремальных точек, приближению алгоритмы. Более детально в работе анализируется метод Хоанг Туя. Доказывается лгаишцевость кусочно-линейных вогнутых функций и проводится соответствующая адаптация метода для решения задач кусочно-линейного вогнутого программирования. Следует заметить, что возншшмщю при этом трудности связаны с отсутствием оценки скорости сходимости метода, с пошаговым увеличением количества первенств, определяющих допустимое множество, и с тем, что для первоначальных версий метода найдены примеры, решение которых чреоуог неограниченное количество итераций.

Дтье раскрывается связь задачи кусочно-линейного вогнутого программирования первого рода со следующий задачей билинейного лр01'р',;,щи1>ч|»(1шя (задачей кусочно-линейного вогнутого про-грошир:)шшия Iчорого рода;:

(х\у*) = аг®п1п(:Г(г,у) : х«Х, у*У>, (1)

где 1(х,у)=хтСу+с1х+гу+е;

(7 11 1гОТ Г 12 1г"11,Г Г 1Г.-1 1г-.лТ

с = [с -с ) . (о -с 1] ..... (с 1 -с '] ,

[21 ет-_-.Т г 22 Ег,, Т /■ чг -1 аг

С -С 2) , (с -С 2) ..... (с 4 -С ч]

размерности П"к;

£ 1г,

(1 = I С - вектор-строка размерности п;

матрица

1=1

г 11 и

= [со _со

12 11г -1 1Г)

со ~С0 » * * ' » С0 ~°0 1

21 2 Г, 22 2Г ЧГ-1 ЧГ

с0 -с0 , с0 -с0 с0 4 -с0 ч} - вектор-строка раз-

мерности к;

е = 2 со скалярная величина;

^={У=(У1,У2,...,УР1,УР1+1,...,У1с)т : 1=ТТч, У^о]

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

1

Теорема 1.3.2. Если (х*,у*) является решением задачи (1), то х* является решением задачи кусочно-линейного вогнутого программирования первого рода, причем Г(х*,у*)=<р(х*). Если х* -решение задачи кусочно-линейного вогнутого программирования первого рода, то существует точка для которой пара

(х*,у*) является решением задачи (1), причем <р(х*)=Г(х*,у+).

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

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

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

торого система

- 6 -

Наибольшее значение 11* параметра Л, для ко-

-А% ^ Су+1, Ьти « гу-11+6,

и > О

имеет решение по и при любых значениях у, удовлетворяющих '1

л.

I

(2)

равняется наименьшему значению функционала 1(х,у) в области Х»У, г. е. 1г*=1(х*,у*), а точка для которой система (2)

не имеет решения по и при Л=1Г, у=у*, является одной из искомых точек в задаче (1).

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

Далее исследуются свойства задач о вложимости полиэдральных множеств. Рассматриваются три задачи:

Р1. Установить, является ли система линейных неравенств

{Их<ВХ,+Ь,

(3)

»0

совместной по х при любом А,, удовлетворяющем системе

(4)

I й + I А. ? 0.

??„, Установить, существует ли , для которого каждое из решений системи (4) в то же время является решением системы

1йГ «б ВЛ + Ь.

(5)

РЗг. Среди точек ц, для которых совместна по г система Г их 4 вл, + ь + Ни,

1 х > О, ц > о,

при любом Ч удовлетворяющем (4), найти ту, на которой достигается минимум функционала

Г(Ю = cV,

где D, В, М, G - целочисленные матрицы размерностей tn,*п, т,*к, т,*г, и2*К; Ь, с, g, х, к - целочисленные Еекторы столбцы размерностей ш,,. г, п^, п, к.

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

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

Устанавливается полиномиальная разрешимость Р2.

Теорема 2.3.1. Для системы (3) существует точка xVESJ, обладашая свойством, что какдое из решений системы (4) является решением системы (6) в том и только том случае, когда совместна система

Г Qy G 1,

I У » о,

где

0=

У=

-G

-sl

m

"V, Б>:

Щ'

0 <ВТ)1

0 1)1 ь,

0 D2 • (BT)2

, 1= b2

-GT О «V

-gT D™1 1 \

О = (4ц, dla, .... din), i=T,m,.

Как дальнейшее развитие последнего результат« доканывается юлиномиальная разрешимость задачи о поиске сечения полиэдраль-юго множества, заданного системой линейных нерш.-"?нстн, солпл-[ащого с ого ортогональной проекцией.

Теорема 2.3.3. Для системы (3) существует точка х*«Е£» обладающая тем свойством, что множество неотрицательных решений системы (4) совпадает с ортогональной проекцией множества, определенного системой (3), на положительный ортант Е> векторов Д., в том и только том случав, когда совместна система

| ОУ^Ч,

где

У=

<3-

у>о,

е:

К,

ъ >

-в1

вт ьт

о

о р1

о о

ьг ф

о \

Б 1

4=

о

(В*1 >1

Ь,

о

(Вт)2

ь„

(ВТ)„

I)1 =

Й12..... 1=1 •

В этой же главе излагается второй алгоритм решения задачи

кусочно-линейного вогнутого программирования на базе свойств

влоишости полиэдральных множеств. Вначале детализируется схема

свидения. Доказываются результаты, позволяющие редуцировать

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

ощзделонным подзадачам, имеющим меньшее число параметров.

соли ввости обозначения

Г1 1 ... 1

-А'1' ' О а

и - , к=

Ь1 г в

О

о

1 1

1

), ... , <ет,)т=(0.....О, 1),

'го ыа/а'ремальпня задача о влокимости полиэдральных множеств (Ч;н, ширину . I.г), соответствующая задаче кусочно-линейного ьу]'луто]'о нрогршлмяроианмя первого рода, может быть сформули-

0

В

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

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

Г DtKBA+b-he 1, i (6) I и^о

является совместной по и при любом X, удовлетворяющем

Г £Я - е < О,

(7)

I Л. » 0. Лемма ¿.4.1. Если совместна система

rncBj, 1«(1,г.....ю,

I U > 0,

го задача (6),(7) эквивалентна следующей экстремальной задаче о вложимости полиэдральных множеств:

h ♦ max,

f Ш « Biub°-hen+1,

I <9)

loo,

г ш. - е < о, I X > о,

где 0, т. е. 1-ая координа-

та зафиксирована и равна хх=о.

Лемма g.4.2. Если совместна система

fDu<-Blf led,2.....R), (io)

то задача (6), (?) эквивалентна следующей экстремальной задаче о вложимости полиэдральных множеств:

1г •* max,

Г Du « BX+b-hem 1,

1 u > О, ■

Г - е < О,

1 £ > О,

которая получается из первой, если произвести замену

т. е. а В получается из В исключением 1-го <ж,июпа и

заменой столбцов Bj на В^-В,, З^Ь г - индекс для

которого верно 1<ДI tpr-i >•■ • »Рг>•

- JO -

Лемма 2.4.3. Бели обе системы (8), (10) несовместны, то решение задачи (6),(7) равно меньшему из решений следующих двух задач:

it -* max, f D~u € ШЬ -hent', 1 u > 0,

E\ - e € 0, £ ? 0,

( В, b, X как и в лемме 2.4.2, д~ - получается добавлешем к D справа вектора-столбца -В^ и имеет размерность ш+1); .

h. ■* max,

( D+u <S BX+b°-hent1,

I U 0,

f 1Я - e < 0, 1 i > 0,

(В и я, как в лемме 2.4.1, D+ получается добавлением к D справа вектора-столбца Вх, и имеет размерность ш+1).

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

Алгоритмы запрограммированы на языке и/1. Программы отлажены на машинах серии ЕС ЭВМ (1045, 1046) в операционной системе тм/sp. Программа, реализующая второй метод, сдана в ГосФАП. Проведены тестовые эксперименты. Необходимо отметить, что метод нечувствителен к количеству кусочно-линейных вогнутых составляющих,^ чувствителен к количеству линейных форм в функционале.

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

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

х*=агезп1пл;[Г1 (х),1„ (х).....Г • (х) 1 „ (11)

зс^Х ч

где Г1(х)=<с1,х> - линейные функции; с1, х, х^Е", 1=175, Ч ~ целое положительное число; Х=(хеЬ I Ах«Ь, х^О); А - матрица размерности т«п; Ь - т-мерннй вектор-столбец; все коэффициенты задачи рациональные.

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

х* =аг0п1п А.тСх, (12)

х«ОС ■

при некотором ХеЕ^ Где _ положительный ортант; С - матрица размерности д«п, которая имеет в качестве строк вектора (с1)1, 1=174. По сути дела, первоначальная задача сводится к решению серии задач линейного программирования, так как для определения одного из решений задачи векторной оптимизации требуется найти некоторый набор положительных А.,,..., при котором задача (12) имеет решение.

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

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

В случае использования метода свертки понятно, что решение задачи (11) при соблюдении отношений предпочтения критериев равносильно некоторому решению.задачи (12) с соблюдением условия

q

j/i = U (13)

> 0, l=T7q.

где a1;)>o - некоторые коэффициенты, указывающие количественно на степень предпочтения критерия 1 над критерием J. Суть данных исследований состоит именно в решении задачи (12) при определенных условиях (13). Для случаев, когда отношение предпочтения критериев соответствует некоторому ориентированному дереву, доказывается, что множество фундаментальных решений может быть построено полиномиальным алгоритмом. На основании этого разрабатывается полиномиальный алгоритм решения первоначальной многокритериальной задачи оптимизации, строящий множество оптимальных по Иарето решений. Указывается, что для решения такого типа задач используются свойства задач о вложимости полиэдральных множеств основываясь на том, что задача (12) интерпретируется как задача билинейного программирования.

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

1(хл)=хТСЯ+0тх+г'ГЛ,+8, (14)

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

А1х € t>\

АгЯ « Ьг, (15)

х±. V, = 0у1, 1=Тйй, 3=Т7п,

где С, А1, Ае - числовые матрицы соответственно размерностей m«n, 1ц *m, k^n; d, р, b1, bE - числовые векторы размерностей соответственно ni, n, k,, Kg. Пусть

m п

HIN= 2 mln(älf0}4 £ ralniri,0}+ l т1п(с±.,,0Ьи1п{в,0);

i-1 ¡J= 1 Ii J

m n

MAX= 2 max{d1,0)4 У maxiryOH £ maxic^Obnaxts^O);

f* - оптимальное значение функционала в задаче (14), (15). Утверждение 3.2.1. Имеет место MIN € Г* < МАХ. Задаче (14), (15) «окно поставить в соответствие следующую непрерывную задачу:

минимизировать функционал

т п

Ф(2,л)^тсх.+(1тх+гтя+в+м Т тШх, ,1-х, им Т питл..,1-х..)

1=1 1 1 ¿=1 3 3

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

" А1Х < Ь1, АгХ < Ьг, Ех. < о, Е\. е, 1х, А. > О,

где М - достаточно большое целое число (М > Е _ точ_

ность решения последней задачи; Б, Е - единичные матрицы соответственно размерностей п»п, т*ш; е, е - векторы соответственно размерностей п, т, состоящие из единиц.

Последняя функционала

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

задача сводится к минимизации билинейного

С ¿Ш] ■¿НЕ О

[ [

[йт-Ыет1-Мет]

+ 84 (ВНП)М

А1 О Е О О Е

Л2 О

5 8

X, у, х,

2 р'1

е

У в .

X ГЬ21

и е в

(16)

(17)

ц » С.

Теорема 3.2.1. Пусть задача (14), (15) тлеет решение: х, оптимальнее решение задачи (14), (16); х*, у*, А-*, |1* -

У,.,

оптимально« рошонио задачи (16), (17). Пусть X

л»

Л(1 11 ХС

и - множества оптимальных решений в задачах соответственно

с л

(17). Тогда Хс1=ХоР лл=ла, Г(х\я*) --

(14), (!Ь) и (16),

Если воспользоваться теперь теоремой 2.4.1, то последней

еядяче соответствует окстромольная задача о влокимпоти поли9-

др;и:ь!1их множеств:

. *

найти наибольшее значение параметра 1г, при котором система

Г(А')Т Ь' о |ц ^ Г О 2МЕ | + [ Л-Ме ] I О О Е I. 2МЕ О -Не ]

[(Ь1)т ет ет]и « [гт-Ыет1-ЫетШ - И+б+(п+т)М,

иго

является совместной по и при любых А., ц, удовлетворяющих системе

А2 О 11X1

оЕ °е ]Н * Ц

к, Ц > 0.

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

Основными результатами являются:

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

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

3. Доказательство Ш>-трудности задачи о проверке вложимости к-мерного единичного куба в ортогональную проекции выпуклого многогранного множества, заданного системой линейных неравенств.

4. Разработка и обоснование алгоритмов решения задач о

вложшости полиэдральных множеств. Построение на их основе алгоритмов решения задач кусочно-линейного вогнутого программирования первого рода. Реализация алгоритмов в виде программ на языке РЬ/1. Проведение тестовых экспериментов на машинах серии ЕС ЭВМ (ЕС-1045, ЕС-1046) в операционной системе УМ/8Р.

5. Исследование и решение задачи линейной многокритериальной оптимизации с отношением предпочтения критериев, определенным линейными неравенствами.

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Унгуряну В.А. Задача о вложимости выпуклых многограшшх множеств и ее приложение в решении и исследовании задач синтеза сетей//Применеше экономико-математических мето-

. дов и вычислительной техники в планировании и управлении народным хозяйством МССР: Тезисы докладов республиканской научно-технической конференции.-Кишинев, 1988,- С. 143.

2. Лозовану Д.Д., Унгуряну В.А. Задачи о совместности сиртем линейных неравенств с правыми частями, зависящими от параметров, и алгоритмы их решениях/Проблемы теоретической кибернетики: Тезисы докладов VIII Всесоюзной конференции, В 2-х частях.-Горький, 1988.- 'Г. 2.- С. 19-20.

3. Лозовану Д.Д., Унгуряну В.А. Об одном алгоритме для задачи кусочно-линейного вогнутого программирования/Л1звесткя АН МССР. Серия физ.-техн. и мат.-1988.- * 3.~ С. 14-20.

4. Унгуряну В.А. кг- трудность задачи проверки вложшости к~ мерного единичного куба в ортогональную проекцию выпуклого многогранного множестиа//Математическсе моделирование и оптимизация.-Кишинев: Штиинца, 1989.- С. 120-128.- Доп. В ВИНИТИ 12.11.198Т, .«7986-887.

5. Лозовану Д.Д., Унгуряну В.А. Алгоритм проверки вложимости к-мерного единичного куба в ортогональную проекции много-гршшого множества, заданного системой линейных: неравенств //Математическое моделирование и оптимизация.~ Кишинйв: Штиинца, 1989.- 0. 67-78.

6. Лозовану Д.Д., Унгуряну В.А. Об использовании билинейного программирования в линейной векторной онтимиэацни//Мето-ди математического программирования и программное обеспечение :'('езисы докладов VI научной конференции.-Свердловск, 1989.- С. 143-144.

7. Лооооану Д.Д., Унгуряну В.А. К вопросу о вложимости вы-

пуклих шогогратшх множеств, заданных системами линейных нераво(;ств//Кибернетика.-1989.-.й 1.- С. 104-107.

8. Гейндрик К.В., Унгуряну В.А. Системы линейных неравенств с правыми частями, зависящими от параметров, и некоторый задачи оптимизации//Методы оптимизации и их приложения: Тезисы докладов международной школы-семинара.-Иркутск, 1989.- С. 53-54.

9. Унгуряну В.А. Задачи о влояошости полиэдральных множеств и параметрическое линейное программирование//Молодежь и совремеиная.наука. Физико-математические науки: Тезисы докладов II республиканской конференции' молодых исследователей,- Кишинев, 1989.- С. 36.

10. Унгуряну В.А. Программа решения задачи кусочно-линейного вогнутого программирования//®®, бюллетень ВКТИЦ. Алгоритмы И программы.-1990.-Уг 11,- С. 21.

11. Унгуряну В.А. Модификация алгоритма решения задачи кусоч-но-лгаюйного вогнутого программирования//Известия Академии наук ССР Молдова. Математика.-1991.- Л 1.- С. 27-33.

12. Унгуряну В.А. О решении задачи линейной векторной оптимизации с отношением предпочтения критериев.- Деп. в ВИНИТИ 05.02.92, Ш9-В92.- 14 с.