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

Раздел 1. Методы исследования линейных детерминированных моделей ИО

Тема 3. ВВЕДЕНИЕ В ТЕОРИЮ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Вопросы:

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

Понятие линейного программирования. Общая форма представления задачи линейного программирования (ЗЛП).

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

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

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

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

                                                            (3.1)

при ограничениях:

                                                                      (3.2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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