2297

Система Mathcad. Розв’язування задач оптимізації

Лекция

Математика и математический анализ

Пошук екстремуму функції. Екстремум функції багатьох змінних. Локальний екстремум. Умовний екстремум. Приклад вирішення транспортної задачі в середовищі Mathcad. Зміна чисельного методу. Вікно діалогу Advanced Options.

Украинкский

2013-01-06

92.14 KB

66 чел.

Лекція 12. Система Mathcad. Розв’язування задач оптимізації

План

1. Пошук екстремуму функції.

1.1. Локальний екстремум.

1.2. Умовний екстремум.

1.3. Екстремум функції багатьох змінних.

2. Приклад розв’язування транспортної задачі в середовищі Mathcad.

1. Пошук екстремуму функції

Задачі пошуку екстремуму функції передбачають знаходження її максимального або мінімального значення в деякій області визначення її аргументів. Обмеження на значення аргументів, які задають цю область, та інші додаткові умови повинні бути визначені у вигляді системи нерівностей і (або) рівнянь.

Для розв’язування задач пошуку максимуму та мінімуму в системі Mathcad є вбудовані функції Minerr, Minimize и Maximize. Всі вони використовують градієнтні чисельні методи.

Mathcad пропонує три різних градієнтних методи . Щоб змінити чисельний метод, потрібно:

  1.  Клацнути правою кнопкою миші на імері функції Find.
  2.  Навести вказівку миші на пункт Nonlinear( Нелинейный) в контекстному меню.
  3.  В меню, що з'явиться, вибрати один із трьох методів: Conjugate Gradient (Спряжених градієнтів), Quasi-Newton (Квазі-Ньютоновський) або Levenberg (Левенберга).

Рис. 1. Зміна чисельного методу

Щоб повернути автоматичний вибір типу чисельного методу, потрібно в контекстному меню вибрати пункт Autoselect (Автоматичний вибір). Крім вибору самого методу , в Mathcad є можливість встановлювати деякі їх параметри. Для цього потрібно за допомогою того ж контекстного меню викликати вікно діалогу Advanced Options (Додаткові параметри), вибравши для цього пункти Nonlinear/ Advanced Options (Нелінійний/Додаткові параметри).

Рис. 2. Вікно діалогу Advanced Options

В цьому вікні є п’ять груп перемикачів, по два в кожній. В першому рядку Derivative estimation (Аппроксимація похідної) визначаєься метод обчислення похідної Forward (Вперед) або Central (Центральна). Вони відповідають апроксимації похідної або правою, або центральною скінченною різницею. В другому рядку Variable estimation (Апроксимація змінних) можна визначити тип апроксимації рядом Тейлора. Для апроксимації дотичною прямою лінією виберіть перемикач Tangent (Дотична), для більш точної квадратичної апроксимації (параболою) встановіть перемикач Quadratic (Квадратична). Наступна група перемикачів Linear variable check (Перевірка лінійності) дозволяє в специфічних задачах зекономити час обчислень. Якщо нелінійності всіх функцій, що входять в рівняння, мало впливають на значення всіх їх частинних похідних, то потрібно встановити перемикач Yes (Так). В цьому випадку похідні будуть прийняті рівним константам і не будуть обчислюватися на кожному кроці. Але потрібно дуже обережно змінювати параметри чисельних методів і тоді, коли розв’язок не знаходиться при заданих за замовчування параметрах або коли обчислення займають багато часу. Пара перемикачів Multistart (Сканування) задають опцю пошуку глобального або локального мінімуму або максимуму. Якщо встановлений перемикач Yes (Так), Mathcad буде намагатися знайти найбільш глибокий екстремум в області, близькій до початкового наближення. Нарешті, останній перемикач Evolutionary (Эволюційний алгоритм) дозволяє використовувати модифікацію чисельного методу для розв’язування рівнянь, визначених не обов’язково гладкими функціями, якщо його встановити в положення Yes (Так). Правильний вибір чисельного методу та його параметрів може допомогти при розв’язуванні нестандартних задач.

Локальний екстремум.

Пошук екстремуму включає в себе задачі знаходження локального та глобального екстремуму.

В Mathcad за допомогою вбудованих функцій розв’язується тільки задача пошуку локального екстремуму. Щоб знайти глобальний максимум (або мінімум), потрібно спочатку обчислити всі їх локальні значення і потім серед них вибрати найбільший (найменший), або попередньо просканувати з деяким кроком задану область, щоб виділити з неї підобласть найбільших (найменших) значень функції і здійснити пошук глобального екстремуму, уже знаходячись в його околі. 

