авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

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


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |

«ЗАДАЧИ И МЕТОДЫ КОНЕЧНОМЕРНОЙ ОПТИМИЗАЦИИ Часть 3 Д. И. Коган Динамическое программирование и дискретная много- критериальная ...»

-- [ Страница 4 ] --

*** Алгоритм А решения задачи Z с целочисленными начальны ми данными назовем псевдополиномиальным, если верхняя оценка количества выполняемых им элементарных операций TА не превышает значения некоторого полинома от двух перемен ных РА(L, M Z ), где L – объем входной информации по задаче Z, а M Z – максимальное из чисел в ее составе.

Пусть Z - произвольная массовая задача, а Р(х) - полином с целыми коэффициентами. Через Z(Р) будем обозначать сово купность входящих в Z индивидуальных задач, в которых M Z не превышает Р( V ).

Задача Z называется NP -полной ( NP -трудной) в сильном смысле, если :

1. она является NP -полной ( NP -трудной);

2. существует такой полином Р, что задача Z(Р) также NP -полна ( NP -трудна).

Из приведенного определения вытекает, что если задача Z NP -полна и не является задачей с числовыми параметрами, то Z - NP - полная в сильном смысле задача. Получаем, что из перечисленных выше задач распознавания 1 – 6 первые пять задач ("Выполнимость КНФ", "Трехмерное сочетание", "Вершинное покрытие", "Клика", "Гамильтонов цикл") NP полны в сильном смысле.

Из гипотезы P NP следует, что для NP -полных в сильном смысле и NP -трудных в сильном смысле задач псевдополиноми альных решающих алгоритмов не существует.

А Отметим, что рассмотренный в главе 1 алгоритм кзр решения m-мерной задачи о ранце с n предметами (1.34) - (1.36) псевдополиномиален. Действительно, верхней оценкой числа выполняемых этим алгоритмом элементарных операций являет ся Сmn(W+1)m, где W –максимальное из чисел, записанных в правых частях линейных ограничений (1.35), а С – константа, не зависящая от конкретных характеристик задачи. Из приведен ной оценки следует, что число выполняемых алгоритмом эле ментарных операций не превышает СL(М+1)m, где L – объем входной информации по задаче, М – максимальное из чисел в ее составе, а С – константа, не зависящая от определяющих задачу параметров. Полученная оценка – полином от переменных L и М степени m+1.Таким образом, m-мерная задача о ранце NP трудна, но не в сильном смысле.

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

*** Известно [7], что NP-полной в сильном смысле является следующая задача «3-Разбиение»: множество М состоит из 3n элементов, каждый элемент х из М имеет вес v(х), суммарный вес всех элементов множества М равен nV, веса всех элементов и V – натуральные числа;

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

Задача сохраняет NP-полноту в сильном смысле и при сле дующем дополнительном условии: для каждого х из М имеет место (V /4) v(х) (V /2).

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

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

3.2. Полиномиально разрешимые подклассы труднорешаемых задач После того, как было формализовано понятие «алгоритм», появилась возможность разделения массовых задач на разреши мые и неразрешимые. Задача неразрешима, если не существует алгоритма, ее решающего. Если та либо иная важная массовая задача неразрешима, то интерес представляет вопрос выделения ее частных случаев (подклассов), для которых можно построить решающие алгоритмы. В качестве примера приведем неразре шимую теорию – арифметику натуральных чисел (см., напри мер, [9]);

важно, что в этой теории имеются разрешимые подте ории (в частности, теория сложения натуральных чисел).

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

эти вопросы важны как в теоретическом плане, так и в чисто прикладном аспекте.

Рассмотрим изучавшуюся в главе 2 каноническую задачу однопроцессорного обслуживания потока заявок. Известно, что эта задача NP-трудна в сильном смысле [12]. Результат о труд норешаемости сохраняется, если рассматривать только задачи, удовлетворяющие легко интерпретируемому и реально выпол няемому в приложениях условию t(n) с*n, (3.1) где с* – фиксированная натуральная константа. Класс задач однопроцессорного обслуживания, для которых условие (3.1) выполняется, обозначим К [с*]. Ниже будут рассматриваться только задачи класса К [с*].

Через W() будет обозначаться величина суммарного штра фа по всем заявкам при условии, что их обслуживание выполня ется по расписанию.

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

Частная модель 1. Заявки и будем называть однотип ными, если () = () и а() = а(). Вводимое здесь ограниче ние касается числа типов заявок в потоке R.

Задачу класса К [с*] отнесем к подклассу К [с*, m], если во входном потоке присутствуют заявки не более чем m различных типов.

В подклассе К [с*, m] любое множество заявок S может быть представлено m-мерным вектором N (S ) = (n1, n2,..., nm), где ni – число заявок i-го типа в множестве S, i = 1, m.

Вместо функции (t, S) введем соответствующую функцию (t, N (S)), полагая для всех S (t, S) = (t, N (S )).

Основное рекуррентное соотношение (2.16) для вычисления значений функции в задачах подкласса К [с*, m] модифициру ется очевидным образом, а общее количество рассматриваемых векторов (n1, n2,..., nm), являющихся аргументами функции, оценивается сверху величиной nm-1. С учетом этого обстоятель ства верхняя оценка числа выполняемых алгоритмом элемен тарных операций принимает вид С**nm, где C** – константа, не зависящая от значений параметров m и n. Таким образом, верх няя оценка временной вычислительной сложности задач под класса К [с*, m] оказывается полиномиальной.

Частная модель 2. В рамках данной модели будем считать, что количество заявок, находящихся в системе и ожидающих обслуживания, не может превысить натуральную константу k.

Множество расписаний, удовлетворяющих этому ограничению, обозначим Ф(k). Рассматриваемая задача записывается в виде min W() (3.2) ( k ) Пусть k(t, S) обозначает минимальную величину суммарно го штрафа по заявкам множества S и заявкам, поступающим в систему обслуживания позднее момента времени t для опреде ляемой состоянием (t, S ) ситуации. При этом считается, что t – момент принятия решения, множество S заявок, ожидающих на данный момент обслуживания, не более чем (k + 1)-элементное (нулевая заявка учитывается), а допустимыми являются только расписания совокупности Ф(k).

Если в момент t начинается обслуживание заявки i, то через временной промежуток (i) количество r(t, i) ожидающих об служивания заявок будет равно S - sign (i) + D(t, (i)).

Обозначим через S(k, t) множество заявок i из S, для которых выполняется неравенство r(t, i) k + 1. С учетом введенных обо значений рекуррентное соотношение динамического програм мирования для решения задачи (3.2) записывается следующим образом:

