Низкая цена
Всего 249a за скачивание одной диссертации
Скидки
75 диссертаций за 4900a по акции. Подробнее
О проекте

Электронная библиотека диссертаций — нашли диссертацию, посмотрели оглавление или любые страницы за 3 рубля за страницу, пополнили баланс и скачали диссертацию.

Я впервые на сайте

Отзывы о нас

Исследование задач и алгоритмов целочисленного программирования на основе регулярных разбиений и унимодулярных преобразований : диссертация ... кандидата физико-математических наук : 01.01.09

Год: 2013

Номер работы: 134

Автор:

Стоимость работы: 249 e

Без учета скидки. Вы получаете файл формата pdf

Оглавление и несколько страниц
Бесплатно

Вы получаете первые страницы диссертации в формате txt

Читать онлайн
постранично
Платно

Просмотр 1 страницы = 3 руб



Оглавление диссертации:

Глава 1 Модели и методы целочисленного программирования Данная

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

1.1. приводится ряд постановок задач: общая задача ЦЛП, одномерная и многомерная задачи о рюкзаке, задача поиска целочисленной точки выпуклого многогранного множества. В п.

1.2. дается описание метода регулярных разбиений. Изложена идея алгоритма перебора L - классов для решен

1.1 Постановки задач Приведем ряд постановок задач целочисленного линейного программирования, которые используются для исследования структуры и сложности задач, разработки и анализа алгоритмов их решения. Рассмотрим следующую задачу ЦЛП общего вида: п XQ = 2_jC3X3 3=1 ~^ m a X (1-1) при условиях п У ^ CLijXj < bj, г = 1, . . . , 3=1 га, (

1.2) Xj ^ 0, j = 1, . . . , п, (

1.3) х5 e z , j = l, ..., п. целых чисел, х = (х\, ..., хп). (

1.4) Здесь Cj, b{, dij £

1.2 Метод регулярных разбиений Метод регулярных разбиений [31] широко используется для исследования задач ЦП, построения и анализа алгоритмов, связанных с релаксацией условия целочисленное™ переменных. Это относится к методам отсечения, ветвей и границ, перебора L - классов и некоторым другим. На основе метода регулярных разбиений изучены структура и сложность ряда задач, предложены новые алгоритмы и классы правильных отсечений, построены оценки числа итераций для известных алгоритмов ЦЛП (

2.1 Унимодулярные преобразования д л я задач о рюкзаке

2.1.1 Об оптимальном п о р я д к е п е р е м е н н ы х Рассматривается задача о рюкзаке (обозначим ее

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

2.2 Анализ L — структуры и алгоритмов решения задач о рюкзаке

2.2.1 Семейства трудных задач Рассмотрим задачу (

1.5) поиска допустимой лексикографически максимальной целочисленной точки в следующем множестве: п Q = {х е Ш : x1 + 2^/xj где п ^ 3, к — четное, 1 < к ^ 2(п — 1). п = к}, (

2.3) Отметим некоторые используемые нами особенности задачи о рюкзаке. Так как задача (

1.5) с множеством S7 = К не содержит целевой функции, то описанный ранее алгоритм LCE пре

3.1 Специальный класс задач целочисленного линейного программирования и z — алгоритм В данном разделе приводится описание z - алгоритма для решения задач ЦЛП. Сначала введем некоторые обозначения и рассмотрим изучаемый класс задач.

3.1.1 Специальный класс задач Округлением вектора х° будем считать любую точку с координатами [х®\ или [х®\ + 1 (если {х®} ф 0), где {а} — дробная часть числа а. Округлением вектора х°, допустимым относительно релаксационного многогранника М задачи ЦЛП, буд

3.2 Исследование z — алгоритма с использованием регулярных разбиений В [46] на основе метода регулярных разбиений проведено исследование алгоритма Вотякова А.А. для решения задач целочисленного линейного программирования [10, 11], анализировался вопрос о регулярности этого алгоритма при решении инвариантных задач [11] относительно кубических и других разбиений [31], изучалась известная верхняя оценка числа итераций алгоритма. Рассматривались задачи, упрощающие применение алгоритма, приведен

3.3 Об оценках числа итераций Использование метода регулярных разбиений при получении различных оценок достаточно актуальное направление. Например, в [27,28] предложен и развивается подход к построению верхних оценок среднего числа итераций для известных алгоритмов ЦЛП, а именно некоторых алгоритмов отсечения, метода ветвей и границ (схема Лэид и Дойг), алгоритма перебора L - классов при решении задач об упаковке множества и о многомерном рюкзаке с булевыми неременными. На основе этого подх