49717 (Автоматизация системного проектирования)

СОДЕРЖАНИЕ

Введение

Задание 1.Автоматизация системного проектирования

1.1 Решить задачу о назначении (Венгерский метод)

1.2 Решить задачу линейного программирования, используя табличный симплексный метод

Задание 2. Имитационное моделирование. Сети Петри

2.1 Построить имитационную модель гибкого производственного модуля

Задание 3. Методы постановки задач и алгоритмы автоматизированного проектирования средств вычислительной техники

3.1 Выбрать схему электрическую принципиальную

3.2 Провести формализацию и, используя два алгоритма (последовательно-групповой и алгоритм Штейнберга), провести размещение микросхем на печатной плате

3.3 Проанализировать полученные результаты и сделать выводы об эффективности использованных алгоритмов

Литература

Введение

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

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

Цель работы – изучение материала, которые направлены на закрепление и углубление теоретических знаний, формирование практических навыков методов и алгоритмов разработки вычислительных средств относительно заданий автоматизации проектирования.

Задание 1.

Автоматизация системного проектирования

1.1 Решить задачу о назначении (Венгерский метод)

ГПМ установки НЭ на ПП состоит из 4-х ед. автоматического технологического оборудования, каждая из которых может устанавливать на плату 4 типа НЭ с разной эффективностью.

1 АТО устанавливает 1 тип НЭ с эффективностью 3, 2 тип – с эффективностью 2, 3 тип - с эффективностью 6, 4 тип с эффективностью 7.

2 АТО устанавливает 1 тип НЭ с эффективностью 2, 2 тип – с эффективностью 3, 3 тип - с эффективностью 4, 4 тип с эффективностью 5.

3 АТО устанавливает 1 тип НЭ с эффективностью 1, 2 тип – с эффективностью 6, 3 тип - с эффективностью 2, 4 тип с эффективностью 5.

4 АТО устанавливает 1 тип НЭ с эффективностью 2, 2 тип – с эффективностью 4, 3 тип - с эффективностью 4, 4 тип с эффективностью 10.

Распределить типы НЭ по АТО по принципу «одно АТО – один тип» таким образом, чтобы суммарная эффективность была максимальна.

Решение:

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

Составим матрицу задания:

Предварительный этап.

Находим максимальный элемент первого столбца – 3. Отнимаем из него все элементы этого столбца. Аналогично для получения второго, третьего и четвертого столбцов новой матрицы отнимаем все элементы этих столбцов от 6, 6 и 10 соответственно. Получим матрицу С^'(C^'~C).

Т.к. в каждом ряду С^' кроме второго есть нуль, поэтому отнимаем лишь минимальный элемент второго ряда (1) от всех элементов этого ряда и получаем матрицу З_{0 ~} С^' и на этом процесс приведения матрицы заканчивается.

(+) + +

Далее ищем и отмечаем знаком '*' независимые нули в З_0, начиная с первого ряда.

Первая итерация. Первый этап

Выделяем знаком «+» первый, второй и четвертый столбец матрицы З_о, которые содержат 0*.

Пересмотрим невыделенный третий столбец, находим в нем невыделенный нуль IЗ₄₃=0, отмечаем его штрихом и выделяем знаком «+» первый ряд.

Ищем минимальный элемент в невыделенной части матрицы З_о (т.е. элементы, которые находятся в столбцах и рядах, не обозначенных знаком «+»).

Вторая итерация. Первый этап

Просматривая все невыделенные элементы, находим среди них невыделенный нуль IЗ₁₂=0, отмечаем его знаком штрих и переходим ко второму этапу.

+ +

Второй этап. Начиная с элемента IЗ₁₂=0^, строим цепь двигаясь от него по столбцу. Находим нуль со звездочкой IЗ₁₁=0*, далее двигаясь по первому ряду и находим 0 (IЗ₁₃).

Таким образом, цепь построенная 0'₂₁-0^*_11-0'_13. Заменяем штрих на звездочку и сокращаем звездочки над парными элементами цепи, а так же все знаки выделения столбцов и рядов. После этой итерации количество независимых нулей (0*) стало равняться 4 (размерности матрицы З) и поэтому алгоритм заканчивает работу.

Искомые элементы назначения отвечают позициям независимых нулей матрицы З_з (т.е. )*0.

Соответствующее значение целевой функции:

F = C12 + C23 + C31 + C44 = 2 + 6 + 6 + 10 = 24.

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

табличный симплексный метод

Предприятию необходимо выпустить 2 вида изделий (Р1; Р2). Есть 3 вида станков (Т1; Т2; Т3), каждый из которых может обрабатывать изделия всех видов.

Продолжительность обработки

на станке 1-го типа изделий 1-го типа 4 единицы

на станке 2-го типа изделий 1-го типа 1 единица

на станке 3-го типа изделий 1-го типа 1 единица

на станке 1-го типа изделий 2-го типа 0 единиц

на станке 2-го типа изделий 2-го типа 2 единицы

на станке 3-го типа изделий 2-го типа 4 единицы

Доход от реализации изделия первого типа составляет 6 единиц, второго типа – 6 единиц.

Запас мощности (рабочее время станка) 1-о типа – 20 единиц, 2-го типа 37 единиц, 3-го типа – 40 единиц.

Составить такой план загрузки станков, при котором себестоимость выпуска продукции будет минимальной.

Решение

Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом. Симплекс метод принадлежит к числу аналитических методов решения основной задачи линейного программирования.

Составим линейные уравнения для решения задачи.

F (x) = 6х₁ + 6 х₂ →max – целевая функция.

где х₁ – количество изделий Р1;

х₂ - количество изделий Р2.

Уравнения ограничений :

4 х₁ ≤ 20;

х₁ + 2 х₂ ≤ 37;

х₁ + 4 х₂ ≤ 40.

Найдем наибольшее значение линейной функции

F = 6 x₁ + 6 x₂

при следующих ограничениях

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

Свободные члены системы ограничений положительны. Выполнено одно из необходимых условий применения симплекс метода.

К левой части неравенства 1 системы ограничений прибавляем неотрицательную переменную x₃ , тем самым мы преобразуем неравенство 1 в равенство.

К левой части неравенства 2 системы ограничений прибавляем неотрицательную переменную x₄ , тем самым мы преобразуем неравенство 2 в равенство.

К левой части неравенства 3 системы ограничений прибавляем неотрицательную переменную x₅ , тем самым мы преобразуем неравенство 3 в равенство.

Введенные нами переменные имеют вполне конкретный физический смысл, непосредственно связанный с условием нашей задачи.

4 x₁ + x₃ = 20

x₁ + 2 x₂ + x₄ = 37

x₁ + 4 x₂ + x₅ = 40

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

Определимся с начальным опорным решением. Наличие единичного базиса в системе ограничений позволяет легко найти начальное опорное решение. Рассмотрим подробнее.

Переменная x₃ входит в уравнение 1 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е x₃ - базисная переменная.

Переменная x₄ входит в уравнение 2 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е x₄ - базисная переменная.