Лекция: Линейное программирование.

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

В самом общем виде задача математически записывается так:

;, (3.1)

где ;

– область допустимых значений переменных ;

– целевая функция.

Для того чтобы решить задачу оптимизации, достаточно найти её оптимальное решение, т.е. указать такое, что при любом, или для случая минимизации при любом .

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

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

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

1. Задачи линейного программирования, если и линейны.

2. Задачи целочисленного программирования, если ставится условие целочисленности переменных .

3. Задачи не линейного программирования, если форма носит не линейный характер.