k(t, S ) = min {а(i) [t + (i) – t(i)] + k(t + (i), (S / i) D(t, (i))}.(3.3) iS ( k,t ) Заметим, что для некоторых промежуточных состояний сис темы обслуживания (t, S ) множество заявок S(k, t) может ока заться пустым. Такие пары считаем запрещенными, а значения соответствующих величин k(t, S ) равными. Если при подсче те оказалось, что k(0, V(0)) =, то в рассматриваемой задаче множество расписаний Ф(k) пусто. С учетом принадлежности решаемой задачи классу К [с*], устанавливаем, что верхней оценкой временной вычислительной сложности основанного на (3.3) алгоритма является полином от n степени k + 1.

Частная модель 3. Будем говорить, что в расписании за явка обгоняет в обслуживании заявку, если (т.е. t() t()), но заявка обслуживается раньше, чем заявка. Разность – будем называть длиной обгона.

Расписание назовем d-расписанием, если при его реализа ции длины обгонов не превышают натуральной константы d.

Очевидно, что при реализации d-расписания произвольную за явку i могут обогнать в обслуживании только заявки из сово купности {i + 1, i + 2,..., i + d}. Множество всех d-расписаний будем обозначать Ф[d].

Рассмотрим экстремальную задачу min W(). (3.4) [ d ] При реализации d-расписания состояния системы – это тройки вида (t,, x), где t – очередной момент принятия решения по загрузке процессора (в момент t процессор считается свобод ным);

– порядковый номер-наименование первой (по возраста нию номеров) необслуженной заявки;

x = (х1, х2,..., хd) – d-мер ный вектор с булевозначными координатами, причем хi = 1, если по состоянию на момент времени t заявка + i уже обслужена, и хi = 0 в противном случае.

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

Для состояния (t,, x) через Q(t,, x) обозначим совокуп ность всех необслуженных на данный момент t заявок. В это множество входят: заявка ;

все принадлежащие потоку R заявки + i такие, что хi = 0 (здесь i = 1, 2,..., d );

все принадлежащие потоку R заявки у такие, что у + d. Через Q d(t,, x) обозначим подмножество заявок из Q(t,, x), номера-наименования кото рых не превосходят + d. Для произвольного множества заявок М через (М ) обозначим минимальный из номеров-наименова ний заявок этого множества, а через w(М ) обозначим вектор (w1, w2,..., wd), в котором координата wi = 0 тогда и только тогда, ко гда заявка (М ) + i находится в множестве М;

во всех остальных случаях wi = 1;

здесь i= 1, n.

Рассмотрим общую ситуацию, когда множество Q(t,, x) со стоит более чем из одной заявки. С учетом введенных обозначе ний, основное соотношение динамического программирования для решения задачи (3.4) записывается в виде d(t,, x) = {a(i) [max (t, t(i)) + (i) –t(i)] + min iQ d ( t,, x ) + d(t + (i), (Q(t,, x) \ {i}), w(Q(t,, x)\{i})}. (3.5) Состояние системы в последний момент принятия решения (все, кроме одной, заявки уже обслужены) записывается как тройка (t, *,(1, 1, …, 1)), где * {n – d – 1, n – d, n – d + 1, …, n}. В такой ситуации d(t, *, (1, 1, …, 1)) = a(*)[max (t, t(*)) + (*) – t(*)].(3.5') Примем дополнительное предположение, что в рассматри ваемом классе задач требуемая продолжительность обслужива ния процессором любой заявки ограничена сверху некоторой константой. В таком случае в процессе вычислений по рекур рентным соотношениям (3.5)–(3.5') аргумент t функции d(t,, x) принимает линейно зависящее от n число различных значений;

аргумент принимает значения из множества {1, 2,..., n};

для возможных значений векторного аргумента x имеется не более 2d вариантов. При вычислении каждого следующего значения функции число выполняемых элементарных операций линейно зависит от параметра d. Получаем, что верхней оценкой вычис лительной сложности алгоритма решения задачи (3.4), основан ного на соотношениях (3.5)–(3.5'), является С d n 2 2 d, где С – константа, не зависящая от значений параметров n и d. При любом фиксированном d верхняя оценка числа необхо димых для решения задачи элементарных операций – полином второй степени от n.

Заметим, что общее число расписаний обслуживания n-эле ментного потока заявок в однопроцессорной системе равно n!;

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

Частная модель 4. Предусматривается следующее ограни чение: каждую заявку могут обогнать в обслуживании не более q других заявок (q – заданная константа).

Расписание назовем {q}-расписанием, если при его реали зации любую заявку обгоняют в обслуживании не более q дру гих заявок. Подкласс {q}-расписаний будем обозначать Ф{q}.

Рассмотрим задачу синтеза оптимального {q}-расписания:

min W(). (3.6) {q} Состояния системы обслуживания – это тройки вида (t,, U ), где t – очередной момент принятия решения по загрузке процес сора (в момент t процессор считается свободным);

– порядко вый номер-наименование первой (по возрастанию номеров) не обслуженной заявки;

U – множество заявок, которые по состоя нию на данный момент уже обогнали в обслуживании заявку, количество заявок в этом множестве не больше q (|U | q).

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

Для состояния (t,, U ) через Q(t,, U ) обозначим совокуп ность всех необслуженных заявок;

в это множество входят: за явка и все заявки + i, не входящие в совокупность U, здесь i {1, 2,…, n – }. Для произвольного множества заявок М через (М ) обозначим минимальный из номеров-наименований заявок этого множества. Через Y (М ) обозначим совокупность, заявок i, i (М ), не входящих в множество М.

Рассмотрим общую ситуацию, когда множество Q(t,, U ) со стоит более чем из одной заявки. Если при этом |U | q, то на немедленное обслуживание можно взять любую заявку из сово купности Q(t,, U );

если же |U | = q, то на немедленное обслужи вание в рассматриваемом состоянии следует взять заявку. По лучаем:

q(t,, U ) = min {a(i) [max (t, t(i)) + (i) –t(i)] + iQ ( t,,U ) + q(t + (i), (Q(t,, U ) \ {i}), Y(Q(t,, x) \ {i})} (3.7) для случая |U| q;

q(t,, U ) = a() [max (t, t()) + () – t()] + + q(t + (), (Q(t,, U ) \ {}), Y(Q(t,, x) \ {})} (3.7') для случая |U | = q.

Если множество Q(t,, U ) состоит из единственной заявки, в таком случае это заявка, то q(t,, U ) = a() [max (t, t()) + () – t()]. (3.7'') Примем дополнительное предположение, что в рассматри ваемом классе задач продолжительность обслуживания процес сором любой заявки ограничена некоторой константой. В таком случае в процессе вычислений по рекуррентным соотношениям (3.7)–(3.7'') аргумент t функции q(t,, U ) принимает линейно за висящее от n число различных значений;

аргумент принимает значения из множества {1, 2,..., n};

для возможных значений аргумента U имеется не более nq вариантов. При вычислении каждого следующего значения функции число выполняемых элементарных операций по верхней оценке линейно зависит от параметра n. Получаем, что верхней оценкой вычислительной сложности алгоритма решения задачи (3.6), основанного на со отношениях (3.7)–(3.7''), является С nq+3, где С – константа, не зависящая от значений параметров n и q.

Частная модель 5. Расписание назовем (d, q)-расписа нием, если при его реализации произвольная заявка i может быть обогнана в обслуживании только некоторыми заявками из совокупности {i + 1, i + 2,..., i + d} и не более чем q другими заявками. В рамках рассматриваемой модели допустимыми счи таются только (d, q)-расписания. Класс (d, q)-расписаний будем обозначать (d, q).

Как очевидно, класс (d, 0)-расписаний совпадает с классом d-расписаний, а класс (0, q)-расписаний совпадает с классом {q}-расписаний.

Пусть t – произвольный момент принятия решения, S – со вокупность заявок, которые по состоянию на момент времени t поступили и ожидают обслуживания. Как и выше, для произ вольного множества заявок М через (М ) мы обозначаем мини мальный из номеров-наименований заявок этого множества. Че рез (t) обозначим максимальное значение i, для которого t(i) t, т.е. (t) – последняя из поступивших в систему по состоя нию на момент времени t заявок. Пусть М(t, S, d ) = {j | (S ) + d j (t)}. (3.8) Расписание является (d, q)-расписанием, если при его реа лизации в любой момент времени t в множестве М (t, S, d ) оказы вается не более чем q завершенных обслуживанием заявок.

Рассмотрим задачу min W(). (3.9) ( d,q ) При реализации (d, q)-расписания в любой момент принятия решения t совокупность Q всех оставшихся пока необслужен ными заявок потока можно полностью описать (d + q + 1) мерным вектором Х(Q) = (х1, х2,..., хd+1, х1, х2,..., хq), в котором: х = (Q );

координаты х2, х3,..., хd+1 – булевы, при этом хj равно единице тогда и только тогда, когда заявка (Q ) + j – 1 уже об служена или заявки с данным текущим номером не существует в силу того, что (Q ) + j – 1 n;

координаты х1, х2,..., хq перечис ляют номера завершенных обслуживанием заявок из совокупности М(t, S, d ). Если в совокупности М(t, S, d ) обслу жено только s заявок, где s q, то хs+1 = хs+2 =... = хq = 0. Вектор Х(Q ) будем называть вектором-описанием. Доопределим Х() как нуль-вектор. Если Х – вектор-описание, то пара (Х, t) – это состояние системы в момент времени t. Отметим, что по паре (Х, t) совокупность не обслуженных по состоянию на момент времени t заявок Q определяется однозначно: Q = Q(Х, t).

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

Начальному состоянию системы соответствует вектор описание Х(V(0)). Поэтому min W() = dq(Х(V(0)), 0).

( d,q ) Пусть Qdq(Х, t) – множество заявок, совпадающее с Q(Х, t), если последняя координата вектора Х нулевая, и состоящее только из заявок множества Q(Х, t) с номерами не больше (Q(Х, t)) + d в противном случае. При синтезе (d, q)-расписания в ситуации, определяемой парой (Х, t), выбор очередной на правляемой на процессор заявки осуществляется только из со вокупности Q dq(Х, t).

Соотношение динамического программирования для решае мой задачи (3.9) записывается следующим образом:

dq(Х, t) = min {a(i) [max (t, t(i)) + (i) – t(i)] + iQdq ( X, t ) + dq(Х(Q(Х, t)) \ {i}), t + (i))}. (3.10) При этом dq(Х(), t(n) + ) = 0 (3.11) для любого 0.

Реализация определяемой рекуррентными соотношениями (3.10)–(3.11) вычислительной процедуры осуществляется в по рядке убывания значений аргумента t, процесс счета заканчива ется отысканием величины dq(Х(V(0)), 0) – оптимального зна чения критерия в рассматриваемой задаче (3.9). Отметим, что подсчет по формуле (3.10) каждого отдельного значения функ ции dq(Х, t) выполняется в линейно зависящем от n времени.

Число рассматриваемых (d + q + 1)-мерных векторов-состояний Х ограничено сверху величиной nq+12d, поскольку первая и q по следних координат этого вектора принимают значения из мно жества {1, 2,..., n}, а остальные координаты булевы. В итоге получаем, что общее число рассматриваемых наборов значений аргументов функции dq имеет порядок nq+22d, а верхней оцен кой временной вычислительной сложности изложенного алго ритма решения задачи (3.9) оказывается О(nq+32d).

Качество оптимального (d, q)-расписания зависит от выбора значений параметров: чем больше d и q, тем шире область воз можных дисциплин обслуживания, что позволяет синтезировать расписания меньшей суммарной стоимости. При этом увеличе ние значения q на единицу предпочтительнее такого же увели чения значения d, ибо в большей степени расширяет класс до пустимых расписаний. Вместе с тем, повышение значения q на единицу сопровождается ростом вычислительной сложности предложенного алгоритма в n раз, в то время как повышение на единицу значения d увеличивает число выполняемых элемен тарных операций лишь в два раза.

Сейчас обратимся к еще одной массовой задаче – классиче ской задаче о ранце (КЗР);

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

Для решения КЗР в главе 1 был описан алгоритм Акзр с верх ней оценкой числа выполняемых элементарных операций СnW, где n – число имеющихся предметов, W – максимально допус тимая величина суммарного веса помещаемых в ранец предме тов, а С – константа, не зависящая от конкретных значений n и W. Внешняя простота приведенной оценки не свидетельствует о разрешимости задачи в полиномиально зависящем от объема входной информации времени. Ясно, что увеличение макси мально допустимого суммарного веса помещенных в ранец предметов в 10k раз влечет за собой увеличение длины записи параметра W в составе входной информации по задаче только на k десятичных разрядов. В то же время приведенная оценка числа выполняемых алгоритмом Акзр элементарных операций возрас тает в 10k раз. Классическая задача о ранце относится к числу NP-трудных, ибо к ней за полиномиально зависящее от объема входной информации время сводится NP-полная задача «Раз биение» (способ построения по исходным данным задачи «Раз биение» соответствующей КЗР дан в гл. 1).

Через Квес[Q] обозначим подкласс задач о ранце с n предме тами, в которых вес каждого предмета не превосходит Q(n), здесь Q(n) – многочлен от одной переменной с неотрицатель ными коэффициентами. Так как суммарный вес всех имеющих ся предметов больше W (иначе задача решается тривиальным образом – в ранец следует поместить все предметы), получаем:

W nQ(n). Для задач рассматриваемого подкласса верхней оценкой числа выполняемых алгоритмом Акзр элементарных операций является Сn2Q(n), т. е. полином от n. Получаем, что задачи любого подкласса Квес[Q], где Q(n) – произвольная поли номиальная монотонно возрастающая функция от одной пере менной, разрешимы в полиномиальном времени.

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

Список S 0 считается состоящим из одной записи:, 0, 0. Да лее поэтапно строятся списки S i для значений i последовательно равных 1, 2, …, n. Составление каждого очередного списка S i реализуется в два шага. На первом шаге для каждой записи z = = М, С, V списка S i1 определяется новая запись z* = М {i + 1}, С + ci+1, V + vi+1, записи z и z* включаются в форми руемый рабочий список Ri. Результатом первого шага является список Ri, содержащий в сравнении со списком S i–1 вдвое боль ше записей. На втором шаге из списка R i изымаются: а) все за писи, в которых значение третьей компоненты превышает W (нарушено весовое ограничение);

б) каждая запись М', С', V', для которой в этом же списке R i имеется запись М'', С'', V'' такая, что одновременно либо С' ' С' и V'' V', либо С'' С' и V'' = V'. Кроме того, если в списке R i имеются несколько запи сей, в которых значения вторых и третьих компонент соответст венно совпадают, то все такие записи, кроме одной (любой из них), изымаются. Список S i определяется как совпадающий с получаемым в результате выполненных изъятий сокращенным списком R i. Результатом n-го этапа является список S n. В этом списке отыскиваем запись с наибольшим значением второй компоненты (суммарной стоимости). Пусть таковой является запись z (!)= М (!), С (!), V (!). Получаем оптимальное решение за дачи: в ранец следует поместить предметы подмножества М (!), максимальное значение критерия равно С (!).

П р и м е р 3. 1. Применением алгоритма Bкзр решить задачу:

х1 + 3х2 + 3х3 + 6х4 max;

х1 + х2 + 2х3 + 4х4 6;

хi {0, 1}, i = 1, 2, 3, 4.

По исходным данным сформулированной задачи строим следующие списки. Список S 0, как всегда, состоит из единст венной записи, 0, 0. В списке R1 две записи:, 0, 0 и {1}, 1, 1. Cписок S1 совпадает со списком R1.

Список R2 включает четыре записи:, 0, 0, {1}, 1, 1, {2}, 3, 1, {1, 2}, 4, 2. Список S 2 получается из R 2 изъятием второй записи;

таким образом, S 2 = {, 0, 0, {2}, 3, 1, {1, 2}, 4, 2}.

Список R 3 включает шесть записей:, 0, 0, {2}, 3, 1, {1, 2}, 4, 2, {3}, 3, 2, {2, 3}, 6, 3, {1, 2, 3}, 7, 4. Список S 3 получается из R 3 изъятием четвертой записи: S 3 = {, 0, 0, {2}, 3, 1, {1, 2}, 4, 2, {2, 3}, 6, 3, {1, 2, 3}, 7, 4}.

Список R 4 включает десять записей:, 0, 0, {2}, 3, 1, {1, 2}, 4, 2, {2, 3}, 6, 3, {1, 2, 3}, 7, 4, {4}, 6, 4, {2, 4}, 9, 5, {1, 2, 4}, 10, 6, {2, 3, 4}, 12, 7, {1, 2, 3, 4}, 13, 8.

При составлении списка S 4 из R 4 по причине нарушения весово го ограничения изымаются девятая и десятая записи;

далее, в соответствии с условием изъятия б), шестая запись. В итоге по лучаем: S 4 = {, 0, 0, {2}, 3, 1, {1, 2}, 4, 2, {2,3}, 6, 3, {1, 2, 3}, 7, 4, {2, 4}, 9, 5, {1, 2, 4}, 10, 6}. Вторая компо нента принимает наибольшее значение 10 в шестой записи по следнего списка. Оптимальное решение задачи следующее: х1 = х2 = х4 = 1, х3 = 0;

оптимальное значение критерия равно 10.

При реализации алгоритма Bкзр число записей в каждом из составляемых списков S i, i = 1, n, не превышает С (!) + 1 (дейст вительно, в любом из этих списков нет двух записей с одинако вым значением второй компоненты, которое всегда целочислен но и принадлежит отрезку [0, С (!)]). Отсюда получаем, что в ка ждом несокращенном списке R i имеется не более 2(С (!) + 1) за писей. Каждый список R i составляется по списку S i–1 выполне нием линейно зависящего от количества записей в списке S i– числа элементарных операций. При переходе от несокращенно го списка R i к списку S i число выполняемых элементарных опе раций по верхней оценке квадратично зависит от количества записей в R i. Получаем, что число элементарных операций, вы полняемых при получении каждого следующего списка имеет верхней оценкой функцию, квадратично зависящую от С (!). С учетом того, что последним составляемым является список S n, получаем в качестве оценки числа выполняемых алгоритмом Bкзр элементарных операций kn(С (!))2, здесь k – константа, не за висящая от значений n и С (!). Если максимальная из стоимостей предметов равна с*, то С (!) не превосходит nс* и в качестве верхней оценки временной вычислительной сложности изло женного алгоритма мы получаем kс*n3.

Через К ст[Q] обозначим подкласс задач о ранце с n предме тами, в которых стоимость каждого предмета не превосходит Q(n), здесь Q(n) – некоторая полиномиальная монотонно возрас тающая функция от одной переменной. На задачах этого под класса алгоритм Bкзр дает верхнюю оценку числа выполняемых элементарных операций kQ(n)n3. Получаем, что задачи любого подкласса К ст[Q], где Q(n) – произвольная полиномиальная мо нотонно возрастающая функция от одной переменной, разре шимы в полиномиальном времени.

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

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

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

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

Приведем несколько более сложных примеров. Если в клас сической задаче о назначениях запрещены некоторые закрепле ния работ за исполнителями, то вопрос о самом существовании допустимых назначений сводится к решению простейшей зада чи о назначениях [6], определяемой системой наложенных за претов. Если в задаче коммивояжера для некоторых пар городов (i, j) запретить непосредственные переходы из i в j, то вопрос существования допустимых решений по своей сложности оказывается эквивалентным NP-полной задаче «Гамильтонов цикл».

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

в случае отсутствия в рассматриваемой задаче ЦЛП допустимых решений, алгоритм дает ответ «». Пусть ZC – произвольная индивидуальная задача ЦЛП, оптимальное значение критерия которой принадлежит отрезку [А, В], числа А и В – целые;

для определенности считаем, что ZC – задача максимизации, ее кри терий обозначаем L(Х). Далее через ZC [P, Q] будем обозначать задачу, получаемую из исходной задачи добавлением линейных P L(Х) Q. Пусть С0 – ближайшая к середине ограничений отрезка [А, В] его целочисленная точка. Применением алгоритма АЦ строим допустимое решение задачи ZC [С 0, В]. Если такого решения не существует, то оптимальное значение критерия за дачи ZC лежит на отрезке [А, С 0 – 1];

если решение имеется, обозначим его Х 0, то оптимальное значение критерия задачи ZC лежит на отрезке [L(Х 0), В]. И в том, и в другом случае нам уда ется уменьшить длину отрезка, в котором локализовано искомое оптимальное значение критерия, не менее, чем в два раза. Далее находим целочисленную точку С 1, ближайшую к середине по лученного отрезка локализации, и применением алгоритма АЦ будем строить допустимое решение полученной задачи ZC [С 1, С 0 – 1] или ZC [С 1, В]. Так определяется итерационный про цесс, на каждом шаге которого длина отрезка, содержащего ис комое оптимальное значение критерия, уменьшается не менее чем в два раза. Выполнив не более log2(В – А) итераций, мы оп ределим, что искомое значение критерия принадлежит некото рому отрезку единичной длины [h, h + 1]. Далее, применяя алго ритм АЦ к задачам ZC [h +1, h +1] и ZC [h, h], а, возможно, только к первой из них, мы найдем оптимальное решение исходной за дачи ZC. Задача ЦЛП относится к числу NP-трудных, ибо тако вым является ее частный случай – классическая задача о ранце.

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

Изложенное показывает целесообразность разделения задач дискретной оптимизации на два класса: К 1 – задачи, для кото рых допустимые решения строить относительно легко (есть по линомиальные алгоритмы синтеза);

К 2 – задачи, для которых допустимые решения строить трудно (нет полиномиальных ал горитмов синтеза). Этот простой вывод для практики оказывает ся важным. Перспективным следует считать создание допусти мых и эвристических алгоритмов для задач класса К 1. Задачи класса К 2 значительно сложнее, в них поиск приближенных ре шений по трудности сравним с поиском оптимальных планов.

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

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

Применяя к определяемой (n n)-матрицей A = {aij} класси ческой задаче о назначениях (КЗН) n max ai (i ) i = жадный алгоритм, мы на первом шаге находим в матрице А наибольший элемент aij и реализуем закрепление исполнителя i за работой Rj;

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

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

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

Рассмотрим класс К* дискретных оптимизационных задач, определяемых следующим образом. Задано конечное множество М, некоторое семейство его подмножеств I и принимающая только неотрицательные значения функция f (x), которая каждо му элементу х из М ставит в соответствие его «вес» f (x). Функ цию f (x) именуем весовой функцией. Весом произвольного под множества Х множества М называем сумму весов входящих в Х элементов. В семействе I требуется найти подмножество наи большего веса.

В рамках К* можно сформулировать широкий класс дис кретных оптимизационных задач (в том числе классическую задачу о назначениях, задачу коммивояжера, задачу о ранце и т.д.). К классу К* относится и задача отыскания в произвольном связном взвешенном n-вершинном неориентированном графе остова минимального веса (остов n-вершинного графа – это также n-вершинный ациклический связный подграф данного графа;

вес остова – сумма весов составляющих его дуг).

Жадный алгоритм для описанной общей модели определяем следующим образом:

1. Полагаем, что W – пустое множество. Элементы мно жества М упорядочиваем (нумеруем) по убыванию их весов, (mi – i-й по полученному порядку элемент множества М, i = 1, n ).

2. Полагаем i = 1.

3. Определяем, является ли W {mi} подмножеством некоторого множества Q из I;

в случае положительного от вета переходим к п. 4, в случае отрицательного – к п. 5.

4. Включаем элемент mi в множество W.

5. Увеличиваем значение i на единицу.

6. Если i n + 1, переходим к п. 3, в противном случае к п. 7.

7. Построенное множество W считаем решением задачи.

Изложенный алгоритм назовем G-алгоритмом (от англий ского greedy – жадный).

Относительно общего класса задач К* поставим вопрос: при каких налагаемых на семейство I условиях G-алгоритм строит оптимальное решение сформулированной экстремальной зада чи?

Введем следующее определение.

Матроид – это пара М, I, где М – произвольное конечное множество, а I – семейство его подмножеств, удовлетворяющее аксиомам:

А1). I и если А I и В А, то В I;

