Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения | страница реферата 2 | Большая Энциклопедия Рефератов от А до Я
Большая Энциклопедия Рефератов от А до Я
  • Рефераты, курсовые, шпаргалки, сочинения, изложения
  • Дипломы, диссертации, решебники, рассказы, тезисы
  • Конспекты, отчеты, доклады, контрольные работы


    • Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения


    Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения

    Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения




    Категория реферата: Рефераты по математике
    Теги реферата: контрольная работа по математике класс, хозяйство реферат
    Добавил(а) на сайт: Костюк.



    Предыдущая страница реферата | 1  2  3  4  5  6 |



     

    (4)

    2. Алгоритм перебора L - классов

    В [?] и других работах развивается подход к анализу и решению задач целочисленного программирования, основанный на регулярных разбиениях пространства Rn. Много результатов было получено с помощью L-разбиения.

    Дадим определение L-разбиения. Пусть Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения, Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения- символы лексикографического порядка. Точки Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещенияявляются L-эквивалентными, если не существует Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения, такой что Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. Это отношение разбивает любое множество Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещенияна классы эквивалентности, которые называются L-классами. L-разбиение обладает рядом важных свойств.

    1) Каждая точка Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещенияобразует отдельный L - класс. Остальные классы состоят только из нецелочисленных точек и называются дробными.

    2) Если X ограниченное множество, то фактор-множество X/L - конечно.

    3) L - разбиение согласовано с лексикографическим порядком, то есть для любого X все элементы X/L могут быть линейно упорядочены следующим образом: Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещениядля всех Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения.

    Если X ограничено, то X/L можно представить в виде

    Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения

    Рангом L - класса V называется число Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения, если V дробный L - класс и r(V) = n+1 для любой целой точки.

    Алгоритм перебора L - классов основан на идее поиска элемента L - разбиения, непосредственно следующего за данным L - классом в порядке лексикографического возрастания (для задачи на минимум).

    Пусть Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. Рассмотрим этот метод более подробно для многогранника Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. Задача булева программирования (БП) имеет вид:

    Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения

     

     

    (5)

    Соответствующая задача линейного программирования (ЛП) состоит в нахождении лексикографически минимального элемента множества M.

    Пусть Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещенияи известен некоторый представитель Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. Сначала мы ищем соседний к V дробный элемент V' такой, что Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещениягде r - ранг класса V, и x - некоторая точка из V'. Если V' будет найден, продолжаем процесс для V' вместо V.

    В противном случае мы ищем V' такой, что Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения, - ранг V', Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. Если V' не может быть найден, мы уменьшаем (если это возможно) r' на 1 и продолжаем просмотр. Если V' будет найден, мы возвращаемся к началу процедуры и V' становится исходным L - классом.

    Если не существует соседнего дробного L-класса, то либо мы получаем оптимум задачи БП, либо приходим к выводу, что задача не имеет решения. Процесс является конечным, так как M ограничено.

    Опишем алгоритм перебора L - классов. Для простоты номер итерации будем опускать.

    Шаг 0. Решаем исходную задачу ЛП. Если она не имеет решения или ее решение целочисленное, процесс завершается. В противном случае идем на шаг 1.

    Шаг 1. Обозначим через Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещенияоптимальное решение задачи ЛП, которая рассматривалась на предыдущем шаге. Находим

    Рефераты | Рефераты по математике | Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения

     


    Рекомендуем скачать другие рефераты по теме: заключение реферата, защита дипломной работы.



    Предыдущая страница реферата | 1  2  3  4  5  6 |




    Поделитесь этой записью или добавьте в закладки

       

    Категории:



    Разделы сайта




    •