Постановка задачі лінійного програмування

Задача лінійного програмування формулюється у такому вигляді:

Знайти такі дійсні значення змінних x =(x ₁,…, x_n), при яких функція мети

Q (x)= p ₁ x ₁+…+ p_nx_n ®min (2.3)

набуває мінімальних значень на множині точок, що задовольняють умовам

a ₁₁ x ₁+ a ₁₂ x ₂+…+ a _{1 n} x_n = b ₁,

a ₂₁ x ₁+ a ₂₂ x ₂+…+ a _{2 n} x_n = b ₂, (2.4)

…

a_{m 1} x ₁+ a_{m 2} x ₂+…+ a_mnx_n = b_m,

x ₁³0, x ₂³0, …, x_n ³0,

де a_ij, b_i, p_i Î R.

Множина, задана рівняннями та нерівностями (2.4), називається допустимою областю. Якщо після відкидання однієї з умов допустима область не зміниться, то ця умова – зайва. Допустима область може бути обмеженою та необмеженою, а у вироджених випадках – порожньою множиною. Без порушення загальності можемо вважати, що b_i ³0.

У матричному вигляді задачу (2.3), (2.4) можна записати таким чином:

Q (x)= p^Tx ®min, (2.5)

Ax = b, x ³0, (2.6)

де

, b =(b ₁,… b_m), x =(x ₁,… x_n), p =(p ₁,… p_n).

Якщо у задачі необхідно знайти максимум функції мети G (x)= p ₁ x ₁+…+ p_nx_n, то цю задачу можна звести до знаходження мінімуму функції Q (x)= - G (x)=(- p ₁) x ₁+…+(- p_n) x_n.

Якщо в умовах на множину допустимих значень є нерівність

a_{i 1} x ₁+ a_{i 2} x ₂+…+ a_inx_n £ b_i,

то її можна замінити рівністю шляхом введення додаткової змінної x_{n +1}:

a_{i 1} x ₁+ a_{i 2} x ₂+…+ a_inx_n + x_{n +1}= b_i.

Аналогічно діємо у випадку, коли нерівностей більше, одержуючи інші додаткові змінні.