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

Экономико-математические модели оптимизации.

Понятие оптимизационных задач и оптимизационных моделей

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

Оптимизационные задачи (ОЗ) решаются с помощью оптимизационных моделей (ОМ) методами математического программирования.

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

• управляемых переменных;

• неуправляемых переменных;

• формы функции (вида зависимости между ними).

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

Если система ограничений несовместима, то область допустимых решений является пустой. Ограничения подразделяются:

a) линейные (I и II) и нелинейные (III и IV) рис.2.1.

b) детерминированные (A, B) и стохастические (Сi) рис.2.2.

 

х₂х₂

Сi

III

 

I IV

      В А

 

 

II

     х₁х₁

Рис.2.1. Линейные и нелинейные ограничения

Рис. 2.2. детерминированные и стохастические ограничения

Стохастические ограничения являются возможными вероятностными и случайными.

ОЗ решаются методами математического программирования, которые подразделяются на:

• линейное программирование;

• нелинейное программирование;

• динамическое программирование;

• целочисленное программирование;

• выпуклое программирование;

• исследование операций;

• геометрическое программирование и др.

Главная задача математического программирования – это нахождение экстремума функции при ограничениях в форме уравнения и неравенств.

Далее будем рассматривать ОЗ, решаемые методами линейного программирования.

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

Пусть:

b_i – количество ресурса вида i (i =1,2,…, m);

а_i,j – норма расхода i-го ресурса на единицу j -го вида продукции;

х_j – количество продукции вида j (j =1,2,…, n);

с_j – прибыль (доход) от единицы этой продукции (в задачах на min – себестоимость продукции).

Тогда ОЗ линейного программирования (ЛП) в общем виде может быть сформулирована и записана следующим образом:

Найти переменные х_j (j =1,2,…, n), при которых целевая функция

,            (2.1)

была бы максимальной (минимальной), не нарушая следующих ограничений:

                             (2.2)

Все три случая можно привести к так называемой канонической форме, введя дополнительные переменные

              (2.3)

где k – количество дополнительных переменных, и условие неограниченности искомых переменных: х_j ≥0.

В канонической форме ставится задача на максимум некоторой линейной функции F, а ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи X₁,X₂,..,X_n являются неотрицательными:

            (2.4)

x₁ ³ 0, x₂ ³ 0,...., x_n ³ 0.

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

a₁₁x₁ + a₁₂x₂ +... + a_1nx_n £ b₁

Вводим переменную x_n+1 = b₁ - a₁₁x₁ - a₁₂x₂ -... - a_1nx_n.

Тогда неравенство запишется в виде

a₁₁x₁ + a₁₂x₂ +... + a_1nx_n + x_n+1 = b_1.

В каждое из неравенств вводится своя “уравнивающая” переменная, после чего система ограничений становится системой уравнений.

Наконец, если исходная задача была задачей на минимум, то введением новой целевой функции F₁ = -F мы преобразуем нашу задачу на минимум функции F в задачу на максимум функции F₁.

В стандартной форме задача линейного программирования является задачей на максимум линейной целевой функции. Система ограничений ее состоит из линейных неравенств типа "£".Все переменные задачи неотрицательны:

                    (2.5)

x₁ ³ 0, x₂ ³ 0,...., x_n ³ 0.

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

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

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