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

Данная программа предназначена для решения задач оптимизации распределения ресурсов при неполной информации с применением методов имитационного моделирования.

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

Кроме того, в программе реализовано:

1. Сохранение и загрузка задач во внешний файл.
2. Каждый эффект от вложения определенного количества ресурса в определенный пункт может быть как статическим так и случайной величиной, лежащей в определенном диапазоне и распределенной по выбранному закону распределения.
3. Использование 5 различных законов распределения:

• Равномерный
• Нормальный
• Экспоненциальный
• Вид возрастающего треугольника
• Вид убывающего треугольника

1. Тестирование датчиков случайных чисел на тождественность теоретического закона ‑ эмпирическому, по критерию Колмогорова
2. Проведение имитационного моделирования задачи с неполной информацией, при этом реализован вывод следующих данных:

• График плотности распределения значений эффективности за последний этап итераций
• График функции распределения значений эффективности за последний этап итераций
• Оценка соответствия полученного распределения эффективностей нормальному закону,  по критерию Колмогорова
• Вывод среднего значения эффективности за последний этап итераций
• Вывод среднеквадратического отклонения от среднего за последний этап итераций
• Вывод моды за последний этап итераций
• Построение доверительного интервала
• Вычисление вероятности попадания в доверительный интервал
• Вывод уникальных,  перспективных вариантов решения задачи, попадающих в доверительный интервал
• Построение графика стремления к устойчивому состоянию и указания 5% и 2% коридора
• Проверка неравенства Чебышева и вычисления необходимого числа итераций от допустимой ошибки

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

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

Все эти операции дублируются на панели инструментов, а так же в главном меню.

Создание задачи

Для создания новой задачи нужно воспользоваться подпунктом Создать задачу в меню Файл, кнопкой Создать на панели инструментов, или ссылок Создать задачу на стартовой странице. В результате, откроется окно Мастера создания новой задачи(Рис. 1).

Рис. 1. Окно мастера создания новой задачи

В окне мастера необходимо указать имя файла для сохранения задачи, а также количество пунктов и максимальное количество ресурсов. При указании последних двух параметров следует учитывать, что пункты назначения изменяются от 1 до 100, а количество ресурсов изменяются от 1 до 300.

После нажатия кнопки Готово в рабочей области вместо стартовой страницы отобразится таблица с исходными данными, по умолчанию для новой задачи. В столбцах таблицы содержатся пункты назначения, в строках ‑ количество ресурсов, на их пересечении ‑ значение эффективности от вложения соответствующего количества ресурсов в данный пункт.

Рис. 2. Таблица исходных данных задачи по умолчанию

Открытие сохраненных задач

Для открытия ранее созданной задачи, необходимо воспользоваться пунктом Файл | Открыть, соответствующей кнопкой на панели инструментов, или ссылкой на стартовой странице.

Кроме того, в меню Файл в подменю Открывавшиеся файлы, а также на стартовой странице в разделе Открыть… содержится список из четырех последних открывавшихся задач.

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

Работа с задачами

После открытия существующей или создания новой задачи, исходные данные становятся доступными для редактирования(рис. 3).

Рис. 3. Фрагмент рабочей области с исходными данными

По горизонтали в столбцах содержатся пункты назначения, а по вертикали, в строках ‑ количество ресурсов. На пересечении строк и столбцов располагаются ячейки, в которых указывается значение эффективности. Чтобы редактировать информацию об эффективности нужно дважды щелкнуть по нужной ячейке, после этого в области задач, в правой части экрана, откроется область Исходных данных. В ней редактируется значение эффективностей (рис. 4)

Рис. 4 Область редактирования исходных данных

При изменении положения двух переключателей Эффективность постоянная и Случайная указывается тип эффективности – постоянная или случайная. Если выбрана статичная эффективность, то для редактирования доступно ее значение.

Если же выбрано случайное изменение эффективности, то для редактирования становится доступным диапазон, в котором должны лежать значение и закон распределения. В виде диапазона могут быть указаны два любых дробных неотрицательных и не равных друг другу числа. В выплывающем списке законов распределения выбирается один из возможных законов (рис. 5):

Рис. 5. Выплывающее меню со списком законов распределения

При изменении информации в области редактирования исходных данных, новые данные автоматически отображаются в рабочей области. В каждой ячейке отображается следующая информация.

 

Текущее значение эффективности à		<— Символическое изображение закона распределения
		<— Диапазон  случайной величины

 

Если все значения эффективностей статические, то можно перейти непосредственно к решению задачи. Однако, если в исходных данных имеется хотя бы одно случайное значение, то перед решением нужно сгенерировать случайные значения эффективностей, что осуществляется соответствующей кнопкой на панели инструментов. При этом новое ,сгенерированное значение отображается в верхнем левом углу.

Решение задачи

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

Задача в зависимости от объемов исходных данных и мощности компьютера может решаться от нескольких секунд до нескольких десятков минут. После решения задачи подробное решение отображается в области исходных данных в виде дополнительных колонок. В области задач при этом появляется область с кратким решением, то есть с набором вариантов распределения ресурсов и значений эффективности (рис. 6).

Рис. 6. Решение задачи в виде набора вариантов распределения ресурсов по пунктам назначения

В области исходных данных добавляются столбцы со значениями эффективностей и вариантами распределения ресурсов между 1..m-1-пунктом и m-пунктом (рис.7).

Рис. 7. Подробное решение задачи

Каждая ячейка в подробном решении содержит следующую информацию:

 

Значения эффективности при распределении ресурсов в соответствии с одним из вариантов справа		Набор вариантов распределения. Первое число – количество ресурсов на пункты 1..m-1 Второе – ресурсов на m-пункт

Имитационное моделирование и просмотр результатов

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

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

Рис. 8. Настройки имитационного моделирования в области задач

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

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

Запускается моделирование щелчком на кнопке Запустить в области задач. В ходе расчетов прогресс будет показан символически на индикаторе процесса в области задач. После произведения расчетов в рабочей области отобразится информация подобная рисунку 9.

Рис. 9. Главное окно программы с результатами имитационного моделирования

Опишем результаты моделирования более подробно.

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

В верхней части окна зеленой полосой отображается график оценки плотности вероятности эффективностей. Красной полосой отображается график нормального закона для данного диапазона разброса эффективностей. Пара синих полос ограничивают доверительный интервал на плотности вероятности эффективностей (рис. 10).

Рис. 10. График плотности вероятности эффективностей

Под графиком располагаются две кнопки F(W) и P(W) для переключения просмотра функции распределения эффективностей и плотности распределения. На графике функции распределения также отображается красной линией положение максимального расхождения между функциями распределения теоретического, нормального закона и функцией распределения эффективности.

В нижней части окна отображается график зависимости  от N, а также 2% и 5% коридор отклонений (рис 11).

Рис. 11. График зависимости Wср.ср. от N

Также в нижней части окна отведена область для проверки неравенства Чебышева. На графике отображается зависимость количества итераций(N) от вероятности (b) того, что математическое ожидание выйдет за предел заданной точности (e).

После проведения моделирования в области задач отобразится список уникальных вариантов распределения ресурсов, то есть тех решений, которые попали в доверительный интервал (рис. 12).

Рис. 12. Список перспективных решений, попавших в доверительный интервал

В завершении отмечу, что приложение написано в среде Delphi 7, для хранения данных использовалась СУБД Microsoft Access.

Сам проект представлялся в Новосибирском государственном техническом университете на конференции «Наука. Технологии. Инновации.» в 2007 году и был отмечен дипломом I степени.