Филиал фгбоу впо «мгуту им. К. Г. Разумовского» в Г. Мелеузе

(Республика Башкортостан)

Контрольная работа

по дисциплине: Методы оптимизации

на тему: вариант №6

Выполнил:

Студент____3____курса

Абсалямов Р.М._________

Института: САиИ______

Специальность:220700 (збс)

Шифр:___986_________

Работа сдана на проверку:

Преподаватель:

Оценка:__________

Мелеуз 2013

Изм.

Лист

№ докум.

Подпись

Дата

Лист

220700.02.11.0986.000

Разраб.

Абсалямов Р.

Провер.

Реценз.

Н. Контр.

Утверд.

Лит.

Листов

Содержание

1.Задача 1.6…………………………………………………………………….3

2.Задача 2.6…………………………………………………………………….7

3.Задача 3.6……………………………………………………………………11

4.Задача 4.6…………………………………………………………………....13

Список использованной литературы………………………………………...15

1.Задача 1.6

Изм.

Лист

№ докум.

Подпись

Дата

Лист

220700.02.11.0986.000

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

Решение: Вычислим градиент и норму для рассматриваемой функции: Итерационный процесс минимизации с использованием нормированого антиградиента в координатной форме запишется: В качестве начальной точки возьмем , а правилом останова служит выполнение неравенства . Рассмотрим три способа выбора . Фиксированная длина шага . В качестве возмем некоторое постоянное для всех итераций значение. Например, возьмем для всех и результаты расчета запишем в таблицу 1.1.

Изм.

Лист

№ докум.

Подпись

Дата

Лист

220700.02.11.0986.000

Таблица 1.1

Номер интерации	x1k	x2k	df(xk)/dx1	df(xk)/dx2	||f҆҆҆ ′(xk)||	f(xk)
				-2	9,797959	-4
	0,979379	2,204124	-0,20621	-1,59175	1,605053	-9,36446
	1,107853	3,195837	1,078531	0,391674	1,147448	-9,90349
	0,167914	2,854493	-8,32086	-0,29101	8,325942	-6,517
	1,167303	2,889446	1,673035	-0,22111	1,687582	-9,84783
	0,175924	3,020467	-8,24076	0,040933	8,240863	-6,60407
	1,175911	3,015499	1,759115	0,030999	1,759388	-9,84504

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

Последовательное (поитерационное) уменьшение .

Зададим некоторое значение и далее величина шага будет поитерационно уменьшается по формуле

Для рассматриваемого примера положим и результаты расчета оформить в таблице 2.

Номер интера-ции	x1k	x2k	αk	df(xk)/dx1	df(xk)/dx2	||f҆҆҆ ′(xk)||	f(xk)
					-2	9,797959	-4
	-0,04124	2,408248		-10,4124	-1,1835	10,47946	-4,22891
	0,952361	2,521184	0,5	-0,47639	-0,95763	1,069583	-9,75939
	1,17506	2,96885	0,25	1,750604	-0,0623	1,751712	-9,8458
	0,925219	2,977741	0,125	-0,74781	-0,04452	0,749138	-9,97154
	1,049998	2,985169	0,0625	0,499976	-0,02966	0,500855	-9,98728
	0,987607	2,988871	0,03125	-0,12393	-0,02226	0,12591	-9,99911
	1,018365	2,994395	0,01562	0,183651	-0,01121	0,183993	-9,99828
	1,002769	2,995347	-	0,027692	-0,00931	0,029214	-9,99994

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

Изм.

Лист

№ докум.

Подпись

Дата

Лист

220700.02.11.0986.000

Определение оптимального значения

Если выбирается из условия

(1)

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

Выполним расчеты на нулевой итерации. В исходной точке нормированный градиент равен (0,9806, -0,1961). Тогда

Вычислим производную по от полученной функции и приравняем её к нулю:

откуда получаем искомое значение .

Определим следующую точку

Вычислим градиент в точке

построим

Вычислим производную по от полученной функции и приравняем её к нулю:

Определим искомое значение

Аналогичным построением позволяют на 4-й итерации добиться решения задачи (таблица 3)

Таблица 3

