- •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. Упрощенный метод классификации с использованием аналитического подхода формирования информативной подсистемы признаков при наличии обучающей выборки
- •Контрольные вопросы
- •Литература
- •Литература
2. Преобразование задачи с дискретными переменными к задаче с булевыми переменными
Пусть x дискретная переменная, принимающая только целые значения 0,1,2,...,k. Тогда эту переменную можно представить как линейную комбинацию (p+1) булевых переменных y0, y1,...,yp, т.е.:
, (1)
где p-наименьшее целое число, удовлетворяющее условию
(2)
Пример. Рассмотрим следующую задачу целочисленного программирования
целые.
Переменная x1 принимает шесть целых значений: 0,1,2,3,4,5. Для этой переменной k1=5. Возьмем для переменной x1 наименьшее целое число p1 , оно определяется из условия (2)
откуда
Исходя из (1), можно произвести замену переменных:
Переменная x2 принимает четыре целых значения 0,1,2,3.
Следовательно, для
Исходная задача дискретного программирования преобразована к следующей задаче булева программирования :
Если дискретная переменная x принимает произвольные целые дискретные значения c1 , c2 , c3 ,..., ck , то в этом случае соотношения (1) и (2) соответственно преобразуются в следующие соотношения:
Таким образом, всегда можно ограничиться рассмотрением задачи булева программирования вместо задачи дискретного программирования.
3. Преобразование задачи линейного булева программирования к задаче нелинейного булева программирования
Задача вида
(1)
(2)
в числе многих задач комбинаторной оптимизации отнесена к классу “труднорешаемых”. Следовательно, для эффективного решения на вычислительных машинах задач большого размера нужно искать алгоритмические принципы, позволяющие определять оптимальное решение без необходимости явно перечислять элементы множества булева вектора x=(x1,x2, . . . , xn) 2n.
Именно эта идея неявного (в противоположность явному) перечисления решений и лежит в основе методов, предлагаемых и исследуемых в данной книге. Идейная основа последних заключается в преобразовании исходной задачи (1), (2) к следующей задаче булева программирования:
. (3)
При переходе от задачи (1), (2) к задаче (3) возникает вопрос: не теряется ли смысловое содержание исходной задачи при переходе к новой форме. Оказывается, не теряется, это объясняется следующим образом: Максимизируя функцию Ф(х) по булевым переменным x=(x1,x2,..., xn ), практически мы , во-первых, максимизируем числитель выражения (3), т.е. линейную функцию булевых переменных
что соответствует задаче (1). Во-вторых, при максимизации выражения (3), минимизируется знаменатель этого выражения, т.е.
Следовательно, минимизация выражения хотя это процедура не обеспечивает точного выполнения условия (2), а способствует выполнению этого же условия.
В дальнейшем исследовании задачи о рюкзаке (см. п.п. 4.1)будет изложена вычислительная схема получения решения задачи (3) в виде упорядоченного ряда булевых переменных
(4)
но этот ряд булевых переменных может не удовлетворять выполнению ограничения вида (2). После получения упорядоченного ряда (4) каждый очередной элемент этого ряда поочередно слева направо будет вставлен в выражения (2) и таким образом проверено выполнение условия
до максимального числа первых n переменных упорядоченного ряда (4).
Таким образом, переход от исходной задачи линейного булева программирования вида (1), (2) к новой задаче – максимизации фишерского типа функционала вида (3) логичен.