Матан_ЛинПрог

3x1 7x2 5x3 15

2x1 3x2 4x3 16

6x1 5x2 8x3 12

x1, x2, x3 0

6.15. F 3x1 4x2 6x3 min

2x1 3x2 x3 8

3x1 2x2 2x3 10

5x1 4x2 x3 7x1, x2, x3 0

6.17. F 4x1 5x2 6x3 min

x1 x2 x3 5

x1 x2 2x3 1

x1 x2 4x3 3

x1 x2 8x3 4

x , x 0

1 2

6.19. F 2x1 3x2 5/2x3 min

2x1 x2 3x3 6

2x1 4x2 3x3 16

3x1 4x2 2x3 12

x1, x3 0

4x1 2x2 3x3 9

3x1 2x2 5x3 8

x1 3x2 4x3 12x1, x2 0

6.16.F 2x1 2x2 3x3 4x4 max

x1 2x2 x3 x4 2

2x1 x2 2x3 3x4 3

3x1 4x2 5x3 2x4 4x1,x3,х4 0

6.18.F 5x1 x2 4x3 max

x2 2x3 9

x			x	2		1
		1
		x2 3x3 8
x1
x				x	3	4
1
	,		x3 0
x2
6.20. F 4x1					6x2 3x3		min
3x1 x2 2x3 9
			2x2 2x3 8
x1
x		6x		2		12
1
			x3 0
x2,

§7. Двойственный симплексный метод

Двойственный симплексный метод, как и симплексный метод, используется при нахождении решения задачи линейного программирования, записанной в форме основной задачи, для которой среди векторов Pj ,

составленных из коэффициентов при неизвестных в системе уравнении, имеется m единичных. Вместе с тем двойственный симплексный метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными). Такую задачу и рассмотрим теперь, предварительно предположив, что единичными являются векторы P1,P2,...,Pm , т.е. рассмотрим задачу, состоящую в определении максимального значения функции:

Fmax c1x1	c2 x2 ... cn xn			(7.1)
при условиях
P1x1 P2x2	...	Pmxm Pm 1xm 1 ...	Pn xn B	(7.2)

xj

0

( j 1,n),

(7.3)

где

1

0

0

a

a

a

b

1m 1

1m 2

1n

1

P1

0

P2

1

0

a2m 1

a2m 2

a2n

b2

,

,...,Pm

,Pm 1

...

,Pm 2

...

,...,Pn

...

,B

...

...

...

...

0

0

1

amm 1

amm 2

amn

bm

и среди чисел bi

(i

) имеются отрицательные.

1,m

В

данном

случае

Х (b1;b2;...;bm;0;0;...;0)

есть

решение

системы

линейных уравнений (7.2). Однако это решение не является планом задачи (7.1)-(7.3), так как среди этих компонент имеются отрицательные числа.

Поскольку векторы P1,P2,...,Pm - единичные, каждый из векторов Pj

( j 1,n) можно представить в виде линейной комбинации данных векторов,

причем коэффициентами разложения векторов Pj по векторам P1,P2,...,Pm

служат числа xij aij (i 1,m; j 1,n).

В симплекс-таблице первые m строк определяются исходными данными

задачи, а показатели m 1	-ой строки вычисляют. В этой строке в столбце
B записывают значение целевой функции, которое вычисляется по формуле:
F (C ,B),	(7.4)

а в столбце вектора Pj - значение:

	j (C ,Pj ) cj , ( j			1,n),						(7.5)
		m				m
где	(C ,B) cibi		и	(C ,Pj ) ciaij ,			( j		),	- скалярные
								1,n
		i 1				i 1
произведения векторов, а ci				- элемент, стоящий в i-ой строке таблицы.
Значения j		называются оценками плана.
	Решение	Х (b1;b2;...;bm;0;0;...;0) системы линейных уравнений (7.2),
определяемое базисом			P1,P2,...,Pm , называется псевдопланом задачи (7.1)-
(7.3), если j		0 для любого		j ( j		).
					1,n

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

min j aij , где aij 0. (7.6)

Число aij является разрешающим элементом. Переход к новой симплекс-

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

Итерационный процесс продолжают до тех пор, пока в столбце вектора B не будет больше отрицательных чисел.

Если на некотором шаге окажется, что в столбце вектора B стоит отрицательное число bi , а среди элементов aij этой строки нет

отрицательных, то исходная задача не имеет решения.

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

1.Находят псевдоплан задачи.

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

3.Выбирают направляющую строку с помощью определения наибольшего по абсолютной величине отрицательного числа столбца вектора B и направляющий столбец с помощью определения минимального отношения ( j ) к отрицательным значениям направляющей строки.

4.Находят новый псевдоплан и повторяют все действия, начиная с этапа

2.

Задача. Решим задачу составления рациона из §1 двойственным симплексным методом.

f 4x1 x2 min

2x1 x2 4

при x1 3x2 6x1 1

x1 0,x2 0.

Решение. Целевую функцию умножим на (-1) и переведем на максимум. А в ограничения добавим дополнительные переменные со знаком «-» и переведем задачу из стандартной формы к канонической:

f 4x1 x2	0x3 0x4					0x5 max
	2x1 x2 x3 4
		3x2 x4 6
при	x1
	x	x	5	1
	1
	x	0,x			2	0.
	1
Дополнительные переменные	x3,x4,x5			означают избыток питательных

веществ S1,S2,S3 соответственно.

Умножим все уравнения системы на (-1), чтобы получить единичные (базисные) векторы:

						2x1 x2 x3 4
								3x2 x4 6
						x1
						x		x			5	1
							1
						x ,x		2	,...,x				5	0
							1
Запишем систему в векторной форме:
			A1x1 A2x2 A3x3 A4x4 A5x5 B
		2			1					1							0		0	4
A1 1 , A2 3 , A3 0 , A4 1 , A5 0 , B 6 .
					0
		1								0							0	1		1
Т.к. в столбце B имеются отрицательные																		числа, то задачу решим
двойственным симплексным методом. Составим первоначальный опорный
план. Пусть x1 0 и			x2 0, тогда x3							4, x4					6, x5 1, а f0 0.
Получим псевдоплан				X0		(0;0; 4; 6; 1). Составим первую симплекс-
таблицу. Вычислим			f0 и j по формулам (7.4) и (7.5):
f0 0 ( 4) 0 ( 6) 0 ( 1) 0,												1 0 ( 2) 0 ( 1) 0 1 4 4,
2 0 ( 1) 0 ( 3) 0 0 1 1,												3 4 5 0.
План X0	не является				оптимальным,									т.к. он				содержит отрицательные
компоненты.
№	БАЗ		C B				-4			-1				0		0		0
	ИС						A1			A2				A3 A4 A5
1	A3		0		-4 -2					-1				1		0		0
2		A4	0		-6 -1					-3				0		1		0 ←
3		A5	0		-1 -1					0				0 0 1
m 1		∆j	f0	0			4			1				0		0		0 X0=(0;0;-4;-6;-1)
m 2							4			1/3				---	---			---
										↑
		ai
I				B
Выберем в столбце					среди отрицательных значений наибольшее по
абсолютной величине число. Это число (-6). Строка A4 стала направляющей.
Найдем наименьшее из				отношений													j	где	aij 0	выбраны из
											min				a		,
																ij
							4			1				1
направляющей строки: min							;							. Отношения на положительные
значения aij	0					1		3						3			A2
		не	рассматривают. Столбец															стал	направляющим. На
пересечении	строки		A4	и	столбца					A2			стоит				разрешающий			элемент (-3),

который означает, что вектор A2 войдет в базис, а вектор A4 выйдет из базиса.

	№ БА-		C B		-4	-1 0		0	0
		ЗИС			A1	A2	A3	A4	A5
	1	A3	0	-2	-5/3	0	1	-1/3	0	-
	2	A2	-1	2	1/3	1	0	-1/3	0	-
	3	A5	0	-1	-1	0	0	0	1	X1=(0;2;-2;0;-1)
II	m 1	∆j	f1 2		11/3	0	0	1/3	0

m 2			11/5 --- ---		1		---
					↑
		ai

	1	A4	0	6	5	0	-3	1	0
	2	A2	-1	4	2	1	-1	0	0
	3	A5	0	-1	-1	0	0	0	1	X2=(0;4;0;6;-1)
III	m 1	∆j	f2 4		2	0	1	0	0
	m 2				2	---	---	---	---
					↑
		ai
	1	A4	0	1	0	0	-3	1	5
IV	2	A2	-1	2	0	1	-1	0	2
	3	A1	-4	1	1	0	0	0	-1	X*=(1;2;0;1;0)
	m 1	∆j	f3 6		0	0	1	0	2

Перейдем ко II-ой итерации, в которой базисными векторами будут A3 , A2 , A5 . Заполним соответствующие им значения С . Все элементы таблицы

вычисляем обычным методом Жордана-Гаусса.
Найдем f1 и j , и получим новый псевдоплан	X1 (0;2; 2;0; 1),

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

Повторяем процесс перехода от итерации к итерации до тех пор, пока все элементы столбца В не станут положительными, т.е. bj 0, а также j 0.

