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

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

---Целевой функции- это математическое представление зависимости критерия оптимальности от искомых переменных. Примеры целевой функции: максимизация прибыли, минимизация себестоимости и т.д.

---Области допустимых решений

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

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

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

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

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

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

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

Пример: прямая задача – есть определенное количество ресурса i, есть норма расходов i-ресурса на производство продукта j. Продаем готовые продукты j по цене P. Цель: найти такой объем продаж или такую сбытовую цену, при которой прибыль максимизируется.

Двойственная задача – при всех вышеприведенных условиях, необходимо понять, рационально ли распределение ресурса i.

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

10-34-64