методичка МО часть 1

Лабораторная работа 5

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

Вопросы:

1.Определение двойственного базисного плана.

2.Определение коплана.

3.Определение псевдоплана.

4.Критерий оптимальности.

5.Достаточное условие пустоты множества допустимых планов

6.Алгоритм двойственного симплекс-метода.

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

условий b.

Алгоритм

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

z c x max,

( A А )x b,

x 0

(5.1)

Б

Н

(обозначения те же, что и в лабораторной работе 2, АБ Em ).

Двойственная к (5.1) задача (см. лабораторную работу 4) имеет вид

T b y min

A

y c

,

(5.2)

Б

Б

A

y c

Н

.

Н

Предположим теперь,

что

y c

Б

начальный

AН cБ сН , тогда вектор

двойственный базисный план задачи (5.1).

Ему соответствует

базисный коплан ( Б 0, Н

сН )

и

AН cБ

базисный псевдоплан

( Б

b, H

0).

1. Строим начальную двойственную симплекс-таблицу.

2. Проверяем выполнение критерия оптимальности. Если

Б

0,

то

вектора y, – оптимальные планы задач (5.2),

(5.1), а если j

0,

j IБ ,

то идем к пункту 3.

3. Проверяем достаточное условие отсутствия прямых планов. Если

j 0 ,

j IБ

и

aij 0,

i I ,

(5.3)

31

то ограничения задачи (5.1) несовместимы. Если условие (5.3) не имеет места, то переходим к пункту 4.

1.Совершаем двойственную симплекс-итерацию – переход к новому базисному коплану:

