Транспортная задача с ограниченными пропускными

Способностями. Метод потенциалов

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

Пропускными способностями (тзо).

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

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

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...,r_1n,...,r_m1,...,r_mn).

Рядом с векторами 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.

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

Свойства ТЗО и основные теоремы.

1. Ранг сложенной из векторов A_ijматрицы А, ограничений транспортной задачи равняется m+n–1, откуда выплывает, что допустимое базисное решение задачи (если он существует) имеет не более m+n–1 перевозок x_ij, которые удовлетворяют условие 0<x_ij<r_ij.

2. Решение ТЗО является базисным, если из его основных коммуникаций невозможно составить замкнутый маршрут (цикл).

3. ДБР x=(x_ij, i=1...,m, j=1...,n) оптимальный тогда и только затем, когда существуют потенциалы u_i, v_jтакие, что

v_j – u_i = с_іj, если x_ij  базисная перевозка

v_j – u_i  с_іj, если x_ij = 0, небазисная перевозка

v_j – u_i  с_іj, если x_ij = r_ij, небазисная перевозка.

Метод поиска выходного ДБР.

Выходной ДБР ТЗО (в отличие от ТЗ без ограничений), если он существует, находится существенно более сложно. Его поиск проводится в два этапа.

Первый этап (предыдущий) напоминает метод минимального элемента в ТЗ без ограничений и в общем случае не дает допустимого решения.

Второй этап содержит ряд итераций метода потенциалов, который применяется к некоторой расширенной ТЗО, построенной за результатами первого этапа.

Выходной ДБР ТЗО. 1 этап.

На множестве невычеркнутых клеточек транспортной таблицы находят клеточку (i1,j1) с минимальными транспортными расходами .

Возлагают .

Если , то вычеркивают i1-йстроку транспортной таблицы.

Если , то вычеркивают j1-йстолбец транспортной таблицы.

Если , то вычеркивают только клеточку (i1,j1) транспортной таблицы.

Если , то в произвольную, невычеркнутую на предыдущих шагах клеточку, которая лежит или в i1-устроке или в j1-устолбце, заносят нулевую базисную перевозку.

После заполнения клеточки во всех случаях величины но уменьшаются на .

Указанные действия выполняют до тех пор, пока не будут вычеркнуты все клеточки транспортной таблицы.

Выходной ДБР ТЗО. II этап.

Пусть X=||x_ij||, i=1...,m, j=1...,n — матрица перевозок, построенная на первом этапе. Положим

x_i,n+1 = a_i – ( x_i1+...+ x_in ), i=1...,m

x_m+1,j = b_j – ( x_1j+...+ x_mj ), j=1...,n.

Пометим

 = x_1,n+1+...+ x_m,n+1 = x_m+1,1+...+ x_m+1,n.

Если =0, то x — выходной ДБР.

Если >0, то исходная ТЗ расширяется за счет фиктивных пунктов производства P_m+1и потребления Q_n+1с a_m+1 = b_n+1 = , где

с_і,n+1 = M, r_i,n+1 = , i=1...,m

c_m+1,j = M, r_m+1,j = , j=1...,n

c_m+1,n+1 = 0, r_m+1,n+1 = ,

M — достаточно большое положительное число  — бесконечность.

Нераспределенные на первом этапе остатки продукта (как по объемам производства, так и по объемам потребления) распределяются по фиктивным пунктам P_m+1и Q_n+1. Соответствующие заполненные клеточки считаются базисными (поскольку пропускные способности соответствующих им коммуникаций неограниченны) и присоединяются к совокупности базисных клеточек заполненных на первом этапе. Если после этого общее количество базисных клеточек не равное (m+1)+(n+1)–1, то множество базисных клеточек дополняют к этому числу за счет незаполненных клеточек или заполненных к пропускной способности, но так, чтобы расширенное множество базисных клеточек не содержало циклов.

Расширенная ТЗ Решается методом потенциалов.

Если в оптимальном решении x*_m+1,n+1=, то, отбрасывая фиктивные пункты, получим выходной ДБР, иначе ТЗО не имеет решений.

Потенциалы.

Потенциалы строк u_{i, i}=1...,m, и столбцов v_j, j=1...,n, определяются как решение системы v_j–u_i=c_ij, где и и j принимают такие значения, что клеточки (і,j) — базисные.

Указанная система содержит m+n–1 уравнений (за числом базисных клеточек) та m+n переменных. Поэтому одна из переменных задается произвольно (например, u₁=0).

Оценки.

Оценки _ijпеременных xijдля всех небазисных клеточек вычисляются за формулой _ij=cij–v_j+u_i (оценки базисных переменных — нулевые).

Текущий ДБР X=||x_ij||, i=1...,m, j=1...,n, оптимальный, когда

_ij=0, если x_ij  базисная перевозка

_ij0, если x_ij = 0, небазисная перевозка

_ij0, если x_ij = r_ij, небазисная перевозка.

Цикл. Метод вычеркивания.

