MO_conspect

в Pn .

пущено вещества. Если ( Pi , Pj ) входит в один путь, то естественно, что в этом пути по ней нельзя пропустить больше чем cij – вещества в единицу

времени.

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

По этой таблице легко определить любую дугу, по которой протекает поток. Пропускная способность дуг, по которым протекает поток, уменьшилась по сравнению с cij на величину xij , а пропускная способ-

ность противоположно направленной (симметричной) дуги увеличилась на xij , что свидетельствует об отсутствии потока по ней.

Обозначим через U множество вершин сети G , которые достижимы из P0 по некоторому пути в последней таблице, а множество остальных

вершин через V .

Тогда увидим, что все дуги сечения (U ,V ), направленные из U в V , загружены полностью до пропускных способностей (т.е. xij для ( Pi , Pj ),

что Pi U , Pj V , xij cij ), а дуги ( Pj , Pi ) противоположного направления, идущие из V в U в построенном потоке не используются (т.е. xij =0, Pi U , Pj V ), так что величина потока равна:

Q xij x ji cij C(U ,V )

Pi U	Pi U	Pi U
Pj V	Pj V	Pj V

т.е. построенный поток максимален, а (U ,V ) – сечение с минимальной пропускной способностью.

Для			определения полученного максимального потока	x*	,
				ij
i, j		,
	0, n		вычитаем из всех элементов начальной таблицы (4) соответст-

вующие элементы таблицы, полученной на последнем шаге. Положительные значения найденных разностей дают величины потоков xij* по дугам ( Pi , Pj ), а величина потока в сети вычисляются по следующей формуле:

n 1	n
Q x*in	x*0 j .
i 0	j 1

Построим максимальный поток для нашего примера.

111

		*	0	0	0		2	2	1	3
	P0		P1	P2		P3	P4	P5	P6		P7
P0			5	9		7 –
P1		0		4					3
P2		0	5				2	6	2
P3	0 +							4			5 –
P4				1				0			4
P5				3		3	3		6		6
P6			2	1				5			8
P7						0 +	0	0	0
min{ c		–} = min{7, 5} = 5.
		ij
Путь 1( P0 , P3 , P7 ) состоит из дуг ( P0 , P3 ), ( P3 , P7 ).
		*	0	0	0		2	2	1	6
	P0		P1	P2		P3	P4	P5	P6		P7
P0			5 –	9		2
P1	0 +			4					3 –
P2		0	5				2	6	2
P3	5							4			0
P4				1				0			4
P5				3		3	3		6		6
P6			2 +	1				5			8 –
P7						5	0	0	0	+
= min{8, 3, 5} = 3;					2(P0, P1 , P6 , P7 ).
		*	0	0	0		2	2	2	4
	P0		P1	P2		P3	P4	P5	P6		P7
P0			2	9	–	2
P1	3			4					0
P2	0 +		5				2 –	6	2
P3	5							4			0
P4				1 +				0			4 –
P5				3		3	3		6		6
P6			5	1				5			5
P7						5	0 +	0	3
= min{4, 2, 9} = 2;					3( P0 , P2 , P4 ,			P7 ).

112

	*	0	0		0	5	2	2	5
	P0	P1	P2		P3	P4	P5	P6		P7
P0		2	7	–	2
P1	3		4					0
P2	2 +	5				0	6 –	2
P3	5						4			0
P4			3				0			2
P5			3 +		3	3		6		6 –
P6		5	1				5			5
P7					5	2	0 +	3
= min{6, 6, 7} = 6; 4( P0 , P2 , P5 , P7 ).
	*	0	0		0		3	2	6
	P0	P1	P2		P3	P4	P5	P6		P7
P0		2	1	–	2
P1	3		4					0
P2	8 +	5				0	0	2 –
P3	5						4			0
P4			3				0			2
P5			9		3	3		6		0
P6		5	1 +				5			5 –
P7					5	2	6	3	+
= min{5, 2, 1} = 1;				5( P0 , P2 , P6 , P7 ).
	*	0	1		0	5	3	2	6
	P0	P1	P2		P3	P4	P5	P6		P7
P0		2 –	0		2
P1	3 +		4 –					0
P2	9	5 +				0	0	1 –
P3	5						4			0
P4			3				0			2
P5			9		3	3		6		0
P6		5	2 +				5			4 –
P7					5	2	6	4	+
= min{4, 1, 4, 2} = 1;					6( P0 , P1 , P2 , P6 , P7 ).

