Общая и каноническая задачи линейного программирования

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

Дана система m линейных уравнений и неравенств с n переменными:

(*)

(где вместо «?» может стоять любой из знаков ; с_j,a_ij – численные коэффициенты при переменных) и функция F = c₁x₁+c₂x₂+…+c_nx_n. Функция F называется целевой функцией (а также линейной функцией, линейной формой или функцией цели), а система (*) – системой ограничений данной задачи.

Любые m переменных системы m линейных уравнений с n переменными (m<n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные n-m переменных называются неосновными (или свободными).

Решить задачу – найти значения переменных Х=(х₁,х₂,…,х_n), для которых выполняются все требования задачи. Оптимальным решением (или оптимальным планом) задачи линейного программирования называется решение Х=(х₁,х₂,…,х_n) системы ограничений, при котором целевая функция принимает оптимальное (максимальное или минимальное) значение. Базисным решением системы m линейных уравнений с n переменными называется решение, в котором все (n-m) неосновных переменных равны нулю. Базисное решение, в котором хотя бы одна из основных переменных равна нулю называется вырожденным. Допустимое базисное решение иначе еще называется опорным планом.

Стандартной (или симметричной) задачей линейного программирования называется задача определения максимума целевой функции F, при условии, что система ограничений состоит из одних неравенств вида , числа b_i – положительные.

Канонической (или основной) задачей линейного программирования называется задача определения максимума целевой функции F, при условии, что система ограничений задачи являются равенствами.

Любую задачу линейного программирования можно записать в виде канонической задачи. Нахождение минимума целевой функции F, можно заменить нахождением максимума функции – F. Ограничение – неравенство исходной задачи, имеющее вид , можно преобразовать в ограничение – равенство добавлением к его левой части дополнительной неотрицательной переменной (называемой балансовой или выравнивающей). Ограничение – неравенство исходной задачи, имеющее вид , можно преобразовать в ограничение – равенство вычитанием из его левой части дополнительной неотрицательной переменной.

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