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

Пусть:

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.

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

Дата добавления: 2014-01-04