113

	*		0	1	0	5		3	2			6
	P0		P1	P2	P3	P4		P5	P6			P7
P0			1	0	2 –
P1	4			3					0
P2	9		6			0		0	0
P3	5 +							4 –				0
P4				3				0				2
P5				9	3 +	3			6	–		0
P6			5	3				5 +				3 –
P7					5	2		6	5	+
= min{3, 6,			4, 2} = 2; 7( P0 , P3 , P5 , P6 , P7 ).
	*		0	1
	P0		P1	P2	P3	P4		P5	P6			P7
P0			1	0	0
P1	4			3					0
P2	9		6			0		0	0
P3	7							2				0
P4				3				0				2
P5				9	5	3			4			0
P6			5	3				7				1
P7					5	2		6	7
	Больше нельзя построить нового пути из P1											в Pn . Вычитаем эту таб-
лицу из первоначальной и получаем:
	P0		P1	P2	P3	P4		P5	P6			P7
P0			4	9	7
P1	–4			1					3
P2	–9		–1			2		6	2
P3	–7							2				5
P4				–2				0				2
P5				–6	–2	0			2			6
P6			–3	–2				–2				7
P7					–5	–2		–6	–7

114

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

n		n
Q x* x*			4 9 7 5 2 6 7 20 .
in		0 j
i 0		i 0
В последней таблице из P0				можно построить пути только в P1 и P2 ,
т.е. имеем множество
		U {P , P, P }
						0	1	2
и сечение с минимальной пропускной способностью
(U,V ) {(P , P ),(P, P ),(P , P ),(P , P ),(P , P )}.
	0	3	1		6		2	6		2	5		2	4
Так как
c 7	, c 3,			c	26	2 ,		c	25	6	, c	24	2 ,
03		16

то минимальная пропускная способность транспортной сети:

C(U,V ) 7 3 2 6 2 20 .

Контрольные вопросы

1.Что такое транспортная сеть? Поток по дуге? Поток в сети?

2.О чем говорит теорема Форда-Фалкерсона?

3.Как строится первоначальная таблица?

4.Как отыскивается новый путь в транспортной сети?

5.Как определить, что нельзя найти нового пути с положительной пропускной способностью?

6.Как найдутся потоки по дугам, соответствующие максимальному поттоку в транспортной сети?

7.Как найти сечение с минимальной пропускной способностью и величиину максимального потока?

13. Параметрическое линейное программирование

13.1.Постановка

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

115

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

Рассмотрим частный случай, когда от параметра t зависят только коэффициенты целевой функции [8]:

PP t P ,

12

ався задача выглядит следующим образом:

Q(x) P T x max ,

т.е.

Q(x) (P1 t P2 ) x max

				;
Ax b
					(1)
x	0.

Рассмотрим геометрическую интерпретацию такой модели.

B

Для

t t0

линии

A

уровня целевой

функ-

ции

параллельны

MN .

При t t

линии уровня

параллельны M2 N2 ,

а

C

M1

при t t

– M1N1 .

Изменению t

от t

M

PB

до

t соответствует поворот

M2

P

PC

MN по часовой стрел-

N2

ке.

При

t t0

опти-

мальное

решение

соот-

N

ветствует

т.

А.

При

t t

N1

, решение

в

т.

В,

при t t

– в т. С.

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

Совокупность значений параметра t , при которых данный опорный план оптимален, называют множеством оптимальности этого плана.

Для исследования параметрической модели воспользуемся алгоритмом метода последовательного улучшения плана.

116

13.2. Алгоритм

Задаемся каким-либо t0 . Если в модели область изменения параметра t ограничена, т.е. t [t1,t2 ], то в качестве t0 можно взять одну из границ.

После конечного числа шагов алгоритма либо придем к оптимальному плану задачи при t0 (случай 10), либо убедимся, что целевая функция

при данном t0 не ограничена на допустимой области (задача неразрешима)

(случай 20).

Рассмотрим сначала случай 10.

Случай 10 . Если мы ищем max линейной формы, то признаком оптимальности опорного плана является неотрицательность коэффициентов

P	строки критерия.
i
	Эти коэффициенты можно представить в виде следующей суммы
	Pi ' Pi ' t Pi		' ,	i = 1,…, n.
	1		2
	Так как план оптимален для	t t0 , то
	Pi '(t0 ) 0,			i = 1,…, n,

