МО-Лекции

	*	0	0		0		2	2	2	4
	P	P		P		P	P	P	P	P
	0	1		2		3	4	5	6	7
P0		2		9 –		2
P	3			4					0
1
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 ).
	*	0	0		0		5	2	2	5
	P	P		P		P	P	P	P	P
	0	1		2		3	4	5	6	7
P		2		7 –		2
0
P	3			4					0
1
P	2 +	5					0	6 –	2
2
P3	5							4		0
P4				3				0		2
P				3 +		3	3		6	6 –
5
P6		5		1				5		5
P						5	2	0 +	3
7
= min{6, 6, 7} = 6;			4( P0 , P2 ,		P5 , P7 ).
	*	0	0		0			3	2	6
	P	P		P		P	P	P	P	P
	0	1		2		3	4	5	6	7
P0		2		1 –		2
P	3			4					0
1
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 ).

140

	*	0	1			0			5	3	2	6
	P	P	P			P			P	P	P	P
	0	1	2			3			4	5	6	7
P0		2 –	0			2
P	3 +		4 –								0
1
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( P	, P ,		P ,	P ,		P ).
			0	1		2	6		7
	*	0	1			0			5	3	2	6
	P	P	P			P			P	P	P	P
	0	1	2			3			4	5	6	7
P0		1	0			2 –
P	4		3								0
1
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( P	, P ,		P ,	P ,		P ).
			0	3		5	6		7
	*	0	1
	P	P	P			P			P	P	P	P
	0	1	2			3			4	5	6	7
P0		1	0			0
P	4		3								0
1
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

141

	Больше нельзя построить нового пути из P								в	P	. Вычитаем эту
							1			n
таблицу из первоначальной и получаем:
		P	P	P	P		P		P		P	P
		0	1	2	3		4		5		6	7
	P0		4	9	7
	P	–4		1							3
	1
	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

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

Q	n 1 x*in		n	x*0 j	4 9 7 5 2 6 7 20 .
	i 0		i 1
В последней таблице из P					можно построить пути только в P							и	P ,
				0							1		2
т. е. имеем множество
				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
Так как
	c03	7 , c16		3, c26		2 , c25		6 , c24		2 ,

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

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

142

КОНТРОЛЬНЫЕ ВОПРОСЫ

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

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

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

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

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

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

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

13.ПАРАМЕТРИЧЕСКОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

13.1.ПОСТАНОВКА ЗАДАЧИ

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

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

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

PP tP ,

12

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

Q(x) PT x max ,

т. е.

Q(x) (P1 t P2 ) x max ,

143

Ax		b ;			(1)
x	0.

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

B

A

C

M1

M PB

	M2	P
		PC

N2

N

N1

Рис. 13.1. Геометрическая интерпретация задачи параметрического линейного программирования

Для t t0 линии уровня целевой функции параллельны MN . При

t t линии уровня параллельны M2 N2 , а при t t –							M1N1 .
							MN по часовой
Изменению t от t до t соответствует поворот

стрелке. При t t0 оптимальное решение соответствует точке А. При t t решение в точке В, при t t – в точке С.

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

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

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

144

13.2. АЛГОРИТМ

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

из границ.

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

функция при данном t0 не ограничена на допустимой области (задача

неразрешима) (случай 20). Рассмотрим сначала случай 10.

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

ентов Pi строки критерия.

Эти коэффициенты можно представить в виде следующей суммы:

Pi	Pi	tPi	, i = 1,…, n.
	1	2
Так как план оптимален для t			t0 , то
	Pi (t0 )	0 ,	i = 1,…, n

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

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

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

tPi1 , Pi2

а для всех	Pi	0
	2

tPi1 . Pi2

145

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

				Pi
	max					1
t				P						(3)
	Pi		0
	2				i
						2
			, если все Pi							0;
							2
					Pi
	min						1
t					P
	Pi		0
	2					i
							2
		, если все Pi								0.
							2

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

			(4)
t t	t	,

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

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

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

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

t	t	и t			t .
Это в том случае, если хотя бы t					или t				.
Исследуем задачу на области t			t . Пусть
			Pi			Pk
t min			1				1	.
			P			P
Pi	0
2			i			k	2
		2

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

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

146

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

t

, т. е. наше

t

становится ле-

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

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

Pi

t min

1

.

P

Pi

0

2

i

2

Если t

или правая граница исходного интервала [t1,t2 ] , t2 t , то

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

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

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

соответствует свой оптимальный план.

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

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

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

Pk	Pk	t0 Pk	2	0	(5)
	1

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

При Pk2 0 условие (5) соблюдается для любого значения пара-

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

		Pk
t t		1	.
1		Pk2
Неразрешима

147

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

	Pk
t t	1	.
1	Pk2

Неразрешима

t

t1

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

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

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

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

И если t1 t2 , то задача неразрешима на всей оси (при t t1 задача неразрешима и при t t2 неразрешима).

				Неразрешима
	Неразрешима
							t
			t1		t2

148

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

	PS
t t2	1	.
	PS2

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

		Неразрешима
		Неразрешима
						t
		t1		t2

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

Аналогично исследования проводятся на луче t t1 .

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

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

Pi

, Pi

и

1

2

Pi1

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

t

P

и

P

в случае 20.

i

S i

i

1

2

2

Pi

2

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

t0 . После

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

P , P

и

Pi1

. Значение

i

i

1

2

Pi

2

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

					Pi
	Тогда при движении вправо строку с				1	заполняют лишь для по-
					Pi
					2
	зиций, соответствующих	Pi	0	. Если все позиции последней строки
		2

оказались незаполненными, то текущий опорный план оптимален для всех t t0 , [t0 , ) . В противном случае индекс минимального элемен-

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

149