Из последней таблицы видно, что все j 0			и	X принимает только
положительные значения, а значит X* (1;2;0;1;0)			является оптимальным и
fmax 6. Умножим	fmax на	(-1) и получим значение исходной функции
fmin 6.
Экономический	смысл	оптимального плана		X* (1;2;0;1;0): чтобы

обеспечить ежедневное необходимое количество питательных веществ для животных (не менее 4 ед. питательного вещества S1, не менее 6 ед. вещества S2 и не менее 1 ед. вещества S3), необходимо приобрести корма I вида в

количестве 1 единицы, корма II вида в количестве 2 единицы, при этом избыток питательного вещества S2 составит 1 единицу, а минимальные затраты на приобретение кормов составит 6 денежных единиц.

Упражнения

7.1.-7.20. Составить двойственные задачи для задач 4.1.-4.20. из §4 и решить их двойственным симплексным методом.

§8. Транспортная задача Общая постановка транспортной задачи состоит в определении

оптимального плана перевозок некоторого однородного груза из m пунктов отправления A1,A2,...,Am в n пунктов назначения B1,B2,...,Bn . В качестве критерия оптимальности берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки.

Введем обозначения. Пусть cij - тарифы перевозки единицы груза из i-го пункта отправления в j-ый пункт назначения; aij - запасы груза в i-том пункте отправления; bj - потребности груза в j-ом пункте назначения; xij -

количество единиц груза, перевозимого из i-го пункта отправления в j-ый пункт назначения.

Тогда экономико-математическая постановка задачи состоит в определении минимального значения функции:

m n

Fmin cij xij

(8.1)

i 1 j 1

при условиях

n

ai,

(i 1,m)

xij

j 1

m

bj,

( j 1,n)

(8.3)

xij

j 1

xij 0

(i

1,m

; j

1,n

)

Если потребности в грузе в пунктах назначения равны запасам груза в пунктах отправления, т.е.

n	m
bj	ai	(8.4)
j 1	i 1

то модель транспортной задачи называется закрытой, в противном случае -

открытой.

Обычно исходные данные транспортной задачи записывают в виде

таблицы.

ПУНКТЫ	ПУНКТЫ НАЗНАЧЕНИЯ						ЗАПАСЫ
ОТПРАВЛ.	В1	В2	...	ВJ	...	ВN	ГРУЗА
	c11	c12	...	c1j	...	c1n
A1	x11	x12		x1j		x1n	a1
	c21	c22	...	c2j	...	c2n
A2	x21	x22		x2j		x2n	a2
...	...	...	...	...	...	...	...
	ci1	ci2	...	cij	...	cin
Ai	xi1	xi2		xij		xin	ai
...	...	...	...	...	...	...	...
	cm1	cm2	...	cmj	...	cmn
Am	xm1	xm2		xmj		xmn	am
ПОТРЕБНОС	b1	b2	...	bj	...	bn
ТИ В ГРУЗЕ

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

Число переменных xij в транспортной задаче равно m n, а число уравнений в системе (8.3) равно m n. Так как выполняется условие (8.4), то

число линейно		независимых	уравнений равно m n 1.				Следовательно,
опорный	план	транспортной	задачи	может	иметь	не	более m n 1,
отличных	от нуля, неизвестных (т.е.			число	заполненных клеток равно
m n 1).
Если в опорном плане число отличных от нуля компонент равно m n 1
(т.е. число заполняемых клеток				m n 1),		то	план является
невырожденным, а если меньше, чем				m n 1, то - вырожденным (при

этом необходимо ввести нулевую поставку).

Для определения опорного плана существует несколько методов. Среди них - метод "северо-западного угла" и метод "минимального элемента".

Для определения оптимального плана существует метод "потенциалов" и метод "дифференциальных рент".

Метод "северо-западного угла": заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного x11 и заканчивается клеткой для неизвестного xmn .

Метод "минимального элемента": заполнение клеток таблицы условий начинается с клетки с минимальным тарифом cij .

Второй метод является более оптимальным.

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

Если для некоторого опорного плана

X* транспортной

задачи

существуют такие числа i

(i

) и j

( j

), что

1,m

1,n

j

i

cij

при xij

0

(для занятых клеток)

(8.5)

и

cij

0

при xij 0

ij

j

i

(для свободных клеток)

(8.6)

то построенный

опорный

план

X*

будет оптимальным

планом

транспортной

задачи.

Числа

i

и

j

называются потенциалами

соответственно пунктов отправления и пунктов назначения.

Данные числа i и j находят из системы уравнений (8.5), где сij -

