Размещено на http://www.allbest.ru/

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

"Уральский государственный технический университет-УПИ"

Нижнетагильский технологический институт (филиал) УГТУ-УПИ

Факультет "Экономики и менеджмента"

Кафедра "Математики"

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

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

Руководитель ст. преподаватель

Халтурина Т. Ю.

Студентка гр. ЭМ 37124-ПМ

Ушакова В.В.

Н. Тагил

2010

Введение

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

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

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

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

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

Цель данной курсовой работы - рассмотреть и изучить основные методы оптимизации. Рассмотреть основные понятия, формулы, теоремы, которые встречаются при решении задач. Также рассмотреть основные приемы решения задач нахождения экстремума и оптимизации в математическом пакете MathCAD. Провести численный расчет, сделать вывод по каждому методу и сравнить их относительно друг друга.

Задачи данной курсовой работы:

1. Изучить численные методы поиска одномерного безусловного экстремума.

2. Рассмотреть численные методы поиска многомерного безусловного экстремума.

3. Решить задачу об проектирования емкости с помощью нахождения условного экстремума.

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

5. Решить задачу линейного программирования, используя программу MathCAD.

6. Познакомится с методами решения транспортной задачи.

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

Задание № 1.1

Для заданной функции решить задачу одномерного поиска f(x)>min(max), xX (XR)и найти промежуток (XR), на котором функция унимодальная.

Пусть f(x) - действительная функция одной переменной, определенная на множестве X (, ). Точка x* X называется точкой локального минимума f(x) на множестве X, если существует такая -окрестность этой точки, что для всех x из этой окрестности, т. е., если | x x*| < , выполняется условие f(x*) f(x). Если выполняется условие f(x*) < f(x), то x* называется точкой строгого локального минимума. У функции может быть несколько локальных минимумов. Точка x* X называется точкой глобального минимума f(x) на множестве X, если для всех x X выполняется условие f(x*) f(x). Значение функции f(x*) называется минимальным значением f(x) на множестве X, Для нахождения глобального минимума необходимо найти все локальные минимумы и выбрать наименьшее значение.

В дальнейшем будем рассматривать задачу нахождения локального минимума.

Известно, что для того, чтобы точка x* была точкой локального минимума дифференцируемой функции f(x), необходимо, чтобы выполнялось равенство

f '(x*) = 0 (1.1)

Точка x*, удовлетворяющая равенству (1.1), называется стационарной точкой. Если функция f(x) дважды дифференцируема, то для того, чтобы стационарная точка x* была точкой строгого локального минимума, достаточно, чтобы выполнялось неравенство

f ''(x*) > 0. (1.2)

Если дважды дифференцируемая функция f(x) задана на отрезке [a, b], то можно предложить следующий путь решения задачи нахождения глобального минимума:

1. Найти все стационарные точки на отрезке [a, b] из условия (1.1), т.е. найти корни уравнения f '(x) = 0, принадлежащие отрезку [a, b].

2. Найденные стационарные точки исследовать на выполнение условия (1.2), т.е. из найденных стационарных точек выделить точки локальных минимумов, для которых выполняется неравенство f ''(x) > 0.

3. Сравнить между собой значения f(x) на концах отрезка [a, b] и в точках локальных минимумов. Наименьшему из этих значений соответствует точка глобального минимума f(x) на отрезке [a, b].

Пусть функция f(x) определена на отрезке [a, b]. Функция f(x) называется унимодальной, если на этом отрезке имеется единственная точка x* локального минимума функции f(x), причем функция строго убывает при x x* и строго возрастает при x x*. Многие алгоритмы минимизации функции одной переменной построены в предположении, что функция унимодальная на некотором отрезке. Этот отрезок будем называть отрезком локализации точки x*.

Из определения унимодальной функции вытекает следующее важное свойство. Пусть f(x) унимодальная функция на отрезке [a, b] и a x1 < x2 b. Тогда

если f(x1) f(x2), то x* [a, x2];

если f(x1) > f(x2), то x* [x1, b], (1.3)

где x* - точка минимума f(x) на отрезке [a, b].

Иллюстрация свойства (1.3) представлена на рис 1.1 и 1.2.

Рис. 1.1

Рис. 1.2.

Аналитический метод нахождения минимума функции одной переменной состоит в решении в явном виде уравнения (1.1) и проверке условия (1.2). Однако во многих случаях это или невозможно, или затруднительно. В таких случаях используются численные методы решения. Мы будем рассматривать методы прямого поиска, основанные на построении минимизирующих последовательностей x1, x2, …, xn, …,. Точки x1, x2, …, xn, … называют пробными точками.

Для эвристического выбора начального интервала неопределенности можно применить Алгоритм Свенна:

1. Задать произвольно следующие параметры: некоторую точку , t>0-величину шага. Положить k=0.

2. Вычислить значение функции в трех точках , ,:

3. Проверить условия окончания:

· если , то начальный интервал неопределенности найден:[ ] = [];

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

· если условие окончания не выполняется, то перейти к шагу 4.

4. Определить величину :

· если , то ;;; k=1;

· если , то ; ; ; k=1.

Найти следующую точку

5. Проверить условие убывания функции

· если и , то;

если и , то.

в обоих случаях положить k=k+1 и перейти к шагу 5;

· Если , процедура завершается. При положить , а при положить . В результате [ ] - искомый начальный интервал неопределенности.

Реализация данной задачи в пакете MathCAD 14

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

Задание функции, реализующей алгоритм Свенна:



Из чего можно сделать вывод, что f(x) унимодальная на отрезке [-2,0],

Задание № 1.2

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

Реализация данной задачи в пакете MathCAD 14

Данную задачу мы решаем для следующей функции:

Графическое изображение функции f(x):

Найдем производную первого порядка для данной функции:

Графическое изображение производной первого порядка данной функции:

Найдем производную второго порядка для данной функции:



Графическое изображение производной второго порядка данной функции:

Изучив данные графики можно сделать вывод, что функция имеет локальный максимум в точке (-1,0).

Задание № 1.3

Найти минимум функции методом перебора с заданной точностью.

Метод перебора

Этот метод является простейшим из прямых методов минимизации.

