Построение сеточной области

МАГИСТЕРСКАЯ ДИССЕРТАЦИЯ

По направлению подготовки 01.04.02 Прикладная математика и информатика

Сеточный алгоритм решения задачи линейного программирования

Выполнил студент Леготин Игорь Олегович

академическая группа МПмаг-202, курс 2 очной формы обучения

____________________________________

«____» ____________ 2016 г.

ДОПУЩЕН К ЗАЩИТЕ Протокол заседания кафедры от «___» ___________ 2016 г. № ____ Заведующий кафедрой Павленко Вячеслав Николаевич __________________________________   «___» _________ 2016 г.     Научный руководитель Соколинская Ирина Михайловна Доцент Кандидат физико-математических наук __________________________________   «___» _________ 2016 г.  

Челябинск

Содержание

Введение............................................................................................................. 3

1.Сеточный алгоритм........................................................................................ 4

... 1.1.Постановка задачи................................................................................... 4

... 1.2.Идея алгоритма....................................................................................... 5

... 1.3.Построение сеточной области................................................................. 8

... 1.4.Пересечение многогранника M с ячейкой 𝛼...................................................... 10

2.Схема сеточного алгоритма............................................................................................ 12

.... 2.1.Схема головной подпрограммы.......................................................................... 12

2.2.Схема подпрограммы инициализации переменных init........................ 16

... 2.3.Схема подпрограммы вычисления псевдопроекции............................. 18

3.Модельный пример........................................................................................ 22

4.Полученные результаты................................................................................ 24

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

Приложение 1

Приложение 2

Введение

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

Сеточный алгоритм

Постановка задачи

Пусть задана задача линейного программирования

Построение сеточной области - student2.ru

Определим фейеровское отображение Построение сеточной области - student2.ru следующим образом:

Построение сеточной области - student2.ru

Пусть M – многогранник, задаваемый ограничениями задачи линейного программирования . Такой многогранник всегда является выпуклым. Известно [10], что Построение сеточной области - student2.ru будет однозначным непрерывным M-фейеровским отображением для любой системы положительных коэффициентов Построение сеточной области - student2.ru , таких, что Построение сеточной области - student2.ru , и коэффициентов релаксации Построение сеточной области - student2.ru . Полагая в формуле Построение сеточной области - student2.ru и Построение сеточной области - student2.ru Построение сеточной области - student2.ru , получаем формулу

Построение сеточной области - student2.ru ,

которая будет использоваться в сеточном алгоритме.

Обозначим

Построение сеточной области - student2.ru .

Под фейеровским процессом, порождаемым отображением Построение сеточной области - student2.ru при произвольном начальном приближении Построение сеточной области - student2.ru , будем понимать последовательность Построение сеточной области - student2.ru . Известно, что указанный фейеровский процесс сходится к точке, принадлежащей множеству M:

Построение сеточной области - student2.ru .

Будем кратко обозначать это следующим образом: Построение сеточной области - student2.ru .

Под Построение сеточной области - student2.ru -проектированием (псевдопроектированием) точки Построение сеточной области - student2.ru на многогранник M понимается отображение Построение сеточной области - student2.ru .

Идея алгоритма

В общем виде сеточный алгоритм может быть описан следующим образом. Все пространство Построение сеточной области - student2.ru делится гиперкубической сеткой на ячейки с переменной длиной грани. Размер ячейки может динамически меняться в зависимости от скорости изменения исходных данных: чем быстрее меняются данные, тем больше становится ячейка, чтобы успевать следить.

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

Построение сеточной области - student2.ru

Рис. 1. Сеточная область кубической формы с целевой ячейкой в центре.

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

Целевая точка – это некоторая точка, находящаяся вне сеточной области. Ее координаты могут динамически вычисляться по коэффициентам целевой функции. Например, при целевой функции Построение сеточной области - student2.ru в качестве целевой точки можно взять точку (T, 2T), где T – достаточно большое положительное число.

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

Неформально сеточный алгоритм может быть описан следующей последовательностью действий.

1. Первоначально выбирается сеточная кубическая область с длиной ребра r и нулевой вершиной в точке g, заведомо покрывающая многогранник M.

2. Выбирается целевая точка Построение сеточной области - student2.ru , расположенная вне сеточной области.

3. Сеточная область разбивается на K ячеек.

4. В условиях динамического изменения входных данных (A, b, c) для всех ячеек внутри сеточной области вычисляется псевдопроекция из точки z на пересечение ячейки с многогранником M. Если пересечение пусто, то такие ячейки отбрасываются.

5. Если получено пустое множество псевдопроекций, то мы увеличиваем размер сеточной области в w раз и переходим на шаг 2.

6. Если получено непустое множество псевдопроекций, то на нем вычисляется максимум целевой функции.

7. Если расстояние от точки максимума до центра сеточной области меньше Построение сеточной области - student2.ru , то длина ребра сеточной области r уменьшается в 2 раза.

8. Если расстояние от точки максимума до центра сеточной области больше Построение сеточной области - student2.ru , то длина ребра сеточной области r увеличивается в 1.5 раза.

9. Центр сеточной области перемещается в центр ячейки, в которой достигнут максимум, и переходим на шаг 2.

Псевдопроекции на шаге 4 для различных ячеек сеточной области могут вычисляться параллельно без обменов данными между процессами. Фейеровский процесс вычисления псевдопроекции, стартовавший из целевой точки на шаге 4, вычисляется до конца, несмотря на то, что координаты целевой точки и сам многогранник M в процессе счета могли измениться. Выполнение условия шага 5 означает, что входные данные изменяются быстрее, чем мы вычисляем псевдопроекции. Константы Построение сеточной области - student2.ru и Построение сеточной области - student2.ru , используемые при выполнении шагов 7 и 8, являются параметрами алгоритма.

Построение сеточной области

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

Пусть Построение сеточной области - student2.ru – размерность пространства решений, Построение сеточной области - student2.ru – количество ячеек в сеточной области по одному измерению. Пусть Построение сеточной области - student2.ru – количество MPI‑процессов, используемых для распараллеливания вычислений. Будем предполагать, что всегда выполняется равенство:

Построение сеточной области - student2.ru ,

то есть, количество ячеек сеточной области равно количеству MPI‑процессов.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
u0
u1
u2

Рис. 2. Линейная нумерация ячеек сеточной области при n = 3.

Зададим в пространстве целочисленных координат Построение сеточной области - student2.ru линейную нумерацию ячеек сеточной области следующим образом. Пусть ячейка Построение сеточной области - student2.ru имеет целочисленные координаты Построение сеточной области - student2.ru . Тогда ее номер Построение сеточной области - student2.ru вычисляется по формуле:

Построение сеточной области - student2.ru .

На рис. 2 приведен пример такой линейной нумерации при Построение сеточной области - student2.ru . Например, ячейка с номером 19 на рис. 2 имеет целочисленные координаты Построение сеточной области - student2.ru Действительно, Построение сеточной области - student2.ru .

Выразим целочисленные координаты ячейки Построение сеточной области - student2.ru через ее порядковый номер Построение сеточной области - student2.ru . Из получаем

Построение сеточной области - student2.ru ;

Построение сеточной области - student2.ru ;

Построение сеточной области - student2.ru ;

. . . . . .

Таким образом, в общем виде имеем:

Построение сеточной области - student2.ru .

Формула содержит ресурсоемкую операцию возведения в степень. От нее можно избавиться следующим образом. По определению операции mod из получаем

Построение сеточной области - student2.ru [1].

Подставив в вместо Построение сеточной области - student2.ru правую часть этого уравнения, получим

Построение сеточной области - student2.ru

По определению операции mod отсюда следует

Построение сеточной области - student2.ru .

Подставив в вместо Построение сеточной области - student2.ru правую часть уравнения , а вместо Построение сеточной области - student2.ru – правую часть уравнения , получим

Построение сеточной области - student2.ru

Из и для Построение сеточной области - student2.ru по индукции получаем:

Построение сеточной области - student2.ru .

Пусть Построение сеточной области - student2.ru – нулевая вершина куба сеточной области. Пусть Построение сеточной области - student2.ru – нулевая вершина произвольной ячейки Построение сеточной области - student2.ru . Выразим координаты точки y через координаты точки g. Обозначим Построение сеточной области - student2.ru – шаг сетки. Тогда

Построение сеточной области - student2.ru .

Определим в качестве центральной ячейки куба ячейку Построение сеточной области - student2.ru с целочисленными координатами Построение сеточной области - student2.ru , где

Построение сеточной области - student2.ru .

Пусть Построение сеточной области - student2.ru – нулевая вершина центральной ячейки Построение сеточной области - student2.ru . Выразим координаты точки Построение сеточной области - student2.ru через координаты точки g, используя формулу :

Построение сеточной области - student2.ru .

1.4. Пересечение многогранника M с ячейкой 𝛼

Пусть Построение сеточной области - student2.ru – нулевая вершина ячейки 𝛼. Тогда область внутри ячейки 𝛼 (включая границы) задается системой из Построение сеточной области - student2.ru неравенств:

Построение сеточной области - student2.ru

Эта же система в матричной форме:

Построение сеточной области - student2.ru ,

где (для Построение сеточной области - student2.ru )

Построение сеточной области - student2.ru , Построение сеточной области - student2.ru .

Положим

Построение сеточной области - student2.ru , Построение сеточной области - student2.ru .

Тогда пересечение многогранника M с ячейкой 𝛼 задается системой неравенств в матричной форме

Построение сеточной области - student2.ru ,

где Построение сеточной области - student2.ru – расширенная матрица размера Построение сеточной области - student2.ru , Построение сеточной области - student2.ru – расширенный столбец свободных членов. Расширенный столбец Построение сеточной области - student2.ru в соответствии с формулой имеет инвариантную часть b, не зависящую от координат нулевой вершины ячейки 𝛼, и вариативную часть Построение сеточной области - student2.ru , зависящую от координат нулевой вершины ячейки 𝛼. Элементы расширенной матрицы Построение сеточной области - student2.ru не зависят от координат нулевой вершины ячейки 𝛼.

Схема сеточного алгоритма

В данном разделе описывается схема сеточного алгоритма в виде диаграмм деятельности UML. Обозначения, используемые при описании алгоритма, суммированы в приложении 1.

Наши рекомендации