Закрытая и открытая модели транспортной задачи

Таблица 5.1

Поставщик	Потребитель	Запас груза ai
В1	В2	…	Вп
Затраты на перевозку единицы груза
А1		с11		с12	…		с1n	a1
x11		x12		x1n
А2		c21		c22	…		c2n	a2
x21		x22		x2n
…	…	…	…	…	…
Ат		cm1		cm2	…		cmn	am
xm1		xm2		xmn
Потребность в грузе bj	b1	b2	…	bn

 

Экономико-математическая модель ТЗ должна отра­жать все условия и цель задачи в математической форме. Так, переменные х_ij должны удовле­творять ограничениям по запасам, потребностям и услови­ям неотрицательности. В математической форме эти усло­вия можно записатьтак:

(5.1)

Цель ТЗ – минимизировать общие затраты на реали­зацию плана перевозок, которые можно представить функцией

. (5.2)

Итак, математически ТЗ ставится так. Даны система ограничений (5.1) и линейная функция (5.2). Требуется среди множества решений системы (5.1) найти такое неотрицательное решение, при котором линейная функция (5.2) принимает минимальное значение (минимизируется).

Будем называть план перевозок Х=[х_ij] допусти­мым, если он удовлетворяет ограничениям (5.1).

Допустимый план перевозок, доставляющий минимум целевой функции (5.2), называется оптимальным.

Теорема 5.1 (о существовании допустимого плана).Для того чтобы ТЗ имела допустимые планы, необходимо и достаточно выполнение равенства

(5.3)

Доказательство. Просуммировав в распредели­тельной табл. 5.1 элементы х_ij раздельно по индексам i и j, получим:

; .

Очевидно, что суммируются все элементы х_ij как по строкам, так и по столбцам, различие лишь в перестановке этих элементов. Однако от перестановки слагаемых сумма не меняется. Поэтому равенство является необходимым условием разрешимости ТЗ.

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

(5.4)

Поскольку , то и А > 0, а поэтому и все х_ij ≥ 0.

Покажем, что переменные (5.4) составляют допусти­мый план. Этот набор неотрицательных чисел будет со­ставлять допустимый план тогда, когда он удовлетворяет системе ограничений (5.1). Просуммируем равенства (5.4) по индексу i. Получим

.

Аналогично, суммируя равенства (5.4) по индексу j, получаем

.

Следовательно, набор чисел удовлетворяет системе ограничений задачи, а потому является допусти­мым планом.

Модель ТЗ называют закрытой, если суммарный объем груза, имеющегося у поставщиков, равен суммарному спросу потребителей, т. е. выполняется равенство

.

Если для ТЗ выполняется одно из условий:

или ,

то модель задачи называют открытой.

Для разрешимости ТЗ с открытой моделью необхо­димо преобразовать ее в закрытую. Так, при выполне­нии первого условия необходимо ввести фиктивный (п+1)-й пункт назначения В_п+1, т. е. в матрице задачи предусматривается дополнительный столбец. Спрос фик­тивного потребителя полагают равным небалансу, т. е.

,

а все соответствующие тарифы – одинаковыми, чаще всего равными нулю.

Аналогично при выполнении второго условия вводится фиктивный поставщик.

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

Теорема 5.2 (о ранге матрицы). Ранг матрицы А тран­спортной задачи на единицу меньше числа уравнений: r(А)=т+п-1.

Доказательство. Матрица системы ограничений имеет вид:

.

Обозначая i-ю строку через p_i, имеем:

.

Отсюда видно, что любая строка матрицы может быть представлена в виде линейной комбинации остальных строк, следовательно, не меняя ранга, можно вычеркнуть, например, последнюю строку. Минор (т+п-1)-го порядка получившейся матрицы, составленный из коэффициентов при х₁₁, х₁₂, …,х_1п, х_2п, …, х_тп, будет отличен от нуля, что и доказывает теорему.