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

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

В наиболее широком смысле под оптимизацией понимают совокупность математических методов, предназначенных для нахождения наилучших (оптимальных в некотором смысле) вариантов из множества возможных и позволяющих избежать полного перебора и оценивания возможных вариантов. Раздел прикладной математики, изучающий задачи оптимизации, называется математическим программированием. Ранее (в теме 1) было показано, что основное назначение ИО состоит в количественном обосновании оптимальных управленческих решений. Реализовать на практике принцип оптимальности в управлении– это значит решить следующую задачу математического программирования:

найти экстремальное значение целевой функции, зависящей от n -мерного вещественного аргумента:

и дополнительных ограничениях

для всех j от 1 до n (3.3)

Множество всех возможных (допустимых) решений задачи математического программирования называется множеством допустимых решений.

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

Если задача математического программирования не имеет ни одного допустимого решения, то она является недопустимой.

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

Глобальный максимум (минимум) функции – это ее наибольшее (наименьшее) значение из локальных максимумов (минимумов). Локальный максимум (минимум) – это наибольшее (наименьшее) значение целевой функции во всех точках ее ближайшей окрестности.

Точка называется допустимым решением задачи математического программирования, если она удовлетворяет ограничениям (соотношениям (3.2)-(3.3)), и будет при этом являться оптимальным решением, если в этой точке целевая функция достигает своего глобального максимума (минимума) (выражение 3.1).

Можно провести следующую классификацию задач математического программирования:

1. В зависимости от количества неизвестных переменных x различают задачу одномерной (x – одна неизвестная) и многомерной (несколько неизвестных переменных x) оптимизации.

2. В зависимости от наличия ограничений в поставленной задаче различают задачу условной (соотношения 3.2 присутствуют) и безусловной (соотношения 3.2 отсутствуют) оптимизации.

3. В зависимости от вида целевой функции и функций ограничений различают:

· задачу линейного программирования, если функции и , являются линейными;

· задачу нелинейного программирования, если хотя бы одна из функций задачи является нелинейной;

· задачу целочисленного программирования, если все переменные x должны принимать целочисленные иди дискретные значения.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Источник

Оглавление

1. Предмет математического программирования. Линейное программирование

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

Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными. Среди множества возможных ва­риантов в условиях рыночных отношений приходится находить наилуч­шие в некотором смысле при ограничениях, налагаемых на природные, экономические и технологические возможности. До недавнего времени большинство таких задач решалось, исходя из здравого смысла и опыта лиц, принимающих решения или просто «на глаз». При таком подходе не было и не могло быть никакой уверенности, что найденный вариант наи­лучший, а при современных масштабах производства даже незначитель­ные ошибки оборачиваются громадными потерями. В связи с этим воз­никла необходимость применять для анализа экономической ситуации математические методы и вычислительную технику. Такие методы объе­диняются под общим названием математическое программирование или математическое моделирование.

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

Математическая модель задачи – это отражение оригинала в виде функций, уравнений, неравенств, цифр и т. д. Модель задачи математиче­ского программирования включает:

_{1) совокупность неизвестных величин , действуя} на которые, систему можно совершенствовать. Её называют планом задачи (вектором управления, решением, стратегией, поведением и т. д.);

2) целевую функцию (она позволяет выбирать наилучший вариант из множества возможных). Её обозначают Z = Z (х). Это может быть прибыль, объем выпуска или реализация продукции, затраты производства, издержки и т. д.;

3) условия (или систему ограничений), налагаемые на неизвестные величины; эти условия могут быть материальные, финансовые, трудовые ресурсы, возможности технического и научного потенциала. Математические ограничения выражаются в виде уравнений и нера­венств. Их совокупность образует область допустимых решений (ОДР). Если ОДР обозначим за q, то модель задачи математического программи­рования примет вид:

Или в развернутом виде: найти план = (х₁ . х_n), доставляющий экстремальное значение це­левой функции z при ограничениях _i (х₁ . х_n) =  B_i. Из экономиче­ских соображений на план задачи налагаются условия неотрицательности х_i  0, иногда целочисленности. Допустимый план, доставляющий функ­ции цели экстремальное значение, называется оптимальным.

Начало ма­тема­тического программирования было положено в 1939 г. советским математиком-экономистом Л. В. Канторовичем. Составными частями ма­тематического программирования являются линейное, нелинейное, дискретное, ди­намическое программирование, а также теория игр и графов.

Источник

Лекция 1 Математическое программирование

Математическое программирование – это область математики, разработанная теории и численные методы, решением многомерных, экстремальных задач с ограничениями.

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

Функцию, экстремальное значение которой необходимо найти в условиях экономических возможностей, называют целевой или показателем эффективности (критерий оптимальности).

Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель. Математическая модель задачи – это отражение оригиналов в виде функций, уравнений, неравенств и др. математических объектов. Модель задачи математического программирования включает в себя:

1. совокупность неизвестных величин х=(х₁,х₂. х_n), их называют планом задачи.
2. Целевую функцию (показатель эффективности, критерий оптимальности). Целевая функция позволяет выбирать наилучший вариант из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение Z=Z(x).
3. Условие или систему ограничений, которая накладывается на неизвестные величины. Эти условия следуют из ограниченности ресурсов, которыми располагает общество в любой момент времени, а также из необходимости удовлетворения насущных потребностей из условий производительных и технологических процессов.

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

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

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

х _i => 0 , Z(x*) = Z*(оптимальный план)

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

В зависимости от особенностей целевой функции, а также функций, задающей ограничения, задача математического программирования делится на ряд типов:

1. Если целевая функция и функции системы ограничений, если они линейные относительно входящих неизвестных x_i ,то такой раздел называется линейным. Методы и модели линейного программирования широко используются при оптимизации процессов во всех областях народного хозяйства. При разработке производственной программы предприятия, при определении наилучшего ассортимента выпускаемой продукции, задачах перспективного, текущего и оперативного планирования. Особенно широкое применение методов и моделей линейного программирования получили при решении экономии ресурсов производственно-транспортных и др. задач. Начало линейного программирования положил Канторович.

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

3. Если на все или некоторые переменные накладывается условия дискретности, например, целочисленности, также задачи рассматриваются в дискретном программировании. Методами целочисленного программирования решаются задачи с логическими условиями, с разрывной целевой функцией. Это задачи о контейнерных перевозках, о маршрутизации, о расширении производственно-складской структур.

Z( x )=∑ Z_j (x_j ) – аддитивный вид

Z( x )= П Z _j(x _j ) – мультипликативный

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

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

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

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

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

Источник