2. Задача составления рациона. Обобщение задачи составления рациона

Задача составления рациона

При откорме каждое животное ежедненвно должно получить не менее 9 ед. питательного вещества S1, не менее 8 ед. питательного вещества S2, , не менее 12 ед. питательного вещества S3.

Для составления рациона используют два вида корма. Содержание количества ед. питательного вещества в 1 кг каждого вида корма и стоимость 1 кг корма приведенны в табл.:

Питательные вещества	Количество ед.питательного вещества в 1 кг
	Корм 1	Корм 2
S1 S2 S3	3 1 1	1 2 6
Стоимость 1 кг	4	6

Необходимо составить дневной рацион нужной питательностью, при чем затраты на него должны быть min.

Обозначим через х1, х2 соответственно количество кг корма 1 и 2 вида в дневном рационе. Если корм 1 не используется, то х1=0, в противном случае х1> 0 ( аналагично для х2).

Задача является многовариантой, т.к х1 и х2 могут принимать бесконечное множество решений.

Z=4x1+6x2 --> min

3x1+x2≥9

X1+2x2≥8

X1+6x2≥12, х1,х2>0

Обобщение задачи составления рациона

Пусть в рационе m видов питательных веществ в количестве не менее чем b_i (i=1,n) используется n видов кормов.

Обозначим через a_ij (i=1,m j=1,n) количество ед. i – го питательного вещества, содержащегося в ед. j-го корма.

C_j –( j=1,n) стоимость единицы j-го корма

X _j (j=1,n) количество j-го корма в дневном рационе

Задача. Минимизировать стоимость затрат на дневной рацион

Z=C1x1+C2x2+…+Cjxj  min

a11x1+a12x2+…+a1nxn≥b1

a21x1+a22x2+…+a2nxn≥b2

….

am1x1+am2x2+…+amnxn≥bm

xj≥0 (j=1,n)

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

1. Задача использования сырья Z=C1x1+C2x2+…+Cnxn+0*x_n+1+0*x_n+2+…+0*x_n+m  max

a11x1+a12x2+…+a1nxn+ x_n+1=b1

a21x1+a22x2+…+a2nxn+ x_n+2=b2

….

am1x1+am2x2+…+amnxn+ x_{n+m =}bn,

где xj≥0 (j=1,n, n+1,…, n+m)

где x_n+1 (i=1,n) – дополнительные переменные, соответствующие им коэффициенты в целевой функции равны 0.

2. Задача составления рациона. Все неравенства содержащие знаки ≥, для перехода к равенству необходимо из левых частей вычесть неотрицательные дополнительные переменные.

Z=C1x1+C2x2+…+Cnxn+0*x_n+1+0*x_n+2+…+0*x_n+m  min

a11x1+a12x2+…+a1nxn- x_n+1=b1

a21x1+a22x2+…+a2nxn- x_n+2=b2

….

am1x1+am2x2+…+amnxn- x_{n+m =}bm,

Правые части неравенств/уравнений в любой системе ограничений можно считать неотрицательным, если какое-либо неравенство bn<0, то умножим его на -1 и поменяем знак неравенства.

3. Замена неравенств уравнениями. Теорема 1.

Рассмотрим линейное неравенство с n неизвестными

a₁x₁+a₂x₂+…+a_nx_n≤b (1); x _n+1 ≥0 (2);

для привед. нер. (1) к равенству необходимо к его левой части + величину x _n+1 => линейное уравнение содержит (n+1) неизвестную

a₁x₁+a₂x₂+…+a_nx_n +x _n+1=b (3)

Теорема 1. каждому решению Ẋ =(β₁ , β₂,… , β_n) линейного неравенства (1) соответствует единственное решение Ẏ=(β₁ , β₂,… , β_n, β_n+1), равенства (3) и неравенства (2) и наобарот каждому решению Ẏ=(β₁ , β₂,… , β_n, β_n+1) урав. (3) и неравенства (2) соответствует единственное решение Ẋ =(β₁ , β₂,… , β_n) неравенства (1).

Доказательство: 1. Пусть Ẋ =(β₁ , β₂,… , β_n) решение неравенства (1), тогда a₁β₁+a₂β₂+…+a_nβ_n ≤b. Перенося левую часть этого неравенствав правую и обозначая выражение в правой части в β_n+1 т. е. 0≤b – (a₁β₁+a₂β₂+…+a_nβ_n)= β_n+1 получаем, что решение Ẏ=(β₁ , β₂,… , β_n, β_n+1) удов-т ур-ию (3) и нер-ву(2).

Действ-во β_n+1≥0

a₁β₁+a₂β₂+…+a_nβ_n +β_n+1 =a₁β₁+a₂β₂+…+a_nβ_n +[ b – (a₁β₁+a₂β₂+…+a_nβ_n)] =b

2. Пусть Ẏ удовлетворяет ур. (3) и нер. (2), т.е. a₁β₁+a₂β₂+…+a_nβ_n +β_n+1 =b, тогда отбрасыв. в левой части рав-ва неотр. β_n+1 =>

a₁β₁+a₂β₂+…+a_nβ_n =b => Ẋ - решение нер. (1). Ч.т.д.

Таким образом, если система лин. огранич. задача лин. прогр. содерж. нер-во, то вводя в каждую из них свою неотриц. доп-ую переменную, её можно преобр. в систему урав. При этом в лин фун-ию каждой доп-ой переменной входит с коэф=0.