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

АКАДЕМИЯ НАУК АЗЕРБАЙДЖАНА ИНСТИТУТ КИБЕРНЕТИКИ

На правах рукописи РТБ ОД УДК 519.854

МАРДАНОВ САХИБ САХРАБ оглы

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

01.01.09—матемэтическая кибернетика

АВТОРЕФЕРАТ

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

БАКУ—

1994

Работа выполнена в Институте кибернетики АН Азербайджана.

Научный руководитель:

—д. т. н-, проф. Бабаев Дж. А.

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

—д. ф.-м. н., ст. н. с. Махмудов 3. Н. (ИК АН Азербайджана).

—к. ф.-м. н., доц. Велиев Г. П

(Азерб. Технический Университет).

Ведущая организация:

—БГУ им. М. Расулзаде (факультет прикладной математики и кибернетики).

Защита диссертации состоится

•ЛУ" КМКЯ 19К г.

в 1400 час. на заседании Специализированного сонета Н.004.21.02 по присуждению ученой степени кандидата физико-математических наук пр,!#/ Институте кибернетики АН Азербайджана по адресу:

370141, г. Баку, ул. Ф. Агаева, квартал 553, дом 9-

Отзывы на автореферат просим выслать в двух экземплярах с заверенными подписями.

С диссертацией можно ознакомиться в библиотеке Института кибернетики АН Азербайджанской Республики.

Автореферат разо;лан „ ОЪ ■ ммя 1994 г.

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

БАГИРОВ А. М.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОМ Актупльность^теш. Известно, что задачи дискретного Программирования принадлокить к классу универсальных переборных задач. Это означает,-что с увеличением числа ограничений и переменных сложность решения задачи растет экспоненциально. Поэтому при потребности широких научных н практических приложений задач декретного программирования необходимо разрабо-агь метода уменьшающие размерность поставленных задач и параллельные алгоритм для их решения.

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

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

Научная_швизна проввдошшх в диссертации исследований и по лученных результатов, выносимых автором на защиту,состоит .в'следующем;

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

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

_Ш19(®®э„ШЗо®ения_исследоващ1й, " При выполнении, работы ис-. пользованы теория и метода дискретного программирования, теория сложности решения комбинаторных задач, теория параллельных систем и для статистической оценки эффективности разработанных алгоритмов широко, применены вычислительные экспер^шен ты.

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

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

диссертации представляют несомпений теоретический и практический интерес.

АЩ?°бация_ЕаОдту. Результаты диссертационной работы докладывались на 2 Всесоюзных конференциях ( 1989, г. Кострома, 1990, г.Баку ),на Республиканской конференции аспирантов (1991,г.Баку), на семинарах по исследованию операций в ИК АН Азербайджана.

Публинащга. Основные результаты диссертгл-утм опубликована в работах [1]-[6]. Отдельные результаты содержатся в отчетах НИР, выполнешшх в МК АН Азербайджана.

СгЕУК1УЕа_и_оДъем_51!ссортации. Диссертационная работа состоит из введения, четырех глав разбитых на 12 параграфов, заключение, списка литературы и приложения. Работа изложена на 112 страницах машинописного текста.. Библиография бодершт 61 нимлюваний.

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

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

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

В .51.1 приведен краткий обзор по методам агрегации дися&анто-вых уравнений. Под термином диофантовых уравнений здесь тлеется в виду линейные алгебраические уравнения с целочисленными коа'> • фицаонташ, правыми частями и целыми -.¡апт^^ьш.-'м ■

В §1.2 исследована проблема послодопяю.' ыюй агрегации дио-фантовых уравнений '

п

^ а^х^Ь., (1)

Х^О. Ц9ЛЫ0, п (2)

(где а.}, Ъ1 - целые). При агрегации задачи (1)-(2) имеется в виду, что построится одно уравнение

п

1 . (3)

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

/т

аг I аи*1» 1=1 ■

Я1 '

ь-ЗМ,. ■ .

Доказано

Теорема 1.1.1. Пусть целые произвольного знака, Ь«=•>',? и Ь,^Ь2>0. Тогда система (1),(2) и уравнение (3) являются эквивалентными при условиях:

и tг>0, целые и взшшо-простые;

где

lV,=max ^ кд., íí =max У