Пусть f(x) - унимодальная на отрезке [a, b] функция. Разобьем отрезок

[a, b] на n равных частей точками x0, x1, x2, …, xn, так, что

xi = a + ih, i = 0, 1, … , n,

h =.

Вычислим значения функции f(x) в точках xi и сравнив их, найдем точку xm, для которой

f(xm) = f(xi).

За приближение x* примем xm.

Оценим погрешность метода перебора.

В силу выбора точки xm справедливы неравенства

f(xm-1) f(xm), т.е. x* [xm-1, b];

f(xm) f(xm+1), т.е. x* [a, xm+1].

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

x* [xm-1, b] [a, xm+1] = [xm-1, xm+1].

Длина отрезка [xm-1, xm+1] равна , и точка xm является его серединой.

Поэтому

xm - x* = n.

Итак, чтобы обеспечить требуемую точность определения минимума функции f(x) методом перебора, нужно число отрезков разбиения n выбрать из условия , т.е.

n . (1.4)

Реализация данной задачи в пакете MathCAD 14

Данную задачу мы решаем для следующей функции:

Задание функции, реализующей метод перебора с заданной точностью:

В результате решения данной задачи был найден минимум x* = -1, значение функции f(x*) = 0 с точностью 0.043 за 45 итераций.

Задание № 1.4

Найти минимум функции методом поразрядного поиска с заданной точностью.

Метод поразрядного поиска

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

Изложенная идея реализуется в методе поразрядного поиска следующим образом. Перебор точек отрезка происходит сначала с шагом = xi+1- xi > до тех пор, пока функция не начнет увеличиваться, т. е. не выполнится условие f(xi+1) f(xi) или пока очередная точка не совпадет с правым концом отрезка [a, b], на котором ищется минимум функции f(x). После этого шаг уменьшается (обычно в четыре раза) и перебор точек производится в обратном направлении, справа налево, пока значения функции f(x) снова не станут увеличиваться или очередная точка не совпадет с левым концом отрезка и т. д. Процесс завершается, когда перебор в данном направлении закончен, и величина шага не превосходит заданной точности .

Алгоритм метода поразрядного поиска.

Шаг 1. Ввести исходные данные: a, b, .

Шаг 2. Выбрать начальный шаг = . Положить x0 = a. Вычислить f(x0).

Шаг 3. Положить x1 = x0 + . Вычислить f(x1).

Шаг 4. Сравнить f(x0) и f(x1). Если f(x0) > f(x1), то перейти к шагу 5, иначе - к шагу 6.

Шаг 5. Положить x0 = x1 и f(x0) = f(x1). Проверить условие x0 (a, b), т. е. a < x0 < b. Если условие выполнено, перейти к шагу 3, иначе -к шагу 6.

Шаг 6. Проверка на окончание поиска. Если , то вычисления завершить, положив x* x0, f(x* ) f(x0), иначе - перейти к шагу

Шаг 7. Изменение направления и шага поиска. Положить x0 = x1 и f(x0) = f(x1), = - . Перейти к шагу 3.

Реализация данной задачи в пакете MathCAD 14

Данную задачу мы решаем для следующей функции:



Задание функции, реализующей метод поразрядного поиска с заданной точностью:

В результате решения данной задачи был найден минимум x* = -0.998, значение функции f(x*) = 0, количество итераций n = 18.

Задание № 1.5

Найти минимум функции методом деления отрезка пополам с заданной точностью.

Метод деления отрезка пополам (метод дихотомии)

В основе этого метода лежит свойство унимодальной функции (1.3), благодаря которому можно сокращать отрезок локализации точки минимума.

Пусть f(x) - непрерывная и унимодальная на отрезке [a, b] функция, принимающая во всех точках этого отрезка конечные значения. Пусть число пробных точек x1, x2, …, xn конечно, и для определения каждой точки xk можно использовать информацию о значениях функции во всех предыдущих точках x1, x2, …, xk - 1 . Положим a0 = a, b0 = b. Середина отрезка [a, b] = [a0, b0] находится в точке . Выберем две симметричные точки

x1 = , x2 = (1.5)

Величина , удовлетворяющая условию 0 < < b - a , является параметром метода, как правило, - малая величина.

Вычислим значения функции в выбранных точках: f(x1) и f(x2). Определим новый отрезок локализации [a1, b1] следующим образом:

если f(x1) f(x2), то a1 = a0, b1 = x2;

если f(x1) > f(x2), то a1 = x1, b1 = b0.

Далее процедура деления отрезка [a1, b1] повторяется.

Деление продолжают до тех пор, пока половина длины отрезка [an, bn] не станет меньше заданной точности решения задачи , , т. е. пока не выполнится неравенство

< .

Тогда за приближение x* принимают середину отрезка [an, bn], т.е.

x* .

Алгоритм 1.2 (Алгоритм метода дихотомии).

Шаг 1. Ввести исходные данные: a, b, , .

Шаг 2. Определить x1 и x2 по формулам (1.5).

Шаг 3. Вычислить f(x1) и f(x2).

Шаг 4. Если f(x1) f(x2), то перейти к новому отрезку [a, b], положив b = x2. Иначе перейти к новому отрезку [a, b], положив a = x1.

Шаг 5. Если < , то требуемая точность достигнута, перейти к шагу 6, иначе - к шагу 2 для продолжения итераций.

Шаг 6. Положить x* . Вычислить f * f(x*).

Число итераций метода дихотомии оценивается по формуле

n log2.

Величину выбирают из условия 0 < < 2. При этом нужно иметь в виду, что при слишком малом из-за погрешности вычисления на ЭВМ сравнение f(x1) и f(x2) становится затруднительным.

Реализация данной задачи в пакете MathCAD 14

Данную задачу мы решаем для следующей функции:

Задание функции, реализующей метод деления отрезка пополам с заданной точностью:



В результате решения данной задачи был найден минимум x* =-1, значение функции f(x*) = 0, количество итераций n = 11.

Задание № 1.6

Найти минимум функции методом Фибоначчи с заданной точностью.

Метод Фибоначчи

Метод Фибоначчи эффективнее метода дихотомии, так как разбиение отрезка производится таким образом, что на каждой итерации требуется вычислять не два значения f(x1) и f(x2), а лишь одно.

