Добавил:

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

Вуз:

Альметьевский государственный нефтяной институт

Предмет:

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

Файл:

«Методы_оптимальных_решений»Зарипова З.Ф

..pdf

Скачиваний:

Добавлен:

15.05.2015

Размер:

374.74 Кб

Скачать

☆

<<< < Предыдущая 1 23 / 63 4 5 6 > Следующая >>>

																			НИ
	№	1			2		3	4		5		6		7		8		9	НИ
	№	1			2		3	4		5		6		7		8		9
	a1	80			100		40	35		50		100		60		50		90
	a2	110			160		40	15		70		90		40		70		35
	a3	140			70		30	60		70		10		90		80		75
	b1	100			80		35	40		60		70		70		100		АГ
	b1	100			80		35	40		60		70		70		100		95
	b2	160			140		15	30		90		80		50		10		80
	b3	70			110		60	40		40		50		70		90		25
	c22	1			1		1	1		1		1		1		ка1		2
	c11	6			4		4	4		3		6		4		4		2
	c12	2			3		5	5		4		1		3		3		7
	c13	5			5		8	8		1		1		1		7		4
	c21	8			101		8	8		4		3		2	е	1		1
	c21	8			101		8	8		4		3		2		1		1
	c23	3			2		3	3		3		8		т		5		5
	c23	3			2		3	3		3		8		4		5		5
	c31	3			3		2	2		2		4		2		1		8
	c32	10			8		6	6		2		и	о	4		8		1
	c32	10			8		6	6		2		5	о	4		8		1
	c33	4			6		7	7		4		3		8		3		3
										б	л
	№	10			11		12	13		14	л	15		16		17		18
	a1	25			40		45	30		40		105		110		25		30
	a2	95			40		65	б	и	30		45		40		85		80
	a2	95			40		65	70	и	30		45		40		85		80
	a3	80			60		30	100		40		50		50		90		90
	b1	35			30		40	50		35		80		100		45		45
	b2	75			45		ая	110		60		90		30		105		50
	b2	75			45		60	110		60		90		30		105		50
	b3	90			65		40	40		15		30		70		50		105
	c11	7			9		1	3		3		8		1		4		3
	c12	2			4	н	4	2		5		4		2		8		7
	c12	2			4		4	2		5		4		2		8		7
	c13	4			н		5	1		7		1		3		2		1
	c13	4			10		5	1		7		1		3		2		1
	c21	2			1		3	4		8		2		8		7		7
	c22	1	о		5		4	5		1		1		5		1		1
	c22	1			5		4	5		1		1		5		1		1
	c23	5			2		9	8		3		7		4		2		2
	c31	1			2		2	6		1		4		3		4		3
	c32	8			8		1	1		5		1		1		3		4
	c33	3			8		8	3		8		3		6		6		1
	к			отправления некоторого однородного груза А1,													А2, А3, А4, в
Имеется 4 пунктатр				отправления некоторого однородного груза А1,													А2, А3, А4, в

которых находится груз соответственно в количестве а1, а2, а3, а4 тонн. Четырем

излi-ого пункта отправления в j –ый пункт назначения ( i, j =1,2,3,4 )заданы

пунктам потребления этого груза – В1, В2, В3, В4 требуется доставить этот груз
соответственное	в количестве b1, b2, b3, b4 тонн. Тарифы перевозок 1 тонны груза

æ	с с с			с	ö	НИ
ç	11	12	13	14	÷	. Составить экономико-математическую модель задачи.
матрицей С= ç	с21с22		с23с24		÷	. Составить экономико-математическую модель задачи.
ç	с	с	с	с	÷
è	31	32	33 34		ø

	Определить				план закрепления								потребителей					за	поставщиками грузов,
	минимизирующий суммарные транспортные расходы.																					АГ
	минимизирующий суммарные транспортные расходы.

	№		19		20		21			22		23		24		25		26	27		28	29	30
	a1		55		100		120			105		105		125		80		75	110		75	125	80
	a2		115		120		110			115		75		125		105		100		ка		125	125
	a2		115		120		110			115		75		125		105		100	100		95	125	125
	a3		155		140		90			110		120		150		125		125	160		100	150	135
	a4		125		100		200			90		160		150		90		150	е		90	150	110
	a4		125		100		200			90		160		150		90		150	80		90	150	110
	b1		80		150		80			70		90		120		110		100	85		90	120	90
	b2		90		130		100			130		90		130		130		100	105		100	130	110
	b3		150		130		120			120		100		200		160		о	120		150	200	160
	b3		150		130		120			120		100		200		160		90	120		150	200	160
																		т
	b4		100		160		150			150		100		200		120		70	85		80	200	160
	c11		2		6		6			6		4		5		6		6	2		2	5	6
	c12		4		7		5			3		6		7		л	и	3	3		5	7	4
	c12		4		7		5			3		6		7		6	и	3	3		5	7	4
	c13		5		3		4			3		8		6		3		5	6		4	6	3
	c14		5		5		3			5		6		4		5		6	4		6	4	2
	c21		4		4		3			5		5		и	б	5		5	6		3	4	6
	c21		4		4		3			5		5		4	б	5		5	6		3	4	6
	c22		3		5		7			4		4		6		4		4	4		4	6	5
	c23		2		3		6			1		3		5		4		4	3		3	5	4
	c24		1		6		5			3		2		3		3		6	5		5	3	3
	c31		2		8		4			7	ая	1	б	4		6		9	8		4	4	5
	c31		2		8		4			7		1	б	4		6		9	8		4	4	5
	c32		4		4		6			2		2		5		5		8	6		3	5	3
	c33		5		5		3			3		3		4		6		8	4		4	4	5
	c34		3		4		4			2		4		6		4		8	6		7	6	4
	c41		6		2		3	н		6		3		3		8		7	3		5	3	7
									н
	c42		6		4		6		3			3		8		4		6	4		3	8	4
	c43		5		5	о	4		4			5		2		2		5	2		5	2	4
	c43		5		5		4		4			5		2		2		5	2		5	2	4
	c44		8	тр			2		2			5		4		4		4	6		7	4	5
	c44		8		8		2		2			5		4		4		4	6		7	4	5
	л	е	к
Э		е

														22
														22

																													НИ
		Тема 7. Нелинейное программирование. Метод множителей Лагранжа
	Задание 7																										АГ
	№ 1-10.																										АГ
	№ 1-10.
			Дана задача						нелинейного программирования :														F = ax1x2			при ограничении
	a11x1 + a12 x2					=b1 . Найти						условный экстремум используя													метода множителей
	Лагранжа.																								ка
			Значения коэффициентов целевой функции и системы ограничений
	указаны в таблице.

			№				1				2		3		4			5		6		7		е	8		9	10
			№

			Значени																		о		т
			я																		о
			я
				a			-1				1		2		1			3		-1			-2		-3		1		2
				a11			3				1		2		3			2		-1			1		3		1		1
				a12			-3				1		3		1			1	л	3			-2		-1		3		3
																				и
				b1			2				1		4		2			3		2			2		3		1		2
															б			б
			№ 11-30.												б			б				2
			По плану производства продукц															предприятию необходимо изготовить
	d поршневых									насосов.				Эти		иизделия					можно				изготовить				двумя
													ая	Производственные затраты на изготовление n
	технологическими способами.													Производственные затраты на изготовление n
	поршневых насосов первым способом равны																			an + n , а для второго способа -
	bn + n2 . Сколько поршневых насосов надо изготовить каждым способом, чтобы
	общие затраты на производство продукции были бы минимальными. Исходные
												н
	данные приведены в т блице.
						№		о			н		a						b							d
					задачи			о
					задачи
						1 1							4						8						200
						тр							12						4						98
						12							12						4						98
						13							3						11						102
			е		к	14							6						2						110
						14							6						2						110
						15							3						7						108
	л					16							13						5						112
	л					17							9						1						90
						17							9						1						90
