Министерство образования республики беларусь белорусский государственный университет гуманитарный факультет Кафедра информационных технологий
Скачать 0.49 Mb.
|
| МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Гуманитарный факультет Кафедра информационных технологий Кухарский Артур Сергеевич Макарова Александра Андреевна Антонова Анна Артуровна доклад на тему: Тема: «Математическое программирование» Минск 2013 СодержаниеСодержание 2 Введение 3 1 Линейное программирование 6 2 Нелинейное программирование 8 3 Целочисленное программирование. 11 4 Условная оптимизация 13 5 Безусловная оптимизация 15 6 Динамическое программирование 17 7 Дискретное программирование 20 8 Стохастическое программирование 21 ПРИЛОЖЕНИЕ 1 Примеры задач линейного программирования: 23 ПРИЛОЖЕНИЕ 2 Нелинейное программирование: 28 Поэтому или zmax ≈ 21,9. 32 ПРИЛОЖЕНИЕ 3 Динамическое программирование 33 Приложение 4 Динамическое программирование 35 Метод северо-западного угла 36 Приложение 5 Целочисленное программирование 42 Приложение 6. Краткое описание MatLab 45 ВведениеМатематическое программирование – это раздел математики, занимающийся разработкой методов отыскания экстремальных значений функции, на аргументы которой наложены ограничения. Математического программирование делится:
Математическое программирование находят применение в различных областях человеческой деятельности, где необходим выбор одного из возможных образов действий, например, при решении многочисленных проблем управления и планирования производственных процессов, в задачах проектирования и перспективного планирования. Наименование «Математическое программирование» связано с тем, что целью решения задач является выбор программы действий. Математическая формулировка задачи математического программирование: минимизировать скалярную функцию j(x) векторного аргумента х на множестве X = {x: gi(x) = 0, hi(x) = 0, i = 1, 2, ..., k}, где gi(x) и hi(x) — также скалярные функции; функцию j(x) называют целевой функцией, или функцией цели, множество X — допустимым множеством, решение х* задачи математического программирования— оптимальной точкой (вектором). В математическое программировании принято выделять следующие разделы. Линейное программирование: целевая функция j(x) и ограничения gi(x) и hi (х) линейны; выпуклое программирование: целевая функция и допустимое множество выпуклы; квадратичное программирование: целевая функция квадратична и выпукла, допустимое множество определяется линейными равенствами и неравенствами; дискретное программирование: решение ищется лишь в дискретных, например целочисленных, точках множества X; стохастическое программирование: в отличие от детерминированных задач, здесь входная информация носит элементы неопределённости; например, в стохастических задачах о минимизации линейной функции  при линейных ограничениях  , i = 1, 2, …, m,либо все величины cj, aij, bi, либо часть из них случайны. Задачи перечисленных разделов обладают общим свойством: всякая точка локального минимума является оптимальной точкой. Несколько в стороне находятся так называемые многоэкстремальные задачи — задачи, для которых указанное свойство не выполняется. В основе теории выпуклого программирования и, в частности, линейного и квадратичного, лежит теорема Куна — Таккера о необходимых и достаточных условиях существования оптимальной точки x*: для того чтобы точка х* была оптимальной, то есть  ,X = {x: gi(x) ³ 0, i = 1, 2, ..., k}, необходимо и достаточно, чтобы существовала такая точка у* (у*1, у*2, ..., у*k), чтобы пара точек х*, у*образовывала седло функции Лагранжа  Последнее означает, что L(x*, y) L(x*, y*) £ L(x, у*) для любых х и всех у³ 0. Если ограничения gi(x) нелинейны, то теорема справедлива при некоторых дополнительных предположениях о допустимом множестве. Если функции j(x) и gi(x) дифференцируемы, то следующие соотношения определяют седловую точку  ,j= 1, 2, …, n; ;  ;i= 1, 2, …, k; , yi ³ 0, i = 1, 2, …, k.Таким образом, задача выпуклого программирования сводится к решению системы уравнений и неравенств. На основе теоремы Куна — Таккера разработаны различные итерационные методы минимизации, сводящиеся к поиску седловой точки функции Лагранжа. В математическом программировании одно из главных мест принадлежит вычислительным методам решения экстремальных задач. Широким классом таких методов являются методы проектирования. Идея этих методов состоит в следующем. В точке xk Î X выбирается направление спуска sk, то есть одно из направлений, по которому функция j(x) убывает, и вычисляется xk+1 = p(xk + aksk), где p(xk + aksk) означает проекцию точки xk + aksk на множество X:  ,число ak > 0 выбирается при этом так, чтобы j(xk +1) < j(xk). Существуют различные варианты методов проектирования. Наиболее распространённым из них является метод проекции градиента, когда sk = —grad j(xk). В математическои программировании доказано, что при определённых условиях на целевую функцию и допустимое множество, последовательность {хk}, построенная методом проекции градиента, такова, что  стремится к нулю со скоростью геометрической прогрессии.Характерной особенностью вычислительной стороны методов решений задач иатематического программирование является то, что применение этих методов неразрывно связано с использованием электронных вычислительных машин, в первую очередь потому, что задачи математического программирования, связанные с ситуациями управления реальными системами, являются задачами большого объёма, недоступными для ручного счёта. Важным направлением исследования в Математическое программирование являются проблемы устойчивости. Здесь существующее значение имеет изучение класса устойчивых задач — задач, для которых малые возмущения (погрешности) в исходной информации влекут за собой малые возмущения и в решении. В случае неустойчивых задач большая роль отводится процедуре аппроксимации неустойчивой задачи последовательностью устойчивых задач — так называемому процессу регуляризации. |
Добавить документ в свой блог или на сайт
Похожие:
 | Республики Беларусь Белорусский государственный университет Юридический факультет Принятие решения по акту проверки и порядок его обжалования в Республике Беларусь 3 |  | Республики Беларусь Белорусский Государственный Университет Интересный факт из истории создания Java-технологии, или удар по «пакету Windows» 29 |
