04. Каноническая задача линейного программирования

Для построения общего метода решения ЗЛП разные формы ЗЛП должны быть приведены к некоторой стандартной форме, называемой канонической задачей линейного программирования (КЗЛП).

В канонической форме

1. все функциональные ограничения записываются в виде равенств с неотрицательной правой частью;

2. все переменные неотрицательны;

3. целевая функция подлежит максимизации.

Таким образом, КЗЛП имеет вид:

(3.10)

, (3.11)

(3.12)

Или в векторно-матричной форме

(3.13)

(3.14)

(3.15)

КЗЛП является частным случаем общей ЗЛП при m1 = 0, p = n

Любую ЗЛП можно привести к каноническому виду, используя следующие правила:

А) максимизация целевой функции = c1x1+…+cnxn равносильна минимизации целевой функции:=-c1x1 -…-cnxn;

Б) ограничение в виде неравенства, например, 3Х1 + 2Х2 – Х3 £ 6, может быть приведено к стандартной форме 3Х1 + 2Х2 – Х3 + Х4 = 6, где новая переменная Х4 неотрицательна. Ограничение Х1 – Х2 + 3Х3 ³ 10 может быть приведено к стандартной форме Х1 – Х2 + 3Х3 – – Х5 = 10, где новая переменная Х5 неотрицательна;

В) если некоторая переменная ХK может принимать любые значения, а требуется, чтобы она была неотрицательная, ее можно привести к виду , где ³ 0 и ³ 0.

< Предыдущая		Следующая >