РПЗ САФИН

Вывод по аналитическому разделу

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

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

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

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

Содержание