Содержание к диссертации
Введение
1 Асимптотически точные алгоритмы для задач упаковки 10
1.1 Задача упаковки в контейнеры 10
1.1.1 Б-регулярные функции 10
1.1.2 Класс задач К\ 14
1.1.3 Условия асимптотической точности алгоритма 17
1.2 Задача упаковки в полосу 23
1.2.1 Класс задач К?п 24
1.2.2 Условия асимптотической точности алгоритма Ач . 25
1.2.3 Учет частичного порядка 32
1.2.4 Задача календарного планирования и упаковка в полосу 36
2 Метод ветвей и границ для задачи упаковки в контейнеры 40
2.1 Представление допустимых решений 41
2.1.1 Представление решений задач упаковки перестановками 42
2.1.2 Регулярные перестановки 45
2.1.3 Доминируемые решения и максимальные упаковки 47
2.2 Сравнение нижних оценок 48
2.2.1 Тривиальная оценка Ь\ 49
2.2.2 Оценка L2 49
2.2.3 Класс оценок ifl 50
2.2.4 Процедура лифтинга и класс оценок L . 53
2.2.5 Результаты вычислительных экспериментов 54
3 Задача календарного планирования со складируемыми ресурсами 56
3.1 Задача календарного планирования 56
3.2 Математическая модель 60
3.3 Некоторые сведения из теории сетевого планирования и T-гіоздние расписания 64
3.4 Задача PSa и формулировка основного результата 67
3.5 Обоснование алгоритма решения задачи PSa на основе Т-поздних расписаний 69
3.6 Алгоритм проверки допустимости Т-позднего расписания в задаче PSa 77
3.7 Завершение доказательства основной теоремы 87
3.8 Полиномиально разрешимый случай задачи MPS* 89
Заключение 92
Список публикаций автора по теме диссертации 94
Список литературы
- Условия асимптотической точности алгоритма
- Условия асимптотической точности алгоритма Ач .
- Доминируемые решения и максимальные упаковки
- Обоснование алгоритма решения задачи PSa на основе Т-поздних расписаний
Введение к работе
Диссертация посвящена двум классам задач комбинаторной оптимизации, которые представляют интерес как с точки зрения теории, так и с практической стороны. Несмотря на то, что эти проблемы имеют совершенно различные области приложений, в их математической природе есть немало общего, и многие задачи упаковки можно рассматривать как специальные случаи моделей календарного планирования [44, 48].
В общем случае задачи упаковки заключаются в распределении некоторого множества небольших объектов («предметов») по более крупным объектам («контейнерам») с соблюдением предписанных условий для достижения заданной цели. Так, в одномерной задаче упаковки в контейнеры каждому предмету приписан положительный вес, а целью является упаковка всех предметов в минимальное число идентичных контейнеров заданной грузоподъемности. В задаче упаковки в полосу имеется один контейнер заданной ширины и неограниченной высоты, а каждый предмет характеризуется положительными шириной и высотой. Необходимо упаковать все предметы таким образом, чтобы высота занятой части контейнера была минимальной. При этом стороны предметов должны быть параллельны сторонам контейнера, вращение и наложения предметов не допускаются. Классификация задач упаковки и раскроя приведена в [36]
Даже в простейшем (одномерном) случае задача упаковки в контейнеры является iVP-трудной в сильном смысле [14], поэтому основные
усилия исследователей направлены на построение эффективных приближенных алгоритмов. Уже в ранних работах, посвященных задаче упаковки в контейнеры, был предложен целый ряд приближенных малотрудоемких алгоритмов и установлены гарантированные оценки их точности в наихудшем случае [51]. Приведем описания некоторых из них, которые используются в диссертации.
Алгоритм NF. Первый предмет помещается в первый контейнер. Каждый последующий предмет помещается в тот же контейнер, что и предыдущий, до тех пор, пока в нем достаточно свободного места. В противном случае предмет помещается в новый (пустой) контейнер.
Алгоритм FF. Первый предмет помещается в первый контейнер. Каждый последующий предмет помещается в контейнер, имеющий минимальный индекс из числа тех, которые подходят для его размещения.
Для этих алгоритмов установлены следующие достижимые асимптотические оценки наихудшего поведения: Rj^F = 2, RpF = 17/10. Если множество предметов предварительно упорядочить по невозрастанию весов предметов, а затем применить к ним алгоритм NF или FF (такие версии алгоритмов обозначаются NFD и FFD соответственно), то оценки улучшаются: RFD = 17/10, RfF = 11/9 [51].
Для задачи упаковки в полосу также был разработан ряд подобных алгоритмов [22, 32, 45]. Один из наилучших на сегодняшний день имеет оценку 5/4 [21]. Более полную информацию об алгоритмах с гарантированными оценками точности можно найти в обзорах [29, 31, 43, 57].
Для задач упаковки в контейнеры и в полосу также известны полиномиальные аппроксимационные схемы (PTAS) [39] и вполне полиномиальные аппроксимационные темы (FPTAS) [53, 54].
Решению задач упаковки методами локального поиска посвящены ра-
боты [20, 40, 64], а также обзор [49].
В ходе вычислительных экспериментов было установлено, что относительная погрешность алгоритмов типа NF и FF «в среднем» существенно отличается от достижимых оценок наихудшего поведения, что стимулировало появление статей, посвященных вероятностному анализу приближенных алгоритмов. Эти работы, как правило, содержат либо оценку отношения математического ожидания числа контейнеров, требуемых некоторым приближенным алгоритмом, к ожидаемому оптимальному числу контейнеров [17, 42, 46, 52, 55], либо описание вероятностных свойств оптимального решения [27, 34, 63, 67]. Обзору различных подходов к вероятностному анализу алгоритмов упаковки посвящена монография [33]
В диссертации для исследования качества приближенного алгоритма используется идея построения алгоритмов с оценками (є, S), предложенная Э. X. Гимади, Н. И. Глебовым и В. А. Перепелицей [7].
Пусть /С — некоторый класс оптимизационных задач. Посредством F*(S) обозначим оптимальное значение целевой функции для задачи S 6 /С. Будем считать, что рассматривается задача на минимум и F*(S) > 0 для всех S Є /С.
Рассмотрим теперь некоторый алгоритм Л, который может быть применен к любой задаче S класса /С, так что результатом этого применения является допустимое решение задачи S со значением целевой функции Fj[(S). При этом, вообще говоря, не исключается, что применение алгоритма Л к некоторым задачам из /С может оказаться безрезультатным с точки зрения достижения требуемой точности решения.
Пусть заданы класс задач /С и некоторое семейство V вероятностных мер, определенных на /С. Будем говорить, что алгоритм Л имеет оценки
(є, 5) относительно V, если
P{FA(S)>(l + s)F*(S)}<6
для всех Р Є V.
Будем рассматривать классы задач, описываемые одним параметром, принимающим в качестве значений натуральные числа. В связи с этим будем далее говорить о классах /Сп задач размерности п, семействах Vn, оценках (єп, 6п) и их свойствах в зависимости от параметра п.
В качестве примера алгоритма с оценками (єп, 6п) можно привести алгоритм А. А. Боровкова [1] для класса /Сп задач коммивояжера, для которых распределения из Vn получаются в результате случайного выбора п точек в ограниченной, односвязной, с достаточно гладкой границей области G г-мерного евклидова пространства.
Алгоритм Л называется. асимптотически точным на классе задач /С, если существуют такие последовательности (єп,5п), что для любого п алгоритм Л удовлетворяет оценкам (єп, 6п) на подмножестве Кп С /С и при этом еп —> 0, 5п —> 0 при п -> оо.
Параметры еп и 8п могут трактоваться как оценки относительной погрешности и вероятности несрабатывания алгоритма- соответственно.
Использование техники построения алгоритмов с оценками (єп, 5п) позволило установить условия асимптотической точности малотрудоемких приближенных алгоритмов для решения ряда труднорешаемых задач дискретной оптимизации [3, 4, 8, 9, 10, 13, 18]. Обзор результатов, полученных до 1982 года можно найти в [65].
Задача календарного планирования (ЗКП) является важной частью системы управления проектами. Проект состоит из множества работ, которые необходимо выполнить для достижения предписанной цели. При
этом расписание выполнения работ проекта должно удовлетворять целому ряду ограничений, наиболее существенными из которых являются ограничения на объемы выделяемых ресурсов. Традиционно рассматриваются невозобновимые (финансы) и возобновимые (производственные мощности, персонал) ресурсы [66]. Обзор моделей и алгоритмов решения ЗКП приведен в работах [26, 62].
Как отмечено в [44], задача упаковки в контейнеры эквивалентна простейшей задаче календарного планирования с одним ограниченным ресурсом возобновимого типа и единичными длительностями работ при отсутствии ограничений на порядок выполнения работ. На основании этого, в частности, можно сделать вывод об iVP-трудности ЗКП.
В связи с этим интересно исследование сложностного статуса ЗКП при наличии складируемых ресурсов, представляющих собой своеобразный компромисс между возобновимыми и невозобновимыми ресурсами.
Диссертация состоит из введения, трех глав, заключения, списка публикаций автора по теме диссертации и списка литературы.
В первой главе рассматриваются задачи упаковки в контейнеры и в полосу со случайными входными данными. Для решения этих задач предложены приближенные малотрудоемкие алгоритмы и установлены условия, при которых они являются асимптотически точными.
Условия асимптотической точности алгоритма
Перейдем теперь к оценке точности алгоритма Л\ на классе задач К\. В случае ?-асимметричной функции pr, г = 1,...,Б, применяем алгоритм Лі, полагая характеристическую функцию оценочного списка S равной X(r) = [npr + ArJ , г = 1,..., В. (1.5)
Свойство оценочности (1.3) списка S следует из определения (1.5) и условий (1.4) срабатывания алгоритма Ль
Теорема 2 Алгоритм Лі на классе К\ задач упаковки в контейнеры с В-асимметричной функцией рг имеет оценку относительной погрешности и асимптотически точен при В — o(n/lnn). Доказательство. При Дг = 2(прг(1 — рг)\пп) из В-асимметр-ичности функции рт следует 5-асимметричность функции Аг, так как
Поэтому В-асимметрична и характеристическая функция (1.5) оценочного списка S как целая часть линейной комбинации двух функций, являющихся 5-асимметричными. Оценим относительную погрешность єд = f Fj — Fg) /Fg алгоритма Л\. Введем для удобства следующее обозначение: в r= [(5+1)/21
В качестве оценки снизу для минимального значения целевой функции при нечетных В возьмем число гх5(г) (т.е. количество предметов, имеющих вес больше половины вместимости контейнера), а при четных В к этому числу добавим величину %5(В/2)/2. С учетом (1.4) это дает следующую оценку оптимального значения целевой функции: rs KXs(r)+Xs(l\){ } r(npr - Ar) + (np[B/2$ - Aiy2j) \ 2 Г = = n rZrpr + pLB/2j —y— \ J - ErAr . Получим верхнюю оценку значения целевой функции, после работы алгоритма Лі: F2i Ft = SrXs.(r) + Xz В В + Ґ Er(npr + Дг) + (npB/2j + AB/2j) - - + 2 Оценим д , учитывая, что для Б-асимметричной функции справедливо неравенство Т,грг + Р[в/2\{(В + 1)/2} 1/2 : л Ег(прг + Дг) + (npL2?/2j + ALJ?/2J) { 1} + 2SrAr + 1/2 n (Erpr +pLB/2j (1}) - ГДГ - n/2 - rAr С учетом Дг 2\/nprlnn и ErA/p7 у/В имеем і 1 + В в 8%/n In п = 01 4\/п1ппЕГЛ/р + 1/2 Є7 —: 7==== 8 ЛІ n/lnny В \1/2 п/2-2л/п1ппЕГЛ/р; V n/lnni_4f ,д v.» Vn/lnn/
В силу следствия из теоремы 1 имеем д = o(l/(nlnn)) и, таким образом, алгоритм А\ в условиях доказываемого утверждения имеет оценки єj — О, 5д — 0 при п - оо, то есть является асимптотически точным. Теорема доказана.
Замечание Если максимальный размер предмета ограничен числом R В, то утверждение теоремы 2 можно скорректировать, заменив В на R.
Перейдем теперь к анализу точности алгоритма А\ на классе /С задач с В-регулярной функцией рг. Выпишем разложение функции рг на 2&-симметричные составляющие Pr ,/2=1,..., Ц . Q Pr = Y,Prk) г = 1,...,5. (1.6) Л/ —/Су Введем обозначения для функций (р(х) = пх + 2(nzlnn)1/2, 0 х 1; [ {v?])\ npnk = Q; № = r = 1,..., В \ P (Prk))} при 1 fc Q , и определим список S по его характеристической функции Q XsW E , г = 1,...,Б. (1.7) Лемма 5 Список S, определенный в (1.7), является В-регулярным, а в случае срабатывания алгоритма Л\ и оценочным.
Доказательство. Из 2 -симметричности функций рг следует, что таковыми являются и функции ypj- . Очевидно также, что функции p(pr ) являются 2 -симметричными как линейные комбинации 2 -сим-метричных функций pi- и ург . Отсюда также следует 2&-симметрич-ность функций gr . Все это в целом влечет В-регулярность списка S в силу представления его характеристической функции Xs(r) в виДе суммы 2 -симметричных функций.
Покажем, что при срабатывании алгоритма Лі список S является оценочным. Действительно, в этом случае справедливы неравенства Х(г) [прг + ArJ , г = 1,...,В. С другой стороны, с учетом формулы (1.6) разложения функции распределения и неравенства (%2ІХІ) Y ixi І ХІ 0 убеждаемся в справедливости неравенств (1.3):
Условия асимптотической точности алгоритма Ач .
Рассмотрим теперь класс задач упаковки в полосу двумерных предметов, на множестве которых задано отношение частичного порядка - . При этом условие предшествования щ - о, понимается как требование расположить прямоугольник aj выше прямоугольника а Алгоритм Д2 состоит в последовательном применении алгоритма Ач к подмножествам правильного разбиения списка S = { 2j г = 1,... ,n} , то есть такого разбиения (5А), А = 1,..., Д , что из аг- - aj, аг- Є Sx , оу Є Sx следует 1 Л Л" Л. Класс Кп случайных списков образуем с помощью схемы п последовательных независимых испытаний: на шаге г предмет а{ принимает ширину W( = w и высоту hi = h и помещается в подмножество SXi согласно дискретному распределению вероятностей Pwh\ = Pr{wi = w, hi = h, A,- = A } 0, w H A w = 1,...,W; h = 1,...,H; X = 1,...,A; 2 2]СРіиЛА = L i»=l Л=1 Л=1 Будем говорить, что список S обладает некоторым свойством (симметричности, асимметричности, регулярности), если им обладает вектор (РіАА,Р2ЛАі -,Pwh\) для всех h = 1,..., Н ; А = 1, . . . , Л.
Проведем вероятностный анализ алгоритма Л2 Для И -регулярных списков. Как и ранее, предполагаем, что W = 2 . Обозначим SWh\ = 2\/nPwh\(l - Pwh\) Inn.
Будем считать, что алгоритм Л2 срабатывает на конкретной реализации случайного списка S , если для всякой тройки индексов w,h,X осуществилось событие Awh\, т.е. выполнено неравенство
Рассмотрим частный случай задачи календарного планирования (ЗКП) в условиях ограниченных ресурсов, полная формулировка которой приведена в главе 3. Предполагаем, что выполнены следующие условия: — имеется ограниченный нескладируемый ресурс одного вида, интенсивность выделения которого постоянна на всем протяжении времени выполнения проекта; — на множестве работ не задано отношение предшествования; — директивные сроки выполнения работ отсутствуют, а интенсивность потребляемого работой ресурса постоянна на всем протяжении времени выполнения работы.
Если каждой работе сопоставить прямоугольник, ширина и высота которого равны соответственно интенсивности потребления ресурса и длительности выполнения работы, то задачу нахождения допустимого расписания можно интерпретировать как укладку прямоугольников в полубесконечную полосу, ширина которой равна интенсивности выделения ресурса. При этом каждый исходный прямоугольник разрешается разрезать горизонтальными линиями на полосы, которые будем называть ломтиками. Во всякой допустимой укладке совокупность вертикальных проекций ломтиков образует отрезок, равный высоте прямоугольника. Допускаются также горизонтальные смещения ломтиков. Очевидно, эта задача является iVP-трудной. Действительно, если мы рассмотрим ЗКП, в которой длительности всех работ равны, то полученная задача будет эквивалентна задаче упаковки в контейнеры.
Из приведенной постановки легко заметить, что без разбиения прямоугольников на ломтики предложенная ЗКП в точности совпадает с ЗУП. Разрешение перемещения ломтиков позволяет в ряде случаев построить из оптимального решения ЗУП (которое, очевидно, является допустимым решением ЗКП) более короткое расписание для ЗКП. Следовательно, решение ЗКП можно рассматривать как нижнюю оценку для ЗУП. Решение ЗУП, в свою очередь, является верхней оценкой для ЗКП.
В качестве иллюстрации рассмотрим список из 9 предметов, представленных в таблице 1.1, при упаковке их в полосу с шириной W = 12. Минимальная высота полосы в ЗКП и ЗУП равны соответственно 4 и 5.
Доминируемые решения и максимальные упаковки
Невозобповимые ресурсы ограничиваются для всего проекта в целом, позволяя, например, моделировать бюджет проекта. Ограничение на ресурс невозобновимого типа есть ограничение на выбор тех или иных мод выполнения работ в мультимодальной постановке задачи. В одномодаль-ной постановке данное ограничение не имеет смысла, если требуется выполнение всех работ проекта.1
В отечественных работах [5, 6, 11, 12, 16] используется другая классификация. Ограниченные ресурсы делятся на складируемые (в [15] — сохраняемые) и нескладируемые. Понятие нескладируемого ресурса в точности совпадает с описанным выше понятием возобновимого ресурса. В то же время, хотя ресурсные ограничения складируемого типа также формулируются в виде баланса между потребляемым и выделяемым количеством ресурса, при этом используется другой механизм подсчета потребляемых и выделяемых ресурсов. А именно для каждой работы j и ресурса к задается интенсивность rjk(t) потребления ресурса к работой j в момент t от начала ее выполнения. Для вычисления объема ресурса к, требуемого для выполнения работы j в течение времени т, необходимо проинтегрировать функцию rjkit) по в интервале [0, г]. Аналогично для вычисления объема ресурса &, выделенного к моменту времени г, необходимо проинтегрировать функцию qk(t) интенсивности выделения ресурса к в интервале [0, г]. Для допустимости расписания относительно складируемого ресурса к необходимо, чтобы для каждого момента времени t О суммарный по всем работам объем ресурса, потребляемого к моменту , не превосходил объема ресурса, выделяемого к моменту t. Примером складируемых ресурсов могут служить материалы с длительным сроком хранения.
Нетрудно заметить, что складируемые ресурсы невозможно учесть с помощью комбинации возобновимых и невозобновимых ресурсов. Более того, недавно введенное понятие частично возобновимых ресурсов [25], которое является обобщением возобновимых и невозобновимых ресурсов, также не позволяет описывать ограничения на складируемые ресурсы. В свою очередь, невозобновимый ресурс может рассматриваться как складируемый, весь объем которого доступен с начала выполнения проекта. В этом случае ресурс как бы выделяется с ненулевой интенсивностью до момента начала выполнения проекта, и с нулевой интенсивностью после этого момента.
Складируемые ресурсы интересны по меньшей мере по двум причинам. Во-первых, они более адекватно учитывают специфику некоторых ресурсов, обладающих свойством складируемости. Во-вторых, понятие складируемых ресурсов позволяет расширить возможности для приближенного решения «традиционных» задач календарного планирования, поскольку складируемые ресурсы являются ослаблением возобновимых. Из полученных ниже результатов в частности следует, что можно за полиномиальное время получать нижние оценки для ЗКП с возобновимыми ресурсами.
В работе [15] для ЗКП с ограничениями на складируемые ресурсы был описан алгоритм без обоснования оптимальности получаемого решения и анализа временной сложности. В [16] исследованы основные свойства расписаний со складируемыми ресурсами и на их основе построен алгоритм, из описания которого можно сделать вывод о его псевдополиномиальной временной сложности. В работах [5, 6, 11, 12] для решения ЗКП с длительностями работ из Ш+, директивными сроками и ограничениями на складируемые ресурсы предложен асимптотически точный алгоритм, время работы которого зависит от числа дуг и в графе редукции частичного порядка как функция порядка ulogu, а абсолютная погрешность стремится к нулю с ростом размерности задачи.
В настоящей главе рассматривается дискретный вариант ЗКП, когда все работы имеют целочисленные длительности, а все функции, определяющие ресурсные ограничения (как то: количество потребляемого каждой работой возобновимого ресурса, интенсивность потребления складируемого ресурса, а также функции количества и интенсивности выделяемых ресурсов) являются кусочно-постоянными, причем все интервалы постоянства этих функций являются целыми. Приводится полиномиальный алгоритм решения этой задачи в частном случае, когда в модели отсутствуют ресурсные ограничения возобновимого типа. Такую задачу мы обозначаем PSa, по аналогии с задачей PSn, рассматриваемой в [25]. Для мультимодальной постановки этой задачи (MPSa) выделяется частный случай, когда предлагаемый полиномиальный алгоритм находит оптимальное решение.
Обоснование алгоритма решения задачи PSa на основе Т-поздних расписаний
Для доказательства допустимости S по ресурсным ограничениям достаточно понять, как выглядит график функции JR% (t) (к Є КУ). Из разделенности работ из J и J" барьером D в расписании ST следует, что график функции R (t) совпадает с графиком функции Щ. (t) в интервале [0,/)) и, следовательно, допустим относительно ресурсных ограничений. В интервале [D, D + А"] функция Щ { ) постоянна (и равна Щ. (D)) и также допустима по отношению к функции Qkit)- Наконец, график Щ {і) в интервале [D + А", Т" + А"] есть график функции F(% (t) в интервале [D, Т"], сдвинутый вправо на величину параметра А". По определению этого параметра такой сдвиг графика обеспечивает его допустимость. Покажем теперь, что для любого (целого) Т Т расписание ST недопустимо по ресурсам (а следовательно, по утверждению 10, допустимого расписания длины Т не существует ни при каком Т Т , откуда следует оптимальность расписания ST ).
Действительно, недопустимость Т-позднего расписания ST при любом Т Т" следует из недопустимости ST" и утверждения 9. При любом Т Т" график функции Щ(г) в интервале [D + T- Т", Т] = [Т - Т , Т] совпадает с графиком функции Щ. (t) в интервале [Z),T"], сдвинутом вправо на величину А = Т - Т". Если Т Т , то А Т - Т" = А". По определению параметра А" = А (Г") найдутся к Є Ка и t Т" такие, что Щ (t) Qk{t + А ), а следовательно,Т-позднее расписание ST недопустимо по ресурсу к. Случай 3 (А" = 0)
Согласно утверждению 11 при А (Г") = А" = 0 расписание ST" допустимо; следовательно, длина Copt оптимального расписания принадлежит интервалу [Г , Т"\. По утверждению 10 Copt совпадает с минимальным значением Т, при котором расписание ST допустимо. Из утверждения 9 следует, что для нахождения такого минимального Т можно использовать дихотомический поиск в интервале [Т", Т"] с помощью следующей процедуры.
В процедуре Ро при различных значениях Т требуется построить Т-позднее расписание и проверить его допустимость относительно каждого ресурсного ограничения. При проверке допустимости расписания ST воспользуемся критерием в форме утверждения 11, в котором фигуриру ет величина А(Т), для вычисления которой необходимо знать функции объемов выделенного Qk{t) и потребляемого Щ(t) (при расписании ST) количества ресурса к. Поскольку обе функции кусочно-линейны, то они полностью определяются значениями в своих узлах (т. е. в точках, где происходит изменение линейного коэффициента функции). Таким образом, необходимо найти все узлы функций Qk{t) и Rk{t), к Є /Сст, после чего становится возможным вычисление параметра А(Т) и установление допустимости расписания ST.
Отыскание узлов функции R%{t) Опишем алгоритм AR(T) отыскания убывающей по времени последовательности у, уі,... узлов функции Щ. (t) для каждого к Є Ка. (При этом узлами функции Щ(t) будем считать все точки, в которых происходит изменение интенсивности потребления ресурса к хотя бы одной из работ, а также точки, совпадающие с директивными сроками.) Попутно в алгоритме будет построено Т-позднее расписание ST, так что его предварительного построения не требуется.
Узел у будет отождествляться с парой (, R) = (t(yk), R(ylk)), где t и R — значения t и Rk(t) в узле у\. Информацию о директивных сроках будем считать заданной в виде упорядоченного по возрастанию списка V различных директивных сроков. (Такой список может быть построен на этапе 2 алгоритма Л по списку директивных сроков, заданных для всех работ j Є Jdir-)
Похожие диссертации на Точные и асимптотически точные алгоритмы для задач упаковки и календарного планирования
