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

ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

1. ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ РЕШЕНИЯ БОЛЬШИХ ОПТИМИЗАЦИОННЫХ ЗАДАЧ
- 1. 1. Генетический алгоритм как метод нахождения оптимальных решений
- 1. 2. Метод решения задачи одномерного раскроя на основе генетического алгоритма
  - 1. 2. 1. Общее описание задачи одномерного раскроя материалов
  - 1. 2. 2. Метод генерации столбцов
  - 1. 2. 3. Математическая постановка задачи раскроя стальных листов разных размеров
  - 1. 2. 4. Генетический алгоритм для решения задачи раскроя стальных листов
  - 1. 2. 5. Практические результаты применения алгоритма GA-CG для задачи раскроя
- 1. 3. Использования генетического алгоритма для решения задачи покрытия множества
  - 1. 3. 1. Постановка задачи о покрытии множества
  - 1. 3. 2. Подход, основанный на генетическом алгоритме, для нахождения минимального покрытия
  - 1. 3. 3. Результаты использования ГА для решения задачи покрытия множества
- 1. 4. Оптимизация структуры атомного кластера с помощью генетического алгоритма
  - 1. 4. 1. Задача конфигурационной оптимизации атомного кластера
  - 1. 4. 2. Обзор предложенных методов
  - 1. 4. 3. Генетический алгоритм оптимизации структуры атомного кластера
  - 1. 4. 4. Параллельная реализация
  - 1. 4. 5. Результаты численных экспериментов нахождения оптимальной структуры атомного кластера
2. МЕТОД НЬЮТОНА ДЛЯ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ БОЛЬШОЙ РАЗМЕРНОСТИ
- 2. 1. Нахождение проекции точки на множество решений двойственной задачи линейного программирования
- 2. 2. Программная реализация и результаты вычислений метода Ньютона для решения двойственной задачи ЛП
3. ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ ОБОБЩЕННОГО МЕТОДА НЬЮТОНА ДЛЯ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ БОЛЬШОЙ РАЗМЕРНОСТИ
- 3. 1. Параллельный итерационный алгоритм
- 3. 2. Основные операции параллельного алгоритма
- 3. 3. Схемы разбиения данных
  - 3. 3. 1. Столбцовая схема
  - 3. 3. 2. Строчная схема
  - 3. 3. 3. Клеточная схема
  - 3. 3. 4. Безматричная схема
- 3. 4. Результаты численных экспериментов
ВЫВОДЫ

Объект исследования и актуальность темы.

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

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

В частности, существенные затруднения связаны с высокой размерностью решаемых задач. Многие прикладные задачи экономики и управления могут быть представлены в виде задач линейного программирования (ЛП), для решения которых давно существуют численные методы и программное обеспечение, и, как могло бы показаться, не представляет никакой трудности найти оптимальное решение [1], [2]. Однако размерности современных задач порою не позволяют решить их традиционными способами, поэтому требуется разработка новых подходов решения с привлечением мощных вычислительных ресурсов. Наличие больших, более мощных и доступных мультипроцессорных компьютеров означает, что параллельное программирование является важным и перспективным направлением современной вычислительной науки, которое целесообразно применять для решения задач большой размерности [3]. Большие практические задачи ЛП часто обладают специфической блочной структурой, для учета которых разработаны различные методы декомпозиции [4]. Большие задачи ЛП, как правило, имеют неединственное решение. Различные методы решения задач ЛП (симплекс-метод, метод внутренних точек, метод квадратичной штрафной функции) дают возможность получать различные решения в случае не единственности. Так симплекс-метод дает решение, которое принадлежит вершине многогранного множества. Методы внутренней точки сходятся к решению, в котором выполнено условие строгой дополняющей нежесткости. Метод внешней квадратичной функции дает возможность найти точное нормальное решение. В данной работе предлагается новый метод нахождения проекции заданной точки на множество решений задачи Л П.

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

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

Нахождение глобального оптимума является общей проблемой для многих отраслей науки, техники и управления, а её решению, глобальной оптимизации, посвящен отдельный раздел прикладной математики [6]. Задачи нахождения глобального оптимума являются весьма сложными с вычислительной точки [7]. В настоящее время большинство методов поиска глобальных экстремумов относится к направленному перебору. Встречающиеся же прикладные: задачи глобальной оптимизации зачастую требуют поиска глобального минимума в пространстве достаточно большого числа переменных исследуемой функции. Примерами таких задач из области химии является поиск глобального минимума поверхности потенциальной энергии (ППЭ) ван-дер-ваальсовых комплексов [8] и предсказание третичной структуры белков [9]. '.

Часто попытки решения NP-трудных задач дискретной или глобальной оптимизации большой размерности связаны с использованием тех или иных эвристических методов. В результате «решения» могут оказаться далекими от оптимальных.

