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

• Темирбулатов, Пилял Исхакович
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Темирбулатов, Пилял Исхакович

ОГЛАВЛЕНИЕ

стр.

ВВЕДЕНИЕ

Глава I. ОЦЕНКИ МАКСИМАЛЬНОЙ МОЩНОСТИ МНОЖЕСТВА

ДОПУСТИМЫХ РЕШЕНИЙ ЗАДАЧИ О ТРИСОЧЕТАНИЯХ НА МНОГОЦВЕТНЫХ ГРАФАХ

§1.1. Формулировка проблемы. Максимальная мощность МДР задачи о

трисочетаниях на 3-цветных графах

§ 1.2. Максимальная мощность МДР задачи о трисочетаниях на 4-цветных графах

Глава II. ОЦЕНКИ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ ВЕКТОРНОЙ ЗАДАЧИ О 3-СОЧЕТАНИЯХ НА ш-ЦВЕТНЫХ ГРАФАХ И СТАТИСТИЧЕСКИ ЭФФЕКТИВНЫЙ АЛГОРИТМ § 2.1. Содержательное описание и математическая постановка задачи

§ 2.2. Полнота задачи

§ 2.3. Мощность ПМА

§ 2.4. Алгоритм

§ 2.5. Вероятный анализ многокритериальной задачи о 3-сочетаних и алгоритма^

§ 2.6. Оптимизация вычислений

Глава III. ИССЛЕДОВАНИЕ РАЗРЕШИМОСТИ С ПОМОЩЬЮ АЛГОРИТМА ЛИНЕЙНОЙ СВЕРТКИ ЗАДАЧИ О ТРИСОЧЕТАНИЯХ НА МНОГОЦВЕТНЫХ ГРАФАХ §3.1. Формулировка проблемы

§ 3.2. Необходимые обозначения и определения

§ 3.3. Исследование разрешимости с помощью АЛС задачи о трисочетаниях с

критериями вида MINSUM на 3-цветных графах

§ 3.4. Исследование разрешимости с помощью АЛС задачи о трисочетаниях с

критериями вида MINSUM на 4-цветных графах

§ 3.5. Исследование разрешимости с помощью АЛС задачи о трисочетаниях с

критериями вида MINSUM на 5-цветных графах

§ 3.6. Исследование разрешимости с помощью АЛС задачи о трисочетаниях с

критериями вида MINSUM на m-цветных графах (т > 6)

§ 3.7. Исследование разрешимости с помощью АЛС задачи о трисочетаниях с

критериями вида MINMAX на 3-цветных графах

§ 3.8. Исследование разрешимости с помощью АЛС задачи о трисочетаниях с

критериями вида MINMAX на 4-,5-цветных графах

§ 3.9. Исследование разрешимости с помощью АЛС задачи о трисочетаниях с

критериями вида MINMAX на m-цветных графах (т > 6)

ЗАКЛЮЧЕНИЕ

ПРИЛОЖЕНИЕ

ЛИТЕРАТУРА

Введение диссертации (часть автореферата) на тему «Исследование сложности и разрешимости некоторых дискретных многокритериальных задач»

ВВЕДЕНИЕ

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

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

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

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

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

Изложению конкретных результатов, полученных в настоящей работе, предпошлем следующее замечание общеметодологического характера. Главная проблема, которую приходится решать при моделировании и анализе всякой сложной системы, - это выбор существенных переменных. В настоящей работе основное внимание сконцентрировано на связке "рассматриваемая культура / -ее предшественник (на данном поле)у". В процессе моделирования для всякой пары (г,у) указанного вида отражается скорее не фактическое плодородие почвы, а его динамика, т.е. его изменения в случае, когда рассматриваемая культура засевается на поле, для которого известна культура - предшественник, которая была засеяна на этом поле в предшествующий сезон. В рассматриваемых математических моделях в конкретный момент времени подразумеваются фиксированными такие факторы как тип почвы, его увлажнение. Вместе с тем, конкретная пара (7,у) определяет собой такие компоненты плодородия, как количество гумуса, азота, фосфора и тому подобное [33]. Важно подчеркнуть, что указанные факторы отражаются в рассматриваемых ниже моделях в виде общего агрегированного показателя, например, в таких относительных (безразмерных) единицах как баллы, проценты и т.д.

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

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

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

числами z = l,2,...,w (т> 3). Севооборотом (польности р) называем

g

