Пусть:

bt — количество ресурса вида / (/ = 1, 2, ..., /я);

a-ij— норма расхода /-того ресурса на единицу у-того вида

продукции;

Xj — количество продукции вида у (/ = 1, 2, ..., п);

Cj — прибыль (доход) от единицы этой продукции (в задачах

на минимум — себестоимость продукции).

Тогда 03 линейного программирования (ЛП) в общем виде

может быть сформулирована и записана следующим образом:

Найти переменные х/ (/ = 1,2, ..., п), при которых целевая

функция

п

F(x) = ^CJXJ -» max (min),

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

ограничений:

п

£я,у xj <bh / = 1, 2, ...9mi9

y=i

n

2^ а» Xi = bj, i = m\ + 1, m\ + 2,..., rri2,

я

X^y Xj > bh i = m2 + 1, /w2 + 2,..., m.

y=i

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

форме, введя дополнительные переменные

п+к

T,ayXj =bh i = 1,2, ...,m,

У=1

где & — количество дополнительных переменных, и условие

неотрицательности искомых переменных: Xj > 0.

В результате решения задачи находится некий план (программа)

работы некоторого предприятия. Отсюда и появилось слово

«программирование». Слово «линейное» указывает на линейный

характер зависимости как в целевой функции, так и в системе

ограничений. Следует еще раз подчеркнуть, что задача обязательно

носит экстремальный характер, т.е. состоит в отыскании максимума

или минимума (экстремума) целевой функции.