В 1975 г. Дж. Холландом было показано, что поиск решения оптимизационной задачи можно представить в виде эволюции группы решений [10]. Это позволило успешно моделировать процессы, происходящие в природе, для решения NP-полных задач. В последние годы разработчики методов и программ для решения сложных проектных и оптимизационных задач все чаще обращают внимание на эволюционные методы, среди которых алгоритм муравьиной колонии, алгоритм моделирования отжига и генетические алгоритмы.

Генетический алгоритм (ГА) представляет собой технику оптимизации, которая моделирует феномен естественной эволюции (впервые открытой Ч. Дарвином) [11]. При естественной эволюции выживают и дают самое многочисленное потомство особи, наиболее адаптированные к сложным условиям окружающей среды. Степень адаптации, в свою очередь, зависит от набора хромосом конкретной особи, полученного от родителей. Это основа выживания сильнейшегоне только процесс выживания, но и участие в формировании следующего поколения. В природе выживание является определяющей и основной функцией. Генетический алгоритм не пытается оптимизировать единственное начальное решение. Он работает с группой начальных решений, которые кодируются, подобно хромосомам. Отдельные гены хромосомы представляют собой уникальные переменные для изучаемой проблемы. На каждом шаге генетического алгоритма присутствует набор объектов — особей, обладающих «генетической информацией», или «хромосом». Для пар особей определяются правила скрещивания, согласно которым, при переходе на следующий шаг алгоритма, производится потомство на основе «генетической информации» родителей. Из этого потомства при помощи критерия приспособленности выбираются особи, которые войдут в следующее поколение. При отборе «здоровых» хромосом из популяции и использовании генетических операторов (таких как рекомбинирование и мутация) в популяции остаются только те хромосомы, которые лучше всех приспособлены к окружающей среде, т. е. наиболее полно отвечают задаче. Особи могут также подвергаться случайным мутациям, в результате которых наследственная информация подвергается изменениям.

Использовавшиеся для моделирования биологической эволюции генетические алгоритмы были обобщены для использования в глобальной оптимизации [12]. В этом случае — «генетическая информация» — это точка в пространстве аргументов, а «приспособленность» — значение целевой функции. Правила скрещивания и мутации выбираются в зависимости от строения множества, на котором определена целевая функция.

К достоинствам генетических алгоритмов относится простота принципов и использование исследуемой функции как «черного ящика», о свойствах которой может быть ничего не известно до начала оптимизации. Однако существенным недостатком является большая специфичность правил скрещивания и мутации по отношению к исследуемой функции. В рамках использования генетических алгоритмов в каждой новой задаче исследователь вынужден вновь формулировать новые правила скрещивания и мутации. Тем не менее, генетические алгоритмы являются достаточно мощным средством решения задач глобальной оптимизации, поскольку их недостатки зачастую оборачиваются их достоинствами. Во-первых, «потомки» всегда несколько похожи на «родителей», за счёт чего процедура позволяет быстро выделить фрагменты генетической информации, отвечающие наилучшей приспособленности и использовать их на следующих шагах алгоритма. Во вторых, правила мутации и скрещивания могут быть подобраны таким образом, что используют особенности задачи при минимизации. И наконец, программы с использованием генетических алгоритмов реже требуют перепроверки результатов и повторного запуска, чем программы с использование моделирования отжига. Но наибольшее преимущество генетические алгоритмы имеют при глобальной оптимизации функции дискретных переменных, когда применение других подходов затруднено.

В связи с интенсификацией производства в настоящее время вопросы оптимизации планирования и управления производства на предприятиях очень актуальны. Перспективным направлением работ по повышению эффективности функционирования автоматизированных систем управления является разработка и реализация программных систем, позволяющих решать совокупность взаимосвязанных оптимизационных задач планирования производства. Построение оптимальных карт раскроя ресурсного материала является одной из самых трудоемких задач на заготовительной стадии производства. В то же время это одна из самых важных задач в ресурсосберегающих технологиях, поскольку напрямую ведет к экономии материала и снижению отходов. Начало теоретическим исследованиям в области методов рационального раскроя положили труды академика JL В. Канторовича [13, 14], в которых он показал возможность эффективного решения оптимизационных задач с помощью ЭВМ. В своих работ Канторовича JI. В. впервые представил задачу раскроя одинаковых листов материала в виде задачи целочисленного линейного программирования, в которой матрица ограничений задана неявно. Эта модель стала основой для многих методов решений. На протяжении последних 70 лет исследованиям в области раскроя и разработки новых алгоритмов укладки плоских заготовок было посвящено множество отечественных и зарубежных работ [15] - [53]. Однако задача раскроя на заводах, где в качестве исходных ресурсов используют материалы различных типоразмеров, порождает очень большую матрицу ограничений, а вместе с тем и огромное количество переменных, что часто не позволяет использовать классические оптимизационные методы. В работе [54] показано, что построение эвристических алгоритмов для решения задачи раскроя материалов различных размеров необходимо, так как точные подходы не пригодны в этом случае. Разработка нового метода решения конкретной практической задачи с учетом ее специфики позволит получить качественно лучшее решение и таким образом повысить эффективность производства.

