русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Виды математического программирования


Дата добавления: 2013-12-23; просмотров: 3615; Нарушение авторских прав


Задачи математического программирования

 

 

В самом общем случае задача нахождения оптимального (максимального или минимального) значения целевой функции может быть записана как:

 

U=f(X)→ max;X,W,

 

где X = (x1,x2,…,xn);

W - область допустимых значений переменных x1,x2,…,xn;

f(X) - целевая функция.

Для того чтобы решить эту оптимизационную задачу, достаточно указать X0ОW такое, что f(X0) ≥f(X) при любом XОW, f(X0) ≤f(X)при любом XОW. Методы решения оптимизационных задач зависят как от вида целевой функции f(X), так и от строения допустимого множества W. Если целевая функция в задаче является функциейn переменных, то методы решения называют методами математического программирования.

В математическом программировании принято выделять следующие основные задачи в зависимости от вида целевой функции f(X) и от области W:

· задачи линейного программирования, если f(X) и W линейны;

· задачи целочисленного программирования, если ставится условие целочисленности переменных x1,x2,…,xn;

· задачи нелинейного программирования, если f(X) или W имеют нелинейный характер.

Общая постановка задачи нелинейного программирования выглядит следующим образом. Найти неотрицательные значения элементов решения x1,x2,...,xn,удовлетворяющие ограничениям произвольного вида и обращающие в максимум произвольную нелинейную функцию этих элементов решения:

 

W=f(x1,x2,...,xn)→ max.

 

Общих способов решения таких задач нет. Иногда их сводят к задачам линейного программирования, рассматривая полученные решения как приближенные. В ряде случаев применяют так называемый "метод штрафных функций" сводящий задачу поиска экстремума при наличии ограничений к аналогичной задаче при отсутствии ограничений, которая обычно решается проще.



Идея метода штрафных функций в том, что вместо наложения системы ограничений, налагается некоторый достаточно большой "штраф" за нарушение ограничений, который добавляется к целевой функции W. Штраф имеет общий вид: a(x1,x2,...,xn), где a - коэффициент пропорциональности (если W максимизируется он отрицателен, если минимизируется - положителен). Далее можно, увеличивая абсолютное значение a, посмотреть, как изменяется при этом оптимальное решение (x1°,x2°,...,xn°)и, когда оно практически перестанет меняться, остановиться на нем.

В ряде случаев при решении задач нелинейного программирования оказывается полезным так называемый "метод случайного поиска", состоящий в том, что вместо упорядоченного перебора возможных вариантов решения применяется случайный розыгрыш.

На практике часто встречаются задачи, совпадающие по постановке с задачами линейного программирования, но отличающиеся той особенностью, что искомые элементы решения непременно должны быть целыми. Такие задачи называют задачами целочисленного (дискретного) программирования; дополнительное условие целочисленности существенно затрудняет их решение. В ряде случаев задачи целочисленного программирования сводят к задачам линейного программирования, а полученные элементы решения рассматривают как приблизительные.

В последнюю очередь упомянем о задачах стохастического программирования. Их особенность в том, что ищется оптимальное решение в условиях неполной определенности, когда ряд параметров, входящих в целевую функцию W и ограничения, накладываемые на решение, представляют собой случайные величины. Часто такие задачи сводят к детерминированным (рассматривая случайные величины как математические ожидания).

В тех случаях, когда использование точных методов затруднительно или исключено, применяют различного рода приближенные алгоритмы, полученные на основе "здравого смысла". Такой подход в специальной литературе часто называют эвристическим программированием, а решаемые задачи - задачами эвристического программирования.

Задачи целочисленного, нелинейного, стохастического и эвристического программирования решаются с привлечением достаточно сложного математического аппарата, поэтому ниже рассмотрен лишь инструментарий линейного программирования и некоторые понятия динамического программирования.

 



<== предыдущая лекция | следующая лекция ==>
Моделирование потоков событий | Общая постановка задачи линейного программирования


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.005 сек.