Добавил:

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

Вуз:

Финансовый университет при Правительстве РФ

Предмет:

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

Файл:

Мат_модели

.pdf

Скачиваний:

Добавлен:

13.03.2015

Размер:

734.08 Кб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 89 / 119 10 11 > Следующая >>>

		B1				B2			B3			B4				ai		ui
A1			11		5				M				2	80			0
A1		− M			−8				60	20				80			0
		− M			−8				60	20
A2			M				4		5				9	170			7
A2		18 − 2M			10				120	40				170			7
		18 − 2M			10				120	40
A3	70		9		8				7	30		M		100				M −2
A3						M −13			M −11					100				M −2
						M −13			M −11
bj	70				10				180	90				400
v j		11 − M				−3			−2			2
Максимальную положительную оценку													33	= M −11 имеем в					клетке A3 B3
и строим цикл, соединяющий клетки												A3 B3 ,		A2 B3 , A2 B4			и A3 B4 :
					120											40
					120				–					+		40
									–					+
									+						–
																30
																30
Так как		= min(30,120) = 30 , делаем перестановку по циклу
					90											70
									+						–
					30				–					+


и получаем транспортную таблицу с новым планом

		B1					B2		B3			B4				ai		ui
A1			11		5				M				2		80			0
A1		−11				−8			60		20				80			0
		−11				−8			60		20
A2			M					4	5				9		170			7
A2		7 − M			10				90		70				170			7
		7 − M			10				90		70
A3				9	8				7				M		100			9
A3	70					− 2			30						100			9
	70					− 2			30
bj	70				10				180			90			400
v j	0					−3			−2			2
Находим потенциалы: u1 = 0											v4		= 2		u2 = 7			v3 = −2		, v2 = −3 ;
v3 = −2	u3		= 9		v1 = 0 ,				а оценки для свободных клеток 11 = −11 < 0 ,
12 = −8 < 0 ,			21 = 7 − M < 0,						32 = −2 < 0,			34	=11− M < 0. Так как все оценки

отрицательны, то данная таблица – заключительная, и увеличивая пере-

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

0		0	60	20
летворяющий всем ограничениям задачи: X =	0	10	90	70	и
	70	50	30	0
	70	50	30	0

F ( X * ) = 4 60 + 2 20 + 4 10 +5 90 +9 70 +9 70 + 7 30 = 2240.

Пример 9.			Найти решение транспортной задачи

		B1	B2	B3		B4			ai
A1		11	5		4		2		80
A1									80

A2		1	4		5		9		170
A2									170

A3		9	8		7		10		150
A3									150

bj		70	60	180		90			400
если из A1 в B4 перевозки запрещены, а из A2									в B4	должно быть завезено
не менее 40 ед. груза, а из A3 в B3					– не более 50 ед. груза.
Решение. Поскольку из A1					в B4 перевозки не могут быть осущест-
влены,	то тариф в A1B4 считаем равным M . Запасы A2 и потребности B4
уменьшаем на 40, а также вводим дополнительного потребителя B33 по-
требностями 180 −50 =130 . Соответственно, в клетке A3B33 стоимость пе-
ревозок считаем равной M , а потребности B3									приравниваем к 50. Полу-
чаем таблицу

		B1	B2	B3		B4			B33		ai
A1		11	5		4		M			4	80
A1			0	50				30			80
			0	50				30
A2		1	4		5		9			5	130
A2		70	60								130
		70	60
A3		9	8		7	50	10	100		M	150
A3											150

bj		70	60	50		50			130
Найдем начальное опорное решение методом минимального тари-
фа. В клетку A2 B1			вводим максимально возможную перевозку 70, в клет-
ку A2 B2	–60, A1B3		– 50, A1B33	– 30, A3B4 – 50 и A3B33						– 100. Поскольку план

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

	B1		B2			B3					B4			B33			ai	ui
A1	11	5				4					M					4	80	0
	−9	0		50							M		30
											14-2M
											14-2M
A2	1	4				5						9				5	130	−1
A2	70	60			− 2						4 − M						130	−1
	70	60			− 2						4 − M
A3	9	8					7					10			M		150	M − 4
A3	M −11		M −7		M −7					50			100				150	M − 4
	M −11		M −7		M −7					50			100
