Министерство образования Республики Беларусь

Белорусский государственный университет информатики и радиоэлектроники

Кафедра систем управления

Курсовая работа

по курсу

Математические основы теории систем

на тему

Методы оптимизации

Выполнил: Бальцевич А.В.

Проверил: Стасевич Н.А.

Минск 2011




Содержание

Введение

1 Линейное программирование

1.1 Прямая задача линейного программирования

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

2 Нелинейное программирование

2.1 Найти максимальное значение функции, без учета

ограничений методом наискорейшего спуска

2.2 Найти максимальное значение функции, без учета

ограничений методом Ньютона - Рафсона

2.3 Найти максимальное значение функции, с учетом

системы ограничений методом Зонтейдейка

2.4 Найти максимальное значение функции, с учетом

системы ограничений методом Куна - Такера

Заключение

Литература



Введение


Методы оптимизации - это раздел вычислительной математики, объединяющий методы и алгоритмы решения задач оптимизации функций, а также обосновывающие применение этих методов теоретические результаты. Линейное программирование дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Одним из обобщений линейного программирования является дробно-линейное программирование. В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи: если и — выпуклые функции, то такую задачу называют задачей выпуклого программирования; если, то имеют дело с задачей целочисленного (дискретного) программирования.

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

Математическое программирование — математическая дисциплина, изучающая теорию и методы решения задач о нахождении экстремумов функций на множествах конечномерного векторного пространства, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами).



1 Линейное программирование

1.1 Прямая задача линейного программирования


Найти максимальный план х^* и экстремальное значение функций F(x). Построить задачу, двойственную к исходной, решить ее и сравнить решения прямой и двойственной задачи.

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

Определим значение целевой функции, при следующих условиях-ограничений.
F(x) = -х₁+4х₂+3х₃-5х₄+2х₅ (max)


4х₁+3х₂+2х₃-2х₄-х₅ <12

5х₁-х₂+4х₃-х₄ >10

2х₂+3х₅ <15

x_i > 0, i = 1.5
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных.
4х₁+3х₂+2х₃-2х₄-х₅ +х₆<12

5х₁-х₂+4х₃-х₄ –х₇>10

2х₂+3х₅ +х₈ <15


4х₁+3х₂+2х₃-2х₄-х₅ +х₆ <12

-5х₁+х₂-4х₃+х₄ +х₇ <-10 (-1)

2х₂+3х₅ +х₈<15


На основании вышеизложенного составляем симплекс – таблицы

Таблица 1

БП	св. чл.	X1	Х2	Х3	Х4	Х5
Х6	12	4	3	2	-2	-1
Х7	-10	-5	1	-4	1	0
Х8	15	0	2	0	0	3
F	0	1	-4	-3	5	-2
Таблица 2
БП	св. чл.	X1	Х6	Х3	Х4	Х5
Х2	4	1,333333	0,333333	0,666667	-0,66667	-0,33333
Х7	-14	-6,33333	-0,33333	-4,66667	1,666667	0,333333
Х8	7	-2,66667	-0,66667	-1,33333	1,333333	3,666667
F	16	6,333333	1,333333	-0,33333	2,333333	-3,33333
Таблица 3
БП	св. чл.	X1	Х6	Х3	Х4	Х8
Х2	4,636364	1,090909	0,272727	0,545455	-0,54545	0,090909
Х7	-14,6364	-6,09091	-0,27273	-4,54545	1,545455	-0,09091
Х5	1,909091	-0,72727	-0,18182	-0,36364	0,363636	0,272727
F	22,36364	3,909091	0,727273	-1,54545	3,545455	0,909091
Таблица 4
БП	св. чл.	X1	Х6	Х2	Х4	Х8
Х3	8,5	2	0,5	1,833333	-1	0,166667
Х7	24	3	2	8,333333	-3	0,666667
Х5	5	0	0	0,666667	0	0,290759
F	35,5	7	1,5	2,833333	2	1,166667

Оптимальный план можно записать так:

x1=x2=x4=x6=x8=0,
x3=8,5; x5=5; x7=24; F=35,5,
F(X) = 3*8.5 + 2*5 = 35.5
x*=0; 0; 8,5; 0; 5



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

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

F(x) = -х₁+4х₂+3х₃-5х₄+2х₅ (max)
4х₁+3х₂+2х₃-2х₄-х₅ <12

5х₁-х₂+4х₃-х₄ >10

2х₂+3х₅ <15

x_i > 0, i = 1.5


F(y) = 12у₁-10у₂+15у₃ (min)

-4х₁-3х₂-2х₃+2х₄+х₅ > -12 (-1)

5х₁-х₂+4х₃-х₄ > 10

-2х₂-3х₅ > -15 (-1)

Составляем матрицу и транспонируем ее:

АТ=	-4	5	0
	-3	-1	-2
	-2	4	0
	2	-1	0
	1	0	-3

А=	-4	-3	-2	2	1
	5	-1	4	-1	0
	0	-2	0	0	-3

Составляем уравнения из матрицы


4у₁-5у₂ ≥ -1

3у₁+у₂+2у₃ ≥ 4

2у₁-4у₂ ≥ 3

-2у₁+у₂ ≥ -5

-у₁+3у₃ ≥ 2
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных


4у₁-5у₂ +у₄ ≥ -1

3у₁+у₂+2у₃ +у₅ ≥ 4

2у₁-4у₂ +у₆ ≥ 3

-2у₁+у₂ +у₇ ≥ -5

-у₁+3у₃ +у₈ ≥ 2

На основании вышеизложенного составляем симплекс – таблицы


Таблица 1

БП	св. чл.	y1	y2	y3
y4	-1	4	-5	0
y5	4	3	1	2
y6	3	2	-4	0
y7	-5	-2	1	0
y8	2	-1	0	3
F	0	12	-10	15



Таблица 2

БП	св. чл.	y1	у2	у8
y4	-1	4	-5	0
у5	-8	3,666667	1	-0,66667
y6	3	2	-4	0
y7	-5	-2	1	0
у3	0,666667	-0,33333	0	0,333333
F	10	-17	10	5

Таблица 3

БП	св. чл.	у5	Y2	у8
у4	7,727273	-1	-6,09091	0,727273
у1	-2,18182	0,272727	0,272727	-0,18182
y6	7,363636	-0,54545	-4,54545	0,363636
y7	-9,36364	0,545455	1,545455	-0,36364
у3	-0,06061	0,090909	0,090909	0,272727
F	-27,0909	4,636364	14,63636	1,909091

Таблица 4

БП	св. чл.	у6	у2	у8
у4	7	-2	3	0
у1	1,5	1	-2	0
у5	2,833333	-1,83333	8,333333	-0,66667
y7	2	1	-3	1
у3	1,166667	0,166667	-0,66667	0,333333
F	35,5	8,5	24	5

Оптимальный план можно записать так:


у6=у2=у8=0,
y4=7; у1=1,5; у5=13,5; y7=2; у3=1,17; F=35,5,
F(у) = 12•1,5 + 15•1,17 = 35,5
у*=1,5; 0; 1,17;


Находим соответствие прямой и двойственной задачей



2 Нелинейное программирование

2.1 Найти максимальное значение функции, без учета ограничений метод наискорейшего спуска


Найти максимальное значение функции F(x) = 2x₁-3x₂-0.5x₁²-x₂²+0.5x₁x₂, при ограничениях: 3x₁ + x₂ < 3, x₁ + 2x₂ < 2, x₁ > 0, x₂ > 0, методом наискорейшего спуска.

Начальная точка Х⁰ = [4/5, 3/5].

В данном методе очередная точка при поиске максимума функции вычисляется по формуле k

,

где - градиент функции характеризует направление движения;

х^k - текущие значение точки экстремума;

α^k – параметр характеризующий длину шага.

На первом шаге движение осуществляется из точки х⁰ вдоль вектора в новую точку х¹:


Величина шага α^k на любом шаге выбирается из условия обеспечения экстремума функции в рассматриваемом направлении. Подставляя координаты точки х¹ в функцию F(x), получим:


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




Вычисляется . Если (), поиск прекращается и считается, что х^* = х¹, если нет, переходим к шагу 2.

Пусть


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

Область допустимых значений представлена на рисунке - 2.1

Рисунок 4.1 Область допустимых значений



2.2 Найти максимальное значение функции, без учета ограничений метод Ньютона – Рафсона
Найти максимальное значение функции F(x) = 2x₁-3x₂-0.5x₁²-x₂²+0.5x₁x₂, методом Ньютона - Рафсона. Начальная точка Х⁰ = [4/5, 3/5].

Очередная точка поиска вычисляется в соответствии с выражением

,

где Н(х) – матрица Гесса функции F(х);

Н^-1(х) – обратная по отношению к Н(х) матрица.

,

,

где detH – определитель матрицы;

AdjH – присоединения к Н матрица (транспонированная матрица алгебраических дополнений).

Находим алгебраические дополнения матрицы Н: m_ij, тогда , , , .

Соответственно:


Следовательно, в точке х¹ = [10/7, -8/7] функция F(x) достигает максимального значения F_max = 35,5



2.3 Найти максимальное значение функции, с учетом системы ограничений метод доступных направлений Зойтендейка

Найти максимальное значение функции F(x) = 2x₁-3x₂-0.5x₁²-x₂²+0.5x₁x₂, при ограничениях: 3x₁ + x₂ < 3, x₁ + 2x₂ < 2, x₁ > 0, x₂ > 0, методом допустимых направлений Зойтендейка.

Начальная точка Х⁰ = [4/5, 3/5].

Находим направление вектора градиента в точке х⁰,

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

Определяем интервал допустимых значений для параметра α⁰, при которых точка х¹ будет принадлежать ОДЗП. Для этого координат точки х¹ подставляем в ограничения задачи


Выбираем наиболее сильные из полученных условий, тогда


