Файл: прикладная математика учебное пособие московский автомобильнодорожный.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.02.2024
Просмотров: 224
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
1. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Задачи выпуклого программирования
Решение задачи нелинейного программирования в Excel
Задания к самостоятельной работе
К ЗАДАЧАМ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Задания для самостоятельного решения
КООПЕРАТИВНЫЕ ИГРЫ И ДРУГИЕ ЗАДАЧИ
Параметры сетей и методы их расчета
Матричный метод расчета сетевого графика
Табличный метод расчета сетевого графика
Таблица стандартного нормального распределения
Анализ и оптимизация сетевой модели
Управление производством работ по сетевым графикам
Проект СРМ и временной резерв стадий
Проект СРМ и временной резерв стадий
(k), тогда в этой точке вычисляют градиент функции (1.24)
(k)
f( X(k) )
f( X(k) )
f( X(k) )
f( X ) x
; x
; ...; x
и строят линейную функцию
f( X(k) )
1 2
f( X(k) )
n
f( X(k) )
F x x1
x x2
... x xn.
(1.27)
1 2 n
Затем находят максимальное значение этой функции при ограни- чениях (1.25 и 1.26). Пусть решение данной задачи определяется точ-
кой
Z(k).
Тогда за новое допустимое решение исходной задачи прини-
мают координаты точки
X(k1)
k
X(k1) X(k) (Z(k) X(k) ),
(1.28)
где k
ченное между нулем и единицей (0 k
1).
Это число k
берут про-
извольно или определяют таким образом, чтобы значение функции в
точке
X(k1)f( X(k1) ),
зависящее от
k,
было максимальным. Для этого
необходимо найти решение уравнения
df 0
dk
и выбрать его наи-
меньший корень. Если его значение больше единицы, то следует по-
ложить k
1.
После определения числа k
находят координаты точ-
ки X(k1)
и вычисляют необходимость перехода к новой точке
X(k2).
Если такая необходимость имеется, то в точке
X(k1)
вычисляют гра-
диент целевой функции, переходят к соответствующей задаче линей- ного программирования и находят ее решение. Определяют коорди-
наты точки
X( k 2 ),
и исследуют необходимость проведения дальней-
ших вычислений. После конечного числа шагов получают с необходи- мой точностью решение исходной задачи.
Итак, процесс нахождения решения задачи (1.24…1.26) методом Франка-Вулфа включает в себя следующие этапы:
Рассмотрим задачу определения максимального значения вогну-
той функции
f(x1, x2,...xn)
при условиях
gi(x1, x2,...xn) bi,
(i 1,...,m),
xj 0 (j
1,...,n),
где
gi(x1, x2,..., xn) – выпуклые функции.
Вместо того, чтобы непосредственно решать эту задачу, находят
максимальное значение функции
F(x1, x2,..., xn) f(x1, x2,..., xn)
H(x1, x2,..., xn),
являющейся суммой целевой функции задачи и неко-
торой функции
H(x1, x2,..., xn),
определяемой системой ограничений и
m
называемой штрафной функцией. Штрафную функцию можно постро- ить различными способами. Однако наиболее часто она имеет вид
H(x1, x2,..., xn) ai(x1, x2,..., xn)gi(x1, x2,..., xn),
i1
где
a(x, x
,..., x
) 0, если bi
gi(x1, x2,..., xn) 0,
(1.29)
i 1 2
n
ai, если bi
gi(x1, x2,..., xn) 0,
ai>0 – представляющие собой весовые коэффициенты.
Используя штрафную функцию, последовательно переходят от одной точки к другой до тех пор, пока не получат приемлемое реше- ние. При этом координаты последующей точки находят по формуле
(k1)
k f( X(k) ) m
g( X(k) )
xj max 0; xj
j
X
ai
i1
Xj
.
(1.30)
Из последнего соотношения следует, что если предыдущая точка
находится в области допустимых решений исходной задачи, то второе слагаемое в квадратных скобках равно нулю и переход к последую- щей точке определяется только градиентом целевой функции. Если же указанная точка не принадлежит области допустимых решений, то
за счет данного слагаемого на последующих итерациях достигается возвращение в область допустимых решений. При этом, чем меньше ai, тем быстрее находится приемлемое решение, однако точность его определения снижается. Поэтому итерационный процесс обычно на- чинают при сравнительно малых значениях aiи, продолжая его, эти значения постепенно увеличивают.
Итак, процесс нахождения решения задачи выпуклого програм- мирования методом штрафных функций включает в себя следующие этапы:
(k)
f( X(k) )
f( X(k) )
f( X(k) )
f( X ) x
; x
; ...; x
и строят линейную функцию
f( X(k) )
1 2
f( X(k) )
n
f( X(k) )
F x x1
x x2
... x xn.
(1.27)
1 2 n
Затем находят максимальное значение этой функции при ограни- чениях (1.25 и 1.26). Пусть решение данной задачи определяется точ-
кой
Z(k).
Тогда за новое допустимое решение исходной задачи прини-
мают координаты точки
X(k1)
k
X(k1) X(k) (Z(k) X(k) ),
(1.28)
где k
-
некоторое число, называемое шагом вычислений и заклю-
ченное между нулем и единицей (0 k
1).
Это число k
берут про-
извольно или определяют таким образом, чтобы значение функции в
точке
X(k1)f( X(k1) ),
зависящее от
k,
было максимальным. Для этого
необходимо найти решение уравнения
df 0
dkи выбрать его наи-
меньший корень. Если его значение больше единицы, то следует по-
ложить k
1.
После определения числа k
находят координаты точ-
ки X(k1)
и вычисляют необходимость перехода к новой точке
X(k2).
Если такая необходимость имеется, то в точке
X(k1)
вычисляют гра-
диент целевой функции, переходят к соответствующей задаче линей- ного программирования и находят ее решение. Определяют коорди-
наты точки
X( k 2 ),
и исследуют необходимость проведения дальней-
ших вычислений. После конечного числа шагов получают с необходи- мой точностью решение исходной задачи.
Итак, процесс нахождения решения задачи (1.24…1.26) методом Франка-Вулфа включает в себя следующие этапы:
-
определяют исходное допустимое решение задачи; -
находят градиент функции (1.24) в точке допустимого решения; -
строят функцию (1.27) и находят ее максимальное значение при условиях (1.25 и 1.26);
-
определяют шаг вычислений; -
по формулам (1.28) находят компоненты нового допустимого ре- шения; -
проверяют необходимость перехода к последующему допустимому решению. В случае необходимости переходят к этапу 2, в против- ном случае, найдено приемлемое решение исходной задачи.
-
Метод штрафных функций
Рассмотрим задачу определения максимального значения вогну-
той функции
f(x1, x2,...xn)
при условиях
gi(x1, x2,...xn) bi,
(i 1,...,m),
xj 0 (j
1,...,n),
где
gi(x1, x2,..., xn) – выпуклые функции.
Вместо того, чтобы непосредственно решать эту задачу, находят
максимальное значение функции
F(x1, x2,..., xn) f(x1, x2,..., xn)
H(x1, x2,..., xn),
являющейся суммой целевой функции задачи и неко-
торой функции
H(x1, x2,..., xn),
определяемой системой ограничений и
m
называемой штрафной функцией. Штрафную функцию можно постро- ить различными способами. Однако наиболее часто она имеет вид
H(x1, x2,..., xn) ai(x1, x2,..., xn)gi(x1, x2,..., xn),
i1
где
a(x, x
,..., x
) 0, если bi
gi(x1, x2,..., xn) 0,
(1.29)
i 1 2
n
ai, если bi
gi(x1, x2,..., xn) 0,
ai>0 – представляющие собой весовые коэффициенты.
Используя штрафную функцию, последовательно переходят от одной точки к другой до тех пор, пока не получат приемлемое реше- ние. При этом координаты последующей точки находят по формуле
(k1)
k f( X(k) ) m
g( X(k) )
xj max 0; xj
j
X
ai
i1
Xj
.
(1.30)
Из последнего соотношения следует, что если предыдущая точка
находится в области допустимых решений исходной задачи, то второе слагаемое в квадратных скобках равно нулю и переход к последую- щей точке определяется только градиентом целевой функции. Если же указанная точка не принадлежит области допустимых решений, то
за счет данного слагаемого на последующих итерациях достигается возвращение в область допустимых решений. При этом, чем меньше ai, тем быстрее находится приемлемое решение, однако точность его определения снижается. Поэтому итерационный процесс обычно на- чинают при сравнительно малых значениях aiи, продолжая его, эти значения постепенно увеличивают.
Итак, процесс нахождения решения задачи выпуклого програм- мирования методом штрафных функций включает в себя следующие этапы:
-
определяют исходное допустимое решение; -
выбирают шаг вычислений; -
находят по всем переменным частные производные от целевой функции и функций, определяющих область допустимых решений задачи; -
по формуле (1.30) находят координаты точки, определяющей возможное новое решение задачи; -
проверяют, удовлетворяют ли координаты найденной точки сис- теме ограничений задачи. Если нет, то переходят к следующему этапу. Если координаты точки определяют допустимое решение задачи, то исследуют необходимость перехода к последующему допустимому решению. В случае такой необходимости переходят к этапу 2, в противном случае, найдено приемлемое решение ис- ходной задачи; -
устанавливают значения весовых коэффициентов и переходят к этапу 4.