bj	70	60				50				50			130
v j	2	5				4					14 − M		4
Из	двух	клеток		с		максимальной								положительной				оценкой
33 = 32 = M −7 выбираем клетку									A3B3 (так как там меньший тариф) и
строим цикл, соединяющий клетки										A3 B3 , A1B3 , A1B33						и A3B33 :
		50											30
		50				–			+				30
						+						–	100
Так как

	= min(50,100) = 50 , делаем перестановку по циклу
													80
						–			+				80
				50		+						–	50


и получаем транспортную таблицу с новым планом

	B1		B2			B3					B4			B33			ai	ui
A1	11	5				4					M					4
A1	−9	0			7 − M						14 − 2M		80				80	0

A2	1	4				5				9						5	130	−1
A2	70	60			5 − M						4 − M			− 2			130	−1
	70	60			5 − M						4 − M			− 2
A3	9	8						7		10					M		150	M − 4
A3	M −11		M −7	50						50			50				150	M − 4
	M −11		M −7	50						50			50
bj	70	60				50				50			130
v j	2	5				11 − M				14 − M			4

Цикл, построенный в клетке с максимальной положительной оценкой 32 = M −7 (соединяющий клетки A3B2 , A1B2 , A1B33 и A3B33 ) имеет вид

0			80
0	–	+	80
	+	–	50

со знаком минус в клетке с нулевой перевозкой. Это означает, что клетка

A3B2 объявляется занятой (с нулевой перевозкой),															а A1B2 – свободной.
Для нового базиса считаем потенциалы и оценки и получаем

	B1				B2			B3			B4			B33		ai	ui
A1		11			5				4			M	80		4	80	0
A1	− 2 − M			7 − M			7 − M				14 − 2M		80			80	0

A2	70	1	60		4				5			9			5	130	M −8
A2							− 2				− 4			M −9		130	M −8
							− 2				− 4			M −9
A3		9	0		8	50			7	50		10		M		150	M − 4
A3	− 4												50			150	M − 4
	− 4												50
bj	70				60			50		50			130

v j	9 − M		12 − M			11 − M				14 − M			4

Имеем единственную положительную оценку 2,33															= M −9 в A2 B33 с цик-
лом из клеток		A2 B33 ,			A3B33 , A3B2 и A2 B2 :
					60
					60			–				+
								–				+
					0			+				–	50
Так как

	= min(50,60) = 50 , приходим к циклу
					10								50
					10			–				+	50
					50			+				–

и получаем транспортную таблицу с новым планом. Вычисляем новые потенциалы и убеждаемся, что все оценки отрицательны. Данная таблица – заключительная, и увеличивая перевозку в клетке A2 B4 на 40, а так-

же складывая перевозки, записанные в соответствующих клетках столбцов B3 и B33 , получим

	B1			B2			B3				B4				B33		ai	ui
A1		11			5			4				M		80		4	80	0
A1	−11			− 2			− 2			5 − M							80	0
	−11			− 2			− 2			5 − M

A2	70	1	10		4			5					9			5	130	1
A2							− 2			−3				50			130	1
							− 2			−3				50
A3		9	50		8	50		7	50			10			M		150	5
A3	− 4													9 − M			150	5
	− 4													9 − M

bj	70		60			50					50				130

v j	0		3			2					5				4

										0		0		80	0
оптимальный		план перевозок						X =			70	10		50	40 , удовлетворяющий
											0	50		50	50
											0	50		50	50

всем ограничениям задачи, и

z( X * ) = 4 80 +1 70 + 4 10 +5 50 +9 40 +8 50 + 7 50 +10 50 = 2290 .

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

		B1	B2	B3	B4	ai
	A1	3	4	7	9	100
88. Найти решение транспортной задачи с таблицей	A2	16	5	12	4	100	,
	A3	8	11	12	5	200
	bj	80	110	90	120

если из A	в B	и из A	в B перевозки не могут быть осуществлены.
1	2	2	3

					B1	B2	B3	B4	ai
				A1	5	14	6	21	120
89. Найти решение транспортной задачи с таблицей				A2	20	13	17	14	90	,
				A3	8	21	6	7	180
				bj	95	110	80	70