последовательность из р = — полей одинаковой площади, к которым (полям)

т

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

В терминах теории графов элементарный севооборот можно представить в виде простого цикла (контура) [21] вершинам которого поставлены во взаимно-однозначное соответствие культуры i е {1,2,...,т}. При этом, если указанный цикл (контур) содержит ребро (дугу) е = (i,j), то это означает, что данный элементарный севооборот определяет собой такую ротацию культур на полях, при которой культура i засевается по предшественнику у, i,j е {1, 2,...,т}, i Фj. Заметим что, если т различных культур засевается на "т" полях и при этом не существует запрещенных пар (i,j) в элементарном севообороте, то формально существует (т - 1)! различных элементарных севооборотов польностир= т.

Как мы уже отмечали выше всякая допустимая пара (i,j) определяет собой некоторое число N компонент плодородия: количество гумуса, азота, фосфора и др. [33]. Перенумеровав эти компоненты индексами v= 1, 2,...,7V, в процессе построения теоретико-графовой модели севооборота для конкретной

допустимой пары e = (i,j) приписываем веса wv(e), v = l,iV, означающие количество v-ой компоненты в почве в случае, когда по предшественнику j была засеяна культура i. Используя эти обозначения можно определить показатели или критерии агробиологической эффективности для всякого элементарного севооборота, представленного циклом

