Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Сыктывкарский Государственный Университет им. Питирима Сорокина

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Задачи ЛП и методы их решения

.pdf

Скачиваний:

167

Добавлен:

29.03.2016

Размер:

8 Мб

Скачать

☆

<<< < Предыдущая 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2122 / 2822 23 24 25 26 27 28 > Следующая >>>

209

2. Критический путь (задача о максимальном пути)

Дан связный граф M, N без контуров, t[N]≥ 0[N] – вектор длин дуг. В графе выделены

две вершины i− и i+ . Требуется найти путь из i− в i+ , имеющий наибольшую длину.

Если M, N – сетевой график выполнения некоторого проекта ( M – множество

событий, i− – начальное событие проекта, i+ – конечное событие проекта, N – множество работ проекта, t[N] – время их выполнения), то нахождение самого длинного пути из i−

в i+ (такой путь в сетевом планировании называется критическим) определяет минимально возможное время выполнения всего проекта

Изменением знаков у t[u] возможно свести нашу задачу к поиску кратчайшего пути, но

можно не пользоваться алгоритмом поиска кратчайших путей, а, вводя "правильную" нумерацию вершин (по алгоритму Форда) найти потенциалы за один проход по правилу

(*) , изменяя в нем min на max . Рассмотрим пример.

(1)

(2)
	5						2		18
		(5)					2	4	5
							2		5
								6	6	5
								4		5
	(7)	8						4
		8				10
(4)						10		8		24
(4)		i+				5		8		24
		i+	0	1		5	4		7	8	28
			0	1			4	9	7	8	28
	7							9		4
	7
					7	3			4
						3		7
								7		5
								10		5
								10
	6	(6)					3		6
(3)	6						7		17

В соответствие с алгоритмом Форда в сети отыскивается вершина, в которую не входит ни одна дуга ( Ni+ = . Первая такая вершина i− – начальное событие проекта). Она получает

очередной номер и удаляются все дуги из нее выходящие. Процесс продолжается до исчерпания множества вершин. Имеем граф с "правильной" нумерацией и заданными длинами дуг t[N].

Применяем правило вычисления потенциалов.

v[1]= 0,

{

(

)

[

]

j }

[

]

= max

+ t

, u N

v[2]= v[1]+ 2 = 0+ 2 = 2

v[3]= v[1]+ 7 = 0+ 7 = 7

[ ]

}

{

}

[

]

= max

{

[ ]

+ 5,v

[

]

+ 4,v

= max

0 +

[

{

[

]

+ 3

5,2+ 4,7 + 3

=10

]

= max

+ 4,v

[

]

}

= max

{

+ 4,10+

}

=18

[

]

{

[

+ 8

= max

]

+ 8,v

]

}

= max

{

+ 8,10 +

}

=17

[

]

{

[

]

+ 7

{

}

= max

+ 6,v

[ ]

+ 3,v

[

]

+ 3,v

[

]

+ 6,v

[

]

}

= max

= 24

+ 4

+ 6,7 + 3,10 + 3,18+ 6,17 + 4

[

]

= max

{

[

]

+ 9,v

[

]

+ 5,v

[

]

}

{

}

+ 4

= max 18+ 9,17 + 5,24+ 4 = 28

210 Длина критического пути равна 28. Дуги критического пути выбираются из условия

vj(u) −v i(u) = t[u]

(выделены на рисунке жирными линиями).

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

2. С задачей о дереве кратчайших путей тесно связана задача о кратчайшем дереве

– связывающем дереве с минимальной суммой длин дуг. Она решается при помощи

алгоритма Прима-Краскала, который основан на выделении связывающего дерева с "правильной" нумерацией [9]

3. Максимальный поток в сети

Эта задача является частным случаем СТЗ с ограничением пропускных способностей дуг. Пусть задан связный ориентированный граф M, N , положительный вектор пропускных