если из A3	в B2	перевозки не могут быть осуществлены, а из A1 в B4 должно быть
перевезено 70 ед. груза.

			B1		B2	B3		B4		ai
	A1	7		12		16		11		150
90. Найти решение транспортной задачи с таблицей	A2	8		2		4		2		140	,
	A3	9		15		16		7		110
	bj	75		145		120		60
если из A2 в B4 перевозки запрещены, из A1 в B3 должно быть доставлено не менее
40 ед. груза, а из A3 в B1 – не более 50 ед. груза.

			B1		B2	B3		B4		ai
	A1	3		10		7		10		140
91. Найти решение транспортной задачи с таблицей	A2	4		9		19		25		105	,
	A3	6		4		5		2		115
	bj	60		130		55		115
если из A2 в B1 перевозки запрещены, из A1 в B2 должно быть перевезено 50 ед.
груза, а из A3 в B4 – не более 20 ед. груза.

			B1		B2	B3		B4		ai
	A1		9		6	7		11		70
92. Найти решение транспортной задачи с таблицей	A2		3		14	25		19		170	,
	A3		2		8	17		10		140
	bj		90		60	160		70
если из A1 в B4 должно быть перевезено не менее 50 ед. груза, из						A3 в B3			должно
быть перевезено не менее 30 ед. груза, а из A2 в B2 – 40 ед. груза.

			B1		B2	B3		B4		ai
	A1	12			14	11		20		90
93. Найти решение транспортной задачи с таблицей	A2	3			4	5		9		155	,
	A3	2			18	14		12		125
	bj	100			75	75	120
если из A1 в B4 должно быть перевезено не менее 40 ед. груза, из A2						в B3		– не более
50 ед. груза, а из A3 в B1 – не менее 60 ед. груза.

ЭЛЕМЕНТЫ ВЫПУКЛОГО И

ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

§1. Задача квадратичного программирования

Рассмотрим задачу оптимизации вида

z(x )→ min (max), x X ,

где множество X Rn , как и в задаче линейного программирования, определяется системой линейных неравенств, а функция z является квадратичной (т.е. многочленом второй степени по переменным x1 , x2 ,K, xn ).

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

Сформулируем сначала общую теорему об условиях оптимальности задачи квадратичного программирования.

Теорема (необходимое и достаточное условие экстремума). Пусть

X Rn – выпуклое множество, заданное системой линейных неравенств

g1 (x1 ,K, xn ) ≤ 0,

KKK

gm (x1 ,K, xn ) ≤ 0.

а z – выпуклая функция на X . Для того, чтобы точка x X являлась точкой глобального минимума функции z на X , необходимо и достаточно, чтобы существовал вектор λ = (λ1 , λ2 ,Kλm ) Rm , удовлетворяю-

щий условиям

Lx′i (x ,λ)= 0 , i =1,K,n ,

λj g j (x* )= 0 , λj ≥ 0 , j =1,K, m ,

где L(x,λ)= f (x) + ∑λj g j (x) – функция Лагранжа.

j =1

Замечание. Необходимое и достаточное условие экстремума является частным случаем теоремы Куна-Таккера о связи экстремумов выпуклой функции на выпуклом множестве со стационарными точками функции Лагранжа. Поэтому далее при его использовании мы будем ссылаться на теорему Куна-Таккера.

Пример 1. Графически найти решение задачи квадратичного программирования

z = (x −16)2 + ( y −12)2 → min

2x + y ≤19,−5y +3x ≥ −30,

5x − 4 y ≤15,

x ≥ 0, y ≥ 0,

и проверить выполнение условий теоремы Куна-Таккера.

Решение. Построим сначала на плоскости (x, y) выпуклое множе-

ство, заданное системой	ограничений задачи.	Изобразим прямые
l1 : 2x + y =19 , l2 : 3x −5y = −30,	l3 : 5x − 4 y =15 . Легко видеть, что нетривиаль-
y
l1
	M
	B
A	K
l2
	C
O	D
	D	x
	l3

ные ограничения вместе с условиями x ≥ 0, y ≥ 0 задают пятиугольник

