Вывод по аналитическому разделу
Если данную задачу попытаться свести к транспортной, то в качестве типов ресурсов мы будем иметь лишь один тип – людей, а в качестве пунктов назначения – образовательные центры. В транспортной задаче мощности стоков и истоков заданы заранее. В нашем же случае мощность истока равна числу клиентов, а мощность каждого стока не может быть найдена, поскольку заранее неизвестно, сколько людей запишется в каждый образовательный центр. Также в транспортной задаче предполагается, что стоимость перевозки каждого ресурса одного вида до одного и того же пункта назначения одинакова. У нас же это число будет варьироваться для каждого клиента, так как расстояние от одного клиента до конкретного ОЦ отличается от расстояния между другим клиентом и тем же ОЦ. Следовательно, данную задачу нельзя свести к транспортной.
При рассмотрении задачи динамического программирования о распределении ресурсов выявляется та же проблема – ресурсы в этой задаче однотипные, как, например, деньги. Следовательно, данная задача не сводится к задаче о распределении ресурсов.
Более широким классом является задача линейного программирования. Задачи линейного программирования включают в себя задачу о распределении ресурсов и транспортную задачу. Проблема состоит в том, что для каждого клиента необходимо будет записать большое множество ограничений в виде равенств и неравенств. Далее задача решается симплекс-методом, который имеет экспоненциальную сложность. Это означает, что при больших количествах переменных результат можно ожидать очень долго. В нашем случае, когда каждые 2-3 минуты на курсы записывается еще один человек, поиск оптимального решения средствами линейного программирования не является приемлемым, так как за время, пока алгоритм будет искать решение, ситуация на рынке может измениться кардинальным образом.
В виду сложности формализации данной задачи, делается вывод о создании нового алгоритма, который использует неформальный подход с учетом априорных данных, занесенных в базу данных.
Конструкторский раздел
Сценарий работы программы
Данная программа предназначена для поиска наиболее приемлемого распределения учащихся по образовательным центрам. Два раза в году при наборе учащихся на очередной семестр, у образовательного учреждения возникает потребность распределить всех учеников таким образом, чтобы прибыль была максимальной.
Шаг 1. Администратор, запустив программу, загружает информацию о клиентах, курсах и образовательных центрах из базы данных.
Шаг 2. Создание начального распределения клиентов по ОЦ, состоящее из списка записей, каждая из которых хранит в себе информацию об ученике и информацию об определенном количестве образовательных центров, в которых ученик может обучаться. Это число администратор может изменять, но, по умолчанию, оно равняется трём. Таким образом, в дальнейшем при создании распределения для каждого ученика будут рассматриваться лишь 3 ближайших к его дому образовательных центра. Чтобы каждый ученик вносил наибольший вклад в функцию прогнозируемой прибыли, он будет распределен к тому ОЦ, к которому живет ближе всего. Этот ОЦ должен стоять первым в списке образовательных центров для каждого клиента. Для этого для каждого ученика производится сортировка соответствующих ему центров в порядке возрастания расстояния от клиента до ОЦ.
Шаг 3. После того, как распределение создано, каждый ученик однозначно определен учиться в конкретном ОЦ, но группы еще не сформированы. В каждом ОЦ по каждому курсу рассчитывается число учеников, которые хотят записаться на данный курс. Используя данные о минимальном и максимальном размере групп для каждого курса, производится расчет возможного числа полных групп (размер которых равен максимальному размеру группы для данного курса). Возможно, после этого шага у некоторых центров для некоторых курсов останутся нераспределенные учащиеся. Для каждого ОЦ для каждого курса смотрим, можно ли из оставшихся людей собрать еще одну группу. Число людей в этой группе должно быть не меньше, чем минимальный размер группы для данного курса. Если можно, увеличиваем число созданных групп на единицу, а число нераспределенных на данный курс в данном ОЦ клиентов приравнивается к 0. Иначе, это число будет равным числу оставшихся нераспределенных клиентов.
Теперь известно точное число людей, оставшихся нераспределенными для каждого ОЦ для каждого предмета. Но привязки конкретного человека к конкретной группе еще не создано. Чтобы прибыль была наибольшей, выгодней оставить нераспределенными тех, кто находится дальше всех от данного ОЦ. Для каждого ОЦ для каждого курса создается список клиентов, которые хотят записаться на данный курс. Эти списки сортируются в порядке уменьшения расстояния от ОЦ до места жительства ученика. Если число нераспределенных клиентов для данного ОЦ данного курса nij не равно 0, то первые nij клиентов в этом списке отмечаются как нераспределенные. Остальных клиентов отмечаем как распределенных. Начальное распределение клиентов по группам создано.
Шаг 4. Нам известно точное число групп, а также данные о распределенных клиентах. Значение функции прогнозируемой прибыли рассчитывается по формуле
как сумма доходов, получаемых с каждого ученика, за вычетом расходов на преподавателей.
Подсчитав прибыль, мы также получили распределение учащихся, где каждому распределенному учащемуся сопоставлен конкретный образовательный центр.
Шаг 5. Суть алгоритма поиска наиболее приемлемого распределения состоит в том, чтобы перебросить лишних нераспределенных учеников в другие ОЦ с целью собрать там полные группы. Но это вовсе не означает, что именно нераспределенных учеников необходимо перенести в другой ОЦ, так как у некоторых из этих учащихся в списке возможных для обучения образовательных центров может и не быть необходимого нам образовательного центра. Таким образом, критериями для переноса учеников из одного центра во второй при формировании нового распределения являются наличие второго ОЦ в списке смежности, а также наибольшее расстояние до 1 ОЦ.
Теперь пользователь программы может запустить алгоритм поиска нового распределения. Поиск распределения состоит в переброске учащихся от одних центров к другим. И тут возможна следующая ситуация:
Рисунок 3. Нераспределенные ученики по курсу “Математика 5 класс”
При таком распределении при формировании только одной группы, например в образовательном центре под номером 7, будет набрана полная группа путем переброски людей из соседних. И это будет оптимальный шаг, если пытаться формировать только 1 группу. Но после этого шага останутся клиенты, которых мы уже не сможем скомпоновать в одну группу, так как они будут находиться слишком далеко друг от друга. Оптимальным же шагом при этой ситуации будет одновременное создание двух групп (в 5 и 11 образовательных центрах). И это, действительно, принесет больше прибыли, т.к. почти все нераспределенные клиенты запишутся на курсы.
Для каждого курса алгоритм рассматривает возможные распределения учеников по различным ОЦ. После набора очередной группы, нераспределенных учеников становится меньше. Критерий завершения алгоритма поиска нового распределения заключается в следующем: если больше ни одна группа не может быть набрана по данному курсу, идет переход к следующему курсу. Если ни одна группа не может быть набрана ни по одному из курсов, алгоритм завершает работу.
Шаг 6. После окончания работы алгоритма поиска наиболее приемлемого распределения, новое распределение и значение функции прибыли запоминаются в качестве текущих значений.
Шаг 7. Производится отображение всех результатов на карте с учетом всех поставленных ограничений.