Э						18							2						10						92
Э						19							11						7						88
						19							11						7						88
																	23

																												НИ
								20							8					12					120			НИ
								20							8					12					120
								21						13						9					122
								22							2					14					118
								23							5					1					80
								24							7					3					82		АГ
								24							7					3					82
								25							9					5					78
								26						14						2					150
								27						15						3					ка
								27						15						3					152
								28							4					16					148
								29							5					13					140
								30						17						5				е	142
								30						17						5					142
			Образец выполнения заданий контрольной рабо ы с комментариями
			Задание 1																		и		т
			Решить графическим методом задачу линейного программирования
								F(x) = 3x1 + x2 → max												л		о
								ì2x1 + 3x2					£ 6		(1)				б
								ï					£ 3		(2)				б
								í2x1 - 3x2					£ 3		(2)		и
								ïx ³ 0,					x ³ 0
								î	1				2
			Решение.
			Для						определения									ОДР					построим					прямые
	x	= -		2	x + 2,			x	= +	2	x -1, x				= 0, x = 0				и		определим					полуплоскости,
	x	= -			x + 2,			x	= +	3	x -1, x				= 0, x = 0				и		определим					полуплоскости,
	2		3			1		2		3		1		1		2
														ая
	соответствующие ограничению системыб																		.
									о	н			н
							тр			н

			е			к
	л					к											(рис. 1)
Э	л																(рис. 1)
Э																	24
																	24

3 x1 + 2 =

3 x1

-1

НИ

ОАКВ – область допустимых решений. Строим вектор

(3,1) и F0^c .

Перемещая линию уровня по направлению вектора

, получим, что точкой

выхода линии F0

из ОДР является точка К.

Координаты точки К найдем как

решение уравнения:

= 1

= 0,5

АГ

= 2,25

ка

F = 3× 2,25 + 0,5 = 7,25

Ответ: Fmax

= 7,25

Задание

Решить

задачу линейного

симплекс-

программированияе

методом

F(x) = 3x1 + x2

® max

ì2x + 3x

£ 6

£ 3

í2x1 - 3x2

ïx ³

0 x

= 0

Решение.

Комментарии.

Симплексный метод основан на последовательном переходе от одного

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

Рассмотрим алгоритм симплексного метода на примере задачи:

ïx

³ 0,

j = 1,n

ая

=б(x1, x2

определить

вектор

.....,xn ),

который

удовлетворяет

ограничениям вида:

ì n

ï å a

x £ b ,

i =

1,m

í j=1

î j

и обеспечивает

максимальное

значение

целевой

функции

F(x) , т.е.

) = å c j x j ® max .

Алго итм симплексногоо

метода включает следующие этапы.

1. Сос авление первого опорного плана

³ 0 . Перейдем от

О ме им, что правые части системы ограничений

системы

неравенствтр

системе

уравнений,

вводя

дополнительные

н отрицательные

переменные.

Векторы-столбцы

при

дополнительных

являются

единичными

образуют

базис.

Назовем

п р менных

соответствующиее

им переменные базисными.

НИ

Итак, å aij × x j

+ xn+1 = bi ,

i =

1,m

i=1

где

xn+ j - базисные переменные, i =

1,m

АГ

xn+ j

= bi - å aij × x j ,

i = 1,m.

xj - свободные переменные,

1,n

Выразим базисные переменные через свободные переменные:

ка

j=1

Функцию цели

запишем в виде равенства:

) =

0 - (-åcj

× xj ) . Положив

x1 = x2 = x3 = ..... = xn = 0,

j =1

получим

первый

опорный

план

= (0,0....0,b1,b2,....bm ), при котором

) = 0.

Занесем его в симплексную

таблицу,

которая

состоит из коэффициентов и свободных членов системы

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

коэффициентами целевой функции, взятыми с прот воположным знаком.

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

Критерий оптимальности при решении задач на максимум:

если все коэффициенты индексной строкил

неотрицательны (³ 0) , то план

является оптимальным. Если найдется хотя бы один коэффициент индексной

строки меньше нуля, то план не является оптимальным и его можно

улучшить.

Критерий оптимальности при решении задач на минимум: если все

ая

то

план

является

коэффициенты индексной строки неположительны,

оптимальным.

Далее переходим к следующему этапу.

3. Определение ведущей строки и ведущего столбца

При решении задач