Задача о покрытии множества (ЗПМ) системой его подмножеств [55]-[57] является математической моделью для многих важных приложений, таких как составление расписания [58], планирование сервиса, распознавание образов [59]-[61], прогнозирование, логический анализ данных, упрощение булевских выражений [57] и т. д. ЗПМ относится к классу NP-полных задач [5], поэтому построение алгоритма нахождения оптимального или приближенного решения является весьма сложной задачей. Однако структура представления реальной задачи предоставляет дополнительную информацию, позволяющую решать ЗПМ довольно больших размерностей (несколько сотен строк и несколько миллионов столбцов) с результатом, отличающимся от оптимального решения примерно на 1%, за приемлемое время счета [57]. Практические методы решения ЗПМ опираются на различные подходы и могут быть распределены по классам таким, как класс алгоритмов, основанных на теории линейного программирования, класс эвристических алгоритмов и класс алгоритмов ветвей и границ [62]. В данной работе будет приведено формальное представление задачи, а так же предложен алгоритм решения ЗПМ, основанный на принципах генетического алгоритма.

Исследования атомных и молекулярных кластеров — быстро развивающаяся область физики и химии [63]-[77]. Как видно из приведённых литературных данных, совершенствование теоретических и экспериментальных методов позволяет исследовать все более сложные системы со всё возрастающей точностью. Поверхности потенциальной энергии кластеров являются своеобразным местом встречи, где теоретические модели могут найти подтверждение со стороны экспериментальных подходов. В то же время, функции, описывающие ППЭ кластеров, в дополнение к большому числу аргументов (степеней свободы), обладают во многих случаях большим числом стационарных точек. Правильное нахождение геометрических конфигураций кластеров, отвечающих наиболее глубоким минимумам ППЭ, важно для правильного описания свойств этих частиц. В то же время, нахождение стационарных точек и, в частности, минимумов, на сложных гиперповерхностях представляет собой отдельную проблему, для решения которой существуют специализированные численные методы. ГА является успешным методом определения глобального минимума, но иногда с физической точки зрения структуры, соответствующие более высоким локальным минимумам, могут быть более важными, чем глобальный минимум. Наконец, стоит отметить, что биологически активные формы белков, возможно, не всегда соответствуют глобальным минимумам. Таким образом, возможность ГА наряду с поиском глобального минимума находить семейство локальных минимумов, близких к глобальному, является особенностью этого метода и имеет важную практическую ценность.

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

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

1. Разработка методов решения задачи линейного программирования с большим числом переменных и ограничений, программная реализация и проведение вычислительных экспериментов;

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

3. Разработка алгоритма решения задачи одномерного раскроя листовых материалов различных типоразмеров на основе генетического алгоритма и алгоритма генерации столбцов;

4. Исследование задачи покрытия множества и разработка алгоритма ее решения на основе генетического алгоритма;

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

Научная новизна:

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

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

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

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

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

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

Разработанный алгоритм решения задачи одномерного раскроя листовых материалов различных типоразмеров внедрен и успешно используется в производственном процессе трубопрокатного завода VG PIPE (Вьетнам).

Результаты, выносимые на защиту состоят в следующем:

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

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

3. Получена оценка порогового значения параметра, начиная с которого метод находит проекцию заданной точки на множество решений двойственной задачи ЛП;

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

Апробация работы. Результаты работы докладывались и обсуждались на следующих конференциях:

1. На 13-й Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, Россия, 2007 г.);

2. На 9-м Международном семинаре по компьютерным наукам и информационным технологиям CSIT'07 (Уфа, Россия, 2007 г.);

3. На XIV Байкальской международной школе-семинаре (Иркутск, Байкал, Россия, 2008 г.);

4. На семинарах отдела прикладных проблем оптимизации ВЦ РАН (Москва, Россия, 2006;2008 гг.);

Основные результаты опубликованы в [78]-[83].

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

В 1.2 приведена модель задачи одномерного линейного раскроя материала, предложенная JI.B. Канторовичем в [13]. Из всех известных методов решения этой задачи выбран и описан метод генерации столбцов. Представлена так же модель для расширенной задачи раскроя с различными исходными материалами на примере раскроя листов стали на трубопрокатном заводе. Показано, что для расширенной задачи. значительно возрастает степень сложности из-за роста количества переменных, и таким образом, почти невозможно решить ее целиком с помощью известных алгоритмов. Доказано, что решение «большой» задачи определено на множестве разбиений вектора заказа. На основе доказанных теорем разработан новый алгоритм решения расширенной задачи на основе комбинирования генетического алгоритма с методом генерации столбцов. Работа предложенного алгоритма продемонстрирована на наборе тестовых примеров. Результаты практического внедрения алгоритма в производственный процесс трубопрокатного завода VG PIPE (Вьетнам) показали его эффективность с точки зрения сокращении объема отходов. Отход металла уменьшился почти в 2 раза.