Метод Фибоначчи основан на использовании чисел Фибоначчи, задаваемых рекуррентным соотношением

Fn = Fn-1 + Fn-2 (n 2) (1.6)

с начальными значениями F0 = 1, F1 = 1.

Этот метод был предложен в 1953 г. Кифером.

Формула (1.6) вместе с начальными значениями определяет следующий ряд чисел Фибоначчи :

n	0 1 2 3 4 5 6 7 8 9 10 11 …
Fn	1 1 2 3 5 8 13 21 34 55 89 144 …

Метод Фибоначчи состоит из n шагов.

Положим вначале a0 = a, b0 = b.

На k-ом шаге, k =0, 1, … , n - 1, определим точки x и x из условия

x = ak + (bk - ak), x = ak + (bk - ak). (1.7)

Формулы (1.7) являются основными расчетными формулами метода Фибоначчи

После этого так же, как и в методе дихотомии, определяют новый, меньший отрезок локализации [ak+1, bk+1] по тому же правилу:

если f(x) f(x), то ak+1 = ak, bk+1 = x;

если f(x) > f(x), то ak+1 = x, bk+1 = bk.

Важно, что одна из пробных точек x, xстанет пробной точкой на новом отрезке локализации, т. е. совпадет с одной из точек x, x.

Поэтому на каждой итерации достаточно определить только одно значение f(x), так как другое уже найдено на предыдущей итерации.

В конце вычислений можно взять в качестве приближенного значения

экстремум минимизация функция линейный

x* = x.

После выполнения n итераций погрешность удовлетворяет следующему неравенству:

n = < . (1.8)

Следовательно, если задана требуемая точность , число итераций n определяется из условия < или

Fn +1 > . (1.9)

Заметим, что из (1.9) следует, что число итераций, необходимое для удовлетворения заданной точности , зависит только от длины отрезка b - a и точности и не зависит от вида функции f(x).

Алгоритм 1.3 (Алгоритм метода Фибоначчи):

Шаг 1. Ввести исходные данные: a, b, . Определить число итераций n из условия (1.9). Ввести числа Фибоначчи F0, F1, F2, … , Fn +1.

Шаг 2. Положить k = 0 и определить x1 и x2 по формулам (1.7).

Шаг 3. Вычислить f(x1) и f(x2).

Шаг 4. Проверить критерий окончания вычислений: k = n . Если k < n, перейти к шагу 5, иначе - к шагу 6.

Шаг 5. Перейти к новому отрезку локализации и новым пробным точкам. Если f(x1) f(x2), то положить b = x2, x2 = x1, f(x2) = f(x1), x1= a +(b - a) и вычислить f(x1). Иначе положить a = x1, x1 = x2, f(x1) = f(x2),

x2 = a + (b - a) и вычислить f(x2). Положить k = k +1 и перейти к шагу 4.

Шаг 6. Положить x* x1. Вычислить f * f(x*).

Данную задачу мы решаем для следующей функции:

Задание функции, реализующей метод Фибоначчи с заданной точностью:

 

В результате решения данной задачи был найден минимум x* = -1, значение функции f(x*) = 5.329*10^-15, количество итераций n = 8.

Задание № 1.7

Найти минимум функции методом золотого сечения с заданной точностью.

Метод золотого сечения

В основе этого метода лежит понятие "золотого сечения", введенного Леонардо да Винчи и используемого, в частности, при построении архитектурных сооружений античности и эпохи Возрождения.

Золотым сечением отрезка называется его разбиение на две неравные части, так, что отношение длины всего отрезка к длине его большей части равно отношению длины большей части к длине меньшей части (рис.1.3, слева)

= .

Рис 1.3

Золотое сечение осуществляется двумя точками x1 и x2, расположенными симметрично относительно середины отрезка (рис.1.3, справа). Нетрудно проверить, что

 = = , (1.10)

= = . (1.11)

Точка x1 осуществляет золотое сечение не только отрезка [a, b], но и отрезка [a, x2], а точка x2 осуществляет золотое сечение не только отрезка [a, b], но и отрезка [x1, b]. Действительно,

= = ,

= = .

Из (1.10) и (1.11) получаем:

x1 = a + , x2 = a +. (1.12)

Формулы (1.12) являются основными расчетными формулами метода золотого сечения.

Из (1.12) следует, что x1 + x2 = a + b. Если обозначить r = , то формулы (1.12) можно переписать так:

x1 = b - r(b - a), x2 = a + r(b - a) (1.13)

Процедура деления отрезка [a, b] такая же, как и для методов дихотомии и Фибоначчи. Вычисляются значения функции в выбранных точках: f(x1) и f(x2). Определяется новый отрезок локализации [a1, b1] следующим образом:

если f(x1) f(x2), то a1 = a, b1 = x2;

если f(x1) > f(x2), то a1 = x1, b1 = b.

Далее процедура деления отрезка [a1, b1] повторяется с использованием формул (1.12) или (1.13).

Так же, как и в методе Фибоначчи, одна из пробных точек x1, x2 станет пробной точкой на новом отрезке локализации. Поэтому на каждой итерации достаточно определить только одно значение f(x), так как другое уже найдено на предыдущей итерации.

В конце вычислений можно взять в качестве приближенного значения x* середину последнего из полученных отрезков.

После выполнения n итераций погрешность удовлетворяет следующему неравенству:

n = < .

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

n <.

Алгоритм 1.4 (Алгоритм метода золотого сечения).

Шаг 1. Ввести исходные данные: a, b, . Положить r = , n = .

Шаг 2. Определить x1 и x2 по формулам (1.13).

Шаг 3. Вычислить f(x1) и f(x2).

Шаг 4. Проверить критерий окончания вычислений. Если n <, перейти к шагу 5, иначе - к шагу 6.

Шаг 5. Перейти к новому отрезку локализации и новым пробным точкам. Если f(x1) f(x2), то положить b = x2, x2 = x1, f(x2) = f(x1), x1 = b - r(b - a) и вычислить f(x1). Иначе положить a = x1, x1 = x2, f(x1) = f(x2), x2 = a + r(b - a) и вычислить f(x2). Положить n = rn, перейти к шагу 4.