k	x1k	x2k	df(xk)/dx1	df(xk)/dx2	||f′(xk)||	αk	f(xk)
				-2	10,198	1,052	-4
	0,968429	2,206314	-0,31571	-1,58737	1,61846	0,702	-9,36508
	1,105366	2,894829	1,053662	-0,21034	1,07445	0,11	-9,93343
	0,997495	2,916363	-0,02505	-0,16727	0,16914	0,078	-9,99297
							-10

k	f′(x1)/||f′(x1)||	f′(x2)/||f′(x2)||
	0,980580676	-0,1961161
	-0,195067056	-0,9807899
	0,980650378	-0,1957673
	-0,148122568	-0,988969
	-	-

Изм.

Лист

№ докум.

Подпись

Дата

Лист

220700.02.11.0986.000

Метод наискорейшего спуска обладает большей скоростью сходимости по сравнению с двумя предыдущими методами.

Ответ:

Изм.

Лист

№ докум.

Подпись

Дата

Лист

220700.02.11.0986.000

2.Задача 2.6

а)Решить графическим методом следующие задачи линейного программирования.

f=-x₁+2x₂→ max (min),

x₁-8x₂≤10,

x₁+x₂≥1,

x₁-5x₂≥-5,

3x₁+10x₂≤30,

x₁≥0, x₂≥0.

Решение.

f=- x ₁+2 x ₂→ max,

x ₁ -8 x ₂ ≤ 10, (1)

x ₁ + x ₂ ≥ 1, (2)

x ₁ -5 x ₂ ≥-5, (3)

3x₁+10x₂≤30 (4)

x ₁ ≥ 0, x ₂ ≥ 0.

1.Строим область допустимых решений задачи. Нумеруем ограничения задачи.

2.Решаем уравнение х ₁ - 8 х ₂ = 10,получаем две точки x ₁ = 0, x ₂ =-1,25 и x ₁ = =10, x ₂ =0.

В прямоугольной декартовой системе координат (рис. 2.1) по этим точкам строим прямую х ₁ - 8 х ₂ = 10 (L₁), соответствующую ограничению (1). Подставляем в неравенство координаты какой-либо точки, не лежащей на прямой. Находим, какая из двух полуплоскостей, на которые эта прямая делит всю координатную плоскость, является областью решений неравенства (1). Стрелки на концах прямой L₁ направлены в полуплоскость, которая является областью решений неравенства.

3. Решаем уравнение x ₁ + x ₂ =1,получаем две точки x ₁ = 0, x ₂ =1 и x ₁ = 1, x ₂ =0.

В прямоугольной декартовой системе координат (рис. 2.1) по этим точкам

Изм.

Лист

№ докум.

Подпись

Дата

Лист

220700.02.11.0986.000

строим прямую x ₁ + x ₂ =1 (L₂), соответствующую ограничению (2). Подставляем в неравенство координаты какой-либо точки, не лежащей на прямой. Находим, какая из двух полуплоскостей, на которые эта прямая делит всю координатную плоскость, является областью решений неравенства (2). Стрелки на концах прямой L₂ направлены в полуплоскость, которая является областью решений неравенства.

Рис.2.1

4. Решаем уравнение x ₁ -5 x ₂ =-5,получаем две точки x ₁ = 0, x ₂ =1 и x ₁ = -5,
x ₂ =0.В прямоугольной декартовой системе координат (рис. 2.1) по этим точкам строим прямую x ₁ -5 x ₂ =-5 (L₃), соответствующую ограничению (3). Подставляем в неравенство координаты какой-либо точки, не лежащей на прямой. Находим, какая из двух полуплоскостей, на которые эта прямая делит

всю координатную плоскость, является областью решений неравенства (3). Стрелки на концах прямой L₃ направлены в полуплоскость, которая является областью решений неравенства.

5. Решаем уравнение3x₁+10x₂=30,получаем две точки x ₁ = 0, x ₂ =1 и x ₁ = -5,
x ₂ =0.В прямоугольной декартовой системе координат (рис. 2.1) по этим точкам строим прямую 3x₁+10x₂=30 (L₄), соответствующую ограничению (4). Подставляем в неравенство координаты какой-либо точки, не лежащей на прямой. Находим, какая из двух полуплоскостей, на которые эта прямая делит всю координатную плоскость, является областью решений неравенства (4). Стрелки на концах прямой L₄ направлены в полуплоскость, которая является областью решений неравенства.