В параграфе 1.3 предложен эвристический алгоритм решения задачи нахождения минимального покрытия с неоднородной стоимостью. Алгоритм основан на генетическом алгоритме с операторами кроссовер и мутации, моделирующими различные свойства естественной эволюции, такие как «доминантность», «чистокровность» и «биологическое разнообразие». Работоспособность разработанного алгоритма проверена на тестовых задачах библиотеки OR-library [84], доступной в Интернете. Результаты вычисления показывают, что алгоритм может дать оптимальное решение для задач средних размерностей и качественно лучшее решение для задач больших размерностей, чем полученное другими алгоритмами и опубликованное в библиотеке OR-library.

Задача оптимизация структуры атомного кластера подробно рассмотрена в параграфе 1.4. Дан обзор как точных, так и эвристических методов поиска минимумов поверхности потенциальной энергии. Представлен генетический алгоритм нахождения множества достаточно хороших конфигураций атомных кластеров с точки зрения минимальной потенциальной энергии без возможности доказательства оптимальности найденных решений. Предложенный алгоритм призван найти набор «хороших» структур атомного кластера за относительно малое время вычислений. Так же разработана схема параллельной реализации предложенного алгоритма, дающая возможность использования современных мощных вычислительных комплексов для нахождения оптимальных структур атомных кластеров больших размеров. Приведено сравнение работы предложенного алгоритма с алгоритмом монотонного случайного спуска по локальным минимумам (Mono-tonic Basin Hopping) для некоторых кластеров Ленарда-Джонса. Так же представлены результаты вычислений для кластеров Морса с количеством атомов 80 < Natom < 95, отсутствующие в Кембриджской базе данных [85] .

В главе 2 предлагается новый метод нахождения проекции заданной точки на множество решений двойственной задачи ЛП, который весьма эффективен для решения в системе MATLAB для однопроцессорных компьютеров задачи ЛП с большим числом переменных (до несколько десятков миллионов) и средним числом ограниченийнеравенств (до 5 тысяч ограничений). Метод заключается в однократной безусловной оптимизации вспомогательной функции и находит проекцию, если параметр этой функции больше некоторого порогового значения. Получена формула для этого порогового значения.

Показано, что повторная безусловная оптимизация этой функции, в которой вместо точки проектирования взято решение двойственной задачи, дает некоторое точное решение прямой задачи ЛП. То есть решения прямой и двойственной задач ЛП можно найти в результате двукратной безусловной оптимизации вспомогательной функции, размерность переменных которой равна числу ограничений задачи ЛП. Для безусловной оптимизации предлагается использовать обобщенный метод Ньютона. Так как вспомогательная функция является выпуклой квадратичной функцией, то для ее минимизации целесообразно применять обобщенный метод Ньютона, который, как показал О. Мангасарьян [86], сходится глобально за конечное число шагов. В параграфе 2.1 приведена программа DLP, которая реализует предложенный метод в системе MATLAB. Проведены численные эксперименты на случайно сгенерированных задач ЛП. Они показали высокую эффективность предложенного метода, возможность решать задачи ЛП с несколькими миллионами переменных и до 5 тысяч ограничений за приемлемой время. Сравнение раннее предложенного метода нахождения проекции на множество решений двойственной задачи [87] с предложенным в данной работе показало явное преимущество последнего. Это связано с тем, что в [87] вспомогательная функция оптимизируется на положительном ортанте и для применения обобщенного метода Ньютона требуется учесть условия неотрицательности переменных с помощью штрафной функции. Еще раз подчеркнем, что предлагаемая в работе вспомогательная функция оптимизируется на всем пространстве обобщенным методом Ньютона.

В третьей главе предлагаются, исследуются и экспериментально проверяются четыре параллельные схемы решения задач ЛП с помощью метода, предложенного в [88]. Метод из [88] подробно исследован в [87]. Численные эксперименты и сравнение программы.

EGM, реализованной в MATLAB, с известными коммерческими и исследовательскими программами показали превосходство программы EGM [89] и возможность решать задачи ЛП с 50 миллионами переменных, но с небольшим числом ограничений (не более 4 тысяч). Параллельная реализация позволила увеличить число ограничений до 200 тысяч и решать задачи ЛП за существенно меньшее время.

выводы.

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

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

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

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

5. Предложены четыре схемы параллельной реализации метода решения прямой и двойственной задачи ЛП. Строчная схема наиболее предпочтительна с точки зрения ускорения, но ее применение к задачам ЛП ограничено размерностью памяти на каждом процессоре. Столбцовая схема наиболее эффективна при очень большом числе переменных и средним числе ограничений. При очень большом числе ограничений (порядка сотен тысяч) следует применять безматричную схему, по этой схеме была решена задача ЛП с 2-мя миллионами переменных при 200-х тысячах ограничений за время порядка 40 минут.

6. Задача одномерного раскроя листовых материалов и разработанное программное обеспечение внедрены в практику производства трубопрокатного завода VG PIPE (Вьетнам) и дали значительную экономию металла.

Показать весь текст

Список литературы

Еремин И. И. Теория линейной оптимизации. Екатеринбург, УрО РАН, 1998.
Васильев Ф. П., Иваницкий А. Ю. Линейное программирование. М.: Факториал, 2003.
Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. -СПб.:БХВ-Петербург, 2002. 608с.
Цурков В. И. Декомпозиция в задачах большой размерности. М.: Наука. 1981.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — Пер. с англ.— 1982.
Стронгин Р.Г., Сергеев Я. Д., Гришагин В. А. Введение в параллельную глобальную оптимизацию. -Н.Новгород: Изд-во ННГУ, 1998, 87стр.
Жиглявский А. А., Жилинкас А. Г. Методы поиска глобального экстремума. М.: Наука. Физматлит, 1991.
Maranas С. D., Floudas С. A. A global optimization approach for Lennard-Jones microclusters //J. Chem. Phys., v 97, pp. 7667−7678, 1992.
Kolinski A., Godzik A., Skolnick J. A general method for the prediction of the three dimensional structure and folding pathway of globular proteins: Application to designed helical proteins //J. Chem. Phys., v. 98, pp. 7420−7433, 1993.
Holland J. H. Adaptation in natural and artificial systems.- The University of Michigan Press, Ann Harbor, MI, 1975.
Гладков JI.A., Курейчик В. В., Курейчик В. М. Генетические алгоритмы / Под ред. В. М. Курейчика. — 2-е изд., испр. и доп.- М.: ФИЗМАТЛИТ, 2006. 320 с.
Goldberg D. Е. Genetic algorithms in search, optimization, and machine learning —MA.: Addison-Wesley, 1989.
Канторович Л.В. Математические методы в организации и планировании производства . — Л.: Изд-во ЛГУ, 1939 (воспроизведено в сб. «Применение математики в экономических исследованиях М., Соцэкгиз, 1959).
Канторович Л.В., Залгаллер В. А. Рациональный раскрой промышленных материалов — Новосибирск: Наука, 1971. — 299 с.
Бронфельд Г. Б. Алгоритм решения задачи оптимального распределения плана производства / / Труды института. Автоматизация и механизация управления производством, Горький, НИИУавтопром. —1977 — вып.2—с.75−83.
Cheng, С.Н., Feiring, B.R., Cheng, Т.С.Е. The cutting stock problem- a survey. // International Journal of Production Economics.— 1994. vol.36.- P.291−305.
Gilmore P., Gomory R. A linear programming approach to the cutting stock problem.// Operations Research, 9, 1961: 849−859.
Gilmore P. C., Gomory R. E. A linear programming approach to the cutting stock problem —Part II. // Operations Research, 11, 1963: 863−888.
Brown A.R. Optimum packing and depletion: The computer in space and resource usage problems// New York, 1971.
Dantzig G. В., Wolfe P. Decomposition Principle for Linear programs. 11 Operations Research, 8, 1960: 101−111.
Dyckhoff H., Kruse H.-J., Abel D., and Gal T. Trim loss and related problems // Omega, 13, 1985: 59−72.
Dyckhoff H. A typology of cutting and packing problems, f/ European Journal of Operational Research, 44(2), 1990: 145−159.
Dyckhoff H., Wascher G. Cutting and packing. // European Journal of Operational Research, 44(2), 1990.
Wascher G., Haubner H., Schumann H. An improved typology of cutting and packing problems.// European Journal of Operational Research, 183(3), 2007: 1109−1130.
Wang P.Y., Wascher G. Cutting and packing.)/ European Journal of Operational Research, 141(2), 2002.
Oliveira J. F., Wascher G. Cutting and Packing. // European Journal of Operational Research, 183, 2007: 1106−1108.
Marcotte O. The cutting stock problem and integer rounding // Math. Program., 33, No. 1, 1985. -p.82−92.
Shahin A. A., Salem О. M. Using genetic algorithms in solving the one-dimensional cutting stock problem in the construction industry. // Canadian Journal of Civil Engineering, Vol.31 (2), 2004. pp.321−332
Afshar A. et al. An Improved Linear Programming Model for One-Dimensional Cutting Stock Problem. // First International Conference on Construction In Developing Countries, Karachi, 2008.
Belov G. and Scheithauer G. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths. // European Journal of Operational Research, 141, no. 2, Special issue on cutting and packing, 2002. -p. 274−294.
Belov G. and Scheithauer G-Л branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. // Technical report, Dresden University, 2003, URL: www.math.tu-dresden.de/?capad.
Belov G. and Scheithauer G. Setup and open stacks minimization in one-dimensional stock cutting // Technical report, Dresden University, 2003.
Sallaume S. et al. One Dimensional Cutting Stock Problem with Redevelopment of the Surplus Material. // EngOpt 2008, Rio de Janeiro, Brazil, 01 05 June 2008.
Wongprakornkul S. et al. Optimization Based Heuristic Approaches for Solving an Integrated One-dimensional Cutting Stock-Transportation Problem. I j Journal of Mathematics and Statistics 3 (3): 142−150, 2007.
Coffman E. G., Garey M. R., and Johnson D. S. Approximation algorithms for bin packing: A survey. // In D. S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston, 1997.
Falkenauer E. Tapping the full power of genetic algorithm through suitable representation and local optimization. // In J. Biethann and V. Nissen, editors, Evolutionary Algorithms in Management Applications. Springer-Verlag, Berlin, 1995.
Falkenauer E. A hybrid grouping genetic algorithm for bin packing. // Journal of Heuristics, 2:5−30, 1996.
Belov G. Problems, Models and Algorithms in One- and Two-Dimentional Cutting Dissertation. TU Dresden, 2004
Puchinger J. Combining Metaheuristics and Integer Programming for Solving Cutting and Packing Problem. Dissertation. Vienna University of Technology.
Scheithauer G. and Terno J. A Branch-and-Bound Algorithm for Solving One-Dimentional Cutting Sock Problems Exactly. // Applicationes Matematicae 23 (2), 1995. pp. 151−167
Alves С. M. M. Cutting and Packing: Problems, Models and Exact Algorithms. Dissertation. Universidade de Minho. 2005
Rietz J. and Dempe S. Large Gaps in One-dimentional Cutting Stock Problems. // Discrete Applied Mathematics, Vol.156 (10), 2008.
Moretti A. C. et al. Nonlinear Cutting Stock Problem Model to minimize the Number of different Patterns and Objects. // Computational & Applied Mathematics, Vol.27 (1), 2008. pp.61−78
Belov G. and Letchford A. N. A Node-Flow Model for ID Stock Cutting: Robust Branch-Cut-and-Price. 2005.
Foerster H., Wascher G. Pattern Reduction in One-Dimentional Cutting Stock Problems. // Int. Journal of Production Research, Vol.38(7), 2000. pp.1657−1676.
Wongprakornkul S. Round Down Technique for Solving an Integer Linear Programming. // KKU Science Journal vol.36, 2008. pp. 187−198
Скобцов Ю.А., Балабанов B.H. К вопросу о применении метаэвристик в решении задач рационального раскроя и упаковки // Вестник Хмельницкого национального университета. — 2008. — Т. 1, N 4. С. 205−217.
Подлазова А.В. Генетические алгоритмы на примерах решения задач раскроя // Проблемы управления, № 2. 2008. -сс.57−63.
Мухачева Э.А., Мухачева А. С., Валеева А. Ф. Картак В.М. Методы локального поиска оптимума в задачах ортогонального раскрояи упаковки: аналитический обзор и перспективы развития.// Информационные технологии, № 5, 2004, приложение, -С. 2−17.
Мухачева Э. А. Рациональный раскрой промышленных материалов. Применение АСУ. М.: Машиностроение, 1984. — 176 с.
Мухачева А.С., Чиглинцев А. В. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя // Информационные технологии. 2001. — № 3. — С. 27−31.
Hinterding R., Khan L. Genetic algorithms for cutting stock problems: with and without contiguity. J J Evo Workshops, 1994: 166−186.
Liang K., Yao X., Newton C., Hoffman D. A new evolutionary approach to cutting stock problems with and without contiguity. // Computers & Operations Research, 29, 2002: 1641−1659.
Holthaus O. Decomposition approaches for solving the integer onedimen-sional cutting stock problem with different types of standard lengths.// European Journal of Operational Research, 141, 2002. pp. 295−312.
Ceria S. et all. Set Covering Problem. //In Dell’Amico, F. Maffioli and S. Martello (eds.), Annotated Bibliographies in Combinatorial Optimization.: Wiley and Sons, 1997.- P.415−428.
Galinier P. and Heztz A. Solution techniques for the large set covering problem. //Discrete applied Mathematics.— 2007.— vol.155. Issue 3.
Caprara A., Fischetti M., Toth P. Algorithms for the set covering problem. //Working Paper, DEIS, University of Bologna — 1998.
Capara A. et all. Algorithms for Railway Crew Management. //Mathematical Programming.— 1997.—vol.79.— P.125−141.
Дюкова E. В. Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основныемодели. Учебное пособие для студентов математических факультетов педвузов. М.: Прометей, 2003. — 29 с.
Дюкова Б.В., Журавлёв Ю. И. Дискретный анализ признаковых описаний в задачах распознавания большой размерности. // Ж. вычисл. матем. и матем. физ. 2000. Т. 40. № 8. С. 1264−1278.
Дюкова Е.В., Инякин А. С. Задача таксономии и тупиковые покрытия целочисленной матрицы. // Сообщения по прикладной математике. М.: ВЦ РАН, 2001. 28с.
Еремеев А. В., Заозерская J1. А., Колоколов А. А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования. ./ Сборник трудов Сибирской конференции по дискретному анализу и исследованию операций. 2000. С. 37−41.
Marka S., Cheney С. P., Wang W., Lupke G., Gilligan J., Yao Y., and Tolk N. H. Nonlinear energy-selective nanoscale modifications of materials and dynamics in metals and semiconductors // Tech. Phys., 1999 V 44, pp. 1069−1072.
Leary R. H. Global optimization on funneling landscapes // J. Global Optim., 18, 367−383, 2000.
Doye J.P.K., Wales D.J., Berry R.S. The effect of the range of the potential on the structure of clusters// J. Chem. Phys, 103, 4234−4249, 1995.
Doye J. P. K. and Wales D. J. Structural consequences of the range of the intera-tomic potential: A menagerie of clusters// J. Chem. Soc., Faraday Trans., 93, 4233−4244, 1997.
Doye J. P. K., Leary R. H., Locatelli M., Schoen F. Global Optimization of Morse Clusters by Potential Energy Transformations// INFORMS Journal on Computing 16(4): 371−379, 2004.
Grosso A., Locatelli M., Schoen F. A population-based approach for hard global optimization problems based on dissimilarity measures// Mathematical Programming, Vol. 110, 373−404, 2007.
Евтушенко Ю.Г., Малкова В. У., Станевичюс А. А. Распараллеливание процесса поиска глобального экстремума// Автоматика и Телемеханика, 46−59, 2007.
Посыпкин М. А. Параллельный эвристический алгоритм глобальной оптимизации // Труды ИСА РАН, Т. 32, 2008 г., С. 117−130.
Wille L.T. Minimum-energy configurations of atomic clusters new results obtained by simulated annealing // Chem. Phys. Lett., v. 133, pp. 405−410, 1987.
Deaven D. M., Но К. M. Molecular-geometry optimization with a genetic algorithm// Phys. Rev. Lett., 75, pp. 288−291, 1995.
Deaven D. M., Tit N., Morris J. R., Но К. M. Structual optimization of Lennard-J ones clusters by a genetic algorithm// Chem. Phys. Lett. 1996, v 256, pp. 195−200.
Ona O., Bazterra V. E., Caputo M. C., Ferraro M. В., Fuentealba P. and Facelli J. C. Modified genetic algorithms to model atomic cluster structures: CuSi clusters// J. Mol. Struct. (THEOCHEM) 681, 149, 2004.
Wolf M. D., Landman U. Genetic algorithms for structural optimization //J. Phys. Chem. A, v. 102, pp. 6129−6137, 1998.
Johnston R. L. Evolving better nanoparticles: Genetic algorithms for optimising cluster geometries //(Dalton Perspective) Dalton Transactions, pp. 4193−4207, 2003.
Cheng L. et al. A connectivity table for cluster similarity checking inthe evolutionary optimization method, j I Chemical Physics Letters, 389, 2004. pp.309−314.
Nguyen Minh Hang et al. A model combining genetic algorithm and simplex method for solving a production expense minimizing problem. // Journal of Computer Science and Cybernetics, No22, Vol.4, Hanoi, 2006. P.319−324 (in Vietnamese).
Нгуен M.X. Применение генетического алгоритма для решения задачи планирования производства. // Труды XIII-й Всероссийской конференции «Математическое программирование и приложения», Екатеринбург, Россия, Март 2007. -с. 132−133.
Nguyen М.Н. About one application of genetic algorithm in Production planning problem. // Proc. of the 9th Int. Workshop on Сотр. Sci. and Inf. Techn., Ufa, 2007, (Sept. 13−16), Vol.1, pp. 225−229.
Нгуен M.X. Применение генетического алгоритма для решения одной задачи планирования производства. / / Динамика неоднородных систем. —М.: Издательство ЛКИ, 2007.— т. 29, вып. 11.—С.160−167.
Нгуен М.Х. Двухэтапный метод решения одной задачи раскроя материалов. // Труды XIV Байкальской международной школы-семинара, т. 4 «Приложение методов оптимизации», Иркутск-Северобайкальск, Россия, Июль 2008. —С. 192−202.
Нгуен М.Х. Применение генетического алгоритма для задачи нахождения покрытия множества. // Динамика неоднородных систем. —М.:Издательство ЛКИ, 2008 — т. 33, вып. 12 —С.206−219.
Beasley J.E. OR-Library: distributing test problems by electronic mail. //Journal of the Operational Research Society.— 1990.—vol.41.— P. 10 691 072.
The Cambridge Cluster Database. http: //www-wales. ch. cam. ас. uk/ CCD. html.
Mangasarian O.L. A Newton Method for Linear Programming. // Journal of Optimization Theory and Applications. 2004. V. 121. P. 1−18.
Моллаверди Н.И. Методы решения задач линейной оптимизации большой размерности. Диссертация на соискание ученой степени кандидата физико-математических наук. ВЦ РАН. 2005.
Голиков А.И., Евтушенко Ю. Г. Метод решения задач линейного программирования большой размерности // ДАН, т.397, N6, 2004. С. 727−732.
Evtushenko Yu. G., Golikov A. I., and N. Mollaverdi Augemented La-grangian method for large-scale linear programming problems, j/ Optimization Methods and Software, vol. 20, N4⁵, 2005. -pp.515−524.
Unger R. The Genetic Algorithm Approach to Protein Structure Prediction Structure and Bonding, vol. 110, 2004. -pp. 153−175.
Feltl H. and Raidl R.G. An improved hybrid genetic algorithm for the generalized assignment problem j I Proceedings of the 2004 ACM symposium on Applied computing, 2004. -pp. 990−995.
Gunther R. Raidl The multiple container packing problem: A genetic algorithm approach with weighted codings // SIGAPP Appl. Comput. Rev., vol. 7 no.2, 1999. -pp. 22−31.
Mahmood A. A Hybrid Genetic Algorithm for Task Scheduling in MultiprocessorReal-Time Systems // Journal of Studies in Informatics and Control, vol.9, no.3, 2000.
Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации. // Дискретная математика и ее приложения. М.: Изд-во центра прикладных исследований при механико-математическм факультете МГУ, 2001. — С 84−117.
Blum С. and Roli A. Hybrid Metaheuristics: An Introduction.)I Studies in Computational Intelligence, Vol. 114, 2008.
Батищев Д. И. Генетические алгоритмы решения экстремальных задач// Учеб. пособие. Воронеж, гос. техн. ун-т- Нижегородский гос. ун-т. Воронеж.— 1995.
Iwanmra К., Okaday N., Deguchiz Y. Recent Advancements of a Genetic Algorithm to Solve the Set Covering Problem — 2004.
Сигал И.Х., Иванова А. П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. —М.: ФИЗМАТЛИТ, 2007.
Lan G. and DePuy G.W. On the effectiveness of incorporating randomness and memory into a multi-start metaheuristic with application to the Set Covering Problem. // Computers and Industrial Engineering.— vol.51, Issue 3 — 2006.
Beasley J.E. and Jornsten K. Enhancing an algorithm for set covering problems. // European Journal of Operational Research. -1992.—No. 58.— R 293−300.
Jacobs L.W. and Brusco M.J. A simulated annealing-based heuristic for the set covering problem. // Working paper, Operations Management and1. fprmation Systems Department, Northern Illinois University, Dekalb, IL 60 115, USA 1993.
Евтушенко Ю. Г. Численный метод поиска глобального экстремума (перебор на неравномерной сетке). Журнал вычислительной математики и математической физики, Т. 11, N 6, 1971. С. 1390−1403.
Евтушенко Ю.Г., Ратькин В. А. Метод половинных делений для глобальной оптимизации функции многих переменных // Техническая кибернетика, № 1, 119−127, 1987.
Kirkpatrick S., Gelatt С. D. and Vecchi М. P. Optimization by simulated annealing //Science, v.220. pp.617−680, 1983.
Schneider J., Morgenstern I., Singer J. M. Bouncing towards the optimum: Improving the results of Monte Carlo optimization algorithms // Phys.Rev. E, v.58, pp. 5085−5095, 1998.
Metropolis N., Rosenbluth A. W., Rothenbluth M. N., Teller A. H., Teller E. Equations of state calculations by fast computing machines // J. Chem. Phys., v.21, p. 1087, 1953.
Mangasarian O.L. A Finite Newton Method for Classification // Opti-mizat. Meth. and Software. 2002. V. 17. P. 913−930.
Голиков А.И., Евтушенко Ю. Г., Моллаверди H. Применение метода Ньютона к решению задач линейного программирования большойразмерности // Ж. вычисл. матем. и матем. физ. 2004. Т. 44. № 9. С. 1564−1573.
Голиков А.И., Евтушенко Ю. Г. Нахождение проекции заданной точки на множество решений задач линейного программирования. // Труды института математики и механики УрО РАН. Т. 14. № 2. 2008. С. 33−47.
Голиков А.И., Евтушенко Ю. Г. Отыскание нормальных решений в задачах линейного программирования // Ж. вычисл. матем. и матем. физ. 2000. Т. 40. № 12. С. 1766−1786.
Kanzow С., Qi Н., Qi L. On the Minimum Norm Solution of Linear Programs. // Journal of Optimization Theory and Applications. 2003. V. 116. P.333−345.
Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
Попов Л.Д. Квадратичная аппроксимация штрафных функций при решении задач линейного программирования большой размерности //Ж. вычисл. матем. и матем. физ. 2007. Т. 47. № 2. С. 206−221.

Заполнить форму текущей работой