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

Пусть:

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.

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

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

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