а) строим новый базис с индексным множеством где p и q находятся из соотношений:

	q	min j	,	p		p	min (		i
						aqp			aqi
		j JБ					i I Н
							a	q i 0

I `	(I	Б
Б

) .

\ q)

p

,

Элемент таблицы aqp

– разрешающий.

б) строим новую двойственную симплекс-таблицу, совершая основное симплексное преобразование по элементу aqp :

'

a

qj

q

, q

aqj

a

a

qp

qp

'

aij

a

* a

ip

qj

,

aij

a

qp

'

p

* a

qi

,

j

j

a

qp

,

i

j

I

		a	ip
i		q*
		a	qp

.

,	i I , i q,

2. К новой таблице применяем п.2 алгоритма и т.д.

Замечание

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

Пример. Решить двойственным симплекс-методом задачу:

z 2x				x			2	max	(5.3)
			1
x	x	2	x		3	2,
1

4x2 2x5 10,

2x2 x3 x4 1,

x	i	0,	i 1,5

Решение

1. Приводим задачу (5.3) к виду (5.1):

32

	2		1			0	0	0 x max
1			1	1			0	0		2
	0		2		0		0	1	X		5
	0	2		1			1	0			1
	x 0,			J	Б	{1, 5, 4}

2. Строим двойственную задачу к задаче (5.4):

(5.4)

2 y		5 y		2	y	3	min
1
y		2,
1
y	2 y		2	2 y		3	1,
1

y1 y3 0, y2 0,

y3 0.

Вектор	y CБ	2, 0, 0		является невырожденным двойственным
базисным, так как AH CБ			CH :
		'

1*( 2) 2*0 2*0 2 1,

1*( 2) 0*0 1*0 2 0.

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

A' y c (0, 3, 2, 0, 0) ,

=(-2, 0, 0, -1, 5).

Базис

a
1
a	5
a	4

Б	a1	a2	a3			a4	a5
-2	1	-1		-1		0	0
5	0	2	0			0	1
-1	0	-2	-1			1	0
	0	3	2			0	0
		3	2

33

a	3	2	-1	1	1	0	0
a	5	5	0	2	0	0	1
a	4	1	-1	-1	0	1	0
			2	1	0	0	0

4. Последняя таблица задает оптимальный план задачи (5.3), так как Б ≥ 0.

Ответ:

x	0	(0, 0, 2, 1,	5),

c' x	0	0.

Задание. Двойственным симплекс-методом решить следующие задачи:

1. z x	10 x	2	max
1

2x1 2x2 2x5 1,

2x1 2x2 x3 2,

4x1 2x2 x4 1,

x	i	0, i 1, 5

2. z 2x	2	4x	4	max

6x1 3x2 1,

3x2 x3 3x4 2, 6x2 12 x4 x5 2,

x	i	0, i 1, 5

3. z 2x								3	x		4				max
2x				2x	3		2x			4				1,
		1
4x			2	32 x			3		4x				4		7,
8x		3		16 x		4			4x			5			1,
x	i		0, i		1, 5

4. z						1		x					1	x			max
							2			2			3			4
5x				5x			2	5x				4				2,
		1
20 x				2	5x			3	25x						4		1,
15x			2		30 x				4		10 x					5		1,
x	i	0, i 1, 5

5. z		1	x x				max	6. z			1	x			x			max
	3			1		4				2				1			5
12 x1	6x2			18x4			1,	21x1 7x3 28x5											1,
12 x1	6x3			18x4			1,	28x 7x					2	49 x				5		2,
										1
3x1 6x4 3x5						1,		14 x 28x						4	49 x				5	5,
										1
xi 0, i
				1, 5				x	i	0, i				1, 5

34

	7. z							1			x					3x									max
								2						2									4
	5x			5x					2		4x							4			1,
		1
	5x		2	x						2x							4		1,
							3
	10 x					2	x					4			x					5					1,
	x	i	0, i 1, 5
	9. z								1			x				2x										max
									2						3									4
	2x				3	8x							4		2x							5			1,
	6x		2	4x						3	2x								4		3,
	2x			2x						3	6x								4		1,
			1
	x	i	0, i							1, 5
	11. z									1				x			2x									max
										2						2									5

x2 x3 x5 3, x1 2x2 4x5 1,

x2 x4 x5 1,

x	i	0, i 1, 5
13. z x				1	x			max
		1	4				3
4x1 4x2 4x3						1,

4x1 4x3 4x4 7,

64 x1 4x3 4x5 39,

xi 0, i 1, 5

8. z x				1	x		max
						4
	1			4
4x	32 x	4	4x			5	3,
1

4x1 4x2 4x4 2,

8x1 4x3 4x4 5,

x	i	0, i 1, 5

10. z x											5x							4			max
									1
12 x				3x							4		3x									8,
		1																		5
3x			3x			3			9x							4		8,
	1
x		3x			2		3x							4		3,
1
x	i	0, i 1, 5
12. z									1	x								1				x		max
																							2
									3			1						2
4x				2x						2						2x			5			3,
		1
2x		4x					2		2x								3	1,
	1
2x				2x						2		2x							4			5,
		1
x	i	0, i						1, 5
14. z									2	x					x							max
									3				2							4

4x2 4x3 8x4 3, 2x1 4x2 6x4 1,

8x2 2x4 4x5 7, xi 0, i 1, 5

35

15. z x																						1		x				max
														2								2				5
5x				5x						2			20 x											5		2,
	1
5x					2		10 x											3			5x						5		3,
5x		2		15x								4				15x									5			1,
x	i		0, i 1, 5
17. z												1					x							2			x				max
												3								2				3						4
2x				2x							2			2x									4		5,
		1
x	2		3x					4			x								5			1,
x				2		x			3			x									4	2,
x	i		0, i								1, 5
19. z												2					x					5x									max
																													3
												3								1
6x							6x								3				6x							4		1,
					1
12 x						6x							2			18x										3		11,
				1
24 x								6x											3		6x							5		7,
						1
x	i		0, i								1, 5

21. z 17 x1 x3 max

7x1 7x3 7x5 4,

x1 x2 x3 1,

63x1 7x4 9,

xi 0, i 1, 5

16. z 5x					4x	2	max
			1
x	2x	2	x	3	2,
1

4x1 3x2 x4 12,

4x1 4x2 x5 10,

	x	i	0, i 1, 5
	18. z					1		x			7			x		max
															4
						2		1			2
	4x			2x			3	2x				4		7,
			1
	2x		2x		2	2x				4	1,
		1
	6x			2x			4	2x				5		5,
			1
	x	i	0, i		1, 5
	20. z x								1		x			max
							2		6				3

6x2 3x3 3x4 1,

6x2 6x3 6x5 7, 3x1 3x2 9x3 1,

x	i	0, i 1, 5
22. z 5x			3	x		max
		1	2		4
3x1 3x3 3x4			1,

2x1 2x4 2x5 1,

4x1 2x2 2x4 1,

xi 0, i 1, 5

36

23. z 3x						2	2x				4	max
3x 3x					4	2,
		3
2x	2	2x	4	2x					5	2,
5x		2x	2	x				4	1,
1
x	0, i 1, 5
i
25. z x					2	3x					max
										3
2x		3x	2	2,
	1
3x	2	x	2x						2,
		3						5
3x	2	x	2x					4	5,
		3
x	0, i 1, 5
i

24. z 2x	2	2x	3	max

6x1 2x2 6x3 2,

2x2 3x5 5,

2x2 3x3 3x4 1,

x	i	0, i 1, 5
26. z 2x			2	3x	5	max

x2 2x3 x5 2, 2x2 x4 1,

x1 3x5 1,

x	i	0, i 1, 5

37

Лабораторная работа 6

Решение матричной транспортной задачи методом потенциалов

Вопросы:

1.Постановка транспортной задачи.

2.Математическая модель транспортной задачи.

3.Условие общего баланса.

4.Метод минимального элемента.

5.Метод потенциалов.

	Постановка задачи. Имеется			m	пунктов			производства
определенного			вида продукции с заданным		объемом		производства
ai	0,	i 1, m	и n пунктов потребления этой продукции в объемах
bj	0,	j 1, n.	Известна стоимость перевозки,		единицы продукции из i-
го пункта производства в j-й пункт потребления – cij , i						1, m		, j	1, n.
Требуется найти такой план перевозок				x (xij ,	i 1, m ,		j 1, n) , чтобы
продукция со всех пунктов была вывезена:

n
x	a	,	i 1, m
ij	i
j 1

(6.1)

Запросы всех пунктов потребления были удовлетворены:

m				(6.2)
xij	bj ,	j	1, n
i 1

И транспортные расходы были минимальными:

			m	n
			c x min .
			i 1	ij ij
				j 1
Здесь	xij	–	количество		продукции, перевозимое
производства в j-й пункт потребления. Ясно, что
		x	0 ,	i 1, m ,	j 1, n
		ij

(6.3)

из i-го пункта

(6.4)

Задача (6.1) – (6.4) является специальной задачей линейного программирования.

Для существования ее решения необходимо и достаточно выполнение

	m	n
условия общего баланса:	ai	bj	(количество производимой
	i 1	j 1
	38

продукции равно количеству потребляемой) и в этом случае применим метод потенциалов.

Алгоритм

При решении задач (6.1) – (6.4) используют транспортные таблицы с

множеством клеток

U {(i, j),

i 1, m,

j 1, n}.

	b1	b2	…	bn
a1	c11	c12	…		c1n	u1
	x11	x12		x1n
a2	c21	c22	…		c2n	u2
	x21	x22		x2n
…	…	…	…	…		…
am	cm1	cm2	…		cmn	um
	xm1	xm2		xmn
	v1	v2	…	vn

1. Построение начального базисного плана перевозок методом минимального элемента.

Метод минимального элемента. Находим

минимальной стоимостью перевозки c		min cij
i	j	(i , j ) U
1	1

в таблице клетку с

.

Полагаем

x		a
i	j	i
1	1	1

строку i1

перевозку в этой клетке

(x	b	)	,	то исключаем из
i	j	j
1	1	1
(столбец		j1		), а число b	(число
					j
					1

		min{ a	,b }. Если
i	j	i	j
1	1	1	1

дальнейшего рассмотрения

a	) заменим на	b	x		(на
	i		j	i	j
	1		1	1

ai	xi	j ). Если ai		=	bj	, то исключаем из рассмотрения либо строку		i1 ,
1	1	1	1		1
либо столбец			j1 .
С уменьшенной таблицей поступаем аналогично. Через							n m 1 шагов

будут построены перевозки	x	, (i, j) U	Б	{(i		, j	), k	1, n m 1}
	ij				k	k
базисное множество клеток.	Полагаем,			xij	0, (i, j) UН				U \ UБ

–

–

множество небазисных клеток.

2. Решение задачи (6.1) – (6.4) методом потенциалов.

1) Находим	потенциалы vj , j		1, n	,	ui , i 1, m
транспортной таблицы, решая систему:
ui	vj cij ,	(i, j) UБ

строк и столбцов

(6.5)

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

39

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

2) Вычисляем оценки для небазисных клеток:

	ij	u	i	v	j	c	,	(i, j) U	Н
						ij

.

3) Проверяем критерий оптимальности базисного плана:

а) если ij		0,		(i, j) UН , то базисный план перевозок оптимален.
Вычисляем на нем транспортные расходы и записываем ответ.
б) если		ij	0,		(i, j) UН , то переходим к п.4.
4)	Находим максимальную оценку:
				max ij .
			i	j	(i , j ) U
			0 0
					H
5)	Начиная из клетки (i0 , j0 ) с использованием клеток U Б , строим
	цикл.
6)	Помечаем клетки цикла знаками “+” и “−” попарно, начиная с
	клетки	(i0 ,	j0	) .
7)	Среди перевозок, помеченных знаком “−” выбираем наименьшую:
			0	xi* j* .
8)	Строим новую транспортную таблицу с базисным множеством
		UБ (UБ \ (i * j*)) (i					j		) .
		/				0		0

Для нее базисный план получается из предыдущего, если изменить в нем лишь перевозки по циклу следующим образом: к перевозкам в

клетках, помеченных знаком “+”		прибавляем		0	, а из перевозок,
помеченных знаком “−” вычитаем	0	. Переходим к п.1.

Замечания

1. В результате одной итерации транспортные расходы сократятся на

величину	0	.
		i	j
		0	0
2. Если для оптимального базисного плана x				1	1 0,	(i1 , j1 ) U	Н	, то у
			i		j

задачи существует альтернативный оптимум. Его можно найти, совершив

еще одну итерацию, считая (i		j	) = (i	, j	) .
	0	0	1	1

Пример. Записать математическую модель и решить транспортную задачу методом потенциалов:

40