^ . J ■

J?«{/| vj=b2Qlj-bla3j>0 | t>j-b3a1 j-b1a2j<0 j.

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

В §1.3 исследована проблема ■ одновременной агрегации системы диофантовых уравнений'(1),(2), для т>2, в одно эквивалентное уравнение (3).Здесь, для.этой цели использована связь между проблемой агрегации и единственности решений диофантовых уравнений и доказаны'следующие теоремы. ■ '

1.. Если ■-•..';.:.'■■''. v .-v;

< i» . ■■ ■■ . а,- 7 П ( Ь, +1), при t-r+f,m,

' ° l-k* I J ■■'■■• ■ •

• , ! ■ • .... то уравнение (3) имеет такое же множество решений, как и система

уравений (1),(2).

Если

ОФ,<Ь2<...<ЬП,

■ i ', , п

а,* ) Л~1) П ( Ъ, +1), 1*1,« «

. '•- - Jrh+t 3 ■

то уравнение (Ь.З). имеет такое же множество решений, как и система ураввний (Ь.1),,;ь.2). Теорема_1.3.3. Если . '

скь.<ъ„<...<ъ

I с. Ш

и уравнение (3) имеет единственное решение, то Теорема 1.3.2 дает тименывое возможное значения максимального коэффициента.

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

Вбросам сокращения числа неизгостных посвяшоны главы 2 и 3. Глава 2 состсит из трех йарсл-рафов.

В §2.1 приведены краткий обзор о состояние вопроса и рассматривается задача

и

£ суг^—>тах • (4)

п

£ • . (5)

х^О,,целое, л=;7п .' (6)

где а.у су>0 и Ь>0.

Для задачи (4)-(6) доказана

ХШейШЛЛЛ • Л"11 есш [аг/а1 то сУДвст^Ует опти-

мальное решение задачи (4)-(6) в котором хг=0. Здесь 1д1-целая часть вещественного числа д.

Из этой теоремы непосредственно вытекает следующее

Следствие: Если в задаче (4)-С5) для некоторой пари индексов (й,г) выполняются условия и сь|аЛ/аг|>ср , то суцостьует

оптимальное решение этой задачи в котором хг-0.

В .§2.2 рассмотрен вопрос сокращения объема параллельных вы -числений тгри решений целочисленной задачи о ранце методам динамического программирования. Доказана следующая Теорема_2.2.1. Если (х1,хг) допустимое решение задачи (4)-(б) и выполняются условия

[а2/а,]+а

где

а=

О, если целое

то

