Простейшая
задача размещения
Библиотека тестовых задач
Простейшая
задача размещения
Головная страница
библиотеки
Простейшая задача размещения
Демонстрационная версия программного обеспечения
Для иллюстрации возможностей оптимизационных алгоритмов решения простейшей задачи размещения разработана демонстрационная версия (demo.exe 493 Kb) программного обеспечения. Она работает под управлением операционной системы WINDOWS-95 и выше. При загрузке демонстрационной версии пользователь получает на экран монитора головную панель управления.
Работа пользователя начинается с задания размерности задачи и кода последовательности псевдослучайных чисел. По умолчанию стоит 100 предприятий, 100 потребителей, код 123. Затем пользователь выбирает класс решаемых задач: легкий, трудный, более трудный, невероятно трудный и задает интервалы изменения стоимости открытия предприятий и транспортных расходов. По умолчанию эти величины для легкого класса меняются от 300 до 3000 и от 0 до 300 соответственно. Число возможных поставщиков для каждого потребителя регулируется параметром плотности. По умолчанию все поставщики могут снабжать продукцией любого потребителя (плотность 100 %). Нажатием кнопки Create пользователь создает исходные данные простейшей задачи размещения. Эти данные он может сохранить на диск (кнопка Save), или загрузить предварительно сохраненные данные (кнопка Load).
После того, как исходные данные получены, можно приступать к решению задачи и исследованию поведения алгоритмов. Для этих целей сначала нужно найти точное решение задачи методом ветвей и границ или нижнюю оценку целевой функции методом Лагранжевых релаксаций. Кнопка LB позволяет задать управляющие параметры для каждого из этих методов. С ее помощью пользователь получает доступ к следующей панели управления.
Для метода ветвей и границ имеется возможность задать следующие параметры: Допустимая относительная погрешность, по умолчанию стоит 0; Включить или выключить блок предварительной отбраковки; Порог отбраковки; Максимальное число открываемых предприятий; Максимальное число итераций метода ветвей и границ; Получено ли уже оптимальное решение задачи.
Для метода субградиентной оптимизации имеется возможность задать следующие параметры: Длина начального шага; Скорость уменьшения шага; Число итераций с постоянным шагом; Минимальный размер шага.
Выбрав один из этих методов и установив его параметры, пользователь возвращается к головной панели управления и применяет этот метод (кнопка Start).
Результаты работы метода выдаются на панель где сообщается следующая информация: число выполненных итераций; итерация, на которой получено рекордное решение; число смен рекорда; наилучшее найденное значение целевой функции; относительная погрешность начального решения; время решения задачи.
Эти же характеристики выдаются пользователю и для генетического алгоритма (GA), алгоритма поиска с запретами (TS) и имитации отжига (SA).
Нажав кнопку GA, пользователь получает доступ к управляющим параметрам генетического алгоритма.
Здесь он может задать длительность эволюции, размер популяции, допустимую относительную погрешность, а также способ выбора начальной популяции, тип операторов скрещивания, мутации и отбора родителей. В качестве способа локального улучшения нового решения можно выбрать один из алгоритмов локального поиска: имитация отжига или поиск с запретами. Понятно, что задав нулевое число итераций локального поиска, можно полностью отказаться от локальной перестройки решения.
Кнопка TS головной панели дает пользователю доступ к управляющим параметрам алгоритма поиска с запретами.
Здесь имеется возможность выбрать алгоритм для построения начального решения, задать способ формирования окрестности и правило поиска в ней, определить список запретов, критерии остановки, способы диверсификации и сбора статистической информации для выбора наиболее перспективных направлений поиска.
Кнопка SA головной панели дает пользователю доступ к управляющим параметрам алгоритма имитации отжига.
Здесь имеется возможность задать способ изменения температуры, выбрать алгоритм для построения начального решения, определить правило остановки и числа итераций при фиксированной температуре.
Раздел графики (Graphs) дает возможность увидеть поведение алгоритмов локального поиска с разных точек зрения. Первые три кнопки D(Opt,x), D(0,x), D(First,x) показывают изменения расстояния Хемминга от текущего решения до оптимального, нулевого и начального решений. Последняя кнопка Error дает возможность увидеть изменения относительной погрешности с ростом числа итераций.
Выход из системы осуществляется нажатием кнопки Exit.
