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

Простейшая транспортная задача (Т-задача)

Эта задача является основополагающей для всех транспортных задач. В общем случае исходными данными являются:

m – число пунктов отправления (ПО) или производства;

n – число пунктов назначения (ПН) или потребления;

C_ij – затраты на перевозку единицы груза из пункта i в пункт j, " ij;

a_i – количество груза в пункте i, " i (возможности ПО);

b_j – потребность в грузе в пункте j, " j.

Критерием задачи являются суммарные затраты на перевозку. Безотносительно к значениям a_i и b_j модель записывается в виде

Однако такая запись модели корректна только тогда, когда Напомним, что задача, в которой суммарные потребности равны суммарной возможности, то есть

(1)

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

(2)

(3)

(4)

" X_ij ³ 0. (5)

Элементы модели:

– матрица перевозок;

– матрица транспортных затрат;

a =(a₁, a₂,..., a_m) – вектор возможностей ПО;

b =(b₁, b₂,..., b_n) – вектор потребностей ПН.

Отметим особенности рассматриваемой задачи:

¨ Модель содержит две группы условий, размерность которых равна соответствующему числу ПО и ПН; число переменных равно произведению m ´ n;

¨ Все коэффициенты при переменных в условиях (3), (4) равны единице;

¨ Каждая переменная входит в условия ровно 2 раза, один и только один раз в группу (3) и также один раз в группу (4);

¨ Задача имеет простые условия разрешимости, которые определяются следующей теоремой.

Теорема.

Для разрешимости Т-задачи необходимо и достаточно, чтобы она была сбалансированной.

Замечание. Теорема справедлива при конечных значениях С_ij.

Приведем доказательство.

Необходимость доказывается исходя из того, что задача (2)-(5) разрешима. В этом случае все условия задачи выполняются. Просуммируем условия (3) по i, а условия (4) по j:

Так как левые части равенств равны, то равны и правые. Таким образом, в разрешимой задаче всегда имеет место формальный баланс возможностей и потребностей.

Достаточность доказывается конструктивным способом.

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

Ограниченность переменных снизу задана явно, а ограничение сверху следует из конечности всех a_i и b_j, больше которых переменные быть не могут. Следовательно, множество ограничено.

Теперь покажем, что оно непустое. Для этого достаточно найти хотя бы одно допустимое решение. Одно из таких решений всегда можно построить, если задача сбалансирована, следующим образом:

(6)

Очевидно, что оно неотрицательно. Остается проверить выполнение основных условий задачи. Подставив (6) в левую часть(3), получим:

Þ решение удовлетворяет условиям (3).

Подставив первый вариант (6) в (4), также убеждаемся в выполнении этих условий:

.

Таким образом, допустимое множество сбалансированной задачи непустое и ограниченное, а, значит, задача всегда разрешима. ▲

Условия (3), (4) – линейно зависимы из-за сбалансированности задачи. Действительно, пусть известны все равенства (3) и (n -1) равенство (4). Просуммируем отдельно первые и вторые и затем из первой суммы вычтем вторую. В результате получим недостающее равенство, описывающее пункт потребления, не включенный в исходную систему (4). Можно строго показать, что число линейно-независимых уравнений или, иначе, ранг системы (3), (4) равен m+n- 1. Следовательно, такую размерность имеют базис и базисное решение Т-задачи.

1.2. Транспортная задача с ограниченными пропускными способностями (T_d - задача)

Отличается от предыдущей задачи учетом ограничений на пропускные возможности коммуникаций. В реальных условиях пропускные способности дорог, воздушных коридоров, линий связи и т.п. всегда ограничены сверху. Если известно, что фактическая загрузка будет заведомо меньше, задача рассматривается как простейшая. В противном случае учет этих ограничений приводит к более сложной транспортной задаче, называемой Т_d-задачей. Ее модель имеет вид

(7)

(8)

(9)

0 £ X_ij £ d_ij, " i,j, (10)

где d_ij –пропускная способность коммуникации i j.

Ограничения (10) вносят существенные коррективы в свойства задачи. Из особенностей модели, присущих Т-задаче, сохраняются все, кроме последней. В Т_d-задаче условие сбалансированности не является достаточным для разрешимости задачи. Более того, в число необходимых условий существования решения помимо его входят еще две группы условий, отражающих физическую реализуемость решения:

(11)

(12)

Они требуют, чтобы суммарная пропускная способность коммуникаций, входящих в каждый ПН была не меньше объема поставок, а выходящих из ПО – не меньше количества вывози­мого груза. Если хотя бы одно из них нарушается, задача заведомо неразрешима.

Однако и выполнение всех необходимых условий не гарантирует разрешимость Т_d-задачи. Например, условия (1), (11) и (12) выполняются для транспортной сети, показанной на рис. 1, что легко проверить. Но задача неразрешима, так как невозможно поставить во второй пункт назначения 8 единиц груза.

В рассмотренных задачах по умолчанию предполагалось, что для отправителей и получателей грузы неразличимы – это задачи с однородным грузом. Если в перевозках участвуют несколько видов груза с одинаковыми или различными транспортными затратами, исходную многопродуктовую задачу можно разбить на задачи с однородным грузом (по числу видов).

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

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

После таких преобразований модель задачи записывается аналогично случаю с однородным грузом, а ее размерность определяется числом пунктов, заменяющих исходные.

Для разрешимости задачи необходимо кроме сбалансированности, чтобы по каждому виду груза суммарные возможности были не меньше суммарной потребности (без учета взаимозаменяемой). Однако и при выполнении всех необходимых условий возможна неразрешимость задачи из-за присутствия запрещенных перевозок.

Дата добавления: 2014-01-11