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

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

Попова Елена Витальевна Л -

т

/ДК 519.6

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

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

АВТОРЕФЕРАТ

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

Черкесск-1998

Работа выполнена в Карачаево-Черкесском Технологическом институте

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

профессор ПЕРЕПЕЛИЦА В.А.

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

профессор НаталухаИ.А. доктор технических наук, кандидат физико-математических наук Иванов П.М.

Ведущая организация: Ставропольский государственный технический университет

Защита диссертации состоится десйдпЛ 199/г. в -/О часов на заседании регионального диссертационного сбвета К200.74.01 по физико-математическим наукам в НИИ ПМА КБНЦ РАН по адресу: 360000, г.Нальчик, ул.Шортанова, 89"а".

С диссертацией можно ознакомиться в научной библиотеке НИИ ПМА КБНЦ РАН

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

Ученый секретарь РДС К200.74.01 к. ф.-м. н. - Шибзухов З.М

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы. Среди важнейших задач общечеловеческого значения проблема взаимодействия человека и окружающей среды, проблема "человек и биосфера" в настоящее время стала одной из основных научных проблем мировой науки. Современные масштабы эко-лого-биологических изменений создают реальную угрозу жизни и здоровью населению. Необходимость компенсации потерь от вредных технологий и крупных аварий бедствий влечет за собой переключение народнохозяйственных ресурсов с решения стратегических задач формирования новой структуры экономики на бесплодные попытки поддержания её нынешнего состояния. В настоящей работе разработана математическая макро модель, учитывающая различные аспекты биотехнологических и агробиологических процессов. В работе исследуется вычислительная сложность и свойства критериального пространства известной задачи теории расписаний (задачи упорядочивания). В отличие от классических одно-критериальных постановок исследуется задача в многокритериальной био-эколого-экономической постановке. В условиях многокритериально-сти выбор наиболее целесообразного решения осуществляется из множества несравнимых альтернатив.

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

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

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

Цель и задачи работы. Основной целью работы является исследование сложности известной задачи теории расписаний в многокритериальной постановке и исследование её критериального пространства с целью выявления закономерностей изменения значений одного критерия при монотонном изменении значений другого критерия (порядок или детерминированный хаос?, фрактальная размерность?, устойчивость или неустойчивость?, и сложность, и др.) Прикладная цель - обосновать механизм отсеивания "очевидно плохих решений" для последующего формирования возможно более ограниченного множества альтернатив, которое предъявляется на вход той или иной системы принятия решений.

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

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

Научная новизна. Доказано, что рассматриваемая задача обладает свойством полноты в случае, когда ВЦФ состоит из критериев вида МШ-БиМ; из этого свойства выведена точная формула вычисления максимальной мощности искомого решения; из этой формулы вытекает утверждение в труднорешаемости задачи. Так же доказано свойство квазиполноты в случае, когда ВЦФ состоит из критериев вида МГЫМАХ; из этого свойства выведена экспоненциальная нижняя оценка мощности искомого решения и, как следствие, утверждение о труднорешаемости задачи в случае когда ВЦФ состоит из критериев вида МШМАХ. Разработана и реализована на персональной электронно-вычислительной машине имитационная модель, которая на базе генератора случайных значений исходных данных воспроизводит и представляет в явном виде критериальное пространство для различных комбинаций критериев, составляющих векторную целевую функцию. Разработана математико-биологичекая модель, в которой при определении эффективности системы учитываются дисконтированные экономические критерии и для этих задач найден класс полиномиально разрешимых задач упорядочивания, для которых существует решающее правило нахождения искомого оптимума.

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

б

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

Достоверность полученных результатов. Представленные в диссертационной работе Теоремы и Леммы имеют строгое математическое обоснование. Результаты компьютерного эксперимента имеют массовую реализацию на многочисленных вариантах исходных данных.

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

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

от того, в какой комбинации критерии (2)-(4) входят в состав ВЦФ (1)(возможны следующие комбинации МГЫБиМ-МШБиМ, МГЫБиМ-М1ЫМАХ, М1ЫМАХ-МПЧМАХ).

