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



Министерство общего и профессионального образования РФ Карачаево-Черкесский технологический институт

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

Темирбулатов Пилял Исхакович

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

05ЛЗЛ6 - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

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

Научный руководитель доктор физ.-мат. наук, профессор В.А. Перепелица

Черкесск - 1998

ОГЛАВЛЕНИЕ

стр.

ВВЕДЕНИЕ................................................................................................ 3

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

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

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

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

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

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

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

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

§ 2.4. Алгоритм...................................................................................... 30

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ.......................................................................................... 94

ПРИЛОЖЕНИЕ.......................................................................................... 96

ЛИТЕРАТУРА............................................................................................ 98

ВВЕДЕНИЕ

На пороге третьего тысячелетия человечество, осознав возможности использования вычислительной техники и математики в решении как локальных, так и глобальных проблем во всех сферах жизнедеятельности, все больше и больше обращается к математическому исследованию и математическому моделированию различных процессов. Общепризнанно, что моделирование - один из наиболее эффективных методов познания. И справедливо утверждение, что "... развитие любой науки можно трактовать - в весьма общем, но вполне разумном смысле, - как "теоретическое моделирование"" [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] впервые показано, что существуют такие ПО некоторых дискретных МКЗ, которые не удается найти никакой линейной сверткой критериев. Тем самым, в этих случаях АЛС не обеспечивает получение всех элементов ПМ, и можно говорить о неразрешимости таких задач в классе линейных св