Файл: прикладная математика учебное пособие московский автомобильнодорожный.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.02.2024
Просмотров: 193
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
1. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Задачи выпуклого программирования
Решение задачи нелинейного программирования в Excel
Задания к самостоятельной работе
К ЗАДАЧАМ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Задания для самостоятельного решения
КООПЕРАТИВНЫЕ ИГРЫ И ДРУГИЕ ЗАДАЧИ
Параметры сетей и методы их расчета
Матричный метод расчета сетевого графика
Табличный метод расчета сетевого графика
Таблица стандартного нормального распределения
Анализ и оптимизация сетевой модели
Управление производством работ по сетевым графикам
Проект СРМ и временной резерв стадий
Проект СРМ и временной резерв стадий
Следствие 2. Если
f( X)
-
строго выпуклая функция, то ее гло-
бальный максимум на выпуклом множестве достигается в единствен- ной точке.
Определение. Функцией Лагранжа задачи выпуклого программи- рования (1.9…1.11) называется функция
m
L(x1, x2,..., xn, y1, y2,..., ym)
f(x , x,..., x) y(bg(x, x,..., x
)),
(1.14)
1 2 n i i i 1 2 ni1
где
y1, y2,..., ym
-
множители Лагранжа.
Определение. Точка ( X0,Y0 ) (x0, x0,...x0,y0, y0...,y0 )
называет-
1 2
ся седловой точкой функции Лагранжа, если
n 1 2 m
L(x, x,..., x, y0,y0,..., y0 ) L(x0, x0,..., x0,y0, y0,...,y0 )
1 2 n 1 2 m 1 2 n 1 2 m
L(x0, x0,..., x0, y, y,..., y)
1 2 n 1 2 m
для всех
xj 0 ( j
1,...,n), yi
0 (i
1,...,m).
Теорема 2 (теорема Куна-Таккера). Для задачи выпуклого про- граммирования (1.9…1.11), множество допустимых решений которой
обладает свойством регулярности, X
1 2 3 4 5 6 7 8 9 ... 42
(x0, x0,..., x0 )
является опти-
0 1 2 n
мальным планом тогда и только тогда, когда существует такой вектор
Y (y0, y0,...,y0 ), где y 0 (i 1,...,m), что ( X,Y)
-
седловая точка
0 1 2 m i 0 0
функции Лагранжа.
Если предположить, что функции f и gi
непрерывно дифферен-
цируемы, то теорема Куна-Таккера может быть дополнена аналитиче- скими выражениями, определяющими необходимые и достаточные
условия для того, чтобы точка
( X0,Y0 )
была седловой точкой функции
Лагранжа, т.е. являлась решением задачи выпуклого программирова- ния. Эти выражения имеют следующий вид:
L0
x 0 ( j
1,...,n);
j
x0 L0
0 (j=1,...,n);
jx j
x0 0 (j=1,...,n);
j
(1.15)
L0
0 (i
1,...,m);
yi 0 L0
yi
yi
0 (i
1,...,m);
i
y0
0 (i
1,...,m),
где
L0
xj
и L0
yi-
значения соответствующих частных производных
функции Лагранжа, вычисленных в седловой точке. Всем отмеченным выше требованиям, позволяющим записать необходимые и достаточ-
ные условия для седловой точки
( X0,Y0 )
функции Лагранжа в виде
выражений (1.15), удовлетворяет задача квадратичного программиро- вания, в которой ограничения являются линейными функциями, а це- левая функция представляет собой сумму линейной и квадратичной функции
Z Cx Cx
... Cx cx2 c x2 ... c x2
1 1 2 2
n n 11 1 22 2
nn n
c12 x1x2 c13 x1x3 ... cn1nxn1xn.
Определение. Квадратичной формой относительно переменных x1, x2, ..., xnназывается числовая функция этих переменных, имеющая вид
F cx2 c xx ...cx c x2 ...
11 1 12 1 2 1nn
n n
22 2
cn1nxn1x
-
c x2 cxx.
n nn n kj k j
k1 j1
Определение. Квадратичная форма Fназывается положительно
(отрицательно) определенной, если
F( X) 0
(F( X) 0)
для всех зна-
чений переменных
X (x1, x2,..., xn) кроме X 0.
Определение. Квадратичная форма Fназывается положитель-
но (отрицательно)-полуопределенной, если
F( X) 0
(F( X) 0)
для
любого набора значений переменных
X (x1, x2,..., xn)
и, кроме того,
существует такой набор переменных
X0 (x0, x0,..., x0 ),
где не все
1 2 n
значения переменных одновременно равны нулю, а F( X0 ) 0.
Теорема 3. Квадратичная форма является выпуклой функцией, если она положительно-полуопределенная, и вогнутой функцией, ес- ли она отрицательно-полуопределенная.
Определение. Задача, состоящая в определении максимального
(минимального) значения функции
n n n