Лемма 2. I. Для ЦФ вида М1МБ1!М (2) существует такое множество значений параметров а,,/=1,П, что для любой пары х^х" еХ выполняется неравенство ^(х1) Ф <р{х") •

Лемма 2.2. Для ЦФ вида МШ8иМ (3) существует такое множество значений параметров о.{, Д, / — 1,п, что для любой пары

У,х"е А' выполняется неравенство ^»(х1) ^ <^(х").

Лемма 2.3. Если критерии ВЦФ = (х)) удовле-

творяют условиям Леммы 1 (Леммы2), то для всякого допустимого решения х= (/] ,/2 ,...,/„) е X сумма {х) + ^ (л) = С, где с-констан-

та, которая не зависит от выбранной последовательности х.

Теорема 2.1. Двукритериальная задача упорядочивания с критериями вида М1ШиМ (2),(3) обладает свойством полноты, т.е. для всякого

п существуют такие значения параметров а^, 2• , О^, ¡=\,п, V = ГТ2,

при которых ПМА ПМ X и МДР X совпадают.

Теорема 2.2. Алгоритмическая проблема нахождения ПМА для двукритериальной задачи упорядочивания с критериями вида МП^ЦМ является труднорешаемой, т.е. вычислительная сложность этой задачи растёт экспоненциально с ростом размерности п .

Для двукритериальной задачи с критериями вида МШМАХ справедливы следующие утверждения.

Лемма 2.4. Нижняя оценка мощности | \р{Х)\=\ {у(х):хеХ} | множества значений критерия ц/{х) вида МШМАХ равна 2"~'.

Лемма 2.5. Верхняя оценка мощности \ц/(Х)\=\{{!/{х)-хеХ\\ множества значений критерия у/{х) вида МГЫМАХ равна

Лемма 2.6. Нижняя оценка мощности множе-

ства значений критерия у/(х) вида МШМАХ равна 2"~'.

Лемма 2.7. Верхняя оценка мощности =|{(Да):хе множе-

ства значений критерия у/(х) вида МШМАХ равна .

Лемма 2.8. Если ВЦФ состоит из критериев вида МШМАХ, то

для всякого её допустимого решения ,¿2 существуют

такие значения параметров задачи упорядочивания, при которых сумма

(л) + Р"2 (х) - С, где С- константа, которая не зависит от выбранной

последовательности х ■

На основании Лемм 2.4-2.8 являются справедливыми Теорема 2.3. Двукритериальная задача упорядочивания с критериями вида МШМАХ (4),(5) обладает свойством квазиполноты, т.е. для всякого П существуют такие значения параметров

а\, 7], , / = 1,П, V = Ц2, при которых для ПМА X", ПМ X и

МДР X выполняется соотношение X® с X = X.

Теорема 2.4. Алгоритмическая проблема нахождения ПМА для двукритериальной задачи упорядочивания с критериями вида МШМАХ (4), (5) является труднорешаемой. При этом для задачи размерности п

п—1

максимальная мощность ПМА ограничена снизу экспонентой 2

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

Рассматриваем нормированную ВЦФ

/■•(лЦ^м. ад).

где

Fj'(x) = ¡л• Fv(x) min, 1 < v < 2. ^ Hv = n-Tv Tq = Г- min А' Т=Щ.

1 i= I

Теорема 3.1. Пусть для всякой индивидуальной задачи упорядочивания её параметры Tj, Д. принимают конкретные значения из множеств , у, ф. Тогда, если множества ¿Д и у являются ограниченными множествами, то для любого при П —>• со пространство значений :. jceJ^ нормированной ВЦФ(6)-(7) представляет

собой ограниченное множество, т.е. значения величин

А = тах/гН(х)> у~1,2 ограничены сверху константой, которая не

зависит от размерности п .

Рис. 1 представляет диаграмму критериального пространства индивидуальной 2-критериальной задачи упорядочивания для случая, когда число объектов п — 5 и параметры 2-критериалыюй задачи упорядочивания получены с помощью генератора псевдослучайных чисел. При этом

для N = 2 ВЦФ (х),7^2(х)) состоит из критериев ^(х)"

вида МПЧБиМ (2) и ^(х)" виДа М1ЫМАХ (4), а параметры а.

случайные числа. На рис.2 представлена диаграмма для такой же задачи с тем лишь отличием, что второй критерий ^ ( х) , так же как и ^ ( х) ,

имеет вид МШЭиМ (2).

В параграфе 4 рассматривается вопрос о методологии фрактального анализа критериального пространства в контексте идей синергетики.

1ШЗиМ1-1ШМАХ2

3500000 3000000 * 2500000 2 2000000 5 1500000 2 1000000 500000

лшэим1

Рис.1

MINSUM1-MINSUM2

7000000 -r-6000000 - •

<N

g 5000000 - v

=> 4000000 -

I 3000000 - -

5 2000000 - -

w

1000000 --

0

MINSUM1

Рис.2

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

Заметим, что к настоящему времени не известно применение перечисленных выше методов и подходов к каким-либо дискретным многокритериальным задачам. Современное состояние исследований в данной области науки(«поп1шеаг science») характеризуется тем, что до настоящего времени методы нелинейной динамики разрабатывались применительно к задачам физики, химии, биологии и, отчасти, гуманитарных дисциплин.

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

С параметрами порядка связан такой показатель (признак) самоорганизации, как симметрия системы. Структурирование системы может означать нарушение её симметрии. Заметим, что С.П. Курдюмов формирует при помощи понятия симметрии аналог второго начала термодинамики («тотальная симметрия»- максимальная энтропия).

Вышеупомянутые методы нелинейной динамики базируются на методах анализа временных рядов и реконструкции аттракторов. Временной ряд - это упорядоченное множество значений г., ]- 1,2,.ДЛЯ которого естественным, упорядочивающим фактором выступает время или другой признак. В качестве такого «монотонного признака» используем первый критерий, что диктуется рассмотренным в параграфе 4 подходом к выбору и принятию решений методом последовательных уступок. С этой целью, занумеруем индексом ] допустимые решения д; еХ> } — 1 ,Ь, Ь= п\ в порядке не убывания значений первого критерия -^(-Ху) данной ВЦФ. Строим ряд

