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

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

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

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

МЕТОДЫ ОПТИМИЗАЦИИ

КУРСОВАЯ РАБОТА



Аннотация

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

Курсовая работа написана по предмету «Методы оптимизации».



Введение

Всякая задача, в которой ищется максимум или минимум некоторой функции n действительных переменных f(x1, x2, …, xn), относится к задачам оптимизации. Функция f(x1, x2, …, xn) называется целевой функцией. Если на переменные xi не наложено ограничений, т. е. < xi <, то задача оптимизации называется задачей безусловной оптимизации, в противном случае говорят о задаче условной оптимизации. В силу того, что max f(x1, x2, …, xn) = min(f(x1, x2, …, xn)), всегда можно свести задачу оптимизации к задаче минимизации. Учитывая это, будем в дальнейшем говорить о задаче минимизации функции f(x1, x2, …, xn).

Цель данной курсовой работы - изучить основные методы оптимизации, рассмотреть основные понятия и теоремы методов оптимизации. Реализовать рассмотренные методы в математическом пакете MathCAD.Проанализировать и сравнить рассмотренные методы, сделать выводы.

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

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

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

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

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

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



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

1.1 Постановка задачи

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

U (, ).

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

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

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

Известно, что для того, чтобы точка 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.2 Метод перебора

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

Пусть 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

Найдем минимум функции f(x), x [0.1, 1] с точностью до.

В итоге получаем f(x*) = -3.749, x*=0.382 с точностью за 9.001* итераций.

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

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

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

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

Шаг 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.

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

Реализация в пакете MathCAD 14

Найдем минимум функции f(x), x [0.1, 1] с точностью до.



В итоге получаем f(x*) = -3.749, x*=0.382 с точностью за 27 итераций.

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

