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

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

МЕДВЕДЕВ Сергей Николаевич

ОБОБЩЁННЫЕ МОДЕЛИ ЗАДАЧИ О НАЗНАЧЕНИЯХ И АДАПТИВНЫЕ АЛГОРИТМЫ ИХ РЕШЕНИЯ

Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

12 ДЕК 2013

Воронеж - 2013 005543964

005543964

Работа выполнена в ФГБОУ ВПО «Воронежский государственный университет»

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

Леденёва Татьяна Михайловна

Официальные оппоненты: Блюмин Семён Львович,

доктор физико-математических наук, профессор, ФГБОУ ВПО «Липецкий государственный технический университет», профессор кафедры прикладной математики

Матвеев Михаил Григорьевич,

доктор технических наук, профессор, ФГБОУ ВПО «Воронежский государственный университет», профессор кафедры информационных технологий управления

Ведущая организация: ФГБОУ ВПО «Тверской государственный университет»

Защита состоится «24» декабря 2013 г. в 15.10 на заседании диссертационного совета Д.212.038.20 при ФГБОУ ВПО «Воронежский государственный университет» по адресу: 394006, г. Воронеж, Университетская пл., д. 1.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Воронежский государственный университет».

Автореферат разослан «21» ноября 2013 г.

Ученый секретарь

диссертационного совета Л*Шабров Сергей Александрович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Для трёхиндексных и других многоиндексных задач о назначениях, которые являются NP-трудными, существует проблема построения алгоритмов для нахождения приближенного (субоптимального) решения. Усовершенствованию алгоритмов посвящено множество работ, в которых прослеживаются несколько основных подходов: постановка и решение ЗОН на графах (Y. Crama, L. Kaufman, Э. X. Гимади, H. М. Коркишко), построение алгоритмов на основе метода ветвей и границ с различными вариантами ветвления и фиксации переменных (Е. Balas, R. Е. Burkard, M. Vlach, Э. X. Гимади, И. П. Воз-нюк), применение метода лагранжевой «релаксации» (D. Magos, P. Camerini, M. К. Кравцов, С. А. Дичковская), модификация известных алгоритмов решения двухиндексных задач (L. Kaufman, С. И. Сергеев). Практически не проводятся исследования, связанные с построением быстрых «жадных» алгоритмов и повышением их эффективности. Известные методы такого типа (R. M. Aiex, JI. Г. Раскин, И. О. Кириченко) дают слишком «грубое» решение. Существует необходимость в их улучшении для работы с задачами больших размерностей, возникающими на практике, что возможно осуществить за счёт построения итеративного алгоритма, учитывающего результаты предыдущих шагов.

Обобщённые ЗОН с интервальными и нечёткими данными возникают в результате формализации неопределённости, присущей многим практическим задачам. Для них не существует единого подхода в определении понятия оптимальности решения и условий его существования, поэтому различны и подходы к построению алгоритмов решения (R. Е. Steuer, F. Mraz, В. И. Левин, С. П. Шарый), что является стимулом к дальнейшему исследованию в этой области.

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

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

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

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

Для достижения цели в диссертации решаются следующие задачи:

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

2. Разработка адаптивных методов для решения аксиальной и планарной трёхиндексных ЗОН.

3. Разработка модели многокритериальной трёхиндексной ЗОН и адаптивных методов ее решения.

4. Развитие подходов к определению оптимальности решения для ЗОН в условиях неопределённости и нахождению области его устойчивости.

5. Разработка программного обеспечения для решения трёхиндексных задач о назначениях и задач с неточными данными.

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

Результаты, выносимые на защиту, и их научная новизна:

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

2) утверждения, определяющие вид условия локального улучшения для каждой из трёхиндексных задач, позволяющие построить адаптивные аналоги «жадных» алгоритмов за счёт перехода к вероятностной постановке задачи и модификации процедуры поиска минимального элемента;

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

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

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

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

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

Область исследования. Тематика работы соответствует следующим пунктам Паспорта специальности 05.13.18 «Математическое моделирование, численные методы и комплексы программ»: п. 2. «Развитие качественных и приближенных аналитических методов исследования математических моделей»; п. 3. «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий»; п. 4. «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента».

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

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

Предложенные в диссертации подходы к решению различных ЗОН позволяют повысить обоснованность принимаемых решений в сложных системах различного назначения, в том числе, при оптимизации вычислительных и производственных процессов. Практические результаты диссертации в форме программного комплекса используются в деятельности ОГБУ «Агентство по инвестициям и стратегическим проектам» (акт№ 51/1-01-11-542).

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях: Международная конференция «Современные методы прикладной математики, теории управления и компьютерных технологий» (Воронеж, 2013); Международная конференция «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 2012); VI Международная научно-техническая конференция «Аналитические и численные методы моделирования естественнонаучных и социальных проблем» (Пенза, 2011); Ежегодная международная конференция КРОМШ (Симферополь, 2010-2011); Международная школа-семинар «Системное моделирование социально-экономических процессов» (Воронеж, 2008), а также на ежегодных научных конференциях Воронежского государственного университета.