Ряд вида (8) обычно называют термином «траектория», которая рассматривается просто как ряд наблюдений, т.е. временной ряд.

Встает вопрос: что можно сказать о системе (в данном случае о 2-критериальной задаче упорядочивания), исходя из ряда (8)? Является ли поведение этой системы детерминированным, т.е. существует ли закономерность, которая обеспечивает полное определение поведения системы? В нашем случае рассматривается вопрос: как по известному начальному множеству ,...,2/ предсказать значения гм,1/+2, и т.д.?

Параграф 5 посвящен анализу 2-крнтериальной задачи упорядочивания методом псевдофазового пространства.

Располагая результатами компьютерного эксперимента в виде ряда (8), мы рассматриваем систему с одной степенью свободы, для которой получена последовательность

где ) ~ Р-1 (-^у ), а Х^ есть такое допустимое решение задачи упорядочивания, которое в представленной выше диаграмме находится на оси абсцисс на у — ом месте.

Цель использования метода псевдофазового пространства состоит в том, чтобы построить зависимость величины 2; =

Ж)

от значения этой же величины в другие моменты «времени»

или — .У^у+д) . При этом имеется основание считать информативным фазовое пространство размерности 2, т.е. в обозначениях (9) пространство точек в декартовых координатах

у = 1,2,.... (Ю)

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

В контексте методов визуализации рассмотрим следующую проблему, которая порождается чрезвычайно большими объемами вычислений. В процессе компьютерного эксперимента графики и диаграммы критериального пространства задачи упорядочивания реально получены для числа объектов упорядочивания п = 5,6,7 • Для значений п > 10 в процессе компьютерного эксперимента можно сгенерировать

лишь подмножество ^ С1, где - МДР задачи упорядочивания, а мощности X | и соотносятся как X = т.е. доля реше-

ний X € X стремиться к нулю с ростом П . Всвязи с этим возникает принципиальный вопрос: обладает ли подмножество представителей

У

