Алгоритмическое и программное обеспечение для задачи выбора комплектов оборудования тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Гончаров, Евгений Николаевич

• Гончаров, Евгений Николаевич
• кандидат физико-математических наук
• 2001

Оглавление диссертации кандидат физико-математических наук Гончаров, Евгений Николаевич

Введение

1 Задача выбора комплектов оборудования и ее связь с задачей размещения

1.1 Содержательная постановка задачи

1.2 Математическая постановка задачи.

1.3 Обзор задач, обобщающих простейшую задачу размещения

1.3.1 Модель размещения производства с двухэтапной обработкой продукции.

1.3.2 Задача размещения предприятий и складов

1.3.3 Двухэшелонная задача размещения.

1.3.4 Задачи минимизации полиномов от булевых переменных и выбора множества строк.

1.3.5 Двухуровневая задача стандартизации.

2 Точные алгоритмы

2.1 Общие характеристики метода ветвей и границ.

2.2 Квазитупиковый алгоритм нахождения нижней оценки для целевой функции

2.2.1 Об алгоритме нахождения нижних оценок задачи в общем случае.

2.2.2 Алгоритм вычисления верхней оценки.

2.2.3 Результаты тестовых расчетов

2.3 Нижняя оценка для значений полинома от булевых переменных

2.3.1 Алгоритм построения приближенного решения задачи минимизации полинома от булевых переменных

2.3.2 Результаты вычислительных экспериментов

3 Вероятностные жадные алгоритмы

3.1 Вероятностные жадные алгоритмы.

3.2 Алгоритм "Лидер группы".

3.3 Условия дополняющей нежесткости.

3.4 Алгоритм "Случайный аутсайдер".

3.5 Принцип ветвления.

4 Вероятностные алгоритмы поиска с запретами

4.1 Вероятностный алгоритм поиска с запретами.

4.2 Цепи Маркова

4.3 Варианты вероятностного алгоритма поиска с запретами

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

Введение диссертации (часть автореферата) на тему «Алгоритмическое и программное обеспечение для задачи выбора комплектов оборудования»

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

Первая глава посвящена обзору моделей, обобщающих задачу размещения.

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

В разделе 1.2 приводится математическая формулировка задачи. Для известных множеств J, /, L потребителей, типов изделий и типов комплектов соответственно, заданных величин fi и gi - начальных затрат, связанных с организацией производства изделий и с формированием комплектов, величин сц - стоимости удовлетворения спроса потребителей комплектами, при участии переменных выбора z\, yi комплектов и изделий, а также переменных назначения хц найти {Ylgizi + ^+Y.J2f' м leL iel jeJ leL ) при ограничениях leL

Zi ^ Xij, I G L, j G J, (3) m > YlG W

Zu Vi, Щ e {0,1}, l G L, г G /, j G J. (5)

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

Задача (1)-(5) обобщает относительно хорошо исследованную простейшую задачу размещения. Задачи, обобщающие простейшую задачу размещения, рассматривались рядом исследователей. Михалевич, Тру-бин, Шор [40] предложили модель многоэтапной задачи размещения. Эта задача отличается наличием нескольких уровней производства продукции, через которые проходит сырье, прежде чем превратится в готовую продукцию и поступит к потребителю. Этими же авторами решалась задача выбора типов и мест базирования вертолетов, предназначенных для выполнения ими в различных пунктах заданного района комплекса работ различных видов. При этом разные виды работ могли быть выполнены разными типами вертолетов с различными производительностями и затратами, которые зависят также от мест базирования вертолетов и от мест выполнения работ. Кроме суммарных затрат на выполнение работ, учитывались затраты на производство и приобретение технических средств, а также затраты на их размещение и техническое обслуживание.

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

В работе Barros и Labbe [53] была предложена модель задачи размещения предприятий и складов. Эта модель по своей сути является задачей выбора комплектов оборудования, где совокупность маршрутов, проходящих через склад, представляют собой (в терминологии настоящей диссертации) комплекты, а пары, состоящие из предприятия и склада, через который это предприятие оперирует — это множество изделий, входящих в данный комплект. Аналогичная двухуровневая (twolevel) модель размещения предприятий с некоторыми дополнительными ограничениями, была предложена в [75]. Многоуровневый вариант этой же модели был рассмотрен в [76]. В обоих случаях для решения этой задачи применялся метод ветвей и границ. В [72] рассматривалась двухстадийная задача размещения с дополнительными ограничениями на объемы производства, для решения которой применялся метод лагранжевых релаксаций.

В работе Gao и Robinson [65] рассматривалась еще одна модель, обобщающая простейшую задачу размещения, названная авторами двухэшелонной. Для ее решения были привлечены идеи теории двойственности и теории линейного программирования. Аналогичная двухэшелонная задача размещения с дополнительными ограничениями рассматривалась также в [77] и, в динамической постановке, в [71].

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

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

Обозначим через I множество {1,., га}, а через J' и J — соответственно множества {1,., п'} и {1,., п}. Пусть F = (fu) и С = (cjj) — матрицы размера т х п' и т х п соответственно. Задачей выбора множества строк назовем задачу отыскания минимума функции f{xb ., хт) = max fu + V" min dj i\xi=1 L—' i\Xi=1

Ш' 1 jeJ 1 от булевых переменных.

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

R / \ S

Р(УЪ • • • , Ут) = ао + «г ( 1 - П Уг + bs П r= 1 \ г£аг / s—1 ieps где аг С I, аг > 0, г = 1,., R, и Д, С I, bs > 0, s == 1,., S.

Коэффициенты при нелинейных членах полинома р(уi,., ут) имеют произвольные знаки.

В [10] и в [9] показывается, что эти задачи и задача выбора комплектов оборудования эквивалентны и, более того, могут рассматриваться как различные формы записи одной и той же задачи.

JI.E. Горбачевской, В.Т. Дементьевым, Ю.В. Шамардиным [33] изучалась двухуровневая задача стандартизации в следующей постановке. Пусть I = {1,. ,п} ~ множество изделий; J = {1,., га} — множество потребителей; с® — затраты на подготовку производства изделия г; — затраты, связанные с производством и реализацией изделия г потребителю j; dij — закупочные и эксплуатационные расходы потребителя j при использовании изделия ц xi — переменная выбора производителем изделия г (х{ G {0,1}, х — (ж*)); 1{х) = {г £ / | Х{ = 1} — список изделий, выбираемых в варианте х; X — множество всех векторов х ф 0 с компонентами 0 и 1; уц — переменная выбора потребителем j изделия г (yij £ {0,1}, у = (yij)); Y(x) — множество возможных вариантов у потребительского выбора. Оно описывается ограничениями: yii = 1} Уч ^ 3 е Jiel

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

Задача верхнего уровня (производственная):

F(x, у*) = У] c°iXi + У2 У1ЫУЬ ~* min' (6) X iel iel jeJ где у* — оптимальное решение задачи нижнего уровня (потребительской) :

У) = S di№з ^ m2/in' У е YМ■ (7) iel jeJ

В [33] была установлена эквивалентность задачи выбора комплектов оборудования и двухуровневой задачи стандартизации.

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

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

Эта задача принадлежит к классу труднорешаемых задач [34], и потому маловероятно, что удастся найти эффективный алгоритм ее решения. В данной диссертации для точного решения задачи выбора комплектов оборудования применяется метод ветвей и границ [10]. В разделе 2.1 приводится общая характеристика метода ветвей и границ. Большое значение для успешности работы метода ветвей и границ имеет эффективность вычисления нижней оценки для целевой функции. В разделе 2.2 для частного случая задачи — без учета начальных затрат на производство и формирование комплектов — описан алгоритм нахождения нижней оценки для целевой функции. С этой целью рассматривается релак-сированная задача, получаемая заменой условия булевости переменных задачи на условие их неотрицательности. Для нахождения нижней оценки рассматривается двойственная ей задача и ищется ее приближенное решение, основанное на построении так называемого квазитупикового решения двойственной задачи. Показывается, что временная сложность этого алгоритма равна 0(ILJ(L + logl)).

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

В разделе 2.2.2 представлен полиномиальный алгоритм нахождения верхней оценки для рассматриваемой задачи. При построении этого алгоритма используется жадный алгоритм с временной сложностью 0(I2JL).

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

В разделе 2.3 представлен метод нахождения нижней оценки для значений полинома от булевых переменных, обобщающий алгоритм, представленный в разделах 2.2 и 2.2.1. Алгоритм состоит в построении матрицы, аналогичной по свойствам тупиковой матрице в так называемой процедуре подъема [7], [10] и названной в силу этого также тупиковой. Предлагается, кроме того, алгоритм нахождения приближенного решения задачи, основанный на использовании свойств тупиковой матрицы.

В [20] и [10] приведено определение тупиковой матрицы и подробное описание алгоритма ее построения. Обобщенное определение тупиковой матрицы и описание общей схемы ее построения в случае задачи выбора множества строк даны в [7]. Работа [22] посвящена построению алгоритмов нахождения нижних оценок целевой функции задачи выбора комплектов оборудования. С помощью вычислительных экспериментов исследуется точность нижних оценок, получаемых при использовании различных правил построения тупиковой матрицы. Рассматриваемый в настоящей диссертации обобщенный алгоритм принципиально не отличается от алгоритмов из [7], [10], [20]. Тем не менее внесенные в нее изменения оказываются существенными для получаемой нижней оценки значений целевых функций рассматриваемых задач. Об этом свидетельствуют, в частности, приводимые в заключительной части работы результаты численных экспериментов. Из этих результатов видно, что значения нижних оценок превышают те значения, что приведены в [22] для аналогичных классов задач. Вместе с тем значения нижних оценок относительно оптимального решения двойственной задачи существенно выше и находятся в пределах 90-95% от него. Это означает, что получаемая с помощью обобщенной процедуры подъема тупиковая матрица близка к оптимальному решению двойственной задачи, а значительный разрыв между нижней оценкой и оптимальным значением целевой функции связан не с качеством получаемой тупиковой матрицы, а с соответствующим разрывом двойственности у задач рассматриваемого класса. Отмечается, что описанный алгоритм построения тупиковой матрицы является псевдополиномиальным, и его трудоемкость можно оценить сверху величиной 0( ILJ(L + logI)F), где F = Еге/ fi

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

В третьей главе для задачи выбора комплектов оборудования дано описание вероятностных жадных алгоритмов, основанных на идеях координатного спуска. В разделе 3.1 представлены новые вероятностные жадные алгоритмы "Лидер группы" и "Случайный аутсайдер", приведены их характеристики и указаны возможные пути модификации этих алгоритмов. Указываются варианты алгоритмов, которые обладают тем свойством, что вероятность нахождения точного решения стремится к 1 с ростом числа испытаний. В разделе 3.5 представлен гибридный алгоритм, построенный с привлечением вероятностного жадного алгоритма и ветвления, присущего методу ветвей и границ.

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

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

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

Рассмотрим задачу минимизации целевой функции F{x) на булевом кубе Вп\ min{F(x) | хеВп}.

Для нахождения глобального оптимума = F(xopt) будем применять вероятностный алгоритм поиска с запретами следующего вида. Обозначим через N(x) окрестность точки х и предположим, что она содержит все точки у £ Вп с расстоянием Хэмминга d(x,y) ^ 2. Вероятностная окрестность Np(x) с вероятностью р, 0 < р < 1, является подмножеством окрестности N(x). Каждая точка у 6 N(x) включается в Np(x) случайно с вероятностью р и независимо от других точек. Понятно, что мощность множества Np(x) для произвольного р Е (0,1) может варьироваться от пустого множества до множества, содержащего все точки N(x).