способностей его дуг d [N] и две выделенные вершины: i− – "источник" и i+	– "сток".
Требуется найти поток x[N], удовлетворяющий во всех вершинах кроме i− и i+	условию
баланса
a[i, N] x[N]= 0, i M \{i− ,i+},

и при этом поток, выходящий из "источника" i− (равный потоку, входящему в "сток" i+ )

				V = 1		N	− x	N	− .
							i−		i−
Эта сумма называется величиной потока.
Пример.
						Числа около дуг – их пропускные способности,
		3(1)				в	круглых скобках – дуговые потоки. На
		2	1	6(1)		остальных дугах потоки равны нулю.
		2	1	6(1)		Величина потока v = 3
6(1)						Величина потока v = 3
6(1)
		3		3
		3
i-	7(1)	5	4		i+
6(1)				6(1)
6(1)
		7	1	4(1)							3(3)
		5(1)									2(2)	1(1)	6(4)
										6(5)
Сведем задачу к СТЗ. Добавим к графу дугу u											3		3(3)
Сведем задачу к СТЗ. Добавим к графу дугу u									i-		3		i+
из i− в i+ .										7(6)	5(2)	4
										7(6)		4

c[u]=1,	c[N]= 0[N],									6(6)		6(6)
c[u]=1,	c[N]= 0[N],									6(6)
b[i+ ]= −b[i− ]= d [u]=1+V,											7(1)	1(1)	4(4)
b[i+ ]= −b[i− ]= d [u]=1+V,													4(4)

b[M0 ]= 0[M0 ],		M0 = M \{i+ ,i−}.									5(3)
Минимизация стоимости			потоков в		этой сети					u
означает	минимизацию			перевозки	по		дуге			u	[u]=1 x[u]=1
означает	минимизацию			перевозки	по		дуге
										c

211

u (x[u]=1), т.е. максимизацию потока V через исходную сеть.

Запись полученной СТЗ в виде задачи линейного программирования выглядит следующим образом:

f = 0[N] x[N]+1 x[u]→ min

a[i− , N] x[N]− x[							]= −1−V
a[i− , N] x[N]− x[					u		]= −1−V
a[M0 , N] x[N]− 0[M0 ]= 0[M0 ]
a[i		, N] x[N]+ x[					]=1+V
a[i		, N] x[N]+ x[				u	]=1+V
	+
		− x[N]					≥ -d [N]
		− x[N]					≥ -d [N]
		− x[		]			≥ -1−V
		− x[	u	]			≥ -1−V
		x[N]≥ 0[N], x[u]≥ 0
		x[N]≥ 0[N], x[u]≥ 0

[ − ]

[

]

[ + ]

[

]

[

]

Выпишем двойственную

задачу ( g = v

, ρ

– вектор

двойственных переменных)

(1+V ) (v[i+ ]− v[i− ]− ρ [

])− ρ [N] d [N]→ max

v[ j(u)

]− v[i(u)]− ρ [u]≤ 0

v[i ]− v[i ]− ρ [

]≤1

−

ρ [N]≥ 0[N], ρ [u]≥ 0

Пусть теперь V – максимальная величина потока, идущего через сеть. Тогда x[u]=1 и

дуга u является дугой оптимального базисного дерева (на рисунке эти дуги выделены). Базисное дерево имеет такую структуру, что при удалении дуги u оно распадается на две компоненты связности (два поддерева, одно из которых содержит источник i− , а другое –

сток i+ ). Обозначим множества вершин этих поддеревьев через M− и M+ соответственно. Тогда дуги, идущие из M− в M+ и обратно из M+ в M− называются дугами разреза (прямыми (N+ ) и обратными (N− )), разделяющего источник и сток (при их удалении

"разрезаются " все пути из источника в сток). Пропускной способностью разреза называется сумма пропускных способностей прямых дуг разреза

C (M− ,M+ ) = 1		+		+
C (M− ,M+ ) = 1	N		d N	.

