Задачи с неоднородным грузом

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