- •50 Часов — лекционных занятий;
- •25 Часов — практических занятий;
- •25 Часов — лабораторных занятий. Содержание
- •Лекция 1. Общие вопросы теории моделирования (2 часа) План
- •2. Роль и место моделирования в исследованиях систем
- •3. Классификация моделей
- •4. Моделирование в процессах познания и управления
- •5. Классификация объектов моделирования
- •6. Основные этапы моделирования
- •7. Этапы моделирования объектов (процессов, явлений)
- •Контрольные вопросы
- •Литература
- •Лекция 2. Технология моделирования (2 часа) План
- •2. Подготовка исходных данных
- •3. Разработка математической модели
- •4. Выбор метода моделирования
- •2. Проверка адекватности и корректировка модели
- •3. Планирование экспериментов с моделью
- •4. Анализ результатов моделирования
- •2. Сведения об объекте
- •3. Априорная информация
- •4. Апостериорная информация
- •1. Постановка задачи идентификации.
- •2. Трудности идентификации
- •1. Постановка задачи идентификации.
- •Следовательно модельный оператор f должен быть таким, чтобы:
- •2. Трудности идентификации
- •1. Идентификация структуры и параметров объекта
- •2. Классификация методов идентификации
- •1. Идентификация структуры и параметров объекта
- •2. Классификация методов идентификации
- •2. Ранжирование входов и выходов объекта (Метод экспертных оценок)
- •Метод непосредственного ранжирования;
- •Метод парных сравнений.
- •3. Метод непосредственного ранжирования
- •2. Определение рационального числа входов и выходов объекта, учитываемых в модели
- •3. Определение характера связи между входом и выходом модели объекта
- •1. Потоки заявок
- •2. Марковские модели
- •1. Потоки заявок
- •2. Марковские модели
- •2. Характеристики вычислительных систем как сложных систем массового обслуживания
- •3. Методы приближённой оценки характеристик вычислительных систем
- •1. Нестационарные режимы функционирования вычислительных систем
- •2. Характеристики вычислительных систем как стохастических сетей
- •1. Нестационарные режимы функционирования вычислительных систем
- •2. Характеристики вычислительных систем как стохастических сетей
- •2. Обобщенные алгоритмы имитационного моделирования
- •2. Метод повторных экспериментов
- •3. Методы генерации случайных величин и последовательностей
- •Контрольные вопросы
- •II. Модель в - для задачи максимизации
- •2. Преобразование задачи с дискретными переменными к задаче с булевыми переменными
- •3. Преобразование задачи линейного булева программирования к задаче нелинейного булева программирования
- •Контрольные вопросы
- •2. Модель задачи автоматической классификации
- •3. Задача об оптимизации размещения букв алфавита на клавиатуре эвм
- •2. Проверка адекватности математической модели
- •3. Алгоритм оптимального управления работы насосной станции
- •Контрольные вопросы
- •2. Аналитический подход к формированию информативной подсистемы признаков в задаче распознавания
- •3. Упрощенный метод классификации с использованием аналитического подхода формирования информативной подсистемы признаков при наличии обучающей выборки
- •Контрольные вопросы
- •Литература
- •Литература
Контрольные вопросы
Измерямые характистики ВС.
Основные формулы для расчета выходных характеристик ВС.
Методика пострения гистограммы и ее использование для иследования ВС.
Основная идея метода повторных экспериментов.
Что понимается под датчиком случайных величин?
Какие методы (алгоритмы, программы) генерации последовательностей случайных величин вы знаете?
Примеры использования датчиков случайных чисел.
Литература
Лекция 14. МОДЕЛИ ЛИНЕЙНОГО БУЛЕВА ПРОГРАММИРОВАНИЯ (2 часа)
План
1. Модели линейной дискретной оптимизации с булевыми переменными
2. Преобразование задачи с дискретными переменными к задаче с булевыми переменными
3. Преобразование задачи линейного булева программирования к задаче нелинейного булева программирования
1. Модели линейной дискретной оптимизации с булевыми переменными
Задача оптимизации линейной целевой функции с булевыми переменными и линейными ограничениями является одной из самых распространенных моделей дискретного программирования. Комбинаторные задачи с булевыми переменными, принимающими значения 0 или 1, встречаются при решении многих практических проблем из экономики, проектирования, управления и других областей.
Задача оптимизации (минимизации или максимизации) линейной целевой функции с булевыми переменными и линейными ограничениями в общем виде описывается с помощью одной из следующих моделей линейного булева программирования:
I. Модель А - для задачи минимизации
(1)
(2)
II. Модель в - для задачи максимизации
(3)
(4)
т.е. требуется минимизировать или максимизировать линейную целевую функцию q(x) по булевым переменным xj{0,1} при выполнении условия, задаваемого системой линейных неравенств вида (2) или (4).
Проблема отыскания решения задачи (1), (2) или (3), (4) может в принципе решаться с применением метода полного перебора, суть которого заключается в переборе всех булевых векторов заданной длины, проверке для каждого вектора выполнения линейных ограничений, вычислении значений целевой функции для допустимых векторов и выборе из них минимального или максимального значения целевой функции. Однако решение, полученное методом полного перебора, связано с большим объемом вычислений, который неосуществим при больших размерностях задачи даже на сверхпроизводительных ЭВМ. Так как каждая из n компонент независимо от других может принимать два значения 0 или 1, поэтому общее число булевых векторов длины n равно 2n.
Это величина и характеризует сложность алгоритма полного перебора. В связи с тем, что для большинства задач дискретной оптимизации полный перебор неосуществим, были разработаны различные методы неявного перебора, которые обеспечивают нахождение точного решения без пересмотра всех булевых векторов. Такими являются различные варианты метода отсечений, метода ветвей и границ, метода динамического программирования. Но опыт применения этих методов при решении реальных задач с достаточно большим числом переменных показал, что многие задачи линейного программирования с булевыми переменными еще являются нерешаемыми на ЭВМ из-за нехватки машинного времени. Следовательно, с ростом размера задачи n она становится "труднорешаемой", т.е. практически неразрешимой.
Задача (1), (2) или (3), (4) в числе многих задач комбинаторной оптимизации отнесена к классу "труднорешаемых" или, NP (nо polynomial) - полных задач. Причина заключается в том, что алгоритма, решающего поставленную задачу за время, ограниченное полиномам от "размера задачи", в настоящее время нет.
В связи с этим исследования, направленные на разработку новых эффективных или полиномиальных методов решения задач линейного программирования с булевыми переменными, являются, несомненно, актуальными.
Сначала рассмотрим широко распространенные практические задачи, описываемые моделями линейного программирования с булевыми переменными.