Контрольная работа по "Математике"

Вариант 1

Данные структурного анализа схемы:

Распределение типов элементарных схем по типам ячеек:

где         tj – тип элементарной схемы;        

Yi – тип ячейки (модуля);

Ci – стоимость ячейки (в условных единицах);

1. Запишем математическую модель задачи покрытия в общем виде:

[pic 2]

При условиях:                        [pic 3]

[pic 4]целое для всех j,

где         аij – количество элементов i-ого типа, содержащиеся в ячейке j-ого типа;        

xj – количество ячеек j-ого типа, используемых при покрытии элементов коммутационной схемы;

cj – стоимость ячейки j-ого типа.

Запишем математическую модель задачи покрытия в соответствии с данными своего варианта:

[pic 5]

При условиях:                                [pic 6]

[pic 7],

[pic 8],

[pic 9],

[pic 10],

[pic 11],

[pic 12],

[pic 13],

[pic 14].

1. Решим задачу покрытия с помощью алгоритма Селютина:

1. Вектор [pic 15]

1. Упорядочим ячейки по возрастанию стоимости:

Перепишем математическую модель задачи покрытия в соответствии с перестановками:

[pic 16]

Выбираем ячейку Я1, так как она имеет наименьшую стоимость.  Определяем локально-минимальное число её использования.

Я1 cодержит элемент t2.