Постановка и классификация задач математического программирования

Постановка и классификация  задач математического программирования.

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

Математическое программирование — область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т. е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных. 
     Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называют целевой, показателем эффективности или критерием оптимальности. Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель. Математическая модель задачи — это отражение оригинала в виде функций, уравнений, неравенств, цифр и т. д. Модель задачи математического программирования включает: 
     1) совокупность неизвестных величин, действуя на которые, систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, управлением, стратегией, поведением и др.); 
     2) целевую функцию (функцию цели, показатель эффективности, критерий оптимальности, функционал задачи и др.). Целевая функция позволяет выбирать наилучший вариант - из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение. Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень обслуживания или дефицитности, число комплектов, отходы и т. д.; 
     Эти условия следуют из ограниченности ресурсов, которыми располагает общество в любой момент времени, из необходимости удовлетворения насущных потребностей, из условий производственных и технологических процессов. Ограниченными являются не только материальные, финансовые и трудовые ресурсы. Таковыми могут быть возможности технического, технологического и вообще научного потенциала. Нередко потребности превышают возможности их удовлетворения. Математически ограничения выражаются в виде уравнений и неравенств. Их совокупность образует область допустимых решений (область экономических возможностей). План, удовлетворяющий системе ограничений задачи, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным. Оптимальное решение, вообще говоря, не обязательно единственно, возможны случаи, когда оно не существует, имеется конечное или бесчисленное множество оптимальных решений.

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

Все эти задачи МП формально сводятся к одной общей постановке:  
Найти значения переменных X1,...,Xn , доставляющие максимум (минимум) заданной скалярной функции z=f(X1,...,Xn) 
при условиях Условия, о которых идет речь, ограничивают выбор значений X1,...,Xn и могут обладать самыми разнообразными свойствами, определяемыми видом функций В каждой из m строк здесь сохраняется какой-либо один знак (равенство, неравенство).

Множество точек  удовлетворяющих системе ограничений есть область определения поставленной выше задачи. Целевая функция z достигает экстремального значения в одной или нескольких точках области которые предстоит найти.

Обычно  вид функций z и  известен, константы bi; заданы, величины m и n являются произвольными целыми. Специально оговариваются ограничения, выраженные в требованиях неотрицательности и целочисленности

Учитывая  сказанное, можно дать краткую запись условий задачи математического программирования: В основу классификации таких задач положены особенности функций z или gi, встречающихся в конкретных исследованиях. Различают два основных класса задач-задачи линейного и нелинейного программирования

К первым относятся те, в которых и целевая функция z, и все функции линейны относительно переменных

Ко вторым-те, в которых присутствуют различного рода нелинейности.

В качестве примеров назовем лишь хорошо изученные и широко распространены задачи:

• Решаемые средствами классической математики при условии, что среди ограничений нет неравенств, выполняется условие т < п, нет требований неотрицательности или целочисленности переменных, функции z и gi непрерывны и по крайней мере дважды дифференцируемы;
• Имеющие линейные ограничения и целевую функцию, представляющую собой полином второй степени относительно
• Имеющие целевую функцию, представленную в виде суммы произвольных функций отдельных переменных xj
• Обладающие такими универсальными свойствами, как выпуклость z и что позволяет формировать и использовать условия существования решений независимо от конкретных форм задания z и