тарифы затрат. Т.к. число заполненных клеток m n 1,			то система (8.6) с
m n неизвестными содержит		m n 1 уравнений.	Поскольку		число
неизвестных	превышает на единицу число уравнений, то			одно		из
неизвестных	можно принять за любое число, например, пусть			1	0 ,	и

найти последовательно из (8.5) значения остальных переменных. После этого находят для каждой свободной клетки по формуле (8.6) числа ij . И если все

ij 0 , то план X* - оптимальный. Если существует хотя бы одно ij 0 ,

то план не оптимальный и необходимо перейти к новому оптимальному плану. Среди ij выбирают максимальное положительное число и

заполняют данную клетку. При этом строят цикл пересчета.

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

Если ломаная линия пересекается, то точки самопересечения не являются вершинами. Примеры циклов:

Затем производят перемещения поставок:

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

2)в данную свободную клетку переносят наименьшее из чисел xij ,

стоящих в минусовых клетках. Одновременно это число прибавляют и числам, стоящих в ключевых клетках, и вычитают из чисел, стоящих в минусовых клетках.

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

			Алгоритм транспортной задачи
1.	Находят	опорный		план. Число	заполненных клеток		должно		быть
	m n 1.
2.	Находят потенциалы i и j .
3.	Находят	ij	для	свободных клеток. Если все		ij	0,	то	план
	оптимальный,		если	есть ij 0,	то переходят к	новому		опорному
	плану.

4.Среди ij 0 выбирают максимальное и строят цикл пересчета.

5.Полученный план проверяют на оптимальность, т.е. переходят к этапу

2.

Задача 1. Найти оптимальный план перевозок транспортной задачи:

На три базы A1,A2,A3 , поступил однородный груз в количествах соответственно равных 50, 30 и 10 единиц. Этот груз требуется перевезти в четыре пункта назначения B1,B2,B3,B4 соответственно в количествах 30, 20, 10 и 20 единиц. Тарифы перевозок единицы груза даны в таблице.

ПУНКТЫ					ПУНКТЫ НАЗНАЧ.				ЗАПАСЫ
ОТПРАВЛ.					В1	В2	В3	В4	ГРУЗА
	A1			1		2	4	1	50
	A2			2		3	1	5	30
	A3			3		2	4	4	10
ПОТРЕБН.
В ГРУЗЕ				30		20	10	20

Пустьxij (i 1,3, j 1,4) - количество единиц груза, перевозимого из i-го пункта отправления в j-ый пункт назначения. Тогда экономикоматематическая модель задачи:

Fmin 1 x11 2 x12 4 x13 1 x14 2 x21 3 x22 1 x23 5 x24

3 x31 2 x32 4 x33 4 x34

при условиях:

	x11	x12		x13			x14		50
		x22		x23			x24		30
	x21
	x31	x32		x33			x34		10
		x21 x31					30
	x11
	x	x	22	x		32	20
	12
	x13	x23		x33			10
	x	x	24	x		34	20
	14
		0	(i 1,3; j 1,4)
	xij

Решение. Так как условие (8.4) не выполняется, то данная модель задачи является открытой. Запасы превышают потребности на 10 единиц, поэтому добавим фиктивный пункт назначения “Ф.П.” с нулевыми тарифами и потребностью в 10 единиц. Получим закрытую модель задачи. Методом

"северо-западного" угла составим опорный	план X0 . Заполнение клеток
начнем с клетки A1B1, учитывая потребности	B1 и запасы A1 , затем A1B2 и

т.д. до тех пор, пока все запасы груза не будут исчерпаны, а потребности в грузах не будут удовлетворены. Получим таблицу:

	ПУНКТЫ	ПУНКТЫ НАЗНАЧЕНИЯ									ЗАПАСЫ
	ОТПРАВЛ.	В1		В2		В3	В4		Ф.П.		ГРУЗА
		1		2		4		1		0
	A1	30		20							50
		2		3		1		5		0
	A2					10	20				30
	A3	3		2		4		4	10	0	10
	ПОТРЕБН. В
	ГРУЗЕ	30		20		10	20		10		90
Запишем опорный план в виде матрицы
				30		20	0	0
		X0				0	10
				0				20 ,
						0	0	0
				0

при котором общая стоимость перевозок:

F0 1 30 2 20 3 0 1 10 5 20 4 0 0 10 180 (ден.ед.).

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

Число заполненных клеток равно 5, а должно быть m n 1 3 5 1 7. Значит, задача вырожденная. Добавим нулевые поставки в те клетки, где прерываются “ступеньки” перехода от заполненной клетки одной строки к заполненной клетке другой строки, т.е., например, в клетки A2B2 и A3B4 .

Вычислим i и	j , используя формулу (8.5). Получим систему
уравнений: