<<
>>

Формирование пространства решений

Для удобства изложения будем осуществлять процесс фор­мирования пространства решений на примере.

Пусть покрываемая схема составлена из элементов 3-х ти­пов: E = {e1, e2, e3}. Количественный состав схемы описывается вектором B = {30, 10,21}. Следовательно, имеем 30 элементов первого типа, 10 — второго и 21 — третьего. Набор покрываю­щих ячеек состоит из 5 типов: T = {tι, t2, t3, t4, t5}. Матрица A, описывающая количественный состав ячеек, имеет вид

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

P = ∖∖pij∣∣n?m, где pij— минимальное число элементов типа ei, которое обязательно должно быть покрыто ячейками типа tj, pij ~≥ 0, pij— целое число. При этом для реализации полного покрытия всех элементов, в соответствии с требования­ми матрицы P, необходимо выполнение ограничений:

Для вышеприведенного примера один из возможных вариантов матрицы P имеет вид

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

Сначала строится матрица D = ∖∖dij∣∣n?m. Элемент матрицы dijявляется целым числом, которое определяется как большее целое от pij∙/aijи фактически равно минимальному числу ячеек типа tj∙, необходимых для покрытия pij∙ элементов типа ei.

Затем в пределах каждого j-го столбца матрицы D находит­ся максимальное число djmax, (∀i)[djmax≥ dij∙]. Оно является минимальным числом Xj = djmaxячеек типа tj, гарантированно обеспечивающих покрытие pij элементов типа eι, p2jэлементов типа Є2,...,pnj элементов типа enв соответствии с требованиями матрицы P, причем, кроме элементов типа ei, для которых dij= dj max, остальные типы элементов могут быть покрыты с избытком.

Для рассматриваемого примера матрица Dи покрывающий набор Xимеют вид

Общее число ячеек в покрывающем наборе определится как Nq=

Общее число элементов типа ei, входящеев состав покрыва­ющего набора ячеек определится как

Для нашего примера:

Общее число элементов, входящих в покрывающий набор, N3= = Ni + N2 + N3 = 119. Итак, матрице P, значения элементов которой удовлетворяет ограничениям (4.2), соответствует одно решение. Различные решения получаются путем комбинирова­ния значениями pijматрицы P, удовлетворяющим ограничениям (4.2). Таким образом, матрица P является символьным представ­лением решения задачи покрытия множествами.

B работе пространство решений представляется множеством P-матриц.

Поиск решения сводится к поиску такой матрицы P, т. е. к поиску совокупности таких значений элементов pij∙ матрицы P, которые оптимизируют показатель качества (критерий).

4.3.

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Формирование пространства решений:

  1. Алгоритм формирования тремерной рабочей сцены при использовании нескольких оптико-электронных датчиков
  2. Метод формирования тремерной рабочей сцены при использовании нескольких оптико-электронных датчиков
  3. 3.1. Формирование стратегии развития системы персональных финансов
  4. Глава II. Зависимость между признанием и приведением в исполнение отмененного арбитражного решения и признанием судебного акта, отменяющего такое решение, в зарубежной судебной практике и доктрине
  5. §1.4 Психологические особенности формирования профессионально-личностной компетентности менеджера коммерческой организации
  6. ХАЛЫН АННА ЮРЬЕВНА. ФОРМИРОВАНИЕ СИСТЕМЫ СТРАТЕГИЧЕСКОГО УЧЕТА НА ИННОВАЦИОННЫХ ПРЕДПРИЯТИЯХ. ДИССЕРТАЦИЯ на соискание ученой степени кандидата экономических наук. Ростов-на-Дону - 2014, 2014
  7. § 3. Последствия принятия второго арбитражного решения после отмены первоначального
  8. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ ПО РАСЧЕТУ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ
  9. Аналитические методы решения двумерных задач строительной механики
  10. 4.1. ПОСТАНОВКА И АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ
  11. § 3. Природа полномочий суда места арбитража на отмену арбитражного решения и последствия такой отмены
  12. ПРОБЛЕМЫ РАЗВИТИЯ ГЕОМЕТРИЧЕСКИХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ ТЕХНИЧЕСКОЙ ТЕОРИИ ПЛАСТИНОК
  13. § 2. Надлежащие основания для отмены арбитражного решения. Применение Европейской Конвенции 1961 года
  14. Графическое представление решений для пластинок в виде треугольников
  15. Приближенные методы решения задач технической теории пластинок
  16. § 2. Последствия исключения отмены арбитражного решения из перечня оснований для отказа в его признании и приведении в исполнение