Вопрос: Постановка общей задачи ЛП.

3 Вопрос: Постановка общей задачи ЛП.

Основные понятия и определения. Каноническая форма задачи ЛП.

Общая задача. Найти максимальное значение линейной

целевой функции

z= c1x1 + c2x2 + ... + cnxn (1.1)

при линейных ограничениях

а11х1 +а12х2+…+а1nxn≤b1

а21х1 +а22х2+…+а2nxn≤b2 (1.2)

………………………………

k1х1 +аk2х2+…+аknxn≤bk

xj≥0, j=1, n={1,2,…,n},

где cj, aij, bi – действительные числа, xj – переменные.

Опр 1.Совокупность чисел x= (x1 , x2 ,..., xn ), удовлетворяющих ограничениям (1.2), называется допустимым решением или планом. Опр 2. план x^*=(x₁^*,x₂^*,….,x_n^*),

При котором целевая функция (1.1) принимает свое максимальное значение, называется оптимальным.

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

1. требуется найти максимум целевой функции; 2. система ограничений содержит только равенства; 3. правые части системы ограничений неотрицательны.

Переход от общей формы к канонической:

1. если в задаче требуется найти минимум целевой функции, то вводим новую целевую функцию z1 = − z, тогда max z1 = -min z; 2. чтобы перейти от неравенства к равенству в системе ограничений, необходимо прибавить (вычесть) дополнительную не отрицательную переменную к левой части неравенства; 3. если в правой части системы ограничений имеются отрицательные числа, то необходимо умножить на "–1" обе части равенства, в котором в правой части стоит отрицательное число.