АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

ЗАДАЧА ПОКРЫТИЯ СХЕМ НАБОРОМ КОНСТРУКТИВНЫХ МОДУЛЕЙ

Читайте также:
  1. VI. Общая задача чистого разума
  2. Вопрос 2 Проверка и оценка в задачах со случайными процессами на примере решения задач экозащиты, безопасности и риска.
  3. Глава 10 Системный подход к задачам управления. Управленческие решения
  4. ГЛАВА 2.1. ЗАЩИТА ИННОВАЦИЙ КАК ЗАДАЧА УПРАВЛЕНИЯ ИННОВАЦИОННЫМИ ПРОЦЕССАМИ
  5. Глава 4. Математические основы оптимального управления в экономических задачах массового обслуживания
  6. Двойственная задача линейного программирования.
  7. Дефицит государственного бюджета и государственный долг. Источники и способы покрытия дефицита государственного бюджета и государственного долга
  8. Доклад о задачах власти Советов
  9. Доклад об экономическом положении рабочих Петрограда и задачах рабочего класса на заседании рабочей секции Петроградского совета рабочих и солдатских депутатов
  10. ДОРОГИ С ТВЕРДЫМИ ПОКРЫТИЯМИ
  11. Задача 1
  12. Задача 1

В результате решения задачи покрытия каждый элемент схемы привязывается к некоторому конструктивному модулю из набора Q={Q1, Q2, …,Qm}.

Математическая постановка задачи покрытия зависит от типа конструктивных модулей набора. Различают 3 типа конструктивных модулей:

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

Например:

2) Тоже что и предыдущий тип, однако в одном конструктивном модуле могут содержаться разнотипные логические элементы.

Модули 1-го и 2-го типов называются модулями с несвязанными элементами.

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

Рассмотрим математическую постановку задачи покрытия схемы конструктивными модулями с несвязанными элементами (1-го и 2-го типов).

Обозначим через bi количество логических элементов ti типа, содержащихся в функционально-логической схеме (ФЛС). При таком подходе состав ФЛС может быть описан матрицей-столбцом: B=||bi||n, где n – число типов логических элементов схемы, bi – число логических элементов ti типа в ФЛС. Будем считать, что каждый тип конструктивного модуля Qj в общем случае содержит несколько типов ti базовых элементов, а весь набор конструктивных модулей Q может быть описан матрицей A=||aij||nxm, где aij – количество базовых логических элементов типа ti в конструктивном модуле типа Qj ( ).

Пример.

      Q1 Q2 Q3
    t1
A = t2
    t3
    t4

В качестве критерия оптимизации будем использовать минимум стоимости покрытия. Обозначим cj стоимость конструктивного модуля Qj.

Пусть для покрытия ФЛС необходимо выделить yj конструктивных модулей Qj, тогда в качестве целевой функции можно взять функцию вида:

.

Будем считать, что каждый тип базового логического элемента схемы может быть реализован как базовый логический элемент того же набора, так и БЛЭ другого типа набора. Например:



Обозначим через xki количество логических элементов типа tk, которое идет на покрытие логических элементов схемы типа ti. Возможность замены БЛЭ типа tk на БЛЭ типа ti будем описывать матрицей W=||wki||nxn,

Очевидно, что xki>0 если wki=1.

Учитывая введенные обозначения, задачу покрытия можно сформулировать следующим образом: если yj количество требуемых конструктивных модулей типа Qj, а в каждом Qj конструктивном модуле содержится aij элементов типа ti, то определяет количество логических элементов типа ti, содержащихся во всем выделенном для покрытия ФЛС наборе конструктивных модулей.

Очевидно, что для покрытия всей ФЛС необходимо выполнение следующего условия:

,

где второе слагаемое – количество логических элементов других типов, которые идут в покрытии на реализацию логических элементов типа ti; последнее слагаемое – количество логических элементов типа ti, которые идут на реализацию логических элементов других типов.

Т. о., ставится задача отыскания таких значений yj и xki, удовлетворяющих (**), чтобы обеспечивался минимум целевой функции (*) – стоимости покрытия. На практике используются приближенные методы, опирающиеся на специфику используемых конструктивных модулей. Если имеем дело с несвязанными элементами конструктивного модуля, то здесь в результате определения требуемого числа модулей не осуществляется привязка логических элементов схемы к конструктивным модулям, отсюда появляется возможность оптимизации по другому критерию, в частности по критерию минимума межблочных связей.

Пример Q={Q1, Q2, Q3}, t={t1, t2, t3, t4} приведен нами выше. Требуется покрыть ФЛС, описываемую вектором B={5, 4, 1, 1}, заданным набором конструктивных модулей.

Блок-схема алгоритма определения требуемого числа конструктивных модулей по критерию минимума стоимости покрытия приведена на рисунке.

 

 

Требуемое число корпусов модуля j-го типа определяется из выражения:

‡агрузка...

(1)

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

Так как a31=0 и a41=0, то в качестве коэффициента

Полагаем, что j=2 и вычисляем

, и следовательно

j=3

Переходим к :

, (остальные bi=0)

Т.о. имеем , , , .

Эти данные подставляем в выражение (1) и определяем:

,

,

.

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


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |


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