Распределительная задача
Полученное решение сохраняется в файле Word. Также автоматически генерируется шаблон решения в Excel. При этом в силу того, что поданный вагон всегда будет загружен на уровне технической нормы, решение в 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.
Пример. На станцию поступает 4 рода порожних вагонов (В1, В2, В3, В4) под погрузку. Имеется груз 5 видов (Г1, Г2, Г3, Г4, Г5). Необходимо распределить грузы по вагонам так, чтобы средняя статическая нагрузка вагона была максимальной.
Требуется составить математическую модель задачи, построить начальный план распределения грузов, решить задачу методом разрешающих множителей.
| Тип вагонов и их количество | Вид груза и его количество, т | ||||
| Г1[400] | Г2[500] | Г3[600] | Г4[600] | Г5[700] | |
| B1[11] | 45 | 46 | 54 | 50 | 54 |
| B2[16] | 49 | 48 | 50 | 47 | 47 |
| B3[11] | 51 | 39 | 40 | 50 | 52 |
| B4[16] | 54 | 48 | 44 | 0 | 49 |
Решение.
1. Составляется начальный план погрузки вагонов, в котором каждый род груза грузится в вагоны с максимальной технической нормой погрузки, что обеспечивает минимум используемых вагонов.
Количество вагонов, необходимых для погрузки конкретного груза определяется по формуле:
xij=ГjPij
Допустимый перегруз равен 2 т/вагон.
Для Г1 максимальная норма погрузки равна 54 т/вагон. Количество вагонов: 400/54=8 ед.
Для Г2 максимальная норма погрузки равна 48 т/вагон. Количество вагонов: 500/48=10 ед.
Для Г3 максимальная норма погрузки равна 54 т/вагон. Количество вагонов: 600/54=11 ед.
Для Г4 максимальная норма погрузки равна 50 т/вагон. Количество вагонов: 600/50=12 ед.
Для Г5 максимальная норма погрузки равна 54 т/вагон. Количество вагонов: 700/54=13 ед.
Итерация №1
2. Определяются избытки и недостатки вагонов по каждой строке (по каждому типу вагонов), сравнивая количество имеющихся вагонов с потребным их числом. Результат записывается в последнем столбце таблицы плана перевозок.
3. Для столбцов [1,2] разрешающий множитель λ не определяется, т.к. в этих столбцах нет занятых клеток в недостаточных строках.
Множители λj:
[Груз 3]: 54/50=1.08
[Груз 4]: 50/47=1.064
[Груз 5]: 54/49=1.102
Таблица №1 - Начальный план погрузки.
| Тип вагонов и их количество | Г1[400] | Г2[500] | Г3[600] | Г4[600] | Г5[700] | Избытки, недостатки |
| B1[11] | 45 | 46 | 54 11/594 | 50 | 54 13/700 | -13 |
| B2[16] | 49 | 48 10/480 | 50 | 47 | 47 | +6 |
| B3[11] | 51 | 39 | 40 | 50 12/600 | 52 | -1 |
| B4[16] | 54 8/400 | 48 | 44 | 0 | 49 | +8 |
| λj | - | - | 1.08 | 1.064 | 1.102 |
План не оптимален (разноименные строки).
4. На выбранное значение λmin умножаются все значения технических норм погрузки во всех избыточных строках (2,4). Значения технических норм погрузки в недостаточных строках не изменяются. Скорректированные значения технических норм погрузки записываются в следующую таблицу.
Выбран λmin = 1.064 (Груз 4). Избыточные строки (+) умножаются на него.
Расчетное значение вагонов для В4Г2 равно 8 ед. Однако на предыдущем план имелся избыток, поэтому корректирвка равна 6 ед.
В ячейку В4Г2 заносим 6 вагонов, исходя из первоначального значения технической нормы погрузки в 48 т/вагон.
Расчетное значение вагонов для В2Г4 равно 12 ед. Однако на предыдущем план имелся недостаток, поэтому корректирвка равна 1 ед.
В ячейку В2Г4 заносим 1 вагон, исходя из первоначального значения технической нормы погрузки в 47 т/вагон.
Итерация №2
Множители λj:
[Груз 3]: 54/53.191=1.015
[Груз 5]: 54/52.128=1.036
Таблица №2 - Скорректированный план погрузки (итерация №2)
| Тип вагонов и их количество | Г1[400] | Г2[500] | Г3[600] | Г4[600] | Г5[700] | Избытки, недостатки |
| B1[11] | 45 | 46 | 54 11/594 | 50 | 54 13/700 | -13 |
| B2[16] | 52.128[49] | 51.064[48] 4/192 | 53.191[50] | 50[47] 1/47 | 50[47] | +11 |
| B3[11] | 51 | 39 | 40 | 50 11/550 | 52 | +0 |
| B4[16] | 57.447[54] 8/400 | 51.064[48] 6/288 | 46.809[44] | 0 | 52.128[49] | +2 |
| λj | - | - | 1.015 | - | 1.036 |
План не оптимален (разноименные строки).
Выбран λmin = 1.015 (Груз 3).
В ячейку В2Г3 заносим 11 вагонов, исходя из первоначального значения технической нормы погрузки в 50 т/вагон.
Итерация №3
Множители λj:
[Груз 5]: 54/52.92=1.02
Таблица №3 - Скорректированный план погрузки (итерация №3)
| Тип вагонов и их количество | Г1[400] | Г2[500] | Г3[600] | Г4[600] | Г5[700] | Избытки, недостатки |
| B1[11] | 45 | 46 | 54 | 50 | 54 13/700 | -2 |
| B2[16] | 52.92[49] | 51.84[48] 4/192 | 54[50] 11/550 | 50.76[47] 1/47 | 50.76[47] | +0 |
| B3[11] | 51.775[51] | 39.593[39] | 40.608[40] | 50.76[50] 11/550 | 52.79[52] | 0 |
| B4[16] | 58.32[54] 8/400 | 51.84[48] 6/288 | 47.52[44] | 0 | 52.92[49] | +2 |
| λj | - | - | - | - | 1.02 |
План не оптимален (разноименные строки).
Выбран λmin = 1.02 (Груз 5).
Итерация №4
Все строки имеют равные знаки, либо равны 0. Конец итераций.
Таблица №4 - Окончательный план.
| Тип вагонов и их количество | Г1[400] | Г2[500] | Г3[600] | Г4[600] | Г5[700] | Избытки, недостатки |
| B1[11] | 45 | 46 | 54 | 50 | 54 11/594 | +0 |
| B2[16] | 54[49] | 52.898[48] 4/192 | 55.102[50] 11/550 | 51.796[47] 1/47 | 51.796[47] | +0 |
| B3[11] | 51.775[51] | 39.593[39] | 40.608[40] | 50.76[50] 11/550 | 52.79[52] | 0 |
| B4[16] | 59.51[54] 8/400 | 52.898[48] 6/288 | 48.49[44] | 0 | 54[49] 2/98 | 0 |
| λj | - | - | - | - | 1.02 |
Общий погруженный груз: 2719 т.
Всего задействовано вагонов: 54
Общий фактически погруженный груз: 2719 т.
Фактически задействовано вагонов: 54
Средняя статическая нагрузка: 2719 / 54=50.352 т/вагон
Типовые задачи, решаемые данным методом
📌 Оптимальная загрузка производственных мощностей (максимизация)
Имеется m групп взаимозаменяемых станков (ресурс Bi) и n видов деталей, которые нужно изготовить в объеме Γj. Коэффициент Pij — это производительность станка i при обработке детали j.
📌 Оптимальное распределение парка транспортных средств (минимизация)
Вместо вагонов и тонн груза могут выступать автомобили разной грузоподъемности, самолеты или морские суда. Ресурс Bi — количество доступных машин типа i, потребность Γj — объем груза на маршруте j. Коэффициент Pij — техническая норма загрузки конкретного автомобиля данным типом груза.
📌 Распределение земельных угодий под сельхозкультуры (максимизация урожая)
Есть m участков земли разного типа площадью Bi и план по сбору n видов сельхозкультур в объеме Γj. Коэффициент Pij — урожайность культуры j на участке земли i.
📌 Распределение работников по видам работ (минимизация трудозатрат)
На предприятии есть бригады (или типы специалистов) численностью Bi, которым нужно выполнить объемы работ Γj. Коэффициент Pij — норма выработки (производительность) бригады i на работе j.