Ясно, что величина потока, складывающаяся из величин потоков на путях, идущих из источника в сток, должна быть не больше пропускной способности разреза (иначе поток "не пройдет" через разрез). Отметим, что потенциалы всех вершин из M− равны нулю

(т.к. v[i− ]= 0 и C[N]= 0[N]), а потенциалы всех вершин из M+ равны единице (т.к.

v[i+ ]= v[i− ]+ c[

]= 0+1=1 и

C[N]= 0[N]). Отсюда следует, что для всех дуг u N с

ненулевым потоком (кроме дуг разреза

N+

и N− )

ρ [u]= 0 . Далее, из соотношений

дополняющей нежесткости получаем

] (v[i+ ]− v[i− ]− ρ [

]−1)= 0

(

[

]

)

[

]

1/ − 0 − ρ

−1

= 0 ρ

= 0

212

По теореме двойственности для оптимальных решений прямой и двойственной задач находим

g = (1+V ) (v[i+ ]− v[i− ]− ρ [

])− ρ [N] d [N] = f = x[

] =1

1+V − ρ [N] d [N]=1 V = ρ [N] d [N]

Далее имеем

−

≥

V = ρ [N] d [N]≥ ρ N

d N

+ ρ N

d N

≥

ρ N

d N

≥ 1

= C (M− ,M+ )

Отсюда

следует,

что

при

V == C (M− ,M+ )

прямые дуги разреза должны быть

насыщенными ( x N+

= d N+ ), а на обратных дуговые потоки должны быть нулевыми

( x N

−

= 0 N

− ).

Алгоритм для нахождения максимального потока является вариантом метода потенциалов, однако, реально вводить b[M ],c[N] и дугу u нет необходимости. Основу алгоритма составляет систематический поиск путей из i− в i+ , поток по которым можно

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

Задача о выборе минимального разреза является также основой алгоритма при

распределении ограниченных ресурсов в сетевом графике [9, стр.185]

К сетевым транспортным моделям сводятся многие задачи о покрытиях и паросочетаниях на графах. В частности, доказательство теоремы Дилворта (минимальное число путей, содержащих все вершины графа равно максимальному числу попарно несравнимых вершин) сводится к решению специальным образом построенной СТЗ. Задачи о паросочетаниях в простых (двудольных) графах могут быть сформулированы в виде потоковых задач на сетях. Методы решения задач линейного программирования применимы ко многим задачам с матрицами из нулей и единиц (задача о различных представителях, задача о наилучшем покрытии или разбиении, задача о порядке исключения переменных) [9].

213

Упражнения и задачи

1. Геометрическая интерпретация ЗЛП

1-11. Решить следующие ЗЛП графически или убедиться в их неразрешимости.