Шаг 6. Положить x* . Вычислить f * f(x*).

Реализация данной задачи в пакете MathCAD 14

Данную задачу мы решаем для следующей функции:

Задание функции, реализующей метод золотого сечения с заданной точностью:



В результате решения данной задачи был найден минимум x* = -1, значение функции f(x*) = 0, количество итераций n = 16.

Задание № 1.8

Найти минимум функции методом средней точки с заданной точностью.

Метод средней точки(метод бисекции).

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

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

Пусть f(x) - унимодальная, непрерывно дифференцируемая на отрезке [a, b] функция и на этом отрезке точка x* является единственной стационарной точкой. Сведем задачу нахождения минимума функции f(x) к решению нелинейного уравнения

f '(x) = 0. (1.14)

Положим a0 = a, b0 = b.

Так как функция f '(x) удовлетворяет условию (1.14), то она принимает на концах отрезка [a0, b0] значения разных знаков, т.е. f(a0)f(b0) < 0.

Разделим отрезок [a0, b0] пополам. Получим точку x0 = . Вычислим f '(x0). Если f '(x0) = 0, то x0 - искомый корень, и задача решена. Если f '(x0) 0, то f '(x0) - число определенного знака: f '(x0) > 0, либо f '(x0) < 0. Тогда либо на концах отрезка [a0, x0], либо на концах отрезка [x0, b0] значения функции f '(x) имеют разные знаки. Обозначим такой отрезок [a1, b1]. Очевидно, что x* [a1, b1], и длина отрезка [a1, b1] в два раза меньше, чем длина отрезка [a0, b0]. Поступим аналогично с отрезком [a1, b1]. В результате получим либо корень x*, либо новый отрезок [a2, b2], и т.д. (рис.1.4 ).

Рис. 1.4

Середина n-го отрезка xn = . Очевидно, что длина отрезка [an, bn] будет равна , а т. к. x* [an, bn], то

| xn - x*| . (1.15)

Оценка (1.15) характеризует погрешность метода средней точки и указывает на скорость сходимости: метод сходится со скоростью геометрической прогрессии, знаменатель которой q = 1/2.

Если задана требуемая точность , то процесс вычислений следует закончить, когда выполнится условие f '(xn) , после чего полагают

x* xn.

Алгоритм 1.5 (Алгоритм метода средней точки).

Шаг 1. Ввести исходные данные: a, b, .

Шаг 2. Определить x0 = .

Шаг 3. Вычислить f '(x0).

Шаг 4. Проверить критерий окончания вычислений. Если f '(x0) , ,перейти к шагу 6, иначе - к шагу 5.

Шаг 5. Перейти к новому отрезку локализации [a, b]. Если f '(x0) > 0, то положить b = x0. Иначе положить a = x0. Перейти к шагу 2.

Шаг 6. Положить x* x0. Вычислить f'(x*).

Реализация данной задачи в пакете MathCAD 14

Данную задачу мы решаем для следующей функции:

Задание функции, реализующей метод средней точки с заданной точностью:

В результате решения данной задачи был найден минимум x* = -1, значение функции f(x*) = 0, количество итераций n = 14.

Задание № 1.9

Найти минимум функции методом Ньютона с заданной точностью.

Метод Ньютона

Пусть f(x) - дважды непрерывно дифференцируемая функция, причем

f ''(x) > 0. Тогда, как уже указывалось в предыдущем разделе, решение задачи минимизации функции f (x) сводится к решению нелинейного уравнения f '(x) = 0.

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

Пусть корень x* [a, b], так, что f '(a)f '(b) < 0. Положим x0 = b. Проведем касательную к графику функции y = f '(x) в точке B0 = (x0, f '(x0))

Рис. 1.5

Уравнение касательной будет иметь вид:

y - f '(x0) = f"(x0)(x - x0). (1.16)

Первое пересечение получим, взяв абсциссу точки пересечения этой касательной с осью OX, т. е. положив в (1.16) y = 0, x = x1:

x1 = x0 - . (1.17)

Аналогично поступим с точкой B1(x1, f '(x1)), затем с точкой B2(x2, f '(x2)), и т. д. в результате получим последовательность приближений x1, x2, …, xn , …, причем

xn +1 = xn - . (1.18)

Формула (1.18) является расчетной формулой метода Ньютона.

При заданной точности > 0 вычисления по формуле (1.18) нужно вести до

тех пор, пока не будет выполнено неравенство| f '(xn)| , после чего полагают x* xn.

Алгоритм 1.6 (Алгоритм метода Ньютона).

Шаг 1. Ввести исходные данные: a, b, . Положить n = 0, x0 = b.

Шаг 2. Вычислить f '(xn) и f "(xn).

Шаг 3. Вычислить xn +1 = xn - .

Шаг 4. Проверить критерий окончания вычислений. Если f '(x n +1) , , перейти к шагу 6, иначе - к шагу 5.

Шаг 5. Положить n = n +1. Перейти к шагу 2.

Шаг 6. Положить x* xn +1 . Вычислить f'(x*).

Реализация данной задачи в пакете MathCAD 14

Данную задачу мы решаем для следующей функции:

Задание функции, реализующей метод Ньютона с заданной точностью:

В результате решения данной задачи был найден минимум x* = -1, значение функции f(x*) = 0, количество итераций n = 13.

Задание № 1.10

Таблица 1 Результаты нахождения минимума функции разными численными методами поиска

Метод	Значение аргумента	Значение функции	Количество итераций	Точность
Метод перебора	-1	0	45	0.045
Метод поразрядного поиска	-0.98	0	18
Метод деления отрезка пополам	-1	0	11
Метод Фибоначчи	-1	0	8
Метод золотого сечения	-1	0	16
Метод средней точки	-1	0	14
Метод Ньютона	-1	0	13

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

Задачи многомерной безусловной минимизации

Для заданной функции решить задачу многомерной безусловной минимизации f(x1, x2), xX (XR) и начальной точки x0.

Пусть f(x) = f(x1, x2, … ,xn) - действительная функция n переменных, определенная на множестве X Rn. Точка x* X называется точкой локального минимума f(x) на множестве X, если существует такая -окрестность этой точки, что для всех x из этой окрестности, т. е., если