А2) Для произвольных P I, Q I, таких что |Q | = |P | + 1, существует элемент е Q \ P такой, что P е I.

Отметим, что условие I исключает вырожденный слу чай I =. Множества семейства I далее будем называть незави симыми, остальные подмножества совокупности М – зависимы ми множествами матроида М, I.

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

Очевидно, что произвольное подмножество элементов из неза висимого множества линейного пространства независимо (сово купность элементов е1, е2, …, еn линейно независима, если не существует набора скаляров 1, 2, …, n не все из которых рав ны нулю такого, что 1е1+ 2е2 + … + nеn = 0). Если для линейно независимых подмножеств P, Q линейного пространства имеет место |Q | = |P | + 1, то P порождает подпространство размернос ти |P |, которое может содержать не более чем |P | элементов множества Q. Следовательно, существует элемент е Q \ P, не принадлежащий указанному подпространству. Таким образом, множество P {е} линейно независимо.

Для произвольного подмножества С из М введем понятие его максимального независимого подмножества. Независимое подмножество А, А С именуем максимальным в С, если в С не существует независимого подмножества В такого, что А В.

Приведем без доказательства следующий результат.

Т е о р е м а 3. 2. Пусть М – конечное множество, а I – семей ство его подмножеств, удовлетворяющее аксиоме А1. В этой ситуации пара М, I является матроидом тогда и только тогда, когда удовлетворяется условие:

А3) Для произвольного подмножества С из М два любых его максимальных подмножества содержат равное число элементов.

Из данной теоремы вытекает, что пара аксиом А1 и А3 обра зует эквивалентную паре А1 и А2 систему аксиом для матрои дов.

Рангом произвольного подмножества С из М называем чис ло элементов в максимальном независимом подмножестве мно жества С. Для ранга произвольного подмножества С из М при нимаем обозначение r (С). Очевидно, что подмножество С из М независимо тогда и только тогда, когда r (С)= |С |. Каждое мак симальное независимое подмножество множества М именуется базой матроида. Число r (М ) – ранг матроида.

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

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

В1) Никакое множество из семейства В не содержится в другом множестве этого семейства.

В2) Если В1 и В2 входят в семейство В, то для любого эле мента х из В1 существует элемент у из В2 такой, что совокуп ность (В1 \ x) у тоже входит в семейство В.

Элементы семейства В – базы матроида.

Рассмотрим несколько примеров матроидов.

1. Пара M, {M}, где M – произвольное конечное непустое множество, является матроидом, единственной базой которого служит само множество M.

2. Пусть L – линейное пространство, M L – произвольное конечное непустое подмножество из L, I – множество, элемен тами которого служат все линейно независимые системы векто ров из M и пустое множество. Тогда пара М, I является мат роидом с набором независимых множеств I. Такой матроид именуется векторным матроидом, порожденным множеством векторов M. Базами этого матроида являются все базы множест ва M. В частности, взяв в качестве M множество векторов, яв ляющихся столбцами (строками) некоторой матрицы В, получа ем матричный матроид. Ранг матроида равен рангу матрицы В.