и, следовательно, совместна система неравенств (из неотрицательности коэффициентов)

Pi	' t Pi	' 0 , i = 1,…, n .	(2)
1	2

Для всех Pi2 ' 0 неравенства этой системы можно переписать в виде

t Pi1 ' , Pi2 '

а для всех Pi2 ' 0

t Pi1 ' . Pi2 '

Введем следующие обозначения:

Pi1

'

max

t

P ' 0

i2

Pi2

'

(3)

Pi2 ' 0;

, если все

Pi1

'

min

P ' 0

Pi2

t i2

'

Pi2 ' 0.

, если все

Таким образом, можно утверждать, что если

t t

t

,

(4)

117

то найденный оптимальный план для t0 будет оставаться оптимальным для всех t, удовлетворяющих неравенству (4).

Если область изменения [t1,t2 ] параметра t, заданная в технических

условиях, не накрывается отрезком [t, t] , то возникает необходимость исследования параметрической модели для

t t

и

t

t

.

t .

Это в том случае, если хотя бы

t

или

Исследуем задачу на области t

t

. Пусть

Pi1

'

Pk1

'

t min

P ' 0

Pi2

Pk2

'

i2

'

Тогда в опорный план (в базис) необходимо ввести переменную, соответствующую столбцу k ( xk ).

Просматривается столбец коэффициентов в таблице. Если среди них

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

ве разрешающего элемента.

что t'

Для нового плана получаем,

t

, т.е. наше t становится левой

границей нового интервала.

Находится правая граница

Pi1

'

t ' min

.

P ' 0

Pi2

i2

'

' или правая граница исходного интервала

[t ,t

] ,

t t' ,

Если t

2

1

2

то исследование в этом направлении прекращается.

Аналогично проводится исследование параметрической модели для t t . В этом случае в базис вводят переменную, соответствующую t .

В результате исследования за конечное число итераций ось t ( , )

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

118

t t0

Случай 20. Необходимо специально остановиться на этом случае, когда в результате предварительного анализа при обнаружено, что

целевая функция не ограничена.

Это соответствует тому, что коэффициент в строке целевой функции

Pk	' Pk ' t0 Pk	' 0	(5)
	1	2

и все коэффициенты в k-м столбце неположительны.

При Pk2 ' 0 условие (5) соблюдается для любого значения параметра, а значит задача неразрешима на всей оси t.

Если Pk2 ' 0, то (5) выполняется для всех значений

t t1 Pk1 ' . Pk2 '

Если Pk2 ' 0 , то (5) выполняется при

t t1 Pk1 ' . Pk2 '

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

Анализ параметрической задачи на луче t t1 начинается с решения задачи линейного программирования при t t1 , отправляясь с имеющегося базиса. Если в этом случае в процессе решения будет найден оптимальный план при t1 , то решение далее продолжается как и случае 10.

Если и сейчас процесс окончился выявлением неразрешимости зада-

чи:

PS ' PS1 ' t1 PS2 ' 0

119

и в столбце коэффициентов a jS 0,	j 1,..., n , то дальнейший анализ за-
висит от знака PS2 ' . Если PS2 ' 0 , то задача неразрешима всюду.
Если PS2 ' 0 , то задача неразрешима при
t t			PS1	'	.
	2		PS2	'
И если t1 t2 , то задача неразрешима на всей оси (при						t t1 задача
неразрешима и при t t2 неразрешима).

Если PS2 ' 0, то задача неразрешима при

t t2 PS1 ' . PS2 '

И если t2 t1 исследования продолжаются при t t2 .

неразрешима, то она вообще неразрешима на всей оси. Аналогично исследования проводятся на луче t t1 .

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

строки критерия вводятся три дополнительные строки Pi

', Pi

'

и

Pi

'

для

1

1

2

Pi2

'

случая 10 и две строки P ' t

S

P ' и

P ' в случае 20.

i

i

2

i

1

2

Процесс решения начинается с анализа для некоторого t t0 . После

выявления случая 10, вводят строки

P ', P ' и

Pi1

'

.

t

стараются вы-

0

i

i

Pi2

'

1

2

брать таким образом, чтобы при анализе движение по оси t происходило в одном фиксированном направлении.

120