x x* < , выполняется условие f(x*) f(x). Если выполняется условие

f(x*) < f(x), то x* называется точкой строгого локального минимума. У функции может быть несколько локальных минимумов. Точка x* X называется точкой глобального минимума f(x) на множестве X, если для всех x X выполняется условие f(x*) f(x). Значение функции f(x*) называется минимальным значением f(x) на множестве X, Для нахождения глобального минимума необходимо найти все локальные минимумы и выбрать наименьшее значение. В дальнейшем будем рассматривать задачу нахождения локального минимума.

Теорема 1(необходимое условия экстремума первого порядка)Пусть есть точка локального минимума(максимума) функции f(x) на множестве и она дифференцируема в точке х* . Тогда градиент функции в точке х* равен нулю.

Теорема 2(достаточное условие): Пусть функция f(x) в точке дважды дифференцируема, ее градиент равен нулю, а матрица Гессе является положительно определенной(отрицательно определенной), т е.

 ()

Тогда точка х* есть точка локального минимума(максимума)функции на множестве .

Для определения знака матрицы Гессе используется критерий Сильвестра.

Задание № 2.1

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

Данную задачу будем решать для функции f(x,y):

- Начальная точка

; x0=(1.5,1.5)

Найдем частные производные первого порядка функции f(x):

; ; ;

Найдем производные второго порядка функции f(x):

Составим матрицу Гессе

Классифицируем матрицу Гессе, используя критерий Сильвестра:

Следовательно, матрица является положительно определенной.

Используя критерии проверки достаточных условий экстремума, можно сделать вывод: точка - является точкой локального минимума

Значение функции в точке минимума:

;

Задание № 2.2

Найти минимум данной функции методом дробления шага.

Метод градиентного спуска с дроблением шага

Метод градиентного спуска является одним из самых распространенных и самых простых методов решения задачи безусловной оптимизации. Он основан на свойстве градиента функции, согласно которому направление градиента совпадает с направлением наискорейшего возрастания функции, а направление антиградиента - с направлением наискорейшего убывания функции. При решении задачи безусловной минимизации за направление спуска из точки x(m) выбирается p(m) = -g(x(m)) = -f '(x(m)). Таким образом, итерационная процедура (2.20) для этого метода имеет вид

x(m+1) = x(m) - (m)g(x(m)). (2.24)

Для выбора шага (m) можно использовать процедуру дробления шага, которая состоит в следующем. Произвольно фиксируют начальное значение шага (m) = (m - 1) = . Если в точке x(m+1), вычисленной в соответствии с (2.24), выполняется неравенство

f(x(m+1)) > f(x(m)),

то шаг дробится, например, пополам, т.е. полагается (m +1) = 0.5(m).

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

f(x) = (Ax, x) + (b, x) + c

с симметричной положительно определенной матрицей A.

Алгоритм (Алгоритм метода градиентного спуска с дроблением шага для квадратичной функции).

Шаг 1. Для квадратичной функции f(x) = + + с ввести матрицу A =(aij), вектор b = (b1, b2, … , bn)T и коэффициент c, i = 1, … , n;

j = 1, … , n. Выбрать произвольную начальную точку x = (x1, x2, … , xn)T, например, x = (0, 0, … , 0)T, начальный шаг и > 0. Вычислить f(x).

Шаг 2. Вычислить g = f '(x) = Ax + b, или покоординатно

g = (g1, g2, … , gn)T,

gi = + bi, i = 1, …, n.

Шаг 3. Проверить выполнение критерия окончания вычислений: f '(x) < , Если это условие выполнено, вычисления закончить и за приближенное значение точки минимума принять точку x* = x = (x1, x2, … , xn)T. В противном случае перейти к шагу 4.

Шаг 4. Вычислить

y = (y1, y2, … , yn), yi= xi- gi, i = 1, …, n.

Шаг 5. Вычислить f(y).

Шаг 6. Если f(y) < f(x), то положить x = y, f(x) = f(y) и перейти к шагу 2, иначе - перейти к шагу 7.

Шаг 7. Положить = и перейти к шагу 4.

Реализация данной задачи в пакете MathCAD 14

Данную задачу мы решаем для следующей функции:

Задание функции, реализующей метод дробления шага:

В результате решения данной задачи был найден минимум x* = (-0.182; -0.091), значение функции f(x*) = -0.091 количество итераций n = 17.

Задание № 2.3

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

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

В методе наискорейшего спуска величина шага (m) из (2.24) находится в результате решения задачи одномерной минимизации

(m)() = f(x(m) - g(x(m))) min, > 0. (2.25)

На рис. 2.3 изображена геометрическая иллюстрация этого метода. Из начальной точки x(0) перпендикулярно линии уровня f (x) = f (x(0)) в направлении p(0) = -g(0) спуск продолжают до тех пор, пока не будет достигнуто минимальное вдоль луча x(0) - g(0) значение функции f. В найденной точке x(1) этот луч касается линии уровня f(x) = f(x(1)). Затем из точки x(1) проводят спуск в перпендикулярном линии уровня направлении

p(1) = -g(1) до тех пор, пока соответствующий луч не коснется в точке x(2) проходящей через эту точку линии уровня и т. д.

Рис. 2.3

Для квадратичной функции f(x) = (Ax, x) + (b, x) + c с симметричной положительно определенной матрицей A эту задачу можно решить аналитически. Величина шага (m), удовлетворяющая условию (2.25).

(m) = (2.26)

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

Алгоритм 2 (Алгоритм метода наискорейшего спуска для квадратичной функции).

Шаг 1. Для квадратичной функции f(x) = + + с

ввести матрицу A =(aij), вектор b = (b1, b2, … , bn)T и коэффициент c,

i = 1, … , n; j = 1, … , n. Выбрать произвольную начальную точку x = (x1, x2, … , xn)T, например, x = (0, 0, … , 0)T и погрешность вычислений > 0.

Шаг 2. Вычислить g = f '(x) = Ax + b, или покоординатно

g = (g1, g2, … , gn)T,

gi = + bi, i = 1, …, n.