3. Пусть G – произвольный конечный неориентированный граф, M – множество всех его ребер. Подмножество ребер Х, Х M, является базой (элементом совокупности В ), если это под множество образует некоторый остов данного графа. Для пары М, В аксиомы В1 и В2 выполняются, данная пара образует матроид.

Т е о р е м а 3. 3. (Теорема Радо–Эдмондса). Если пара М, I – матроид, то для любой весовой функции применением к данной паре G-алгоритма конструируется множество Х, являю щееся независимым множеством с наибольшим весом. Если же пара М, I не является матроидом, то существует такая весовая функция f (x), что конструируемое применением G-алгоритма множество Х не является независимым множеством с наиболь шим весом.

Теорема Радо–Эдмондса дает ответ на поставленный для за дач класса К* вопрос об условиях, при которых G-алгоритм строит решения, являющиеся оптимальными.

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

В случае, если массовая задача Z – это задача коммивояже ра, сформулированный вопрос об оптимальности построенного жадным алгоритмом решения произвольной индивидуальной задачи Z1 не имеет способа получения ответа с полиномиальной верхней оценкой числа выполняемых элементарных операций (считается, что Р NP). Данный факт прямо следует из доказа тельств теорем 19.5 и 19.6 монографии [17]. Идентичное имеет место и для задачи о ранце.

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

Для произвольной задачи opt K ( X ) (3.12) XD с обозначаемым через К* ненулевым оптимальным значени ем критерия решение Х назовем -оптимальным, если {|К* – К(Х )| / К*}. (3.13) Дробь{|К* – К(Х ) | / К*} называем относительным отклоне нием критерия К(Х ) при решении Х от своего оптимального зна чения.

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

Рассмотрим формулируемую следующим образом задачу об упаковке в контейнеры. Задано конечное множество предметов А = {a1, a2, …, an};

каждый предмет ai имеет «размер» v(ai), где v(ai) – рациональное число, принадлежащее отрезку [0, 1];

тре буется найти разбиение множества А на попарно непересекаю щиеся подмножества А1, А2, …,Аg такое, чтобы сумма «разме ров» элементов каждого подмножества не превосходила 1 и чтобы значение g (число подмножеств в разбиении) было мини мально возможным. Здесь мы считаем, что предметы одного подмножества должны упаковываться в один контейнер «разме ра» 1 и наша цель – использовать как можно меньшее число контейнеров.

Введенная задача NP - трудна в сильном смысле, ибо в част ном случае она дает задачу «3-разбиение». С учетом гипотезы Р NP, можно утверждать отсутствие для задачи об упаковке в контейнеры даже псевдополиномиального алгоритма синтеза оптимального решения. Однако имеются несколько весьма про стых алгоритмов синтеза для этой задачи -оптимальных реше ний.

Один из таких алгоритмов известен под названием «Первый подходящий» (ПП). Предположим, что имеется бесконечная по следовательность контейнеров размера 1, каждый из них в на чальный момент пуст. Предметы множества А распределяем по контейнерам согласно следующему простейшему правилу: оче редной (по возрастанию индекса) предмет ai помещается в кон тейнер с наименьшим номером, у которого сумма размеров уже помещенных в него предметов не превосходит 1 – v(ai). Иными словами, предмет ai помещается в первый контейнер, куда его поместить можно. Отметим, что алгоритм ПП не начинает за полнять новый контейнер до тех пор, пока можно использовать контейнеры, уже начатые заполнением.

Обозначим через ХПП решение задачи об упаковке в контей неры, конструируемое изложенным алгоритмом. Число нужных при этом решении контейнеров К(ХПП) удовлетворяет неравен ству n К(ХПП) 2 v(ai ). (3.14) i = Действительно, в противном случае в построенном решении обязательно найдутся два непустых, но загруженных менее чем на половину контейнера, что невозможно. То, что указанная граница – наилучшая из возможных, следует из рассмотрения задачи с множеством предметов А = {a1, a2, …, an}, где v(ai) = = (1/2) +,. i = 1, n. Так как никакие два предмета не могут быть помещены в один контейнер, общее число нужных контейнеров равно n. В то же время суммарный размер предметов равен (n/2) + n;

если выбрать достаточно малым, суммарный размер окажется сколь угодно близким к n/2.

Оценим, как К(ХПП) может отличаться от минимально необ ходимого числа контейнеров К*. Очевидно неравенство n v(ai ).

К* (3.15) i = Из соотношений (3.14)–(3.15) получаем, что К(ХПП) 2К*.

Таким образом, алгоритм ПП для решения задачи упаковки в контейнеры является -оптимальным при = 1. Более тонкие рассуждения (см. [7]) дают возможность установить -оптималь ность алгоритма ПП для = 7/10.

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

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

характеристики этих алгоритмов практически совпа дают.

Сейчас предположим, что предметы совокупности А упоря дочены не произвольно (как это считалось ранее), а по умень шению размеров. Процедура применения алгоритма ПП к упо рядоченному таким образом списку предметов называется «Первый подходящий в порядке убывания» (ПППУ). Решение, получаемое этой процедурой, обозначим ХПППУ. Тогда К(ХПППУ) – число нужных при этом решении контейнеров. Минимально необходимое число контейнеров в рассматриваемой задаче по прежнему обозначаем К*. Имеет место следующий результат.

Т е о р е м а 3. 4. (Теорема Джонсона, см., например, [7]).

Для любой задачи об упаковке в контейнеры выполняется нера венство К(ХПППУ) (11/9)К* + 4.

Более того, существуют задачи об упаковке в контейнеры, для которых К(ХПППУ) (11/9)К*.

Сейчас рассмотрим классическую задачу о ранце n ci xi max (3.16) i = при условиях n vi xi W ;

(3.17) i = хi {0, 1}. (3.18) и задачу о ранце с дробимыми предметами, отличающуюся от КЗР заменой условия (3.18) на хi [0, 1]. (3.18') В задаче с ограничением (3.18') считается, что предметы в ранец можно помещать не только целиком, но и частями. Для этой задачи известен очень простой способ синтеза оптимально го решения – алгоритм Данцига [8]. Этот алгоритм заключается в следующем. Для каждого i-го предмета вычисляется показа тель i = сi / vi;

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

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

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

Для задачи (3.16)–(3.18) алгоритм Данцига может тракто ваться как следующая эвристическая процедура: для каждого i го предмета вычисляем показатель i = сi /vi;

помещаем в ранец предмет с наибольшим значением этого показателя (если таких предметов несколько – первый из них по номеру), каждый сле дующий (по убыванию показателя i) предмет помещается в ра нец, если это позволяет сделать ограничение (3.17). Изложен ную процедуру именуем эвристическим алгоритмом Данцига (ЭАД).

Рассмотрим следующий пример классической задачи о ран це:

2х1 + Мх2 max;

х1 + М х2 М;

хi {0,1}, i = 1, 2;

здесь М – натуральная константа, удовлетворяющая ограниче нию М 3.

Для приведенной задачи ЭАД строит решение Х = (1, 0);

обеспечиваемое этим решением значение критерия равно 2. В то же время оптимальным является решение Х* = (0, 1), обеспечи вающее значение критерия М. Так как константа М может быть сколь угодно большой, ЭАД не является -оптимальным ни при каком значении.

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

299х1 + 73х2 + 159х3 + 221х4 + 137х5 + 89х6 + 157х7 max при ограничениях 4х1 + х2 + 2х3 + 3х4 + 2х5 + х6 + 2х7 10;


хi {0, 1}, i = 1, 2, …, 7.

Если к данной задаче применить алгоритм Bкзр, то получим, что оптимальным решением является совокупность предметов с множеством номеров М (!) = {1, 2, 3, 6, 7}, а оптимальное значе ние критерия С (!) равно 777. В процессе реализации алгоритма приходится построить списки, суммарное число записей в кото рых оказывается равным 91. Естественная идея упрощения за ключается в замене нулем младшего разряда в каждом из пара метров сi. В рассматриваемой задаче получаем следующий критерий:

290х1 + 70х2 + 150х3 + 220х4 + 130х5 + 80х6 + 150х7 max.

При новой критериальной функции получаем М (!) = {1, 3, 4, 6}, а оптимальное значение критерия С (!) равно 740. Здесь при реализации алгоритма Bкзр приходится построить списки, сум марное число записей в которых оказывается равным 36, т.е.

практически втрое меньше, чем раньше. В то же время отличие в значении критерия около 5%;

если для полученного множест ва {1, 3, 4, 6} вычислить значение первоначальной критериаль ной функции, то получим 768 (отличие от оптимума порядка 1%).

В общем случае, если при округлении отбросить в числах сi последние t разрядов, то отклонение от оптимального значения критерия не будет превышать 10 tn. Время, необходимое для ра боты алгоритма при решении исходной задачи не превосходит kс*n3. После отбрасывания t разрядов оценка временных затрат принимает вид kс*n310 –t.

Если решение Х задачи о ранце с n предметами построено алгоритмом Bкзр после того, как в числах сi отброшены послед ние t разрядов, разность К* – К(Х ) не превышает 10 tn. При этом К* не меньше, чем с*. Получаем, что найденное решение Х яв ляется -оптимальным при некотором (10 tn)/с*. Отсюда с* (10 tn)/.

С учетом последнего неравенства, верхняя оценка числа вы полняемых алгоритмом Bкзр элементарных операций kс*n310 –t путем замены параметра с* преобразуется к виду kn4/.

Будем говорить, что алгоритм является полиномиальной приближенной схемой (ППС) для массовой задачи оптимизации Z, если по начальным данным индивидуальной задачи Z0 и он выдает -оптимальное решение этой задачи за время, ограни ченное полиномом (зависящим от ) от одной переменной – объема входной информации по решаемой задаче.

Таким образом, нами определена ППС для решения классической задачи о ранце;

полином, зависящий от, имеет здесь вид (kn4)/. Полученная оценка полиномиальна относительно n и 1/. Это достаточно удачная ситуация, ибо сделанное определение ППС допускает полином, в котором наибольшей степенью переменной n является, например, 1/.

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

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

Т е о р е м а 3. 5. В предположении Р NP при любом для задачи коммивояжера нет решающей ППС.

Положим противное;

допустим, что при некотором 0 имеется ППС, решающая задачу коммивояжера. Покажем, что в таком случае существует способ решения задачи «Гамильтонов цикл» за полиномиальное время.

По произвольному конечному ориентированному графу G с множеством вершин {1, 2, …, n} строим (nn)-матрицу S = {sij}, определяющую задачу коммивояжера. Полагаем, что все эле менты главной диагонали матрицы S нулевые;

в случае i j эле мент sij этой матрицы равен 1 тогда и только тогда, когда в гра фе G имеется дуга (i, j);

если i j и дуги (i, j) в графе нет, эле мент sij полагаем равным 2 + n0.

Применим к построенной задаче коммивояжера ППС, кон струирующую 0-оптимальное решение. Утверждаем, что дан ной схемой в построенной задаче коммивояжера будет найдено решение с суммарной длиной обхода n тогда и только тогда, ко гда в исходном графе G гамильтонов цикл имеется.

Если применением ППС в задаче коммивояжера найдено решение с суммарной длиной обхода n (обходов меньшей длины в построенной задаче существовать не может), то граф G, оче видно, гамильтонов. Докажем справедливость обратного утвер ждения. Предположим противное, т.е. что граф G гамильтонов, а применением ППС строится решение задачи коммивояжера с суммарной длиной обхода большей, чем n. В таком случае сум марная длина обхода не меньше n + 1 + n0, ибо реализуется по меньшей мере один элементарный переход длины 2 + n0. Вме сте с тем, так как граф G гамильтонов, оптимальное значение критерия в построенной задаче коммивояжера равно n. Разность между значением критерия для решения, построенного приме нением ППС, и оптимальным его значением оказывается не меньше n0 + 1, а относительное отклонение критерия задачи при найденном ППС решении от оптимального его значения оказывается не меньшим 0 + 1/n. Но это противоречит утвер ждению о том, что применяемая ППС строит 0-оптимальное решение. Получаем, что применением ППС в построенной зада че коммивояжера решение с суммарной длиной обхода n стро ится тогда и только тогда, когда в исходном графе G гамильто нов цикл имеется. Таким образом, рассматриваемая ППС в по линомиальном времени решает проблему определения по про извольному графу, является ли он гамильтоновым. В предполо жении Р NP это невозможно. Методом от противного теорема доказана.

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

Пусть max К(Х) XD – произвольная задача дискретной оптимизации. Предпола гаем, что для каждого X из D определена окрестность G(Х ), при этом X G(Х ). Решения, принадлежащие окрестности G(Х), это в том либо ином смысле близкие X решения. Алгоритмы ло кальной оптимизации имеют следующую общую структуру:

1. Находим исходное допустимое решение Х0, Х0 D;

пола гаем k = 0;

2. По имеющемуся допустимому решению Хk определяем окрестность этого решения G(Хk);

перебором принадлежащих окрестности решений находим решение Х*, оптимизирующее значение критерия при условии, что X G(Хk). Если К(Хk) = = К(Х*), то Хk – локальный оптимум. В противном случае пере ходим к п. 3.

2. Полагаем k = k +1;

3. Полагаем Хk = Х* и переходим к п. 2.

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

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

Отметим, что симплекс-метод решения задач линейного программирования может трактоваться как локальный поиск;

совокупность D – вершины многогранника ограничений, окре стность каждой точки Х из D включает вершины, смежные с вершиной Х.

В задаче коммивояжера понятие k-окрестности (k – нату ральное число, фиксирующее размер окрестности, k 2) опре делим следующим образом: гамильтонов цикл С* принадлежит k-окрестности гамильтонова цикла С, если С* можно получить из С путем замены не более чем k дуг. Выполненные экспери менты показывают, что использование систем окрестностей при k = 2 малоэффективно, при k = 3 получаются достаточно хоро шие (в среднем) результаты;

переход к значению k = 4 сущест венно увеличивает время вычислений и мало улучшает качество получаемых результатов.

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

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

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

Следует указать две сферы приложений эвристических ал горитмов: 1) синтез расписаний приемлемого для практического использования качества;

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

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

В канонической модели однопроцессорного обслуживания заявки потока R = {1, 2,..., n} считаются пронумерованными в порядке их поступления (0 = t(1) t(2)... t(n)). Дополнитель но полагаем, что заявки, поступающие на обслуживание одно временно, получают очередные номера в порядке убывания по казателя µ(i) = а(i)/(i).

Первый эвристический алгоритм тривиален, он основан на принципе «первый пришел – первым обслуживается» (ПП-ПО) Результатом применения алгоритма ПП-ПО, с учетом принятого способа нумерации заявок, всегда является расписание = (1, 2,..., n). Как правило, более качественными оказываются расписа ния, конструируемые µ-алгоритмом, предусматривающим, что в каждый момент принятия решения по загрузке освободившегося процессора из совокупности ожидающих обслуживания выби рается заявка с наибольшим значением показателя µ = а(i)/(i).

Изложим идею следующего эвристического алгоритма, на зовем его (p, q)-алгоритмом, здесь p и q – небольшие натураль ные числа (n p q). На первом этапе работы алгоритма рас сматривается начальный отрезок входного потока (подпоток R1), содержащий заявки 1, 2,..., p. Любым точным методом, эффек тивно работающим благодаря выбранному небольшому значе нию параметра p, строится минимизирующая суммарный штраф последовательность 1 обслуживания заявок этого подпотока;


