» ГЛАВНАЯ > К содержанию номера
 » Все публикации автора

Журнал научных публикаций
«Наука через призму времени»

Октябрь, 2017 / Международный научный журнал
«Наука через призму времени» №7 2017

Автор: Амирова Лейла Икрам кызы, кандидат физико-математических наук
Рубрика: Физико-математические науки
Название статьи: Применение редукции в одной задаче принятия решения

Статья просмотрена: 965 раз

УДК 519.8

ПРИМЕНЕНИЕ РЕДУКЦИИ В ОДНОЙ ЗАДАЧЕ ПРИНЯТИЯ РЕШЕНИЯ

Гамидов Рафаэль

Доцент, кандидат физико-математических наук

Муталлимов Муталлим

Доктор технических наук

Амирова Лейла

Кандидат физико-математических наук

Бакинский Государственный Университет, Баку, Азербайджан

 

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

Ключевые слова: Множество Парето, методы декомпозиции, задачи большой размерности.

 

При решении задач с большим числом переменных, используют различные методы декомпозиции [1,2] и редукции [3,4]. Однако во многих задачах принятия решения практическое осуществление применения этих методов не всегда даёт ожидаемый эффект. Одна из таких задач рассматривается в настоящей работе. Матрица условий задачи является M–матрицей [5]. В отличие от [5] здесь не требуется расположение ненулевых элементов по близости диагонали М – матрицы. Такая матрица используется при постановке различных задач экономического и технического характера [6, 7]. В [7] она появляется в модели оптимизации нефтедобычи в статическом режиме при применении модели типа Леонтьева при анализе экономических задач и в других задач практического характера. В предлагаемой работе исследуется возможность исключить части переменных до момента организации процесса принятия решения. Для двухкритериальных задач дробно – линейного программирования с М – матрицей условий показана схема реализации этой возможности. Затем на числовом примере иллюстрируется методика редуцирования. Отметим, что структура задачи, которая получается в результате редукции остаётся неизменной. А это очень важно, так как источником организации эффективных процедур принятия решения во многих задачах является ее специальная структура [7]. Решаемый числовой пример позволяет в определенной степени оценить достоинства процесса редукции с практической точки зрения.

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

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

Множество, где требуется организовать поиск решения поставленной задачи, задается следующим образом:

 (1)

где  является М - матрицей.

Будем использовать следующие обозначения. Матрицу называют неотрицательной матрицей , если при любом i и j  Матрица называется матрицей, если при и

Пусть - требуемое решение, которого следует выбирать из множества

Рассмотрим множество  и множество

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

 

2. Алгоритм редукции

Условию (1) можно представить в следующей форме:

 (2)

где - единичная матрица.

Пусть - диагональная матрица с диагональными элементами , если , при . Следуя [8] назовем P характеристической матрицей множества G. Тогда будет характеристической матрицей множества . Множество будет множеством решения системы (3),(4):

 (3)

 (4)

Из (3) имеем

Отсюда и из (4) имеем

Тогда

 (5)

Очевидно, что

Следовательно, в (5) не участвуют переменные т.е. мы исключили переменные из дальнейшего процесса поиска решения.

Нетрудно заметить, что структура ограничения (1) сохраняется и в (5).

3. Применение алгоритма редукции

Рассматривается следующая задача:

 (6)

Предполагается, что а)

Задача (6) является частным случаем задачи, которая изучается в [9]. Там и приводится одна схема организации процесса принятия решения. Все результаты, полученные в [9] остаются в силе и для задачи (6), где поиск решения осуществляется среди эффективных оценок рассматриваемой задачи.

Рассмотрим многокритериальную задачу

 (7)

Множества Парето оценок задачи (6), (7) обозначим через и соответственно. Тогда нетрудно доказать следующую лемму

Лемма.

Множество находится из решения следующей многопараметрической задачи линейного программирования [10].

 (8)

Определим множество

И пусть

Теорема. Задачу (6) можно редуцировать относительно множества .

Доказательство. Достаточно доказать, что задачу (8) можно редуцировать относительно G. Задачу (8) можно решать с помощью итерационного процесса из [10], который обладает свойством: переменные  становятся базисными переменными в найденном оптимальном базисе.

4. Числовой пример

Рассматриваемый пример имеет следующую форму записи:

          (9)

Матрица задачи (9) является M -матрицей. Если перейти к матричной форме записи, то имеем

 

Имеют место неравенства , которые обеспечивают ограниченность множества X. . Отсюда следует выполнение условия а) и существование и не отрицательность матрицы _.

Теперь покажем процесс реализации редукции на примере. Легко можно проверить, что . Тогда, для любой точки  имеют места равенства

С помощью этих равенств исключаем переменные x₁ и x₂. После исключения x₁ и x₂ все остальные коэффициенты целевой функции получают неотрицательные приращения [7], т.е. имеется возможность продолжить процесс редукции, если . Как будет видно, для вновь полученной задачи  .

Сначала находим

и вычисляем коэффициент x₃ в целевой функции после исключения переменных x₁ и x₂:

Отсюда имеем

Нет необходимости проводить аналогичную проверку для c₂. Так как коэффициент и он тоже получает положительное приращение после исключения x₁ и x₂ т.е. . Далее, имеем

Тогда получаем, что и исключаем x₃ из дальнейшего рассмотрения. Находим

и вычисляем

Тогда

 (10)

Аналогичным образом вычисляем

Тогда

 (11)

Нетрудно заметить, что , т.е. процесс редукции задачи (9) завершается.

Теперь формируем условия редуцированной задачи:

  (12)

Задача (10), (11), (12) будет запись редуцированной задачей для задачи (9). Новая задача полностью сохраняет прежнюю структуру исходной задачи (9). С помощью характеристической матрицы задача (12) будет иметь следующий вид:

где P- характеристическая матрица множества .

5. Частные случаи

Случай 1. . Тогда задача (6) приобретает вид

 (13)

и согласно [11] , она решается следующим образом. Строится итерационный процесс

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

В случае 1 метод редуцирования становится методом решения задачи (1), (2).

Случай 2. . Тогда имеем задачу

Оптимальное решение  задачи является эффективным решением задачи

Тогда согласно [10], существует такое , что будет оптимальным решением задачи

 (14)

при

В [12] предложена простая конечная итеративная процедура, которая определяет .

Если , то оптимальное решение (14) одновременно будет и оптимальным решением (13).

Случай 3. , тогда имеем задачу

Случай 4 сводится к случаю 3.

Случай 5.  и этот случай легко сводится к случаю 3.

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

 

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

1. Лэсдон Л.С. Оптимизация больших систем. ¬М., Наука, 1975. 431 с.
2. Цурков В.И. Декомпозиция в задачах большой размерности. М., Наука, 1981, 352 с.
3. Цурков В.И. Динамические задачи большой размерности. М., Наука, 1988, 288 с.
4. Davison E.J. Method for simplifying linear dynamic systems // IEEE Trans. Autom. Control, 1966, V.11, № 1, pp. 93-101.
5. Yu-Qin Bai, Ting-Zhu Huang. Convergence of two-stage multisplitting method with ssor multisplitting for linear systems with H-matrices, Appl. Comput. Math., V.11, N.3, 2012, pp.358-367.
6. Peter Benner, Lihong Feng. Model order reduction for coupled problems (Survey), Appl. Comput. Math., 2015, V.14, N.1, pp. 3-22
7. Мееров М.В., Литвак Б.Л., Оптимизация систем многосвязного управления. М., Наука. 1972, 344 с.
8. Мееров М.В, Берщанский Я.М. Решение динамических задач оптимизации для линейных многосвязных систем. Препринт, М., Институт проблем управления, 1975, 68 c.
9. Гамидов Р.Г., Аллахвердиева Н.К. Принятие решение в двухкритериальной задаче дробно-линейного программирования. Proceeding of the Institute of Applied Mathematics, 2015, Vol 4, № 1, pp.85-95.
10. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.,Наука, 1982, 256 с.
11. Беленький В.З. О задачах математического программирования, обладающих минимальной точкой. Докл. АН СССР, 1968, т.183, № 1, с. 15-17.
12. Гамидов Р.Г. Об одном алгоритме решения задач дробно–линейного программирования М., ВИНИТИ, 1986, №2156-В 86, 14 с.



Комментарии:

Фамилия Имя Отчество:
Комментарий: