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

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

3.1.1. Общая постановка задачи линейного программирования

Общая задача линейного программирования может быть сформулирована следующим образом: найти значения переменных Х₁, Х₂,…,Х_n, максимизирующие линейную форму f(x₁,x₂,…,x_n)= c₁x₁+…+c_nx_n при условиях

1. i= 1,…,m₁ (m₁ £ m) (1)

2. i=m₁+1,…,m (2)

3. j=1,…,p (p £ n)

Соотношения (1) и (2) будем называть соответственно функциональными и прямыми ограничениями задачи линейного программирования (ЗЛП).

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

Общая задача линейного программирования (ОЗЛП) может быть сформулирована следующим образом: найти значения переменных Х₁, Х₂,…,Хn, максимизирующие линейную форму

(x₁,x₂,…,x_n)= c₁x₁+…+c_nx_n (3.1)

при условиях

, i= 1,…,m₁ (m₁m) (3.2)

, i=m₁+1,…,m (3.3)

x_j 0, j=1,…,p (pn)

Соотношения (3.2) и (3.3) будем называть соответственно функциональными и прямыми ограничениями задачи линейного программирования (ЗЛП).

Значения переменных Хj (j=1,2,…,n) можно рассматривать как компоненты некоторого вектора =(Х₁,Х₂,…,Хn) пространства Еn.

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

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

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

= (3.4)

при условиях

, i= 1,…,m (3.5)

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

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

(3.7)

A  (3.8)

x  , (3.9)

где =(с₁,с₂,…,с_n); =(b₁,b₂,…,b_m); А=(a_ij) – матрицы коэффициентов ограничений (3.5). Задача (3.4)- (3.6) или (3.7) – (3.9) называется основной ЗЛП. Основная ЗЛП является частным случаем общей ЗЛП при m₁=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.