7, если ■ а2/а(- нецелое,

о1,т1+о^гг^о1 [(а121-а2)/а1]4сг(х2+1)г

Из'ьтой теоремы вытекает следующие следствие Следствие_2.2.1. Если выполняется условие теоремы 2.2.1, то существует оптимальное решение задачи (4)-(6), для п=2, следующего вида:

Следстви§_2^2. Если для задачи (4)-(6) выполняется условие

J=1,n-I,

то .

где

О, вела ~ В&лое

^ | 1, если (т^, - нецелое, г 7«

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

*п=[ь/ап}' п

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

НИМИ. '.' ■■■

Результаты полученные во второй 'главе били расширены в главе 3 для задач целочисленного линейного программирования (фЩ) и линейного программирования (.ЛП). .

Глава 3 так ке состоит из трех параграфов. В §3,1 рассмотрен вопрос уменьшения числа неизвестных в задачах ЛП следующего ввида:\

£ —тх, . . ' . (Т) .. .)=»' . п

а^х^ $ Ь{ , «см., (8)

О, . jel¡ ,

Здесь U=t 1,2.....m), K={ ! ,2.....n). '

Ьвэдем обозначения :

I,=It(q,rM f ! a(q>0 и а(г^О }, I2=I2(q,r)={ I I a(q<0 и a(T.<0 }, 1л-13(ч.гМ i | a{q»0 и otr<0 ),

(9)

k-

arg min(a. /а. ), если I ¡¿0 , iíI tr tq 7

arg шах(а /а ) , если I.=0, I-tfi, tcl, 4

(10)

При этих обозначениях доказана Тбо]эема_3.1_.!. Пусть условия (7)-(9> совместны и для пары индексов (q.r), q(II, r(N, выполняются условия:

13=0.

если и (^г/аА())с^ сг,

(11)

либо

либо

если и 1„?*0 ц min(a, /а. )5?тах(а, /а. ),

если IfUI2=0 и '.¿q>0,

то любому допустимому решению X' задачи (7)-(Э) можно поставить в соответствие другое.решение X2» для которого. ^=0

I * I сА

Теорема 3.1.1 на основе сравнения двух столбцов матрицы ограничений дает достаточные условия, где при многократных выполнениях к частд неизвестных присваиваются нулевое значение. Из Теоремы 3.1.1 получены следующие следствия Следствие JL 1.1.. Если выполняются условия теоремы 3.1.1, то в задаче (7)-(9) мокно принять х ==0 , При этом верны следующие выводы: • '

а) если область допустимых решений, определяемая условиям (3) и (9) является ограниченной (неограниченной), то для полученной задачи она аакй,, будет ограничешой (неограниченной);

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

55ействке_3.1 JZ. Если выполняются условия теореш 3.1.1 и деловая функция (7) ограничена сверху, то существует оптимальное решение задачи (7)-(9), в котором ^г=0. Если, кроме того,, в уело-, вии (11) неравенство (а^/а^ )cq^cr выполняется строго, то хг=0 во всех оптималыгах решениях задачи (7)-(9).

Представляет интерес применение теоремы 3.1.1 к двойственной задаче ЛП (ДЗЛП). Для этого'введем обозначения: G)=G,(p,e)={ j I а^'<0 и 8s;«0 ),

G2=G2(р,3)={ j (. &pJ>0 и а^>0 ),

G3=G.j(p,a)={ j | apJ<0 и asJ>0 ),

arg min (a ,/a .), если G./0, je_ G "J PJ . t- !

arg max (a ,/a .), если G =0 и G /0. je g '

Здесь р<41 и seM. Доказана следующая

1§9В§ма_3.1Л2. Пусть условия (8), (9) совместны, целевая функция (7) ограничена сверху и для пары индексов (р,з), р(И : и эеН выполняются условия:

<aa/aPt>bP^S' и кроме того, при Gf*0 и G ¿0 справедлива

rain (а ./а„.);> пах (а ,/а .). jtG, aJ PJ je<¡„ Rj pJ

Тогда в оптимальном решении двойственной задачи переменная,соот-вотствушая ограничешио о исходной задачи, равна нулю.

В §3.2 рассмотрен вопрос уменьшения числа неизвестных в задачах ЦДЛ. Тамже показано, что Теорема 3.1.1 допускает гтрименеыю на случай, когда

х целые, «íN .' (12)

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

Н=

[a¿r/afcci], если 1^0 8>г/а>,- если 1,=0 и

(13)

Здесь а J -целая часть вещественного числа а. Доказана

Теорсмг_3.2^1_. Пусть-условия (8), (12) совместны и для индексов (ч.г), г( 11, выполняются условия:

V0,

если I.UI.^0 и Не io ,

IS q Г

.П5бО

6ели I.^p, 1,И0 и n.in 1а. /а. Ьшах а. /а. ,

1 г tei L ir ^J 1я

7 £

либо

если I.UI„=0 и с >0, ' с ч

то любому допустимому решению X' задачи (7), (8), (12) можно поставить в соответствие другое допустимое решение X2, для которого

01метка, что Следствия 3.1.( и 3.1.2 Теоремы 3.1.1 остается в силе такке длп 'Георомы 3.2.1, т.е. для задачи ЩШ.

С целью эфректаензети Теорем 3.1.1 и 3.2.1 как основы для процедур 'гменычвиия размерности задач ЛГ1 и ДЛП Окли проведены ви-числатблыще эксперименты. Эксперименты проводились на задачах с неотрицательной матрицей ограничений, т.е. на задачах ЛП (7)-(9) и ЦЛП (7), (8),(12), коэффициенты которых удовлетворяют дополнительным условиям, т.е. Результаты вычислительных экспериментов показывают, что предложенные в главе 3 и основанные на теоремах 3.1.1 и 3.2.1 метода априорного анализа могут оказаться эффективным средством для предварительного уменьшения размерности задач ЛП и ЩГП. При этом они особенно эффективны для задач с ■небольшим количеством ограничений. •

Четвертей глава дасводш . вараллельйы« авг^штм рщения задач Ш. Общая модель задачи ЛЛ с искуссгйеййш бвзтм 'имеет следующую форму (для удобства числа ограничений ириня/э равным

п*п-1 ' 1

Для этой задачи предлагается новый ' параллельный алгоритм симплекс-метода с искусственным базисом. В отличие от известных ра-' бот по параллельным алгоритмам решения задач ЛП, здесь использовано представление данных о задаче в .виде "скошенной" матрицы и предложена новая архитектура многопроцессорной вычислительной системы для реализации.этого алгоритма. Проведено сравнение алгоритмической сложности симплекс-метода с искусственным базисом на .системах с кольцевой'архитектурой, на Матричной системе тшш ' ШЛРС-П и на предлагаемой системе/ •.■-".'■■

В предлогаемой системе, в отличйе от кольцевой системы (КС), допол!ит<''л1..но гагаотс-я управляющий процессор (УП)коммутатор связи, связывающий (ЭТТ) со.всеми параллельными процессорами (ПП), и т/2-1 локальных связей .'меаду (ПП) с номерами . )21,

кр=(к+?)21. -где .««Мо^т-*, ■ Ь*0,2(П/21*1-!) : (где ь^2Г,'г целое). В (КС) имеется т (ПП) и т локальные связи, связывающие эти процессоры по кольцу.

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

ш элементов за 0(1о^гт) шагов.

Предположим, что элементы су alJ, в памяти ЭВМ размещены в виде матрицы:

0 °2 сз а п с , п* 1 ■ о п+т-1

V а,2 а,з а1п

Ь2 аг, а22 °23 агп а2.пИ •■ а2,п+т-1

Ьт-/ °т-1.1 ат-1.2 ат-1,3 " ,п ат-1 ,п+1

. .а

'т.-1, п*т-1

Скошенной матрицей для матрицы А*, называется матрица А, которая получена из Л*следующим образом: столбцы матрицы А, J-í,п+т, получены сдвигом соответствующих столбцов А*. Сдвигом столбца .М а именно (с^...', где '-знак транспонирования) на к строк будем называть операцией сдвига всех элементов на к строк в сторону увеличения номеров строк. При этом все элементы, выходящие за последнюю строку, переставляются на начало столбца. При т<п ' номера столбцов матрицы А4 могут быть представлены в виде: + , e=[(J-1)/m]f Столбец J матрицы

А получается из столбца J матрицы А* сдвигом на з 'строк, где J'=J-вm-1=(J-1) той(т). ■

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

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

Анализ результатаов диссертации позволяет сделать следующее заключение: :

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

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

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

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

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

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

' дельный Алгоритм» Показано, что этот Алгоритм ни лрдаошшэй ш-■ числительной системе работает с эффективность», близкой к едини; це. : ; -V

7, На; основе вшив указанных критерий разработан алго^ тм для сокращения размерности целочисленной задачи о ранце с одним и со многими ограничениями, '

Основные результате, цолучошшв в диссертационной работа опубликованы в сладукцих работок:

1. Бабаев Дх. Л., Марданов С.С, Параллельный алгоритм решения

задач линейного программирования. " Кури. Вычисл, Матем. и ма-, тем. фкз., т. 30, й 1, 1991, с. 86-95.

.2. Бабаев Дх. А., Марданов С,С» Параллельный алгоритм решения' задач лаиеЗаого программировать, Сб, тез. доке Всесоюз. науч. техн. койф, "Проблема создания опыт разработки, внедрения автоматизированных скотом управления в Нефтяной, газовой, нефти-, хкьптокек прочш'дошюсти и объектов нефтиснабхещя Азарб. НПО • НефтгоаЛЕ'юмат", Сумгаит, 1990, с. 30. -

3. Бабаев Дк. А., Марданов С.С. Последовательная и одновременная.агрегация диофантових уравнений. Деп. ВИНИТИ 5280-В90,

1990. ■■.■:.■ ' . Л ■ л'г.--.. •

4. Бабаев Дж.А., Марданов С.О, Проблема агрегации диофантовых уравнений, " Проблемы прикладной математики и информатики М.: Вычислительный ЦЕНТР РАН, 1992, часть 2.

б» Марданов О,С. Класс уравнений даофанта, шещих единственное ■ решение и их приложения. Мастер, науч.. кайф, аспир. АН Азерб.,

1991, с. 16-18.

. Карданов С.С. Сокращение размерности целочисленной 'задачи о ранце и ее решении параллельным алгоритмом динамического программирования. М.1 Яур. Дискретная математика, т. 4, вып. 2, 1992, с. 32-38.

И Л А С Э

ДиссертасиЗа ыяи дискрет ей хаття програмлашдариа иаоэлзлэри-ннь тэдгиги проблеиларннэ hacp едилшшдир- Бу тип ыэсэлэлзр халг тасарруфатшшн плаадаодыршшэсцни» елы ва техниканы» иухтэлиф саПолэриидэ татбиг олувдугундац ишн актуаллигы шуСЬэ догурыур.

Мэ'лундур ки, дискрет прогрзйлашдарыа ивсэдэлзршшн Ьэлли.бир га¿да олараг, oejyK Ьаадда ЬесаРлеУа аиалхШатлары илэ цушаиЗат олуиур. Бела ки, аиэлнЗЗатлари?! давдвры бамдлан иэсалвларин олчу-сундэн експопинсиал всылшигда олур. ЬесаСламаларин уыуш чэтин-л^Занин азалдал^аси ыэгсэда ила тац гаЗыатли хатти програулашдцр-ьш (^асалалзрзу^ вэ елэчэ дэ tau дэ^вдаила чакта «зсадасинда ел-чупун азаддалуаса усулу таюзф. олуиур. АПарылша Ьасаблааа експе-$жгкн*яэра мясф' ощгщш уеулун ефрахтрлифиш тэсдар ед«р. Динар тарэфдвя вершЕях- уеовлзлэрин KahAyAisJJsr вортлорящн аэад-. додогси Т-Т-» Тйшишдардааи агрегаси^а усуллари тэклиф

ояукур.

Tea даЗкдвшщ чакта иэсалосишш Ьэдшпшн сналатик дустурла ja-жлдан сю'фп uyaj Заавзвдфгазедвир. Дуз вэ.гсшца хзтти програцлаи-;?-!r:jr, кэсгл&лзри унуп олчуиук аэалдалндеы усуллари Еерилнб во он-лорин ei'ieк~;флиЗшпш Зохлашдаэсы учун Ьесаблаца експерииантларн апарнлшкздцр,

Хэттм програцлавдр^а вэ таи дэЗишгош чвнта мэсалзлэри учуп параллел алгорнтцлэр шлашквцир. Бу алгоритмами раалкзаы^асц учун de ins параллел архитектурами йесаблаиа мввшш твклиф олуныуш-дур. Квстэрилиийдир ки, сун'и бпзисли параллел снцплес алгоритм таклиф олуиан парйлел архитектура ли heсаблама цаиашнда öeJyK сур'этлэ еэ вйЫдэ Захни еффектиьликла раализа олуиур

S17KMARY

The present dissertation work Is dedicated to Investigation of the discrete and linear piogrammlng problems. As these problems are widely applied in planning national economy and In various fields • of science and technique, the actuality of the work is undoubted.

. It is known that a solution of a discrete programming problem, in the main, involves a lot of computational .operations expressed in an exponential dependence on the dimension of the problem considered. To decrease the total eomplexit.v of computations the reduce methods of the dimension in integer linear programming problems, 'aa well as in knapsack problem with Integer variables are proposed. With a- view to study the efficiency of the suggested methods computational experiments are carried out.'

In oder to.decrease the dimension of Dlophantine equations the aggregation methods are suggeste'.-

A class of knapsack problems is separated for which a optimal solution is designed by the analytical formula;

For the linear and dual linear programming problems the crite-rions of reducing the dimension are. proposed and for Investigation of the efficiency of the proposed crlterions the computational experiments are also conducted.

• For solving the knapsack and linear programming problems the _ parallel algorithms are designed and to. realize these algorithms a multiprocessor' system with the parallel architecture is suggested. It is shouwn that the designed parallel algorithms to solve linear programming problems on the suggested multiprocessor system/are' realized with a largo velocity and the efficiency closed to unit.