Публикации. Основные результаты диссертации отражены в 13 опубликованных работах, в том числе, 4 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве, лично соискателю принадлежит: [1, 2] - решение задачи по /¡; [2] - математическая модель многокритериальной трёхиндексной ЗОН; [4] - утверждение о сведении полной нечёткой ЗОН к задаче с нечёткой целевой функцией, алгоритм решения на основе венгерского метода; [5] - «жадные» алгоритмы решения трёхиндексной ЗОН; [б] - детальная разработка «жадного» и адаптивного алгоритмов; [9] - переход от нечёткой к интервальной ЗОН, алгоритм решения нечёткой задачи с использованием адаптивного алгоритма; [10] - модуль программы, связанный с использованием приближённой информации при решении задач в условиях неопределённости; [11] - адаптивный алгоритм решения трёхиндексной ЗОН, исследование возможности корректировки целевых коэффициентов стандартной ЗОН при сохранении оптимального решения.

Объём и структура работы. Диссертация состоит из введения, четырёх глав, заключения, списка используемых источников из 169 наименований и приложения; изложена на 147 страницах основного текста и включает 30 рисунков и 15 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассматриваются обобщения стандартной ЗОН (I). Её математическая модель имеет следующий вид

= min (1)

ы j=\

¿*s = l(/ = ü), (2) i>V=l(/ = M), (3) (D

/=1 7=1

*, = {0,l}(i.y = ÜO- (4)

Обобщениями стандартной ЗОН являются аксиальная (II) и пленарная (III) трёхиндексные ЗОН, относящиеся к JVP-трудным задачам.

т = Ц±44 min L(X) = £i±ctf -» min

7=1 *=■ ы

¿2Х=1(;=Ч)> ("> ¿** = 1(а=й), (Ш)

1=1 *=1 7=1

'-1 7=1 *=1

X* ={0,1} (/,7, к = Щ. =

Приводится обзор основных теоретических результатов для перечисленных задач и методов их решения. Установлено, что наиболее перспективными

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

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

Во второй главе рассмотрены возможности расширения базовых алгоритмических схем «жадного» типа для решения ЗОН и её трёхиндексных обобщений посредством перехода к вероятностной постановке на основе рандомизации переменных. Суть перехода заключается в том, что задача вида

L(X) min (5)

А'еП

заменяется задачей минимизации математического ожидания, т.е.

M(Z,(X))-> min , (6)

где {X} - множество случайных величин X с реализациями X из множества Q..

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

В диссертации разработан комплекс численных методов, включающий адаптивные алгоритмы решения стандартной ЗОН (I), аксиальной (И), планар-ной (III) и многокритериальной трёхиндексных ЗОН.

Математическая модель многокритериальной ЗОН (IV) имеет вид

т т пк

L,(X1) = £X44->mm ... =

¡=1 f=l J=!

т _ __К % _

][>*=1(*=1,К,./ = 1,«Д =1,1»), (IV)

_ __*=i М

x-j ={0,1} (i = l,m, k = l,KJ = l,nk).

Для перехода к вероятностной постановке (6) для каждой из задач I-IV специальным образом вводится рандомизация переменных, и задаются полные группы событий (FullGroup) (табл. 1). Пусть xt) (**) - элемент матрицы назначений; Ап (Л*) - событие, которое заключается в том, что хи=\ (х* =l), т.е. д.. =[*.. = 1] ( л* = [** = 1]). С данным событием свяжем булеву случайную величину ХДХ*), такую, что

(1, если произошло событие /I., ^ = f 1, если произошло событие Д*, « (0, иначе, " |0, иначе.

Каждая из случайных величин Xv (х*.) представляет собой индикатор события А,; [А]) 11 задаётся рядом распределения, содержащим два возможных значения 1 и 0, которые случайная величина принимает с вероятностью prj (/;*)

И -Р„ (^=1 -р1) соответственно, т.е. йу=Р(Д,) (р* = Р(л£)). Общая схема для построения адаптивных методов включает: Этап 1. Задание движения во множестве случайных величин {X}. Этап 2. Решение неравенства - условия локального улучшения (УЛУ)

Л/(£(Х"+,))-м(£(х")) = Мх,л (Мх„ (1(х™)-£(х"))) < 0. (7) Этап 3. Пересчёт вероятностей в соответствии с результатом УЛУ.

Таблица 1 - Рандомизация переменных

Рандомизация Полные группы событий (ри1Югоир)

1 Х = [Х, ... Х„]' - матрица, X, =(ХЯ, ..., Хй ) - строка матрицы X, Х„ - индикатор, где у = 1, п. V/ = Ц7 (РиПвгоирЦ) = {4}^)

11 X = [X1 ... X"] - трёхмерная матрица, X* = [Х|" ... X* ]т - матрица размера я х я, X* = (Х*, ..., X*) - строка матрицы X*, X* - индикатор, где ¡, ],к = 1,и . Ук = (Ги1Югоир(к) = {Д'}()

111 Аналогично II. V/",* =Пй (ШЮгопр{1,к) = ъ, к=1

К =[<(,) =1 ('=ми. К = Vк = ЩРиПвгоирЮ = ) УА- =1,77 ^ р* = 1 , - множество и«. ) перестановок чисел {1, ..., п}

IV Х=[Х' ... Х*] - трёхмерная матрица, X* =[Х^ ... X*]т - матрица размера пхпк, X* = (Х^, ..., X* ) - строка матрицы Хк, X*. - индикатор, где / = 1,77,у = 1 ,пк, к = \,К. V* = ЩриПвПир{ 0 = к

V/ = ц; V* = Тл{ри1Юппф{],к) = Ц'},-)

Рассмотрим подробнее каждый из этапов метода.

Этап 1. Для всех задач используется следующая формула, задающая движение во множестве случайных величин:

Х/",=иХл'+иУлч\ (8)

где У™ е {X} - случайная величина, определяющая направление движения на (Лг +1)-м шаге, и - индикатор, такой, что Р(и = 1) = ри, Р(и = 0) = ди=1 -ри.

В диссертации доказано следующее

Утверждение I. Если движение задаётся формулой (8), то УЛУ (7) можно записать в виде неравенства

МХ(МУ(ЦУ^)-ЦХ-Ы)))<0. (9)

Этап 2. Наполнение данного этапа производится на основе введённых в табл. 1 полных групп событий и следующих утверждений, доказанных с учётом того, что УЛУ выполняется для реализаций случайных величин.

Утверждение 2. Условие локального улучшения (7) для вероятностной постановки задачи (I) имеет вид

а»)

м+1 у V ¡=;+1 / для фиксированного I = \,п и произвольных номеров.?, /г.

Утверждение 3. Условие локального улучшения (7) для вероятностной постановки задачи (II) представимо в виде

л- 111 j г-1

J J

к , к \N

V*=;+i y=i ы+i i=i

<0

(11)

для фиксированного / = l,w, и произвольных номеров г, s,q,h.

Утверждение 4. Условие локального улучшения (7) для вероятностной постановки задачи (III) представимо в виде

с'ь-{± + ±4(pDn)-(«£ - f t Mf +1]] < 0, (12)

Vi-r+l 1=1* I J V Vi=r+1 i=J+l JJ

для фиксированных /, г = 1 ,n, и произвольных номеров s,h, а также

Ii« -il ± <®cpt<o)w]-iZcU -iz 1(i3)

i=i V f=i *=/+i J v <'=1 v w 1 У у

для фиксированного 1 = 1,п, и произвольных перестановок <р, у/ из .

Установлено, что адаптивный алгоритм решения задачи (IV) в обоих вариантах задания полных групп событий (табл. 1) и при соответствующей перенумерации индексов сводится к алгоритму решения задачи (I).

Этап 3. Для гарантированного выполнения неравенств (10)-(13) при фиксированных номерах q, h и перестановки <р номера г, s и перестановка ц/ выбираются таким образом, чтобы выражения, являющиеся вычитаемыми в формулах (10)-(13), были минимальными. На основе решения УЛУ для каждой из задач пересчитываются вероятности, например, для аксиальной трёхиндексной ЗОН (II) в результате решения неравенства (11) пересчёт вероятностей осуществляется следующим образом:

если nun < crs -

j=i *=f+i 1=1

j-i

(14)

(15)

(ptr'-ipif (k = l+l,n,i,j = U). (16)

Таким образом, условие локального улучшения позволяет модифицировать соответствующий шаг базового «жадного» метода следующим образом: при фиксированном к вместо min^ с* = c*v

п п п и

вы числит ь min {с* - ( X Z 4 (-Р'ч )" + X 2cUpL )" '.)) =

■-<t + t > (17)

гЭе J-множество номеров j, I -множество номеров i, зафиксировать = 1 (для получения рекордов).

Адаптивный метод для решения задачи (II) представлен на рис. 1. Начальные данные:

V/t = М :((/>*)'= Л'ГИ,> Л' = 1

Рисунок 1 - Блок-схема адаптивного алгоритма решения задачи (П) Установлено, что вычислительная сложность каждой итерации данного алгоритма есть 0(и4). В диссертации предложен способ построения дополнительной (адаптивной) кубической матрицы С, позволяющий уменьшить вычислительную сложность до 0("3)-

Аналогичным образом в диссертации строятся адаптивные алгоритмы для остальных задач I и III, учитывающие различные способы формирования полных групп событий (см. табл. 1).

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

В третьей главе представлены результаты исследования ЗОН с интервальными и нечёткими коэффициентами, а также методы их решения.

Интервальная ЗОН вводится на основе стандартной модели (1)-(4), в которой целевая функция (1) заменяется на функцию вида

_ ¡=i}-1_

где L{X)=[L(X), Д1)], с, =[£,,<•„] (i,j=U).

Согласно правилам сравнения интервалов, целевую функцию (18) можно переписать в виде пары функций

1(А') = ££сЛ->тт, (19) L(X) = min, (20)

;=t у-1 ¡«1 j=i

и тогда интервальная задача с целевой функцией (18) и стандартными ограничениями (2)-(4) разбивается на верхнюю ЗОН (19), (2)-(4) и нижнюю ЗОН (20), (2)-(4), которые являются полностью детерминированными.

Известно следующее определение оптимальности.

Определение 1. Точка х е С1 является оптимальным решением задачи условной оптимизации <р(х) —> min, если V х е £2 (<7>(х) > cp(x')j.

Для интервальных функций определение 1 не всегда позволяет найти оптимальное решение. В связи с этим в диссертации предлагается

Определение 2. Точка х' ей. является оптимальным решением задачи условной оптимизации гр(х) -» min , если не существует х е П такого, что выполняется неравенство <р(х) < <р(х'), т.е. ->(з х е Q (<р(х) < <р(*'))) ■

Заметим, что для детерминированных задач оптимизации данные определения эквиваленты, так как V х е Q (<р(х) > = ->(з х е Q (V/>(x) < 9>(х*))).

Множество оптимальных решений интервальной ЗОН по определению 1 задаётся как пересечение множеств решений нижней и верхней задач, а соответствующее значение целевой функции как интервал L* = L ]. Если же пересечение пусто, то оптимального решения по определению 1 не существует.

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

Утверждение 5. Любое оптимальное решение X нижней ЗОН является оптимальным для соответствующей интервальной ЗОН по определению 2.

Утверждение б. Любое оптимальное решение X* верхней ЗОН является оптимальным для соответствующей интервальной ЗОН по определению 2.

Следствие. Значения интервальной целевой функции (18) для решений Х_' и X* связаны соотношением L(X ) = [L, L ] с I.(X^) =\lL, Ц-

Рассмотрим задачу с целевой функцией вида

1 w = Zi>»+ шш (21>

/.] j.1

и ограничениями (2)-(4), которую назовём возмущённой для ЗОН (1)-(4).

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

11

Утверждение 7. В задаче (1)-(4) оптимальное назначение X' не изменится, если коэффициенты целевой функции, соответствующие небазисным координатам с,, ((/, У) г /„), увеличить на любое число Ас&. > 0 ((г1, _/) £ ).

Утверждение 8. В задаче (1)-(4) оптимальное назначение X' не изменится, если коэффициенты, соответствующие базисным координатам ((7,у) е Iв) уменьшить на любое число Л е., > 0 ((г,/) е /й).

Утверждение 9. В задаче (1)-(4) оптимальное назначение X* не изменится, если коэффициенты целевой функции^. ((<,7)е/и), для которых соответствующая базисная координата = 0, увеличить на любое число Лс1; > О

ГДе 7а> ={0',Л:0'>У)е/в, =0}.

На основании утверждений 7-9, а также известного факта, что, если все оценки = СтвХу - Су = СвВ~'Аи - е.. < 0 (/,; = 1,«), где - разложение столбца Ад по базису В, то полученное решение оптимально для задачи минимизации, для оптимального назначения ЗОН (1)-(4) можно задать область устойчивости, определение которой дано в диссертации.

Утверждение 10. Область устойчивости оптимального назначения X' задачи (1)-(4) является множеством решений системы линейных неравенств

А С^-Ц, - А с, < -А, ((/, 7) Ив). (22)

Данное утверждение создаёт основу для исследования интервальной задачи (18), (2)-(4). Заметим, что в результате её решения могут возникнуть следующие ситуации: найдено оптимальное решение по определению 1 или найдены два оптимальных решения в смысле определения 2.

В первом случае возможно найти область устойчивости оптимального решения, при этом формула (22) примет вид

4 - ЛсГ. < -Ад ((;,./) £1В), (23)

ДС^'Ц - А с, < -А, ((м) Цв). (24)

Кроме того, добавляются ограничения на приращения

Щ ^ £и - Сц > д£/ ^ ^ " <ч, ('">•/ =") • (25)

Совокупность условий (23)-(25) задаёт область устойчивости оптимального решения интервальной задачи о назначениях.

В случае, когда найдены два оптимума X и X по определению 2, задачу можно переформулировать: найти изменения целевых коэффициентов, при которых задача (18), (2)-(4) будет иметь оптимальное решение по определению 1.

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

Утверждение 11. Если А= удовлетворяют неравенствам

лгг>£7-с5(/,у=й), (26)

то оптимальное решение ¿ нижней задачи становится оптимальным (по определению 1) и для интервальной ЗОН.

12

Утверждение 12. Если Ас:] (i,j = \,n) удовлетворяют неравенствам

= (27)

то оптимальное решение X верхней задачи становится оптимальным (по определению 1) и для интервальной ЗОН.

Утверждение 13. Если полная нечёткая ЗОН (A. Kumar, A. Gupta, А. Kaur), в которой переменные и целевые коэффициенты являются неотрицательными треугольными нечёткими числами, имеет единственное решение X', то оно является оптимальным и для ЗОН с нечёткой целевой функцией

£ £гЛ-*пип (28)

¡=1 J=]

и стандартными ограничениями (2)-(4), и не может быть нечётким.

Известно, что при заданном уровне а целевые коэффициенты cs становятся интервалами {_cij,c'iJ]a, и нечёткая ЗОН (28), (2)-(4) преобразуется в интервальную задачу (18), (2)-(4). На основании этого предлагается приближённый алгоритм решения задачи (28), (2)-(4), который содержит следующие этапы.

Этап 1. Задаётся множество уровней и для каждого ак

{к = 1, AT) предложенным в диссертации способом строится матрица D"'.

К

Этап 2. Формируется матрица D = ^ О"1 и нормируется по строкам.

к=I

Этап 3. На данном этапе реализуется один из следующих вариантов:

3.1. К коэффициентам целевой функции (28) применяется функция ранга, а затем полученная ЗОН решается адаптивным методом с начальным распределением вероятностей, заданным матрицей D.

3.2. Решается на максимум ЗОН с матрицей затратD.

В четвёртой главе описана структура программного комплекса «Алгоритмы решения обобщённых задач о назначениях», реализованного в среде Borland Delphi 7.0 и предназначенного для решения рассмотренных ЗОН (рис. 2).

Модуль ввода данных

Выбор типа данных

Выбор задачи

Выбор алгоритма решения

JEL

Задание параметров алгоритма

Выбор способа представления ответа

Модуль обработки приближённой информации

Вывод ответа

Библиотека методов

Венгерский метод

Реализация «жадных» алгоритмов

Алгоритм с последовательным применением венгерского метода

Алгоритмы поиска минимального элемента

Реализация адаптивных алгоритмов

Инициализация вероятностей

Создание адаптивной матрицы +

Пересчёт вероятностей

Рисунок 2 - Структура программного комплекса 13

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

С использованием программного комплекса был проведён вычислительный эксперимент, анализ результатов которого позволяет сделать следующие выводы:

1) Адаптивные методы дают значения целевых функций (ЦФ) существенно лучше (рис. 3), чем соответствующие базовые, а именно, для задачи (И) h^0,6-L6a3, для задачи (III) LM «0,75-i^ ,Ьадтт2 «0,8-L^; _

'S о а

я з

а а

я

а -е-

150 120 90 60 30 0

-П

«Жадный» Адаптивный (10 Адаптивный (50 Адаптивный (100 итераций) итераций) итераций)

Случайное заполнение матрицы числами

от 1 до 10

. * от 1 до 50

О от 1 до 100

Рисунок 3 - Зависимость значения целевой функции от выбранного алгоритма для аксиальной ЗОН размерности 50 х 50 х 50

2) При фиксированном количестве итераций лучшие значения ЦФ достигаются при значении параметра ри <0,1;

3)Время выполнения одной итерации мало, и для задач размерности 100x100x100 составляет для (И) 1гЛтю «0,06с, для (III) «0,1 с, tM «2 с;

4) Время работы алгоритмов линейно зависит от количества итераций;

5) Для задачи (И) при небольшом разбросе значений элементов матрицы относительно размерности задачи адаптивный метод решает задачу точно! При размерности задачи 100x100x100 и равномерном распределении чисел от 1 до 10 метод даёт оптимальное значение ЦФ, равное 100, при 50 итерациях.

Таблица 2 - Характеристики адаптивных алгоритмов

100x100x100 10 итераций 100 итераций

^adntim ! ^'ütn Время, с ^адапт / Айн Время, с

Алгоритм для задачи (II) 0,67 0,76 0,61 7,68

Алгоритм 1 для задачи (III) 0,81 1,005 0,75 10,18

Алгоритм 2 для задачи (1П) 0,85 23,46 0,8 254,3

В табл. 2 указаны отношения средних значений целевых функций адаптивного и соответствующего базового алгоритмов, время работы адаптивных алгоритмов для задач размерности 100x100x100 при равномерном распределении значений элементов матриц от 1 до 100, ри = 0,1.

В заключении излагаются основные результаты диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. На основе анализа существующих методов решения трёхиндексных аксиальной и планарной ЗОН сделан вывод о необходимости модификации «жадных» алгоритмов решения с целью повышения их эффективности.

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

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

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

5. Доказано утверждение о том, что в полной нечёткой оптимальное решение не может быть нечётким, поэтому рассматривается задача только с нечёткой целевой функцией, для которой предложен приближённый метод решения.

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

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

Публикации в изданиях, рекомендованных ВАК РФ

1. Медведев С. Н. Использование двойственных методов для решения одной многокритериальной задачи о назначениях / О. А. Малюгина, С. Н. Медведев, Г. Д. Чернышева // Вестник Воронеж, гос. ун-та. Серия : Системный анализ и информационные технологии. -Воронеж : Воронеж, гос. ун-т., 2010. -№ 1. -С. 31-34.

2. Медведев С. Н. Использование двойственных методов для решения трёх-индексной задачи о назначениях / О. А. Медведева, С. Н. Медведев, Г. Д. Чернышева // Вестник Воронеж, гос. ун-та. Серия : Системный анализ и информационные технологии. - Воронеж : Воронеж, гос. ун-т., 2011. - № 2. - С. 32-35.

3. Медведев С. Н. Нахождение области устойчивости интервальной задачи о назначениях / С. Н. Медведев // Вестник Воронеж, гос. тех. ун-та. - Воронеж : Воронеж. гос. тех. ун-т., 2011. -Том 7, № 10. -С. 51-54.

4. Медведев С. Н. О нечёткой задаче о назначениях / С. Н. Медведев, Т. М. Леденёва // Вестник Белгородского государствешюго технического университета им. В. Г. Шухова. - Белгород: БГТУ, 2012. - С. 154-157.

Статьи и материалы конференций

5. Медведев С. Н. Задача комплектования штатов / О. А. Малюгина, С. Н. Медведев, Г. Д. Чернышева // Системное моделирование социально-экономических процессов : труды 31-й Междунар. шк.-сем., Воронеж, 1-5 октября 2008г. -Воронеж: Воронеж, гос. ун-т., 2008. -Ч. П1. - С. 265-272.

6. Медведев С. Н.Использование адаптивных алгоритмов для решения трёх-индексной задачи о назначениях / С. Н. Медведев, Г. Д. Чернышева // Вест, факуль-

тета прикладной математики, информатики и механики. - Воронеж : Воронеж, гос. ун-т., 2010.-Вып. 8,-С. 148-155.

7. Медведев С. Н. Алгоритмизация задач, возникающих при комплектовании штатов / С. Н. Медведев, Г. Д. Чернышова // КРОМШ-2010 : Тез. довел. 21-ой ежегод. Междунар. конф. - Симферополь : изд-во КНЦ НАНУ, 2010. - С. 53.

8. Медведев С. Н. Многокритериальная трехиндексная задача о назначениях / Г.Д. Чернышова, О.А. Малюгина, С.Н. Медведев // КРОМШ-2011 : Тез. докл. 22-ойежегод. Междунар. конф. - Симферополь : изд-во КНЦ НАНУ, 2011. - С. 55. http://www.kromsh.info/files/abstracts/abstraets-2011 .рс1Г

9. Медведев С. Н. Применение адаптивного алгоритма для решения нечёткой задачи о назначениях / О. А. Медведева, С. Н. Медведев // Аналитические и численные методы моделирования естественнонаучных и социальных проблем : сб. ст. VI Междунар. науч.-техн. конф., Пенза, 25-29 октября 2011г. - Пенза: АННОО «Приволжский Дом знаний», 2011. - С. 78-81.

10. Медведев С. Н. Программный комплекс для решения различных модификаций задачи о назначениях / О. А. Медведева, С. Н. Медведев // Матер. Всерос. мо-лодежнар. научи, шк., Воронеж, 29-30 июня 2012г. - Воронеж: ООО ИПЦ «Научная книга», 2012,-С. 191-192.

11. Медведев С. Н. Задача комплектования штатов / О. А. Медведева, С. Н. Медведев // Актуальные проблемы прикладной математики, информатики и механики : сб. тр. Междунар. конф., Воронеж, 26-28 ноября 2012 г. : в 2 ч. - Воронеж : Из-дательско-полиграфический центр Воронеж, гос. ун-та, 2012. -Ч. 2. - С. 203-208.

12. Медведев С. Н. Адаптивные алгоритмы решения трёхиндексных задач о назначениях / С. Н. Медведев // Современные методы прикладной математики, теории управления и компьютерных технологий: сб. тp.VI Междунар. конф., Воронеж, 10-16 сентября 2013г. - Воронеж : Воронеж, гос. ун-т., 2013. - С. 153-156.

13. Медведев С. Н. Интервальная задача о назначениях. Анализ решения / С. Н. Медведев // Современные методы прикладной математики, теории управления и компьютерных технологий: сб. тр. VI Междунар. конф., Воронеж, 10-16 сентября 2013г. - Воронеж : Воронеж, гос. ун-т., 2013. - С. 156-158.

Свидетельства о государственной регистрации программ для ЭВМ

14. Медведев С. Н. Программный комплекс для решения многокритериальной трёхиндексной задачи о назначениях / О. А. Медведева, С. Н. Медведев // Свидетельство о гос. регистрации программы для ЭВМ №2012617580, РФ, 2012.

15. Медведев С. Н. Программный комплекс для решения различных модификаций задачи о назначениях / О. А. Медведева, С. Н. Медведев // Свидетельство о гос. регистрации программы для ЭВМ №2012618203, РФ, 2012.

Подписано в печать 19.11.13. Формат 60x84 '/„. Усл. печ. л. 0,93. Тираж 100 экз. Заказ 1218.

Отпечатано с готового оригинал-макета в типографии Издательско-полихрафического центра Воронежского государственного университета. 394000, Воронеж, ул. Пушкинская, 3

ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

04201452211

Медведев Сергей Николаевич

ОБОБЩЁННЫЕ МОДЕЛИ ЗАДАЧИ О НАЗНАЧЕНИЯХ И АДАПТИВНЫЕ АЛГОРИТМЫ ИХ РЕШЕНИЯ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

ДИССЕРТАЦИЯ

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

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

доктор технических наук, профессор

Леденёва Татьяна Михайловна

Воронеж-2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.........................................................................................4

ГЛАВА 1. ПОСТАНОВКИ ОБОБЩЁННЫХ ЗАДАЧ О НАЗНАЧЕНИЯХ И ИХ КЛАССИФИКАЦИЯ............................................................................10

1.1 Многоиндексные обобщения задачи о назначениях................................10

1.1.1 Классификация задач о назначениях.................................................11

1.1.2 Постановки трёхиндексных задач о назначениях.................................14

1.1.3 Обзор научных результатов для аксиальной трёхиндексной задачи о назначениях................................................................................16

1.1.4 Обзор научных результатов для планарной трёхиндексной задачи о назначениях................................................................................19

1.2 Обзор задач о назначениях в условиях неопределённости........................22

1.2.1 Типы данных..............................................................................23

1.2.2 Переход к вероятностной постановке задачи.......................................25

1.2.3 Основные понятия для работы с интервальными величинами..................27

1.2.4 Понятие нечёткого числа...............................................................30

1.2.5 Обзор задач оптимизации в условиях неопределённости........................32

1.3 Цель и задачи исследования..............................................................37

Выводы по главе 1................................................................................40

ГЛАВА 2. АДАПТИВНЫЕ АЛГОРИТМЫ РЕШЕНИЯ ТРЁХИНДЕКСНЫХ ЗАДАЧ О НАЗНАЧЕНИЯХ....................................................................42

2.1 Построение адаптивного алгоритма решения для стандартной задачи о назначениях...................................................................................43

2.2 Многокритериальная трёхиндексная задача о назначениях......................56

2.3 Аксиальная трёхиндексная задача о назначениях...................................62

2.4 Планарная трёхиндексная задача о назначениях....................................74

Выводы по главе 2...............................................................................95

ГЛАВА 3. ОБОБЩЁННЫЕ ЗАДАЧИ О НАЗНАЧЕНИЯХ В УСЛОВИЯХ НЕОПРЕДЕЛЁННОСТИ.......................................................................97

3.1 Постановка интервальной задачи о назначениях. Существование оптимального решения...................................................................98

3.2 Нахождение области устойчивости оптимального решения стандартной задачи о назначениях....................................................................103

3.3 Анализ решения интервальной задачи о назначениях...........................111

3.4 Нечёткая задача о назначениях с нечёткими коэффициентами................118

Выводы по главе 3...............................................................................128

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

4.1 Описание программного обеспечения...............................................130

4.2 Вычислительный эксперимент........................................................134

4.2.1 Алгоритмы решения аксиальной трёхиндексной задачи о назначениях.... 135

4.2.2 Алгоритмы решения планарной трёхиндексной задачи о назначениях.....140

Выводы по главе 4...............................................................................144

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

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ.......................147

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ......................................148

ПРИЛОЖЕНИЯ................................................................................165

Приложение А..................................................................................166

Приложение Б...................................................................................167

Приложение В..................................................................................168

Приложение Г...................................................................................172

ВВЕДЕНИЕ

Актуальность темы исследования и степень разработанности проблемы.

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

Для трёхиндексных и других многоиндексных задач о назначениях, которые являются АТ'-трудными, существует проблема построения алгоритмов для нахождения приближённого (субоптимального) решения. Усовершенствованию алгоритмов посвящено множество работ, в которых прослеживаются несколько основных подходов: постановка и решение ЗОН на графах (Y. Crama, L. Kaufman, Э. X. Гимади, H. М. Коркишко), построение алгоритмов на основе метода ветвей и границ с различными вариантами ветвления и фиксации переменных (Е. Balas, R. Е. Burkard, M. Vlach, Э. X. Гимади, И. П. Вознюк), применение метода лагранжевой «релаксации» (D. Magos, P. Camerini, M. К. Кравцов, С. А. Дичковская), модификация известных алгоритмов решения двухиндексных задач (L. Kaufman, С. И. Сергеев). Практически не проводятся исследования, связанные с построением быстрых «жадных» алгоритмов и повышением их эффективности. Известные методы такого типа (R. M. Aiex, Л. Г. Раскин, И. О. Кириченко) дают слишком «грубое» решение. Существует необходимость в их улучшении для работы с задачами больших размерностей, возникающими на практике, что возможно осуществить за счёт построения итеративного алгоритма, учитывающего результаты предыдущих шагов.

Обобщённые ЗОН с интервальными и нечёткими данными возникают в результате формализации неопределённости, присущей многим практическим задачам. Для них не существует единого подхода в определении понятия оптимальности решения и условий его существования, поэтому различны и подходы к построению алгоритмов решения (R. Е. Steuer, F. Mraz, В. И. Левин, С. П. Шарый), что является стимулом к дальнейшему исследованию в этой области.

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

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

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

Для достижения цели в диссертации решаются следующие задачи:

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

2. Разработка адаптивных методов для решения аксиальной и планарной трёхиндексных ЗОН.

3. Разработка модели многокритериальной трёхиндексной ЗОН и адаптивных методов ее решения.

4. Развитие подходов к определению оптимальности решения для ЗОН в условиях неопределённости и нахождению области его устойчивости.

5. Разработка программного обеспечения для решения трёхиндексных задач о назначениях и задач с неточными данными.

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

Результаты, выносимые на защиту, и их научная новизна:

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

2) утверждения, определяющие вид условия локального улучшения для каждой из трёхиндексных задач, позволяющие построить адаптивные аналоги «жадных» алгоритмов за счёт перехода к вероятностной постановке задачи и модификации процедуры поиска минимального элемента;

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

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

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

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

Область исследования. Тематика работы соответствует следующим пунктам Паспорта специальности 05.13.18 «Математическое моделирование, численные методы и комплексы программ»: п. 2. «Развитие качественных и приближенных аналитических методов исследования математических моделей»; п. 3. «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий»; п. 4. «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента».

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

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

Предложенные в диссертации подходы к решению различных ЗОН позволяют повысить обоснованность принимаемых решений в сложных системах различного назначения, в том числе, при оптимизации вычислительных и производственных процессов. Практические результаты диссертации в форме программного комплекса используются в деятельности ОГБУ «Агентство по инвестициям и стратегическим проектам» (акт№ 51/1-01-11-542).

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях: Международная конференция «Современные методы прикладной математики, теории управления и компьютерных технологий» (Воронеж, 2013); Международная конференция «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 2012); VI Международная научно-техническая конференция «Аналитические и численные методы моделирования естественнонаучных и социальных проблем» (Пенза, 2011); Ежегодная международная конференция КРОМШ (Симферополь, 2010-2011); Международная школа-семинар «Системное моделирование социально-экономических процессов» (Воронеж, 2008), а также на ежегодных научных конференциях Воронежского государственного университета.

Публикации. Основные результаты диссертации отражены в 13 опубликованных работах, в том числе, 4 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве, лично соискателю принадлежит: [60] -математическая модель многокритериальной трёхиндексной задачи о назначениях; [63] - утверждение, обосновывающее сведение полной нечёткой задачи о назначениях к задаче с нечёткими целевыми коэффициентами, алгоритм решения поставленной задачи на основе венгерского метода; [55] - «жадные» алгоритмы решения трёхиндексной задачи о назначениях; [58] - детальная разработка «жадного» и адаптивного алгоритмов, конкретизация и наполнение шагов решения поставленной задачи; [59, 60] - решение задачи по ¡1; [64] -переход от нечёткой к интервальной задаче о назначениях, алгоритм решения поставленной задачи с использованием адаптивного алгоритма; [65] - модуль

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

Объём и структура работы. Диссертация состоит из введения, четырёх глав, заключения, списка используемых источников из 169 наименований и приложения; изложена на 147 страницах основного текста и включает 30 рисунков и 15 таблиц.

ГЛАВА 1. ПОСТАНОВКИ ОБОБЩЁННЫХ ЗАДАЧ О НАЗНАЧЕНИЯХ И ИХ КЛАССИФИКАЦИЯ

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

Пусть задано конечное множество X = и конечное множество комбинаций его элементов

^ = {^15 ' ^лг) >

при этом под комбинацией 5 е О понимается упорядоченная или неупорядоченная т-выборка из п элементов множества X. Пусть /(.у) - функция,

заданная на множестве О. Требуется найти элемент /еб, доставляющий экстремум этой функции.

Широко известна проблема поиска экстремума функции /(я) на множестве перестановок. В этом случае

Я/ЕЯ..

где Бп - симметричная группа и N < п\.

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

1.1 Многоиндексные обобщения задачи о назначениях

Задача о назначениях (ЗОН) имеет множество разновидностей и модификаций, таких как стандартная (или классическая) задача о назначениях [13, 25], её многоиндексные аналоги [130, 148, 165], квадратичные и биквадратичные

и

постановки [106], обобщения задачи, связанные с использованием неполной и неточной исходной информации [69] и т.д.

Математическая модель стандартной ЗОН имеет вид

ЦХ) = ££с,Л->1тп (1.1)

,=i j=1

±XlJ=\,j=ü, (1.2) 1=1

5>„=i, *=!Я (1.3)

7=1

хц = {ОД}, ij = u (1.4)

Ограничения (1.1)-(1.4) задают множество допустимых решений Q. 1.1.1 Классификация задач о назначениях

Различные модификации ЗОН можно классифицировать по следующим основным признакам.

1. По виду целевой функции.

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

L{X) - maxc х —> min.

1.2. Нелинейные целевые функции (квадратичные, кубические, биквадратичные). Квадратичная целевая функция, например, пред ставима в виде [131]

п п п п я п

l{X)=ZEXZaA v«+ ^ min-

,=1 J=l к=1 /=1 (=1 ;=1

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

2. По типу коэффициентов.

Можно выделить следующие обобщения задачи.

2.1. Детерминированная ЗОН, например, (1.1)-(1.4), в которой коэффициенты целевой функции являются числами.

2.2. Интервальная ЗОН, в которой коэффициенты целевой функции известны с точностью до интервалов возможных значений, то есть имеют вид

сц =[су, Су], i, j = l,n. Математическая модель интервальной ЗОН представима в виде

ЦХ) = ^сцхц->тт (1.5)

1=1 7=1

2X=w=Vn, (i.6)

í=I

п __

^хц =1, г' = 1,л, (1.7)

ху={0,1}, í,y = U, (1.8)

где Х(Х) - функция с интервальными коэффициентами су .

2.3. Нечёткая ЗОН, основанная на примен