Шаг 3. Для заданной точности вычислений проверить выполнение критерия окончания вычислений.: f '(x) < , Если это условие выполнено, вычисления закончить и за приближенное значение точки минимума принять точку x* = x = (x1, x2, … , xn)T, f* = f(x*).

В противном случае перейти к шагу 4 для продолжения итерационного процесса.

Шаг 4. (Шаги 4 - 7 используются для вычисления величины шага (m) по формуле (2.26)

Вычислить

B1= (g, g) =.

Шаг 5. Вычислить

Ag = (A1, A2, … , An)T, где

Ai = , i = 1, …, n.

Шаг 6. Вычислить

B2 = (Ag, g) =.

Шаг 7. Вычислить

= .

Шаг 8. Положить

x = x - g(x)

или покоординатно xi = xi - gi, i = 1, …, n. Перейти к шагу 2.

Реализация данной задачи в пакете MathCAD 14

Данную задачу мы решаем для следующей функции:

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

В результате решения данной задачи был найден минимум

x* = (-0.1813628451;-0.090478367),

значение функции f(x*) = -0.0909084795 количество итераций n = 10.

Задание № 2.4

Найти минимум данной функции методом покоординатного спуска.

Метод покоординатного спуска

Пусть нужно найти минимум функции f(x1, x2, … ,xn). Основная идея метода покоординатного спуска состоит в последовательной минимизации функции f(x1, x2, … ,xn) сначала в направлении координатной оси x1, затем в направлении координатной оси x2 и т. д. После окончания минимизации в направлении координатной оси xn цикл повторяется. Метод покоординатного спуска не требует вычисления производных функции f(x1, x2, … ,xn), поэтому целесообразно использовать критерии окончания вычислений в виде (2.21) или (2.22).

Опишем сначала алгоритм метода покоординатного спуска в общем виде.

Алгоритм (Алгоритм метода покоординатного спуска).

Шаг 1. Выбрать произвольную начальную точку x(0) = (x, x, … , x)T, например, x(0) = (0, 0, … , 0)T и погрешность вычислений > 0. Вычислить f (x(0) ).

Шаг 2. Положить j =1.

Шаг 3. Рассмотреть функцию f(x1, x2, … ,xn) как функцию одной переменной xj, а все остальные переменные зафиксировать. Найти x, решив задачу одномерной минимизации, т.е.найти

f(x1, x2, ,xn).

Шаг 4. Если j < n, то положить j = j + 1 и перейти к шагу 3. В противном случае перейти к шагу 5.

Шаг 5. Найдено очередное приближение x(1) = (x, x, …, x). Проверить критерий окончания вычислений

x(1) - x(0) < или f(x(1)) - f(x(0)) < . Если критерий окончания вычислений выполнен, то положить x* = x, f* = f(x*) и закончить вычисления. В противном случае положить x(0) = x(1) , f*(x(0)) = f(x(1)) и перейти к шагу 2.

На рис. 2.4 изображена геометрическая иллюстрация циклического покоординатного спуска.

Рис. 2.4

Применим метод покоординатного спуска для квадратичной функции f(x) = (Ax, x) + (b, x) + c с симметричной положительно определенной матрицей A.

Выберем произвольную начальную точку x(0) = (x, x, … , x)T. Рассмотрим функцию f(x1, x, … , x) как функцию одной переменной x1, а все остальные переменные зафиксируем. Найдем значение x1 = x, при котором достигается f(x1, x, … , x).

При этом необходимо, чтобы = 0.

Это условие можно записать в следующем виде:

a11x1 + + b1 = 0,

x= - (+ b1).

Затем рассмотрим функцию f(x, x2, x… , x) как функцию одной переменной x2, а все остальные переменные зафиксируем. Найдем значение x, при котором достигается f(x, x2, x… , x). Пусть на очередном

j-ом шаге функция f(x1, x2, … ,xn) рассматривается как функция одной переменной xj, а все остальные переменные зафиксированы. Значение xj, определяется из условия f(x, x, … , x, xj, x, …, x). При этом необходимо, чтобы

= 0.

Это условие можно записать в следующем виде:

+ bj = 0.

Отсюда

x = -( + bj). (2.27)

В результате n шагов будет получено первое приближение

x(1) = (x, x, …, x).

Затем итерационный процесс может быть продолжен. Опишем алгоритм этого процесса.

Алгоритм (Алгоритм метода покоординатного спуска для квадратичной функции).

Шаг 1. Для квадратичной функции f(x) = + +с ввести матрицу A =(aij), вектор b = (b1, b2, … , bn)T и коэффициент c,

i = 1, … , n; j = 1, … , n. Выбрать произвольную начальную точку

x = (x1, x2, … , xn)T, например, x(0) = (x, x, … , x)T и погрешность вычислений > 0. Вычислить f(x(0)).

Шаг 2. В цикле по m = 0, …

В цикле по j =1, … , n вычислить

x = -(+ bj).

Если верхний предел суммирования окажется меньше нижнего, то положить = 0. Положить x(1) = x = (x, x, … , x)T.

Шаг 3. Проверить выполнение критерия окончания вычислений:

x(1) - x(0) = < ,

f(x(1)) - f(x(0)) < .

Если критерий окончания вычислений выполнен, то положить x* = x(1), f*min = f(x*) и закончить вычисления. В противном случае положить x(0) = x(1), f(x(0)) = f(x(1)) и перейти к шагу 2.

Реализация данной задачи в пакете MathCAD 14

Данную задачу мы решаем для следующей функции:

Задание функции, реализующей метод покоординатного спуска:

В результате решения данной задачи был найден минимум

x* = (-0.17998; -0.08507), значение функции f(x*) = -0.09088, количество итераций n = 5.

Задание № 2.5

Найти минимум данной функции методом Ньютона.

Метод Ньютона

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

Метод Ньютона для функции многих переменных является обобщением метода Ньютона для одномерного случая (разд. 1.8)

Пусть дана дважды непрерывно дифференцируемая функция n переменных f(x) = f(x1, x2, … ,xn) и начальная точка x(0) = (x, x, … , x)T.

Разложим функцию f(x) в ряд Тейлора в точке x(0) как функцию многих переменных и ограничимся тремя членами:

f(x)=f(x(0)) + (2.28)

Пусть x(m) приближенное значение точки минимума, полученное на m-ом шаге итерационного процесса. Разложение (2.28) будет иметь место и для точки x(m), а именно

f(x)=f(x(m))+ (2.29)

или в векторной форме

f(x) f(x(m)) + (g(x(m)), (x - x(m)) + (G(x(m))(x - x(m)), (x - x(m))), (2.30)

где G(x(m)) - матрица Гессе (матрица вторых производных) функции f(x) в точке x(m).

Из соотношения (2.29) видно, что в окрестности точки x(m) поведение функции f(x) может быть приближенно описано квадратичной функцией с точностью до величины порядка o(||x - x(m)||)2

Необходимое условие минимума - равенство нулю в точке минимума первой производной функции f(x), т. е.

f '(x) g(x(m)) + G(x(m))(x - x(m)) = 0. (2.31)

Умножим (2.31) на G-1(x(m)):

G-1(x(m))g(x(m)) + (x - x(m)) = 0.

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

x = x(m) - G-1(x(m))g(x(m)).

Пусть точка минимума x* x(m+1). Тогда

x(m+1) = x(m) - G-1(x(m))g(x(m)). (2.32)

Формула (2.32) является расчетной формулой метода Ньютона.

Для квадратичной функции матрица Гессе есть матрица квадратичной формы, равенство (2.31) является точным, и решение (точка минимума) находится за одну итерацию. В общем случае метод Ньютона обеспечивает , как правило, быструю сходимость. Недостатком метода Ньютона является необходимость на каждой итерации вычисления матрицы Гессе и обратной к ней матрицы. Кроме того, если начальная точка выбрана недостаточно близко к точке минимума x*, то последовательность x(0), x(1), …, x(m), … может расходиться. Для избежания подобной ситуации используется обобщенный метод Ньютона, со следующей расчетной формулой:

x(m+1) = x(m) - (m)G-1(x(m))g(x(m)). (2.33)

Формула (2.33) есть расчетная формула метода спуска (см. формулу (2.18)) с направлением в точке x(m), определяемым вектором

p(m) = G-1(x(m))g(x(m)), и с шагом (m).

Величина шага (m) может быть выбрана из условия одномерной минимизации функции (m)() = f(x(m) - (m)G-1(x(m))g(x(m)).

Формулу (2.32) также можно рассматривать как формулу спуска с шагом

(m)= 1.

Опишем теперь алгоритм метода Ньютона.

Алгоритм (Алгоритм метода Ньютона).

Шаг 1. Выбрать произвольную начальную точку x(0) = (x, x, … , x)T, например, x(0) = (0, 0, … , 0)T и погрешность вычислений > 0.

В цикле по m =0, …, пока не будет выполнен критерий окончания вычислений,

Шаг 2. Вычислить g(x(m)) и G(x(m)).

Шаг 3. Вычислить G-1(x(m)).

Шаг 4. Вычислить x(m+1) = x(m) - G-1(x(m))g(x(m)).

Вычисления продолжить до тех пор, пока не будет выполнен критерий окончания вычислений:

x(m+1) - x(m) = < ,

f(x(m+1)) - f(x(m)) < .

Если критерий окончания вычислений выполнен, то положить x* = x(m+1), f* = f(x*) и закончить вычисления.

В случае, когда f(x) - квадратичная функция, матрица Гессе есть матрица квадратичной формы и не зависит от x (G(x(m)) = A). Для этого случая получим следующий алгоритм.

Алгоритм (Алгоритм метода Ньютона для квадратичной функции).

Шаг 1. Для квадратичной функции f(x) = + +с ввести матрицу A =(aij), вектор b = (b1, b2, … , bn)T и коэффициент

c, i = 1, … , n; j = 1, … , n. Выбрать произвольную начальную точку x = (x1, x2, … , xn)T, например, x = (0, 0, … , 0)T и погрешность вычислений > 0.

Шаг 2. Вычислить

g(x(0)) = (g, g, … , g)T,

g= , i = 1, …, n.

Шаг 3. Вычислить A-1.

Шаг 4. Вычислить x(1) = x(0) - A-1 g(x(0))

Реализация данной задачи в пакете MathCAD 14

Данную задачу мы решаем для следующей функции:

Задание функции, реализующей метод Ньютона

В результате решения данной задачи был найден минимум

x* = ( -0.18182; -0.09091), значение функции f(x*) = -0.09091 количество итераций n = 2.

Задание № 2.7

Таблица 2 Результаты нахождения минимума функции разными численными методами поиска

Метод	Значение аргумента х	Значение аргумента у	Значение функции	Количество итераций
Классический метод	0.181818	-0.09091	-0.09091
Метод дробления шага	-0.182	-0.091	-0.091	17
Метод наискорейшего спуска	-0.18136	-0.09048	-0.09091	10
Метод покоординатного спуска	-0.17998	-0.08507	-0.09088	5
Метод Ньютона	-0.18182	-0.09091	-0.09091	2

По данным таблицы можно сделать вывод, что наиболее точным и наиболее эффективным является метод Ньютона, этот метод считает за наименьшее количество итераций; самым неэффективным методом является метод дробления шага, нашедший минимум функции за 17 итераций.

Методы поиска условного экстремума

Общая постановка задачи: пусть требуется найти экстремум функции f(x), где x=(x1,x2,…,xn) при условии gj(x1,x2,…,xn)=0(*) или gj(x1,x2,…,xn)?0. Предполагается, что функции f, g имеют непрерывные частные производные по всем переменным.

(*)-уравнение связи

Говорят, что точка x* удовлетворяет уравнениям связи (*) и имеет условный max(min), если f(x*)>f(x) (f(x*)<f(x)).

Функция называется обобщенной функцией Лагранжа, числа л0,л1,…лj- множители Лагранжа.

Классическая функция Лагранжа:



Градиентом обобщенной функции Лагранжа по x называется векторный столбец.

Вторым дифференциалом обобщенной функции Лагранжа называется функция.

Ограничение gj(x)?0. называется активным в точке, если gj(x)=0, то ограничение называется пассивным.

Градиенты ограничений g1(x),… gj(x),называются линейно независимыми в точке x, если равенство выполняется только при л0,л1,…лj =л1=…=лj=0 (условие регулярности).

Теорема (принцип Лагранжа): пусть x* - точка локального экстремума, причем - линейно независимые, тогда существует такое лj, что для классической функции Лагранжа выполняются равенства:

(*)

Теорема (расширенный принцип Лагранжа)

Пусть x* - точка минимума (максимума) и имеется решение (x*,лj) системы (*), тогда второй дифференциал обобщенной функции Лагранжа, вычисленный в точке неотрицателен (неположителен)

Задание № 3

Решить задачу о проектировании ёмкости.

Имеется квадратный листовой материал со стороной 1м. спроектировать цилиндрическую ёмкость так, чтобы его объём был максимальным и высота меньше 0.4м.

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

Вырежем из квадрата круг, из оставшейся площади вырежем прямоугольники как показано на рисунке:

Тогда боковая поверхность цилиндра представляет собой прямоугольник длиной (3+4r), где r - радиус круга, и высотой h:

По условию h<0.4м и V->max.

Таким образом, получаем задачу нахождения условного максимума функции при ограничении типа неравенств:

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

Пусть л0=0, то

Функция имеет условный максимум в точке (0.50000010818454444088, 0.196).



Следовательно, полученная цилиндрическая емкость будет иметь радиус основания, равный r=0.50000010818454444088, объем V=0.196 куб.м, и высоту h=0.25

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

Решение задачи линейного программирования графическим и симплексным методом

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

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

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

Основные этапы решения задач ЛП

· Введение переменных.

· Составление системы ограничений.

· Составление целевой функции.

Каноническая форма задачи ЛП

В канонической форме:

· Все функции ограничения записываются в виде равенств с неотрицательной правой частью;

· Все переменные неотрицательные;

· Целевая функция подлежит минимизации.

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

· любые ограничения- неравенства сводятся к равенству введением новой неотрицательной переменной;

· в случаи, когда задача имеет произвольно изменяющиеся переменные xj, их заменяем разностью двух неотрицательных переменных.

Дополнительные переменные - вновь введенные переменные.

Базисным решением задачи ЛП называется такое дополнительное решение, что положив

xj =0, где j ? n в ограничениях

Графический метод решения задач ЛП

· По системе ограничений строим допустимую область. Она должна быть выпуклой.

· По целевой функции строим линию уровня c1x1+c2x2=const.

· Оптимальное решение находим в точках допустимого множества.

· Линию уровня перемещаем в направлении вектора нормали {c1,c2}, если находим max, и в противоположном направлении, если находим min.

· В случаи задач с n- переменными, графический метод возможен, если n-r?2, где ранг r - системы условий.

Симплекс метод

Симплекс- метод - это метод упорядоченного перебора опорных планов. Упорядоченность в данном случае обеспечивается последовательным перебором опорных планов с монотонным изменением значения целевой функции в сторону возрастания (убывания).

Представим схему, позволяющую осуществить переход от одного опорного к другому.

· Построение опорного плана. Задачу ЛП приводим к канонической форме (с помощью введения новых переменных)

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

Построение симплекс-таблицы

		A0	C1	C2	C3	….	Cn
			А1	A2	A3	….	An
A1	C1
A2	C2
…..	….
	Zj-Cj	Z0

Первый столбец - выбранный базис.

Во втором столбце записываются коэффициенты при векторах базиса

A0 - первоначальный опорный план, иначе говоря, свободные коэффициенты - правая часть ограничений задачи.

Z0 - значение целевой функции при первоначальном опорном плане.

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

В центральной части таблицы записывают коэффициенты при неизвестных в ограничениях исходной задачи

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

Критерий 1 (критерий оптимальности). Если все Дk = zk-ck 0 , то выбранный план для задачи максимизации является оптимальным (для задачи на минимум признак оптимальности - неположительность всех Дk ).

Критерий 2 . Если обнаруживается некоторое Дk < 0 (для задачи минимизации Дk>0), то переход к новому опорному плану увеличит (уменьшит) значение целевой функции. При этом в базис будет вводиться новый вектор/

Переход к очередной симплексной таблице сводится к тому, чтобы выразить Xk из уравнения, соответствующего минимуму и исключить из остальных уравнений (в итоге получаем единичный вектор при новой базисной компоненте и тем самым сохраняется единичная подматрица при базисных векторах):

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

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

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

Задание № 4

Для заданной математической постановки задачи ЛП, приняв дополнительно условие неотрицательности переменных, выполнить следующие действия:

· решить задачу графическим методом;

· привести задачу к канонической форме записи;

· составить симплексную таблицу;

· произвести решение задачи симплексным методом ручным способом;

· проверить результаты решения с помощью программы MathCAD

· составить отчет с приведением результатов по каждому пункту.

Задача:

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

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

Технологическая операция	Затраты времени на изготовление единицы продукта, час.	Фонд времени
	1-го вида	2-го вида	3-го вида
Изготовление	1	1	1	3
Упаковка	1	2	0	4
Доход, т.руб	6	4	8	1

Зададим условие задачи:



Решим задачу графическим методом.

1	1	1	3
1	2	0	4
6	4	8	0

1	1	1	3
0	1	-1	1
0	1	-1	9

Отбросим неотрицательные и заменим знаки равенства знаками неравенства.

Вектор нормали (-1, -9)



Рассчитаем значение функции в полученной точке

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

За первоначальный базис возьмем переменные х4, х5 .

Составим симплексную таблицу:

Базис	x1	x2	x3	x4	x5	Своб.чл.	Оценка
	x4	1	1	1	1	0	3

Размещено на http://www.allbest.ru/

x5	1	2	0	0	1	4
	F	-6	-4	-8	0

0Размещено на http://www.allbest.ru/

Базис	x1	x2	x3	x4	x5	Своб.чл.	Оценка
x3	1	1	1	1	0	3
x5	1	2	0	0	1	4
F	2	4	0	8	0	24

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

Ответ: точка (0, 0, 3)-точка максимума, f(x)=24

Проверим результаты решения с помощью программы Mathcad 14:

Зададим функцию



Зададим матрицу коэффициентов при переменных данной функции:

Зададим матрицу коэффициентов при переменных ограничений: