Разработка и анализ алгоритмов решения дискретных задач оптимального размещения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

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

ЛЕВАНОВА Татьяна Валентиновна

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

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Иркутск - '2000

Работа выполнена в Омском филиале Института математики имени С.Л.Соболева СО РАН.

Научный руководитель: доктор физико-математических

наук, профессор Колоколов A.A.

Официальные оппоненты: доктор физико-математических

наук, профессор Булатов В.П., кандидат физико-математических наук Хамисов О.В.

Ведущая организация: Институт математики и механики УрО РА!

Защита состоится " & * 2000 г. в Й часов на за се.

нин диссертационного совета Д 063.32.04 в Иркутском государств ном университете по адресу: 664000, Иркутск, бульвар Гагарина. 1-й корпус ИГУ.

С диссертацией можно ознакомиться в библиотеке Иркутского сударственного университета (бул. Гагарина, 24).

Автореферат разослан иол 2000 г.

ченып секретарь диссертационного совета к.ф.-м.н., доцент

Bif^ .9 ,Ъ иск ^е.тно&"оз

Н.Б.Бельтю!

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

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

В настоящее время область дискретной оптимизации. связанная с задачами размещения, активно развивается. Ведутся исследования структуры и вычислительной сложности задач, выделяются полиномиально разрешимые случаи, развиваются точные и приближенные методы ах решения [1-4, 7-11,13-17,19-36]. В последние годы интенсивно разрабатываются подходы, основанные на аналогиях с природой (генетические алгоритмы, алгоритмы муравьиной колонии, имитации отжига и др.) [5,12] и методы локальной оптимизации [14,18].

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

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

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

Научная новизна. В диссертации подучили дальнейшее разви-

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

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

1. Разработаны точные алгоритмы решения задачи размещения с ограничениями на объемы производства, простейшей задачи размещения и задачи о р-медиане, основанные на декомпозиции Бендерса и лексикографическом переборе элементов //-разбиения. Разработана комбинация этих алгоритмов с различными эвристиками.

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

3. Построены приближенные алгоритмы решения задачи размещения с ограничениями на объемы производства, простейшей задачи размещения и задачи о р-медиане. Для задачи о р-медиане предложены варианты рандомизации одного из алгоритмов.

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

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

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

Апробация работы. Результаты диссертации докладывались на Школе "Декомпозиция и координация в задачах проектирования и управления" (Миасс, 1988), Всесоюзной конференции "Дискретная оптимизация и исследование операций" (Новосибирск, 1992), "Расширенных заседаниях одесской школы-семинара по дискретной математике и приложениям" (Одесса, 1993, 1994, 1997), Всесоюзной конференции "Математическое программирование и приложения" (Екатеринбург, 1993. 1995), 10 и 11 Байкальской школе-семинаре "Методы оптимизации п их приложения" (Иркутск, 1995, 1998), "Втором Сибирском конгрессе по прикладной и индустриальной математике" (Новосибирск, 1996), Международной конференции "Проблемы оптимизации и экономические приложения" (Омск, 1997), International Conference on Operations Research (Цюрих, Швейцария, 1998), "Международной сибирской конференции по исследованию операций" (Новосибирск, 1998), Symposium on Operations Research SOR'99 (Магдебург, Германия, 1999), Международной конференции "Распределенные системы: оптимизация к приложения р экономике и науках об окружающей среде" (Екатеринбург. 2000), Международной конференции "Дискретный анализ и исследование операций" (Новосибирск, 2000), на научных семинарах в ИИТПМ СО РАН (Омск), Омском филиале

Института математики СО РАН, Институте динамики систем и теории управления СО РАН (Иркутск).

Публикации. Основные результаты диссертации опубликованы в 17 работах. Их список приведен в конце автореферата.

Структура и объем работы. Диссертация изложена на 130 страницах и состоит из введения, четырех глав, заключения, списка литературы (130 наименований) и приложения.

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

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

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

В п.1.1 содержатся целочисленные и комбинаторные постановки ряда задач размещения производства. Особое внимание уделяется задаче размещения с ограничениями на объемы производства, простейшей задаче размещения (ПЗР) и задаче о р-медиане.

Рассматривается следующая постановка ПЗР. Дано конечное множество I = {1, ...,т} пунктов возможного размещения предприятий, производящих однородный продукт в неограниченном количестве, и список клиентов ] € 3 — {1,...,«}. Известны стоимости размещения предприятий С{ в указанных пунктах г € / и затраты на удовлетворение спроса каждого клиента _/ € ■/• Требуется разместить предприятия и прикрепить к ним клиентов та^, чтобы суммарные затраты на размещение предприятий н обслуживание клиентов были минимальны. Целочисленная модель ПЗР имеет вид:

Дс, я) = Е + Е Е ';Я:<7 га1п «е^ ¡61 №

Zij = 1, 'i > Zij, г G I,j G J,

iel

Zj G {0,1}, > 0, г e /. j G •/,

где Xij - доля спроса клиента j. которую обеспечивает предприятие i:

= 1, если предприятие г открыто п 0 - в противном случае.

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

В задаче размещения с ограничениями на объемы производства известны объемы производства а,-, г G /. и потребления bj,j G J■ Ее модель целочисленного линейного программирования (ЦЛП) пмеет вид:

F{z,x) = Y, ci~> + E E tijXij min «e i ieijeJ

E ^у = bj,j £ ^ E < ««*>> i e i,

Ш jeJ

®fj>0, zi G {0,1}, i 6 I.j € J.

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

В п. 1.4 рассматриваются задачи размещения взаимосвязанных объектов, дается краткий обзор работ по этим задачам, указывается, в каких областях они возникают, их возможные постановки и методы решения. Описывается целочисленная модель задач размещения габаритных объектов на линии с минимально допустимыми расстояниями на взаимное расположение. Пусть'дано множество N = {1....,п} номеров размещаемых взаимосвязанных объектов. Структура связей задана графом G = (N, Е), где Е С N'y N. Ребро (i.j) G Е, если существует связь между объектами i и j. Симметричные (пх п)- матрицы

С = (dj),R = (Tij) задают удельные стоимости связей и минимально допустимые расстояния, соответственно. Необходимо разместить множество габаритных объектов вдоль линии так, чтобы суммарная стоимость связей была наименьшей и выполнялись ограничения на минимально допустимые расстояния.

В работе рассматривается модель ЦЛП этой задачи [9]. Приводятся некоторые свойства модели, предлагаются приближенные алгоритмы получения размещения. Описываются алгоритмы проверки размещения объектов на плоскости на оптимальность и его коррекции. Основные результаты этой главы опубликованы в [20,21,27,29].

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

В п.2.1 содержатся краткие сведения об известных алгоритмах с оценками погрешности получаемых решений, дается обобщение задачи о р-медиаве, вводится понятие крутизны целевой функции, отмечаются установленные автором свойства супермодулярных функций. В п.2.2 в терминах крутизны выводится оценка погрешности дискретного варианта градиентного алгоритма #ля задачи минимизации супермодулярной функции. В п.2.3 предлагается способ построения задач с заданной крутизной.

Рассматривается обобщение задачи о ;)-меднане

mm{/iX) = £ min Cij : |Х| = р} (2,1)

XCl -£J 1СЛ

на случай, когда /(А').- невозрастающая супермодулгркая функция.

В качестве приближенного метода решения используется дискретный аналог градиентного алгоритма спуска. Пусть Opt - оптимальное решение задачи, а Gr - решение, построенное указанным алгоритмом.

ЛпяХ с I пх £Х обозначим йх(Х) = /(X \ {а:}) - /(Х)> 0. Крутизной целевой функции будем называть величину

Ъ{{х})-<1У(1)

5 = шах - , /-.

•«.»б- 1 -Г г)

Легко видеть, что .5 € [0,1].

Нами получена следующая оценка погрешности данного алгоритма з терминах крутизны я целевой функции [30].

Теорема 2.1. Для любой невозрастающей супермодулярнои целевой функции задачи (2.1) крутизны з 6 (0,1) имеет место оценка

КОг± < 1 _

('г)'-1

(2.2)

ДОрЦ где д = т -р, t =

Как следствие теоремы 2.1 получена оценка погрешности алгоритма в терминах только целевой функции.

Следствие. Для любой невозрастающей супермодулярной целевой функции задачи (2.1) крутизны £ € (0,+ео) имеет место

ПСг) е'-1 !{Ор1) ~ г '