. 1.	f = x1 + x2	→ max
	{x1 + x2	≤1

x1 ≥ 0, x2 ≥ 0

2. f = x1 + 2x2 → max

x1 + x2 ≤1

x1 − x2 ≤1 x1 ≥ 0, x2 ≥ 0

4.f = x1 + x2 → max

x1		+ 2x2				≤1
2x				+ x		≤	1
		1			2
			− x2		≤1
x1			− x2		≤1
x			− 2x			≤	1
	1				2
2x				− x	2	≤1
		1			2

x1 ≥ 0, x2 ≥ 0

6.f = x1 + x2 → min

	0	≤ x1			≤ 1
		≤	x2		≤ 2
	0
	0	≤ x1	+ x2		≤ 3

−1		≤ x	− x	2	≤ 0
		1

8.f = x1 + 2x2 → max

3x1		− 2x2	≤ 6
	− x1 + 2x2		≤ 4

	3x1	+ 2x2	≤12

	x	≥ 0
	1

3. f = x1 + 2x2 → max

x1 − x2 ≤1

x1 − 2x2 ≤1 x1 ≥ 0, x2 ≥ 0

5.f = x1 − x2 → min

x1 + x2				≤ 1
x	− 2x				≤		1
1				2
		+ 3x2				≤ 2
2x1
3x		+ 2x				≤ 3
	1				2
x	+ x		2	≥ 1 2
1
x1		≥ 0, x2					≥ 0

7.f = x1 − x2 → max

1		≤ x1 + x2 ≤ 2
		≤ x1 − 2x2 ≤ 3
2
	1	≤ 2x1 − x2 ≤ 2

		x1 ≥ 0, x2 ≥ 0

9.f = 2x1 + x2 → max

− x1	+ x2	≤ 2
x1 + 2x2 ≤ 7
x1 + 2x2 ≤ 7
4x1 − 3x2			≤ 6
4x1 − 3x2			≤ 6
x	≥ 0, x	2	≥ 0
1		2

214

10. f = 7x1

+ 5x2 → min

11. f = −x1 + 2x2

→ min

x + x

≥ 3

− 3x

≥ 0

x1 + 5x2 ≥ 5

x1 − x2 ≤ 3

+ x

≥ 4

− x

= 4

12-15. Используя метод исключения неизвестных и графический способ, найти решения следующих ЗЛП:

12. f = 8x1 − 2x2

− 3x3

→ max

13.

= x1

+ x3 − 7x4

+ x5 → max

− x

+ 3x

+ x

≤ 4

− x

− 2x

= −7

7x1

− 2x3 ≤ 16

x2 − x3 − 4x4 + 6x5 = 24

− x

= 2

+ x

− x

−

+ 7x

= 32

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

xj ≥ 0, j 1: 5

14.

= −x1 + x2

+ x4

+ 3x5

→ min

+ 2x

− x

− 5x

= −5

x1 + x

2 + x3 − 2x4 + 5x5 = −2

− 2x2 + x3 + 3x4 − 3x5 = 6

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

15.

f = x1 + x2 + 2x3

− 9x4

→ max

2x1 − x2 + x3 − 4x4 ≤ 6

+ 2x2

− x3 + 7x4 = 5

5x1 + x2

− 3x4 = 11

+ x

− 3x

= 7

≥ 0,

j 1: 4

2.Базисные решения. Метод полного перебора вершин.

16-23. Найти базисы решений систем, приведенных в условиях (в случае вырожденности решения найти все его базисы).

x − x		=1	3x + 2x			=1
16. 1	2		17.	1	2
x1 ≥ 0, x2 ≥ 0			x1	≥ 0, x2 ≥ 0
X0 = (1, 0)			X0	= (0 ,1/ 2)

215

− x2 = 0

+ x

= 2

= 0

18.

≥ 0, x2 ≥ 0

19. x1 − x2

≥ 0, x

≥ 0

= (0 , 0)

X0 = (1,1)

x + x

+ x

x + x

+ x

= 0

20. x1

− x3

= 0

21. x1

− x2

+ x3

= 0

≥ 0, i 1:3

X 0

= (1/ 2, 0 ,1/ 2)

X 0

= (0 , 0 , 0)

+ x2 + x3 + x4 =1

+ x

= 0

− x2

+ x3

− x4 =1

x1 − x2 + x3 − x4 = 0

22. x1

23.

+ x2 − x3 + x4 = 0

≥ 0, i 1: 4

X 0

= (1, 0 , 0 , 0)

X 0

= (0 , 0 , 0 , 0)

24-27. Найти решения следующих ЗЛП методом полного перебора вершин.

24.

f = x1 + x2

+ x3

→ max

25.

f = x1 + x2

+ 2x3

+ 3x4

→ min

− x

+ x

≤ 4

2x − x

+ x

−

≤ 6

2x1 + x2 + x3 ≤ 3

+ x2 + 3x3 + 4x4 =12

+ x

+ 2x

≤ 6

− x

+ x

− x

= 2

+ 2x2 − x3 ≤ −3

x j ≥ 0, j 1:4

− x1

26.

f = x1

+ 2x2 − 3x3

→ max

27.

= x1 + x2

− 4x3 + 2x4

→ max

− x +

−

+ x

= −4

− x1 + 2x2 + 2x3 ≤1

3 x1 − x2 − x3 + 2x4 ≤ −3

x1 + x2 − x3 = 0

x + 5x

+ x

+ 3x

≤ 4

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

≥ 0,

≥ 0

216

3. Прямой алгоритм симплекс-метода.

28-45. Решить ЗЛП, рассматривая в качестве начального базисного решения приведенное в условии.

28.

f = x1 − 2x2

+ x3 → max

29.

f = x1 + x2 + x3 → max

x + 4x

+ x

= 5

− x + x

+ x

= 2

x1 − 2x2 − x3 = −1

3x1 − x2 + x3 = 0

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

X 0

= (1,1, 0)

X 0

= (0 ,1,1)

30.

f = 2x1 + x2

+ 3x3 + x4

→ max 31.

f = 6x1 + x2

+ 4x3

− 5x4 → max

x + 2x

+ 5x

− x

= 4

3x + x

− x

+ x

x1 − x2 − x3 + 2x4 =1

5x1 + x2 + x3 − x4 = 4

x j ≥ 0, j 1:4

X 0

= (0 , 0 ,1,1)

X 0 = (1, 0 , 0 ,1)

32.

f = x1 + 2x2

+ 3x3 − x4

→ max

33.

f = x1 − 3x2

− 5x3

− x4

→ max

x − 3x

− x

− 2x

= −4

x + 4x

+ 4x

+ x

= 5

x1 − x2 + x3

= 0

x1 + 7x2 + 8x3 + 2x4 = 9

x j ≥ 0, j 1:4

X 0

= (0 ,1,1, 0)

X 0 = (1, 0 ,1, 0)

34.

f = x1 + x2 + x3

+ x4 → max

35.

f = x1 + 2x2 − x3

+ x4 → max

x + 3x

+ x

+ 2x

= 5

x + x

− 2x

+ 3x

2x1

− x3 + x4 =1

2x1 − x2 − x3 + 3x4 = 2

x j ≥ 0, j 1:4

X 0

= (0 ,1, 0 ,1)

X 0

= (0 , 0 ,1,1)

36.

f = x1 + x2 + x3

+ x4

+ x5 → max

2x + 3x

+ 5x

+ 7x

+ 9x

=19

− x2

+ x4 + 2x5 = 2

x j

≥ 0,

j 1:5

= (0 , 0 ,1, 2 , 0)

217

37.

f = −2x1 + x2 + x3 − x4

+ 4x5

+ x6 → max

3x + x

+ 2x

+ 6x

+ 9x

+ 3x

=15

x1 + 2x2 − x3

+ 2x4 + 3x5 + x6 = 5

x j ≥ 0,

j 1:6

X 0

= (1, 0 , 0 , 0 , 0 ,4)

38.

f = x1 + x2 + 2x3

− x4 + x5 − x6 → max

x + 3x

+ x

− 3x

+ 4x

+ x

= 6

x1 − x2 − x3

+ x4

− x6 = 2

x j ≥ 0,

j 1:6

X 0

= (0 , 0 , 0 , 0 ,1,2)

39.

f = x1 − x2

+ x3

+ x4 − x5 − x6 → max

+ x

+ 3x

= 7

− x3

+ x5 − x6 = −2

+ x3

+ x4 + x5 + 2x6 = 5

x j

≥ 0,

j 1:6

X 0 = (0 , 0 , 2 , 0 ,1,1)

40. f = 5x1 + x2 + 2x3 + x4 → max

41.

f = x1 + 3x2 + x3

− x4

→ max

− x

+ x

= 1

+ 2x

+ x

= 3

2x1 + x2

+ x4 = 5

− x1 + x2 + x3

xj ≥ 0, j 1: 4

x j ≥ 0, j 1:4

X0 = (0 , 0 ,1, 5)

X 0

= (0 , 0 ,1, 3)

42.

f = 3x1

+ 7x2 + 4x3 − 3x4 + 2x5

+ 2x6 → max

− x1 + 3x

2 + 2x3 + x4 + x5 + 3x6 = 3

4x1

− 2x2 − 3x3 − 4x4 + x5 − 7x6 = −2

x j ≥ 0,

j 1:6

X 0

= (0 , 0 ,1, 0 ,1, 0)

218

43.

f = x1 + 3x2

+ 2x3 + 4x4

− 2x5 → min

− x1

+ x3 − 2x4

= −2

x2 − x3 + x4 − 2x5 = 0

+ 5x

+ x

= 7

x j ≥ 0,

j 1:5

X 0

= (3,1,1, 0 , 0)

44.

f = 3x1

− 2x2 + x3 + 3x4 + 3x5

→ max

2x1 − x2 + x3 + x4 + x5 = 2

− 4x1 + 3 x2 − x3 − x4 − 3x5 = −4

+ 2 x

+ 3x

+ 5x

= 3

x j

≥ 0,

j 1:5

X 0

= (1, 0 , 0 , 0 , 0)

45.

f = x1 + 3x2 − 2x3 − x4

+ x5 + 3x6 → max

x2 + x3 + x4 − x5 + x6 =1

− x2

− x3 + x4 + 4x5 − 3x6 = −1

+ x2

+ x4 + x5

+ x

x j

≥ 0,

j 1:6

X 0

= (0 ,1, 0 , 0 , 0 , 0)

46-48. Решить следующие ЗЛП, предварительно преобразовав их к канонической форме.

46. f = −x1 + x2

− 2x3 + 3x4 + x5 → max

+ 2x

− x

− 2x

+ x

≤ 3

− x1

− x2 + x3 + 2x4 + x5

≤1

+ x

− x

≤1

x j

≥ 0,

j 1:5

<<< < Предыдущая 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2122 / 2822 23 24 25 26 27 28 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
01.07.202565 Кб1Задания СП часть1 2017.docx
#
01.07.2025174 Кб0Задания СП часть2 2017[75].docx
#
01.05.202562 Кб3Задача инвестиции 5 вариант.docx
#
01.07.202563 Кб1задачи и тесты для студентов.docx
#
28.03.2016152 Кб18Задачи к экзамену.doc
#
29.03.20168 Мб167Задачи ЛП и методы их решения .pdf
#
01.05.202586 Кб15Задачи по пропедевтике.docx
#
23.11.2018455 Кб13ЗАДАЧИ СОКОЛОВ!!!.doc
#
28.03.201698 Кб6задачи.doc
#
28.03.2016692 Кб17Задачник по статистике (соц.-эконом. стат-ка).doc
#
29.03.201621 Мб32Закон Божий. Руководство для семьи и школы.pdf

(2)
	5						2		18
		(5)					2	4	5
							2		5
								6	6	5
								4		5
	(7)	8						4
		8				10
(4)						10		8		24
(4)		i+				5		8		24
		i+	0	1		5	4		7	8	28
			0	1			4	9	7	8	28
	7							9		4
	7
					7	3			4
						3		7
								7		5
								10		5
								10
	6	(6)					3		6
(3)	6						7		17

(2)
	5						2		18
		(5)					2	4	5
							2		5
								6	6	5
								4		5
	(7)	8						4
		8				10
(4)						10		8		24
(4)		i+				5		8		24
		i+	0	1		5	4		7	8	28
			0	1			4	9	7	8	28
	7							9		4
	7
					7	3			4
						3		7
								7		5
								10		5
								10
	6	(6)					3		6
(3)	6						7		17

(2)
	5						2		18
		(5)					2	4	5
							2		5
								6	6	5
								4		5
	(7)	8						4
		8				10
(4)						10		8		24
(4)		i+				5		8		24
		i+	0	1		5	4		7	8	28
			0	1			4	9	7	8	28
	7							9		4
	7
					7	3			4
						3		7
								7		5
								10		5
								10
	6	(6)					3		6
(3)	6						7		17