Находим величину которая обеспечивает максимум функций F(x). Процедура полностью совпадает с первым шагом решения задачи методом наискорейшего спуска, поэтому . Это значение не принадлежит найденному интервалу, поэтому принимается, что . Координаты точек х¹ и значение градиента функции в этой точке определяется выражениями:


_{Вычисляется составляющие вектора градиента в точке х}¹_,


Направление вектора перпендикулярно направлению S¹ , следовательно, данная точка х¹ =[ 1, 0 ] обеспечивает максимум функции F(x).

Рисунок 3.1 Область допустимых значений



2.4 Найти максимальное значение функции, с учетом системы ограничений Метод Куна – Таккера


Найти максимальное значение функции F(x) = 2x₁-3x₂-0.5x₁²-x₂²+0.5x₁x₂, при ограничениях: 3x₁ + x₂ < 3, x₁ + 2x₂ < 2, x₁ > 0, x₂ > 0, используя условия теоремы Куна - Таккера.

Составляется функция Лагранжа:

где g(х) – левые части ограничений, приведенные к нулевой правой части;

λ_j – неопределенные множители Лагранжа:


Точка экстремума является седловой точкой с максимумом по х и минимумом по λ, поэтому ограничения приведены к виду :

2x₁ - 3x₂ - 0.5x₁² - x₂² + 0.5x₁x₂ + λ₁ ()+λ₂()


Условия теоремы Куна – Таккера записываются следующим образом:


Частные производные функции Лагранжа определяются выражением:


Для приведения неравенства к виду равенств вводятся дополнительные неотрицательные переменные V и W. Одновременно свободные члены переносятся в правую часть тогда:




Решение этой системы из четырех алгебраических уравнений, содержащих 8 неизвестных, можно найти с помощью симплекс – процедуры. На первом шаге в базис включаются все введенные дополнительные переменные, тогда первая – симплекс таблица соответствует табл. 1.
Таблица 1

БП	св. чл.	Небазисные переменные
		X1	X2	λ1	λ2
V1	-2	-1	0,5	-3	-1
V2	3	0,5	-1	-1	-2
W1	3	3	1	0	0
W2	2	1	2	0	0

Таблица 2

БП	св. чл.	Небазисные переменные
		V1	X2	λ1	λ2
Х1	2	-1	-1	3	1
V2	2	0,5	-0,75	-2,5	-2,5
W1	-3	3	7	-9	-3
W2	0	1	2,5	-3	-1

Таблица 3

БП	св. чл.	Небазисные переменные
		V1	X2	W1	λ2
Х1	1	0	2	0,333333	0
V2	2,833333	-0,33333	-2,69444	-0,27778	-1,66667
λ1	0,333333	-0,33333	-0,77778	-0,111111	0,333333
W2	1	1	0,166667	-0,33333	0

Область допустимых значений представлена на рисунке - 4.1

Рисунок 4.1 Область допустимых значений


В каждой из таблиц выделен ведущий элемент. Решение, определяемое табл. 3, соответствует допустимому базисному решению х₁=1; v₂ = 2.83; λ₁ = 0.33; W₂ = 1; х₂ = v₁ = λ₂ = W₁ = 0. Кроме того, выполняется условие <sub>, поэтому х1 = 1, является оптимальным решением задачи .



Заключение</sub>
В результате проделанной работы был рассмотрен теоретический материал, посвященный решению прямой и двойственной задачи. Прямая и двойственная модели приводят к одному и тому же решению и к получению одинаковой информации о чувствительности модели. Единственная причина, по которой предпочтение отдается той или иной модели, состоит в том, что одну из них решить, как правило, легче, чем другую. Структура двойственной и прямой задачи одинакова. Если прямая модель линейного программирования построена, из нее легко получить соответствующую двойственную модель.

Метод наискорейшего спуска является одной из наиболее фундаментальных процедур минимизации дифференцируемой функции нескольких переменных. Он является наиболее известным среди градиентных методов. Идея этого метода проста: поскольку вектор градиента указывает направление наискорейшего возрастания функции, то минимум следует искать в обратном направлении. Этот метод работает, как правило, на порядок быстрее других методов.

Метод возможных направлений Зойтендейка. На каждой итерации метода строится возможное направление спуска и затем проводится оптимизация вдоль этого направления.

В теории условия Куна — Таккера: — необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые условия регулярности. Метод является обобщением метода множителей Лагранжа. В отличие от него, ограничения, накладываемые на переменные, представляют собой не уравнения, а неравенства.


Литература

1. 
   Методические указания и контрольные задания по курсу “Методические основы теории систем” для студентов заочной формы обучения /Сост. А.В. Паплова. – Мн.: БГУИР, 2002.
   
2. 
   Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
   
3. 
   Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
   
4. 
   Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд.. — М.: Лаборатория Базовых Знаний, 2000.
   
5. 
   Волков Е. А. Численные методы. — М.: Физматлит, 2003.
   
6. 
   Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
   
7. 
   Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
   
8. 
   Максимов Ю. А.,Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.