Богданов А. А., Зайцев Е. Н., Кабанов С. А., Староселец В. Г. Многокритериальная оптимизация планов перевозок грузов: текстовая версия

Методы решения транспортной задачи, заключающейся в составлении оптимальных планов перевозок по критерию стоимости, широко известны. Однако на практике могут оказаться не менее актуальными планы перевозок, составленные на основании других критериев (продолжительности перевозок, суммарного времени занятости транспортных средств перевозок и др.). В таком случае каждый из планов окажется наилучшим по одному из критериев, но будет уступать другим планам по остальным. Поэтому требуется обоснованный выбор плана в условиях многокритериальности. Рассмотрим решение такой задачи для простого случая — составления планов перевозок по критериям стоимости и времени. Классическая транспортная задача линейного программирования, как известно, заключается в составлении такого плана перевозок, который обеспечивает все пункты назначения необходимыми перевозками грузов из всех пунктов отправления при минимальных суммарных издержках. Это так называемая транспортная задача по критерию стоимости. Она заключается в составлении плана перевозок , который обеспечивает минимум целевой функции при соблюдении условий.

Кроме того, считается, что все пункты отправления соединены маршрутами со всеми пунктами назначения. Если перечисленные условия не соблюдаются, то задачу можно привести к классической (см., напр.: [1]). Рассмотрим простой пример решения классической транспортной задачи по критерию стоимости из [там же]. Имеются пункты отправления А1, А2, А3 с запасами груза (в условных единицах): а1 = 40, а2 = 80, а3 = 60. Потребности пунктов назначения В1, В2, В3: b1 = 30, b2 = 100, b3 = 50. Стоимости перевозок единицы груза заданы матрицей.

Наилучшим планом перевозок по критерию времени будет считаться тот план, при котором время Т окончания всех перевозок минимально. Обозначим через время, необходимое для перевозки груза из пункта Аi в пункт Вj. Предполагается, что время не зависит от количества перевозимого груза . Математически транспортная задача по критерию времени формулируется следующим образом. Требуется определить план перевозок, при котором. адача (2)–(4) не является задачей линейного программирования. Однако последовательно решая ее по критерию стоимости ( играет роль стоимости перевозок) и запрещая после каждого решения элементы матрицы , для которых можно получить решение задачи (2)–(4). Запрещение проводится заменой данного элемента на достаточно большое число М.