где е - основание натурального логарифма.

Доказана также следующая Теорема 2.2. Для любой невозрастающей супермодулярной целевой функции / задачи (2.1) крутизна 5 = 0 тогда и только тогда, когда !(Х) = /(0) - ДХ) - аддитивна и /({*}) = /({»}) V*, у е I.

Оценка 2.2 достижима для любого ^ > 0. Отсюда следует, что алгоритм, хорошо зарекомендовавший себя в эксперименте, теоретически может давать сколь угодно плохое решение. Проведено сравнение с понятием хсрутизны, введенным в [10].

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

Результаты этой главы опубликованы в [21,24,25,30,32,33].

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

В п. 3.1 дается краткий обзор метбдов решения рассматриваемых задач. В п. 3.2 вводятся регулярные разбиения пространства Я", в том числе Z-разбиенне, предложенное A.A. Колоколовым. Пусть >-,>:-символы лексикографического порядка. Точки х,у £ Rn(x У у) принадлежат одному классу ¿-разбиения, если не существует такого целочисленного вектора г, что х У z У у. Каждая точка г 6 Z" представляет собой отдельный класс разбиения, остальные классы содержат лишь нецелочисленные точки. Для Q С R" элементы фактор-множества Q/Z. задаваемого ¿-разбиением, называются ¿-классами. В п. 3.2 приводится ряд важных свойств ¿/-разбиения. В, п.3.3 описывается ¿-структура задач размещения и ее свойства, которые используются при построении и анализе алгоритмов.

В п. 3.4 излагаются'алгоритмы перебора ¿-классов и декомпозиции Бендерса для задачи целочисленного программирования на минимум, а также разработанные автором декомпозиционные алгоритмы для решения задачи размещения с ограничениями на объемы производства, простейшей задачи размещения и задачи о р-медиане.

Алгоритм перебора L - классов основан на идее последовательного просмотра элементов ¿ - разбиения релаксационного множества задачи в лексикографическом порядке. Суть декомпозиционного подхода заключается в разбиении исходной задачи на производственную и транспортную подзадачи и их последовательном решении. К ограничениям текущей производственной задачи добавляются отсечения Бендерса, которые строятся на основе соотношений двойственности [2,6] и служат для исключения "неперспективных" производственных планов. Решение производственных подзадач осуществляется с помощью алго-

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

Опишем основные шаги декомпозиционного алгоритма на примере задачи с ограничениями на объемы производства.

Введем обозначения: Р^ - производственная задача на к-й итерации, - ее решение; Т(г^) - соответствующая транспортная задача, х(к) — ее оптимальное решение: задача, двойственная к Т(г^),

и^ - оптимальное решение этой задачи; Р<0> - начальное значение рекорда целевой функции, - его значение на к-й итерации.

На предварительном шаге алгоритма формулируется исходная производственная задача РО; найти лексикографически минимальное решение системы, состоящей из ограничений а,-г* > Л ¡р.; bj (условие баланса), < %о> 5 = 1. (отсечения Бендерса и другие нера-

венства, полученные с помощью эвристик), г,- € {0,1}, г € I.

Итерация к, к > 1.

Шаг 1. Решаем задачу Р'^ с помощью алгоритма перебора Ь - классов. Если она неразрешима, то производственно-транспортный план, на котором достигается рекорд Г1'-1', является оптимальным решением исходной задачи. Процесс решения завершается. Иначе идем на шаг 2.

