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

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

В большинстве методов решения задач линейного программирования предполагается, что система ограничений состоит из уравнений и естественных условий неотрицательности переменных. Однако при со­ставлении математических моделей экономических задач ограничения в основном формируются в системы неравенств, поэтому необходимо уметь переходить от системы неравенств к системе уравнений. Это мо­жет быть сделано следующим образом.

Возьмем, например, линейное неравенство а ₁ х ₁ + а ₂ х ₂ +... + а_п х_п ≤ b и прибавим к его левой части некоторую величину х_{п+ 1}, такую, чтобы неравенство превратилось в равенство а ₁ х ₁+ а ₂ х ₂ +... + а_п х_п+ х_{п+ 1} = b, где х_{п+ 1} =b-а ₁ х ₁ - а ₂ х ₂ - -... - а_п х_п . Неотрицательная переменная х_{n +1}≥0 называется дополнительной переменной.

Например, если в задаче использования ресурсов в левую часть каждого уравнения системы ограниченийдобавить положительную переменную х_{п+ 1}, i =1,2,..., m, то получится система уравнений-ограничений

В задаче составления рациона питания система ограничений - неравенств имеет вид

В этом случае система уравнений-ограничений получится, если в левой части каждого неравенства вычесть соответствующую неотрицательную дополнительную переменную

Полученная таким образом система уравнений-ограничений вместе с условиями неотрицательности переменных, т.е. х_j ≥ 0, j = 1, 2,..., n, и целевой функцией является канонической формой записи задачи линейного программирования.

Дополнительные переменные вводятся в целевую функцию с нулевыми коэффициентами и поэтому не влияют на ее значение.

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