6.Находим общую часть полуплоскостей решений, учитывая при этом условия неотрицательности; полученную область допустимых решений отметим на рис. 2.1 штриховкой.

7.Строим нормаль линий уровня ñ = (1, 2) и линию уровня, например x ₁+2 x ₂=0. Так как решается задача на отыскание максимума целевой функции,

то линию уровня

Изм.

Лист

№ докум.

Подпись

Дата

Лист

220700.02.11.0986.000

перемещаем в направлении нормали до опорной прямой. Эта прямая проходит через точку X* пересечения прямых, ограничивающих об­ласть допустимых решений и соответствующих неравенствам (1) и (4). Определяем, координаты точки X* =L₁∩L₄.

Решаем систему x ₁ -8 x ₂ = 10, x ₁ =8 x ₂ + 10,

3x₁+10x₂=30; 3(8 x ₂ + 10)+10x₂=30

34 x ₂ =30-30; x ₂ =0; x₁=10

получаем X* = (10, 0)

Вычисляем Z(X*) = x ₁+2 x ₂=10 + 2 • 0 = 10.

Ответ: max Z(X) = 10 при X* = (10, 0).

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

f=-x₁+2x₂→min,

x₁-8x₂≤10,

x₁+x₂≥1,

x₁-5x₂≥-5,

3x₁+10x₂≤30,

x₁≥0, x₂≥0.

Решение: f=-x₁+2x₂→ min

x ₁ -8 x ₂ ≤ 10, (1)

x ₁ + x ₂ ≥ 1, (2)

x ₁ -5 x ₂ ≥-5, (3)

3x₁+10x₂≤30 (4)

x ₁ ≥ 0, x ₂ ≥ 0.

В задаче на отыскание минимума функции выполняем пункты с 1по 5 предыдущей задачи на отыскание максимума функции. Строим область допустимых решений, нормаль линий уровня ñ = (1, 2) и одну из линий уровня, имеющую общие точки с этой областью (рис. 2.). Перемещаем линию уровня в направлении, противоположном направлению нормали ñ, так как решается задача на отыскание минимума функции.

Рис.2.2

Изм.

Лист

№ докум.

Подпись

Дата

Лист

220700.02.11.0986.000

Опорная прямая проходит через точку пересечения прямой L₂ и оси абсцисс х _1. Эту точку Х* =L₂∩ х ₁, находим, решая систему уравнений:

x ₁ + x ₂ =1 x ₁ =1 X * = (1, 0)

x ₂=0; x ₂ =0 Вычисляем Z(X*) = x ₁+2 x ₂=1 + 2 • 0 = 1.

Ответ: min Z(X) = 1.

Изм.

Лист

№ докум.

Подпись

Дата

Лист

220700.02.11.0986.000

3.Задача 3.6

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

f=-x₁+2x₂→ max,

x₁-8x₂≤10,

x₁+x₂≤1,

3x₁+10x₂≤3,

x₁≥0, x₂≥0.

Приведем условие задачи к каноническому виду

f(х)+x₁-2x₂=0,

x₁-8x₂+х₃=10,

x₁+x₂+х₄=1,

3x₁+10x₂+х₅=3,

x₁≥0, x₂≥0.

Составим симплекс-таблицу(3.1).

БП	СЧ	Х1	Х2	Х3	Х4	Х5	α1
Х3			-8				-1,25
Х4
Х5							0,3
f			-2

Таблица 3.1.

В строке коэффициентов целевой функции найдем наибольшее отрицательное значение (-2).Столбец, соответствующий этому значению называется веду- щим. Разделим значения свободных членов на соответствующие значения ведущего столбца. В результате получим значения α_1.Выберем среди них наименьшее положительное значение (0,3).Соответствующая строка Х5 является ведущей.Пересечение ведущей строки и ведущего столбца дает ведущий элемент 10.