OABCD с угловыми точками O(0,0) , A(0,6), B(5,9), C(7,5) и D(3,0). Далее,

линиями уровня целевой функции z являются концентрические окружности (x −16)2 + ( y −12)2 = C с центром в точке M (16,12), лежащей, очевид-

но, вне многоугольника OABCD . Поэтому минимальное значение функции z достигается в точке касания с отрезком BC окружности соответствующего радиуса. Найдем точку касания K как точку пересечения прямой l1 и прямой m1 , перпендикулярной l1 и проходящей через точку

M (16,12). Так как прямая l1 определяется уравнением 2x + y =19 , а вектор нормали к ней, равный nr = (2,1), является направляющим вектором для

прямой m , то каноническим уравнением m является					x−16	=	y −12	, а общим
прямой m , то каноническим уравнением m является						=	1	, а общим
1			1	2			1
x − 2 y = −8 . Точка пересечения K = l1 ∩m1			находится как решение системы
2x + y =19,		K (6,7).
	− 2 y = −8.	K (6,7).
x	− 2 y = −8.
Таким образом, решением задачи			является	точка			x = (6,7) и
z(x )= z(6,7)= (6 −16)2 + (7 −12)2	=125 .

Проверим теперь, что точка x = (6,7) является решением системы,

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

2x + y ≤19,5y −3x ≤ 30,5x − 4 y ≤15,

− x ≤ 0,

− y ≤ 0,

и составим функцию Лагранжа

L(x,λ) = (x −16)2 + ( y −12)2 + λ1(2x + y −19)+

+ λ2 (5y −3x −30)+ λ3 (5x − 4 y −15) −λ4 x −λ5 y.

Теперь мы можем записать условия теоремы в виде системы:

L′x = 2(x −16) + 2λ1 −3λ2 +5λ3 −λ4 = 0,

L′y = 2( y −12) + λ1 +5λ2 − 4λ3 −λ5 = 0,

λ (2x + y −19) = 0,λ12 (5y −3x −30)= 0,

λ3 (5x − 4 y −15)= 0,

λ4 x = 0,λ5 y = 0.

Подставляя x = 6, y = 7 , немедленно убеждаемся, что λ2 = λ3 = λ4 = λ5 = 0 , и

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

− 20 + 2λ1 = 0,

−10 + λ1 = 0,

откуда имеем, что λ1 =10 ≥ 0, т.е. для точки x = (6,7) условия теоремы вы-

полнены.

Пример 2. Рассмотрим теперь другой метод решения задачи

z = (x −16)2 + ( y −12)2 → min

2x + y ≤19,−5y +3x ≥ −30,

5x − 4 y ≤15,

x ≥ 0, y ≥ 0,

основанный на применении симплекс-метода. Сначала приведем систему нетривиальных ограничений к каноническому виду, т.е. введем балансовые неотрицательные переменные u1,u2 ,u3 , такие что

2x + y +u1 =19,5y −3x +u2 = 30,5x − 4 y +u3 =15.

При этом получим, что 2x + y −19 = −u1 и условие λ1(2x + y −19) = 0 перепи-

сывается в виде λ1u1 = 0 и, аналогично, λ2u2 = λ3u3 = 0 . Таким образом, не-

обходимые и достаточные условия экстремума для исходной задачи

<<< < Предыдущая 1 2 3 4 5 6 7 89 / 119 10 11 > Следующая >>>

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

#
13.03.20151.52 Mб8Маркетинговые исследования.doc
#
13.03.201557.2 Кб6Мартиросова. ИОГП..docx
#
20.11.201813.41 Кб1масла.docx
#
25.08.2019218.11 Кб4Масло.doc
#
24.03.2016415.74 Кб35Мат.Анализ-контрольная работа.doc
#
13.03.2015734.08 Кб13Мат_модели.pdf
#
13.03.2015585.29 Кб20матан.pdf
#
27.09.2019163.85 Кб4Матан_Теория_а.docx
#
13.03.2015987.65 Кб110Матанализ_методичка_2семестр2014.doc
#
27.09.2019200.52 Кб3Матанчик Часть А.docx
#
13.03.2015425.29 Кб18Математика _1 семестр 2012 для ПИ1.pdf