Содержание к диссертации
Введение
1. Моделирование структур в задачах назначения 13
1.1. Постановка задачи о назначении как задачи структурного моделирования 13
1.2. Анализ частных случаев формализованных постановок задач 22
1.2.1. Транспортная задача 22
1.2.2. Задача о размещении и раскрое 27
1.2.3. Двухуровневая задача о назначении 29
1.2.4. Конечные автоматы 31
1.3. Методы решения задач 36
1.3.1. Комбинаторные методы 37
1.3.2. Методы линеаризации 49
1.3.3. Генетические алгоритмы 53
1.4. Выводы и постановка задачи исследования 59
2. Задача структурного моделирования 61
2.1. Постановка задачи в общем виде 61
2.2. Интерпретация задачи на графах 63
2.3. Разработка способов формализации ограничений 64
2.4. Квадратичная задача о назначении как частный случай 67
3. Разработка генетического алгоритма для решения задачи структурного моделирования 73
3.1. Математическая интерпретация основных понятий и этапов генетического алгоритма 73
3.2. Синтез и исследование алгоритма решения квадратичной задачи о назначениях ...77
3.3. Преимущества и недостатки метода 84
4. Примеры реализации задач структурного моделирования 86
4.1. Задача о раскрое с произвольным видом границ 86
4.2. Задача составления расписания занятий 90
Заключение 99
Литература 100
Приложение 1 109
Приложение 2 116
- Анализ частных случаев формализованных постановок задач
- Разработка способов формализации ограничений
- Синтез и исследование алгоритма решения квадратичной задачи о назначениях
- Задача о раскрое с произвольным видом границ
Введение к работе
Во всех областях хозяйственной и научной деятельности значительную роль играет класс задач о назначении. К ним относятся задачи планирования, распределения, расписания, транспортные задачи, задачи о раскрое и другие статические задачи выбора. В настоящее время известно множество математических описаний постановок задач, которым ставится в соответствие своя совокупность методов решения, например, симплекс-метод для линейных задач, метод ветвей и границ для различных дискретных задач, динамическое программирование, метод потенциалов для транспортных задач и другие. Однако формализация многих практически важных задач не соответствуют классической постановке, например задача о раскрое с нелинейным видом границ, поэтому применение известных методов решения становится затруднительным. Особую сложность вызывает случай высокой размерности задач, где алгоритмы решения сводятся к NP-полному перебору. Кроме того, определенные трудности возникают при интерпретации практической задачи на множество известных классических постановок.
С точки зрения теоретико-множественного отношения все задачи о назначении обобщаются структурным аспектом, выражающимся в наличии отношений на множествах. Это определяет возможность построения обобщенного математического описания класса задач о назначениях в терминах теоретико-множественных отношений. Такой подход позволяет формализовать процессы построения критериев и ограничений произвольной задачи из класса задач о назначении, что существенно унифицирует и облегчает процедуру создания математической модели задачи любой сложности. Более того, построение унифицированной структурной модели задачи о назначении позволяет определить общие подходы к решению таких задач, например, генетическим алгоритмом, который обеспечивает сложность меньшую NP-полного перебора. Реализация такого подхода допускает решение более широкого класса задач, получение более эффективного метода решения, что, в конечном счете, определяет актуальность темы исследования, особенно в условиях задач с высокой размерностью.
Тематика диссертационной работы соответствует научному направлению кафедры ПМиЭММ «Разработка математических моделей, методов и информационных технологий в технических и экономических системах перерабатывающей промышленности» (JV» г.р. 01200003664).
Объектом диссертационных исследований являются математические модели и численные методы решения класса задач о назначении.
Предметом диссертационных исследований являются свойства моделей и численных методов.
Цель диссертационной работы заключается в проведении структурного анализа математических моделей класса задач о назначении, разработке унифицированного подхода к построению таких моделей и обосновании применения генетического алгоритма в качестве метода решения.
Для достижения поставленной цели необходимо решение следующих задач:
• Сравнительный анализ существующих моделей задач о назначении и методов их решения с позиции структурного моделирования класса задач о назначении.
• Разработка методов формализации отношений, обеспечивающего построение общей математической модели задач назначения при произвольных ограничениях. • Обоснование применения и разработка генетического алгоритма для решения задач о назначении в структурной постановке.
• Проведение анализа эффективности разработанного алгоритма и апробацию решения задач структурного моделирования на конкретных примерах.
Методы исследования. Использовались методы теоретико-множественного моделирования, методы вычислительной математики, методы теории графов, эволюционные методы, комбинаторные методы решения в условиях больших размерностях задач.
Научная новизна. В работе получены следующие результаты, характеризующиеся научной новизной:
1. Математическая модель класса задач о назначениях отличающаяся унифицированным структурным представлением ограничений и критерия.
2. Оператор кроссовера, отличающийся использованием случайной функцией порождения гена потомка.
3. Оператор мутации генетического алгоритма, в котором реализована проверка хромосомы на соответствие ограничениям.
Практическая ценность. Использование структур его моделирования позволяет реализовать формализацию более широкого класса практических задач о назначении, получать приемлемые решения этих задач в условиях большой размерности.
Апробации работы. Основные научные и практические результаты докладывались и обсуждались на III Всероссийской научно-технической конференции «Теория конфликта и ее приложения» (Воронеж, 2004). На VII Всероссийской научно-технической конференции «Повышение эффективности средств обработки информации на базе математического моделирования» (ТВЛИИ, Тамбов, 2004). III Региональной научно-методической конференции «Информатика: проблемы, методологии, технологии», (ВГУ, Воронеж, 2003). IV Региональной научно-методической конференции «Информатика: проблемы, методологии, технологии», (ВГУ, Воронеж, 2004), а также на научных семинарах кафедры прикладной математики и экономико-математических методов ВГТЛ.
Публикации. Результаты диссертации отражены в 9 печатных работах, из них 5 - без соавторов, 1 - из списка ВАК.
В первой главе рассматриваются известные математические модели, которые анализируются с точки зрения структурного взаимоотношения. Существует много практических задач, сводящихся к задачам о назначении. Дискретные оптимизационные задачи оперируют конечными множествами объектов. Цель задачи оптимальным образом сопоставить множества, учитывая при этом ряд ограничений. Как простейший пример структурного моделирования рассматривается задача о назначении. Целевая функция максимизирует стоимость назначения, ограничения учитывают, чтобы каждый объект был назначен только один раз. Между элементами в множествах отсутствуют отношения, т.е. это множества бесструктурные, В задачах структурного моделирования предполагается взаимозависимость элементов. Структурное моделирование включает в себя широкий класс задач о назначении. Показывается, что задачи планирования, распределения, расписания, транспортные задачи, задача о размещении и раскрое и многие другие известные постановки обобщаются при рассмотрении их как задач о назначении структур, Под структурой понимается множество с заданным на нем отношением. Таким образом, в первой главе поставлены общие принципы новой модификации задачи о назначении, которые является значительным ее расширением. В силу того, что данная постановка позволяет работать со структурными множествами, то ее можно назвать задачей структурного моделирования (ЗСМ). Приведены основные принципы формализации сложных ограничений, проиллюстрирована идея подхода, рассмотрены некоторые формализованные постановки задач, которые проанализированы с точки зрения структурного моделирования, представлены их методы решения.
Во втором главе рассматривается задача структурного моделирования в общем виде, в которой оптимальным образом требуется сопоставить некоторое конечное число множеств с заданными структурами. При этом критерием является учет структуры множеств, от которого зависит качество назначения. Структура объекта нредставима в виде множества элементов с заданным на нем отношением, а отношения на множествах можно задавать в виде булевых матриц. В зависимости от того насколько сложна структура множества, настолько много потребуется элементов в отношении, чтобы ее описать. Поэтому вводится понятие показателя сложности структуры. Каждому отношению между элементами на множестве сопоставляется булевая матрица. Переменной в математической модели также является многомерная булевая матрица. Задается целевая функцию задачи. Она учитывает матрицу отношений и взаимозависимость элементов. Поэтому в целевой функции проверяются поэлементно назначения из каждого множества, если отношения соблюдаются, то произведение равняется 1, в противном случае - 0. Таким образом, целевая функция стремиться к максимуму, чтобы увеличить количество выполненных отношений. Из целевой функции и ограничений видно, что квадратичная задача о назначении является частным случаем предлагаемой модели. Полученная математическая модель интерпретируется на графах как задача поиска наибольшего клика. Но при больших размерностях задач, требуется поиск решения за приемлемое время, что не могут обеспечивать алгоритмы, реализованные на графах. Также метод ветвей и границ, различные способы линеаризации целевой функции вызывают ряд сложностей при реализации вычислительной схемы. Итак, во второй главе, построена общая модель задач о структурном назначении. В третьей главе предлагается генетический алгоритм и исследование его эффективности. Для реализации разработанной математической модели определяются основные термины: индивидуум, хромосома, ген, приспособленность. Задается функция кроссовера скрещивания двух индивидуумов. Скрещивание происходит похромосомно, т.е. потомок формируется из хромосом родителей. Т.к. индивидуум должен удовлетворять ограничениям модели, то в каждой хромосоме присутствует только один ненулевой ген, следовательно /-я хромосома индивидуума Л определяется позицией ненулевого гена. Чтобы приблизить генетический алгоритм к более реальному биологическому процессу, в кроссовере используется функция рандомизации. Работа операции кроссовера заключается в последовательном скрещивании позиций ненулевых генов хромосом индивидуумов. При вычислении новой хромосомы необходимо учитывать ограничения модели, т.е. в каждой строке и столбце матрицы находится только один не нулевой элемент. Для соблюдения этого ограничения, после вычисления позиции единичного гена, достаточно корректировать ее сдвигая поочередно вправо и влево. Данная коррекция позиции называется случайной - мутацией хромосомы. Согласно введенного понятия мутации последняя хромосома индивидуума будет предопределяется предыдущими. Доказано утверждение, что предлагаемый алгоритм представим в каноническом виде. Канонический вид генетического алгоритма оперирует двоичными векторами-хромосомами, в нем используется одноточечный кроссовер, эффективность канонического вида алгоритма доказана в теореме о шимах Д.Холландом в 1972. Численные эксперименты тестирования предлагаемого генетического алгоритма подтверждают достоверность теоретических заключений.
В четвертой главе рассматривается разработанный в рамках специальности программный комплекс, состоящий из нескольких подсистем. ИС «Коммунальные платежи» зарегистрирована в государственном фонде алгоритмов н программ, имеет соответствующий сертификат во Всероссийском научно-техническом информационном центре. Задачи о раскрое и составлении расписаний рассматриваются как примеры задач структурного моделирования. В задаче о раскрое предлагается способ описания произвольных нелинейных форм изделии и заготовок. Согласно материалу изделия и точности, которую необходимо обеспечить, на заготовки изделия наносится сетка требуемого размера ячейки. На множествах элементов сетки задаются отношения представимые булевыми матрицами. Целевая функция максимизирует количество корректно назначенных ячеек, т.е. стремится к сохранению исходной формы изделии и заготовок. Т.к. элементы из множеств изделий и заготовок могут назначаться друг другу только один раз, то добавляются соответствующие ограничения. В результате получается частный случай квадратичной задачи о назначении с единичными коэффициентами в целевой функции.
Приводятся результаты вычислительных экспериментов генетического алгоритма для квадратичной задачи о назначении. В процессе тестирования генетический алгоритм показал хорошие результаты за приемлемое время. Результаты вычислений оформлены в виде соответствующих графиков п таблиц.
Анализ частных случаев формализованных постановок задач
Исследования в области теории автоматов начались в середине 50-х годов прошлого века. Несмотря на свою простоту, модель конечного автомата оказалась чрезвычайно удобной в огромном числе приложений не только в информатике, но и во многих других областях инженерной деятельности. Большой интерес к этой теории объясняется именно широкими возможностями ее применения. Без преувеличения можно сказать, что теория автоматов является одним из фундаментальных блоков современной теоретической и практической информатики. Наряду с классическими приложениями теории автоматов, такими как проектирование встроенных систем логического управления, обработка текстов и построение компиляторов искусственных языков, в последнее время появились новые, нетрадиционные области применения этой теории - спецификация и верификация систем взаимодействующих процессов (в частности, протоколов коммуникации), языки описания документов и объектно-ориентированных программных систем, оптимизация логических программ и другие. Для одного из наиболее обещающего из новых важных приложений теории автоматов, а именно для верификация систем процессов, необходимы знания из логики и теории логического вывода.
Не все окружающие нас преобразователи информации выполняют функциональное отображение информации. Результат преобразования вход = выход зачастую зависит не только от того, какая информация в данный момент появилась на входе, но и оттого, что происходило раньше, от предыстории преобразования, Множество примеров тому дают биологические системы. Например, один и тот же вход — неудачная попытка после совершения каких-либо действий вызовет одну реакцию в первый раз и совсем другую в последующие разы. Реакция будет различной, она будет зависеть от предыдущих событий.
Таким образом, существуют более сложные, не функциональные преобразователи информации; их реакция зависит не только от входа в данный момент, но и оттого, что было на входе раньше, от входной истории. Такие преобразователи называются автоматами. Число возможных входных историй бесконечно (счетно), даже если различных элементов входной информации у автомата конечное. Если автомат по-разному будет себя вести для каждой возможной предыстории, то такой «бесконечный» автомат должен иметь бесконечный ресурс - память, чтобы все эти предыстории как-то запоминать. Введем на множестве предыстории отношение эквивалентности. Две предыстории будем считать эквивалентными, если они одинаковым образом влияют на дальнейшее поведение автомата. Очевидно, что для своего функционирования автомат должен не обязательно запоминать входные истории, достаточно, чтобы автомат запоминал класс эквивалентности, к которому принадлежит данная история.
Случай, когда количество классов эквивалентных входных историй конечно, является простейшим, и именно он вызвал значительный интерес и имеет очень широкие применения. Соответствующая формальная модель называется конечным автоматным преобразователем информации, или просто конечным автоматом.
Состоянием автомата называется класс эквивалентности его входных историй. В своих состояниях автомат запоминает свое «концентрированное прошлое». Неформально состояние системы — это ее характеристика, однозначно определяющая ее дальнейшее поведение, все последующие реакции системы на внешние события. На один и тот же входной сигнал конечный автомат может реагировать по-разному, в зависимости от того, в каком состоянии он находится в данный момент.
Поскольку состояние представляет собой класс эквивалентных предыстории входов, состояние может измениться только при приходе очередного входного сигнала. При получении входного сигнала конечный автомат не только выдает информацию на выход как функцию этого входного сигнала и текущего состояния, но и меняет свое состояние, поскольку входной сигнал изменяет предысторию. Функционирование автомата удобно представлять графически. На рис. 6 блок памяти автомата хранит информацию о текущем состоянии 5, которое вместе с входным сигналом Л определяет выходную реакцию автомата У и следующее состояние.
Текущее состояние автомата представляет все то, что автомат знает о прошлом с точки зрения его будущего поведения -г реакций на последующие входы. Эта история в концентрированном виде определена текущим состоянием, и все будущее поведение автомата, как реакция его на последующие входные сигналы, определено именно текущим состоянием, но не тем, как автомат пришел в него.
Итак, конечный автомат - это устройство, работающее в дискретные моменты времени (такты). На вход конечного автомата в каждом такте поступает один из возможных входных сигналов, а на его выходе появляется выходной сигнал, являющийся функцией его текущего состояния и поступившего входного сигнала. Внутреннее состояние автомата также меняется. Моменты срабатывания (такты) определяются либо принудительно тактирующими синхросигналами, либо асинхронно, наступлением внешнего события — прихода сигнала.
Определим конечный автомат формально. [33] Опередслснне. Конечным автоматом Мили называется шестерка объектов: A = S, X, Y, s0, S, Я , где S- конечное непустое множество (состояний); А - конечное непустое множество входных сигналов (входной алфавит); Y— конечное непустое множество выходных сигналов (выходной алфавит); SQ eS- начальное состояние; 5: S х X— Л"- функция переходов; Я : S х X — У— функция выходов. Рассмотрим двоичный автомат применительно к задаче структурного моделирования. В данном случае автомат можно представить как прибор для решения булевой задачи оптимизации. В общем виде постановка задачи определяется булевой целевой функцией и ограниченным множеством допустимых значений. Пусть п - размерность решаемой задачи. Множество состояний S с Вп - подпространство /(-разрядных двоичных векторов, которое совпадает с множеством допустимых значений. Входным алфавитом X является двоичный вектор коэффициентов целевой функции. Выходной алфавит У — конечное множество значений целевой функции. Функция перехода S - это алгоритм последовательного перехода к следующему состоянию. Функция выхода Л - вычисление значения целевой функции на данном состоянии. Решением задачи является состояние, на котором достигается экстремальное значение целевой функции.
Разработка способов формализации ограничений
Генетические алгоритмы (ГЛ) - адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Рассмотрим идею алгоритма, происхождение и некоторые особенности.
Генетические алгоритмы предлагаются как один из удачных подходов к решению оптимизационных задач. Наблюдается заинтересованность в использовании принципа генетического алгоритма [38-33], предложенного Дж. Холландом (Мичиганский университет) в 1975 г. [13]. Генетические алгоритмы имеют большое число реализаций с исследованными методами оптимизации, улучшения и настройки, объединенными единой идеей совершенствования алгоритма.
Функционирование любого генетического алгоритма основано на принципе эволюции, впервые описанном Ч. Дарвином. Существует математическое доказательство, которое объясняет причину эффективности такого подхода (так называемая теорема схем - Schema Theorem) [65,93]. Как и в природной эволюционной модели, поиск оптимального решения ведется параллельно во множестве вариантов. Поэтому в генетических (или эволюционных) алгоритмах терминология в основном аналогична теории эволюции Дарвина.
В отличие от обычных алгоритмов, где поиск оптимального решения ведется линейно, в одном варианте, в эволюционных алгоритмах имеем множество альтернативных решений, которые в процессе работы алгоритма конкурируют между собой и изменяются по определенным правилам. В итоге выбирается наилучшее решение, которое считается результатом работы алгоритма. Основной принцип работы классического генетического алгоритма условно можно разделить ЕШ три этапа; инициализация, моделирование эволюционного процесса и окончание работы.
Инициализации. Создается популяция (набор) значительного числа решений-кандидатов. В общем случае при их генерации не накладывается никаких условий — они полностью случайны, а их дальнейшая оптимизация проводится в процессе работы второй части алгоритма.
Однако в реальных реализациях генетических алгоритмов часто используют различные эвристики уже во время создания начальной популяции решений. Эти эвристики специфичны для каждой конкретной оптимизационной задачи, но основное их предназначение - увеличить среднее значение оптимальности уже среди начальных решений. Это, в свою очередь, позволяет существенно уменьшить время работы основной части алгоритма,
В классических реализациях генетического алгоритма альтернативные решения задаются в виде набора битовых строк, каждая из которых называется хромосомой, а бит - соответственно геном. Способ представления хромосом (например, в виде битовых строк) не имеет существенного семантического значения, кроме влияния на продуктивность конкретной программной реализации алгоритма. Моделирование эволюционного процесса. Следующая фаза алгоритма наиболее длительна и важна, поскольку к начальной популяции применяются эволюционные законы. Как известно, основными принципами эволюции есть наследование, мутации и отбор. Именно эти правила итеративно применяются к начальной популяции, которая под их действием начинает постоянно изменяться. Моделировать природные эволюционные процессы оказалось удобно, рассматривая каждое решение как хромосому, которая состоит из неделимых частей - генов. Поэтому на этапе реализации решения представляются в виде хромосом, а в алгоритме законы эволюции реализуются следующим образом. К каждому гену всех хромосом первого поколения применяется оператор мутации, который с малой вероятностью может изменить ген на любую его модификацию. ? В хромосомах первого поколения происходит обмен участками. Таким образом, формируются хромосомы второго поколения. При этом вероятность участия в формировании следующего поколения тем больше, чем выше оценка хромосомы первого поколения. После образования такого же числа хромосом во втором поколении, что и в первом, второе поколение полностью замещает первое и итерация повторяется. Интуитивно ясно, что можно подобрать такие параметры работы второй фазы генетического алгоритма, при которых популяция решении будет постепенно улучшаться, т. е. становиться оптимальнее. Тип репродукции, используемый в работе генетического алгоритма, определяет способ, по которому осуществляется смена поколений. Различают два основных типа репродукции — генерационный (generation — поколение) и «стойкий» режим (steady state). Генерационный тип репродукции означает полную замену популяции следующим поколением на каждой итерации алгоритма [13]. Пусть количество хромосом в популяции равно N. Тогда на каждой итерации алгоритма выбирается N/2 пар родительских хромосом, с помощью которых будут сгенерированы N хромосом-детей. Полученное таким образом поколение полностью замещает родительское поколение. При стойком режиме репродукции в отличие от генерационного режима каждая итерация повторяется только для одной пары хромосом, т. е. предыдущее поколение не заменяется новым. Сгенерированные хромосомы- дети возвращаются в исходную популяцию, замещая имеющиеся в ней наихудшие решения [36].
Синтез и исследование алгоритма решения квадратичной задачи о назначениях
Для решения квадратичной задачи о назначениях разработано множество точных алгоритмов. Однако, как известно, эта задача относится к классу NP полных, поэтому при данной размерности (более 1000 неизвестных) отыскание точного решения представляется затруднительным. Однако в практической реализации себя хорошо зарекомендовали простейшие приближенные алгоритмы, позволяющие отыскивать возможные варианты расписания за несколько секунд. Программный комплекс составления расписаний учебных занятий является удобным инструментом для формирования расписания «с нуля», а также для дальнейшего сопровождения. Основная сложность при работе с расписанием заключается именно в сопровождении. Это связанно с постоянно изменяющимися требованиями к расписанию. В готовое расписание очень тяжело вносить коррекцию, так как при этом происходит накладка по многим кабинетам и учителям.
Программа поддерживает возможность составлять расписание вручную. В процессе работы пользователю предлагаются только те предметы, которые подходят для расстановки, при этом работать можно и любом из трех срезов данных, т.е. составлять по классам, учителям и по кабинетам. Очень удобной является возможность «досоставления» расписания. Если пользователь затрудняется в расположении предметов в некоторых ячейках, то он может пометить их как «автоячейки». Программа оптимальным образом подберет в них нужные предметы. Очевидно, чтобы автоматически составить расписание целиком, для этого нужно сделать автоячейками все ячейки сетки расписания. Основные функциональные возможности программы приведены на рис. 25.
Рассмотрим более подробно алгоритм составления расписания. Цель программы сводится к отысканию матрицы xi}, которая сопоставляет каждому предмету класса ячейку в расписании. Матрица ху универсальная, поэтому предполагается, что индексом j нумеруется не только список предметов школы, а все предметы из учебного плана. Таким образом, если в классе 4«А» должно быть 5 часов предмета «Математика» в неделю, а в классе 4«Б» - б часов, то в матрице хи этот предмет будет встречаться 9 раз. Чтобы сопоставить для каждого класса именно его предметы для этого достаточно для соответствующих индексов і и j присвоить 0. Это обстоятельство позволяет до решения задачи о назначении сильно уменьшить размерность матрицы. Итак, процесс автоматического составления расписания разбивается на два этапа; уменьшение размерности матрицы д\. и поиск решения.
Универсальность матрицы хд заключается не только в том, что она способна «хранить» учебный план школы. Составление расписание обязательно должно учитывать иногда обязательные пожелания некоторых учителей. Каждый предмет закрепляет за собой любое количество ресурсов, т.е. учителей и кабинетов (такой подход также увеличивает универсальность применения задачи, т.к. во многих школах классы разбиваются на несколько подгрупп), и если какой-либо учитель не может преподавать в определенный день или урок, то для всех предметов, которые используют этого учителя достаточно поставить 0 в необходимые дни или уроки. Такое обстоятельство тоже значительно уменьшает размерность задачи, но следует не забывать, что чем меньше размерность, тем меньше область поиска, поэтому это можно воспринимать как плюс так и минус.
Итак, перейдем ко второму пункту — алгоритму поиска решения. Так как размерность задачи достаточно большая, то воспользуемся приближенным алгоритмом. Целевая функция на минимум и имеет квадратичный вид. Предположим, что наиболее сложные предметы, в смысле дефицита ресурса, расставлять нужно в первую очередь, а более простые в последнюю, при этом если некоторые простые все таки расставлены не будут, то это лучше, чем не расставленные сложные. Дефицитность ресурса определяется частотой его использования, поэтому предметы его использующие чаще фигурируют в матрице S, а следовательно и в целевой функции. Поэтому будем назначать в первую очередь те предметы, которые максимальным образом уменьшает размер целевой функции. Составим целочисленную матрицу Pji,i = ltN, j = \,N следующего вида.
Каждому элементу матрицы соответствует число, которое показывает сколько пар произведений вычеркнется из целевой функции при присвоении х.. = 1. Далее находится максимальный элемент p[io,Jo] и соответствующему элементу x[i0,J0] присваивается 1. Таким образом, станут нулевыми все элементы из целевой функции, которые участвуют в произведении с элементом .Y y, т.к. функция на минимум. Необходимо учесть, что в ограничениях также произойдет обнуление многих элементов, что повлияет на размер целевой функции. Работу алгоритма представлена в виде блок-схемы на рис. 26.
Задача о раскрое с произвольным видом границ
Программный комплекс составления расписаний учебных занятий является удобным инструментом для формирования расписания «с нуля», а также для дальнейшего сопровождения. Основная сложность при работе с расписанием заключается именно в сопровождении. Это связанно с постоянно изменяющимися требованиями к расписанию. В готовое расписание очень тяжело вносить коррекцию, так как при этом происходит накладка по многим кабинетам и учителям.
Программа поддерживает возможность составлять расписание вручную. В процессе работы пользователю предлагаются только те предметы, которые подходят для расстановки, при этом работать можно и любом из трех срезов данных, т.е. составлять по классам, учителям и по кабинетам. Очень удобной является возможность «досоставления» расписания. Если пользователь затрудняется в расположении предметов в некоторых ячейках, то он может пометить их как «автоячейки». Программа оптимальным образом подберет в них нужные предметы. Очевидно, чтобы автоматически составить расписание целиком, для этого нужно сделать автоячейками все ячейки сетки расписания. Основные функциональные возможности программы приведены на рис. 25.
Рассмотрим более подробно алгоритм составления расписания. Цель программы сводится к отысканию матрицы xi}, которая сопоставляет
каждому предмету класса ячейку в расписании. Матрица ху универсальная, поэтому предполагается, что индексом j нумеруется не только список предметов школы, а все предметы из учебного плана. Таким образом, если в классе 4«А» должно быть 5 часов предмета «Математика» в неделю, а в классе 4«Б» - б часов, то в матрице хи этот предмет будет встречаться 9 раз. Чтобы сопоставить для каждого класса именно его предметы для этого достаточно для соответствующих индексов і и j присвоить 0. Это обстоятельство позволяет до решения задачи о назначении сильно уменьшить размерность матрицы. Итак, процесс автоматического составления расписания разбивается на два этапа; уменьшение размерности матрицы д\. и поиск решения. Универсальность матрицы хд заключается не только в том, что она способна «хранить» учебный план школы. Составление расписание обязательно должно учитывать иногда обязательные пожелания некоторых учителей. Каждый предмет закрепляет за собой любое количество ресурсов, т.е. учителей и кабинетов (такой подход также увеличивает универсальность применения задачи, т.к. во многих школах классы разбиваются на несколько подгрупп), и если какой-либо учитель не может преподавать в определенный день или урок, то для всех предметов, которые используют этого учителя достаточно поставить 0 в необходимые дни или уроки. Такое обстоятельство тоже значительно уменьшает размерность задачи, но следует не забывать, что чем меньше размерность, тем меньше область поиска, поэтому это можно воспринимать как плюс так и минус. Итак, перейдем ко второму пункту — алгоритму поиска решения. Так как размерность задачи достаточно большая, то воспользуемся приближенным алгоритмом. Целевая функция на минимум и имеет квадратичный вид. Предположим, что наиболее сложные предметы, в смысле дефицита ресурса, расставлять нужно в первую очередь, а более простые в последнюю, при этом если некоторые простые все таки расставлены не будут, то это лучше, чем не расставленные сложные. Дефицитность ресурса определяется частотой его использования, поэтому предметы его использующие чаще фигурируют в матрице S, а следовательно и в целевой функции. Поэтому будем назначать в первую очередь те предметы, которые максимальным образом уменьшает размер целевой функции. Составим целочисленную матрицу Pji,i = ltN, j = \,N следующего вида. Каждому элементу матрицы соответствует число, которое показывает сколько пар произведений вычеркнется из целевой функции при присвоении х.. = 1. Далее находится максимальный элемент p[io,Jo] и соответствующему элементу x[i0,J0] присваивается 1. Таким образом, станут нулевыми все элементы из целевой функции, которые участвуют в произведении с элементом .Y y, т.к. функция на минимум. Необходимо учесть, что в ограничениях также произойдет обнуление многих элементов, что повлияет на размер целевой функции. Работу алгоритма представлена в виде блок-схемы на рис. 26. В результате проведенных в диссертационной работе теоретических исследований и практических экспериментов достигнуты следующие результаты работы: 1. Проведен теоретико-множественный анализ задач, обеспечивший унифицированный подход к построению математических моделей из класса задача о назначении, 2. Разработан метод структурного моделирования для построения моделей на основе введения отношений на множествах обеспечивающий формализацию широкого класса задач о назначении. 3. Проведен анализ известных подходов и методов решения из класса задач о назначении, что обосновало применение генетического алгоритма при условиях большой размерности. 4. Разработаны основные операторы кроссовер и мутация генетического алгоритма, обеспечивающие его реализацию. 5. Обоснована эффективность разработанного алгоритма, что позволяет его применять в условиях больших размерностей. 6. На примере квадратичной задачи о назначении проведена апробация предложенных моделей и алгоритмов, подтверждающая их эффективность. 7. Основные теоретические и практические результаты работы внедрены в учебный процесс в Воронежской государственной технологической академии и Воронежского государственного университета.