Изм.

Лист

№ докум.

Подпись

Дата

Лист

220700.02.11.0986.000

Разделим все элементы ведущей строки на ведущий элемент 10.Обозначение ведущей строки Х₅ заменим на обозначение ведущего столбца Х₂.Составим вторую симплекс - таблицу(3.2), используя преобразования:

новая Х₃=старая Х₃-(-8)*новая Х₂;

новая Х₄= старая Х₄-новая Х₂;

новая f=старая f-(-2)*новая Х₂.

БП	СЧ	Х1	Х2	Х3	Х4	Х5	α2
Х2	0,3	0,3				0,1
Х3	12,4	3,4				0,8
Х4	0,7	0,7				-0,1
f	0,6	1,6				0,2

Таблица 3.2

Все значения в строке функции базиса Х₂, Х₃, Х₄ не отрицательны. Следовательно, α₂=(0; 0,3; 12,4; 0,7; 0). Поэтому β=(0; 0,3)-оптимальное решение исходной задачи, при этом f(β)=0,6.

Ответ: β=(0; 0,3); f(β)=0,6.

Изм.

Лист

№ докум.

Подпись

Дата

Лист

220700.02.11.0986.000

4.Задача 4.6

Решить транспортную задачу, с заданными начальными условиями:

Транспортные издержки (матрица C)	Объём производства (матрица А)	Объём потребления (матрица В)
1 4 2 5 2 1 4 1 3 2 1 3	6,3,3	4,2,4,2

Решение:

1. Найдем опорный план перевозок. Для этого распределим груз между потребителями так, чтобы каждый из них получил требуемое количество груза.

Таблица 4.1.

Поставщик	Потребитель	Объём производства	U
B1	B2	B3	B4
A1	4 1	… 4	2 2	… 5
A2	… 2	1 1	… 4	2 1		-2
A3	… 3	1 2	2 1	… 3		-1
Объём потребления
V

Изм.

Лист

№ докум.

Подпись

Дата

Лист

220700.02.11.0986.000

2. Найдем потенциалы поставщиков и потребителей. Для этого составим уравнения для заполненных клеток таблицы:

U₁+V₁=1, U₁+V₃=2, U₂+V₂=1,

U₂+V₄=1, U₃+V₃=2, U₃+V₃=1.

Пусть U₁=0.Тогда все остальные потенциалы для данного опорного решения можно определить:

U₁=0, V₁=1, V₃=2, U₃=-1, U₂=-2, V₄=3, V₂=3.

3.Затем для проверки оптимальности опорного плана просмотрим свобод- ные клетки, для которых определяем косвенные тарифы C'_ij =U_i + V_j.

C'₁₂ =U₁+V₂=0+3=3, C'₁₄ =U₁+V₄=0+3=3, C'₂₁ =U₂+V₁=-2+1=-1,

C'₂₃ =U₁+V₃=-2+2=0, C'₃₁ =U₃+V₁=-1+1=0, C'₃₄ =U₃+V₄=-1+3=2.

4.Далее для каждой свободной клетки вычислим оценки, то есть разницу между тарифом и косвенным тарифом S_ij=C_ij - C'_ij.

S₁₂=4-3=1, S₁₄=5-3=2, S₂₁=2-(-1)=3,

S₂₃=4-0=4, S₃₁=3-0=3, S₃₄=3-2=1.

Полученный план является оптимальным, так как он не содержит не одной отрицательной разности S_ij.

Оптимальный план имеет вид:

Х_опт.=

Ответ: Х_опт.=

Изм.

Лист

№ докум.

Подпись

Дата

Лист

220700.02.11.0986.000

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

1. Ашмаков С.А. Линейное программирование. – М.: Наука, 1981. – 304 с.

2. Галеев Э.М. Оптимизация: теория, примеры, задачи: Учебное пособие. –

М.: Едиториал УРСС, 2002. – 304 с

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

МГУТУ, Москва, 2004г.

4. Пантелеев А.В. Методы оптимизации в примерах и задачах: Учеб. пособие/

А.В. Пантелеев, Т.А. Летова. – М.: Высш. шк., 2002. – 544 с.