Распределительная задача
Полученное решение сохраняется в файле Word (Пример решения транспортной задачи). Также автоматически генерируется шаблон решения в Excel.
Постановка распределительной задачи
Постановка распределительной задачи. На станции имеются порожние вагоны разных типов i (i = 1,2,...m) в количестве Bi единиц. На станции должны быть погружены и отправлены по заявкам грузоотправителей различные рода грузов j (j = 1,2,...n) в объеме Γj тонн.Техническая норма загрузки груза рода j в соответствующий тип вагона i, равна Pij. В исключительных случаях допускается перегруз вагона равный 2 тоннам.
Требуется оптимально распределить имеющиеся на станции порожние вагоны под погрузку разными родами грузов, чтобы средняя статическая нагрузка по станции на один вагон была максимальной.
При разработке модели не учитывается партионность отдельных отправок, т. е. поданный вагон всегда будет загружен на уровне технической нормы.
Количество вагонов типа i подаваемых под погрузку груза j обозначим xij.
Т.к. статическая нагрузка вагона определяется, Pст=n∑i=1PiUn , а для нашего примера Pст=n∑j=1Γjm∑i=1n∑j=1xij , то, для увеличения статической нагрузки необходимо обеспечить погрузку минимальным суммарным количеством порожних вагонов.
Т.о. требуется минимизировать целевую функцию:
При условиях, что:
- нельзя подать под погрузку вагонов каждого типа больше, чем их имеется на станции
- нельзя погрузить грузов каждого рода больше чем его имеется;
Кроме того, отрицательные значения погруженных вагонов не имеют смысла.
Итак, сформулирована, так называемая, распределительная задача. В общем случае она сводится к такому распределению взаимозаменяемых ресурсов (технических средств, рабочей силы, вагонов, локомотивов и т.п.) по видам работ, чтобы суммарная производительность была максимальной (в примере – статическая нагрузка), либо сумма издержек на выполнение этих работ была минимальной.
Для решения распределительной задачи используется специальный метод разрешающих множителей.
Метод разрешающих множителей
Метод представляет собой строгий алгоритм действий и расчетов. Сначала составляется план, обеспечивающий минимум целевой функции, но не отвечающий ограничениям. Затем с помощью специальной процедуры отыскивается допустимый оптимальный план.Алгоритм метода
1. Для составления начального плана в каждом столбце отыскивается клетка с максимальной технической нормой погрузки, в нее заносится число тонн груза и число вагонов необходимых для полного удовлетворения погрузки (в столбце), с учетом допустимого перегруза.
2. По каждой строке определяется разность между количеством имеющихся вагонов на станции и числом погруженных вагонов
В результате расчета, в зависимости от знака, полученного при расчете по формуле (4), каждая строка классифицируется на избыточную или недостаточную. Если в при расчете разности получается 0, то знак строки и, соответственно её классификация определяется через клетки с выравненными техническими нормами загрузки в конкретных столбцах и такие строки называются условно-избыточными или условно-недостаточными.
Задача считается решенной, если все строки будут с одинаковым знаком, т.е. только избыточные или только недостаточные.
В случае невыполнения этого условия производится корректировка начального плана распределения грузов по вагонам.
3. Для корректировки неоптимального плана для каждого столбца находится разрешающий множитель $\lambda_j$ по формуле
где Pзан(−)j - техническая норма погрузки в занятой клетке недостаточной строки;
Pmax(+)j - максимальная техническая норма погрузки в избыточных строках.
Разрешающие множители всех столбцов сравниваются между собой и, к дальнейшим расчетам принимается минимальный разрешающий множитель.
4. Все технические нормы погрузки во всех избыточных строках (+) умножаются на выбранный разрешающий множитель, или во всех недостаточных строках (-) делится на него. Через клетки с выравненными техническими нормами погрузки осуществляется корректировка распределения вагонов. Корректировка осуществляется с учетом истинных значений технических норм погрузки.
Получается новый план погрузки, для которого выполняется п.2 алгоритма. Если план не оптимален, то продолжается решение задачи согласно п.п.3,4.