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

 

Пусть:

b _i количество ресурса вида i ( i = 1, 2, ..., m );

a _{i , j} норма расхода i -того ресурса на единицу j -того вида продукции;

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

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

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

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

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

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

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

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