 |
Каноническая форма задачи линейного программирования
|
|
|
|
В общем случае задача линейного программирования записывается так, что ограничениями являются как уравнения, так и неравенства, а переменные могут быть как неотрицательными, так и произвольно изменяющимися. В том случае, когда все ограничения являются уравнениями и все переменные удовлетворяют условию неотрицательности, задачу линейного программирования называют канонической. Она может быть представлена в координатной, векторной или матричной форме записи.
1. Каноническая задача линейного программирования в координатной записи имеет вид
F(X) = с 1 х 1 + с 2 х 2 +... + сп хп→ max (min),
Данную задачу можно записать, используя знак суммирования:
max (min),
i= 1, 2,..., m,
2. Каноническая задача линейного программирования в векторной записи имеет вид
F(X)=C·X → max (min),
A 1 x 1+ A 2 x 2+…+ An xn=A0 ,
X ≥ θ.
В данном случае введены векторы
Х =(х 1, х 2, ….,, хn), С =(с 1, с 2,…., сn),
θ =(0,0,…,0).
Здесь C·X ― скалярное произведение векторов C и X.
3. Каноническая задача линейного программирования в матричной записи имеет вид
F(X) = CX → max (min),
AX = A0 , X≥ θ,
где 
Здесь А ― матрица коэффициентов системы уравнений, Х ― матрица-столбец переменных задачи, Ао — матрица-столбец правых частей системы ограничений.
Нередко используются задачи линейного программирования, называемые симметричными, которые в матричной записи имеют вид
F(X) = CX→ max, или F(X) = CX→ min,
AX ≤A0 , X≥ θ AX ≥A0 , X≥ θ.
Приведение общей задачи линейного программирования
К канонической форме
В большинстве методов решения задач линейного программирования предполагается, что система ограничений состоит из уравнений и естественных условий неотрицательности переменных. Однако при составлении математических моделей экономических задач ограничения в основном формируются в системы неравенств, поэтому необходимо уметь переходить от системы неравенств к системе уравнений. Это может быть сделано следующим образом [5].
|
|
|
Возьмем, например, линейное неравенство а 1 х 1+ а 2 х 2 +... + ап хп ≤ b и прибавим к его левой части некоторую величину хп+ 1,такую, чтобы неравенство превратилось в равенство а 1 х 1+ а 2 х 2 +... + ап хп+ хп+ 1 = b, где хп+ 1 =b-а 1 х 1 - а 2 х 2 -... - ап хп. Неотрицательная переменная хn +1≥0 называется дополнительной переменной.
Следующая теорема дает основание для возможности такого преобразования.
Теорема 1. Каждому решению β=(β1, β2, … β n) неравенства а 1 х 1 +а 2 х 2 +... + ап хп≤ b соответствует единственное решение 
=(β1, β2, … β n , β n+ 1) уравнения а 1 х 1+ а 2 х 2 +...+ апхп+хп+ 1= b, и неравенства хn+ 1 ≥ 0, и, наоборот, каждому решению уравнения и неравенства соответствует единственное решение β неравенства.
Доказательство. Пусть β=(β1, β2, … β n) — решение неравенства а 1 х 1 +а 2 х 2 +... + ап хп≤b. Тогда а 1β1 + а 2β2 +...+ап β п≤b или 0≤ b- (а 1β1 +а 2β2 +.. + +ап β п)=β n+ 1.
Подставив в уравнение вместо переменных значения β1, β2, … β n , β n+ 1, получим:
а 1β1 +а 2β2 +...+ап β п +β n+ 1= а 1β1 +а 2β2 +...+ап β п+b- (а 1β1 +а 2β2 +...+ап β п)= b.
Таким образом, решение удовлетворяет уравнению и неравенству. Значит, доказана первая часть теоремы. Аналогично доказывается обратное.
Например, если в задаче использования ресурсов в левую часть каждого уравнения системы ограничений 
добавить положительную переменную хп+ 1, i =1,2,..., m, то получится система уравнений-ограничений 
В задаче составления рациона питания система ограничений - неравенств имеет вид 
В этом случае система уравнений-ограничений получится, если в левой части каждого неравенства вычесть соответствующую неотрицательную дополнительную переменную 
|
|
|
Полученная таким образом система уравнений-ограничений вместе с условиями неотрицательности переменных, т.е. хj ≥ 0, j = 1, 2,..., n, и целевой функцией является канонической формой записи задачи линейного программирования.
Дополнительные переменные вводятся в целевую функцию с нулевыми коэффициентами и поэтому не влияют на ее значение.
|
|
|
