Стандартная и каноническая формы задачи линейного программирования

Общая задача математического программирования. Постановка

Необходимо найти оптимальное значение целевой функции F зависящей от независимых переменных х₁, х₂… х_n при ограничениях следующего вида:

F(х₁, х₂… х_n)→opt

g₁(х₁, х₂… х_n)≤b₁ - (*) множество допустимых решений (МДР)

g₂(х₁, х₂… х_n)≤b₂

…

g_m(х₁, х₂… х_n)≤b_m

F(х₁, х₂… х_n) – целевая функция задачи.

Решением такой задачи будет вектор хⁱ=(x₁ⁱ, x₂ⁱ…x_nⁱ) ͼ МДР

Допустимое решение – это решение xⁱ, если оно ͼ МДР, т.е. на нем выполняется система ограничений (*).

хⁱ=(x₁ⁱ, x₂ⁱ…x_nⁱ) ͼ МДР

Оптимальное решение:

Х⁰=(x₁⁰, x₂⁰…x_n⁰) ͼ МДР и F(x₁⁰, x₂⁰…x_n⁰))→opt

Стандартная и каноническая формы задачи линейного программирования

Линейное программирование – это математический аппарат, разработанный для решения задач математического программирования, в которых целевая функция и ограничения являются линейными функциями своих аргументов.

∑_jС_j x_j→min - стандартная форма

∑_ja_ij x_j≤b_i, i=1,m

Замечание: Задача линейного программирования может быть сформулирована как на max, так и на min. При этом следует иметь ввиду, что max F(х₁, х₂… х_n)=-min(-F(х₁, х₂… х_n))

∑_jС_j x_j→min - каноническая форма

∑_ja_ij x_j=b_i, i=1,m

x_j≥0, j=1,n

Исходя из этой формы, задачи линейного программирования имеет канонический вид, если:

-все ограничения задачи имеют вид равенств;

-все переменные задачи неотрицательны.

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

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

2)Если переменная не неотрицательна, то ее заменяют на x=y₁-y₂, y₁ ≥0, y₂≥0