В основе этого метода лежит свойство унимодальной функции (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

Найдем минимум функции f(x), x [0.1, 1] с точностью до, .



В итоге получаем f(x*) = -3.749, x*=0.382 с точностью за 26 итераций.

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

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

Золотым сечением отрезка называется его разбиение на две неравные части, так, что отношение длины всего отрезка к длине его большей части равно отношению длины большей части к длине меньшей части (рис.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

Найдем минимум функции f(x), x [0.1, 1] с точностью до



В итоге получаем f(x*) = -3.749, x*=0.382 с точностью за 18 итераций.

1.6 Аналитическое решение

Убедимся что функция унимодальна.



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

Определим стационарные точки, при помощи функции root()

Проверим является ли найденная точка точкой минимума.



Так как вторая вторая производная в этой точке положительна, значит найденная точка- точка min.

Теперь найдем значение целевой функции в данной точке.

1.7 Сравним прямые методы

Погрешности:

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

	Методы
	перебора	поразрядного поиска	дихотомии	Золотого сечения
Число вычислений	9.001*	27	26	18
Погрешность относительно аналитического решения	5.678*

Выводы из сравнения:

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

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

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

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

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



В итоге получаем f(x*) = -3.749, x*=0.382 с точностью за 15 итераций.

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).

Рис. 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

В результате получаем f(x*) = -3.749, x*=0.382 с точностью за 16 итераций.



1.10 Метод хорд

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

Запишем координату точки xЮЮ:

(1.12)

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

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

Шаг 1. Найти xЮЮ по формуле (1.12). Вычислить значение производной и перейти к шагу 2.

Шаг 2. Проверить условие на окончание поиска. Если условие выполняется, считаем значение функции в полученной точке и завершаем поиск, иначе переходим к шагу 3.

Шаг 3. Переход к новому отрезку. Если f '(x0) > 0, то положить b = xЮЮ. Иначе положить a = xЮЮ. Перейти к шагу 1.

Реализация в пакете MathCAD 14

В результате получаем f(x*) = -3.749, x*=0.382 с точностью за 35 итераций.

1.11 Сравним методы использующие производную целевой функции

Погрешности.



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

	Методы
	бисекции	хорд	Ньютона
Число вычислений	15	35	16
Погрешность относительно аналитического решения

Вывод из сравнения:

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

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

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

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



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

2.1 Необходимые сведения из курса линейной алгебры

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

= (x1, x2, …, xn)T, (2.1)

где символ "T" - знак транспонирования. Тогда x -точка в пространстве Rn и f(x) =f(x1, x2, … ,xn).

Скалярное произведение векторов x = (x1, x2, …, xn)T и y = (y1, y2, …, yn)T определяется следующим образом:

(x, y) = . (2.2)

Нормой (длиной) вектора x называется число

x = = . (2.3)

Определено расстояние между векторами x и y:

(x, y) = x - y = . (2.4)



Матрица A =(aij), i = 1, … , m; j = 1, … , n, представляет собой прямоугольную таблицу размера mn, состоящую из m строк и n столбцов. В частности, вектор-столбец x является матрицей размера n 1.

Квадратная матрица A называется симметрической, если aij = aji, i, j = 1, … , n.

Произведением матрицы A размера mn на вектор-столбец x Rn является вектор-столбец b = (b1, b2, … , bm)T Rm, координаты которого вычисляются по формуле:

bi = = (ai, x) , i = 1, 2, …, m, (2.5)

где ai = (ai1, … , ain) - i-ая строка матрицы A, т. е. Ax = b.

Определителем квадратной матрицы A (обозначается detA или A) размера nn называется число, которое определяется по формуле:

detA = A = . (2.6)

Здесь Aij - алгебраическое дополнение элемента aij, Aij = (-1)i+jMij , а Mij - минор, который является определителем матрицы, полученной из A вычеркиванием i-ой строки и j-го столбца.

Если определитель матрицы A не равен нулю, то существует обратная матрица A-1 = (ij). Элементы обратной матрицы находят по формуле:

ij = , (2.7)

где Aji - алгебраическое дополнение элемента aji матрицы A.

Квадратичной формой Q от n переменных x1, x2, …, xn называется сумма, каждый член которой является либо квадратом одного из этих переменных, либо произведением двух разных переменных. Считая, что в квадратичной форме Q уже сделано приведение подобных членов, введем следующие обозначения: коэффициент при xобозначим через aii, а коэффициент при произведении xixj для i j - через 2aij. Член 2aijxixj можно записать в виде

2aijxixj = aijxixj + ajixjxi.

Очевидно, что aij = aji. Всю квадратичную форму Q можно записать в виде суммы всевозможных членов aijxixj, где i и j независимо друг от друга принимают значения от 1 до n:

Q = . (2.8)

В частности, при i = j получается член aiix.

Из коэффициентов aij можно составить квадратную матрицу A = (aij) размера nn; она называется матрицей квадратичной формы Q.

Так как aij = aji, матрица A является симметрической.

Квадратичную форму Q можно записать в ином виде, используя введенное ранее умножение матрицы на вектор-столбец и скалярное произведение векторов. Равенство (2.8) равносильно равенству

Q(x) = = (Ax, x). (2.9)

Квадратичная форма Q(x) называется положительно определенной, если для всех x 0 имеет место неравенство Q(x) > 0.

Из курса линейной алгебры известен критерий Сильвестра положительной определенности квадратичной формы: для того, чтобы квадратичная форма Q(x) была положительно определенной, необходимо и достаточно, чтобы ее матрица A = (aij) была положительно определена, т. е. все ее угловые миноры были положительными:

a11 . . . a12

a11 a12 . . .

1 = a11 > 0; 2 = > 0; n = . . > 0. (2.10)

a21 a22 . .

a11 . . . a12

2.2 Постановка задачи

Пусть 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, Для нахождения глобального минимума необходимо найти все локальные минимумы и выбрать наименьшее значение. В дальнейшем будем рассматривать задачу нахождения локального минимума.

Множество точек, для которых функция принимает постоянное значение f(x) = c, называется поверхностью уровня. Если число переменных n = 2, это множество называют линией уровня. На рис 2.1 показано, как получаются линии уровня для функции двух переменных. Функция f(x1, x2) задает в трехмерном пространстве некоторую поверхность u = f(x1, x2), низшая точка которой и дает решение задачи минимизации. Для того, чтобы изобразить рельеф этой поверхности, проведем несколько равноотстоящих плоскостей u = const. Проекции на плоскость (x1 x2) линий пересечения этих плоскостей с поверхностью u = f(x1, x2) и дают линии уровня.

Рис. 2.1

Вектор из первых частных производных

g(x) = f '(x) =

называется градиентом. Если в точке x градиент не равен нулю, то он перпендикулярен проходящей через эту точку поверхности уровня и указывает направление наискорейшего возрастания функции. Вектор - g(x) называется антиградиентом и указывает направление наискорейшего убывания функции (рис. 2.2).



Рис. 2.2

Точка x, для которой градиент равен нулю, т.е.

f '(x) = 0, (2.11)

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

Равенство (2.11) представляет собой систему n нелинейных уравнений с неизвестными x1, x2, …, xn, которая в развернутом виде выглядит так:

= 0,

……………………. (2.12)

= 0

Достаточным условием того, чтобы стационарная точка x была точкой локального минимума, является положительная определенность (см. п. 2.1) матрицы



G(x) = f "(x) = , (2.13)

составленной из вторых частных производных функции f(x). Матрица (2.13) называется матрицей Гессе.

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

f(x) = + + с. (2.14)

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

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

где A - симметричная положительно определенная матрица, b - вектор-столбец коэффициентов bj.

Вычислим градиент и матрицу Гессе для квадратичной функции (2.15). Продифференцировав f(x) по xk, получим

= + + bk.

Так как aik = aki в силу симметрии матрицы A, получим формулу

= + bk. (2.16)

Матричная форма (2.16) имеет вид:

f '(x) = Ax + b. (2.17)

Дифференцируя обе части равенства (2.16) по xi, получим

= aik.

Это означает, что для квадратичной функции (2.14) матрица Гессе не зависит от x и равна A.

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

Метод градиентного спуска является одним из самых распространенных и самых простых методов решения задачи безусловной оптимизации. Он основан на свойстве градиента функции, согласно которому направление градиента совпадает с направлением наискорейшего возрастания функции, а направление антиградиента - с направлением наискорейшего убывания функции. При решении задачи безусловной минимизации за направление спуска из точки 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.

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

Шаг 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



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

x* = (-32,945; -33,055), значение функции f(x*) = 1,572*количество итераций n = 1572*.

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

В методе наискорейшего спуска величина шага (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), равна (см., например, в [1])

(m) = (2.26)

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

Алгоритм 2.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



2.5 Метод сопряженных градиентов

До сих пор в итерационной процедуре градиентного спуска

x(m+1) = x(m) + (m)p(m)

мы предполагали, что движение к минимуму функции производится в направлении антиградиента, p(m) = -g(m). Для некоторых функций направление антиградиента в точке x(m) может значительно отличаться от направления к точке минимума x*. В результате траектория приближения к точке минимума может иметь зигзагообразный характер. Метод сопряженных градиентов в существенной степени избавлен от этого недостатка. Этот метод основан на понятии сопряженных направлений. Будем рассматривать задачу минимизации квадратичной функции

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

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

Направления p(0), p(1), … , p(m -1) называются взаимно сопряженными относительно матрицы A, если (Ap(k), p(l)) = 0 для всех k l.

В основе метода сопряженных градиентов лежит итерационный процесс:

x(m+1) = x(m) + (m)p(m), m = 0, 1, …; p(0) = -g(0) = -f '(x(0)) .

Величина шага (m) так же, как и в методе наискорейшего спуска, выбирается из условия одномерной минимизации функции (m)() = f(x(m) + (m)p(m)),

Направления p(m) находят по следующему правилу:

p(0) = -g(0) = -f '(x(0)),

p(m+1) = -g(m+1) + (m) p(m), n 1,

(m) = ,

g(m) = Ax(m) + b,

где

p(m) = p(x(m)) - вектор сопряженных направлений;

g(m) = g(x(m)) - вектор направлений градиента;

x(m) = (x, x, … , x) - m-ое приближение.

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

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

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

p(0) = - g(0) = -(Ax(0) + b),

Покоординатно:

p(0) = (p, p, … , p)T,

p= - g= -, i = 1, …, n.



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

Шаги 3 - 6 реализуют вычисление величины шага (m)

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

B= (g(m), p(m)) =.

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

Ap(m) = (A, A, … , A)T, где

A= , i = 1, …, n.

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

B= (Ap(m), p(m)) = .

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

(m) = - .

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

x(m+1) = x(m) +(m)p(m), или покоординатно

x(m+1) = (x, x, … , x)T,

x= x+ (m)p, i = 1, …, n.



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

g(m+1) = Ax(m+1) + b, или покоординатно

g(m+1) = (g, g, … , g),

g= , i = 1, …, n.

Шаг 9. Для заданной точности вычислений проверить выполнение критерия окончания вычислений.: f '(x(m+1)) = g(m+1)) < , Если это условие выполнено, вычисления закончить и за приближенное значение точки минимума принять точку x* = x(m+1) = (x, x, … , x)T, f* = f(x*). В противном случае перейти к шагу 10 для продолжения итерационного процесса.

Шаги 10 - 12 реализуют вычисление нового вектора сопряженного градиента p(m+1).

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

безусловный минимизация многомерный экстремум

С= (Ap(m), g(m+1)) = .

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

(m) = .

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

p(m+1) = - g(m+1) + (m) p(m), или покоординатно

p(m+1) = (p, p, … , p),

p= - g+ (m)p, i = 1, …, n.

Шаг 13. Перейти к шагу 3 при m = m+1.

Реализация в среде MathCAD



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

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

Метод Ньютона для функции многих переменных является обобщением метода Ньютона для одномерного случая (разд. 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.

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

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

Шаг 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). Для этого случая получим следующий алгоритм.

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

Шаг 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





2.7 Аналитическое решение

2.8 Линии уровня



2.9 Сравнение методов многомерной безусловной минимизации

Метод	Значение аргумента х1	Значение аргумента х2	Значение функции	Количество итераций
Аналитический метод	-32.945	-33.055	-2.132*10^3
Метод дробления шага	-32.945	-33.055	-2.132*10^3	1.572*10^3
Метод наискорейшего спуска	-32.945	-33.055	-2.132*10^3	1.34*10^3
Метод сопряженных градиентов	-32.945	-33.055	-2.097*10^3	1
Метод Ньютона	-32.945	-33.055	-2.132*10^3	1

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

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

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



3.Задача о проектировании ёмкости

Постановка задачи: Имеется прямоугольной формы листовой материал со сторонами 1 и 2.Спроектировать цилиндрическую ёмкость так, чтобы её объем был максимален. Способ построения ёмкости:

Из одной части вырезается дно , а из другой сетка.

Построение математической модели:

Сумма площадей вырезанных фигур меньше чем площадь всего листа. То есть

Sкр + S2 + S1 < S

Если расписать площади то получим

т.к. , площадь круга меньше площади квадрата.

Также следует учесть что диаметр круга не может быть больше минимальной из сторон прямоугольного листа, то есть

2rA

Объем цилиндрической ёмкости V=Sкр*h, где h высота цилиндра. В свою очередь h зависит от r, следующим образом

Тогда оббьем равен:

Где r=x, A=1, B=2.Подставив данные получим

Решение:

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

1 случай: , тогда

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

Так как , то одновременно. Тогда рассмотрим 2 случая

1сл.,; x=0,5, система не выполняется.

2сл.,; x=0, система выполняется. Но не выполняется необходимое условие максимума второго порядка, значит х=0, не является точкой максимума.

2 случай:, тогда

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

Рассмотрим четыре возможных случая:

1 сл.; x=(мы не рассматриваем х, система выполняется.

2сл.,; x=0,5, система не выполняется.

3сл.,; x=0, система не выполняется.

3сл.,; система не выполняется.

Посмотрим, выполняется ли необходимое условие максимума второго порядка

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

Значит для получения искомой ёмкости максимального объема радиус дна должен бать равен.

Тогда получаем объем проектируемой ёмкости V=

V=0,476(.



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

4.1 Теоретическая часть

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

№

Базис

с базиса

…

…

…

…

…

…

…

…

…

…

1

1

0

…

0

…

0

…

…

…

2

0

1

…

0

…

0

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

l

0

0

…

1

…

0

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

m

0

0

…

0

…

1

…

…

…

m+1

Z()

Высчитываются оценки плана

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 Практическая часть

Задача. Предприятие располагает запасами сырья трех видов. Из этого сырья можно изготовить два типа продукции: A и B. Известны количество сырья каждого вида, идущего на производство каждого типа продукции, запасы сырья и доход от реализации единицы каждого типа продукции. Данные представлены в таблице. Составить план выпуска продукции, при котором доход от реализации максимален.

Виды сырья	Расход сырья на единицу продукции	Запас сырья
	А	В
1	3	1	21
2	2	2	30
3	0	2	16
Прибыль	3	2

Табл. 4.2. Условие задачи 1

Математическая модель задачи

Обозначим А как , а В как . Составим математическую модель:

Общая прибыль составит , -целевая функция.

Графическое решение

определим многоугольник решений. Для этого в неравенствах системы заменим знаки неравенства знаками ровно:

Изобразим данные прямые и нормаль к функции:



Где g1(x),g2(x),g3(x) линии ограничений, а нормаль к функции.

Заштрихованный многоугольник-это многоугольник решений данной задачи.

Построим линию уровня для нашей функции :



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

Получаем

Подставим полученные х в f(x)=29, значит максимально возможный доход равен 29.

Ответ: f(x)max=29. Максимальный доход равен 29.

Решение Симплекс-методом.

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

; ;; ; ;

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

№	Базис	с базиса				0		0
1				3*	1	1	0	0
2				2	2	0	1	0
3		0	16	0	2	0	0	1
4				-3	-2	0	0	0

Получившийся опорный план не является оптимальным, так как в 4 строке есть отрицательная оценка -2 и -3.Переходим к новому опорному плану в соответствии с алгоритмом описанным в теоретической части.

№	Базис	с базиса				0		0
1				1	1/3	1/3	0	0
2				0	4/3	-2/3	1	0
3		0	16	0	2*	0	0	1
4				0	-1	1	0	0

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

№	Базис	с базиса				0		0
1				1	0	1/3	0	-1/6
2			/3	0	0	-2/3	1	-2/3
3		2	8	0	1	0	0	1/2
4				0	0	1	0	1/2

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

f(x)max=29. Максимальный доход равен 29.

Проверка решения с помощью MathCAD

Опишем целевую функцию:

Введем начальное приближение:



Введем систему ограничений и граничные значения:

Введем вектор столбец искомых параметров и воспользуемся встроенной функцией Maximize:

Находим искомые параметры:



И находим значение функции:

Что подтверждает наши пред идущие решения, Максимальным доход будет тогда, когда 4.333 продукта А и 8 продукта В, он будет равняется 29.



5.Транспортная задача

5.1Формулировка транспортной задачи

Однородный груз сосредоточен у m поставщиков в объемах . Данный груз необходимо доставить n потребителям в объемах . Известны , i=1,2,,…,m, j=1,2,…,n- стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны. Исходные данные транспортной задачи обычно записываются в таблице.

Таблица 4.1.

			…	Запас поставщика
			…	a1
			…	a2
…	…	…	….	….
Ограничение потребителя	b1	b2	…

Исходные данные задачи могут быть представлены также в виде вектора запасов поставщиков А=(), вектора запросов потребителей

В=() и матрицы стоимости .

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

5.2Математическая модель транспортной задачи

Переменными (неизвестными) транспортной задачи являются i=1,2,,…,m, j=1,2,…,n - объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок

Так как произведение определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны . По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция имеет вид