Рассмотрим конечную последовательность {ж^}, 1 ^ t ^ к со свойством xt+1 £ N(xt). Упорядоченное множество

Ч> = {(hJk), (ik-ujk-i), • • •, {ч-i+hЗк-Hi)}

12 называется списком запретов, если векторы xt и xt+i различаются только координатами (it,jt). Константа I называется длиной списка запретов. Заметим, что по определению ц и jt равны между собой, если векторы Xt и xt+i различаются ровно по одной координате. Положим ц — jt = О, если xt+i — Xt- Наконец, множество Np(xt, ф) определим как множество точек у G Np(xt), которые не запрещены списком запретов ср. Очевидно, Np(xt, может быть пустым для непустого множества Np(xt).

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

Вероятностный алгоритм поиска с запретами

1. Полагаем ж0 £ Вп, F* := F(x0), ^ := 0, t := 0.

2. Пока не выполнено условие останова, выполнять

2.1. Генерируем окрестность Np(xt,(p).

2.2. Если Np(xt,(f) = 0, то полагаем xt+i := Xt, иначе находим xt+i такой, что F(xt+i) =min{F(y), у е Np(xt,(p)}.

2.3. Если F(xt+1) < F*, то полагаем F* := F(xt+i).

2.4. Обновляем список запретов ip и счетчик t := t + 1.

Обозначим через Q множество всех пар (x,ip), где х G Вп, и ср является списком запретов. Для вероятностного алгоритма поиска с запретами доказывается следующая

Теорема. Для произвольных целых I ^ 0 и вещественных 0 < р < 1 вероятностный алгоритм поиска с запретами генерирует неразложимую марковскую цепь на Q.

Следствие. Для произвольной начальной точки хо G Вп имеем

1. limt—>оо Pr{minT<^ F(xT) = Fopt} = 1;

2. существуют константы 6>1и1>с>0 такие, что Pr{minT<^ F{xT) ф

Fopt] < be1;

3. Марковская цепь (xt,<Pt) имеет единственное стационарное распределение 7Г > 0.

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

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

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

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

• "Элегия-СО" (1983-85);

• "Жиро-СО" (1986-89),

• "Жетон-СО" (1991-92),

• "Экватор-АН" (1993-94),

• "Электролиния-СО" (1992-94),

• "Задача выбора оптимального типажа и состава перспективных средств автоматического управления тракторами", заказчик — Научно-производственное объединение по тракторостроению (НПО НАТИ), 1983, отзыв о внедрении см. в Приложение 2;

• "Исследование и разработка математических моделей, методов, инструментальных средств и новых информационных технологий обоснования сбалансированного развития системы вооружения Сухопутных войск" (1995),

• раздел "Математические модели решения задач альтернативного выбора комплекса экологических мероприятий, позволяющих получать необходимый экологический эффект при ограничениях на ресурсы" в рамках проекта "Разработка моделей и методов решения задач реализации экологической межрегиональной программы страны с учетом экологических ситуаций в регионах, производственных возможностей промышленности и ресурсных ограничений с целью максимизации суммарного экологического эффекта" (1993-95).

В приложении 1 приведены несколько содержательных постановок рассмотренных в НИР задач, а в приложении 2 — отзыв заказчика по одной их НИР.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Гончаров, Евгений Николаевич

Заключение

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Гончаров, Евгений Николаевич, 2001 год

1. Агеев А.А. О минимизации некоторых полиномов от булевых переменных. // Целочисленные экстремальные задачи- (Управляемые системы). Новосибирск, 1981. Вып. 21, 3-5.

2. А. А. Агеев, О сложности задач минимизации полиномов от булевых переменных, Управляемые системы 23 (1983), стр.3-11.

3. А. А. Агеев, Полиномиальный алгоритм решения задачи размещения на последовательно-параллельной сети, Управляемые системы, 30, 1990, с.3-16.

4. А. А. Агеев, В. Л. Береснев, Алгоритмы минимизации для некоторых классов полиномов от булевых переменных, Модели и методы оптимизации, Труды ИМ СО РАН, 10, 1988, с.5-17.

5. Александров Д. А. Алгоритм муравьиной колонии для задачи о минимальном покрытии // Методы оптимизации и их приложения. Труды 11-й Байкальской школы-семинара, 1998. Т. 3, с. 17-20.

6. Береснев В. J1. Алгоритм неявного перебора для задачи типа размещения и стандартизации Управляемые системы: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1974. Вып. 12. С. 2434.

7. Береснев В. JI. Алгоритмы минимизации полиномов от булевых переменных Проблемы кибернетики. М.: Наука, 1979. Вып. 36. С. 225246.

8. Береснев В. JI: Эффективный алгоритм для задачи размещения производства с вполне уравновешенной матрицей. Дискрет, анализ и ис-след. операций. Сер. 1. 1998. Т. 5, ДО 1. С. 20-31.

9. Береснев В. JI., Гончаров Е. Н. Приближенный алгоритм для задачи минимизации полиномов от булевых переменных // Дискрет, анализ и исслед. операций. Сер. 2. 1998. Т. 5, № 2. С. 3-19.

10. Береснев В. JL, Гимади Э. X., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978.

11. Боровков А.А. Теория вероятностей. М.: Наука, 1976.

12. Гимади Э.Х. Эффективный алгоритм решения задачи размещения с областями обслуживания, связными относительно ациклической сети. Управляемые системы, 1983, 23, с. 12—23.

13. Гимади Э.Х. Задача размещения на цепи с центрально-связными областями обслуживания. Управлямые системы, 1984, 25, с. 38-47.

14. Гимади Э.Х. Обоснование априорных оценок качества приближенного решения задачи стандартизации. Управляемые системы, 1987, 27, с. 3-11.

15. Гимади Э.Х. Задача стандартизации с данными произвольного знака и связными, квазивыпуклыми и почти квазивыпуклыми матрицами. Управляемые системы, 1990, 30, с. 12-23.

16. Гимади Э. X. Эффективные алгоритмы для решения многоэтапной задачи размещения на цепи // Дискрет, анализ и исслед. операций. 1995, т. 2, N 4, с. 13-31.

17. Гимади Э. X., Дементьев В. Т. О методах решения некоторых задач оптимизации параметрических рядов. Стандарты и качество, 1971, 12, с. 10-12.

18. Э. X. Гимади, Н. И. Глебов, В. А. Перепелица, Алгоритмы с оценками для задач дискретной оптимизации, Проблемы кибернетики 31, 1975, с.35-42.

19. Гимади Э. X., Дементьев В. Т. Некоторые задачи выбора оптимальных параметрических рядов и методы их решения (задачи стандартизации). Проблемы кибернетики, 1973, 27, с. 19-32.

20. Гончаров Е. Н. Математическая модель и метод решения двухуровневой задачи стандартизации. // Модели и методы оптимизации. Новосибирск: Ин-т математики СО РАН, 1994. С. 77-90. (Тр. РАН Сиб. отд-ние. Ин-т математики; Т. 28).

21. Гончаров Е. Н. Метод ветвей и границ для простейшей двухуровневой задачи размещения предприятий // Дискрет, анализ и исслед. операций. Сер. 2. 1998. Т. 5, № 1. С. 19-39.

22. Гончаров Е. Н., Кочетов Ю. А. Вероятностный жадный алгоритм с ветвлением для многостадийной задачи размещения // Методы оптимизации и их приложения. Труды 11-й Байкальской школы-семинара 1998. Т. 1. С. 121-124.

23. Гончаров Е. Н., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения // Дискрет, анализ и исслед. операций. Сер. 2. 1999. Т. 6, № 1. С. 12-32.

24. Гончаров Е. Н. О двухуровневой целочисленной задаче стандартизации. Проблемы теоретической кибернетики: Материалы XI Международной конференции, 10-14 июня 1996 г. М: Рос. гос. гуманит. ун-т. 1996. с.50-51.

25. Гончаров Е. Н. О двухуровневой целочисленной задаче стандартизации с учетом начальных затрат двух типов. Второй Сибирский Конгресс по Прикладной и Индустриальной Математике (ИНПРИМ -96), Новосибирск, 25-30 июня 1996 г., Тез. докл., с. 135.

26. Гончаров Е. Н. Об одной нижней оценке для двухуровневой задачи стандартизации. Тезисы межд.конф. Омск, 1997.

27. Гончаров Е. Н., Кочетов Ю. А. Алгоритм локального поиска с ветвлением для многостадийной задачи размещения. Международная Сибирская конф. по иссл. опер. Материалы конференции. Новосибирск: Изд-во Института математики СО РАН, 1998, с.99.

28. Гончаров Е. Н., Кочетов Ю. А. Поведение в среднем одного вероятностного жадного алгоритма. Тезисы докладов XII международной конференции "Проблемы теоретической кибернетики". Нижний Новгород, 1999. Том 2, с.54

29. Гончаров Е. Н., Кочетов Ю. А. Вероятностные жадные алгоритмы для многостадийной задачи размещения. Тезисы докладов XII конференции "Математическое программирование и приложения". Екатеринбург, 1999, с.78-79.

30. Гончаров Е. Н., Кочетов Ю. А. Вероятностный алгоритм поиска с запретами для многостадийной задачи размещения. Тезисы докладов Сибирской конференции по дискретному анализу и исследованию операций (DAOR'2000).

31. Горбачевская JI. Е. Алгоритмы и сложность решения двухуровневых задач стандартизации с коррекцией дохода // Дискрет, анализ и исслед. операций. Сер. 2. 1998. Т. 5, № 2. С. 20-33.

32. Горбачевская Jl. Е., Дементьев В.Т., Шамардин Ю.В. Двухуровневая задача стандартизации с условием единственности оптимального потребительского выбора // Дискрет, анализ и исслед. операций. Сер. 2. 1999. Т. 6, № 2. С. 3-11.

33. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М: Мир, 1982.

34. Еремеев А. В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации: дис. канд. физ.-мат. наук. Омск, 2000.

35. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журн. исслед. операций. Новосибирск. - 1994. - Т.1, № 2. - с. 18-39.

36. Кочетов Ю. А., Пащенко М. Г. Лагранжевы релаксации в задаче выбора оптимального состава системы технических средств. // Управляемые системы: Сб. научн. тр. Новосибирск: Ин-т математики СО РАН, 1993. Вып. 31: С. 48-58.

37. Кочетов Ю. А., Пащенко М. Г. Нижние границы в задаче выбора состава двухуровневой системы технических средств. // Дискрет, анализ и исслед. операций. 1995. Т. 2. N 4. С. 32-41.

38. Крамер Г. Математические методы статистики. М: Мир, 1975.

39. Михалевич В. С., Трубин В. А., Шор Н. 3. Оптимизационные задачи производственно-транспортного планирования. М.: Наука, 1986.

40. Пащенко М.Г. Нижние оценки для целевой функции в динамической задаче выбора оптимального состава двухуровневой систем технических средств. //Дискретный анализ и исследование операций. Серия 2. Новосибирск, 1997. Т. 4, N 1, 40-53.

41. Свириденко М. И. О точности решений жадными алгоритмами задач размещения на максимум. Дискретный анализ и Исследование операций, 1997, 4(3), серия 1, с. 35-48.

42. Свириденко М. И. Алгоритмы с оценками для дискретных задач размещения: дис. канд. физ.-мат. наук. Новосибирск, 1998.

43. Трубин В.А. Эффективный алгоритм решения задачи размещения на сети в форме дерева. Доклады Академии наук СССР, 1976, 231, N3, с. 547-550.

44. Трубин В. А. Два класса задач размещения на древовидных сетях. Кибернетика, 1983, 4, с. 84-87.

45. Трубин В.А., Шарифов Ф.А. Простейшая многоэтапная задача размещения на древовидной сети. // Кибернетика и системный анализ. 1992. N. 6. С. 128-135.

46. Черенин В. П., Хачатуров В. Р. Решение методом последовательных расчетов одного класса задач о размещении производства. Экономика и математические методы, 1965, 2, с. 279-290.

47. Aarts Е. Н. L., Lenstra J. К. (Eds.) Local Search in Combinatorial Optimization. Chichester: John Wiley & Sons, 1997.

48. Aart, E. H. L., Korst, J .H. M., and Laarhoven, P. J. M. Simulated Annealing, in:.Aart, E. H. L. and Lenstra, J. K., eds., Local Search in Combinatorial Optimization, Wiley, Chichester, 1997, 91-120

49. Ageev A. A. A Criterion of Polynomial-Time Solvability for the Network Location Problem. Integer Programming and Combinatorial Optimization, Carnegie-Mellon University, 1992, p. 237-245.

50. Ageev A. A. Complexity of the Network Median Problem on Planar Grids. Siberian Advances in Mathematics, 1995, 5, p. 1-9.

51. Ageev A. A., Sviridenko M. I. An 0.828-approximation algorithm for the uncapacitated facility location problem. Discrete Applied Mathematics, 1999, 93, p. 149-156.

52. Barros A. I., Labbe M. A general model for the uncapacitated facility and depot location problem// Location Science. 1994. V. 2, N 3, P. 173191.

53. Bilde 0, Krarup J. Sharp lower bounds and efficient algorithms for the simple plant location problem // Ann. Discrete Math. 1977. V. 1. P. 7997.

54. Billionet A., Costa M.-C. Solving the uncapacitated plant location problem on trees. Discrete Applied Mathematics, 1994, 49, N 1-3, 51-59.

55. Chvatal V. A greedy heuristic for the set-covering problem. -Mathematics of Operations Reseach, 1979, 4, p. 233-235.

56. Chudak F. Improved approximation algorithms for uncapacitated facility location. In Proceedings of the 6th IPCO Conference, 1998, p. 180-194.

57. Cornuejols G., Fisher M. L. and Nemhauser G. L., Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms, Management Science 22 (1977), pp.789-810.

58. Cornuejols G., Nemhauser G. L. and Wolsey L. A. Worst Case and Probalistic Analysis of Algorithms for Location Problems, Operation Research 28 (1980), pp.847-858.

59. Cornuejols G., Nemhauser G. L. and Wolsey L. A. The Uncapacitated Facility Location Problem, In book edited by P. B. Mirchandani and R. L. Francis, Wiley&Sons, 1990.

60. Erlenkotter D. A dual-based procedure for uncapacitated facility location // Oper. Res. 1978. V. 26, N 6. P. 992-1009.

61. Feige U. A threshold of Inn for approximating set cover // Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing. New York: ACM Press, 1996. P. 314-318.

62. Faigle, U. and Kern, W. Some convergence results for probabilistic tabu search. ORSA Journal on Computing, 1992, 4, 32-37

63. Feo Т. A. Greedy randomized adaptive search procedures, J. Global Optim. 1995. V.6. P. 109-133.

64. Gao L., Robinson E. P. Jr."A Dual-Based Optimization Procedure for the Two-Echelon Uncapacitated Facility Location Problem. // Naval Res. Logistics. 1992. V. 39, P. 191-212.

65. Glover F. Tabu Search. Part I. ORSA Journal on Computing, 1989, 1, 190-209.

66. Glover F., Laguna M. Tabu Search. Dordrecht: Kluwer Academic Publishers, 1997.

67. Goncharov E. N., Kochetov Yu. A. Behavior of a Probabilistic Tabu Search Algorithm for the Multi-Stage Uncapacitated Facility Location Problem. Proceedings of INFORMS-KORMS, Seoul, 2000.

68. Goncharov E. N., Kochetov Yu. A. Probabilistic Tabu Search Algorithm for the Multi-Stage'Uncapacitated Facility Location Problem. Operations Research Proceedings 2000, Springer-Verlag, 2001, pp.65-70.

69. Helsgaun K. An effectiv implementation of the Lin-Kernighan traveling salesman heuristics. // European J. Oper. Res. 2000. V. 126, P. 106-130.

70. Hinojosa Y., Puerto J., Fernandez F.R. A multiperiod two-echelon multicommodity capacitated plant location problem. // European J. Oper. Res. 2000. V. 123, P. 271-291.

71. Klose A. A Lagrangean relax-and-cut approach for the two-stage capacitated facility location problem. // European J. Oper. Res. 2000. V. 126, P. 408-421.

72. Kolen A. Solving covering problems and the uncapacitated plant location on the trees. Eur. J. Oper. Res., 1983, 12, N 3, 266-278.

73. Kolokolov A. A., Eremeev A. V\, Zaozerskaya L. A. On hybrid L-class enumeration and genetic algorithm for set covering problem / / 15-th Conference of international federation of operational societies (IFORS'99): Abstr. Pekin, 1999. - p.117.

74. Ro H. В., Tcha D. W. A branch and bound algorithm for the two-level uncapacitated facility location problem with some side constraints. // European J. Oper. Res. 1984, V. 18, N 3, P. 343-358.

75. Tcha D. W., Lee B.-Y. A branch-and-bound algorithm for the multilevel uncapacitated facility location problem. // European J. Oper. Res. 1984. V. 18, N 1, P. 35-43.

76. Tragantalerngsak S., Holt J., Ronnqvist M. An exact method for the two-echelon, single-source, .capacitated facility location problem. // European J. Oper. Res. 2000. V. 123, P. 473-489.1. Отчеты по НИР

77. Гимади Э.Х., Гончаров E. H. и др. Отчет ИМ СО АН СССР, инв. 1495, 1983.

78. Гимади Э.Х., Гончаров Е. Н. Задача выбора оптимального типажа и состава перспективных средств автоматического управления тракторами. Отчет ИМ СО АН СССР, 1983.

79. Гимади Э.Х., Гончаров Е. Н. и др. Отчет ИМ СО АН СССР, инв. 1618, 1984.

80. Гимади Э.Х., Гончаров Е. Н. и др. Отчет ИМ СО АН СССР, инв. 1732, 1986.

81. Гимади Э.Х., Гончаров Е. Н. и др. Отчет ИМ СО АН СССР, инв. 2048, 1991.

82. Гимади Э.Х., Гончаров Е. Н., Сычев А. Н. Математические модели выбора рационального состава системы. //Исследование операций, ИМ СО АН СССР, 1990, инв.-2047.

83. Гимади Э.Х., Гончаров Е. Н. и др. Отчет ИМ СО АН СССР, инв. 2048, 1991.

84. Гимади Э.Х., Гончаров Е. Н. и др. Отчет ИМ СО РАН, инв. 2061, 1992.

85. Гимади Э.Х., Гончаров Е. Н. и др. Отчет ИМ СО РАН, инв. 2063, 1992.

86. Гончаров Е. Н., Ерзин А.И., Лавлинский С.М. Экспертная система прогнозирования экологических последствий реализации региональных планов и программ. Отчет ИМ СО РАН, Новосибирск, 1993

87. Гимади Э.Х., Гончаров Е. Н. и др. Отчет ИМ СО РАН, инв. 2090, 1994.

88. Гимади Э.Х., Гончаров Е. Н. и др. Отчет ИМ СО РАН, инв. 2093, 1994.