Головная страницa    Редколлегия    Подписка   Для авторов   Содержание 

Дискретный анализ и исследование операций
Серия 2, 2000,  том 7,  № 2

Специальный выпуск DAOR'2000

Содержание:

МЕЖДУНАРОДНАЯ КОНФЕРЕНЦИЯ DAOR'2000
стр. 3–4

 

Л. Е. Горбачевская
Двухуровневая задача выбора изделий многоразового использования с условием однозначности выбора потребителя
стр. 5–11

Исследуется задача булевого двухуровневого программирования, моделирующая выбор изделий многоразового использования. Показано, что задача является NP-трудной. Рассмотрен случай, когда она решается эффективно.
Библиогр. 7.
Адрес автора: Институт математики им. С. Л. Соболева СО РАН,
пр. Академика Коптюга, 4, 630090 Новосибирск, Россия.
E-mail: orlab@math.nsc.ru

 

В. А. Емеличев, А. В. Пашкевич
О линейной свертке критериев в векторной дискретной оптимизации
стр. 12–21

Исследуется тот аспект проблематики многокритериальной дискретной оптимизации, который связан с агрегированием частных критериев и последующим сведением исходной задачи поиска множества Парето к однокритериальной (скалярной) параметрической задаче.
Библиогр. 27.
Адрес авторов: Белорусский государственный университет,
пр. Ф. Скорины, 4, 220050 Минск, Беларусь.
E-mail: eva@mmf.bsu.unibell.by

 

А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов
Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования
стр. 22–46

Задача о покрытии множества широко известна в дискретной оптимизации и имеет многочисленные приложения. В настоящей статье содержится обзор результатов, связанных со структурой и сложностью этой задачи, алгоритмами ее решения и результатами вычислительных экспериментов. Особое внимание уделяется последним достижениям.
Библиогр. 99.
Адрес авторов: Омский филиал Института математики
им. С. Л. Соболева СО РАН, ул. Певцова, 13, 644099 Омск, Россия.

 

А. А. Колоколов, М. В. Девятерикова
Анализ устойчивости L-разбиения множеств в конечномерном пространстве
стр. 47–53

Исследуется вопрос об изменении лексикографической структуры (L-разбиения) множеств в конечномерном пространстве при их расширениях. Найдены верхние оценки мощности L- интервалов компактного множества при малых расширениях. Рассмотрены приложения полученных результатов в целочисленном программировании.
Библиогр. 8.
Адрес авторов: Омский филиал Института математики
им. С. Л. Соболева СО РАН, ул. Певцова, 13, 644099 Омск, Россия.
E-mail: kolo@iitam.omsk.net.ru

 

Р. М. Ларин, А. В. Пяткин
Двухуровневая биматричная игра с регулировкой выигрыша
стр. 54–59

Рассматривается двухуровневая биматричная игра, в котоpой игpок верхнего уровня не только выбирает смешанную стратегию, но и имеет возможность изменять элементы матриц выигрышей. Игpок нижнего уровня стpоит свою оптимальную стратегию с учетом выбора стратегии на верхнем уровне и изменения матрицы выигрышей. Показано, что в кооперативном случае, когда интересы нижнего уровня не противоречат интересам верхнего уровня, pешение игpы сводится к сеpии задач линейного программирования. В антикооперативном случае доказано существование e -оптимальных решений.
Библиогр. 5.
Адрес авторов: Институт математики им. С. Л. Соболева СО РАН,
пр. Академика Коптюга, 4, 630090 Новосибирск, Россия.
E-mail: orlab@math.nsc.ru

 

Л. С. Мельников, А. А. Добрынин
Построение трехсвязных графов с совпадающими цепными матрицами слоев
стр. 60–73

Цепная матрица слоев (цепная степенная последовательность) t(G) содержит количественную информацию о цепях, начинающихся в вершинах обыкновенного связного неориентированного графа G. Под длиной цепи графа понимается число ее ребер. Элемент t_ij матрицы равен количеству всех простых цепей длины j, начинающихся в вершине v_i. Предлагается метод для построения пар неизоморфных графов без точек сочленения с совпадающими цепными матрицами слоев. Построены бесконечные семейства таких графов, в том числе наименьшие известные графы, обладающие различными свойствами. Показано, что для любого p18 существуют как планарные, так и непланарные двусвязные и трехсвязные p-вершинные графы с совпадающими цепными матрицами слоев. Сформулированы аналогичные утверждения для r-регулярных графов. Например, для любого pЦепная матрица слоев (цепная степенная последовательность) t(G) содержит количественную информацию о цепях, начинающихся в вершинах обыкновенного связного неориентированного графа G. Под длиной цепи графа понимается число ее ребер. Элемент t_ij матрицы равен количеству всех простых цепей длины j, начинающихся в вершине v_i. Предлагается метод для построения пар неизоморфных графов без точек сочленения с совпадающими цепными матрицами слоев. Построены бесконечные семейства таких графов, в том числе наименьшие известные графы, обладающие различными свойствами. Показано, что для любого p26 \ (p30) существуют неизоморфные трехсвязные непланарные (планарные) p-вершинные кубические графы с совпадающими цепными матрицами слоев. Приводится несколько открытых вопросов.
Ил. 6, библиогр. 20.
Адрес авторов: Институт математики им. С. Л. Соболева СО РАН,
пр. Академика Коптюга, 4, 630090 Новосибирск, Россия.
E-mail: omeln@math.nsc.ru ; dobr@math.nsc.ru

 

М. С. Нечаева, О. В. Хамисов
Метод ветвей и границ для задачи минимизации невыпуклой квадратичной функции при выпуклых квадратичных ограничениях
стр. 74–88

Рассматривается задача поиска минимума квадратичной функции на выпуклом ограниченном множестве, заданном квадратичными и линейными неравенствами. Для ее решения предлагается вариант метода ветвей и границ, на каждом шаге которого множество, образованное пересечением конечного числа эллипсоидов, аппроксимируется внешним и внутренним эллипсоидами. Оценки оптимального значения целевой функции находятся в результате решения задачи минимизации квадратичной функции на шаре. Доказывается сходимость метода и приводится оценка скорости сходимости.
Библиогр. 16.
Адрес автора: Институт систем энергетики им. Л. А. Мелентьева СО РАН,
ул. Лермонтова, 130,664033 Иркутск, Россия.
E-mail: nechaeva@isem.sei.irk.ru ; khamisov@isem.sei.irk.ru 

 

А. В. Плясунов
Полиномиально разрешимый класс задач двухуровневого нелинейного программирования
стр. 89–113

Рассматривается задача двухуровневого программирования, ограничения которой содержат нелинейные слагаемые специального вида. Показано, что исходная задача сводится к серии задач линейного программирования и, следовательно, решается с полиномиальной сложностью.
Ил. 5, библиогр. 6.
Адрес автора: Институт математики им. С. Л. Соболева СО РАН,
пр. Академика Коптюга, 4, 630090 Новосибирск, Россия.
E-mail: apljas@math.nsc.ru

 

Ю. В. Шамардин
О двухуровневой задаче размещения при ограничениях на объем производства
стр. 114–118

Рассмотрена задача о наилучшем выборе пунктов производства некоторого продукта. Объемы производства, которые предполагаются ограниченными, выбирает “производитель”, но перевозку продукта в пункты спроса осуществляет “потребитель”, минимизируя транспортные расходы. Требуется найти минимум производственных затрат с учетом реакции потребительской стороны. Показано, что если матрица транспортных затрат потребителя обладает свойством “сильной связности”, то исходная двухуровневая задача сводится к задаче о “ближайшем соседе” и решается методом динамического программирования.
Библиогр. 5.
Адрес автора: Институт математики им. С. Л. Соболева СО РАН,
пр. Академика Коптюга, 4, 630090 Новосибирск, Россия.
E-mail: orlab@math.nsc.ru

 

  Головная страницa    Редколлегия    Подписка   Для авторов   Содержание