Сценарий работы программы

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

Шаг 1. Администратор, запустив программу, загружает информацию о клиентах, курсах и образовательных центрах из базы данных.

Шаг 2. Создание начального распределения клиентов по ОЦ, состоящее из списка записей, каждая из которых хранит в себе информацию об ученике и информацию об определенном количестве образовательных центров, в которых ученик может обучаться. Это число администратор может изменять, но, по умолчанию, оно равняется трём. Таким образом, в дальнейшем при создании распределения для каждого ученика будут рассматриваться лишь 3 ближайших к его дому образовательных центра. Чтобы каждый ученик вносил наибольший вклад в функцию прогнозируемой прибыли, он будет распределен к тому ОЦ, к которому живет ближе всего. Этот ОЦ должен стоять первым в списке образовательных центров для каждого клиента. Для этого для каждого ученика производится сортировка соответствующих ему центров в порядке возрастания расстояния от клиента до ОЦ.

Шаг 3. После того, как распределение создано, каждый ученик однозначно определен учиться в конкретном ОЦ, но группы еще не сформированы. В каждом ОЦ по каждому курсу рассчитывается число учеников, которые хотят записаться на данный курс. Используя данные о минимальном и максимальном размере групп для каждого курса, производится расчет возможного числа полных групп (размер которых равен максимальному размеру группы для данного курса). Возможно, после этого шага у некоторых центров для некоторых курсов останутся нераспределенные учащиеся. Для каждого ОЦ для каждого курса смотрим, можно ли из оставшихся людей собрать еще одну группу. Число людей в этой группе должно быть не меньше, чем минимальный размер группы для данного курса. Если можно, увеличиваем число созданных групп на единицу, а число нераспределенных на данный курс в данном ОЦ клиентов приравнивается к 0. Иначе, это число будет равным числу оставшихся нераспределенных клиентов.

Теперь известно точное число людей, оставшихся нераспределенными для каждого ОЦ для каждого предмета. Но привязки конкретного человека к конкретной группе еще не создано. Чтобы прибыль была наибольшей, выгодней оставить нераспределенными тех, кто находится дальше всех от данного ОЦ. Для каждого ОЦ для каждого курса создается список клиентов, которые хотят записаться на данный курс. Эти списки сортируются в порядке уменьшения расстояния от ОЦ до места жительства ученика. Если число нераспределенных клиентов для данного ОЦ данного курса n_ij не равно 0, то первые n_ij клиентов в этом списке отмечаются как нераспределенные. Остальных клиентов отмечаем как распределенных. Начальное распределение клиентов по группам создано.

Шаг 4. Нам известно точное число групп, а также данные о распределенных клиентах. Значение функции прогнозируемой прибыли рассчитывается по формуле

как сумма доходов, получаемых с каждого ученика, за вычетом расходов на преподавателей.

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

Шаг 5. Суть алгоритма поиска наиболее приемлемого распределения состоит в том, чтобы перебросить лишних нераспределенных учеников в другие ОЦ с целью собрать там полные группы. Но это вовсе не означает, что именно нераспределенных учеников необходимо перенести в другой ОЦ, так как у некоторых из этих учащихся в списке возможных для обучения образовательных центров может и не быть необходимого нам образовательного центра. Таким образом, критериями для переноса учеников из одного центра во второй при формировании нового распределения являются наличие второго ОЦ в списке смежности, а также наибольшее расстояние до 1 ОЦ.

Теперь пользователь программы может запустить алгоритм поиска нового распределения. Поиск распределения состоит в переброске учащихся от одних центров к другим. И тут возможна следующая ситуация:

Рисунок 3. Нераспределенные ученики по курсу “Математика 5 класс”

При таком распределении при формировании только одной группы, например в образовательном центре под номером 7, будет набрана полная группа путем переброски людей из соседних. И это будет оптимальный шаг, если пытаться формировать только 1 группу. Но после этого шага останутся клиенты, которых мы уже не сможем скомпоновать в одну группу, так как они будут находиться слишком далеко друг от друга. Оптимальным же шагом при этой ситуации будет одновременное создание двух групп (в 5 и 11 образовательных центрах). И это, действительно, принесет больше прибыли, т.к. почти все нераспределенные клиенты запишутся на курсы.

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

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

Шаг 7. Производится отображение всех результатов на карте с учетом всех поставленных ограничений.