начальный, длины q, отрезок последовательности 1 считаем начальным отрезком синтезируемого расписания обслуживания * заявок исходного потока R = {1, 2,..., n};

заявки, нашедшие свое место в расписании * из потока R изымаются, получаемый в результате поток обозначаем R1;

момент завершения обслужи вания заявок, входящих в построенную начальную часть распи сания * обозначим Т (*,1). На втором этапе заявки потока R1, поступившие не позднее момента Т (*,1), переупорядочиваются в порядке убывания значений показателя µ(i), получаемый по ток обозначаем R (1);

далее рассматривается начальный отрезок потока заявок R (1) (подпоток R2), содержащий p заявок;

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

начальный, длины q, отрезок последовательности 2 счи таем следующим отрезком синтезируемого расписания * об служивания заявок потока R;

заявки, нашедшие свое место в расписании * из потока R изымаются, получаемый в результате поток обозначаем R 2;

момент завершения обслуживания заявок, входящих в построенную к данному моменту начальную часть расписания * обозначим Т (*, 2). На третьем этапе заявки по тока R 2, поступившие не позднее момента Т (*, 2), переупоря дочиваются в порядке убывания значений показателя µ(i), полу чаемый поток обозначаем R (2);

далее рассматривается началь ный отрезок потока R (2), содержащий p заявок, и т.д., вплоть до момента либо естественного завершения процесса, либо выпол нения после некоторого k-го этапа условия Т (*, k) t(n). При реализации последнего варианта заявки, не вошедшие в сфор мированную часть расписания, приписываются к ней справа в порядке убывания показателя µ(i).

Легко видеть, что верхней оценкой временной вычислитель ной сложности изложенного алгоритма (с учетом сортировок) является Сn log2 n, где С – не зависящая от n константа.

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

Реально вместо изложенной канонической (p, q)-процедуры целесообразно применение ее естественных модификаций. Так в случае, когда на некотором k + 1-м этапе в совокупность рас сматриваемых р заявок подпотока входят только уже поступив шие заявки, а первая поступающая позднее момента времени Т (*,k) заявка имеет большее значение показателя µ(i), то эту за явку следует зачислить в число перспективных к включению на данном этапе.

Концепция (p, q)-алгоритма играет существенную роль и для периодов с относительно большим горизонтом планирования, когда точной может быть информация о моментах поступления только идущих вначале заявок, для последующих заявок момен ты прибытия известны как ожидаемые средние значения. Тогда реализация этапов синтеза (p, q)-алгоритмом расписания обслу живания * синхронизируется с поступлением уточненных дан ных о моментах прибытия последующих заявок. С учетом пе риодичности поступления таких данных выбираются значения параметров p и q.

Идея следующего эвристического алгоритма, именуемого алгоритмом вставки, тоже достаточно проста. На первом этапе определяем оптимальную последовательность 1 обслуживания заявок 1 и 2 в предположении, что других заявок нет;

при этом подсчитываются суммарные штрафы по двум указанным заяв кам для обеих возможных последовательностей их обслужива ния. На втором этапе: если заявка 3 поступает ранее момента завершения обслуживания первой в 1 заявки, подсчитываются суммарные штрафы для трех последовательностей, получаемых из 1 приписыванием заявки 3 к 1 слева, справа и ее вставкой в промежутке между первым и вторым элементом этой последо вательности;

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

если заявка 3 поступает не ранее момента завер шения обслуживания второй заявки последовательности 1, приписываем заявку 3 к 1 справа. Через 2 обозначаем ту из по следовательностей, для которой суммарный штраф минимален.

При определении расположения произвольной заявки k состав ленную на предыдущем этапе последовательность k-2 разбиваем на две последовательные части k–2 и *k–2, где k–2 – макси мально возможная по числу элементов начальная часть такая, что реализация расписания k–2 завершается не позднее момента прибытия заявки k;

далее из k–2 путем вставки заявки k на ме сто между частями k–2, *k–2 и на все места правее указанного получаем ряд последовательностей обслуживания;

для каждой из полученных последовательностей вычисляем суммарный штраф, последовательность с минимальным значением суммар ного штрафа обозначаем k–1. Итогом работы алгоритма являет ся последовательность обслуживания n–1.

Оценка временной вычислительной сложности алгоритма вставки Сn2, где С – не зависящая от n константа.

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

Отметим возможность построения для канонической задачи однопроцессорного обслуживания алгоритмов локальной опти мизации. При этом k-окрестность произвольного расписания образуют расписания, каждое из которых получается из путем некоторого перераспределения мест между k заявками, в после довательности идущими подряд. Начальный для процедуры локальной оптимизации вариант расписания может быть по строен одним из ранее изложенных эвристических алгоритмов (например, (p, q)-алгоритмом или алгоритмом вставки).

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

Сейчас рассмотрим сформулированную в гл. 2 задачу синте за расписания обслуживания потока поступающих в дискретном времени заявок R = {1, 2,..., n} в системе, состоящей из m иден тичных параллельных процессоров j ( j = 1, m ). Для этой зада чи в гл. 2 записаны рекуррентные соотношения динамического программирования, однако определяемый ими вычислительный процесс очень трудоемок и реально осуществим лишь при ма лом числе процессоров и небольшом количестве заявок в пото ке. Основанная на декомпозиции эвристическая процедура со стоит в последовательном выполнении двух этапов.

На первом этапе строится расписание обслуживания 0 – «нулевой» вариант искомого решения. При этом используется модифицированная на случай m параллельных процессоров многошаговая (p, q)-процедура, где p и q – относительно не большие натуральные числа, q p n. При реализации каждого шага этой процедуры с учетом того, что число p подлежащих обслуживанию заявок невелико, можно использовать метод ди намического программирования.

В результате выполнении первого этапа мы получаем распи сание 0, которое разделяет поток заявок R = {1, 2,..., n} на m подпотоков, заявки j-го подпотока должны обслуживаться про цессором j ( j = 1, m ).

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

Глава 4. ДИСКРЕТНЫЕ МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ.

МНОГОКРИТЕРИАЛЬНОЕ ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Важной особенностью многих проблем, возникающих в процессах принятия решений в системах планирования, управ ления и проектирования, является наличие нескольких показа телей, по которым решения оцениваются. Рассмотренные в пре дыдущих разделах модели и методы в таких случаях оказыва ются недостаточными. В последние десятилетия значительное внимание уделяется изучению дискретных оптимизационных задач в многокритериальных постановках. При этом возникают вопросы, какие решения следует считать целесообразными (оп тимально-компромиссными) и как эти решения строить. В дан ной главе излагается ряд подходов к решению многокритери альных задач, строятся соответствующие алгоритмы. Отметим, что по имеющейся исходной информации единственное целесо образное решение многокритериальной задачи определить, как правило, невозможно. Поэтому в процессах решения многокри териальных задач существенную роль играет лицо, принимаю щее решения (ЛПР). Именно ЛПР определяет тип решающей процедуры и при необходимости назначает ее параметры. В случае, если найдено многоэлементное множество оптимально компромиссных решений, ЛПР осуществляет выбор одного из них.

4.1 Концепция Парето-оптимального решения и схемы компромисса между критериями.

Пусть max (Q1 (x), Q2 (x),..., Ql (x)) (4.1) xD – произвольная задача многокритериальной оптимизации.

Вектор-функция Q( x) = (Q1 (x), Q2 (x),..., Ql (x)) отображает об ласть допустимых решений D в множество DQ из l-мерного про странства критериев:

DQ = {Q | Q = (Q1 (x), Q2 (x),..., Ql (x)), }, где x D;

элементы множества DQ именуются оценками. Каж дая оценка Q(x) характеризует порождающее ее решение x. Два допустимых решения задачи (4.1) эквивалентны, если их оценки одинаковы. Обозначим через M произвольное множество оце нок;

оценка w = (w1, w2, …, wl) из M называется недоминируе мой в M, если в этом множестве не найдется оценки w = (w1, w2, …, wl) такой, что wi wi, i = 1, l, причем по меньшей мере одно из записанных неравенств выполняется как строгое нера венство. Недоминируемые в DQ оценки именуются эффектив ными (по Парето) [19]. Множество всех эффективных оценок образует обозначаемую через E область компромиссов рассмат риваемой задачи, E DQ. Обратное отображение Q –1 совокуп ности E в область допустимых решений D определяет полную совокупность Парето-оптимальных решений. Очевидно, что любое целесообразное решение многокритериальной задачи должно быть Парето-оптимальным.

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

Т е о р е м а 4. 1. Для любого четного n существует бикрите риальная одномерная задача о ранце с n предметами, в которой имеется не менее 2n/2 различных эффективных оценок.

В конструируемой задаче о ранце n K1 ( X ) = c1j x j max;

(4.2) j = n K 2 ( X ) = c 2 x j max;

(4.3) j j = n a j x j b;

(4.4) j = x j {0;

1}, j = 1, n, (4.5) совокупность предметов считаем состоящей из пар ( П1, П 2 ), ( П 3, П 4 ), …, ( П n1, П n ). Для предметов пары ( П 2i 1, П 2i ), i = 1, n 2, полагаем a2i = a2i 1 = 10i 1 ;

c1 i 1 = 10i 1 ;

n c2i 1 = 0 ;

c1 i = 0 ;

c2i = 10i 1. Определяем b = 10 (i 1).

2 i = Рассмотрим решения ( x1,..., xn ) сформулированной задачи (предмету П j соответствует переменная x j, j = 1, n ), удовле творяющие условию x2i 1 + x2i = 1, i = 1, n 2. Множество таких решений обозначим W. Как очевидно, совокупность W содер жит 2 n 2 элементов. Каждое решение ( x1,..., xn ) из W порожда ет в плоскости критериев оценку ( n 2 n 21... 1, n 2 n 21...1 ), где i и i – цифры (система счисления десятичная), опреде ляемые следующим образом:

0, если x2i = 1, i = (4.6) 1, если x2i = 0;

1, если x2i = 1, i = (4.7) 0, если x2i = 0.

Отметим, что по структуре исходных данных задачи (4.2)– (4.5) для любого решения X = ( x1,..., xn ) выполняется условие:

n K1 ( X ) + K 2 ( X ) = a j x j b. (4.8) j = Оценки, порождаемые решениями из W, удовлетворяют ра венству:

K1 ( X ) + K 2 ( X ) = b. (4.9) Из (4.8)–(4.9) следует, что каждое принадлежащее множест ву W решение Парето-оптимально. Если Х и Y – различные Па рето-оптимальные решения из W, то порождаемые этими реше ниями оценки различны (см.(4.6)–(4.7)). Таким образом, реше ниями совокупности W порождается 2 n 2 различных эффек тивных оценок. Теорема доказана.

Перейдем к рассмотрению бикритериальных задач о назна чениях. Каждую такую задачу определяем парой (nn)-матриц А = {aij} и В = {bij}, элементы которых – целые неотрицательные числа;

aij (bij) трактуется как оценка закрепления исполнителя i за работой rj по первому (соответственно второму) показателю.

Каждое назначение (взаимно однозначное отображение множества {1, 2,..., n} в себя) закрепляет за исполнителем i ра боту r(i), i = 1, 2,..., n. Назначение оценивается критериями n n ai(i ) bi(i ). Критерии считаем максими Q1() = и Q2() = i =1 i = зируемыми. Возникающая бикритериальная задача о назначе ниях (БКЗН) записывается в виде:

max {Q1(), Q2()}. (4.10) Т е о р е м а 4. 2. Для любого натурального n существует БКЗН, множество эффективных оценок которой имеет в своем составе n! различных элементов.

Покажем способ построения соответствующей БКЗН. Вна чале предположим, что n =10. Матрицу А = {aij} определяем следующим образом:

j = 1, a1j = j – 1, (в первой строке последовательно стоят одноразрядные числа от 0 до 9);

остальные строки определяются рекуррентно:

akj = 10ak–1 j, k = 2, 3,..., 10;

j =1, 2,..., 10.

Из специфики матрицы А видим, что любое назначение ха рактеризуется числом взятых из первой строки матрицы А еди ниц, числом взятых из второй строки этой матрицы десятков, числом взятых из третьей строки сотен и т.д. При этом, так как в каждом столбце реализуется только один элемент, сумма выби раемых в матрице А произвольным назначением десяти элемен тов представляет собой 10-разрядное число, составленное из цифр 0, 1,..., 9 (каждая цифра в записи числа присутствует ров но один раз, цифра 0 может стоять и в старшем разряде). Оче видно и обратное: любое 10-разрядное число, запись которого – перестановка цифр 0, 1,..., 9, является возможным значением критерия Q1();

общее число перестановок, а, следовательно, и значений данного критерия, 10!.

Максимальным в составе введенной матрицы А является элемент а10 10, равный 9109. Далее, определяя матрицу В, поло жим для всех возможных значений индексов i и j:

bij = (9109) – aij.

Легко видеть, что при таком определении матриц А и В для любого назначения имеем:

Q1() + Q2() = 10(9109) = 91010.

Так как для любых двух различных назначений критерий Q1() принимает различные значения и так как чем больше ве личина Q1(), тем меньше значение Q2(), в построенной БКЗН каждое назначение Парето-оптимально. Оценки, порождаемые различными назначениями, не совпадают;

общее число эффек тивных оценок совпадает с числом Парето-оптимальных назна чений и равняется 10!. Принцип выполненного доказательства сохраняется и при значениях n, отличных от 10;

в качестве ос нования системы счисления, в которой задаются численные оценки, следует взять n. Теорема доказана.

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

В качестве первой схемы укажем линейную свертку крите риев (ЛСК). Реализуя ЛСК, задачу (4.1) заменяем однокритери альной задачей K (x) = 1Q1 ( x) + 2 Q2 (x) +... + l Ql (x) max (4.11) при условии х D.

Считается, что назначаемые ЛПР и фиксирующие компро мисс между критериями коэффициенты свертки удовлетворяют ограничениям:

i (0, 1), i = 1, l, 1 + 2 +... + l = 1.

Методом от противного легко доказывается, что оптималь ное решение задачи (4.11) в задаче (4.1) является Парето оптимальным. Обратное, вообще говоря, неверно. Не всякое Па рето-оптимальное решение и не всякую эффективную оценку можно получить реализацией линейной свертки критериев. Для примера рассмотрим бикритериальную задачу о ранце max (10 x1 + 4 x3,10 x2 + 4 x3 ), (4.12) x1 + x2 + x3 1, (4.13) xi {0;

1}, i = 1, 2, 3. (4.14) В задаче (4.12)–(4.14) имеются три ненулевых допустимых решения: x1 = (1, 0, 0), x 2 = (0, 1, 0), x 3 = (0, 0, 1) ;

они порожда ют оценки (10;

0), (0;

10), (4;

4) соответственно. Все эти оценки эффективны, все перечисленные решения Парето- оптимальны.

Применением линейной свертки критериев из (4.12)–(4.14) для любого фиксированного (0, 1) получаем однокритериальную задачу max [(10 x1 + 4 x3 ) + (1 )(10 x2 + 4 x3 )], x1 + x2 + x3 1, xi {0;

1}, i = 1, 2, 3.

Легко проверить, что в этой задаче при 0 0,5 имеется единственное оптимальное решение x1, при 0,5 1 – един ственное оптимальное решение x 2, при = 0,5 – два опти мальных решения, x1 и x 2. Таким образом, Парето - оптималь ное решение x 3 = (0, 0, 1) и порождаемая этим решением эффек тивная оценка (4, 4) линейной сверткой критериев получены быть не могут.

Пусть M – множество эффективных оценок в некоторой l-критериальной задаче Z. Линейное упорядочение множества M именуется лексикографическим, если для некоторой переста новки {i1, i2, …, il} чисел 1, 2,…, l выполняется условие: в случа ях, когда произвольная оценка а следует в упорядочении раньше оценки в, то либо i1-я координата оценки а больше i1-й коорди наты оценки в, либо i1-я, i2-я, …, ik-я координаты этих оценок соответственно совпадают, а ik+1-я координата оценки а больше ik+1-й координаты оценки в (здесь k {1, 2,…, l – 1}). Оценка m из M называется крайней, если в лексикографическом упорядо чении, соответствующем некоторой перестановке {i1, i2, …, il} чисел 1, 2, …, l, эта оценка стоит первой. Крайними решениями многокритериальной задачи Z будем называть решения, порож дающие крайние оценки.

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



Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.