С = [ii, ¿2..........(I')

Предполагая, что каждому ребру е - (4, 4+ i)eC, к = 1,7V, im+ \ = i\, приписан вектор весов

(wi(e), w2(e),wv(e),..., wN(e)), суммарную эффективность элементарного севооборота (1) представляем в виде суммы

Fv(C) = 5>v(iO->extr,

ееС

где extr может принимать значения max или min в зависимость от того, положительный или отрицательный эффект заложен в компоненту

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

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

Пусть М= {С} - множество всех допустимых циклов (т.е. элементарных севооборот), определенных на множестве культур i=l,2,...,m. Для формулируемой векторной задачи об элементарном севообороте множество М называется множеством допустимых решений (МДР). На МДР М определена векторная целевая функция (ВЦФ)

F( С) = (F,(C),F2( С),..F^C)), (3)

которая в свою очередь определяет собой паретовское множество (ПМ), MczM, состоящее из паретовских оптимумов (ПО) [52]. ПМ М содержит в себе так называемое полное множество альтернатив (ПМА) М° [23, 25, 26, 27] которое и представляет собой искомое математическое решение многокритериальной задачи в том смысле, что наиболее целесообразное решение выбирается из М° с помощью процедур теории выбора и принятия решений [50].

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

Для математической постановки рассматриваемой задачи используем следующее обозначение G= (V, Е) - л-вершинный граф, в котором каждому ребру ееЕ приписаны веса wv(e) > 0, v= 1, 2Vk - подмножество вершин ve V, окрашенных в цвет к, к= 1 ,т. В общем случае допустимым решением задачи является такой подграф xe(V, Ех\ Excl Е, в котором каждая компонента связности есть полный 3-вершинный подграф, вершины которого окрашены в различные цвета; X = X(G)= {х} - множество всех допустимых решений на данном графе G. На МДР X определена векторная целевая функция

F(x) = {F,{x\F2{x\...,Fn{x)) (1)

X(е) 1ШП, V = 1, 2,...,ЛАЬ ^ <

ееЕг

Fv(x)=max и^ (е) -» тт, V = N1 + 1, ЭД + 2,...,М

ееЕ.

(2) (3)

ВЦФ (1) с критериями вида МШБЦМ (2) и МШМАХ (3) при N>2 определяетпаретовское множество 1сХ [22, 48, 49, 52].

Определение. Элемент х е X называется парето-оптимальным, если не

существует элемента х*еХ, что выполняется ру(х*) < /\,(3с), v = среди которых есть хотя бы одно строгое. «Наилучшее» решение выбирается из полного множества альтернатив (ПМА) Х°. ПМА называется такое подмножество которое имеет минимальную мощность |Х°| при

выполнении условия Р(Х°) = Р(Х), где Р(Х*)={Г(х) \хеХ* } для любого X* сХ[22, 48, 49, 52].

В главе I получены точные формулы максимальной мощности МДР X для

3-, 4-цветных графов.

Обозначим через &(п, т) - множество всех и-вершинных т-цветных графов; 1|/((7) - мощность МДР задачи на графе ф(я, т) = шах (Сг), где максимум берется по всем графам (7 е (з{п, т).

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

Теорема 1. Для т = 3 и всех п, кратных 3, максимальная мощность Ф(и,3) = (Л)2,где/ = у.

Теорема 3. Для т = 4 и всех п кратных 12 максимальная мощность множества допустимых решений задачи о трисочетаниях на я-вершинных

4-цветных графах равна

ф0,4) =

/п/\ Г я/\

п/ 4/12

п/ \/\1)

К\2;

В главе II установлено, что если в (1), (2) значение N\> 2, то рассматриваемая задача обладает свойством полноты, т.е. при определенных значениях весов w(e) ребер графа G выполняются равенства X(G)=X = Х°. Доказана следующая теорема.

Теорема 1. Задача о трисочетаниях является труднорешаемой, т.е. вычислительная сложность нахождения ее ПМА растет экспоненциально от п, если ВЦФ (1) содержит хотя бы два критерия вида MINSUM.

Теорема 1 относится к такой формулировке алгоритмической проблемы, которая определяет вычислительную сложность по принципу «в худшем случае» [53]. Однако значительный интерес представляет статистический подход к вычислительной сложности, когда верхняя оценка ее значения вычисляется в смысле «почти всегда» или «для почти всех индивидуальных задач». Для формулировки результатов, полученных в этом направлении, введем следующие обозначения: т, г) = {G} - множество всех /ю-цветных

я-вершинных графов G= ( V, Е), у каждого из которых компоненты wv(e) весов w(e) ребер е^Е принимают значения wv(e) е {1, 2,...,r}, v=l,N. Пусть произвольная функция Х(п) —» оо, при п —» оо.

почти всех графов Сг е т, г) ПМА X2 является одноэлементным (|^|=1) при любом е {0,1, 2

Для нахождения одноэлементного ПМА построен приближенный

Теорема 3. При выполнении условий теоремы 2 алгоритм а является статистически эффективным, т.е. он находит ПМА для почти всех графов ^л(п, т, г) с полиномиальной вычислительной сложностью.

Теорема 2. Если выполняется неравенство

п

-, то для

In п + Х(п)

полиномиальный алгоритм а с вычислительной сложностью т(а) = б(п 2).

5/2-

Алгоритм Л называется асимптотически точным, если существуют

последовательности {'£„} и {§„}, стремящиеся к нулю с ростом размерности задачи, для которых выполняется неравенство

^Т^Ф1-5"'

где 2л - значение ЦФ полученное в результате работы алгоритма Д г* -оптимальное значение ЦФ, Р{...} - вероятность события {...}.

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

Глава III посвящена открытому в настоящее время вопросу: является ли разрешимой с помощью алгоритмов линейной свертки (АЛС) многокритериальная задача о трисочетаниях, в случае если ее векторная целевая функция (ВЦФ) состоит из критериев весового вида (в терминах [27] из критериев вида МШ§иМ или МАХ811М).

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

N

Пусть Ам = =1 >0, V = 1,2,...,]Ч}. Всякому

вектору ХеАм соответствует линейная свертка критериев данной ВЦФ (1):

N

= • Идея алгоритмов линейной свертки базируется на

следующем утверждении, справедливым для любого ХеА^ : если на элементе х* еХ значение линейной свертки /^(х) достигает минимума, то х* является паретовским оптимумом, т.е. х* е X.

Последнее утверждение служит основой большинства известных алгоритмов решения многокритериальных задач математического программирования [17, 36, 51, 62, 69].

Отличительной особенностью этих алгоритмов (АЛС) является то, что они не всегда гарантируют нахождение всего искомого множества альтернатив (МА). В [2,69] впервые показано, что существуют такие ПО некоторых дискретных МКЗ, которые не удается найти никакой линейной сверткой критериев. Тем самым, в этих случаях АЛС не обеспечивает получение всех элементов ПМ, и можно говорить о неразрешимости таких задач в классе линейных сверток.

Как отмечено в [38], эффективные алгоритмы нахождения МА разработаны лишь для некоторых дискретных задач с двумя критериями. До сих пор не известны задачи дискретной оптимизации с N>3 критериями, для которых существовали бы алгоритмы гарантированного нахождения ПМ X, принципиально отличающиеся от перебора всех элементов МДР X. По этой причине немногочисленные известные алгоритмы нахождения ПМ характеризуются исключительно большой вычислительной сложностью. Например, предложенный в [32] алгоритм (3 нахождения всех парето-оптимальных цепей из фиксированной вершины имеет оценку сложности 0{Ып2п ~3), где N - количество весов, которыми взвешено каждое ребро п-вершинного графа.

Всякая индивидуальная МКЗ определяется парой (X, К), где МДР X и все параметры ВЦФ ^ = Е(х) фиксированы. Множество X в этом случае называется индивидуальным МДР, а векторную функцию - индивидуальной ВЦФ.

МКЗ с N критериями назовем разрешимой с помощью АЛС, если для всякой ее индивидуальной задачи (X, I7) справедливо утверждение: УЗсеХ 3^еАн: Б1(х) = тт{Р1(х):хеХ},

где ^(рс) - линейная свертка критериев (2). Примером разрешимой МКЗ является задача линейного программирования с несколькими целевыми

функциями.

МКЗ называется неразрешимой с помощью АЛС, если существует такая ее индивидуальная задача (X, Т7), для которой выполняется условие:

3 3с еХ: Р"(х)>тт{Р"(1):хеХ}

В обзоре [27] представлены теоремы о неразрешимости с помощью АЛС таких векторных задач как задачи: о коммивояжере, об остовных деревьях, о цепях между парой вершин, о паросочетаниях. По отношению к ним новым результатом является следующие теоремы.

Теорема 4. Для всякого кратного 3 п,п>т- 3> 6 и всякого N>2 задача о трисочетаниях с критериями вида МШБИМ на ш-цветных А^-взвешенных и-вершинных графах неразрешима с помощью АЛС.

Теорема 7. Для всякого кратного 3 п,п>т- 3> 6 и всякого N>2 задача о трисочетаниях с критериями вида МШМАХ на т-цветных ТУ-взвешенных «-вершинных графах неразрешима с помощью АЛС.

По теме диссертационной работы опубликовано 13 печатных работ. Основные результаты диссертации докладывались на Международной конференции «Математическое программирование и приложения» Института математики и механики УрО РАН (Екатеринбург, 1995), на Международной конференции "Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики"' (Нальчик, 1996), на I Всероссийском симпозиуме «Экономика и право - стратегии 3000» (Кисловодск, 1997), на молодежной научной конференции «XXIII Гагаринские чтения" (Москва, 1997), на Международной конференции «Математическое программирование и приложения» института математики и механики УрО РАН (Екатеринбург, 1997), на Второй научно-практической конференция Карачаево-Черкесского технологического института (Черкесск, 1997), на Международном коллоквиуме 1КМ'97 (Веймар, 1997), на II Всероссийском симпозиуме «Экономика и право - стратегии 3000» (Кисловодск, 1998), а также на

заседаниях научного математического семинара КЧТИ, на Всероссийской научно-технической конференции с международным участием "Компьютерные технологии инженерной и управленческой деятельности" (Таганрог, 6-8 октября 1998).

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

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Темирбулатов, Пилял Исхакович

Результаты исследования были реализованы при имитационном моделировании задачи о трисочетаниях на 3-цветном графе и доложены на "Втором Всероссийском симпозиуме "Математическое моделирование и компьютерные технологии"" [59] (см. Приложение 1).

ЗАКЛЮЧЕНИЕ

В диссертации

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

- осуществлено всестороннее математическое исследование этой модели в условиях многокритериальности;

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

- впервые выведены точные формулы вычисления максимальной мощности множества допустимых решений;

- получены нижние оценки максимальной мощности множества альтернатив для векторной задачи о трисочетаниях на многоцветных графах для числа цветов т. = 3,4;

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Темирбулатов, Пилял Исхакович, 1998 год

ЛИТЕРАТУРА

1. АхоА., ХопкрофтДж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979. - 536 с.

2. Батищев А.Ф., Гришин A.A. Перепелица В.А. Из опыта решения задач по нахождению оптимального севооборота и их внедрения. В сб. Экономико-математические методы и ЭВМ в сельском хозяйстве. - 4.2- Вильнюс: НИИЭСХЛССР, 1970- С.141-145.

3. Батищев А.Ф., Перепелица В.А. Об одном алгоритме нахождения оптимального севооборота. В. сб. Оптимальное планирование. Новосибирск: Ин-т математики СОАН СССР, 1970.

4. Бирюков Б.В., Гастев Ю.А., Геллер Е.С. Моделирование - ВКН.: БСЭ. Изд. 3, 1974, Т. 16,-С. 395.

5. Вилкас Э.И., Майминас Е.З. Решения: теория, информация, моделирование.-М.: Наука, 1982.-256с.

6. Виниченко С.М. Подсчет гамильтоновых циклов и путей в полных гс-цветных графах // Комбинаторный анализ. 1983 - Вып.6. М.: Изд-во МГУ. -с. 65-67.

7. Вольтерра В. Математическая теория борьбы за существование. - М.: Наука, 1976.

8. Вольтерра В. Теория функционалов, интегральных и интегро-функциональных уравнений. -М.: Наука, 1982.

9. Вязгин В.А., Федоров В.В. Математические методы автоматизированного проектирования. -М.: Высшая школа, 1989 - с. 184.

Ю.Гермейер Ю.Б. Введение в теорию исследования операций.-М.;Наука,1971.

11.Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками задач дискретной оптимизации //Проблемы кибернетики. - Вып. 31. - М.: Наука, 1975. - С. 35-42.

12.Гладкий A.A., Янушкевич О.А.О линейной свертке частных критериев векторной задачи минимизации// Тез. докл. IX .Всероссийской конф. « Математическое программирование и приложения.»-Екатеринбунг,1995.-С.65.

13.Гулиев P.P., Коновалов М.Г., Огневцев С.Б. Моделирование севооборотов с помощью управляемых Марковских цепей.// Народной хозяйство Азербайджана. № 8, 1985. С. 49-51.

14.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -М.: Мир, 1982. - 416 с.

15.Дубов Ю.А., Травкин С.И., Якимец В.Н. Многокритериальные модели формирования и выбора вариантов систем.-М..;Наука,1986.

16.Емеличев В.А. К оценке сложности многокритериальных транспортных задач // Докл. АН БССР, 1986. Т.ЗО. -N. 7.-С. 593-596.

17.Емеличев В.А., Кравцов М.К. О задачах векторной дискретной оптимизации на системах подмножеств неразрешимых с помощью алгоритмов линейной свертки // ЖВМ и МФ, 1994. Т. 34. - №7. - С. 9-11.

18.Емеличев В.А., Кравцов М.К. О неразрешимости векторных задач дискретной оптимизаций на системах подмножеств в классе алгоритмов линейной свертки критериев //Докл. РАН,1994. Т. 334. -Nl. -С.9-11.

19.Емеличев В.А., Кравцов М.К., Янушкевич O.A. Разрешимость минимаксных задач векторной оптимизации с помощью алгоритма линейной свертки критериев //Тез. докл. IX Всероссийской конф. «Математическое программирование и приложения». -Екатеринбунг, 1995. -С. 88-89.

20.Емеличев В.А., Кравцов М.К., Янушкевич O.A. Условия парето-оптимальности в одной дискретной векторной задаче на системе подмножеств // :ЖВМиМФ,1995. T.35.-N11.-C. 1641-1652.

21.Емеличев В.А., Мельников О.Н., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука, 1990 - с. 384.

22.Емеличев В.А., Перепелица В.А. К алгоритмическим проблемам векторной оптимизации на графах // Системы программного обеспечения решения задач оптимального планирования: Тез. докл. 9 Всесоюз. симпоз. (Минск, 23 февр. - 3 март. 1986г.) - М.% ЦЭМИ АН СССР, 1986.-С.79-80.

23.Емеличев В.А., Перепелица В.А. К вычислительной сложности многокритериальных задач //Изв. АН СССР. Техн. Кибер. - 1988. - №1. - С. 85-87.

24.Емеличев В.А., Перепелица В.А. Многокритериальные задачи об остовах графа//ДАН СССР,1988. Т. 298. -N3. -С.544-547.

25.Емеличев В.А., Перепелица В.А. О некоторых алгоритмических проблемах многокритериальной оптимизации на графах //ЖВМиМФ, 1989. -N2. -С. 171183.

26.Емеличев В.А., Перепелица В.А. Сложность дискретных

многокритериальных задач // Дискретная математика. 1989.

27.Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач. // Дискретная математика.-1994.Т 6 № 1.-C3-33.

28.Казиев В.М. Некоторые алгоритмы и программы идентификации математических моделей накопления биомассы растений. - В сб.: Методы математического моделирования в системах автоматизированного проектирования и планирования. Нальчик, 1985. - С. 135-145.

29.Карлин С. Математические .методы в теории игр, программировании и экономике.

30.Кляус П. С. Минимум суммарных затрат в одной задаче выбора. Математические методы и их применение //материалы 3 конф. Молодых ученых ин-та математики АН БССР и ин-та физики и математики АН Лит.ССр.-Минск, 1977.-78с.

31.Козина Г.Л. Алгоритмы и оценки для некоторых задач векторной оптимизации на многоцветных графах. - Диссертация на соискание ученной степени КФ-МН. - Запорожье; ЗГУ, 1994 - с.416.

32.Козина Г.Л. Исследование векторной задачи коммивояжера на многоцветных графах // Методы решения анализа задач дискретной оптимизации: Сб. Научных трудов: Омск: ОмГУ, 1992. - С. 52-60.

33.Константинов А.Р. Погода, почва и урожай озимой пшеницы. Ленинград: Гидрометеоиздат, 1978.

34.Коршунов А.Д. Об одном алгоритме нахождения паросочетаний в конечных графах.// Кибернетика.- 1975.-№1.-С.1-8.

35.Коршунов А.Д. Основные свойства случайных графов с большим числом вершин и ребер // Успехи математических наук. - 1985. - Т.40, №1(241). -С. 107-173.

36.Кравцов М.К., Янушкевич O.A. О многокритериальных задачах, разрешаемых с помощью алгоритмов линейной свертки критериев || Препринт. - МН.: Ин-т техн. Кибернетика АН Беларуси, 1995. - №16. - 16 с.

37.Кристофидис Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978.-432с.

38.Ларичев О.И. Наука и искусство принятия решения. - М.: Наука, 1979.-200с.

39.Лупанов О.Б. О методах получения оценок сложности и вычисления индивидуальных функций //Дискр.анализ.-1974.- Вып.25.-№ 1.-е.7-11.

40.Майника Э. Алгоритмы оптимизации на сетях и графах. - М.: Мир, 1981.-323с.

41.Маламед И.И., Сигал И.Х. Исследование линейной свертки критериев в многокритериальном дискретном // Тез. докл. IX Всероссийской конф . «Математическое программирование, и приложения .»-Екатеринбург, 1995.-С.65.

42.Меламед И.И. Методы оптимизации в транспортном процессе. ВИНИТИ, Сер. Организация управления транспортом (1991) 10, 1-164.

43.Михалевич B.C., Волкович B.JI. Вычислительные методы исследования и проектирования сложных систем.- М.: Наука, 1981.- 287с.

44.Моисеев H.H. Математические задачи системного анализа.- М.: Наука, 1981.-312с.

45.Нахушев A.M. и др. К вопросу автоматизированного прогнозирования урожайности основных сельскохозяйственных культур в условиях орошения и степной зоны. - В сб.: САПР и АСПР в мелиорации. Нальчик, 1983. - С. 156-163.

46.Озерной В.М., Гафт М.Г. Методология решения дискретных многокритериальных задач. В кн.: Многокритериальные задачи принятия решений. Машиностроение, Москва, 1978, с. 14-47.

47.Пападимитриу X., СтайглицК. Комбинаторная оптимизация. Алгоритмы и их сложность. - М.: Мир, 1985. - 512 с.

48.Перепелица В.А. К алгоритмической проблеме для многокритериальных задач проектирования управляющих систем // Проблемы теоретической кибернетики: Тез. докл.7 Всесоюз.конф. (Иркутск, 18-20 сент. 1985г.) Иркутск: Иркутск.гос.ун-т, 1985.-4.1.-С. 164-165.

49.Перепелица В.А. Мамедов A.A. Исследование сложности разрешимости векторных задач на графах.- Черкесск: КЧТИ, 1995.- 45с.

50.Перепелица В.А., КасаевА.Д., Попова Е.В., Салпагарова A.A., Темирбулатов П.И. Исследование операций и принятие решений. Часть II, методическое пособие для экономических специальностей. - Черкесск: КЧТИ, 1996, 36 стр.

51.Перепелица В.А., Сергиенко Н.В. Исследование одного класса целочисленных многокритериальных задач // ЖВМ и МФ, 1988. Т. 28. - №3. -С. 400-419.

52.Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. Наука, Москва, 1982. - 256с.

53.Салпагарова А.А., Тамбиева Ж.А., Темирбулатов П.И. Исследование задач о кликах // Тезисы докладов Международной конференции «Нелокальные краевые задачи, и родственные проблемы математической биологии, информатики и физики». - Нальчик: ИПМ РАН, - 1996. - С. 78-79.

54.Темирбулатов П. И. Исследование многокритериальной задачи о трисочетаниях на 3-цветном графе. // Тезисы докладов научной конференции " XXIII Гагаринские чтения ".- М.: 1997-С26-27.

55.Темирбулатов П.И. Оценки вычислительной сложности векторной задачи о трисочетаниях на m-цветных графах и статистически эффективный алгоритм. Рукопись деп. 10.02.98, - 20 с. //«2.-5*а--. /3 9^

56.Темирбулатов П.И. Оценки максимальной мощности допустимых решений задач о трисочетаниях на многоцветных графах. Рукопись деп. 14.05.96, №1540-В96. - 18 с.

57.Темирбулатов П.И., Темирбулатов А.П. Об имитационном моделировании задачи о трисочетаниях на многоцветных графах. - В сб. Математичекое моделирование и вычислительный эксперимент в естественных, гуманитарных и технических науках. Кисловодск, 1998. Т. II. - С. 88-91.

58.Холл М. Комбинаторика.- М.: Мир, 1970. - 424с.

5 9. Черкасский Б.В. Новый алгоритм генерации остовных деревьев // Кибернетика.- 1987.- №1.-С.85-89.

бО.Шустер Г. Детерминированный хаос. Введение.-М.:Мир,1988.

61.Эрроу К.Дж., Гурвиц Л., Удзова X. Исследования по линейному и нелинейному программированию.-М.; ИЛ, 1962.

62.Brucker P. Discrete parameter optimization problem and essential efficient points || Operat. Res. (1972). V.16. -№5. - P. 189-197.

63.Burkard R.E., Keiding H., Krarup J., Prnzan P.M.A relationship between optimality and efficiency in multicriteria О -1 programming problems// Computers & Optuations Research, 1981. V.8.-N4.-P.241-247.

64.Burkard R.E., Krarup J., Pruzan P.M. Efficiency and optimality in minisum, minimax 0-1 programming problems.// J. Oper. Res. Soc. (1982) 33, №2, - P. 137151.

65.Chaoc Theory in Economics: Methods, Models and Evidnce. Edited by Dechert

W. D., Edward Elgar, 1996.

66.Charnes A., Cooper W. W. Management Models and Jdustrial Application of Linear Programming-N.Y.; Wijey, 1961.

67.Corley H.W., Moonl.D. Shortest paths in networks with vector weights. J. Optimiz. Theory Appl. (1985) 46, №1, 79-86.

68.Edmonds J., Fulkerson D.R. Bootleneck extrema //J.Combin. Thery.-1970.- 8№8.-P.299-306.

69.Emelichev V.A., Perepeliza V. A. Complexity of vector optimization problems on graphs// Optimization, 1991. V. 22 - №6. -P. 903-918.

70.Geoffrion.A.M. Proper efficiency and the theory of vector maximization //J. Math. Analysis and Ahhj,1968.V.22-P.-630.

71.Hamacher H.W., Rendl F. Color constrained combinatorial optimization problem / Oper. Res. Letters, 1991. - V. 10. №4. p.p. 211-219.

72.Hutchinson G.E. Circular causual systems in ecology. - Ann. N.Y. Acad. Sci.? 1948, 50, P. 221-246.

73.Koopmans T.C. Activity analysis of production. -N. Y.; Wiley, 1951

74.KungH.T., LuccioF., Preparata F.P. On finding the maxima of set of vectors. J. Assoc. Comput. Mach. (1975) 22, №4, 469-476.

75.Robertson T.B. The chemical basis of growth and senscience. Monographs on experimental biology. I.B.L.C. - Philadelphia, London, 1923.

76.Steuer R. Mujticriteria optimization.-N.Y.; Wijey, 1985.

77.Yemelichev V.A., Kravtsov M K., Yanushkevich O. A. JN solvability of vector problems on systems of subsets using a linear criteria convolution algorithm //Abstracts of the second International Conference «Mathematical algorithms».-Nizhny Novgorod, 1995.-P.21.

78.Yu P.L. Cone convexity, cone extreme points, and nondominated solutions in decision problems with mltiobjectives// JOTA,1974.V.14.-N3.-P.319-377.

79.Zeleny M. Linear Multiobjective Programming. Springer, Berlin, 1974.