а максимум из отрицательных коэффициентов

индексной строки выбираем наибольший по абсолютной величине, что и

определит ведущий столбец, которым пометим стрелочкой - - .

При решении

нзадач на минимум из положительных коэффициентов

выбираем наибольшее, что

укажет ведущий столбец.

Ведущий столбец

показывает, какая

переменная на

итерации

перейдет

из

свободных в базисные.

За ем элементы

столбца

значений базисных

переменных

делим

на

ведущеготр

знака (+ + , - -).

элементы

столбца того

же

Результаты

занесем

столб ц коценочных

отношений

σi .

Строка,

которая

соответствует

наименьшему оценочному отношению δi , является ведущей.

	НИ
Ведущая строка указывает, какая переменная	xi на следующей

итерации выйдет из базиса и станет свободной. Ведущую строку отметим

стрелкой	- ← . Элемент симплексной таблицы, находящийся на пересечении
ведущей	строки и ведущего столбца является разрешающим,		выделим его
кружком.			АГ

4.	Построение нового опорного плана
Чтобы перейти к новому плану, заменим сначала переменные в базисе, т.к.
		ка
вместо	xi в базис войдет переменная	xj , соответствующая ведущему столбцу.
Разделим все элементы ведущей строки предыдущей симплексной таблицы на
разрешающий элемент и полученные частные запишем в строку следующей
симплексной таблицы, соответствующую введенной переменной			xj . На месте
разрешающего элемента получим 1.		В остальные кл тки этого столбца,

включая индексную строку, поместим нули. Остальные эл менты нового плана

находим по правилу прямоугольника

А × В

н.э = ст.э -

Р.Э

где ст.э – элемент старого плана, н.э-элемент нового плана;

Р.Э – разрешающий элемент;

А, В – элементы старого плана, образующиеи

прямоугольник с

элементами ст.э

и Р.Э.

Далее возвращаемся ко 2-му этапу проверке плана на оптимальность.

Рассмотрим решение задан я 2

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

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

x3 и x4 .

ая

ì2x + 3x

+ x

= 6

î2x1 - 3x2 + x4 = 3

Рассмотрим матрицу

A = (aij ) этой системы уравнений:

æ2

0ö

A = ç

- 3

è1

1ø

линейно

независимы, соответствующие им вектора

x3 и

Векторы A3,A4

тр

составляют базис. Выразим базисные переменные из системы уравнений:

x3 = 6 - 2x1 - 3x2

x4 =

3x2

3 - 2x1 +

Целевую функцию перепишем

в виде F(x) - 3x1 - x2

= 0 .

Положим,

что

свободные

переменные

= x = 0,

получим

первый

опорный

план

x1 = (0,0,6,3),

F(x1

) = 0.

Внесем полученный план в таблицу.

НИ

Значения

σi

Базис

базисных

переменных

АГ

6/2=3

-3

3/2

F(x)

-3

-1

Первый опорный

план

ка

не

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

находятся отрицательные

коэффициенты: -3, -1.

Так

как

− 3

−1 ,

то

ведущий

выберем

столбец,

за

столб ц

соответствующий переменной

отношения σ ,

деля

x . Вычислим оценочные

значения базисных переменных

на коэффициенты

ведущего столбца.

min σi = min(3,3/ 2) = 3/ 2 = 1,5 .

Следовательно,

2-ая

строка будет

ведущей.

Разрешающий элемент равен 2.

Формируем

следующую

часть

таб ицы, вместо переменной

войдет в базис

x1 .

Строка,

соответствующая

x1 в плане 2,

получена

результате деления строки

на разрешающийл

элемент

На месте

разрешающего элемента в

плане

получим

остальные клетки

этого

столбца помещаем нули. Таким образом, в плане 2

заполнится строка

столбец

x1 .

Все

остальные

элементы

вычислим

всем

по

правилу

прямоугольника. Для этого вы ерем из старого плана 4-ре числа, образующие

вершины прямоугольника и применимб

соответствующую

формулу.

В итоге

будет сформирована таблица 2.

ая

Значения

Базис

σi

базисных

переме ыхн

-1

1/2

тр

3/2

-3/2

F(x)

9/2

-5,5

3/2

на оптимальность,

сформируем

план 3,

который

Проверим критерий

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

Значения

НИ

Базис

базисных

переменных

1/6

-1/6

2,25

-1/4

F(x)

7,25

5,5/6

3/4

= (2.25,0.5)

АГ

Оптимальный план

F(x ) = 7.25

Задание 3. Решите задачу методом искусственного базиса:

F = 3x1 + 8x2 + 6x3 ® max

ка

ì3x1 + 2x2

+ 2x3 = 100

ï2x + 3x

+ 4x

³ 160

ï 1

íx + 2x

- 2x

£ 120

ï 1

ïx ³ 0,i = 1,3

î i

Решение.

Комментарии.

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

переменных,

позволяющих

единичную

матрицу.

Наличие

о разовать

единичной

матрицы является

нео ходимым условием

при решении задач

ая

симплексным методом.

и ( или)

Если же ограничения з д чи з даны в виде неравенства вида åаij xj ³ bi

j =1

= bi , то невозможно сразу получить начальное базисное

в виде уравнений åaij xj

j =1

решение,

если

матрица

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

коэффициентов при

неизвестных

тр

Причем

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

достаточно час о уравнения отражают собой жесткие условия ограничений по ресурсамк, не допускающие никаких отклонений. Для соблюдения равенств вводятсяе ис усственные переменные yi=0. Векторы искусственных переменных образуютл необходимую для решения единичную матрицу. Такой базис называется искусственным, а метод решения называется методом

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

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

НИ

Преобразование ограничений, заданных уравнениями, рассмотрим на примере:

ì7x +

2x + 3x = 23

ка

АГ

í6x1 +

3x2 + 5x3 = 29

ï4x + 5x

= 30

систему

равенств

вводим

искусственные

у1,у2,у3 с

переменные

коэффициентами, равными единице,

что позволит образовать искусственный

базис решения:

ì7x1 + 2x2 + 3x3 +1y1 = 23

í6x1 + 3x2 + 5x3 +1y2 = 29

ï0x + 4x + 5x +1y = 30

решении задачи на максимум-

Целевая функция при этом примет вид: прил

F(x)=c x +c x +c x +(-My )+ (-My )+ (-My );

3 3

б3

на минимум- F(x)=c1x1+c2x2+c3x3+My1+ My2 +My3.

За

использование

искусственных

переменных

накладывается

«штраф»

величиной М, М→ ∞ .

ая

Если

ограничения

з д ны

неравенствами,

то

сначала

следует ввести

ые xi, а затем искусственные переменные.

дополнительные переме

в табличной форме выражают

С целью формулировки задачи для ее решения

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

искусственные переме

функцию. Далее задача решается симплексным методом.

Решение задания 3.

Приведемтрзадачу к каноническому виду, для этого разнородную систему

ограниченийк

преобразуем

к системе уравнений, введя

неотрицательные

ба ансовые переменные x

³ 0, x

³ 0.

<<< < Предыдущая 1 23 / 63 4 5 6 > Следующая >>>

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

#
08.08.2019154.62 Кб172Voprosy_i_zadachi_dlya_GEK_-_menedzhment_-_2011....doc
#
15.05.201520.59 Кб56Voprosy_RNGM.docx
#
18.09.2019167.42 Кб3Vozmozhnye_zadachi_buh.doc
#
15.05.2015193.48 Кб10Zhukova_S_B_Yagudin_R_Kh_Organizatsia_normirov.pdf
#
26.04.201978.34 Кб6Znachenie_transporta_nefti.doc
#
15.05.2015374.74 Кб23«Методы_оптимальных_решений»Зарипова З.Ф..pdf
#
15.05.2015258.55 Кб52Автоматизация.docx
#
15.05.201537.89 Кб21АДРЕСНЫЙ БЛАНК.doc
#
15.05.20151.59 Mб28Айнур пояснялка.docx
#
15.05.201566.05 Кб14актуальные проблемы 7 вар.doc
#
15.05.201597.79 Кб15АХД 1 контр. раб..doc