всеми свойствами всего МДР Хч Положительный ответ на этот вопрос обосновывается с помощью графического представления серии отрезков траектории (9) и использовании методов визуализации. Причем, компьютерный эксперимент проведен для П = 7 и следующих вариантов комбинаций критериев (х) , Р2 (х), составляющих ВЦФ: 1)МШ811М,

МГШиМ; 2)МШМЛХ, МШБЬ'М; 3)МШ8иМ, МГКМЛХ; 4) МПЧМАХ, МШМАХ. Последовательность (9) и соответственно (10) состоят из я!=7!=5040 точек (элементов). Эти последовательности развивались-

где дисконтирующий множитель р^ и специальная функция 5§П у определяется следующим образом:

\0,у<0 1

Теорема 4.1. Для всякого п>2 существуют такие индивидуальные задачи упорядочивания с ЦФ вида МШБИМ, у которых множество оптимальных решений, полученных с учетом и соответственно без учета дисконтирования, не совпадают, и более того, не пересекаются.

Теорема 4.2. В случае ЦФ вида МШМАХ существуют такие индивидуальные задачи упорядочивания, у которых множество опти-мачьных решений, полученных с учетом и соответственно, без учета дисконтирования, не совпадают, и, более того, не пересекаются.

С целыо выявления достаточных условий для существования решающего правила для критериев с учетом дисконтирования рассмотрим ряд индивидуальных задач упорядочивания, для которых значения параметров ограничены следующим образом: =0, Т^ > 0, ОС■ > 0,

Е > 0, п — Поскольку решения каждой такой задачи оце-

ниваются ЦФ вида МГШиМ с учетом дисконтирования и все /). = 0, то для этих задач ЦФ имеет следующий вид

~ / л " ''к

К (.г) = ф{х) = X I а, Л -» шш' (11)

к=1 /=1 к

Достаточные условия существования решающего правила определяет следующая

Теорема 4.3. Если при О - =0, 1 = 1,п перестановка х® ,¿2 ) определяет невозрастающую последовательность значений О., к = \,п, так, что и соответствующая последовательность 1к

значений 7^ ,/с=1,п не убывает, то на перестановке х^ ,'2 '■•■'/г) ¡с

ЦФ вида МШ51]М с учетом дисконтирования (11) достигает минимума.

Из рассмотренных индивидуальных двукритериальных задач вытекает, что является справедливым

Утверждение 4.1. В общем случае являются различными паре-товские множества многокритериальных постановок задачи упорядочивания с учетом дисконтирования критериев её В ЦФ и без учета дисконтирования критериев её ВЦФ.

В заключении сформулированы основные результаты работы, которые состоят в следующем:

1. Построена и исследована био-эколого-математическая модель задачи упорядочивания в многокритериальной постановке;

2. Доказано, что рассматриваемая задача обладает свойством полноты в случае, когда ВЦФ состоит из критериев вида МШБиМ; из этого свойства выведена точная формула вычисления максимальной мощности искомого решения; из этой формулы вытекает утверждение в трудноре-шаемости задачи;

3. Доказано свойство квазиполноты в случае, когда ВЦФ состоит из критериев вида М1ЫМАХ; из этого свойства выведена экспоненциальная

нижняя оценка мощности искомого решения и, как следствие, утверждение о труднорешаемости задачи в случае, когда ВЦФ состоит из критериев вида МПЧМАХ;

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

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

6. Осуществлено обобщение исследуемой математико-биологической модели на случай, когда при оценке эффективности системы учитываются дисконтированные экономические критерии.

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

Основные положения диссертации опубликованы в следующих работах:

1 - Попова Е.В. Исследование мощности множества альтернатив дву-критериальной задачи инвестора. Карачаево-Черкесский технологический институт, 1996. Деп. в ВИНИТИ,№ 3711-В96.

2 . Перепелица В.А., Попова E.B. Исследование мощности множества альтернатив для двукритериальной задачи инвестора. В сб.: Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики. Тез. докл. международ. Конф. - Нальчик: НИИ ПМиА РАН, 1996. -С. 66.

3 . Перепелица В.А., Попова Е.В. Исследование мощности множества альтернатив многокритериальной задачи инвестора. «Математическое моделирование и компьютерные технологии» по материалам международного научного симпозиума «Экономика и право-стратегии 3000» 6-9 октября, Кисловодск 1996 , ~ С, У "79,

4 . Окопная В.А-А., Попова Е.В. Исследование многокритериальной задачи о штрафах. «XXIII Гагаринские чтения»: Тез.докл. молодежной научной конференции. Москва,8-12 апреля 1997.-М.:РГТУ-МАТИ. -с.гг

5 . Zinchenko О.А, Kochkarov A.M., Popova E.V. Multicriteria Problems of regulation when planning building processes. Internationales Kolloquium über Anwendungen der Informatik und Mathematik in Architektur und Bauwesen. 26.Februarbis Ol.Marz 1997 Weimar, y3.

6 . Перепелица B.A., Попова E.B. Оценки сложности многокритериальных задач теории расписаний. Информационный бюллетень Ассоциации математического программирования. №7 Научное издание. Екатеринбург: УрО РАН, 1997. -С. 176-177.

7 . Окопная В.А., Попова Е.В. Применение методов теории детерминированного хаоса к анализу дискретных многокритериальных задач. Вторая научно-практическая конференция Карачаево-Черкесского Технологического Института, 11-14 ноября., КЧТИ, Черкесск, 1997.

-с. вг.

8 . Окопная В.А., Перепелица В.А., Попова Е.В. Исследование критериального пространства и сложности одной задачи календарного планирования. «Математическое моделирование и компьютерные технологии» по материалам II международного научного симпозиума «Экономика и право-стратегии 3000» 24-26 апреля, Кисловодск 1997. " С.

9 . Popova E.V. Estimates of Complexity of the Vector Ordering Problem, Abstracts of Short Communications and Poster Sessions, International Congress of Mathematicians, 1CM'98, Berlin, August 18-27,1998

10 . Окопная B.A-A., Перепелица E.B., Попова E.B. Использование методологии нелинейных динамических систем в дискретной многокритериальной оптимизации. Карачаево-Черкесский технологический институт. 1998. Деп в ВИНИТИ №2619-В98

11 . Попова Е.В., Перепелица В.А. Использование задачи инвестора с учетом дисконтирования денежных потоков. Карачаево-Черкесский технологический институт. 1998. Деп. в ВИНИТИ №2620-В98

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

¿//М-

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РФ КАРАЧАЕВаЧЕРКЕССКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ

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

ТЕОРИИ РАСПИСАНИЙ

05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

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

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

Попова Елена Витальевна

/

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

Черкесск-1998

СОДЕРЖАНИЕ

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

ГЛАВА 1

ДИСКРЕТНЫЕ МАТЕМАТИЧЕСКИЕ МОДЕЛИ УПРАВЛЯЕМЫХ БИОТЕХНИЧЕСКИХ И АГРОБИОЛОГИЧЕСКИХ ПРОЦЕССОВ..................30

1.1. Два типа математико-биологических моделей........................................30

1.2. О задаче на перестановках для управляемых биотехнологических

процессов.....................................................................................................................32

1.3.0 задаче процесса утилизации биологических отходов.........................35

ГЛАВА 2

ОБОСНОВАНИЕ ОЦЕНОК СЛОЖНОСТИ ВЕКТОРНЫХ ЗАДАЧ УПОРЯДОЧИВАНИЯ.............................................................................................44

2.1 Векторная постановка задачи упорядочивания........................................... 44

2.2. Обоснование оценок вычислительной сложности.....................................46

ГЛАВА 3

ИСПОЛЬЗОВАНИЕ МЕТОДОЛОГИИ НЕЛИНЕЙНЫХ ДИНАМИЧЕСКИХ СИСТЕМ В ДИСКРЕТНОЙ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ. 56

3.1. Общее описание проблемы................................................................................56

3.2.К проблеме выбора и принятия решения.........................................................59

3.3.к представлению критериального пространства в контексте

методов теории принятия решений........................................................................60

3.4.0 методологии фрактального анализа критериального пространства в

контексте идей синергетики....................................................................................68

3.5.Классификации моделей и методологические вопросы их выбора ........ 75

3.6.анализ 2-критериальной задачи упорядочивания методом псевдофазового пространства...............................................................................78

ГЛАВА 4

ИССЛЕДОВАНИЕ ЗАДАЧИ УПОРЯДОЧИВАНИЯ С УЧЕТОМ ДИСКОНТИРОВАННЫХ ЭКОНОМИЧЕСКИХ КРИТЕРИЕВ.......................137

4.1. Дисконтирование затрат и результатов......................................................137

4.2. Векторная постановка задачи упорядочивания с учетом инфляции и дисконтирования.....................................................................................................141

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

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

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

ВВЕДЕНИЕ

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

До настоящего времени модели математической биологии в подавляющем большинстве отражают естественно сложившиеся процессы. Очень мало постановок, в которых отражается эффективность управляющих воздействий на этот или другой биологический процесс. Этим, в частности, можно объяснить весьма упрощенный вид известных к настоящему времени математических моделей управляемых биологических процессов, в частности, агробиологических [2,9,58], утилизационно-биологических [6] и эколого-биологических [7,58].

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

таточно сложных систем и объектов постановка скалярной (однокрите-риальной) задачи оптимизации не удовлетворяет потребностям лица принимающего решения (ЛПР)[15,27], в связи с тем, что построение обобщенных функций полезности (интегральной эффективности) является проблемой весьма сложной, а иногда и неразрешимой [60]. В то же время потребности практики разработки и эксплуатации сложных систем (в том числе биотехнологических, агробиологических, эколого-экономических и финансово-экономических [18]) требуют учета и согласования значительного числа разнородных требований и целей [12,36,53].

Актуальной научной проблемой является разработка принципиально иного подхода к отысканию наилучшего компромиссного решения. Предложенный в работе подход базируется на априорном знании структуры множества значений векторной целевой функции задачи в критериальном пространстве. В задаче упорядочивания, даже если количество объектов упорядочивания п = 10, совокупность альтернатив представляет собой множество большой мощности, которое ЛПР не в состоянии проанализировать. Если же структура этих значений известна, то при формировании множества альтернатив можно учесть механизм работы процедур системы поддержки принятия решений, которую использует лицо принимающее значение ЛПР. При знании структуры критериального пространства появляется возможность формировать множество альтернатив, которое обозримо для ЛПР. Более того, можно использовать метод ранжирования элементов множества альтернатив по убыванию их предпочтительности, т.е. полезности.

Цель и задачи работы. Основной целью работы является исследование сложности известной задачи упорядочивания теории расписаний в многокритериальной постановке и исследование её критериального пространства с целью выявления закономерностей изменения

значений одного критерия при монотонном изменении значений другого критерия (порядок или детерминированный хаос [42]?, фрактальная размерность [63]?, устойчивость или неустойчивость?, и сложность, и др.). Прикладная цель работы - обосновать механизм отсеивания "очевидно плохих решений" для последующего формирования возможно более ограниченного множества альтернатив, которое предъявляется на вход той или иной системы принятия решений.

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

Научная новизна. В работе доказано, что рассматриваемая задача обладает свойством полноты в случае, когда ВЦФ состоит из критериев вида ММвиМ; из этого свойства выведена точная формула вычисления максимальной мощности искомого решения; из этой формулы вытекает утверждение в труднорешаемости задачи. Так же доказано свойство квазиполноты в случае, когда ВЦФ состоит из критериев вида М1ЫМАХ; из этого свойства выведена экспоненциальная нижняя оценка мощности искомого решения и, как следствие, утверждение о труднорешаемости задачи в случае когда ВЦФ состоит из критериев вида М1ММАХ. Разработана и реализована на персональной электронно-

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

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

Достоверность полученных результатов. Представленные в диссертационной работе Теоремы и Леммы имеют строгое математическое обоснование. Результаты компьютерного эксперимента имеют массовую реализацию на многочисленных вариантах исходных данных.

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

списком симпозиуме «Экономика и право - стратегии 3000» (Кисловодск, 1998), на Международном коллоквиуме 1КМ'97(Веймар,1997), на Международном конгрессе математиков 1СМ'98(Берлин,1998), на заседаниях научного математического семинара КЧТИ, на Всероссийской международной конференции "Компьютерные технологии инженерной и управленческой деятельности" (Таганрог, 1998).

Глава 1 посвящена формулировке дискретных экстремальных задач, определенных на множестве перестановок [77]. Различным является содержательный смысл, который отражается в этих задачах. Одна из этих задач относится к проблеме утилизации биологических отходов, для которых важно учесть и их свойство "нескладируемости". Последнее означает, что поступающие на переработку массы с течением времени изменяют свои биологические свойства, в результате чего может теряться экономическая эффективность соответствующего управляемого процесса утилизации [6]. Вторая задача относится к проблеме технологического содержания, которая возникает в отраслях биохимической и фармацевтической промышленности [23,83,87,94].

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

Задача упорядочивания (задача одного станка) известна в одно-критериальной постановке [21,71]. В настоящей работе эта задача формулируется как многокритериальная. Математическая модель этой многокритериальной постановки состоит в следующем. Рассматриваются п объектов упорядочивания, перенумерованных индексом /=1,2,- продолжительность "реализации" I -го объекта или этапа, - "удельный штраф" или "ожидаемый эффект" за единицу

времени от / -го объекта, Ц - директивный срок "реализации" / -го объекта. Всякое допустимое решение задачи упорядочивания представляет собой одну из п\ перестановок х=(ц ,г2 чисел

1,2,...,П. Х= {•*}- множество всех допустимых решений (МДР) этой

задачи. На множестве ^^{х} всех и! перестановок оп~

ределена векторная целевая функция (ВЦФ)

= ), (1) состоящая из минимизируемых критериев, т.е. частных целевых функций (ЦФ)

Ру(х) е{ (ру{х), <р (х), у/у(х) (х)\, \<у< N,

V

где

п

9у{х) = шах - В^, 0)-> пип, (2)

<РУ (х) = Е а у шах (В? - ^, 0) пип, ^

Уу{х) = шах аУ шах - ВУ , 0) пип, (4)

1<к<п к к к

¥у(х) = шах а. шах (В. -, 0) тт.

1<к<п К к к

(5)

В литературных источниках критерии (2) и (3) зачастую называют соответственно терминами "критерий вида ММЗиМ", а (4) и (5)- "критерий вида М1ЫМАХ".

Допустимое решение хеХ называется парето-оптимальным или паретовским оптимумом (ПО), если не существует такого элемента

х*е1, что выполняются неравенства V = и хотя

бы одно из этих неравенств строгое.

Через X обозначим паретовское множество (ПМ), состоящее из всех ПО рассматриваемой задачи с ВЦФ (1) на МДР X.

Подмножество 1°с1 называется полным множеством альтернатив (ПМА), если его мощность минимальна и при этом выполняется равенство где = УХ* с! [46,49].

В Главе 2 получены оценки мощности ПМА двукритериальной задачи упорядочивания в зависимости от того, в какой комбинации критерии (2)-(4) входят в состав ВЦФ (1) (возможны следующие комбинации ММвиМ-М^ЭиМ, Л/ИЫвиМ-М^МАХ, М1ЫМАХ-М1ЫМАХ).

Лемма 2.1. Для ЦФ вида ММвС/М (2) существует такое множество значений параметров аьТьВь 1 = 1,и, что для любой пары выполняется неравенство <р(У) ф . В результате доказательства Леммы 2.1 получены следующие значения параметров для ЦФ вида М1Ы81)М (2), щ = 2™, /=1,2,...п, где