Для пошуку лкальних екстремумів є дві вбудовані функції, які можуть використовуватися як в межах обчислювального блоку, так і автономно.

Minimize (f, x1, ... ,хм) — вектор значень аргументів, при яких функція досягає мінімуму;

Maximize (f, х1, ... ,хм) — вектор значень аргументів, при яких функція досягає максимуму;

f (x1, ... , хм,...) — функція;

x1, ... , xм — аргументи, за якими виконується мінімізація (максимізація).

Всім аргументам функції f попередньо потрібно присвоїти деякі значення, причому для тих змінних, за якими виконується мінімізація, вони будуть сприйматися як початкові наближення.

Розглянемо приклади обчислення екстремуму функції однієї змінної без додаткових умов. Так як ніякиї додаткових умов не накладається, пошук екстремуму виконується для будь-яких значень.

Приклад 1. Знайти мінімум функції однієї змінної

Приклад 2. Знайти максимум функції однієї змінної

Умовний екстремум

В задачах на умовний екстремум функції мінімізації та максимізації повинні бути включені в обчислювальний блок , тобто перед функціями повинно бути записане ключове слово Given. В проміжку між Given і функцією пошуку екстремуму за допомогою бульових операторів записуються логічні вирази, які задають обмеження на значення аргументів функції. Розглянемо приклад пошуку умовного екстремуму функції. Порівняйте результати цього прикладу з результатами двох попередніх.

Приклад 3. Три приклади пошуку умовного екстремуму функції

Екстремум функції багатьох змінних

Обчислення екстремуму функції багатьох змінних принципово не відрізняється від обчислення екстремуму функції однієї змінної. Тому обмежимося розглядом прикладу знаходження максимуму та мінімуму функції

Приклад 4. Екстремум функції двох змінних

2. Приклад розв’язування транспортної задачі в середовищі Mathcad

Постановка ТЗ

При організації та плануванні перевезень вантажів виникає широкий клас задач, пов'язаних з мінімізацією затрат на перевезення, які розв'язують за допомогою математичного апарату лінійного програмування.

Розглянемо постановку ТЗ в загальному вигляді. Нехай маємо m постачальників А1 , А2 ,..., Аm із запасами однорідних вантажів a1 , a2 ,..., am та n споживачів B1 , B2 ,..., Bn з потребами b1 , b2 ,..., bn. Тарифи перевезень вантажів, що можуть виражатись різними показниками (відстань, вартість або час) між постачальниками та споживачами, задані у вигляді матриці

Необхідно скласти такий план перевезень вантажів, при якому сумарна вартість перевезень мінімальна.

Якщо ввести такі позначення: xij - обсяг перевезень вантажів від і-го постачальника до j-го споживача та Z - сумарна вартість перевезень вантажів, то при розв'язанні ТЗ ми повинні мінімізувати вартість перевезень вантажів . 

Матрицю X = (xij ), називають матрицею перевезень.

В залежності від співвідношення запасів вантажів у постачальників та сумарних потреб споживачів розрізняють закриту та відкриту ТЗ.

Означення 1. Транспортна задача називається закритою (ЗТЗ), якщо сума запасів вантажів у постачальників дорівнює сумі потреб споживачів, тобто виконується умова .

Необхідна умова розв’язання ТЗ — ТЗ має розв’язок лише тоді, коли вона є закритою.

Означення 2. Транспортна задача називається відкритою (ВТЗ), якщо сума запасів вантажів у постачальників не дорівнює сумі потреб споживачів, тобто виконується умова .

Розглянемо два випадки:

1) якщо сума запасів у постачальника менша, ніж сума потреб споживачів, тобто виконується умова то вводять додаткового фіктивного постачальника із запасами = . Тарифи перевезень (відстані) від цього постачальника до споживачів дорівнюють нулю.

2) якщо сума запасів у постачальника більша, ніж сума потреб споживачів, тобто виконується умова  то вводять додаткового фіктивного споживача із потребами = . Тарифи перевезень (відстані) від цього споживача до постачальників дорівнюють нулю.

Приклад 1. Приклад розв’язування транспортної задачі в середовищі Mathcad.


 

А также другие работы, которые могут Вас заинтересовать

33633. Построение модели систем защиты на базе Е-сетей на основе выделенного набора правил фильтрации 78 KB
  2 Переходы: d3 = XEâ€r3 p1 p2 p3 t3 установление соединения проверка пароля и имени пользователя для доступа к внутренней сети подсети; d4 = XEâ€r4 p2 p4 р5 0 подсчет попыток ввода пароля и имени; d5 = Tp4 p6 0 вывод сообщения о неверном вводе пароля и имени; d6 = Tp1 p6 0 – передача пакета для повторной аутентификации и идентификации; d7 = Tp5 p7 t4 создание соответствующей записи в журнале учета и регистрации. 3 Решающие позиции: r3 проверка пароля и имени пользователя; r4 ...
33634. RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman) 92.5 KB
  Алгоритм RS состоит из следующих пунктов: Выбрать простые числа p и q заданного размера например 512 битов каждое. Вычислить n = p q Вычисляется значение функции Эйлера от числа n: m = p 1 q 1 Выбрать число d взаимно простое с m Два целых числа называются взаимно простыми если они не имеют никаких общих делителей кроме 1. Выбрать число e так чтобы e d = 1 mod m Числа e и d являются ключами. Шифруемые данные необходимо разбить на блоки числа от 0 до n 1.
33635. IDEA (англ. International Data Encryption Algorithm, международный алгоритм шифрования данных) 121 KB
  Interntionl Dt Encryption lgorithm международный алгоритм шифрования данных симметричный блочный алгоритм шифрования данных запатентованный швейцарской фирмой scom. Известен тем что применялся в пакете программ шифрования PGP. Если такое разбиение невозможно используются различные режимы шифрования. Каждый исходный незашифрованный 64битный блок делится на четыре подблока по 16 бит каждый так как все алгебраические операции использующиеся в процессе шифрования совершаются над 16битными числами.
33636. Advanced Encryption Standard (AES) - Алгоритм Rijndael 317.5 KB
  dvnced Encryption Stndrd ES Алгоритм Rijndel Инициатива в разработке ES принадлежит национальному институту стандартов США NIST. Основная цель состояла в создании федерального стандарта США который бы описывал алгоритм шифрования используемый для защиты информации как в государственном так и в частном секторе. В результате длительного процесса оценки был выбрал алгоритм Rijndel в качестве алгоритма в стандарте ES. Алгоритм Rijndel представляет собой симметричный алгоритм блочного шифрования с переменной длиной блока и переменной...
33637. Актуальность проблемы обеспечения безопасности сетевых информационных технологий 13.99 KB
  Отставание в области создания непротиворечивой системы законодательноправового регулирования отношений в сфере накопления использования и защиты информации создает условия для возникновения и широкого распространения компьютерного хулиганства и компьютерной преступности. Особую опасность представляют злоумышленники специалисты – профессионалы в области вычислительной техники и программирования досконально знающие все достоинства и слабые места вычислительных систем и располагающие подробнейшей документацией и самыми совершенными...
33638. Основные понятия информационной безопасности 31 KB
  В связи с бурным процессом информатизации общества все большие объемы информации накапливаются хранятся и обрабатываются в автоматизированных системах построенных на основе современных средств вычислительной техники и связи. Автоматизированная система АС обработки информации – организационнотехническая система представляющая собой совокупность взаимосвязанных компонентов: технических средств обработки и передачи данных методов и алгоритмов обработки в виде соответствующего программного обеспечения информация массивов наборов баз...
33639. Классификация уязвимостей 37.5 KB
  Некоторые уязвимости подобного рода трудно назвать недостатками скорее это особенности проектирования. В Уязвимости могут быть следствием ошибок допущенных в процессе эксплуатации информационной системы: неверное конфигурирование операционных систем протоколов и служб использование нестойких паролей пользователей паролей учетных записей по умолчанию и др. по уровню в инфраструктуре АС К уровню сети относятся уязвимости сетевых протоколов стека TCP IP протоколов NetBEUI IPX SPX. Уровень операционной системы охватывает уязвимости...
33640. Основные механизмы защиты компьютерных систем 39 KB
  Основные механизмы защиты компьютерных систем Для защиты компьютерных систем от неправомерного вмешательства в процессы их функционирования и несанкционированного доступа НСД к информации используются следующие основные методы защиты защитные механизмы: идентификация именование и опознавание аутентификация подтверждение подлинности субъектов пользователей и объектов ресурсов компонентов служб системы; разграничение доступа пользователей к ресурсам системы и авторизация присвоение полномочий пользователям; регистрация и...
33641. Криптографические методы защиты информации, Контроль целостности программных и информационных ресурсов 37 KB
  Криптографические методы защиты информации Криптографические методы защиты основаны на возможности осуществления специальной операции преобразования информации которая может выполняться одним или несколькими пользователями АС обладающими некоторым секретом без знания которого с вероятностью близкой к единице за разумное время невозможно осуществить эту операцию. В классической криптографии используется только одна единица секретной информации ключ знание которого позволяет отправителю зашифровать информацию а получателю расшифровать...