При построении цикла применяется метод вычеркивания. На каждом шагу методу в транспортной таблице вычеркивается либо строка, либо столбец, которые в дальнейшем игнорируются. Зачеркиванию подлежат строки (столбцы), которые содержат только одну базисную клеточку. Невычеркнутые клеточки транспортной таблицы образуют цикл.

Новый ДБР.

Среди всех клеточек (і,j), для присоединяется к совокупности базисных клеточек. которых не выполняется критерий оптимума, избирают клеточку с наибольшим модулем оценки _ij. Пометим такую клеточку через (i₀,j₀).

Пусть клеточка (i₀,j₀), для которой

Находится цикл, что образуется этими клеточками. Цикл разбивается на положительный (C+) и отрицательный (C^–) полуциклы, клеточки которых чергуються одна из одною, причем клеточка (i₀,j₀) относится к положительному полцикла. Вычисляются величины

₁ = min{x_ij} по C^–,

₂ = min{r_ij – x_ij} по C+

 = min{₁ ₂}.

Увеличивают на значение  перевозка x_ijв клеточках полцикла C+и уменьшают их на то же значение в клеточках C^–.

Для клеточки (i₀,j₀) такой, что отмена заключается в том, что она относится к отрицательному полцикла.

В результате выполнения указанных процедур клеточка (i0,j0) вводится к множеству базисных, а клеточка, связанная с , становится небазисной. Если  достигается на клеточке (i₀,j₀), то множество базисных клеточек не изменяется после перераспределения перевозок вдоль цикла на постоянную  и новый ДБР будет иметь ту же самую систему потенциалов и те же самые оценки, что и предыдущий. Поэтому в этом случае после вычисления нового ДБР непосредственно переходят к проверке его на оптимум.

Алгоритм метода потенциалов.

1. Строится выходной ДБР.

2. Дальше метод потенциалов состоит из однотипных шагов, на каждом из которых:

i) Вычисляются потенциалы u_i, i=1...,m, и v_j, j=1...,n;

ii) Вычисляются оценки _ij переменных x_ij, i=1...,m, j=1...,n;

iii) Анализируются найденные оценки _ij. Если _ij0 для x_ij = 0 та _ij0 для x_ij = r_ij, то текущий ДБР оптимальный. В другом случае переходят к улучшению текущего ДБР (п. п. iv) и v)).

iv) Строится цикл.

v) Находится новый ДБР.

Шаг закончен. Переход к пункту и).

Программное обеспечение.

Обучающий модуль, с помощью которого транспортная задача с ограниченными пропускными способностями коммуникаций Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.

Задание.

Решить методом потенциалов транспортные задачи, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи:

1)		6	2	5	3			16	34	15	19
	C =	3	6	9	7	,	R =	13	17	12	4	,
		7	1	6	5			17	19	2	4

а = (74, 33, 19), b = (28, 70, 15, 13);

2)		2	1	5	5			13	10	31	15
	C =	2	3	7	4	,	R =	20	28	7	22	,
		9	5	7	1			19	6	15	8

а = (63, 72, 17), b = (33, 40, 43, 36);

3)		3	6	6	4			5	8	6	4
	C =	3	2	2	6	,	R =	29	24	15	17	,
		1	4	10	7			20	5	10	6

а = (13, 79, 34), b = (49, 30, 22, 25);

4)		5	1	2	7			4	12	5	5
	C =	6	1	8	7	,	R =	20	10	37	10	,
		2	9	4	10			25	10	10	15

а = (20, 76, 54), b = (40, 30, 52, 28);

5)		9	6	6	1			15	10	34	7
	C =	8	10	9	2	,	R =	31	23	20	11	,
		5	9	2	6			11	15	4	10

а = (64, 75, 21), b = (57, 33, 44, 26);

6)		6	4	8	5			20	5	15	12
	C =	2	8	3	2	,	R =	45	20	21	19	,
		1	7	2	8			8	20	12	4

а = (42, 99, 27), b = (68, 40, 30, 30);

7)		5	6	10	3			37	20	7	21
	C =	6	4	7	2	,	R =	5	26	7	11	,
		8	8	3	7			5	20	25	10

а = (78, 37, 53), b = (38, 60, 30, 40);

8)		6	1	9	3			16	30	21	30
	C =	9	2	9	7	,	R =	18	4	5	11	,
		3	2	10	6			30	4	29	15

а = (77, 24, 70), b = (56, 30, 40, 45);

9)		8	4	6	8			12	20	30	20
	C =	8	9	9	6	,	R =	25	4	3	2	,
		9	10	4	7			33	10	30	10

а = (72, 29, 68), b = (65, 24, 50, 30);

10)		1	3	8	7			10	26	23	8
	C =	9	4	5	10	,	R =	6	18	30	5	,
		9	7	2	8			9	2	25	3

а = (53, 45, 38), b = (21, 30, 75, 10).

Ответы:

1) L(x*)= 444. 2) L(x*)= 538. 3) L(x*)= 413. 4) L(x*)= 837. 5) L(x*)= 1091.

6) L(x*)= 700. 7) L(x*)= 800. 8) L(x*)= 885. 9) L(x*)= 1134. 10) L(x*)= 649.

Лабораторная работа 7.