т=к^2и2, 1, /—1,7?, Ц = О, /=1,72, при который для любой пары выполняется неравенство <р(у) ф ^(х") ■ Лемма 2.2. Для ЦФ вида М1ЫЭиМ (3) существует такое множество значений параметров / = 1 ,п, что для любой пары

у, х" е Xвыполняется неравенство <р(х!) ф .

Используя технику доказательства Леммы 2.1 для Леммы 2.2 получены те же значения параметров для ЦФ вида ММЭиМ (3), а( = 2тг,

/=1,2,...и, где m=\og1n1, Tt = 1, i=l,n, Ц = 0, i=l,n, при который для

любой пары х!,х!'еХ выполняется неравенство ^ ■

Рассматривается двукритериальная задача упорядочивания, у которой размер "удельных штрафов" <^=2^,z'=l,2,...л, продолжительность 2^= 1 для всех объектов / = 1,и, а директивные сроки Д1 = 0,

— л -

/ = 1,л для критерия ^(х) вида (2) и Dl = Т= =п, i = \,n для кри-

i=1

терия /^(-х) вида (3), а качество допустимых решений хе J оценивается векторной целевой функцией

F(x) = ( F{(x), F2(x) ) (6)

с минимизируемыми критериями

F{(x) = ^(х) = Тк2мк —min,

(7)

F2(x) = (р2(х) = Z(n-k)2mik min (8)

k=1

Лемма 2.3. Если ВЦФ (6) определена согласно (7), (8), то для всякого допустимого решения х= (ц,12,-,1п)G X сумма

F](x) + F1(x) = С, где С- константа, которая не зависит от выбранной последовательности х.

Из Лемм 2.1, 2.2 и 2.3 вытекает, что всякая пара решений при определенных выше параметрах является векторно-несравнимой по ВЦФ (6)-(8), т.е. справедливы

Теорема 2.1. Двукритериальная задача упорядочивания с критериями вида MINSUM (2),(3) обладает свойством полноты, т.е. для всякого п существуют такие значения параметров

aj, Tt, DJ, i = Un, у=1Л, при которых ПМА Х°, ПМ X и МДР X совпадают.

Теорема 2.2. Алгоритмическая проблема нахождения ПМА для двукритериальной задачи упорядочивания с критериями вида М1Ы-Эим является труднорешаемой, т.е. вычислительная сложность этой задачи растёт экспоненциально с ростом размерности п.

Рассматривается исследуемая двукритериальная задача с критериями вида М1ЫМАХ.

Лемма 2.4. Нижняя оценка мощности \у/(Х)\=\{у/(х):х Х}\ множества значений критерия у/(х) вида М1ЫМАХ равна 2П~1.

Лемма 2.5. Верхняя оценка мощности \у/(Х)\ = \{у/(х)'.хеХ}\ множества значений критерия у/{х) вида М1ЫМАХ равна п2п~1.

Рассмотрим теперь ЦФ (5), определив значения её параметров следующим образом:

¿ = 1,2,..., п-\)лап = 2п;

Т,=2\ ¿ = 1,2(Ю)

Ц = 21п, I = 1,2,...,п. (11)

Тогда при значениях (9)-(11) параметров а^Т^И^ г = 1 ЦФ

(5) принимает вид

щ(х) = тахо,- (21п -и ), (12)

1 <к<п к к

где

к . . 1к 5=1 ^ 1к к к; (13)

к ;

15

*= 1 (14)

Далее определяем множество = на котором ЦФ (12) принимает значения

щх | = 21п -2патг_лх

(15)

В результате получаем что ЦФ (15) получает количество попарно различных значений, равное

т=\

т

п

_ v WW _ - L Cn_i - Z ,

т=1

(16)

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

Лемма 2.6. Нижняя оценка мощности у/(Х) = {у/{х):хеХ) множества значений критерия у/(х) вида MINMAXравна 2п~х. По аналогии с Леммой 2.5 является справедливой Лемма 2.7. Верхняя оценка мощности у/(Х) = {\[/{х):х<еХ\ множества значений критерия у/(х) вида MINMAX равна п2п~1.

По аналогии с Леммой 2.3 является справедливой Лемма 2.8. Если ВЦФ состоит из критериев вида MINMAX, то для всякого её допустимого решения х= (z^v-A) е X существуют такие значения параметров задачи упорядочивания, при которых суммаF{(x) + F2(x) = С, где С- константа, которая не зависит от выбранной последовательности х.

На основании Лемм 2.4-2.8 являются справедливыми Теорема 2.3. Двукритериальная задача упорядочивания с критериями вида MINMAX (