Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

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




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

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, и целевой функцией является канонической формой записи задачи линейного программирования.

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

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...