| Республики Беларусь Учреждение образования «Белорусский государственный... Составители: В. А. Овсянкин, кандидат педагогических наук, доцент, Г. Н. Сущенко, старший преподаватель | | Министерство образования и науки РФ новосибирский государственный... Когда появляется изображение цепи ордена Андрея Первозванного на российском гербе |
| Республики Беларусь Белорусский государственный университет Управляющие... Если необходимо обеспечить выполнение цикла хотя бы один раз, то удобно использовать оператор цикла с постусловием: 20 | | Дмитрий Олегович Роль информационных технологий в обеспечении деятельности... Роль информационных технологий в обеспечении деятельности банковской системы Республики Беларусь на примере сэд «Канцлер» |
| Совершенствование правового регулирования таможенных процедур переработки... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Московский государственный... | | Государственный образовательный стандарт высшего профессионального... На основании статьи 35 Закона Республики Беларусь от 20 июля 2007 года "Об обращении с отходами" Министерство природных ресурсов... |
| Классификация и кодирование информации; системы классификации; методы кодирования Министерство образования республики беларусь учреждение оразования «мозырский государственный педагогический университет имени И.... | | Республики Беларусь Учреждение образования «Белорусский государственный... Контрольная работа предназначена для самостоятельного выполнения студентами с целью проверки качества освоения ими теоретического... |
| Пояснительная записка программа интернатуры по оториноларингологии... Заведующая кафедрой болезней уха, горла, носа учреждения образования «Белорусский государственный медицинский университет», кандидат... | | Республики Беларусь Учреждение образования «Белорусский государственный... Дневник здоровья предназначен для определения физического состояния студентов бгпу, записи заданий преподавателя для самостоятельных... |
| «московский психолого-социальный университет» факультет информационных технологий утверждаю Рабочая программа предназначена для бакалавров кафедр Информатики и математики и Информационных технологий очной и заочной формы... | | Министерство образования и науки российской федерации правительство... Правила определяют основные требования технической эксплуатации железной дороги |
| Применение технологий olap и Data Mining для поддержки принятия стратегических решений в вузе Дагестанский государственный университет, факультет информатики и информационных технологий, Махачкала, Россия | | Учебно-методический комплекс по модулю «астрономия» (б кв ) Факультет... ... |
