Методичка по курсовым и лабораторным работам (1085639), страница 8
Текст из файла (страница 8)
Шаг 1. Выбрать произвольную начальную точку x(0) = (x
, x
, … , x
)T, например, x(0) = (0, 0, … , 0)T и погрешность вычислений e > 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)|| = 
< e ,
или
|f(x(m+1)) – f(x(m))| < e.
Если критерий окончания вычислений выполнен, то положить 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 и погрешность вычислений e > 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)) .
Пример 2.7.
Методом Ньютона найдем минимум функции f(x) = 2x
+ 3x
+x1x2 –3 x1 с точностью e = 0.1.
Шаг 1. Введем
4 1
A = 1 6 ,
b = (– 3, 0)T,
x(0)) = (0, 0)T.
Шаг 2. Вычислим
g(x(0)) = (g , g )T,
g = 
= 4×0 + 1×0 +(– 3) = – 3,
g = 
= 1×0 + 6×0 + 0 = 0.
Шаг 3. Вычислим A–1 = (aij). Элементы обратной матрицы находят по формуле (2.7) (разд. 2.1)
aij = 
,
где Aji – алгебраическое дополнение элемента aji матрицы A.
Для нашего примера
detA = 4×6 – 1×1 = 23,
A11 = a22 = 6, A12 = – a12 = –1, A21 = – a21 = – 1, A22 = a11 = 4.
Следовательно,
A–1 = .
Шаг 4. Вычислим x(1) = x(0) – A–1 g(x(0)) .
Покоординатно
x(1) = (x
, x
)T,
x = x – 
= 0 – ×(–3) – ( )×0 = 
,
x = x – 
= 0 –( )×(–3) – ×0 = –
.
Точка x(1) = (x , x )T = ( ,– )T есть точка минимума.
Тема 3. Задачи многомерной оптимизации при наличии ограничений. Линейное программирование
3.1. Постановка и классификация задач математического программирования
До сих мы рассматривали задачи безусловной оптимизации. Важный класс задач оптимизации – задачи условной оптимизации. Многие практические задачи сводятся к случаю, когда ищется максимум или минимум функции f(x1, x2, …, xn):
f(x1, x2, …, xn) ® min (max) (3.1)
при условии, что на переменные x1, x2, …, xn наложены ограничения. Эти ограничения имеют вид равенств или неравенств:
gi(x1, x2, …, xn) = 0, iII1, (3.2)
gi(x1, x2, …, xn) ? 0 , iII2, (3.3)
где I1, I2 – заданные множества индексов, I1, I2 I {1, 2, …, n}.
Функция (3.1) называется целевой функцией задачи.
Соотношения (3.1) – (3. 4) представляют собой запись условий задачи математического программирования. Рассмотрим основные типы задач математического программирования.
1. Задача линейного программирования. Функции f(x1, x2, …, xn), gi(x1, x2, …, xn) линейны, и все переменные x1, x2, …, xn удовлетворяют условию неотрицательности xi ? 0, i = 1, 2, …, n.
2. Задача нелинейного программирования. Хотя бы одна из функций f(x1, x2, …, xn) и gi(x1, x2, …, xn) не является линейной.
3. Задача выпуклого программирования. Все функции f(x1, x2, …, xn) и gi(x1, x2, …, xn) выпуклы, и ограничения-равенства (3.2) отсутствуют.
3.2. Постановка задачи линейного программирования
Пусть имеется n переменных x1, x2, …, xn. Необходимо найти значения этих переменных, так, чтобы достигался минимум (или максимум) линейной функции:
f(x1, x2, …, xn) = с1x1+ с2x2 + …+cnxn ® min(max) (3.4)
при ограничениях
a11x1+ a12x2 + …+a1nxn = b1,
a21x1+ a22x2 + …+a2nxn = b2,
…………………………… (3.5)
am1x1+ am2x2 + …+amnxn = bm,
am+1,1x1+ am+1,2x2 + …+am+1,nxn ? bm+1,
………………………………………
am+k,1x1+ am+k,2x2 + …+am+k,nxn ? bm+k,
и условии неотрицательности переменных x1, x2, …, xn
x1 ? 0, x2 ? 0, …, xn ? 0. (3.6)
Не умаляя общности, можно считать, что первые m ограничений являются равенствами, а остальные – неравенствами. Этого всегда можно добиться, перенумеровав ограничения соответствующим образом.
Задача поиска максимума функции f(x1, x2, …, xn) =с1x1+ с2x2 + …+cnxn сводится к задаче поиска минимума, если учесть, что
max f(x1, x2, …, xn) = –min (–f(x1, x2, …, xn)).
В дальнейшем будем рассматривать задачу нахождения минимума.
Запишем задачу линейного программирования (3.4) – (3.6) в следующем виде:
f(x1, x2, …, xn) = 
® min
= bi, i = 1, 2, …, m, (3.7)
? bi, i = m +1, m +2, …, m +k,
xj ? 0, j = 1, 2, …, n.
Задачу линейного программирования, записанную в форме (3.7), называют общей задачей линейного программирования (ОЗЛП).
Если все ограничения являются неравенствами, то задачу линейного программирования называют основной задачей линейного программирования. Таким образом, основная задача линейного программирования имеет вид:
f(x1, x2, …, xn) = ® min
? bi, i = 1, 2, …, m, (3.8)
xj ? 0, j = 1, 2, …, n.
Если все ограничения являются равенствами, то задачу линейного программирования называют канонической задачей линейного программирования (КЗЛП). Из этого следует, что каноническая задача линейного программирования имеет вид
f(x1, x2, …, xn) = ® min
= bi, i = 1, 2, …, m, (3.9)
xj ? 0, j = 1, 2, …, n.
Между основной и канонической задачами линейного программирования существует двусторонняя связь.
1. Можно от основной задачи (3.7) перейти к канонической, введя дополнительные переменные xn+i ? 0, i = 1, … , m. Тогда имеем:
f(x1, x2, …, xn) = ® min
+ xn+i = bi, i = 1, 2, …, m, (3.10)
xj ? 0, j = 1, 2, …, n + m.
2. Можно от канонической задачи (3.8) перейти к основной, удвоив число ограничений и заменив каждое ограничение-равенство двумя ограничениями-неравенствами:
f(x1, x2, …, xn) = ® min
? bi, i = 1, 2, …, m, (3.11)
? bi, i = 1, 2, …, m,
xj ? 0, j = 1, 2, …, n.
3.3. Графическое решение ЗЛП
Если число переменных в задаче линейного программирования равно двум, то эта задача допускает простую геометрическую интерпретацию и может быть решена графически.
Пусть ограничения ЗЛП заданы в виде неравенств. Тогда эта задача имеет следующий вид:
f(x1, x2) = с1x1+ с2x2 ® min
a11x1+ a12x2 ? b1,
a21x1+ a22x2 ? b2,
…………………………… (3.12)
am1x1+ am2x2 ? bm,
x1 ? 0, x2 ? 0.
Рассмотрим неравенство
a11x1+ a12x2 ? b.
Из курса аналитической геометрии известно, что прямая a11x1+ a12x2 = b делит плоскость (x1, x2) на две полуплоскости, в одной из которых выполняется неравенство a11x1+ a12x2 < b, а в другой неравенство a11x1+ a12x2 > b. На самой прямой выполняется равенство a11x1+ a12x2 = b.
Пример 3.1.
Прямая 2x1+ 3x2 = 6 делит плоскость на две полуплоскости
3.4. Симплекс-таблицы
Пусть задача линейного программирования задана в каноническом виде:
f(x1, x2, …, xn) = ® min,
= bi, i = 1, 2, …, m, (3.13)
xj ? 0, j = 1, 2, …, n.
В этой задаче n переменных x1, x2, …, xn, m ограничений-равенств и n условий неотрицательности переменных x1, x2, …, xn.
Рассмотрим прежде всего вопрос о существовании допустимых решений задачи (3.13), т. е. неотрицательных значений x1, x2, …, xn, удовлетворяющих системе уравнений:
a11x1+ a12x2 + …+a1nxn = b1,
a21x1+ a22x2 + …+a2nxn = b2,
…………………………… (3.14)
am1x1+ am2x2 + …+amnxn = bm,
Целевую функцию f(x1, x2, …, xn) = пока исключим из рассмотрения.
Приведем необходимые сведения из курса линейной алгебры. Система уравнений (3.14) имеет матрицу
a11 a12 … a1n
A = a21 a22 … a2n
……………… (3.15)
am1 am2 … amn
размера m?n (в ней m строк и n столбцов).
Расширенной матрицей системы линейных уравнений называется та же матрица, дополненная столбцом свободных членов:
a11 a12 … a1n b1
= a21 a22 … a2n b2
……………… (3.16)
am1 am2 … amn bm
Рангом матрицы называется наибольший порядок отличного от нуля минора (т. е. определителя, полученного из матрицы вычеркиванием каких-то строк и столбцов).
В линейной алгебре доказывается, что система линейных уравнений совместна (имеет решение) тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы.
Пример 3.1.
Дана система трех уравнений с четырьмя неизвестными:
2x1+ x2 – x3 + x4 = – 1,
x1 – x2 = 2,
x1 – 2x3 = 3.
Определить, является ли система совместной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
