1.Постановка злп.

Линейное программирование – область математики, разрабатывающая теорию и численные методы решения задач нахождения экстремума (максимума или минимума) линейной функции многих переменных при наличии линейных ограничений, т.е. линейных равенств или неравенств, связывающих эти переменные. К задачам линейного программирования приводится широкий круг вопросов планирования экономических и технико-экономических процессов, где ставится задача поиска наилучшего (оптимального) решения; само возникновение и развитие линейного программирования непосредственно связано с экономической проблематикой. По типу решаемых задач его методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений. 

2.Запишите злп в форме озлп.

Общая задача линейного программирования (ОЗЛП) может быть сформулирова-

на следующим образом: найти значения переменных Х1, Х2,…,Хn, максимизирующие ли-нейную форму

f (x1,x2,…,xn) = c1x1+…+cnxn (3.1)

при условиях

n

∑a_ij x_j ≤ b _i = 1,…, m1 (m1 ≤ m) , (3.2)

j=1

n

∑a_ij x_j = b_i = m1 + 1,…, m ,

j=1

x_j ≥ 0, j = 1,…, p (p ≤ n) . (3.3)

Соотношения (3.2) и (3.3) будем называть соответственно функциональными и

прямыми ограничениями задачи линейного программирования (ЗЛП).

Значения переменных Хj

(j = 1, 2,…, n) можно рассматривать как компоненты неко-

торого вектора Х = (Х1, Х2,…, Хn) пространства Еn.

3.Запишите ЗЛП в формОснЗЛП.

ЗЛП во многих случаях оказывается ассоциированной с задачей распределитель-ного типа или с задачей производственного планирования, в которой требуется распре-

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

Такую ЗЛП можно поставить следующим образом: найти значения переменных

Х1,Х2,…,Хn, максимизирующие линейную форму

n

f (x_) = ∑ cj xj (3.4)

j=1

при условиях

n

∑aij xj ≤ bi , i = 1,…, m , (3.5)

j=1

xj ≥ 0, j = 1,…, n (3.6)

или в векторно-матричной форме

f (x ) = (c, x ) → max (3.7)

A x ≤ b (3.8)

x ≥ о , (3.9)

где c = (с1, с2,…, сn); b = (b1, b2,…, bm); А = (aij) – матрицы коэффициентов ограничений

(3.5). Задача (3.4) – (3.6) или (3.7) – (3.9) называется основной ЗЛП. Основная ЗЛП является частным случаем общей ЗЛП при m1 = m, p = n.

4.Запишите злп в форме кзлп.

Для построения общего метода решения ЗЛП разные формы ЗЛП должны быть приведены к некоторой стандартной форме, называемой канонической задачей линейного программирования (КЗЛП).

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

1) все функциональные ограничения записываются в виде равенств с неотрицательной правой частью

2. все переменные неотрицательны

3. целевая функция подлежит максимизации

Таким образом,

КЗЛП имеет вид:

f(x)=∑c_j x_j →max

∑a_ijx_j =b_j, i=1,...,m

xi ≥ 0, j =1,...,n; bi ≥ 0; i =1,...,m

или в векторно-матричной форме

f (x) = (c, x) → max

Ах =b

x≥0, b≥0

КЗЛП является частным случаем общей ЗЛП при m₁ = 0, p = n

Любую ЗЛП можно привести к каноническому виду, используя следующие правила:

а) максимизация целевой функции f (x) = c1x1+...+cnxn равносильна минимизации

целевой функции: f (x) =-c1x1 -...-cnxn

б) ограничение в виде неравенства, например, 3Х1 + 2Х2 – Х3 ≤ 6, может быть приведено к стандартной форме 3Х1 + 2Х2 – Х3 + Х4 = 6, где новая переменная Х4 неотрицательна. Ограничение Х1 – Х2 + 3Х3 ≥ 10 может быть приведено к стандартной форме Х1 – Х2 + 3Х3 – – Х5 = 10, где новая переменная Х5 неотрицательна

в) если некоторая переменная Хk может принимать любые значения, а требуется, чтобы она была неотрицательная, ее можно привести к виду X = X′ − X′′,где X′ ≥0и X′′ ≥0.