Особенности решения транспортных задач с неправильным балансом

До сих пор рассматривались транспортные задачи с правильным балансом. Однако на практике чаще встречаются задачи с неправильным балансом. Каковы особенности их решения?

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

Очевидно, что в этом случае при составлении оптимального плана перевозок часть запасов поставщиков, равная b_{n +1}= - , останется не вывезенной. Поэтому в системе ограничений транспортной задачи первую группу уравнений следует заменить неравенствами , i =1,2,..., т.

Вторая группа уравнений остается без изменения, так как запросы всех потребителей удовлетворяются полностью. Для приведения к канонической форме в неравенства вводят дополнительные переменные х _{1(п+ 1)}, х _{2(п +1)},…, х_{т (п+ 1)}, в результате первые т ограничений задачи принимают вид , i =1,2,..., т.

В целевую функцию дополнительные переменные не входят (входят с нулевыми коэффициентами). Математическая модель задачи принимает вид

F (X) = + → min,

, i =1,2,..., т,

, j= 1, 2,..., п.

х_ij ≥ 0, i =1,2,..., т, j= 1, 2,..., п.

Запишем необходимое и достаточное условие разрешимости задачи:

= .

Отсюда - - = b_{n+ 1} .

Следовательно, чтобы задача в рассматриваемом случае имела решение, необходимо ввести фиктивного потребителя с запросами b_{n+ 1}, равными разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза с_{i ( n +1)} = 0 i.

2. Аналогично в случае, когда суммарные запросы потребителей превосходят суммарные запасы поставщиков, т.е. < , часть запросов потребителей, равная а_{т+ 1} = - , останется не удовлетворенной. Поэтому вторая группа уравнений системы ограничений транспортной задачи заменяется неравенствами , j= 1, 2,..., п.

После введения дополнительных переменных х _{(т +1)1}, х _{(т +1)2},...,. х _{(т +1) п} в эти неравенства математическая модель задачи примет вид

F (X) = + → min,

, i =1,2,..., т,

, j= 1, 2,..., п.

х_ij ≥ 0, i =1,2,..., т, j= 1, 2,..., п.

Для того чтобы задача имела решение, необходимо и достаточно, чтобы

= = .

Отсюда = - - = а_{т+ 1.}

Следовательно, чтобы в этом случае задача имела решение, необходимо ввести фиктивного поставщика с запасами а_{т+ 1}, равными разно суммарным запросам потребителей и запасам поставщиков, и нулевыми стоимостями перевозок единиц груза с _{(т +1) j} = 0 j.

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