Шаг 2. Формулируем и решаем задачи Т{:[к>) и Вычисляем

Г« = тпгп{р(^,р(г^,х^)}. Если Р« < то Р^"1' заменяем

на Р^ в системе ограничений задачи

Шаг 3. Строим линейное неравенство (отсечение Бендерса):

(ал)

Шаг 4■ Формулируем задачу Р^41': найти который является лексикографически минимальным целочисленным решением системы ограничений задачи Р^ ж (3.1). Переходим к следующей итерашш.

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

Основные результаты главы приводятся в работах [26-29.-31.34-36] В четвертой главе излагаются результаты экспериментальных ис следований разработанных алгоритмов.

. В п.4.1 проводится экспериментальное сравнение приближенны: алгоритмов решения задач размещения предприятий со случайным! данными. Здесь же содержатся сведения об экспериментальном иссле довании влияния крутизны функции на точность детерминированногс приближенного алгоритма и его рандомизированных схем на задача? размерности т — 100, п — 100.

В п.4.2 излагаются результаты экспериментального сравнения различных схем декомпозиционных алгоритмов на задачах со случайным! данными размерности т < 100. п < 100, примерах из ОЙ-1лЬгагу [15] и задачах, составленных по правилам, описанным Ю. А .К очетовыь: (тп = 50, п = 50). Алгоритмы оказались эффективными при решении задач со случайными данными. Для примеров, полученных на основе указанных правил, время решения мало зависело от структуры матрицы транспортных затрат. Сравнение с алгоритмом СРЬЕХ подтвердило перспективность разработки гибридных схем алгоритмов.

П.4.3 содержит результаты экспертизы секции 500 Павлодарского нефтеперерабатывающего завода, проведенной с использованием предложенных алгоритмов. Экспертиза показала возможность улучшения компоновки нефтехимических аппаратов. Результаты этой главы опубликованы в работах [20,22,23].

Список использованной литературы

[1] Агеев A.A. Точные и приближенные алгоритмы для задач размещения: обзор последних достижений// Материалы конференции-Новосибирск: Изд-во ИМ СО РАН, 1998 - С.4-10.

[2] Бахтин А.Е., Колоколов A.A., Коробкова З.В. Дискретные задачи производственно-транспортного типа. Новосибирск: Наука, 1978 - 160с.

[3] Береснев B.JL, Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации Новосибирск, 1978.- 333с.

[4] Булатов В.П. Методы погружения е задачах оптимизации Новосибирск: Наука, 1977.- 161с.

[5] Еремеев A.B. Генетический алгоритм для задачи о покрытии// Дискр. анализ и исслед. операций. Сер. 2. -2000. -Т.7, N1. -С.47-60.

[6] Еремин И.И., Мазуров В.Д., Астафьев H.H. Несобственные задачи линейного выпуклого программир-я- М.: Наука, 1983.- 336с.

[7] Жак С.В., Зннченко А.Б. Комбинаторные методы решения задачи размещения помещений в производственном здании// Автоматизация архитектурно-строительного проектирования,-Ростов-на-Дону - 1979 - C.S7-92.

[8] Заблоцкая O.A. L-разбиение многогранника стандартизации// Моделирование и оптимизация систем сложной структуры: Меж-вуз. сб. научн. труд. Омск: ОмГУ, 1987.- С.151-154.

[9] Забудский Г.Г.О целочисленной постановке одной задачи размещения объектов на линии// Управляемые системы.- Новосибирск, 1990.- Выл.ЗО - С. 35-45.

[10] Ильев В.П. Оценка, точности алгоритма жадного спуска для задачи минимизации суперм.одулярной функции//Лжкретяып анализ и исследование операции - Се'рня!.- 1998 - Т.5. N4.- С.45-60.

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

[12] Кочетов Ю.А. Вероятностные алгоритмы локального поиска для задач дискретной оптимизации// Материалы конф,- Новосибирск: Изд-во ИМ СО РАН, 1998.- С.21-24.

[13] Панюков А.В. Алгоритмы локальной оптимизации для задачи размещения прямоугольных объектов с минимальной длиной связывающей их сети// Изв. АН СССР, Техн. киб-ка.- 1981. N6.-С.180-184.

[14] Стоян Ю.Г., Яковлев С.В. Матбматические модели и оптимизационные методы геометрического проектирования. Киев: На-укова думка.- 1986.- 268с.

[15] Beasley J.E. Art algorithm for solving large capacitated warehouse location problems// Europ. J. of Oper. Res. - 1988 - 33 - P.314-325.

[16] Discrete Location Theory/ Ed. by Pitu B.Mirchamdani and Richard L.Franscis, John Wiley k Sons, Inc, 1990.

[17] Kolokolov A.A. Decomposition algorithms for solving of some production-transportation problems//Triennal Symp. on Transport. Analysis II. Prepr. Vol.1- Capri, Itjaly, 1994 - P.179-183.

[18] Local search in Combinatorial optimization/ Edited by E.Aarts and J.K.Lenstra, John Wiley and Sons Ltd, 1997.

[19] R. Shridharan Invited Review. The capacitated plant location problem}/ Europ. J. of Operational Research 87.- 1995 - P.203-213.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[20] Дордина Т.Л., Леванова Т.В. К задаче оптимального размещения взаимосвязанных объектов// Вестник Омского ун-та.-Омск: ОмГУ, 2000. - N 2. - С.15-17.

[21] Живетьева И.А., Леванова T.B. Анализ градиентных алгоритмов решения задачи о р-медиане на основе крутизны целевой функцииjI Матер, междунар. конф. "Дискретный анализ и исследование операций". Новосибирск, 2000.- С.167.

[22] Забудский Г.Г., Колмычевская Н.В., Леванова Т.В. Оптимизация размещения технологическдго оборудования на генплане// Тез. симп. "Системы программного обеспечения решения задач оптимального планирования". М., 1988.- C.14S.

[23] Забудский Г.Г., Леванова Т.В. Разработка алгоритмического и программного обеспечения для решения задач оптимальной компоновки/ / Тез. конф. "Проблемы повышения эффективности создаваемых и внедряемых АСУ". Омск, 1988.- С.26.

[24] Ильев В.П., Леванова Т.В. Оценки погрешности жадного алгоритма для задачи минимизации супер модулярной функции/ / Тез. докл. междунар. конф. "Проблемы оптимизации и экономические приложения", Омск, 1997 - С.80-82.

[25] Ильев В.П., Левалова Т.В. Анализ градиентного алгоритма минимизации супермодулярной функции на матроиде// Тр. XI междунар. Байкальской шк.-сем., Иркутск. -1998, Том1.- С.143-146.

[26] Колоколов A.A., Левалова Т.В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения // Вестник Омского ун-та - Омск: ОмГУ, 1996. - N 1. - С.21-23.

[27] Леванова Т.В. Решение некоторых задач размещения на информационно-вычислительной. сети// Информ. технологии и радиосети (ИНФОРАДИО'96): Междунар. науч.-практ. конф.-Новосибирск: Изд-во ИМ СО РАН, 1998 - С.44-47.

[28] Леванова Т.В. Исследование декомпозиционных алгоритмов для решения некоторых задач размещения// Тез. докл. конф. "Математическое программирование и приложения". Екатеринбург. 1997 - С.144-145.

[29] Леванова Т.В. Некоторые алгоритмы решения задачи размеще ния с ограничениями на объемы производства// Матер. Между-нар. Сиб. конф. по исслед. операций, Новосибирск, 1998.- С.103.

[30] Леванова Т.В. Двойственный жадный алгоритм для задачи с р-медиане и ее обобщений// Препринт 98-4. Омск: Омский госуниверситет, 1998.- 13с.

[31] Леванова Т.В. Алгоритмы решенья одной задачи размещения ни основе декомпозиции и перебора L-классов// В сб. докл. Меж-дунар. конф. "Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде", Екатеринбург. 2000 - С. 146-149.

[32] Il'ev V.P., Levanova T.V. On the minimization supermodular set function problem// Abstr. of Int. Couf. "Optimal Discrete Structures and Algirithms", Rostock, Germany, 1997. - P.44.

[33] fl'ev V.P., Levanova T.V. On the minimization supermodular set function over matroids// Abstr. of International Conference on Operations Research, Zurich, 1998 - P.53.

[34] Kolokolov A.A., Levanova T.V. Some L-class enumeration algorithm for simple plant location problem// Abstr. of Int. Conf. on Operations Research, Berlin, 1994 - P.75. 1

[35] Kolokolov A.A., Levanova T.V. Some Hybrid Algorithms for the Production-Transportation Problem // Preprints of 8th IFAC Symposium, Greece, 1997 - P. 896.

[36] Levanova T.V. Some decomposition algorithms for plant location problem// Book of Abstr. Symposium on Operations Research, Germany, Magdeburg, 1999.- P.76. Jj!a