|
|
Поиск экстремума унимодальных функций, условная оптимизацияСОДЕРЖАНИЕ ЗАДАНИЕ 1 3 ЗАДАНИЕ 2 7 Список литературы 10 ЗАДАНИЕ 1 Поиск экстремума унимодальных функций методом дихотомии. Найти максимум функции: f(x) = 4x + 8x3 - 6x4 . РЕШЕНИЕ Функция одной переменной, имеющая в интервале исследования один максимум (минимум), называется унимодальной , или функция у(х) унимодальная, если x1 < xопт, x2 < xопт , x1 < x2 , то y(x1) < y(x2). Как правило задачи исследования операций имеют унимодальную целевую функцию. Унимодальная функция не обязательно должна быть гладкой и даже непрерывной - она может быть изломанной (недифференцируемой), разрывной и даже может в некоторых точках интервала быть неопределенной. Предположение унимодальности не связано с жесткими ограничениями и выполняется во многих практических задачах поиска оптимума. Если целевая функция унимодальна, то можно сузить интервал исследования функции на оптимум путем определения значений целевой функции в двух точках интервала задания функций y(x1) и y(x2) и последующего поинтервального сравнения. Последовательно сужая интервал исследования, в котором находится оптимальное значение искомой управляющей переменной, можно с достаточной степенью точности найти оптимальное значение искомой переменной. Для этого необходимо выработать такую стратегию поиска, чтобы за заданное число шагов (этапов) определить минимальный интервал, в котором лежит искомый оптимум, или свести исходный интервал до области заданной длины за минимальное число шагов расчетов. К последовательным детерминированным методам поиска экстремума унимодальных функций (учитывающим результаты предыдущих шагов) относятся методы дихотомии, Фибоначчи и золотого сечения. В методе дихотомии искомая длина интервала исследования XN,в котором лежит искомый оптимум, уменьшается с каждым шагом N почти в два раза. Алгоритм метода состоит из следующих этапов: 1) Задаём точность искомого решения ? = ?x - xопт?. 2) Задаём границы интервала поиска решения хнач и хкон. 3) Делим исходный интервал исследования пополам х = (хнач + хкон)/2. 4) Вблизи точки деления (пo разные ее стороны) подсчитываем дважды значение целевой функции y(x1) и y(x2), где x1 = x - ?x , x2 = x + ?x , а наименьший интервал измененния управляющей переменной ?x = ? / 2 . 5) Используя свойства унимодальных функций, определяем интервал, в котором находится экстремальное значение целевой функции: если y(х1) > y(х2), то хопт < х2 и xкон = x ; если y(х1) < y(х2), то хопт > х1 и xнач = x . Процесс расчета повторяется c пункта 3 алгоритма по аналогичной схеме до тех пор, пока не будет найден хопт: y(х1) = y(х2), то х1 < хопт < х2 . Для автоматизации итерационных расчётов составляем программу на языке высокого уровня BASIC. Блок-схема программы на основе описанного алгоритма приведёна на рис. 1. Программы некритична к версии интерпретатора (компилятора) языка и модели персональной ЭВМ, так как использует универсальный набор операторов. ЛИСТИНГ ПРОГРАММЫ 10 CLS 20 INPUT "Ao = "; A0 30 INPUT "A1 = "; A1 40 INPUT "A2 = "; A2 50 INPUT "B = "; B 60 INPUT "C = "; C 70 INPUT "Xn = "; XN 80 INPUT "Xk = "; XK 90 INPUT "e = "; E 100 DX = .5 * E 110 X = (XN + XK) / 2 120 X1 = X - DX: X2 = X + DX 130 Y1 = A0 * X1 + A1 * (X1 ^ B) - A2 * (X1 ^ C) 140 Y2 = A0 * X2 + A1 * (X2 ^ B) - A2 * (X2 ^ C) 141 PRINT 142 PRINT "X1=", X1, "Y1=", Y1 143 PRINT "X2=", X2, "Y2=", Y2 150 IF ABS(Y1 - Y2) < E THEN 190 160 IF Y1 > Y2 THEN 180 170 XN = X: XK = XK: GOTO 110 180 XN = XN: XK = X: GOTO 110 190 Y = (Y1 + Y2) * .5 200 PRINT "Xopt = ", X, "Ymax = ", Y 210 STOP Рис. 1. Блок-схема. В соответствии с вариантом задания принимаем а0 = 4, а1 = 8, а2 = 6, b = 3, c = 4. Для расчёта на ЭВМ точность вычислений можно задать повышенную. Принимаем ? = 0,001. Интервал поиска от xнач = 0 до xкон = 100. Результаты машинного расчёта: X1= 1.122547 Y1= 6.279175 X2= 1.123547 Y2= 6.279451 Xopt = 1.123047 Ymax = 6.279313 Откуда делаем заключение, что своего максимума ymax = 6,279 целевая функция достигает при xопт = 1,123. Высокая степень точности и реализация расчёта на ЭВМ позволяет говорить о достаточной достоверности результатов расчёта. Доказательством правильности расчёта служит график целевой функции (рис. 2), построенный средствами табличного процессора Excel 97 для интервала от хнач = 0 до хкон = 1,8 с шагом 0,01. На графике наглядно представлено, что максимум функции соответствует вычисленным значениям. Рис. 2. График функции. ЗАДАНИЕ 2 Условная оптимизация. Метод множителей Лагранжа. Найти максимум функции f(x, y) = 4x2y6 + 8x4y1 на прямой 2x+4y = 10. РЕШЕНИЕ Метод множителей Лагранжа позволяет определить экстремальные точки функции многих переменных при наличии дополнительных связей между оптимизируемыми параметрами. Пусть требуется найти экстремум целевой функции: y = f(x1, x2, ..., xn) . При этом существуют дополнительные условия: ?k (x1, x2, ..., xn) = 0 , k = . Поэтому, добавив р дополнительных ?1,..., ?p множителей, можно построить новую функцию: L = f(x1, x2,..., xn) - ??k ?k (x1, x2,..., xn) , где ?k - множители Лагранжа. Необходимым условием экстремума является равенство нулю всех первых частных производных от L по ?k и xi: ?L/??k = 0 (k = ) ; ?L/?xk = 0 (i= ) . В результате получается n + р уравнений с неизвестными (x1, x2, ..., xn, ?1, ?2,..., ?p). Решение этих уравнений относительно переменных x и ? дает возможность определить положение стационарной точки. Использование вспомогательной функций позволяет заменить задачу с дополнительными условиями задачей без них. Введение р дополнительных переменных, которые должны быть исключены с помощью р дополнительных уравнений, является недостатком метода множителей Лагранжа. Этому методу присущи недостатки и трудности классического метода дифференциального исчисления. Существенным недостатком метода множителей Лагранжа является невозможность решения с его помощью задач, имеющих ограничения в форме неравенств. Составим функцию Лагранжа для заданного выражения: L = 4x2y6 + 8x4y + ?(10 - 2x- 4y) . Производные по х и y: ?L/?x = 8xy6 + 32x3y - 2? , ?L/?y = 24x2y5 + 8x4 - 4? . Из первого уравнения находим: ? = 8xy6 + 32x3y / 2 = 4xy6 + 16x3y . Из второго уравнения: ? = 24x2y5 + 8x4 / 4 = 6x2y5 + 2x4 . Приравнивая уравнения между собой, получим: 4xy6 + 16x3y = 6x2y5 + 2x4 , 4xy6 + 16x3y - 6x2y5 - 2x4 = 0 , 2x(2y6 + 8x2y - 3xy5 - x3) = 0 , 2y6 + 8x2y - 3xy5 - x3 = 0 . Используя заданное уравнение прямой, находим: x = 5 - 2y . Подставив это выражение в предыдущее уравнение, получим: 2y6 + 8(5 - 2y)2y - 3(5 - 2y)y5 - (5 - 2y)3 = 0 2y6 + 8(5 - 2y)(5 - 2y)y - 3(5 - 2y)y5 - (5 - 2y)(5 - 2y)(5 - 2y)= 0 2y6 + 8(25 - 10y - 10y + 4y2)y - 3(5 - 2y)y5 - (5 - 2y)(25 - 20y + 4y2) = 0 2y6 + 200y - 160y2 + 32y3 - 15y5 - 6y6 - (125 - 50y - 100y + 40y2 + 20y2 - 8y3) = 0 2y6 + 200y - 160y2 + 32y3 - 15y5 - 6y6 - 125 + 50y + 100y - 40y2 - 20y2 + 8y3 = 0 - 4y6 - 15y5 + 40y3- 220y2 + 350y - 125 = 0 Решая это уравнение средствами математического процессора MathCAD 8.0, получаем корни уравнения: y1 ? 0,503451, y2 ? 1,190992 . Решение подтверждено графически на рис. 2. Рис. 2. Тогда: x1 = 5 - 2 ? 0,503451 = 3,993099 ; x2 = 5 - 2 ? 1,190992 = 2,618015 . Значения целевой функции: f(x1, y1) = 4? 3,9930992?0,5034516 + 8?3,9930994?0,503451 = 1025,008 ; f(x2, y2) = 4?2,61801526?1,1909926 + 8?2,618014 ?1,190992 = 525,8429 . Максимум целевой функции на прямой 2x+4y = 10 равен: f(x1, y1) = f(3,993099, 0,503451) = 1025,008 . Привлечение средств вычислительной техники гарантирует высокую степень точности решения. СПИСОК ЛИТЕРАТУРЫ Логинов Е.Л. Исследование операций в гражданской авиации. М.: МИИГА, 1982 Лобанов В.В. Исследование операций (на примерах систем гражданской авиации): Конспект лекций. - МИИГА, 1977. Кудрявцев Е.М. Исследование операций в задачах, алгоритмах и программах. - М.: Радио и связь, 1984. 1 2 Работа на этой странице представлена для Вашего ознакомления в текстовом (сокращенном) виде. Для того, чтобы получить полностью оформленную работу в формате Word, со всеми сносками, таблицами, рисунками, графиками, приложениями и т.д., достаточно просто её СКАЧАТЬ.  |
|
Банк готовых работ
Форма заказа
Скачать работу
экономические  Copyright © refbank.ru 2005-2024
Все права на представленные на сайте материалы принадлежат refbank.ru. Перепечатка, копирование материалов без разрешения администрации сайта запрещено. |
|