Федеральное государственное автономное образовательное учрежение высшего образования
жүктеу/скачать 5,2 Mb. Pdf көрінісі
|
| ГЛАВА 3
КОМБИНАТОРНЫЕ МОДЕЛИ И АЛГОРИТМЫ ДЛЯ НЕКОТОРЫХ ЗАДАЧ ОПТИМИЗАЦИИ Попов Виталий Борисович кандидат физико-математических наук, доцент
технологии широко применяются для решения различных задач, возникающих в экономике, управлении, проектировании и других сферах экономической деятельности. Значительное внимание уделяется использованию моделей и методов дискретной и комбинаторной оптимизации. Это обусловлено необходимостью решать достаточно сложные задачи с большим числом возможных вариантов и выбирать из них наилучшие с учетом различных ограничений. Использование моделей и алгоритмов дискретной математики, в частности, дискретной оптимизации, делает возможным решение разнообразных прикладных технико-экономических задач, таких, как задачи размещения экономических объектов, к ней относятся простейшая и многостадийная задача, задачи размещения с предпочтениями клиентов, задачи стандартизации и унификации, а также задачи, которые являются актуальными для проектирования и разработки современных корпоративных информационных систем, для построения автоматизированных рабочих мест специалистов аналитиков. Большую роль алгоритмы оптимизации производства оказывают на архитектуру и методы построения современных корпоративных информационных систем, которые являются важнейшими составляющими любой
современной экономической структуры. Эти алгоритмы решают задачи размещения экономических объектов; проблемы оптимизации корпоративных информационных систем планирования ресурсов (Enterprise Resource Planning, ERPII); задачи оптимизации цепочек предложений (SCM) и связанные с ними задачи логистики. Отметим, что задача планирования потребностей в
358
материалах (Materials Requirements Planning, MRP) оказалась первой задачей, которая привела к созданию целой индустрии программного обеспечения для управления предприятием, в основе которого лежат алгоритмы комбинаторной и дискретной оптимизации. Следующая концепция развития корпоративных систем получила название MRPII. В свою очередь ERPII представляет собой уже не класс систем управления, а методологию организации бизнес-процессов предприятия. Важной особенностью проектирования систем управления предприятием на принципах ERP является направленность на планирование ресурсов производства. Большинство функций учета, реализованных в этих системах, служат лишь дополнением к основной задаче по составлению планов поставок материалов, управление производством. Эволюция развития стандартов прошла от MRP до самых современных систем с методологией ERPII, в которых используются последние результаты искусственного интеллекта. Это обусловливает актуальность данной работы.
и дискретного программирования предложено и на практике успешно применяется большое число алгоритмов и методов решения оптимизационных задач. Эти алгоритмы успешно используются для
оптимального решения
проблем в корпоративных информационных системах. В классе
комбинаторных методов решения широко известны следующие алгоритмы: метод частичного порядка [1], метод ветвей и границ [2], локальные алгоритмы Ю. И. Журавлева [3], метод последовательного анализа и отсеивания вариантов, предложенный В. С. Михалевичем, Н. З. Шором [4], последовательные схемы
В. А.
Емеличева [5,6],
аппроксимационно-комбинаторный метод
[7], метод
динамического программирования [8], приближенные методы, различные эвристики для решения задач дискретного программирования, методы глобальной оптимизации для решения задач смешанного нелинейного целочисленного программирования, методы отсечения, декомпозиционные методы, гибридные методы. Большое количество задач дискретной и комбинаторной оптимизации формулируются в виде 359
} | ) ( { max
X f , где R Μ 2 : f – монотонная неотрицательная функция от X , – непустое конечное множество, – семейство максимальных по включению множеств семейства подмножеств Μ 2 . Например, одной из важных задач является разработка алгоритмов поиска экстремальных значений субмодулярных функций в геометрической решетке. Задачи оптимизации модулярных и супермодулярных функций возникают в различных областях дискретной математики, ее приложениях, в частности, в экономике и изучались в течение ряда лет многими авторами. Важная роль методов дискретной оптимизации или дискретного программирования в экономических приложениях обусловлена тем, что дискретные оптимизационные модели используют концепцию неделимости объектов, учитывают особенности ограничений логического типа, наиболее адекватно передают то, что называется нелинейными характеристиками и удовлетворяют другим требованиям, присущим объектам соответствующей предметной области. Нерешенные проблемы. В тоже время многие задачи комбинаторного и дискретного программирования являются NP– трудными. Подавляющее число практических задач содержат большое число переменных задачи оптимизации и ограничений, что приводит к большим сложностям во время решения этих задач. С этой точки зрения исследование существующих и разработка новых подходов к решению задач дискретного программирования, а также применение получаемых результатов в экономических приложениях представляется актуальным. Утверждение, что задачи дискретной оптимизации и их различные обобщения, как правило, являются NP–трудными, требует построения эвристических алгоритмов, которые могут быть использованы в прикладных исследованиях [9,10,11]. В последние годы в области дискретной оптимизации в этом направлении активно велись разработки методов локального поиска, известных как алгоритмы муравьиной колонии, поиска с запретами, генетические алгоритмы и др. [12–18]. Построение алгоритмов такого типа представляется перспективным и для рассматриваемых нами задач, возникающих на этапе технической подготовки производства. 360
Рассмотрим основные алгоритмические подходы и понятия, используемые в задачах комбинаторной оптимизации.
В научной литературе описывается широкий класс алгоритмов решения оптимизационных задач, которые имеют название «жадный алгоритм» (семейство Greedy Algorithm). Термин «жадный алгоритм» употребляется по отношению к довольно разнообразным алгоритмам решения дискретных оптимизационных задач. Иногда для теоретических целей ему придают какое-либо точное значение, но, в общем, он имеет не очень четко определенную область применения. Так называют алгоритмы, в которых на каждом шаге делается выбор, дающий наибольший эффект. Известно, что алгоритмы, предназначенные для решения задач оптимизации, обычно представляют собой последовательность шагов,
на каждом
из которых
предоставляется некоторое множество выборов. Это не обязательно наибольшее приращение целевой функции, эффект может заключаться в чем-то другом, по видимости полезном для поиска наилучшего итогового решения. В жадном алгоритме всегда делается выбор, который кажется самым лучшим в данный момент. При таком подходе производится локально оптимальный выбор в надежде, что он приведет к оптимальному решению глобальной задачи. Иногда жадные алгоритмы называют градиентными, тем самым подчеркивая алгоритмическую близость к градиентному спуску – известному методу решения непрерывных задач. Распространенность жадных алгоритмов связана в первую очередь с их быстродействием. В большинстве случаев жадные алгоритмы не гарантируют оптимальности решения задачи в целом, и не всегда приводят к оптимальному решению, можно считать, что они являются эвристическими или приближенными методами решения
оптимизационных комбинаторных задач. Поэтому жадные алгоритмы относят к классу интуитивных эвристик, в которых на каждом шаге принимается решение, являющееся наиболее выгодным в данный момент, без учета того, что происходит на последующих шагах поиска. Но есть задачи, при решении которых они дают нужный результат, для которых решение, полученное жадным
361
алгоритмом, всегда оптимально. В научной литературе достаточно изучены задачи оптимизации, пригодные для решения с помощью жадных алгоритмов. Имеется большое число публикация по этой тематике. Можно выделить следующие из них. Впервые в 1926 году подобный алгоритм был предложен О. Борувкой [19]. В дальнейшем алгоритм упоминается в работе [20], в которой этот алгоритм применялся для решения задачи об оптимальном остовном дереве графа. Обширное количество материала по жадным алгоритмам и матроидам представлено в монографиях Лоулера (Lawler) [21], Пападимитриу (Papadimitriou) [22] и Стайглица (Steiglitz) [22]. Впервые жадный алгоритм был описан в литературе по комбинаторной оптимизации в статье Эдмондса (Edmonds) [23, 24].
Семейства независимых множеств Примем следующее определение – «Трансверсалью произвольного семейства множеств C называется множество (не обязательно из C), обладающее непустым пересечением с каждым множеством из C, а поперечником (C) этого семейства называют мощность наименьшей его трансверсали». При оперировании с этими понятиями всегда можно без нарушения общности считать C классом, поскольку исключение повторяющихся множеств из семейства не влияет на его трансверсали. Пусть C = { n U U U ,...,
, 2 1 } – конечное семейство непустых конечных множеств, a W=
1 . Один из алгоритмов нахождения трансверсалей T
алгебре высказываний, был предложен X. Магу [25] для графов. Следующее определение независимого семейства множеств взято из [26]. Определение. Конечное семейство C = { n U U U ,...,
, 2 1 }, где 1 n , называется независимым, если существует такая перестановка n j j j U U U ,...,
, 2 1 его множеств, при которой ) \ ( } ..., , 2 , 1 { 1 1
i i j r j U U n r , (
0 1 i i j U ).
362
Семейство множеств, не допускающее таких упорядочений, зависимо. Пустое семейство множеств считают независимым по определению. Из этого определения непосредственно следует, что
} {U , состоящее из единственного множества, независимо тогда и только тогда 0 U ; Семейство } ,
U U из двух совпадающих множеств всегда зависимо;
Всякое подсемейство независимого семейства независимо (тогда,
семейство, содержащее зависимое подсемейство, само зависимо). Рангом
множеств, образующих независимое подсемейство. Ранг семейства не меняется при удалении из него пустого множества и повторения множеств. Пусть C 1 , C 2 ,…, C s – все различные минимальные зависимые подсемейства заданного семейства C = { n U U U ,...,
, 2 1 }. Рассматривая C i как множества, элементами которых служат n U U U ,...,
, 2 1 , можно образовать трансверсали семейства S = {C 1 , C 2 ,…, C s }. Лемма. Подсемейство C ’
тогда, когда его дополнение C \ C
является трансверсалью для S. Доказательство. Действительно, C ’ независимо в том и только том случае, если никакое зависимое C
равносильно, никакое минимальное зависимое C
не является подсемейством C’, т.е. когда } ,..., 2 , 1 { n r (C r
(C\ C’)) . Последнее означает, что C\ C ’ – трансверсаль для S. Следствие. (C) =
( S). Исходя из вышесказанного, для того чтобы найти ранг данного семейства множеств C = {
,...,
, 2 1 } и выявить его наибольшие независимые подсемейства используют информацию, для которой достаточно знать множество S всех минимальных зависимых подсемейств у C. Вместо S рассматривают любое множество зависимых подсемейств, которое содержит все минимальные, поскольку для
трансверсалей такая замена не отражается на их структуре.
363
3.3. Наследственные системы
Наследственные системы, являются универсальными комбинаторными объектами, которые сочетают в себе черты систем независимости – систем подмножеств конечного множества, обладающих свойством наследственности, и систем множеств с аналогичным свойством наследственности «вверх». В научной литературе доказано, задачи оптимизации и аппроксимации на наследственных системах являются математическими моделями множества сложных
в вычислительном плане практически важных задач. Основные понятия наследственных систем. Пусть U – конечное множество и S
– непустое семейство его подмножеств, удовлетворяющее аксиоме наследственности:
2 U , ' ' A A A 2 U . Пара S (U,S) называется системой независимости или наследственной системой на U. Множества семейства S называются независимыми, все остальные подмножества U – зависимыми. Семейство всех зависимых множеств обозначим D. Говорят, что D обладает свойством наследственности «вверх», т.е. выполняется
D, ' ' D D D D. Каждое из семейств однозначно определяет наследственную систему
(U,S) либо
(U,D). Базами системы
называются максимальные по включению независимые множества, а циклами – минимальные по включению зависимые множества. Объектами исследования на
независимых системах являются оптимизационные задачи типа: }, |
( min{
}, | ) ( max{
C X X f X X f
где B – семейство всех баз, C – семейство всех циклов некоторой наследственной системы
, : f
U
R
– неотрицательная функция, определенная на множествах.
Матроиды
Матроиды и коматроиды являются частными случаями наследственных систем. Впервые упоминаются в 1930 году, когда Ван дер Варден предложил аксиоматический подход к понятию линейной и алгебраической независимости. Термин «матроид» был введен Хасслером Уитни (Hassler Whitney) в середине 30-х 364
годов. В [27] Х.Уитни обнаружил, что можно с единых позиций рассматривать понятия зависимости в линейной алгебре и теории графов. В работе изучались матричные матроиды элементами, которых являются строки заданной матрицы. Множество строк является независимым, если они линейно независимы в обычном смысле. На настоящий момент наиболее полное и
найти в монографиях Д. Уолша [28] и Г. Оксли [29]. Можно выделить статьи [30, 31]. В этих статьях матроиды изучаются в первую очередь как упорядоченные структуры, а именно как комбинаторные геометрии – полумодулярные геометрические решетки Матроид (matroid) – это упорядоченная пара M = (A,S), удовлетворяющая сформулированным ниже условиям. 1.
Множество A конечное. 2.
S – непустое семейство подмножеств множества A (которые называются независимыми подмножествами), таких, что если
S и B A , то
A S. Если семейство S удовлетворяет этому свойству, то его называют наследственным (hereditary). Заметим, что пустое множество
с необходимостью принадлежит семейству S. 3.
A S,
S и B A , то существует такой элемент B A x \ , что } {x A S. Говорят, что структура M удовлетворяет свойству замены (Exchange Property). Системой подмножеств ) , ( J E S называется конечное множество
вместе с семейством J подмножеств множества E , замкнутым относительно включения, т.е. если J A и
A A ' , то J A ' . Элементы семейства J
называются независимыми. Подмножество E B , не входящее в J , называется зависимым. Комбинаторная задача
оптимизации для
системы подмножеств ) ,
J E S формулируется следующим образом. «Для каждого
задан вес 0 )
e w . Требуется найти независимое подмножество, имеющее наибольший общий вес».
begin
: I
365
while E do
begin пусть
e – элемент из E с наибольшим весом; удалить
из
E ; if )
( e I J then
e I I :
end end. Р. Радо [32] и Дж. Эдмондс [23, 24] установили разрешимость задачи поиска базы матроида максимального веса посредством жадного алгоритма. Определение. Система подмножеств ) , ( J E S является матроидом, если жадный алгоритм корректно решает любую индивидуальную комбинаторную задачу оптимизации для системы
.
Пусть ) , ( J E S – система подмножеств. Тогда следующие утверждения эквивалентны:
S – матроид;
S I I p p 1 , , где
p I p и 1 1
I p , то существует такой элемент
\ 1 , что J e I p ;
если E A и
1 , I I – максимальные по включению подмножества множества
, то
1 I I .
3.5. Решетки
ограниченная дистрибутивная решетка, т.е.
дистрибутивная решетка с наименьшим элементом 0 и наибольшим элементом 1 0 и операциями ) , ( . Следующие определения можно найти в [34]. Определение. Решетка L называется модулярной, если в ней выполняется модулярный закон – «если z x , то
z y x z y x ) ( ) ( ». Это имеет место в любой дистрибутивной решетке. Г. Биркгофом [33] были введены условия полумодулярности для решеток конечной длины и была показана большая важность класса полумодулярных решеток.
условиям: 1.
b a и оба элемента a и
b покрывают c , то
b a
покрывает и a , и
b ;
366
2.
двойственно, если b a и
c покрывает оба элемента a
и b , то
a и
b оба покрывают b a ,
называются полумодулярными. Определение. Точечной (или «атомарно порожденной») называется решетка, в которой каждый элемент является объединением точек. Геометрическая решетка (или «матроидная решетка») – это конечномерная полумодулярная (сверху) точечная решетка.
Решетка
L называется решеткой с дополнениями, если в ней для любого a L существует
L такой,
1 , 0 b a b a .
относительными дополнениями, если в ней из того, что
, следует существование y , для которого b y x a y x , .
Геометрические или матроидные решетки
Пусть L – решетка, p z y x b a , , , , , – элементы решетки. Говорят, что элемент b покрывает элемент a в решетке L, или элемент
покрывается элементом b в решетке L, и пишут b a или
b a , если интервал x b a { ] , [
} |
x a решетки L состоит точно из двух элементов a и
b .
Элемент решетки x покрывает подмножество решетки Y , если для каждого Y y выполнено x y и в решетке нет элемента z , удовлетворяющего неравенствам Y y y z x . Этот факт обозначают следующим образом x Y .
снизу или называется полумодулярной снизу, если выполняется y x x y x y x y , ,
Определение. Решетка L удовлетворяет условию покрытия сверху
или называется полумодулярной сверху,
если выполняется
x y x y x y x , ,
Определение. Решетка L называется атомарной, если в ней есть минимальный элемент min(
L ) и подмножество элементов (атомов) вида a a Αt | { L } , a обладает свойством: если
x, L и y x , то
) ( } , | { ) (
At x z At z z x Αt . Другими словами, решетка L называется атомарной, или точечной, если любой элемент
L является верхней гранью атомов, т.е.
a sup{
L } | a p
.
367
Определение. Решетка называется геометрической или матроидной, если она атомарная и полумодулярная. Идеалы решеток определяются следующим образом. Пусть (L,≤) – частично-упорядоченное множество. Подмножество I
называется (порядковым) идеалом, если выполняется
y x y I. Двойственным образом, подмножество F
называется (порядковым) фильтром, если
F, y x y F.
Пучки решеток Пучки стали активно использоваться в исследованиях по математике после открытия их Ж. Лере в 1945 году. История структурных исследований алгебраических структур кратко описывается, например, в работе [38]. Представлениями алгебраических систем сечениями пучков занимались И. Ламбек [35], Р. Пирс [36], К Хофман [37] и другие. Благодаря их работам пучки
становятся неотъемлемым инструментом такой
дисциплины как алгебраическая топология. Приведем одно из определений пучка: с точки зрения пучковых представлений пучок можно понимать, во-первых, как обобщение конструкции алгебры ??????(??????) непрерывных функций на топологическом пространстве. Отличительной особенностью пучка (??????, ??????) при этом является то, что функции принимают значения не в одном объекте, а в различных алгебрах для различных точек из ??????. Во-вторых, пучковое представление алгебры ?????? можно понимать, как подпрямое произведение алгебр ??????
?????? той же сигнатуры, что и у ??????, индексированных точками некоторого топологического пространства. В последствии были исследованы и некоторые иные пучковые конструкции. В результате были получены различные изоморфные представления. Значительное число научных работ по указанной тематике привело к появлению общих конструкций, таких как: компактность представлений, их полнота и др. Были выявлены связи между различными функциональными представлениями. И наконец, оформлена теория пучковых представлений для колец. Было получено несколько результатов по представлениям для ограниченных дистрибутивных решеток, почти-колец, решеточно-упорядоченных групп и колец.
368
Наиболее важным представлением для дальнейших исследований является представление Пирса. В фундаментальной работе [36] Пирсом построены пучки колец и модулей на стоуновском пространстве кольца. Любое кольцо изоморфно кольцу сечений своего пирсовского пучка. Среди отечественных работ по теории пучковых представлений можно выделить работы Е. М. Вечтомова [39], В. В. Чермных [38, 40, 41] и др. В работе [35] был предложен алгоритм построения частично упорядоченного множества (ЧУМ), решетка идеалов которого изоморфна решетке оптимальных решений в задаче минимизации так называемой субмодулярной функции. Далее рассмотрим вопросы представления геометрических решеток сечениями пучков. Непустое подмножество I дистрибутивной решетки L называется идеалом решетки L, если b a, I выполняется условие I
, b a b I. Идеал
I дистрибутивной решетки
называется собственным, если I L. Собственный идеал P
дистрибутивной решетки L
называется простым, если
b a L b a, P b P a . Для любого идеала P множество } 0
( | { t l P t L l O P
называется 0-компонентой идеала P . Верно следующее утверждение. Пусть a – некоторый элемент в L, и пусть главный идеал P a простой. Тогда a неприводим. Через
L Spec обозначается множество всех простых идеалов решетки
. Для любого идеала A решетки L пологают } |
) (
P L Spec P A D
и показывают, что L Spec
является топологическим пространством с семейством открытых множеств вида ) ( A D . Множество }} 0 { | { }) 0 ({ P L Spec P D пусто, а L Spec L D ) ( . Пусть
i A B A , , – идеалы решетки L . Тогда
). ( } | } ) ( | { ) ( ) ( } | } & | { ) ( ) (
i i i i i i A D P A L Spec P A P A L Spec P A D B A D B A P L Spec P B P A P L Spec P B D A D Таким образом, на L Spec вводится топология, которую называют топологией Зарисского. Топологическое пространство
с топологией Зарисского называется простым спектром 369
решетки L . Функциональным (пучковым) представлением решетки
называется полукольцевой гомоморфизм ) ,
: X P Г L
решетки L в решетку ) ,
X P Г глобальных сечений некоторого пучка
решеток над топологическим пространством X . Ограниченная дистрибутивная решетка L изоморфна полукольцу глобальных сечений пучка P L / на
L Spec . Решетки в таком контексте исследовались, например, в работах [39–43]. Представляет определенный интерес рассмотреть две составляющие исследования – это
теория пучковых представлений алгебр и теория решеток, в частности геометрических решеток.
1. Ковалев М.М. Матроиды в дискретной оптимизации / М.М. Ковалев – М.: Едиториал УРСС. 2003. – 224с. 2.
Land A. H., Doig A. G. An automatic method of solving discrete programming problem / A. H. Land, A. G. Doig. // Econometrica, Vol. 28, No. 3. –1960. – pр. 497–520. 3.
Журавлев Ю. И. Избранные научные труды / Ю. И. Журавлев // М.: Магистр. 1998. – 420 с. 4.
их применение. 1. / В. С. Михалевич // Кибернетика. 1965. №2. С. 85–88. 5.
Емеличев В. А. Дискретная оптимизация: последовательные схемы решения. / В. А. Емеличев // Кибернетика.– 1971. №6. С. 109–121. 6.
схемы решения. 2. / В. А Емеличев // Кибернетика. 1972. №2. С. 109–121. 7.
Хачатуров В. Р., Веселовский В. Е., Злотов А. В. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности / В. Р. Хачатуров, В. Е. Веселовский, А. В. Злотов // М.: Наука. 2000. – 354 с. 8.
пер. с англ. – М.: Изд-во иностр. Лит. 1960. – 400 с. 9.
Введение в исследование операций. Пер. с англ./ Таха Хемди, А. М.: Издательский дом «Вильяме», 2001. - 912 с. 10.
Мину. М.: Наука, 1990. - 488 с. 11.
Целочисленное программирование и потоки в сетях. Пер. с англ./ Т.С. Ху. М.: Мир, 1974. - 519 с. 12.
Glover F., Laguna M. Tabu Search / F. Glover., and M. Laguna // C.R. Reeves (ed.) Modern Heuristic Techniques for Combinatorial Problems, Oxford. 1993. Pр.70 - 150. 370
13.
Van Laarhoven, P.J.M., Aarts, E.H.L. Aarts. Simulated Annealing: Theory and Practice / P.J.M., Van Laarhoven, E.H.L. Aarts // Kluwer Academic Publishers, Dordrecht, 1987. 512 р. 14.
Edited by E.Aarts and J.K.Lenstra, John Wiley & Sons Ltd. 1997. 15.
Beasley J.E. Lagrangean heuristic for location problems / J.E. Beasley // European Journal of Operational Research, 1993. № 65. P. 383 –399. 16.
Distributed optimization by ant colonies / A. Colorny, M. Dorigo, V. Maniezzo // In Proceedings of the First European Conference on Artifical Life, Elsevier, 1992. P. 134 –142. 17.
Stutzle // MIT Press, 2004. 18.
Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И.. Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, и др. // М.: Наука, 1990. - 344 с. 19.
Pfidovedecke Spolecnosti (Acta Societatis Scientiarium Moravicae). 1926. V. 3. Pр. 37-58. 20.
travelling salesman problem / J. B. Kruskal // Proc. Amer. Math. Soc. 1956. V. 7, N 1. P. 48-50. 21.
Lawler // N.Y.: Holt, Reinhart and Winston. 1976. – 367 p. 22.
Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность: Пер. с англ. / Х. Пападимитриу, К. Стайглиц. – М. : Мир. 1985. – 512 с. 23.
/ J. Edmonds // Combinatorial Structures and their Applications. New York: Gordon and Breach. 1970. Pр. 69-87. 24.
Math. Programming. 1971. V. 1, N 2. Pр. 127-136. 25.
Maghоut Kh. Sur la determination des nombres de stabilite et du nombre chromatique d'un graph / Kh. Maghоut // G. R. Acad. Sci. – Paris. 1959. – Pр. 3522–3523. 26.
Т. 29. Вып. 6. С. 89-154. 27.
Whitney H. On the Abstract Properties of Linear Dependence / H. Whitney – American Journal of Mathematics, Vol. 57, No. 3 (Jul., 1935), pp. 509-533 28.
Press. 1976. – 433 p. 29.
Oxley J.G. Matroid Theory / J.G. Oxley // N.Y.: Oxford Univ. Press. 1992 – 532 p.
371
30.
Crapo H.H., Rota G.G. On the foundations of Combinatorial Theory. Combinatorial Goemetrics / H.H. Crapo, G.G.Rota // M.I.T. Press. Cembridge Mass. 1970. – 215 p. 31.
Acad.Sc. 1970. – Pр. 89-92. 32.
Rado R. Note on independence functions / R. Rado // Proc. London Math. Soc. 1957. V. 7, N 3. P. 300-320. 33.
Биркгоф Г. Теория решеток: Пер. с англ. / Г. Биркгоф – М.: Наука. 1984. – 568 с. 34.
Писарук Н. Н. Представление решетки оптимальных решений в задаче минимизации субмодулярной функции / Н. Н. Писарук // Журнал вычислительной математики и математической физики. – 1989. – том 29. № 9. с. 1426–1431. 35.
Ламбек И. Кольца и модули // И. Ламбек.: – М. – Мир, 1971. - 280 c. 36.
Pierce R. S. Modules over commutative regular rings // Mem. Amer. Math. Soc. – 1967. – Vol. 70. – P. 1–112. 37.
Hofmann K. H. Representations of algebras by continuons sections // Bull. Am. Math. Soc. – 1972. – Vol. 78, № 3. – P. 291–373. 38.
В. В. Чермных. Функциональные представления полуколец. Фундаментальная и прикладная математика, 2011/2012. – том 17, № 3, с. 111–227. 39.
представимые цепями // Фундаментальная и прикладная математика. – 1996. – Т. 2, № 1. – С. 93–102. 40.
Вятского гос. гуманитарного. ун-та. 2005. – № 13. – С. 151–158. 41.
Чермных В. В. Пучковые представления полуколец // Успехи мат. наук. 1993. Т. 48, № 5. С. 185 – 186.
|