СПОСОБНОСТЯМИ. МЕТОД ПОТЕНЦИАЛОВ

Постановка транспортной задачи с ограниченными

пропускными способностями (ТЗО).

В пункте Pi (i=1...,m) производится a_i единиц некоторого продукта, а в пункте Qj (j=1...,n) потребляется b_j единиц того же продукта. Транспортные расходы на перевозку единицы продукта из пункта Pi в пункт Qj составляют с_іj единиц. Коммуникация Pi Qj имеет пропускную способность r_ij. Считая, что суммарный объем производства равняется суммарному объему потребления, нужно составить план перевозок продукта, что минимизирует суммарные транспортные расходы.

Математическая модель ТЗО имеет вид:

L(x)= c₁₁ x₁₁ +...+ c_1n x_1n +...+ c_m1 x_m1 +...+ c_mn x_mn ® min

x_i1 +...+ x_in = a_i, i=1...,m

x_1j +...+ x_mj = b_j, j=1...,n

0£x_ij£r_ij, i=1...,m, j=1...,n

a₁ +...+ a_m = b₁ +...+ b_n.

Последнее условие определяет сбалансированную ТЗО.

Кроме векторов перевозок x, производства-потребления b, коммуникаций Aij и транспортных расходов c, определения которых приведены при формулировке обычной сбалансированной транспортной задачи (см. лаб. раб. 5), введем вектор ограничений пропускных способностей коммуникаций

r=(r11...,r1n,...,rm1,...,rmn).

Рядом с векторами x, c, r будем также рассматривать и матрицы X=||x_ij||, C=||c_ij||, R=||r_ij||, i=1...,m, j=1...,n.

Основные определения.

Допустимое решение ТЗО x=||x_ij||, i=1...,m, j=1...,n, базисный, если его перевозкам x_ij, которые удовлетворяют условие 0<x_ij<r_ij, отвечает система линейно независимых векторов коммуникаций A_ij.

Последовательность разных коммуникаций

 

называется маршрутом, что связывает пункты и .

Маршрут, к которому прибавленная коммуникация , называется замкнутым маршрутом (циклом).

Коммуникация PiQj называется основной коммуникацией решения x, если для этого решения 0<xij<rij.

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